(57)【要約】【課題】ホストの平均待ち時間を最小にする、再呼び出し要求の処理順を最適化する技術を提供すること。【解決手段】ストレージ・マネージャは、テープ・ライブラリから再呼び出しする必要のあるデータに対するホスト装置の要求を受け付けると、これをキュー・テーブルに格納する。要求の格納に応答して、ストレージ・マネージャは、キュー・テーブル内に格納されている全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての待ち時間を算出する。ストレージ・マネージャは、算出した待ち時間を、実行中の要求を含む全要求について足し合わせ、合計が最小となる実行順を適用すべき実行順として決定し、該実行順に従って、キュー・テーブル内の要求を並び替える。
2010035617.tif 000002
【特許請求の範囲】
【請求項１】
テープ・ライブラリに接続された、データの再呼び出し順を決定するための装置であって、
前記テープ・ライブラリから再呼び出しする必要のあるデータに対するホスト装置の要求を受け付ける要求受付手段と、
前記要求をキュー・テーブルに格納する格納手段と、
前記キュー・テーブルへの前記要求の格納に応答して、前記キュー・テーブル内に格納されている全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての前記要求受付手段による受け付けから前記テープ・ライブラリにおける処理の完了までの待ち時間を予測する第１待ち時間予測手段と、  
前記第１待ち時間予測手段により予測された前記待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となる実行順である第１実行順を、適用すべき実行順として決定する第１実行順決定手段と、
決定された前記適用すべき実行順に従って、前記キュー・テーブル内の前記全要求の実行順を並び替える並び替え手段と、
を含む装置。
【請求項２】
前記第１実行順決定手段は、前記第１待ち時間予測手段により予測された前記待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となり、かつ、各要求の前記待ち時間がいずれも最大許容待ち時間を超えない実行順である第１実行順を、適用すべき実行順として決定する、請求項１に記載の装置。
【請求項３】
前記テープ・ライブラリは複数のテープ・ドライブを含み、前記キュー・テーブル、前記第１待ち時間予測手段及び前記第１実行順決定手段はそれぞれ前記テープ・ドライブ毎に複数用意され、
前記格納手段は１つの前記要求を複数の前記キュー・テーブルにそれぞれ仮想的に格納し、
複数の前記第１実行順決定手段がそれぞれ決定した、複数の前記第１実行順における複数の前記待ち時間の合計の中で、最小の前記待ち時間の合計を決定した前記第１実行順決定手段を用意された前記テープ・ドライブに、前記１つの要求を割り当てる割り当て先決定手段を更に含み、
前記並び替え手段は、前記要求を割り当てられた前記テープ・ドライブに対応する前記キュー・テーブルへの前記１つの要求の格納を確定し、該キュー・テーブル内の全要求の実行順を、前記要求を割り当てられた前記テープ・ドライブに対応する前記第１実行順決定手段により決定された前記前記第１実行順に従って並び替える、
請求項１又は２に記載の装置。
【請求項４】
前記キュー・テーブルへの前記要求の格納に応答して、前記実行中の要求を現在までの処理を行う第１要求と残りの処理を行う第２要求に仮想的に分割し、該第２要求を含む前記キュー・テーブル内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての前記待ち時間を予測する第２待ち時間予測手段と、
前記第２待ち時間予測手段により予測された前記待ち時間を前記第１要求を含む全要求について足し合わせた合計が最小となる実行順を、第２実行順として決定する第２実行順決定手段と、
前記第２実行順における前記待ち時間の合計が、前記第１実行順における前記待ち時間の合計よりも小さい場合に前記第２実行順を、それ以外の場合は前記第１実行順を、前記適用すべき実行順として再決定する適用実行順決定手段と、
前記適用すべき実行順としての前記第２実行順の決定に応答して、前記実行中の要求の処理を中断する中断手段とを更に含む、請求項１に記載の装置。
【請求項５】
前記第１実行順決定手段は、前記第１待ち時間予測手段により予測された前記待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小であり、かつ、各要求の前記待ち時間がいずれも最大許容待ち時間を超えない実行順である第１実行順を、適用すべき実行順として決定し、
前記第２実行順決定手段は、前記第２待ち時間予測手段により予測された前記待ち時間を前記第１要求を含む全要求について足し合わせた合計が最小であり、かつ、各要求の前記待ち時間がいずれも前記最大許容待ち時間を超えない実行順を前記第２実行順として決定する、
請求項４に記載の装置。
【請求項６】
前記テープ・ライブラリは複数のテープ・ドライブを含み、前記キュー・テーブル、前記第１待ち時間予測手段、前記第１実行順決定手段、前記第２待ち時間予測手段、前記第２実行順決定手段、前記中断手段及び前記適用実行順決定手段はそれぞれ前記テープ・ドライブ毎に複数用意され、
前記格納手段は１つの前記要求を複数の前記キュー・テーブルにそれぞれ仮想的に格納し、
複数の前記適用実行順決定手段がそれぞれ決定した、複数の前記適用すべき実行順における複数の前記待ち時間の合計の中で、最小の前記待ち時間の合計を決定した前記適用実行順決定手段を用意された前記テープ・ドライブに、前記１つの要求を割り当てる割り当て先決定手段を更に含み、
前記複数の中断手段はそれぞれ、対応する前記テープ・ドライブに前記１つの要求が割り当てられた場合に、対応する前記第２実行順の前記適用すべき実行順としての決定に応答して、前記実行中の要求の処理を中断し、
前記並び替え手段は、前記要求を割り当てられた前記テープ・ドライブに対応する前記キュー・テーブルへの前記１つの要求の格納を確定し、該キュー・テーブル内の全要求の実行順を、前記要求を割り当てられた前記テープ・ドライブに対応する前記適用実行順決定手段により決定された前記適用すべき実行順に従って並び替える、
請求項４又は５に記載の装置。
【請求項７】
テープ・ライブラリに接続された装置において実行される、データの再呼び出し順を決定するための方法であって、
前記テープ・ライブラリから再呼び出しする必要のあるデータに対するホスト装置の要求を受け付けるステップと、
前記要求をキュー・テーブルに格納するステップと、
前記キュー・テーブルへの前記要求の格納に応答して、前記キュー・テーブル内に格納されている全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての該要求の受け付けから前記テープ・ライブラリにおける処理の完了までの待ち時間を予測するステップと、  
予測した前記待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となる実行順である第１実行順を、適用すべき実行順として決定するステップと、
決定された前記適用すべき実行順に従って、前記キュー・テーブル内の前記全要求の実行順を並び替えるステップと、
を含む方法。
【請求項８】
前記キュー・テーブルへの前記要求の格納に応答して、前記実行中の要求を現在までの処理を行う第１要求と残りの処理を行う第２要求に仮想的に分割し、該第２要求を含む前記キュー・テーブル内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての前記待ち時間を予測するステップと、
予測した前記待ち時間を前記第１要求を含む全要求について足し合わせた合計が最小となる実行順を、第２実行順として決定するステップと、
前記第２実行順における前記待ち時間の合計が、前記第１実行順における前記待ち時間の合計よりも小さい場合に前記第２実行順を、それ以外の場合は前記第１実行順を、前記適用すべき実行順として再決定するステップと、
前記適用すべき実行順としての前記第２実行順の決定に応答して、前記実行中の要求の処理を中断するステップとを更に含む、請求項７に記載の方法。
【請求項９】
テープ・ライブラリに接続された装置において実行される、データの再呼び出し順を決定するためのプログラムであって、前記プログラムは、前記装置に、
前記テープ・ライブラリから再呼び出しする必要のあるデータに対するホスト装置の要求を受け付けるステップと、
前記要求をキュー・テーブルに格納するステップと、
前記キュー・テーブルへの前記要求の格納に応答して、前記キュー・テーブル内に格納されている全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての該要求の受け付けから前記テープ・ライブラリにおける処理の完了までの待ち時間を予測するステップと、  
予測した前記待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となる実行順である第１実行順を、適用すべき実行順として決定するステップと、
決定された前記適用すべき実行順に従って、前記キュー・テーブル内の前記全要求の実行順を並び替えるステップと、
を実行させるプログラム。
【請求項１０】
前記キュー・テーブルへの前記要求の格納に応答して、前記実行中の要求を現在までの処理を行う第１要求と残りの処理を行う第２要求に仮想的に分割し、該第２要求を含む前記キュー・テーブル内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての前記待ち時間を予測するステップと、
予測した前記待ち時間を前記第１要求を含む全要求について足し合わせた合計が最小となる実行順を、第２実行順として決定するステップと、
前記第２実行順における前記待ち時間の合計が、前記第１実行順における前記待ち時間の合計よりも小さい場合に前記第２実行順を、それ以外の場合は前記第１実行順を、前記適用すべき実行順として再決定するステップと、
前記適用すべき実行順としての前記第２実行順の決定に応答して、前記実行中の要求の処理を中断するステップとを更に前記装置に実行させる、請求項９に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想テープ・サーバにおけるボリュームの再呼び出しに関し、詳細には、ボリュームの再呼び出し要求の処理順を、該要求をしたホスト装置の平均待ち時間を最小にする観点から最適化する技術に関する。
【背景技術】
【０００２】
仮想テープ・ストレージ・システムは、ハードディスク・ドライブを用いて、テープ・ドライブ及びテープ・カートリッジをエミュレートする。例えば、ホスト装置は、テープ・ライブラリをエミュレートする一組のハードディスク・ドライブに対して入力／出力（Ｉ／Ｏ）操作を行うことによって、テープ・ライブラリに対するＩ／Ｏ操作を行う。Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ（ＩＢＭ：ＩＢＭはＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）Ｍａｇｓｔａｒ仮想テープ・サーバのような従来技術の仮想テープ・ストレージ・システムでは、少なくとも１つの仮想テープ・サーバ（ＶＴＳ）が、複数のテープ・ドライブ及びテープ・カートリッジを含むテープ・ライブラリに結合される。ＶＴＳはまた、相互接続された複数のハード・ディスク・ドライブから構成された直接アクセス記憶装置（Ｄｉｒｅｃｔ  Ａｃｃｅｓｓ  Ｓｔｏｒａｇｅ  Ｄｅｖｉｃｅ、ＤＡＳＤ）にも結合される。【０００３】
ＤＡＳＤは、テープ・ライブラリ内のボリュームに対するキャッシュとして機能する。ＶＴＳは、ホスト装置から要求を受け取ると、要求されたボリュームをキャッシュから読み出してホスト装置へ返す。要求されたボリュームがキャッシュにない場合、ＶＴＳは、ボリュームをテープ・ライブラリからキャッシュに呼び戻す。キャッシュは、テープ・ライブラリより迅速にＩ／Ｏ要求を満たすことができる。しかしながら、キャッシュの容量はテープ・ライブラリに比較して相対的に小さいので、頻繁にアクセスされるボリュームのみがキャッシュに保持される。ＶＴＳは、ＬＲＵ（最長時間未使用）等のアルゴリズムを採用して、アクセスされなくなったボリュームを、キャッシュからテープ・ライブラリへ転送する。転送されたボリュームはキャッシュから除去され、一例として、テープ・カートリッジ上のデータを指すポインタに短縮される。【０００４】
ところで典型的なＶＴＳでは、ボリュームの再呼び出しに使用可能なテープ・ドライブよりも、仮想ボリュームへのアクセスを提供する仮想デバイスの数の方が多い。そのため、テープ・ドライブよりも多くの仮想デバイスが、キャッシュにない仮想ボリュームにアクセスする場合がある。このような場合、後からなされた再呼び出しは処理待ちのためキューに入れられる。一般に、キューに入れられるこれらの再呼び出しは、先入れ先出し順で処理される。ここで問題となるのが、再呼び出しにかかる時間である。【０００５】
例えば、再呼び出しされたデータを含むテープ・カートリッジが、いずれのテープ・ドライブにもマウントされていない場合、現在マウントされているいずれかのテープ・カートリッジをテープ・ドライブからアンロードしなければならない。このプロセスには１分以上かかる可能性がある。次に、目的のデータを含むテープ・カートリッジをテープ・ドライブにロードし、テープをデータの先頭に位置づける必要がある。このプロセスには１分が費やされる可能性がある。更に、全てのテープ・ドライブが使用中である場合、いずれかのテープ・ドライブにおいて処理が終了するのを待つ必要がある。処理の終了を待つ時間は、実行中の処理に要する時間に依存する。【０００６】
このような問題を解決し、再呼び出し要求の効率を上げるための従来技術として特許文献１が存在する。特許文献１は、１つまたは複数の最適化規則に従ってキューを再配列することにより、キューの処理を最適化する技術を開示する。最適化規則として、特許文献１は、例えば、単一の実装可能メディア上に常駐する論理ボリュームに対応する最小数又は最大数の再呼び出し要求を、キュー内で順次グループ化することや、グループ化において実装可能メディア上の少なくとも２つの再呼び出し要求の物理的場所に従うことを開示する。特許文献１はまた、第１の再呼び出し要求を第２の再呼び出し要求の状況に基づいて処理し、或いは、特定の再呼び出し要求について最小待機しきい値に達した場合に、該要求を、最適化規則を無視して処理する等により、任意の特定の要求について要求者を長く待たせすぎることがないようにする技術も開示する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−１９０２７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記特許文献１に開示される技術により、再呼び出し要求の効率を上げることが可能となる。しかしこれはＶＴＳからみた再呼び出し要求の効率化であって、ホスト装置からみた効率化ではない。上記特許文献１の技術は、ＶＴＳがテープ・ドライブを利用する時間を可能な限り短くする。しかし、ホスト装置の待ち時間は、ＶＴＳがホスト装置の要求を受け付けてからその処理が完了するまでの時間であり、ＶＴＳによって先に受け付けられた要求の処理にかかる時間にも大きく依存する。【０００９】
例えば、処理に非常に長い時間を要する要求がＶＴＳによって先に受け付けられると、その直後に発行されキューに入れられた要求は本来短時間で処理できるものであっても、先の要求の長い処理時間を待たなければならない。その結果、ホスト装置の平均待ち時間は長くなる。なお、特許文献１においても、最小待機しきい値等を設ける等により、ホスト装置への応答時間を保証するよう配慮がなされている。しかし上記特許文献１に開示される技術は、あくまで任意の特定の要求について要求者を長く待たせすぎることがないようするものであり、ホスト装置の平均待ち時間を短くするものではない。実際、特許文献１において、各要求の実際の処理時間は何ら考慮されていない。【００１０】
そこで本発明は、上記の課題、即ち、ホスト装置への応答時間の全要求についての合計を考慮することにより、ホスト装置の平均待ち時間を最小にすることのできる、データの再呼び出し順を決定するための装置、方法、及びプログラムを提供することを目的とする。本発明は更に、実行中の要求をも含めて、ホスト装置への応答時間の全要求についての合計を考慮することにより、ホスト装置の平均待ち時間を最小にすることのできる、データの再呼び出し順を決定するための装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の目的を達成するため、本発明は、キュー・テーブルに入れられた全要求の考え得る全実行順の中から、要求が受け付けられてからその処理が完了するまでの待ち時間の平均が最小となる実行順を求め、該実行順に従ってキュー・テーブル内の要求を並び替える。即ち、本発明は、次のようなテープ・ライブラリに接続された、データの再呼び出し順を決定するための装置によって実現される。この装置は、テープ・ライブラリから再呼び出しする必要のあるデータに対するホスト装置の要求を受け付ける要求受付手段と、要求をキュー・テーブルに格納する格納手段と、キュー・テーブルへの要求の格納に応答して、キュー・テーブル内に格納されている全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての要求受付手段による受け付けからテープ・ライブラリにおける処理の完了までの待ち時間を予測する第１待ち時間予測手段と、第１待ち時間予測手段により予測された待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となる実行順である第１実行順を、適用すべき実行順として決定する第１実行順決定手段と、決定された適用すべき実行順に従って、キュー・テーブル内の全要求の実行順を並び替える並び替え手段とを含む。【００１２】
好ましくは、第１実行順決定手段は、第１待ち時間予測手段により予測された待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となり、かつ、各要求の待ち時間がいずれも最大許容待ち時間を超えない実行順である第１実行順を、適用すべき実行順として決定する。ここで、最大許容待ち時間は、予め管理者により装置に設定されていてもよく、あるいは、ホスト装置から要求と共に指定されるものであってもよい。【００１３】
更に好ましくは、上記テープ・ライブラリは複数のテープ・ドライブを含む。この場合、キュー・テーブル、第１待ち時間予測手段及び第１実行順決定手段はそれぞれテープ・ドライブ毎に複数用意される。そして、上記格納手段は１つの要求を複数のキュー・テーブルにそれぞれ仮想的に格納する。上記装置はまた、複数の第１実行順決定手段がそれぞれ決定した、複数の第１実行順における複数の待ち時間の合計の中で、最小の待ち時間の合計を決定した第１実行順決定手段を用意されたテープ・ドライブに、１つの要求を割り当てる割り当て先決定手段を更に含む。上記並び替え手段は、要求を割り当てられたテープ・ドライブに対応するキュー・テーブルへの１つの要求の格納を確定し、該キュー・テーブル内の全要求の実行順を、要求を割り当てられたテープ・ドライブに対応する第１実行順決定手段により決定された第１実行順に従って並び替える。【００１４】
また本発明では、現在実行中の要求の処理を一旦中断して後に受け付けた要求を先に処理する方が、オーバヘッドを考慮してもホスト装置の平均待ち時間を短縮できる場合があることを考慮する。
即ち、好ましくは上記装置は、キュー・テーブルへの要求の格納に応答して、実行中の要求を現在までの処理を行う第１要求と残りの処理を行う第２要求に仮想的に分割し、該第２要求を含むキュー・テーブル内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての待ち時間を予測する第２待ち時間予測手段と、第２待ち時間予測手段により予測された待ち時間を第１要求を含む全要求について足し合わせた合計が最小となる実行順を、第２実行順として決定する第２実行順決定手段と、第２実行順における待ち時間の合計が、第１実行順における待ち時間の合計よりも小さい場合に第２実行順を、それ以外の場合は第１実行順を、適用すべき実行順として再決定する適用実行順決定手段と、適用すべき実行順としての第２実行順の決定に応答して、実行中の要求の処理を中断する中断手段とを更に含む。【００１５】
更に好ましくは、第１実行順決定手段は、第１待ち時間予測手段により予測された待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小であり、かつ、各要求の待ち時間がいずれも最大許容待ち時間を超えない実行順である第１実行順を、適用すべき実行順として決定する。そして、第２実行順決定手段は、第２待ち時間予測手段により予測された待ち時間を第１要求を含む全要求について足し合わせた合計が最小であり、かつ、各要求の待ち時間がいずれも最大許容待ち時間を超えない実行順を第２実行順として決定する。ここで、最大許容待ち時間は、予め管理者により装置に設定されていてもよく、あるいは、ホスト装置から要求と共に指定されるものであってもよい。【００１６】
更にまた好ましくは、上記テープ・ライブラリは複数のテープ・ドライブを含む。この場合キュー・テーブル、第１待ち時間予測手段、第１実行順決定手段、第２待ち時間予測手段、第２実行順決定手段、中断手段及び適用実行順決定手段はそれぞれテープ・ドライブ毎に複数用意される。そして、上記格納手段は１つの要求を複数のキュー・テーブルにそれぞれ仮想的に格納する。上記装置はまた、複数の適用実行順決定手段がそれぞれ決定した、複数の適用すべき実行順における複数の待ち時間の合計の中で、最小の待ち時間の合計を決定した適用実行順決定手段を用意されたテープ・ドライブに、１つの要求を割り当てる割り当て先決定手段を更に含む。複数の中断手段はそれぞれ、対応するテープ・ドライブに１つの要求が割り当てられた場合に、適用すべき実行順としての対応する第２実行順の決定に応答して、実行中の要求の処理を中断する。上記並び替え手段は、要求を割り当てられたテープ・ドライブに対応するキュー・テーブルへの１つの要求の格納を確定し、該キュー・テーブル内の全要求の実行順を、要求を割り当てられたテープ・ドライブに対応する適用実行順決定手段により決定された適用すべき実行順に従って並び替える。【００１７】
以上、データの再呼び出し順を決定するための装置として本発明を説明したが、本発明は、そのような装置において実行される、データの再呼び出し順を決定するための方法又はプログラムとして把握することもできる。
【発明の効果】
【００１８】
本発明によれば、キュー・テーブルに入れられた各要求は、要求が受け付けられてからテープ・ライブラリにおけるその処理が完了するまでの待ち時間の全要求についての合計が最小となるような実行順に並び替えられる。その結果、本発明に係る装置では、ホスト装置の平均待ち時間を最小にすることができ、ホスト装置からみた再呼び出し要求の効率が上がる。本発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態において使用可能な仮想テープ・システム１００のハードウェア構成の一例を示す図である。
【図２】仮想テープ・サーバ（ＶＴＳ）１１０の概略ブロックの一例を示す図である。
【図３】本発明の第１実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ａの機能構成の一例を示す図である。
【図４】（ａ）は、本発明の第１及び第３実施形態に係るキュー・テーブル３１５の一例を示す図である。（ｂ）は、本発明の第２及び第４実施形態に係るキュー・テーブル３１５の一例を示す図である。
【図５】（ａ）は、受け付け順に要求を処理する場合の、各要求の待ち時間を示す図である。（ｂ）は、本発明の第１及び第３実施形態における、各要求の待ち時間を示す図である。
【図６】（ａ）は、本発明の第１及び第３実施形態に係る待ち時間算出テーブルの一例を示す図である。（ｂ）は、（ａ）は、本発明の第２及び第４実施形態に係る待ち時間算出テーブルの一例を示す図である。
【図７】本発明の第２実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｂの機能構成の一例を示す図である。
【図８】実行中の要求を中断して後の要求を先に処理する場合の、各要求の待ち時間を示す図である。
【図９】本発明の第３実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｃの機能構成の一例を示す図である。
【図１０】本発明の第４実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｄの機能構成の一例を示す図である。
【図１１】本発明の第１実施形態に係るストレージ・マネージャ３００ａの処理の流れを示すフローチャートの一例を示す図である。
【図１２】本発明の第２実施形態に係るストレージ・マネージャ３００ｂの処理の流れを示すフローチャートの一例を示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明を実施するための形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００２１】
図１は、本発明の実施の形態において使用可能な仮想テープ・システム１００の代表的なハードウェア構成の一例を示す。本実施形態に係る仮想テープ・システム１００は、少なくとも１つのホスト装置１０５、少なくとも１つの仮想テープ・サーバ（Ｖｉｒｔｕａｌ  Ｔａｐｅ  Ｓｅｒｖｅｒ、ＶＴＳ）１１０、及びライブラリ・システム１１５を含む。
【００２２】
各ホスト装置１０５ａ、ｂは、パーソナル・コンピュータ、ワークステーション、サーバ、メインフレームのような、当該技術分野において周知のいずれかの計算機とすることができる。また各ホスト装置１０５ａ、ｂは、当該技術分野において周知のいずれかのオペレーティング・システムを含むことができる。ホスト装置１０５とＶＴＳ１１０の間の接続１２０は、ストレージ・エリア・ネットワーク（ＳＡＮ）又は、他の好適な通信チャネル、例えばＩＢＭ（商標）メインフレーム・コンピュータで使用されるエンタープライズ・システム接続（ＥＳＣＯＭ）（商標）チャネルを使用できる。
【００２３】
ＶＴＳ１１０は、当該技術分野において周知のいずれかのサーバ計算機であり、当該技術分野において周知のいずれかのオペレーティング・システムを含む。例えば、本発明の特定の実施において、ＶＴＳ１１０は、ＩＢＭ  ＲＳ／６０００（登録商標）システム、ＩＢＭ  Ｐシリーズ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）を含む１つ又は複数のコンピュータにおいて実施することができ、ＩＢＭ  ＡＩＸ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）オペレーティング・システムを含むことができる。
【００２４】
ＶＴＳ１１０はまた、ストレージの使用を最適化するストレージ・マネージャのようなアプリケーションを含むことができる。ストレージ・マネージャは、独立のアプリケーションとして実装することも、又は複数の他のアプリケーションの一部として実装することもできる。特定の実施においてストレージ・マネージャは、ＩＢＭ  Ｍａｇｓｔａｒ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）仮想テープ・サーバ及びＩＢＭ  ＡＤＳＴＡＲ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）分散型管理（ＡＤＳＭ）ソフトウェア又はＴｉｖｏｌｉ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）ストレージ・マネージャのような自動データ・ストレージ・ライブラリを使用するためのソフトウェアを含むことができる。ストレージ・マネージャは、ホスト装置１０５、後述するＶＴＳ１１０内のキャッシュ、及びライブラリ・システム１１５間のデータ移動作業を行うことができる。
【００２５】
ライブラリ・システム１１５は、Ｍａｇｓｔａｒ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）３４９４テープ・ライブラリのようなテープ・ライブラリ、又は、当該技術分野において周知の他のいずれかの自動データ・ストレージ・ライブラリ・システムとすることができる。特定の実施において、ライブラリ・システム１１５は、ライブラリ・マネージャ１３０、テープ・ドライブ・ユニットとすることができる１以上のテープ・ドライブ装置１３５ａ、ｂ、ｃ、アクセス機構１４０、及び複数のテープ・カートリッジ１４５ａ、…、ｎを含む。計算機によって実現されるライブラリ・マネージャ１３０は、テープ・ドライブ装置１３５及びアクセス機構１４０と相互接続され、これらの動作を制御する。
【００２６】
図１には、３つのテープ・ドライブ装置１３５ａ、ｂ、ｃが示されている。本発明は１つ又は複数のテープ・ドライブ装置１３５を含む仮想テープ・システム１００の下において動作可能である。図１において、ライブラリ・マネージャ１３０と、テープ・ドライブ装置１３５及びアクセス機構１４０との相互接続は、ライブラリ・マネージャ１３０が、テープ・ドライブ装置１３５或いはアクセス機構１４０又はその両方に制御信号を送信及び受信するためのものであることを示すため、破線で示している。その一方で、ＶＴＳ１１０とテープ・ドライブ装置１３５との間の相互接続は、格納又は検索されるデータを送信及び受信するためのものであることから、実線で示している。
【００２７】
ＶＴＳ１１０とテープ・ドライブ装置１３５との間の相互接続１２５は、ＳＡＮ、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、又はインターネットを介して行うことができる。又は、ＶＴＳ１１０とテープ・ドライブ装置１３５は、ポイント・ツー・ポイント又はマルチドロップ・バス接続、例えば、ＳｍａｌｌＣｏｍｐｕｔｅｒ  Ｓｔｏｒａｇｅ  Ｉｎｔｅｒｆａｃｅ（ＳＣＳＩ）インター・フェースを介した直接接続を含む、他の好適なタイプのネットワークを介して接続してもよい。
【００２８】
アクセス機構１４０は、選択されたテープ・カートリッジ１４５を指定されたテープ・ドライブ装置１３５へ移送するように構成された、ロボット・アーム又は他の機械的な装置とすることができる。アクセス機構１４０は、通常はグリッパと、グリッパ上に実装されたバーコード・スキャナまたは同様の読み取りシステムを含む。バーコード・スキャナはテープ・カートリッジ１４５に貼り付けられたカートリッジ・ラベル上に印刷されたボリュームの通し番号を読み取るために使用される。
【００２９】
オペレータ・インタフェース１５０が、ライブラリ・マネージャ１３０に接続される。オペレータ・インタフェース１５０は、ライブラリ・マネージャ１３０と通信する計算機とすることができる。ユーザは、ホスト装置１０５とは独立にライブラリ・システム１１５のオペレーティング・パラメータを制御することができる。
【００３０】
ホスト装置１０５は、ＶＴＳ１１０とテープ操作を取り交わす。テープ操作の実行は、後述するＶＴＳ１１０内のキャッシュ内に格納された論理ボリュームからデータを検索するか、又は、該論理ボリュームにデータを格納するというものである。ＶＴＳ１１０は、キャッシュ内の論理ボリュームを自動的に事前マイグレーション（オフロード）する。特定の実施においては、最長時間未使用の論理ボリュームが、キャッシュからライブラリ・システム１１５内のテープ・カートリッジ１４５へ転送される。ホスト装置１０５が、キャッシュ内にはない論理ボリュームを必要とする場合、ＶＴＳ１１０のストレージ・マネージャは、要求される論理ボリュームを含むテープ・カートリッジ１４５を適当なテープ・ドライブ装置１３５にマウントするよう、ライブラリ・システム１１５、即ちライブラリ・マネージャ１３０に命令する。要求されたデータは、ＶＴＳ１１０のキャッシュ内の論理ボリュームとして、上記テープ・カートリッジ１４５から呼び戻されコピーされる。
【００３１】
図２は、図１に示すＶＴＳ１１０の一実施形態を示す概略ブロック図である。ＶＴＳ１１０は、バス、プロセッサ、メモリ、その他を備えた計算機によって実現できる。しかしながらこれらの要素は、本発明に関するＶＴＳ１１０の様々な実行可能モジュール及びデータ・ブロックをより明確に示すために、図２からは省略されている。またＶＴＳ１１０の実装は、当分野で知られた他の実行可能モジュール及びデータ・ブロックが存在してもよいが、本発明に不可欠な要素に焦点を当てるためにそのような要素は図２では省略している。
【００３２】
図２に示されるように、ＶＴＳ１１０は、複数の仮想テープ・ドライブ２００ａ、…ｍ、ファイル・システム・マネージャ２０５、少なくとも１つの直接アクセス記憶装置（Ｄｉｒｅｃｔ  Ａｃｃｅｓｓ  Ｓｔｏｒａｇｅ  Ｄｅｖｉｃｅ、ＤＡＳＤ）キャッシュ２１０、ストレージ・マネージャ２１５、及びキュー２２０を含む。
【００３３】
ＤＡＳＤキャッシュ２１０は、ホスト装置１０５からのデータを論理ボリューム上にファイルの形式で一時的に格納する。一例によれば、ＤＡＳＤキャッシュ２１０は、ＲＡＩＤ５などの独立ドライブの冗長アレイ内に配置構成可能な１つまたは複数のハードディスク・ドライブにより実現される。ホスト装置１０５からの書き込みコマンド及びデータは、仮想テープ・ドライブ２００によって受け取られ、処理された後、ファイルとしてＤＡＳＤキャッシュ２１０に書き込まれる。その後適当なタイミングで、ストレージ・マネージャ２１５は、テープ・カートリッジ１４５へのファイルのコピーを、ライブラリ・マネージャ１３０に要求する。その後、更新済み論理ボリュームは、ストレージ・マネージャ２１５により、ＤＡＳＤキャッシュ２１０からテープ・ドライブ装置１３５にマウントされた適切なテープ・カートリッジ１４５へ転送される。なお、仮想テープ・ドライブ２００は、ホスト装置１０５からの制御コマンドも処理する。
【００３４】
ファイル・システム・マネージャ２０５は、ＤＡＳＤキャッシュ２１０内のデータ・ストレージを管理及び調整する。ストレージ・マネージャ２１５は、ファイル・システム・マネージャ２０５とテープ・ドライブ装置１３５との間の通信を制御する。ストレージ・マネージャ２１５はまた、ＶＴＳ１１０とライブラリ・マネージャ１３０との間の通信も制御する。ホスト装置１０５が、特定の論理ボリュームを要求すると、仮想テープ・ドライブ２００を介して該要求を受け取ったストレージ・マネージャ２１５は、要求された論理ボリュームがＤＡＳＤキャッシュ２１０内にあるか否かを判断する。
【００３５】
ＤＡＳＤキャッシュ２１０内にない場合、ストレージ・マネージャ２１５は、要求された論理ボリュームの再呼び出しを、ライブラリ・マネージャ１３０に要求する。その後テープ・ドライブ装置１３５からＶＴＳ１１０へ戻された要求された論理ボリュームは、ＤＡＳＤキャッシュ２１０にコピーされるとともに、仮想テープ・ドライブ２００を介してホスト装置１０５へ返される。ストレージ・マネージャ２１５は、追加の再呼び出し要求を一時的に入れるためのキュー２２０を含むことができる。従って、ストレージ・マネージャ２１５は、テープ・ドライブ装置１３５を用いてテープ・カートリッジ１４５から論理ボリュームを再呼び出しするための装置である。
【００３６】
なお、図１に示すライブラリ・マネージャ１３０は、その内部に、論理ボリューム及び物理ボリュームに関する情報を格納するデータ・ベース（図示しない）を有する。ＶＴＳ１１０から命令を受け取ると、ライブラリ・マネージャ１３０は、そのデータ・ベースを参照して、論理ボリュームのコピーが作成される又は検索されることになるテープ・カートリッジ１４５を見つけ、該テープ・カートリッジ１４５をマウントするための命令を、適切なテープ・ドライブ装置１３５あるいはアクセス機構１４０またはその両方へ送る。  
【００３７】
（第１実施形態）図３は、本発明の第１実施形態に係る、データの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ａの機能構成の一例を示す図である。なお、第１実施形態では、図１に示すライブラリ・システム１１５はテープ・ドライブ装置１３５を１つのみ含むものとする。第１実施形態に係るストレージ・マネージャ３００ａは、キュー・テーブルに入れられた全要求の考え得る全実行順の中から、要求が受け付けられてからライブラリ・システム１１５におけるその処理が完了するまでの待ち時間の平均が最小となる実行順を求め、該実行順に従ってキュー・テーブル内の要求を並び替える。
【００３８】
そのような第１実施形態に係るストレージ・マネージャ３００ａは、要求受付部３０５、格納部３１０、キュー・テーブル３１５、最小待ち時間決定部３２０ａ、並び替え部３３５を含む。ここで、最小待ち時間決定部３２０ａは、第１待ち時間予測部３２５及び第１実行順決定部３３０を含む。
【００３９】
要求受付部３０５は、ライブラリ・システム１１５から再呼び出しする必要のあるデータに対するホスト装置１０５の要求Ｘを受け付ける。このとき、要求受付部３０５は、要求Ｘの受信時刻として現在時刻を取得する。要求受付部３０５はまた、要求Ｘを一意に識別するためのコマンドＩＤを、受け付けた要求に割り当てる。なお、要求受付部３０５が受け付けるホスト装置１０５の要求Ｘは、データの読出し又は書込み要求のいずれかであり得るが、本実施例ではデータの読出し要求について説明する。
【００４０】
ホスト装置１０５からのデータ読出し要求には、目的のデータを識別するための情報が含まれる。そこで、要求受付部３０５は、目的のデータの識別情報から、目的のデータが記録されているメディアＩＤ、即ちテープ・カートリッジの識別子、テープ・カートリッジ上の読出し開始位置、目的のデータの読出しにかかる実行時間、及びテープ・カートリッジ上の読出し終了位置を決定する。ここで、実行時間は、読出し開始位置から読出し終了位置までテープを移動させるために要する時間を意味する。実行時間を求めるに際しては、例えば、デフォルト設定されている読出し時のテープ速度（例えば８．５ｍ／ｓｅｃ）を利用できる。要求受付部３０５は、受け付けた要求に関する各種情報を、格納部３１０へ渡す。
【００４１】
格納部３１０は、要求受付部３０５により受け付けられた要求Ｘをキュー・テーブル３１５に格納する。図４（ａ）は、本発明に係るキュー・テーブル３１５の一例を示す。図４（ａ）に示すように、本実施例におけるキュー・テーブル３１５は、コマンドＩＤフィールド、受信時刻フィールド、メディアＩＤフィールド、開始位置フィールド、実行時間フィールド、及び終了位置フィールドを含む。格納部３１０は、要求受付部３０５から渡された各種情報を、キュー・テーブル３１５の対応するフィールドにそれぞれ格納する。なお、要求Ｘは、処理のためにキュー・テーブル３１５から取り出される際にキュー・テーブル３１５から削除される。しかしながら、取り出された要求Ｘの各種情報は、その処理開始時刻とともに、要求Ｘの処理が完了するまでメモリに保持される。図４（ａ）では、理解を容易にするため、処理中の要求（コマンド＃０）のエントリを含む、開始時刻フィールドを有するキュー・テーブル３１５を示す。
【００４２】
第１待ち時間予測部３２５は、キュー・テーブル３１５への要求Ｘの格納に応答して、キュー・テーブル３１５内に格納されている全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての待ち時間を予測する。ここで、待ち時間とは、要求受付部３０５による要求Ｘの受け付けから要求Ｘのライブラリ・システム１１５における処理の完了までの時間を意味する。このような要求Ｘの待ち時間ＴＸは、次の式により表すことができる。
ＴＸ＝ＷＸ（ｏ）＋ＡＸ（ｐ、ｎ）  ―（１）
【００４３】
式（１）において、ＷＸ（ｏ）は、要求受付部３０５において要求Ｘが受け付けられてから要求Ｘの処理が開始されるまでの、開始前待ち時間を表す。ＷＸ（ｏ）は、キュー・テーブル３１５に格納されている全要求の処理順に依存する関数である。また、ＡＸ（ｐ、ｎ）は、要求Ｘの処理が開始されてから終了するまでの処理所要時間を表す。ＡＸ（ｐ、ｎ）は、直前及び直後に処理される要求に依存する関数である。処理所要時間を表すＡＸ（ｐ、ｎ）はまた、次の式により表すことができる。
ＡＸ（ｐ、ｎ）＝ＬＸ（ｐ）＋ＳＸ（ｐ）＋ＣＸ＋ＲＸ（ｎ）＋ＵＸ（ｎ）―（２）
【００４４】
ＬＸ（ｐ）は、要求Ｘが対象とするデータを記録するメディア、即ちテープ・カートリッジ１４５をテープ・ドライブ装置１３５にロードするのに必要なロード時間を表す。ロード時間は、厳密にはテープ・カートリッジ１４５の格納場所とテープ・ドライブ装置１３５の物理的な位置関係に依存すると考えられる。しかし、テープドライブ装置１３５がテープ・カートリッジ１４５をアンロードしている間に、アクセス機構１４０が次に使用するテープ・カートリッジ１４５をテープドライブ装置１３５のすぐ傍に移動させるライブラリ・システム１１５の下では、違いはない。本実施例ではＬＸ（ｐ）は、予め定めたロード時間、例えば１０秒とする。但し、要求Ｘが対象とするデータが、直前に処理される要求と同じテープ・カートリッジ１４５に記録されている場合、テープ・カートリッジ１４５をロードする必要はないため、ＬＸ（ｐ）は０となる。以上のようにＬＸ（ｐ）は、直前に処理される要求に依存する関数である。
【００４５】
ＳＸ（ｐ）は、要求Ｘが対象とするデータの読出し開始位置にテープを移動させるのに必要な位置合わせ時間を表す。ＳＸ（ｐ）は、テープの先頭から要求Ｘが対象とするデータの読出し開始位置までのテープの長さを、テープの移動速度で割ることにより求められる。テープの移動速度は、デフォルト設定されているテープの移動速度（例えば、１０ｍ／ｓｅｃ）を利用できる。但し、要求Ｘが対象とするデータが、直前に処理される要求と同じテープ・カートリッジ１４５に記録されている場合、関数ＳＸ（ｐ）は、直前の要求のデータの読出し終了位置から、要求Ｘが対象とするデータの読出し開始位置までのテープの長さを、テープの移動速度で割ることにより求められる。以上のようにＳＸ（ｐ）は、直前に処理される要求に依存する関数である。
【００４６】
ＣＸは、上述した、目的のデータの読出しに実際にかかる実行時間を表す。ＲＸ（ｎ）は、目的のデータの読出し終了後に、テープをその先頭まで巻き戻すのに必要な巻き戻し時間を表す。ＲＸ（ｎ）は、要求Ｘが対象とするデータの読出し終了位置からテープの先頭からまでのテープの長さを、テープの移動速度で割ることにより求められる。テープの移動速度は、上述したようにデフォルト設定されているテープの移動速度（例えば、１０ｍ／ｓｅｃ）を利用できる。但し、要求Ｘが対象とするデータが、直後に処理される要求と同じテープ・カートリッジ１４５に記録されている場合、テープの巻き戻しは必要ないため、ＲＸ（ｎ）は０となる。以上のようにＲＸ（ｐ）は、直後に処理される要求に依存する関数である。
【００４７】
最後にＵＸ（ｎ）は、データの読出しが終了したテープ・カートリッジ１４５を、テープ・ドライブ装置１３５からアンロードするのに必要なアンロード時間を表す。なお、テープ・ドライブ装置１３５は、テープ・カートリッジ１４５をアンロードした後は次の処理を行うことができるため、本実施例におけるアンロード時間は、テープ・カートリッジ１４５をテープ・ドライブ装置１３５からもとの格納場所まで移動させるに要する時間を含まないものとする。本実施例では、ＵＸ（ｐ）は、予め定めたアンロード時間、例えば２０秒とする。但し、要求Ｘが対象とするデータが、直後に処理される要求と同じテープ・カートリッジ１４５に記録されている場合、テープ・カートリッジ１４５をアンロードする必要はないため、ＵＸ（ｐ）は０となる。以上のようにＵＸ（ｐ）は、直後に処理される要求に依存する関数である。
【００４８】
ここで、図５（ａ）及び（ｂ）を参照して、ＷＸ（ｏ）が、キュー・テーブル３１５に格納されている全要求の処理順に依存することを説明する。図５（ａ）及び（ｂ）では、現在時刻Ｔｃｕｒにおいて要求（コマンド＃０）の再呼び出し要求が処理されており、キュー・テーブル３１５には、要求（コマンド＃１）と、時刻Ｔｃｕｒに受け付けられたばかりの要求（コマンド＃２）が格納されているものとする。そして、要求（コマンド＃１）の実行時間Ｃ１は非常に長く、一方要求（コマンド＃２）の実行時間Ｃ２は非常に短いとする。
【００４９】
図５（ａ）及び（ｂ）において、時刻ＴＲ０、ＴＲ１、ＴＲ２はそれぞれ、要求（コマンド＃０）〜要求（コマンド＃２）の要求受付部３０５における受付時刻を示す。また時刻ＴＳ０は、要求（コマンド＃０）の処理開始時刻を、時刻ＴＥ０、ＴＥ１／Ｔ’Ｅ１、ＴＥ２／Ｔ’Ｅ２はそれぞれ、要求（コマンド＃０）〜要求（コマンド＃２）の処理終了時刻を示す。なお、理解を容易にするため、要求（コマンド＃０）〜要求（コマンド＃２）がそれぞれ目的とするデータは、いずれも同じテープ・カートリッジ１４５に記録されているものとする。
【００５０】
このような状況において、要求受付部３０５における受付時刻の早い順に要求を処理する場合の各要求の開始前待ち時間Ｗ及び処理所要時間Ａを示したのが図５（ａ）である。図５（ａ）をみると分かるように、要求（コマンド＃１）の処理所要時間Ａ１５０８がその実行時間Ｃ１に起因して非常に長いため、要求（コマンド＃２）の開始前待ち時間Ｗ２５１０は、その処理所要時間Ａ２５１２は非常に短いにも関わらず、長くなっている。
【００５１】
一方、要求（コマンド＃１）よりも後に受け付けられた要求（コマンド＃２）を先に処理した場合の各要求の開始前待ち時間Ｗ及び処理所要時間Ａを示したのが図５（ｂ）である。この場合、要求（コマンド＃２）は、長い実行時間Ｃ１を有する要求（コマンド＃１）の処理を待つ必要がないため、その開始前待ち時間Ｗ２５２６は、図５（ａ）における要求２の開始前待ち時間Ｗ２５１０よりも非常に短くなっている。一方要求（コマンド＃１）の開始前待ち時間Ｗ１５３０は、５（ａ）における要求（コマンド＃１）の開始前待ち時間Ｗ１５０６よりも長くなっているが、先に処理される要求（コマンド＃２）の実行時間Ｃ２が非常に短いため、その差はわずかである。結果、要求（コマンド＃０）〜要求（コマンド＃２）の待ち時間の平均は、図５（ａ）の場合よりも図５（ｂ）の場合のほうが小さい。このように、要求Ｘの開始前待ち時間ＷＸ（ｏ）は、キュー・テーブル３１５に格納されている全要求の処理順に依存する。
【００５２】
第１待ち時間予測部３２５は、上述した式（１）及び（２）を用いて、キュー・テーブル３１５内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求の待ち時間を予測する。一例として、第１待ち時間予測部３２５は、次のようにして各要求の待ち時間を算出する。なお、説明のため、現在要求（コマンド＃０）の再呼び出しが処理中であり、キュー・テーブル３１５には、要求（コマンド＃１）〜要求（コマンド＃Ｎ）までのＮ個の要求が格納されていると仮定する。すると、全要求の考え得る実行順はＮ！通り存在する。そこで、Ｎ！通りの実行順について、図６（ａ）に示すような待ち時間算出テーブルを順に作成する。
【００５３】
図６（ａ）に示す複数の待ち時間算出テーブルの各々は、コマンドＩＤフィールド、受信時刻フィールド、開始時刻フィールド、処理所要時間フィールド、完了時刻フィールド、待ち時間フィールドを有する。ここである１つの実行順Ｄについて、待ち時間算出テーブルの作成方法を説明する。実行順Ｄの待ち時間算出テーブルを完成させるため、まず、実行順Ｄに従って順に、各要求のコマンドＩＤと受信時刻とを待ち時間算出テーブルに登録する。ここで、登録する要求は現在処理中の要求（コマンド＃０）も含む。但し、どの実行順の待ち時間算出テーブルについても、要求（コマンド＃０）は実行順０として待ち時間算出テーブルの最初に登録する。
【００５４】
次に、上述した式（２）を用いて、実行順Ｄに従って順に各要求の処理所要時間を算出し、算出した処理所要時間を待ち時間算出テーブルに登録する。なお、任意の要求Ｘの処理所要時間ＡＸ（ｐ、ｎ）は、その前後に実行される要求が定まれば、キュー・テーブル３１５内の値を使用して、上記式（２）により求めることができることに留意されたい。但し、要求（コマンド＃０）の直前に処理された要求のメディアＩＤと読出し終了位置は、常にメモリに一時的に保持しておくものとし、要求（コマンド＃０）の処理所要時間ＡＸ（ｐ、ｎ）を求める際に参照するものとする。
【００５５】
そして次に、キュー・テーブル３１５から要求（コマンド＃０）の開始時刻ＴＳ０を読み出して待ち時間算出テーブルに登録する。また、要求０の開始時刻ＴＳ０に要求（コマンド＃０）の処理所要時間Ａ０を足し合わせることにより、要求０の完了時刻ＴＥ０を求める。最終的に要求（コマンド＃０）の待ち時間は、完了時刻ＴＥ０から受信時刻ＴＲ０を引くことにより求まる。  
【００５６】
他の要求についても、要求（コマンド＃０）と同様の処理を実行順Ｄに従って順に行う。但し、他の要求についての開始時刻は、該要求の直前の要求の完了時刻となる。そして上記待ち時間算出テーブル作成処理を、Ｎ！通りの実行順それぞれについて行うと、最終的に、全実行順のそれぞれについて、該実行順で処理した場合の各要求の待ち時間が求まる。
【００５７】
第１実行順決定部３３０は、第１待ち時間予測部３２５により予測された待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となる実行順である第１実行順を、適用すべき実行順として決定する。第１実行順決定部３３０は、第１待ち時間予測部３２５により作成されたＮ！個の待ち時間算出テーブルのそれぞれについて、要求０〜Ｎまでの待ち時間の合計を算出する。そして、第１実行順決定部３３０は、待ち時間の合計が最小となる待ち時間算出テーブルに対応する実行順である第１実行順を、実際に適用すべき実行順として決定する。
【００５８】
好ましくは第１実行順決定部３３０は、第１待ち時間予測部３２５により予測された待ち時間を実行中の要求を含む全要求について足し合わせた合計が最小となり、かつ、各要求の待ち時間がいずれも最大許容待ち時間を超えない実行順である第１実行順を、適用すべき実行順として決定する。こで、最大許容待ち時間は、予め管理者により装置に設定されていてもよく、あるいは、ホスト装置１０５から要求と共に指定されるものであってもよい。
【００５９】
この場合、第１実行順決定部３３０は、第１待ち時間予測部３２５により作成されたＮ！個のテーブルから、要求（コマンド＃０）〜要求（コマンド＃Ｎ）までの各待ち時間がいずれも最大許容待ち時間を超えていない待ち時間算出テーブルを取り出す。そして第１実行順決定部３３０は、取り出した待ち時間算出テーブルそれぞれについて、要求（コマンド＃０）〜要求（コマンド＃Ｎ）までの待ち時間の合計を算出する。最後に第１実行順決定部３３０は、待ち時間の合計が最小となる待ち時間算出テーブルに対応する実行順である第１実行順を、実際に適用すべき実行順として決定する。
【００６０】
並び替え部３３５は、第１実行順決定部３３０により決定された適用すべき実行順に従って、キュー・テーブル３１５内の全要求の実行順を並び替える。
【００６１】
このように第１実施形態に係るストレージ・マネージャ３００ａでは、キュー・テーブル３１５に入れられた各要求は、要求が受け付けられてからその処理が完了するまでの待ち時間の全要求についての合計が最小となるような実行順に並び替えられる。その結果、本発明に係る装置では、ホスト装置１０５の平均待ち時間を最小にすることができ、ホスト装置からみた再呼び出し要求の効率が上がる。
【００６２】
（第２実施形態）図７は、本発明の第２実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｂの機能構成の一例を示す図である。なお、第２実施形態においても、図１に示すライブラリ・システム１１５はテープ・ドライブ装置１３５を１つのみ含むものとする。第２実施形態に係るストレージ・マネージャ３００ｂは、現在実行中の要求の処理を一旦中断して後に受け付けた要求を先に処理する方が、オーバヘッドを考慮してもホスト装置１０５の平均待ち時間を短縮できる場合があることを考慮する。
【００６３】
そのように現在実行中の要求の処理を一旦中断した方が、ホスト装置１０５の平均待ち時間を短縮できる場合を、図５（ａ）及び図８を参照して説明する。図５（ａ）及び図８では、現在時刻Ｔｃｕｒにおいて要求（コマンド＃０）の再呼び出し要求が処理されており、キュー・テーブル３１５には、要求（コマンド＃１）と、時刻Ｔｃｕｒに受け付けられたばかりの要求（コマンド＃２）が格納されているものとする。そして、要求（コマンド＃０）の実行時間Ｃ０と要求（コマンド＃１）の実行時間Ｃ１は非常に長く、一方要求（コマンド＃２）の実行時間Ｃ２は非常に短いとする。
【００６４】
また図５（ａ）及び図８において、時刻ＴＲ０、ＴＲ１、ＴＲ２はそれぞれ、要求（コマンド＃０）〜要求（コマンド＃２）の要求受付部３０５における受付時刻を示す。時刻ＴＳ０は、要求（コマンド＃０）の処理開始時刻を示す。図５（ａ）において、時刻ＴＥ０、ＴＥ１、ＴＥ２はそれぞれ、要求（コマンド＃０）〜要求（コマンド＃２）の処理終了時刻を示す。また、図８において、時刻Ｔ’Ｅ０は要求（コマンド＃０）を中断した時刻（同時に、現在時刻Ｔｃｕｒ、要求（コマンド＃２）の受付時刻でもある）、Ｔ’’Ｅ0、Ｔ’’Ｅ１、Ｔ’’Ｅ２はそれぞれ、再開した要求（コマンド＃０）、要求（コマンド＃１）及び要求（コマンド＃２）の処理終了時刻を示す。なお、理解を容易にするため、要求（コマンド＃０）〜要求（コマンド＃２）がそれぞれ目的とするデータは、いずれも同じテープ・カートリッジ１４５に記録されているものとする。
【００６５】
このような状況において、要求受付部３０５における受付時刻の早い順に要求を処理する場合の各要求の開始前待ち時間Ｗ及び処理所要時間Ａを示したのが図５（ａ）である。図５（ａ）をみると分かるように、要求（コマンド＃０）の処理所要時間Ａ０５０４及び要求（コマンド＃１）の処理所要時間Ａ１５０８がその実行時間Ｃ０、Ｃ１に起因してそれぞれ非常に長いため、要求（コマンド＃２）の開始前待ち時間Ｗ２５１０は、その処理所要時間Ａ２５１２は非常に短いにも関わらず、長くなっている。
【００６６】
一方、要求（コマンド＃０）の再呼び出し処理を、要求（コマンド＃２）を受け付けた現在時刻Ｔｃｕｒで一旦中断して、要求（コマンド＃２）を先に処理した場合の各要求の開始前待ち時間Ｗ及び処理所要時間Ａを示したのが図８である。この場合、要求（コマンド＃２）は、長い実行時間Ｃ０、Ｃ１をそれぞれ有する要求０及び要求１の処理を待つ必要がないため、その開始前待ち時間は０となっている。なお、要求（コマンド＃０）と要求（コマンド＃２）が、それぞれ異なるテープ・カートリッジ１４５に記録されているデータを目的とする場合は、要求（コマンド＃２）は、要求（コマンド＃０）についての巻き戻し時間Ｒ１（ｎ）及びアンロード時間Ｕ１（ｎ）を待つ必要がある。
【００６７】
一方、要求（コマンド＃０）は、処理の再開を待つため、新たに開始前待ち時間Ｗ’０８０８の待ち時間が発生する。また、要求（コマンド＃１）も、要求（コマンド＃２）の処理を待つ必要があるため、その開始前待ち時間Ｗ１８１２は図５（ａ）の開始前待ち時間Ｗ１５０６よりも長くなっている。しかし要求（コマンド＃２）の実行時間Ｃ２が非常に短いため、その影響はわずかである。結果、要求（コマンド＃０）〜要求（コマンド＃２）の待ち時間の平均は、図５（ａ）の場合よりも図８の場合のほうが短い。なお、要求（コマンド＃０）の待ち時間は、Ｗ０８０２、Ａ’０８０４、Ｗ’０８０８及びＡ’’０８１０の合計となる。このように、現在実行中の要求の処理を一旦中断した方が、ホスト装置１０５の平均待ち時間を短縮できる場合がある。なお、中断する前に要求（コマンド＃０）について読み出したデータは一時的に保持しておいてもよい。そして要求（コマンド＃０）を再開する際には、残りのデータのみを読み出すようにしてもよい。    
【００６８】
このように現在処理中の要求の中断を考慮する、第２実施形態に係るストレージ・マネージャ３００ｂは、第１実施形態に係るストレージ・マネージャ３００と一部同じ機能構成を有する。しかし、第２実施形態に係る最小待ち時間決定部３２０は、更に、現在実行中の要求の処理を一旦中断すると仮定した場合の最小の待ち時間の平均値を求めるための、第２待ち時間予測部３４０及び第２実行順決定部３４５を含む。また、第２実施形態に係る最小待ち時間決定部３２０は、現在実行中の要求の処理を中断しないと仮定した場合の最小の待ち時間の平均値と、現在実行中の要求の処理を一旦中断すると仮定した場合の最小の待ち時間の平均値とを比較し、中断した方が待ち時間の平均値が小さくなる場合に現在実行中の要求の処理を中断するための、適用実行順決定部３５０及び中断部３５５を含む。
【００６９】
そこで以下では、新たに追加される上記複数の構成要素について説明をする。なお、第２待ち時間予測部３４０及び第２実行順決定部３４５による処理は、第１待ち時間予測部３２５及び第１実行順決定部３３０による処理から独立しており、従って、これらの処理は同時になされてもよく、又はいずれか一方が先になされてもよく、どちらでもよい。
【００７０】
第２待ち時間予測部３４０は、キュー・テーブル３１５への要求Ｘの格納に応答して、実行中の要求を現在までの処理を行う第１要求と残りの処理を行う第２要求に仮想的に分割し、該第２要求を含むキュー・テーブル３１５内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての待ち時間を予測する。第２待ち時間予測部３４０による処理の具体的な方法を以下に説明する。
【００７１】
まず、第２待ち時間予測部３４０は、キュー・テーブル３１５への要求Ｘの格納に応答して、キュー・テーブル３１５のコピーを作成する。但し、キュー・テーブル３１５のコピーには、第１要求と第２要求のエントリを追加する。例えば、要求Ｘが要求受付部３０５により受け付けられたとき、要求（コマンド＃０）が処理中であり、図４（ａ）に示すキュー・テーブル３１５があったと仮定する。なお第１実施形態に関して説明したように、図４（ａ）に示すキュー・テーブル３１５には、説明を容易にするため、要求（コマンド＃０）のエントリを残し、また、開始時間フィールドを設けている。実際はこれらのデータは、キュー・テーブル３１５とは別にメモリに保持されている。すると、第２待ち時間予測部３４０は、図４（ａ）に示すキュー・テーブル３１５を基に、図４（ｂ）に示す新たなキュー・テーブルを作成する。
【００７２】
図４（ａ）において、現在処理中の要求のコマンドＩＤはコマンド＃０である。また、図４（ｂ）において、現在処理中の要求を分割してできた第１要求と第２要求のコマンドＩＤはそれぞれ、コマンド＃０−１とコマンド＃０−２である。第２要求のメディアＩＤフィールドと終了位置フィールド、また、第１要求の受信時刻フィールド、メディアＩＤフィールド、開始位置フィールド及び開始時刻フィールドには、元の現在処理中の要求、即ちコマンド＃０のエントリの対応する値がそのままコピーされる（図４（ａ）及び図４（ｂ）参照）。第１要求の残りのフィールド、即ち、第１要求の終了位置フィールドには、要求Ｘがキュー・テーブル３１５へ入れられた時点におけるテープ・ドライブ装置１３５のヘッドの現在位置Ｅ’０が登録される。第１要求の実行時間フィールドには、開始位置Ｓ０から終了位置Ｅ’０までの距離を、読出し時のテープ速度（例えば８．５ｍ／Ｓｅｃ）で割った値Ｃ’０が登録される。
【００７３】
一方、第２要求の開始位置フィールドには、第１要求の終了位置Ｅ’０の値が登録される。また第２要求の実行時間フィールドには、元の現在処理中の要求、即ちコマンド＃０の実行時間Ｃ０から第１要求の実行時間Ｃ’０を引いた値Ｃ’’０が登録される。なお、第２要求の受信時刻フィールドは、空欄のままとする。これは次の理由による。第２要求の受信時刻は、第１要求の処理の完了時刻となる。しかし、第１要求の処理は、現在処理中の要求（コマンド＃０）の中断の決定と同時に終了するのではなく、第１要求についてのテープの巻き戻し、及びテープ・カートリッジのアンロードが終了した時点で終了する。そして、巻き戻し時間Ｒとアンロード時間Ｕは、上述したように、直後の要求に依存する。そのため、第１要求の次に処理される要求が決定されないことには、第１要求の処理の完了時刻を算出することはできない。
【００７４】
キュー・テーブル３１５のコピーが作成できると、第２待ち時間予測部３４０は、第1実施形態に関して説明した待ち時間算出テーブルを、第1実施形態に関して説明したのと基本的に同様の方法で作成する。そのような待ち時間算出テーブルを図６（ｂ）に示す。なお、第２待ち時間予測部３４０は、処理中の要求（コマンド＃０）を仮想的に分割して、実行中の第１要求と処理待ちの第２要求として取り扱う。そのため、キュー・テーブル３１５内の処理待ちの要求の数が１つ増えたのと等しくなり、第２待ち時間予測部３４０は、待ち時間算出テーブルを作成するに当たって、キュー・テーブル３１５ではなく、上記作成したキュー・テーブル３１５のコピーを利用する。また、全要求について考えられる実行順は（Ｎ＋１）！通りとなるため、（Ｎ＋１）！個の待ち時間算出テーブルが作成される。
【００７５】
なお、いずれの待ち時間算出テーブルにおいても、要求２の受信時刻フィールドは、第１要求の処理の完了時刻の算出後に、該完了時刻が登録されることに留意されたい。第２待ち時間予測部３４０によって、（Ｎ＋１）！個の待ち時間算出テーブルが作成されると同時に、第２要求を含むキュー・テーブル３１５内に格納された全要求の考え得る全実行順のそれぞれについて、該実行順で処理した場合の各要求についての待ち時間が求まる。
【００７６】
第２実行順決定部３４５は、第２待ち時間予測部３４０により予測された待ち時間を第１要求を含む全要求について足し合わせた合計が最小となる実行順を、第２実行順として決定する。第２実行順決定部３４５は、第２待ち時間予測部３４０により作成された（Ｎ＋１）！個の待ち時間算出テーブルのそれぞれについて、第１要求（コマンド＃０−１）、第２要求（コマンド＃０−２）、及び要求（コマンド＃１）〜要求（コマンド＃Ｎ）までの待ち時間の合計を算出する。そして、第２実行順決定部３４５は、待ち時間の合計が最小となる待ち時間算出テーブルに対応する実行順を、第２実行順として決定する。
【００７７】
好ましくは第２実行順決定部３４５は、第２待ち時間予測部３４０により予測された待ち時間を第１要求を含む全要求について足し合わせた合計が最小となり、かつ、各要求の待ち時間がいずれも最大許容待ち時間を超えない実行順を、第２実行順として決定する。ここで、最大許容待ち時間は、予め管理者により装置に設定されていてもよく、あるいは、ホスト装置１０５から要求と共に指定されるものであってもよい。
【００７８】
この場合、第２実行順決定部３４５は、第２待ち時間予測部３４０により作成された（Ｎ＋１）！個の待ち時間算出テーブルから、第１要求（コマンド＃０−１）、第２要求（コマンド＃０−２）、及び要求（コマンド＃１）〜要求（コマンド＃Ｎ）の各待ち時間がいずれも最大許容待ち時間を超えていない待ち時間算出テーブルを取り出す。そして第２実行順決定部３４５は、取り出した待ち時間算出テーブルについて、第１要求（コマンド＃０−１）、第２要求（コマンド＃０−２）、及び要求（コマンド＃１）〜要求（コマンド＃Ｎ）までの待ち時間の合計を算出する。最後に第２実行順決定部３４５は、待ち時間の合計が最小となる待ち時間算出テーブルに対応する実行順を、第２実行順として決定する。
【００７９】
適用実行順決定部３５０は、第２実行順決定部３４５によって決定された第２実行順における待ち時間の合計が、第１実行順決定部３３０によって決定された第１実行順における待ち時間の合計よりも小さい場合に第２実行順を、それ以外の場合は第１実行順を、適用すべき実行順として再決定する。第２実行順を適用すべき実行順として決定した場合、適用実行順決定部３５０は、並び替え部３３５に、第２要求のエントリをキュー・テーブル３１５に追加するよう通知する。
【００８０】
並び替え部３３５は、適用実行順決定部３５０により決定された適用すべき実行順に従って、キュー・テーブル３１５内の全要求の実行順を並び替える。適用実行順決定部３５０から第２要求のエントリを追加するよう通知を受けた場合、並び替え部３３５は、第２待ち時間予測部３４０により作成されたキュー・テーブル３１５のコピーを利用して、キュー・テーブル３１５に第２要求のエントリを追加する。その後、並び替え部３３５は、キュー・テーブル３１５内の全要求の実行順の並び替えを実行する。
【００８１】
中断部３５５は、適用実行順決定部３５０による適用すべき実行順としての第２実行順の決定に応答して、実行中の要求の処理を実際に中断する。なお、上述したように、再開時には残りのデータのみを読み出せばよいように、中断前に読み出されたデータは一時的にメモリに保存してもよい。
【００８２】
このように第２実施形態に係るストレージ・マネージャ３００ｂでは、オーバヘッドを考慮してもホスト装置１０５の平均待ち時間を短縮できる場合には、現在実行中の要求の処理を一旦中断して後に受け付けた要求を先に処理する。その結果、本発明に係る装置では、ホスト装置１０５の平均待ち時間を最小にすることができ、ホスト装置からみた再呼び出し要求の効率が上がる。
【００８３】
（第３実施形態）図９は、本発明の第３実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｃの機能構成の一例を示す図である。第３実施形態に係るストレージ・マネージャ３００ｃは、第１実施形態に係るストレージ・マネージャ３００ａと基本的に同じ機能構成を有する。但し、第３実施形態では、図１に示すライブラリ・システム１１５は、複数のテープ・ドライブ装置１３５を含む。即ち、第３実施形態に係るストレージ・マネージャ３００ｃは、第１実施形態に係るストレージ・マネージャ３００ａを、複数のテープ・ドライブ装置１３５ａ、ｂ、…を含むライブラリ・システム１１５に適用可能なように拡張したものである。
【００８４】
第３実施形態に係るストレージ・マネージャ３００ｃは、テープ・ドライブ装置１３５毎に、キュー・テーブル３１５、第１待ち時間予測部３２５、及び第１実行順決定部３３０をそれぞれ用意する。第３実施形態に係る格納部３１０は、１つの要求を、複数のキュー・テーブル３１５ａ、ｂ、…にそれぞれ仮想的に格納する。テープ・ドライブ装置１３５毎に複数用意される上記各構成要素は、仮想的に格納される要求に対し、第１実施形態に関して説明したのと同様に機能する。
【００８５】
即ち、第３実施形態に係る最小待ち時間決定部３２０ｃでは、同一のキュー・テーブル３１５に対応する第１待ち時間予測部３２５及び第１実行順決定部３３０のペア毎に、対応するキュー・テーブル３１５に入れられた全要求の考え得る全実行順の中から、要求が受け付けられてからその処理が完了するまでの待ち時間の平均が最小となる実行順が求められる。なお、最小となる実行順の求め方は第１実施形態に関して説明したので、繰り返しを避けるためここでは説明を省略する。
【００８６】
第３実施形態に係るストレージ・マネージャ３００ｃはまた、割り当て先決定部３６０を含む。割り当て先決定部３６０は、第１待ち時間予測部３２５及び第１実行順決定部３３０の各ペアによりそれぞれ求められた複数の実行順に基づいて、上記要求を実際に割り当てるテープ・ドライブ装置１３５を決定する。即ち、割り当て先決定部３６０は、複数の第１実行順決定部３３０ａ、ｂ、…がそれぞれ決定した、複数の第１実行順における複数の待ち時間の合計の中で、最小の待ち時間の合計を決定した第１実行順決定部３３０を用意されたテープ・ドライブ装置１３５に、上記１つの要求を割り当てる。
【００８７】
第３実施形態に係る並び替え部３３５は、割り当て先決定部３６０により割り当て先として決定されたテープ・ドライブ装置１３５に対応するキュー・テーブル３１５への上記要求の格納を確定する。そして、並び替え部３３５は、上記要求の格納を確定したキュー・テーブル３１５内の全要求の実行順を、割り当て先として決定された上記テープ・ドライブ装置１３５に対応する第１実行順決定部３３０により決定された第１実行順に従って並び替える。  
【００８８】
（第４実施形態）図１０は、本発明の第４実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｄの機能構成の一例を示す図である。第４実施形態に係るストレージ・マネージャ３００ｄは、第２実施形態に係るストレージ・マネージャ３００ｂと基本的に同じ機能構成を有する。但し、第４実施形態では、図１に示すライブラリ・システム１１５は、複数のテープ・ドライブ装置１３５を含む。即ち、第４実施形態に係るストレージ・マネージャ３００ｄは、第２実施形態に係るストレージ・マネージャ３００ｂを、複数のテープ・ドライブ装置１３５ａ、ｂ、…を含むライブラリ・システム１１５に適用可能なように拡張したものである。  
【００８９】
第４実施形態に係るストレージ・マネージャ３００ｄは、テープ・ドライブ装置１３５毎に、キュー・テーブル３１５、第１待ち時間予測部３２５、第１実行順決定部３３０、第２待ち時間予測部３４０、第２実行順決定部３４５、適用実行順決定部３５０及び中断部３５５をそれぞれ用意する。第４実施形態に係る格納部３１０は、１つの要求を、複数のキュー・テーブル３１５ａ、ｂ、…にそれぞれ仮想的に格納する。テープ・ドライブ装置１３５毎に複数用意される上記各構成要素は、仮想的に格納される要求に対し、第１実施形態及び第２実施形態に関して説明したのと同様に機能する。
【００９０】
即ち、第４実施形態に係る最小待ち時間決定部３２０ｄでは、キュー・テーブル３１５ごとに、対応する適用実行順決定部３５０が、対応する第１実行順決定部３３０及び第２実行順決定部３４５によりそれぞれ決定された第１実行順と第２実行順とを比較して、適用すべき実行順を決定する。なお、最小となる実行順の求め方は第２実施形態に関して説明したので、繰り返しを避けるためここでは説明を省略する。
【００９１】
第４実施形態に係るストレージ・マネージャ３００ｃはまた、割り当て先決定部３６０を含む。第４実施形態に係る割り当て先決定部３６０は、複数の適用実行順決定部３５０ａ、ｂ、…によりそれぞれ求められた複数の実行順に基づいて、上記要求を実際に割り当てるテープ・ドライブ装置１３５を最終的に決定する。即ち、第４実施形態に係る割り当て先決定部３６０は、複数の適用実行順決定部３５０ａ、ｂ、…がそれぞれ決定した、複数の適用すべき実行順における複数の待ち時間の合計の中で、最小の待ち時間の合計を決定した適用実行順決定部３５０に対応するテープ・ドライブ装置１３５に、上記１つの要求を割り当てる。  
【００９２】
第４実施形態に係る並び替え部３３５は、上記割り当て先決定部３６０により要求を割り当てられたテープ・ドライブ装置１３５に対応するキュー・テーブル３１５への上記要求の格納を確定する。そして、並び替え部３３５は、上記要求の格納を確定したキュー・テーブル３１５内の全要求の実行順を、要求を割り当てられた上記テープ・ドライブ装置１３５に対応する適用実行順決定部３５０により決定された適用すべき実行順に従って並び替える。
【００９３】
次に、図１１のフローチャートを参照して、第１実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ａの動作を説明する。図１１において処理はステップ１００から開始し、ストレージ・マネージャ３００ａは、ホスト装置１０５からＮ番目の要求を受け付け、該要求をキュー・テーブル３１５に格納する（ステップ１０５）。このとき実行中の要求のコマンドＩＤをコマンド＃０とし、キュー・テーブル３１５には、要求（コマンド＃１）〜要求（コマンド＃（Ｎ−１））までの、Ｎ−１個の要求が格納されているものとする。
【００９４】
要求（コマンド＃Ｎ）をキュー・テーブル３１５に格納すると、ストレージ・マネージャ３００ａは、キュー・テーブル３１５内に格納された全要求の考え得る全実行順、即ち、Ｎ！通りの並び順のそれぞれについて、該実行順で処理した場合の各要求の待ち時間Ｔｉ（ｉ＝０〜Ｎ）を算出する（ステップ１１０）。ここで、各要求の待ち時間とは、各要求のストレージ・マネージャ３００ａにおける受け付けからテープ・ドライブ装置１３５における処理の完了までの待ち時間を意味する。
【００９５】
Ｎ！通りの並び順のそれぞれについて各要求の待ち時間を算出すると、ストレージ・マネージャ３００ａは、各要求の待ち時間がいずれも最大許容待ち時間を超えない、そのような並び順をすべて決定する。そして、ストレージ・マネージャ３００ａは、決定した並び順の中から、実行中の要求（コマンド＃０）を含む全要求について待ち時間を足し合わせ、その合計が最小となる実行順を第１実行順として決定する（ステップ１１５）。なお、全要求の待ち時間がいずれも最大許容待ち時間内である並び順がなかった場合、処理はそこで終了する。
【００９６】
最後にストレージ・マネージャ３００ａは、第１実行順を適用すべき実行順とし、第１実行順に従ってキュー・テーブル３１５内の要求を並び替える（ステップ１２０）。そして処理は終了する。
【００９７】
なお、第３実施形態に係るストレージ・マネージャ３００ｃの動作も、基本的な部分は、図１１に示すフローチャートと同じである。しかしながら、第３実施形態に係るストレージ・マネージャ３００ｃの場合、ステップ１０５において、要求は確定的ではなく、仮想的に複数のキュー・テーブル３１５ａ、ｂ、…に格納される。そして、ストレージ・マネージャ３００ｃは、各キュー・テーブル３１５に対し、ステップ１１０及びステップ１１５を実行する。
【００９８】
その後第３実施形態に係るストレージ・マネージャ３００ｃは、ステップ１２０へ進む前に、各キュー・テーブル３１５に対してそれぞれ決定した複数の第１実行順の中から、待ち時間の合計が最小となる第１実行順を適用すべき実行順として決定する。そして、ストレージ・マネージャ３００ｃは、適用すべき実行順としての第１実行順を決定されたキュー・テーブル３１５に対応するテープ・ドライブ装置１３５に、上記要求を割り当てる。即ち、適用すべき実行順としての第１実行順を決定されたキュー・テーブル３１５についてのみ、上記要求の格納を確定する。その後処理はステップ１２０へ進み、ストレージ・マネージャ３００ｃは、適用すべき実行順に従って、上記要求を割り当てられたテープ・ドライブ装置１３５に対応するキュー・テーブル３１５内の要求を並び替える。
【００９９】
次に、図１２のフローチャートを参照して、第２実施形態に係るデータの再呼び出し順を決定するための装置としてのストレージ・マネージャ３００ｂの動作を説明する。図１２において処理はステップ２００から開始し、ストレージ・マネージャ３００ｂは、ホスト装置１０５からＮ番目の要求を受け付け、該要求をキュー・テーブル３１５に格納する（ステップ２０５）。このとき実行中の要求のコマンドＩＤをコマンド＃０とし、キュー・テーブル３１５には、要求（コマンド＃１）〜要求（コマンド＃（Ｎ−１））までの、Ｎ−１個の要求が格納されているものとする。
【０１００】
要求（コマンド＃Ｎ）をキュー・テーブル３１５に格納すると、ストレージ・マネージャ３００ｂは、ステップ２１０からステップ２１５までの第１の処理と、ステップ２２０からステップ２３５までの第２の処理を並列に、または順に実行する。なお、ステップ２１０及びステップ２１５の処理については、図１１のステップ１１０及び１１５を参照して説明した処理と同じであるから、詳細な説明は省略する。第２実施形態に係るストレージ・マネージャ３００ｂは、ステップ２１５の処理の後、第１実行順Ｏ１と該実行順Ｏ１に対応する最小の待ち時間の合計値Ｓ１とを取得する。但し、ステップ２１５において、全要求の待ち時間がいずれも最大許容待ち時間内である並び順がなかった場合、処理はステップ２４５へ進む。
【０１０１】
ストレージ・マネージャ３００ｂはまた、実行中の要求（コマンド＃０）の中断を仮定して、テープ・ドライブ装置１３５の読み取りヘッドの現在位置を取得する（ステップ２２０）。そして、ストレージ・マネージャ３００ｂは、実行中の要求（コマンド＃０）を、現在までの処理を行う第１要求（コマンド＃０−１）と残りの処理を行う第２要求（コマンド＃０−２）に仮想的に分割し、上記ヘッドの現在位置を利用して、要求２を含むキュー・テーブル３１５のコピーを新たに作成する（ステップ２２５）。
【０１０２】
そしてストレージ・マネージャ３００ｂは、要求２を含むＮ＋１個の要求が格納されたキュー・テーブル３１５のコピーを基に、（Ｎ＋１）！通りの並び順のそれぞれについて、該実行順で処理した場合の各要求の待ち時間Ｔｉ（ｉ＝０−１、０−２、１〜Ｎ）を算出する（ステップ２３０）。なお、ここでも各要求の待ち時間とは、各要求のストレージ・マネージャ３００ｂにおける受け付けからテープ・ドライブ装置１３５における処理の完了までの待ち時間を意味する。
【０１０３】
（Ｎ＋１）！通りの並び順のそれぞれについて各要求の待ち時間を算出すると、ストレージ・マネージャ３００ｂは、各要求の待ち時間がいずれも最大許容待ち時間を超えない、そのよな並び順をすべて決定する。そして、ストレージ・マネージャ３００ｂは、決定した並び順の中から、要求１及び要求２を含む全要求について待ち時間を足し合わせ、その合計が最小となる実行順を第２実行順Ｏ２として、また第２実行順Ｏ２に対応する最小の待ち時間の合計値Ｓ２を決定する（ステップ２３５）。但し、全要求の待ち時間がいずれも最大許容待ち時間内である並び順がなかった場合、処理はステップ２５５へ進む。
【０１０４】
その後ストレージ・マネージャ３００ｂは、第１実行順Ｏ１に対応する最小の待ち時間の合計値Ｓ１と、第２実行順Ｏ２に対応する最小の待ち時間の合計値Ｓ２とを比較する（ステップ２４０）。合計値Ｓ２がＳ１以下の場合（ステップ２４０：ＮＯ）、ストレージ・マネージャ３００ｂは、実行中の要求（コマンド＃０）の中断をライブラリ・システム１１５に指示する（ステップ２４５）。そして、ストレージ・マネージャ３００ｂは、キュー・テーブル３１５のコピーを用いて元のキュー・テーブル３１５を更新し、更新後の要求２を含むキュー・テーブル３１５内の要求を、第２実行順Ｏ２に従って並び替える（ステップ２５０）。そして処理は終了する。
【０１０５】
一方、合計値Ｓ２がＳ１より大きい場合（ステップ２４０：ＹＥＳ）、ストレージ・マネージャ３００ｂは、キュー・テーブル３１５内の要求を、第１実行順Ｏ１に従って並び替える（ステップ２５５）。そして処理は終了する。
【０１０６】
なお、第４実施形態に係るストレージ・マネージャ３００ｄの動作も、基本的な部分は、図１２に示すフローチャートとステップ２４０まで同じである。しかしながら、第４実施形態に係るストレージ・マネージャ３００ｄの場合、ステップ２０５において、要求は確定的ではなく、仮想的に複数のキュー・テーブル３１５ａ、ｂ、…に格納される。そして、ストレージ・マネージャ３００ｄは、各キュー・テーブル３１５に対し、ステップ２１０からステップ２４０までの処理を実行し、適用すべき実行順を決定する。即ち、ステップ２４０においてＹＥＳであれば、第１実行順Ｏ１を採用することになり、ステップ２４０においてＮＯであれば、第２実行順Ｏ２を採用することになる。
【０１０７】
その後第４実施形態に係るストレージ・マネージャ３００ｄは、各キュー・テーブル３１５に対してそれぞれ決定した複数の実行順の中から、待ち時間の合計が最小となる実行順を適用すべき実行順として決定する。そして、ストレージ・マネージャ３００ｄは、適用すべき実行順を決定されたキュー・テーブル３１５に対応するテープ・ドライブ装置１３５に、上記要求を割り当てる。即ち、適用すべき実行順を決定されたキュー・テーブル３１５についてのみ、上記要求の格納を確定する。最後にストレージ・マネージャ３００ｄは、適用すべき実行順に従って、上記要求を割り当てられたテープ・ドライブ装置１３５に対応するキュー・テーブル３１５内の要求を並び替える。
【０１０８】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。例えば本発明の第１実施形態を、複数のテープ・ドライブ装置１３５ａ、ｂ、…を含むライブラリ・システム１１５に適用可能なように拡張するにあたり、本発明の第３実施形態では、テープ・ドライブ装置１３５毎に用意された複数のキュー・テーブルそれぞれに対し、新たに受け付けた要求の割り当てを仮定して、平均待ち時間を算出した。しかしながら、計算時間をより短縮するために次のような方法を採用することもできる。
【０１０９】
即ち、新たに受け付けた要求が、テープ・ドライブ装置１３５のいずれかにマウントされたテープ・カートリッジ１４５に対するものである場合、該テープ・カートリッジ１４５をマウントされたテープ・ドライブ装置１３５に要求を割り当てる。新たに受け付けた要求が、テープ・ドライブ装置１３５にマウントされたテープ・カートリッジ１４５のいずれに対するものでもない場合、同じテープ・カートリッジ１４５に対する要求を集めてグループ化する。そして、メンバー数が多いグループから順に、そのキュー・テーブル３１５に格納される要求が少ないテープ・ドライブ装置１３５に振り分ける。そして、要求の割り当てが決定した後に、要求を割り当てられたテープ・ドライブ装置１３５のキュー・テーブル３１５に対して、第１実施形態に係るストレージ・マネージャ３００ｃによる要求の再配置を実行する。
【０１１０】
同様の手法により、第２実施形態を、複数のテープ・ドライブ装置１３５ａ、ｂ、…を含むライブラリ・システム１１５に適用可能なように拡張することができる。このように上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図１】
2010035617.tif 000003
【図２】
2010035617.tif 000004
【図３】
2010035617.tif 000005
【図４】
2010035617.tif 000006
【図５】
2010035617.tif 000007
【図６】
2010035617.tif 000008
【図７】
2010035617.tif 000009
【図８】
2010035617.tif 000010
【図９】
2010035617.tif 000011
【図１０】
2010035617.tif 000012
【図１１】
2010035617.tif 000013
【図１２】
2010035617.tif 000014
【国際調査報告】
2010035617.tif 000015
2010035617.tif 000016
2010035617.tif 000017
2010035617.tif 000018