(57)【要約】【課題】複数の要求元からのリクエストを公平に多重化することは難しい。【解決手段】ストレージマルチプレクサ３０は、各要求元のリクエストが入力される複数の予約チャネル３２と出力ポート４２を含む。出力ポート４２は、複数の予約チャネル３２から渡されるリクエストをディスクスケジューラ２０に出力する。各予約チャネル３２は、各要求元からリクエストを処理するための帯域幅の予約を受け付ける。複数の要求元からのリクエストを多重化するための時間単位であるタイムフレームが設けられ、あるタイムフレームにおいて、他の予約チャネル３２から出力されるリクエストによって、予約帯域幅の少なくとも一部が横取りされた予約チャネル３２は、次のタイムフレームにおいて、横取りされた予約帯域幅の補償を受ける。【選択図】図２
2008097312.tif 000002
【特許請求の範囲】
【請求項１】
サービスの要求元毎に設けられ、各要求元からリクエストを処理するための帯域幅の予約を受け付け、各要求元からリクエストが入力される複数のチャネルと、
複数の前記チャネルから渡されるリクエストを出力する出力ポートとを含み、
複数の要求元からのリクエストを多重化するための時間単位であるタイムフレームが設けられ、あるタイムフレームにおいて、他のチャネルから出力されるリクエストによって、予約帯域幅の少なくとも一部が横取りされたチャネルは、次のタイムフレームにおいて、横取りされた予約帯域幅の補償を受けることを特徴とするマルチプレクサ。
【請求項２】
タイムフレームの任意の時点において、前記出力ポートの出力先のキューにリクエストが存在しない場合、当該タイムフレーム内で空き帯域幅が生じたと仮定して、あるチャネルにその空き帯域幅を割り当てることを特徴とする請求項１に記載のマルチプレクサ。
【請求項３】
前記チャネルで待ち状態にあるリクエスト数に応じて動的に変更される優先度が前記チャネル毎に設けられた場合に、前記優先度の高い順に前記チャネルが選択され、そのチャネルに前記空き帯域幅が割り当てられることを特徴とする請求項２に記載のマルチプレクサ。
【請求項４】
空き帯域幅が生じたと仮定されたタイムフレームにおいて、帯域幅を予約したチャネルからリクエストが遅れて到着したことにより、そのリクエストに帯域幅を割り当てることができなくなった場合、割り当てることができなくなった帯域幅を横取りされた予約帯域幅として計数することを特徴とする請求項２または３に記載のマルチプレクサ。
【請求項５】
他のチャネルの予約帯域幅を横取りしたチャネルについては、１つ前のタイムフレームにおいて超過して使用した帯域幅を現タイムフレームにおいてすでに使用したものとみなして予約帯域幅の割り当てを実施することにより、横取りされた予約帯域幅を補償することを特徴とする請求項１から４のいずれかに記載のマルチプレクサ。
【請求項６】
サービスの１つ以上の要求元から入力されるリクエストを出力するマルチプレクサと、
前記マルチプレクサから出力されたリクエストをスケジューリングして実行するスケジューラとを含み、
前記マルチプレクサは、
前記要求元毎に設けられ、各要求元からリクエストを処理するための帯域幅の予約を受け付け、各要求元からリクエストが入力される複数のチャネルと、
複数の前記チャネルから渡されるリクエストを出力する出力ポートとを含み、
複数の要求元からのリクエストを多重化するための時間単位であるタイムフレームが設けられ、あるタイムフレームにおいて、他のチャネルから出力されるリクエストによって、予約帯域幅の少なくとも一部が横取りされたチャネルは、次のタイムフレームにおいて、横取りされた予約帯域幅の補償を受けることを特徴とする情報処理装置。
【請求項７】
前記スケジューラは、前記出力ポートから出力されたリクエストをキューイングするスケジューラキューを含み、
前記マルチプレクサは、タイムフレームの任意の時点において、前記スケジューラキューにリクエストが存在しない場合、当該タイムフレーム内で空き帯域幅が生じたと仮定して、あるチャネルに待ち状態のリクエストがあれば、そのリクエストを取り出して前記スケジューラに渡すことにより、そのチャネルにその空き帯域幅を割り当てることを特徴とする請求項６に記載の情報処理装置。
【請求項８】
サービスの要求元毎にリクエストを処理するための帯域幅の予約を受け付けるチャネルを提供し、各要求元からのリクエストを複数のチャネルにて受け付けるチャネル機能と、
複数の前記チャネルから渡されるリクエストを出力する出力ポートを提供する出力ポート機能と、
複数の要求元からのリクエストを多重化するための時間単位であるタイムフレームが設けられ、あるタイムフレームにおいて、他のチャネルから出力されるリクエストによって、予約帯域幅の少なくとも一部が横取りされたチャネルに対して、次のタイムフレームにおいて、横取りされた予約帯域幅を補償するエラー補償機能とをコンピュータに実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の要求元からのリクエストを多重化する技術に関する。
【背景技術】
【０００２】
オペレーティングシステムは、動画像や音声などの連続メディアを利用するリアルタイムアプリケーションや、ＷＷＷ（World Wide Web）サーバやデータベースサーバからのファイル転送、ワードプロセッサなどのインタラクティブなアプリケーションなど、幅広いアプリケーションをサポートする必要がある。これらのアプリケーションは、ハードディスクなどの記憶装置に対するアクセスを伴うが、サービス品質（QoS）の要求は、それぞれ異なっている。テキスト編集などのインタラクティブなアプリケーションは、リクエストの平均レスポンスタイムが最小であることを要求する。一方、ファイル転送はスループットが最大であることを要求する。また、ビデオや音声などのマルチメディアアプリケーションは、動画のフレームがデッドラインよりも前に到着することを要求するが、フレーム落ちが生じることをある程度許容する。
【０００３】
このようなサービス品質に対する幅広い要求に応えるためには、ディスク装置において個々のアプリケーションのリクエストを適切にスケジューリングすることが必要である。ディスクは、一般に、シリンダ、トラックおよびセクタの組み合わせで論理ブロックアドレスが付けられている。ディスクのアクセス時間は、ディスクヘッドがアクセス対象のトラック位置に移動するのに要するシーク時間、アクセス対象のセクタがディスクヘッドの位置に来るまで待つ回転待ち時間、およびアクセス対象のセクタから読み取ったデータを転送するのにかかるデータ転送時間を足し合わせたものである。ディスクアクセス時間の中で特に支配的なものはシーク時間、すなわちディスクヘッドの移動にかかる時間であり、これをいかにして減らすかがディスク性能を決める。
【０００４】
代表的なディスクスケジューリング方式として、ＳＳＴＦ（Shortest Seek Time First）アルゴリズムやエレベータアルゴリズムがある。ＳＳＴＦアルゴリズムでは、シーク時間順、すなわちアームの移動が小さいリクエストから順に処理するものであり、ディスクヘッドの移動距離を小さくすることができる。また、エレベータアルゴリズムでは、アームが一方向に動くようにリクエストの処理順序を変え、ディスクヘッドをディスクの内周から外周の方向、あるいは外周から内周の方向に連続的に移動させ、端に到達するまではディスクヘッドの移動方向を変えないようにする。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
オペレーティングシステムは、幅広いアプリケーションの様々なサービス品質要求に応える必要があり、ディスク装置からのデータ転送の品質は個々のアプリケーションのサービス品質要求に合ったものでなければならない。しかし、個々のアプリケーションのサービス品質を最優先にリクエストをスケジューリングすると、シーク時間や回転待ち時間などのディスクのアクセス時間が増大し、ディスク性能が落ち、ディスク装置からのデータ転送の帯域幅が減少することになる。一方、ディスク性能を最大化するスケジューリング方式を採用すると、個々のアプリケーションのリクエストがそのサービス品質要求を無視する形でスケジューリングされるため、アプリケーションのサービス品質要求を満足させることができなくなる。
【０００６】
サービス品質要求の異なる複数の要求元からのリクエストをスケジューリングして実行する際、複数の要求元からのリクエストの多重化処理が必要になる。リクエストの多重化処理を効率的に行わなければ、リクエストの実行に支障を来す。また、リクエストの多重化に当たって、複数の要求元の間で公平性を担保することも必要である。
【０００７】
本発明はこうした課題に鑑みてなされたものであり、その目的は、複数の要求元からのリクエストを公平に多重化することのできる多重化処理技術を提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明のある態様のマルチプレクサは、複数のチャネルと出力ポートとを含む。前記チャネルは、サービスの要求元毎に設けられ、各要求元からリクエストを処理するための帯域幅の予約を受け付け、各要求元からリクエストが入力される。前記出力ポートは、複数の前記チャネルから渡されるリクエストを出力する。複数の要求元からのリクエストを多重化するための時間単位であるタイムフレームが設けられ、あるタイムフレームにおいて、他のチャネルから出力されるリクエストによって、予約帯域幅の少なくとも一部が横取りされたチャネルは、次のタイムフレームにおいて、横取りされた予約帯域幅の補償を受ける。
【０００９】
本発明の別の態様は、情報処理装置である。この装置は、サービスの１つ以上の要求元から入力されるリクエストを出力するマルチプレクサと、前記マルチプレクサから出力されたリクエストをスケジューリングして実行するスケジューラとを含む。前記マルチプレクサは、複数のチャネルと出力ポートとを含む。前記チャネルは、前記要求元毎に設けられ、各要求元からリクエストを処理するための帯域幅の予約を受け付け、各要求元からリクエストが入力される。前記出力ポートは、複数の前記チャネルから渡されるリクエストを出力する。複数の要求元からのリクエストを多重化するための時間単位であるタイムフレームが設けられ、あるタイムフレームにおいて、他のチャネルから出力されるリクエストによって、予約帯域幅の少なくとも一部が横取りされたチャネルは、次のタイムフレームにおいて、横取りされた予約帯域幅の補償を受ける。
【００１０】
ここで、「リクエスト」は、ハードディスクなどのストレージデバイスに対するリクエストに限らず、プロセッサ、メモリ、周辺機器などの各種のデバイスに対するリクエストや、ネットワークを経由したサーバなどのデバイスに対するリクエストを含む。また「スケジューリング」は、ディスクスケジューリング以外に、プロセッサ、メモリ、周辺機器などの各種のデバイスに対するアクセススケジューリングや、ネットワークを経由したサーバなどのデバイスに対するアクセススケジューリングを含む。
【００１１】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラム、データ構造などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、複数の要求元からのリクエストを公平に多重化してサービス品質を向上させることができる。
【発明を実施するための最良の形態】
【００１３】
［１］構成
図１は、ストレージサブシステム１００の構成を説明する図である。ストレージサブシステム１００は、オペレーティングシステム１４０内にファイルシステム１３０とともに設けられる。
【００１４】
ファイルシステム１３０は、ストレージインタフェース１２０を介してストレージサブシステム１００との間でコネクションを構築し、構築されたコネクションを用いて、ストレージデバイス１５０に対するアクセスリクエストをストレージサブシステム１００に供給する。ファイルシステム１３０はストレージサブシステム１００と複数のコネクションを構築することができる。ファイルシステム１３０は、アプリケーションタイプ毎にコネクションを設定してもよい。アプリケーションタイプとして、マルチメディアアプリケーション、リアルタイムアプリケーション、インタラクティブアプリケーション、ファイル転送などがある。
【００１５】
ストレージサブシステム１００は、ストレージサービスプロバイダ６０、ＳＣＳＩ（Small Computer System Interface）クラスドライバ５０、リクエストスケジューラ４０、およびデバイスドライバ１０を含む。ストレージサービスプロバイダ６０は、ファイルシステム１３０からのコネクションを管理し、ストレージへのアクセスサービスをファイルシステム１３０に提供する。ストレージサービスプロバイダ６０は、アプリケーションタイプやアプリケーションからの要求によってコネクション毎にストレージデバイス１５０のデータ転送の帯域幅を予約することができる。
【００１６】
ＳＣＳＩクラスドライバ５０は、ＳＣＳＩ規格にしたがったドライバであり、各コネクションからのストレージデバイス１５０に対するアクセスリクエストを発行し、リクエストスケジューラ４０に供給する。
【００１７】
リクエストスケジューラ４０は、ストレージマルチプレクサ３０とディスクスケジューラ２０を含み、１以上のコネクションからのリクエストを多重化してデバイスドライバ１０に与える。
【００１８】
デバイスドライバ１０は、ストレージデバイス１５０のデバイス情報をもつデバイス固有のドライバである。デバイスドライバ１０は、ディスクスケジューラ２０から渡されるリクエストを実行して、ストレージデバイス１５０に対するデータの読み書きを行い、ＳＣＳＩクラスドライバ５０に結果を通知する。
【００１９】
図２は、リクエストスケジューラ４０の構成図である。リクエストスケジューラ４０は、ストレージデバイス１５０に対するリクエストを多重化し、スケジュールする。同図は機能に着目したブロック図を描いており、これらの機能ブロックはハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現することができる。
【００２０】
リクエストスケジューラ４０は、ストレージマルチプレクサ（以下、単に「マルチプレクサ」と呼ぶ）３０とディスクスケジューラ２０を含む。マルチプレクサ３０は、各コネクションからのリクエストを後述の「タイムフレーム」（time-frame）単位で多重化するとともに、各コネクションの帯域幅を確保する。ディスクスケジューラ２０は、マルチプレクサ３０から供給されたリクエストの実行順序をタイムフレーム単位でスケジューリングしてデバイスドライバ１０に供給する。
【００２１】
マルチプレクサ３０は、各コネクションのリクエストが入力される複数のチャネル（符号３１、３２）と、出力ポート４２と、タイマ３８と、空き帯域幅ポート４４とを含む。
【００２２】
チャネルは、マルチプレクサ３０内に設けられた、リクエストが入出力される論理的な経路であり、チャネル内のポートの開閉によりマルチプレクサ３０に入力されたリクエストの出力を制御する。チャネルの帯域幅は、そのチャネルからの最大データ転送レートで与えられる。チャネルには、メインチャネル３１と予約チャネル３２の二種類がある。
【００２３】
メインチャネル３１は、帯域幅を予約しないコネクション用のチャネルである。メインチャネル３１からのデータ転送には、予約可能な総帯域幅（後述の「総予約可能帯域幅ｎｅｔ＿ｂｗ」）の内、残存する未予約帯域が用いられる。予約チャネル３２が全く生成されなかった場合、メインチャネル３１はデータ転送のために全帯域を用いることができる。
【００２４】
予約チャネル３２は、帯域幅を予約する各コネクション毎に設けられる。予約チャネル３２は、帯域幅を予約するコネクションが構築される度にランタイムで生成され、コネクションの消滅とともに破棄される。
【００２５】
メインチャネル３１はチャネルポート３３とチャネルキュー３５をもつ。同様に、予約チャネル３２もチャネルポート３４とチャネルキュー３６をもつ。各チャネル３１、３２のチャネルポート３３、３４にはＳＣＳＩクラスドライバ５０から各コネクションのリクエストが入力される。チャネルポート３３、３４が開いている場合、チャネルポート３３、３４に入力されたリクエストは、チャネルキュー３５、３６にキューイングされることなく、直接、出力ポート４２に送られる。チャネルポート３３、３４は、予約された量のリクエストがポートを通過した後、閉じられる。チャネルポート３３、３４が閉じられている場合、リクエストは、チャネルキュー３５、３６にキューイングされる。
【００２６】
各チャネルキュー３５、３６は、現在のタイムフレームに対してチャネルポート３３、３４が閉じられている間、チャネルポート３３、３４に入力されたリクエストを蓄積する。予約チャネル３２のチャネルポート３４は、各タイムフレームの開始時点で開き、予約された量のリクエストがポートを通過した時点で閉じることで、予約された量のリクエストだけが出力ポート４２に送られる。メインチャネル３１のチャネルポート３３も、各タイムフレームの開始時点で開き、予約可能な総帯域幅の内、未予約帯域幅内に収まる量のリクエストがポートを通過した時点で閉じることで、未予約帯域範囲内の量のリクエストだけが出力ポート４２に送られる。
【００２７】
タイマ３８は１タイムフレーム分の時間経過をクロックによって計測しており、１タイムフレームの経過をメインチャネル３１、予約チャネル３２、および出力ポート４２に通知する。タイマ３８からの通知を受けて、メインチャネル３１、予約チャネル３２、および出力ポート４２において、新しいタイムフレームの開始に当たり、各種パラメータが適宜リセットされる。タイマ３８から１タイムフレームの経過を通知されると、各チャネル３１、３２においてチャネルポート３３、３４が開かれ、まず各チャネル３１、３２のチャネルキュー３５、３６にキューイングされたリクエストが開かれたチャネルポート３３、３４から出力ポート４２に送られる。
【００２８】
出力ポート４２は、各チャネル３１、３２から渡されたリクエストを多重化してディスクスケジューラ２０に送る。これにより、マルチプレクサ３０に入力されたリクエストは、出力ポート４２を通じて多重化されてディスクスケジューラ２０のディスクスケジューリング用のキュー（以下、「ディスクスケジューラキュー」という）２２に渡される。なお、タイムフレームの開始時点で、チャネルキュー３５、３６で待ち状態になっていたリクエストは、開かれたチャネルポート３３、３４から出力ポート４２に出力され、出力ポート４２を経由してディスクスケジューラキュー２２に送られる。ディスクスケジューラキュー２２には、タイムフレーム単位でリクエストがキューイングされる。同図では、タイムフレームｎではリクエスト２４ａ〜２４ｃが、タイムフレームｎ＋１ではリクエスト２５ａ〜２５ｄがキューイングされている様子が模式的に示されている。
【００２９】
ディスクスケジューラ２０は、マルチプレクサ３０からフレーム単位で多重化されたリクエストを受け取り、ディスクスケジューラキュー２２にキューイングし、フレーム毎にフレーム内のリクエストの実行順序をスケジューリングする。ディスクスケジューラ２０は、ディスク性能を最大化するために、フレーム内の各リクエストのディスクアクセスパターンを考慮して、スケジューリングを行い、スケジューリングされたリクエストをデバイスドライバ１０に供給する。
【００３０】
ディスクスケジューラキュー２２にリクエストが全くないとき、ディスクスケジューラ２０は、空き帯域幅ポート４４にリクエストを要求する。ディスクスケジューラ２０からの要求を受けて、マルチプレクサ３０は、リクエストをキューイングしている最も高い優先度のチャネルを選び、そのチャネルにキューイングされたリクエストを取り出して空き帯域幅ポート４４に渡す。ディスクスケジューラ２０は、空き帯域幅ポート４４からリクエストを受け取って実行に移す（すなわちリクエストをデバイスドライバ１０に渡す）。
【００３１】
以上述べたように、マルチプレクサ３０に入力されたリクエストは次の３つのパスのいずれかを通ってディスクスケジューラ２０に渡される。
（１）チャネルポート３３、３４が開いているとき、リクエストがチャネルキュー３５、３６にキューイングされることなく（チャネルキュー３５、３６をバイパスして）、直接、出力ポート４２に渡され、出力ポート４２からディスクスケジューラキュー２２にキューイングされるパス。
（２）チャネルポート３３、３４が閉じているとき、リクエストがチャネルキュー３５、３６にいったんキューイングされた後、次のタイムフレームの始まりにおいて、開かれたチャネルポート３３、３４から出力ポート４２に渡され、出力ポート４２からディスクスケジューラキュー２２にキューイングされるパス。
（３）ディスクスケジューラキュー２２が空いているとき、優先度の高いチャネルのチャネルキュー３５、３６にキューイングされたリクエストが空き帯域幅ポート４４に渡され、ディスクスケジューラキュー２２にキューイングされることなく、実行されるパス。
【００３２】
図３（ａ）、（ｂ）を参照して、メインチャネル３１および予約チャネル３２の内部構成とリクエストの入出力制御を詳しく説明する。メインチャネル３１と予約チャネル３２の内部構成と入出力制御は共通しているので、まとめて説明する。図３（ａ）に示すように、チャネル３１、３２のチャネルポート３３、３４は、入力側ポート４５と出力側ポート４６を含む。入力側ポート４５、出力側ポート４６はそれぞれ開端子と閉端子をもち、どちらかに切り替えることでポートが開閉される。
【００３３】
チャネル３１、３２の入力側ポート４５と出力側ポート４６の開閉状態により、図３（ｂ）に示すような３通りのチャネルポートの状態が作られる。状態Ａは、入力側ポート４５が「開」かつ出力側ポート４６が「閉」の状態であり、入力側ポート４５の開端子に入力されたリクエストは、出力側ポート４６の閉端子を通ってチャネルキュー３５、３６にキューイングされる。
【００３４】
状態Ｂは、入力側ポート４５が「開」かつ出力側ポート４６が「開」の状態であり、入力側ポート４５の開端子に入力されたリクエストは、出力側ポート４６の開端子を通って出力ポート４２に出力される（チャネルキュー３５、３６をバイパスする）。
【００３５】
状態Ｃは、入力側ポート４５が「閉」かつ出力側ポート４６が「開」の状態であり、入力側ポート４５が閉じられているため、新しいリクエストが入力されることはなく、チャネルキュー３５、３６にキューイングされたリクエストが入力側ポート４５の閉端子に入力され、出力側ポート４６の開端子を通って出力ポート４２に出力される。
【００３６】
「チャネルポート３３、３４が閉じている」とは、状態Ａをいう。このとき、入力されたリクエストはチャネルキュー３５、３６にキューイングされる。
【００３７】
「チャネルポート３３、３４が開いている」とは、状態Ｂと状態Ｃの２通りを指す。新しいタイムフレームが始まると、最初は、チャネルポート３３、３４は状態Ｃになって、チャネルキュー３５、３６にキューイングされたリクエストがチャネルポート３３、３４から出力ポート４２に出力される。この後、チャネルの帯域幅がまだ残っていれば、チャネルポート３３、３４は、状態Ｂになり、新しく到着するリクエストがチャネルキュー３５、３６をバイパスしてチャネルポート３３、３４から出力ポート４２に出力される。もし、状態Ｃにおいてキューイングされたリクエストをチャネルポート３３、３４から出力したことにより、チャネルの帯域幅を使い切った場合は、チャネルポート３３、３４は、状態Ａになり、新しく到着するリクエストはチャネルキュー３５、３６にキューイングされる。
【００３８】
このように、チャネルポート３３、３４は、入力側ポート４５と出力側ポート４６を内部構成としてもち、それらの開閉状態により、リクエストの入出力経路が制御されるが、以下の説明では、簡単のため、内部構成とリクエストの入出力経路の制御動作については触れずに、出力側ポート４６の開閉状態のみに注目して、チャネルポート３３、３４の開閉状態を説明していることに留意する。
【００３９】
［２］パラメータ
図２のリクエストスケジューラ４０で用いられる各種パラメータを説明する。
［２．１］タイムフレーム
タイムフレームは、マルチプレクサ３０において帯域幅が計算される時間単位である。タイムフレームは、ディスクスケジューラ２０において多重化されるリクエストを区切るタイムウインドウでもある。異なるタイムフレームで発行されたリクエスト間では順番が入れ替えられることはなく、発行された順序で実行される。一つのタイムフレーム内で発行されたリクエスト間ではディスクスケジューラ２０において順番が入れ替えられることがある。
【００４０】
タイムフレームはシステム内で可変の値である。タイムフレームが長いほどスループットが良くなり、タイムフレームが短いほど平均レスポンスタイムがより良くなる。レスポンスタイムとスループットの間にはトレードオフがあり、スケジュール対象のコネクションの種類やその組み合わせなどによってタイムフレームを適宜変えることができる。
【００４１】
［２．２］予約パラメータ
予約パラメータは、帯域幅予約に使われるパラメータであり、帯域幅予約の変更に伴って調整される。以下の帯域幅の定義は、タイムフレームの値によってスケーリングされることに留意する。予約パラメータには以下のものがある。
【００４２】
［２．２．１］最小デバイス帯域幅と最大デバイス帯域幅
ストレージデバイス１５０が提供することができるデータ転送レートをデバイス帯域幅という。ディスクのシークタイムが変動することから、ストレージデバイス１５０は、単位時間当たりに同じ量のデータ転送を実行できるとは限らない。データ転送レートは、最小値と最大値の間で変動する。最小デバイス帯域幅は、ストレージデバイス１５０が提供できる最小の帯域幅である。ワーストケースの評価にもとづいて、デバイスドライバ１０は最小デバイス帯域幅を求めて通知することができる。マルチプレクサ３０は、予約された帯域幅の合計が最小デバイス帯域幅を超えない範囲で、帯域幅予約を許可する。最大デバイス帯域幅は、ストレージデバイス１５０がベストの条件下で提供可能な持続的なデータ転送レートである。
【００４３】
［２．２．２］総予約可能帯域幅、総予約帯域幅、および総未予約帯域幅
総予約可能帯域幅ｎｅｔ＿ｂｗは、１つ以上のチャネルによって予約可能な総帯域幅であり、最小デバイス帯域幅に等しい。総予約帯域幅ｎｅｔ＿ｒｅｓｅｒｖｅｄは、すべてのチャネルの予約帯域幅の合計である。総未予約帯域幅ｎｅｔ＿ｕｎｒｅｓｅｒｖｅｄは、予約可能な残存する帯域幅であり、総予約可能帯域幅ｎｅｔ＿ｂｗから総予約帯域幅ｎｅｔ＿ｒｅｓｅｒｖｅｄを引いた値に等しい。
【００４４】
［２．３］タイムフレームパラメータ
タイムフレームパラメータは、マルチプレクサ３０において用いられるパラメータである。タイムフレームパラメータは、すべてのチャネルに共通するパラメータであり、タイムフレーム毎に変化する。タイムフレームパラメータには以下のものがある。
【００４５】
［２．３．１］仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔ
どのチャネルからも要求されないディスク帯域幅は、仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔと呼ばれる。帯域幅を予約したコネクションは、必ずしも各タイムフレームで予約した帯域幅を利用するとは限らない。帯域幅を予約したコネクションであっても、タイムフレーム内で帯域幅を要求しない、すなわちリクエストを発行しないことがあり、空き帯域幅が生じる。現タイムフレームに対する仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔには最小デバイス帯域幅と最大デバイス帯域幅の差も加算される。
【００４６】
各コネクションのリクエストはタイムフレームの始まりに到着することも、タイムフレームの終わり近くになって到着することもあり、リクエストの到着時間は予測不可能である。そのため、タイムフレームの途中で、ある予約チャネルからのリクエストが未到着で帯域に空きが生じる場合は、とりあえず空き帯域が生じたと仮定して、その都度、他の予約チャネルや帯域予約のないメインチャネルからのリクエストに帯域を割り当てる。しかし、そのタイムフレーム内に予約チャネルからリクエストが遅れて到着し、予約した帯域幅が要求されることがある。すなわち、予約リクエストが到着しないために、空き帯域幅であると想定して他のチャネルのリクエストのためにその空き帯域幅を使ってしまうと、遅れて到着した予約チャネルのリクエストに割り当てる帯域が足りなくなり、そのリクエストを実行することができない事態が発生する。これが次に述べる「偽空き帯域幅」が発生した状態である。
【００４７】
［２．３．２］偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔ
１つ以上の予約チャネルのリクエストが現タイムフレームにおいて帯域不足で実行できない状態になった場合、現タイムフレームにおいて以前に「空き帯域幅が生じた」と仮定したことが誤りであったことを意味する。仮定した空き帯域幅は、実際は、「偽空き帯域幅」であったのであるから、その帯域幅を要求したチャネルは、次のタイムフレームにおいて、帯域幅が奪われたチャネルに帯域幅を返さなければならない。このように誤って空き帯域幅であると仮定して使用してしまった帯域幅を偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔという。
【００４８】
［２．３．３］総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄ
マルチプレクサ３０とディスクスケジューラ２０がともにリクエストをもたないとき、デバイスドライバ１０はアイドル状態になり、ディスク帯域幅は浪費される。デバイスドライバ１０がアイドルである、すなわちストレージデバイス１５０がアイドルである間の帯域幅を総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄという。
【００４９】
［２．３．４］総使用帯域幅ｎｅｔ＿ｕｓｅｄ
総使用帯域幅ｎｅｔ＿ｕｓｅｄは、現タイムフレームにおいて出力ポート４２を通過したリクエストのサイズ（バイト単位）の合計である。
【００５０】
［２．３．５］総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄ
総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄは、現タイムフレームにおいて利用可能な帯域幅の残存量であり、総予約可能帯域幅ｎｅｔ＿ｂｗから総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄと総使用帯域幅ｎｅｔ＿ｕｓｅｄを引いた値である。
net_unused = net_bw - (net_wasted + net_used)
【００５１】
［２．４］チャネルパラメータ
チャネルパラメータも、マルチプレクサ３０において用いられるパラメータである。チャネルパラメータはチャネル毎に設定されるパラメータであり、チャネルの状態を示す。チャネルパラメータには以下のものがある。
【００５２】
［２．４．１］チャネル予約帯域幅ｃ＿ｒｅｓｅｒｖｅｄ
チャネルに割り当てられた帯域幅をチャネル予約帯域幅ｃ＿ｒｅｓｅｒｖｅｄという。
［２．４．２］チャネル使用帯域幅ｃ＿ｕｓｅｄ
チャネル使用帯域幅ｃ＿ｕｓｅｄは、現タイムフレームにおいてチャネルを通過したリクエストのサイズ（バイト単位）の合計である。
［２．４．３］チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄ
チャネルが現タイムフレームにおいてデータ転送に用いることができる帯域幅の残存量である。チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄは、チャネル予約帯域幅ｃ＿ｒｅｓｅｒｖｅｄからチャネル使用帯域幅ｃ＿ｕｓｅｄと次に述べるチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄを引いたものである。
c_unused = c_reserved - (c_used + c_wasted)
【００５３】
［２．４．４］チャネル浪費帯域幅ｃ＿ｗａｓｔｅｄ
総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄの内、各チャネルの割り当て分をチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄという。各チャネルのチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄは、そのチャネルのチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄに比例する。すなわち、総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄは、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄの比でチャネル間に配分される。
【００５４】
［２．４．５］チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔ
チャネルが、割り当てられた帯域幅を超えて使用した場合、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔは、その超過量だけインクリメントされる。チャネルが、自分自身に割り当てられた帯域幅を他のチャネルに奪われたとき、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔは、その奪われた量だけデクリメントされる。正のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値は、そのチャネルが予約量を超えて使ったことを意味し、負のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値は、そのチャネルが予約量よりも少ない量しか使っていないことを意味する。
【００５５】
チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔは、次のタイムフレームに対してチャネル使用帯域幅ｃ＿ｕｓｅｄを設定するために用いられる。あるチャネルが他のチャネルの帯域幅を横取りして、より多くの帯域幅を使った場合、次のタイムフレームにおいて、そのチャネルは超過分を償うために帯域幅の使用量を少なくする。あるチャネルが自分が使用する帯域幅を奪われた場合、次のタイムフレームにおいて、そのチャネルはチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの補償を受ける。
【００５６】
［２．４．６］チャネル優先度ｃ＿ｐｒｉｏｒｉｔｙ
チャネル優先度ｃ＿ｐｒｉｏｒｉｔｙは、チャネルが空き帯域幅を使用する際の優先度である。優先度が高いほど、チャネルが空き帯域幅を取得できる確率が高くなる。チャネル優先度ｃ＿ｐｒｉｏｒｉｔｙの調整の仕方は後述する。
【００５７】
［２．５］帯域幅予約タイプ
各コネクションは、ストレージデバイス１５０のデータ転送の帯域幅を絶対量で予約する。すべてのコネクションで予約された帯域幅の合計は、ストレージデバイス１５０の総予約可能帯域幅ｎｅｔ＿ｂｗを超えることはできない。帯域幅を予約することにより、ある単位時間内で最低限、ある量のデータが転送されることが保証されるため、レスポンスタイムが予測できないものになるのを防ぐことができる。また、帯域幅を予約することにより、コネクション間でストレージデバイス１５０のデータ転送能力を公平に共有することが可能になる。
【００５８】
帯域幅予約には、最小帯域幅を指定する予約と、最大帯域幅を指定する予約の２種類がある。最小帯域幅予約では、帯域幅の指定量は最小要求として扱われる。最小帯域幅を予約したコネクションは、その指定量の帯域幅を保証され、他の帯域幅予約に影響を与えない限り、より高いデータ転送速度が得られることもある。
【００５９】
最大帯域幅予約では、帯域幅の指定量は最大要求として扱われる。最大帯域幅を予約したコネクションは、その指定量を超えるデータ転送速度が得られることはない。最大帯域幅予約は、チャネルが最大帯域幅を超えて空き帯域幅を要求しないように制限するために用いられる。
【００６０】
［３］リクエストの多重化処理
［３．１］概要
リクエストスケジューラ４０によるリクエストの多重化処理手順を説明する。リクエスト多重化処理は、帯域幅割り当てのエラー（前述の「偽空き帯域幅」）を補償する処理を含む。あるタイムフレームで発生した帯域幅割り当てのエラーは、次のタイムフレームで補償される。エラー補償処理を用いることで、マルチプレクサ３０による多重化処理を高い精度をもたせたままで計算量的に軽量にすることができる。望ましい多重化処理の振る舞いは２つのフレームにまたがって実現されるから、完全な多重化処理が保証される単位時間は２フレーム分の長さになる。
【００６１】
リクエスト多重化処理は次の３つの方針に基づいている。
（１）チャネルポートに入力されるリクエストは、チャネル予約帯域幅ｃ＿ｒｅｓｅｒｖｅｄに達するまではチャネルポートを通過することが許される。チャネル予約帯域幅ｃ＿ｒｅｓｅｒｖｅｄに達した後は、チャネルポートに入力されるリクエストは、チャネルキューにキューイングされる。キューイングされたリクエストは、現タイムフレームにおいて帯域幅を使うことが制限される。
（２）現タイムフレームが終わり、次のタイムフレームがスタートすると、チャネルキューからリクエストが（チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄを上限として）出力される。
（３）ディスクスケジューラキュー２２が空きであるとき、ディスクスケジューラ２０は、マルチプレクサ３０の最も優先度が高いチャネルからリクエストを一つずつ取り出すことができる。
【００６２】
［３．２］チャネルポートの状態
チャネルポートは、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄの値に依存して、開いているか、閉じているかどちらかの状態をもつ。チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄの値が正（ゼロを含まない）であれば、チャネルポートは開いており、そうでなければ閉じている。チャネルポートが開いているとき、チャネルポートに入力されたリクエストは直接、出力ポート４２に送られる。所定の量のリクエストがチャネルポートを通過すると、チャネルポートは次のタイムフレームまで閉じられる。チャネルポートが閉じられると、リクエストはチャネルキューにキューイングされる。チャネルポートは、そのチャネルが他のチャネルの帯域幅を使用するのを制限するために用いられる。
【００６３】
［３．３］出力ポートの状態
出力ポート４２は、未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄの値に依存して、開いているか、閉じているかのいずれかの状態を取る。未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄの値が正であるなら、出力ポート４２は開いており、そうでなければ、閉じている。
【００６４】
［３．４］チャネル優先度の調整
マルチプレクサ３０は、空き帯域幅が利用可能であるときは、その空き帯域幅を最も優先度の高いチャネルに割り当てる。チャネル優先度ｃ＿ｐｒｉｏｒｉｔｙは、チャネル基本優先度ｃ＿ｂａｓｅ＿ｐｒｉｏｒｉｔｙとチャネルキューリクエスト数ｃ＿ｑｕｅｕｅｄ＿ｒｅｑｕｅｓｔの和である。
c_priority=c_base_priority+c_queued_request
【００６５】
チャネル基本優先度ｃ＿ｂａｓｅ＿ｐｒｉｏｒｉｔｙは、チャネルのタイプの違いまたは緊急性の要求度に応じてチャネルを区別するものであり、次の３つのレベルがある。
通常レベル：各チャネルのデフォルトの優先度である。
優先レベル：空き帯域幅を用いることがより好ましいチャネルに対して設定される。
剥奪レベル：あるチャネルが現タイムフレームにおいて自分の予約した帯域幅を使うことができないとき、そのチャネルは、次のタイムフレームにおいて、剥奪レベルの優先度がマルチプレクサ３０によって設定される。
通常レベル、優先レベル、剥奪レベルの順に優先度が高くなる。マルチプレクサ３０は、新しいタイムフレームが始まると、チャネル基本優先度をリセットする。
【００６６】
チャネルキューリクエスト数ｃ＿ｑｕｅｕｅｄ＿ｒｅｑｕｅｓｔは、チャネルキューでペンディングしているリクエストの数である。チャネルキューにあるリクエストの数が増えると、チャネル優先度は増える。
【００６７】
［３．５］浪費帯域幅の更新
ディスクスケジューラ２０がアイドルであるなら、帯域幅はリクエストが到着するまで浪費される。マルチプレクサ３０はディスクスケジューラ２０がアイドルになった時点のタイムスタンプwaste_time_startを記録する。
【００６８】
ディスクスケジューラ２０がアイドルであるときにリクエストが到着すると、マルチプレクサ３０は現在のタイムスタンプｗａｓｔｅ＿ｔｉｍｅ＿ｅｎｄを取得し、浪費時間ｗａｓｔｅｄ＿ｔｉｍｅを計算する。
waste_time_end = get_current_time();
wasted_time = waste_time_end - waste_time_start;
【００６９】
マルチプレクサ３０は、最小デバイス帯域幅を用いて、浪費時間に対応する浪費帯域幅ｗａｓｔｅｄ＿ｂａｎｄｗｉｄｔｈを計算し、総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄを更新する。
wasted_bandwidth = scale_to_bandwidth(wasted_time);
net_wasted = net_wasted + wasted_bandwidth;
【００７０】
総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄは、非ゼロのチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄをもっているすべてのチャネルの間で、各チャネルのチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄに比例するように分配される。すなわち、チャネル浪費帯域幅ｃ＿ｗａｓｔｅｄは以下のように計算される。
for all channels:
c_wasted = c_wasted + (c_unused * wasted_bandwidth) / net_unused;
【００７１】
このようにしてマルチプレクサ３０はリクエストを発行する予定のあるすべてのチャネルに対して、総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄを比例配分したチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄを各チャネルのチャネル使用帯域幅ｃ＿ｕｓｅｄに加算し、そのチャネルがあたかもそのチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄの分を使用したかのように扱うことで、各チャネルにペナルティを与える。更新されたチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄによって、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄは更新されて減少する。更新されたチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄに基づいて、マルチプレクサ３０は、チャネルポートの状態を更新する。チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄが０以下になると、チャネルポートは閉じられる。
【００７２】
［３．６］フローチャート
図４〜図８を参照して、リクエストスケジューラ４０によるリクエスト多重化処理の手順を説明する。図４は、リクエスト多重化処理の全体的な流れを示すフローチャートである。リクエストスケジューラ４０は、イベントの発生待ち状態にある（Ｓ１００）。イベントとして、イベントＡ「リクエスト到着」、イベントＢ「ディスクスケジューラキューが空である」、イベントＣ「新しいタイムフレームの開始」の３つがあり、各イベントが発生すると、ステップＳ１１０、Ｓ１２０、Ｓ１３０の処理がそれぞれ実行される。各処理が実行されると、リクエストスケジューラ４０は停止条件を確認し（Ｓ１４０）、停止しない場合（Ｓ１４０のＮ）、ステップＳ１００のイベント発生待ち状態に戻り、停止する場合（Ｓ１４０のＹ）、終了する。
【００７３】
［３．６．１］イベントＡ：リクエスト到着
図５Ａは、ステップＳ１１０のイベントＡ「リクエスト到着」が発生したときの処理を示すフローチャートである。新たなリクエストの到着時、それ以前にディスクスケジューラキュー２２が空であったなら（Ｓ９のＹ）、浪費帯域幅の計測を終了するために現在時刻を記録し（Ｓ１０）、浪費帯域幅の更新とチャネルポートの状態の更新を行う（Ｓ１１）。新たなリクエストの到着時、それ以前にディスクスケジューラキュー２２が空でなかった場合（Ｓ９のＮ）は、浪費帯域幅の計測をしていないので、ステップＳ１０、Ｓ１１の処理は不要であり、ステップＳ１２に進む。
【００７４】
図５Ｂは、ステップＳ１１の浪費帯域幅の更新とチャネルポートの状態の更新の処理を詳しく示すフローチャートである。
【００７５】
総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄとチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄを上記の［３．５］で説明した手順にしたがって更新する（Ｓ１５０）。チャネル使用帯域幅ｃ＿ｕｓｅｄの値と更新されたチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄの値によって、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄが次式により更新され（Ｓ１５２）、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄが正でなければ（Ｓ１５４のＮ）、チャネルポートが閉じられる（Ｓ１５６）。
c_unused = c_reserved - (c_used + c_wasted)
【００７６】
総使用帯域幅ｎｅｔ＿ｕｓｅｄの値と更新された総浪費帯域幅ｎｅｔ＿ｗａｓｔｅｄの値によって、総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄが次式により更新され（Ｓ１５８）、総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄが正でなければ（Ｓ１６０のＮ）、出力ポート４２が閉じられる（Ｓ１６２）。
net_unused = net_bw - (net_used + net_wasted)
【００７７】
図５Ａに戻る。リクエストが到着したチャネルのチャネルポートが閉じている場合（Ｓ１２のＮ）、リクエストはチャネルキューにキューイングされ、チャネル優先度が１つだけインクリメントされ（Ｓ３８）、イベントＡの処理は終了する。
【００７８】
リクエストが到着したチャネルのチャネルポートが開いており（Ｓ１２のＹ）、かつ、出力ポート４２が開いている場合（Ｓ１４のＹ）、リクエストは出力ポート４２に直接送られ、出力ポート４２から出力される（Ｓ１６）。
【００７９】
リクエストが出力ポート４２から出力されると、チャネル使用帯域幅ｃ＿ｕｓｅｄと総使用帯域幅ｎｅｔ＿ｕｓｅｄは次式によりリクエストサイズ（バイト単位）だけインクリメントされる（Ｓ１８）。
c_used = c_used + request_size
net_used = net_used + request_size
【００８０】
更新されたチャネル使用帯域幅ｃ＿ｕｓｅｄの値によって、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄが次式により更新され（Ｓ２０）、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄが正でなければ（Ｓ２２のＮ）、チャネルポートが閉じられる（Ｓ２４）。
c_unused = c_reserved - (c_used + c_wasted)
【００８１】
更新された総使用帯域幅ｎｅｔ＿ｕｓｅｄの値によって、総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄが次式により更新され（Ｓ２６）、総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄが正でなければ（Ｓ２８のＮ）、出力ポート４２が閉じられる（Ｓ３０）。
net_unused = net_bw - (net_used + net_wasted)
【００８２】
なお、ステップＳ１８において、リクエストサイズがチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄよりも大きい場合は、チャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄを超えて帯域幅を割り当てる必要があるため、その超過帯域幅の分だけ、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔをインクリメントした上で、チャネル使用帯域幅ｃ＿ｕｓｅｄと総使用帯域幅ｎｅｔ＿ｕｓｅｄをリクエストサイズ（バイト単位）だけインクリメントすることになる。この場合、チャネルポートは直ちに閉じられる。ステップＳ１８を疑似コードで書けば、次のようになる。
【００８３】
if(c_unused < request_size)
c_credit = c_credit +(request_size - c_unused);
c_used = c_used + request_size;
net_used = net_used + request_size;
【００８４】
ステップＳ１４において、出力ポート４２が閉じている場合（Ｓ１４のＮ）、リクエストが到着したチャネルのチャネルポートが開いているにもかかわらず、出力ポート４２が閉じているということであるから、別のチャネルが「偽空き帯域幅」を使用したことを意味する。この場合、リクエストをチャネルキューにキューイングし、チャネルの基本優先度を「剥奪レベル」に設定する（Ｓ３２）。
【００８５】
次に剥奪された帯域幅ｄｅｐｒｉｖｅｄを求める（Ｓ３４）。剥奪された帯域幅ｄｅｐｒｉｖｅｄは、通常はリクエストサイズであるが、リクエストサイズがチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄを超える場合もあるので、剥奪された帯域幅ｄｅｐｒｉｖｅｄは、正確には、リクエストサイズとチャネル未使用帯域幅ｃ＿ｕｎｕｓｅｄのいずれか小さい方で与えられる。チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔから剥奪された帯域幅ｄｅｐｒｉｖｅｄを引き、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔに剥奪帯域幅ｄｅｐｒｉｖｅｄを加える（Ｓ３６）。ステップＳ３４、３６の疑似コードは次のようになる。
【００８６】
if(c_unused > 0) {
deprived = smallerof(c_unused, request_size);
c_credit = c_credit - deprived;
net_deficit = net_deficit + deprived;
}
【００８７】
［３．６．２］イベントＢ：ディスクスケジューラキューが空
図６は、ステップＳ１２０のイベントＢ「ディスクスケジューラキューが空」が発生したときの処理を示すフローチャートである。マルチプレクサ３０が実際のデバイス帯域幅よりも少ないリクエストを出力すると、ディスクスケジューラキュー２２は各タイムフレームにおいて空き状態になる。ディスクスケジューラキュー２２は、入力されるリクエストが存在しない場合にも空き状態になる。イベントＢ「ディスクスケジューラキューが空」は、ディスクスケジューラキュー２２が空であるとき、ディスクスケジューラ２０が空き帯域幅ポート４４からリクエストの取り出しを試みることにより発生するイベントである。
【００８８】
ディスクスケジューラ２０からの空き帯域幅ポート４４に対するアクセスを受けて、マルチプレクサ３０は、いずれかのチャネルのチャネルキューにリクエストがあるかどうかを調べる（Ｓ５０）。いずれかのチャネルキューにリクエストがある場合、最も優先度が高いチャネルキューからリクエストを取り出し、空き帯域幅ポート４４に渡す（Ｓ５２）。マルチプレクサ３０は、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔと仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔをリクエストサイズだけインクリメントする（Ｓ５４）。
c_credit = c_credit + request_size
net_credit = net_credit + request_size
【００８９】
空き帯域幅ポート４４からリクエストを取得したことが出力ポート４２に通知され、総使用帯域幅ｎｅｔ＿ｕｓｅｄが更新され、その結果、総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄが更新される（Ｓ５５）。更新された総未使用帯域幅ｎｅｔ＿ｕｎｕｓｅｄが正でなければ（Ｓ５６のＮ）、出力ポート４２が閉じられる（Ｓ５７）。
【００９０】
ディスクスケジューラ２０は空き帯域幅ポート４４からリクエストを取得して実行に移す（Ｓ５８）。
【００９１】
帯域幅が本当に空いているかどうかは、当該タイムフレームが終了し、新しいタイムフレームが始まるときまでわからないから、ステップＳ５２〜Ｓ５８は「空き帯域幅」であるとの仮定のもと実行される。もし、「偽空き帯域幅」であった場合は、次のタイムフレームで、チャネルクレジット帯域幅を用いて、エラーが補償される。エラー補償処理については、図７および図８で詳述される。
【００９２】
いずれのチャネルキューにもリクエストが存在しない場合（Ｓ５０のＮ）、マルチプレクサ３０は空き帯域幅ポート４４にリクエストを渡すことがない。このとき、マルチプレクサ３０は、ディスクスケジューラ２０が空き帯域幅ポート４４からリクエストを取り出そうとしていたことから、ディスクスケジューラ２０がアイドルであることを知ることができる。そこで、マルチプレクサ３０は、浪費帯域幅の計測を開始するために現在時刻を記録する（Ｓ５９）。そして、既に図５で述べたように、現タイムフレームにおいて次のリクエストが到着した時点で、マルチプレクサ３０は、浪費帯域幅の計測を終了し、そのときの時刻を記録し、すべてのチャネルについてチャネル浪費帯域幅ｃ＿ｗａｓｔｅｄを更新し、新しいリクエストを処理する前に適宜チャネルポートの状態を変更する（図５ＡのＳ９〜Ｓ１１参照）。
【００９３】
［３．６．３］イベントＣ：新しいタイムフレームの開始
図７は、ステップＳ１３０のイベントＣ「新しいタイムフレームの開始」が発生したときの処理を示すフローチャートである。一つ前のタイムフレームＴＦ（ｎ−１）の期間が終わると、新しいタイムフレームＴＦ（ｎ）が始まる（ここで、ｎはタイムフレームの番号を示す）。新しいタイムフレームＴＦ（ｎ）が始まると、マルチプレクサ３０は、まず、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔがゼロかどうかを調べる（Ｓ６０）。偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔがゼロなら（Ｓ６０のＹ）、マルチプレクサ３０は、すべてのチャネルのチャネル使用帯域幅ｃ＿ｕｓｅｄとチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔをゼロにリセットし、総使用帯域幅ｎｅｔ＿ｕｓｅｄ、仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔもゼロにリセットし（Ｓ６２）、ステップＳ６５に進む。
【００９４】
偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔがゼロでないなら（Ｓ６０のＮ）、一つ前のタイムフレームＴＦ（ｎ−１）で仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔを用いたチャネルは現タイムフレームＴＦ（ｎ）で帯域幅の使用量を減らさなければならない。一つ前のタイムフレームＴＦ（ｎ−１）で超過帯域幅を使用したチャネルに対してチャネル使用帯域幅ｃ＿ｕｓｅｄを増加させることにより、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔに対するエラー補償がなされる（Ｓ６４）。ステップＳ６４のエラー補償処理は、図８で詳述する。
【００９５】
エラー補償処理が終わると、出力ポート４２が開く（Ｓ６５）。各チャネルのチャネル未使用帯域幅を調べ（Ｓ６６）、チャネル未使用帯域幅が正であれば（Ｓ６６のＹ）、そのチャネルのチャネルポートは開き（Ｓ６８）、チャネルポートが開き続けている限り、チャネルキューが空になるまで、チャネルキューで待ち状態にあったリクエストが直ちに、開かれたチャネルポートから出力ポート４２に渡され、出力ポート４２から出力される（Ｓ７０）。チャネルキューからリクエストが出力される度に、そのチャネルのチャネル未使用帯域幅が減少していく。ステップＳ６６において、チャネルのチャネル未使用帯域幅が正でない場合（Ｓ６６のＮ）、チャネルポートは閉じられ、新しいタイムフレームＴＦ（ｎ）において開かれることがない（Ｓ７２）。
【００９６】
図８は、ステップＳ６４のエラー補償処理の詳細な手順を示すフローチャートである。最低優先度のチャネルを選択し（Ｓ８０）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが正であれば（Ｓ８２のＹ）、選択されたチャネルについてステップＳ８４〜Ｓ９２を実行し、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが０になれば（Ｓ８２のＮ）、選択されたチャネルについてステップＳ９４を実行する。次に優先度が低いチャネルがあればそれを選択し（Ｓ９６のＹ）、以降、ステップＳ８２〜Ｓ９４を繰り返し、すべてのチャネルの処理が終われば（Ｓ９６のＮ）、エラー補償処理を終了する。
【００９７】
まず、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが正である場合（Ｓ８２のＹ）について、選択されたチャネルについてのステップＳ８４〜Ｓ９２の処理を説明する。
【００９８】
選択されたチャネルについて、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが正であり（Ｓ８４のＹ）、かつ、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔよりも小さい場合（Ｓ８６のＹ）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔをチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔだけ減算する（Ｓ８８）。そして、チャネル使用帯域幅ｃ＿ｕｓｅｄにチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔを代入し、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔをゼロにする（Ｓ９２）。これにより、このチャネルについては、あたかもチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔ分だけ帯域幅を使用したような状態になる。
【００９９】
チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが正であるが（Ｓ８４のＹ）、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔ以上である場合（Ｓ８６のＮ）、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔを偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔに置き換え、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔをゼロにする（Ｓ９０）。その上で、チャネル使用帯域幅ｃ＿ｕｓｅｄにチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔを代入し、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔをゼロにする（Ｓ９２）。これにより、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔを超えるチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの場合は、いったんチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔを偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔの値に減らした上で、チャネル使用帯域幅ｃ＿ｕｓｅｄに代入される。
【０１００】
チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが正でない場合（Ｓ８４のＮ）、チャネル使用帯域幅ｃ＿ｕｓｅｄにチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔを代入し、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔをゼロにする（Ｓ９２）。したがって、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが負である場合、チャネル使用帯域幅ｃ＿ｕｓｅｄが負になり、その分だけ、チャネル未使用帯域幅ｃ＿ｕｎｓｅｄが増えるから、余分に帯域幅を使用することができることになる。
【０１０１】
偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔがゼロになると（Ｓ８２のＮ）、それ以上のエラー補償処理は不要であるから、選択されたチャネルについて、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔとチャネル使用帯域幅ｃ＿ｕｓｅｄをゼロにする（Ｓ９４）。
【０１０２】
図９は、図８のエラー補償処理の手順を具体的な例を用いて説明する図である。同図は、１つ前のタイムフレームにおける各チャネルのチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔにもとづいて現タイムフレームの各チャネルのチャネル使用帯域幅ｃ＿ｕｓｅｄが決定される様子を示す。
【０１０３】
１つ前のタイムフレームにおける６つのチャネルＣ１〜Ｃ６のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔは、それぞれ２、４、３、１、−４、−１である。１つ前のタイムフレームにおける仮空き帯域幅ｎｅｔ＿ｃｒｅｄｉｔは、チャネルＣ１〜Ｃ４の正のチャネルクレジット帯域幅２、４、３、１の和であり、その値は１０である。一方、１つ前のタイムフレームにおける偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔは、チャネルＣ５、Ｃ６の負のチャネルクレジット帯域幅−４、−１の絶対値の和であり、その値は５である。したがって、現タイムフレームにおいて補償しなければならない帯域幅は５である。
【０１０４】
チャネルＣ１〜Ｃ６はこの順で優先度が低くなるとする。最低優先度のチャネルＣ６を選択し（Ｓ８０）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが５であり（Ｓ８２のＹ）、チャネルＣ６のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが−１である（Ｓ８４のＮ）から、チャネルＣ６のチャネル使用帯域幅ｃ＿ｕｓｅｄは、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値が代入されることにより、−１になる（Ｓ９２）。
【０１０５】
次に優先度が低いチャネルＣ５を選択し（Ｓ９６）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが５であり（Ｓ８２のＹ）、チャネルＣ５のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが−４である（Ｓ８４のＮ）から、チャネルＣ５のチャネル使用帯域幅ｃ＿ｕｓｅｄは、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値が代入されることにより、−４になる（Ｓ９２）。
【０１０６】
さらに次に優先度が低いチャネルＣ４を選択し（Ｓ９６）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが５であり（Ｓ８２のＹ）、チャネルＣ４のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが１であり（Ｓ８４のＹ）、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値１は偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔの値５よりも小さい（Ｓ８６のＹ）から、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔは、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値１だけ減算されることにより、４になる（Ｓ８８）。そして、チャネルＣ４のチャネル使用帯域幅ｃ＿ｕｓｅｄは、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値が代入されることにより、１になる（Ｓ９２）。
【０１０７】
さらに次に優先度が低いチャネルＣ３を選択し（Ｓ９６）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが４であり（Ｓ８２のＹ）、チャネルＣ３のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが３であり（Ｓ８４のＹ）、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値３は偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔの値４よりも小さい（Ｓ８６のＹ）から、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔは、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値３だけ減算されることにより、１になる（Ｓ８８）。そして、チャネルＣ３のチャネル使用帯域幅ｃ＿ｕｓｅｄは、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値が代入されることにより、３になる（Ｓ９２）。
【０１０８】
さらに次に優先度が低いチャネルＣ２を選択し（Ｓ９６）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが１であり（Ｓ８２のＹ）、チャネルＣ２のチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが４であり（Ｓ８４のＹ）、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値４は偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔの値１よりも小さくはない（Ｓ８６のＮ）から、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔを偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔの値１に置き換え、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔをゼロにする（Ｓ９０）。その上で、チャネルＣ２のチャネル使用帯域幅ｃ＿ｕｓｅｄは、置換されたチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの値１が代入されることにより、１になる（Ｓ９２）。
【０１０９】
さらに次に優先度が低いチャネルＣ１を選択し（Ｓ９６）、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔが０になったから（Ｓ８２のＮ）、これ以上のエラー補償は不要であり、チャネルＣ１のチャネル使用帯域幅ｃ＿ｕｓｅｄはゼロに設定される（Ｓ９４）。
【０１１０】
このようにして、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが負であるチャネルのチャネル使用帯域幅ｃ＿ｕｓｅｄはチャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔと等しい負の値にしておき、余分に帯域幅を使用できるようにし、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔが正であるチャネルについては、優先度の低い方のチャネルから順に、チャネルクレジット帯域幅ｃ＿ｃｒｅｄｉｔの分だけ帯域幅を使用したことにしていくことで、偽空き帯域幅ｎｅｔ＿ｄｅｆｉｃｉｔを補償することができる。
【０１１１】
以下、上記の説明では述べなかった点を補足して説明する。
【０１１２】
［４］大きなサイズのデータに対するリクエストの繰り返し処理
ストレージデバイス１５０に格納された画像や音声などの大きなサイズのデータにアクセスする場合、リクエストするブロックのサイズは大きくなり、１つのタイムフレームには収まらないことがある。また、ブロックサイズが１つのタイムフレームに収まる場合でも、タイムフレームの大部分を大きなブロックサイズのリクエストが占有してしまうと、他のリクエストをタイムフレーム内に割り当てることができなくなり、他のリクエストのレスポンスが極端に悪化する。
【０１１３】
そこで、マルチプレクサ３０は、大きなブロックサイズのリクエストを小さなブロックサイズのリクエストに分割し、分割された小さなブロックサイズのリクエストを繰り返し発行することにより、大きなブロックサイズのリクエストを処理する。これにより、大きなブロックサイズのリクエストにより、他のリクエストのレスポンスタイムが悪くなるのを防ぐことができる。
【０１１４】
［５］ディスクスケジューリング
ディスクスケジューラ２０によるディスクスケジューリングの動作について詳しく説明する。ディスクスケジューラ２０は、スループットもしくはレスポンスタイムの性能を最大化するために、ディスクに対するアクセスパターンを考慮してディスクスケジューリングを行う。ディスクスケジューラ２０は、ディスクスケジューリングアルゴリズムを適宜選択し、あるいは組み合わせて用いる。たとえば、レスポンスタイムを良くするためには、シーク時間の短い順にスケジューリングするＳＳＴＦアルゴリズムを用いることができる。また、サービスタイムを良くするためには、エレベータアルゴリズムやＳＣＡＮアルゴリズムを用いることができる。
【０１１５】
ディスクスケジューラ２０は、フレーム内のリクエストをスケジューリングする際、各リクエストのアプリケーションタイプを参考にして、どのようなディスクスケジューリング方式をどのような比率で組み合わせて用いればよいかを判断する。ディスクスケジューラ２０は、アプリケーションタイプをディスクスケジューリングのヒントとして用いる。
【０１１６】
アプリケーションタイプには、マルチメディア、リアルタイム、インタラクティブ、ファイル転送などがある。ディスクスケジューラ２０は、フレーム内にどのようなタイプのリクエストがどれくらいの割合で多重化されているかを判断する。インタラクティブなアプリケーションはレスポンスタイムに敏感であり、マルチメディアアプリケーションはサービスタイムに敏感である。レスポンスタイムに敏感なアプリケーションとサービスタイムに敏感なアプリケーションの比率がα対（１−α）である場合、レスポンスタイムのタイプに適したＳＳＴＦアルゴリズムと、サービスタイムに適したエレベータアルゴリズムもしくはＳＣＡＮアルゴリズムとをα対（１−α）の比で組み合わせて用いる。
【０１１７】
ディスクスケジューラ２０は、さらに、リクエストサイズを一つの要因として評価し、より小さなリクエストサイズのリクエストについては早くサービスするように制御してもよい。そのために、ＳＳＥＤＶ（Shortest Seek and Earliest Deadline by Value）アルゴリズムを改良して用いることができる。
【０１１８】
以上述べたように、本実施の形態のリクエストスケジューラ４０によれば、ディスクスケジューラ２０の前段にマルチプレクサ３０を設け、各コネクションの予約帯域幅を保証しながら、複数のコネクションからのリクエストを多重化することができる。
【０１１９】
マルチプレクサ３０は、チャネルポートと出力ポート４２の２つのポートをもち、各チャネルポートに到着したリクエストの総量がそのチャネルの予約帯域幅の制限を超えない限りは、チャネルポートを開けて、チャネルキューをバイパスして直接、出力ポート４２にリクエストが送られるようにしたことで、チャネルキューへのキューイングによるオーバーヘッドをなくし、チャネルがボトルネックとなることを防ぐことができる。
【０１２０】
また、各チャネルポートに到着したリクエストの総量がそのチャネルの予約帯域幅の制限を超えた場合は、チャネルポートを閉じて、次のタイムフレームが始まるまでチャネルキューにリクエストをキューイングすることで、各チャネルが使用する帯域幅を制限することができる。
【０１２１】
さらに、ディスクスケジューラ２０のキューにリクエストが存在しないときは、いずれかのチャネルキューにキューイングされたリクエストを取り出してディスクスケジューラ２０に渡すための空き帯域幅ポート４４が予備ポートとして、出力ポート４２とは別に設けられているため、空き帯域幅を有効に活用することができる。そして、リクエストが遅れて到着して、空き帯域幅であると仮定したことが誤りであることがわかった場合は、剥奪された帯域幅を次のタイムフレームで補償することで、チャネル間の帯域幅の割り当ての公平性を保証することができる。
【０１２２】
また、本実施の形態によれば、マルチプレクサ３０が、各コネクションが予約するディスク転送の帯域幅に応じて、コネクションからのリクエストを多重化し、ディスクスケジューラ２０が、ディスクアクセスのリクエストをディスクに対するアクセスパターンにもとづいてスケジューリングする。これにより、様々なサービス品質の要求のあるアプリケーションからディスクアクセスリクエストがあった場合、マルチプレクサ３０によるリクエストの多重化により個々のアプリケーションのサービス品質要求を保証することができ、同時に、ディスクスケジューラ２０によるディスクアクセスパターンにもとづくディスクスケジューリングによりディスク性能を最大化することができる。
【０１２３】
ストレージデバイスは、一般的に非決定的（あるいは非確定的）（non-deterministic）な動作をし、ディスクに対するアクセスリクエストがいつ実行されるかを予測することができないが、本実施の形態のリクエストスケジューラ４０によれば、マルチプレクサ３０が各コネクションのリクエストを一定の時間で処理されるタイムフレーム内に多重化し、ディスクスケジューラ２０がタイムフレーム内のリクエストの実行順序を変えることでディスクのスケジューリングを行うため、リクエストが実行される時間は決定的（あるいは確定的）（deterministic）なものとなり、サービス品質の保証が可能になる。
【０１２４】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【０１２５】
マルチプレクサ３０のチャネルは、いろいろな用途で用いることができる。コネクション毎にチャネルを別々に設けてもよく、１つのチャネルを複数のコネクションで共有してもよい。たとえば、リアルタイム、マルチメディア、インタラクティブなどのアプリケーションタイプ毎にチャネルを用意し、同じアプリケーションタイプの複数のコネクションが、対応するアプリケーションタイプのチャネルを共有するようにしてもよい。インタラクティブアプリケーションの複数のコネクションがあれば、それらのコネクションのリクエストは、すべてインタラクティブタイプ用のチャネルにキューイングされる。
【０１２６】
マルチプロセッサシステムにおいてリクエストスケジューラ４０が利用される場合、各プロセッサがストレージデバイス１５０に対してコネクションを構築することができる。その場合、マルチプレクサ３０のチャネルは、プロセッサ毎に設けられてもよく、プロセッサが構築するコネクション毎に設けられてもよい。
【０１２７】
実施の形態では、ディスクスケジューリングを例に説明したが、本発明は、ディスク以外のデバイスに対するアクセススケジューリングにも適用することができる。また、本実施の形態のマルチプレクサ３０をディスクスケジューラ２０から切り離し、ディスクなどのデバイスに対するアクセススケジューリング以外に、複数のコネクションからのリクエストの多重化処理が必要な分野にも適用することができる。たとえば、ネットワークを経由したサーバなどへのアクセスリクエストをＦＩＦＯバッファに蓄積して多重化処理する場合にも適用することができる。
【図面の簡単な説明】
【０１２８】
【図１】実施の形態に係るストレージサブシステムの構成を説明する図である。
【図２】図１のリクエストスケジューラの構成図である。
【図３】図３（ａ）、（ｂ）は、図２のメインチャネルおよび予約チャネルの内部構成とリクエストの入出力制御を詳しく説明する図である。
【図４】図２のリクエストスケジューラによるリクエスト多重化処理の全体的な流れを示すフローチャートである。
【図５Ａ】図４のイベントＡ「リクエスト到着」が発生したときの処理を示すフローチャートである。
【図５Ｂ】図５Ａの浪費帯域幅の更新とチャネルポートの状態の更新の処理を詳しく示すフローチャートである。
【図６】図４のイベントＢ「ディスクスケジューラキューが空」が発生したときの処理を示すフローチャートである。
【図７】図４のイベントＣ「新しいタイムフレームの開始」が発生したときの処理を示すフローチャートである。
【図８】図７のエラー補償処理の詳細な手順を示すフローチャートである。
【図９】図８のエラー補償処理の手順を具体的な例を用いて説明する図である。
【符号の説明】
【０１２９】
１０  デバイスドライバ、  ２０  ディスクスケジューラ、  ２２  ディスクスケジューラキュー、  ３０  ストレージマルチプレクサ、  ３１  メインチャネル、  ３２  予約チャネル、  ３３、３４  チャネルポート、  ３５、３６  チャネルキュー、  ３８  タイマ、  ４０  リクエストスケジューラ、  ４２  出力ポート、  ４４  空き帯域幅ポート、  ５０  ＳＣＳＩクラスドライバ、  ６０  ストレージサービスプロバイダ、  ６２  コネクション、  １００  ストレージサブシステム、  １２０  ストレージインタフェース、  １３０  ファイルシステム、  １４０  オペレーティングシステム、  １５０  ストレージデバイス。
【図１】
2008097312.tif 000003
【図２】
2008097312.tif 000004
【図３】
2008097312.tif 000005
【図４】
2008097312.tif 000006
【図５Ａ】
2008097312.tif 000007
【図５Ｂ】
2008097312.tif 000008
【図６】
2008097312.tif 000009
【図７】
2008097312.tif 000010
【図８】
2008097312.tif 000011
【図９】
2008097312.tif 000012