ディスクスケジューリングアルゴリズムとは何ですか?-よくある問題-php.cn

ディスクスケジューリングアルゴリズムには次のものが含まれます: 1. 先着順アルゴリズム、プロセスがディスクへのアクセスを要求した順序に従ってスケジューリングが実行されます; 2. 最短検索時間優先アルゴリズム、スケジューリング用に選択されたトラック現在のヘッドが配置されているトラックからの距離毎回の検索時間を最小限に抑えるための最も近いトラック; 3. スキャンアルゴリズム; 4. ループスキャンアルゴリズム。

ディスクスケジューリングアルゴリズムとは何ですか?

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

ディスクスケジューリングマルチプログラムされたコンピュータシステムでは、各プロセスがディスク上の読み取り/書き込み操作に対して異なる要求を継続的に行うことがあります。これらのプロセスは、ディスクの応答よりも早くリクエストを送信する場合があるため、ディスクデバイスごとに待機キューを作成する必要があります。

一般的に使用されるディスクスケジューリングアルゴリズムは 4 つあります。

先着順アルゴリズム (FCFS)
最短シークトラック時間優先アルゴリズム (SSTF)
スキャンアルゴリズム (SCAN)
サイクリックスキャンアルゴリズム (CSCAN)

##先着順アルゴリズム

FCFS アルゴリズムは、プロセスがディスクへのアクセスを要求した順序に従ってスケジュールを設定します。これは最も単純なスケジューリングアルゴリズムです。このアルゴリズムの利点はその公平性です。アクセスが必要なプロセスが少数で、ほとんどのリクエストがクラスター化されたファイルセクターにアクセスする場合は、良好なパフォーマンスが期待されますが、ディスクの使用を競合するプロセスが多数ある場合、このアルゴリズムのパフォーマンスはランダムスケジューリングに近いことがよくあります。したがって、実際のディスクスケジューリングでは、より複雑なスケジューリングアルゴリズムが考慮されます。

1. アルゴリズムの考え方: アクセス要求を到着順に処理します。

2. 利点: シンプルかつ公平です。

3. 短所: 効率は高くありません。2 つの隣接するリクエストにより、シリンダの最内周から最外周へのシークが発生し、磁気ヘッドが繰り返し移動するため、サービス時間が長くなり、サービスにとって良くありません。機械。

最短探索時間優先アルゴリズム

SSTF アルゴリズムは、現在のヘッドが位置するトラックに最も近いスケジューリング処理用のトラックを選択します。毎回最短です。もちろん、常に最小検索時間を選択しても、最小平均検索時間が保証されるわけではありませんが、FCFS アルゴリズムよりも優れたパフォーマンスを提供できます。このアルゴリズムは「飢餓」現象を引き起こします。

1. アルゴリズムのアイデア: 主にシーク優先度を考慮して、サービスの現在のヘッドに最も近いアクセス要求を優先します。

2. 利点: 平均ディスクサービス時間の向上。

3. 欠点: 一部のアクセス要求は長時間待機し、処理されません。

スキャンアルゴリズム (エレベーターアルゴリズムとも呼ばれる)

SCAN アルゴリズムは、現在のヘッドが位置するトラックの現在の移動方向に最も近いリクエストを選択します。次のサービスオブジェクトとしてのヘッド。頭部の移動パターンがエレベータに似ているため、エレベータスケジューリングアルゴリズムとも呼ばれます。 SCAN アルゴリズムは、最近スキャンされた領域に対して公平ではないため、アクセスの局所性の点では FCFS アルゴリズムや SSTF アルゴリズムほど優れていません。

1. アルゴリズムの考え方: デバイスにアクセス要求がない場合、磁気ヘッドは移動しません。アクセス要求がある場合、磁気ヘッドは一方向に移動し、移動中に発生したアクセス要求に対応します。 [2] 次に、この方向にまだアクセス要求があるかどうかを判断し、存在する場合はスキャンを続行し、そうでない場合は移動方向を変更して、通過するアクセス要求に対応する、というように続きます。

2. 利点: 距離と方向の両方を考慮して、最短シークを優先する欠点を克服します。

サイクリックスキャンアルゴリズム

スキャンアルゴリズムに基づいて、磁気ヘッドはサービスを提供するために一方向に移動することが規定されており、戻るときは磁気ヘッドが直接移動します。リクエストを処理せずにすぐに開始し、終了します。 SCAN アルゴリズムは最も内側または最も外側のトラックに近いアクセス要求を処理することを好むため、この問題を回避するために改良された C-SCAN アルゴリズムが使用されます。

SCAN アルゴリズムと C-SCAN アルゴリズムを使用すると、磁気ヘッドは常にディスクの一端から他端までの動きに厳密に追従しますが、実際の使用では明らかに改善できます。磁気ヘッドの移動は最端まで到達するだけでよく、ディスクのエンドポイントに到達することなく単一のリクエストを返すことができます。この形式の SCAN アルゴリズムおよび C-SCAN アルゴリズムは、LOOK および C-LOOK スケジューリングと呼ばれます。これは、特定の方向に進む前に、要求があるかどうかを確認するためです。特に指定しない限り、SCAN アルゴリズムと C-SCAN アルゴリズムは、デフォルトで LOOK および C-LOOK としてスケジュールすることもできることに注意してください。