プロセッサスケジューリング

タグ (スペース区切り): プロセススケジューリングスケジューリングアルゴリズムオペレーティングシステム

基本概念

定義
: オペレーティングシステムは、複数のプロセス (または複数のプロセスがリクエスト）がこれらのリソースを使用したい場合、リソースには限りがあるため、スケジューリングと呼ばれる特定の原則に従ってリソースを占有するプロセス（リクエスト）を選択する必要があります。

目的は、リソースユーザーの数を制御し、リソースを占有するリソースユーザーの権限を選択することです。プロセッサスケジューリングの 3 つのレベル:

高レベルのスケジューリング: ジョブスケジューリング、スケジューリングオブジェクトはジョブです
中級レベルのスケジューリング: メモリスケジューリング (本質的にはメモリのスワップ機能)
低レベルレベルスケジューリング: プロセススケジューリング、スケジューリングオブジェクトはプロセスまたはカーネルレベルのスレッドです

ジョブスケジューリングのアルゴリズムはプロセススケジューリングにも適用できます

サービス時間(T_s): システムにかかる時間ジョブまたはプロセスにサービスを提供するための時間
ターンアラウンドタイム(T_i) : ジョブまたはプロセスがシステムに送信されてから完了するまでの時間間隔
通常、以下が含まれます:

ジョブの時間。外部ストレージのバックアップキューでのスケジューリングを待機する時間。
プロセスが準備完了キューでプロセスのスケジューリングを待機する時間。
プロセスが CPU 上で実行する時間。
プロセスが I/O 操作の完了を待機する時間。

平均所要時間:
[T = frac{sum_{i=1}^n T_i}{n}]
加重所要時間あり: サービスにかかる時間に対するジョブの所要時間の比率それ
[W_i = frac{T_i}{T_s}]
平均加重所要時間:
[W = frac{sum_{i=1 }^n frac{T_i}{T_s}}{n}]

タイミング、切り替え、プロセスのスケジューリング

プロセスのスケジューリングと切り替えプログラムは、オペレーティングシステムのカーネルプログラムです。スケジューリングを要求するイベントが発生すると、プロセススケジューラが実行され、新しい準備完了プロセスがスケジュールされると、プロセス間の切り替えが実行されます。理論的には、これら 3 つが順番に実行されるはずですが、実際の設計では、OS のカーネルプログラムが動作しているときに、ある時点でプロセスのスケジューリングを引き起こす要因が発生すると、すぐにスケジューリングや切り替えができない場合があります。

最新のオペレーティングシステムでは、以下の状況ではプロセスのスケジューリングと切り替えを実行できません:

割り込み処理プロセス中: 割り込み処理プロセスが複雑で、実装時にプロセス切り替えを実現することが困難であり、割り込みが発生する処理はシステムの作業の一部であり、論理的にはプロセスに属さないため、プロセッサリソースを奪われるべきではありません。
プロセスはオペレーティングシステムのカーネルプログラムのクリティカルセクションにあります。クリティカルセクションに入った後は、理論上、他の並列プログラムが入るのを防ぐために共有データにアクセスする必要があります。ロックを解除する前に他のプロセスに切り替えて、共有データのリリースを高速化します。
割り込みの完全なシールドを必要とするその他のアトミック操作: ロック、ロック解除、サイト保護の中断、回復、その他のアトミック操作など。アトミックプロセスでは、割り込みさえもマスクする必要があり、プロセスのスケジューリングや切り替えは実行すべきではありません。

上記のプロセス中にスケジューリングを引き起こす条件が発生し、スケジューリングと切り替えをすぐに実行できない場合は、システムのリクエストスケジューリングフラグを設定する必要があり、上記のプロセスが完了するまで、対応するスケジューリングと切り替えは実行されません。

プロセスのスケジューリングと切り替えを実行する必要がある状況は次のとおりです。

スケジューリング条件が発生し、現在のプロセスが実行を続行できない場合、スケジューリングと切り替えをすぐに実行できます。この状況でオペレーティングシステムがプロセススケジューリングのみを実行する場合、それは非剥奪スケジューリングです。
割り込み処理やトラップ処理が完了した後、割り込まれたプロセスのユーザーモードプログラム実行サイトに戻る前に、リクエストスケジューリングフラグがセットされていれば、即座にプロセスのスケジューリングや切り替えを行うことができます。この場合、オペレーティングシステムが実行スケジューラをサポートしている場合、剥奪モードスケジューリングが実装されます。

プロセスの切り替えは、スケジューリング完了直後に発生することが多く、元のプロセスの現在の切り替えポイントのオンサイト情報を保存し、スケジュールされたプロセスのオンサイト情報を復元する必要があります。コンテキストを切り替えるとき、オペレーティングシステムカーネルは、元のプロセスのコンテキスト情報を現在のプロセスのカーネルスタックにプッシュして保存し、スタックポインタを更新します。カーネルは、新しいプロセスのカーネルスタックから新しいプロセスのローカル情報をロードし、現在実行中のプロセス空間ポインタを更新し、PC レジスタをリセットし、その他の関連作業を完了すると、新しいプロセスの実行を開始します。

スケジューリング方式

非プリエンプティブ方式
プロセッサがプロセスに割り当てられると、現在実行中のプロセスのプロセッサは、クロックの中断やその他の理由によってプリエンプトされることはありません。プロセスが完了またはイベントによってブロックされた場合にのみ、プロセッサーが他のプロセスに割り当てられます。
プリエンプションモード
システムは、スケジューラーが特定の原則に基づいて実行中のプロセスを一時停止できるようにし、割り当てられたプロセスはプロセッサーになります。

優先順位の原則
短いプロセスの優先順位の原則
タイムスライス原理

典型的なスケジューリングアルゴリズム

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

つまり、両方のジョブスケジューリングに使用できるFCFSスケジューリングアルゴリズムです。システムは、ジョブが到着した順序に従ってスケジュールを設定します (準備完了キューで待機時間が最も長いジョブを優先します)。
欠点: ジョブの緊急性は考慮されず、短いジョブのみが処理されます。 (プロセスを) 順番に実行できます

優先順位付けされたスケジューリングアルゴリズム (短いジョブを最初に):

は、ほとんどのオペレーティングシステムが短いジョブであるため、ジョブの実行中に最も短いジョブを選択します。

SJF (非プリエンプティブル): アルゴリズムはジョブの長さ (ジョブの実行に必要な時間) に基づいて優先度を計算します。ジョブが短いほど、優先度は高くなります。

SPF (プリエンプティブル): 上記と同じですが、ジョブの優先度が高い場合、リソースを占有して最初に実行する可能性があります。

ジョブプロセスに悪影響を及ぼします

人間とコンピューターの対話を実現できません
はジョブの緊急性を考慮していません
- スケジューリングアルゴリズム:
優先度
をジョブに割り当てます (次に最も高いリクエスト率):

Priority Right = (待機時間 + 要求されたサービス時間) / 要求されたサービス時間

は次のように省略できます。

R = 応答時間 / 要求されたサービス時間

特徴:

ジョブの待機時間が同じ場合、要求されたサービス時間は短いほど優先度が高くなります。これは SJF アルゴリズムと同様です。短いジョブに有益です

ジョブが同じサービス時間を必要とする場合、FCFS アルゴリズムと同様に、ジョブの待機時間はほぼ長くなり、優先度が高くなります。これは、長いジョブに有益です

原則: システムはすべての準備を整えます。 FCFS ポリシーに従ってプロセスを準備完了キューに入れ、一定の間隔で順次割り込みを生成するように設定し、システム内のプロセススケジューラをアクティブにして順次スケジューリングを完了し、新しいキューリーダープロセス (または新しく到着したプロセス) に CPU を割り当てます。

注

: タイムスライスの選択が小さすぎると、頻繁に実行されるプロセスのスケジューリングとプロセスの長いコンテキストの切り替えにより、システムのオーバーヘッドが増加します。選択時間が長すぎる場合、RR アルゴリズムは FCFS アルゴリズムに縮退し、短いジョブや対話型ユーザーのニーズを満たすことができなくなります。そのため、タイムスライスは、通常の一連の対話に必要な時間よりもわずかに大きく選択する必要があります。

。

キュー内のプロセスは、ローテーションアルゴリズムに従ってスケジュールされます。新しいプロセスは、メモリの後、最初に最も高い優先度でキューに入ります

リアルタイムシステムでのプロセススケジューリングアルゴリズム

リアルタイムシステムとは、システムが外部イベントのリクエストにタイムリーに応答し、この機能に基づいてこれらのリクエストをリアルタイムで処理できることを意味します。システムは産業 (兵器) 制御、マルチメディア、その他のシステムで一般的です。
リアルタイムシステムには通常、期限があり、開始期限までに実行し、終了期限までに完了する必要があります。ソフトリアルタイムタスクは上記と同じですが、厳密ではありません。
リアルタイムシステムでは、注目に値する 2 種類のアルゴリズムがあります: 最も早いデッドライン優先と最も緩い優先の両方のタイプのアルゴリズム。非プリエンプティブスケジューリングですが、後者はプリエンプティブスケジューリングでよく使用されます。
m 周期のリアルタイムスケジューリングでは、各リアルタイムタスクの処理時間 (C_i)、サイクルタイム (P_i)プロセッサーが 1 つだけの場合、条件が満たされる必要があります: $sum_{i= 1}^mfrac{C_i}{P_i} (1 未満; マルチプロセッサー条件下では、条件が満たされる必要があります)sum_{ i=1}^mfrac{C_i}{P_i} $ は N より小さく、N はプロセッサの数です。