オペレーティングシステム (プロセススケジューリング) 2009年10月8日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2009/

CPUプロセススケジューリング マルチプログラミングの概念 スケジューリングの必要性

CPUの数が限られている→切り替えて使う スケジューリングの必要性 CPUの数が限られている→切り替えて使う 割り当てを考えないといけない 実行の流れ(Thread of Execution)が複数存在 切り替えの時期を考えないといけない Non-Preemptive Multitasking プロセスが自主的に実行権を放棄 実行中のタスクは中断されない Preemptive Multitasking タイムスライスを使い切ったら実行権を放棄 自主的にプロセスが実行権を放棄することもできる 実行中のタスクの中断が許される

スケジューリングの基準 CPU動作時間 経過時間 CPU利用率 ロードアベレージ スループット タスクが実行中だった時間の合計 日常の時の進みの中での経過時間 CPU利用率 CPU動作時間÷システム稼働時間 ロードアベレージ 稼働時間ではなく、単位時間あたりのCPU利用率 スループット CPUが単位時間当たりに行う仕事量

スケジューリングの基準 ターンアラウンド時間 待ち時間 応答時間（レスポンスタイム） プロセスの実行要求から完了までの時間 実行可能状態から実行できるまでの時間 応答時間（レスポンスタイム） 実行要求から最初の応答が得られるまでの時間 UIにはこれが重要 イベント駆動による実装

Preemptive Multitasking スケジューリングアルゴリズム Preemptive Multitasking ラウンドロビンスケジューリング(到着型、FIFO型） タイムスライスを使い切ったら順番にCPUを割り当てる 優先度スケジューリング スケジューリング時に最も高い優先度のものへCPUを割当て 飢餓状態を防ぐためにエージングと併用 Non-Preemptive Multitasking FCFS(First Come First Service)スケジューリング 実行権を先に放棄したプロセスからCPUを割当て 長い処理のプロセスが先→平均ターンアラウンド時間が悪化 SJFスケジューリング 最も短いCPU処理時間であるプロセスからCPUを割当て FCFSスケジューリングの欠点を解消

ラウンドロビンスケジューリング タスク1 タスク1 タスク6 タスク6 タスク2 タスク2 実行可 タスク5 タスク5 タスク3 タスク3 タスク4 タスク4 実行中 タスク1 実行可 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 タスク2 実行可 タスク3 実行可 タスク4 実行可 タスク5 実行可 タスク6 実行可

優先度スケジューリング タスク1 タスク1 タスク6 タスク2 タスク2 実行可 タスク5 タスク3 タスク3 タスク4 タスク4 実行中 優先度10 タスク6 タスク2 タスク2 優先度５ 優先度10 実行可 タスク5 タスク3 タスク3 優先度５ 優先度９ タスク4 タスク4 優先度８ 実行中 消滅中 タスク1 実行可 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 消滅中 消滅中 実行中 実行可 消滅中 実行中 実行可 タスク2 実行可 タスク3 実行可 タスク4 実行可 タスク5 実行可 タスク6 実行可

FCFSスケジューリング タスク1 タスク1 実行可 タスク3 タスク3 タスク2 タスク2 実行中 タスク1 実行可 実行可 実行中 5 15 2 3 10 4

SJFスケジューリング タスク1 タスク1 実行可 タスク3 タスク3 タスク2 タスク2 実行中 タスク1 実行可 実行可 実行中 実行可 5 15 2 4 3 10 最も処理時間の短いタスクへ優先的にプロセッサを割り付ける。 処理時間はタスクが実行し終わらないとわからないので、ここでは過去の実行時間を利用

多重レベルスケジューリング

優先順位付きラウンドロビン 各タスクにはタイムスライスが与えられる。 スケジューラは実行可能タスクの優先度を見る 実行時間に制限が加わる タイムスライスを使い尽くしたら実行権が無くなる スケジューラは実行可能タスクの優先度を見る 最高優先度のタスクを実行する 同一優先度のタスクが複数あれば順番に実行 エイジングを導入して実行されないタスクをなくす 低優先度タスクは時間とともに優先度を一時的に上昇 優先度に応じてそれなりに実行されるようになる

優先順位付きラウンドロビン 優先順位ごとにキューを形成 キューごとにラウンドロビンでスケジューリング 低優先順位キューのタスクが実行されるのは、 より高い優先順位の実行可能タスクが無いとき →　スタベーション（飢餓）の発生 実行可状態で待っているとき、経過時間に応じて優先度を上げていく。 →　エージング

例：優先度スケジューリング タイムスライスごとにプリエンプション発生 タイムスライスごとに優先度が１上がる 実行中状態を経たら、優先度は初期値に戻る 初期優先度 タスク１ １０ タスク２ １０ タスク3 ９ タスク4 ８

優先順位つきラウンドロビン タスク1 タスク1 タスク4 タスク4 タスク2 タスク2 実行可 タスク3 タスク3 実行中 タスク2 優先度12 優先度10 優先度13 優先度10 優先度12 優先度11 優先度11 優先度10 優先度10 優先度11 優先度9 優先度13 優先度11 優先度8 優先度10 優先度９ 優先度8 優先度11 優先度9 優先度12 タスク1 タスク1 タスク4 タスク4 タスク2 タスク2 実行可 タスク3 タスク3 実行中 タスク2 タスク3 タスク1 タスク4 実行可 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中 実行可 実行中

ディスパッチャとは？ 記憶領域は各プロセスに持たせればよい。 演算器（加減算とか条件分岐とか）は共有できる。→これも問題無い。 CPU内部のレジスタ達は1組しかないし、演算データのような途中結果を保持している。実行を中断し、再開するときは、以前の状態にしておいてもらわないといけない。→問題だ。

CPU内部のレジスタ達 レジスタコンテキスト コンテキスト入れ替え コンテキストスイッチ [Intel, ``Software Developer Manual’’]

Intel系CPUでは、プロセス管理ブロックに含まれるデータのうち、レジスタコンテキスト [Intel, ``Software Developer Manual’’] Intel系CPUでは、プロセス管理ブロックに含まれるデータのうち、レジスタコンテキスト に関しては(TSSという名前で管理されている)、プロセッサが入れ替えてくれる。 言い換えれば、レジスタコンテキスト(TSS)のスイッチはプロセッサがサポートしている。 TSSを参照するFARジャンプ命令一発でコンテキストスイッチが起こる。