プロセッサーのスケジューリングの詳細な紹介

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

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

---

基本概念

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

目的は、リソース ユーザーの数を制御し、リソースを占有するリソース ユーザーの権限を選択することです。プロセッサ スケジューリングの 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 のカーネルプログラムが動作しているときに、ある時点でプロセスのスケジューリングを引き起こす要因が発生すると、すぐにスケジューリングや切り替えができない場合があります。

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

1. 割り込み処理プロセス中: 割り込み処理プロセスが複雑で、実装時にプロセス切り替えを実現することが困難であり、割り込みが発生する処理はシステムの作業の一部であり、論理的にはプロセスに属さないため、プロセッサ リソースを奪われるべきではありません。

2. プロセスはオペレーティング システムのカーネル プログラムのクリティカル セクションにあります。クリティカル セクションに入った後は、理論上、他の並列プログラムが入るのを防ぐために共有データにアクセスする必要があります。ロックを解除する前に他のプロセスに切り替えて、共有データのリリースを高速化します。

3. 割り込みの完全なシールドを必要とするその他のアトミック操作: ロック、ロック解除、サイト保護の中断、回復、その他のアトミック操作など。アトミックプロセスでは、割り込みさえもマスクする必要があり、プロセスのスケジューリングや切り替えは実行すべきではありません。

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

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

1. スケジューリング条件が発生し、現在のプロセスが実行を続行できない場合、スケジューリングと切り替えをすぐに実行できます。この状況でオペレーティング システムがプロセス スケジューリングのみを実行する場合、それは非剥奪スケジューリングです。

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

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

スケジューリング方式

• 非プリエンプティブ方式
  プロセッサがプロセスに割り当てられると、現在実行中のプロセスのプロセッサは、クロックの中断やその他の理由によってプリエンプトされることはありません。プロセスが完了またはイベントによってブロックされた場合にのみ、プロセッサーが他のプロセスに割り当てられます。

• プリエンプションモード
  システムは、スケジューラーが特定の原則に基づいて実行中のプロセスを一時停止できるようにし、割り当てられたプロセスはプロセッサーになります。
  

• 優先順位の原則

• 短いプロセスの優先順位の原則

• タイムスライス原理

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

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

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

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

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

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

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

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

• 人間とコンピューターの対話を実現できません

• はジョブの緊急性を考慮していません

• - スケジューリング アルゴリズム:

PSA アルゴリズムは、ジョブの緊急度に基づいており、ジョブの優先順位スケジュールに従って、対応する
• 優先度

  をジョブに割り当てます (次に最も高いリクエスト率):

HRRN アルゴリズム。ジョブの待機時間とジョブの実行時間の両方を考慮します。ジョブがない場合の動的な優先順位を導入します。

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

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

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

特徴:

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

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

長いジョブの場合(長いサービス時間が必要)、待機時間が十分に長いため、より高い優先順位を取得することもできます。永遠に待つことはありません。
タイムスライスローテーションスケジューリングアルゴリズム(RR)

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

プロセス切り替え
タイムスライスが使い果たされておらず、実行中のプロセスが完了した場合、スケジューラは直ちにアクティブ化され、実行キューから削除され、スケジューリング準備完了キューに配置されます。キューのプロセスが実行され、新しいタイム スライスが開始されます。タイム スライスが使い果たされると、プロセスの実行が完了していない場合、スケジューラはそのプロセスを準備完了キューの最後に送信します。

注

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

詳細 マルチレベル フィードバック キュー スケジューリング アルゴリズム (マルチレベル フィードバック キュー):
複数の準備完了キューを設定し、各キューに異なる優先度を与えます。優先度が高いほど、そのタイム スライスは小さくなります。優先度が最も高いキューのタイム スライスが最も小さくなります。最初にスケジュールされるキューに入力します
優先度の高いキュー内のすべてのプロセスが完了した場合にのみ、次のキューがスケジュールされます

。

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

新しいプロセスが到着すると、優先度の低いキューが実行されます。 、このタイム スライスの実行後、CPU は新しく到着したジョブにすぐに割り当てられます (プリエンプティブ)。

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

リアルタイム システムとは、システムが外部イベントのリクエストにタイムリーに応答し、この機能に基づいてこれらのリクエストをリアルタイムで処理できることを意味します。システムは産業 (兵器) 制御、マルチメディア、その他のシステムで一般的です。
リアルタイム システムには通常、期限があり、開始期限までに実行し、終了期限までに完了する必要があります。ソフト リアルタイム タスクは上記と同じですが、厳密ではありません。
リアルタイム システムでは、注目に値する 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 はプロセッサの数です。

Earliest Deadline First Algorithm (EDF)

このアルゴリズムは、実際の期限に従ってタスクの優先順位を決定します。

1. 非プリエンプティブ

2. プリエンプティブ

Low Slack First Algorithm (LLF)

この方法では、タスクの緊急度 (緩さ) に応じて優先順位が与えられます。タスクのスラック度 = 完了しなければならない時間 - 自身の実行時間 - 現在の時間

システムのタスクはスラック度に応じて準備完了キューに配置されます。キューの先頭に配置されます。つまり、スケジューラーが最初にそれらを実行します。

以上がプロセッサーのスケジューリングの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。