(57)【要約】  本発明は、データの実時間取扱に関連し、とりわけフレームの断片化を考慮したビデオレンダリング用のフレームを取り出すために必要な時間の推定に関連する。これは、特にトリックプレイのデータ取り出しに関しては些細なことではない。何故なら、取り出されるべきフレームが断片化されているかどうかは事前には分からないからである。非連続的に断片化されたフレームの取り出しには、断片化されていないフレームを取り出しより少なくとも２倍多い時間がかかる。本発明は、割り当て単位が取り出されるべきフレームのサイズよりも大幅に大きい場合を考慮して、様々な有利な実施例を提供する。本発明の一実施例は、トリックプレイの速度、割り当て単位のサイズ、フレームサイズ及び取り出すべきフレーム間の論理データ距離が判明している場合に正確な取り出し時間を推定する方法を提供する。
2007519141.tif 000002
【特許請求の範囲】
【請求項１】
既定のデータ取扱期間において少なくとも１つの記憶装置要求を実行することによって、割り当て単位で編成された記憶装置により処理されるべきデータ取扱要求を発することにより、少なくとも１つのデータオブジェクトのグループを取り扱う方法であって、
ａ）前記データ取扱期間内に取り扱われるべきデータオブジェクトの数を決定するステップと、
ｂ）前記データ取扱要求に関して、関連する割り当て単位の数の上限を決定するステップと、
ｃ）ステップａ）で決定された前記データ取扱要求の数を、関連する割り当て単位の数の前記上限に乗算することにより記憶装置要求の数の上限を決定するステップと、
ｄ）ステップｃ）で決定された前記記憶装置要求の数の実行のために必要な時間量を決定することによって、前記データ取扱期間の間に前記データオブジェクトを取り扱うためのデータ取扱要求の実行により消費される時間量の上限を決定するステップと、
ｅ）ステップｄ）において決定された時間量を、前記記憶装置要求の実行のためにデータ取扱期間内に確保するステップと、
ｆ）前記データオブジェクトを前記記憶装置要求の実行により取り扱うステップと、
を有する方法。
【請求項２】
ａ）前記データオブジェクトの最大サイズは、前記割り当て単位のサイズよりも大幅に小さく、
ｂ）前記データオブジェクトは、複数のデータオブジェクトが１つの割り当て単位に格納されうるように互いから実質的に等しい論理距離で非連続的に格納され、
ｃ）データ取扱要求毎に関連する割り当て単位の数の上限を決定する前記ステップが、実質的に等しい論理距離で隔てられて断片化されて格納されている請求項１のステップａ）で決定されたデータオブジェクトの数の上限を決定するステップにより置換され、
ｄ）前記記憶装置要求の数の上限を決定するステップが、前記データ取扱要求の数と本請求項のステップｃ）で決定された前記データオブジェクトの数との和を取るステップにより置換される、
請求項１に記載の方法。
【請求項３】
ａ）１つの割り当て単位のサイズを決定するステップと、
ｂ）データオブジェクトの最大サイズを決定するステップと、
を有し、関連する割り当て単位の数の上限が、
［関連する割り当て単位数］
2007519141.tif 000020
［データオブジェクトの最大サイズ］／［１つの割り当て単位のサイズ］＋２
なる式により決定される、請求項１に記載の方法。
【請求項４】
ａ）前記データオブジェクト間の最大距離を決定するステップと、
ｂ）１つの割り当て単位のサイズを決定するステップと、
ｃ）データオブジェクトの最大サイズを決定するステップと、
を有する方法であって、関連する割り当て単位数の上限が、
［記憶装置要求の数］
2007519141.tif 000021
［データ取扱要求の数］＋（［関連する割り当て単位数］−１）
なる式により決定され、前記データ取扱要求の実行に関連する割り当て単位の数の上限が、
［関連する割り当て単位数］
2007519141.tif 000022
（［データ取扱要求の数］×
（［最大距離］＋［最大サイズ］）／［割り当て単位のサイズ］）＋２
なる式により決定される、請求項２に記載の方法。
【請求項５】
前記データオブジェクトが、オーディオビジュアルデータのストリームに含まれるビデオフレームである、請求項１に記載の方法。
【請求項６】
前記オーディオビジュアルデータのストリームが、インター符号化された及びイントラ符号化されたフレームを有する、請求項５に記載の方法。
【請求項７】
前記データ取扱要求が関連する前記複数のデータオブジェクトが、前記イントラ符号化されたフレームの少なくとも幾つかである、請求項６に記載の方法。
【請求項８】
ステップｄ）が、前記記憶装置要求の数の上限を記憶装置要求により消費される時間量により乗算するステップを有する、請求項１に記載の方法。
【請求項９】
前記時間量が予め決定されている、請求項８に記載の方法。
【請求項１０】
前記記憶装置がディスクドライブであり、前記時間量の上限を決定するステップが、
ａ）ディスクの１回転に必要な時間量、
ｂ）前記ディスクドライブのピックアップユニットの、前記データ取扱要求が目指すデータオブジェクトが配置されたディスク上の位置までのシーク時間、
ｃ）前記データ取扱要求が目指すデータオブジェクトの取り出しに必要な時間、
なるパラメータのうちの少なくとも１つを更に考慮する、請求項１に記載の方法。
【請求項１１】
前記記憶装置がディスクドライブであり、前記時間量の上限を決定するステップが、
ａ）ディスクの１回転に必要な時間、
ｂ）前記ディスクドライブのピックアップユニットの、前記データ取扱要求が目指す第１データオブジェクトが配置されたディスク上の第１位置までのシーク時間、
ｃ）前記第１データ取扱要求が目指すデータオブジェクトを取り出すために必要とされる時間、
ｄ）前記ピックアップユニットが、前記ディスク上の前記第１位置から、前記データ取扱要求が目指す第２の後続のデータオブジェクトが配置された前記ディスク上の第２位置まで移動するために要する時間、
なるパラメータのうちの少なくとも１つを考慮する、請求項２に記載の方法。
【請求項１２】
データ取扱要求毎に関連する割り当て単位の数の上限を決定する前記ステップが、前記データオブジェクトのサイズを１つの割り当て単位のサイズにより除算するステップを有する、請求項１に記載の方法。
【請求項１３】
データ取扱期間内に取り扱われる少なくとも１つの記憶装置要求により処理されるべきデータ取扱要求によって、少なくとも１つのデータオブジェクトのグループを取り扱う装置であって、前記データ取扱は割り当て単位で編成された記憶装置により取り扱われるべきであり、
ａ）データ取扱期間あたりに取り扱われるべきデータオブジェクトの数を決定し、
ｂ）データ取扱要求あたりに関連する割り当て単位の数の上限を決定し、
ｃ）データ取扱要求の数に、前記関連する割り当て単位の数の上限を乗算することによって、記憶装置要求の数の上限を決定し、
ｄ）前記記憶装置要求の数の上限に記憶装置要求により消費される時間量を乗算することによって、１つのデータ取扱期間内においてデータオブジェクトを取り扱うために記憶装置要求の実行により消費された時間量の上限を決定し、
ｅ）前記記憶装置要求を実行するために、データ取扱期間内に、ステップｄ）で決定された時間量を確保し、
ｆ）前記記憶装置要求を実行することにより前記データオブジェクトを取り扱う、
ように構成された中央処理ユニットを有する装置。
【請求項１４】
コンピュータが請求項１に記載の方法を実行するようにプログラムされるのを可能にする、コンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを担持する、記録担体。
【請求項１６】
請求項１に記載の方法を実行することを可能にされた、プログラムされたコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも１つのデータオブジェクトのグループを取り扱う方法に関する。
【０００２】
本発明は、更に、少なくとも１つのデータオブジェクトのグループを取り扱う装置に関する。
【０００３】
本発明は、コンピュータが、少なくとも１つのデータオブジェクトのグループを取り扱う方法を実行するようにプログラムされることを可能にするコンピュータプログラムにも関する。
【０００４】
本発明は、更に、前記コンピュータプログラムを担持する、記録担体に関する。
【０００５】
本発明は、少なくとも１つのデータオブジェクトのグループを取り扱う方法を実行するようにプログラムされたコンピュータにも関する。
【背景技術】
【０００６】
１９９７年の対話型分散マルチメディアシステム及び遠隔通信サービス（Interactive  Distributed  Multimedia  Systems  and  Telecommunication  Services）に関するヨーロッパワークショップにおける論文「可変レートデータストリーム用ディスクスケジューリング」は、実時間処理するために複数のデータストリームに対するデータ要求をスケジューリングする方法を開示している。
【０００７】
たとえばレンダリングのためにビデオストリームを取り出すとき、データの実時間処理が必要とされる。ビデオデータの適切な再生を保証するために、ビデオデータは間に合わせてレンダリングユニットに提供されなければならない。データが間に合うように取り出されないとき、再生されるビデオデータにおいて不都合な結果が生じうる。複数のストリームが１つの記憶装置から同時に取り出されるとき、様々なデータ取扱要求（又はファイル要求；ファイル又はオーディオビジュアルデータのストリームにおける主要なセグメントのような、大きなデータの塊に対する高い水準の要求；これらの仕様は、この出願の状況では相互交換可能である）が実時間で扱われなければならず、スケジューリングがますます重要になる。
【０００８】
前記の論文は、データストリームの各々に対してディスク上の読取ヘッダの１つの掃引においてデータブロックを取り込むために必要な時間量の上限を計算するための式を開示している。この式は
式Ａ
2007519141.tif 000003
であり、ここで、
2007519141.tif 000004
は
2007519141.tif 000005
ユーザー（又はデータストリーム）の集合であり、
2007519141.tif 000006
は、扱うべき、即ち格納又は取り出すべき、
2007519141.tif 000007
番目のデータブロックのサイズであり、
2007519141.tif 000008
はデータ転送レートであり、
2007519141.tif 000009
は
2007519141.tif 000010
ユーザーに対する切り替え時間関数である。
【０００９】
この計算式は、取り出されるべきブロックのサイズ、ハードディスクのデータレート及び切り替え時間関数を考慮に入れている。後者は、データストリームそれぞれに対してデータブロックを取り込む間において、読み込みヘッドの切り替えに最大に費やされる時間を計算する関数である。
【００１０】
しかしながらこの論文は、切り替え時間関数の実際の形を明記していない。切り替え時間はハードディスクドライブ利用時間の大きな量を形成するので、この時間関数は重要である。不適切なスケジューリングは、切り替えオーバーヘッドにおいて容易にＨＤＤ時間の９０％を浪費することがありうる。更に、通常ハードディスクドライブが分割されている複数の割り当て単位に、取り出されるべきデータの塊又はブロックが格納される場合、割り当て単位がディスク上で連続して位置されていないとき、切り替え時間は増加する。しかしながら前記の論文は、取り出すべきデータブロックの可能性のある断片化が、サービス時間又はディスクドライブからのデータブロックの取り出し時間に対してどんな影響をもつのか開示していない。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
データ取扱要求をスケジューリング及び実行する方法を提供することが本発明の目的であり、該スケジューリングは、取り扱われるデータオブジェクトの断片化の取り出し時間に対する影響を考慮している。
【課題を解決するための手段】
【００１２】
この目的を成し遂げるために、本発明は、既定のデータ取扱期間に少なくとも１つの記憶装置要求を実行することにより、割り当て単位で編成された記憶装置によって処理されるべきデータ取扱要求を出すことによって、少なくとも１つのデータのグループを扱う方法を提供するもので、該方法は、上記データ取扱期間において取り扱われるべきデータオブジェクトの数を決定するステップと、該データ取扱要求に関わる割り当て単位の数に対する上限を決定するステップと、第１ステップで決定されたデータ取扱要求の数と、関連する割り当て単位の数の上限とを掛けることにより記憶装置要求の数に対する上限を決定するステップと、前のステップにおいて決定された数の記憶装置要求を実行するために必要な時間量を決定することにより、前記データ取扱期間において前記データオブジェクトを取り扱うために前記データ取扱要求を実行することによって消費される時間量に対する上限を決定するステップと、前記憶装置要求を実行するためのデータ取扱期間内に、前のステップにおいて決定された時間量を確保するステップと、前記憶装置要求を実行することにより前記データオブジェクトを取り扱うステップとを有する。
【００１３】
通常ハードディスクのような記憶装置は、割り当て単位に分かれている。１つの割り当て単位からデータを取り出すためには、１つの記憶装置要求が必要とされる。連続した割り当て単位からのデータはたいてい同様に１つの記憶装置要求により取り出される。データが取り出されなければならない割り当て単位が連続していないとき、１つのデータ取扱要求の実行には複数の記憶装置要求が必要となり、そのデータ取扱要求は取り出されなければならないすべてのデータに関係する。
【００１４】
データ取扱要求は、取り扱われる（記録される又は取り出される）データを必要とするアプリケーションによって出される。データ取扱要求から記憶装置要求への変換は、通常起動しているアプリケーションよりも下の階層のファイルシステムにより実行される。
【００１５】
データオブジェクトが割り当て単位のサイズよりも小さいときに、データオブジェクトは、１つの割り当て単位で格納されるか、２つの連続した割り当て単位に格納されるか、又はせいぜい２つの割り当て単位で断片化されて格納される。これは、１つのデータオブジェクトを取り出すために実行されなければならない記憶装置要求はせいぜい２つであるということを意味している。
【００１６】
一方、データオブジェクトのサイズが１つの割り当て単位のサイズよりも著しく大きい場合、データオブジェクトを取り出すための１つのデータ取扱要求が実行するために、実行されなければならない記憶装置要求の最大値は２よりも大きい。データオブジェクトを取り出すために実行されなければならない記憶装置要求の最大値を決定する１つのアプローチは、１つの割り当て単位のサイズにデータオブジェクトのサイズを断片化することである。
【００１７】
別のアプローチは、データオブジェクトの断片のリストを維持することである。データオブジェクトが取り扱われなければならず、データオブジェクトのサイズが１つの割り当て単位のサイズよりも大きいとき、とりうる断片によりそのリストが調べられる。データオブジェクトが断片に格納されたとき、おそらく複数の連続した割り当て単位を有する連続しないデータエリアの数は、リストから取り出される。この数は、前記データ取扱要求の実行のために実行されなければならない記憶装置要求の数である。
【００１８】
データ取扱期間にデータオブジェクトを取り扱うためのデータ取扱要求の実行により消費される時間の上限を決定するために、前記の数の記憶装置要求を実行するために必要な時間が決定されなければならない。このためには、切り替え時間もまた考慮されなければならない。本発明による方法の利点は、切り替え時間関数が単純化されうるということである。データオブジェクトが断片化されて格納された場合には、読み込みユニットは、取り扱われるデータオブジェクトと関連するデータが位置する（また、記録プロセスの場合では位置されるであろう）あるエリアから別のエリアに、切り替わらなければならないので、先行技術のアプローチでは記憶装置内のデータオブジェクトの断片化は、切り替え時間の決定の際に考慮されなければならない。本発明の方法を用いると、データの断片化は、取り扱われる記憶装置要求の数においてすでに考慮されている。
【００１９】
本発明による方法の実施例において、データオブジェクトの最大のサイズは割り当て単位のサイズよりも十分に小さくなっており、データオブジェクトは、連続しない場所に格納され、複数のデータオブジェクトが１つの割り当て単位に格納されうるように実質的にそれぞれから等しい論理距離となっていて、データ取扱要求あたりに関連する割り当て単位数の上限を決定するステップは、断片化され格納された実質的に論理距離が等しく隔てられる請求項１のステップａ）で決定されるデータオブジェクトの数の上限を決定するステップに置き換えられ、記憶装置要求の数の上限を決定するステップは、請求項２のステップｃ）で決定されるデータオブジェクトの数とファイル要求の数との和をとるステップに置き換えられる。
【００２０】
データオブジェクト間の論理距離は、たとえばディスクプラッタ、半導体結晶、又は記憶媒体における空間の距離と区別するため、ビット又はバイトで測定される。
【００２１】
この実施例の利点は、このようにデータ取扱要求の実行に必要とされる時間が、より正確で通常低く見積もられうるということである。これは通常データ取扱要求の実行をスケジューリングする際に予約された時間でもあるので、先行技術と比較してより多くのデータ取扱要求が同じ時間内にスケジュールされうる。これは、本発明による方法の実施例を用いるとより多くのデータが取り扱われうるということを意味している。
【００２２】
本発明による方法の別の実施例では、データオブジェクトがオーディオビジュアルデータのストリームにより構成されるビデオフレームで、これらのフレームはインターコード又はイントラコードされ、データ取扱要求と関連するデータオブジェクトの少なくともいくつかは、イントラコードされたフレームである。
【００２３】
イントラコードされたフレームサイズのように、オーディオビジュアルデータのストリームのコード化（圧縮）レートや内部コード化されたフレームのサイズが知られるとき、通常内部でコード化されたフレーム間の距離が知られる又は少なくとも上限が知られるので、請求項２の実施例の発明による方法を適用するととりわけ好都合である。これは、スケジューリングやデータを取り扱うときに、これらの要素を決定するための追加の計算又は測定が不要になるということを意味している。
【００２４】
本発明のさらに別の実施例では、「前のステップで決定されたように上限の数の記憶装置要求を実行するために必要な時間を決定することによって、１つのデータ取扱期間にデータオブジェクトを扱うためのデータ取扱要求の実行に消費される時間の上限を決定する」ステップは、記憶装置要求の数の上限に記憶装置要求により消費される時間を掛けるステップにより構成される。
【００２５】
この実施例は、データ取扱により消費されうる時間の決定をするために単純な乗算しかなされないという事実において主要な利点を与える。これはより速くなされうるものであり、切り替え時間を厳密に決定するためにディスク上に正確に位置しているデータを必要とする変則的なアルゴリズムを必要しない。しかしながら、この実施例は正確性に欠ける。
【００２６】
本発明によるコンピュータプログラムは、コンピュータを請求項１に記載の方法を実行するためにプログラムすることを可能にする。
【００２７】
本発明による記録担体は、請求項１４に記載のコンピュータプログラムを担持する。
【００２８】
本発明によるプログラミングされたコンピュータは、請求項１に記載の方法を実行することが可能にする。
【００２９】
本発明は、図により記載される実施例の説明から明らかになるだろう。
【発明を実施するための最良の形態】
【００３０】
図１は、本発明による装置の一実施例としての民生電子装置１１０、ユーザー制御装置１６０及びＴＶセット１５０を有する民生エンタテイメントシステム１００を示している。
【００３１】
装置１１０は、好ましくはオーディオビジュアルデータを格納するためのハードディスクドライブ１２２等の記憶装置、当該装置を制御するための処理ユニット１２４、処理ユニット１２４をプログラムするプログラムデータを格納するための本発明による記録担体の一実施例としての読み取り専用メモリ（ＲＯＭ）１２６、ハードディスクドライブ１２２から、同様に当該装置に含まれるビデオレンダリングユニット１３０へ高速にデータを伝送するためのＤＭＡコントローラ１２８及びユーザーコマンドを受けるユーザーコマンドコントローラ１３４を有している。ＲＯＭ１２６は、ソリッドステートＲＯＭ、ＥＥＰＲＯＭ、磁気データ担体、光学データ担体又は他の担体などの様々な方法で実施されうる。
【００３２】
ＴＶセット１５０は、スクリーン１５２を有する。ＴＶセットは、第１コネクタ１３２により民生電子装置１１０に接続される。
【００３３】
ユーザー制御装置１６０は、民生電子装置１１０によりオーディオビジュアルデータのストリームの再生の方向及び速度を制御するための再生ボタン１６２、巻き戻し（高速戻し）ボタン１６４及び早送りボタン１６６を有する。ユーザー制御装置１６０は、第２コネクタ１３６により民生電子装置１１０に接続されている。該接続は、有線又は無線になりうるが、これは本発明の範囲とは無関係である。
【００３４】
民生電子装置１１０は、ハードディスクドライブ１２２に格納されたオーディオビジュアルデータのストリームを再生することを意図されている。別の実施例では、これは光学ディスクであることもありうる。再生は、例えば再生ボタン１６２を押すなどのユーザーコマンドにより開始される。これは、ユーザーコマンドコントローラ１３４により受信され、処理ユニット１２４に伝送されるようなユーザー制御装置１６０における制御信号を発生させる。
【００３５】
上記制御信号を受けると、ＲＯＭ１２６のプログラムでプログラムされた処理ユニット１２４は、ハードディスクドライブ１２２からのオーディオビジュアルデータの取り出しを開始し、ＤＭＡコントローラ１２８を介してのビデオレンダリングユニット１３０への取り出したデータの伝送の準備をする。ビデオレンダリングユニット１３０は、本実施例においてはＭＰＥＧ（モーションピクチャーエキスパートグループ）２規格により圧縮されているようなオーディオビジュアルデータをデコードする。上記ビデオレンダリングユニットの出力は、知られたフォーマット（例えばＳＥＣＡＭ又はＰＡＬ）によるビデオ信号であり、ＴＶセット１５０で見ることが可能である。このビデオ信号は、第１コネクタ１３２を介して供給される。
【００３６】
図２は、ＭＰＥＧ２規格により圧縮された、圧縮されたビデオデータのストリーム２００を示している。ストリーム２００は、３つの異なるタイプの圧縮されたフレームから成り立っている。これらフレームは、いわゆるグループオブピクチャー、即ちＧＯＰにグループ化されている。この例の場合、６なるＧＯＰサイズがとられているが、当業者は別のＧＯＰサイズも許可される理解するであろう。
【００３７】
「Ｉ」フレームはイントラ符号化されており、これは、これらフレームが適切な伸張アルゴリズムと、このフレーム自身からのデータとを用いて伸張されうることを意味する。「Ｂ」及び「Ｐ」フレームはインター符号化されており、これは、これらフレームを伸張するためには、他の（デコードされた）フレームからのデータも必要とされることを意味する。圧縮されたＰフレームのデコードには、直前のＩフレームからのデータが必要とされる。Ｂフレームの伸張には、先行する及び／又は後続するＩフレーム又はＰフレームからのデータが必要とされる。
【００３８】
当該データの通常の実時間再生の間においてすべての画像を見せることは、前の段落で説明されたすべてのデコードを実時間で実行することができるので、ＴＶセット１５０（図１）のディスプレイ１５２（図１）上に滑らかなビデオ映画をレンダリングする。例えば実時間再生中にユーザーが巻き戻しボタン１６４又は早送りボタン１６６を押した場合のような、当該ビデオデータの高速再生の場合、全てのフレームを該高速再生と同期してデコードすることは、もはや不可能になる。そのような場合には、ヒトの目及び脳により処理することができるより多くのフレームがレンダリングされるので、これは必要というわけでもない。
【００３９】
それゆえ、通常Ｉフレームのみがレンダリングされる。ストリーム２００の場合、これは、高速再生では第１Ｉフレーム２０２、第２Ｉフレーム２０４、第３Ｉフレーム２０６及び第４Ｉフレーム２０８がトリックプレイストリーム２２０へと結合されることを意味するだろう。ストリーム２００と同じフレームレートでのトリックプレイストリーム２２０の再生は、結果として６倍の速度の増加となる。すべてのフレームが３倍長く表示されると、これは２倍の速度増加という結果になるだろう。
【００４０】
例えば実時間の１２倍等の一層高速なレンダリング速度の場合、いくつかのＩフレームのレンダリングはスキップすることができ、選択された数のＩフレームのみがレンダリングされうる。これが、ストリーム３００を示す図３に図示されている。ストリーム３００は、ＭＰＥＧ２規格を用いて圧縮されている。単純化のためにＩフレームのみが示され、ＧＯＰサイズは６である（１つのＩフレームに対して、各Ｉフレーム後の１つのＰフレームと４つのＢフレームとが伴う）。ＧＯＰサイズが６であり、それぞれのＧＯＰが１つのＩフレームを持つので、図３において矢印で示された１つ置きのＩフレームがレンダリングされなければならない。この場合において、各フレームは通常の再生速度間と同じ長さで示され、再生の速度上昇係数は１２となる。
【００４１】
オーディオビジュアルデータを再生する際に、データがハードディスクドライブ１２２（図１）から時間内に取り出され、ビデオレンダリングユニット１３０（図１）により時間内にレンダリングされることが重要である。
【００４２】
時間内のデータの供給を保証するために、データの取り出し（及び書き込み、該書込は同じデータ量に対して概ね同じ時間がかかる）は、通常は０．５秒から２秒間のいわゆるサイクルに分割される。実時間要求のサイクルをベースとしたスケジュールに関する背景となる情報に対しては、読者はこの説明につづく参照文献を参照されたい。１つのサイクル期間内では、いくつかのデータ取り出し要求がスケジュールされうる。データ取り出し要求は、２つ以上のアプリケーションにより送信されうる。例えば、あるアプリケーションは、ハードディスクドライブ１２２に格納されたビデオデータの再生（及び取り出し）を引き受けているのに対し、別のアプリケーションは、ハードディスクドライブ１２２にユーザープロファイルを周期的に格納することを引き受けているとする。両方の要求のデータ取扱（データの読み取り及び書き込みであり、明瞭化のために、矛盾が生じない限り、残りの説明では取り出しが利用される）は、同じサイクルでスケジュールされうる。
【００４３】
これは、データ及びレンダリングに必要な時間を予測することを必要とする。ビデオレンダリングユニット１３０の処理速度は、通常かなり予測でき、その推定はあまり重要ではない。というのは、該ユニットは、ストリームをレンダリングすることに専念していて、他の仕事を行う必要がないからである。一方、ハードディスクドライブ１２２からデータを取り出すために必要な時間の推定は、より重要である。これの理由は、多くの場合においてハードディスクドライブ１２２は、ユーザープロファイルの格納のようなビデオ再生以外のアプリケーションによっても使用されうるからであり、且つ、例えば１つのＩフレームのためのデータを取り出すのに必要な時間は、同じＩフレームのレンダリングのためにビデオレンダリングユニットにより必要とされる処理時間よりも通常予測しにくいからである。
【００４４】
データ取り出しを予測することが困難な理由は、他にもあるが、データの断片化及びデータの誤った取り出しの確率が挙げられる。
【００４５】
データが誤って取り出されるとき（これは、当業者により知られているように冗長検査により検出されうる）、現行の技術のハードディスクは、データ取扱を再度試みるだろう。これには、通常のデータ取り出し要求の実行と同程度の時間がかかり、全取り出し時間は２倍に増加する。これは、もし２度目の試みが成功した場合の話である。幸運なことに、現行の技術のハードディスクドライブは、記憶能力が１０１２ビット又は１０１１バイトのオーダーで、１０１４に対して１ビットの誤り率を有している。４時間の高品質映画の記憶は、この量のおよそ４％を消費することになり、取り出し（又は再生）の間の誤りの見込みを非常に低くさせる。
【００４６】
しかしながら、断片化の問題は一層しばしば起こりうる。これが、図３においてストリーム３００の下のバー３５０により示されている。バー３５０は、ハードディスクドライブ１２２の一部を模式的にあらわしたものであり、第１割り当て単位３５２、第２割り当て単位３５４、第３割り当て単位３５６及び第４割り当て単位３５８に分けられている。１つの割り当て単位のサイズは１つのＩフレームのサイズよりも大きいが、１つのＩフレームが２つの割り当て単位にわたって断片化されて格納されることも依然として可能性がある。更に、これら割り当て単位は連続して描かれているが、斯かる割り当て単位はディスク上で必ずしも連続して位置されていなければならないわけではない。
【００４７】
割り当て単位がディスク上で連続して位置していないとき、１つのＩフレームの取り出しのために、２つの割り当て単位からのデータが取り出されなければならないという問題が起きる。これは、１つのデータ取扱要求に対して、２つのディスク要求が実行されなければならない（１つのディスク要求により、多くて１つのグループの連続した割り当て単位のデータが取り出されうる）ということを意味している。トリックプレイの間におけるＩフレームの取り出し時間の増加は、誤りによる取り出し時間の増加よりも遙かに頻繁に起こりうるので、断片化による取り出し時間の増加をモデル化することが重要である。
【００４８】
ディスク要求（又はより一般には記憶装置要求）の数に対する単純だが非常に大まかな推定は、取り出されなければならない全てのデータオブジェクトが断片化されていると推定し、従って全てのファイル要求が２つのディスク要求を必要とするという上限を設けることである。次に、ファイル要求の実行のための最悪の場合の時間量を得るために、１つのディスク要求を実行するために必要な最悪の場合の時間を、ディスク要求の数に掛ける。全く同様に、１つのディスク要求の実行に必要な平均時間が使われうるが、その場合には当該計算によりファイル要求の実行のための平均時間が得られるだろう。この時間要因の構成は以下の説明においてより更に明確にされるだろう。より小さい割り当て単位及びより大きいファイル要求に対して、上限は式１により与えられる。
式１
［ディスク要求の数］
2007519141.tif 000011
［ファイル要求の数］×（ＩＮＴ（［ファイル要求の最大サイズ］／［割り当て単位のサイズ］）＋２）
ここで、関数ＩＮＴ（
2007519141.tif 000012
）は実数
2007519141.tif 000013
を最も近い整数に切り下げる。
【００４９】
より大きなサイズの割り当て単位及び／又はより小さなサイズのファイル要求（又は、この例におけるＩフレームのような、取り出すべき他のデータオブジェクトのサイズ）の場合、ディスク要求の数に２なる係数を掛けるアプローチは、最悪の場合の上限を与える。図３に見られるように、割り当て単位が十分に大きいときは、相対的に少ない数のＩフレームだけが断片化される。しかしながら、図３に描かれているのは、Ｉフレームだけが示されていてＧＯＰの残りは小さく描かれているので、きわめて図式的なものであるということに留意されたい。
【００５０】
データオブジェクトが互いから実質的に等しい距離で格納され、ファイル要求のサイズ（取り出すべきデータの塊のサイズ）が割り当て単位のサイズよりも小さいとき、本発明の一実施例によれば、同じ量のファイル要求数に対しては、ディスク要求の数及びこれらのディスク要求を実行するために必要な最悪の場合の時間の、上述したものよりも一層正確な推定を得ることができるということを、本発明者らは理解した。
【００５１】
ＭＰＥＧ２で圧縮されたビデオストリームの場合、Ｉフレーム間の距離（バイト単位、従って論理距離）は、Ｉフレームのサイズと同様に実質的に一定である。ＭＰＥＧ２圧縮は可変ビットレート圧縮アルゴリズムであるが、これらの距離はかなり良好に推定することができ、すくなくとも上限は与えられうる。
【００５２】
Ｉフレームのサイズ、これらフレームの間の距離及び割り当て単位のサイズを知ると、取り出されるべきＩフレームのどれだけ多くが１つの割り当て単位に断片化されずに格納されるかを推定することができ、これのために下限が与えられうる。この推定は、Ｉフレームのサイズ及びそれらの間の距離の平均を取ることにより計算することができ、下限は最悪の場合の値をとることにより計算されうる。
【００５３】
次に、ファイル要求の総数（これは、取り出すべきデータオブジェクトの数に等しい）が判明し、断片化されていないデータオブジェクトの数の下限が判明するので、取り出されるべき断片化されたＩフレームの数の上限が決定されうる。割り当て単位のサイズがデータオブジェクトのサイズよりもかなり大きいことが判明すると、データオブジェクトはせいぜい２つの割り当て単位にわたって断片化され得ると推測されうる。これは、ディスク要求の数の上限が、ファイル要求の数と取り出されるべき断片化されたデータオブジェクトの数の上限との和をとることにより計算されうるということを意味している。
【００５４】
要素の平均値が、取り出されるべき断片化された（又は断片化されていない）データオブジェクトの量を決定するために使用された場合、ディスク要求の数の推定が計算されうる。
【００５５】
ディスク要求の最悪の場合の数を計算する計算式が、式２及び式３で与えられる。
式２
［ディスク要求の数］
2007519141.tif 000014
［ファイル要求の数］＋（［関連する割り当て単位数］−１）
及び、
式３
［関連する割り当て単位数］
2007519141.tif 000015
ＩＮＴ（［ファイル要求の数］×ＩＮＴ（（［最大距離］＋［最大サイズ］）／［割り当て単位のサイズ］）＋２）
これは数値の例を用いて説明することができる。
ＧＯＰ：３８０キロバイト
Iフレームサイズ：４０キロバイト
レンダリングのために１つ置きのＩフレームを選択する。
ジャンプサイズ（距離）：３４０キロバイト
割り当て単位のサイズ：１０２４キロバイト
フレームレート：４フレーム／秒
サイクルサイズ：２秒
１サイクルあたりのファイル要求：８
［関連する割り当て単位数］
2007519141.tif 000016
ＩＮＴ（（８×（４０＋３４０）／１０２４）＋２）＝ＩＮＴ（４．９７）＝４
従って、関連する割り当て単位の最大数はスケジューリングサイクルあたり３となり、式２に代入すると
［ディスク要求の数］
2007519141.tif 000017
８＋４−１＝１１
【００５６】
上記の場合の概略図を示す図３は、確かに４つの割り当て単位が関連することを示している。ディスク要求の数は、この場合見、推定よりも少なくなっている。要求されたファイルの１つだけが断片化されており、従ってディスク要求の数は、ファイル要求の数よりも１つだけ大きい、すなわち９となっている。それでも、１１のファイル要求という推定は、式１が算出する１６のファイル要求という推定よりも、９に大幅に近くなっている。
【００５７】
式４及び式５は、幾つかの場合に関して、関連するディスク要求数の上限に対する一層正確な推定を与える。
式４
［ディスク要求数］
2007519141.tif 000018
［ファイル要求数］＋１＋
（［ファイル要求数］−１）／（［関連する割り当て単位数］＋１）
及び、
式５
［関連する割り当て単位数］
2007519141.tif 000019
ＩＮＴ（（［割り当て単位のサイズ］−［ファイル要求の最大サイズ］）／
（［最大距離］＋［最大サイズ］））
【００５８】
次に、ハードディスクドライブによる実行のためにディスク要求を適切にスケジュールするため、１つのディスク要求の実行のために必要とされる時間が必要とされる。この時間の量はいくつかの構成物からなり、なかでも最も重要な３つが図４において議論されるだろう。図４は、第１データ部分４０４を有する第１データトラック４０２と、第２データ部分４０８を有する第２データトラック４０６とを持つハードディスクドライブのディスク４００を示している。図４は、読取／書込ヘッド４２２を持つアーム４２０も示している。
【００５９】
第１の矢印４３２は、シーク時間を示している。これは、上記ハードディスクドライブの読取／書込ヘッドを、第１データブロック４０４が取り出されなければならない第１トラック４０２へ位置決めするために必要とされる時間量である。近年のハードディスクの場合、この時間は０から４０ミリ秒である。
【００６０】
第２の矢印４１２は、回転の遅れを示している。これは、第１データ部分４０４の取り出しを開始するために、第１データ部分４０４の始点を読取／書込ヘッド４２２に位置合わせをするようにディスク４００を回転させるために必要な時間量である。７２００回転／分の回転速度を持つ近年のハードディスクでは、この値は多くて８．３ミリ秒である。
【００６１】
第３の矢印４１４は、データ取り出し時間を示している。これは、データ取り出しが命令されたデータを、実際に取り出すために必要な時間量である。この時間量は、取り出されるべきデータの量に非常に依存する。上記の場合、すなわち各ディスク要求で４０キロバイトの１つのＩフレームのみが取り出されなければならない場合、この時間量は相対的に小さい。
【００６２】
非常に単純なアプローチの場合、ディスク要求の数の上限に、１つのディスク要求を実行するために必要な最悪の場合の時間を掛ける。この最悪の場合の時間は、前の段落に記載の３つのタイミングパラメータ（又はそれらのうちのいくつか）に、恐らくは他のパラメータ（１つ、いくつか又は全てのパラメータの標準偏差のような）を加えたものの和となりうる。
【００６３】
しかしながら、複数のディスク要求に対するデータが接近して一緒に位置しているとき、おそらく切り替え時間は余り必要とされない。当業者にとっては、複数のディスク要求の実行のタイミングの振る舞いを推定するための一層進んだモデルを記載した様々な文献が利用可能である。しかしながら、本発明全体に対しては、どのモデルを用いるかは重要ではない。
【００６４】
本発明は、サイクルに基づくスケジューリングアルゴリズムにおいて、ファイル要求を実行するための最悪の場合の時間を決定するように説明されているが、本発明は、他のスケジューリングアルゴリズムを用いて、データ取り出しシステムにおけるデータの取り出し及び実行時間を推定するために使用することもできる。
【００６５】
本発明の実施例は、本発明による方法の実施例を実行するための１つの処理ユニットを持つ装置として記述されている。しかしながら、本発明による方法の実施例の様々なステップが複数の処理ブロックにより実行されるような本発明による装置の他の実施例も、本発明の範囲から逸脱することなしに可能である。
【００６６】
本発明の好ましい実施例においては、本発明は、オーディオビジュアルデータの取扱に応用される。当業者は、もちろん、本発明が他のタイプのデータにも応用することができると理解するであろう。
【００６７】
要約すると、本発明は、実時間データ取扱に関連し、より詳細にはフレームの断片化を考慮してビデオレンダリングのためのフレームを取り出すために必要な時間を推定することに関連する。特にトリックプレイのためにデータを取り出すためには、これは些細な事柄ではない。何故なら、取り出されるべきフレームが断片化されているかどうかは事前には分からないからである。非連続的に断片化されたフレームの取り出しには、断片化されていないフレームの取り出しより少なくとも２倍多い時間がかかる。本発明は、割り当て単位が取り出されるべきフレームのサイズよりも大幅に大きい場合を考慮して、種々の有利な実施例を提供する。本発明の一実施例は、トリックプレイ速度、割り当て単位のサイズ、フレームサイズ及び取り出すべきフレーム間の論理的データ距離が分かる場合に、正確な取り出し時間を推定する方法を提供する。
【参考文献】
【００６８】
J.  Korst,  V.  Pronk  and  P.  Coumans,  Disk  scheduling  for  variable-rate  data  streams,  Philips  Research  Laboratories  Eindhoven,  The  Netherlands,  Proc.  European  Workshop  on  Interactive  Distributed  Multimedia  Systems  and  Telecommunication  Services,  IDMS'97,  1997.
【図面の簡単な説明】
【００６９】
【図１】本発明による装置の一実施例である。
【図２】オーディオビジュアルデータのストリームからどのようにトリックプレイストリームが作られるかを示す。
【図３】割り当て単位でのオーディオビジュアルデータのストリームの格納を示す。
【図４】ディスク要求のサービス時間を決定するための様々なタイミングパラメータを説明するために、ピックアップユニットを持つディスクの概要を示す。
【図１】
2007519141.tif 000023
【図２】
2007519141.tif 000024
【図３】
2007519141.tif 000025
【図４】
2007519141.tif 000026
【国際調査報告】
2007519141.tif 000027
2007519141.tif 000028
2007519141.tif 000029