(57)【要約】【課題】ホストから到来するコマンドを効率的に処理する。【解決手段】ホストから到来するコマンドを格納し、次に実行されたとした場合にアクセス開始位置にヘッドが到達するまでの到達時間が最も短いコマンドを選択し、優先的に実行すべきコマンドである優先コマンドを検出し、実行中のコマンドおよび優先コマンドを除く前記格納された各コマンドについて実行中のコマンドの終了角度に対して小さい終了角度をもつコマンドの順に探索を行って、優先コマンドを次に実行するとした場合における前記優先コマンドのアクセス開始位置への前記ディスクヘッドの到着時刻に、前記優先コマンドの前に実行しても前記ディスクヘッドの移動が間に合う第１のコマンドを見つけ、見つかった第１のコマンドのうち最も周回待ち数が少なくかつ前記実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを次に実行するコマンドとする。【選択図】図１
2008071404.tif 000002
【特許請求の範囲】
【請求項１】
実行要求された読み出しまたは書き込みのコマンドにしたがって、ディスク状記憶媒体上を移動可能なディスクヘッドにより前記ディスク状記憶媒体に対しデータの読み書きを行うディスク装置に実行させる前記コマンドの実行順序を管理するコマンド管理装置であって、
ホストからデータの読み出しまたは書き込みを指示するコマンドを受け取るコマンド受取部と、
受け取られた前記コマンドを格納するコマンド格納部と、
前記コマンドによりアクセスされるディスク状記憶媒体上の領域のアクセス終了位置が、前記ディスク上記憶媒体上の基準となる半径線に対して周方向に有する角度である終了角度を計算する終了角度計算部と、
前記ディスク装置により実行中のコマンドの次に実行されたとした場合に、アクセス開始位置に前記ディスクヘッドが到達するまでの到達時間が最も短いコマンドを前記コマンド格納部から選択するコマンド選択部と、
前記コマンド選択部により選択されたコマンドを、次に実行されるべきコマンドとして保持するコマンド保持部と、
前記ディスク装置からコマンドの実行結果を表すデータを受け取るデータ受信部と、
前記コマンド保持部に保持されるコマンドの実行を前記ディスク装置に要求するコマンド実行要求部と、
実行終了したコマンドを前記コマンド格納部から削除するコマンド削除部と、
前記実行中のコマンドの次に、あるコマンドを前記ディスク装置に実行させるとした場合に、前記あるコマンドによりアクセスされる領域のアクセス開始位置へ前記ディスクヘッドをシークさせる間に前記アクセス開始位置が前記ディスクヘッドの移動経路上を通りすぎる回数を表す周回待ち数を計算する周回待ち数計算部と、
優先的に実行すべきコマンドである優先コマンドを検出する優先コマンド検出部と、
前記実行中のコマンドおよび優先コマンドを除く前記コマンド格納部内の各コマンドについて前記実行中のコマンドの終了角度に対して小さい終了角度をもつコマンドの順に探索を行って、前記優先コマンドを次に実行するとした場合における前記優先コマンドのアクセス開始位置への前記ディスクヘッドの到着時刻に、前記優先コマンドの前に実行しても前記ディスクヘッドの該アクセス開始位置への移動が間に合う第１のコマンドを見つける探索部と、
前記第１のコマンドが見つかった場合、見つかった第１のコマンドのうち最も周回待ち数が少なくかつ前記実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを前記コマンド保持部に保持し、前記第１のコマンドが見つからなかった場合、前記選択されたコマンドに代えて前記優先コマンドを前記コマンド保持部に保持する、コマンド変更部と、
を備えたコマンド管理装置。
【請求項２】
前記探索部は、前記探索を行う前に、前記優先コマンドを次に前記ディスク装置に実行させたとした場合に前記ディスクヘッドが前記実行中のコマンドのアクセス終了位置から前記優先コマンドのアクセス開始位置に到達するまでに要する第１の到達時間または前記ディスク状記憶媒体の第１の回転角度量が、前記選択されたコマンドを次に前記ディスク装置に実行させるとした場合に前記ディスクヘッドが前記実行中のコマンドのアクセス終了位置から前記選択されたコマンドのアクセス開始位置に到達するまでに要する第２の到達時間または前記ディスク状記憶媒体の第２の回転角度量以下であるかどうかを判定し、
前記コマンド変更部は、前記第１の到達時間または前記第１の回転角度量が前記第２の到達時間または前記第２の回転角度量以下である場合は、前記優先コマンドを前記コマンド保持部に保持することを特徴とする請求項１に記載のコマンド管理装置。
【請求項３】
前記コマンド格納部内の各コマンドがそれぞれ前記コマンド格納部に格納されてから前記ディスク状記憶媒体が何回転したかを表す総周回待ち数を計算する総周回待ち数計算部と、
前記優先コマンド検出部は、総周回待ち数が閾値以上のコマンドを前記優先コマンドとして検出することを特徴とする請求項２に記載のコマンド管理装置。
【請求項４】
前記探索部は、前記実行中のコマンドのアクセス終了位置から前記優先コマンドによるアクセス開始位置に前記ディスクヘッドが到達するまでに要する第１の到達時間または前記ディスク状記憶媒体の第１の回転角度量と、前記実行中のコマンドのアクセス終了位置から前記コマンド格納部内の前記コマンドによるアクセス領域を通過し前記優先コマンドによるアクセス開始位置に前記ディスクヘッドが到達するまでに要する第３の到達時間または第３の回転角度量とを比較し、前記第３の到達時間または前記第３の回転角度量が前記第１の到達時間または第１の回転角度量以下である場合は前記コマンドを前記第１のコマンドとして検出することを特徴とする請求項１に記載のコマンド管理装置。
【請求項５】
前記ディスク状記憶媒体上における前記ディスクヘッドの位置を検出するディスクヘッド位置検出部をさらに備え、
前記コマンド選択部、前記探索部、前記コマンド変更部は、前記実行中のコマンドが存在しない場合は、前記ディスクヘッドの位置をもとに各々の処理を行うことを特徴とする請求項１ないし４のいずれか一項に記載のコマンド管理装置。
【請求項６】
前記受け取られたコマンドによりアクセスされるディスク状記憶媒体上の領域のアクセス開始位置が、前記半径線に対して周方向に有する角度である開始角度を計算する開始角度計算部と、
前記コマンド格納部内の各コマンドを開始角度の昇順で結合した開始角度リンクリストを生成および維持する開始角度リンクリスト維持部と、をさらに備え、
前記コマンド選択部は、前記開始角度リンクリストにおいて前記実行中のコマンドの終了角度に対して最も小さい開始角度をもつコマンドを起点として前記開始角度リンクリストを順に辿り、前記実行中のコマンド以外で周回待ち数が所定のパラメータに最も早く一致したコマンドを選択する請求項１ないし５のいずれか一項に記載のコマンド管理装置。
【請求項７】
前記コマンド選択部は、前記所定のパラメータに一致する周回待ち数のコマンドが存在しない場合は、前記パラメータを増加し、再度前記開始角度リンクリストを辿ることを特徴とする請求項６に記載のコマンド管理装置。
【請求項８】
前記コマンド格納部内の各コマンドを終了角度の昇順で結合した終了角度リンクリストを生成および維持する終了角度リンクリスト維持部をさらに備え、
前記探索部は、前記終了角度リンクリストを前記実行中のコマンドの次のコマンドから辿ることにより前記探索を行うことを特徴とする請求項１に記載のコマンド管理装置。
【請求項９】
前記受け取られたコマンドによりアクセスされるディスク状記憶媒体上の領域のアクセス開始位置が、前記半径線に対して周方向に有する角度である開始角度を計算する開始角度計算部と、
前記実行中のコマンドの次に実行されたとした場合に前記ディスクヘッドがアクセス開始位置に到達するまでの到達時間が最も短いコマンドを根ノードにもち、かつ、前記根ノードのコマンドの開始角度を基準として親ノードのコマンドの開始角度が子ノードのコマンドの開始角度以下であるという条件を満たす２分木を、前記実行中のコマンドおよび前記優先コマンドを除く前記コマンドテーブル内の各コマンドを用いて生成および維持する２分木維持部と、をさらに備え、
前記コマンド選択部は、前記根ノードにあるコマンドを選択することを特徴とする請求項１ないし５のいずれか一項に記載のコマンド管理装置。
【請求項１０】
前記２分木維持部は、前記実行中のコマンドの終了角度を基準として、前記２分木における各コマンドと各コマンドの子孫コマンドとのうちで最も小さい終了角度をもつコマンドが、各コマンドからみて左側の子コマンド方向、右側の子コマンド方向、または自分自身であることを示す最小終了角度情報を設定し、
前記探索部は、前記２分木の根ノードに置かれたコマンドから前記最小終了角度情報を元に前記２分木を辿ることにより前記実行中のコマンドの終了角度に対して最も小さい終了角度をもつコマンドを特定することを特徴とする請求項９に記載のコマンド管理装置。
【請求項１１】
前記２分木維持部は、特定された前記コマンドが前記第１のコマンドでなかった場合、または前記特定されたコマンドが第１のコマンドであるがその周回待ち数が前記選択されたコマンドの周回待ち数と異なる場合、前記特定されたコマンドを前記２分木からいったん除去し、さらに前記２分木を更新し、
前記探索部は、更新された前記２分木の根ノードに置かれたコマンドから前記最小終了角度情報を元に前記２分木を再度辿ることにより前記実行中のコマンドの終了角度に対して最も小さい終了角度をもつコマンドを特定することを特徴とする請求項１０に記載のコマンド管理装置。
【請求項１２】
前記探索部が、前記最も小さい終了角度をもつコマンドとして根ノードに置かれたコマンドを特定し、かつ、特定された前記コマンドが第１のコマンドである場合は、前記探索を終了し、
前記コマンド変更部は、前記探索部によって見つけられた全ての第１のコマンドのうち、最も周回待ち数が少なくかつ前記実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを前記コマンド保持部に保持することを特徴とする請求項１１に記載のコマンド管理装置。
【請求項１３】
実行要求された読み出しまたは書き込みのコマンドにしたがって、ディスク状記憶媒体上を移動可能なディスクヘッドにより前記ディスク状記憶媒体に対しデータの読み書きを行うディスク装置に実行させる前記コマンドの実行順序を管理するコマンド管理方法であって、
ホストからデータの読み出しまたは書き込みを指示するコマンドを受け取り、
受け取られた前記コマンドをコマンド格納部に格納し、
前記コマンドによりアクセスされるディスク状記憶媒体上の領域のアクセス終了位置が、前記ディスク上記憶媒体上の基準となる半径線に対して周方向に有する角度である終了角度を計算し、
前記ディスク装置により実行中のコマンドの次に実行されたとした場合に、アクセス開始位置に前記ディスクヘッドが到達するまでの到達時間が最も短いコマンドを前記コマンド格納部から選択し、
前記コマンド選択部により選択されたコマンドを、次に実行されるべきコマンドとして保持し、
前記ディスク装置からコマンドの実行結果を表すデータを受け取り、
前記保持されるコマンドの実行を前記ディスク装置に要求し、
実行終了したコマンドを前記コマンド格納部から削除し、
優先的に実行すべきコマンドである優先コマンドを検出し、
前記実行中のコマンドおよび前記優先コマンドを除く前記コマンド格納部内の各コマンドについて前記実行中のコマンドの終了角度に対して小さい終了角度をもつコマンドの順に探索を行って、前記優先コマンドを次に実行するとした場合における前記優先コマンドのアクセス開始位置への前記ディスクヘッドの到着時刻に、前記優先コマンドの前に実行しても前記ディスクヘッドの該アクセス開始位置への移動が間に合う第１のコマンドを見つけ、
前記第１のコマンドが見つかった場合、見つかった第１のコマンドのうち最も周回待ち数が少なくかつ前記実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを前記次に実行するコマンドとして保持し、前記第１のコマンドが見つからなかった場合、前記選択されたコマンドに代えて前記優先コマンドを前記次に実行するコマンドとして保持する、
ことを特徴とするコマンド管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディスク装置に実行させる読み出しおよび書き込みコマンドの実行順序を管理するコマンド管理装置およびコマンド管理方法に関する。
【背景技術】
【０００２】
ハードディスクドライブ（HDD：Hard Disk Drive）は、ホストから転送された読み出しまたは書き込みコマンドをコマンドキューに格納し、実行中のコマンドが終了した後に、コマンドキューに格納されたコマンドの中より、次に実行するコマンドを選択する。コマンドの選択は、例えば、実行終了したコマンドのディスク上の終了位置から、最も早くアクセス可能なコマンドを計算することで行う。ただし、実行を迅速に行いたい優先コマンドが発生した場合は、実行中コマンドの次に、優先コマンドを実行する。
【特許文献１】特開２００３−３１６５２３公報
【特許文献２】特開２００４−１３９４８２公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上述した従来のコマンド選択方法では、実行するコマンドを選択する計算を、実行中コマンドが終了し、ディスクが利用可能になってから行うため、計算時間中もディスクが回転し、コマンドに余計な待ち時間が生じる。また、コマンドキューに格納したコマンド数が増えれば増えるほど計算時間が長くなるため、コマンドの待ち時間もそれだけ長くなる。一方において、従来のコマンド選択方法では、コマンドキューにおいて長時間選択されることなく取り残され続けるコマンドが発生し、このコマンドを発行したホストは、コマンドの実行結果を長時間待機させられてしまう。
【０００４】
本発明は、ホストから到来したコマンドを効率的に処理可能なコマンド管理装置およびコマンド管理方法を提供する。
【課題を解決するための手段】
【０００５】
本発明の一態様としてのコマンド管理装置は、実行要求された読み出しまたは書き込みのコマンドにしたがって、ディスク状記憶媒体上を移動可能なディスクヘッドにより前記ディスク状記憶媒体に対しデータの読み書きを行うディスク装置に実行させる前記コマンドの実行順序を管理するコマンド管理装置であって、
ホストからデータの読み出しまたは書き込みを指示するコマンドを受け取るコマンド受取部と、
受け取られた前記コマンドを格納するコマンド格納部と、
前記コマンドによりアクセスされるディスク状記憶媒体上の領域のアクセス終了位置が、前記ディスク上記憶媒体上の基準となる半径線に対して周方向に有する角度である終了角度を計算する終了角度計算部と、
前記ディスク装置により実行中のコマンドの次に実行されたとした場合に、アクセス開始位置に前記ディスクヘッドが到達するまでの到達時間が最も短いコマンドを前記コマンド格納部から選択するコマンド選択部と、
前記コマンド選択部により選択されたコマンドを、次に実行されるべきコマンドとして保持するコマンド保持部と、
前記ディスク装置からコマンドの実行結果を表すデータを受け取るデータ受信部と、
前記コマンド保持部に保持されるコマンドの実行を前記ディスク装置に要求するコマンド実行要求部と、
実行終了したコマンドを前記コマンド格納部から削除するコマンド削除部と、
前記実行中のコマンドの次に、あるコマンドを前記ディスク装置に実行させるとした場合に、前記あるコマンドによりアクセスされる領域のアクセス開始位置へ前記ディスクヘッドをシークさせる間に前記アクセス開始位置が前記ディスクヘッドの移動経路上を通りすぎる回数を表す周回待ち数を計算する周回待ち数計算部と、
優先的に実行すべきコマンドである優先コマンドを検出する優先コマンド検出部と、
前記実行中のコマンドおよび優先コマンドを除く前記コマンド格納部内の各コマンドについて前記実行中のコマンドの終了角度に対して小さい終了角度をもつコマンドの順に探索を行って、前記優先コマンドを次に実行するとした場合における前記優先コマンドのアクセス開始位置への前記ディスクヘッドの到着時刻に、前記優先コマンドの前に実行しても前記ディスクヘッドの該アクセス開始位置への移動が間に合う第１のコマンドを見つける探索部と、
前記第１のコマンドが見つかった場合、見つかった第１のコマンドのうち最も周回待ち数が少なくかつ前記実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを前記コマンド保持部に保持し、前記第１のコマンドが見つからなかった場合、前記選択されたコマンドに代えて前記優先コマンドを前記コマンド保持部に保持する、コマンド変更部と、
を備える。
【０００６】
本発明の一態様としてのコマンド管理方法は、実行要求された読み出しまたは書き込みのコマンドにしたがって、ディスク状記憶媒体上を移動可能なディスクヘッドにより前記ディスク状記憶媒体に対しデータの読み書きを行うディスク装置に実行させる前記コマンドの実行順序を管理するコマンド管理方法であって、
ホストからデータの読み出しまたは書き込みを指示するコマンドを受け取り、
受け取られた前記コマンドをコマンド格納部に格納し、
前記コマンドによりアクセスされるディスク状記憶媒体上の領域のアクセス終了位置が、前記ディスク上記憶媒体上の基準となる半径線に対して周方向に有する角度である終了角度を計算し、
前記ディスク装置により実行中のコマンドの次に実行されたとした場合に、アクセス開始位置に前記ディスクヘッドが到達するまでの到達時間が最も短いコマンドを前記コマンド格納部から選択し、
前記コマンド選択部により選択されたコマンドを、次に実行されるべきコマンドとして保持し、
前記ディスク装置からコマンドの実行結果を表すデータを受け取り、
前記保持されるコマンドの実行を前記ディスク装置に要求し、
実行終了したコマンドを前記コマンド格納部から削除し、
優先的に実行すべきコマンドである優先コマンドを検出し、
前記実行中のコマンドおよび前記優先コマンドを除く前記コマンド格納部内の各コマンドについて前記実行中のコマンドの終了角度に対して小さい終了角度をもつコマンドの順に探索を行って、前記優先コマンドを次に実行するとした場合における前記優先コマンドのアクセス開始位置への前記ディスクヘッドの到着時刻に、前記優先コマンドの前に実行しても前記ディスクヘッドの該アクセス開始位置への移動が間に合う第１のコマンドを見つけ、
前記第１のコマンドが見つかった場合、見つかった第１のコマンドのうち最も周回待ち数が少なくかつ前記実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを前記次に実行するコマンドとして保持し、前記第１のコマンドが見つからなかった場合、前記選択されたコマンドに代えて前記優先コマンドを前記次に実行するコマンドとして保持する、
ことを特徴とする。
【発明の効果】
【０００７】
本発明により、ホストから到来したコマンドを効率的に処理できる。
【発明を実施するための最良の形態】
【０００８】
（第１の実施の形態）
図１は、本発明の一実施の形態にしたがったコマンド管理装置を搭載したデータ記憶装置の構成を示すブロック図である。
【０００９】
ホスト1はハードディスクドライブ（HDD：Hard Disk Drive）2に対しデータの読み出しまたは書き込み（読み出し／書き込み）を要求する読み出し／書き込みコマンドを発行する。コマンドは、読み出し命令であるか書き込み命令かを示すコマンド種類と、磁気ディスク等のディスクにおけるアクセス位置（LBA：Logical Block Addressing（ロジカルブロックアドレッシング））と、読み出し／書き込みを行うデータサイズとを含んでいる。LBAはディスク上の論理アドレスを表す。
【００１０】
HDD２は、ホストから受け取ったコマンドを実行し、実行結果（例えば読み出しの場合は読み出したデータ、書き込みの場合は書き込みを完了した旨の通知）をホスト１に返す。HDD２はホストから受け取ったコマンドの実行順序を管理する制御部（コマンド管理装置）３と、コマンドを実行するディスク装置４とを備える。制御部３におけるテーブル管理部６は、コマンドテーブル（コマンド格納部）５を用いて、ホスト１から発行されたコマンドの管理（追加・削除・更新）を行う。テーブル管理部６は、コマンドテーブル５から次に実行するべきコマンドを、本実施の形態の特徴となる方法を用いて選択し、選択したコマンドの実行をコマンド実行要求部８がディスク装置４に対して要求する。テーブル管理部６は、コマンドテーブル５内の各コマンドをディスク装置4によるコマンド実行が終了するまで（読み出し／書き込みが完了するまで）コマンドテーブル5に保持し、実行が終了するとコマンドテーブル５から削除する。すなわちテーブル管理部６は、コマンド実行が終了したコマンドをコマンドテーブル５から削除するコマンド削除部を備える。
【００１１】
以下図１のデータ記憶装置についてさらに詳しく説明する。
【００１２】
図２はコマンドテーブル５の一例を示す。
【００１３】
ホスト１による１つのコマンドの発行に対応して、コマンド情報（アドレス、開始角度、終了角度、サイズ、種類）と、開始角度ポインタと、終了角度ポインタとがコマンドテーブル５に格納される。
【００１４】
コマンド情報における種類は、発行されたコマンドが読み出しコマンドであるか書き込みコマンドであるかを表す。開始角度は、図３に示すように、ディスク１３上に基準線（基準となる半径線）１６を設け、その基準線１６とコマンドの先頭（アクセス開始位置）とが周方向において成す角度１７である。終了角度は、基準線１６とコマンドの末尾（アクセス終了位置）とが周方向において成す角度１８である。開始角度ポインタは、基準線１６に対し、自コマンドの次に大きい開始角度を持つコマンドを指す。終了角度ポインタは、基準線１６に対し、自コマンドの次に大きい終了角度を持つコマンドを指す。コマンドの開始角度および終了角度は、該コマンドのディスク上におけるアクセス開始位置と、アクセスすべきデータのサイズとをもとに角度計算部（開始角度計算部および終了角度計算部）７によって算出される。角度計算部７は、ホストから受け取ったコマンドのアドレス（例えばLBA）とデータサイズとからアクセスを開始および終了するCHS(Cylinder/Head/Sector)をそれぞれ求め、各CHSに対応するディスク上の基準線１６に対する角度をそれぞれ開始角度（セクタの先頭の基準線１６に対する角度）および終了角度（セクタの末尾の基準線１６に対する角度）として求める。CHS(Cylinder/Head/Sector)は、ディスク上の物理アドレスで、何シリンダの何ヘッドの何セクタ目かを表す。このように、テーブル管理部６は、角度計算部７を利用して、コマンドテーブル５内の各コマンドを開始角度順および終了角度順に管理する。
【００１５】
ディスク装置4は、コマンド実行要求部８から実行要求されたコマンドに指定されるアドレスから、指定されたサイズ分のデータの読み出し／書き込みを行う。ディスク装置４の構造の一例を図４に平面図として、図５に斜示図としてそれぞれ簡略的に示す。図５に示すようにディスク装置４は複数枚のディスク１３と、複数のディスクヘッド１２と、ディスクヘッド移動機構１９とを備えている。図４において矢印Ｙ１はディスク１３の回転方向を示す。データは磁気情報として、ディスク１３の同心円上に配置されるトラック１１に格納される。データの読み出し／書き込みはディスクヘッド１２によって行う。ディスクヘッド１２を、読み出し／書き込み対象となるデータ１４が存在するトラック１１上へ動かし、ディスクヘッド１２の位置においてディスク１３上のデータ１４が回転してくるのを待つことで、データ１４へのアクセスが行われる。ＳＴはデータ１４へのアクセス開始位置（コマンドの読み出し開始位置または書き込み開始位置）、ＥＤはアクセス終了位置（コマンドの読み出し終了位置または書き込み終了位置）を示す。ディスクヘッド１２を目標のトラック１１上に移動させる動作を「シーク」と呼ぶ。シーク終了後、ディスクヘッドの位置にディスク１３上のデータが到来するのを待つことを「回転待ち」と呼ぶ。データへのアクセス時間は、「シーク時間+回転待ち時間」で表すことができる。
【００１６】
テーブル管理部６は、基本的に、基準位置（実行中のコマンドの終了時のディスクヘッドの位置（コマンドの終了位置）、実行中のコマンドが存在しない場合はディスクヘッドの位置にリオーダリングの計算中におけるディスクの回転量を加算した位置。詳細は後述する）から、読み出し／書き込みを開始するまでに最も時間がかからないコマンド（アクセス開始位置にディスクヘッドが到達するまでの到達時間が最も短いコマンド）を、次に実行すべきコマンドとして決定する（STFアルゴリズムに基づくリオーダリング）。すなわちテーブル管理部６はSTFアルゴリズムに基づいたリオーダリングによりコマンドを選択するコマンド選択部を備える。ディスクヘッド位置は、ディスク上におけるディスクヘッド１２の位置を検出するディスクヘッド位置検出部9を用いて取得する。ディスクヘッド位置検出部９による位置検出機構について説明すると以下の通りである。
【００１７】
ディスク上には、サーボデータと呼ばれるディスク上の位置情報を保持したデータが存在する。サーボデータに対し、ユーザが読み書きするデータをユーザデータと呼ぶ。ディスクヘッドからサーボデータを読み出すことで、ディスクヘッドの現在位置を把握できる。サーボデータの配置方法として、ユーザデータとサーボデータが同一ディスク面上に混在するデータ面サーボ方式、およびサーボデータのためのディスク面を用意し、ユーザデータとサーボデータを区別するセクタ・サーボ方式がよく知られている。図７５（Ａ）および図７５（Ｂ）はデータ面サーボ方式を説明する図である。図７５（Ａ）のようにサーボデータはディスクの中心から外周に向かって配置され、図７５（Ｂ）のようにトラック上でディスクヘッドにより読み取ることができる。図７６はセクタ・サーボ方式を説明する図である。図示のようにこの方式ではサーボデータのみを保持するディスク面が存在する。
【００１８】
ここで、リオーダリングおよびSTFアルゴリズムについて説明する。
【００１９】
リオーダリングは、一般にホストから発行されるコマンドをコマンドキューに格納し、効率的なデータアクセスを可能とするように、実行するコマンドの順番をコマンドキュー内で入れ替える手法を指す。たとえば、図６（Ａ）のように、コマンド１、コマンド２、コマンド３の順でコマンドが発行されたとする。この場合、発行された順番でコマンドを実行（ディスクアクセス）するよりも、リオーダリングにより、図６（Ｂ）のように、コマンド１→コマンド３→コマンド２の順でコマンドを実行することで、データの読み出し／書き込みを効率よく行うことができる。
【００２０】
STFアルゴリズムは、リオーダリングアルゴリズムの１つであり、最もアクセス時間が短いコマンドを次々に選ぶアルゴリズムである。たとえば、図７のように、現在、コマンド1（コマンド１が読み出し／書き込みの対象とするディスク上のデータ１が示されている）を実行中であるとする。STFアルゴリズムでは、次に実行するコマンドとして、コマンド3を選択する。一見、コマンド2の方が早くアクセスできそうであるが、シーク中にコマンド２が通り過ぎてしまい、ディスク一周分の余計な回転待ち（シーク終了後、読み出し／書き込みを行うデータが到来するのを待つこと）が生じてしまう。シークの際に、読み出し／書き込みを行うディスク領域（セクタ）がディスクヘッドの移動経路上を通りすぎてしまうことは「周回待ち」と称される。トラック間が離れている場合2以上の周回待ちも起こり得、発生した周回待ちの回数は「周回待ち数」と称される。テーブル管理部６は、コマンドの周回待ち数を計算する周回待ち数計算部を備えていてもよい。コマンド３の実行終了後、コマンド４はシークが待ち合うため、コマンド3の次に実行するコマンドは、一番早くアクセスできるコマンド4となる。
【００２１】
最も早く次にアクセスできるコマンドはたとえば以下のようにして算出できる。図７において、コマンド1の実行終了後、コマンド2の実行開始までに要する時間（データ１のアクセス終了からデータ２のアクセス開始までに要する時間）は、最短で、コマンド2の先頭角度とコマンド1の先頭角度との差にディスク１３の回転角速度を乗じた値となる。ディスク１３の回転角速度は一定であるため、アクセスに要する時間はコマンドの角度差に比例する。ただし、コマンド1からコマンド2へのシークが間に合わない場合は、周回待ちが発生するため、発生した周回待ちの回数分（トラック間が離れている場合2以上の周回待ちが起こりうる）、時間を余計に要することになる。コマンドキュー内の各コマンドについてアクセスに要する時間をそれぞれ計算することで、最も早く次にアクセスできるコマンドを算出できる。ここではアクセスに要する時間に着目して次に最も早くアクセスできるコマンドを算出したが、コマンドの実行開始までに要するディスクの回転量に着目してもよい。この場合、回転量が最も小さいコマンドを次に最も早くアクセスできるコマンドとして検出する。
【００２２】
テーブル管理部６は、基本的に上述したSFTアルゴリズムに基づくリオーダリングを行うが、可能な限り早く実行を終了したい優先コマンドが発生することがある。ホスト１からコマンドが優先コマンドとして発行される場合、またはHDD２内部で早く実行すべきことを判断されたコマンドが優先コマンドとなる場合などがある。すなわちテーブル管理部６は優先コマンドを検出する優先コマンド検出部を備える。後者の例としては、データの整合性を保つために先に実行すべきコマンドが存在する場合、または取り残しコマンドが検出された場合がある。取り残しコマンドとは一向に実行されずＨＤＤ２内に取り残されたコマンドのことである。上述のSTFアルゴリズムでは、コマンドの実行終了後、最も早く次にアクセスできるコマンドを次々に選択する。つまりSTFアルゴリズムではコマンドの発行された順番は考慮されない。そのため、新しく発行されたコマンドばかり選択されて以前に発行されたコマンドの実行が先送りされる現象が起こり得る。そこで取り残しコマンドが検出された場合、取り残しコマンドを早期に実行すべく、取り残しコマンドが優先コマンドとして扱われる。
【００２３】
以下優先コマンドについてより詳しい説明を行う。
【００２４】
優先コマンドとは、上述したように可能な限り早く実行を終了したいコマンドであり、以下のような場合が考えられる。
（１）パラレルATAにおける読み出しコマンド
パラレルATAにおいては、規格上複数のコマンドを同時に発行することはできない。読み出しコマンドは、そのコマンドの実行が完了し要求データをホストに返してからでないと、HDDはホストに対し終了通知を発行することができない。ホストは終了通知を受け取った時点でコマンドが終了したと判断するため、パラレルATAでは、読み出しコマンドの実行が終了するまで、新しいコマンドを発行することはできない。そのため、読み出しコマンドは迅速に実行すべきである。そこでコマンドの受理時に、そのコマンドの種類を検出し、コマンドの種類が読み出しコマンドであれば、該コマンドを優先コマンドとして扱ってもよい。
（２）データ整合性を保つため
ディスク上の同一アドレスに、読み出しコマンドと書き込みコマンドが発行された場合、リオーダリングにより、発行順と異なる順序にこれらのコマンドを入れ替えてしまうと、ホストが要求しているデータとは違うデータをHDDは送付してしまうことになる。データの整合性を保つため、同一LBA(Logical Block Addressing)への要求が発生した場合、後に発行されたコマンドを実行する前に、先に発行されたコマンドを実行する必要がある。そのため、先に発行されたコマンドの実行が終了するまで、後に発行されたコマンドをコマンドテーブルに格納するのを待機させる。この場合、先に発行されたコマンドの実行が完了するまで、後に発行されたコマンドはコマンドテーブルに格納されずに待ち続けることとなる。そのため、先に発行されたコマンドを優先コマンドとし、迅速に実行することが好ましい。よって、ＨＤＤの制御部３に到達する各コマンドについては、整合性を保つため、LBAの重なりを調べ、LBAが重複したコマンドを見つけたら、先に発行されたコマンドを優先コマンドとして扱ってもよい。
（３）取り残しコマンド削減のため
取り残しコマンドとは、上述したように、リオーダリングで選択されずにHDD内で実行されずに取り残されたコマンドである。取り残されたコマンドが読み出しコマンドあった場合、ホストが必要としているデータの転送が大幅に遅れる問題が生じ、取り残されたコマンドが書き込みコマンドであった場合、書き込みたいデータが揮発性のキャッシュに長時間保存されることとなり、データの信頼性に問題が生じる。これらの問題を解決するため、書き込みたいデータがキャッシュに格納されてから一定時間以上経過したコマンドを優先コマンドとして迅速な実行を促す。取り残しコマンドの検出方法は、本実施形態では、コマンドがコマンドテーブルに格納されてから、ディスクが総計で何回転したかを示す「総周回待ち数」に着目している。
【００２５】
優先コマンドが発生した場合、原則として、優先コマンドが優先的に実行される。たとえばあるコマンドの実行中に優先コマンドが発生した場合は、該あるコマンドの実行終了後、STFアルゴリズムで決定したコマンド（コマンド選択部により選択されたコマンド）ではなく、優先コマンドを原則として次に実行する。ただし、本実施の形態では、テーブル管理部６が、優先コマンドの実行前に実行しても優先コマンドの実行開始が遅れないコマンド（第１のコマンド）を効率的に探索し、探索されたコマンドを先に実行することで、効率的なコマンド処理を実現している。
【００２６】
このような効率的なコマンド処理を実現するため、テーブル管理部６は、
実行中のコマンドおよび優先コマンドを除くコマンドテーブル内の各コマンドについて実行中のコマンドの終了角度に対して小さい終了角度をもつコマンドの順に探索を行って、STFアルゴリズムで選択されたコマンドに代えて優先コマンドを次に実行するとした場合における前記優先コマンドのアクセス開始位置への前記ディスクヘッドの到着時刻に、前記優先コマンドの前に実行しても前記ディスクヘッドの該アクセス開始位置への移動が間に合う第１のコマンドを見つける探索部と、
第１のコマンドが見つかった場合、見つかった第１のコマンドのうち最も周回待ち数が少なくかつ実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドをコマンド保持部に保持し、
第１のコマンドが見つからなかった場合、選択されたコマンドに代えて優先コマンドをコマンド保持部に保持する、コマンド変更部と、を上述した各要素（たとえば角度計算部、コマンド選択部、コマンド削除部、優先コマンド検出部、周回待ち数計算部など）に加え、さらに備えている。
【００２７】
上記探索部は、実行中のコマンドのアクセス終了位置から優先コマンドによるアクセス開始位置にディスクヘッドが到達するまでに要する第１の到達時間または前記ディスク状記憶媒体の第１の回転角度量と、実行中のコマンドのアクセス終了位置からコマンド格納部内のコマンドによるアクセス領域を通過し優先コマンドによるアクセス開始位置にディスクヘッドが到達するまでに要する第３の到達時間または第３の回転角度量とを比較し、第３の到達時間または第３の回転角度量が第１の到達時間または第１の回転角度量以下である場合は上記コマンドを第１のコマンドとして検出してもよい。
【００２８】
以下、テーブル管理部６による処理の具体例として、「リンクリストを用いたコマンド管理」「２分木を用いたコマンド管理」の２つを説明する。後者については第２の実施の形態において説明する。
【００２９】
以下「リンクリストを用いたコマンド管理」について説明する。
【００３０】
説明に先立ち、使用する用語について説明しておく。
「開始角度リンクリスト」：コマンドを開始角度の昇順で並べて１つのリスト構造にしたものである。一番開始角度の大きいコマンドから、一番開始角度の小さいコマンドへは循環状に結合される。すなわち開始角度リンクリストは環状をなす。図２に示したコマンドテーブルは、開始角度ポインタによって各コマンドを開始角度の昇順で結合した開始角度リンクリストを含んでいる。つまり、コマンドテーブルにおいてコマンド情報と開始角度ポインタとからなるデータ集合が開始角度リンクリストに相当する。すなわちテーブル管理部６は、開始角度リンクリストを生成及び維持する開始角度リンクリスト維持部を備えている。
「終了角度リンクリスト」：コマンドを終了角度の昇順で並べて１つのリスト構造にしたものである。一番終了角度が大きいコマンドから一番終了角度の小さいコマンドへは循環状に結合される。すなわち終了角度リンクリストは環状をなす。図２に示したコマンドテーブルは、終了角度ポインタによって各コマンドを開始角度の昇順で結合した終了角度リンクリストを含んでいる。つまり、コマンドテーブルにおいてコマンド情報と終了角度ポインタとからなるデータ集合が終了角度リンクリストに相当する。すなわちテーブル管理部６は、終了角度リンクリストを生成及び維持する開始角度リンクリスト維持部を備えている。
「基準位置」：コマンド実行中であれば、該コマンドの終了位置を表し、コマンド実行中でなければ現在のディスクヘッド位置に、リオーダリングの計算時間中に回転するディスクの回転量を加算した位置を表す。実行するコマンドを決定する際、基本的にこの基準位置からシークを開始したとき、最も早くアクセスできるコマンドを計算する（リオーダリングの計算）。リオーダリングの計算中にもディスクは回転しているため、リオーダリングの計算開始時における基準線１６に対するディスクヘッドの位置と、シークの開始時（リオーダリングの計算終了時）における基準線１６に対するディスクヘッドの位置とは異なる。したがって実際にはリオーダリングの計算に要する時間を予め見積もっておき、その分余裕をもった位置を基準位置として計算を行う。例えば、コマンドテーブル内のコマンド数を引数にした関数を計算することで、リオーダリングの計算時間（リオーダリングの計算時間中のディスクの回転量）を求めておく。具体的には、
コマンドテーブルに格納されたコマンド数：n
コマンド数nのとき、リオーダリングにかかる計算時間：R(n)
としたとき、どのnにも以下の式が成り立つ関数Fを上記関数として用いればよい。
R(n)+α<F(n)
ただしαはマージン（余裕分）を表す。R(n)はコマンドテーブルの種類（本実施の形態におけるリンクリスト、第２の実施の形態で述べる２分木）により異なる
「基準コマンド」：上記基準位置の角度から、最も遠い開始角度をもつコマンドである。新しいコマンドをコマンドテーブルに格納する際、基準コマンドから開始角度リンクリストを探索することにより、コマンドの格納を迅速に行うことができる。基準コマンドは基準ポインタによって指し示され、基準ポインタはテーブル管理部６において内部的に管理される。
「候補コマンド」：次に実行するコマンドである。候補コマンドは、候補ポインタによって指し示され、候補ポインタはテーブル管理部６において内部的に管理される。すなわちテーブル管理部６は次に実行されるべきコマンドを保持するコマンド保持部を備える。新しいコマンドを実行する際は、無条件にこの候補コマンドの実行要求をコマンド実行要求部８がディスク装置４に行う。候補コマンドを決定する際、テーブル管理部６はリオーダリングを行い、以下の条件を満たすものを候補コマンドとして決定する。
・優先コマンドが存在しない場合はSTFアルゴリズムによって求まるコマンド
・優先コマンドが存在する場合は優先コマンド、または、優先コマンドより先に実行しても優先コマンドの実行開始時刻が変わらないコマンドが存在する場合は該コマンド
「コマンドの実行」：シーク、回転待ち、およびデータの読み出し／書き込みを意味し、これらのいずれかの対象となっているコマンドは「実行コマンド」と称される。実行コマンドは実行ポインタによって指し示され、実行ポインタはテーブル管理部６において内部的に管理される。
「優先コマンド」：先にも説明したように迅速に実行をしたいコマンドである。優先コマンドは優先ポインタによって指し示される。優先ポインタはテーブル管理部６において内部的に管理される。優先コマンドが複数発生した場合は、一番古いコマンドを優先コマンドとみなし、他のコマンドは優先コマンドの候補とみなす。優先コマンドの実行が終了した時点で、優先コマンドの候補の中で一番が古いコマンドが優先コマンドとして扱われる。すなわち、優先コマンドおよび優先コマンド候補は発行順に図８に示すように管理される。優先コマンドおよび優先コマンド候補の実際の管理方法としては、各コマンドをポインタで結ぶ方法、または別途キューを作成する方法などがある。
【００３１】
以下、リンクリストを用いたコマンド管理について図９〜図３２を用いて具体的に説明する。
【００３２】
（１）コマンド（２０、６０）の到来
まずホスト１からコマンド（２０、６０）が到来する。コマンド（２０、６０）は、ホスト１から到来したコマンドを、ＨＤＤ２内部においてコマンド（CA、CB）の形式で表現したものである。CAはコマンドの開始角度、CBはコマンドの終了角度である。コマンド（２０、６０）のディスク上における位置を図９に示す。ホスト１からコマンドが到来すると、図２４のフローチャートに示すコマンド格納処理を行う。このコマンド格納処理では、到来したコマンドを開始角度リンクリストおよび終了角度リンクリストに追加するとともに、基準ポインタおよび候補ポインタの更新を行う。
【００３３】
より詳細に、ホスト１からコマンド（２０、６０）（コマンドAとする）が到来すると、Ｓ１１において、図２５のフローチャートに示す開始角度リンク追加処理を実行する。まずコマンドテーブルのコマンド数をチェックする（Ｓ２１）。コマンド数は現在０であるため、コマンドＡをコマンドテーブルに追加した後（Ｓ２０）、コマンドＡの次に大きい開始角度をもつコマンドを自分自身に設定した開始角度リンクリストを作成する（Ｓ２２）。すなわちコマンドＡの開始角度ポインタを自分自身に設定する。そして、コマンドＡを候補コマンドかつ基準コマンドとする（候補ポインタおよび基準ポインタをコマンドＡに設定する）（Ｓ２３）。すなわち、最初に到来したコマンドは、基準コマンドかつ候補コマンドとされる。図２４に戻り、コマンドテーブルのコマンド数をチェックし（Ｓ１２）、コマンド数は１であるため、コマンドＡの次に大きい終了角度をもつコマンドを自分自身に設定した終了角度リンクリストを作成する。すなわち、コマンドＡの終了角度ポインタを自分自身に設定する（Ｓ１３）。
【００３４】
以上の結果、開始角度リンクリストおよび終了角度リンクリストは図１０のようになる。実線矢印は開始角度ポインタによるコマンドの結合を表し、開始角度リンクと称される。開始角度リンク（開始角度ポインタ）によって結合されたコマンドの集合は開始角度リンクリストに相当する。また、点線矢印は終了角度ポインタによるコマンドの結合を表し、終了角度リンクと称される。終了角度リンク（終了角度ポインタ）によって結合されたコマンドの集合は終了角度リンクリストに相当する。点線矢印に付加された数字は、終了角度リンクリストにおけるコマンドの結合順序を示すもので、理解の簡単のため付加したものである。コマンドを表す矩形の内側に記された「基」はこのコマンドが基準コマンドであることを表し、「候」はこのコマンドが候補コマンドであることを表す。「０」は総周回待ち数を表す。総周回待ち数はテーブル管理部６において内部的に管理される。現時点において基準位置は０であるとする。なお実行コマンドはまだ存在しない。
【００３５】
（２）コマンド（４０、５０）の到来
次にホスト１からコマンド（４０、５０）（コマンドＡ）が到来する。コマンド（４０、５０）のディスク上における位置を図９に示す。（１）と同様に、図２４のフローチャートに示すコマンド格納処理を行って、到来したコマンドを開始角度リンクリストおよび終了角度リンクリストに追加し、基準ポインタおよび候補ポインタを更新する。
【００３６】
より詳細に、Ｓ１１において図２５の開始角度リンク追加処理に進み、コマンドテーブルのコマンド数をチェックする（Ｓ２１）。
【００３７】
コマンド数は１つであるためＳ２４に進む。Ｓ２４において、基準コマンド（基準ポインタ）から開始角度リンクリストを辿り、開始角度が昇順になる位置にコマンドＡを追加する。すなわちコマンドテーブル内の各コマンドの開始角度が昇順になるように各コマンドの開始角度ポインタを更新する。
【００３８】
次に、基準位置から最も遠い開始角度を保持するのは基準コマンド（現在、コマンド（２０、６０））であるかコマンドＡであるかをチェックする（Ｓ２５）。現在、実行コマンドは無く、ヘッド位置は０度（基準線１６上）とする。よって、基準位置は０度となり、コマンドＡが基準位置から最も遠い開始角度を保持する。よってコマンドＡを基準コマンドとする（基準ポインタを更新する）（Ｓ２６）。
【００３９】
次に、コマンドＡが優先コマンドであるかどうかを検査し（Ｓ２７）、コマンドＡは優先コマンドでないため（Ｓ２７のＮＯ）、次に、優先コマンドが存在するかどうかをチェックする（Ｓ２８）。
【００４０】
優先コマンドは存在しないため（Ｓ２８のＮＯ）、次に、基準位置から最も早くアクセス可能であるのはコマンドＡか候補コマンドであるかを判断する（Ｓ２９）。基準位置から最も早くアクセス可能であるのはここでは候補コマンド（コマンド（２０、６０））であるとし、コマンド（２０、６０）がそのまま候補コマンドとなる（候補ポインタはそのまま）。仮に優先コマンドが存在する場合は（Ｓ２８のＹＥＳ）、コマンドＡが優先コマンドを遅らせずに実行でき（Ｓ３２のＹＥＳ）かつコマンドＡの方が候補コマンドよりも早く実行終了する（Ｓ３３のコマンドＡ）場合はコマンドＡを候補コマンドとし（Ｓ３０）、これ以外の場合は（Ｓ３２のＮＯあるいはＳ３３の候補コマンド）、候補コマンドをそのままとする。
【００４１】
図２４に戻り、コマンドテーブルのコマンド数をチェックし（Ｓ１２）、コマンド数は２つであるため、Ｓ１４に進み、終了角度リンクリストを辿ったときに終了角度が昇順になる位置にコマンドＡを追加する。すなわちコマンドテーブル内の各コマンドの終了角度が昇順になるように各コマンドの終了角度ポインタを更新する。
【００４２】
以上の結果、開始角度リンクリストおよび終了角度リンクリストは図１１のようになる。
【００４３】
（３）コマンド（３０、７０）の到来
次にホスト１からコマンド（３０、７０）（コマンドＡ）が到来する。コマンド（３０、７０）のディスク上における位置を図９に示す。（１）と同様に、図２４のフローチャートに示すコマンド格納処理を行って、到来したコマンドを開始角度リンクリストおよび終了角度リンクリストに追加し、基準ポインタおよび候補ポインタを更新する。
【００４４】
より詳細に、Ｓ１１において図２５の開始角度追加リンク処理に進み、コマンドテーブルのコマンド数をチェックする（Ｓ２１）。
【００４５】
コマンド数は２つであるためＳ２４に進む。Ｓ２４において、基準コマンド（基準ポインタ）から開始角度リンクリストを辿り、開始角度が昇順になる位置にコマンドＡを加える。すなわち、コマンドテーブル内の各コマンドの開始角度が昇順になるように各コマンドの開始角度ポインタを更新する。
【００４６】
次に、基準位置から最も遠い開始角度を保持するのは基準コマンド（現在、コマンド（４０、５０））であるかコマンドＡであるかをチェックする（Ｓ２５）。現在、実行コマンドは無く、ヘッド位置は５度（基準位置は５度）とする。よって現在の基準コマンド（４０、５０）がそのまま基準コマンドとなる（基準ポインタはそのまま）。
【００４７】
次に、コマンドＡが優先コマンドであるかどうかを検査し（Ｓ２７）、コマンドＡは優先コマンドでないため（Ｓ２７のＮＯ）、次に、優先コマンドが存在するかどうかをチェックする（Ｓ２８）。
【００４８】
優先コマンドは存在しないため（Ｓ２８のＮＯ）、次に、基準位置から最も早くアクセス可能であるのはコマンドＡか候補コマンドであるかを判断する（Ｓ２９）。基準位置から最も早くアクセス可能であるのはここでは候補コマンド（コマンド（２０、６０））であるとし、コマンド（２０、６０）がそのまま候補コマンドとなる（候補ポインタはそのまま）。
【００４９】
図２４に戻り、コマンドテーブルのコマンド数をチェックし（Ｓ１２）、コマンド数は３つであるため、Ｓ１４に進み、終了角度リンクリストを辿ったときに終了角度が昇順になる位置にコマンドＡを追加する。すなわちコマンドテーブル内の各コマンドの終了角度が昇順になるように各コマンドの終了角度ポインタを更新する。
【００５０】
以上の結果、開始角度リンクリストおよび終了角度リンクリストは図１２のようになる。
【００５１】
（４）コマンド（６０、８０）の到来
次にホスト１からコマンド（６０、８０）（コマンドＡ）が到来する。コマンド（６０、８０）のディスク上における位置を図９に示す。（１）と同様に、図２４のフローチャートに示すコマンド格納処理を行って、到来したコマンドを開始角度リンクリストおよび終了角度リンクリストに追加し、基準ポインタおよび候補ポインタを更新する。
【００５２】
より詳細に、Ｓ１１において図２５の開始角度追加リンク処理に進み、コマンドテーブルのコマンド数をチェックする（Ｓ２１）。
【００５３】
コマンド数は３つであるためＳ２４に進む。Ｓ２４において、基準コマンドから開始角度リンクリストを辿り、開始角度が昇順になる位置にコマンドＡを加える。すなわちコマンドテーブル内の各コマンドの開始角度が昇順になるように各コマンドの開始角度ポインタを更新する。
【００５４】
次に、基準位置から最も遠い開始角度を保持するのは基準コマンド（現在、コマンド（４０、５０））であるかコマンドＡであるかをチェックする（Ｓ２５）。現在、実行コマンドは無く、現在のヘッド位置は１０度（基準位置は１０度）とし、コマンドＡが基準位置から最も遠い開始角度を保持する。よってコマンドＡを基準コマンドとする（基準ポインタを更新する）（Ｓ２６）。
【００５５】
次に、コマンドＡが優先コマンドであるかどうかを検査し（Ｓ２７）、コマンドＡは優先コマンドでないため（Ｓ２７のＮＯ）、次に、優先コマンドが存在するかどうかをチェックする（Ｓ２８）。
【００５６】
優先コマンドは存在しないため（Ｓ２８のＮＯ）、次に、基準位置から最も早くアクセス可能であるのはコマンドＡか候補コマンドであるかを判断する（Ｓ２９）。基準位置から最も早くアクセス可能であるのはここでは候補コマンド（コマンド（２０、６０））であるとし、コマンド（２０、６０）がそのまま候補コマンドとなる（候補ポインタはそのまま）。
【００５７】
図２４に戻り、コマンドテーブルのコマンド数をチェックし（Ｓ１２）、コマンド数は４つであるため、Ｓ１４に進み、終了角度リンクリストを辿ったときに終了角度が昇順になる位置にコマンドＡを追加する。すなわちコマンドテーブル内の各コマンドの終了角度が昇順になるように各コマンドの終了角度ポインタを更新する。
【００５８】
以上の結果、開始角度リンクリストおよび終了角度リンクリストは図１３のようになる。
【００５９】
（５）コマンド実行の開始
コマンドを実行する際は、コマンド実行要求部８が候補コマンドの実行要求をディスク装置４に対し行う。ここではコマンド（２０、６０）が実行コマンドとなる。コマンドの実行要求を行ったら、図２６のフローチャートに示すテーブル更新処理を行って、基準ポインタおよび候補ポインタ（基準コマンドおよび候補コマンド）を更新する。
【００６０】
より詳細に、まずＳ４１において、図２７のフローチャートに示す基準コマンド探索処理を行う。現在の基準コマンドをコマンドＢとし、開始角度リンクリストにおいてコマンドＢの１つ先のコマンドをコマンドＢ２とする（Ｓ５１）。
【００６１】
基準位置がコマンドＢの開始角度とコマンドＢ２の開始角度の間であるかどうかをチェックする（Ｓ５２）。ここではコマンドＢはコマンド（６０、８０）、コマンドＢ２は（２０、６０）であるから、基準位置をｘとした場合、６０≦ｘ≦３６０または０≦ｘ＜２０の条件を満たすかどうかをチェックする。基準位置は実行コマンドの終了角度である６０度である。よって上記条件が満たされるため（Ｓ５２のＹＥＳ）、コマンドＢを基準コマンドとする（Ｓ５３）（角度が等しい時は一番遠いものとみなす）。すなわち基準コマンドは変わらない。仮にＳ５２において上記条件が満たされない場合は（Ｓ５２のＮＯ）、コマンドＢ２をコマンドＢとし（Ｓ５４）、コマンドＢ２の次のコマンドをコマンドＢ２として（Ｓ５５）、Ｓ５２に戻る。
【００６２】
図２６に戻り、Ｓ４２において優先コマンドが存在するかどうかをチェックし（Ｓ４２）、優先コマンドは存在しないため（Ｓ４２のＮＯ）、Ｓ４４に進む。Ｓ４４においてパラメータａ＝０とし、次のＳ４５において基準コマンド（Ｓ５３で決定した基準コマンド）をコマンドＢとして、図２８のフローチャートに示す候補コマンド探索処理を行う（Ｓ４６）。
【００６３】
実行していないコマンドがコマンドテーブルに存在していれば（Ｓ６１のＹＥＳ）Ｓ６２に進み、そうでなければ（Ｓ６１のＮＯ）本処理を終了する。ここではＳ６２に進み、開始角度リンクリストにおいてコマンドＢ（基準コマンド）の次のコマンドをコマンドＢとする。次に、コマンドＢが実行コマンドであるかどうかをチェックし（Ｓ６３）、ここではコマンドＢはコマンド（２０、６０）であり実行コマンドであるため（Ｓ６３のＹＥＳ）Ｓ６２に戻る。Ｓ６２においてコマンド（３０、７０）がコマンドＢとなり、Ｓ６３のＮＯを経て、Ｓ６４において、基準位置からコマンドＢにシークした際の周回待ち数ｂを計算する。ここで周回待ち数ｂは０と計算されたとする。パラメータａと周回待ち数ｂとが等しいかどうかをチェックする（Ｓ６５）。ここではａとｂとが等しいため（Ｓ６５のＹＥＳ）、コマンドＢを候補コマンドとする（Ｓ６６）。仮にＳ６５においてａとｂとが等しくない場合は（Ｓ６５のＮＯ）、コマンドＢが基準コマンドであるかどうかをチェックし（Ｓ６７）、基準コマンドでない場合は（Ｓ６７のＮＯ）Ｓ６２に戻る。一方コマンドＢが基準コマンドである場合は（Ｓ６７のＹＥＳ）ａに１を加算し（パラメータを１増加し）（Ｓ６８）Ｓ６２に戻る。要するに、開始角度リンクリストにおいて実行中のコマンドの終了角度（基準位置）に対して最も小さい開始角度をもつコマンドを起点として開始角度リンクリストを順に辿り、実行中のコマンド以外で周回待ち数がパラメータａに最も早く一致したコマンドを選択し、パラメータａに一致する周回待ち数のコマンドが存在しなかった場合は、パラメータａを増加して、再度開始角度リンクリストを辿る。
【００６４】
以上の結果、開始角度リンクリストおよび終了角度リンクリストは図１４のようになる。
【００６５】
（６）コマンド（１００、１５０）の到来
次に、ホスト１からコマンド（１００、１５０）（コマンドＡ）が到来する。コマンド（１００、１５０）のディスク上における位置を図９に示す。（１）と同様に、図２４のフローチャートに示すコマンド格納処理を行って、到来したコマンドを開始角度リンクリストおよび終了角度リンクリストに追加し、基準ポインタおよび候補ポインタを更新する。。
【００６６】
より詳細に、Ｓ１１において図２５の開始角度追加リンク処理に進み、コマンドテーブルのコマンド数をチェックする（Ｓ２１）。
【００６７】
コマンド数は４つであるためＳ２４に進む。Ｓ２４において、基準コマンド（基準ポインタ）から開始角度リンクリストを辿り、開始角度が昇順になる位置にコマンドＡを加える。すなわちコマンドテーブル内の各コマンドの開始角度が昇順になるように各コマンドの開始角度ポインタを更新する。
【００６８】
次に、基準位置から最も遠い開始角度を保持するのは基準コマンド（現在、コマンド（６０、８０））であるかコマンドＡであるかをチェックする（Ｓ２５）。コマンド（２０、６０）が実行中であり、基準位置は６０度である。よって、現在の基準コマンドが基準位置から最も遠い開始角度を保持する。よって現在の基準コマンドがそのまま基準コマンドとなる（基準ポインタはそのまま）。
【００６９】
次に、コマンドＡが優先コマンドであるかどうかを検査し（Ｓ２７）、コマンドＡは優先コマンドでないため（Ｓ２７のＮＯ）、次に、優先コマンドが存在するかどうかをチェックする（Ｓ２８）。
【００７０】
優先コマンドは存在しないため（Ｓ２８のＮＯ）、次に、基準位置から最も早くアクセス可能であるのはコマンドＡか候補コマンドであるかを判断する（Ｓ２９）。基準位置から最も早くアクセス可能であるのはここではコマンドＡ（コマンド（１００、１５０））であるとし、コマンドＡを候補コマンドとする（候補ポインタを更新する）。（Ｓ３０）。
【００７１】
図２４に戻り、コマンドテーブルのコマンド数をチェックし（Ｓ１２）、コマンド数は５つであるため、Ｓ１４に進み、終了角度リンクリストを辿ったときに終了角度が昇順になる位置にコマンドＡを追加する。すなわちコマンドテーブル内の各コマンドの終了角度が昇順になるように各コマンドの終了角度ポインタを更新する。
【００７２】
以上の結果、開始角度リンクリストおよび終了角度リンクリストは図１５のようになる。
【００７３】
（７）コマンド（２０、６０）の実行終了
コマンド（２０、６０）の実行が終了したら、図２９のフローチャートに示すコマンド削除処理を行って該コマンドをコマンドテーブル（開始角ドリンクリストおよび終了角度リンクリスト）から削除する。
【００７４】
より詳細には,まずコマンドテーブルのコマンド数をチェックする（Ｓ７１）。コマンド数は２つ以上（５つ）であるため、Ｓ７２に進む。Ｓ７２では、終了角度リンクリストにおいてコマンドＡ（元実行コマンド）の１つ手前のコマンド（ここではコマンド（４０、５０））と、１つ後のコマンド（ここではコマンド（３０、７０））とが昇順になるように終了角度ポインタを更新する。Ｓ７１においてコマンドテーブルのコマンド数が１つである場合は、終了角度リンクリストを削除する（Ｓ７４）。Ｓ７２またはＳ７４の後、Ｓ７３に進み、図３０のフローチャートに示す開始角度リンク削除処理を行う。
【００７５】
図３０において、コマンドテーブルのコマンド数をチェックし（Ｓ８１）、コマンド数は２以上（５つ）であるため、Ｓ８２に進む。コマンド数が１つである場合は（Ｓ８６）開始角度リンクリストを削除し（Ｓ８６）、図２９に戻り、コマンド削除処理を終了する。
【００７６】
Ｓ８２において、コマンドＡ（元実行コマンド）は基準コマンドであるか否かをチェックし、ここではコマンドＡは基準コマンドでないため（Ｓ８２のＮＯ）、Ｓ８３に進む。仮にコマンドＡが基準コマンドである場合は（Ｓ８２のＹＥＳ）、開始角度リンクリストにおいてコマンドＡの１つ手間のコマンドを基準コマンドとする（基準ポインタを更新する）（Ｓ８５）。
【００７７】
Ｓ８２またはＳ８５の後、コマンドＡが候補コマンドであるか否かをチェックする（Ｓ８３）。コマンドＡは候補コマンドでないため（Ｓ８３のＮＯ）、Ｓ８４に進む。開始角度リンクリストにおいてコマンドＡの１つ手前のコマンドと、１つ後のコマンドとを開始角度が昇順になるように結び、コマンドＡをコマンドテーブル（開始角度リンクリストおよび終了角度リンクリスト）から削除する。この後、図２９に戻り、コマンド削除処理を終了する。以上により開始角度リンクリストおよび終了角度リンクリストは図１６のようになる。なお、コマンドＡが候補コマンドである場合は（Ｓ８３のＹＥＳ）、Ｓ８７〜Ｓ８９において候補コマンドの探索を行う。コマンドＡが候補コマンドである場合としては、例えば同一LBAに書き込みコマンドが発生した場合が挙げられる。すなわち同一LBAに書き込みコマンドが発生した場合、先に発行されているコマンド（候補コマンドとする）を行う必要がなくなるため、図２９のコマンド削除処理を実行して、先のコマンドを削除する。
【００７８】
図２９のコマンド削除処理を終了したら、次の実行コマンドを決定する。ここでは候補コマンド（１００、１５０）が次の実行コマンドとして決定される。実行コマンドが決定されたら、図２６に示したコマンド更新処理を行って、基準コマンドおよび候補コマンドを更新する。
【００７９】
より詳細には、まずＳ４１で基準コマンド探索処理を行い（図２７参照）、この結果、実行コマンド（１００、１５０）が基準コマンドとされる。基準位置は実行コマンド（１００、１５０）の終了角度である１５０度である。優先コマンドは存在しないため（Ｓ４２のＮＯ）、ａ＝０とし（Ｓ４４）、コマンドＢを基準コマンドとして（Ｓ４５）、Ｓ４６で候補コマンド探索処理（図２８参照）を行う。この結果、コマンド（３０、７０）が候補コマンドとされる。
【００８０】
次に、図３１のフローチャートに示す取り残しコマンド検出処理を行って、コマンドテーブルにある各コマンドの総周回待ち数を更新する。すなわちテーブル管理部６はコマンドテーブルにある各コマンドがそれぞれコマンドテーブルに格納されてからディスクが何回転したかを表す総周回待ち数を計算する総周回待ち数計算部を備える。
【００８１】
より詳細には,まず元実行コマンド（ここではコマンド（２０、６０））から実行コマンド（ここではコマンド（１００、１５０））へのシーク中の周回待ち回数をａ（ここでは０）とする（Ｓ９１）。
【００８２】
次に、コマンドテーブルにある全てのコマンドの総周回待ち数にａを加算する（Ｓ９２）。
【００８３】
次に、元実行コマンド（ここではコマンド（２０、６０））をコマンドＢとする（Ｓ９３）。
【００８４】
次に、開始角度リンクリストにおいてコマンドＢ（なおコマンドＢは既に削除されている）の次のコマンド（ここではコマンド（３０、７０））をコマンドＢとする（Ｓ９４）。
【００８５】
次に、コマンドＢが実行コマンドであるか否かをチェックする（Ｓ９５）。ここではコマンドＢは実行コマンドでないため（Ｓ９５のＮＯ）、コマンドＢの総周回待ち数に１を加算して（Ｓ９６）、Ｓ９４に戻る。同様にして、コマンド（４０、５０）、コマンド（６０、８０）の総周回待ち数も１加算される。
【００８６】
Ｓ９４において実行コマンド（１００、１５０）がコマンドＢとされたら（Ｓ９５のＹＥＳ）、本処理を終了する。
【００８７】
以上により開始角度リンクリストおよび終了角度リンクリストは図１７のようになる。
【００８８】
（８）優先コマンド（７０、９０）の到来
コマンド（１００、１５０）の実行中（シーク中、回転待ち中あるいはデータの読み出しまたは書き込み中）に、ホスト１から優先コマンド（７０、９０）（コマンドＡ）が到来する。コマンド（７０、９０）のディスク上における位置を図９に示す。（１）と同様に、図２４のフローチャートに示すコマンド格納処理を行う。
【００８９】
すなわち、Ｓ１１において図２５の開始角度追加リンク処理に進み、コマンドテーブルのコマンド数をチェックする（Ｓ２１）。
【００９０】
コマンド数は４つであるためＳ２４に進む。Ｓ２４において、基準コマンド（基準ポインタ）から開始角度リンクリストを辿り、開始角度が昇順になる位置にコマンドＡを加える。すなわちコマンドＡをコマンドテーブルに追加するとともに、コマンドテーブル内の各コマンドの開始角度が昇順になるように各コマンドの開始角度ポインタを設定する。この時点における開始角度リンクリストおよび終了角度リンクリストを図１８に示す。
【００９１】
次に、基準位置から最も遠い開始角度を保持するのは基準コマンド（現在、コマンド（１００、１５０））であるかコマンドＡであるかをチェックする（Ｓ２５）。ここで、基準位置は１５０度であり、したがって現在の基準コマンド（１００、１５０）がそのまま基準コマンドとなる（基準ポインタの値は変わらない）。
【００９２】
次に、コマンドＡが優先コマンドであるかどうかを検査し（Ｓ２７）、コマンドＡは優先コマンドであるため（Ｓ２７のＹＥＳ）、優先コマンドの前に実行可能なコマンドを探索するべく、図３２のフローチャートに示す実行可能コマンド探索処理を行う（Ｓ３１）。
【００９３】
まず、候補コマンドに関して調べる。基準位置から候補コマンドまでの到達時間（基準位置から候補コマンドにシークを開始し読み出しまたは書き込みを開始するまでのディスクの総回転角度量）が、優先コマンドに到達する時間（基準位置から優先コマンドにシークを開始し読み出しまたは書き込みを開始するまでのディスクの総回転角度量）以上の場合（Ｓ１０１〜Ｓ１０４、１０５のＹＥＳ）、優先コマンドの実行に影響を与えずに実行できるコマンドは無く、優先コマンドが候補コマンドとなる（Ｓ１０６）。これは、コマンドテーブルに格納されている全てのコマンドの中で、基準位置から到達するまでの総回転角度量（到達時間）が最も小さいのは候補コマンドであるからである。なお、Ｓ１０２、Ｓ１０４で用いられる計算式内の記号%はモジュロと呼ばれる。a%bは、aをbで割り算したときの余りを表す。Ｓ１０２で計算されるｘは、基準位置から優先コマンドに到達するまでのディスクの総回転角度量を表し、Ｓ１０４で計算されるｙは、基準位置から候補コマンドに到達するまでのディスクの総回転角度量を表す。
【００９４】
一方、候補コマンドまでの到達時間が優先コマンドより短い場合（１０５のＮＯ）、優先コマンドに影響を与えずに実行できるコマンドが存在する可能性が有るため、コマンド探索を実行する（Ｓ１０７〜Ｓ１２３）。
【００９５】
すなわち、テーブル管理部６における探索部は、優先コマンドを次に実行したとした場合にディスクヘッドがアクセス開始位置に到達するまでに要する第１の到達時間（第１の回転角度量）が、候補コマンドを次に実行したとした場合にディスクヘッドがアクセス開始位置に到達するまでに要する第２の到達時間（第２の回転角度量）以下であるかどうかをチェックする。コマンド変更部は、第１の到達時間または第１の回転角度量が、第２の到達時間または第２の回転角度量以下である場合は、優先コマンドを候補コマンドとして確定し、そうでない場合はＳ１０７〜Ｓ１２３における探索を開始する。
【００９６】
以下、Ｓ１０７〜Ｓ１２３で行われる探索の詳細を説明する。
【００９７】
まずＳ１０３で計算された、基準位置から候補コマンドまでに生じる周回待ち数cを記憶しておく。cは、全コマンドの中で最小の周回待ち数となり、探索終了を判定する際に利用される。
【００９８】
コマンドの探索は、実行コマンドが存在するときは実行コマンド、存在しないときは基準コマンドから終了角度リンクリストを、終了角度の小さいコマンド順に辿る（Ｓ１０８〜Ｓ１１１）。探索中のコマンドBが優先コマンドに影響を与えることなく実行可能であるか調べ（Ｓ１１２〜Ｓ１１７）、影響を与えずにアクセスでき（Ｓ１１７のＮＯ）その周回待ち数ｂ１がcと等しい場合（Ｓ１１９のＮＯ）、コマンドBは候補コマンドとなる（Ｓ１２０）。優先コマンドに影響を与えずにアクセスできるが周回待ち数がcより大きい場合は（Ｓ１１９のＹＥＳ）候補コマンドの候補となる（準候補コマンドと呼ぶ）（Ｓ１２２）。既に準候補コマンドが存在する場合、周回待ち数がコマンドBの方が小さい場合のみ（Ｓ１２１のＹＥＳ）準候補コマンドをコマンドBに更新する（Ｓ１２２）。探索の結果、優先コマンドに影響を与えることなく実行可能でありかつｃと同じ周回待ち数をもつコマンドが無かった場合は、準候補コマンドが候補コマンドとして扱われる（候補ポインタが該準候補コマンドに設定される）。本例では、実行コマンド（１００、１５０）から終了角度リンクリストを辿り、最初のコマンド（４０、５０）が優先コマンドに影響を与えることなく実行可能でありかつ周回待ち数ｂ１がｃと等しいため、コマンド（３０、７０）からコマンド（４０、５０）に候補コマンドが変更されるとする。
【００９９】
以上のコマンド探索処理では、コマンドテーブルに格納された各コマンドで周回待ち数が全体的に大きい値である場合、全てのコマンドの探索が終わるまで、候補コマンドを決められないことが起こり得る。しかし、そのようなケースは、希少なケースである。現在のディスクにおいて、最外周から最内周までに生じるシーク時間は20ms程度、ディスクが一回転する時間は10ms程度であるため、周回待ち数は高々3程度である。また、ディスクの内側のアクセスと外側のアクセスとが混在するアクセスパターンは少なく、アクセスするのに周回待ち数が大きいコマンドだらけになることは生じづらい。よって、多くの場合、全てのコマンドの探索が完了する前に（探索の途中で）、候補コマンドが決定されるものと想定される。
【０１００】
以上のようにして候補コマンドが決定されたら、図２５に戻って開始角度リンク追加処理を終了し、さらに図２４に戻り、Ｓ１２に進む。
【０１０１】
Ｓ１２において、コマンドテーブルのコマンド数をチェックし、コマンド数は５つであるため、Ｓ１４に進み、終了角度リンクリストを辿ったときに終了角度が昇順になる位置にコマンドＡを追加する。すなわちコマンドテーブル内の各コマンドの終了角度が昇順になるように各コマンドの終了角度ポインタを更新する。
【０１０２】
以上により、開始角度リンクリストおよび終了角度リンクリストは図１９のようになる。
【０１０３】
（９）コマンド（１００、１５０）の実行終了
コマンド（１００、１５０）の実行が終了したら、図２９に示したコマンド削除処理を行って、該コマンドをコマンドテーブル（開始角ドリンクリストおよび終了角度リンクリスト）から削除する。
【０１０４】
より詳細には、まずコマンドテーブルのコマンド数をチェックする（Ｓ７１）。コマンド数は５つであるため、終了角度リンクリストにおいてコマンドＡ（ここでは元実行コマンド（１００、１５０））の１つ手前のコマンド（ここではコマンド（７０、９０））と、１つ後のコマンド（ここではコマンド（４０、５０））とが昇順になるように終了角度ポインタを更新する（Ｓ７２）。次に、Ｓ７３に進み、図３０に示した開始角度リンク削除処理を行う。
【０１０５】
図３０において、コマンドテーブルのコマンド数をチェックし（Ｓ８１）、コマンド数は２以上（５つ）であるため、Ｓ８２に進む。Ｓ８２において、コマンドＡ（元実行コマンド（１００、１５０））は基準コマンドであるか否かをチェックし、基準コマンドであるため（Ｓ８２のＹＥＳ）、開始角度リンクリストにおいてコマンドＡの１つ手前のコマンド（ここではコマンド（７０、９０））を基準コマンドとする（Ｓ８５）。次に、コマンドＡが候補コマンドであるか否かをチェックする（Ｓ８３）。コマンドＡが候補コマンドでないため（Ｓ８３のＮＯ）、Ｓ８４に進み、開始角度リンクリストにおいてコマンドＡの１つ手前のコマンドと、１つ後のコマンドとが昇順になるように開始角度ポインタを設定し、コマンドＡをコマンドテーブル（開始角度リンクリストおよび終了角度リンクリスト）から削除する。この後、図２９に戻り、コマンド削除処理を終了する。
【０１０６】
図２９のコマンド削除処理を終了したら、次の実行コマンドを決定する。候補コマンド（４０、５０）を次の実行コマンドとして設定する。この時点における開始角度リンクリストおよび終了角度リンクリストを図２０に示す。実行コマンドを決定したら、図２６に示したテーブル更新処理を行って、基準コマンドおよび候補コマンドを更新する。
【０１０７】
より詳細には,まずＳ４１で基準コマンド探索処理（図２７参照）を行い、この結果、実行コマンド（４０、５０）が基準コマンドとされる。基準位置は、実行コマンド（４０、５０）の終了角度である５０度である。
【０１０８】
次に、優先コマンドが存在するかどうかをチェックし（Ｓ４２）、ここでは優先コマンドが存在するため（Ｓ４２のＹＥＳ）、図３２に示した実行可能コマンド探索処理を行う（Ｓ４３）。この結果、優先コマンドの前に実行しても優先コマンドの実行開始時刻が変わらないコマンドは存在しないため（Ｓ１０５のＹＥＳ）、優先コマンドが候補コマンドとされる（Ｓ１０６）。図２６に戻り、テーブル更新処理を終了する。
【０１０９】
テーブル更新処理を終了したら、図３１に示した取り残しコマンド検出処理を行って、コマンドテーブル内の各コマンドの総周回待ち数を更新する。
【０１１０】
まず、元実行コマンド（１００、１５０）から次の実行コマンドへのシーク中の周回待ち回数をａ（ここでは０）とする（Ｓ９１）。
【０１１１】
次に、全てのコマンドの総周回待ち数にａを加算する（Ｓ９２）。
【０１１２】
次に、元実行コマンド（１００、１５０）をコマンドＢとする（Ｓ９３）。
【０１１３】
次に、開始角度リンクリストにおいてコマンドＢ（なおコマンドＢは既に削除されている）の次のコマンド（ここではコマンド（３０、７０））をコマンドＢとする（Ｓ９４）。
【０１１４】
次に、コマンドＢが実行コマンドであるか否かをチェックする。（Ｓ９５）、実行コマンドでないため（Ｓ９５のＮＯ）、コマンドＢの総周回待ち数を１加算して（Ｓ９６）、Ｓ９４に戻る。コマンド（３０、７０）の次のコマンドは実行コマンド（４０、５０）であるため（Ｓ９５のＹＥＳ）、本処理を終了する。
【０１１５】
以上により開始角度リンクリストおよび終了角度リンクリストは図２１のようになる。
【０１１６】
（１０）コマンド（４０、５０）の実行終了
コマンド（４０、５０）の実行が終了したら、図２９に示したコマンド削除処理を行って、該コマンドをコマンドテーブル（開始角ドリンクリストおよび終了角度リンクリスト）から削除する。
【０１１７】
より詳細には,まずコマンドテーブルのコマンド数をチェックする（Ｓ７１）。コマンド数は２つ以上（４つ）であるため、終了角度リンクリストにおいてコマンドＡ（ここでは元実行コマンド（４０、５０））の１つ手前のコマンド（ここではコマンド（７０、９０））と、１つ後のコマンド（ここではコマンド（３０、７０））とが昇順になるように終了角度ポインタを更新する（Ｓ７２）。次に、Ｓ７３に進み、図３０に示した開始角度リンク削除処理を行う。
【０１１８】
図３０において、コマンドテーブルのコマンド数をチェックし（Ｓ８１）、コマンド数は２以上（4つ）であるため、Ｓ８２に進む。Ｓ８２において、コマンドＡ（元実行コマンド（４０、５０））は基準コマンドであるか否かをチェックし、基準コマンドであるため（Ｓ８２のＹＥＳ）、開始角度リンクリストにおいてコマンドＡの１つ手前のコマンド（ここではコマンド（３０、７０））を基準コマンドとする。次に、コマンドＡが候補コマンドであるか否かをチェックする（Ｓ８３）。コマンドＡが候補コマンドでないため（Ｓ８３のＮＯ）、Ｓ８４に進み、開始角度リンクリストにおいてコマンドＡの１つ手前のコマンドと、１つ後のコマンドとが昇順になるように開始角度ポインタを設定し、コマンドＡをコマンドテーブル（開始角度リンクリストおよび終了角度リンクリスト）から削除する。この後、図２９に戻って、コマンド削除処理を終了する。
【０１１９】
図２９のコマンド削除処理を終了したら、次の実行コマンドを決定する。候補コマンド（７０、９０）を次の実行コマンドとして設定する。この時点で優先コマンドが無くなったため、総周回待ち数が閾値（ここでは２とする）以上で、基準線（基準となる半径線）に対し最も開始角度の小さいコマンドを優先コマンドとする。すなわちテーブル管理部６における優先コマンド検出部は、総周回待ち数計算部によって計算される総周回待ち数が閾値以上となったコマンドを優先コマンドとして検出する。ここではコマンド（３０、７０）が優先コマンドとして検出される。実行コマンドを決定したら、図２６に示したテーブル更新処理を行って、基準コマンドおよび候補コマンドを更新する。
【０１２０】
より詳細には,まずＳ４１で基準コマンド探索処理（図２７参照）を行い、この結果、コマンド（７０、９０）が基準コマンドとされる。基準位置は、実行コマンド（７０、９０）の終了角度である９０度である。この時点にける開始角度リンクリストおよび終了角度リンクリストを図２２に示す。
【０１２１】
次に、優先コマンドが存在するかどうかをチェックし（Ｓ４２）、ここでは優先コマンドが存在するため（Ｓ４２のＹＥＳ）、図３２に示した実行可能コマンド探索処理を行う（Ｓ４３）。この結果、優先コマンドが候補コマンドとされる。図２６に戻り、テーブル更新処理を終了する。
【０１２２】
テーブル更新処理を終了したら、図３１に示した取り残しコマンド検出処理を行う。
【０１２３】
元実行コマンド（４０、５０）から次の実行コマンド（７０、９０）へのシーク中の周回待ち回数をａ（ここでは０）とする（Ｓ９１）。
【０１２４】
次に、全てのコマンドの総周回待ち数にａを加算する（Ｓ９２）。
【０１２５】
次に、元実行コマンド（４０、５０）をコマンドＢとする（Ｓ９３）。
【０１２６】
次に、開始角度リンクリストにおいてコマンドＢ（コマンドＢは既に削除されている）の次のコマンド（ここではコマンド（６０、８０））をコマンドＢとする（Ｓ９４）。
【０１２７】
次に、コマンドＢが実行コマンドであるか否かをチェックする（Ｓ９５）。実行コマンドでないため（Ｓ９５のＮＯ）、コマンドＢの総周回待ち数を１加算して（Ｓ９６）、Ｓ９４に戻る。コマンド（６０、８０）の次のコマンドは実行コマンド（７０、９０）であるため（Ｓ９５のＹＥＳ）、本処理を終了する。
【０１２８】
以上により開始角度リンクリストおよび終了角度リンクリストは図２３のようになる。
【０１２９】
以降、同様にして、コマンドテーブル内の残りのコマンドが順次実行されていく。
【０１３０】
（第２の実施の形態）
本実施の形態では、テーブル管理部６による処理の一例として「２分木を用いたコマンド管理」について説明する。まず本実施の形態で使用する用語について簡単に説明しておく。なお「基準位置」「実行コマンド」「優先コマンド」「候補コマンド」は第１の実施形態と同様であるため説明を省略する。
「ヒープ」：テーブル管理部６により管理される各コマンドは、開始角度、終了角度、最小終了角度（後述）、最小終了角度方向（後述）の情報を保持している。コマンドの管理方法は基本的に、図３３（Ａ）の中央に示すように、開始角度に基づいたヒープ条件を満たす２分木で行う。根コマンド（後述するように２分木の根に当たる位置に格納されたコマンド）には、基準位置からの周回待ちが最も小さくかつ基準位置から最も小さい開始角度を持つコマンド（基準位置からシークして実行するとした場合のディスクの総回転角度量が最も小さいコマンド）が格納される。実行コマンドおよび優先コマンドは2分木とは別に管理される。テーブル管理部６はこのような２分木を生成および維持する２分木維持部を備えている。優先コマンドは複数発生することが考えられるため、これらを優先コマンドキューにおいて発行順に管理し、最も古いコマンドを優先コマンドとし、それ以外のコマンドを優先コマンドの候補として扱う。ヒープは配列で管理可能であるため、図３３（Ｂ）に示すように、一つの配列（コマンドテーブル）内で、ヒープ（２分木）、優先コマンドキュー、実行コマンドを管理できる（コマンド総数をNとしている）。
「２分木の条件」：根の位置に来るコマンドは、基準位置からの周回待ちが最も小さくかつ基準位置から最も小さい開始角度を持つコマンド（ＳＴＦにより選択されるコマンド）であり、根コマンドの開始角度を基準として昇順になるようにヒープを構成していることである。２分木の条件を満たす２分木の一例を図３７に示す。「丸１（円を表す図形の中に１が入っている）」は後述する最小終了角度、「丸２（円を表す図形の中に２が入っている）」は後述する最小終了角度方向である。候補コマンドは、優先コマンドが存在しない場合は、必ず2分木の根の位置に格納され、実行するコマンドを決める際は無条件にこの根コマンドが選択される。ただし、優先コマンドが存在する場合は、候補コマンドは、2分木の根コマンドとは限られず、優先コマンドの場合もある。
「根コマンド」「葉コマンド」「末尾コマンド」：２分木の根に格納されたコマンドを根コマンド、２分木の葉に格納されたコマンドを葉コマンドという。また、葉コマンドの中で、最も根コマンドから階層が深く、かつ、一番右に位置するコマンドを末尾コマンドという。根コマンド、葉コマンド、末尾コマンドの例を図３４に示す。
「親コマンド」「子コマンド」「左子コマンド」「右子コマンド」：あるコマンドAに対し、根の方向に隣接したコマンドをコマンドAの親コマンド、葉の方向に隣接したコマンドをコマンドAの子コマンドという。子コマンドは左側に位置する左子コマンドと、右側に位置する右子コマンドの２種類ある。親コマンド、子コマンド、左子コマンド、右子コマンドの例を図３５に示す。
「先祖コマンド」「子孫コマンド」：あるコマンドAにおいて、コマンドAの格納位置より、根方向に枝を辿った際に通る全てのコマンドをAの先祖コマンド、根から遠ざかる方向に枝を辿った際に通る全てのコマンドをAの子孫コマンドと呼ぶ。先祖コマンドおよび子孫コマンドの例を図３６に示す。
「最小終了角度」「最小終了角度方向」：コマンドAの最小終了角度とは、コマンドAとその子孫コマンドの終了角度の中で、基準位置から見て最小の終了角度のことである。コマンドAの最小終了角度方向とは、コマンドAの最小終了角度となる終了角度を保持するコマンドがコマンドAから見て、どの方向にあるのかを表す情報である。自分自身の場合、コマンドAの右子コマンドの子孫となる場合、コマンドAの左子コマンドの子孫となる場合の3通りある。図３７の２分木の例を用いて具体的に示す。基準位置を０度、コマンド（８０、１０５）をコマンドＡとする。コマンドＡの子孫コマンドはコマンド（８８、９０）およびコマンド（９５、１６０）の２つである。コマンドＡおよびこれらの子孫コマンドの中で、基準位置０度から見て最小の終了角度をもつものは、終了角度９０をもつコマンド（８８、９０）である。したがってコマンドＡの最小終了角度は９０度、最小終了角度方向は左となる。最小終了角度と最小終了角度方向とを総称して、「終了角度情報」と呼ぶ。
【０１３１】
以下、「２分木を用いたコマンド管理」について具体例を用いて詳細に説明する。
【０１３２】
（１）コマンド（２０、６０）の到来
まずホスト１からコマンド（２０、６０）が到来する。ホスト１からコマンドが到来すると、図６３のフローチャートに示すコマンド格納処理（コマンドn(n_t, n_l)を２分木に格納する処理）を行う。コマンドn(n_t, n_l)におけるn_tはコマンドｎの開始角度、n_lはコマンドnの終了角度を表す。２分木にコマンドが無いため（Ｓ２０１のＹＥＳ）、到来したコマンドを、図３８に示すように、根の位置に格納し（Ｓ２０２）、図６５のフローチャートに示す終了角度情報の更新処理（子との終了角度更新処理）を行う（Ｓ２０３）。この処理では、対象となるコマンド（コマンドＡ）と、その子コマンドの終了角度情報とを比べて、終了角度情報の更新を行う。現時点では子コマンドが存在しないため（図６５のＳ２４１のＮＯ）、最小終了角度は自コマンドの終了角度である６０度、最小終了角度方向は自分となる（Ｓ２４２）。ここでA_mはコマンドAの最小終了角度、A_lはコマンドAの終了角度、A_dはコマンドAの最小終了角度方向を表す。また後の説明に出てくるA_tはコマンドAの開始角度を表す。図３８のコマンド内に示される（２０、６０）はコマンドの（開始角度、終了角度）を表し、「６０」は最小終了角度が６０度であること、「自」は最小終了角度方向が自分であること、「０」は総周回待ち数が０であることを表す。優先コマンドが存在しないため、候補ポインタは２分木の根を指し示す（図中矢印参照）。このように、コマンドは、（開始角度、終了角度）で表現し、最小終了角度、最小終了角度方向、コマンドの総周回待ち数は、（開始角度、終了角度）の下側に表示される。最小終了角度方向は、自分自身なら「自」、左子コマンド方向なら「左」、右子コマンド方向なら「右」とする。優先コマンド、実行コマンドに対してはそれぞれ、後に示されるように、「優」、「実」の文字が付される。
【０１３３】
（２）コマンド（４０、５０）の到来
次にコマンド（４０、５０）が到来し、コマンド格納処理（図６３参照）を行う。２分木に他のコマンドが存在するため（Ｓ２０１のＮＯ）、到来したコマンドを根コマンドと比較し根コマンドの条件（基準位置から周回待ちが最も少なくかつ基準位置から最も開始角度が小さいコマンド）を満たすコマンド、すなわちSTFアルゴリズムにより選択されるコマンドを根コマンドとし、そうでない方を２分木の末尾に格納する。現在、基準位置は０度とし（実行コマンドはまだ無い）であり、基準位置からコマンド（２０、６０）に周回待ち無しでアクセスできると想定する。根コマンドの条件を満たすのはコマンド（２０、６０）であるため（Ｓ２０４、Ｓ２０５、Ｓ２０６、Ｓ２０７のＮＯ、Ｓ２０８のＹＥＳ、Ｓ２０９のＹＥＳ）、コマンド（４０、５０）を２分木の末尾に格納するためコマンド末尾格納処理を行う（Ｓ２１０）。なお根コマンドr(r_t, r_l)におけるr_tは根コマンドrの開始角度、r_lは根コマンドrの終了角度を表す。コマンド末尾格納処理のフローを図６４に示す。この処理において、コマンド（４０、５０）を２分木の末尾に格納するとともに（Ｓ２２１）、格納したコマンドを２分木の条件に合うようにするためソーティング処理（Ｓ２２２〜Ｓ２２６）を行う。２分木の条件とは、前述したように、根コマンドの条件を満たし、かつ、根コマンドの開始角度を基準として開始角度の昇順になるようにヒープを構成することである。ソーティング処理の結果、２分木は図３９のようになる。ソーティング処理におけるＳ２２６では、図６６のフローチャートに示す終了角度情報（最小終了角度および最小終了角度方向）の更新処理（先祖との終了角度更新処理）を行う。この処理では、格納位置Ｘ（ここではコマンド（４０、５０））から、その先祖にあるコマンドＡ（ここではコマンド（２０、６０））までの終了角度情報を更新する（Ｓ２６１〜S２６７）。
【０１３４】
（３）コマンド（３０、７０）の到来
次にコマンド（３０、７０）が到来し、コマンド格納処理（図６３参照）を行う。２分木に他のコマンドが存在するため（Ｓ２０１のＮＯ）、到来したコマンドを根コマンドと比較し根コマンドの条件を満たす方を根コマンドとし、そうでない方を２分木の末尾に格納する。現在、基準位置は５度（実行コマンドはまだ無い）とし、基準位置からコマンド（２０、６０）に周回待ち無しでアクセスできると想定する。根コマンドの条件を満たすのはコマンド（２０、６０）であるため（Ｓ２０４、Ｓ２０５、Ｓ２０６、Ｓ２０７のＮＯ、Ｓ２０８のＹＥＳ、Ｓ２０９のＹＥＳ）、コマンド（３０、７０）を２分木の末尾に格納するためコマンド末尾格納処理（図６４参照）を行う（Ｓ２１０）。この処理では、コマンド（３０、７０）を２分木の末尾に格納するとともに（Ｓ２２１）、格納したコマンドを２分木の条件に合うようにするためソーティング処理（Ｓ２２２〜Ｓ２２６）を行う。このソーティング処理の結果、２分木は図４０のようになる。
【０１３５】
（４）コマンド（６０、８０）の到来
次にコマンド（６０、８０）が到来し、コマンド格納処理（図６３参照）を行う。２分木に他のコマンドが存在するため（Ｓ２０１のＮＯ）、到来したコマンドを根コマンドと比較し根コマンドの条件を満たす方を根コマンドとし、そうでない方を２分木の末尾に格納する。現在、基準位置は１０度（実行コマンドはまだ無い）とし、基準位置からコマンド（２０、６０）に周回待ち無しでアクセスできると想定する。根コマンドの条件を満たすのはコマンド（２０、６０）であるため（Ｓ２０４、Ｓ２０５、Ｓ２０６、Ｓ２０７のＮＯ、Ｓ２０８のＹＥＳ、Ｓ２０９のＹＥＳ）、コマンド（６０、８０）を２分木の末尾に格納するためのコマンド末尾格納処理（図６４参照）を行う（Ｓ２１０）。この処理では、コマンド（６０、８０）を２分木の末尾に格納するとともに（Ｓ２２１）、格納したコマンドを２分木の条件に合うようにするためソーティング処理（Ｓ２２２〜Ｓ２２６）を行う。ソーティング処理の結果、２分木は図４１のようになる。
【０１３６】
（５）コマンド実行の開始
コマンドを実行する際は、候補ポインタに示される候補コマンドを実行コマンドとして選択する。ここでは図４２に示すように、コマンド（２０、６０）が選択される。基準位置は、実行コマンドの終了角度である６０度となるが、現段階では更新しないものとする。
【０１３７】
次に、実行コマンドとして選択されたコマンド（２０、６０）を２分木から削除するため図６７のフローチャートに示すコマンド削除処理を行う。この処理では、図４３に示すように、２分木から削除したいコマンド（ここではコマンド（２０、６０））の格納位置に末尾のコマンド（ここではコマンド（６０、８０））を入れ（Ｓ２７１）、２分木の条件を満たすように２分木をソーティング処理する（Ｓ２７２、Ｓ２７３のＹＥＳ、Ｓ２７４、Ｓ２７５、S２８０１）。この結果、図４４に示すように、根の位置にあったコマンド（６０、８０）がコマンド（３０、７０）と入れ替えられるとともに図４５のようにコマンド（３０、７０）の終了角度情報が更新される。より詳しく説明すると、Ｓ２７４では、図６９のフローチャートに示す子との比較＆入れ替え処理（Ｓ２９１〜Ｓ２９４）を行う。この処理では、対象となるコマンド（コマンドＡ）とその子コマンドを比較し、２分木の条件を満たすまでコマンドＡと子コマンドの入れ替えを行う。Ｓ２９１では、図７０のフローチャートに示す子同士の比較＆入れ替え処理（Ｓ３０１〜Ｓ３１１）を行う。この処理では、左右両方の子コマンド同士を比較し、開始角度が小さいコマンドを探す。図６７のＳ２７４の処理の結果、２分木は図４４に示したようになり、続いて、Ｓ２７５、S２８０１において終了角度情報の更新（図６６参照）を行うことで、図４５に示したように、コマンド（３０、７０）の終了角度情報が更新される。
【０１３８】
ここで、基準位置を更新する。この結果、基準位置は、実行コマンド（２０、６０）の終了角度である６０度になる。
【０１３９】
続いて、図７１のフローチャートに示す２分木の更新処理（S３２０〜S３４０）を行って、２分木の条件を満たすように２分木を更新する。本例では、図４６に示すように、全てのコマンドは一度根に到達した後、末尾に格納され、このため、各コマンドの総周回待ち数は１加算される。優先コマンドが存在する場合は（Ｓ３３１のＹＥＳ）、後述する優先コマンド処理を行う（Ｓ３３２）。
【０１４０】
（６）コマンド（１００、１５０）の到来
コマンド（２０、６０）の実行中にコマンド（１００、１５０）が到来し、コマンド格納処理（図６３参照）を行う。２分木に他のコマンドが存在するため（Ｓ２０１のＮＯ）、到来したコマンドを根コマンド（３０、７０）と比較し、根コマンドの条件を満たす方を根コマンドとし、そうでない方を２分木の末尾に格納する。現在、基準位置は６０度であり、根コマンドの条件を満たすのはコマンド（１００、１５０）であるため（Ｓ２０４、Ｓ２０５、Ｓ２０６、Ｓ２０７のＮＯ、Ｓ２０８のＹＥＳ、Ｓ２０９のＮＯ）、図４７に示すように、コマンド（１００、１５０）を根の位置に格納し（Ｓ２１１）、さらにコマンド（３０、７０）を２分木の末尾に格納するためコマンド末尾格納処理（図６４参照）を行う（Ｓ２１２）。この処理では、図４８に示すように、コマンド（３０、７０）を２分木の末尾に格納するとともに（Ｓ２２１）、格納したコマンドを２分木の条件に合うようにするためソーティング処理（Ｓ２２２〜Ｓ２２６）を行う。ソーティング処理の結果、２分木は図４９のようになる。ソーティング処理におけるＳ２２６では、終了角度情報の更新（図６６参照）を行っている。
【０１４１】
（７）コマンド（２０、６０）の実行終了
実行中のコマンド（２０、６０）が終了すると、図５０に示すように、実行コマンド（２０、６０）をコマンドテーブルから削除し、候補コマンド（１００、１５０）の実行を開始する（実行コマンドとして選択する）。ただしこの時点では基準位置はまだ更新しないものとする。
【０１４２】
次に、実行コマンドとして選択されたコマンド（１００、１５０）を２分木から削除するためコマンド削除処理（図６７参照）を行う。すなわち、末尾のコマンド（４０、５０）を根の位置に入れ、２分木の条件を満たすようにソーティング処理（２分木のソート、終了角度情報の更新）を行う。この結果、２分木は図５１に示すようになる。
【０１４３】
次に、図５２に示すように基準位置を更新する。この結果、基準位置は、実行コマンド（１００、１５０）の終了角度である１５０度になる。次いで、２分木の更新処理（図７１参照）を行う。図５２に示されている２分木は更新処理後のものである。なおここでは２分木における各コマンドの総周回待ち数は加算されない。
【０１４４】
（８）優先コマンド（７０、９０）の到来
コマンド（１００、１５０）の実行中に、優先コマンド（７０、９０）が到来する。到来した優先コマンド（７０、９０）は、図５３に示すように、優先コマンドキューに格納される。優先コマンドが優先コマンドキューに格納されたら、候補コマンドの探索を行うため、図７２（Ａ）〜７２（Ｄ）および図７３のフローチャートに示す優先コマンド発生時候補コマンド探索処理を行う（Ｓ３４１〜Ｓ４０８）。この処理では、優先コマンドの実行を遅らせることなく優先コマンドの前に実行可能なコマンドが存在すればそのコマンドを候補コマンドとし、存在しなければ優先コマンドを候補コマンドとする。本例では、図５４に示すように、コマンド（４０、５０）が候補コマンドとして選択される。
【０１４５】
以下優先コマンド発生時候補コマンド探索処理について詳細に説明する。
【０１４６】
本処理では以下の２分木の２つの性質（［性質１］、［性質２］）を利用している。
［性質１］：基準位置から根コマンドに到達する際に生じる周回待ち数は、2分木に格納されている全てのコマンドの中で最小となる。
［性質２］：終了角度が最小のコマンドを２分木から削除することで、2番目に最小のコマンドを検索しやすくできる。
【０１４７】
（探索方法）
まず、根コマンドに関して調べる。基準位置から根コマンドまでの到達時間が優先コマンドに到達する時間の長さ以上の場合、優先コマンドの実行に影響を与えずに実行できるコマンドは無く、候補コマンドは優先コマンドとなる（図７２（Ａ）のＳ３４１〜Ｓ３４４、Ｓ３４５のＹＥＳ、Ｓ３４６）。根コマンドは2分木に格納されている全てのコマンドの中で一番早く到達できるコマンドであるため、それより早く到達できる優先コマンドが最も早く到達できるコマンドとなるためである。
【０１４８】
一方、根コマンドまでの到達時間が優先コマンドより短い場合（Ｓ３４５のNO）、優先コマンドに影響を与えずに実行できるコマンドが存在する可能性が有り、コマンドの探索を実行する必要がある（Ｓ３４７）。この際、基準位置から根コマンドまでに生じる周回待ち数b（Ｓ３４３で計算済み）を記憶しておく。bは［性質１］より、２分木における全コマンドの中で最小の周回待ち数であり、探索の終了を判定する際に利用される。
【０１４９】
コマンドの探索は［性質２］を利用して終了角度の小さい順に行う。根コマンドから最小終了角度方向を辿ることで2分木の中で基準位置から最も小さい終了角度のコマンドを見つけることができる（図７３のＳ３８２）。２番目に小さいコマンドを見つけるには、そのコマンドを一時的に2分木から外し、2分木を再構築する（Ｓ４０５およびＳ３９２において呼び出される図７２（Ｃ）のフローのＳ３６１、Ｓ３６２）。すなわち、探索（特定）されたコマンドが第１のコマンドでない場合、または探索されたコマンドが第１のコマンドであるもののその周回待ち数が根コマンドの周回待ち数と同じでない場合、探索されたコマンドを２分木からいったん除去し、２分木を更新する。そして再構築された2分木の根コマンドから最小終了角度方向を辿ることにより、２番目に小さい終了角度のコマンドを見つけることができる（図７２（Ｃ）のＳ３６３）。以下同様にして、終了角度が小さい順にコマンドを探索できる。探索が終了したら（候補コマンドが決定したら）、２分木から一時的に外されたコマンドを2分木に加え最初の状態に戻す（図７２（Ｄ）のＳ３７１〜Ｓ３７３）。
【０１５０】
（探索中の処理）
＜１＞探索中のコマンドmが優先コマンドに影響を与えることなく実行可能であるか調べる。優先コマンドに影響を与えずに実行でき（図７３におけるＳ３８４のＮＯ）、かつ、以下の［条件１］および［条件２］のいずれかを満たす場合、候補コマンドは決定し、探索を終了できる。
【０１５１】
［条件１］：基準位置からアクセスした際に生じる周回待ち数がｂであるとき
bは周回待ち数の最小値であり、終了角度の小さい順にコマンドを探索しているため、残りのコマンドのうちコマンドmより早く実行終了可能なコマンドは無い。よって、コマンドmが候補コマンドとなり探索を終了できる（Ｓ３８３、Ｓ３８４のＮＯ、Ｓ４００のＹＥＳ、Ｓ４０７、Ｓ４０８）。
【０１５２】
［条件２］：コマンドの格納位置が2分木の根であるとき
2分木に格納されているコマンドのうち、最も早くコマンド実行開始可能であるのが根コマンドである。また、終了角度の小さい順にコマンドを探索しているため、根コマンドが最も早くコマンドの実行終了可能なコマンドとなる。ゆえに、2分木におけるコマンドの中で最も候補コマンドの条件（優先コマンドの実行に影響を与えずに最も早く実行終了可能なコマンド）を満たしているのが根コマンドとなる。既に、候補の候補となるコマンド（準候補コマンドと呼ぶことにする）が存在した場合、準候補コマンドとコマンドmを比べ、より適した方を候補コマンドとして探索を終了する（Ｓ４０１、Ｓ４０２、Ｓ４０３、Ｓ４０４のＹＥＳ、Ｓ４０６）。すなわち、探索部は、２分木の根に配置された第１のコマンドを見つけたら探索を終了し、コマンド変更部は、探索部により見つけられた全ての第１のコマンドのうち、最も周回待ち数が少なくかつ実行中のコマンドの終了角度を基準として最も小さい終了角度をもつ第１のコマンドを候補コマンドとして決定する。
【０１５３】
優先コマンドに影響を与えずに実行できる探索中のコマンドｍが上記2つの条件のいずれか一方を満たしていない場合は、残されたコマンドの中に、より候補コマンドに適したコマンドが存在する可能性が有る。ゆえに探索を続行しなくてはならない（Ｓ４０４のＮＯ→Ｓ４０５→Ｓ３８３）。コマンドmは準候補コマンドとし記憶する。既に準候補コマンドが存在する場合は、コマンドmと比較し、より適したコマンドを準候補コマンドとする。
【０１５４】
＜２＞探索中のコマンドmが、優先コマンドの実行に影響を与える場合（図７３におけるＳ３８４のＹＥＳ）、以下の［条件３］および［条件４］のいずれかを満たせば、探索は終了となる。以下の条件のいずれか一方も満たさない場合は、探索を続ける（Ｓ３８６のＮＯ→Ｓ３９２→Ｓ３８３、Ｓ３８８のＮＯ→Ｓ３９２→Ｓ３８３）。
【０１５５】
［条件３］：コマンドmが根コマンドで、基準位置からコマンドmまでの到達時間が優先コマンドに到達する時間以上であるとき（Ｓ３８４のＹＥＳ、Ｓ３８５のＮＯ、Ｓ３８６のＹＥＳ、Ｓ３８７、Ｓ３８８のＹＥＳ）
コマンドmは2分木に格納されているコマンドの中で、基準位置から一番早くアクセスできるコマンドであり、2分木に格納されている残りのどのコマンドも優先コマンドより早くアクセスできないことが分かる。ゆえに、残りのコマンドに候補となり得るコマンドは存在せず、この時点で探索を終了できる。準候補コマンドが存在すれば、そのコマンドが候補コマンドとなり（Ｓ３８９のＹＥＳ）、そうでなければ優先コマンドが候補となる（Ｓ３８９のＮＯ、Ｓ３９０）。
【０１５６】
［条件４］：2分木に格納されているコマンドが１つのとき（Ｓ３８５のＹＥＳ）
全てのコマンドを辿り終えたため、探索は終了となる。準候補コマンドが存在すれば、そのコマンドが候補コマンドとなり（Ｓ３８９のＹＥＳ）、そうでなければ優先コマンドが候補となる（Ｓ３８９のＮＯ、Ｓ３９０）。
【０１５７】
（９）コマンド（１００、１５０）の実行終了
図５４においてコマンド（１００、１５０）の実行が終了したら、図５５に示すように、候補コマンドであるコマンド（４０、５０）の実行を開始する（実行コマンドとして選択する）。
【０１５８】
次に、実行コマンドとして選択されたコマンド（４０、５０）を２分木から削除するためコマンド削除処理（図６７参照）を行う（Ｓ２７３のＮＯ、Ｓ２７８のＹＥＳ）。この結果、２分木は図５６に示すようになる。この段階では候補ポインタは更新されない。なお、コマンド削除処理において、もし削除されたコマンドの位置に入れられたコマンド（末尾のコマンドｚ）の開始角度が親コマンドの開始角度以下であれば（２７８のＮＯ）、図６８のフローチャートに示す親との比較＆入れ替え処理（Ｓ２７９）、および図６６の終了角度情報更新処理（Ｓ２８０）を行う。親との比較＆入れ替え処理では、対象となるコマンド（コマンドＡ）とその親コマンドを比較し、２分木の条件を満たすまでコマンドＡと親コマンドの入れ替えを行う。
【０１５９】
次に、基準位置を更新し、この結果、基準位置は、実行コマンド（４０、５０）の終了角度である５０度になる。続いて、２分木の更新処理（図７１参照）を行う。この結果、２分木は図５７のようになり、コマンド（３０、７０）の総周回待ち数は２になる。取り残しコマンド検出のための総周回待ち数の閾値を２に設定しているとすると、図５７に示すように、コマンド（３０、７０）は優先コマンドとして扱われ、優先コマンドキューに格納される。
【０１６０】
次に、優先コマンドキューに格納したコマンド（３０、７０）を２分木から削除するためコマンド削除処理（図６７参照）を行う。この結果、２分木は図５８のようになる。なお、候補ポインタの更新はまだ行われない。
【０１６１】
次に、候補コマンドの探索を行うため（候補ポインタの付け替えを行うため）、図７２および図７３のフローチャートに示す優先コマンド発生時候補コマンド探索処理を行う。コマンド（６０、８０）を実行すると、優先コマンド（７０、９０）へのシークが間に合わなくなるため（図７２におけるＳ３４５のＹＥＳ）、図５９に示すように、最も古い優先コマンド（７０、９０）が候補コマンドとされる。
【０１６２】
（１０）コマンド（４０、５０）の実行終了
コマンド（４０、５０）の実行が終了したら、図６０に示すように、候補コマンドであるコマンド（７０、９０）を優先コマンドキューから取り出し、実行を開始する（実行コマンドとして選択する）。そして、優先コマンドキュー内のコマンドを先頭側へ詰める。
【０１６３】
次に、基準位置を更新し、この結果、基準位置は、実行コマンド（７０、９０）の終了角度である９０度になる。続いて、２分木の更新処理（図７１参照）を行う。この結果、２分木は図６１のようになり、コマンド（６０、８０）の総周回待ち数は２になる。総周回待ち数の閾値は２であるため、コマンド（６０、８０）は優先コマンドとなり、図６２に示すように、コマンド（６０、８０）は優先コマンドキューに格納される。これにより２分木は存在しなくなったため、新たにコマンドが到来しない限り、優先コマンドキュー内のコマンドが古いものから順番に、すなわち、コマンド（３０、７０）、コマンド（６０、８０）の順に実行される。仮に新たなコマンドが到来した場合は、図７４のフローチャートに示す優先コマンド存在時候補コマンド探索処理によって候補コマンドを決定する（Ｓ４１１〜Ｓ４２７）。本処理の基本的な考え方は前述の優先コマンド発生時コマンド探索処理と同じであり、要するに、新たに到来したコマンドが優先コマンド（３０、７０）の実行に影響を与えることなく実行可能であれば、この新たに到来したコマンドを候補コマンドとして選択し、そうでなければ優先コマンド（３０、７０）をそのまま候補コマンドとする。
【０１６４】
以上のように本発明の第１および第２の本実施の形態によれば、コマンドの実行中に、次に実行するべきコマンドを候補コマンドとして選択しておき、実行中のコマンドが終了したら、この選択しておいた候補コマンドを即座に実行すればよいため、コマンドの処理効率を高めることができる。すなわちコマンドの実行終了後、次のコマンドの実行開始までの時間を著しく短くすることができる。
【０１６５】
また、優先コマンドが発生した場合に、優先コマンドの実行に影響を与えずに実行可能なコマンド（第１のコマンド）を、基準位置に対して終了角度の小さいコマンドから順に探索し、最初に探索された最も周回待ち数の少ない（例えば現在の候補コマンドと同じ周回待ち数の）コマンドを次に実行するべきコマンドとして選択するようにしたことにより、優先コマンドの実行前に、可能な限り多くのコマンドを実行することができる。これによってコマンドの処理効率を高めることができる。また、終了角度の小さいコマンドから順に探索する際、あらかじめ作成しておいた終了リンクリストまたは２分木を辿ればよいため、探索時間を短くできる。
【０１６６】
また、コマンドテーブルに格納されている各コマンドの総周回待ち数を計算することによって取り残しコマンドを検出し、検出した取り残しコマンドを優先コマンドとして扱うようにしたため、長時間にわたりコマンドテーブルに取り残しコマンドが滞在することを防ぐことができる。
【図面の簡単な説明】
【０１６７】
【図１】本発明の一実施の形態にしたがったコマンド管理装置を搭載したデータ記憶装置の構成を示すブロック図
【図２】コマンドテーブル５の一例を示す図
【図３】開始角度および終了角度を説明する図
【図４】ディスク装置４の構造の一例を示す平面図
【図５】ディスク装置４の構造の一例を示す斜示図
【図６】リオーダリングを説明する図
【図７】STFアルゴリズムを説明する図
【図８】優先コマンドおよび優先コマンド候補の管理を説明する図
【図９】ＨＤＤに到来するコマンドのディスク上での位置を示す図
【図１０】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１１】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１２】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１３】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１４】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１５】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１６】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１７】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１８】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図１９】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図２０】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図２１】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図２２】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図２３】第１の実施の形態にかかる開始角度リンクリストおよび終了角度リンクリストの一状態を示す図
【図２４】第１の実施の形態にかかるコマンド格納処理の流れを示すフローチャート
【図２５】第１の実施の形態にかかる開始角度リンク追加処理の流れを示すフローチャート
【図２６】第１の実施の形態にかかるテーブル更新処理の流れを示すフローチャート
【図２７】第１の実施の形態にかかる基準コマンド探索処理の流れを示すフローチャート
【図２８】第１の実施の形態にかかる候補コマンド探索処理の流れを示すフローチャート
【図２９】第１の実施の形態にかかるコマンド削除処理の流れを示すフローチャート
【図３０】第１の実施の形態にかかる開始角度リンク削除処理の流れを示すフローチャート
【図３１】第１の実施の形態にかかる取り残しコマンド検出処理の流れを示すフローチャート
【図３２】第１の実施の形態にかかる実行可能コマンド探索処理の流れを示すフローチャート
【図３３】ヒープを説明する図
【図３４】根コマンド、葉コマンド、末尾コマンドの例を示す図
【図３５】親コマンド、子コマンド、左子コマンド、右子コマンドの例を示す図
【図３６】先祖コマンドおよび子孫コマンドの例を示す図
【図３７】２分木の一例を示す図
【図３８】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図３９】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４０】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４１】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４２】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４３】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４４】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４５】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４６】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４７】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４８】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図４９】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５０】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５１】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５２】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５３】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５４】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５５】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５６】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５７】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５８】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図５９】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図６０】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図６１】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図６２】第２の実施の形態にかかる２分木、優先コマンドキュー、実行コマンドの一状態を示す図
【図６３】第２の実施の形態にかかるコマンド格納処理の流れを示すフローチャート
【図６４】第２の実施の形態にかかるコマンド末尾格納処理の流れを示すフローチャート
【図６５】第２の実施の形態にかかる子との終了角度更新処理の流れを示すフローチャート
【図６６】第２の実施の形態にかかる先祖との終了角度更新処理の流れを示すフローチャート
【図６７】第２の実施の形態にかかるコマンド削除処理の流れを示すフローチャート
【図６８】第２の実施の形態にかかる親との比較＆入れ替え処理の流れを示すフローチャート
【図６９】第２の実施の形態にかかる子との比較＆入れ替え処理の流れを示すフローチャート
【図７０】第２の実施の形態にかかる子同士の比較＆入れ替え処理の流れを示すフローチャート
【図７１】第２の実施の形態にかかる２分木の更新処理の流れを示すフローチャート
【図７２】第２の実施の形態にかかる優先コマンド発生時候補コマンド探索処理の流れを示すフローチャート
【図７３】第２の実施の形態にかかる優先コマンド発生時候補コマンド探索処理の流れを示すフローチャート
【図７４】第２の実施の形態にかかる優先コマンド存在時候補コマンド探索処理の流れを示すフローチャート
【図７５】データ面サーボ方式を説明する図
【図７６】セクタ・サーボ方式を説明する図
【符号の説明】
【０１６８】
１：ホスト
２：ハードディスクドライブ（ＨＤＤ）
３：制御部（コマンド管理装置）
４：ディスク装置
５：コマンドテーブル
６：テーブル管理部
７：角度計算部（開始角度計算部および終了角度計算部）
８：コマンド実行要求部
９：ディスクヘッド位置検出部
１６：基準線（基準となる半径線）
１７：開始角度
１８：終了角度
ＳＴ：アクセス開始位置
ＥＤ：アクセス終了位置
【図１】
2008071404.tif 000003
【図２】
2008071404.tif 000004
【図３】
2008071404.tif 000005
【図４】
2008071404.tif 000006
【図５】
2008071404.tif 000007
【図６】
2008071404.tif 000008
【図７】
2008071404.tif 000009
【図８】
2008071404.tif 000010
【図９】
2008071404.tif 000011
【図１０】
2008071404.tif 000012
【図１１】
2008071404.tif 000013
【図１２】
2008071404.tif 000014
【図１３】
2008071404.tif 000015
【図１４】
2008071404.tif 000016
【図１５】
2008071404.tif 000017
【図１６】
2008071404.tif 000018
【図１７】
2008071404.tif 000019
【図１８】
2008071404.tif 000020
【図１９】
2008071404.tif 000021
【図２０】
2008071404.tif 000022
【図２１】
2008071404.tif 000023
【図２２】
2008071404.tif 000024
【図２３】
2008071404.tif 000025
【図２４】
2008071404.tif 000026
【図２５】
2008071404.tif 000027
【図２６】
2008071404.tif 000028
【図２７】
2008071404.tif 000029
【図２８】
2008071404.tif 000030
【図２９】
2008071404.tif 000031
【図３０】
2008071404.tif 000032
【図３１】
2008071404.tif 000033
【図３２】
2008071404.tif 000034
【図３３】
2008071404.tif 000035
【図３４】
2008071404.tif 000036
【図３５】
2008071404.tif 000037
【図３６】
2008071404.tif 000038
【図３７】
2008071404.tif 000039
【図３８】
2008071404.tif 000040
【図３９】
2008071404.tif 000041
【図４０】
2008071404.tif 000042
【図４１】
2008071404.tif 000043
【図４２】
2008071404.tif 000044
【図４３】
2008071404.tif 000045
【図４４】
2008071404.tif 000046
【図４５】
2008071404.tif 000047
【図４６】
2008071404.tif 000048
【図４７】
2008071404.tif 000049
【図４８】
2008071404.tif 000050
【図４９】
2008071404.tif 000051
【図５０】
2008071404.tif 000052
【図５１】
2008071404.tif 000053
【図５２】
2008071404.tif 000054
【図５３】
2008071404.tif 000055
【図５４】
2008071404.tif 000056
【図５５】
2008071404.tif 000057
【図５６】
2008071404.tif 000058
【図５７】
2008071404.tif 000059
【図５８】
2008071404.tif 000060
【図５９】
2008071404.tif 000061
【図６０】
2008071404.tif 000062
【図６１】
2008071404.tif 000063
【図６２】
2008071404.tif 000064
【図６３】
2008071404.tif 000065
【図６４】
2008071404.tif 000066
【図６５】
2008071404.tif 000067
【図６６】
2008071404.tif 000068
【図６７】
2008071404.tif 000069
【図６８】
2008071404.tif 000070
【図６９】
2008071404.tif 000071
【図７０】
2008071404.tif 000072
【図７１】
2008071404.tif 000073
【図７２】
2008071404.tif 000074
【図７３】
2008071404.tif 000075
【図７４】
2008071404.tif 000076
【図７５】
2008071404.tif 000077
【図７６】
2008071404.tif 000078