オペレーティングシステム
#3
計算機工学III
オペレーティングシステム
#3 CPUの仮想化:
スケジューリング
2006/04/21
津邑 公暁
オペレーティングシステム
#3
■
...の前に
講義資料

http://www.matlab.nitech.ac.jp/
資料 (ppt)
メールアドレス
オペレーティングシステム
#3
■
プロセス切り替え

■
復習:スレッド
コスト高
スレッド

プロセスを分割

CPUリソースを割り当てる,さらに細かい単位

主記憶領域が同じのため,切り替えコスト低
オペレーティングシステム
#3
■
復習:割込み
割込み



通常のCPU演算動作とは異なる事象
➔
キーボード入力を受け取った
➔
自動車がどこかに衝突した
➔
サーバからデータが送られてきた
割込み発生時にプロセスの切り替えが起こる
TSSでは、プロセス切り替えのために
インターバルタイマーが定期的に割込みを発生
オペレーティングシステム
#3
■
■
復習:割込みの種類
内部割込み

スーパバイザコール割込み

プログラムチェック(例外)割込み
外部割込み

入出力割込み

タイマ割込み

マシンチェック割込み

リスタート割込み
オペレーティングシステム
#3
■
スケジューリング

スケジューリングの基本

様々なスケジューリング手法

実際のOSにおけるスケジューリング例
今日の内容
オペレーティングシステム
#3
3.1
スケジューリングの基本
オペレーティングシステム
#3
CPU以外のリソースを獲得
or
スーパバイザコール終了
復習:プロセスの三状態
実行可能
(ready)
CPUリソースが
割り当てられた
(順番がまわってきた)
割込み
待ち
(wait)
実行
(running)
スーパバイザコール
or
CPU以外のリソース喪失
オペレーティングシステム
#3
プロセスの状態遷移
プロセス
待ち行列
CPUリソースが
割り当てられた
(順番がまわってきた)
CPU以外のリソースを獲得
or
スーパバイザコール終了
待ち
割込み
スーパバイザコール
or
CPU以外のリソース喪失
CPU
オペレーティングシステム
#3
■
■
実行プロセスの選択

CPUスケジューラが行う

対話型処理では,数十~数百回/s
スケジューリングアルゴリズム

高速かつ軽量に行う必要
➔
■
スケジューリング
オーバヘッド削減のため
基本

待ち行列の先頭プロセスにCPUリソースを割り当て
➔
全待ちプロセスの数に依存しない時間で
スケジューリングが可能
オペレーティングシステム
#3
■
実行プロセスの切り替えにはプロセスの
中断が必要

■
プロセスの中断方式
復習:CPU状態(PSW)の PCB への待避
中断方式


プリエンプション方式
➔
OSがプロセスから実行権を剥奪
➔
UNIX, WindowsXP, MacOS X
ノンプリエンプション方式
➔
プロセスがOSに実行権を自主的に返還
➔
Windows 95, MacOS 9
プロセス暴走時には
システム停止も
オペレーティングシステム
#3
3.2
スケジューリングの目的
オペレーティングシステム
#3
■
リソースを効率的に利用したい


■
スケジューリングの目的
CPUリソースは時分割により仮想化
➔
プロセス切り替えが多発
➔
次に実行するプロセスを選択する機会も膨大
切り替えごとにコスト(オーバヘッド)が発生
➔
スケジューリング次第で全体のオーバヘッドが増減
➔
効率の悪いスケジューリング=全体の性能低下
効率のよいスケジューリングが必要
オペレーティングシステム
#3
■
応答時間

ある依頼した処理に対して
応答が返ってくるまでに要する時間
➔
対話処理:レスポンスタイム
-
➔
端末から入力した命令に対しシステムから結果を受け取るまでの時間
バッチ処理:ターンアラウンドタイム
-
■
効率化の指標
投入したジョブに対しシステムから結果を受け取るまでの時間
スループット

ある単位時間においてシステムが処理する仕事量
➔
プロセス切り替えに必要となるオーバヘッド等は含まない
➔
ユーザにとって意義のある仕事をいかにこなせるか
オペレーティングシステム
#3
■
応答時間とスループットは
トレードオフになる場合も

■
効率化の指標
例)
➔
応答時間向上を追求
➔
対話型処理を優先的に
➔
TSSのクオンタムを短く
➔
切り替え回数増加,切り替えオーバヘッド増加
➔
スループット低下
ユーザの要求やシステムの性質に応じて適切な
指標・スケジューリングを用いることが重要
オペレーティングシステム
#3
3.3
さまざまな
スケジューリング方式
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
さまざまなスケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重フィードバック
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
さまざまなスケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重フィードバック
オペレーティングシステム
#3
■
■
FIFO
到着順スケジューリング

FCFS: First Come First Served

FIFO: First In First Out
常に待ち行列の先頭から処理

○単純
➔

○公平
➔

プロセス選択機構も簡単になるし,選択オーバヘッドも小
追い抜き禁止
×ターンアラウンドタイムは良くない
オペレーティングシステム
#3
■
FIFOの欠点
ターンアラウンドタイム
待ち行列
プロセス プロセス プロセス プロセス
100s
1s
1s
1s
103s
3s
2s
1s
待ち行列
プロセス プロセス プロセス プロセス
1s
1s
1s
100s
103s
102s
101s
100s
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
さまざまなスケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重フィードバック
オペレーティングシステム
#3

■
FIFOの欠点は,
各プロセスの「重さ」を考慮していないのが原因
処理時間順スケジューリング

SPTF: Shortest Processing Time First

待ち行列内プロセスを処理時間順でソート

亜種;残り処理時間順(SRTF)
SPTF
オペレーティングシステム
#3
■
SPTF
処理時間の短いプロセスから順に処理

○応答時間最短;理想的

×実装不可能
➔
各プロセスの処理時間を事前に知ることはできない
待ち行列
プロセス
50s
20s
プロセス
5s
オペレーティングシステム
#3
■
プロセスの処理時間を推定してスケジューリング

■
SPTFの実装手法
経験則(heuristic)から近似的に処理時間を求める
対話型処理のプロセス処理時間
度
数
処理時間

ほとんどのプロセスは短時間で終了

短時間で終了しないプロセスは,なかなか終了しない
オペレーティングシステム
#3
■
すでに実行した時間から
■
入出力処理から
SPTFの近似実装
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
さまざまなスケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重フィードバック
オペレーティングシステム
#3
■
PS
各プロセスに優先度を付加

静的優先度:プロセス生成時に指定した優先度を使用
➔

動的優先度:プロセス実行中に優先度を適宜変化
➔


例)・プロセスの種類ごとに優先度を規定
リアルタイムプロセス > OS > 対話型 > バッチ
例)・既実行時間に応じて優先度を変化
・入出力操作直後のプロセスの優先度を高く
○優先度を適切に設定できれば非常に有効
×高負荷時,優先度の低いプロセスがなかなか
実行権を獲得できない(starvation)
➔
待ち時間に応じた優先度変化(aging)などで対処
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
さまざまなスケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重フィードバック
オペレーティングシステム
#3
■
RR
TSSで用いられる方式
待ち行列
CPU
プリエンプション
プロセス プロセス プロセス

■
待ち行列から選択されたプロセスに,微少な
CPU利用時間(クオンタム)を割り当て
クオンタム

クオンタム≒無限大:RR = FIFO

クオンタム=極小 :処理時間の短いプロセス有利
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
さまざまなスケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重レベルフィードバック
オペレーティングシステム
#3
■
Multi-Level Feedback


優先度別に待ち行列を用意
プロセスは,クオンタムを得るごとに
より優先度の低い待ち行列に移される
CPU
高
プロセス プロセス プロセス
優
先
度
低
MLF
オペレーティングシステム
#3
■
Multi-Level Feedback


複数のクオンタムを必要とするようなプロセス
(すなわち長い時間がかかるプロセス)
は,どんどん優先度が下がってゆく
SPTFの良い近似になっている
MLF
オペレーティングシステム
#3
3.4
スケジューリングアルゴリズム
の実行例
オペレーティングシステム
#3
FIFOの例
プロセス
t=2
t=6
処理時間 [s]
到着時刻 [s]
A
10
0
B
20
2
C
5
6
t=10
t=30
10s
28s
29s
t=35
オペレーティングシステム
#3
SPTFの例
プロセス
t=2
t=6
処理時間 [s]
到着時刻 [s]
A
10
0
B
20
2
C
5
6
t=10
t=15
t=35
10s
33s
9s
オペレーティングシステム
#3
RRの例
プロセス
t=2
処理時間 [s]
到着時刻 [s]
A
10
0
B
20
2
C
5
6
t=23
t=35
t=6
t=20
23s
33s
14s
オペレーティングシステム
#3
3.5
事例:
UNIXにおける
スケジューリング
オペレーティングシステム
#3
■
実際のOS (UNIX) の具体的実装例
■
UNIX SystemV
■

Solaris

AIX

HP-UX
Linux 2.6
オペレーティングシステム
#3
■
多重レベルフィードバックがベース
■
相違点



UNIX SysV
実行の終わったプロセスは,同じ優先度の待ち行列に
再登録
スーパバイザモードで実行されるプロセスは,
そのプリエンプションの原因から優先度を決定
ユーザモードで実行されるプロセスは,以下で決定
➔
静的優先度
➔
動的優先度(過去のCPUリソースの割当状況から計算)
➔
NICE値(ユーザが指定する優先度)
オペレーティングシステム
#3
高
0
優
先
度
SysVのスケジューリング
割
込
不
可
これらの
プロセスの実行中は
割り込み禁止
例)ディスク入出力待ち
他のリソースを確保してい
る可能性が高く,早く実行し
てやらないと他プロセスを
足止めする。
低 128
オペレーティングシステム
#3
高
0
SysVのスケジューリング
■
ユーザモード優先度

優
先
度



低 128
P_USER
+ NICE
+ P_CPU
P_USER
基準値 (=60)
NICE
ユーザ指定優先度
P_CPU
動的優先度
オペレーティングシステム
#3
高
■
0
ス
|
パ
バ
イ
ザ
優
先
度
P_USER



60
ユ
|
ザ
低 128
SysVのスケジューリング

ユーザモードプロセス
の基準値
必ずこの値よりも優先
度が低くなる
スーパバイザモードプ
ロセスとの境界
通常 60
オペレーティングシステム
#3
高
0
SysVのスケジューリング
■
NICE


優
先
度

60
低 128
ユーザが指定する
優先度
ユーザは実行するプロ
セスの優先度を下げ
ることができる
(基本的には)上げる
ことはできない
オペレーティングシステム
#3
高
0
SysVのスケジューリング
■
P_CPU

LOAD
➔

優
先
度
P_CPU
➔
60
低 128
■
過去にどれだけCPUを
割り当てられたか
前のP_CPU値
P_CPUt
= ½( P_CPUt-1
+ LOADt-1)
オペレーティングシステム
#3
■
LOAD値と過去のP_CPU値を
一定の割合で結合
■
LOAD値
■

直前のCPU割当状況から計算

変動:大
P_CPU値

過去の履歴を反映

変動:緩やか
P_CPU
オペレーティングシステム
#3
■
実際のOS (UNIX) の具体的実装例
■
UNIX SystemV
■

Solaris

AIX

HP-UX
Linux 2.6
オペレーティングシステム
#3
■
O(1)スケジューリング
オーダ1


問題サイズに関わらず,一定時間で処理できる
参考)O(n):オーダ n
問題サイズに比例して要する時間が増加:
例)待ちプロセス数が2倍になると,
プロセス決定に要する時間も2倍
オペレーティングシステム
#3
Linux 2.6 のスケジューリング
active
expired
高
CPU
優
先
度
低
オペレーティングシステム
#3
Linux 2.6 のスケジューリング
active
expired
高
CPU
優
先
度
低
クオンタムが残っている:
←activeへ
クオンタムを使い切った:
expiredへ→
オペレーティングシステム
#3
Linux 2.6 のスケジューリング
expired
active
expired
active
高
CPU
優
先
度
低
オペレーティングシステム
#3
まとめ
オペレーティングシステム
#3
■
FIFO (First In First Out)

■
優先度順スケジューリング
RR (Round Robin)

■
処理時間順スケジューリング
PS (Priority Scheduling)

■
到着順スケジューリング,FCFS
SPTF (Shortest Processing Time First)

■
まとめ:スケジューリング方式
ラウンドロビン
MLF (Multi-Level Feedback)

多重フィードバック
オペレーティングシステム
#3
■
■
まとめ:処理時間順
処理時間順スケジューリング

理論上,応答時間を最小にできる

実装が不可能
近似により処理時間順を実現

多重レベルフィードバック
オペレーティングシステム
#3
■
静的優先度

■
プロセス生成時に決定
動的優先度

■
まとめ:プロセス優先度
実行中に変化
優先度スケジューリング

優先度の低いプロセスがstarvationに陥る可能性

aging等で解決
ダウンロード

講義資料