JP3575870B2 - Disk controller - Google Patents

Description

【００４５】
ここでＴ（ｘ）は、読み出し要求Ｒ（ｘ）の限界許容遅延時間を示す。
【００４６】
【数２】

【００４７】
（２）式は、追加された読み出し要求より後順位の読み出し要求については、それぞれのＰ（ｘ）から追加された読み出し要求の読み出し時間ｔ（α）を減算し、その値をＰ（ｘ）として更新することを意味する。また、（２）式では、計算を簡略化するため、読み出し要求Ｒ（α）を追加することによるシーク時間Ｓ（ｘ）への影響を考慮していない。というのは、この影響は無視できるほど小さいからである。このようにしてキューテーブル２１１のＰ（ｘ）は、キューに読み出し要求が追加された時点で新たに算出され、その後、順位が後順位に変更された時点で順位の変更に起因して生じる遅延時間だけ小さい値に更新されることになる。
【００４８】
読出時間計算部２３１は、新たに読み出し要求Ｒ（α）が並び換え制御部２０３に入力されたとき、Ｒ（α）に対する読み出し時間ｔ（α）を計算する。この読み出し時間ｔ（α）は、読み出すべきデータのサイズを、ハードディスク２００の最小データ転送速度で割って、さらにディスクの最大回転待ち時間を加えることにより計算される。例えば、データサイズを６４ｋバイト、データ読み出しの最小速度を２．７Ｍバイト／Ｓ、最大回転待ち時間を１１．２ｍＳとすると、読み出し時間ｔ（α）＝６４ｋ／２．７Ｍ＋１１．２＝約３５ｍＳと計算される。
【００４９】
トラック位置計算部２３２は、新たに読み出し要求Ｒ（α）が並び換え制御部２０３に入力されたとき、読み出し要求Ｒ（α）に対するデータのトラック位置Ａ（α）を計算する。例えば、ディスクの内周と外周の１トラックあたりのデータサイズが等しい場合には、トラック位置計算部２３２は、ハードディスク２００の最内周トラックの論理アドレスＬＡｍｉｎと、最外周トラックの論理アドレスＬＡｍａｘと、Ｒ（α）の論理アドレスＬＡαと、全トラック数ＴＮとに基づいて次のようにＡ（α）を求める。
【００５０】
【数３】

【００５１】
シーク時間計算部２３３は、並び換え部２３４によって読み出し要求Ｒ（α）がキューテーブル２１１に追加される毎に、追加された読み出し要求Ｒ（α）以降の読み出し要求に対してシーク時間Ｓ（ｘ）を計算する。具体的には、シーク時間計算部２３３は、Ａ（ｘ）−Ａ（ｘ−１）間の距離を、ハードディスク２００のヘッドのシーク速度で割り算することによりシーク時間を求める。
【００５２】
並び換え部２３４は、新たに読み出し要求Ｒ（α）が入力されたる毎に、キューテーブル２１１及び許容遅延データテーブル２２１を参照して、読み出し時間ｔ（α）、シーク時間Ｓ（α）に基づいて、キュー内の全て読み出し要求が限界許容遅延時間を満たし、かつ、シーク方向が一定になるように並び換えを行う。図５は、並び換え部２３４の詳細な並び換え処理を示すフローチャートを示す。並び換え部２３４は、読み出し要求Ｒ（α）が入力されると読出時間計算部２３１、トラック位置計算部２３２にそれぞれ読み出し時間ｔ（α）、トラック位置Ａ（α）を計算させ（ステップ６０１、６０２）、キューテーブル２１１のキュー長ｎが０であれば（ステップ６０３：ｎｏ）、読み出し要求Ｒ（α）、読み出し時間ｔ（α）、トラック位置Ａ（α）、シーク時間計算部２３３で計算されたシーク時間Ｓ（α）をキューテーブル２１１に登録するとともに、限界許容遅延時間計算部２２２で計算された許容遅延データＰ（α）と、禁止フラグｆｌｇ（α）＝ＯＦＦとを許容遅延データテーブル２２１に登録する（ステップ６０４）。 また、並び換え部２３４は、キュー長ｎが１以上であれば（ステップ６０３：ｙｅｓ）、変数ｋをｎから順に１ずつ減少するパラメータとして、キューの末尾から順に許容遅延データテーブル２２１の禁止フラグｆｌｇ（ｋ）を参照して、禁止フラグがＯＮである読み出し要求Ｒ（ｋ）を検出する（ステップ６０６−６０８）。
【００５３】
さらに、並び換え部２３４は、読み出し要求Ｒ（α）のトラック位置Ａ（α）が末尾の読み出し要求Ｒ（ｎ）のトラック位置Ａ（ｎ）と一致している場合には（ステップ６０９：ｙｅｓ）、読み出し要求Ｒ（α）を、ｔ（α）、Ａ（α）とともにキューテーブル２１１のキューの最後尾に登録し（ステップ６１１）、限界許容遅延時間計算部２２２、シーク時間計算部２３３にそれぞれ許容時間Ｐ（α）、シーク時間Ｓ（α）を計算させて、計算結果を許容遅延データテーブル２２１、キューテーブル２１１に登録する（ステップ６１２）。
【００５４】
一致していない場合には（ステップ６０９：ｎｏ）、並び換え部２３４は、トラック位置Ａ（ｎ）からみて、トラック位置Ａ（α）とトラック位置Ａ（ｋ）とが同じ方向にあるか否かを判定する。具体的には並び換え部２３４は、（Ａ（ｋ）−Ａ（ｎ））と（Ａ（α）−Ａ（ｎ））の積をとった結果が正であるが負であるかにより同じ方向にあるかか否かを判定する。
【００５５】
その結果、同じ側でない場合には（ステップ６１０：ｎｏ）、図６（ａ）に示すように、読み出し要求Ｒ（α）をキューの末尾に登録し（ステップ６１１）、限界許容遅延時間計算部２２２、シーク時間計算部２３３にＰ（α）、Ｓ（α）を計算させて、ｔ（α）、Ａ（α）、Ｓ（α）、Ｐ（α）、ｆｌｇ（α）をキューテーブル２１１、許容遅延データテーブル２２１に登録する（ステップ６１２）。この場合図６（ａ）のように、読み出し要求Ｒ（α）を末尾に登録することによって、ハードディスク２００のシーク方向がＡ（ｋ）→Ａ（ｎ）→Ａ（α）というように一定に保たれる。
【００５６】
また、同じ側である場合には（ステップ６１０：ｙｅｓ）、並び換え部２３４は、並び換え部２３４は変数ｙをｎから１ずつ減少するパラメータとして、キュー内の読み出し要求Ｒ（ｙ）１つずつを対象として以下の処理を行う。
まず、Ｒ（ｙ）の直前にＲ（α）を挿入してもシーク方向を一定に保って、かつ、Ｒ（ｙ）の限界許容遅延時間を守れるかどうかを調べる。図６（ｂ）にこの様子を表す模式図を示す。より詳しくいうと、Ａ（α）からみてＡ（ｙ）とＡ（ｎ）とが同じ方向にあって、ｆｌｇ（ｙ）がＯＦＦ、かつ、Ｐ（ｙ）≧ｔ（α）である場合には（ステップ６１４：ｙｅｓ、６１５：ｎｏ、６１６ｙｅｓ）、Ｒ（ｙ）の直前にＲ（α）を挿入可能であると判断する。また、Ｒ（ｙ）の限界許容遅延時間を守れない（Ｐ（ｙ）≧ｔ（α）でない）場合には（ステップ６１６：ｎｏ）、ｆｌｇ（ｎ）をＯＮにしてから（ステップ６１７）、Ｒ（α）をキューの末尾に登録する（ステップ６１８、６１９）。ここでｆｌｇ（ｎ）をＯＮにしているのは、末尾に登録したＲ（α）を除く全てのキュー内の読み出し要求を並び換えの対象外にするためと、Ｒ（α）の次からシーク方向を逆にするためである。
【００５７】
ついで、直前に挿入可能と判断された場合（ステップ６１６：ｙｅｓ）、さらに変数ｙ＝ｙ−１と更新することにより１つ前の読み出し要求に対して（ステップ６２０）、Ａ（α）からみてＡ（ｙ）とＡ（ｎ）とが同じ方向にあるか否かを判定するすることにより、Ｒ（α）をＲ（ｙ）の直前に挿入してもシーク方向を保てるかどうかを判定する。シーク方向を保てると判定された場合には（ステップ６１４：ｙｅｓ）、ステップ６１５以降の処理を上記と同様に行う。シーク方向を保てないと判定された場合には（ステップ６１４：ｎｏ）、Ｒ（α）をＲ（ｙ）の直後に挿入する（ステップ６２１、６２２）。図６（ｃ）に、この場合の様子を表す模式図を示す。
【００５８】
以上のように構成された本発明のディスク制御装置について、以下その動作を説明する。
今、図７（ａ）のように、キューテーブル２１１、許容遅延データテーブル２２１内に既に読み出し要求Ｒ（１）−Ｒ（５）が保持されているものとする。同図の例では、全ての読み出し要求の限界許容遅延時間を３００ｍＳ、データサイズを６４ｋバイトとし、また、ハードディスク２００の最大シーク時間を２０ｍＳ、最大回転待ち時間を１１．２ｍＳ、最大データ転送速度を５．５Ｍバイト、最小データ転送速度を２．７Ｍバイト、シリンダ数２０００であるものとする。この場合、各読み出し要求の読出時間ｔ（ｘ）は６４ｋバイト／２．７Ｍバイト＋１１．２ｍＳ＝約３５ｍＳとなる。
【００５９】
この状態で、新たに読み出し要求Ｒ（６）が並び換え制御部２０３に入力されると、読出時間計算部２３１により読み出し時間ｔ（６）＝３５ｍＳが計算され、トラック位置計算部２３２によりトラック位置Ａ（６）が計算される。ここで計算されたＡ（６）は３００であるものとする。この読み出し要求Ｒ（６）は、図６（ａ）に示したように、末尾のＡ（５）からみてＡ（６）とＡ（２）とが同じ方向にないので、キューの末尾に登録される。登録された結果を図７（ｂ）に示す。 さらにこの状態で新たに読み出し要求Ｒ（７）が並び換え制御部２０３に入力されると、同様にｔ（７）＝３５ｍＳが計算される。またＡ（７）＝１３００と計算されたものとする。この読み出し要求Ｒ（７）については、並び換え部２３４によって、末尾のＡ（６）からみてＡ（７）（＝１３００）とＡ（２）（＝２０００）とが同じ方向に同じ方向にあると判定される（図５ステップ６１０）。さらに、キューのどの位置にＲ（７）を挿入できるかを判定するため、Ａ（７）（＝１３００）からみてＡ（ｙ）とＡ（６）（＝５００）とが同じ方向にあるかどうかが判定される。ここで、ｙ＝６、５、４のときは、図６（ｂ）に示したように、同じ方向にあってかつ許容遅延データＰ（ｙ）がｔ（７）よりも大きいので（ステップ６１４−６１６、６２０のループを３度回る）、Ｒ（ｙ）の直前に挿入可能と判定される。
【００６０】
さらにｙ＝３のときは、図６（ｃ）に示したように、Ａ（７）（＝１３００）からみてＡ（３）（＝１５００）とＡ（６）（＝５００）とが同じ方向にないので（図５ステップ６１４）、Ｒ（７）をＲ（３）の直後に挿入すると決定される（ステップ６２１）。Ｒ（７）がＲ（３）の直後に挿入された状態を図７（ｃ）に示す。この場合、Ｒ（７）をＲ（３）の直後に挿入しても、Ｒ（６）−Ｒ（４）のそれぞれの限界許容遅延時間を守れることは、上記の３回のループ処理により確認されている。また、シーク方向が一定に保てる位置に挿入されるので、ディスクの読み出し効率を向上させている。
【００６１】
さらに補足的にディスク制御装置の性能限界について説明する。例えば図７（ｃ）の状態では、さらに読み出し要求Ｒ（８）が入力されたとする。このとき、Ｐ（７）＝２１ｍＳ、ｔ（８）＝３５ｍＳなので、Ｐ（７）≧ｔ（８）を満たさないので（ステップ６１６：ｎｏ）、Ｒ（８）はキューの末尾に登録されることになる。このときＰ（８）は０より小さくなる。その結果Ｒ（８）は限界許容遅延時間を満足できないことになる。限界許容遅延時間を満足できないのは、ディスク制御装置の性能を越えて多数の読み出し要求が入力されたことを意味する。ディスクの読出効率を向上させることはディスク装置の性能を向上させることになる。
【００６２】
以上説明してきたように本発明のディスク制御装置によれば、個々の読み出し時間毎の限界許容遅延時間を満足させながら、ディスクの読出効率を向上させることができる。
図８は、本発明のディスク制御装置と従来のディスク制御装置の両者について、使用率−廃棄率特性をシミュレーションした結果を示す。同図において、横軸の「使用率」は、６４ｋバイトデータをランダムに連続して読み出したデータ取得量を１．０とした場合の、読み出しデータ量の割合を示す。このデータ取得量（使用率＝１．０）は、ハードディスク２００の平均データ転送時間、平均回転待ち時間、平均シーク時間をそれぞれＴｔｒａｎｓｍｉｔ、Ｔｗａｉｔ、Ｔｓｅｅｋで表した場合、次式により与えられる。
【００６３】
【数４】

【００６４】
また、縦軸の「廃棄率」は、限界許容遅延時間を越えて処理されたため、読出後にデータが廃棄された読み出し要求の割合を表す。同図のように、本発明のディスク制御装置は、従来技術に比べて廃棄率が２桁から４桁小さくなっており（１００分の１〜１００００分の１に小さくなっており）、ディスクの読出効率が向上していることがわかる。
【００６５】
以下、本発明の第２実施例を説明する。図９は、第２実施例におけるディスク制御装置の構成を示すブロック図である。図１と同じ構成要素は同じ番号を付与して説明を省略し、異なる点のみ説明する。
図９のディスク制御装置は、第１実施例の並び換え制御部２０３の代わりに並び換え制御部１００３を備える点が異なり、第１実施例と同様の読み出し要求（以下通常要求と呼ぶ）に加えて、優先的に読み出す必要がある優先要求を受け付ける点が異なる。ここで、優先要求は、限界許容遅延時間が短いが、廃棄が許される要求である。例えば、ビデオサーバにおいてユーザが早送りや逆再生を指示した場合には、ユーザに供給すべきデータは、多少の欠落してもよいが遅延時間は小さくする必要がある。この様な場合に優先要求が用いられる。また、通常要求は、優先要求に比べると限界許容遅延時間が長く、廃棄を最小限に押さえる必要がある要求である。ビデオサーバにおいては通常再生に相当する。
【００６６】
図９において、並び換え制御部１００３は、通常要求に加えて優先要求を受け付けて、キューに既に保持された読み出し要求の限界許容遅延時間を満たすキュー位置に登録する点は、第１実施例と同様である。このとき登録すべきキュー位置において、優先要求の限界許容遅延時間を満たせない場合には、その優先要求を廃棄する。
【００６７】
図１０は、並び換え制御部１００３の詳細な構成を示す。同図において優先要求判定部１１０１、並び換え部１１０２以外は第１実施例と同じであるので説明を省略する。
優先要求判定部１１０１は、読み出し要求が入力される毎に、それが優先要求であるか通常要求であるかを判定し、並び換え部１１０２に通知する。例えば、１５０ｍＳというしきい値を保持しておき、限界許容遅延時間が１５０ｍＳ以下であれば優先要求、それより大きければ通常要求と判定する。
【００６８】
並び換え部１１０２は、通常要求については第１実施例と全く同じであるが、優先要求についてはその限界許容遅延時間を満足できない場合には廃棄する。並び換え部１１０２の詳細な処理内容は、図５に示したフローチャートのステップ６１４とステップ６２１の間に図１１に示す処理を追加したものとなる。
図１１において、並び換え部１１０２は、ステップ６１４の続いて、優先要求判定部１１０１により読み出し要求Ｒ（α）が優先要求であると判定された場合には（ステップ１２１：ｙｅｓ）、キュー内の読み出し要求Ｒ（ｙ）の読み出しが完了するまでの時間ｔ１（ｙ）がその優先要求の限界許容遅延時間Ｔ１（α）より大きいときには（ステップ１２２：ｙｅｓ）、Ｒ（ｙ）の直後にＲ（α）登録し（ステップ６２１）、小さいときにはＲ（α）を廃棄する（ステップ１２３）。ここで、要求Ｒ（ｙ）の読み出しが完了するまでの時間ｔ１（ｙ））は、次式により計算される。
【００６９】
【数５】

【００７０】
上記のように並び換え部１１０２は、優先要求についてキュー内の挿入すべき位置を通常要求と同様にして決定し、その限界許容遅延時間が満足できない場合には廃棄する。これにより通常要求と優先要求とをその要求される品質に応じて処理することができる。
なお、上記第１、第２実施例では、シーク方向が一定になるように並び換えを行っているが、隣接する読み出し要求のトラック位置の間隔が小さい場合には部分的にシーク方向を逆行させるように並び換えてもよい。例えば、逆行が許されるトラック位置の間隔が５以内とする場合、ｏｆｆｓｅｔを５として図５のステップ６１４を次のように変更すればよい。
【００７１】
【数６】
この式の何れかを満たす場合にはステップ６１５へ進み、何れも満たさない場合にはステップ６２１へ進む。
第１実施例では全ての限界許容遅延時間を３００ｍＳとして説明したが、個々の読み出し要求毎に異なる限界許容遅延時間を有していても構わない。その場合でも（１）式に示したように、個々の読み出し要求の限界許容遅延時間Ｔ（ｘ）に基づいて許容遅延データＰ（ｘ）を計算しているので、個々の読み出し要求の限界許容遅延時間を満たすことができる。
【００７２】
第２実施例において優先要求判定部１１０１は、限界許容遅延時間としきい値との大小を比較することにより優先要求か通常要求かを判定したが、読み出し要求内に優先であるか通常であるかを示す情報（例えばフラグ）を持たせ、その情報により判定するようにしてもよい。
【００７３】
【発明の効果】
以上説明したように、請求項１の発明によれば、並び換え制御手段は、読み出し要求が入力される毎に、許容時間保持手段内の許容時間に基づいて、入力された読み出し要求とともにキュー手段内の読み出し要求を並び換える。これにより、読み出し要求が入力される毎にキューの並び換えを行うのでアクセス効率がよくなり、しかも、最大の限界許容遅延時間内のデータを出力することができる。特に動画や音声データに対してアクセス効率を向上させるとともに、リアルタイム性を確保することができるという効果がある。
【００７４】
加えて、新たにキューに追加された読み出し要求については、許容時間保持手段に許容時間を新たに設定し、元々キューにあった読み出し要求で順位が後順位に変更されたものについては、許容時間を更新するので、許容時間保持手段の各許容時間は、キューに新たな読み出し要求が追加された時点で必要なものだけを更新することができるという効果もある。
【００７５】
更に、入力された読み出し要求の許容時間は、前記許容時間算出手段内の第１の算出手段および第２の算出手段により算出される。
請求項２の発明によれば請求項１の効果に加えて、ディスクのヘッドシーク方向を一定に保つことによるアクセス効率の向上を図ることができる。
【００７６】
請求項３の発明によれば請求項２と同様の効果がある。請求項４の発明によれば請求項１の効果に加えて、比較的小さい距離のヘッドシーク逆行を許してディスクのヘッドシーク方向をほぼ一定に保つことによるアクセス効率の向上を図ることができる。請求項５の発明によれば請求項４と同様の効果がある。
【００７７】
請求項６の発明によれば請求項３又は５と同様の効果がある。請求項７の発明によれば請求項６の効果に加えて、許容時間をより高い精度で計算することができる。請求項８の発明によれば請求項７の効果に加えてに、限界許容遅延時間は、画一的に処理することができる。
【００７８】
請求項９の発明によれば請求項８と同様の効果がある。請求項１０の発明によれば請求項７の効果に加えて、読み出し要求毎に限界許容遅延時間が異なっている場合でも、それぞれの許容時間が順守されるので、読み出し要求毎に必要とされるデータ品質に応じて効率的に読み出すことができる。
【００７９】
請求項１１の発明によれば請求項１０の効果に加えて、廃棄される可能性が高いけれども短い遅延時間で優先要求が出力されるので、例えばディスク上のデータが映画を表す場合に、早送りや逆戻しを優先要求とすれば、要求されるデータ品質を満たして効率よくデータを読み出すことができる。請求項１２の発明によれば請求項９又は１１の効果に加えて、方向判定手段が禁止フラグを用いて判定することによって、入力された読み出し要求を挿入すべき位置の判定を迅速に行うことができる。
【００８０】
請求項１３の発明によれば請求項１２の効果に加えて、入力された読み出し要求がキューの末尾にしか追加できないことを迅速に判定することができる。請求項１４の発明によれば請求項１乃至１３の何れかの効果に加えて、リアルタイム性を要求されるビデオサーバにおいて、動画や音声を含むマルチメディアデータを、動画や音声を途切らせることなく効率よく読みだすことができる。
【図面の簡単な説明】
【図１】本発明の実施例におけるディスク制御装置の概略構成を示すブロック図である。
【図２】同実施例における読み出し要求がキューとして管理される様子を示す模式図である。
【図３】同実施例におけるディスク制御装置の詳細構成を示すブロック図である。
【図４】（ａ） キューテーブルを示す図である。
（ｂ） 許容遅延データテーブルを示す図である。
【図５】並び換え処理を示す詳細なフローチャートを示す。
【図６】（ａ）〜（ｃ） 並び換えの様子を示す模式図である。
【図７】（ａ）〜（ｃ） キューテーブル、許容遅延データテーブルの具体例を示す。
【図８】本発明によるディスク装置と従来のディスク装置の両者について、使用率−廃棄率特性をシミュレーションした結果を示す。
【図９】第２実施例のディスク制御装置の構成を示すブロック図である。
【図１０】並び換え制御部の詳細構成を示すブロック図である。
【図１１】並び換え制御部の処理を表すフローチャートである。
【図１２】従来のディスク装置の構成を示すブロック図である。
【符号の説明】
２００ ハードディスク
２０１ キュー管理部
２０２ 許容遅延データ管理部
２０３ 並び換え制御部
２１１ キューテーブル
２１２ 読出制御部
２２１ 許容遅延データテーブル
２２２ 限界許容遅延時間計算部
２３１ 読出時間計算部
２３２ トラック位置計算部
２３３ シーク時間計算部
２３４ 並び換え部[0001]
[Industrial applications]
The present invention relates to a disk control device in which a seek time is reduced for a randomly generated read request to improve read processing performance, and in particular, to processing a read request generated at a constant speed in real time. It relates to a disk controller used for a video server that requires it.
[0002]
[Prior art]
2. Description of the Related Art In recent years, a video server provided with a disk device for storing multimedia data including video data and audio data and supplying data to a plurality of users connected via a communication line has been put to practical use. The data supplied from the video server allows the user to watch the desired movie when he wants to watch it.
[0003]
In a video server, it is necessary to output data to a plurality of users in real time, and a technology for efficiently reading data on a disk is required. As a technology for efficiently reading a disk device, there is a technology for changing the data reading order so that the head seek direction of the disk device is constant.
FIG. 12 is a block diagram showing a configuration of a conventional disk control device. In FIG. 1, the disk control device includes a hard disk 100, a rearrangement control unit 102, and a hard disk 103.
[0004]
The hard disk 100 divides multimedia data representing a plurality of types of movies into pieces each having a certain size and stores the divided pieces.
The queue management unit 101 holds data read requests as queues and sequentially outputs the read requests to the hard disk 100.
The rearrangement control unit 102 registers the read request once in the queue management unit 101 every time it receives the read request, and further, all the read requests registered in the queue management unit 101 at regular time intervals, the head seek direction of the disk device is fixed. Rearrange so that The queue management unit 101 sequentially outputs the rearranged requests to the hard disk 100. As a result, the average seek time of the head in response to a read request from the hard disk 100 is reduced.
[0005]
[Problems to be solved by the invention]
However, in the above-described conventional configuration, there is a problem that the delay time from when a read request is generated to when data is output varies.
More specifically, data output from the video server must be continuously output at predetermined time intervals so that the data can be reproduced as a moving image. If the next data is not output within a predetermined period of time, for example, the video is skipped or the sound is interrupted, and the movie cannot be normally reproduced. Therefore, the disk device has an allowable range of delay time from when a read request is issued to when data is output (hereinafter, referred to as a limit allowable delay time). The prior art does not consider this limit allowable delay time.
[0006]
For example, in the related art, if the fixed time (interval for rearranging) is set sufficiently shorter than the permissible delay time, data can be output within the permissible delay time.
However, in this case, the number of read requests to be rearranged is reduced, so that the effect of shortening the seek time is sacrificed, and there is a problem that reading cannot be performed efficiently. Conversely, if the certain time is set longer than the allowable time, the number of read requests to be rearranged increases, so that the effect of shortening the seek time can be sufficiently obtained. As a result, there is a problem that a read request to be moved to a position beyond the permissible delay time occurs.
[0007]
As described above, in the related art, there is a trade-off between improving the read efficiency of the disk and keeping the marginal allowable delay time. Therefore, it is difficult to set the above-mentioned fixed time appropriately especially when the read requests are generated continuously or in bursts.
In view of the above problems, an object of the present invention is to provide a disk control device that efficiently accesses while satisfying a marginal allowable delay time required from when a read request is issued to when data is output.
[0008]
[Means for Solving the Problems]
In order to solve the above problems, the invention of claim 1 is:next Three It has two structural features.
1 The third isA disk control that holds a plurality of read requests as a queue, rearranges the read requests held together with the read requests each time a read request is input, sequentially retrieves the read requests from the queue, and outputs the requested data from the disk. A queue means for temporarily holding a read request for reading data from a disk as a rearrangeable queue; and a delay until completion of reading determined for each read request in the queue according to the order in the queue. A permissible time holding means for holding a permissible time indicating how much delay can be given to the time, and each time a read request is input, based on the permissible time of each read request in the queue. Reordering means for reordering read requests in the queue together with the input read requests And includes aIs a point.
[0009]
No. Two The structural features ofEach time the rearrangement is performed, for the input read request, the permissible time is calculated according to the rank in the queue and stored in the permissible time holding unit. A permissible time updating unit for updating each permissible time of the permissible time holding unit with respect to each read request changed to the rear rank to a value smaller by a delay time caused by the change of the rank.Is a point.
[0010]
The third structural feature is:Each time the queue is rearranged by the rearrangement control unit, the permissible time calculation unit advances the input read request from the inserted position in the queue to the beginning, and further takes out the data read from the disk. A first calculating means for calculating a delay time expected to be required, and a delay time from when the input read request is input to the rearrangement control means until the corresponding data is output from the disk. Second calculating means for calculating the allowable time for the input read request by subtracting the delay time calculated by the first calculating means from the maximum allowable delay time.Is a point.
[0011]
The invention of claim 2 is based on claim 1.The rearrangement control means searches for a position in the queue at which the head seek direction of the disk can be kept constant when the input read request is inserted into the queue every time a read request is input. Searching means, and time determining means for determining, when an input read request is inserted at the searched position, whether or not the permissible time of a read request which is a subsequent rank of the read request becomes 0 or less, Position determining means for determining a position to be inserted when the allowable time is determined not to be 0 or less as a position to be inserted, and a read input to insert the read request at the determined position A reordering means for reordering the read requests in the queue along with the requests.Have.
[0012]
The invention of claim 3 is based on claim 2,The read request includes the logical address of the data to be read and the size of the data, and the queue unit performs, for each read request in the queue, the order in the queue and the time from when the data is read and output immediately after the seek. A queue that holds the required transfer time, the track position on the disk where the corresponding data exists, and the seek time required for the head movement from the track position of the data of the immediately preceding rank to the track position of that rank. A track position calculating means for calculating a position of a track on a disk on which the corresponding data exists based on a logical address included in the input read request; Read and output data immediately after seek based on the data size included in the request A data transfer time calculating means for calculating a data transfer time required for the read request, and a seek time based on the track position in the queue table for a read request whose rank in the queue has been changed each time the queue is rearranged by the rearrangement means. And a seek time calculating means for calculating the read request in the queue table, wherein the searching means specifies the order of the read requests in the queue one by one from the end, and each time the order is specified. Direction determining means for determining whether the track position of the read request at the end of the queue and the track position of the read request of the designated order are in the same direction with respect to the track position calculated by the track position calculating means; And the rearranging means updates the order of the queue table so as to be inserted at the determined position, and Click position calculating means calculates the track position, corresponding to the read request input data transfer time calculated by the data transfer time calculating means for queued table.
[0013]
The invention of claim 4 is based on claim 1.The rearrangement control means allows the head seek direction of the disk to be relatively constant by allowing the head seek to move backward by a relatively small distance every time a read request is input, when the input read request is inserted into the queue; A search means for searching for a position in the queue that can be kept at a predetermined time, and when an input read request is inserted at the searched position, the allowable time of a read request that is ranked after the read request becomes 0 or less. Time determining means for determining whether or not the position is to be inserted, position determining means for determining the position to be inserted when the allowable time is determined not to be 0 or less, and position determining means for determining the position to be inserted. And a rearranging means for rearranging the read requests in the queue together with the input read requests so as to insert the read requests.
[0014]
The invention of claim 5 is based on claim 4,The read request includes the logical address of the data to be read and the size of the data, and the queue unit performs, for each read request in the queue, the order in the queue and the time from when the data is read and output immediately after the seek. A queue that holds the required transfer time, the track position on the disk where the corresponding data exists, and the seek time required for the head movement from the track position of the data of the immediately preceding rank to the track position of that rank. A track position calculating means for calculating a position of a track on a disk on which the corresponding data exists based on a logical address included in the input read request; Read and output data immediately after seek based on the data size included in the request A data transfer time calculating means for calculating a data transfer time required for the read request, and a seek time based on the track position in the queue table for a read request whose rank in the queue has been changed each time the queue is rearranged by the rearrangement means. And a seek time calculating means for calculating the read request in the queue table, wherein the searching means specifies the order of the read requests in the queue one by one from the end, and every time the order is specified. With respect to the track position calculated by the track position calculating means, it is determined whether the track position of the read request at the end of the queue and any of several tracks before and after the track position of the read request of the designated order are in the same direction. Determining means for determining the direction, wherein the rearranging means determines the order of the queue table so as to be inserted at the determined position. Updates the calculated track position on the track position calculating means, corresponding to the read request input data transfer time calculated by the data transfer time calculating means for queued table.
[0015]
The invention of claim 6 is based on claim 3 or 5,When the time determining means determines that the directions are in the same direction by the direction determining means, the data transfer time is subtracted from the allowable time corresponding to the read request of the order specified by the order specifying means, and the subtraction result is 0 or less. It is determined whether or not the position is determined. If the position determination unit determines that the vehicle is in the same direction by the direction determination unit, and the time determination unit determines that the value does not become 0 or less, the position determination unit is designated by the rank specification unit. If the direction determination means determines that the next order is not in the same direction, it determines between the read requests of the two orders the position where the input read request is to be inserted.
[0016]
The invention of claim 7 is based on claim 6,The first calculating unit adds the data transfer time and the seek time of all the first-order read requests in the queue to the input read request every time the queue is rearranged by the rearrangement unit. The delay time is calculated, and the permissible time updating unit sets each permissible time of the permissible time holding unit to a value smaller by the data transfer time for each read request whose rank in the queue has been changed to the rear rank by rearrangement. Update.
[0017]
The invention of claim 8 is based on claim 7,As the limit allowable delay time, a value common to all read requests is predetermined. An invention according to claim 11 is based on the tenth aspect, wherein the position determining means determines whether the position is in the same direction by the direction determining means and the time determining means determines that the position is equal to or less than 0. Is determined as the position to insert.
[0018]
The invention of claim 10 is based on claim 7,The limit allowable delay time is included in an input read request. According to a thirteenth aspect of the present invention, in accordance with the twelfth aspect, when the position determining means is determined to be in the same direction by the direction determining means and is determined to be 0 or less by the time determining means, Is determined as a position to insert the end of, and the read request is classified into a speed priority request that may be discarded for a short maximum allowable time and another request. Priority request determining means for determining whether the input read request is a priority request; and, if the read request is determined to be a priority request, and if the position determination means determines to insert at the end, If the addition result obtained by adding the data transfer time and the seek time of the read request is longer than the maximum allowable time of the priority request, discard judging means for judging to discard, and discarding With discarding the determined priority request, and a discarding means for inhibiting the operation of rearranging the control means for the priority request.
[0019]
The invention of claim 12 is based on claim 9 or 11,The permissible time holding unit further holds, for each read request in the queue, a prohibition flag indicating that another read request cannot be inserted immediately before the queue and that the seek direction is reversed, The changing means determines whether the direction is determined to be in the same direction by the direction determining means, is determined to be 0 or less by the time determining means, and the position determining means determines that the end of the queue is to be inserted. Sets a prohibition flag corresponding to the read request immediately preceding the read request inserted at the end after rearrangement.
[0020]
The invention of claim 13 is based on claim 12,The rearrangement control unit further includes: when a read request is input, a prohibition flag in the allowable time holding unit is set, and a prohibition flag detection unit that detects a read request closest to the end of the queue; With respect to the track position of the read request, the track position of the input read request,By the prohibition flag detection meansDetermine whether or not the track position of the detected read request is in the same directionSame direction determination meansAnd the position determining means are the sameDirection determination meansWhen it is determined that the input request is not in the same direction, the input read request is determined as a position where the end of the queue is to be inserted, and the search means includes:Same direction determination meansWhen it is determined that they are in the same direction, the search is performed.
[0021]
The invention of claim 14 is the invention of claims 1 to 13Any of the disk control devices is used in the video server, and the limit allowable delay time is a delay time required for real-time reproduction on the user side of the video server.
[0022]
[Action]
ContractIn the disk control device according to claim 1, the rearrangement control means, each time a read request is input, based on the allowable time in the read request holding means, together with the input read request and the read request in the queue means. Rearrange. Thereby, the queue is rearranged every time a read request is input, so that the access efficiency is improved. Further, since the maximum allowable delay time is satisfied, the real-time performance of moving image and audio data is ensured. be able to.
[0023]
Moreover,Each time the rearrangement is executed, the permissible time calculating means calculates the permissible time for the input read request in accordance with the rank in the queue and stores the permissible time in the permissible time holding means. The permissible time updating unit updates each permissible time of the permissible time holding unit to a value smaller by a delay time caused by the change of the rank for each read request whose rank in the queue has been changed to the rear rank by the rearrangement. As a result, for a read request newly added to the queue, the allowable time is newly set in the allowable time holding means, and for a read request originally in the queue whose rank has been changed to a rear rank, the allowable time is set. Can be updated.
[0024]
further,The allowable time of the input read request is calculated by the first calculating means and the second calculating means in the allowable time calculating means.
In the disk control device according to the second aspect,Each time a read request is input, the search means searches for a position in the queue where the head seek direction of the disk can be kept constant when the input read request is inserted into the queue. The time determination means determines whether or not the permissible time becomes 0 or less for the position searched by the search means. The position determining means determines the searched position when it is determined that the allowable time does not become 0 or less as the position to be inserted. The rearranging means rearranges the read requests in the queue together with the input read requests so as to insert the input read requests at the determined positions.
[0025]
In the disk control device according to the third aspect,The queue means implements a logical queue by including the queue table. Each time the order is specified by the order specifying means, the direction determining means in the searching means sets the track position of the queue read request to the track position calculated by the track position calculating means. It is determined whether the track position of the rank read request is in the same direction. The rearranging means updates the order of the cue table so as to be inserted at the position determined by the position determining means, and also updates the track position calculated by the track position calculating means and the data transfer calculated by the data transfer time calculating means. The time is stored in the queue table in correspondence with the input read request.
[0026]
In the disk control device according to the fourth aspect of the present invention,The search means allows the head seek direction of the disc to be kept relatively constant by permitting head seek reversal of a relatively small distance every time a read request is input and the input read request is inserted into the queue. Find a position in the queue where you can. The time determination means determines whether or not the allowable time of the read request after the read request is 0 or less when the input read request is inserted at the searched position. The position determining means determines the searched position when it is determined that the allowable time does not become 0 or less as the position to be inserted. The rearranging means rearranges the read requests in the queue together with the input read requests so as to insert the input read requests at the determined positions. As a result, the head seek can be maintained in a substantially constant direction while allowing the head seek backward for several tracks before and after without allowing the allowable time to become zero. That is, the backward movement can be permitted only when the track positions are extremely close.
[0027]
In the disk control device according to the fifth aspect of the present invention,The queue means implements a logical queue by including the queue table. Each time the order is specified by the order specifying means, the direction determining means compares the track position of the tail read request of the queue with the track position calculated by the track position calculating means and the read request of the specified order. It is determined whether any of several tracks before and after the track position is in the same direction.
[0028]
In the disk control device according to the sixth aspect of the present invention,The time determining means, when it is determined by the direction determining means that they are in the same direction, subtracts the data transfer time from the allowable time corresponding to the read request of the order specified by the order specifying means, and the subtraction result is 0 or less. Is determined. The position deciding means, when it is judged by the direction judging means to be in the same direction, and when it is judged by the time judging means that it does not become 0 or less, the direction judging means Are determined not to be in the same direction, the position between the read requests of the two orders is determined as the position where the input read request is to be inserted.
[0029]
In the disk control device according to the seventh aspect of the present invention,The first calculating means calculates the delay time by adding the data transfer time and the seek time of all read requests of the first priority in the queue table. The permissible time updating unit updates each permissible time of the permissible time holding unit to a value smaller by the data transfer time for each read request whose rank in the queue has been changed to the rear-rank by the rearrangement. As a result, the allowable time can be calculated with high accuracy.
[0030]
In the disk control device according to the eighth aspect of the present invention,As the limit allowable delay time, a value common to all read requests is predetermined. As a result, the limit allowable delay time is uniformly processed. In the disk control apparatus according to the eleventh aspect of the present invention, in the disk control device according to the tenth aspect, the position determining means is determined by the direction determining means to be in the same direction, and is determined to be 0 or less by the time determining means. In this case, the end of the queue is determined as the position to be inserted.
[0031]
In the disk control device according to the tenth aspect,The limit allowable delay time is included in an input read request.
In the disk control apparatus according to the eleventh aspect,The read request includes a priority request that has a short maximum allowable time and may be discarded, and other requests. The position determining means determines that the end of the queue is to be inserted when the direction determining means determines that the directions are in the same direction, and when the time determining means determines that the value is 0 or less. The discard determination unit adds the data transfer time and seek time of all read requests in the queue table when the priority request determination unit determines that the request is a priority request and the position determination unit determines that the request is inserted at the end. If the added result is longer than the maximum allowable time of the priority request, it is determined that the request is discarded. The discarding unit discards the priority request determined to be discarded by the discarding determining unit, and prohibits the operation of the rearrangement control unit for the priority request. And As a result, the priority request is output with a short delay time, but the possibility of being discarded increases. For example, when the data on the disk represents a movie, if fast-forward or reverse is used as the priority request, there are two types of priority requests. And the data can be efficiently read out.
[0032]
In the disk control device according to the twelfth aspect,The permissible time holding unit further holds, for each read request in the queue, a prohibition flag indicating that another read request cannot be inserted immediately before the queue and that the seek direction is reversed. The rearranging means is determined by the direction determining means to be in the same direction, is determined to be 0 or less by the time determining means, and is determined by the position determining means to be a position where the end of the queue is to be inserted. In this case, a prohibition flag corresponding to the read request immediately preceding the read request inserted at the end after the rearrangement is set. This makes it possible to quickly determine the position where the input read request is to be inserted.
[0033]
According to a thirteenth aspect of the present invention, there is provided a disk control apparatus according to the twelfth aspect, whereinMeans that when the read request is input, the prohibition flag in the permissible time holding means is set and the prohibition flag detection means for detecting the read request closest to the end of the queue, and the track position of the end read request Then, it is determined whether or not the track position of the input read request and the track position of the detected read request are in the same direction. The position determining means,Same direction determination meansWhen it is determined that the read request is not in the same direction, the input read request is determined as the position where the tail of the queue should be inserted. Further, the search means includes:Same direction determination meansWhen it is determined that they are in the same direction, the search is performed. This makes it possible to quickly determine that the input read request can only be added to the end of the queue.
[0034]
In the disk control apparatus according to the fourteenth aspect, the disk control apparatus according to any one of the first to thirteenth aspects is used for a video server, and the limit allowable delay time is a delay time required for real-time reproduction on the user side of the video server. It is. As a result, in a video server that requires real-time processing, multimedia data including moving images and audio can be efficiently read out without interrupting moving images and audio.
[0035]
【Example】
FIG. 1 is a block diagram illustrating a schematic configuration of a disk control device according to an embodiment of the present invention. In FIG. 1, the disk control device includes a hard disk 200, a queue management unit 201, an allowable delay data management unit 202, and a rearrangement control unit 203. By rearranging, the seek time is shortened, and data is output within the limit allowable delay time.
[0036]
The hard disk 200 stores a plurality of types of multimedia data by dividing the data by a certain size. When the disk controller is used in a video server, a movie of a plurality of titles is divided into a predetermined size (64 Kbytes) and stored.
The queue management unit 201 holds a plurality of continuously input read requests as a processing queue, and sequentially outputs the read requests to the hard disk 200. Here, the read request indicates a request for reading data of the predetermined size. FIG. 2 shows a schematic diagram of the queue. In the figure, R (1) -R (n) represents a read request in the queue. The read request R (1) at the head of the queue is output when the processing of the immediately preceding read request R (0) in the hard disk 200 is completed. R (α) represents a newly generated read request.
[0037]
The allowable delay data management unit 202 holds allowable delay data for each read request in the queue. Here, the permissible delay data indicates how much delay can be given to the read request at the current queue position to keep the limit permissible delay time. Specifically, for a read request newly added to the queue, the allowable delay data is newly calculated at the time the read request is added to the queue. Is changed to a lower rank, the allowable delay data is updated to a smaller value by a delay time caused by the change in the rank.
[0038]
The reordering control unit 203 shortens the seek time for the queue of the queue management unit 201 with reference to the permissible delay data managed by the permissible delay data management unit 202 every time a read request is input. Insert the input read request at the queue position.
Although not shown in FIG. 1, a user management unit that supplies a read request to the rearrangement control unit 203 will be described. In a video server, for a movie specified by a user, it is necessary to continuously supply a plurality of data constituting the movie to the user. Therefore, when the user management unit receives the designation of a specific movie from the user, the user management unit sequentially issues a request to read out individual data for the movie to the rearrangement control unit 203. This read request includes the logical address, the data size, and the limit allowable delay time. Here, the logical address is a logical address indicating the head position on the hard disk 200 of the data to be read. The data size is the size of the data to be read, for example, about 64 kbytes. The marginal allowable delay time is a condition for sequentially reproducing data without dividing the movie as a movie on the user side, and represents a maximum allowable delay time from issuance of a read request to output of data from the hard disk 200, For example, it is about 300 ms.
[0039]
FIG. 3 is a block diagram showing a more detailed configuration of the disk control device. As shown in the drawing, the queue management unit 201 rearranges the queue table 211 and the read control unit 212, and the allowable delay data management unit 202 rearranges the allowable delay data table 221 and the limit allowable delay time calculation unit 222. The control unit 203 includes a read time calculation unit 231, a track position calculation unit 232, a seek time calculation unit 233, and a rearrangement unit 234.
[0040]
The queue table 211 is a table for managing read requests logically as queues. FIG. 4A shows a configuration example of the queue table 211. As shown in the figure, the queue table 211 stores an order x, a read time t (x), a track position A (x), and a seek time S (x) corresponding to each read request R (x) in the queue. I do. Here, “order x” indicates the order of the read request in the queue. 1 indicates the head of the queue, and the maximum value n indicates the end of the queue. This n is also the queue length. Here, the “read time t (x)” is the time required to read and output the data corresponding to the read request R (x) on the hard disk 200 and the maximum rotation waiting time in the track, and Indicates the maximum time required to retrieve the data. The “track position A (x)” indicates the position of the cylinder where the data corresponding to the read request x is written (which track). “Seek time S (x)” indicates the time required to move the head from A (x−1) to A (x).
[0041]
The read control unit 212 detects whether the hard disk 200 is in the access state or the ready state, and immediately takes out the read request R (1) at the head of the queue table 211 when the hard disk 200 enters the ready state, and responds. The control of reading data from the hard disk 200 is performed. At this time, the read request R (1) and the data related thereto are deleted from the queue table 211, and the order x of the remaining read requests is updated (the order is increased).
[0042]
The allowable delay data table 221 is a table that holds the allowable delay data P (x) for each read request R (x) in the queue table 211. FIG. 4B shows a configuration example of the allowable delay data table 221. As shown in the figure, the permissible delay data table 221 stores permissible delay data P (x) and a prohibition flag flg (x) corresponding to each read request R (x) in the queue. Here, the “permissible delay data P (x)” indicates a permissible time indicating how far the read request R (x) can be delayed. If the “prohibition flag flg (x)” is ON, it indicates that a new request cannot be inserted before the request R (x) and that the seek direction is reversed before and after the read request. Represent.
[0043]
Each time a read request is added to the queue table 211 by the reordering unit 234, the limit allowable delay time calculation unit 222 refers to the queue table 211 for the added read request and the read requests in the subsequent order. Then, the allowable delay data is calculated and stored in the allowable delay data table 221. This calculation is based on the following formula (1) for the added read request, and based on the following formula (2) for the read request of a higher rank.
[0044]
(Equation 1)

[0045]
Here, T (x) indicates the limit allowable delay time of the read request R (x).
[0046]
(Equation 2)

[0047]
Formula (2) is to subtract the read time t (α) of the added read request from each P (x) for the read requests that are lower in rank than the added read request, and to calculate the value as P (x) Means to update. In addition, in Equation (2), in order to simplify the calculation, the effect on the seek time S (x) by adding the read request R (α) is not considered. For this effect is negligible. In this way, P (x) of the queue table 211 is newly calculated when a read request is added to the queue, and thereafter, when a rank is changed to a rear rank, a delay caused by a change in rank is generated. It will be updated to a value smaller by time.
[0048]
When a new read request R (α) is input to the rearrangement control unit 203, the read time calculation unit 231 calculates a read time t (α) for R (α). The read time t (α) is calculated by dividing the size of the data to be read by the minimum data transfer speed of the hard disk 200 and adding the maximum rotation wait time of the disk. For example, if the data size is 64 kbytes, the minimum data reading speed is 2.7 Mbytes / S, and the maximum rotation waiting time is 11.2 ms, the reading time t (α) = 64 k / 2.7 M + 11.2 = about 35 mS. Is calculated.
[0049]
When a new read request R (α) is input to the rearrangement control unit 203, the track position calculation unit 232 calculates a track position A (α) of data corresponding to the read request R (α). For example, when the data size per track on the inner and outer tracks of the disk is equal, the track position calculation unit 232 calculates the logical address LAmin of the innermost track of the hard disk 200, the logical address LAmax of the outermost track, and A (α) is obtained as follows based on the logical address LAα of R (α) and the total number of tracks TN.
[0050]
(Equation 3)

[0051]
Each time the reordering unit 234 adds a read request R (α) to the queue table 211, the seek time calculation unit 233 calculates a seek time S (x) for a read request after the added read request R (α). ) Is calculated. Specifically, the seek time calculation unit 233 obtains the seek time by dividing the distance between A (x) -A (x-1) by the seek speed of the head of the hard disk 200.
[0052]
The reordering unit 234 refers to the queue table 211 and the allowable delay data table 221 each time a new read request R (α) is input, and based on the read time t (α) and the seek time S (α). Then, rearrangement is performed so that all the read requests in the queue satisfy the limit allowable delay time and the seek direction is constant. FIG. 5 is a flowchart illustrating a detailed reordering process of the reordering unit 234. When the read request R (α) is input, the reordering unit 234 causes the read time calculation unit 231 and the track position calculation unit 232 to calculate the read time t (α) and the track position A (α), respectively (step 601). 602) If the queue length n of the queue table 211 is 0 (step 603: no), the read request R (α), the read time t (α), the track position A (α), and the seek time calculation unit 233 calculate The registered seek time S (α) is registered in the queue table 211, and the allowable delay data P (α) calculated by the limit allowable delay time calculator 222 and the prohibition flag flg (α) = OFF are stored in the allowable delay data. The information is registered in the table 221 (step 604). If the queue length n is 1 or more (step 603: yes), the reordering unit 234 sets the variable k as a parameter for decreasing the variable k by one from n in order from the end of the queue to the prohibition flag in the allowable delay data table 221. With reference to flg (k), a read request R (k) whose inhibit flag is ON is detected (steps 606-608).
[0053]
Further, the rearrangement unit 234 determines that the track position A (α) of the read request R (α) matches the track position A (n) of the last read request R (n) (step 609: yes) ), The read request R (α) is registered at the end of the queue in the queue table 211 together with t (α) and A (α) (step 611), and the limit allowable delay time calculation unit 222 and the seek time calculation unit 233 The allowable time P (α) and the seek time S (α) are calculated, and the calculation results are registered in the allowable delay data table 221 and the queue table 211 (step 612).
[0054]
If they do not match (step 609: no), the rearranging unit 234 determines whether the track position A (α) and the track position A (k) are in the same direction, as viewed from the track position A (n). Is determined. Specifically, the reordering unit 234 determines whether the product of (A (k) -A (n)) and (A (α) -A (n)) is positive but negative. It is determined whether it is in the direction.
[0055]
As a result, if not on the same side (step 610: no), as shown in FIG. 6A, the read request R (α) is registered at the end of the queue (step 611), and the limit allowable delay time calculation unit 222, causing the seek time calculation unit 233 to calculate P (α) and S (α) and to store t (α), A (α), S (α), P (α), and flg (α) in the queue table 211. Is registered in the allowable delay data table 221 (step 612). In this case, as shown in FIG. 6A, by registering the read request R (α) at the end, the seek direction of the hard disk 200 becomes constant as A (k) → A (n) → A (α). Will be kept.
[0056]
If they are on the same side (step 610: yes), the reordering unit 234 sets the variable y as a parameter for decreasing the variable y by one from n by one read request R (y) in the queue. The following processing is performed for each of the objects.
First, it is checked whether or not the seek direction can be kept constant even if R (α) is inserted immediately before R (y) and the limit allowable delay time of R (y) can be maintained. FIG. 6B is a schematic diagram showing this state. More specifically, when A (y) and A (n) are in the same direction as viewed from A (α), flg (y) is OFF, and P (y) ≧ t (α) (Step 614: yes, 615: no, 616yes), it is determined that R (α) can be inserted immediately before R (y). If the limit allowable delay time of R (y) cannot be maintained (P (y) ≧ t (α)) (step 616: no), flg (n) is turned on (step 617), R (α) is registered at the end of the queue (steps 618 and 619). The reason why flg (n) is turned ON is that read requests in all queues except for R (α) registered at the end are excluded from rearrangement, and seeks are performed after R (α). This is to reverse the direction.
[0057]
Next, when it is determined that the data can be inserted immediately before (step 616: yes), the variable y is updated to y = y-1, and the immediately preceding read request (step 620) is viewed from A (α). By determining whether A (y) and A (n) are in the same direction, it is determined whether the seek direction can be maintained even if R (α) is inserted immediately before R (y). . If it is determined that the seek direction can be maintained (step 614: yes), the processing after step 615 is performed in the same manner as described above. If it is determined that the seek direction cannot be maintained (step 614: no), R (α) is inserted immediately after R (y) (steps 621 and 622). FIG. 6C is a schematic diagram showing the situation in this case.
[0058]
The operation of the disk controller of the present invention configured as described above will be described below.
Now, it is assumed that the read requests R (1) to R (5) are already held in the queue table 211 and the allowable delay data table 221 as shown in FIG. In the example shown in the figure, the limit allowable delay time of all read requests is 300 mS, the data size is 64 kbytes, the maximum seek time of the hard disk 200 is 20 mS, the maximum rotation waiting time is 11.2 mS, and the maximum data transfer speed is It is assumed that 5.5 Mbytes, the minimum data transfer rate is 2.7 Mbytes, and the number of cylinders is 2000. In this case, the read time t (x) of each read request is 64 kbytes / 2.7 Mbytes + 11.2 mS = about 35 mS.
[0059]
In this state, when a new read request R (6) is input to the rearrangement control unit 203, the read time t (6) = 35 mS is calculated by the read time calculation unit 231 and the track position calculation unit 232 calculates the track position. A (6) is calculated. It is assumed that A (6) calculated here is 300. This read request R (6) is registered at the end of the queue because A (6) and A (2) are not in the same direction as viewed from the end A (5), as shown in FIG. Is done. FIG. 7B shows the registered result. Further, when a new read request R (7) is input to the rearrangement control unit 203 in this state, t (7) = 35 mS is calculated similarly. It is also assumed that A (7) = 1300 has been calculated. With respect to the read request R (7), A (7) (= 1300) and A (2) (= 2000) are in the same direction in the same direction as viewed from the end A (6) by the reordering unit 234. Is determined (step 610 in FIG. 5). Further, in order to determine at which position in the queue R (7) can be inserted, A (y) and A (6) (= 500) are in the same direction from A (7) (= 1300). Is determined. Here, when y = 6, 5, and 4, as shown in FIG. 6B, since the delay is in the same direction and the allowable delay data P (y) is larger than t (7) (step 614). (The loop of -616 and 620 is performed three times), and it is determined that insertion is possible immediately before R (y).
[0060]
Further, when y = 3, as shown in FIG. 6C, A (3) (= 1500) and A (6) (= 500) are in the same direction when viewed from A (7) (= 1300). (Step 614 in FIG. 5), it is determined that R (7) should be inserted immediately after R (3) (step 621). FIG. 7C shows a state where R (7) is inserted immediately after R (3). In this case, even if R (7) is inserted immediately after R (3), it is confirmed by the above-described three loop processes that the respective marginal allowable delay times of R (6) -R (4) can be maintained. Have been. Further, since the disc is inserted at a position where the seek direction can be kept constant, the reading efficiency of the disc is improved.
[0061]
Further, the performance limit of the disk control device will be further described. For example, in the state of FIG. 7C, it is assumed that a read request R (8) is further input. At this time, since P (7) = 21 mS and t (8) = 35 mS, P (7) ≧ t (8) is not satisfied (step 616: no), and R (8) is registered at the end of the queue. Will be. At this time, P (8) becomes smaller than 0. As a result, R (8) cannot satisfy the limit allowable delay time. Failure to satisfy the limit allowable delay time means that many read requests have been input beyond the performance of the disk controller. Improving the read efficiency of the disk will improve the performance of the disk device.
[0062]
As described above, according to the disk control device of the present invention, it is possible to improve the disk reading efficiency while satisfying the limit allowable delay time for each reading time.
FIG. 8 shows the results of simulating the usage rate / discard rate characteristics of both the disk controller of the present invention and the conventional disk controller. In the figure, the “usage rate” on the horizontal axis indicates the ratio of the amount of read data when the amount of data obtained by continuously reading 64 kbytes of data is 1.0. This data acquisition amount (use rate = 1.0) is given by the following equation when the average data transfer time, average rotation wait time, and average seek time of the hard disk 200 are represented by Ttransmit, Twait, and Tseek, respectively.
[0063]
(Equation 4)

[0064]
The “discard rate” on the vertical axis represents the rate of read requests in which data was discarded after reading because the processing was performed beyond the permissible delay time. As shown in the figure, in the disk control device of the present invention, the discard rate is reduced by two to four orders of magnitude compared to the prior art (reduced to 1/100 to 1 / 10,000). It can be seen that the reading efficiency has been improved.
[0065]
Hereinafter, a second embodiment of the present invention will be described. FIG. 9 is a block diagram illustrating a configuration of a disk control device according to the second embodiment. The same components as those in FIG. 1 are denoted by the same reference numerals and the description thereof will be omitted.
The disk control device of FIG. 9 is different from the first embodiment in that a rearrangement control unit 1003 is provided in place of the rearrangement control unit 203, and in addition to a read request (hereinafter, referred to as a normal request) similar to that of the first embodiment. In that priority requests that need to be read preferentially are accepted. Here, the priority request is a request that has a short marginal allowable delay time but is permitted to be discarded. For example, when the user instructs fast-forward or reverse playback in the video server, the data to be supplied to the user may be slightly missing, but the delay time needs to be reduced. In such a case, a priority request is used. Further, the normal request is a request in which the marginal allowable delay time is longer than that of the priority request, and the discard needs to be minimized. In a video server, this corresponds to normal reproduction.
[0066]
In FIG. 9, the rearrangement control unit 1003 accepts a priority request in addition to a normal request and registers the priority request in a queue position that satisfies the limit allowable delay time of a read request already held in the queue. The same is true. At this time, if the limit allowable delay time of the priority request cannot be satisfied at the queue position to be registered, the priority request is discarded.
[0067]
FIG. 10 shows a detailed configuration of the rearrangement control unit 1003. In the figure, components other than a priority request determination unit 1101 and a rearrangement unit 1102 are the same as those in the first embodiment, and a description thereof is omitted.
Each time a read request is input, the priority request determination unit 1101 determines whether the read request is a priority request or a normal request, and notifies the rearrangement unit 1102 of the read request. For example, a threshold value of 150 mS is held, and if the permissible delay time is 150 mS or less, it is determined that the request is a priority request, and if it is longer than that, the request is determined to be a normal request.
[0068]
The reordering unit 1102 is exactly the same as that of the first embodiment for the normal request, but discards the priority request when the limit allowable delay time cannot be satisfied. The detailed processing contents of the reordering unit 1102 are obtained by adding the processing shown in FIG. 11 between steps 614 and 621 of the flowchart shown in FIG.
In FIG. 11, after the step 614, if the read request R (α) is determined to be a priority request by the priority request determination unit 1101 (step 121: yes), the rearrangement unit 1102 When the time t1 (y) until the reading of the read request R (y) is completed is longer than the limit allowable delay time T1 (α) of the priority request (step 122: yes), R (y) immediately follows R (y). α) is registered (step 621), and if smaller, R (α) is discarded (step 123). Here, the time t1 (y) until the reading of the request R (y) is completed is calculated by the following equation.
[0069]
(Equation 5)

[0070]
As described above, the reordering unit 1102 determines the position of the priority request to be inserted in the queue in the same way as the normal request, and discards the priority request if the allowable delay time cannot be satisfied. As a result, the normal request and the priority request can be processed according to the required quality.
In the first and second embodiments, the rearrangement is performed so that the seek direction is constant. However, when the interval between adjacent read request track positions is small, the seek direction is partially reversed. May be rearranged as follows. For example, if the interval between the track positions where the backward movement is allowed is within 5, the offset may be set to 5 and the step 614 in FIG. 5 may be changed as follows.
[0071]
(Equation 6)
If any of the expressions is satisfied, the process proceeds to step 615; otherwise, the process proceeds to step 621.
In the first embodiment, all the permissible delay times have been described as 300 mS, but different read requests may have different permissible delay times. Even in that case, as shown in the equation (1), the allowable delay data P (x) is calculated based on the limit allowable delay time T (x) of each read request. The delay time can be satisfied.
[0072]
In the second embodiment, the priority request determination unit 1101 determines whether the request is a priority request or a normal request by comparing the threshold allowable delay time with the threshold value. (E.g., a flag) indicating the information, and the determination may be made based on the information.
[0073]
【The invention's effect】
As described above, according to the first aspect of the present invention, each time a read request is input, the rearrangement control unit sets the queue unit together with the input read request based on the allowable time in the allowable time holding unit. Rearrange the read requests in the list. Thus, the queue is rearranged each time a read request is input, so that access efficiency is improved, and data within the maximum allowable delay time can be output. In particular, it has the effect of improving access efficiency to video and audio data and ensuring real-time performance..
[0074]
In addition, for a read request newly added to the queue, a new allowable time is set in the allowable time holding means, and for a read request originally in the queue whose rank is changed to a lower rank, the allowable time is changed. UpdateSoEach permissible time of the permissible time holding means can be updated only when necessary when a new read request is added to the queue.There is also an effect.
[0075]
Furthermore,The allowable time of the input read request is calculated by the first calculating means and the second calculating means in the allowable time calculating means.
According to the invention of claim 2, in addition to the effect of claim 1,Access efficiency can be improved by keeping the head seek direction of the disk constant.
[0076]
According to the invention of claim 3, claim 2Has the same effect as.According to the invention of claim 4, claim 1In addition to the effects described above, the head seek direction of the disk is allowed to reverse in a relatively small distance to maintain the head seek direction of the disk substantially constant, thereby improving the access efficiency.According to the invention of claim 5, claim 4Has the same effect as.
[0077]
According to the invention of claim 6, claim 3 or 5Has the same effect as.According to the invention of claim 7, claim 6In addition to the effect, the permissible time can be calculated with higher accuracy.According to the invention of claim 8, claim 7In addition to the above effect, the marginal allowable delay time can be uniformly processed.
[0078]
According to the invention of claim 9, claim 8Has the same effect as.According to the tenth aspect, the seventh aspect is provided.In addition to the effect of the above, even when the marginal allowable delay time differs for each read request, the respective allowable time is observed, so that it is possible to read efficiently according to the data quality required for each read request. it can.
[0079]
According to the invention of claim 11, claim 10In addition to the effects ofhand,Since the priority request is output with a short delay time although it is highly likely to be discarded, if the data on the disc represents a movie, for example, if fast-forward or reverse is a priority request, the required data quality is satisfied. Data can be read out efficiently.According to the invention of claim 12, claim 9 or 11In addition to the effect described above, the direction determining means makes a determination using the prohibition flag, whereby the position where the input read request is to be inserted can be quickly determined.
[0080]
According to the invention of claim 13, claim 12In addition to the effect described above, it is possible to quickly determine that the input read request can be added only to the end of the queue.According to the invention of claim 14, claims 1 to 13In addition to the effects of any of the above, in a video server that requires real-time processing, multimedia data including moving images and audio can be efficiently read out without interrupting moving images and audio.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a schematic configuration of a disk control device according to an embodiment of the present invention.
FIG. 2 is a schematic diagram illustrating a state in which a read request is managed as a queue in the embodiment.
FIG. 3 is a block diagram showing a detailed configuration of a disk control device in the embodiment.
FIG. 4A shows a queue table.
(B) is a diagram showing an allowable delay data table.
FIG. 5 is a detailed flowchart showing a rearrangement process.
FIGS. 6A to 6C are schematic diagrams showing a state of rearrangement.
7A to 7C show specific examples of a queue table and an allowable delay data table.
FIG. 8 shows the results of simulating the usage rate-discard rate characteristics of both the disk device according to the present invention and the conventional disk device.
FIG. 9 is a block diagram illustrating a configuration of a disk control device according to a second embodiment.
FIG. 10 is a block diagram illustrating a detailed configuration of a rearrangement control unit.
FIG. 11 is a flowchart illustrating a process of a rearrangement control unit.
FIG. 12 is a block diagram showing a configuration of a conventional disk device.
[Explanation of symbols]
200 hard disk
201 Queue management unit
202 Allowable delay data management unit
203 Rearrangement control unit
211 queue table
212 read control unit
221 Allowable delay data table
222 Limit allowable delay time calculator
231 Read time calculation unit
232 Track position calculation unit
233 seek time calculator
234 Rearranger

Claims (14)

A disk control that holds a plurality of read requests as a queue, rearranges the read requests held together with the read requests each time a read request is input, sequentially retrieves the read requests from the queue, and outputs the requested data from the disk. A queue means for temporarily holding a read request for reading data from a disk as a rearrangeable queue; and a delay until completion of reading determined for each read request in the queue according to the order in the queue. A permissible time holding unit for holding a permissible time indicating how much delay can be given to the time, and each time a read request is input, based on the permissible time of each read request in the queue. Reordering means for reordering read requests in the queue together with the input read requests , Each time the rearrangement is performed, for input read request, the permissible time calculating means for storing the allowable time holding unit calculates the allowable time according to rank in the queue, the reordering, rank in the queue Updating the permissible time of the permissible time holding means for each read request changed to the rear rank to a value smaller by the delay time due to the change of the rank, and the permissible time calculating means, Each time the queue is rearranged by the rearrangement control means, it is expected that the input read request will proceed from the inserted position in the queue to the head, and will be required until it is taken out and the data read from the disk is completed. A first calculating means for calculating the delay time, and a response from the time when the input read request is input to the rearrangement control means By subtracting the delay time calculated by the first calculation means from the maximum allowable delay time allowed as a delay time until data is output from the disk, the allowable time for the input read request is calculated. A second calculating means for performing the calculation . Each time a read request is input, the rearrangement control means searches for a position in the queue where the head seek direction of the disk can be kept constant when the input read request is inserted into the queue. Time determining means for determining whether an allowable time of a read request which is a subsequent rank of the read request when the input read request is inserted at the searched position is 0 or less; Position determining means for determining the searched position to be inserted when the time is determined not to be 0 or less, and a read request input so as to insert the input read request at the determined position 2. The disk control device according to claim 1, further comprising a rearrangement unit that rearranges read requests in the queue. The read request includes the logical address of the data to be read and the size of the data, and the queue unit performs, for each read request in the queue, the order in the queue and the time from when the data is read and output immediately after the seek. A queue that holds the required transfer time, the track position on the disk where the corresponding data exists, and the seek time required for the head movement from the track position of the data of the immediately preceding rank to the track position of that rank. A track position calculating means for calculating a position of a track on a disk on which the corresponding data exists based on a logical address included in the input read request; Read and output data immediately after seek based on the data size included in the request A data transfer time calculating means for calculating a data transfer time required for the read request, and a seek time based on the track position in the queue table for a read request whose rank in the queue has been changed each time the queue is rearranged by the rearrangement means. And a seek time calculating means for calculating the read request in the queue table, wherein the searching means specifies the order of the read requests in the queue one by one from the end, and each time the order is specified. Direction determining means for determining whether the track position of the read request at the end of the queue and the track position of the read request of the designated order are in the same direction with respect to the track position calculated by the track position calculating means; And the rearranging means updates the order of the queue table so as to be inserted at the determined position, and Click position calculated track position in the calculation means, the disk according to claim 2, wherein the storing in correspondence with the read request input data transfer time calculated by the data transfer time calculating unit in the queue table Control device. Each time a read request is input, the rearrangement control means allows the head seek direction of the disk to be substantially constant by allowing head seek reverse of a relatively small distance when the input read request is inserted into the queue. Search means for searching for a position in the queue that can be kept, and when an input read request is inserted at the searched position, the permissible time of a read request that is ranked after the read request becomes 0 or less. Time determination means for determining whether or not the allowable time does not become 0 or less, position determination means for determining the position to be inserted when the searched position is to be inserted, and readout input to the determined position request to insert, de according to claim 1, characterized in that it comprises a rearrangement unit with input read request rearranges the read request in the queue Disk controller. The read request includes the logical address of the data to be read and the size of the data, and the queue unit performs, for each read request in the queue, the order in the queue and the time from when the data is read and output immediately after the seek. A queue that holds the required transfer time, the track position on the disk where the corresponding data exists, and the seek time required for the head movement from the track position of the data of the immediately preceding rank to the track position of that rank. A track position calculating means for calculating a position of a track on a disk on which the corresponding data exists based on a logical address included in the input read request; Read and output data immediately after seek based on the data size included in the request A data transfer time calculating means for calculating a data transfer time required for the read request, and a seek time based on the track position in the queue table for a read request whose rank in the queue has been changed each time the queue is rearranged by the rearrangement means. And a seek time calculating means for calculating the read request in the queue table, wherein the searching means specifies the order of the read requests in the queue one by one from the end, and every time the order is specified. With respect to the track position calculated by the track position calculating means, it is determined whether the track position of the read request at the end of the queue and any of several tracks before and after the track position of the read request of the designated order are in the same direction. Determining means for determining the direction, wherein the rearranging means determines the order of the queue table so as to be inserted at the determined position. Updates the, claims, characterized in that to store the calculated track position on the track position calculating means, corresponding to the read request input data transfer time calculated by the data transfer time calculating unit in the queue table 5. The disk control device according to item 4 . The time determining means, when it is determined by the direction determining means that they are in the same direction, subtracts the data transfer time from the allowable time corresponding to the read request of the order specified by the order specifying means, and the subtraction result is 0 or less. Is determined by the direction determining means, and if the time determining means determines that it does not become 0 or less, the position determining means is designated by the rank specifying means. and for the next order, when it is determined that the direction determining means is not in the same direction, claims and determining the position for inserting a read request input between the read request of the two rank Item 6. The disk control device according to item 3 or 5 . The first calculating unit adds the data transfer time and the seek time of all the first-order read requests in the queue to the input read request each time the queue is rearranged by the rearrangement unit. A delay time is calculated, and the permissible time updating unit sets each permissible time of the permissible time holding unit to a value smaller by the data transfer time for each read request whose rank in the queue has been changed to the rear rank by rearrangement. 7. The disk controller according to claim 6 , wherein said disk controller is updated. 8. The disk control device according to claim 7, wherein a value common to all read requests is predetermined for the limit allowable delay time. The position determining means determines that the end of the queue is to be inserted when the direction determining means determines that they are in the same direction, and when the time determining means determines that it is 0 or less. 9. The disk control device according to claim 8, wherein: 8. The disk control device according to claim 7 , wherein the limit allowable delay time is included in an input read request. The position determining means determines that the end of the queue is to be inserted when it is determined by the direction determining means to be in the same direction and is determined to be 0 or less by the time determining means. Requests are classified into priority requests that may be discarded for a short maximum allowable time and other requests, and the rearrangement determination control unit further determines whether the input read request is a priority request. If the priority request is determined to be a priority request, and if it is determined to be inserted at the end by the position determining means, an addition result obtained by adding the data transfer time and seek time of all read requests in the queue table is obtained. If it is longer than the maximum permissible time of the priority request, the discard determination means for determining to discard, the priority request determined to be discarded is discarded, and the priority request is discarded. The disk control apparatus according to claim 10, characterized in that it comprises a discarding means for inhibiting the operation of the rearrangement control unit for seeking. The permissible time holding unit further holds, for each read request in the queue, a prohibition flag indicating that another read request cannot be inserted immediately before the queue and that the seek direction is reversed, The changing means determines whether the direction is determined to be in the same direction by the direction determining means, is determined to be 0 or less by the time determining means, and the position determining means determines that the end of the queue is to be inserted. 12. The disk control device according to claim 9 , wherein: sets a prohibition flag corresponding to a read request immediately preceding the read request inserted at the end after rearrangement. The rearrangement control unit further includes: when a read request is input, a prohibition flag in the allowable time holding unit is set, and a prohibition flag detection unit that detects a read request closest to the end of the queue; Same direction determining means for determining whether the track position of the input read request and the track position of the read request detected by the prohibition flag detecting means are in the same direction with respect to the track position of the read request. wherein the position determining means, when it is determined that it is not in the same direction by the same direction determining means determines the input read request to the position to be inserted at the end of the queue, the searching section, the same direction 13. The disk control device according to claim 12 , wherein the search is performed when the determination unit determines that the directions are the same. 14. The disk according to claim 1 , wherein the disk control device is used in a video server, and the limit allowable delay time is a delay time required for real-time reproduction on a user side of the video server. Control device.

Images