Operating-system-os-process-scheduling-algorithms

オペレーティングシステムスケジューリングアルゴリズム

プロセススケジューラは、特定のスケジューリングアルゴリズムに基づいてCPUに割り当てられるさまざまなプロセスをスケジュールします。 この章では、6つの一般的なプロセススケジューリングアルゴリズムについて説明します。

• 先着順（FCFS）スケジューリング
• Shortest-Job-Next（SJN）スケジューリング
• 優先度スケジューリング
• 最短残り時間
• ラウンドロビン（RR）スケジューリング
• 複数レベルのキュースケジューリング

これらのアルゴリズムは、*非プリエンプティブまたはプリエンプティブ*です。 非プリエンプティブアルゴリズムは、一度プロセスが実行状態になると、割り当てられた時間を完了するまで先取りできないように設計されています。プロセスは準備完了状態になります。

先着順（FCFS）

• ジョブは先着順に実行されます。
• これは、プリエンプティブではないプリエンプティブなスケジューリングアルゴリズムです。
• 簡単に理解して実装できます。
• その実装は、FIFOキューに基づいています。
• 平均待機時間が長いため、パフォーマンスが低下します。

先着順スケジューリングアルゴリズム

• 各プロセスの待機時間*は次のとおりです-

Process	Wait Time : Service Time - Arrival 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）

• これは、最短ジョブ優先、またはSJFとも呼ばれます
• これは、プリエンプティブではないプリエンプティブなスケジューリングアルゴリズムです。
• 待ち時間を最小限に抑えるための最良のアプローチ。
• 必要なCPU時間が事前にわかっているバッチシステムに簡単に実装できます。
• 必要なCPU時間が不明な対話型システムに実装することはできません。
• 処理者は、処理にかかる時間を事前に知る必要があります。

指定：プロセスの表、およびその到着時間、実行時間

Process	Arrival Time	Execution Time	Service Time
P0	0	5	0
P1	1	3	5
P2	2	8	14
P3	3	6	8

最短ジョブファーストスケジューリングアルゴリズム

• 各プロセスの*待機時間*は次のとおりです-

Process	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が最も低い優先度であると考えています。

Process	Arrival Time	Execution Time	Priority	Service Time
P0	0	5	1	0
P1	1	3	2	11
P2	2	8	1	14
P3	3	6	3	5

優先度スケジューリングアルゴリズム

• 各プロセスの*待機時間*は次のとおりです-

Process	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時間が不明な対話型システムに実装することはできません。
• 短いジョブが優先される必要があるバッチ環境でよく使用されます。

ラウンドロビンスケジューリング

• ラウンドロビンは、プリエンプティブプロセススケジューリングアルゴリズムです。
• 各プロセスには、実行するための修正時間が提供され、*量子*と呼ばれます。
• プロセスが特定の期間実行されると、そのプロセスは横取りされ、他のプロセスは特定の期間実行されます。
• コンテキスト切り替えは、横取りされたプロセスの状態を保存するために使用されます。

ラウンドロビンスケジューリングアルゴリズム

• 各プロセスの待機時間*は次のとおりです-

Process	Wait Time : Service Time - Arrival 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に割り当てます。