スポンサーリンク
OS

【OS】CPUスケージュリング

CPUスケジューラ

CPUスケジューラの待ち行列内のプロセスの中から選択し、CPUコアに割り当てする。プロセスの実行は、CPU実行とI/O待機のサイクルで構成される。

CPUスケジューリングの決定

①runningからwaiting(プリンプティブ)
②runningからready(ノンプリエンプティブ)
③waitingからready(ノンプリエンプティブ)
④Terminated(プリンプティブ)

ノンプリエンプティブ:OSがタスクを切り替えるのではなく、実行状態のタスクが自ら待ち状態に遷移するか終了するまで、他のタスクが実行状態に遷移しない方法のこと

ディスパッチャ

マイクロプロセッサ(CPU/MPU)が実行するプログラムを短い時間ごとに次々に切り替えるものをプロセスディスパッチャと呼び、単に略してディスパッチャとも呼ばれる。以下のことが含まれる

content switching

ユーザーモードへの切り替え

ユーザープログラムの適切なところに飛んでそのプログラムを再起動する。

ディスパッチャレイテンシ:ディスパッチャが1つのプロセスを停止して他のプロセスを実行するのにかかる時間

スケジューリング基準

( )の中はスケジューリングアルゴリズムを最適化するためにしたいこと

CPU utilization(大きくしたい)

CPUの使用率

Throughput(大きくしたい)

単位時間あたりに実行できるプロセスの数

Turnaround time(小さくしたい)

あるプロセスを完了させるまでの時間

Waiting time(小さくしたい)

プロセスが準備完了待ち行列で待機していた時間

Response time(小さくしたい)

リクエストが送信されてから最初のレスポンスが返ってくるまでにかかる時間

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

CPUスケジューリングのアルゴリズムは4つある。

FCFS(First Come First served )→到着順

ノンプリエンプティブ。プロセスが実行可能になると、実行待ち行列の最後に置かれる。スケジューラはCPUを実行可能待ち行列の先頭のプロセスから順に実行していく。FIFO(First in first out )をキューで実装する。

メリット

単純、公平

デメリット

長時間実行するプロセスがあった時、その後に並ぶプロセスは(例え実行時間が短いものでも)長時間待たされる

コンボイ効果;遅いプロセスが原因でOS全体が遅くなる

Waiting time: P1 = 0, P2 = 24, P3 = 27
Average waiting time:( 0 + 24 + 27 )/ 3 = 17

SJF(Shortest Job First)→実行時間の短い順

ノンプリエンプティブ。CPU Burst timeの短い順にCPU割り当てをする。

メリット

プロセス実行完了までの時間の平均値が最小になる

デメリット

実現化困難(プロセスの実行時間をあらかじめ知るのは難しい)

Average waiting time = ( 3 + 16 + 9 + 0)/4 = 7

CPU Burst Timeの決定

1.t_n = n<sup>th<\sup>番目のCPU burstの実際の長さ

2.\tau_{n+1}= 予想した次のCPU burst

3.0\leq\alpha\leq1

4.\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n

普通、\alpha\frac{1}{2}に設定する

RR(Round Robin)

プリエンプティブ。FCFS(到着順)でプログラムを実行していく。プログラムの実行が開始され定時間が経過すると、次のプログラムが開始される。 いったん実行を終えたプログラムは待ち行列の最後にまわされる。n個のプロセスがレディキューがあり、quantum time(一つのプロセスが一回にCPUに割り当てられる時間)がqのときn回に一度CPUが回ってくる。

メリット

どのプロセスも公平に同時実行される

デメリット

実行切り替えが頻繁にあり、オーバーヘッドが大きい

オーバーヘッド
あることを実現するために必要なシステム資源の消費などのコスト

次の例はquantum time = 4

SJFよりTurnaround timeの平均は高いが、response timeは平均は低い
qは10-3秒から100-3

Priority→優先度順

ノンプリエンプティブ。各プロセスに実行の優先度を与え、優先度の順に実行するというものである。優先度はさまざまな基準によって定義される。同じ優先順位の場合は、FCFS(到着順)の順序でスケジューリングされる。

メリット

優先度の高い(すなわち重要な)プロセスが早く実行されるという意味で、システム的な効率はいい

デメリット

優先度の低いプロセスは実行可能であってもなかなか実行されないという飢餓状態(starvation)に陥ることがある。

飢餓状態(starvation):優先度の低いプロセスは実行可能であってもなかなか実行されない状況

→aging:時間の経過とともにプロセスの優先度が上がる(解決策)

スレッドスケジューリング

process-contention scope(PCS)

 

system-contention-scope(SCS)

 

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

マルチコアCPU

common ready queue

全てのスレッドは、共通のレディキューにある場合がある。

per-core run queues

各プロセッサは、独自のスレッドのプライベートキューを持っている

マルチスレッドコア

同じ物理チップに複数のプロセッサコアを配置する

M: memory stall cycle
C: compute cycle

 

NUMAシステム

Heterogeneous マルチプロセッシング

 

リアルタイムCPUスケジューリング

ソフトリアルタイムシステムとハードリアルタイムシステム

ソフトリアルタイムシステム

決められた時刻までに終了できなくても致命的な問題とはならないシステムで座席予約やバンキングシステムなど。

ハードリアルタイムシステム

決められた時刻までに処理が終了できなかった場合に、システムやそれを扱う人に致命的ダメージが発生するシステムで、例えばエアバック制御システムなど。

待ち時間(レイテンシ)

割り込み待ち時間

割り込みの到着から割り込みを処理する手順を開始するまでの時間

ディスパッチャ待ち時間

現在のプロセスをCPUから切り離して別のプロセスに切り替えるスケジュールまでの時間

スポンサーリンク