JPH10162507A - 同時リード−ライト要求用ビデオサーバスケジューリング - Google Patents

同時リード−ライト要求用ビデオサーバスケジューリング

Info

Publication number
JPH10162507A
JPH10162507A JP9255319A JP25531997A JPH10162507A JP H10162507 A JPH10162507 A JP H10162507A JP 9255319 A JP9255319 A JP 9255319A JP 25531997 A JP25531997 A JP 25531997A JP H10162507 A JPH10162507 A JP H10162507A
Authority
JP
Japan
Prior art keywords
write request
request
deadline
queue
write
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP9255319A
Other languages
English (en)
Other versions
JP3372842B2 (ja
Inventor
Cammel Ibraheem
イブラヒム・カメル
G Alef Warid
ワリド・ジー・アレフ
Aronso Raphael
ラファエル・アロンソ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Publication of JPH10162507A publication Critical patent/JPH10162507A/ja
Application granted granted Critical
Publication of JP3372842B2 publication Critical patent/JP3372842B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/21—Server components or server architectures
    • H04N21/218—Source of audio or video content, e.g. local disk arrays
    • H04N21/21815—Source of audio or video content, e.g. local disk arrays comprising local storage units
    • H04N21/2182—Source of audio or video content, e.g. local disk arrays comprising local storage units involving memory arrays, e.g. RAID disk arrays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
    • H04N21/231—Content storage operation, e.g. caching movies for short term storage, replicating data over plural servers, prioritizing data for deletion
    • H04N21/2312—Data placement on disk arrays
    • H04N21/2315—Data placement on disk arrays using interleaving
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
    • H04N21/232—Content retrieval operation locally within server, e.g. reading video streams from disk arrays
    • H04N21/2326—Scheduling disk or memory reading operations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/80—Generation or processing of content or additional data by content creator independently of the distribution process; Content per se
    • H04N21/83—Generation or processing of protective or descriptive data associated with content; Content structuring
    • H04N21/845—Structuring of content, e.g. decomposing content into time segments
    • H04N21/8456—Structuring of content, e.g. decomposing content into time segments by decomposing the content in the time domain, e.g. in time segments

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Databases & Information Systems (AREA)
  • Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)
  • Signal Processing For Digital Recording And Reproducing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【課題】 ビデオ・オン・デマンド要求により同時にビ
デオオーサリング及び編集を処理できるように、ビデオ
サービスの機能拡張を意図したものである。 【解決手段】 ビデオサーバに於ける同時ディスクリー
ド及びライト要求をサポートすると共に、バッファプー
ルに於ける有用なスペース量に基づいてライト要求に対
するデッドラインを割り当てるステップと；リード要求
と共通ディスクキューに於ける前記要求を挿入するステ
ップと；そして、キューの先頭に来る前記リード及びラ
イト要求を処理するステップを有する方法を提供する。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明は、同時リード及び
ライト要求に関連するリアルタイム要求に於いて、ユー
ザによって成される同時リード−ライト要求をサポート
する新しいディスクスケジューリングアルゴリズムに関
する。
【０００２】
【従来の技術】ビデオ・オン・デマンド及びビデオオー
サリングツールが、非常な興味と共にマルチメディアア
プリケーションを切り開くものとして出現している。こ
れらは、高帯域幅を必要とすると共に、リアルタイム要
求を擁する特別なハードウェアとネットワーキングプロ
トコルを必要とする。ビデオ・オン・デマンドアプリケ
ーションを取り扱う各種のビデオサーバアーキテクチャ
が提案されている。１９９４年５月発行の第５回インタ
ーナショナルワークショップオンマルチメディアコミュ
ニケーション誌、３４１−３４６頁に発表されたＹ．イ
トー及びＴ．タナカによる「ＡＴＭスイッチング技術を
用いたビデオサーバ」；１９９２年発行のＡＣＭ会報の
コンピュータシステム誌の１０（４）、３１１−３３７
頁に発表されたディビッドアンダーソン、ヨシヒトオサ
ワ、及びラメシュゴヴィンダンによる「連続メディアの
ファイルシステム」；１９９２年７月発行のＩＥＥコミ
ュニケーションマガジン、５６−６４頁に発表された
Ｐ．Ｖ．ランガン、Ｈ．Ｍ．ビン、及びＳ．ラマナサン
による「オン・デマンドマルチメディアサービスの設
計」がある。本発明は、第５回インターナショナルワー
クショップオンマルチメディアコミュニケーション誌に
提案された、ＡＴＭスイッチにより内部接続されるファ
イルサーバ及び複数のディスクを用いるようなサーバア
ーキテクチャに良く適合する。本発明は、その他のアー
キテクチャにも実施できる。数種のパフォーマンススタ
ディ及びシミュレーションによって、本システムの性能
が見積もられている。
【０００３】ビデオサーバは各種のアプリケーションを
サポート出来る。これらのアプリケーションの中には、
ビデオ・オン・デマンド、及びビデオオーサリング或い
は編集が有る。各アプリケーションは、それ自身のシス
テム要求を有している。本発明は、そのようなシステム
のディスクスケジューリング要求に主眼を置いている。
例えば、ディスクと言う観点から見ると、ビデオ編集ア
プリケーションがリード及びライトの両要求を発行して
いる間に、ビデオ・オン・デマンドアプリケーションは
ディスクに対してリードオンリー要求を発行する。更
に、ある種のアプリケーションは、リアルタイムデッド
ラインを所有或いは非所用するリード及／或いはライト
要求がデッドラインの前に使用されるようにこれらの要
求を発行する。例えば、ビデオ・オン・デマンドに置い
ては、各リード要求は、所定のデッドライン内に実行さ
れねばならない。最終的に、ある種のアプリケーション
は、自身のリード或いはライト要求の幾つかがシステム
によって喪失されるのを、つまりディスクによって利用
したり実行されたりしないことを容認する。例えば、フ
レームの幾つかは、ディスクに於ける渋滞の為に、ビデ
オ表示中に喪失され得る。
【０００４】正式には、ディスクスケジューリングの観
点から、リード及びライト要求を、それぞれ特定のアプ
リケーションに対して有用で且つ互いに異なる要求を有
する４つのカテゴリーに分類するものとする。これらの
カテゴリーには： １．ｄｌ要求： これらは、渋滞の場合には喪失（los
t）し得る要求とデッドライン（deadline）を有するリ
ード或いはライト要求である。本カテゴリーのリード及
びライト要求は、それぞれ、Ｒdl及びＷdlとして参照さ
れる。 ２．ｄｎ要求： これらは、システムの渋滞に関わらず
喪失が許されない（not）要求とデッドライン（deadlin
e）を有するリード或いはライト要求である。本カテゴ
リーのリード及びライト要求は、それぞれ、Ｒdn及びＷ
dnとして参照される。 ３．ｎｌ要求： これらは、渋滞の場合には喪失（los
t）が許される要求を有するがデッドラインを有しない
（no）リード或いはライト要求である。本カテゴリーの
リード及びライト要求は、それぞれ、Ｒnl及びＷnlとし
て参照される。 ４．ｎｎ要求： これらは、システムの渋滞に関わらず
喪失が許されない（not）要求を有するがデッドライン
を有しない（no）リード或いはライト要求である。本カ
テゴリーのリード及びライト要求は、それぞれ、Ｒnn及
びＷnnとして参照される。
【０００５】例えば、ビデオ・オン・デマンドに於ける
アプリケーションが、Ｒｄｌ要求だけをサポートしなけ
ればならないディスクスケジューリングプロセスで有る
場合である。つまりデッドラインを有するが、そのデッ
ドラインの前に要求が使用されない場合には喪失が可能
なリード要求である。要求の各カテゴリーに対して、異
なるディスクスケジューリングプロセスをデザインする
必要がある。カテゴリーｎｌ（Ｒnl或いはＷnl）に所属
する要求に対しては、デッドラインが無いので、これら
の要求が満足されるまで遅延できるので常に真である。
それ故に、それらが用いられるまで待たせることができ
るように、それらを喪失させることはシステムにとって
意味が無い。結果的に、Ｗnl及びＲnlは此処では、それ
ぞれ、Ｗnn及びＲnnとして扱われる。なぜならば、それ
らはデッドラインを有しないし、決して喪失されないか
らである。結果として、此処ではｄｌ、ｄｎ、及びｎｎ
カテゴリーに対してのみ、ディスクスケジューリング技
法を考慮する。
【０００６】
【発明が解決しようとする課題】リード要求に関するＲ
dl及びＲnnカテゴリーと、ライト要求に関するＷnnカテ
ゴリーとをサポートする新しいディスクスケジューリン
グプロセスを提供する。更に、これらのカテゴリーの組
み合わせて、ビデオサービス用のある種の共通アプリケ
ーション自然に整合する方法及び装置を提供することを
目的とする。
【０００７】
【課題を解決するための手段】本発明は、前記課題を解
決するための手段として、である。ビデオサーバーでデ
ィスクリード要求とディスクライト要求を同時に保持す
る方法であって、バッファープールの利用可能な空間の
総量に基づく上記ライト要求にデッドラインを割り当
て、共通のディスクキューに上記リード要求とライト要
求とを挿入し、上記キューの先頭に来る上記リード要求
と上記ライト要求を処理する方法を提供する。更に、デ
ィスクリード要求とディスクライト要求を同時に保持す
るビデオサーバー構成であって、メモリーバッファープ
ールであって、上記リード要求及び上記ライト要求が一
時的に貯蔵されるもの、共通のディスクキューであっ
て、上記メモリーバッファーからの上記リード要求及び
上記ライト要求が受け入られるもの、上記リード要求と
ライト要求を処理するファイルサーバーであって、すく
なくともディスクを１つ保持するもの、上記ディスクキ
ューに上記リード要求及びライト要求を挿入する位置を
決定するコントロール手段であって、上記ライト要求が
割り当てられたデッドラインであるものを含んだ構成を
提供する。
【０００８】
【発明の実施の形態】本発明は、ビデオプリゼンテーシ
ョン及びビデオ編集に対するリアルタイム要求に於い
て、同時リード及びライト要求を処理するディスクスケ
ジューリングングに関する。更に詳述すれば、本発明の
プロセスは、ライト要求に対するＷnnカテゴリーとリー
ド要求に対するＲdl及びＲnnカテゴリーをサポートす
る。ビデオ編集がリード及びライトの両要求（Ｒnn及び
Ｗnn要求）に至るのに対して、ビデオプリゼンテーショ
ン或いは表示はファイルシステムに対するリード要求
（Ｒdl）に至る。
【０００９】本発明は、本明細書の一部として取り込ま
れる１９９４年５月発行の第５回インターナショナルワ
ークショップオンマルチメディアコミュニケーション
誌、３４１−３４６頁に発表されたＹ．イトー及びＴ．
タナカによる「ＡＴＭスイッチング技術を用いたビデオ
サーバ」に提案されたビデオサーバアーキテクチャに置
いて実施することが出来る。本アーキテクチャに於ける
主な要素が図１に示されている。サーバアーキテクチャ
の概要を以下に述べる。
【００１０】ビデオサーバ１０はＭＰＥＧ-エンコード
（圧縮）されたビデオストリームをサポートしている。
各ストリームは、メディアセグメントファイル（ＭＳ
Ｆ）ブロックと呼ばれる固定長単位に分解される。所定
のビデオストリームに対するメディアセグメントファイ
ルブロックは、ファイルシステムの全体に分散して保存
される。ファイルシステムは複数のディスク保存サーバ
を有しており、そこでは各保存サーバがメディアセグメ
ントファイルサーバ（ＭＳＦＳ）と呼ばれる。メディア
セグメントファイルサーバ１２は、様々なビデオストリ
ームに所属するメディアセグメントファイル（ＭＳＦ）
のブロックを保存する。ビデオストリームを正しい順番
で取り出す為に、シーケンスコントロールブローカ（Ｓ
ＣＢ）１４は、ビデオストリームの全メディアセグメン
トファイルブロックに対するポインタの順番リストを保
存する。シーケンスコントロールブローカ１４は、ユー
ザの代わりに、ビデオ再生ストリームを維持するべく作
用する。各シーケンスコントロールブローカ１４は、例
えば２４或いは６４ユーザというような一以上のユーザ
ターミナル１６を同時にサポート出来る。一つのシーケ
ンスコントロールブローカ１４に接続されるユーザター
ミナル１６の数は、システム全体として全てのユーザに
対して連続ビデオ再生を保証できるように予め決められ
る。
【００１１】ビデオ再生セッションの初期化では、シー
ケンスコントロールブローカ（ＳＣＢ）１４が、要求さ
れた映画のポインタリストを取り出す。再生中には、シ
ーケンスコントロールブローカ１４が、ユーザの代わり
にメディアセグメントファイルサーバ（ＭＳＦ）１２に
リード要求を送出して、ユーザに不断のサービスを保証
する。シーケンスコントロールブローカ（ＳＣＢ）１４
は、更に、例えば早送りとか巻き戻しという仮想ビデオ
カセットレコーダ（ＶＣＲ）機能要求処理も受け持つ。
【００１２】シーケンスコントロールブローカ（ＳＣ
Ｂ）１４及びメディアセグメントファイル（ＭＳＦ）セ
クタＳ１２は、一つのブロックに組み込まれている。ビ
デオサーバに於いては、例えば１５個という、複数のＰ
Ｕユニット１８が存在する。各シーケンスコントロール
ブローカ（ＳＣＢ）１４は、対応するメディアセグメン
トファイルサーバ１２に存在するデータに直接アクセス
できる。しかしながら、メディアセグメントファイルは
複数のメディアセグメントファイルサーバ１２にまたが
って保存されているので、シーケンスコントロールブロ
ーカ１４はその他のプロセッシングユニット１８のメデ
ィアセグメントファイルサーバ１２にアクセスする必要
がある。
【００１３】プロセッシングユニット１８が通信する為
に、全てがＡＴＭスイッチ２０に接続される。例えば、
シーケンスコントロールブローカ１４がＡＴＭスイッチ
２０を使って、複数のプロセッシングユニットに存在す
るメディアセグメントファイルサーバ１２に渡るメディ
アセグメントファイル（ＭＳＦ）を取り出す。ＡＴＭス
イッチ２０は、メディアセグメントファイルサーバ１２
の全てに対して、システムに於ける各シーケンスコント
ロールブローカ１４からの接続を保証するメッシュネッ
トワークを提供する。
【００１４】シーケンスコントロールブローカ１４は、
他の側から、ビデオサーバ１０をエンドユーザ１６に接
続する外部ネットワーク２２に接続されている。ユーザ
１６はセット・トップボックスを用いて外部ネットワー
ク２２に接続される。このセット・トップボックスは、
ＭＰＥＧエンコードされたビデオデータをデコードし、
仮想ＶＣＲ機能要求に対するユーザインターフェースを
提供し、シーケンスコントロールブローカ１４と通信す
る機能を有している。
【００１５】Ｒdlリード要求は、特定の時間に特定の映
画或いはビデオクリップを見るというユーザのデマンド
の結果である。一旦システムに入れば、ユーザには特定
の品質のサービスが保証される。このことは、聴視者が
気づかない程フレームのロス率が非常に小さいフレーム
の連続ストリームを聴視するということで表される。フ
レームロスは多岐に渡る理由により起こり得るが、此処
ではメディアセグメントファイルサーバ１２中のディス
クの渋滞に起因する喪失を対象とする。メディアセグメ
ントファイルサーバ１２のディスクに対する各リード要
求は、リアルタイムデッドラインを有している。メディ
アセグメントファイルサーバ１２は、デッドライン中に
要求を実行できるか否かを判定する。これに基づいて、
メディアセグメントファイルサーバ１２は要求を受諾或
いは拒絶する。後者の場合、拒絶されたリード要求に対
応する頁は喪失されたと見なされる。
【００１６】シークタイムは、ディスクから頁を引き出
す際に最も時間を要する部分である。ディスクスケジュ
ーリングプロセスの目的の一つは、ディスクから頁を引
き出すことである。これは、シークタイムが最小になる
ようにディスクアクセス要求をキューすると共にオーダ
ーすることにより達成出来る。プロセスＳＣＡＮは、こ
の問題を処理する従来のディスクスケジューリングプロ
セスの一つである。Ａ．シルバーシャッツ及びＰ．Ｂ．
ガルヴィン。アディソンウェズリィにより、１９９４年
発行のオペレーティングシステムコンセプト、第４版に
発表されている。ＳＣＡＮに於いては、ディスクヘッド
は一方向（内側或いは外側）へ移動し、シリンダーポジ
ションがディスクヘッドが現在位置している場所になる
ようなディスク要求を出す。ディスクヘッドは、シリン
ダーポジションの最高位置に達すると、移動方向を反転
して、そのパスに沿って広がるディスク要求を出す。
【００１７】リアルタイム要求により、ＳＣＡＮは、要
求された頁のリアルタイムコンシダレーションに適合す
るように修正されている。プロセスＳＣＡＮＲＴ（リア
ルタイムコンシデレーションを伴うＳＣＡＮ）は、ＳＣ
ＡＮの修正版である。ディスク問い合わせ中に新たに挿
入された要求がキュー中に既に存在するディスク要求の
リアルタイム要求を破らない限り、ＳＣＡＮＲＴはディ
スク要求をＳＣＡＮの順番に出す。ＳＣＡＮの順番に挿
入された新たな要求が、ディスクキューに既に存在する
他の要求をデッドラインを損なわせる場合には、新たな
要求はキューの終端で挿入される。この時には、新たに
挿入されたディスク要求が、自身のデッドラインに間に
合うように適時出すことが出来るかが判断される。もし
間に合わないと判断される場合には、要求は無視され、
喪失したものと見なされる。
【００１８】ｎｎ要求に対するｄｌ要求の量、例えば混
合比が５０％対５０％或いは９０％対１０％、によって
システム負荷特性が決定されるということ重要なことで
ある。これは、ビデオサーバ１０中に於けるビデオプリ
ゼンテーション対編集活動量を反映するものである。ビ
デオ編集或いはオーサリングセッションに於いて、リー
ド及びライト要求を出すことができる。先ず、ライト要
求について述べた後に、リード要求について述べる。
【００１９】ビデオ編集セッションに於いて、セッショ
ン中に出されるライト要求が、Ｗnnカテゴリーに属する
もモデルとして説明する。ライト要求に対するＷnnカテ
ゴリーは、ビデオプリゼンテーションに対するリード要
求と異なる特性を有しており、それ故にシステムによっ
て異なるように扱われる。これらの特性は以下の如く要
約出来る。 １． ディスクに書き込まれる任意の頁は、既にメイン
メモリライトバッファプール２８中に予め保存されてい
る。 ２． Ｗnnライト要求はリアルタイムデッドラインを有
しない。それ故に、リード要求に比べて長時間の遅延を
可能とする。 ３． Ｗnnライト要求はデッドラインを有していない
が、不定時間の待機は出来ない。ライトバッファプール
２８が一杯になるのを防ぐ為に、将来のいつか実行され
るべきである。 ４． Ｗnnライト要求は、システム負荷等によって喪失
出来ない。ソステム負荷に関わらず、ライト要求は或る
時間にシステムによって実行されねばならない。 ５． システム負荷に基づいて、ライトバッファプール
２８は一杯になることが出来る。バッファスペースを新
たに到着するライト要求の為に空けてやるために、この
時点でペンディング中のＷnnライト要求のいくらかは、
図２に示すようにディスク３０にフラッシュされねばな
らない。 ６． Ｗnnライト要求は、例えば電源不全のようなシス
テムクラッシュに対して柔軟で無ければ成らない。言い
換えれば、ユーザの観点からは、システムが一旦ライト
要求を認識したら、ユーザは書き込まれた頁Ｐwは将来
の任意の時間にシステム中に存在していることを期待す
る。これは、Ｐwがメモリバッファ中に一次的に保存さ
れ得ると言う事実に反しているので、電源不全の時に
は、それが失われる可能性がある。システムはこのよう
なシナリオの事態を防止するべく必要な予防策を講じな
ければならない。
【００２０】上述の特性点に基づいて、システムの性能
にとって重要なパラメータの幾つかについて述べる。こ
れらの特徴点の中で最も重要なのは、図２に示すよう
に、メインメモリライトバッファプール２８の大きさで
ある。ライト要求によりシステムに化された要求は、よ
り大きなライトバッファプールによって低減できると予
期される。Ｒdlリード及びＷnnライトの両要求を同時に
取り扱う為に、システムは、同両要求が適合すると共に
両タイプの要求をサポートする均質フレームを採用す
る。
【００２１】本発明は、これを、上述したライト要求の
特性に反映したライト要求Ｗnnの達成のために、人為的
なデッドライン(区切り)を発展させることにより達成す
る。リード要求Ｒdlもまたデッドラインを持つので、本
発明は、リードおよびライト要求の双方のカテゴリーに
対する同質な処理方法を提供する。本発明のディスクの
スケジュール作成技術を詳しく紹介する前に、いくつか
の基本概念の概要を開示する。図５（Ａ）および５
（Ｂ）(集合して図５と呼ぶ)を参照すると、図５（Ａ）
は、通常のディスクのスケジュール作成のプロセスがい
かに実施されるかを示す。図５（Ｂ）は、いかに本発明
が動作するかを示す。これらの二つの図を比較すると、
本発明のいくつかの原理を理解できる。
【００２２】図５（Ａ）において、分離したリードキー
１００とライトキュー１０２は、リードおよびライトの
アクセスに役立つ。図５（Ａ）において、ディスクは、
１０４にて図形的に描かれている。個々のリード要求１
０６は、それぞれ関連するデッドライン１０８を持つ。
図５（Ａ）において、個々のリード要求は、図式的に楕
円１０６で示され、それらは関連するデッドラインのパ
ラメータ１０８を持つ。これらのリード要求は、種々の
異なった時間で、システムの一人または多くのユーザー
から生じたものである。図５（Ａ）でわかるように、リ
ード要求は、デッドラインのパラメータに基づきキー１
００内のメモリ位置に割り当てられる。この結果、リー
ド要求は、短いデッドラインでもってキューの先頭に接
近して位置し、これにより、それらの要求はより迅速に
処理される。そのデッドラインの属性は、リード要求を
“エレベータ”の順に配列するために用いられる。その
要求は、ディスクへの効率よいアクセスとなるような観
点に従って配置される。その結果、リード要求は、可能
な限り、蓄積された記録を連続的にリードできるように
配列される。
【００２３】そのリード要求に反して、ライト要求（図
式的に１１０で示す）は割り当てられたデッドラインを
持たない。この結果、システムのユーザーがライト要求
を出したとき、その要求はライトキュー１０２内の次に
利用可能なメモリ位置に置かれる。ディスク１０４への
リードおよびライト信号は、最初に処理用のリードキュ
ー１００によって処理され、リードキューをサポートす
るために使用されないフリー時間があるときのみ、処理
用のライトキュー１０２によって処理される。
【００２４】図５（Ｂ）を参照すると、本発明は、個別
のリードおよびライトキューを利用するための必要性を
省く。その替わりに、本発明は、単一の同質のキュー１
１２を用い、これは、同じメモリ構成でレード要求とラ
イト要求の双方をサポートする。上述したように、リー
ド要求１０６は、関連したデッドラインの属性１０８を
持つ。本発明は通常の実行とは異なり、すべてのライト
要求に人為的なものではなく実際のデッドラインを割り
当てる、優先モジュール１１４を採用する。その結果、
図５（Ｂ）において、ライト要求１１０は、それぞれ関
連したデッドラインの属性１１６を持つようになる。以
下により詳細に述べるように、それらのデッドライン
は、利用可能なフリーのバッファスペースに基づき割り
当てられる。すべてのライト要求に人為的に割り当てら
れたデッドラインを持つことにより、リードおよびライ
ト要求は、エレベータ式の位置決めスキームを用いて単
一の同質のキュー１１２を通じて処理されるようにな
る。その構成は、バッファのオーバーフローを防止する
ために必要とされたとき、リード要求を犠牲にすること
により、ライト要求は失われない。実際に、本発明は、
リードおよびライト要求がシステムに出されたとき、よ
り優先順位の高いリードおよびライト要求をキューの先
頭により接近させることにより、すべてのデッドライン
を試した。
【００２５】次のパラメータは、本発明のプロセスを記
述するために用いられる。 Ｎb：ライトバッファプール２８のバイトサイズ Ｐw：ライトページのバイトサイズ（これらの二つのパ
ラメータからＮw（バッファが収容できるライトページ
の数）を演算できる) λw：ティスクライト要求のシステムへの到着速度 時刻ｔにおいて、ユーザーがページ、つまりＰwがディ
スク３０にライトされることを要求したと仮定する。ペ
ージＰwがディスク３０にデッドラインの前にライトさ
れるように、ページＰwに対してデッドラインが割り当
てられる。
【００２６】ライト要求のデッドラインは、次のように
して演算される。ｎw(ｔ)を時刻ｔにバッファ２８に存
在するライト要求の個数、ｎf(ｔ)を時刻ｔにバッファ
プール２８内のフリーバッファスロットの個数とする。
すると、ｎf(ｔ)＝Ｎw−ｎw(ｔ)。最悪ケースの想定で
は、リード要求Ｒdlのため、バッファ２８からディスク
３０へページは書き込まれず、同時に、新しいライト要
求がλwの速度でライトバッファプール２８に続いて到
着する。その結果、(新しいライト要求により)その時刻
で、ライトページｐwがバッファプール２８に到着し、
この最悪ケースの想定に対して、必要とされる時刻、つ
まり、ライトバッファプール２８が満杯になる前のｄ
(ｔ)が予測される。ｄ(ｔ)は以下のように演算される。 ｄ(ｔ)＝ｔ＋ｎf(ｔ)／λw
【００２７】そのｄ(ｔ)は、実際に、時刻ｔ、つまりｄ
(ｔ)でのライトバッファプール２８内のすべてのページ
のデッドラインは、ライトバッフア２８内の現行のすべ
てのページに対する全体的なデッドラインであることに
注目する。その結果、ページｐwがディスク３０に物理
的に書き込まれたとき、バッファプール２８内で一つの
バッファスロットをフリーにする。その結果、バッファ
２８が満杯になるまでにより多くの時間があるので、バ
ッファプール２８内のすべてのページに対するデッドラ
インｄ(ｔ)は緩和される。それ故、ｄ(ｔ)は次のように
して緩和される。ｔ0をｄ(ｔ)が修正されたラストの時
刻とすると、 ｄ(ｔ)←ｔ−ｔ0＋ｄ(ｔ0)＋１／λw
【００２８】これは、上記のｄ(ｔ)に対する公式と一致
する、つまり、 ｄ(ｔ)←ｔ−ｔ0＋ｄ(ｔ0)＋１／λw ＝ｔ−ｔ0＋ｔ0＋ｎf(ｔ0)／λw＋１／λw ＝ｔ＋(ｎf(ｔ0)＋１)／λw ＝ｔ＋ｎf(ｔ)／λw ｔ0はバッファプール２８内でのあらゆる変化のラスト
タイムなので、ｎf(ｔ)＝ｎf(ｔ0)＋１は、ライトペー
ジがディスク３０に物理的に書き込まれた後の新しいス
ペース合計である。
【００２９】ライトページが到着を要求したとき、対応
するペ−ジ、つまりｐwは、ライトバッファプール２８
内に位置する。ライト要求をディスクキュー３２内へ挿
入するために、リード／ライトのスケジュール作成シス
テムは、ｐwに対するデットライン、つまりｄw(ｔ)を割
り当て、そのｄw(ｔ)は、ライトバッファプール２８の
全体のデットラインｄ(ｔ)デットラインに対応する。つ
まり、ｄw(ｔ)←ｄ(ｔ)。最後に、ｐwおよびそのデット
ラインｄw(ｔ)は、ディスクキュー３２に挿入される。
本発明の主な利点は、スケジュール作成のプロセスが、
ライト要求をスキャン順に、リード要求を扱うＳＣＡＮ
ＲＴと同様な方法によって位置させるように試みる。こ
のことが達成され、又、ディスクキュー３２内でリード
とライトの要求の間で相互作用する機構を以下に述べ
る。
【００３０】先に述べたように、ＳＣＡＮＲＴディスク
のスケジュール作成プロセスは、キュー、ディスク・ス
ケジューラー・キュー、または単にディスクキューを保
ち、ディスクキュー３２内への加入は、ディスク３０に
１ページのリードまたはライトするための要求を示す。
ディスクキュー３２での要求は、シークタイムを減じ
て、ディスクキュー３２内であらゆる要求に対してデッ
ドラインの違反がないように、ＳＣＡＮＲＴ順に出され
る。リードのみに対して、ディスクキュー３２内のＲdl
およびＷnnの同時要求を扱うとき、考慮すべき必要な４
つの項目がある。これらは次のように分類される。 (１)ライト要求Ｗnnをディスクキュー３２に挿入し、
(２)リード要求Ｒdlをディスクキュー３２に挿入し、
(３)リード要求Ｒdlを処理し(ディスク３０から実際に
読み出す)、(４)ライト要求Ｗnnを処理する(ディスク３
０に実際に書き込む)。新しいプロセスは以下に述べる
ように、それらの各項目で異なる動作を実行する。
【００３１】ライト要求Ｗnnを挿入 図３に示したフローチャートに関しては、デイスクキュ
ー３２へのライト要求Ｗnnの挿入が記載されている。ペ
ージｐwに対するライト要求が一旦、ライトバッファプ
ールに到着すると(Ｓ４０)、メディアセグメントファイ
ルサーバー１２は、上述したように、ライト要求にデッ
ドラインを割り当てる(Ｓ４２)。次にライト要求がデイ
スクキュー３２に挿入される。これは以下のようにして
達成される。
【００３２】メディアセグメントファイルサーバー１２
のスケジュール作成プロセスは、スキャン順４４下にお
いてページｐwがどこに行くかを決定し、そして、新し
いライト要求をデイスクキュー３２内においてそのスキ
ャン順の中に挿入する。このケースにおいていくつかの
可能性が提示される。 １．デイスクキュー３２内でいずれのリードおよびライ
ト要求のデッドラインが無く、挿入された新しいライト
要求を含むとき、違反する。 ２．新しいライト要求がスキャン順に挿入されるなら
ば、オーダーのデッドラインは違反しない。しかし、挿
入時、いくつかの他のリード要求のデッドラインが違反
する。 ３．新しいライト要求がスキャン順に挿入されるなら
ば、オーダーのデッドラインは違反しない。しかし、挿
入時、いくつかの他のライト要求のデッドラインが違反
する。 ４．新しいライト要求がスキャン順に挿入されるなら
ば、そのライト要求のデッドラインが違反する。
【００３３】スケジュール作成プロセスがこれらの各々
の可能性をいかに処理するかは以下に述べる。ケース１
は、処理が容易で最も可能性の高いシナリオである。も
しスケジュール作成プロセスが、新しいライト要求のデ
ッドラインのみならず、キュー３２に既に存在するリー
ドおよびライト要求のデッドラインに違反することな
く、をキュー３２内へスキャン順にライト要求を挿入で
きることがみいだされたならば(Ｓ４６)、新しいライト
要求は、そのスキャン順にデイスクキュー３２へ挿入さ
れる。
【００３４】ケース２において、新しいライト要求がス
キャン順に挿入されたとき、新しいライト要求のデッド
ラインが違反しないが(Ｓ５０)、その挿入時、いくつか
の他のリード要求のデッドラインが違反する(Ｓ５２)。
このプロセスは、違反したデッドラインを持つリード要
求の喪失を避けるように試みる。もし、ライト要求のデ
ッドラインが違反することなく、そのライト要求がキュ
ー３２の終端で置き換えることができるならば(Ｓ５
４)、そのプロセスは、スキャン順ではなく、デイスク
キュー３２の終端に新しいライト要求を位置させる。こ
のことは、違反したデッドラインを持つリード要求が喪
失するのに役立つ。ここでの最も高い可能性は、キュー
３２の終端で別のスキャン順(次スキャン順と呼ぶ)を維
持し、そして、新しいライト要求を単にキュー３２の終
端に位置させる代わりに、その新しいライト要求を次ス
キャン順に挿入することである。
【００３５】ケース１およびケース２は、通常のシステ
ム動作において典型的なシナリオを構築する。他方、ケ
ース３および４は、ライト要求の速度がシステムの基本
タイムで定められた上限を超過する極端なケースではあ
る。システム動作の間に、ケース３およびケース４の発
生回数が重要になるとき、要求パラメータが変化し、評
価システムのパラメータを、例えばバッファプール２８
のサイズを拡張を示す。
【００３６】スケジュール作成プロセスがいからケース
３および４を扱うかを示すことに留まっており、新しい
ライト要求は、デイスクキュー３２内に既に存在する別
のライト要求のデッドラインを違反させるために決定さ
れる(Ｓ５８)。この場合、そのプロセスは、違反したデ
ッドラインを持つすべてのライト要求をデイスクキュー
３２の先頭に移動する(Ｓ６０)。この結果、デッドライ
ンが違反するようになったリード要求は、喪失したと考
えられる。もしライト要求のデッドラインが違反したと
き、新しいライト要求はスキャン順に挿入される(Ｓ５
９)。
【００３７】ケース３(新しいライト要求が他のライト
要求のデッドラインを違反させる)は、ライトバッファ
プール２８が混雑し、システムがオーバーロードしたこ
とを示す。この状況は、ビデオサーバ１０の許可制御プ
ロセスにより避けなければならない。ケース３では、新
しいライト要求がそのスキャン順に挿入されるならば、
新しいライト要求のデッドラインが違反する(Ｓ５０)。
ライト要求のデッドラインのリコールは、ライト要求が
満杯になる時刻に基づき演算される。その結果、ライト
要求は、その違反したデッドラインを持つ余裕がなく、
この結果、バッファがオーバーフローし、ライト要求の
喪失が起こり得る。Ｗnnページを喪失することはできな
いので(定義により)、プロセスは、新しいライト要求を
そのデッドラインを違反させることなくスケジュールし
なしてはならない。これは以下のようにして達成され
る。
【００３８】そのプロセスは、新しいライト要求をキュ
ー３２の先頭に設ける(Ｓ６２)。デッドラインが違反す
るようになったリード要求は、喪失したとみなされる
が、デッドラインが違反するようになったライト要求は
(Ｓ６４)、ケース３として扱われる、つまり、新しいラ
イト要求に沿ってキュー３２の先頭に移動される。ケー
ス３およびケース４の双方で、キュー３２の先頭に移動
したライト要求は、スキャン順に自身の間で順位が決め
られる。絶対デッドラインがリードおよびライト要求の
双方に格納されるため、新しい要求の挿入時、スキャン
順において新しい要求以前の各要求のデッドラインはア
ップデートされる必要はないことに注目。
【００３９】ライト要求Ｗnnの処理 上述のすべてのケースにおいて、ライトページｐwが一
旦、ディスクキュー３２に挿入されると、そのライトペ
ージはディスク３０に物理的に書き込まれていることが
保証される。ディスク３０にページを書き込むことは、
フリーバッファスペースを生む(そのスペースはライト
ページで占有される)。それ故、一旦、ページがディス
ク３０に書き込まれると、ディスクキュー３２内のライ
トページのデッドラインだけでなく、ライトバッファプ
ール２８内のすべてのページのデッドラインを緩和する
ことができる。上述したように、可変値ｄ(ｔ)を全体的
に修正することにより、ライトバッファプール２８内の
ページのデッドラインが緩和される。
【００４０】同様に、ディスクキュー３２に対して、デ
ィスク３０へライトページを書き込むとき、次の手順を
適用する。現在の時刻をｔとする。 １．ディスクキュー３２をスキャンする。 ２．すべてのライト要求をキュー３２に位置させる。 ３．ディスクキュー３２内の各ライト要求ｐwに対して
優先順位ｄw(ｔ0)を付与する。(ｔ0は、ｄw(ｔ0)が修正
された最後の時刻) ｄw(ｔ0)←ｔ−ｔ0＋ｄw(ｔ0)＋１／λw このデッドラインの緩和に対する理由は、システム全体
の要求を減じるためであり、それ故、リードページの喪
失を減じるためである。
【００４１】リード要求Ｒdlの挿入および処理 リード要求Ｒdlの扱いは、本来のＳＣＡＮＲＴプロセス
にて何が実行されるのかに似る。新しいリード要求Ｒdl
がディスクキュー３２に到着したとき、図４のフローチ
ャートに示されるように、そのプロセスは、その要求を
正確なＳＣＡＮの順位に挿入する。最初、そのプロセス
は、その位置を、そのページのスキャン順に対応してキ
ュー３２内に位置させる(Ｓ７０)。その要求をその位置
に挿入する前に、プロセスは、キュー３２内のすべての
要求のデッドラインが違反していないかをチェックする
(Ｓ７２)。これは、ディスクキュー３２内に既に位置す
るリードおよびライト要求の双方に適用する。デッドラ
インが違反していなければ、新しいリード要求Ｒdlは、
そのスキャン順にディスクキュー３２内に挿入される。
もし、一つまたはよりおくのデッドラインが違反してい
るならば、新しいリード要求Ｒdlは、キュー３２内のそ
のスキャン位置に挿入されない。その代わりに、キュー
３２の終端に挿入するよう試みられる。この場合、も
し、新しいリード要求Ｒdlが市販していないと決定され
れば(Ｓ７６)、キュー３２の終端に挿入される(Ｓ７
８)。そうでなければ、リード要求は、喪失したとみな
され、そして、システムによって処理されない(Ｓ８
０)。
【００４２】ここでの可能性のある１つの最適活用は、
デッドラインを侵害することなしにディスクキュー３２
の末尾に位置を替えることができるキュー３２のライト
要求を検索をすることである。リード要求が、デッドラ
インに至っているリード要求のスキャンオーダー中の新
しいリード要求に適応する場合のみ、リード要求のこう
いった位置替えが、実行される。現在、ライト要求のデ
ッドラインを概算する第２の方法は、上述された方法の
処理を表にするディスクの実行を発達させるものとして
発表されている。
【００４３】以下の記載を目的として、ディスクキュー
３２はＤで示され、キュー３２の位置ｉでの要求（リー
ド又はライト）はＤ［i］で示され、さらにキュー３２
の先頭の要求はＤ［0]で示される。ライト要求Ｗnが位
置ｎでのディスクキュー３２に挿入されている、即ちＤ
［ｎ］＝Ｗnを仮定する。ディスクキュー３２の位置０
〜ｎ−１の数量は、ＮｕｍＷｒｉｔｅｓ（ｎ−１）で示
される。ＮｕｍＷｒｉｔｅｓ（ｎ−１）は、ディスクキ
ュー３２のＷnの前のライト要求の数量を示していて、
Ｗnが表に書き込まれるのに先行する（システムによっ
て命令された際のデッドラインの衝突が原因で、何回か
のライト要求の再編成が発生するまで）。
【００４４】１のライト要求の処理は、ページがディス
ク３０に書き込まれること、及びライトバッファープー
ル２８でいくらかのバッファー空間を開放することを含
んでいる。結果、例えばＷoであるライト要求がディス
クスケジュール処理で処理された場合、このことで１／
λwまでの全ての未決定のライト要求のデッドラインを
緩和する。我々はこの事実を利用して、ディスクキュー
３２にライト要求を挿入する時にライト要求のデッドラ
インをより優れて（より効率的に）予測する。ライト要
求Ｗｎが、ディスクキュー３２の位置ｎ、時間ｔで、デ
ィスクキュー３２に挿入されることを仮定する。Ｗnの
挿入に関して、我々は以下の方法でＷnのデッドライン
を計算する。 ｄ（ｔ）＝ｔ＋（ｎf（ｔ）＋ＮｕｍＷｒｉｔｅｒｓ
（ｎ−１））／λw
【００４５】これを本発明の第１の実施例で与えられた
Ｗnのデッドラインを計算する公式と比較する。新しい
公式はディスクキュー３２のＷnに先行するライト要求
の数量を考慮するものであり、ライト要求に関してより
現実的で、緩和されたデッドラインを提供する。このこ
とによって、ロストリード要求の数量の減少に関してシ
ステムの混雑が減少されることが望まれる。少ない要求
が原因で、このことが緩和されたデッドラインに関する
ライト要求に課せられる。ライト要求のデッドラインの
計算を変形したので、ディスクスケジュール処理の幾つ
かの密接な関係と変形が発生する。一度システムがライ
ト要求を処理すると（ディスク３０に物理的にページを
書き込むまで）、ライト要求のデッドラインをもはや更
新する必要はない。その結果、ライト要求を処理するま
で、さらなる更新処理は必要ない。他方、ライト要求が
位置づけられるごと又はシステムによって新しい位置に
再配置されるごと、例えばライト要求をキュー３２の先
頭に移動させた場合、ディスクキュー３２中のライト要
求のデッドラインは再調整を必要とする。
【００４６】Ｒnnリード要求の挿入と処理 リード要求のＲnnカテゴリーは、ビデオを編集する応用
例に役立つ。Ｒnnカテゴリーは以下の特性を有する。 １． Ｒnnにはリアルタイムデッドラインがない。この
ため、別の要求よりも長い遅延を提供することが可能に
なる。 ２． デッドラインが無いので、Ｒnnリード要求は無制
限に待機できない。将来いつか、Ｒnnリード要求は完了
されなくてはならない。 ３． システムロード等のおかげでＲnnはロストできな
い。システムロードにも関わらず、Ｒnnリード要求は、
時間的なある地点においてシステムによって完了させら
れなくてはならない。リードページは編集される候補で
あるから、ユーザーはそれらの全てを得るべきである、
即ち処理は、Ｒnnがリード時間中にロストしないことを
ユーザーに保証する。
【００４７】Ｗnnライト要求に関して、デッドラインの
不足のおかげでＷnnライト要求は、Ｒdlよりも低い優先
順位としてみなされる。同様にデッドラインの不足のお
かげで、Ｒnnリード要求は、Ｒdlリード要求よりも低い
優先順位を有するものとしてみなされる。しかしながら
ライト要求と比較して、Ｒnnリード要求はバッファー問
題がないので（書き込まれるページの空間がある限
り）、我々は、Ｒnnもまたライト要求よりも劣る優先順
位としてみなすことができる。従ってシステムは、表へ
の書き込み関してＲnnリード要求に最下位の優先順位を
与える。結果、システム中に未決定のＷnn又はＲdl要求
が無い場合のみ、Ｒnnリード要求はディスクキュー３２
に挿入される。
【００４８】処理を実行中、以下の断定が適用できる。 ∀ｔ∀ｐw：ｄｗ（ｆ）＝ｄ（ｆ） この断定は、以下のように言い直すことができる。先の
セクションで記載されたようにシステムによって実行さ
れた割り当てのデッドライン、及びそれらの維持が与え
られているので、処理実行中は常時、各ライトページの
デッドラインは、別の全ライトページのデッドラインに
等しい。ここで、上記断定が正しいと仮定すると、シス
テムの実行の影響を受けることなしに処理は有意に単純
化される。言い換えると、同じ数値を有するマルチプル
コピーのデッドラインを更新する代わりに、我々は１つ
のコピーのデッドラインのみを維持し、かつそのデッド
ラインを全てのライトページ要求に利用する。実際には
我々がディスクキューに存する全ライトページの包括的
な１つのデッドラインｄ（ｔ）のみを維持することを必
要とすることを上記断定は包含する。結果的にディスク
にページを書き込むまで、ｄ（ｔ）に限り更新される必
要があり、かつライトページのデッドラインを更新する
為にディスクキュー中のライトページを走査する必要は
ない。
【００４９】処理の実行中、以下の断定も適用される。 ∀ｔ≧ｔ0：ｄ（ｔ）＝ｔ0＋（Ｎw＋Ｎ
serviced（ｔ））／λw ｔ0は処理の実行を開始した時間であり、Ｎwはライトバ
ッファープール２８が適合することができるページの総
数量であり、さらにＮserviced（ｔ）は時間ｔ0から時
間ｔまででディスク３０によってサービスされた（書き
込まれた）ライトページの総数量である。時間ｔ0＝０
で処理が開始されたと仮定すると、 ∀ｔ≧０：ｄ（ｔ）＝（Ｎw＋Ｎserviced（ｔ））／λ
ｗ
【００５０】以上に詳述した新しいリード／ライトスケ
ジュール処理の重要な１つの長所は、デッドライン及び
リード要求とライト要求の配置に関してリード／ライト
スケジュール処理が、リード及びライト要求の両方を同
一の方法で可能な限り多くスキャンオーダーで処理する
ことである。ビデオサーバー環境でディスクリード要求
とライト要求とを同時に保持する処理が提供される。ラ
イト要求がビデオクリップ編集又は処理が許可されてい
る映画の結果である一方、リード要求は動画を見ること
の結果である。動画を見ることのリアルタイムの要求の
おかげで、リード要求がロストしたとみなされない場
合、リード要求は一定のデッドライン内で完了されなく
てはならない。ディスクに書き込まれるべきデータがメ
インメモリーバッファーに蓄えられるので、臨界リード
要求が処理されるまでライト要求が延期されることがで
きる。しかしながら、妥当な遅延で不確定な延期の可能
性なしに、ライト要求は処理されなくてはならない。こ
のことは、メインメモリーライトバッファーの制限され
た寸法である物理的拘束によるものである。新しい処理
はリード要求及びライト要求の両方をスケジュールし、
発表されているデッドラインに合致しないディスクリー
ドの数量を最小化し、さらに不確定な延長及びディスク
ライトケースの大きなバッファー寸法を除外する。
【００５１】
【発明の効果】以上の説明から明らかなように、本発明
によれば、ビデオ・オン・デマンド要求により同時にビ
デオオーサリング及び編集を処理できるように、ビデオ
サービスの機能拡張を意図したものである。この新たな
環境下では、或るユーザは既存のビデオストリーム（例
えば、映画）を要求する。ビデオストリームの観点から
は、ビデオ編集及びオーサリングがリード／ライトアプ
リケーションであるのに対して、ビデオ・オン・デマン
ドはリードオンリーアプリケーションであることが大き
な相違点である。この相違は、ビデオサーバに於けるプ
ロセス設計に強い影響を及ぼす。これらの諸目的は、ビ
デオサーバに於ける同時ディスクリード及びライト要求
をサポートすると共に、バッファプールに於ける有用な
スペース量に基づいてライト要求に対するデッドライン
を割り当てるステップと；リード要求と共通ディスクキ
ューに於ける前記要求を挿入するステップと；そして、
キューの先頭に来る前記リード及びライト要求を処理す
るステップを有する方法を提供することによりを達成出
来る。これらの諸目的は、ビデオサーバに於ける同時デ
ィスクリード及びライト要求をサポートすると共に、リ
ード及びライト要求を一次的に保存するメモリバッファ
プールと；メモリバッファプールからリード及びライト
要求を受け取る共通ディスクキューと；そして、リード
及びライト要求、少なくとも一つのディスクを有するフ
ァイルサーバ；ライト要求がデッドラインに割り当てら
れるディスクキューに於けるリード及びライト要求を挿
入する位置を決定する制御手段を有するビデオサーバア
ーキテクチャを提供することによりを達成出来る。
【００５２】本発明の更なる適用範囲は、以下の記述よ
り明らかになる。しかしながら、詳細な記述及び具体的
な事例は発明の好ましい実施例を示す為であって、本技
術の熟練したものであれば、そのような記述や事例から
本発明の思想及び範囲に属する様々な変形や改良を読み
とれることは明白である。このように本発明は記載され
ていて、同一のものが多くの方法で変形されてもよいこ
とは明白である。こういった変形物は、本発明の分野と
意図から離れたものとみなされず、当業者にとって明ら
かな全ての変形は、以下の請求項の分野に含まれる。
【図面の簡単な説明】
【図１】 本発明に関連して用いられるビデオサーバの
アーキテクチャをの模式図である。
【図２】 本発明に係るリード及びライト要求のデータ
フロー図である。
【図３】 本発明の原理に基づいてライト要求をディス
クキューに挿入する位置の決定に用いられるプロセスを
説明するフローチャートである。
【図４】 本発明の原理に基づいてＲｄｌタイプのライ
ト要求をディスクキューに挿入する位置の決定に用いら
れるプロセスを説明するフローチャートである。
【図５】 （Ａ）及び（Ｂ）で併せて、発明に用いられ
る技術を俯瞰するブロック図である。
フロントページの続き (72)発明者 ラファエル・アロンソ アメリカ合衆国08512ニュージャージー州 クランベリー、ブレントウッド・レイン９ 番

Claims (18)

    【特許請求の範囲】
  1. 【請求項１】 ビデオサーバーでディスクリード要求と
    ディスクライト要求を同時に保持する方法であって、 バッファープールの利用可能な空間の総量に基づく上記
    ライト要求にデッドラインを割り当て、 共通のディスクキューに上記リード要求とライト要求と
    を挿入し、 上記キューの先頭に来る上記リード要求と上記ライト要
    求を処理するもの。
  2. 【請求項２】 共通のディスクキューに上記リード要求
    及び上記ライト要求を挿入する上記ステップが、スキャ
    ンオーダーに上記ライト要求が従う位置を決定し、スキ
    ャンオーダーに上記ライト要求を挿入することで別のデ
    ッドラインが侵害されるかどうかを決定し、侵害されな
    い場合、上記ライト要求をスキャンオーダーに上記ディ
    スクキューに挿入するステップをさらに含んでいる請求
    項１記載の方法。
  3. 【請求項３】 共通のディスクキューに上記リード要求
    及び上記ライト要求を挿入する上記ステップが、新ライ
    ト要求がスキャンオーダーに挿入されることで、上記ラ
    イト要求のデッドラインが侵害されるかどうかを決定
    し、侵害される場合、上記キューの先頭に上記新しいラ
    イト要求を位置づけるステップをさらに含んでいる請求
    項２記載の方法。
  4. 【請求項４】 別のライト要求のデッドラインが侵害さ
    れたかどうかを決定し、別のライト要求のデッドライン
    が侵害されている場合、侵害されたデッドラインを有す
    る上記ライト要求をスキャンオーダーの上記キューの先
    頭に移動させるステップをさらに含んでいる請求項３記
    載の方法。
  5. 【請求項５】 スキャンオーダーに上記新ライト要求を
    挿入することで、別のリード要求が侵害されるかどうか
    を決定し、侵害された場合、上記キューの終端部に上記
    新ライト要求を挿入させることで、上記新ライト要求の
    デッドラインが侵害されるかどうかを決定し、侵害され
    ない場合、上記キューの終端部に上記新ライト要求を挿
    入するステップをさらに含んでいる請求項３記載の方
    法。
  6. 【請求項６】 上記新ライト要求のデッドラインを侵害
    せずに、上記新ライトを上記キューの終端部に挿入する
    ことができないと決定した場合、スキャンオーダーに上
    記新ライト要求を挿入することで、別のライト要求のデ
    ッドラインが侵害されるかどうかを決定し、侵害されな
    い場合、上記新ライト要求がスキャンオーダーに挿入さ
    れる請求項５記載の方法。
  7. 【請求項７】 スキャンオーダーに上記新ライト要求を
    挿入することで、別のライト要求のデッドラインが侵害
    するとを決定された場合、侵害されたデッドラインを有
    する全ライト要求が、スキャンオーダーの上記キューの
    先頭に移動する請求項６記載の方法。
  8. 【請求項８】 共通のディスクのキューに上記リード要
    求と上記ライト要求とを挿入するステップは、スキャン
    オーダーに新リード要求を挿入することで、上記キュー
    のリード要求又はライト要求のデッドラインが侵害され
    るかどうかを決定し、侵害されない場合、上記スキャン
    オーダーに上記新リード要求を挿入するステップをさら
    に含んでいる請求項１記載の方法。
  9. 【請求項９】 共通のディスクのキューに上記リード要
    求と上記ライト要求とを挿入するステップは、スキャン
    オーダーに新リード要求を挿入することで、上記キュー
    のリード要求又はライト要求のデッドラインが侵害され
    るかどうかを決定し、侵害されている場合、上記新リー
    ド要求のデッドラインが侵害されているかどうか、上記
    新リード要求が上記キューの終端部に上記新リード要求
    が挿入されているかどうか決定し、挿入されていない場
    合、上記キューの終端部に上記リード要求を挿入するス
    テップをさらに含んでいる請求項１記載の方法。
  10. 【請求項１０】 上記ライト要求にデッドラインを割り
    当てる上記ステップは、バッファープールのフリーブッ
    ファースロットの数量、及び上記システムのディスクラ
    イト要求の到着比率の関数として上記デッドラインを計
    算するステップを含んでいる請求項１記載の方法。
  11. 【請求項１１】 ディスクリード要求とディスクライト
    要求を同時に保持するビデオサーバー構成であって、 メモリーバッファープールであって、上記リード要求及
    び上記ライト要求が一時的に貯蔵されるもの、 共通のディスクキューであって、上記メモリーバッファ
    ーからの上記リード要求及び上記ライト要求が受け入ら
    れるもの、 上記リード要求とライト要求を処理するファイルサーバ
    ーであって、すくなくともディスクを１つ保持するも
    の、 上記ディスクキューに上記リード要求及びライト要求を
    挿入する位置を決定するコントロール手段であって、上
    記ライト要求が割り当てられたデッドラインであるもの
    を含んでいるもの。
  12. 【請求項１２】 新ライト要求がスキャンオーダーにゆ
    だねられる位置を決定することを含んでいる処理に従っ
    て、上記リード要求及び上記ライト要求が上記キューに
    挿入される請求項１１記載のビデオサーバー。
  13. 【請求項１３】 さらに上記処理が、スキャンオーダー
    に上記新しいライト要求を挿入することでデッドライン
    が侵害されたかどうかを決定し、侵害されていない場
    合、スキャンオーダーに上記新ライト要求を挿入する請
    求項１２記載のビデオサーバー。
  14. 【請求項１４】 さらに上記処理は、上記新ライト要求
    がスキャンオーダーに挿入されている場合、上記新ライ
    ト要求のデッドラインが侵害されているかどうかを決定
    し、侵害されている場合、上記新ライト要求を上記ディ
    スクキューの先頭に挿入する請求項１３記載のビデオサ
    ーバー。
  15. 【請求項１５】 さらに上記処理は、上記ディスクキュ
    ーの先頭に上記新ライト要求が挿入されることで、別の
    ライト要求のデッドラインが侵害されたかどうかを決定
    して、侵されている場合、侵害されているデッドライン
    を有する上記ライト要求が、スキャンオーダーの上記キ
    ューの先頭に移動される請求項１４記載のビデオサーバ
    ー。
  16. 【請求項１６】 さらに上記処理は、上記新ライト要求
    がスキャンオーダーで挿入されている場合に、上記新ラ
    イト要求のデッドラインが侵害されているかどうかを決
    定し、侵害されていない場合で、上記新ライト要求がス
    キャンオーダーに挿入された場合、リード要求のデッド
    ラインが侵害されたかどうかを決定し、侵害されている
    場合は、上記新ライト要求のデッドラインを侵害するこ
    となしに、上記新ライト要求がディスクキューの終端部
    に挿入することが可能かどうかを決定し、可能である場
    合、上記ライト要求が上記ディスクキューの終端部に挿
    入される請求項１５記載のビデオサーバー。
  17. 【請求項１７】 上記処理は、上記新ライト要求がスキ
    ャンオーダーに挿入されている場合に、上記ライト要求
    のデッドラインが侵害されているかどうかを決定し、デ
    ッドラインが侵害されている場合、侵害されているデッ
    ドラインを有する全ライト要求を上記ディスクキューの
    先頭に移動させる請求項１２記載のビデオサーバー。
  18. 【請求項１８】 上記コントロール手段が、各々の上記
    ライト要求にデッドラインを、上記メモリーバッファー
    プールのフリーバッファースロットの数量とシステムの
    ディスクライト要求の到達比率との関数として割り当て
    る請求項１２記載のビデオサーバー。
JP25531997A 1996-09-20 1997-09-19 同時リード−ライト要求用ビデオサーバスケジューリング Expired - Fee Related JP3372842B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/718279 1996-09-20
US08/718,279 US6263411B1 (en) 1996-09-20 1996-09-20 Video server scheduling for simultaneous read-write requests

Publications (2)

Publication Number Publication Date
JPH10162507A true JPH10162507A (ja) 1998-06-19
JP3372842B2 JP3372842B2 (ja) 2003-02-04

Family

ID=24885507

Family Applications (1)

Application Number Title Priority Date Filing Date
JP25531997A Expired - Fee Related JP3372842B2 (ja) 1996-09-20 1997-09-19 同時リード−ライト要求用ビデオサーバスケジューリング

Country Status (2)

Country Link
US (1) US6263411B1 (ja)
JP (1) JP3372842B2 (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6678227B1 (en) 1998-10-06 2004-01-13 Matsushita Electric Industrial Co., Ltd. Simultaneous recording and reproduction apparatus and simultaneous multi-channel reproduction apparatus
EP1152342A4 (en) * 1999-01-12 2006-09-06 Fujitsu Ltd ACCESS CONTROL DEVICE AND METHOD FOR SUPPORTING ACCESS TO RECORDING MEDIUM
JP2009187584A (ja) * 2009-05-25 2009-08-20 Fujitsu Ltd コピー制御装置および方法

Families Citing this family (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6721794B2 (en) * 1999-04-01 2004-04-13 Diva Systems Corp. Method of data management for efficiently storing and retrieving data to respond to user access requests
US6609149B1 (en) * 1999-04-12 2003-08-19 International Business Machines Corporation Method and apparatus for prioritizing video frame retrieval in a shared disk cluster
JP2001134495A (ja) * 1999-11-05 2001-05-18 Sony Corp マルチメディア情報の読み出し方法、マルチメディア情報の読み出し装置、記憶媒体ドライブ装置、伝送媒体、情報ストリーム、電子機器
US6496899B1 (en) * 2000-02-28 2002-12-17 Sun Microsystems, Inc. Disk scheduling system with bounded request reordering
US6937814B1 (en) * 2000-04-14 2005-08-30 Realnetworks, Inc. System and method for play while recording processing
US20020019843A1 (en) * 2000-04-26 2002-02-14 Killian Robert T. Multiprocessor object control
US20030084261A1 (en) * 2001-10-29 2003-05-01 Byrd James M. Method for reordering commands to a storage device
US7127534B2 (en) * 2003-06-27 2006-10-24 Emulex Design & Manufacturing Corporation Read/write command buffer pool resource management using read-path prediction of future resources
US20050262526A1 (en) * 2004-04-16 2005-11-24 Grzegorz Lindenberg Interactive television channel
US20090043922A1 (en) * 2005-11-04 2009-02-12 David Aaron Crowther Method and Apparatus for Managing Media Storage Devices
US9158466B1 (en) 2007-06-29 2015-10-13 Emc Corporation Power-saving mechanisms for a dynamic mirror service policy
US7882373B1 (en) * 2007-06-29 2011-02-01 Emc Corporation System and method of reducing power consumption in a storage system through shortening of seek distances
US8060759B1 (en) 2007-06-29 2011-11-15 Emc Corporation System and method of managing and optimizing power consumption in a storage system
US8554941B2 (en) * 2007-08-30 2013-10-08 At&T Intellectual Property I, Lp Systems and methods for distributing video on demand
KR100927190B1 (ko) * 2007-10-12 2009-11-18 한국전자통신연구원 디스크 스케줄링 방법 및 장치
US20090328115A1 (en) * 2008-06-27 2009-12-31 At&T Delaware Intellectual Property, Inc. Systems and Methods for Distributing Digital Content
US8706900B2 (en) * 2008-07-10 2014-04-22 Juniper Networks, Inc. Dynamic storage resources
US9170928B1 (en) * 2013-12-31 2015-10-27 Symantec Corporation I/O scheduling and load balancing across the multiple nodes of a clustered environment
JP2016024835A (ja) * 2014-07-18 2016-02-08 ソニー株式会社 情報処理装置と情報処理方法およびプログラム
GB2540809B (en) * 2015-07-29 2017-12-13 Advanced Risc Mach Ltd Task scheduling
TWI554950B (zh) * 2015-12-17 2016-10-21 英業達股份有限公司 Ｆｒｕ的讀取／寫入方法及讀／寫系統

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07239756A (ja) * 1994-02-28 1995-09-12 Nippon Telegr & Teleph Corp <Ntt> 入出力スケジューリング方法及び入出力スケジューリングシステム
JPH0870446A (ja) * 1994-08-08 1996-03-12 Internatl Business Mach Corp <Ibm> ビデオ視聴者リクェストのスケジュール方法及びスケジューラ
JPH0871752A (ja) * 1994-08-31 1996-03-19 Suzuki Motor Corp 巻きパイプ及びこれの溶接位置の検査装置
JPH0950667A (ja) * 1995-07-31 1997-02-18 Hewlett Packard Co <Hp> ディスク・ドライブを制御する方法
JPH09106327A (ja) * 1995-10-11 1997-04-22 Oki Techno Syst Lab:Kk データ転送スケジューリング方法
US5644786A (en) * 1990-11-08 1997-07-01 At&T Global Information Solutions Company Method for scheduling the execution of disk I/O operations
JPH09258914A (ja) * 1996-03-27 1997-10-03 Hitachi Ltd コンピュータシステムのデータ転送方式

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3255908B2 (ja) * 1988-06-30 2002-02-12 エルジー・セミコン・カンパニー・リミテッド メモリー制御ユニット
JPH07200386A (ja) * 1993-12-28 1995-08-04 Toshiba Corp 共有メモリのアクセス制御装置および画像形成装置
US5541912A (en) * 1994-10-04 1996-07-30 At&T Corp. Dynamic queue length thresholds in a shared memory ATM switch
US5524235A (en) * 1994-10-14 1996-06-04 Compaq Computer Corporation System for arbitrating access to memory with dynamic priority assignment
US5737547A (en) * 1995-06-07 1998-04-07 Microunity Systems Engineering, Inc. System for placing entries of an outstanding processor request into a free pool after the request is accepted by a corresponding peripheral device

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5644786A (en) * 1990-11-08 1997-07-01 At&T Global Information Solutions Company Method for scheduling the execution of disk I/O operations
JPH07239756A (ja) * 1994-02-28 1995-09-12 Nippon Telegr & Teleph Corp <Ntt> 入出力スケジューリング方法及び入出力スケジューリングシステム
JPH0870446A (ja) * 1994-08-08 1996-03-12 Internatl Business Mach Corp <Ibm> ビデオ視聴者リクェストのスケジュール方法及びスケジューラ
JPH0871752A (ja) * 1994-08-31 1996-03-19 Suzuki Motor Corp 巻きパイプ及びこれの溶接位置の検査装置
JPH0950667A (ja) * 1995-07-31 1997-02-18 Hewlett Packard Co <Hp> ディスク・ドライブを制御する方法
JPH09106327A (ja) * 1995-10-11 1997-04-22 Oki Techno Syst Lab:Kk データ転送スケジューリング方法
JPH09258914A (ja) * 1996-03-27 1997-10-03 Hitachi Ltd コンピュータシステムのデータ転送方式

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6678227B1 (en) 1998-10-06 2004-01-13 Matsushita Electric Industrial Co., Ltd. Simultaneous recording and reproduction apparatus and simultaneous multi-channel reproduction apparatus
US7095688B2 (en) 1998-10-06 2006-08-22 Matsushita Electric Industrial Co Ltd Simultaneous recording and reproduction apparatus and simultaneous multi-channel reproduction apparatus
EP1152342A4 (en) * 1999-01-12 2006-09-06 Fujitsu Ltd ACCESS CONTROL DEVICE AND METHOD FOR SUPPORTING ACCESS TO RECORDING MEDIUM
JP2009187584A (ja) * 2009-05-25 2009-08-20 Fujitsu Ltd コピー制御装置および方法

Also Published As

Publication number Publication date
JP3372842B2 (ja) 2003-02-04
US6263411B1 (en) 2001-07-17

Similar Documents

Publication Publication Date Title
JP3372842B2 (ja) 同時リード−ライト要求用ビデオサーバスケジューリング
US6023720A (en) Simultaneous processing of read and write requests using optimized storage partitions for read and write request deadlines
Yu et al. Grouped sweeping scheduling for DASD-based multimedia storage management
US6871011B1 (en) Providing quality of service for disks I/O sub-system with simultaneous deadlines and priority
US5928327A (en) System and process for delivering digital data on demand
Lougher et al. The design of a storage server for continuous media
JP3617089B2 (ja) 映像蓄積配送装置及び映像蓄積配送システム
JP2742390B2 (ja) ビデオ・システムにおけるポーズ・レジュームをサポートする方法およびシステム
US5956321A (en) Stream scheduling system for real time stream server
US5721956A (en) Method and apparatus for selective buffering of pages to provide continuous media data to multiple users
JP2601993B2 (ja) ファイル提供方法及び装置
US5708796A (en) Method of retrieving continuous and non-continuous media data from a file system
US6496899B1 (en) Disk scheduling system with bounded request reordering
US6609149B1 (en) Method and apparatus for prioritizing video frame retrieval in a shared disk cluster
JPH11119923A (ja) データアクセス制御装置及びデータアクセス制御プログラムを記録した媒体
JPH0855137A (ja) メモリバッファ管理方法及びシステム
US7739421B1 (en) Buffer management method and system with data displayed directly from buffers
EP1357747A2 (en) Prioritized content recording and storage management
JP3575862B2 (ja) ストリームスケジューリング方法及び装置
Aref et al. Disk scheduling in video editing systems
US6678469B1 (en) Recorded information reproducing apparatus
JPH0981455A (ja) クライアント装置、サーバ装置及び記憶装置制御方法
Santos et al. Scheduling heterogeneous multimedia servers: different QoS for hard, soft and non real-time clients
Ng et al. Analysis on disk scheduling for special user functions
Rangan Architectures and algorithms for digital multimedia on-demand servers

Legal Events

Date Code Title Description
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20071122

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081122

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091122

Year of fee payment: 7

LAPS Cancellation because of no payment of annual fees