オペレーティングシステムのスケジューリングアルゴリズム
プロセススケジューラは、特定のスケジューリングアルゴリズムに基づいて、CPUに割り当てられるさまざまなプロセスをスケジュールします。この章で説明する6つの一般的なプロセススケジューリングアルゴリズムがあります-
- 先入れ先出し(FCFS)スケジューリング
- Shortest-Job-Next(SJN)スケジューリング
- 優先スケジューリング
- 最小残余時間
- ラウンドロビン(RR)スケジューリング
- 複数レベルのキューのスケジューリング
これらのアルゴリズムはどちらかです non-preemptive or preemptive。非プリエンプティブアルゴリズムは、プロセスが実行状態に入ると、割り当てられた時間が完了するまでプリエンプションできないように設計されていますが、プリエンプティブスケジューリングは優先度に基づいており、スケジューラーは優先度の高いときにいつでも優先度の低い実行中のプロセスをプリエンプションできますプロセスは準備完了状態になります。
先入れ先出し(FCFS)
- ジョブは先着順で実行されます。
- これは、非プリエンプティブ、プリエンプティブスケジューリングアルゴリズムです。
- 理解と実装が簡単です。
- その実装はFIFOキューに基づいています。
- 平均待機時間が長いため、パフォーマンスが低下します。
Wait time 各プロセスの概要は次のとおりです-
処理する | 待ち時間:サービス時間-到着時間 |
---|---|
P0 | 0-0 = 0 |
P1 | 5-1 = 4 |
P2 | 8-2 = 6 |
P3 | 16-3 = 13 |
平均待機時間:(0 + 4 + 6 + 13)/ 4 = 5.75
次の最短ジョブ(SJN)
これは、 shortest job first、またはSJF
これは、非プリエンプティブ、プリエンプティブスケジューリングアルゴリズムです。
待ち時間を最小限に抑えるための最良のアプローチ。
必要なCPU時間が事前にわかっているバッチシステムで簡単に実装できます。
必要なCPU時間が不明なインタラクティブシステムに実装することはできません。
処理者は、処理にかかる時間を事前に知っておく必要があります。
与えられた:プロセスの表、およびそれらの到着時間、実行時間
処理する | 到着時刻 | 実行時間 | サービス時間 |
---|---|---|---|
P0 | 0 | 5 | 0 |
P1 | 1 | 3 | 5 |
P2 | 2 | 8 | 14 |
P3 | 3 | 6 | 8 |
Waiting time 各プロセスの概要は次のとおりです-
処理する | 待ち時間 |
---|---|
P0 | 0-0 = 0 |
P1 | 5-1 = 4 |
P2 | 14-2 = 12 |
P3 | 8-3 = 5 |
平均待機時間:(0 + 4 + 12 + 5)/ 4 = 21/4 = 5.25
優先度ベースのスケジューリング
優先度スケジューリングは、非プリエンプティブアルゴリズムであり、バッチシステムで最も一般的なスケジューリングアルゴリズムの1つです。
各プロセスには優先順位が割り当てられます。優先度の最も高いプロセスが最初に実行されます。
同じ優先度のプロセスは先着順で実行されます。
優先順位は、メモリ要件、時間要件、またはその他のリソース要件に基づいて決定できます。
与えられたもの:プロセスの表、およびそれらの到着時間、実行時間、および優先度。ここでは、1が最低の優先順位であると考えています。
処理する | 到着時刻 | 実行時間 | 優先 | サービス時間 |
---|---|---|---|---|
P0 | 0 | 5 | 1 | 0 |
P1 | 1 | 3 | 2 | 11 |
P2 | 2 | 8 | 1 | 14 |
P3 | 3 | 6 | 3 | 5 |
Waiting time 各プロセスの概要は次のとおりです-
処理する | 待ち時間 |
---|---|
P0 | 0-0 = 0 |
P1 | 11-1 = 10 |
P2 | 14-2 = 12 |
P3 | 5-3 = 2 |
平均待機時間:(0 + 10 + 12 + 2)/ 4 = 24/4 = 6
最小残余時間
最小残余時間(SRT)は、SJNアルゴリズムのプリエンプティブバージョンです。
プロセッサは、完了に最も近いジョブに割り当てられますが、完了までの時間が短い新しい準備完了ジョブによってプリエンプトされる可能性があります。
必要なCPU時間が不明なインタラクティブシステムに実装することはできません。
これは、短いジョブを優先する必要があるバッチ環境でよく使用されます。
ラウンドロビンスケジューリング
ラウンドロビンは、プリエンプティブプロセススケジューリングアルゴリズムです。
各プロセスには、実行するための修正時間が提供されます。これは、 quantum。
プロセスが指定された期間実行されると、そのプロセスはプリエンプトされ、他のプロセスは指定された期間実行されます。
コンテキストスイッチングは、プリエンプトされたプロセスの状態を保存するために使用されます。
Wait time 各プロセスの概要は次のとおりです-
処理する | 待ち時間:サービス時間-到着時間 |
---|---|
P0 | (0-0)+(12-3)= 9 |
P1 | (3-1)= 2 |
P2 | (6-2)+(14-9)+(20-17)= 12 |
P3 | (9-3)+(17-12)= 11 |
平均待機時間:(9 + 2 + 12 + 11)/ 4 = 8.5
複数レベルのキューのスケジューリング
マルチレベルキューは、独立したスケジューリングアルゴリズムではありません。それらは、他の既存のアルゴリズムを利用して、共通の特性を持つジョブをグループ化およびスケジュールします。
- 共通の特性を持つプロセスに対して、複数のキューが維持されます。
- 各キューは、独自のスケジューリングアルゴリズムを持つことができます。
- 優先順位は各キューに割り当てられます。
たとえば、CPUバウンドジョブを1つのキューでスケジュールし、すべてのI / Oバウンドジョブを別のキューでスケジュールできます。次に、プロセススケジューラは、各キューからジョブを交互に選択し、キューに割り当てられたアルゴリズムに基づいてそれらをCPUに割り当てます。