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

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

青灯夜游
青灯夜游オリジナル
2021-04-16 14:45:3815177ブラウズ

ディスク スケジューリング アルゴリズムには次のものが含まれます: 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 としてスケジュールすることもできることに注意してください。

関連知識の詳細については、

FAQ 列をご覧ください。

以上がディスク スケジューリング アルゴリズムとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。