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

ディスク スケジューリング アルゴリズムには次のものが含まれます: 1. 先着順アルゴリズム、プロセスがディスクへのアクセスを要求した順序に従ってスケジューリングが実行されます; 2. 最短検索時間優先アルゴリズム、スケジューリング用に選択されたトラック現在のヘッドが位置するトラックからの距離 各検索時間を最小化する最も近いトラック 3. スキャン アルゴリズムでは、磁気ヘッドの現在の移動方向で現在のヘッドが位置するトラックに最も近いリクエストを選択します。次のサービス オブジェクト; 4. ループ スキャン アルゴリズム、スキャン アルゴリズム内 サービスを提供するために磁気ヘッドが一方向に移動するという規定に基づいて、戻るときは、要求を処理せずに開始端にすぐに直接移動します。

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

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

一般的に使用されるディスク スケジューリング アルゴリズム

先着順アルゴリズム

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

• アルゴリズムのアイデア: アクセス要求を到着順に処理します。

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

• 短所: 効率は高くありません。2 つの隣接するリクエストにより、シリンダーが最も内側から最も外側にシークされ、ヘッドが繰り返し移動することになり、サービス時間が増加し、影響を受ける可能性があります。マシンが不利です。

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

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

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

• 利点: ディスクの平均サービス時間が改善されました。

• 欠点: 一部のアクセス要求は、待ち時間が長いために処理されない可能性があります。

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

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

アルゴリズムのアイデア: デバイスにアクセス要求がない場合、磁気ヘッドは移動しません。アクセス要求がある場合、磁気ヘッドは一方向に移動し、移動中に発生するアクセス要求に対応します [2] 、その後、この方向にまだアクセス要求があるかどうかを判断し、存在する場合はスキャンを続行します。そうでない場合は、移動方向を変更して、アクセス要求の受け渡しを処理します。以下の図に示すように:

スキャニング アルゴリズム (エレベーター アルゴリズム) のヘッド移動軌跡

• 利点:最短シーク優先 この方法の欠点は、距離と方向の両方を考慮することです。

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

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

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

#補足: 各種アルゴリズムの比較

#いいえ、ディスク ヘッドの端から遠く離れたリクエストにアクセスするのに役立ちますC-SCAN アルゴリズム両端でのトラック リクエストの不一致を排除します。 公正です。--関連する詳細な知識については、

	#利点	欠点
FCFSアルゴリズム	公平かつシンプル	平均シーク距離は長いため、ディスク I/O が少ない状況でのみ使用してください。
SSTF アルゴリズム	パフォーマンスは「先着順」よりも優れています	##平均シーク時間の最短化は保証​​できず、「飢餓」が発生する可能性があります
SCAN アルゴリズム	シークのパフォーマンスが向上し、「飢餓」現象を回避できます

FAQ

列をご覧ください。

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