[OS] CPU Scheduling

プロセス属性分類

CPU burstとI/O burstを交互に使用します.

I/O-bound process

ジョブに要するI/O時間は、CPUを占有計算する時間よりも

多い.

many short CPU bursts

CPU-bound process

計算を主とするジョブ

few very long CPU bursts

複数種類のジョブ(＝プロセス、I／Oバインドジョブ、CPUバインドジョブ)が混在しているため、CPUスケジューリング(誰にどのくらいの時間を与えるか、どのくらいの時間を費やすか)が必要となります.

Interactive Jobが適切な応答を提供することを望んでいる.

CPUやI/O機器などのシステムリソースを利用する.

CPU Scheduler & Dispatcher

どちらもハードウェアではなくオペレーティングシステムにあります.

CPU Scheduler

アテンション

Ready状態のプロセスで、今回CPUに割り当てられるプロセスを選択します.

Dispatcher

CPUの制御権は、CPUスケジューラ選択のプロセスに渡される.

このプロセスをコンテキスト切替(コンテキスト交換)と呼ぶ.

スケジュールが必要

ステータスの変更は次のとおりです.

1. Running -> Blocked (ex. I/O 요청하는 시스템 콜)
2. Running -> Ready (ex. 할당 시간 만료로 timer interrupt)
3. Blocked -> Ready (ex. I/O 완료 후 인터럽트)
4. Terminate

1,4:プリエンプト不可
2、3:プリエンプト(->強制プリエンプト)

Scheduling Criteria

パフォーマンス・インデックス(=パフォーマンス・メトリック、パフォーマンス・メトリック)
システム側(H/W、OS)

CPU利用率(利用率):

スループット(スループット):所与の実行時間内に完了するプロセス数

プロセスの側面

ターンタイム(所要時間、戻り時間)
CPUを入力して使い切る時間

プロセス終了ではなくCPU完了

Waiting time
レディーQで並んで待っている時間
待機CPUの総待ち時間

Response time
レディキューからCPUを最初に取得するまでの時間
待ち時間とは異なり、待ち時間は最初のCPUを取得する時間である.

Scheduling Algorithms

FCFS(First-Come First-Service)

先着先着アルゴリズム

Convoy効果:長い流れの前に短い流れが長い時間待つ

は非効率です.

Nonpreemptive

SJF(Shortest-Job-First)

CPUバースト時間が最も短いプロセスは第1位

にランクする.

2方式

Nonpreemptive
CPUが見つかれば、CPUクラッシュが完了するまでCPU

をプリエンプトすることはない.

Preemptive
新しいCPUバースト時間の短いプロセスが到着すると、CPUが占有されます.
この方法はShortest Remaining Time First(SRTF)です.
Averageの待ち時間が最も少ないアルゴリズムです.(SRTF)

SJF is optimal

は、与えられたプロセスの最小平均待ち時間が

であることを保証する.

Priority Scheduling

は、最も優先度の高いプロセス

にCPUを割り当てる.

方式(プリエンプト式、非プリエンプト式)

高優先度プロセスがCPUを占有できるかどうかの観点

.

SJFも優先度スケジューリングです.
priority = predicted next CPU burst time

問題:起動(飢餓)-長時間のプロセスでCPU

を取得できない

ソリューション:Aging-Processの優先度は時間が経つにつれて徐々に向上します.

RR(Round Robin)

現代スケジューリングに基づく

プリエンプトスケジューリング

各プロセスは、同じ割り当て時間(10~100ミリ秒)の

を有する.

が時間を割り当てると、プロセスはプリエンプトされ、readyキューの最後の列に並べられます.

は一般にSJFの平均回転時間より長いが応答時間は速い.

待ち時間

は、自身のCPU時間に比例する.

n個のプロセスがレディキューにあり、割り当てられた時間がq時間ユニットである場合、各プロセスは最大q時間ユニットでCPU時間の1/nを取得する.
👉 どのプロセスも(n-1)q timeunit以上を待つことはありません.

[パフォーマンス]割り当て時間が長ければ長いほど、FCFS(FIFO)が小さくなり、コンテキスト切り替えのオーバーヘッドが大きくなります.

Multilevel Queue

タスクをグループ化して、複数のキュー

を管理および割り当てます.

Readyキューを複数のキューに分割

foreground(interactive)

background(batch - no human interaction)

各キューには独立したスケジューリングアルゴリズムがあります.

foreground - RR

background - FCFS

キューのスケジューリングが必要です.

Fixed priority scheduling

優先度が高い;飢餓の可能性O

フロント

より優先

Time slice

CPU時間適切な割合で

を割り当てる.

ex) foreground 80% in RR, background 20% in FCFS

Multilevel Feedback Queue

プロセスは、他のキュー

に移動することができる.

エージェントは、このようにして実現され得る.

これらのパラメータを定義する

.

Queueの数

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

プロセスは、親キューの標準

に送信される.

プロセスによるサブキューへの標準

プロセスは、CPUサービスの受信を試みるとき(初めて)、キューに入る基準が

であると判断する.
割り当て時間が最小のRRキューに最初に割り当てられます.
時間が終わると、低級に変わります.
処理時間が短い場合、優先度が高いほど、長いほど優先度が低くなります.

Multiple-Processor Scheduling

複数のCPUがある場合、スケジューリングはさらに複雑になります.

同一プロセッサの場合(同一プロセッサ)

キューを1行に並べ、各プロセッサが自分で取り出すようにします.

は、特定のプロセッサによって処理される必要がある場合がありますが、これはより複雑になります.

ex.複数のデザイナーがいて、特定のデザイナー

を裁断しています.

Load Sharing

は、特定のプロセッサ上のワークロードを回避するための適切な負荷共有メカニズムを必要とする

独立キューと連合キューを使用する方法

Symmetric Multiprocessing(SMP)

各プロセッサは、独自のスケジューリング決定

を有する.

Asymmetric Multiprocessing

1プロセッサはシステムデータへのアクセスと共有を担当し、残りのプロセッサは

Real-Time Scheduling

Hard real-time systems
必ず規定の時間内に完成するように手配しなければならない.

Soft real-time computing
一般的なプロセスに比べて、より高い優先度を持つ必要があります.

Thread Scheduling

ローカルスケジューリング:ユーザーレベルスレッドユーザープロセスはスレッドを直接管理します.
->オペレーティングシステム、カーネルは関与しません.

グローバルスケジューリング:Kernel level threadの場合、カーネルの短期スケジューラは、通常のプロセスと同様に、どのスレッドをスケジューリングするかを決定します.
->オペレーティングシステム参加(調整)

Algorithm Evaluation

Queueing models
performance index

実施・測定(性能測定)
実際のシステムにおいてアルゴリズムを実装し、実際の動作の性能を測定する

シミュレーション
上記の実測方法よりも簡単な方法
シミュレーションプログラムを用いて作成した後,trace(入力データ)比較結果(ATT値導出)を入力する.
cf) ATT: Averaget Turnaround Time