CPU スケジューリング Algorithms in Operaティングシステムズ

CPU スケジューリングの種類

XNUMX 種類のスケジュール方法を次に示します。

プリエンプティブ スケジューリング

プリエンプティブ スケジューリングでは、ほとんどのタスクには優先順位が割り当てられます。 場合によっては、たとえ優先度の低いタスクがまだ実行中であっても、優先度の高いタスクを別の優先度の低いタスクの前に実行することが重要である場合があります。 優先度の低いタスクはしばらく保持され、優先度の高いタスクの実行が終了すると再開されます。

ノンプリエンプティブなスケジューリング

このタイプのスケジューリング方法では、CPU が特定のプロセスに割り当てられます。 CPU をビジー状態に保つプロセスは、コンテキストを切り替えるか終了することによって CPU を解放します。 これは、さまざまなハードウェア プラットフォームで使用できる唯一の方法です。 それは、プリエンプティブ スケジューリングのような特別なハードウェア (タイマーなど) が必要ないためです。

スケジューリングがプリエンプティブまたは非プリエンプティブの場合は?

スケジューリングがプリエンプティブであるか非プリエンプティブであるかを判断するには、次の XNUMX つのパラメーターを考慮してください。

1. プロセスは実行状態から待機状態に切り替わります。
2. 特定のプロセスが実行状態から準備完了状態に切り替わります。
3. 特定のプロセスが待機状態から準備完了状態に切り替わります。
4. プロセスは実行を終了し、終了しました。

条件 1 と 4 のみが適用され、スケジューリングは非プリエンプティブと呼ばれます。

他のすべてのスケジュールはプリエンプティブです。

CPU スケジューリングに関する重要な用語

• バースト時間/実行時間: プロセスが実行を完了するまでに必要な時間です。 実行時間とも言います。
• 到着時刻： プロセスが準備完了状態になったとき
• 終了時刻： プロセスが完了してシステムを終了したとき
• マルチプログラミング: メモリ内に同時に存在できる多数のプログラム。
• 仕事： これは、ユーザーとの対話をまったく必要としないタイプのプログラムです。
• ユーザー： ユーザーとの対話を伴うプログラムの一種です。
• プロセス： ジョブとユーザーの両方に使用される参照です。
• CPU/IOバーストサイクル: CPU アクティビティと I/O アクティビティを交互に繰り返すプロセス実行の特徴を示します。 通常、CPU 時間は I/O 時間よりも短くなります。

CPU スケジューリング基準

CPU スケジューリング アルゴリズムは、次のものを最大化および最小化しようとします。

最大化します

CPU使用率：CPU 使用率は、オペレーティング システムが CPU を可能な限りビジー状態に維持するために必要な主なタスクです。範囲は 0 ～ 100 パーセントです。ただし、RTOS の場合、低レベル システムでは 40 パーセント、高レベル システムでは 90 パーセントになります。

スループット： 単位時間当たりに実行を終了するプロセスの数はスループットと呼ばれます。 したがって、CPU がプロセスの実行でビジー状態になっているとき、その時点で作業が行われており、単位時間あたりに完了する作業をスループットと呼びます。

最小限に抑える

待ち時間： 待機時間は、特定のプロセスが準備完了キューで待機する必要がある時間です。

反応時間： これは、リクエストが送信されてから最初の応答が生成されるまでの時間です。

ターンアラウンドタイム： 所要時間は、特定のプロセスを実行するのにかかる時間です。 これは、メモリに入るまでの待機時間、キューでの待機時間、および CPU での実行に費やした合計時間の計算です。 プロセスの送信時刻から完了時刻までの期間がターンアラウンドタイムです。

インターバルタイマー

タイマー割り込みは、プリエンプションと密接に関係する方法です。 特定のプロセスが CPU 割り当てを取得すると、タイマーが指定された間隔に設定される場合があります。 タイマー割り込みとプリエンプションはどちらも、CPU バーストが完了する前にプロセスに CPU を強制的に返します。

マルチプログラム オペレーティング システムのほとんどは、プロセスがシステムを永久に拘束するのを防ぐために、何らかの形式のタイマーを使用します。

ディスパッチャーとは何ですか?

CPU の制御をプロセスに提供するモジュールです。 ディスパッチャーは、コンテキストが切り替わるたびに実行できるように高速である必要があります。 ディスパッチ レイテンシは、CPU スケジューラが XNUMX つのプロセスを停止して別のプロセスを開始するのに必要な時間です。

ディスパッチャーによって実行される機能:

• コンテキストの切り替え
• ユーザーモードに切り替える
• 新しくロードされたプログラム内の正しい場所に移動します。

CPUスケジューリングアルゴリズムの種類

大きく分けてXNUMX種類あります プロセススケジューリングアルゴリズム

1. 先入れ先出し（FCFS）
2. 最短ジョブ優先 (SJF) スケジューリング
3. 最短残り時間
4. 優先スケジューリング
5. ラウンドロビンスケジューリング
6. マルチレベルキューのスケジューリング

先着順

先着順サービスは FCFS の完全な形式です。 これは、最も簡単でシンプルな CPU スケジューリング アルゴリズムです。 このタイプのアルゴリズムでは、CPU を要求するプロセスが最初に CPU 割り当てを取得します。 このスケジューリング方法は、FIFO キューを使用して管理できます。

プロセスが準備完了キューに入ると、その PCB (プロセス制御ブロック) がキューの最後尾にリンクされます。 したがって、CPU が空いたら、キューの先頭のプロセスに CPU を割り当てる必要があります。

FCFS工法の特徴

• ノンプリエンプティブおよびプリエンプティブのスケジューリング アルゴリズムを提供します。
• ジョブは常に先着順で実行されます
• 実装と使用は簡単です。
• ただし、この方法はパフォーマンスが低く、一般に待ち時間が非常に長くなります。

最短残り時間

SRT の完全な形式は最短残り時間です。 SJF プリエンプティブ スケジューリングとも呼ばれます。 この方法では、完了に最も近いタスクにプロセスが割り当てられます。 この方法により、新しい準備完了状態のプロセスが古いプロセスの完了を保留することがなくなります。

SRTスケジューリング方式の特徴

• この方法は主に、短いジョブを優先する必要があるバッチ環境に適用されます。
• これは、必要な CPU 時間が不明な共有システムに実装するには理想的な方法ではありません。
• 各プロセスに、次の CPU バーストの長さを関連付けます。これにより、オペレーティング システムはこれらの長さを使用し、プロセスを可能な限り短い時間でスケジュールするのに役立ちます。

優先順位に基づいたスケジューリング

優先スケジューリング 優先度に基づいてプロセスをスケジュールする方法です。 この方法では、スケジューラは優先度に従って作業するタスクを選択します。

優先スケジューリングは、OS が優先順位を割り当てるのにも役立ちます。 優先度の高いプロセスが最初に実行される必要がありますが、同じ優先度のジョブはラウンドロビンまたは FCFS ベースで実行されます。 優先順位は、メモリ要件、時間要件などに基づいて決定できます。

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

ラウンドロビンは、最も古く、最も単純なスケジューリング アルゴリズムです。このアルゴリズムの名前は、各人が順番に何かを平等に受け取るラウンドロビンの原理に由来しています。これは主に、マルチタスクのスケジューリング アルゴリズムに使用されます。このアルゴリズム方式は、プロセスの飢餓のない実行に役立ちます。

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

• ラウンドロビンはクロック駆動のハイブリッドモデルです。
• タイム スライスは最小値である必要があり、処理される特定のタスクに割り当てられます。 ただし、プロセスによって異なる場合があります。
• これは、特定の制限時間内にイベントに応答するリアルタイム システムです。

最短のジョブが最初

SJF は、(Shortest job first) の完全な形であり、実行時間が最も短いプロセスが次に実行されるように選択されるスケジューリング アルゴリズムです。 このスケジューリング方法は、プリエンプティブまたは非プリエンプティブにすることができます。 実行を待機している他のプロセスの平均待ち時間が大幅に短縮されます。

SJFスケジューリングの特徴

• これは、完了までの時間単位として各ジョブに関連付けられます。
• この方法では、CPU が使用可能な場合、完了時間が最も短い次のプロセスまたはジョブが最初に実行されます。
• 非プリエンプティブ ポリシーで実装されます。
• このアルゴリズム方法は、ジョブの完了を待つことが重要ではないバッチタイプの処理に役立ちます。
• 最初に実行する必要がある短いジョブを提供することにより、ジョブの出力が向上します。これらのジョブは、ほとんどの場合、所要時間が短くなります。

複数レベルのキューのスケジューリング

このアルゴリズムは、レディ キューをさまざまな個別のキューに分割します。 この方法では、プロセスの優先順位、メモリのサイズなど、プロセスの特定のプロパティに基づいてプロセスがキューに割り当てられます。

ただし、ジョブをスケジュールするには他のタイプのアルゴリズムを使用する必要があるため、これは独立したスケジューリング OS アルゴリズムではありません。

複数レベルのキュースケジューリングの特徴

• いくつかの特性を持つプロセスに対して複数のキューを維持する必要があります。
• 各キューには個別のスケジューリング アルゴリズムが存在する場合があります。
• キューごとに優先順位が与えられます。

スケジューリング アルゴリズムの目的

スケジュール アルゴリズムを使用する理由は次のとおりです。

• CPU は効率を向上させるためにスケジューリングを使用します。
• これは、競合するプロセス間でリソースを割り当てるのに役立ちます。
• マルチプログラミングにより、CPU の使用率を最大限に高めることができます。
• 実行されるプロセスは準備完了キューにあります。

製品概要

• CPU スケジューリングは、別のプロセスが保留されている間に、どのプロセスが実行用の CPU を所有するかを決定するプロセスです。
• プリエンプティブ スケジューリングでは、ほとんどのタスクには優先順位が割り当てられます。
• ノンプリエンプティブスケジューリング方式では、CPU が特定のプロセスに割り当てられます。
• バースト時間は、プロセスの実行が完了するまでに必要な時間です。 実行時間とも言います。
• CPU 使用率は、オペレーティング システムが CPU を可能な限りビジー状態に維持する必要がある主なタスクです。
• 単位時間当たりに実行を終了するプロセスの数はスループットと呼ばれます。
• 待機時間は、特定のプロセスが準備完了キューで待機する必要がある時間です。
• これは、リクエストが送信されてから最初の応答が生成されるまでの時間です。
• 所要時間は、特定のプロセスを実行するのにかかる時間です。
• タイマー割り込みは、プリエンプションと密接に関係する方法です。
• ディスパッチャは、CPU の制御をプロセスに提供するモジュールです。
• プロセス スケジューリング アルゴリズムには、2) 先着順 (FCFS)、3) 最短ジョブ優先 (SJF) スケジューリング、4) 最短残り時間、5) 優先度スケジューリング、6) ラウンド ロビン スケジューリング、XNUMX) マルチレベル キュー スケジューリングの XNUMX 種類があります。
• 先着順方式、CPU を要求するプロセスが最初に CPU 割り当てを取得します。
• 「最短残り時間」では、プロセスは完了に最も近いタスクに割り当てられます。
• 優先順位スケジューリングでは、スケジューラは優先順位に従って作業するタスクを選択します。
• ラウンドロビンスケジューリング 各人が順番に何かを平等に分配するという原則に基づいて機能します。
• 最初の「最短ジョブ」では、次に実行するために最も短い実行時間を選択する必要があります。
• マルチレベル スケジューリング方法では、レディ キューをさまざまな個別のキューに分割します。 この方法では、プロセスは特定のプロパティに基づいてキューに割り当てられます。
• CPU は効率を向上させるためにスケジューリングを使用します。