プロセス属性分類
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