(57)【要約】記憶装置(110)のスケジューリング・アルゴリズムのブリージングの方法。該方法は：(a)記憶装置(110)のブリージング・サイクル（P）の最悪の場合の持続時間を計算する工程；(b)ブリージング・サイクルを開始する工程；(c)以下；(i)リアルタイム要求数が、データ・ストリーム数と、記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であるという条件；並びに(ii)何れかの単一のストリームに対する未処理要求数が2つ以上になるという条件；のうちの一方がPの終了前に真になるかを判定する工程；(d)(i)と(ii)とのうちの少なくとも一方がPの持続時間中に真の状態のままにとどまる場合、ブリージング・サイクルの完了後に後続ブリージング・サイクルを開始する工程；及び(e)(i)と(ii)との何れもPの持続時間中真でない場合、後続ブリージング・サイクルを開始するまで、ブリージング・サイクルの開始からP時間単位、待つ工程；を有する。
2006512636.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置のスケジューリング・アルゴリズムのブリージングの方法であって：
(a)該記憶装置のブリージング・サイクルの最悪の場合の持続時間を計算する工程；
を備え；
該最悪の場合の持続時間はPによって表し；
更に、(b)ブリージング・サイクルを開始する工程；及び
(c)(i)と(ii)とのうちの一方が、P時間単位の終了前に真になるかを判定する工程；
を備え；
(i)は、リアルタイム要求数がデータ・ストリーム数と、該記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であるという条件であり；
(ii)は、何れかの単一のストリームに対する未処理要求数が2つ以上になるという条件であり；
更に、(d)(i)と(ii)とのうちの少なくとも一方が、該ブリージング・サイクルの該開始からP時間単位の該持続時間中に真のままにとどまる場合に、該ブリージング・サイクルの完了後に後続ブリージング・サイクルを開始する工程；及び
(e)  (i)も(ii)も前記ブリージング・サイクルの該開始からP時間単位の該持続時間中に真でない場合、前記後続ブリージング・サイクルを開始する前に、前記ブリージング・サイクルの該開始からP時間単位待つ工程；
を備えることを特徴とする方法。
【請求項２】
請求項1記載の方法であって：
該ブリージング・サイクル中に到着するベスト・エフォート要求が該ブリージング・サイクル中に処理されることを特徴とする方法。
【請求項３】
請求項1記載の方法であって、更に：
複数のブリージング・サイクルについて、工程(b)乃至(e)を繰り返す工程；
を備えることを特徴とする方法。
【請求項４】
請求項1記載の方法であって、更に：
(f)(ii)の該条件の判定に基づいてデータ・ストリームの実際ビット・レートを計算する工程；
を備えることを特徴とする方法。
【請求項５】
請求項4記載の方法であって、更に：
(g)工程(f)の該計算に基づいて該データ・ストリームのビット・レートを変更する工程；
を備えることを特徴とする方法。
【請求項６】
請求項5記載の方法であって、工程(g)が：
該データ・ストリームの推定最大ビット・レートを超える場合に該データ・ストリームの高ビット・レートを確保する工程；
を備えることを特徴とする方法。
【請求項７】
請求項6記載の方法であって：
該データ・ストリームが、該記憶装置とバッファとの間で転送され；
更に：
(h)該バッファのサイズを増加させる工程；
を備えることを特徴とする方法。
【請求項８】
請求項5記載の方法であって、工程(g)が：
該データ・ストリームの推定最大ビット・レートを超えない場合に該データ・ストリームの低ビット・レートを確保する工程；
を備えることを特徴とする方法。
【請求項９】
請求項8記載の方法であって：
該データ・ストリームが該記憶装置とバッファとの間で転送され；
更に、(h)該バッファのサイズを低減させる工程；
を備えることを特徴とする方法。
【請求項１０】
記憶装置のスケジューリング・アルゴリズムのブリージングを制御する記憶装置スケジューラであって：
(a)該記憶装置のブリージング・サイクルの最悪の場合の持続時間を計算する工程を行う手段；
を備え；
該最悪の場合の持続時間はPによって表し；
更に、(b)ブリージング・サイクルの開始を命令する工程を行う手段；及び
(c)(i)と(ii)とのうちの一方が、P時間単位の終了前に真になるかを判定する工程を行う手段；
を備え；
(i)は、リアルタイム要求数がデータ・ストリーム数と、該記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であるという条件であり；
(ii)は、何れかの単一のストリームに対する未処理要求数が2つ以上になるという条件であり；
更に、(d)(i)と(ii)とのうちの少なくとも一方が、該ブリージング・サイクルの該開始からP時間単位の該持続時間中に真のままにとどまる場合に、該ブリージング・サイクルの完了後に後続ブリージング・サイクルを開始する工程を行う手段；及び
(e)  (i)も(ii)も前記ブリージング・サイクルの該開始からP時間単位の該持続時間中に真でない場合、前記後続ブリージング・サイクルを開始する前に、前記ブリージング・サイクルの該開始からP時間単位待つ工程を行う手段；
を備えることを特徴とする記憶装置スケジューラ。
【請求項１１】
請求項10記載の記憶装置スケジューラであって、更に：
複数のブリージング・サイクルについて、手段(b)における前記工程と、手段(c)における前記工程と、手段(d)における前記工程と、手段(e)における前記工程とを繰り返す工程；
を備えることを特徴とする記憶装置スケジューラ。
【請求項１２】
請求項10記載の記憶装置スケジューラであって、更に：
(f)(ii)の前記条件の判定に基づいてデータ・ストリームの実際ビット・レートを計算する工程；
を行う手段を備えることを特徴とする記憶装置スケジューラ。
【請求項１３】
請求項12記載の記憶装置スケジューラであって、更に：
(g)工程(f)の該計算に基づいて該データ・ストリームのビット・レートを変更する工程；
を行う手段を備えることを特徴とする記憶装置スケジューラ。
【請求項１４】
請求項13記載の記憶装置スケジューラであって、工程(g)が：
該データ・ストリームの推定最大ビット・レートを超える場合に該データ・ストリームの高ビット・レートを確保する工程；
を行う手段を備えることを特徴とする記憶装置スケジューラ。
【請求項１５】
請求項14記載の記憶装置スケジューラであって：
該データ・ストリームが、該記憶装置とバッファとの間で転送され；
更に：
(h)該バッファのサイズを増加させる工程；
を行う手段を備えることを特徴とする記憶装置スケジューラ。
【請求項１６】
請求項13記載の記憶装置スケジューラであって、工程(g)が：
該データ・ストリームの推定最大ビット・レートを超えない場合に該データ・ストリームの低ビット・レートを確保する工程；
を行う手段を備えることを特徴とする記憶装置スケジューラ。
【請求項１７】
請求項16記載の記憶装置スケジューラであって：
該データ・ストリームが該記憶装置とバッファとの間で転送され；
更に、(h)該バッファのサイズを低減させる工程；
を行う手段を備えることを特徴とする記憶装置スケジューラ。
【請求項１８】
請求項10記載の記憶装置スケジューラであって、更に：
該ブリージング・サイクル中に到着するベスト・エフォート要求を該ブリージング・サイクル中に処理する手段；
を備えることを特徴とする記憶装置スケジューラ。
【請求項１９】
マシンによって判読可能なプログラム記憶装置であって：
記憶装置のスケジューリング・アルゴリズムのブリージングの方法を行うよう該マシンによって実行可能な命令のプログラムを有形的に実施し；
該方法が：
(a)該記憶装置のブリージング・サイクルの最悪の場合の持続時間を計算する工程；
を備え；
該最悪の場合の持続時間はPによって表し；
該方法が更に、(b)ブリージング・サイクルを開始する工程；及び
(c)(i)と(ii)とのうちの一方が、P時間単位の終了前に真になるかを判定する工程；
を備え；
(i)は、リアルタイム要求数がデータ・ストリーム数と、該記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であるという条件であり；
(ii)は、何れかの単一のストリームに対する未処理要求数が2つ以上になるという条件であり；
該方法が更に、(d)(i)と(ii)とのうちの少なくとも一方が、該ブリージング・サイクルの該開始からP時間単位の該持続時間中に真のままにとどまる場合に、該ブリージング・サイクルの完了後に後続ブリージング・サイクルを開始する工程；及び
(e)  (i)も(ii)も前記ブリージング・サイクルの該開始からP時間単位の該持続時間中に真でない場合、前記後続ブリージング・サイクルを開始する前に、前記ブリージング・サイクルの該開始からP時間単位、待つ工程；
を備えることを特徴とするプログラム記憶装置。
【請求項２０】
コンピュータ判読媒体において実施されて、記憶装置のスケジューリング・アルゴリズムのブリージングを行うコンピュータ・プログラム・プロダクトであって：
(a)該記憶装置のブリージング・サイクルの最悪の場合の持続時間を計算するコンピュータ判読可能プログラム・コード手段；
を備え；
該最悪の場合の持続時間はPによって表し；
更に、(b)ブリージング・サイクルを開始するコンピュータ判読可能プログラム・コード手段；及び
(c)(i)と(ii)とのうちの一方が、P時間単位の終了前に真になるかを判定するコンピュータ判読可能プログラム・コード手段；
を備え；
(i)は、リアルタイム要求数がデータ・ストリーム数と、該記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であるという条件であり；
(ii)は、何れかの単一のストリームについての未処理要求数が2つ以上になるという条件であり；
更に、(d)(i)と(ii)とのうちの少なくとも一方が、該ブリージング・サイクルの該開始からP時間単位の該持続時間中に真のままにとどまる場合に、該ブリージング・サイクルの完了後に後続ブリージング・サイクルを開始するコンピュータ判読可能プログラム・コード手段；及び
(e)  (i)も(ii)も前記ブリージング・サイクルの該開始からP時間単位の該持続時間中に真でない場合、前記後続ブリージング・サイクルを開始する前に、前記ブリージング・サイクルの該開始からP時間単位待つコンピュータ判読可能プログラム・コード手段；
を備えることを特徴とする記憶装置スケジューラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、ディスク・スケージューリング・アルゴリズムのブリージングに関し、特に、リアル・タイム要求の処理を遅延させることによってブリージングを改善して、特定の条件が満たされていないという前提で、ディスク・スケジューリング・アルゴリズムの従来技術のブリージングに関連した課題を軽減する方法に関する。
【背景技術】
【０００２】
現行のサイクル・ベースのディスク・スケジューリング・アルゴリズムは、ストリーム毎に最大でも1つのディスク・アクセスがバッチ毎に処理されるような方法で、バッチ単位でディスク要求を処理する。最大ビット・レートが各ストリームについて既知であるということと、ディスクの保証スループットの正確なモデルとを前提とすれば、最悪の場合のサイクルの持続時間が判定され、そのサイクルに基づいて、バッファ・サイズと、ディスクとバッファとの間で繰り返し転送されるブロックのサイズが判定される。更に、いわゆるベスト・エフォート要求に対する帯域を、ベスト・エフォート要求に対する最悪の場合のサイクルの所定の割合を確保することによって確保することが可能である。
【０００３】
ディスク・アルゴリズムは、先行バッチが完了すると直ちに新たなバッチが処理されるという意味合いでブリージングと呼ばれている。最悪の場合の、サイクル、バッファ・サイズ、及びブロック・サイズを判定するうえで、ストリームのビット・レートと、ディスク性能パラメータとに関する最悪の場合の前提が組み入れられているということを前提とすれば、バッチ毎のリアルタイム要求数は通常、ストリーム数よりもかなり小さくなる。ディスクに対する現行負荷が低い場合、バッチは小さくなり、新たなストリームを開始する工程又は大きなベスト・エフォート要求を出す工程に対する応答時間は小さくなる。ディスクに対する負荷が増大する際にはいつでも、更に大きなバッチの処理が自動的に行われ始めることになり、そうするうえで、切り替えに費やす時間は少なくなる。よって、必要な場合はいつでも、ディスクは更に効率的に処理し始めることになる。このブリージング特性の別の効果としては、公称ビット・レートよりも高いビット・レートを一時的又は連続的に必要とするストリームであるローグ・ストリームに対する上記アルゴリズムの依存性が低いことがある。上記アルゴリズムが利用可能な帯域がある際にはいつでも、別のストリームに保証された性能を脅かすことなく、最悪の場合の解析において明確にされた頻度よりも多く、それらのストリームを自動的に処理することになる。よって、ディスクの性能が最悪の場合の性能よりも良好であることと、公称最大ビット・レートよりも小さいビット・レートを一部の別のストリームが必要とすることが理由で利用可能になる利用可能帯域は全ては浪費されずに、ローグ・ストリームに費やすことが可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、これらのブリージング・アルゴリズムにはいくつかの欠点が関係する。先行バッチが完了される際にはいつでも、新たなバッチを直ちに開始することは、以下の欠点を有する。すなわち、
1.  通常のPCアプリケーションでは通常のことである、ベスト・エフォート要求を一度に１つだけしか出さないアプリケーションは、サイクル毎に１つのベスト・エフォート要求しか出すことができないことになる。このアプリケーションが多くの小さい要求を出すが、１つの要求が出される際にはいつでも阻止する場合には、結果としてもたらされる平均ビット・レートは極めて低いものであり得る。更に：
2.  一般的に、リアルタイム・ストリームによる平均所要ビット・レートは、最悪の場合の所要レートよりもかなり小さくなる。その結果、サイクル毎のリアルタイム要求数はかなり小さくなる。その結果、比較的に大きな時間部分がシーク処理に費やされる。このことは、エネルギ消費、ディスクの寿命、及びディスクが動作中に発生させる雑音に対して悪影響を及ぼす。
【課題を解決するための手段】
【０００５】
したがって、本発明の目的は、ディスク・スケジューリング・アルゴリズムのブリージングを、当該技術分野で現在利用されているものに対して改善したものを備えることにある。よって、記憶装置に対するスケジューリング・アルゴリズムのブリージングの方法を備える。該方法は：(a)記憶装置のブリージング・サイクルの最悪の場合の持続時間を計算する工程；を備え；最悪の場合の持続時間はPによって表され；更に、(b)ブリージング・サイクルを開始する工程；(c)以下のうちの一方が、P時間単位の終了より前に真になるかを判定する工程；を備え；(i)では、リアルタイム要求数が、データ・ストリーム数と、記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であり：(ii)では、何れかの単一のストリームに対する、未処理状態の要求の数が2つ以上となり；更に、(d)(i)と(ii)とのうちの少なくとも一方が、ブリージング・サイクルの開始からP時間単位の持続時間中真状態に留まったままである場合、ブリージング・サイクルの完了後、後続ブリージング・サイクルを開始する工程；及び、(e)(i)も(ii)も、ブリージング・サイクルの開始からP時間単位の持続時間中に真でない場合、後続ブリージング・サイクルを開始する前にブリージング・サイクルの開始からP時間単位待つ工程；を備える。
【０００６】
好ましくは、ブリージング・サイクル中に到着するベスト・エフォート要求は、ブリージング・サイクル中に処理される。上記方法は好ましくは更に、複数のブリージング・サイクルについて工程(b)乃至(e)を繰り返す工程を備える。
【０００７】
上記方法は好ましくは、(f)データ・ストリームの実際のビット・レートを上記(ii)の判定に基づいて計算する工程を備える。その場合、上記方法は更に、(g)データ・ストリームのビット・レートを工程(f)における計算に基づいて変更する工程を備える。好ましくは、工程(g)は、そのデータ・ストリームの最大推定ビット・レートを超える場合にそのデータ・ストリームに対する高ビット・レートを確保する工程を備え、該工程では、データ・ストリームが記憶装置とバッファとの間で転送され、上記方法は更に、(h)バッファ・サイズを増加させる工程を備える。あるいは、工程(g)は、そのデータ・ストリームの最大推定ビット・レートを超えない場合にそのデータ・ストリームに対する低ビット・レートを確保する工程を備え、該工程では、データ・ストリームが記憶装置とバッファとの間で転送され、上記方法は更に、(h)バッファ・サイズを低減させる工程を備える。
【０００８】
記憶装置のスケジューリング・アルゴリズムのブリージングを制御する記憶装置スケジューラも備える。記憶装置スケジューラは：(a)記憶装置のブリージング・サイクルの最悪の場合の持続時間を計算する手段；(b)ブリージング・サイクルの開始を命令する手段；(c)以下のうちの一方が、P時間単位の終了より前に真になるかを判定する手段；を備え；(i)では、リアルタイム要求数が、データ・ストリーム数と、記憶装置の性能パラメータとに基づいた少なくとも所定の閾値であり：(ii)では、何れかの単一のストリームに対する、未処理状態の要求の数が2つ以上となり、更に、(d)(i)と(ii)とのうちの少なくとも一方が、ブリージング・サイクルの開始からP時間単位の持続時間中真状態に留まったままである場合、ブリージング・サイクルの完了後、後続ブリージング・サイクルを開始する手段；及び、(e)(i)も(ii)も、ブリージング・サイクルの開始からP時間単位の持続時間中に真でない場合、後続ブリージング・サイクルを開始する前にブリージング・サイクルの開始からP時間単位待つ手段；を備える。
【０００９】
記憶装置スケジューラは好ましくは更に、複数のブリージング・サイクルについて工程(b)乃至(e)を繰り返す工程を備える。
【００１０】
記憶装置スケジューラは好ましくは更に、(f)データ・ストリームの実際のビット・レートを工程(ii)の判定に基づいて計算する工程を備える。その場合、記憶装置スケジューラは好ましくは更に、(g)データ・ストリームのビット・レートを工程(f)における計算に基づいて変更する工程を備える。好ましくは、工程(g)は、そのデータ・ストリームの最大推定ビット・レートを超える場合にそのデータ・ストリームに対する高ビット・レートを確保する工程を備え、該工程では、データ・ストリームが記憶装置とバッファとの間で転送され、上記方法は更に、(h)バッファ・サイズを増加させる工程を備える。あるいは、工程(g)は、そのデータ・ストリームの最大推定ビット・レートを超えない場合にそのデータ・ストリームに対する低ビット・レートを確保する工程を備え、該工程では、データ・ストリームが記憶装置とバッファとの間で転送され、上記方法は更に、(h)バッファ・サイズを低減させる工程を備える。
【００１１】
本発明の上記方法を行うコンピュータ・プログラム・プロダクトと、コンピュータ・プログラム・プロダクトをその中に記憶させるそのプログラム記憶装置とも備える。
【発明を実施するための最良の形態】
【００１２】
本発明の装置と方法との、これらや別の特性、特徴、及び効果は、下記明細書、特許
請求の範囲、及び添付図面を参照すれば、更によく分かるものであり、添付図面は、本発明の方法とともに用いるシステム・アーキテクチャの概略図を示す。次に添付図面を参照すれば、参照数字100によって概括的に表すシステム・アーキテクチャの概略図を示す。添付図面におけるシステム・アーキテクチャは単に例として表しているものであり、本発明の範囲又は趣旨を限定するものでない。本発明の方法は、ハード・ディスク・ドライブなどの記憶装置からデータを取り出すディスク・スケジューリング・アルゴリズムを利用する何れかのシステムにおいて利用し得る。
【実施例】
【００１３】
図１は、本発明の方法とともに用いるシステム100の構成図の概略を表す。そのようなシステム100の例としては、ハード・ディスク・レコーダ、セットトップ・ボックス、テレビジョン受信機、オーディオ・ジュークボックス、及びビデオ・サーバ並びにマルチメディア・サーバがある。マルチメディア・アプリケーションは、視聴覚マテリアルの広範囲にわたる利用によって特徴付けることが可能である。本発明の方法は、ディスク又は別の記憶装置を用いてオーディオ又はビデオを再生する、（VOD）サーバ、更には、ホーム・サーバ、パーソナル・ビデオ・レコーダ、ポータブル・マルチメディア機器、及び別の機器に適用可能である。
【００１４】
オーディオ又はビデオの再生には、オーディオ・データ/ビデオ・データのほぼ連続した供給が必要である。マルチメディア・サーバの既知の例としては、ニア・ビデオ・オン・デマンド・サーバとビデオ・オン・デマンド・サーバとを有する。ニア・ビデオ・オン・デマンド・システムでは、タイトルを再生する時点はサービス・プロバイダが判定する。タイトルのデータを有するデータ・ストリームは多くのユーザによって同時に受信し得る。ビデオ・オン・デマンド・システムでは、通常、ユーザがタイトルと、VCRに似たコントロールを備えているコントロールと、タイトルの再生とを選択する。相互作用のレベルは高く、データ・ストリームは通常、１ユーザによってしか消費されない。マルチメディア・サーバは通常、連続したデータ・ストリームを多数のユーザに並行して供給するよう特に企図されているファイル・サーバを用いて実施される。
【００１５】
通常、1つ又は複数のマルチメディア・タイトルがバックグラウンド記憶媒体110上に記憶される。通常、ハード・ディスクなどのディスクが、低コストでのその大記憶容量と、ランダム・アクセスの可能性とに基づいてそのバックグランド記憶媒体110として用いられる。更に、光ディスク、テープや、ソリッド・ステート・メモリなどの別の記憶媒体も用い得ることとする。記憶媒体110は好ましくは、単一の記憶装置であるが、複数の記憶ユニットに分割する場合もあり、その場合には、データ・ブロックを読み書きする要求によって各ディスクに対するディスク・アクセスをもたらすようにデータを複数のディスクに及んでストライピングすることが可能である。
【００１６】
システム100は、データを記憶媒体110から読み取る読取り装置180を備える。読取り装置180はSCSIインタフェース又はIDEインタフェースを用いて実施し得る。効果的には、記憶媒体110はシステム100も有する。ディスク指向記憶媒体110では、データはディスク・アクセス・ブロック（DAB）の単位で取り出され、DABは連続セクタ・シーケンスによって構成される。読み取り装置180は、ディスクから読み取られるデータを、データをバス140を介してシステムの残りに供給する前に一時的に、潜在的には、ディスクから読み取られるシーケンスとは異なるシーケンスで記憶させるキャッシュ・メモリを有する場合もある。特にビデオについては、データ・ストリームの容量が非常に大きいものであり得る。この容量を削減するよう、通常、圧縮手法が用いられる。圧縮手法は、例えばMPEG-1符号化の固定レート形式を用いた固定レート・データ・ストリームをもたらす場合も、MPEG-2符号化の変動レート形式を用いた変動レート・データ・ストリームをもたらす場合もある。システムは、固定レート・システム、更には変動レート・システムに用い得る。通常、データは、圧縮形式で、記憶媒体110に記憶され、システム100によって処理される。データ・ストリームがデコーダを用いて圧縮解除されるのはユーザ130においてだけである。特に可変レート・システムについては、システム100はVCRに似た制御機能をサポートすることができる場合もある。システム100は、データ・ストリームについて、現行状態を示すストリーム・ステータスを維持する。1つ又は複数のデータ・ストリームについてのストリーム・ステータスを、サーバの主メモリ（RAM）又は特殊レジスタなどのステータス・メモリ190に記憶させ得る。データは記憶媒体110からデータ・ストリーム・バッチについて読み取られ、このバッチ・データはバス140を介して時間多重化ストリームとして供給される。記憶媒体110は、連続したデータ・ストリームをシステムのユーザ全てに同時に供給することができない。その代わりに、データ・ストリーム部分集合のデータが読み取られ、相当するデータ・ストリームによって消費されるデータ・レートよりも高いデータ・レートでシステム100の残りに供給される。システム100は、したがって、データを所要レートでユーザ130に供給することを達成するバッファ125を備える。通常、バッファ125は、システムのメモリの一部分120においてRAMを用いて実施される。システム100は更に、データ・ストリームのデータをユーザに転送する通信手段150を備える。通信手段150はローカル・エリア・ネットワークなどの何れかの適切な手段によって形成されて、システム100近くに位置するユーザにデータを供給し得る。実際には、通信ネットワーク又はケーブル・ネットワークは、データを長距離にわたって供給するのに用いられる。
【００１７】
システム100は、自らを制御する制御装置160も備える。制御装置の主部分は、バッファのアンダフロー又はオーバフローが起こらないようにするためにどのDABをリーダ180によって記憶媒体110から読み取ることとするかを判定するスケジューラ170によって構成される。制御装置は、ROM又はハード・ディスクなどの記憶媒体からロードされるリアル・タイム・オペレーティング・システムの制御下で動作する、RISC型又はCISC型のマイクロプロセッサなどのプロセッサによって通常構成される。スケジューラ170は、オペレーティング・システムに一体化されるかアプリケーション・プログラムとしてロードされるソフトウェア・モジュールとして実施し得る。通常、スケジューラ170は、自らの判定の基にする、バッファの充填度などのステータス情報を受信する。VCRに似たコントロールを提供するシステムについては、スケジューラはストリームのステータスに関する情報も受信する。そのようなシステムでは、通常、制御情報はユーザ130から通信手段150を介して受信される。記憶装置100がハード・ディスクの場合、データは、ディスク上の、トラックと呼ぶ同心円に記憶される。各トラックは整数の数のセクタを有する。ディスクの外端近くのトラックは、内端近くトラックよりも多くのセクタを有し得る。この目的で、現代のディスクはトラック群を重なり合わないゾーンに配置させ、ゾーンにおけるトラックは同数のセクタを有し、別々のゾーンは、異なる、トラック毎セクタ数に相当する。通常、ディスクは一定の角速度で回転するので、外端近くのゾーンにあるトラックから読み取ることによって、内端近くのゾーンにあるトラックから読み取るよりも高いデータ転送レートをもたらす。ディスクからデータをアクセスするのに必要な時間は、シーク時間、すなわち、読み取りヘッドを所望のトラックに移動させるのに必要な時間、回転レーテンシ、すなわち、トラックに到達すると読み取りヘッドの下に所要データが移動するまでに経過する時間、及び読み取り時間、データを実際に読み取る時間によって主に判定される。シーク時間と回転レーテンシとの和はスイッチ時間と呼ぶ。読み取り時間は、読み取る対象のデータ量と、データが記憶されるトラックの径方向位置によって変わってくる。アクセス毎回転レーテンシは多くて、ディスクの一回転を占める。アクセス毎シーク時間は、読み取りヘッドを内端から外端までか、外端から内端まで移動させることを要する場合に最大である。そのような最大値にならないようにするよう、シークはアクセス毎に考慮することを要し、ディスク・アクセスは、スイープと呼ぶバッチにて処理される。ヘッドが内端から外端までか、外端から内端まで移動するにつれ、所要データ・ブロックは、ディスク上で出くわす順序で読み取られる。
【００１８】
本発明の方法を次に、添付図面を参照しながら説明することとする。KorstなどによるDisk  scheduling  for  variable-rate  data  streams,  Proc.  European  Workshop  on  Interactive  Distributed  Multimedia  Systems  and  Telecommunication  Services,  IDMS  ’97,  Darmstadt,  September  10-12,  Lecture  Notes  in  Computer  Science,  1309(1997)  119-132(1997)によって表されているものなどの公知のトリプル・バッファリング・アルゴリズムに焦点を当てれば、ブリージングは好ましくは、以下のように調節される。しかし、現在公知であるか将来策定される別のアルゴリズムも本発明の方法とともに利用することが可能であるということは、当業者が分かるものである。サイクルの最悪の場合の持続時間をPによって表すこととし、サイクルは、通常、データ・ストリーム毎に（多くて）１つのDABを取り出すのに用いる時間間隔として定義され、場合によってはベスト・エフォート要求を処理する別の時間が確保される。サイクルの、最悪の場合の計算は周知である。当該技術分野において現在実施されているように、サイクルが完了するといつでも、次のサイクルをその直後に開始することが可能であるが、しかし、本発明の方法では、次のサイクルの開始は、完了サイクル後P時間単位、遅延させることが可能である。全てのストリームがその最大ビット・レートを超えないということを前提とすれば、バッファ・アンダフローもバッファ・オーバフローも当該場合には起こらないことになるということをなお保証することが可能である。何れの手法も、次のサイクルを開始するべき時点を判定するうえで考えられるストラテジの範囲の２つの極端な場合として見なし得る。
【００１９】
ブリージングの効果と欠点とのバランスを良好に保つこの代替ストラテジを次に更に詳細に説明することとする。本発明の方法のストラテジは、その時点より前に以下の2つの条件の一方が真にならない限り、先行サイクルの開始からP時間単位が経過したその時点まで待って次のサイクルを開始するものである。これらの条件のうちの一方が真になる場合、次のサイクルは直ちに開始される。次のサイクルが開始されない限り、ディスクはアイドル状態である必要はないが、ベスト・エフォート要求を連続バッチにおいて処理することが可能である。ベスト・エフォート要求は、リアルタイム要求を有する次サイクルが現行サイクルの開始後のP時間単位より後には開始されないように処理されることとする。更に、ベスト・エフォート要求の各バッチの完了後に、条件を検査することとする。
【００２０】
次のサイクルを直ちに開始する条件は以下に記載する。すなわち：
1.  （リアルタイム）要求の数が少なくともn閾値であり、n閾値は、ストリーム数n及びディスク性能パラメータによって変わってくる、適切に選定される数である。N≧5の場合、n閾値は2又は3に等しくなるように選定し得る。サイクル毎に3個の要求を行うことによってスウィープを相当に効率的に利用することをもたらす。更に：
2.  単一ストリームに対する未処理要求数は2となる。ストリームがその最大ビット・レートを超えない場合、この条件が真になることは全くないことになる。しかし、一部のストリームがその推定最大ビット・レートを一時的又は連続的に超える場合、バッファ・アンダフロー又はバッファ・オーバフローを可能な限りないようにすることとする。
【００２１】
P時間単位が経過するのを待つよりも先行して次のサイクルを開始することによって、高ビット・レートを、別のストリームに対する保証ビット・レートを脅かすことなくそのようなストリームに提供することが可能である。何れの要求もその場合、同じスイープで処理されるので、スウィープが効率化される機会は増えるが、それは単一のストリームの２つの要求が多くの場合、連続することになるからである。なお、新たなストリームが開始される場合、直ちに、2つの要求又は３つもの要求を出すことになる。その場合、上記の第２の条件が満たされ、新たなストリームの起動時間は相当して少ないものとなる。上記ストラテジは、ブリージングの効果を概ね維持する。平均応答時間は、最悪の場合よりもなお、かなり小さくなるが、それは、平均すれば、サイクルはP時間単位よりもなお、かなり短くなるからである。ローグ・ストリームは、その最大ビット・レートよりも高いビット・レートをなお受信することが、そうするうえで利用可能な帯域が存在するという前提で可能である。
【００２２】
更に、このストラテジは、ブリージングの欠点を大きく軽減する。一度に１つの小さなベスト・エフォート要求を出すアプリケーションは、サイクル毎に複数要求を出すことができることになる。次のサイクルが開始されない限り、このストラテジは、要求を繰り返し出し続けることが可能である。更に、ディスクは、高いエネルギ効率で動作し、低雑音を発生させ、長寿命を有することになるが、それは、特に、平均してベスト・エフォート負荷が適度の場合にアイドル状態が多くなるからである。
【００２３】
上記ストラテジの別の効果には、第２条件を検査することを用いてストリームの実際ビット・レートに対するフィードバックを備えることが可能であるということがある。ストリームがその推定最大ビット・レートを連続して超える場合、そのストリームについてディスクとバッファとの間で繰り返し転送されるデータ・ブロックは増加される、すなわち、そのストリームに対する高ビット・レートを確保するよう増加される。そのストリームのバッファ・サイズは同様に増加されることになる。更に、ストリームが連続してその推定最大ビット・レートよりも低いビット・レートを要求する場合、そのブロック・サイズとバッファ・サイズとを調節することを検討することも可能である。
【００２４】
例：
本発明のディスク・スケジューリング方法をプロトタイプ・システムに適用することによって、以下の改善結果が観察された。12のリアルタイム・ストリームに加えて、大きなベスト・エフォート要求バッチが出されている。12DVBビデオ・ストリームによって、600msの最悪の場合のサイクル長を用いてIBMデスクスター(Deskstar)60GXP  40GBディスクをアクセスすることによって、以下の結果が得られた。すなわち：
ビデオ・ストリームの合計ビット・レートが48Mbit/sの場合、本発明の方法の、新たなサイクルが常に、先行するサイクルが完了すると直ちに開始される好適実施例を用いた場合にベスト・エフォート・データの8.8Mbits/sから16.8Mbits/ｓへの増加が観察された。ビデオ・ストリームの合計ビット・レートが56Mbit/sである場合、ベスト・エフォート・データのビット・レートの0.8Mbit/sから9.6Mbit/sへの増加が観察された。よって、利得は、ディスクに対するリアルタイム負荷によって大きく変わってくる。このことは、別の実験によって確認されている。ベスト・エフォート要求は、実験毎に10個の１MByteブロックを有するものであった。上記では、P＝600msであり、n=12である（すなわち、12個のリアルタイム・ストリームである。）。
【００２５】
これらの予備実験は、ベスト・エフォート・レートの、少なくとも3倍から6倍の増加を示している。更に、ベスト・エフォートとして（部分的に）処理されたトリック・プレイの動作に伴う課題は、かなり少ないものであった。
【００２６】
本発明の方法は、コンピュータ・ソフトウェア・プログラムによって行われるのに特に適しており、そのようなコンピュータ・ソフトウェア・プログラムは好ましくは、方法の個々の工程に相当するモジュールを有する。そのようなソフトウェアは当然、集積チップ又は周辺装置などのコンピュータ判読可能媒体において実施することが可能である。
【００２７】
本発明の好適実施例としてみなされるものを表し、説明したが、種々の、形式又は詳細における修正や変更を本発明の趣旨から逸脱することなく容易に行うことが可能であるということは当然分かるものである。したがって、本発明は、説明し、図示するまさにその形態に限定されるものでなく、本特許請求の範囲記載の範囲内に収まり得る修正全てに及ぶよう解釈されることとするということが意図されている。
【図面の簡単な説明】
【００２８】
【図１】本発明の方法とともに用いるシステム100の概略を表す構成図である。
【図１】
2006512636.tif 000003
【国際調査報告】
2006512636.tif 000004
2006512636.tif 000005