最短シークタイムファーストアルゴリズム(SSTF)
Shortest Seek Time First Algorithm
記事のディレクトリ
ディスクアクセスシーケンス:98、183、37、122、14、124、65、67を想定します。読み取り/書き込みヘッドの開始位置:53。要件:ヘッドサービスシーケンスとヘッド移動の間の合計距離(数値トラックの)。
質問の意味と先入れ先出しアルゴリズムのアイデアから、下図に示す頭の動きの軌跡が得られます。したがって:
ヘッドサービスシーケンスは、98、183、37、122、14、124、65、67です。
頭の動きの合計距離=(98-53)+(183-98)+ | 37-183 | +(122-37)+ | 14-122 | +(124-14)+ | 65-124 | +(67- 65)= 640(トラック)
SSTFアルゴリズムは、現在のヘッドが配置されているトラックに最も近いトラックとしてスケジューリング処理のトラックを選択するため、検索時間は毎回最短になります。もちろん、常に最小検索時間を選択しても、最小平均検索時間が保証されるわけではありませんが、FCFSアルゴリズムよりも優れたパフォーマンスを提供できます。この種のアルゴリズムは「空腹」現象を引き起こします。
単純に考えてください:
あなたはそのようなシーケンスを想像することができます、頭は現在真ん中にあります。
- 最初のシークでは、頭に最も近いトラックが中点の左側にあり、頭がこの位置に移動します。
- 2回目のシークでは、頭に最も近いトラックが中点の右側にあり、頭がこの位置に移動します。
- 3回目のシークでは、頭に最も近いトラックが中点の左側にあり、頭がこの位置に移動します。
- ..。
このように、磁気ヘッドは中間点で往復運動を続けます。これは、一方の側でトラックを検索してからもう一方の側で検索するよりも明らかに優れています。