【事件の表示】
　特許第２９４１７６５号「優先順位付けされた記憶媒体リクエストのリアルタイムスケジューリング装置及びその方法とリアルタイムスケジューリングシステム」の請求項１乃至１４に係る特許に対する特許異議の申立てについて、次のとおり決定する。
【結　論】
　訂正を認める。
　特許第２９４１７６５号の請求項１乃至１２に係る特許を維持する。
【理　由】
Ａ　手続きの経緯
　本件特許第２９４１７６５号発明（以下「本件特許発明」という）は，平成１０年２月１２日に特許出願され，該出願と同時に１９９７年（平成９年）２月１１日に米国になした特許出願に基づいてパリ条約第４条の規定により優先権を主張され，平成１１年６月１８日にその特許の設定登録がなされたものであり，その後，平成１２年２月２９日に日本電気株式会社より特許異議の申立てがなされ，平成１２年５月１０日に取消理由通知がなされ，平成１２年７月２５日に訂正請求がなされたものである。
Ｂ　訂正の適否
１　訂正の要旨
　前記訂正の要旨は，本件特許発明の明細書を訂正請求書に添付された訂正明細書の通り，すなわち下記の通り訂正することを求めるものである。
　　　　　　　　　　　　　　　　　記
訂正事項１
　本件特許明細書の発明の名称の欄の「優先順位付けされたディスクリクエストのリアルタイムスケジューリング」を，
　「優先順位付けされた記憶媒体リクエストのリアルタイムスケジューリング装置及びその方法とリアルタイムスケジューリングシステム」と訂正する。
訂正事項２
　本件特許明細書の特許請求の範囲の欄の請求項１の「【請求項１】　記憶媒体の利用度を最大にするための記憶媒体スケジューラであって，単一スケジューリング待ち行列と，優先度，および前記待ち行列によって保持されたデッドラインを有する複数のリクエストと，前記記憶媒体の利用度が最大となるように，スキャン順番，前記優先度，およびデッドラインに基づく前記複数のリクエストの実行順番を計画するプロセッサと，を備え，該プロセッサは，スキャン順番に従い新しいリクエストをスケジューリング待ち行列に挿入し，いずれかのリクエストについてデッドラインを超えるものがあれば，優先度の低いリクエストを待ち行列の最後に配置することを特徴とする記憶媒体スケジューラ。」を，
　「【請求項１】　それぞれ優先度およびデッドラインを有する複数のリクエストをスケジューリングする記憶媒体スケジューリング装置であって，上記処理されるべき全てのリクエストを挿入して構成される単一の待ち行列を保持する待ち行列保持部と，シーク最適化スキャン順番と上記優先度およびデッドラインに基づいて上記複数のリクエストの実行順番を制御するプロセッサと，を備え，該プロセッサは，新しいリクエストが与えられると，上記最適化スキャン順番に従い，該新しいリクエストを上記待ち行列に挿入する手段と，上記新しいリクエストの挿入によってデッドラインが過ぎてしまうリクエストがある場合は，該デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と，上記識別されたリクエストのうち最下位優先度を有するリクエストを選択する手段と，上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段と，該選択された最下位優先度の最も余裕のあるデッドラインを有するリクエストを，上記待ち行列内で処理されるべき最後の位置に配置する手段とを有することを特徴とする記憶媒体スケジューリング装置。」と訂正する。
訂正事項３
　特許請求の範囲の欄の請求項２の「【請求項２】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の音声データを含む，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項２】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の音声データを含む，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項４
　特許請求の範囲の欄の請求項３の「【請求項３】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の映像データを含む，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項３】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の映像データを含む，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項５
　特許請求の範囲の欄の請求項４の「【請求項４】　前記優先度が，対顧客別サービス品質費用に基づく，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項４】　前記優先度が，対顧客別サービス品質費用に基づく，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項６
　特許請求の範囲の欄の請求項５の「【請求項５】　前記優先度が，記録媒体に記録されるデータの種類によって指示される，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項５】　前記優先度が，記録媒体に記録されるデータの種類によって指示される，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項７
　特許請求の範囲の欄の請求項６の「【請求項６】　前記記憶媒体が，磁気記憶ディスクである，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項６】　前記記憶媒体が，磁気記憶ディスクである，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項８
　特許請求の範囲の欄の請求項７の「【請求項７】　前記記憶媒体が，光記憶ディスクである，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項７】　前記記憶媒体が，光記憶ディスクである，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項９
　特許請求の範囲の欄の請求項８の「【請求項８】　前記記憶媒体が，磁気テープである，請求項１に記載の記憶媒体スケジューラ。」を，
　「【請求項８】　前記記憶媒体が，磁気テープである，請求項１に記載の記憶媒体スケジューリング装置。」と訂正する。
訂正事項１０
　特許請求の範囲の欄の請求項９の「【請求項９】　優先順位付けされたディスクリクエストによって指定された情報を含み，検索するにはアクセスアセンブリを移動しなければならない記憶媒体上のロケーションを指定する優先順位付けされたディスクリクエストをスケジュールするための，前記記憶媒体の利用度を最大にするリアルタイムシステムであって，前記優先順位付けされたディスクリクエストを保持するための単一待ち行列と，
前記優先順位付けされたリクエストのそれぞれに対して優先データ，デッドラインデータ，および記憶媒体ロケーションデータを有するメモリと，記録媒体ロケーションデータに従い新しいリクエストをスケジューリング待ち行列に挿入し，いずれかのリクエストについてデッドラインを超えるものがあれば，優先データの低いリクエストを待ち行列の最後に配置するプロセッサと，前記記録媒体の利用度が最大となるように，前記アクセスアセンブリに命令して，前記単一待ち行列によって指定された順に前記記録媒体から情報を検索する記憶媒体コントローラと，を備えたリアルタイムシステム。」を，
　「【請求項９】　記憶媒体上のシーク最適化ロケーションを指定し，優先順位付けされた複数のリクエストをリアルタイムスケジューリングするためのスケジューリングシステムであって，上記優先順位付けされた複数のリクエストを有する単一の待ち行列を保持する待ち行列保持部と，上記複数のリクエストのそれぞれに対して優先度データ，デッドラインデータ及び記憶媒体ロケーションデータを含むリクエスト関連データを保持するリクエスト関連データメモリ部と，上記リクエスト関連データに基づいて新しいリクエストを上記待ち行列に挿入し，順序付けを再構成するプロセッサと，上記再構成された待ち行列によって指定された順に上記記憶媒体から情報を検索するコントローラと，を備え，上記プロセッサは，上記新しいリクエストを上記待ち行列に挿入するときに，上記シーク最適化の記憶媒体ロケーションデータに従い，該新しいリクエストを上記待ち行列に挿入する手段と，上記新しいリクエストの挿入によってデッドラインが過ぎてしまうリクエストがある場合は，該デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と，上記識別されたリクエストのうち最下位優先度を有するリクエストを選択する手段と，上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段と，該選択された最下位優先度の最も余裕のあるデッドラインを有するリクエストを，上記待ち行列内で処理されるべき最後の位置に配置する手段とを有することを特徴とするリアルタイムスケジューリングシステム。」と訂正する。
訂正事項１１
　特許請求の範囲の欄の請求項１０の「【請求項１０】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされるかどうかを判定するために前記単一待ち行列を試験する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムシステム。」を，
　「【請求項１０】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされるかどうかを判定するために前記単一待ち行列を試験する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムスケジューリングシステム。」と訂正する。
訂正事項１２
　特許請求の範囲の欄の請求項１１の「【請求項１１】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされない場合には前記単一待ち行列を再構成する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムシステム。」を，
　「【請求項１１】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされない場合には前記単一待ち行列を再構成する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムスケジューリングシステム。」と訂正する。
訂正事項１３
　特許請求の範囲の欄の請求項１２及び１３を削除する。
訂正事項１４
　特許請求の範囲の欄の請求項１４の「【請求項１４】　前記プロセッサは，処理される前記単一待ち行列の最後の位置に配置された最下位優先度を有する前記優先順位付けされたリクエストに対しデッドラインを判定し，デッドラインを過ぎてしまうと判定された場合に，前記単一待ち行列から排除される，請求項１２に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムシステム。」を，
　「【請求項１２】　前記プロセッサは，処理される前記単一待ち行列の最後の位置に配置された最下位優先度を有する前記優先順位付けされたリクエストに対しデッドラインを判定し，デッドラインを過ぎてしまうと判定された場合に，前記単一待ち行列から排除される，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムスケジューリングシステム。」と訂正する。
訂正事項１５
　特許請求の範囲の欄の請求項１５の「【請求項１５】　優先度およびデッドラインを有する記憶媒体リクエストの実行をスケジュールするための方法であって，（ａ）スキャン順番に基づいて複数のリクエストを構成するステップと，（ｂ）前記スキャン順番で配置された新リクエストを含む前記複数のリクエストの新構成を作成するステップと，（ｃ）前記新構成内に含まれたデッドラインが過ぎてしまうリクエストを識別するステップと，（ｄ）前記デッドラインリクエストの前に実行され，最下位優先度を有するこれらのリクエストを含む前記新構成の部分集合を生成するステップと，（ｅ）前記新構成部分集合から最も緩いデッドラインを有するリクエストを識別するステップと，（ｆ）最も緩いデッドラインを有する前記リクエストが，最後に実行されるように前記新構成の最後に前記リクエストを配置するステップと，を含む記憶媒体リクエストの実行をスケジュールするための方法。」を，　「【請求項１３】　優先度およびデッドラインを有する記憶媒体リクエストの実行をスケジュールするための方法であって，（ａ）スキャン順番に基づいて複数のリクエストを構成するステップと，（ｂ）前記スキャン順番で配置された新リクエストを含む前記複数のリクエストの新構成を作成するステップと，（ｃ）前記新構成内に含まれたデッドラインが過ぎてしまうリクエストを識別するステップと，（ｄ）前記デッドラインリクエストの前に実行され，最下位優先度を有するこれらのリクエストを含む前記新構成の部分集合を生成するステップと，（ｅ）前記新構成部分集合から最も緩いデッドラインを有するリクエストを識別するステップと，（ｆ）最も緩いデッドラインを有する前記リクエストが，最後に実行されるように前記新構成の最後に前記リクエストを配置するステップと，を含む記憶媒体リクエストの実行をスケジュールするための方法。」と訂正する。
訂正事項１６
　特許請求の範囲の欄の請求項１６の「【請求項１６】　最も緩いデッドラインを有する前記リクエストが最後に実行されるとすれば，該リクエストの１デッドラインが満たされるかどうかを判断し，デッドラインを過ぎてしまうと判定される場合に，前記新構成から該リクエストを排除するステップをさらに含む，請求項１５に記載の記憶媒体リクエストの実行をスケジュールするための方法。」を，
　「【請求項１４】　最も緩いデッドラインを有する前記リクエストが最後に実行されるとすれば，該リクエストの１デッドラインが満たされるかどうかを判断し，デッドラインを過ぎてしまうと判定される場合に，前記新構成から該リクエストを排除するステップをさらに含む，請求項１３に記載の記憶媒体リクエストの実行をスケジュールするための方法。」と訂正する。
訂正事項１７
　発明の詳細な説明の欄の段落番号【００２５】の「図４は，本発明の実施形態のディスクスケジューリングシステム８０を示す。このシステムは，ディスク記憶システム８２，必要な命令を提供してディスク８８からデータを検索するための読取り／書込みアクセスヘッドを位置決めするディスクドライブコントローラ８４，処理されるべき多数の優先レベルのリクエストの全てを含む単一リクエスト待ち行列９０，およびリクエスト関連データ９４に基づいてリクエスト待ち行列９０の順番を制御するリクエストプロセッサ９２から成る。」を，
　「図４は，本発明の実施形態のディスクスケジューリングシステム８０を示す。このシステムは，ディスク記憶システム８２，必要な命令を提供してディスク８８からデータを検索するための読取り／書込みアクセスヘッドを位置決めするディスクドライブコントローラ８４，処理されるべき多数の優先レベルのリクエストの全てを含む単一リクエスト待ち行列９０を保持する待ち行列保持部，およびメモリ部９４に保持されたリクエスト関連データに基づいてリクエスト待ち行列９０の順番を制御するリクエストプロセッサ９２から成る。」と訂正する。
訂正事項１８
　発明の詳細な説明の欄の段落番号【００３０】の「ディスクスケジューリングシステムのこの方法をさらに理解するために，次の例が提示される。図６は，４つのリクエスト１４０，１４２，１４４，１４６，１４８，および新たに受け取られたリクエスト１５０を示す。図７に示されるように，これらのリクエストは，この例示では最適となり得る最も効率的なスキャン順番に基づいてリクエスト待ち行列内に配置される。」を，
　「ディスクスケジューリングシステムのこの方法をさらに理解するために，次の例が提示される。図６は，５つのリクエスト１４０，１４２，１４４，１４６，１４８，および新たに受け取られたリクエスト１５０を示す。図７に示されるように，これらのリクエストは，この例示では最適となり得る最も効率的なスキャン順番に基づいてリクエスト待ち行列内に配置される。」と訂正する。
訂正事項１９
　図面の図５を，明瞭でない記載の釈明を目的として，添付の訂正図面（図５）に示すように訂正する。
（ステップＳ１１５に枠線を付し，ステップＳ１１６に記載の「新リクエストの前に処理・・・」を明細書の段落【００２８】の記載内容に基づいて「デッドラインが過ぎてしまうリクエストの前に処理・・・」に訂正し，ステップＳ１２０に記載の「・・・リクエストが１つ以上存在・・・」を明細書の段落【００２８】の記載内容に基づいて「・・・リクエストが複数個存在・・・」に訂正する）
２　訂正の目的・範囲の適否と拡張・変更の存否
　前記訂正事項１〜訂正事項１９について検討する。
　前記訂正事項１は本件特許発明の内容を明瞭にするものであるから明瞭でない記載の釈明を目的とするものであり，前記訂正事項２〜訂正事項１２は特許請求の範囲の欄に上記下線で示した部分を追加するものであり且つ本件特許発明の構成を明瞭にするものであるから特許請求の範囲の減縮及び明瞭でない記載の釈明を目的とするものであり，前記訂正事項１３は特許請求の範囲の欄の請求項１２及び１３を削除するものであるから特許請求の範囲の減縮を目的とするものであり，前記訂正事項１４は本件特許発明の構成を明瞭にするものであるから明瞭でない記載の釈明を目的とするものであり，訂正事項１５及び１６は前記訂正事項１３による請求項の削除に伴うものであり，訂正事項１７は本件特許発明の実施例を明瞭にするものであるから明瞭でない記載の釈明を目的とするものであり，前記訂正事項１８は，誤記の訂正を目的とするものであり，訂正事項１９は本件特許発明の実施例を明瞭にするものであるから明瞭でない記載の釈明を目的とするものである。
　そして，前記各訂正は，願書に添付した明細書又は図面に記載した事項の範囲内であり，実質上特許請求の範囲を拡張し又は変更するものでない。
３　訂正の適否
　１，２を総合して判断すると，前記訂正請求は，特許法第１２０条の４第２項第１号乃至第３号に掲げる事項を目的とし，且つ同条第３項で準用する特許法第１２６条第２項及び第３項の規定に適合するので，当該訂正を認める。
Ｃ　特許異議の申立て
１　特許異議申立の理由の要旨
　本件特許発明は，甲第１号証（「日経エレクトロニクスＮo.621」（p171　1994.11.7））に記載された発明に基づいて，当業者が容易に発明をすることができたものであるから，特許法第２９条第２項の規定により特許を受けることができないものである。
２　本件特許発明
　本件各特許発明は，特許明細書及び図面の記載からみて，前記訂正請求で訂正された特許請求の範囲の欄の請求項１乃至請求項１２に記載された事項により特定される通りのものである。
３　甲１号証記載の発明
　甲第１号証には，デッドラインスケジューリングを優先させた，シーク最適化ケジューリングとデッドラインスケジューリングとを組み合わせて成るリアルタイムスケジューリング装置（方法，システム）が記載されている。
４　容易性の検討
　甲第１号証には，デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と，上記識別されたリクエストのうち最下位優先度を有するリクエストを選択する手段と，上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段を有することは記載されていない（要するに，優先度が低く且つ最も余裕のあるデッドラインを有するリクエストを選択することが記載されていない）し，その他本件特許発明の様な具体的解決手段も記載されていない。
　それらの具体的解決手段の記載無しに，本件請求項１乃至請求項１２記載の発明が，前記甲第１号証に記載された発明から当業者が容易に発明をすることができたということは出来ない。
　以上の通り，請求項１乃至請求項１２記載に係る発明は，特許異議申立人が提出した甲第１号証に記載された発明から当業者が容易に発明をすることができたものではない。
５　特許異議申立人の主張の検討
　平成１２年２月２９日付け特許異議申立書の４．申立ての理由の（４）ウ．に於ける主張について検討する。
ａ　特許異議申立人は，同書の第５頁第２８行〜第６頁第２行に於いて，要するに，本件発明と甲第１号証に記載の発明は，デッドラインスケジューリングとシーク最適化スケジューリングの何れを優先するかという相違でしかない旨主張する。
　しかし，本件各特許発明の要旨は，前述した様に，前記訂正請求で訂正された特許請求の範囲の欄の請求項１乃至請求項１２に記載された事項により特定される通りのものであり，デッドラインスケジューリングを具体化する前記２つの選択手段を初めとする具体的解決手段を有するものであるのに対して，甲第１号証には前記２つの選択手段を初めとする具体的解決手段が何も記載されていない。
　従って，特許異議申立人の「両者の相違はいずれを優先するかという相違でしかない」と言う主張は根拠に欠けるものである。
ｂ　特許異議申立人は，同書の第６頁第３行〜第７行に於いて，「本件発明はデッドラインスケジューリングの破綻をきたさないようにするために，そのデッドラインの遵守に障害となるリクエストのうち，優先度の低いものをリクエスト待ち行列の最後に配置することとしているが，優先度をパラメータとしてデータのスケジューリングを行うことは公知であり，当業者であれば当然に想到することであるのでこの部分をもってしても進歩性の欠如を免れ得ない」と主張する。
　しかし，特許異議申立人のこの主張はａで述べた主張を前提とするものであり，その前提が根拠に欠けるので，特許異議申立人のこの主張も根拠がない。
　また，本件特許発明は「優先度の低いもの」のみでなく「最も余裕のある」デッドラインを有するリクエストを選択しリクエスト待ち行列の最後に配置するのであるが，その様にすることについての容易性は証明していない。
　従って，特許異議申立人の前記主張も根拠がない。
ｃ　特許異議申立人は，同書の第６頁第８行〜第１３行に於いて，要するに，「以上に述べた構成要件以外の構成要件については」進歩性がない旨主張する。
　しかし，本件各特許発明の要旨は，前述した様に，前記訂正請求で訂正された特許請求の範囲の欄の請求項１乃至請求項１２に記載された事項により特定される通りのものであり，特許異議申立人が同書で言う「以上に述べた構成要件以外の構成要件について」審査で指摘しない構成要件が存在し，それが進歩性がないことも証明していない。
　従って，特許異議申立人の前記主張も根拠がない。
Ｄ　取消理由
１　前記取消理由の要旨は次の通りである。
　本件出願は，明細書の特許請求の範囲の欄の請求項１乃至請求項１４の記載に不備があり，また図面の記載と明細書の記載に相違があるため，本件特許発明の構成，効果が不明であるので，特許法第３６条第４項及び第６項に規定する要件を満たしていない。
２　取消理由の存否
　本件特許明細書及び図面は前記訂正請求により訂正され，その結果前記取消理由は解消した。
Ｅ　結び
　以上述べた通り，前記訂正請求はこれを認め，特許異議申立ての理由及び証拠並びに前記取消理由によっては請求項１乃至請求項１２記載に係る発明の特許を取り消すことはできず，他に本件特許を取り消すべき理由を発見しない。
　よって，結論のとおり決定する。
【異議決定日】
平成１２年１０月３０日（２０００．１０．３０）
【訂正の要旨】
訂正事項１
　本件特許明細書の発明の名称の欄の「優先順位付けされたディスクリクエストのリアルタイムスケジューリング」
　を，明瞭でない記載の釈明を目的として，
　「優先順位付けされた
記憶媒体
装置及びその方法とリアルタイムスケジューリングシステム
　と訂正する。
訂正事項２
　本件特許明細書の特許請求の範囲の欄の請求項１の「【請求項１】　記憶媒体の利用度を最大にするための記憶媒体スケジューラであって，
　単一スケジューリング待ち行列と，
　優先度，および前記待ち行列によって保持されたデッドラインを有する複数のリクエストと，
　前記記憶媒体の利用度が最大となるように，スキャン順番，前記優先度，およびデッドラインに基づく前記複数のリクエストの実行順番を計画するプロセッサと，を備え，
　該プロセッサは，スキャン順番に従い新しいリクエストをスケジューリング待ち行列に挿入し，いずれかのリクエストについてデッドラインを超えるものがあれば，優先度の低いリクエストを待ち行列の最後に配置することを特徴とする記憶媒体スケジューラ。」
　を，特許請求の範囲の減縮及び明瞭でない記載の釈明を目的として，
　「【請求項１】　
それぞれ優先度およびデッドラインを有する複数のリクエストをスケジューリングする
リング装置
　
上記処理されるべき全てのリクエストを挿入して構成される
の
を
する待ち行列保持部
　
シーク最適化
いて上
制御
　該プロセッサは，
新しいリクエストが与えられると，上記最適化
上記
する手段と
上記新しいリクエストの挿入によって
が過ぎてしまうリクエスト
る場合は
該デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と，上記識別されたリクエストのうち最下位
を有する
選択する手段と，上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段と，該選択された最下位優先度の最も余裕のあるデッドラインを有するリクエストを，上記
内で処理されるべき
の位置
手段とを有する
リング装置
　と訂正する。
訂正事項３
　特許請求の範囲の欄の請求項２の「【請求項２】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の音声データを含む，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項２】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の音声データを含む，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項４
　特許請求の範囲の欄の請求項３の「【請求項３】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の映像データを含む，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項３】　前記記憶媒体が，ビデオ・オン・ディマンドマルチメディア用途の映像データを含む，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項５
　特許請求の範囲の欄の請求項４の「【請求項４】　前記優先度が，対顧客別サービス品質費用に基づく，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項４】　前記優先度が，対顧客別サービス品質費用に基づく，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項６
　特許請求の範囲の欄の請求項５の「【請求項５】　前記優先度が，記録媒体に記録されるデータの種類によって指示される，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項５】　前記優先度が，記録媒体に記録されるデータの種類によって指示される，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項７
　特許請求の範囲の欄の請求項６の「【請求項６】　前記記憶媒体が，磁気記憶ディスクである，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項６】　前記記憶媒体が，磁気記憶ディスクである，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項８
　特許請求の範囲の欄の請求項７の「【請求項７】　前記記憶媒体が，光記憶ディスクである，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項７】　前記記憶媒体が，光記憶ディスクである，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項９
　特許請求の範囲の欄の請求項８の「【請求項８】　前記記憶媒体が，磁気テープである，請求項１に記載の記憶媒体スケジューラ。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項８】　前記記憶媒体が，磁気テープである，請求項１に記載の記憶媒体スケジュー
リング装置
　と訂正する。
訂正事項１０
　特許請求の範囲の欄の請求項９の「【請求項９】　優先順位付けされたディスクリクエストによって指定された情報を含み，検索するにはアクセスアセンブリを移動しなければならない記憶媒体上のロケーションを指定する優先順位付けされたディスクリクエストをスケジュールするための，前記記憶媒体の利用度を最大にするリアルタイムシステムであって，
　前記優先順位付けされたディスクリクエストを保持するための単一待ち行列と，前記優先順位付けされたリクエストのそれぞれに対して優先データ，デッドラインデータ，および記憶媒体ロケーションデータを有するメモリと，
　記録媒体ロケーションデータに従い新しいリクエストをスケジューリング待ち行列に挿入し，いずれかのリクエストについてデッドラインを超えるものがあれば，優先データの低いリクエストを待ち行列の最後に配置するプロセッサと，
　前記記録媒体の利用度が最大となるように，前記アクセスアセンブリに命令して，前記単一待ち行列によって指定された順に前記記録媒体から情報を検索する記憶媒体コントローラと，
を備えたリアルタイムシステム。」
　を，特許請求の範囲の減縮および明瞭でない記載の釈明を目的として，
　「【請求項９】　記憶媒体上の
シーク最適化
複数の
リアルタイム
スケジューリング
　上記優先順位付けされた
複数の
を有する単一の待ち行列を
保持部
　上記
複数の
度
を含むリクエスト関連データ
保持
リクエスト関連データ
部
　
上記リクエスト関連
に基づいて
上記待ち
順序付けを再構成
　
上記再構成された
を備え，
　上記プロセッサは，上記新しいリクエストを上記待ち行列に挿入するときに，上記シーク最適化の記憶媒体ロケーションデータに従い，該新しいリクエストを上記待ち行列に挿入する手段と，上記新しいリクエストの挿入によってデッドラインが過ぎてしまうリクエストがある場合は，該デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と，上記識別されたリクエストのうち最下位優先度を有するリクエストを選択する手段と，上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段と，該選択された最下位優先度の最も余裕のあるデッドラインを有するリクエストを，上記待ち行列内で処理されるべき最後の位置に配置する手段とを有することを特徴とする
スケジューリング
　と訂正する。
訂正事項１１
　特許請求の範囲の欄の請求項１０の「【請求項１０】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされるかどうかを判定するために前記単一待ち行列を試験する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムシステム。」
　を，明瞭でない記載の釈明を日的として，
　「【請求項１０】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされるかどうかを判定するために前記単一待ち行列を試験する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイム
スケジューリング
　と訂正する。
訂正事項１２
　特許請求の範囲の欄の請求項１１の「【請求項１１】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされない場合には前記単一待ち行列を再構成する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムシステム。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項１１】　前記プロセッサは，前記優先順位付けされたディスクリクエストのデッドラインが満たされない場合には前記単一待ち行列を再構成する，請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイム
スケジューリング
　と訂正する。
訂正事項１３
　特許請求の範囲の欄の請求項１２及び１３を削除する。
（請求項１２及び１３に記載された事項は何れも，請求項１及び９に追加された）
訂正事項１４
　特許請求の範囲の欄の請求項１４の「【請求項１４】　前記プロセッサは，処理される前記単一待ち行列の最後の位置に配置された最下位優先度を有する前記優先順位付けされたリクエストに対しデッドラインを判定し，デッドラインを過ぎてしまうと判定された場合に，前記単一待ち行列から排除される，請求項１２に記載の優先順番付けされたディスクリクエストをスケジューリングするための、リアルタイムシステム。」
　を，明瞭でない記載の釈明を目的として，
　　「【請求項１２】　前記プロセッサは，処理される前記単一待ち行列の最後の位置に配置された最下位優先度を有する前記優先順位付けされたリクエストに対しデッドラインを判定し，デッドラインを過ぎてしまうと判定された場合に，前記単一待ち行列から排除される，請求項
９
スケジューリング
　と訂正する。
訂正事項１５
　特許請求の範囲の欄の請求項１５の「【請求項１５】　優先度およびデッドラインを有する記憶媒体リクエストの実行をスケジュールするための方法であって，
　（ａ）スキャン順番に基づいて複数のリクエストを構成するステップと，
　（ｂ）前記スキャン順番で配置された新リクエストを含む前記複数のリクエストの新構成を作成するステップと，
　（ｃ）前記新構成内に含まれたデッドラインが過ぎてしまうリクエストを識別するステップと，
　（ｄ）前記デッドラインリクエストの前に実行され，最下位優先度を有するこれらのリクエストを含む前記新構成の部分集合を生成するステップと，
　（ｅ）前記新構成部分集合から最も緩いデッドラインを有するリクエストを識別するステップと，
　（ｆ）最も緩いデッドラインを有する前記リクエストが，最後に実行されるように前記新構成の最後に前記リクエストを配置するステップと，
を含む記憶媒体リクエストの実行をスケジュールするための方法。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項
１３
　（ａ）スキャン順番に基づいて複数のリクエストを構成するステップと，
　（ｂ）前記スキャン順番で配置された新リクエストを含む前記複数のリクエストの新構成を作成するステップと，
　（ｃ）前記新構成内に含まれたデッドラインが過ぎてしまうリクエストを識別するステップと，
　（ｄ）前記デッドラインリクエストの前に実行され，最下位優先度を有するこれらのリクエストを含む前記新構成の部分集合を生成するステップと，
　（ｅ）前記新構成部分集合から最も緩いデッドラインを有するリクエストを識別するステップと，
　（ｆ）最も緩いデッドラインを有する前記リクエストが，最後に実行されるように前記新構成の最後に前記リクエストを配置するステップと，
を含む記憶媒体リクエストの実行をスケジュールするための方法。」
　と訂正する。
訂正事項１６
　特許請求の範囲の欄の請求項１６の「【請求項１６】　最も緩いデッドラインを有する前記リクエストが最後に実行されるとすれば，該リクエストの１デッドラインが満たされるかどうかを判断し，デッドラインを過ぎてしまうと判定される場合に，前記新構成から該リクエストを排除するステップをさらに含む，請求項１５に記載の記憶媒体リクエストの実行をスケジュールするための方法。」
　を，明瞭でない記載の釈明を目的として，
　「【請求項
１４
１３
　と訂正する。
訂正事項１７
　発明の詳細な説明の欄の段落番号【００２５】の「図４は，本発明の実施形態のディスクスケジューリングシステム８０を示す。このシステムは，ディスク記憶システム８２，必要な命令を提供してディスク８８からデータを検索するための読取り／書込みアクセスヘッドを位置決めするディスクドライブコントローラ８４，処理されるべき多数の優先レベルのリクエストの全てを含む単一リクエスト待ち行列９０，およびリクエスト関連データ９４に基づいてリクエスト待ち行列９０の順番を制御するリクエストプロセッサ９２から成る。」
　を，特許請求の範囲の欄の請求項１および９の訂正に伴ない，明瞭でない記載の釈明を目的として，
　「図４は，本発明の実施形態のディスクスケジューリングシステム８０を示す。このシステムは，ディスク記憶システム８２，必要な命令を提供してディスク８８からデータを検索するための読取り／書込みアクセスヘッドを位置決めするディスクドライブコントローラ８４，処理されるべき多数の優先レベルのリクエストの全てを含む単一リクエスト待ち行列９０
を保持する待ち行列保持部
メモリ部９４に保持された
　と訂正する。
訂正事項１８
　発明の詳細な説明の欄の段落番号【００３０】の「ディスクスケジューリングシステムのこの方法をさらに理解するために，次の例が提示される。図６は，４つのリクエスト１４０，１４２，１４４，１４６，１４８，および新たに受け取られたリクエスト１５０を示す。図７に示されるように，これらのリクエストは，この例示では最適となり得る最も効率的なスキャン順番に基づいてリクエスト待ち行列内に配置される。」
　を，誤記の訂正を目的として，
　「ディスクスケジューリングシステムのこの方法をさらに理解するために，次の例が提示される。図６は，
５つ
　と訂正する。
訂正事項１９
　図面の図５を，明瞭でない記載の釈明を目的として，添付の訂正図面（図５）に示すように訂正する。
（ステップＳ１１５に枠線を付し，ステップＳ１１６に記載の「新リクエストの前に処理・・・」を明細書の段落【００２８】の記載内容に基づいて「
デッドラインが過ぎてしまう
複数個
（５４）【発明の名称】
優先順位付けされた記憶媒体リクエストのリアルタイムスケジューリング装置及びその方法とリアルタイムスケジューリングシステム
（５７）【特許請求の範囲】
　　【請求項１】　それぞれ優先度およびデッドラインを有する複数のリクエストをスケジューリングする記憶媒体スケジューリング装置であって、
　上記処理されるべき全てのリクエストを挿入して構成される単一の待ち行列を保持する待ち行列保持部と、
　シーク最適化スキャン順番と上記優先度およびデッドラインに基づいて上記複数のリクエストの実行順番を制御するプロセッサと、を備え、
　該プロセッサは、新しいリクエストが与えられると、上記最適化スキャン順番に従い、該新しいリクエストを上記待ち行列に挿入する手段と、上記新しいリクエストの挿入によってデッドラインが過ぎてしまうリクエストがある場合は、該デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と、上記識別されたリクエストのうち最下位優先度を有するリクエストを選択する手段と、上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段と、該選択された最下位優先度の最も余裕のあるデッドラインを有するリクエストを、上記待ち行列内で処理されるべき最後の位置に配置する手段とを有することを特徴とする記憶媒体スケジューリング装置。
　　【請求項２】　前記記憶媒体が、ビデオ・オン・ディマンドマルチメディア用途の音声データを含む、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項３】　前記記憶媒体が、ビデオ・オン・ディマンドマルチメディア用途の映像データを含む、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項４】　前記優先度が、対顧客別サービス品質費用に基づく、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項５】　前記優先度が、記録媒体に記録されるデータの種類によって指示される、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項６】　前記記憶媒体が、磁気記憶ディスクである、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項７】　前記記憶媒体が、光記憶ディスクである、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項８】　前記記憶媒体が、磁気テープである、請求項１に記載の記憶媒体スケジューリング装置。
　　【請求項９】　記憶媒体上のシーク最適化ロケーションを指定し、優先順位付けされた複数のリクエストをリアルタイムスケジューリングするためのスケジューリングシステムであって、
　上記優先順位付けされた複数のリクエストを有する単一の待ち行列を保持する待ち行列保持部と、
　上記複数のリクエストのそれぞれに対して優先度データ、デッドラインデータ及び記憶媒体ロケーションデータを含むリクエスト関連データを保持するリクエスト関連データメモリ部と、
　上記リクエスト関連データに基づいて新しいリクエストを上記待ち行列に挿入し、順序付けを再構成するプロセッサと、
　上記再構成された待ち行列によって指定された順に上記記憶媒体から情報を検索するコントローラと、を備え、
　上記プロセッサは、上記新しいリクエストを上記待ち行列に挿入するときに、上記シーク最適化の記憶媒体ロケーションデータに従い、該新しいリクエストを上記待ち行列に挿入する手段と、上記新しいリクエストの挿入によってデッドラインが過ぎてしまうリクエストがある場合は、該デッドラインが過ぎてしまうリクエストの前に処理されるべき全てのリクエストを識別する手段と、上記識別されたリクエストのうち最下位優先度を有するリクエストを選択する手段と、上記最下位優先度を有するリクエストのうち最も余裕のあるデッドラインを有するリクエストを選択する手段と、該選択された最下位優先度の最も余裕のあるデッドラインを有するリクエストを、上記待ち行列内で処理されるべき最後の位置に配置する手段とを有することを特徴とするリアルタイムスケジューリングシステム。
　　【請求項１０】　前記プロセッサは、前記優先順位付けされたディスクリクエストのデッドラインが満たされるかどうかを判定するために前記単一待ち行列を試験する、請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムスケジューリングシステム。
　　【請求項１１】　前記プロセッサは、前記優先順位付けされたディスクリクエストのデッドラインが満たされない場合には前記単一待ち行列を再構成する、請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムスケジューリングシステム。
　　【請求項１２】　前記プロセッサは、処理される前記単一待ち行列の最後の位置に配置された最下位優先度を有する前記優先順位付けされたリクエストに対しデッドラインを判定し、デッドラインを過ぎてしまうと判定された場合に、前記単一待ち行列から排除される、請求項９に記載の優先順番付けされたディスクリクエストをスケジューリングするためのリアルタイムスケジューリングシステム。
　　【請求項１３】　優先度およびデッドラインを有する記憶媒体リクエストの実行をスケジュールするための方法であって、
　　（ａ）スキャン順番に基づいて複数のリクエストを構成するステップと、
　　（ｂ）前記スキャン順番で配置された新リクエストを含む前記複数のリクエストの新構成を作成するステップと、
　　（ｃ）前記新構成内に含まれたデッドラインが過ぎてしまうリクエストを識別するステップと、
　　（ｄ）前記デッドラインリクエストの前に実行され、最下位優先度を有するこれらのリクエストを含む前記新構成の部分集合を生成するステップと、
　　（ｅ）前記新構成部分集合から最も緩いデッドラインを有するリクエストを識別するステップと、
　　（ｆ）最も緩いデッドラインを有する前記リクエストが最後に実行されるように前記新構成の最後に前記リクエストを配置するステップと、
を含む記憶媒体リクエストの実行をスケジュールするための方法。
　　【請求項１４】　最も緩いデッドラインを有する前記リクエストが最後に実行されるとすれば、該リクエストのデッドラインが満たされるかどうかを判断し、デッドラインを過ぎてしまうと判定される場合に、前記新構成から該リクエストを排除するステップをさらに含む、請求項１３に記載の記憶媒体リクエストの実行をスケジュールするための方法。
【発明の詳細な説明】
　　　【０００１】
　　【発明の属する技術分野】
　本発明は、一般に、本質的に機械的である記憶媒体のリソース管理に関する。さらに詳述すれば、本発明は、記憶媒体アクセスのために優先順位付けしたリクエストのリアルタイムスケジューリングのための装置および方法に関する。
　　　【０００２】
　　【従来の技術】
　記憶媒体リソース管理は、多くのデータ集約型用途では重要である。例えば、ディスクリソース管理は、マルチメディア用途では重要な要素である。ディスク技術は、速度および記憶容量が向上し続けるが、ディスク帯域幅は、このデータ集約型用途では限界のリソースのままである。ディスク技術は、現在デジタルで蓄積されたビデオ・オン・ディマンドを供給するために使用される。ディスク技術は、マルチメディアシステムでも使用される。これらのマルチメディア用途などでは、データリクエストは、典型的に厳密なデッドラインを有する。これらのデッドラインは、用途によって要求される。ビデオ・オン・ディマンドシステムは、分裂、または遅延が使用者の端末にジッタを生成するので、これらを起こすことなくビデオデータストリームを提供しなければならない。理想的には、記憶媒体アクセスシステムは、いかなるリクエストも失わずに、全てのリクエストを適宜に処理すべきである。実際には、高需要時には、幾つかのリクエストは要求された時間に処理され得ず、これらのリクエストは紛失として扱われる。好ましくは、この記憶媒体アクセスシステムは、より重要なリクエスト（例えば、より高い対価を支払うもの）がより低優先順位のリクエストを犠牲にして取り扱われるようにリクエストを優先順位付けすべきである。
　　　【０００３】
　例えば、Ｉ．Ｐ．Ｂフレーム列の形式で蓄積されたＭＰＥＧ符号化ビデオデータのブロックにおいて、Ｉデータブロックを紛失すると、Ｐ、またはＢデータブロックを紛失する場合と比べ、より多くのディスプレイフレームを紛失することとなる。ＰまたはＢフレームに比べ、Ｉフレームを優先するディスクスケジューリングアルゴリズムは、より良質なサービスが行われることとなる。
　　　【０００４】
　ハイエンドマルチメディア用途など、幾つかのデータ集約型用途では、価格付けシステムが、データリクエストを優先順位付けするために使用される。異なる優先順位が、それらに対応する費用に割り当てられ、データリクエストを処理するその費用は、提供されるサービスの品質に略正比例する。より高質のサービスを要求する使用者は、より多く課金されることになる。サービスの質は、ジッタ、紛失パケットなどについて数量化できる。サービスレベルについての異なる品質を履行する１つの方法は、使用者が加入している価格付けパッケージに基づいて、各使用者からのディスクリクエストを優先順位付けすることである。
　　　【０００５】
　サービス品質は、単なる価格付けに関するものよりも若干複雑なものとなる。これは、再生中のサービス品質についての使用者の知覚が、サービス材料の媒体および形式によってまちまちとなるからである。例えば、一方が音声ストリームを検索し、他方が映像ストリームを検索する二人の使用者を考えてみると、両方のデータストリームは、周期的にディスクアクセスリクエストを必要とする。これらのストリームが総当たり方式である場合、両ストリームに対するディスクリクエストは、同一のデッドラインで処理されなければならなくなる。ディスクアクセスシステムの負荷が十分に高い場合、ある時点で、それらのそれぞれのデッドライン内で全てのリクエストを履行するのが不可能となる。これは、遅延した（紛失した）リクエストとなる。音声データストリーム内での一瞬のギャップ（例えば、数百ミリ秒）でも、雑音、ジッタ信号として容易に知覚される。しかし映像データストリーム内のそれに匹敵するギャップは、意識さえされないであろう。これは、音声データのリクエストが映像データよりもより高い優先順位で処理されて、同程度に知覚される品質のサービスを配給する必要があることを意味する。
　　　【０００６】
　　【発明が解決しようとする課題】
　上記ケースの全てにおいて、デッドライン単独では、メディアアクセスのためのアプリケーション要件をモデル化するには不十分である。メディアアクセススケジューリングは、その用途に対するデータの相対的重要性の情報をもって行われなければならない。スキャン−ＥＤＦ、スキャン−ＲＴなどのリアルタイムディスクスケジューリングアルゴリズムは、全てのリクエストが同じ優先度を有すると仮定する。従来、多数の優先リクエストは次にように扱われてきた。個別の待ち行列が各優先レベルごとに維持される。より高い優先リクエストは、常により低い優先リクエストに優先する。より低い優先リクエストは、より高い優先リクエスト待ち行列が空である場合にのみ処理できる。これは、最上位優先リクエストに対して最適性能を達成するが、シークタイムの大域的最適化がないので、それは、通常、より低いディスク利用度（より低い効率）となる。より低い優先リクエストは、従来の個別待ち行列方式では不足する可能性もある。
　　　【０００７】
　　【課題を解決するための手段】
　本発明は、従来技術の欠点のない、多数の優先リクエストを扱う新メディアスケジューリング技術を提案する。本発明のこのメディアスケジューリングシステムは、優先度およびデッドラインだけでなく、ディスクの利用度および効率をも最適化するように努力する。厳密には、本システムは、優先度をより広い観点から見て、シークタイムの大域的最適化のための機構を提供する。このシークタイムは、読取りヘッドおよび記録媒体が要求されたデータ上に正しく位置決めされるのに要する時間である。既存の磁気ディスクアクセスシステムでは、そのシークタイムは、典型的に読取りヘッドが現在のトラックから要求されたトラックまで移動するのに要する時間である。テープアクセスシステムでは、そのシークタイムは、一般に、要求されたデータが読取りヘッドの下に来るポイントまでテープが前方、または後方に巻かれるのに要した時間である。
　　　【０００８】
　各優先レベル毎に個別の待ち行列を利用する従来の技術と異なり、本発明は、全てのリクエストがその中に挿入される単一の待ち行列を利用する。このシステムは、可能な限りスキャン順番でリクエストを処理することによってディスク利用度（効率）を増す。デッドラインを過ぎてしまうことなく、スキャン順番で全てのリクエストを処理することが不可能な場合、このシステムは、自動的に待ち行列の順番を再配置して、より高い優先度を有するリクエストを優先し、必要に応じて、より低い優先度のリクエストは落とす。
　　　【０００９】
　より厳密には、本システムは、優先度に関係なく、全てのブロックリクエストを保持するための単一待ち行列を維持する。新ブロックリクエストが作成されるとき、待ち行列の最後のスキャンサイクルで、スキャン順番に従ってその待ち行列内に挿入される。故に、この新リクエストは、より遠くのロケーションの途中にあっても読み取りヘッドによって処理されるように待ち行列内のロケーションに挿入される。本システムは、次にその待ち行列を検査して、提案されたスキャン順番によっていずれかのデッドラインが過ぎてしまうかどうかを判定する。過ぎてしまわない場合、本システムは、挿入ステップを終了して、リクエストが処理される順番をその待ち行列が指定できるようになる。他方、新リクエストの挿入のため、待ち行列内のどれかのリクエストのデッドラインが過ぎてしまう場合、本システムは、次にように再配置する。これは、挿入されたリクエストの前の全リクエストの中で最下位優先度を有するリクエストを見つけ、そのより低い優先リクエストを待ち行列の末尾に移動する。挿入されたリクエストの前に１つ以上の低優先候補がある場合、最も余裕のあるデッドラインを有する低優先リクエストが、待ち行列の末尾に移動される。そのように移動された最下位優先リクエストのデッドラインが過ぎてしまう場合、それは紛失と宣言され、待ち行列から排除される。上述の待ち行列再調整ステップは、待ち行列内に残留するリクエストの全てが、デッドラインを過ぎてしまうことなく扱うことができるようになるまで、必要に応じて、続く。
　　　【００１０】
　本発明、その目的、および利点をより完全に理解するために、次の詳細な説明および添付の図面が参照されても良い。
　　　【００１１】
　　【発明の実施の形態】
　実施形態の説明は、ディスク記憶媒体について行われるが、本発明にかかる装置および方法は、ディスク記憶システムに限定されるものではない。本発明は、順次にアクセスされる記憶媒体をすべて含むものである。
　　　【００１２】
　図１は、従来型ディスク記憶システム１８の２つの主構成要素を示し、図２は、図１の従来型ディスク記憶システム１８の側面図である。従来型ディスク記憶システム１８の第１の構成要素は、中心スピンドル２２に取り付けられた円形搭載板、またはディスク２０であり、第２の構成要素は、機械的アクセスアセンブリ、またはアーム２４であり、読取り／書込みヘッド２６を備え、ディスク２０が回転されている間、ディスク２０の表面を横切って移動することができる。この機械的アクセスアセンブリは、ディスクアームと呼ばれる。
　　　【００１３】
　一つの通常の構成では、ディスク２０は、その表面上に多数のトラックを有する。トラックは、ディスクアーム２６を移動させずに読みとることができるディスク２０表面の一部である。個々のトラックは、ディスクアームの位置に対応する一連の同心円を作る。１表面当たりのトラック数は、少数（例えば、３０トラック）から数千のトラックまでの範囲で、まちまちである。説明を簡単にするため、６トラック（２８，３０，３２，３４，３６，３８）しかディスク２０上に示されていない。トラック内に蓄積できるデータ量は、通常、コンピュータメモリから１回の読取りで転送されるにはあまりにも大きすぎる。故に、トラックは、それぞれが転送できるデータのユニットを含む多数のセクターに分割される。ディスクシステム１８は、アームに対するディスク２０の現在位置を決定する手段を有する。
　　　【００１４】
　一般に、ディスク２０にアクセスする度に、ディスクに対してアームが移動する。適当なセクターが読取り／書込みヘッド２６の下に移動するのに要する時間間隔に加えて、時間間隔は、アーム２４が指定トラックに移動するためにも必要である。この時間はアームが横断した距離、すなわち横断したトラック数、に依存する。故に、別のトラックのセクタ内に含まれる情報を得るためにトラックがアーム２４によって横断され、再横断される場合、望ましくない時間的ペナルティが発生する。
　　　【００１５】
　例えば、トラック２８内に含まれるセクタからのデータが要求され、続いてトラック３６内のセクタからのデータのリクエスト、次にトラック３０内のセクタから、最後にトラック３８内のセクタから要求される場合、アクセスアセンブリ２４は、トラック３８、３６、３４、３２，３０を経て、第１のアクセストラック２８に移動し、続いてトラック３０、３２、３４を経て、トラック３６に戻り、次に後方に、トラック３４、３２を経て移動してトラック３０にアクセスし、最後にトラック３２、３４、３６を経てトラック３８にアクセスすることが求められる。アームによるこの大きな移動は、かなり大量の時間を要し、より低い帯域幅となる。アクセス時間を低減するために、アーム２４の移動を最小限に抑えで情報を検索することができるよう、順次にアクセスされる情報を隣接するトラックに割り当てるシステムを考える事ができるが、これは常に可能であるとは限らない。特に、情報が不規則な順番でアクセスされる場合には不可能となる。
　　　【００１６】
　ディスク記憶システムの効率は、アクセスアセンブリの移動を最小限に抑えるような順番でトラック内に含まれる情報を読み出すことによって、すなわち記憶媒体上をアームによって移動される距離が最小となるような順番でにディスクリクエストを処理することによって低減されることも考えられる。これは、スキャン順番の最適化と称する。
　　　【００１７】
　例えば、アクセスアセンブリが、最初にディスク２０の外縁の外側の位置にある場合、ディスク２０の６つのトラックから情報を読み出すための最適なスキャン順番は、次のとおりである。トラック３８、トラック３６、トラック３４、トラック３２、トラック３０、トラック２８。図２に示されるように、この順番によれば、アクセスアセンブリの移動距離は、ディスク２０の半径２５と等しくなる。すなわち、スピンドル２２に向かう方向に移動が開始した後、ディスク２０の外縁に向かう逆方向の移動によって生成される追加的距離が除かれた距離となる。この順番によれば、読取り／書込みヘッドの移動を最小限に抑えることができ、ディスクシステムの利用度を最大限に引き上げることができるが、リクエストの優先度およびデッドラインを含む場合は、利用できない。
　　　【００１８】
　リクエストに優先度を与えるシステムの例として、ビデオ・オン・ディマンドマルチメディアがある。このシステムでは、顧客は、音声、または映像の配給を、音声、または映像データを含む供給源からリクエストする。この供給源は、一般に図１および図２に示された構成のものであり、それから音声、または映像データがディスクシステム１８を使用して検索され、最終的にリクエストしている顧客に提供される。顧客に対するサービス料金は、提供されるサービス品質（ＱＯＳ）に正比例する。（すなわち、より高いＱＯＳを要求する顧客には割り増し料金が課金される。）これは、高い優先度で位置付けされた顧客から出されたリクエストが、低い優先度で位置付けされた顧客から出されたリクエストより先に処理されるように、加入した際のパッケージの価格に基づいて顧客から受けたリクエストを優先順位付けすることによって達成される。
　　　【００１９】
　リクエストの優先度は、他の要素に基づいても決定できる。例えば、ビデオ・オン・ディマンドにおいては、再生中、使用者によるＱＯＳの知覚が優先レベルを指示しても良い。使用者は、映像の紛失フレームよりも、音声の遅延／紛失フレームを容易に知覚することができるので、音声データのリクエストは、映像データよりも高い優先度で処理される必要がある。
　　　【００２０】
　優先レベルに加えて、データリクエストは、それらが処理されなければならない時間、すなわちデッドラインを含んでもよい。リクエストがそのデッドラインまでに処理されない場合、それは紛失したものと見なされ、望ましくないジッタが使用者の端末に生成される。但し、ビデオ・オン・ディマンドマルチメディアなどでは、デッドライン単独では、ディスクリクエストに対する要求をモデル化するには不十分であり、用途に対するデータの重要性を知ることによりディスクスケジューリングを実行する必要がある。
　　　【００２１】
　図３は、ディスクスケジューリングシステム５０の従来技術の構成を示す。多数の優先リクエストのこの従来型処理法では、厳密な優先度が、より低い優先リクエストに比べてより高い優先リクエストに認められる。１９８９年、オランダのアムステルダムで開催されたＶｅｒｙ　Ｌａｒｇｅ　Ｄａｔａ　Ｂａｓｅ（大規模データベース）についての国際会議でのＭ．カリー（Ｃａｒｅｙ）、Ｒ．ジャハリ（Ｊａａｈａｒｉ）、Ｍ．リブニー（Ｌｉｖｎｙ）の、ＤＢＭＳリソーススケジューリングにおける優先度、および１９９１年、１２ｔｈ　Ｒｅａｌ−Ｔｉｍｅ　Ｓｙｓｔｅｍｓ　Ｓｙｍｐｏｓｉｕｍ、２２２−２３２頁に記載されたＷ．キム（Ｋｉｍ）およびＪ．スリヴァスタバ（Ｓｒｉｖａｓｔａｖａ）のＥｎｈａｎｃｉｎｇ　Ｒｅａｌ−Ｔｉｍｅ　ＤＢＭＳ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｗｉｔｈ　Ｍｕｌｔｉｖｅｒｓｉｏｎ　Ｄａｔａ　ａｎｄ　Ｐｒｉｏｒｉｔｙ　Ｂａｓｅｄ　Ｄｉｓｋ　Ｓｃｈｅｄｕｌｉｎｇ（マルチ型データおよび優先度を基礎にしたディスクスケジューリングでのリアルタイムＤＢＭＳ性能の強化）を参照。このスケジューリングシステム５０は、各優先レベル毎に１つの待ち行列を有する。この提案では、スケジューリングシステム５０は、優先度５の待ち行列５２が最上位優先度を有し、優先度１の待ち行列５４が最下位優先度を有する５つの優先レベルに対応する５つの待ち行列を有する。待ち行列からのリクエストは、より高い優先度を有する任意の待ち行列内に待機中のリクエストが存在しない場合にのみスケジュールされる。例えば、優先度３の待ち行列５８に含まれたりクエスト４　５６は、優先度４の待ち行列６２に含まれたリクエスト１　６０、および優先度５の待ち行列５２に含まれたりクエスト３　６４がスケジュールされるまで、処理されないであろう。このシステムは、高優先度のリクエストのみに対する応答時間および紛失度に関して最適性能となるが、性能全体としては必ずしも優れているとはいえない。
　　　【００２２】
　従来技術のスケージューリングシステムの欠点は、次の例で説明できる。図３をさらに参照して、全てのリクエストが同じサービスタイム、たとえば２０ｍｓ、を必要とすると仮定する。（サービスタイムは、情報にアクセスして読み取りを完了するのに必要な時間である。）各リクエストが到着すると、それには優先度が割り当てられ、割り当てられた優先値の待ち行列内に配置される。図３に示されるように、リクエスト０　６６は、低優先度１、および６０ｍｓｅｃの短い厳しいデッドラインを有する。従来技術のシステムの下では、リクエスト０　６６は、余裕のあるデッドラインを有するリクエスト１　６０およびリクエスト４　５６等のより高い優先度の待ち行列にあるリクエストの全てがスケジュールされるまで処理されない。このスケジューリングによれば、３つのより高い優先度のリクエストを処理するため６０ｍｓ要するが、これはリクエスト０　６６の６０ｍｓｅｃデッドラインと同じであり、結局、リクエスト０　６６は紛失される。但し、リクエスト０　６６が、リクエスト１　６０およびリクエスト４　５６の前に処理されることが可能であれば、リクエスト０　６６は救われ、より高い優先度のリクエストのデッドラインも守られ、システムの総性能が増すこととなる。本発明は、この前提に基づくものである。
　　　【００２３】
　本発明の実施形態のディスクスケジューリング方法および装置は、高優先リクエストの処理だけでなく、利益を上げるためシステム全体の処理も考慮している。この方法は、高優先のリクエストのデッドラインが許す限り、厳しいデッドラインを有する低優先リクエストをも処理する。さらに、本発明の実施形態は、最適スキャン順番を探すスケジューリングを通じてシークタイムを最小限に抑えることによってディスク利用度を最大限にまで上げる。
　　　【００２４】
　この実施形態は、３つの条件を満たそうとする。第１の条件は、帯域幅効率が低減されないこと。これは、最適スキャン順番を維持することによって、または少なくともいかなる争奪（ｓｃｒａｍｂｌｉｎｇ）も最小限に抑えることによって達成される。第２の条件は、争奪を最小限に抑えるため、または最適スキャン順番を提供するための再構成が、より高い優先リクエストの紛失とならないこと。最後に、紛失したリクエスト数が最小限に抑えられること。第２および第３の条件は、各優先レベルに対するリクエストの費用を表す関数を定義することによって捉えることができる。各優先レベルでリクエストを紛失すると、異なる費用となるので、その最終目標は、システムに対する総費用を最小限に抑えることとなろう。使用されるシステムは、効率的に実施可能なものでなければならない。最良のスケジュールが選ばれるよう、全ての予期される有効スケジューリング順番を、与えられた時間で遂行することは必ずしも可能でない。
　　　【００２５】
　図４は、本発明の実施形態のディスクスケジューリングシステム８０を示す。このシステムは、ディスク記憶システム８２、必要な命令を提供してディスク８８からデータを検索するための読取り／書込みアクセスヘッドを位置決めするディスクドライブコントローラ８４、処理されるべき多数の優先レベルのリクエストの全てを含む単一リクエスト待ち行列９０を保持する待ち行列保持部、およびメモリ部９４に保持されたリクエスト関連データに基づいてリクエスト待ち行列９０の順番を制御するリクエストプロセッサ９２から成る。
　　　【００２６】
　新しいリクエスト９６がディスクスケジューリングシステム８０に与えられると、それはリクエストプロセッサ９２によって受け取られる。このリクエストプロセッサ９２は、最初にリクエスト待ち行列９０にこの新リクエストを挿入する。挿入後、このリクエストプロセッサ９２は、リクエスト待ち行列９０にあるリクエストの内、そのデッドラインが過ぎてしまっているものがあるかどうかを判定する。このリクエストプロセッサ９２は、リクエスト関連データ９４からデッドライン情報を得る。デッドラインが過ぎておらずリクエストの全てがまだ有効である場合、このリクエストプロセッサはそれ以上なにも活動しない。リクエストのデッドラインが、現在の順番のままでは超えてしまう場合、このリクエストプロセッサは、リクエスト関連データ９４内に含まれる優先度データおよびデッドラインデータに基づいてその待ち行列順番を並び替える。
　　　【００２７】
　図５は、リクエスト待ち行列の順番を判定するのにリクエストプロセッサによって使用されるステップのフロー図を示す。前述のように、ステップ１１０により待ち行列再構成プロセスが開始される。スキャン順番に基づいてリクエスト待ち行列内に新リクエストを挿入する（ステップ１１２）。この挿入ステップ１１２の後に、この順番は、検査され、リクエストデッドラインが過ぎてしまっているかどうかを判定する（ステップ１１４）。デッドラインの全てが過ぎていない場合、リクエスト待ち行列の順番は正しく、リクエストプロセッサによる再順番付けは、それ以上なにもなされない（ステップ１１５）。しかし、少なくともどれか一つのリクエストのデッドラインが過ぎていれば、このプロセッサは、リクエスト待ち行列を再度順番付けする。
　　　【００２８】
　リクエスト待ち行列の再順番付けを行う第１のステップは、デッドラインが過ぎてしまうリクエストの前に処理されるべきリクエストの全てを識別する（ステップ１１６）。この部分集合から、最下位優先度を有するリクエストが選択される（ステップ１１８）。この群から、最下位優先度を有する単一のリクエストが、または最下位優先度群内に多数のリクエストがあるかどうかが判定される（ステップ１２０）。低優先度群内に多数のリクエストがある場合には、最も緩い、すなわち余裕のあるデッドラインを有するリクエストが選択され（ステップ１２２）、処理されるリクエスト待ち行列の最後の位置に配置される（ステップ１２４）。最下位優先度を有する単一リクエストしかない場合、この単一の低優先リクエストは、選択され（ステップ１２６）、リクエスト待ち行列の最後のサービス位置に移動される（ステップ１２４）。
　　　【００２９】
　最後のサービス位置におけるリクエストのデッドラインは、次に検査され、そのデッドラインが過ぎてしまうかどうか判定し（ステップ１２８）、過ぎてしまう場合、紛失されることが宣言され、待ち行列から排除される（ステップ１３０）。その待ち行列は、次に再検査され、過ぎてしまうデッドラインがなにもないことを確認し（ステップ１１４）、再順番付けステップが開始されるか、または終了される（ステップ１１５）。
　　　【００３０】
　ディスクスケジューリングシステムのこの方法をさらに理解するために、次の例が提示される。図６は、５つのリクエスト１４０、１４２、１４４、１４６、１４８、および新たに受け取られたリクエスト１５０を示す。図７に示されるように、これらのリクエストは、この例示では最適となり得る最も効率的なスキャン順番に基づいてリクエスト待ち行列内に配置される。
　　　【００３１】
　図８を参照、して、新リクエスト１５０を受け取ると、この新リクエストは、好適スキャン順番となる位置に試験的に配置される（図７に示されるようにリクエスト２とリクエスト３との間である）。新リクエスト１５０の挿入により待ち行列内のいかなるリクエストのデッドラインが過ぎてしまうことが無い場合、さらにそれ以上活動せず、この待ち行列は、配列されたとおり正しいとされる。
　　　【００３２】
　しかし、この例では、各リクエストのサービスタイムが２０ｍｓｅｃであるので、リクエスト３　１４６のデッドラインは、新リクエスト１５０の挿入で過ぎてしまうこととなる。故に、この待ち行列は再構成されなければならない。
　　　【００３３】
　デッドラインが過ぎてしまうリクエスト３　１４６の前に現在処理されるべきリクエストの内、リクエスト２　１４４は、最下位優先度、および最も余裕のあるデッドラインを有する。故に、図９に示されるように、リクエスト２　１４４は、待ち行列の末尾に移動される。待ち行列のこの順番は、次に解析されて、いずれかのデッドラインが過ぎてしまうかどうかが判定されるが、この例では、なにも存在しない。この順番は、次にリクエストを紛失させずに現存するリクエストを処理し、優先度を尊重し、且つ記憶媒体の利用度を最大限まで上げるスキャン順番に最も近似する順番を維持することができるようにする。
　　　【００３４】
　前述から、本発明は、ディスク媒体を参考にして例示、説明してきたが、説明を目的とした実施例で採用された技術が、他の用途にも適用できることは明白であることは理解されよう。故に、本発明は、添付の請求の範囲で詳述されるように本発明の趣旨を逸脱することなく一定の修正、または変更が可能であることは理解されよう。
【図面の簡単な説明】
　　【図１】　従来のディスク記憶装置の平面図である。
　　【図２】　図１の従来型ディスク記憶装置の側面図である。
　　【図３】　優先レベルのそれぞれに対して１つの待ち行列を有する従来技術のスケジューリング構成の説明図である。
　　【図４】　本発明の実施形態の記憶媒体アクセスヘの優先順位付けされたリクエストをスケジュールするための装置のシステム全体のブロック図である。
　　【図５】　本発明の実施形態の待ち行列順番付けステップのフローチャートである。
　　【図６】　新リクエストの挿入前の、本発明の実施形態の単一スケジューリング待ち行列のブロック図である。
　　【図７】　スキャン順番で図６のリクエストのディスクロケーションを示す平面図である。
　　【図８】　デッドラインが過ぎてしまう新リクエストの挿入後の、本発明の実施形態の単一待ち行列のブロック図である。
　　【図９】　再構成後の、本発明の実施形態の単一待ち行列のブロック図である。
　　【符号の説明】
　　　８０…ディスクスケジューリングシステム
　　　８２…ディスク記憶システム
　　　８４…ディスクドライブコントローラ
　　　８８…ディスク
　　　９０…単一リクエスト待ち行列
　　　９４…リクエスト関連データ
　　　９２…リクエストプロセッサ
【図面】