(57)【特許請求の範囲】
【請求項１】
複数の読み出し要求をキューとして保持し、読み出し要求が入力される毎にその読み出し要求とともに保持された読み出し要求を並び換え、キューから読み出し要求を順に取り出して要求されたデータをディスクから出力するディスク制御装置であって、ディスクのデータ読出を要求する読み出し要求を並び換え可能なキューとして一時的に保持するキュー手段と、キュー内の読み出し要求毎に、キューにおける順位に応じて決まる読み出し完了までの遅延時間に対して、さらにどれだけの遅延を与えることができるかを表す許容時間を保持する許容時間保持手段と、読み出し要求が入力される毎に、キュー内の各読み出し要求の許容時間に基づいて、入力された読み出し要求とともにキュー内の読み出し要求を並び換える並び換え制御手段と、並び換えが実行される毎に、入力された読み出し要求について、キューにおける順位に応じて前記許容時間を算出して許容時間保持手段に格納する許容時間算出手段と、並び換えによって、キューにおける順位が後順位に変更された各読み出し要求について許容時間保持手段の各許容時間を、順位の変更に起因する遅延時間だけ小さい値に更新する許容時間更新手段とを備え、前記許容時間算出手段は、並び換え制御手段によりキューが並び換えられる毎に、入力された読み出し要求について、キュー内の挿入された位置から先頭まで進み、さらに取り出されてディスクのデータ読み出しが完了するまでに要すると予想される遅延時間を算出する第１の算出手段と、入力された読み出し要求が並び換え制御手段に入力された時点から対応するデータがディスクから出力されるまでに遅延時間として許される最大の限界許容遅延時間から、第１の算出手段により算出された遅延時間を減算することにより、入力された読み出し要求に対する許容時間を算出する第２の算出手段とを備えることを特徴とするディスク制御装置。
【請求項２】
前記並び換え制御手段は、読み出し要求が入力される毎に、入力された読み出し要求がキューに挿入された場合に、ディスクのヘッドシーク方向を一定に保つことができるキュー内の位置を探索する探索手段と、探索された位置に入力された読み出し要求が挿入された場合に、その読み出し要求の後順位になる読み出し要求の許容時間が０以下になるか否かを判定する時間判定手段と、許容時間が０以下にならないと判定されたときの探索された位置を挿入すべき位置と決定する位置決定手段と、決定された位置に入力された読み出し要求を挿入するように、入力された読み出し要求とともにキュー内の読み出し要求を並び換える並び換え手段とを備えることを特徴とする請求項１記載のディスク制御装置。
【請求項３】
前記読み出し要求は、読み出すべきデータの論理アドレスと、データのサイズとを含み、前記キュー手段は、キュー内の各読み出し要求について、キュー内の順位と、シーク直後からデータを読み取って出力するまでに要する転送時間と、対応するデータが存在するディスク上のトラック位置と、１つ前の順位のデータのトラック位置から当該順位のトラック位置までのヘッド移動に要するシーク時間とを対応させて保持するキューテーブルを備え、前記並び換え制御手段はさらに、入力された読み出し要求に含まれる論理アドレスに基づいて対応するデータが存在するディスク上のトラックの位置を算出するトラック位置算出手段と、入力された読み出し要求に含まれるデータサイズに基づいてシーク直後からデータを読み取って出力するまでに要するデータ転送時間を算出するデータ転送時間算出手段と、並び換え手段によりキューが並び換えられる毎に、キュー内の順位が変更された読み出し要求について、キューテーブルのトラック位置に基づいてシーク時間を算出してキューテーブルに格納するシーク時間算出手段とを備え、前記探索手段は、キュー内の読み出し要求の順位を末尾から順に１つずつ指定する順位指定手段と、順位が指定される毎に、トラック位置算出手段により算出されたトラック位置に対して、キューの末尾の読み出し要求のトラック位置と、指定された順位の読み出し要求のトラック位置とが同じ方向にあるかを判定する方向判定手段とを備え、前記並び換え手段は、決定された位置に挿入するようにキューテーブルの順位を更新するとともに、トラック位置算出手段に算出されたトラック位置、データ転送時間算出手段により算出されたデータ転送時間を入力された読み出し要求に対応させてキューテーブルに格納することを特徴とする請求項２記載のディスク制御装置。
【請求項４】
前記並び換え制御手段は、読み出し要求が入力される毎に、入力された読み出し要求がキューに挿入された場合に、比較的小さい距離のヘッドシーク逆行を許してディスクのヘッドシーク方向をほぼ一定に保つことができるキュー内の位置を探索する探索手段と、探索された位置に入力された読み出し要求が挿入された場合に、その読み出し要求の後順位になる読み出し要求の許容時間が０以下になるか否かを判定する時間判定手段と、許容時間が０以下にならないと判定されたときの探索された位置を挿入すべき位置と決定する位置決定手段と、決定された位置に入力された読み出し要求を挿入するように、入力された読み出し要求とともにキュー内の読み出し要求を並び換える並び換え手段とを備えることを特徴とする請求項１記載のディスク制御装置。
【請求項５】
前記読み出し要求は、読み出すべきデータの論理アドレスと、データのサイズとを含み、前記キュー手段は、キュー内の各読み出し要求について、キュー内の順位と、シーク直後からデータを読み取って出力するまでに要する転送時間と、対応するデータが存在するディスク上のトラック位置と、１つ前の順位のデータのトラック位置から当該順位のトラック位置までのヘッド移動に要するシーク時間とを対応させて保持するキューテーブルを備え、前記並び換え制御手段はさらに、入力された読み出し要求に含まれる論理アドレスに基づいて対応するデータが存在するディスク上のトラックの位置を算出するトラック位置算出手段と、入力された読み出し要求に含まれるデータサイズに基づいてシーク直後からデータを読み取って出力するまでに要するデータ転送時間を算出するデータ転送時間算出手段と、並び換え手段によりキューが並び換えられる毎に、キュー内の順位が変更された読み出し要求について、キューテーブルのトラック位置に基づいてシーク時間を算出してキューテーブルに格納するシーク時間算出手段とを備え、前記探索手段は、キュー内の読み出し要求の順位を末尾から順に１つずつ指定する順位指定手段と、順位が指定される毎に、トラック位置算出手段により算出されたトラック位置に対して、キューの末尾の読み出し要求のトラック位置と、指定された順位の読み出し要求のトラック位置の前後数トラックの何れかとが同じ方向にあるかを判定する方向判定手段とを備え、前記並び換え手段は、決定された位置に挿入するようにキューテーブルの順位を更新するとともに、トラック位置算出手段に算出されたトラック位置、データ転送時間算出手段により算出されたデータ転送時間を入力された読み出し要求に対応させてキューテーブルに格納することを特徴とする請求項４記載のディスク制御装置。
【請求項６】
前記時間判定手段は、方向判定手段により同じ方向にあると判定されたとき、順位指定手段に指定された順位の読み出し要求に対応する許容時間から、データ転送時間を減算し、減算結果が０以下になるか否かを判定し、前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下にならないと判定された場合、順位指定手段に指定された次の順位について、方向判定手段が同じ方向にないと判定した場合には、その２つの順位の読み出し要求の間を入力された読み出し要求を挿入すべき位置と決定することを特徴とする請求項３又は５記載のディスク制御装置。
【請求項７】
前記第１の算出手段は、並び換え手段によりキューが並び換えられる毎に、入力された読み出し要求について、キュー内の全ての先順位の読み出し要求のデータ転送時間及びシーク時間を加算することにより前記遅延時間を算出し、前記許容時間更新手段は、並び換えによって、キューにおける順位が後順位に変更された各読み出し要求について、許容時間保持手段の各許容時間を、前記データ転送時間だけ小さい値に更新することを特徴とする請求項６記載のディスク制御装置。
【請求項８】
前記限界許容遅延時間は、全ての読み出し要求に共通の値が予め定められていることを特徴とする請求項７記載のディスク制御装置。
【請求項９】
前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定された場合には、キューの末尾を挿入すべき位置と決定することを特徴とする請求項８記載のディスク制御装置。
【請求項１０】
前記限界許容遅延時間は、入力される読み出し要求に含まれることを特徴とする請求項７記載のディスク制御装置。
【請求項１１】
前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定された場合には、キューの末尾を挿入すべき位置と決定し、前記読み出し要求は、最大許容時間が短く廃棄されてもよい優先要求と、それ以外の要求とに分類され、前記並び換え判定制御手段はさらに、入力された読み出し要求が優先要求であるかどうかを判別する優先要求判別手段と、優先要求であると判別され、かつ、位置決定手段により末尾に挿入すると決定された場合、キューテーブル内の全ての読み出し要求のデータ転送時間及びシーク時間を加算した加算結果がその優先要求の最大許容時間よりも大きければ、廃棄すると判定する廃棄判定手段と、廃棄すると判定された優先要求を廃棄するとともに、優先要求に対する並び換え制御手段の動作を禁止する廃棄手段とを備えることを特徴とする請求項１０記載のディスク制御装置。
【請求項１２】
前記許容時間保持手段は、さらにキュー内の読み出し要求毎に、キューの内の直前に他の読み出し要求を挿入できないことと、シーク方向が逆になることとを表す禁止フラグを保持し、前記並び換え手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定され、かつ、位置決定手段によりキューの末尾が挿入すべき位置と決定された場合には、並び換え後に末尾に挿入された読み出し要求の直前順位の読み出し要求に対応する禁止フラグをセットすることを特徴とする請求項９又は１１記載のディスク制御装置。
【請求項１３】
前記並び換え制御手段はさらに、読み出し要求が入力されたとき、許容時間保持手段内の禁止フラグがセットされていて、かつ、キューの末尾に最も近い読み出し要求を検出する禁止フラグ検出手段と、末尾の読み出し要求のトラック位置に対して、入力された読み出し要求のトラック位置と、禁止フラグ検出手段によって検出された読み出し要求のトラック位置とが同じ方向にあるか否かを判定する同一方向判定手段とを備え、前記位置決定手段は、同一方向判定手段により同じ方向にないと判定された場合に、入力された読出要求をキューの末尾を挿入すべき位置と決定し、前記探索手段は、同一方向判定手段により同じ方向にあると判定された場合に、前記探索を行うことを特徴とする請求項１２記載のディスク制御装置。
【請求項１４】
前記ディスク制御装置は、ビデオサーバに用いられ、前記限界許容遅延時間は、ビデオサーバのユーザ側においてリアルタイム再生に要求される遅延時間であることを特徴とする請求項１乃至１３記載の何れかディスク制御装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ランダムに発生する読み出し要求に対して、シーク時間を減少させて読み出しの処理能力を向上させたディスク制御装置に関し、特に、一定の速度で発生する読出要求をリアルタイムに処理することを必要とするビデオサーバーに使用されるディスク制御装置に関する。
【０００２】
【従来の技術】
近年、映像データと音声データを含むマルチメディアデータを記憶するディスク装置を備え、通信線を介して接続された複数のユーザに対してデータを供給するビデオサーバが実用化されている。ビデオサーバから供給されるデータによりユーザは、見たいときに希望する映画を見ることができる。
【０００３】
ビデオサーバにおいては、複数のユーザに対してデータのリアルタイムに出力する必要があり、効率よくディスク上のデータを読み出す技術が必要とされる。ディスク装置を効率的に読み出す技術として、ディスク装置のヘッドシークの方向を一定にするようにデータの読出順序を入れ換える技術がある。
図１２は、従来のディスク制御装置の構成を示すブロック図である。同図においてディスク制御装置は、ハードディスク１００、並び替え制御部１０２、ハードディスク１０３とからなる。
【０００４】
ハードディスク１００は、複数種類の映画を表すマルチメディアデータを一定のサイズ毎に分割して記憶する。
キュー管理部１０１は、データの読み出し要求をキューとして保持し、ハードディスク１００に対して順に読み出し要求を出力する。
並び換え制御部１０２は、読み出し要求を受け取る毎にキュー管理部１０１に一旦登録し、さらに、一定時間毎にキュー管理部１０１に登録されている全て読み出し要求を、ディスク装置のヘッドシーク方向が一定になるように並び換える。キュー管理部１０１は、並び換えられた要求を順にハードディスク１００に出力する。これにより、ハードディスク１００における読み出し要求に対するヘッドの平均シーク時間の短縮が図られている。
【０００５】
【発明が解決しようとする課題】
しかしながら上記従来の構成では、読み出し要求が発生してからデータが出力されるまでの遅延時間がばらついてしまうという問題があった。
より詳しくいうと、ビデオサーバから出力されるデータは、動画として再生できるように所定の時間毎に連続して出力される必要がある。もし所定の時間内に次のデータが出力されなければ、例えば映像が飛んだり、音声が途切れたりして映画として正常に再生できなくなる。そのため、ディスク装置においては読み出し要求が発生してからデータが出力されるまでの遅延時間として許容される範囲（以下、限界限界許容遅延時間と呼ぶ）がある。従来技術では、この限界許容遅延時間を考慮していなかった。
【０００６】
例えば従来技術において、上記一定時間（並び換えを行う間隔）を限界許容遅延時間よりも十分短く設定すれば、限界許容遅延時間内にデータ出力することができる。
しかし、この場合には並び換えの対象となる読み出し要求の個数が少なくなるので、シーク時間を短縮という効果が犠牲になってしまい、効率よく読み出すことができないという問題があった。逆に、上記一定時間を許容時間よりも長く設定すれば、並び換えの対象となる読み出し要求の個数が多くなるので、シーク時間を短縮という効果が十分に得られるものの、この場合には並び換えの結果、限界許容遅延時間を越えてしまう位置に移動させられる読み出し要求が生じてしまうという問題があった。
【０００７】
上記のように、従来技術ではディスクの読み出し効率を向上させることと、限界許容遅延時間を守ることとはトレードオフの関係にある。したがって、特に、読み出し要求が、連続的に発生する場合や、バースト的に起こる場合には上記一定時間を適切に設定することは難しい。
上記課題に鑑み本発明は、読み出し要求が発生してからデータが出力されるまでに要求される限界許容遅延時間を満たしつつ、効率よくアクセスするディスク制御装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記課題を解決するため、請求項１の発明は、次の3つの構成上の特徴を備える。
1番目は、複数の読み出し要求をキューとして保持し、読み出し要求が入力される毎にその読み出し要求とともに保持された読み出し要求を並び換え、キューから読み出し要求を順に取り出して要求されたデータをディスクから出力するディスク制御装置であって、ディスクのデータ読出を要求する読み出し要求を並び換え可能なキューとして一時的に保持するキュー手段と、キュー内の読み出し要求毎に、キューにおける順位に応じて決まる読み出し完了までの遅延時間に対して、さらにどれだけの遅延を与えることができるかを表す許容時間を保持する許容時間保持手段と、読み出し要求が入力される毎に、キュー内の各読み出し要求の許容時間に基づいて、入力された読み出し要求とともにキュー内の読み出し要求を並び換える並び換え制御手段とを備えている点である。
【０００９】
第2の構成上の特徴は、並び換えが実行される毎に、入力された読み出し要求について、キューにおける順位に応じて前記許容時間を算出して許容時間保持手段に格納する許容時間算出手段と、並び換えによって、キューにおける順位が後順位に変更された各読み出し要求について許容時間保持手段の各許容時間を、順位の変更に起因する遅延時間だけ小さい値に更新する許容時間更新手段とを備えている点である。
【００１０】
第３の構成上の特徴は、前記許容時間算出手段が、並び換え制御手段によりキューが並び換えられる毎に、入力された読み出し要求について、キュー内の挿入された位置から先頭まで進み、さらに取り出されてディスクのデータ読み出しが完了するまでに要すると予想される遅延時間を算出する第１の算出手段と、入力された読み出し要求が並び換え制御手段に入力された時点から対応するデータがディスクから出力されるまでに遅延時間として許される最大の限界許容遅延時間から、第１の算出手段により算出された遅延時間を減算することにより、入力された読み出し要求に対する許容時間を算出する第２の算出手段とを備えている点である。
【００１１】
請求項２の発明は請求項１に対して、前記並び換え制御手段が、読み出し要求が入力される毎に、入力された読み出し要求がキューに挿入された場合に、ディスクのヘッドシーク方向を一定に保つことができるキュー内の位置を探索する探索手段と、探索された位置に入力された読み出し要求が挿入された場合に、その読み出し要求の後順位になる読み出し要求の許容時間が０以下になるか否かを判定する時間判定手段と、許容時間が０以下にならないと判定されたときの探索された位置を挿入すべき位置と決定する位置決定手段と、決定された位置に入力された読み出し要求を挿入するように、入力された読み出し要求とともにキュー内の読み出し要求を並び換える並び換え手段とを備えている。
【００１２】
請求項３の発明は請求項２に対して、前記読み出し要求は、読み出すべきデータの論理アドレスと、データのサイズとを含み、前記キュー手段は、キュー内の各読み出し要求について、キュー内の順位と、シーク直後からデータを読み取って出力するまでに要する転送時間と、対応するデータが存在するディスク上のトラック位置と、１つ前の順位のデータのトラック位置から当該順位のトラック位置までのヘッド移動に要するシーク時間とを対応させて保持するキューテーブルを備え、前記並び換え制御手段はさらに、入力された読み出し要求に含まれる論理アドレスに基づいて対応するデータが存在するディスク上のトラックの位置を算出するトラック位置算出手段と、入力された読み出し要求に含まれるデータサイズに基づいてシーク直後からデータを読み取って出力するまでに要するデータ転送時間を算出するデータ転送時間算出手段と、並び換え手段によりキューが並び換えられる毎に、キュー内の順位が変更された読み出し要求について、キューテーブルのトラック位置に基づいてシーク時間を算出してキューテーブルに格納するシーク時間算出手段とを備え、前記探索手段は、キュー内の読み出し要求の順位を末尾から順に１つずつ指定する順位指定手段と、順位が指定される毎に、トラック位置算出手段により算出されたトラック位置に対して、キューの末尾の読み出し要求のトラック位置と、指定された順位の読み出し要求のトラック位置とが同じ方向にあるかを判定する方向判定手段とを備え、前記並び換え手段は、決定された位置に挿入するようにキューテーブルの順位を更新するとともに、トラック位置算出手段に算出されたトラック位置、データ転送時間算出手段により算出されたデータ転送時間を入力された読み出し要求に対応させてキューテーブルに格納する。
【００１３】
請求項４の発明は請求項１に対して、前記並び換え制御手段が、読み出し要求が入力される毎に、入力された読み出し要求がキューに挿入された場合に、比較的小さい距離のヘッドシーク逆行を許してディスクのヘッドシーク方向をほぼ一定に保つことができるキュー内の位置を探索する探索手段と、探索された位置に入力された読み出し要求が挿入された場合に、その読み出し要求の後順位になる読み出し要求の許容時間が０以下になるか否かを判定する時間判定手段と、許容時間が０以下にならないと判定されたときの探索された位置を挿入すべき位置と決定する位置決定手段と、決定された位置に入力された読み出し要求を挿入するように、入力された読み出し要求とともにキュー内の読み出し要求を並び換える並び換え手段とを備えている。
【００１４】
請求項５の発明は請求項４に対して、前記読み出し要求は、読み出すべきデータの論理アドレスと、データのサイズとを含み、前記キュー手段は、キュー内の各読み出し要求について、キュー内の順位と、シーク直後からデータを読み取って出力するまでに要する転送時間と、対応するデータが存在するディスク上のトラック位置と、１つ前の順位のデータのトラック位置から当該順位のトラック位置までのヘッド移動に要するシーク時間とを対応させて保持するキューテーブルを備え、前記並び換え制御手段はさらに、入力された読み出し要求に含まれる論理アドレスに基づいて対応するデータが存在するディスク上のトラックの位置を算出するトラック位置算出手段と、入力された読み出し要求に含まれるデータサイズに基づいてシーク直後からデータを読み取って出力するまでに要するデータ転送時間を算出するデータ転送時間算出手段と、並び換え手段によりキューが並び換えられる毎に、キュー内の順位が変更された読み出し要求について、キューテーブルのトラック位置に基づいてシーク時間を算出してキューテーブルに格納するシーク時間算出手段とを備え、前記探索手段は、キュー内の読み出し要求の順位を末尾から順に１つずつ指定する順位指定手段と、順位が指定される毎に、トラック位置算出手段により算出されたトラック位置に対して、キューの末尾の読み出し要求のトラック位置と、指定された順位の読み出し要求のトラック位置の前後数トラックの何れかとが同じ方向にあるかを判定する方向判定手段とを備え、前記並び換え手段は、決定された位置に挿入するようにキューテーブルの順位を更新するとともに、トラック位置算出手段に算出されたトラック位置、データ転送時間算出手段により算出されたデータ転送時間を入力された読み出し要求に対応させてキューテーブルに格納する。
【００１５】
請求項６の発明は請求項３又は５に対して、前記時間判定手段が、方向判定手段により同じ方向にあると判定されたとき、順位指定手段に指定された順位の読み出し要求に対応する許容時間から、データ転送時間を減算し、減算結果が０以下になるか否かを判定し、前記位置決定手段が、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下にならないと判定された場合、順位指定手段に指定された次の順位について、方向判定手段が同じ方向にないと判定した場合には、その２つの順位の読み出し要求の間を入力された読み出し要求を挿入すべき位置と決定する。
【００１６】
請求項７の発明は請求項６に対して、前記第１の算出手段が、並び換え手段によりキューが並び換えられる毎に、入力された読み出し要求について、キュー内の全ての先順位の読み出し要求のデータ転送時間及びシーク時間を加算することにより前記遅延時間を算出し、前記許容時間更新手段が、並び換えによって、キューにおける順位が後順位に変更された各読み出し要求について、許容時間保持手段の各許容時間を、前記データ転送時間だけ小さい値に更新する。
【００１７】
請求項８の発明は請求項７に対して、前記限界許容遅延時間は、全ての読み出し要求に共通の値が予め定められている。請求項１１の発明は請求項１０に対して、前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定された場合には、キューの末尾を挿入すべき位置と決定する。
【００１８】
請求項１０の発明は請求項７に対して、前記限界許容遅延時間は、入力される読み出し要求に含まれる。請求項１３の発明は請求項１２に対して、前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定された場合には、キューの末尾を挿入すべき位置と決定し、前記読み出し要求は、最大許容時間が短く廃棄されてもよい速度的な優先要求と、それ以外の要求とに分類され、前記並び換え判定制御手段はさらに、入力された読み出し要求が優先要求であるかどうかを判別する優先要求判別手段と、優先要求であると判別され、かつ、位置決定手段により末尾に挿入すると決定された場合、キューテーブル内の全ての読み出し要求のデータ転送時間及びシーク時間を加算した加算結果がその優先要求の最大許容時間よりも大きければ、廃棄すると判定する廃棄判定手段と、廃棄すると判定された優先要求を廃棄するとともに、優先要求に対する並び換え制御手段の動作を禁止する廃棄手段とを備えている。
【００１９】
請求項１２の発明は請求項９又は１１に対して、前記許容時間保持手段は、さらにキュー内の読み出し要求毎に、キューの内の直前に他の読み出し要求を挿入できないことと、シーク方向が逆になることとを表す禁止フラグを保持し、前記並び換え手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定され、かつ、位置決定手段によりキューの末尾が挿入すべき位置と決定された場合には、並び換え後に末尾に挿入された読み出し要求の直前順位の読み出し要求に対応する禁止フラグをセットする。
【００２０】
請求項１３の発明は請求項１２に対して、前記並び換え制御手段はさらに、読み出し要求が入力されたとき、許容時間保持手段内の禁止フラグがセットされていて、かつ、キューの末尾に最も近い読み出し要求を検出する禁止フラグ検出手段と、末尾の読み出し要求のトラック位置に対して、入力された読み出し要求のトラック位置と、禁止フラグ検出手段によって検出された読み出し要求のトラック位置とが同じ方向にあるか否かを判定する同一方向判定手段とを備え、前記位置決定手段は、同一方向判定手段により同じ方向にないと判定された場合に、入力された読出要求をキューの末尾を挿入すべき位置と決定し、前記探索手段は、同一方向判定手段により同じ方向にあると判定された場合に、前記探索を行う。
【００２１】
請求項１４の発明は、請求項１乃至１３の何れかのディスク制御装置がビデオサーバに用いられ、前記限界許容遅延時間はビデオサーバのユーザ側においてリアルタイム再生に要求される遅延時間である。
【００２２】
【作用】
請求項１に係るディスク制御装置では、並び換え制御手段は、読み出し要求が入力される毎に、読み出し要求保持手段内の許容時間に基づいて、入力された読み出し要求とともにキュー手段内の読み出し要求を並び換える。これにより、読み出し要求が入力される毎にキューの並び換えを行うのでアクセス効率がよくなり、しかも、最大の限界許容遅延時間を満たすようにしているので、動画や音声データのリアルタイム性を確保することができる。
【００２３】
その上、許容時間算出手段は、並び換えが実行される毎に、入力された読み出し要求について、キューにおける順位に応じて前記許容時間を算出して許容時間保持手段に格納する。許容時間更新手段は、並び換えによって、キューにおける順位が後順位に変更された各読み出し要求について許容時間保持手段の各許容時間を、順位の変更に起因する遅延時間だけ小さい値に更新する。これにより新たにキューに追加された読み出し要求については、許容時間保持手段に許容時間を新たに設定し、もともとキューにあった読み出し要求で順位が後順位に変更されたものについては、許容時間を更新することができる。
【００２４】
さらに、入力された読み出し要求の許容時間は、前記許容時間算出手段内の第１の算出手段および第２の算出手段により算出される。
請求項２の発明に係るディスク制御装置では請求項１に対して、探索手段は、読み出し要求が入力される毎に、入力された読み出し要求がキューに挿入された場合に、ディスクのヘッドシーク方向を一定に保つことができるキュー内の位置を探索する。時間判定手段は、探索手段により探索された位置について、許容時間が０以下になるか否かを判定する。位置決定手段は、許容時間が０以下にならないと判定されたときの探索された位置を挿入すべき位置と決定する。並び換え手段は、決定された位置に入力された読み出し要求を挿入するように、入力された読み出し要求とともにキュー内の読み出し要求を並び換える。
【００２５】
請求項３の発明に係るディスク制御装置では請求項２に対して、前記キュー手段は、前記キューテーブルを備えることにより論理的なキューを実現する。前記探索手段内の方向判定手段は、順位指定手段により順位が指定される毎に、トラック位置算出手段により算出されたトラック位置に対して、キューの末尾の読み出し要求のトラック位置と、指定された順位の読み出し要求のトラック位置とが同じ方向にあるかを判定する。前記並び換え手段は、位置決定手段により決定された位置に挿入するようにキューテーブルの順位を更新するとともに、トラック位置算出手段に算出されたトラック位置、データ転送時間算出手段により算出されたデータ転送時間を入力された読み出し要求に対応させてキューテーブルに格納する。
【００２６】
請求項４の発明に係るディスク制御装置では請求項１に対して、探索手段は、読み出し要求が入力される毎に、入力された読み出し要求がキューに挿入された場合に、比較的小さい距離のヘッドシーク逆行を許してディスクのヘッドシーク方向をほぼ一定に保つことができるキュー内の位置を探索する。時間判定手段は、探索された位置に入力された読み出し要求が挿入された場合に、その読み出し要求の後順位になる読み出し要求の許容時間が０以下になるか否かを判定する。位置決定手段は、許容時間が０以下にならないと判定されたときの探索された位置を挿入すべき位置と決定する。並び換え手段は、決定された位置に入力された読み出し要求を挿入するように、入力された読み出し要求とともにキュー内の読み出し要求を並び換える。これにより許容時間が０になることなく、前後数トラック分のヘッドシーク逆行を許容してほぼ一定方向にヘッドシークを保つことができる。つまり、トラック位置が極めて近い場合のみ逆行を許容することができる。
【００２７】
請求項５の発明に係るディスク制御装置では請求項４に対して、前記キュー手段は、前記キューテーブルを備えることにより論理的なキューを実現する。方向判定手段は、順位指定手段により順位が指定される毎に、トラック位置算出手段により算出されたトラック位置に対して、キューの末尾の読み出し要求のトラック位置と、指定された順位の読み出し要求のトラック位置の前後数トラックの何れかとが同じ方向にあるかを判定する。
【００２８】
請求項６の発明に係るディスク制御装置では請求項３又は５に対して、前記時間判定手段は、方向判定手段により同じ方向にあると判定されたとき、順位指定手段に指定された順位の読み出し要求に対応する許容時間から、データ転送時間を減算し、減算結果が０以下になるか否かを判定する。前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下にならないと判定された場合、順位指定手段に指定された次の順位について、方向判定手段が同じ方向にないと判定した場合には、その２つの順位の読み出し要求の間を入力された読み出し要求を挿入すべき位置と決定する。
【００２９】
請求項７の発明に係るディスク制御装置では請求項６に対して、前記第１の算出手段が、キューテーブル内の全ての先順位の読み出し要求のデータ転送時間及びシーク時間を加算することにより前記遅延時間を算出する。前記許容時間更新手段が、並び換えによって、キューにおける順位が後順位に変更された各読み出し要求について、許容時間保持手段の各許容時間を、前記データ転送時間だけ小さい値に更新する。これにより許容時間を高い精度で計算することができる。
【００３０】
請求項８の発明に係るディスク制御装置では請求項７に対して、前記限界許容遅延時間は、全ての読み出し要求に共通の値が予め定められている。これにより限界許容遅延時間は、画一的に処理される。請求項１１の発明に係るディスク制御装置では請求項１０に対して、前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定された場合には、キューの末尾を挿入すべき位置と決定する。
【００３１】
請求項１０の発明に係るディスク制御装置では請求項７に対して、前記限界許容遅延時間は、入力される読み出し要求に含まれる。
請求項１１の発明に係るディスク制御装置では請求項１０に対して、前記読み出し要求は、最大許容時間が短く廃棄されてもよい優先要求と、それ以外の要求とを含む。前記位置決定手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定された場合には、キューの末尾を挿入すべき位置と決定する。廃棄判定手段は、優先要求判定手段により優先要求であると判別され、かつ、位置決定手段により末尾に挿入すると決定された場合、キューテーブル内の全ての読み出し要求のデータ転送時間及びシーク時間を加算した加算結果がその優先要求の最大許容時間よりも大きければ、廃棄すると判定する。廃棄手段は、廃棄判定手段により廃棄すると判定された優先要求を廃棄するとともに、優先要求に対する並び換え制御手段の動作を禁止する。とを備えている。これにより、優先要求は短い遅延時間で出力されるが、廃棄される可能性も高くなるので、例えばディスク上のデータが映画を表す場合に、早送りや逆戻しを優先要求とすれば、２種類のデータ品質を満たして効率よくデータを読み出すことができる。
【００３２】
請求項１２の発明に係るディスク制御装置では請求項９又は１１に対して、前記許容時間保持手段は、さらにキュー内の読み出し要求毎に、キューの内の直前に他の読み出し要求を挿入できないことと、シーク方向が逆になることとを表す禁止フラグを保持する。前記並び換え手段は、方向判定手段により同じ方向にあると判定され、かつ、前記時間判定手段により０以下になると判定され、かつ、位置決定手段によりキューの末尾が挿入すべき位置と決定された場合には、並び換え後に末尾に挿入された読み出し要求の直前順位の読み出し要求に対応する禁止フラグをセットする。これにより入力された読み出し要求を挿入すべき位置の判定を迅速に行うことができる。
【００３３】
請求項１３の発明に係るディスク制御装置では請求項１２に対して、同一方向判定手段は、読み出し要求が入力されたとき、許容時間保持手段内の禁止フラグがセットされていて、かつ、キューの末尾に最も近い読み出し要求を検出する禁止フラグ検出手段と、末尾の読み出し要求のトラック位置に対して、入力された読み出し要求のトラック位置と、検出された読み出し要求のトラック位置とが同じ方向にあるか否かを判定する。前記位置決定手段は、同一方向判定手段により同じ方向にないと判定された場合に、入力された読出要求をキューの末尾を挿入すべき位置と決定する。また、前記探索手段は、同一方向判定手段により同じ方向にあると判定された場合に、前記探索を行う。これにより入力された読み出し要求がキューの末尾にしか追加できないことを迅速に判定することができる。
【００３４】
請求項１４の発明に係るディスク制御装置では請求項１乃至１３の何れかのディスク制御装置がビデオサーバに用いられ、前記限界許容遅延時間はビデオサーバのユーザ側においてリアルタイム再生に要求される遅延時間である。これによりリアルタイム性を要求されるビデオサーバにおいて、動画や音声を含むマルチメディアデータを、動画や音声を途切らせることなく効率よく読みだすことができる。
【００３５】
【実施例】
図１は、本発明の実施例におけるディスク制御装置の概略構成を示すブロック図である。同図において、ディスク制御装置は、ハードディスク２００、キュー管理部２０１、許容遅延データ管理部２０２、並び換え制御部２０３から構成され、連続的に入力される複数の読み出し要求に対して、読み出し順序を並び換えることによりシーク時間を短縮し、かつ限界許容遅延時間の範囲内でデータ出力する。
【００３６】
ハードディスク２００は、複数種類のマルチメディアデータを一定のサイズ毎に分割して記憶する。本ディスク制御装置がビデオサーバに用いられる場合には、複数タイトルの映画を所定のサイズ（６４Ｋバイト）に分割して記憶する。
キュー管理部２０１は、連続的に入力される複数の読み出し要求を処理待ちキューとして保持し、ハードディスク２００に対して順に読み出し要求を出力する。ここで読み出し要求は、上記所定サイズ分のデータ読み出しの要求を表す。図２にキューの模式図を示す。同図においてＲ（１）−Ｒ（ｎ）は、キュー内の読み出し要求を表す。キューの先頭の読み出し要求Ｒ（１）は、ハードディスク２００における１つ前の読み出し要求Ｒ（０）の処理が終了した時点で出力される。また、Ｒ（α）は新たに発生した読み出し要求を表す。
【００３７】
許容遅延データ管理部２０２は、キュー内の各読み出し要求に対する許容遅延データを保持する。ここで許容遅延データとは、読み出し要求に対して、現在のキュー位置ではさらにどれだけの遅延を与えても限界許容遅延時間を守れるかを表す。具体的には、新たにキューに追加された読み出し要求については、キューに読み出し要求が追加された時点で許容遅延データが新たに算出され、また、既にキュー内に存在した読み出し要求については、順位が後順位に変更された時点で順位の変更に起因して生じる遅延時間だけ許容遅延データが小さい値に更新される。
【００３８】
並び換え制御部２０３は、読み出し要求が入力される毎に、キュー管理部２０１のキューに対して、許容遅延データ管理部２０２に管理されている許容遅延データを参照して、シーク時間が短くなるキューの位置に入力された読み出し要求を挿入する。
図１に図示していないが、並び換え制御部２０３に読み出し要求を供給するユーザ管理部について説明する。ビデオサーバではユーザ指定された映画について、その映画を構成する複数のデータをユーザに連続的に供給する必要がある。そのため、ユーザ管理部は、ユーザからの特定の映画の指定を受け付けると、その映画に対する個々のデータの読み出し要求を順次並び換え制御部２０３に発行する。この読み出し要求は、論理アドレスと、データサイズと、限界許容遅延時間とを含む。ここで論理アドレスは、読み出すべきデータのハードディスク２００上の先頭位置を示す論理的なアドレスである。データサイズは、読み出すべきデータのサイズであり、例えば６４ｋバイト程度である。限界許容遅延時間は、ユーザ側で映画として分断することなくデータを順次再生するための条件であり、読み出し要求の発行からハードディスク２００からデータが出力されるまでの許される最大の遅延時間を表し、例えば３００ｍｓ程度である。
【００３９】
図３は、本ディスク制御装置のさらに詳細な構成を示すブロック図である。同図に示すように、キュー管理部２０１は、キューテーブル２１１と読出制御部２１２とから、許容遅延データ管理部２０２は、許容遅延データテーブル２２１と限界許容遅延時間計算部２２２とから、並び換え制御部２０３は、読出時間計算部２３１とトラック位置計算部２３２とシーク時間計算部２３３と並び換え部２３４とから構成される。
【００４０】
キューテーブル２１１は、読み出し要求を論理的にキューとして管理するためのテーブルである。図４（ａ）にキューテーブル２１１の構成例を示す。同図のようにキューテーブル２１１は、キュー内の各読み出し要求Ｒ（ｘ）に対応させて、順序ｘ、読み出し時間ｔ（ｘ）、トラック位置Ａ（ｘ）、シーク時間Ｓ（ｘ）を記憶する。ここで「順序ｘ」は、読み出し要求のキューにおける順序を示す。１がキューの先頭を、最大値ｎがキューの末尾を表す。このｎはキュー長でもある。ここで「読み出し時間ｔ（ｘ）」は、読み出し要求Ｒ（ｘ）に対するデータをハードディスク２００において読み取って出力するのに要する時間に、トラックでの最大回転待ち時間を加えたものであり、シーク後データを取り出すまでに必要とする最大の時間を示す。「トラック位置Ａ（ｘ）」は、読み出し要求ｘに対するデータが書き込まれているシリンダーの位置（どのトラックであるか）を示す。「シーク時間Ｓ（ｘ）」は、Ａ（ｘ−１）からＡ（ｘ）までヘッドを移動させるのに要する時間を示す。
【００４１】
読出制御部２１２は、ハードディスク２００がアクセス状態であるかレディ状態であるかを検出し、レディ状態になった時点で直ちにキューテーブル２１１の先頭にある読み出し要求Ｒ（１）を取り出して、対応するデータをハードディスク２００から読み出す制御を行う。このとき、取り出した読み出し要求Ｒ（１）およびそれに関連するデータをキューテーブル２１１から削除するとともに、残りの読み出し要求の順序ｘを更新する（順番を繰り上げる）。
【００４２】
許容遅延データテーブル２２１は、キューテーブル２１１内の各読み出し要求Ｒ（ｘ）に対する許容遅延データＰ（ｘ）を保持するテーブルである。図４（ｂ）に許容遅延データテーブル２２１の構成例を示す。同図のように許容遅延データテーブル２２１は、キュー内の各読み出し要求Ｒ（ｘ）に対応させて、許容遅延データＰ（ｘ）、禁止フラグｆｌｇ（ｘ）を記憶する。ここで、「許容遅延データＰ（ｘ）」は、読み出し要求Ｒ（ｘ）をあとどれだけ遅延させることができるかをを表す許容時間を示す。「禁止フラグｆｌｇ（ｘ）」は、ＯＮであれば、要求Ｒ（ｘ）の前に新たな要求を挿入することができないことと、その読み出し要求の前後でシーク方向を逆にすることとを表す。
【００４３】
限界許容遅延時間計算部２２２は、並び換え部２３４によってキューテーブル２１１に読み出し要求が追加される毎に、追加された読み出し要求及びそれより後順序の読み出し要求を対象に、キューテーブル２１１を参照して許容遅延データを計算して、許容遅延データテーブル２２１に格納する。この計算は、追加された読み出し要求については次式（１）により、それより後順位の読み出し要求については次式（２）による。
【００４４】
【数１】
0003575870.tif 000002
【００４５】
ここでＴ（ｘ）は、読み出し要求Ｒ（ｘ）の限界許容遅延時間を示す。
【００４６】
【数２】
0003575870.tif 000003
【００４７】
（２）式は、追加された読み出し要求より後順位の読み出し要求については、それぞれのＰ（ｘ）から追加された読み出し要求の読み出し時間ｔ（α）を減算し、その値をＰ（ｘ）として更新することを意味する。また、（２）式では、計算を簡略化するため、読み出し要求Ｒ（α）を追加することによるシーク時間Ｓ（ｘ）への影響を考慮していない。というのは、この影響は無視できるほど小さいからである。このようにしてキューテーブル２１１のＰ（ｘ）は、キューに読み出し要求が追加された時点で新たに算出され、その後、順位が後順位に変更された時点で順位の変更に起因して生じる遅延時間だけ小さい値に更新されることになる。
【００４８】
読出時間計算部２３１は、新たに読み出し要求Ｒ（α）が並び換え制御部２０３に入力されたとき、Ｒ（α）に対する読み出し時間ｔ（α）を計算する。この読み出し時間ｔ（α）は、読み出すべきデータのサイズを、ハードディスク２００の最小データ転送速度で割って、さらにディスクの最大回転待ち時間を加えることにより計算される。例えば、データサイズを６４ｋバイト、データ読み出しの最小速度を２．７Ｍバイト／Ｓ、最大回転待ち時間を１１．２ｍＳとすると、読み出し時間ｔ（α）＝６４ｋ／２．７Ｍ＋１１．２＝約３５ｍＳと計算される。
【００４９】
トラック位置計算部２３２は、新たに読み出し要求Ｒ（α）が並び換え制御部２０３に入力されたとき、読み出し要求Ｒ（α）に対するデータのトラック位置Ａ（α）を計算する。例えば、ディスクの内周と外周の１トラックあたりのデータサイズが等しい場合には、トラック位置計算部２３２は、ハードディスク２００の最内周トラックの論理アドレスＬＡｍｉｎと、最外周トラックの論理アドレスＬＡｍａｘと、Ｒ（α）の論理アドレスＬＡαと、全トラック数ＴＮとに基づいて次のようにＡ（α）を求める。
【００５０】
【数３】
0003575870.tif 000004
【００５１】
シーク時間計算部２３３は、並び換え部２３４によって読み出し要求Ｒ（α）がキューテーブル２１１に追加される毎に、追加された読み出し要求Ｒ（α）以降の読み出し要求に対してシーク時間Ｓ（ｘ）を計算する。具体的には、シーク時間計算部２３３は、Ａ（ｘ）−Ａ（ｘ−１）間の距離を、ハードディスク２００のヘッドのシーク速度で割り算することによりシーク時間を求める。
【００５２】
並び換え部２３４は、新たに読み出し要求Ｒ（α）が入力されたる毎に、キューテーブル２１１及び許容遅延データテーブル２２１を参照して、読み出し時間ｔ（α）、シーク時間Ｓ（α）に基づいて、キュー内の全て読み出し要求が限界許容遅延時間を満たし、かつ、シーク方向が一定になるように並び換えを行う。図５は、並び換え部２３４の詳細な並び換え処理を示すフローチャートを示す。並び換え部２３４は、読み出し要求Ｒ（α）が入力されると読出時間計算部２３１、トラック位置計算部２３２にそれぞれ読み出し時間ｔ（α）、トラック位置Ａ（α）を計算させ（ステップ６０１、６０２）、キューテーブル２１１のキュー長ｎが０であれば（ステップ６０３：ｎｏ）、読み出し要求Ｒ（α）、読み出し時間ｔ（α）、トラック位置Ａ（α）、シーク時間計算部２３３で計算されたシーク時間Ｓ（α）をキューテーブル２１１に登録するとともに、限界許容遅延時間計算部２２２で計算された許容遅延データＰ（α）と、禁止フラグｆｌｇ（α）＝ＯＦＦとを許容遅延データテーブル２２１に登録する（ステップ６０４）。  また、並び換え部２３４は、キュー長ｎが１以上であれば（ステップ６０３：ｙｅｓ）、変数ｋをｎから順に１ずつ減少するパラメータとして、キューの末尾から順に許容遅延データテーブル２２１の禁止フラグｆｌｇ（ｋ）を参照して、禁止フラグがＯＮである読み出し要求Ｒ（ｋ）を検出する（ステップ６０６−６０８）。
【００５３】
さらに、並び換え部２３４は、読み出し要求Ｒ（α）のトラック位置Ａ（α）が末尾の読み出し要求Ｒ（ｎ）のトラック位置Ａ（ｎ）と一致している場合には（ステップ６０９：ｙｅｓ）、読み出し要求Ｒ（α）を、ｔ（α）、Ａ（α）とともにキューテーブル２１１のキューの最後尾に登録し（ステップ６１１）、限界許容遅延時間計算部２２２、シーク時間計算部２３３にそれぞれ許容時間Ｐ（α）、シーク時間Ｓ（α）を計算させて、計算結果を許容遅延データテーブル２２１、キューテーブル２１１に登録する（ステップ６１２）。
【００５４】
一致していない場合には（ステップ６０９：ｎｏ）、並び換え部２３４は、トラック位置Ａ（ｎ）からみて、トラック位置Ａ（α）とトラック位置Ａ（ｋ）とが同じ方向にあるか否かを判定する。具体的には並び換え部２３４は、（Ａ（ｋ）−Ａ（ｎ））と（Ａ（α）−Ａ（ｎ））の積をとった結果が正であるが負であるかにより同じ方向にあるかか否かを判定する。
【００５５】
その結果、同じ側でない場合には（ステップ６１０：ｎｏ）、図６（ａ）に示すように、読み出し要求Ｒ（α）をキューの末尾に登録し（ステップ６１１）、限界許容遅延時間計算部２２２、シーク時間計算部２３３にＰ（α）、Ｓ（α）を計算させて、ｔ（α）、Ａ（α）、Ｓ（α）、Ｐ（α）、ｆｌｇ（α）をキューテーブル２１１、許容遅延データテーブル２２１に登録する（ステップ６１２）。この場合図６（ａ）のように、読み出し要求Ｒ（α）を末尾に登録することによって、ハードディスク２００のシーク方向がＡ（ｋ）→Ａ（ｎ）→Ａ（α）というように一定に保たれる。
【００５６】
また、同じ側である場合には（ステップ６１０：ｙｅｓ）、並び換え部２３４は、並び換え部２３４は変数ｙをｎから１ずつ減少するパラメータとして、キュー内の読み出し要求Ｒ（ｙ）１つずつを対象として以下の処理を行う。
まず、Ｒ（ｙ）の直前にＲ（α）を挿入してもシーク方向を一定に保って、かつ、Ｒ（ｙ）の限界許容遅延時間を守れるかどうかを調べる。図６（ｂ）にこの様子を表す模式図を示す。より詳しくいうと、Ａ（α）からみてＡ（ｙ）とＡ（ｎ）とが同じ方向にあって、ｆｌｇ（ｙ）がＯＦＦ、かつ、Ｐ（ｙ）≧ｔ（α）である場合には（ステップ６１４：ｙｅｓ、６１５：ｎｏ、６１６ｙｅｓ）、Ｒ（ｙ）の直前にＲ（α）を挿入可能であると判断する。また、Ｒ（ｙ）の限界許容遅延時間を守れない（Ｐ（ｙ）≧ｔ（α）でない）場合には（ステップ６１６：ｎｏ）、ｆｌｇ（ｎ）をＯＮにしてから（ステップ６１７）、Ｒ（α）をキューの末尾に登録する（ステップ６１８、６１９）。ここでｆｌｇ（ｎ）をＯＮにしているのは、末尾に登録したＲ（α）を除く全てのキュー内の読み出し要求を並び換えの対象外にするためと、Ｒ（α）の次からシーク方向を逆にするためである。
【００５７】
ついで、直前に挿入可能と判断された場合（ステップ６１６：ｙｅｓ）、さらに変数ｙ＝ｙ−１と更新することにより１つ前の読み出し要求に対して（ステップ６２０）、Ａ（α）からみてＡ（ｙ）とＡ（ｎ）とが同じ方向にあるか否かを判定するすることにより、Ｒ（α）をＲ（ｙ）の直前に挿入してもシーク方向を保てるかどうかを判定する。シーク方向を保てると判定された場合には（ステップ６１４：ｙｅｓ）、ステップ６１５以降の処理を上記と同様に行う。シーク方向を保てないと判定された場合には（ステップ６１４：ｎｏ）、Ｒ（α）をＲ（ｙ）の直後に挿入する（ステップ６２１、６２２）。図６（ｃ）に、この場合の様子を表す模式図を示す。
【００５８】
以上のように構成された本発明のディスク制御装置について、以下その動作を説明する。
今、図７（ａ）のように、キューテーブル２１１、許容遅延データテーブル２２１内に既に読み出し要求Ｒ（１）−Ｒ（５）が保持されているものとする。同図の例では、全ての読み出し要求の限界許容遅延時間を３００ｍＳ、データサイズを６４ｋバイトとし、また、ハードディスク２００の最大シーク時間を２０ｍＳ、最大回転待ち時間を１１．２ｍＳ、最大データ転送速度を５．５Ｍバイト、最小データ転送速度を２．７Ｍバイト、シリンダ数２０００であるものとする。この場合、各読み出し要求の読出時間ｔ（ｘ）は６４ｋバイト／２．７Ｍバイト＋１１．２ｍＳ＝約３５ｍＳとなる。
【００５９】
この状態で、新たに読み出し要求Ｒ（６）が並び換え制御部２０３に入力されると、読出時間計算部２３１により読み出し時間ｔ（６）＝３５ｍＳが計算され、トラック位置計算部２３２によりトラック位置Ａ（６）が計算される。ここで計算されたＡ（６）は３００であるものとする。この読み出し要求Ｒ（６）は、図６（ａ）に示したように、末尾のＡ（５）からみてＡ（６）とＡ（２）とが同じ方向にないので、キューの末尾に登録される。登録された結果を図７（ｂ）に示す。  さらにこの状態で新たに読み出し要求Ｒ（７）が並び換え制御部２０３に入力されると、同様にｔ（７）＝３５ｍＳが計算される。またＡ（７）＝１３００と計算されたものとする。この読み出し要求Ｒ（７）については、並び換え部２３４によって、末尾のＡ（６）からみてＡ（７）（＝１３００）とＡ（２）（＝２０００）とが同じ方向に同じ方向にあると判定される（図５ステップ６１０）。さらに、キューのどの位置にＲ（７）を挿入できるかを判定するため、Ａ（７）（＝１３００）からみてＡ（ｙ）とＡ（６）（＝５００）とが同じ方向にあるかどうかが判定される。ここで、ｙ＝６、５、４のときは、図６（ｂ）に示したように、同じ方向にあってかつ許容遅延データＰ（ｙ）がｔ（７）よりも大きいので（ステップ６１４−６１６、６２０のループを３度回る）、Ｒ（ｙ）の直前に挿入可能と判定される。
【００６０】
さらにｙ＝３のときは、図６（ｃ）に示したように、Ａ（７）（＝１３００）からみてＡ（３）（＝１５００）とＡ（６）（＝５００）とが同じ方向にないので（図５ステップ６１４）、Ｒ（７）をＲ（３）の直後に挿入すると決定される（ステップ６２１）。Ｒ（７）がＲ（３）の直後に挿入された状態を図７（ｃ）に示す。この場合、Ｒ（７）をＲ（３）の直後に挿入しても、Ｒ（６）−Ｒ（４）のそれぞれの限界許容遅延時間を守れることは、上記の３回のループ処理により確認されている。また、シーク方向が一定に保てる位置に挿入されるので、ディスクの読み出し効率を向上させている。
【００６１】
さらに補足的にディスク制御装置の性能限界について説明する。例えば図７（ｃ）の状態では、さらに読み出し要求Ｒ（８）が入力されたとする。このとき、Ｐ（７）＝２１ｍＳ、ｔ（８）＝３５ｍＳなので、Ｐ（７）≧ｔ（８）を満たさないので（ステップ６１６：ｎｏ）、Ｒ（８）はキューの末尾に登録されることになる。このときＰ（８）は０より小さくなる。その結果Ｒ（８）は限界許容遅延時間を満足できないことになる。限界許容遅延時間を満足できないのは、ディスク制御装置の性能を越えて多数の読み出し要求が入力されたことを意味する。ディスクの読出効率を向上させることはディスク装置の性能を向上させることになる。
【００６２】
以上説明してきたように本発明のディスク制御装置によれば、個々の読み出し時間毎の限界許容遅延時間を満足させながら、ディスクの読出効率を向上させることができる。
図８は、本発明のディスク制御装置と従来のディスク制御装置の両者について、使用率−廃棄率特性をシミュレーションした結果を示す。同図において、横軸の「使用率」は、６４ｋバイトデータをランダムに連続して読み出したデータ取得量を１．０とした場合の、読み出しデータ量の割合を示す。このデータ取得量（使用率＝１．０）は、ハードディスク２００の平均データ転送時間、平均回転待ち時間、平均シーク時間をそれぞれＴｔｒａｎｓｍｉｔ、Ｔｗａｉｔ、Ｔｓｅｅｋで表した場合、次式により与えられる。
【００６３】
【数４】
0003575870.tif 000005
【００６４】
また、縦軸の「廃棄率」は、限界許容遅延時間を越えて処理されたため、読出後にデータが廃棄された読み出し要求の割合を表す。同図のように、本発明のディスク制御装置は、従来技術に比べて廃棄率が２桁から４桁小さくなっており（１００分の１〜１００００分の１に小さくなっており）、ディスクの読出効率が向上していることがわかる。
【００６５】
以下、本発明の第２実施例を説明する。図９は、第２実施例におけるディスク制御装置の構成を示すブロック図である。図１と同じ構成要素は同じ番号を付与して説明を省略し、異なる点のみ説明する。
図９のディスク制御装置は、第１実施例の並び換え制御部２０３の代わりに並び換え制御部１００３を備える点が異なり、第１実施例と同様の読み出し要求（以下通常要求と呼ぶ）に加えて、優先的に読み出す必要がある優先要求を受け付ける点が異なる。ここで、優先要求は、限界許容遅延時間が短いが、廃棄が許される要求である。例えば、ビデオサーバにおいてユーザが早送りや逆再生を指示した場合には、ユーザに供給すべきデータは、多少の欠落してもよいが遅延時間は小さくする必要がある。この様な場合に優先要求が用いられる。また、通常要求は、優先要求に比べると限界許容遅延時間が長く、廃棄を最小限に押さえる必要がある要求である。ビデオサーバにおいては通常再生に相当する。
【００６６】
図９において、並び換え制御部１００３は、通常要求に加えて優先要求を受け付けて、キューに既に保持された読み出し要求の限界許容遅延時間を満たすキュー位置に登録する点は、第１実施例と同様である。このとき登録すべきキュー位置において、優先要求の限界許容遅延時間を満たせない場合には、その優先要求を廃棄する。
【００６７】
図１０は、並び換え制御部１００３の詳細な構成を示す。同図において優先要求判定部１１０１、並び換え部１１０２以外は第１実施例と同じであるので説明を省略する。
優先要求判定部１１０１は、読み出し要求が入力される毎に、それが優先要求であるか通常要求であるかを判定し、並び換え部１１０２に通知する。例えば、１５０ｍＳというしきい値を保持しておき、限界許容遅延時間が１５０ｍＳ以下であれば優先要求、それより大きければ通常要求と判定する。
【００６８】
並び換え部１１０２は、通常要求については第１実施例と全く同じであるが、優先要求についてはその限界許容遅延時間を満足できない場合には廃棄する。並び換え部１１０２の詳細な処理内容は、図５に示したフローチャートのステップ６１４とステップ６２１の間に図１１に示す処理を追加したものとなる。
図１１において、並び換え部１１０２は、ステップ６１４の続いて、優先要求判定部１１０１により読み出し要求Ｒ（α）が優先要求であると判定された場合には（ステップ１２１：ｙｅｓ）、キュー内の読み出し要求Ｒ（ｙ）の読み出しが完了するまでの時間ｔ１（ｙ）がその優先要求の限界許容遅延時間Ｔ１（α）より大きいときには（ステップ１２２：ｙｅｓ）、Ｒ（ｙ）の直後にＲ（α）登録し（ステップ６２１）、小さいときにはＲ（α）を廃棄する（ステップ１２３）。ここで、要求Ｒ（ｙ）の読み出しが完了するまでの時間ｔ１（ｙ））は、次式により計算される。
【００６９】
【数５】
0003575870.tif 000006
【００７０】
上記のように並び換え部１１０２は、優先要求についてキュー内の挿入すべき位置を通常要求と同様にして決定し、その限界許容遅延時間が満足できない場合には廃棄する。これにより通常要求と優先要求とをその要求される品質に応じて処理することができる。
なお、上記第１、第２実施例では、シーク方向が一定になるように並び換えを行っているが、隣接する読み出し要求のトラック位置の間隔が小さい場合には部分的にシーク方向を逆行させるように並び換えてもよい。例えば、逆行が許されるトラック位置の間隔が５以内とする場合、ｏｆｆｓｅｔを５として図５のステップ６１４を次のように変更すればよい。
【００７１】
【数６】
この式の何れかを満たす場合にはステップ６１５へ進み、何れも満たさない場合にはステップ６２１へ進む。
第１実施例では全ての限界許容遅延時間を３００ｍＳとして説明したが、個々の読み出し要求毎に異なる限界許容遅延時間を有していても構わない。その場合でも（１）式に示したように、個々の読み出し要求の限界許容遅延時間Ｔ（ｘ）に基づいて許容遅延データＰ（ｘ）を計算しているので、個々の読み出し要求の限界許容遅延時間を満たすことができる。
【００７２】
第２実施例において優先要求判定部１１０１は、限界許容遅延時間としきい値との大小を比較することにより優先要求か通常要求かを判定したが、読み出し要求内に優先であるか通常であるかを示す情報（例えばフラグ）を持たせ、その情報により判定するようにしてもよい。
【００７３】
【発明の効果】
以上説明したように、請求項１の発明によれば、並び換え制御手段は、読み出し要求が入力される毎に、許容時間保持手段内の許容時間に基づいて、入力された読み出し要求とともにキュー手段内の読み出し要求を並び換える。これにより、読み出し要求が入力される毎にキューの並び換えを行うのでアクセス効率がよくなり、しかも、最大の限界許容遅延時間内のデータを出力することができる。特に動画や音声データに対してアクセス効率を向上させるとともに、リアルタイム性を確保することができるという効果がある。
【００７４】
加えて、新たにキューに追加された読み出し要求については、許容時間保持手段に許容時間を新たに設定し、元々キューにあった読み出し要求で順位が後順位に変更されたものについては、許容時間を更新するので、許容時間保持手段の各許容時間は、キューに新たな読み出し要求が追加された時点で必要なものだけを更新することができるという効果もある。
【００７５】
更に、入力された読み出し要求の許容時間は、前記許容時間算出手段内の第１の算出手段および第２の算出手段により算出される。
請求項２の発明によれば請求項１の効果に加えて、ディスクのヘッドシーク方向を一定に保つことによるアクセス効率の向上を図ることができる。
【００７６】
請求項３の発明によれば請求項２と同様の効果がある。請求項４の発明によれば請求項１の効果に加えて、比較的小さい距離のヘッドシーク逆行を許してディスクのヘッドシーク方向をほぼ一定に保つことによるアクセス効率の向上を図ることができる。請求項５の発明によれば請求項４と同様の効果がある。
【００７７】
請求項６の発明によれば請求項３又は５と同様の効果がある。請求項７の発明によれば請求項６の効果に加えて、許容時間をより高い精度で計算することができる。請求項８の発明によれば請求項７の効果に加えてに、限界許容遅延時間は、画一的に処理することができる。
【００７８】
請求項９の発明によれば請求項８と同様の効果がある。請求項１０の発明によれば請求項７の効果に加えて、読み出し要求毎に限界許容遅延時間が異なっている場合でも、それぞれの許容時間が順守されるので、読み出し要求毎に必要とされるデータ品質に応じて効率的に読み出すことができる。
【００７９】
請求項１１の発明によれば請求項１０の効果に加えて、廃棄される可能性が高いけれども短い遅延時間で優先要求が出力されるので、例えばディスク上のデータが映画を表す場合に、早送りや逆戻しを優先要求とすれば、要求されるデータ品質を満たして効率よくデータを読み出すことができる。請求項１２の発明によれば請求項９又は１１の効果に加えて、方向判定手段が禁止フラグを用いて判定することによって、入力された読み出し要求を挿入すべき位置の判定を迅速に行うことができる。
【００８０】
請求項１３の発明によれば請求項１２の効果に加えて、入力された読み出し要求がキューの末尾にしか追加できないことを迅速に判定することができる。請求項１４の発明によれば請求項１乃至１３の何れかの効果に加えて、リアルタイム性を要求されるビデオサーバにおいて、動画や音声を含むマルチメディアデータを、動画や音声を途切らせることなく効率よく読みだすことができる。
【図面の簡単な説明】
【図１】本発明の実施例におけるディスク制御装置の概略構成を示すブロック図である。
【図２】同実施例における読み出し要求がキューとして管理される様子を示す模式図である。
【図３】同実施例におけるディスク制御装置の詳細構成を示すブロック図である。
【図４】（ａ）  キューテーブルを示す図である。
（ｂ）  許容遅延データテーブルを示す図である。
【図５】並び換え処理を示す詳細なフローチャートを示す。
【図６】（ａ）〜（ｃ）  並び換えの様子を示す模式図である。
【図７】（ａ）〜（ｃ）  キューテーブル、許容遅延データテーブルの具体例を示す。
【図８】本発明によるディスク装置と従来のディスク装置の両者について、使用率−廃棄率特性をシミュレーションした結果を示す。
【図９】第２実施例のディスク制御装置の構成を示すブロック図である。
【図１０】並び換え制御部の詳細構成を示すブロック図である。
【図１１】並び換え制御部の処理を表すフローチャートである。
【図１２】従来のディスク装置の構成を示すブロック図である。
【符号の説明】
２００    ハードディスク
２０１    キュー管理部
２０２    許容遅延データ管理部
２０３    並び換え制御部
２１１    キューテーブル
２１２    読出制御部
２２１    許容遅延データテーブル
２２２    限界許容遅延時間計算部
２３１    読出時間計算部
２３２    トラック位置計算部
２３３    シーク時間計算部
２３４    並び換え部
【図１】
0003575870.tif 000007
【図２】
0003575870.tif 000008
【図３】
0003575870.tif 000009
【図４】
0003575870.tif 000010
【図５】
0003575870.tif 000011
【図６】
0003575870.tif 000012
【図７】
0003575870.tif 000013
【図８】
0003575870.tif 000014
【図９】
0003575870.tif 000015
【図１０】
0003575870.tif 000016
【図１１】
0003575870.tif 000017
【図１２】
0003575870.tif 000018