(57)【特許請求の範囲】
【請求項１】
プロセッサユニットと、メモリと、１またはそれ以上のメディア／ストレージデバイスとを含むシステム内で、１またはそれ以上のメディア／ストレージデバイスに対する入力または出力（入出力）をハンドリングする方法であって、
ａ）前記プロセッサ上で実行中のアプリケーションから、１またはそれ以上のメディア／ストレージデバイスに対するデータの転送または受信のための入出力リクエストを受信するステップと、
ｂ）前記入出力リクエストを受信した後、前記プロセッサが実行可能でかつ前記メモリ内に実体化された、前記入出力リクエストに関連する１またはそれ以上の処理のレイヤを規定する木構造命令を含む木構造を生成するステップとを含み、
前記木構造命令は、１またはそれ以上の対応する処理命令を実行することで、前記入出力リクエストの前記データを、前記１またはそれ以上の前記入出力リクエストの処理のレイヤにおける１またはそれ以上のチャンク（chunk；塊）に分解するものであり、前記１またはそれ以上の処理のレイヤにおける各処理命令は、先の処理のレイヤ内の１またはそれ以上の対応する処理命令に関連するデータ依存関係を持っており、所与の処理命令に対する前記データ依存関係は、前記先の処理のレイヤ内の対応する１またはそれ以上の依存関係のある処理命令の実行の後に前記所与の処理命令の実行を許可するものであり、
当該方法はさらに、
ｃ）前記木構造を生成した後に、前記木構造内の処理命令を、各チャンクの記憶場所および異なる入出力リクエスト処理のレイヤのチャンク間におけるデータ依存関係を決定することで処理の順序に並べ替えるステップと、
ｄ）前記木構造内の処理命令を処理の順序に並べ替えた後に、前記メモリ内に実体化されたスケジュール内の少なくとも部分的には前記処理の順序に依存する位置に、１またはそれ以上の処理命令を挿入するステップと、
ｅ）前記処理命令は前記メモリ内に実体化された前記スケジュール内の前記木構造に関連した前記処理の順番にしたがって前記プロセッサによって実行されるものであり、１またはそれ以上の前記処理命令を前記メモリ内に実体化されたスケジュール内に挿入した後に、前記スケジュールにしたがって前記プロセッサで前記処理命令を実行することによって前記入出力リクエストの要求に応えるステップとを含むことを特徴とする方法。
【請求項２】
ある特定の処理のレイヤに関連づけられた前記チャンクは、別の処理のレイヤに関連づけられた前記チャンクとは異なるサイズであることを特徴とする請求項１に記載の方法。
【請求項３】
ステップｅ）は、データ依存関係を持っている所与の処理命令を実行する前に、依存している処理命令の実行が完了しているか否かを決定することを含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記木構造は最下層のレイヤを含み、前記最下層のレイヤ内の１またはそれ以上の処理命令は前記最下層のレイヤ内の異なる処理命令への関連するデータ依存関係を持っており、前記最下層のレイヤ内の所与の処理命令用の前記データ依存関係は、前記最下層のレイヤ内の対応する１またはそれ以上の依存している処理命令が実行された後のみ、前記所与の命令の実行を許可することを特徴とする請求項１に記載の方法。
【請求項５】
ステップｅ）は、共通のレイヤからの２またはそれ以上の処理命令を同時に実行することを含むことを特徴とする請求項１に記載の方法。
【請求項６】
ステップｅ）は、２またはそれ以上の異なるレイヤからの２またはそれ以上の処理命令を同時に実行することを含むことを特徴とする請求項１に記載の方法。
【請求項７】
ステップｅ）は、１またはそれ以上の入出力リクエストからの１またはそれ以上の処理命令を、前記木構造の命令の実行の中にプロセッサに交互に実行させることを含むことを特徴とする請求項１に記載の方法。
【請求項８】
ステップｅ）は、前記木構造の１またはそれ以上の処理命令の実行することで、前記１またはそれ以上の入出力リクエストからの前記１またはそれ以上の処理命令を同時に実行することを含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記１またはそれ以上の処理のレイヤは、デアーカイブまはたアーカイブレイヤを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記１またはそれ以上の処理のレイヤは、復号または暗号化レイヤを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記１またはそれ以上の処理のレイヤは、解凍または圧縮レイヤを含むことを特徴とする請求項１に記載の方法。
【請求項１２】
ステップｄ）において前記スケジュール内に前記入出力リクエストの処理命令を挿入することは、前記入出力リクエストに関連づけられた処理命令の実行の優先度制約にさらに依存することを特徴とする請求項１に記載の方法。
【請求項１３】
ステップｄ）において前記スケジュール内に前記入出力リクエストの処理命令を挿入することは、前記入出力リクエストに関連づけられた処理命令の実行の期限制約にさらに依存することを特徴とする請求項１に記載の方法。
【請求項１４】
ステップｅ）は、２またはそれ以上の入出力リクエストに関連づけられた前記木構造が、前記スケジュールに入っている１またはそれ以上の入出力リクエストのデータ依存関係の重複（オーバーラップ）があるときに、前記入出力リクエストを交互配置するか否かを決定するために定められたオーバーラップ閾値を満たすとき、前記スケジュール内への挿入に先立って、前記２またはそれ以上の入出力リクエストを交互に配置することを特徴とする請求項１に記載の方法。
【請求項１５】
ステップｅ）は、実行時に、１またはそれ以上のファイルに差分パッチを適用することを含むことを特徴とする請求項１に記載の方法。
【請求項１６】
プロセッサユニットと、
前記プロセッサユニットに接続されたメモリと、
前記プロセッサユニットに接続された１またはそれ以上のメディア／ストレージデバイスと、
前記メモリ内に実体化されたプロセッサに実行可能な一セットのプログラム命令であって、前記命令は、
ａ）前記プロセッサ上で実行中のアプリケーションから、１またはそれ以上のメディア／ストレージデバイスに対するデータの転送または受信のための入出力リクエストを受信する機能と、
ｂ）前記入出力リクエストを受信した後、前記プロセッサが実行可能でかつ前記メモリ内に実体化された、前記入出力リクエストに関連する１またはそれ以上の処理のレイヤを規定する木構造命令を含む木構造を生成する機能とを含み、
前記木構造命令は、１またはそれ以上の対応する処理命令を実行することで、前記入出力リクエストの前記データを、前記１またはそれ以上の前記入出力リクエストの処理のレイヤにおける１またはそれ以上のチャンク（chunk；塊）に分解するものであり、前記１またはそれ以上の処理のレイヤにおける各処理命令は、先のレイヤ内の１またはそれ以上の対応する処理命令に関連するデータ依存関係を持っており、所与の命令に対する前記データ依存関係は、前記先のレイヤ内の対応する１またはそれ以上の依存関係のある命令の実行の後に前記所与の命令の実行を許可するものであり、
当該命令はさらに、
ｃ）前記木構造を生成した後に、前記木構造内の処理命令を、各チャンクの記憶場所および異なる前記入出力リクエストの処理のレイヤのチャンク間におけるデータ依存関係を決定することで処理の順序に並べ替える機能と、
ｄ）前記木構造内の処理命令を処理の順序に並べ替えた後に、前記メモリ内に実体化されたスケジュール内の少なくとも部分的には前記処理の順序に依存する位置に、１またはそれ以上の処理命令を挿入する機能と、
ｅ）前記処理命令は前記メモリ内に実体化された前記スケジュール内の前記木構造に関連した前記処理の順番にしたがって前記プロセッサによって実行されるものであり、１またはそれ以上の前記処理命令を前記メモリ内に実体化されたスケジュール内に挿入した後に、前記スケジュールにしたがって前記プロセッサで前記処理命令を実行することによって前記入出力リクエストの要求に応える機能とを前記プロセッサユニットに実現させることを特徴とするシステム。
【請求項１７】
請求項１６に記載のシステムであって、
前記メモリ内に実体化されたプロセッサに実行可能な一セットの命令はさらに、請求項２から１５のいずれかに記載の方法を実行する機能を含むことを特徴とするシステム。
【請求項１８】
コンピュータに読み取り可能なコードを格納するコンピュータに読み取り可能な記録媒体であって、
前記コンピュータに読み取り可能なコードは前記記録媒体の中に実体化されており、当該コードは実行されたときに１またはそれ以上のメディア／ストレージデバイスに対する入力または出力（入出力）をハンドリングするものであり、
当該コンピュータプログラムプロダクトは、請求項１から１５のいずれかの方法を前記コンピュータに実現させることを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００９年１０月２６日に出願された、アンドリュー  アール．  ターラー
による即時的にデータをチャンクにすることを用いたファイル入出力スケジューリングと題する米国仮出願第６１／２５５，０１３号の優先権を主張し、開示内容全体を参照によりここに完全に組み入れる。
【０００２】
本出願は、２０１０年１０月１２日に出願された、アンドリュー  アール．  ターラー
による即時的にデータをチャンクにすることを用いたファイル入出力スケジューリングと題する米国出願第１２／９０２，７６８号の優先権を主張し、開示内容全体を参照によりここに完全に組み入れる。
【０００３】
本発明の実施の形態はコンピュータゲームおよび関連するアプリケーションに関し、より具体的には、コンピュータゲームおよび関連するアプリケーションにおけるファイルの入力／出力（入出力）管理に関する。
【背景技術】
【０００４】
ビデオゲームのような多くのソフトウェアアプリケーションは、アプリケーション内のメディアアクセスをより効率よくかつ信頼あるものとするためのファイル入力／出力（入出力；Ｉ／Ｏ）スケジューラを含む。ファイル入出力システム（file I/O system: FIOS）は、いくつかのパーツからなるファイルにアクセスするための、スケジューラおよび任意の入出力フィルタレイヤを含むミドルウェアレイアである。スケジューラは、典型的には任意の期限および優先度制約による条件の下、可能な限り最短時間で完了するように入出力リクエストを最適に並べ替えるように設計されている。
【０００５】
多くの異なるゲームコンポーネントは、ストレージメディア内のファイルへの入出力アクセスを要求する。オーディオコンポーネントはオーディオファイルを読み込み、ゲームプレイのエンジンはレベルの定義を読み込み、グラフィックコンポーネントはテクスチャマップおよびモデルを読み込み、動画コンポーネントは音声映像ファイルを読み込み、サブシステムは巨大なＷＡＤファイルを読み込む。メディアは、ＵＭＤ（universal media disc）、ＣＤ（compact disc）、ＤＶＤ（digital video disc）、Ｂｌｕ−ｒａｙ（登録商標）ディスク等のような光学ディスク、ハードディスクのような中間ストレージメディア、あるいは発達するプラットフォームの等の他のメディアタイプのような、ゲーム配信メディアであってもよい。
【０００６】
ビデオゲームのような単一のアプリケーションは、典型的には多数のコンポーネントを持っており、各コンポーネントは独自の入出力要求を持っている。あるものはメデイアへのストリーミングアクセスを要求する。ここで入出力システムは、コンポーネントがゲームプレイヤにストリーム化（stream）されたデータを連続的に提示できるようにファイル内のデータをストリーム化する。例えば、音声コンポーネントは典型的にはサウンドトラックの再生のためにオーディオファイルをストリーミングする。動画コンポーネントはプレイヤに動画を再生するために音声映像コンテンツをストリーミングする。他のコンポーネントは、コンポーネントを処理するためにデータをファイルから一部分（以下「チャンク（chunk；塊）」という。）を取ってくる非ストリーミングアクセスのみを必要とする。これらのコンポーネントは処理するための決まったデータフローを要求しないが、チャンクの配信のタイミングはしばしば極めて重要となる。もしアプリケーションがデータが必要なときにそれを受け取れないと、パフォーマンスを下げるかも知れない。
【０００７】
現在、チャンキング（chunking）（例えば、入出力リクエストのためにデータを部分／チャンクにばらすこと）は入出力リクエストの実行中に発生する。チャンク間のデータの依存関係は、実行の前には決定されず、これは入出力リクエストの処理の非効率化を招く。例えば、所与の入出力リクエストは、転送の前に復号と解凍との両方が必要とされるデータを要求するかも知れない。入出力システムは、解凍の前に所与のチャンクの復号の発生を要求しうるが、異なるチャンクのサイズが復号と解凍に関連づけられうる。例えば、復号に関連づけられているチャンクのサイズは６４キロバイトのように固定されていてもよく、解凍に関連づけられているチャンクのサイズは可変であってもよい。それ故、復号されるチャンクと解凍されるチャンクとの間のデータ依存関係を決定しないと、ひとたび必要とする復号化された所与のチャンクが処理されてからその解凍を開始するというのではなく、ファイルが解凍可能となる前にファイル全体を復号しなければならない。
【０００８】
同様に、多数のメディアのソースからデータが読み出されることを要求する所与の入出力リクエストは、実行中にチャンキングする現在の形態では非効率的に処理されうる。処理に先立ってチャンク間のデータ依存関係を決定することをしないと、メデイアデバイスは、理論的には同時にふたつのメディアデバイスが処理されるときでも、一方のメディアデバイスが処理されているときにもう一方は働いていないことになりうる。これは最終的にビデオゲームや他のアプリケーションの機能を低下させる。
【０００９】
さらに、ビデオゲームはしばしばかなりの量の入出力を行う。ゲームのイベントはしばしば必ず間に会わなければならない期限を持つタイムドリブン型のものである。例えば、もしプレイヤがＡ地点からＢ地点まで移動すると、ゲームはプレイヤがＢ地点に到達する前にＢ地点に関連するデータ用のファイルを持っておく必要がある。ゲームコンポーネントは低水準の入出力基本命令（primitives）を使ってメディアからデータを読み出すことができるが、これらの基本命令は多数のコンポーネントが同じデバイスからのデータを同時に要求するときにデバイス接続を扱うことはしない。混雑した入出力リクエストはストリーミングデータフローを中断したり、必要なときにコンポーネントがデータのチャンクを取得することを妨げたりする可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
アプリケーションのコンポーネントは、典型的にはお互いの入出力活動を関知していないので、それらの入出力リクエストはかなりの量の過度な探索（データを探すために行きつ戻りつすること）を含む、とても非効率な入出力パターンにしばしば陥る。ゲームが大きくなると、過度な探索および非効率なデータ取得が増加する。
【００１１】
本発明の実施の形態はこのような文脈の中で生じた。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明のある形態は、プロセッサユニットと、メモリと、１またはそれ以上のメディア／ストレージデバイスとを含むシステム内で、１またはそれ以上のメディア／ストレージデバイスに対する入力または出力（入出力）をハンドリングする方法である。この方法は、ａ）前記プロセッサ上で実行中のアプリケーションから、１またはそれ以上のメディア／ストレージデバイスに対するデータの転送または受信のための入出力リクエストを受信するステップと、ｂ）前記プロセッサが実行可能でかつ前記メモリ内に実体化された、前記入出力リクエストに関連する１またはそれ以上の処理のレイヤを規定する命令を含む木構造を生成するステップとを含む。ここで前記命令は、前記入出力リクエストの前記データを前記１またはそれ以上の処理のレイヤにおける１またはそれ以上のチャンク（chunk；塊）に分割するものであり、前記１またはそれ以上のレイヤそれぞれは、先のレイヤ内の１またはそれ以上の命令に対応する関連するデータ依存関係を持っており、所与の命令に対する前記データ依存関係は、前記先のレイヤ内の対応する１またはそれ以上の依存関係のある命令の実行の後に前記所与の命令の実行を許可するものであり、本方法はさらに、ｃ）前記木構造内の命令を、各チャンクの記憶場所および異なる処理のレイヤのチャンク間におけるデータ依存関係を決定することで処理の順序に並べ替えるステップと、ｄ）１またはそれ以上の命令を前記メモリ内に実体化されたスケジュール内の、少なくとも部分的には前記処理の順序に依存する位置に挿入するステップと、ｅ）前記命令は前記メモリ内に実体化された前記木構造に関連した前記処理の順番にしたがって前記プロセッサによって実行されるものであり、前記スケジュールにしたがって前記プロセッサで前記命令を実行することによって前記入出力リクエストの要求に応えるステップとを含む。
【図面の簡単な説明】
【００１３】
本発明の実施の形態は、添付の図面と併せて、以下の詳細な説明を考慮することによって容易に理解される。
【図１】本発明の実施の形態に係るファイル入出力システム（file I/O system: FIOS）を実装するシステムを示すブロック図である。
【図２】本発明の別の実施の形態に係るファイル入出力システムを実装する別のシステムを示すブロック図である。
【図３】本発明の実施の形態に係るファイル入出力システム（file I/O system: FIOS）ソフトウェアのブロック図である。
【図４】本発明の実施の形態に係るファイル入出力システムの行程の流れを例示するデータフロー図である。
【図５】本発明の実施の形態に係るファイル入出力システムで使用さらえるソフトウェアスケジューラの例を示すフロー図である。
【発明を実施するための形態】
【００１４】
以下の詳細な説明には、説明のための多くの具体的な詳細事項が含まれるが、それらに対する多くの変更や修正も本発明の技術範囲に含まれることは、当業者であれば誰でも理解するであろう。したがって、以下に説明する本発明の例示的な実施の形態は、クレームされた発明の一般性をなんら損なうことなく、また限定も行うことなく記載されている。
【００１５】
本発明の実施の形態は、システム用の全ての入出力が通過する集中型のレイヤを提供するファイル入出力システム（file I/O system: FIOS）によって実装されうる。ファイル入出力システムは、ここの入出力リクエストの最適な処理のための木構造を作成する命令と、入出力リクエストをスケジュールし、入出力リクエストが最も効率的にサービスを提供する順序を決定する命令とを含む。
【００１６】
例として、図１に示すように、コンピュータで実装されたシステム１００が本発明の実施の形態に係るファイル入出力システム（file I/O system: FIOS）を実装するように構成されてもよい。例として、一般性を失うことなく、システム１００は本発明の実施の形態の実行に適したパーソナルコンピュータ、ビデオゲームのコンソール、携帯型ゲームデバイス、携帯電話、ＰＤＡ（personal digital assistant）、または他のデジタルデバイスとして実装されてもよい。システム１００はＣＰＵ１０５と、処理ユニット１０５に接続するメインメモリ１０６とを含んでもよい。ＣＰＵ１０５はソフトウェアアプリケーションおよび、オプションとしてオペレーティングシステムを実行するように構成されている。セルプロセッサアーキテクチャの例は、「セルブロードバンドエンジンアーキテクチャ」に詳細が記述されている。これは、ＩＢＭ、ソニー・コンピュータエンタテインメント、東芝の２００５年８月８日付けの著作権で保護されており、コピーはｈｔｔｐ：／／ｃｅｌｌ．ｓｃｅｉ．ｃｏ．ｊｐ／からダウンロード可能であり、その内容全体を参照によってここに組み入れる。
【００１７】
メインメモリ１０６は、ＣＰＵ１０５に使用されるアプリケーションおよびデータを格納する。メインメモリ１０６は、例えばＲＡＭ、ＤＲＡＭ、ＲＯＭやそれと同様の集積回路の形態であってもよい。コンピュータプログラム１０１は、ＣＰＵ１０５上で実行可能な命令の形態でメインメモリ１０６内に格納される。プログラム１０１の命令は他のもの、すなわち以下に記載する特徴を持ったファイル入出力システム（file input/output system: FIOS）で実装するよう構成されてもよい。メモリ１０６は、例えばスタックまたはキューの形態で、ファイル入出力プログラム１０１に使用される受信、スケジュール、発行、完了、および解放の入出力リクエストである入出力キュー１０１Ｑを含む。それらのキューの例もまた以下に記載される。
【００１８】
例として、ファイル入出力プログラム１０１は、ａ）アプリケーション１０３からのメディアデバイス１１８に作用する着信してくる入出力リクエストを受信し、ｂ）転送されるデータのチャンク（例えば一部分）の記憶位置とデータ依存関係とを決定することにより、入出力リクエストのための処理の最適な順序を形成するように作成されている木構造を作成し、ｃ）メモリ１０６内に実体化されたスケジュール内に着信してくる入出力リクエストを挿入し、ｄ）スケジュールと木構造とにしたがって入出力リクエストを実装する命令を含んでもよい。ここで、スケジュール内に着信してくる入出力リクエストを挿入する位置は、少なくとも部分的には、木構造の処理の順序に依存する。
【００１９】
クライアントシステム１００はさらに、入出力（Ｉ／Ｏ）装置１１１、電源（Ｐ／Ｓ）１１２、クロック（ＣＬＫ）１１３およびキャッシュ１１４などの公知のサポート機能５１０を備えてもよい。クライアントシステム１００は、アプリケーションとデータ用の不揮発性のストレージを提供するハードディスクのような高速ストレージ１１５をさらに備えてもよい。高速ストレージ１１５は、他のものの間で、より遅いメディアデバイス１１８から読み出されたファイル１１６の一時的または長期間のストレージに使用されてもよい。さらに、高速ストレージ１１５上のファイル１１６は、より遅いメディアデバイス１１６以外の他のソースから来てもよい。限定されるものではないが、例えば、ファイル１１６はオペレーティングシステムのファイル、アプリケーションによって作成されたテンポラリファイル、写真、音声、映像のようなユーザのデータ、ダウンロードされたコンテンツ、その他を含んでもよい。例として、高速ストレージ１１５は固定ディスクドライブ、リムーバブルディスクドライブ、フラッシュメモリデバイス、あるいはテープドライブであってもよい。より遅いメディアデバイス１１８は、例えばＣＤ−ＲＯＭドライブ、ＤＶＤ−ＲＯＭドライブ、ＨＤ−ＤＶＤ（high-definition digital versatile disc）ドライブ、Ｂｌｕ−Ｒａｙ（登録商標）ドライブ、ＵＭＤドライブ、または他の光学ストレージデバイス等の大容量光学ディスクドライブであってもよい。メディアデバイス１１８からのプリフェッチファイル１１６は、メインメモリ１０６に素早く読み出されるために、高速ストレージ１１５のハードウェアキャッシュに一時的に格納されてもよい。
【００２０】
１またはそれ以上の入力デバイス１２０は、１またはそれ以上のユーザからのユーザ入力をシステム１００に伝えるために使われてもよい。例として、１またはそれ以上のユーザ入力デバイス１２０は入出力エレメント１１１を経由してクライアントデバイス１００と接続されていてもよい。適切な入力デバイス１２０の例は、キーボード、マウス、ジョイスティック、タッチパッド、タッチスクリーン、光学ペン、静止または動画カメラ、および／またはマイクロフォンを含む。クライアントデバイス１００は電子通信ネットワーク１２７を介してコミュニケーションを促進するためのネットワークインタフェース１２５を含んでもよい。ネットワークインタフェース１２５はローカルエリアネットワークおよびインターネットのようなワイドエリアネットワーク上の有線または無線通信を実装するように構成されていてもよい。システム１００は、データを送信および受信し、および／またはネットワーク１２７を介して１またはそれ以上のメッセージパケット１２６を通じたファイルをリクエストしてもよい。
【００２１】
システムは、グラフィックプロセッシングユニット（ＧＰＵ）１３５とグラフィックスメモリ１４０とを有するグラフィックス・サブシステム１３０を更に含む。グラフィックスメモリ１４０は、出力イメージの各画素に対する画素データを格納するために使われるディスプレイメモリ（例えばフレーム・バッファ）を含む。グラフィックスメモリ１４０は、ＧＰＵ１３５と同じデバイス内に統合されてもよく、別のデバイスとしてＧＰＵ１３５に結合されてもよく、メモリ１０６内に実装されてもよい。画素データは、ＣＰＵ１０５から直接グラフィックスメモリ１４０に提供される。あるいは、ＣＰＵ１０５は、所望の出力イメージを定めるデータやインストラクションをＧＰＵ１３５に提供する。ＧＰＵ１３５はそれを用いて１またはそれ以上の出力イメージの画素データを生成する。所望出力イメージを定めるデータやインストラクションは、メモリ１０６やグラフィックスメモリ１４０に格納される。ある実施の形態では、ＧＰＵ１３５は、例えば、適当なプログラミングまたはハードウェア・コンフィギュレーションによって構成され、シーンのためにジオメトリ、ライティング（照明）、シェーディング、テクスチャリング、モーション、および／またはカメラパラメータを定めるインストラクションとデータから出力イメージに対する画素データを生成するための３Ｄレンダリング機能をもつ。ＧＰＵ１３５は、シェーダプログラムを実行することができるプログラム可能な実行ユニットを更に含む。
【００２２】
グラフィックス・サブシステム１３０は、表示装置１５０で表示されるべきグラフィックスメモリ１４０からのイメージに対する画素データを周期的に出力する。表示装置１５０は、システム１００からの信号に応じてビジュアル情報を表示することができる任意のデバイスであり、ＣＲＴ、ＬＣＤ、プラズマ、およびＯＬＥＤディスプレイを含む。コンピュータシステム１００は、表示装置１５０にアナログまたはデジタル信号を提供する。一例として、表示装置１５０は、テキスト、数字、グラフィカルシンボル、または画像を表示するＣＲＴまたはフラットパネルスクリーンを含む。さらに、ディスプレイ１５０は、可聴もしくは検知可能な音を出すオーディオスピーカーを含んでもよい。そのような音の生成を容易にするために、クライアントデバイス１００は、ＣＰＵ１０５、メモリ１０６、および／またはストレージ１１５によって提供されたインストラクションおよび／またはデータからアナログまたはデジタル音声出力を生成するために適したオーディオプロセッサ１５５を更に含む。
【００２３】
ＣＰＵ１０５、メモリ１０６、支援機能１１０、データストレージデバイス１１５、ユーザ入力デバイス１２０、ネットワークインタフェース１２５、およびオーディオプロセッサ１５５を含むシステム１００の構成要素は、データバス１６０を介して互いに機能的に接続されている。これらの構成要素は、ハードウェア、ソフトウェアまたはファームウェア、あるいはこれらのうちの２つ以上の組合せで実装される。
【００２４】
本発明のある実施の形態は、セルプロセッサアーキテクチャやそれと類似するプロセッサアーキテクチャをうまく利用する。図２は、本発明の別の実施の形態に係るファイル入出力システムを実装するセルプロセッサ２００を示す。セルプロセッサ２００は、メインメモリ２０２、ひとつのパワープロセッサ要素（ｐｏｗｅｒ  ｐｒｏｃｅｓｓｏｒ  ｅｌｅｍｅｎｔ：ＰＰＥ）２０４、および８つのシナジスティックプロセッサ要素（ｓｙｎｅｒｇｉｓｔｉｃ  ｐｒｏｃｅｓｓｏｒ  ｅｌｅｍｅｎｔ：ＳＰＥ）２０６を備える。図４の例では、セルプロセッサ４００は、１個のＰＰＥ４０４と８個のＳＰＥ４０６とを備える。このような構成では、７個のＳＰＥ４０６が並列処理に用いられ、１個は他の７個の一つが故障したときのバックアップとして確保されている。例示として、ＰＰＥ２０４は、関連するキャッシュを持った６４ビットのパワーＰＣプロセッサユニット（ＰＰＵ）であってもよい。ＰＰＥ２０４は、システム管理リソース（例えば、メモリ保護テーブルなど）にアクセス可能な汎用処理装置である。ハードウェアリソースは、ＰＰＥに見られるように実アドレス空間に明示的にマップされてもよい。したがって、ＰＰＥは適当な実効アドレス値を用いて、直接これらのリソースのいずれにでもアドレス指定できる。ＰＰＥ２０４の主な機能は、セルプロセッサ２００のＳＰＥ２０６に対するタスク管理とタスク割り当てである。ハードウェアリソースは、ＰＰＥ２０４に見られるように実アドレス空間に明示的にマップされてもよい。したがって、ＰＰＥ２０４は適当な実効アドレス値を用いて、直接これらのリソースのいずれにでもアドレス指定できる。ＰＰＥ２０４の主な機能は、異なるＳＰＥ２０６に対するタスク管理とタスク割り当てである。ＰＰＵはファイル入出力プログラム１０１のコード化された命令を実行する。
【００２５】
なんらシステム管理機能を果たさないＳＰＵ２０６は、ＰＰＥ２０４よりは簡単な構造のコンピュータ装置である。ＳＰＥ２０６のそれぞれは、ときにシナジスティックプロセッサユニット（ｓｙｎｅｒｇｉｓｔｉｃ  ｐｒｏｃｅｓｓｏｒ  ｕｎｉｔ：ＳＰＵ）として参照されるプロセッサユニットと、関連するローカル記憶領域ＬＳ（local store）とを含む。ＳＰＵ２０６は、一般にＳＩＭＤ（ｓｉｎｇｌｅ  ｉｎｓｔｒｕｃｔｉｏｎ，  ｍｕｌｔｉｐｌｅ  ｄａｔａ）機能を有し、通常はデータ処理を行い、割り当てられたタスクを行うために（ＰＰＥ２０４により設定されたアクセス特性にしたがって）要求されたデータ転送を開始する。ＳＰＥ２０６はファイル入出力プログラム１０１の一部を実装するローカルストア命令２０７を自身のローカルストア内に格納する。ＳＰＵ２０６の目的は、より高いコンピュータ装置密度を要求するアプリケーションを可能として、提供された命令セットを有効に利用できるようにすることである。本例では８個のＳＰＥが示されているが、セルプロセッサ２００は任意の数のＳＰＥを用いて設定される。図２を参照すると、メモリ２０２、ＰＰＥ２０４、およびＳＰＥ２０６は、リングタイプの要素相互接続バス２１０を介して、お互いにおよび入出力デバイス２０８と通信可能である。メモリ２０２は、メモリインタフェースコントローラ（ｍｅｍｏｒｙ  ｉｎｔｅｒｆａｃｅ  ｃｏｎｔｒｏｌｌｅｒ：ＭＩＣ）を介してＰＰＥ２０４およびＳＰＥ２０６からアクセスされる。
【００２６】
メモリ２０２は、以下に記載するような受信、スケジュール、発行、完了、解放、およびプリフェッチキュー等の入出力キュー２０３を含む。メモリ２０２は、本明細書に記載されているファイル入出力プログラム１０１と同様の特徴を持っているファイル入出力プログラム１０１の部分も含む。ＰＰＥ２０４は内部キャッシュ（Ｌ１）および外部キャッシュ（Ｌ２）を含んでもよい。ＰＰＥはこの内部キャッシュ（Ｌ１）にファイル入出力プログラム１０１の部分を格納する。ファイル入出力プログラム１０１とＳＰＥに実装されたファイル転送命令２０７、またはその一部とはまた、必要なときにＳＰＥ２０６とＰＰＥ２０４によってアクセスされるためにメモリ２０２に格納されてもよい。
【００２７】
例として、図３に示すように、ストレージデバイス１１５やメディアデバイス１１８のようなハードウェアとのインタフェースを容易にするために、ファイル入出力プログラム１０１はメディアスタック３００を含んでもよい。メディアスタック３００は、木構造レイヤ３０１、スケジューラ３０３、１またはそれ以上のメディアフィルタレイヤ３０５、デバイスメディアレイヤ３０７、プロセッサファイルシステム（ｐｒｏｃｅｓｓｏｒ  ｆｉｌｅ  ｓｙｓｔｅｍ：ＦＳ）、読み込みレイヤ３０９、およびハードウェアレイヤ３１１を含んでもよい。
【００２８】
木構造レイヤ３０１は、転送される個々の入出力リクエストに関連づけられたデータの最適な処理を容易にするためにマップを作成する。最初に、１またはそれ以上の処理のレイヤ３０６（例えば復号、解凍、デアーカイブ（de-archiving）等）を規定する、所与の入出力リクエストに関連づけられた木構造３１３が生成される。入出力リクエスト毎に転送や受信されるデータは木構造３１３の各レイヤにおいて処理され、木構造３１３は、先のレイヤ内の十分なデータが処理されるまでは続くレイヤの処理を開始しないように構成されている。木構造３１３はその後、１またはそれ以上の処理レイヤ３０６のそれぞれにおいて転送または受信されるように、データを１またはそれ以上のチャンク３０２に分解する。ある特定の処理のレイヤ３０６に関連づけられたチャンク３０２は、その特定の処理のレイヤ３０６に対応する１またはそれ以上のサイズを持つ。異なるレイヤのチャンクのサイズは異なってもよい。木構造３１３は、各チャンク３０２の記録場所と、異なる処理レイヤ３０６チャンク３０２間のデータ依存関係３０４とを決定することによって、異なるレイヤ用のチャンクの処理の最適な順序を形成する。
【００２９】
限定されるものではないが、一例として、入出力リクエストは暗号化され圧縮された受信データを含んでもよい。木構造は最初に、入出力リクエストを実行するために復号レイヤおよび解凍レイヤを含むふたつの処理のレイヤを作成する。この例では、転送されるデータはアプリケーションに受信可能となる前に解凍される必要があり、また解凍可能となる前に復号される必要がある。木構造レイヤ３０１は、転送されるデータを処理のレイヤに依存しているチャンク（例えば、データの一部分）に解体する。具体的には、木構造３０１はデータをあるサイズのチャンクに細分化するための命令を生成する。そのサイズは、データ全体についてあるレベルの処理が終わるまで次の処理レベルが待機しなくてはならないのではなく、データの一部分が同時に処理されるように選択される。所与のチャンク用の各命令は、パスネーム、オフセット、および長さによって定義されてもよい。
【００３０】
例えば、復号は固定の６４Ｋのチャンクのサイズで達成できるので、木構造レイヤ３０１は復号用にはデータを６４Ｋのチャンクに分解する。しかし、解凍は様々なサイズのチャンクで処理されるので、木構造レイヤは解凍用には様々なサイズのチャンクに分解する。
【００３１】
解凍（デアーカイバ（de-archiver）変換）処理は様々なサイズの圧縮および復号されたチャンク取り入れてそれを解凍し、固定サイズの圧縮されていないチャンクにする。木構造レイヤ３０１またはメディアフィルタレイヤ３０５は、圧縮されかつ復号されたデータのどの可変サイズのチャンクが、それらを解凍することなく固定サイズのチャンクに解凍されるかを決定するように構成されてもよい。チャンキングの時点で暗号化されたチャンクの様々な長さを決定することを容易にするために、メディアフィルタレイヤ３０５（これは最終的にどのチャンクが生成されるかを決定する）は、所与のチャンクのサイズおよび格納場所を計算するために必要な情報は何でもＲＡＭの中に格納してもよい。例えば、ファイル入出力システムのpsarcファイル用に、デアーカイバレイヤはpsarcファイルの目次（table of contents: TOC）をＲＡＭに保持してもよい。目次はファイル中の全ての圧縮されたブロックのサイズを並べたテーブルを含んでおり、デアーカイバメディアレイヤはそこからブロックの格納場所を引き出すことができる。このため、デアーカイバは圧縮されていないデータブロック用の着信リクエストを、対応する圧縮されたデータブロック用のリクエストに効率的に翻訳することができる。デアーカイバがこの翻訳をするために必要な唯一の情報は目次であり、この目次はＲＡＭの中にある。デアーカイバは木ノードを作成するために、何のデータも実際に読んだり解凍したりする必要がない。
【００３２】
復号レイヤのチャンクのサイズおよび解凍レイヤのチャンクのサイズは列挙されていないので、所与の復号されたチャンクは、常にはすぐに解凍されなくてもよい。その代わり、１以上の復号レイヤのチャンクが、解凍レイヤのチャンクが解凍されるのが開始される前に復号される必要がある。その後、処理の最適な順序が、各レイヤに関連づけられたチャンクの格納場所や異なるレイヤのチャンク間のデータ依存関係が決定されることによって確立される。このように、あるレイヤの全体の処理が完了するまでそれに続くレイヤの処理が待つのではなく、先のレイヤ内の必要なデータのチャンクが処理されるとすぐに続くレイヤの処理が開始される（例えば、ひとたび復号レベルのチャンクが復号されるのが終了すれば、所与のチャンクの解凍が開始する）。
【００３３】
ときには、入出力リクエストは１またはそれ以上のメディア／ストレージデバイスからデータが読み出されることを要求する。そのため、実行に先立ってデータ依存関係を決定することにより、あるメディア／ストレージデバイスがそれ自身の入出力リクエストの一部を処理する一方で別のメディア／ストレージデバイスが何もしないでいるというのではなく、多数のメディア／ストレージデバイスからのデータを伴う入出力リクエストの処理が同時に行われる。限定されるわけではないが、例として、所与の入出力リクエストはハードディスク（hard disk: HD）とＢｌｕ−ｒａｙ（登録商標）メディアデバイスとの両方からデータを読み出すことを要求してもよい。所与の入出力リクエスト用のデータ依存関係の要点をまとめることにより、ハードディスクからは何が本当に必要で、Ｂｌｕ−ｒａｙ（登録商標）からは何が本当に必要なのかが決定される。このように、木構造がそれを許容範囲であると決定すると、一方のデバイスが処理されているときにもう一方のデバイスが何もしないというのではなく、両方のデバイスからのデータが同時に処理される。
【００３４】
ひとたび木構造３１３が生成されると、スケジューラ３０３は着信する入出力リクエストを構成する木構造の命令をメモリ内に実体化されたスケジュールに挿入する。所与の命令のスケジュール内の位置は、少なくとも部分的には機構造３１３に関連した処理の順序に依存する。
【００３５】
スケジュール内の２またはそれ以上の入出力リクエストが類似の木構造３１３を含む場合、１またはそれ以上リクエストが同時に処理されるようにこれらの入出力リクエストはインタリーブ（interleave）される。各入出力リクエストの処理が完了するまで次の処理の開始を待つのではなく、関連する入出力リクエストが同時あるいは重複するタイミングで完了するため、入出力リクエストの実行の効率が改善される。例えば、ある実施の形態では、木構造３１３の命令とインタリーブされた他の入出力リクエストからの１またはそれ以上の命令は、その木構造３１３の命令の実行と同時に実行される。
【００３６】
限定されるわけではないが、例として、スケジューラ３０３がもし入出力リクエストがインタリーブされればそれがより早く処理されると決定した場合、入出力リクエストはインタリーブされてもよい。
【００３７】
第１の例では、ふたつのパッチの当てられた読み込みが同時に実行されることを仮定する。ファイルＡは５つのチャンク（Ａ１）（Ａ２）（Ｐ１）（Ａ３）（Ｐ２）を必要とする。ファイルＢは４つのチャンク（Ｂ１）（Ｐ３）（Ｂ２）（Ｂ３）を必要とする。このケースで「Ｐ」はパッチファイルを意味し、「Ａ」および「Ｂ」はオリジナルのデータファイルを意味する。ディスク上のレイアウトは以下のようになる。
・・・（Ａ１）（Ａ２）（Ａ３）・・・（Ｂ１）（Ｂ２）（Ｂ３）・・・（Ｐ１）（Ｐ２）・・・
【００３８】
ディスク上のファイルの近接度から、スケジューラ３０３は、最小の探索で両者の読み込みを終了するための最速の方法はＡ１−Ａ３をまず読み込み、次にＢ１−Ｂ３、その次にＰ１−Ｐ３を読み込ことによってリクエストをインタリーブすることを決定するであろうことに留意する。
【００３９】
第２の例では、スケジューラ３０３は第１の読み込みリクエストと、第２の高優先度かつ低いレイテンシの読み込みリクエスト（例えば、オーディオリクエスト）とをスケジューリングしたと仮定する。ファイル入出力システム１０１は、下記の表１に表されるように第１の読み込みのチャンクから取り組みを開始する。表１では、チャンクは時間とともに左に移動する。キューから開始し、実行に移動し、最終的に完全に終了する。
【００４０】
【表１】
0005292473.tif 000002
Ａ３の実行が開始した後、キューは下記の表に示したように見える。
【００４１】
【表２】
0005292473.tif 000003
【００４２】
オーディオスレッドが到着して突然（Ｂ１）および（Ｂ２）の読み込みを必要とすると仮定する。オーディオリーダが即時のサービスを要請したとすると、スケジューラ３０３はキューの先頭に（Ｂ１）および（Ｂ２）の読み込みを置く。キューは下記の表３のようになるであろう。
【００４３】
【表３】
0005292473.tif 000004
【００４４】
最終的にキューのこの部分の実行が終了すると、表４に示すように、入出力はふたつの読み込みリクエストのためにインタリーブされたことがわかる。
【００４５】
【表４】
0005292473.tif 000005
【００４６】
デバイスメディアレイヤ３０７（時にはメディアアクセスレイヤと呼ばれる）は上述のメディアフィルタレイヤ３０５から受信したメディアリクエストに応答し、クエストされたデータを読み出し、スタック３００にその応答を送り返すように構成されてもよい。
【００４７】
メディアフィルタレイヤ３０５は、パッチャ３２２、デアーカイバ３０８、ＲＡＭキャッシュレイヤ３１０、スケジューラキャッシュレイヤ３１２、オーバーレイレイヤ３１４、カタログキャッシュレイヤ３１６、暗号化／復号レイヤ３１８、および圧縮／解凍レイヤ３０６を含んでもよい。これらのメディアフィルタレイヤ３０５は、木構造３１３に関連づけられた処理レイヤ３０６に対応する。入出力リクエストに関連づけられた所与のデータの一部は、データに関連づけられたメディアフィルタレイヤの数に依存している多数の処理レイヤを持っていてもよい。デアーカイバ３０８は、圧縮されたアーカイバから特定の有用なファイルを抽出することを手助けするのに用いられてもよい。ＲＡＭキャッシュレイヤ３１０は、例えばメインメモリ内等にデータをキャッシュすることを実装するために用いられてもよい。スケジューラキャッシュ３１２は、光学ディスクのようなより遅いソースからのデータを一時的に格納するための、単純なディスクからディスクへの（disc-to-disc）キャッシュであってもよい。本明細書で用いられているように、「スケジューラキャッシュ」という用語は、メディアデバイスへのアクセスよりも速いアクセスであるストレージメディア内への一時的なデータの格納をいう。スケジューラキャッシュ３１２内の全てのデータがプリフェッチされる必要はなく、いくらかは要求に応じて読み出されてキャッシュ内にコピーされてもよい。限定されるわけではないが、例として、スケジューラキャッシュレイヤ３１２は、そのような一時的な格納場所を生み出すために高速ストレージメディアを利用する。高速ストレージメディアがハードディスクドライブ（hard disk drive: HDD）である特別なケースでは、スケジューラキャッシュ３１２はときにハードディスクドライブキャッシュと呼ばれる。
【００４８】
スケジューラキャッシュ３１２は、単一のファイルまたは多数のファイルとして保持されてもよい。加えて、スケジューラキャッシュ３１２のコンテンツは、欠ける部分のない全体のファイルである必要はない。多数のファイルのキャッシュは、多くのデータを犠牲にすることなく必要なときにインテリジェントにディスクスペースを空けるために、いくつかの個々のファイルを消去することによって部分的に消去されてもよい。対称的に、単一ファイルのキャッシュは、典型的には切り捨てられるかあるいは完全に消去される。複数ファイルのキャッシュは典型的には追加の帳簿作業（bookkeeping work）を要求するため、単一ファイルのキャッシュは複数ファイルのキャッシュよりも高いパフォーマンスを提供する。帳簿作業は追加の入出力を要求し、ホストファイルシステム自体の内部で行われる。
【００４９】
オーバーレイレイヤ３１４は、以下で述べられるように、ファイルシステムレベルにおいてファイルおよびディレクトリの任意のオーバーレイを可能にするために用いられてもよい。カタログキャッシュレイヤ３１６は、プロセッサユニットまたはセルプロセッサのためのオペレーティングシステムが適切にキャッシュしないであろうキャッシュデータ（例えばファイルの存在やサイズ、格納場所等）として用いられてもよい。暗号化／復号レイヤ３１８は、転送用にデータの暗号化または復号を容易にするために用いられてもよい。圧縮／解凍レイヤ３２０は転送用にデータの圧縮または解凍を容易にするために用いられてもよい。
【００５０】
木構造レイヤ３０１およびファイル入出力プログラム１０１のスケジューラ３０３の演算は、以下に述べられる図４を参照することで理解されよう。クライアントからの視点では、入出力リクエスト４０３は比較的直接的な方法で実行される。例えば、ビデオゲームのようなアプリケーション４０１内のスレッド４０２は、関数（例えば、readFile()）を呼び出すことによってファイル入出力プログラム１０１を通して入出力をリクエストしてもよい。関数は、入出力リクエスト４０３およびリクエスト４０３が完了されるべき期限を特定してもよい。続いて、ファイル入出力メディアスタック３００は、入出力リクエスト用の処理の最適な順序を規定するマップを形成する入出力リクエスト４０３用の木構造３１３を生成するために、木構造レイヤ３０１を使用する。
【００５１】
はじめに木構造は、所与の入出力リクエスト４０３に関連づけられた処理のレベル３０６を規定する。例えば、所与の入出力リクエスト４０３は、プロセッサからメディアデバイスへのデータの転送を要求してもよい。ここで、データは圧縮され、暗号化され、およびアーカイブされることを必要とすることとする。このような状況において、木構造３１２３は、入出力リクエスト４０３に関連づけられたデータの圧縮、暗号化、およびアーカイブのための処理の３つのレベル３０６を規定するであろう。所与のデータの一部分は暗号化される前に圧縮されなければならず、アーカイブされる前に暗号化されなければならず、かつ最終的にメディアデバイスに転送される前にアーカイブされなければならない。
【００５２】
木構造３１３は続いて、処理のレベル３０６にしたがって転送されるデータをチャンク３０２に分解する（例えば圧縮のレベルにおいてはデータは６４Ｋに分解され、暗号化のレベルにおいてはデータは様々なサイズに分解され、アーカイブのレベルではデータは６４Ｋに分解される）。所与の任意のレベルまたは異なるレベルのデータの一部が、次の処理のレベル３０６が開始する前に、リクエスト内の全てのデータがある処理のレベル３０６を終了するまで待機しなければならないということではなく、同時に処理されるように、データはチャンク３２０に分解される。ある処理のレベル３０６のチャンク３０２は、他の処理のレベル３０６のチャンク３０２を用意する必要はないので、異なる処理のレベル３０６に関連づけられたチャンク３０２のデータ依存関係３０４は、入出力リクエスト４０３の処理の無駄をなくす（streamline）ためにマッピングされなければならない。例えば、所与の圧縮レベルのチャンクは、圧縮が終了したらすぐに暗号化を始めなければならないとは限らないであろう。暗号化のレベルは様々なサイズで処理されるので、暗号化レベルのチャンクが暗号化を始める前に、２またはそれ以上の圧縮レベルのチャンクが圧縮されなければならないかも知れない。それ故、木構造３１３は、所与の入出力リクエスト４０３の処理を最適化するために、これらのデータ依存関係３０４を決定する必要がある。さらに、入出力リクエストが多数のメディア／ストレージデバイスからデータを読み出すことを要求するとき、木構造３１３に要約された（outline）データ依存関係３０４はあるメディア／ストレージデバイスが何も動作していない間に他のメディア／ストレージデバイスからのデータを処理させるのではなく、異なるメディア／ストレージデバイスからのデータの同時処理を可能にする。
【００５３】
木構造３１３に関連づけられた最終的な生成物は、所与の入出力リクエスト４０３のための処理の最適な順序を規定するマップである。入出力リクエストのスケジュールの最適化に関わらず、各入出力リクエスト４０３は、可能な限り短い時間で完了するように木構造３１３によって個別に最適化されている。この入出力リクエスト４０３および関連する木構造３１３は、効率的なスケジューリングのためにスケジューラ３０３に入力される。
【００５４】
入出力リクエストに関連づけられたデータは、上述したふたつのレイヤよりもさらに多くの処理のレイヤを持っている点は注意しなくてはならない。木構造は入出力リクエストを実際に処理するのではなく、個々の入出力リクエストが最適に処理されるようにマップを生成するだけである。
【００５５】
限定されるわけではないが、例として、入出力リクエストは木構造に分解され、その木構造内で、リクエストの処理が行われる各レイヤにおいて各データのチャンクは対応する命令によって扱われる。木構造のレイヤ内の所与の命令は、ひとつ前のレイヤからの１またはそれ以上の命令を指示する関連したデータ依存関係を持っており、その命令が開始される前にひとつ前のレイヤは完了しなければならない。
【００５６】
表５は、入出力リクエスト用の木構造の例を示す。表１では、各命令はパスネーム、オフセット、およびキロバイト（kilobytes: KiB）単位での長さによって特定されるデータを使用する。この例では、木構造内におけるレイヤの処理の順序は下から上に向かう。しかしながら、木構造内の命令はデータ依存関係を満たす限り同時に実行されてもよい。表５において、所与の命令の依存関係は、実行を始める前に完了しなければならない下位のレイヤの命令がどれかを示している。この例では、パスネームは/dev_（参照するメディア）から始まっている。具体的には、/dev_hdd0および/dev_hdd1はハードディスクドライブを意味し、/dev_bdvd0は高精細デジタルビデオドライブ（high-definition digital video drive: DVD）を意味する。/dev_（参照するメディア）から始まらないパスネームは、他の命令によって読み出されるデータから構成される仮想ファイルを意味する。
【００５７】
【表５】
0005292473.tif 000006
0005292473.tif 000007
0005292473.tif 000008
【００５８】
表５に示される例では、入出力リクエストはＤＶＤからのファイル用である。この例において木構造内の個々のレイヤは「ボトムアップ」の順序で実行される。これは、最下層のレイヤ内の命令のうち少なくともいくつかは、データ依存関係のために最初に実行されなければならないことを意味する。本明細書において、「最下層のレイヤ」という用語は、それよりも前の（下位の）レイヤが存在しない、構造におけるレイヤを意味する。それよりも前（または下位の）レイヤがないことによって、最下層のレイヤ内の命令はいずれも、異なるレイヤ内の命令の実行が先立って完了することを要求するデータ依存関係を持たないことを意味する。しかしながら、最下層のレイヤ内の１またはそれ以上の命令が最下層レイヤ内の他の命令の実行が先立って完了することを要求するデータ依存関係を持つことは可能である。上述の表１に関して記載した例において、最下層のレイヤはハードディスクキャッシュレイヤである。表５における命令の処理の正確な順序は、ある程度ハードディスクキャッシュレイヤ内の命令におけるデータ依存関係に左右されうる。例として、表５におけるハードディスクキャッシュレイヤ内の最後の入出力リクエストは、下記の表６に示される実行の順序でdevice/partition内に格納される。
【００５９】
【表６】
0005292473.tif 000009
【００６０】
表６内の命令は、（※）で示された依存関係を伴うものは例外として、同時に発行されうる。（※）で示された依存関係を伴う命令は、スケジューラ３０３によって格納されかつ発送されてもよい。具体的には、書き込み命令の９４番、読み込み命令の７７、７９、８１、８３、８５、８７、８９、９１、および９３番はデータ依存関係を持たないので、これらの命令は、同時にどのような順序で実行されてもよい。書き込み命令７８、８０、８２、８４、８６、８８、９０、および９２番は、それぞれ最初の番号における書き込み命令９４および読み込み命令７７、７９、８１、８３、８５、８７、８９、９１、および９３にそれぞれ依存する。その結果、これらの各書き込み命令は、９４番の書き込みおよび対応する読み込み命令が実行されるまで待たなければならない。
【００６１】
上述の表１に示された木構造内の残りの命令は、データ依存関係を満たす限り同時に実行されてもよい。入出力リクエストを受信した後即座に生成される木構造内にデータ依存関係を含めることにより、木構造の所与のレイヤ内の各命令は、それらの命令のデータ依存関係の要求を満たすとすぐに実行できることは重要である。この結果、各命令のデータ依存関係が満たされる限りふたつの異なるレイヤの命令を同時に実行することが可能となる。それ故、ひとつのレイヤにおける命令はその前のレイヤ内の全ての命令が完了するのを待機する必要がない。
【００６２】
例えば、入出力リクエストの命令０を実行するため、パッチャ命令１、２、３、４は最初に完了されなければならない。パッチャ命令４が実行可能となる前に、デアーカイバ命令１２および２０〜２５のみが完了されなければならない。デアーカイバ命令２５が実行可能となる前に、解凍命令４６のみが完了されなければならない。解凍命令４６が開始可能となる前に、ＲＡＭキャッシュ命令５５のみが完了されなければならない。ＲＡＭキャッシュ命令５５が開始可能となる前に、復号命令６４のみが完了されなければならない。復号命令４６が開始可能となる前に、オーバーレイ命令７３のみが完了されなければならない。オーバーレイ命令７３が開始可能になる前に、ハードディスクキャッシュ命令９７のみが完了されなければならない。
【００６３】
ひとたび入出力リクエスト４０３が木構造レイヤ３０１を通過し、その特定の入出力リクエスト用の処理の順序が決定されると、入出力リクエスト４０３はスケジューラ３０３によって受信キュー４０４内に移される。例として、受信キュー４０４はＦＩＦＯ（first-in-first-out）キューであり、キュー４０４内に最初に置かれたリクエストが、スケジューラ３０３によって最初にスケジューリングされるリクエストである。受信キュー４０４内へのリクエスト４０３の挿入は、非同期の入出力を要求するときにスレッドがブロックされることを防ぐために、アトミックな操作（atomic operation）によって実装されてもよい。ある実施の形態では、受信キュー４０４は、アトミックな交換（atomic exchange）とともに補助プロセッサ１０５Ｂにしたがうアトミックなスタック（atomic stack）の形態であってもよい。
【００６４】
限定されないが、例として、入出力リクエスト４０３が読み込み命令の場合、クライアントアプリケーション４０１はメディアデバイスから読み込んだデータを受信するためのバッファ４０５を提供してもよい。入出力リクエスト４０３が完了したとき、クライアントアプリケーション４０１は提供したブッファ４０５から読み出されたデータを読み込んでもよい。クライアントが入出力リクエスト４０３の処理を終了したとき、クライアントは、将来の入出力での使用においてリソースが利用可能となるように、バッファ４０５の割り当てを解除（de-allocate）してもよい。
【００６５】
入出力リクエスト４０３は、スケジューラ３０３がまだ起動していない場合、スケジューラ３０３を起動してもよい。その後、アプリケーション４０１は入出力リクエスト４０３が完了するまで待機してもよい。例えば、クライアントアプリケーション４０１は、アトミックなメソッド（atomic method、例えばisDone()）を用いて周期的にポーリングしてもよい。もう一つの方法としては、クライアントは、入出力リクエスト４０３が完了したときにファイル入出力プログラム１０１が呼び出すコールバック関数４１１を待ってもよい。
【００６６】
受信キュー４０４内に入出力リクエスト４０３が挿入された後に、ファイル入出力プログラム１０１はスケジュール挿入４０７を実行するためにスケジューラ３０３を呼び出してもよい。スケジューラ３０３によって実装された演算の順序は図５を参照することで理解されるであろう。５０２で示すように、スケジューラ３０３は、扱うべき入出力がない場合、スリープ（例えば、依然として起動していない）状態であってもよい。新しい入出力リクエスト４０３が受信キュー４０４に入ると、スケジューラ３０３はスリープを解除してそれを扱う。ひとたびスケジューラ３０３がスリープを解除（あるいは既に解除）すると、受信キュー４０４内の新しいリクエスト４０３に気づいて、そのリクエストをスケジューリングキュー４０６内の適切な場所に移動する。
【００６７】
５０３に示すように、入出力リクエスト４０３のキューの位置を決定するために、スケジューラ３０３はオプションとして、例えばデバイスメディアレイヤ３０７やファイル入出力システムのメディアスタック３００内の他のレイヤに問い合わせることにより、メディアデバイスの現在の状態を決定してもよい。状態データは、ファイル入出力システムのメディアスタック３００およびスタック３００内にある様々なレイヤによって扱われるメディアデバイスの種類に依存して変わりうる。例としては、もっとも最近にアクセスされた論理ブロックアドレス（logical block address: LBA）、ＲＡＭキャッシュの最後にアクセスされたパスおよびオフセット、現在のディスクレイヤ、先頭の位置、ストリーミングのモード、およびストリーミングではないモード（non-streaming mode）が含まれる。
【００６８】
本発明の実施の形態によれば、スケジューラ３０３はメディアデバイスのパフォーマンスモデル３０３Ａに基づいてもよい。現存の入出力スケジューラとは異なり、ドライブモデル（drive model）３０３Ａは、リクエスト４０３の最適なスケジュールを決定する際にメディアデバイス１１８のパフォーマンスに関するデータを考慮に入れる。ドライブモデルを用いて入出力リクエスト４０３をスケジューリングすることは、ＣＤを生成するマスタ処理の逆と比較されてもよい。パフォーマンスモデル３０３Ａは、オーバーヘッド、ディスクの移動時間、読み込み時間、およびそれと同様のもののような要素を考慮するように構成されていてもよい。パフォーマンスモデル３０３Ａは、スループット、レーザの細かな揺れ（wiggles）、読み取りヘッドの動き、レーザの変更、およびリクエストのオーバーヘッドのようなメディアデバイス１１８の任意の複雑な特性をモデル化してもよい。パフォーマンスモデル３０３Ａはまた、入出力リクエスト４０３によって引き起こされたメディアデバイス１１８によって読み込まれたり書き込まれたりする特定のメディアの他のパラメータを考慮に入れてもよい。例えば、パフォーマンスモデル３０３Ａは、デバイスが単一のレイヤのディスクを読み込んでいるのか、あるいは多数のレイヤのディスク（例えばＢｌｕ−ｒａｙ（登録商標）ＤＭＤのような二重のレイヤのディスク）を読み込んでいるのかを考慮してもよい。
【００６９】
５０４に示されるように、スケジューラ３０３はオプションとして、新しい入出力リクエストのタイミング（例えば期限）および優先度を調べてもよい。５０６に示されるように、スケジューラはオプションとして、インタリーブするために受信キュー４０４内の入出力リクエストとスケジュールキュー４０６内の入出力リクエストとを比較するように構成されていてもよい。受信キュー４０４内の所与の入出力リクエストの木構造３１３によって要約されたデータ依存関係３０４は、スケジュールキュー４０６に既に入っている１またはそれ以上の入出力リクエストの木構造３１３によって要約されたデータ依存関係との重複を持っていてもよい。例えば、受信キュー４０４内の入出力リクエストは所与のメディアデバイスからのデータのチャンクを読み出す必要があるであろうし、スケジュールキュー４０６内の入出力リクエストは同じメディアデバイスからのデータの近隣のチャンクを読み出す必要があるかも知れない。それ故、これらふたつの入出力リクエストをインタリーブすることによって、それらの入出力リクエストを処理することの効率が改善しうる。インタリーブは、ふたつの所与の木構造３１３間における重複の閾値（threshold overlap value）を設定し、かつ重複の閾値を満たすときこれらの木構造３１３に関連づけられたふたつの入出力リクエストをインタリーブすることによって実行される。もし２またはそれ以上の入出力リクエストがインタリーブされると、スケジューラはスケジュール間の単一のリクエストとしてこれらのインタリーブされたリクエストを扱ってもよい。
【００７０】
ひとたびいずれかの入出力リクエストをインタリーブするか否かが決定されると、スケジューラ３０３は、５０７に示されるように、現在の入出力リクエスト用に最適なキュー配置を決定してもよい。スケジューラ３０３はスケジュールキューの任意の位置に受信入出力リクエストを置くことから始めてもよい。優先条件と同様に、スケジュール全体を完了するために必要な合計時間および期限の制限がスケジュールキューの試行錯誤を用いて決定される。５０７に示されるように、この処理は最適なスケジュールキューの順序が決定されるまで、異なるキューの順序で反復して繰り返されてもよい。リクエスト４０３用の初期の状態は、スケジュールの順序におけるひとつ前リクエストの最終の状態から決定され、またスケジュールの順序における次のリクエストの初期の状態はリクエスト４０３の最終の状態から決定されることに注意する。
【００７１】
スケジューラ３０３は、スケジューリングキュー内のリクエストを検証して、既にキュー内にあるリクエストに対してリクエスト４０３の特性を比較する。スケジューラ３０３は、キュー内におけるリクエスト４０３の考え得る各位置を試し、優先度を無視していること、期限を過ぎること、およびタイミングの判断を探す。スケジューラ３０３は、リクエストされた入出力操作がいずれも期限を過ぎない順序を探すことによって、考え得る最適な新しいキューの順序を決定してもよい。もし１またはそれ以上のリクエストが絶対に期限を途過するという場合、スケジューラは異なる基準を用いてキューの順序を決定してもよい。スケジュールキュー４０６内のリクエストの順序に影響を与える追加の基準は、限定はされないが、入出力リクエストの優先度、ストリームバッファの状態、要求されるレイテンシ、および異なる入出力リクエストの木構造間における重複するデータ依存関係を含んでもよい。
【００７２】
ある実施の形態では、例えば期限が全て解決できない場合、優先度が使用される。例えば、ある期限が否応なく途過する場合、最良のキューの順序は、最も優先度の低いリクエストがその期限を途過する順序であろう。前述の考察を満たす多数の可能なキューの順序がある場合、同じ優先度である期限を途過するリクエストの数が最小となるキューの順序が最良の順序であろう。前述した考察を全て満たす多数の可能なキューの順序がある場合、可能な限り少ない時間で全てのキューを実行するキューの順序が最良の順序であろう。いくつかの場合、高い優先度のリクエストが期限に間に合う限りにおいて、低い優先度のリクエストは高い優先度のリクエストの前にスケジューリングされてもよい。
【００７３】
前述した考察を全て等しく満たす多数の可能なキューの順序がある場合、スケジュールキュー４０６内の最新のリクエストはキューの末尾に来る順序が最良のオーダーであろう。
【００７４】
ひとたびスケジューラ３０３がリクエスト４０３を満たすためのスケジュールキュー４０６内の最適な位置を決定すると、図４の４０７および図５の５０８に示されるように、リクエストはそこに挿入される。図４を再び参照すると、もし入出力リクエストを実行可能なリソースが存在すれば、４０９に示されるように、スケジューラ３０３はスケジュールキュー４０６内の最初のリクエストを発行キュー４０８に移動する。続いて、リクエストは発行キュー４０８から実行される。所与の入出力リクエスト４０３を実行するために、スケジューラ３０３は、所与のリクエスト４０３に関連づけられた木構造３１３と同様に、ファイル入出力システムメディアスタック３００内の最初のレイヤに至るまでリクエスト４０３を通過する。
【００７５】
スケジューラ３０３以下の各レイヤは、入出力リクエスト４０３および対応する木構造が上位のレイヤを通り抜けたように見える。適切な場合、レイヤはリクエストに関連づけられたデータのチャンク３０４を処理する。各レイヤは、リクエスト４０３に関連づけられた木構造３１３にしたがってリクエスト４０３を処理し、可能な限り最も効率的な方法でリクエストが処理されるようにする。限定されないが、例えば、リクエストが読み出し操作の場合、デアーカイバレイヤ３０８は開かれているアーカイブのコンテンツに対して与えられたパスネームを確認し、もしファイルを見つけた場合、圧縮されたデータの読み込みの中にリクエストを再マッピングしてもよい。ファイル入出力システムメディアスタック３００の各レイヤは、リクエストが最終的にハードウェアレイヤ３１０に到達するまで、処理されたあるいは処理されていない入出力リクエストを飛ばして次の下位のレイヤに進む。ハードウェアレイヤ３１０がリクエストに応答するとき、その応答はメディアスタック３００内の各レイヤを下から上に向かって進み、各レイヤは適切な場合読み出したデータのチャンク３０２を処理してもよい。例えば、解凍レイヤは返されたデータのチャンク３０２は解凍されなければならないことを知っているので、応答がスタック３００を上部に帰る前に解凍する。応答は最終的にスケジューラ３０３に戻る。
【００７６】
読み出されたデータがスタック３００に戻るとき、スケジューラ３０３がそれを受信して入出力リクエスト４０３を完了キュー４１０に移動する。完了キュー４１０はアプリケーション４０１へのコールバック関数の契機となる（コールバックがアプリケーションによって設定されている場合）。別の方法として、アプリケーション４０１は入出力リクエスト４０３が完了したか否かを決定するためにファイル入出力システムメディアスタック３００をポーリングしてもよい。ひとたび入出力リクエスト４０３が完了すると、解放入出力プール４１２に移動される。解放入出力プール４１２は使用済みとなった入出力リクエストのセットを含む。そのようなリクエストは、クライアントアプリケーション４０１に割り当てられていなかったリクエストやクライアントアプリケーション４０１によって使用され再び使用するために解放されたリクエストを含んでもよい。クライアントアプリケーション４０１が入出力リクエスト４０３を行うと、スケジューラ３０３はこのプール４１２からクライアントに入出力リクエストを割り当てる。解放入出力プール４１２はスタックとして実装されてもよい。解放入出力リクエストは解放入出力プール４１２からポップされ、受信キュー４０４にプッシュされる。このように、解放入出力リクエストは再利用される。
【００７７】
本発明の実施の形態によれば、スケジューラ３０３は以下のようにスケジュールループを動作する。
１．入出力の完了を調べる。
２．新しい入出力リクエストを発行する。
３．入出力コールバックを発行する（もしあれば）。
４．スケジュールに挿入する（受信からスケジュールに挿入する）。
５．再度新規に発行する。
６．予想される期限の途過を調べる。
７．１に戻る。
各反復におけるスケジュールの挿入の数は、ある最大数（例えば１６）で制限されていてもよい。
【００７８】
本発明のある実施の形態では、補助プロセッサユニット１０５Ｂ（例えばＳＰＥ２０６）が、受信する入出力用のリクエストを、メインプロセッサ１０５ＡまたはＰＰＥ２０４に関してアトミックな交換を通じて受信キュー４０４に追加することによって、自分自身に入出力をリクエストすることができる。例えば、従来型のセルプロセッサの実装において、ＳＰＥ２０６はいずれの入出力能力も持っていない。しかしながら、受信キュー４０４が共通のデータ要素である場合、補助プロセッサ１０５Ｂは、メインプロセッサ１０５との標準的なアトミックな交換およびメインプロセッサ１０５に通知することを通じて、入出力リクエストをキューに追加することができる。
【００７９】
多くの従来技術における実装では、補助プロセッサ１０５Ｂが即時に処理するデータを必要とする場合、そのデータはメインメモリになければならない。これとは対称的に、本発明の実施の形態では、補助プロセッサ１０５Ｂはファイル入出力システムメディアスタック３００に、ハードメディアデバイス１１８やネットワーク１２７を介して得た所望のデータを取りに行かせる。
【００８０】
限定するわけではないが、例として、受信キュー４０４、完了キュー４１０、および解放入出力プール４１２はアトミックなスタックであってもよい。補助プロセッサ１０５Ｂは解放入出力プール４１２から入出力リクエストをポップし、入出力リクエストのパスを書き込み、受信キュー４０４にリクエストをプッシュし、さらに同期の実行とスケジューラ３０２をウェイクアップする。補助プロセッサ１０５Ｂは入出力リクエストの完了のための間欠的なポーリングの間に別の仕事を行ってもよい。
【００８１】
例として、セルプロセッサシステム２００内において、入出力リクエストはＳＰＥ２０６によってサービスされる。ＳＰＥ２０６によってリクエストされたデータは、ＰＰＥ２０４によってアドレス可能な場所であればどこでも送信される。ＳＰＥ２０６がロックされている場合、ファイル入出力システムメディアスタック３００はＳＰＥ２０６のローカルストア（local store: LS）にデータを直接書き込むことができる。ある実施の形態では、ひとつのＳＰＥ２０６は解凍レイヤに対して他のＳＰＥが解凍するようリクエストしてもよい。これは例えばプロセッサ間の遠隔手続呼び出し（remote procedure call: RPC）を用いて実装されてもよい。この例では、ＳＰＥ２０６がＰＰＥ２０４に何かをするように要求する。より従来型の遠隔手続呼び出しではこれと逆である。
【００８２】
ある実施の形態では、スケジューラキャッシュレイヤ３１２（例えばハードディスクキャッシュ）は、ファイルが後に素早く読み出せるように、メディアデバイス１１８からのファイルをストレージデバイス１１５内のキャッシュ１１７にプリフェッチするために用いられる。そのようなケースでは、プリフェッチ操作４１３は発行キュー４０８に直接挿入されてもよい。プリフェッチは、ＰｏｗｅｒＰＣのＣＰＵアーキテクチャにおける「dcbt」命令のような多くの種類のキャッシュによって実装される標準的な手動プリフェッチであってもよい。本発明の実施の形態によれば、プリフェッチは上述のスケジューラループの一部としてキューに入れられ、かつ実行されてもよい。プリフェッチは、比較的高いレイテンシでかつ低いスループットを伴う、他の入出力リクエストが完了しているときにアクセスされなければならない比較的遅いソースメディア（例えばＢｌｕ−ｒａｙ（登録商標）やＵＭＤ）の仕事の手助けをする。
【００８３】
スケジューラ３０２は、メディアデバイス１１８がアイドル状態で、かつ他の入出力リクエストを邪魔しない、使用されていない時期にのみ実行するような、比較的低い優先度のプリフェッチを実装するように構成されてもよい。例えば、システム１００は遅いメディアデバイス（例えばＢｌｕ−ｒａｙ（登録商用）ディスク（ＢＤ）のような光学ディスク）と、ハードディスクのようなより高速なストレージデバイス１１５とを持っているとする。スケジューラキャッシュレイヤ３０５は  光学ディスクドライブからハードディスクへの非同期なコピーのために用いられてもよい。ファイルが後にアクセスされるとき、入り低速な光学ディスクのスピード（例えば８ＭｉＢ／ｓ）の代わりに、より高速なハードディスクドライブのスピード（例えば２０ＭｉＢ／Ｓ）で読み込まれる。
【００８４】
キャッシュプリフェッチは通常ハードディスクキャッシュで行われるが、プリフェッチはメインメモリ１０６、２０２で行われてもよい。プリフェッチリクエストは、スケジューリングが完了した後に受信された順序でスケジュールキュー４０６の末尾に含まれてもよい。ある実施の形態では、プリフェッチリクエストは、必要なときに遅延されてもよい。プリフェッチリクエストは他の入出力リクエスト４０３と同様の方法ではスケジューリングされない。プリフェッチリクエストは、スケジュールキュー４０６がからのときのみ実行される別個のプリフェッチキュー４１３に保管される。プリフェッチリクエストは必要があれば遅延されてもよい。そうでなければ、プリフェッチは受信された順序で完了されてもよい。スケジューラ３０３はプリフェッチリクエストを並ばせて保持し、入出力サブシステムが特定の長さの時間だけアイドル状態であるときにのみそれらのプリフェッチリクエストを実行する。これにより、プリフェッチリクエストが通常の入出力リクエストを邪魔するのを防ぐ。加えて、プリフェッチは単一のキャッシュブロックには限定されず、任意のサイズでよく、キャッシュにファイルのはじめから最後まで全体をロードすることを伝える特別な「全ファイル（whole-file）」値を渡してもよい。さらに、プリフェッチは任意のサイズでよいが、プリフェッチは、ファイル入出力システムメディアスタック３００がアイドル状態を継続しているかを調べるためにスケジューラ３０３に戻る前には、せいぜいひとつのキャッシュブロックしか満たされないように実装されてもよい。
【００８５】
キャッシュプリフェッチは、ビデオゲームや入出力駆動型（I/O driven）のアプリケーションの入出力や、現代的なビデオゲームコンソールのような特殊な入出力を要するプラットフォームにおける入出力のパフォーマンスを向上しうる。特に、ゲームデータはしばしば光学ディスクやネットワークファイルサーバのような低速なメディアに格納されるが、ゲームはハードディスクドライブのような高速なローカルストレージからアクセスしうる。
【００８６】
本発明の実施の形態は、かなりの量の入出力を用いるアプリケーションやシステムにおける向上した入出力パフォーマンスを提供する。上述したように、本発明の実施の形態はビデオゲームアプリケーションおよびビデオゲームシステムで特に有用である。しかしながら、本発明の実施の形態はそのようなアプリケーションやシステムに限定されない。
【００８７】
上述した実施の形態の変形例もまた、本発明の実施の形態の範囲内である。例えば、ある実施の形態では、パッチャレイヤ３２２によってファイルにパッチを当てることは、実行時に適用されるバイナリの差分パッチ（バイナリディフ（binary diff））の利用を通して実装されてもよい。例として、バイナリディフパッチ１１９はストレージデバイス１１５に格納され、実行時に関連するファイルに適用されてもよい。
【００８８】
伝統的には、パッチはネットワークを介してダウンロード可能な差分ファイルからの実行可能な命令にしたがって全体の新しいファイルを生成することによって適用される。これらの命令は、ファイルからどのバイトを取り除き、どのバイトをファイルに追加するかを指示する命令である。ストレージデバイス１１５に格納されたバイナリディフパッチ１１９はそのような命令を含む。パッチを当てることは、伝統的には、例えば実行時ではなくオフラインで行われる。典型的な伝統的パッチにおいては、オリジナルファイル全体がストレージデバイスからメモリ内に読み込まれる。新しいファイルを生成するためにディフパッチが適用され、新しいファイルがストレージデバイスに書き戻される。目的は、ダウンロードするパッチのサイズを最小化することである。
【００８９】
ディフパッチは３００ボー（baud）または１２００ボーの情報量がダウンロードされたときに展開された。この時点ではダウンロードのサイズを減らすことが重要であった。インターネットの発展とともに、ダウンロードのスピードはより広帯域で可能となった。したがって、ディフパッチを使わずに、単にネットワークを介してファイル全体を転送し、ストレージデバイス１１５にダウンロードするのがより一般的な方法である。このやり方はいくぶん大雑把であるが、それでも効果的である。
【００９０】
しかしながら、多くのアプリケーション、特にビデオゲームでは、しばしばとても大きなファイルにパッチを当てる必要がある。パッチを適用するためにファイル全体がメモリに読み込まれなければならないので、とても大きなファイルにディフパッチを当てることは潜在的に遅くなりうる。例えば、ストレージから１ギガバイトのファイルをメモリに読み込むのはパッチを適用する前でさえ１分以上かかってしまうであろう。
【００９１】
これら両方のパッチを当てることの先行技術は、帯域コストの問題を提示する。この問題はダウンロードすべき置き換えファイルがストレージデバイス１１５内の空き領域の相当の部分を占めてしまうことが特に深刻である。例えば、５００メガバイトのパッチの当てられたファイルをダウンロードすることは、２０ギガバイトのハードディスクの相当部分を占めてしまうことになる。
【００９２】
さらに、いくつものとても大きなファイルが、とても少ない量のデータを置き換えることを要求すると問題となる。例えば、あるアプリケーションが、先頭に１６バイトのＩＤ内にバグがあるいくつものファイルを持っているとする。ところが、パッチはファイルサイズのレベルで動作するため、ファイル置き換えによってパッチを適用することはアプリケーションの全てのファイルをダウンロードして置き換えることを意味する。これはファイルが数ギガバイトである場合には現実的ではない。たとえ伝統的なディフパッチでファイルにマッチが当てられる場合でも、パッチを当てるために全てのファイルがコピーされなければならない。
【００９３】
これらの問題を克服するために、バイナリパッチが生成され、伝統的な方法でダウンロードされる。しかしながら、オフラインでパッチを当てる代わりに、例えばアプリケーションの実行中に、アプリケーションからの入出力リクエスト処理の一部などの実行時にパッチが当てられてもよい。そのような実行時におけるバイナリディフパッチを実装するためには、都合のよいものではあるものの、上述のような即時チャンキングは要求されないことは留意すべきである。
【００９４】
パッチは木構造の比較的早い段階において適用されてもよい。例えば、受信入出力リクエストの初期プロセスの一部が、リクエスト内にリストアップされたいずれかのファイル用のディフパッチがあるか否かを決定するパッチテーブルのチャンキングを伴ってもよい。これは上述したデアーカイバＴＯＣルックアップと類似したものである。パッチテーブルは、ＲＡＭに格納さてもよく、パッチをどこにどのように当てるかを決めるためにファイル入出力システム１０１が必要とする情報を含んでいてもよい。
【００９５】
本発明の好ましい実施の形態を完全な形で説明してきたが、いろいろな代替物、変形、等価物を用いることができる。したがって、本発明の範囲は、上記の説明を参照して決められるものではなく、請求項により決められるべきであり、均等物の全範囲も含まれる。ここで述べた特徴はいずれも、好ましいかどうかを問わず、他の特徴と組み合わせてもよい。請求項において、明示的に断らない限り、各項目は１またはそれ以上の数量である。請求項において「〜のための手段」のような語句を用いて明示的に記載する場合を除いて、請求項が、３５ＵＳＣのセクション１１２、パラグラフ６における「手段」または「ステップ」節と解してはならない。特に、請求項において「〜ステップ」との使用は、３５ＵＳＣのセクション１１２、パラグラフ６の条項を行使することを意図するものではない。
【００９６】
本発明を好適な態様を参照しながら多くの詳細を述べてきたが、他の態様も可能である。したがって、請求項の趣旨および範囲は本明細書に記載された好適な実施態様の記載に限定されるべきではない。
【００９７】
読者の注意は、本明細書とともに提出され、本明細書とともに公開された全ての論文や文書に向けられており、そのような論文や文書の内容は参照によりここに組み入れる。
【００９８】
本明細書に開示された全ての特徴（添付のいずれの請求項、要約書、および図面を含む）は、特に断らない限り、同一の、等価な、あるいは類似の目的を達成する代替する特徴で置き換えられてもよい。したがって、特に断らない限り、開示された各特徴は等価または類似の一般的なシリーズのひとつの単なる例示である。
【図１】
0005292473.tif 000010
【図２】
0005292473.tif 000011
【図３】
0005292473.tif 000012
【図４】
0005292473.tif 000013
【図５】
0005292473.tif 000014