CPUスケジューリング

多重プログラミングの概念



CPUを無駄なく使いたい

開始 遊休状態： 入力 ジョブA 遊休状態： 入力 開始 遊休状態： 入力 ジョブB 遊休状態： 入力 図４．１ 二つの上部Ａ，Ｂの実行 停止 停止 2

図４．２ 多重プログラミング機構のない場合のジョブ実行 開始 遊休状態： 入力 ジョブA 遊休状態： 入力 停止 開始 遊休状態： 入力 ジョブB 遊休状態： 入力 停止 待 ち

多重プログラミングの概念

開始 遊休状態： _入力 ジョブA 遊休状態： 入力 停止 開始 遊休状態： 入力 ジョブB 遊休状態： 入力 停止

プロセスとは？



厳密な概念はない！ 定義は困難



あえて言うと，プロセスとは下記の２つの定義？あり

１）実行しているプログラム

２）疑似プロセッサ

プログラムを実行するための器

その他，ユーザの代理という概念？もあり．

OSが管理するための単位

プロセスのことをタスクとも言う．

4

プロセスの状態

活動中 新規 待機中 停止 図４．６ プロセス状態遷移図 実行中 新規 待機中 実行待ち 停止

プロセス制御ブロック（PCB: Process Control Block）



プロセスに関する情報を格納しておく器



必要な情報（詳細はOS，ハードウェアによって異なる）

 プロセスの状態

 新規，実行待ち，実行中，．．．

 プログラムカウンタ

 レジスタの内容

 レジスタの種類はプロセッサによって異なる．

 メモリ管理情報

 上限／下限レジスタ，ページ表（ページングシステ ム），．．

 課金情報

 CPU使用時間，実使用時間，課金番号，ジョブ番号，．．

 入出力情報

 未完了の入出力要求，割当てられている入出力装置， オープンされているファイル，．．

 CPUスケジューリング情報

 プロセスの優先度，レディキューへのポインタ，．．． プログラムカウンタ レジスタ類 開かれたファイルのリスト 記憶範囲 プロセス番号 プロセス 状態 ポインタ ・ ・ ・ 図４．８ プロセス制御ブロック 6

コンテキスト（context）とは？

コンテキストスイッチ：プログラムの切り替え

レジスタ退避 ・ ・ ・ レジスタ復元 レジスタ退避 ・ ・ ・ レジスタ復元 利用者プログラムA オペレーティングシステム 利用者プログラムB 割込みまたはスーパバイザコール 割込みまたはスーパバイザコール 実行状態 実行状態 実行状態 遊休状態 遊休 状態 遊休 状態 図４．９ 利用者間でのCPUの切り替え 8

スケジューリングのためのキュー（１／２）



レディキュー（Ready queue，実行待ち列）

実行可能状態のプロセスをつないでおくキュー



デバイスのためのキュー（デバイスキュー，装置待

ち列）

装置が空くのを待っているプロセスのキュー

図４．１０ 実行待ち列と種々の入出力装置待ち列（図：準備中_）

スケジューリングのためのキュー（２／２）

図４．１２ 単純化した待ち列図式（図：準備中_）

図４．１１ CPUスケジューリングの待ち列図式表現（図：準備中_）

スケジューラ

ースケジューラの種類ー



長期スケジューラ（Long term scheduler, ジョブスケジューラ）

 システムで処理すべきジョブを選択

 複数（多重度）のジョブを選択

 メモリにロード



短期スケジューラ（short term scheduler，CPUスケジューラ）

 実際にCPUに割当てるジョブを選択

 選択するのは１つのみ



中期スケジューラ（medium term scheduler）（ないOSもある）

 多重度の制御

 プロセスをシステムから取り除く．

ディスパッチャ（dispatcher）



CPUスケジューラで選択されたプロセスにCPUを実際

に割当てるプログラムのこと．OSの一部．



仕事

プログラムカウンタの設定，レジスタ内容のロード，

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

12

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



評価基準： 何を目標にするか？



_CPU使用率



スループット（throughput）

 単位時間当りに完了したジョブ数 

ターンアラウンド時間（turnaround time）

 ジョブ投入からジョブ完了までにかかった時間 

待ち時間（waiting time）

 レディキューにいる時間 

応答時間（response time）

 会話型システム：コマンド投入からプロンプトが帰ってくるまでの時間 

理想



_{CPU使用率，スループット → 最大}



ターンアラウンド時間，待ち時間，応答時間 → 最小

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



横取りのない(non-preemptive)アルゴリズム



先着順サービス方式（FCFS, First-Come-First-Served）



最短ジョブ優先方式



優先度方式



横取りのある（preemtive）アルゴリズム

ラウンドロビン（Round-Robin，巡回方式）

多重レベル待ち列（Multi-queue scheduling）

多重レベルフィードバック列（Multi-level feedback

queue）

14

横取りのない(non-preemptive)アルゴリズム



先着順サービス方式（FCFS, First-Come-First-Served）



最短ジョブ優先方式

先着順サービス方式（FCFS, First-Come-First-Served）

ジョブ バースト時間 １ ２４ ２ ３ ３ ３ 到着した順番に実行する． 例 ジョブ２ ジョブ１ ジョブ３ ０ ２４ ２７ ３０ ガント図 時刻０でほとんど同時にジョブ１，２，３が到着したが， ジョブ１，ジョブ２，ジョブ３の順で到着した場合： ジョブ２ ジョブ３ ジョブ１ ０ ３ ６ ３０ 時刻０でほとんど同時にジョブ１，２，３が到着したが， ジョブ２，ジョブ３，ジョブ１の順で到着した場合： 平均ターンアラウンド時間＝（２４＋２７＋３０）／３ ＝ _２７ 平均ターンアラウンド時間＝（３０＋３＋６）／３ ＝ _１３ ガント図 16

最短ジョブ優先方式

ジョブ バースト時間 １ ６ ２ ３ ３ ８ ４ ７ 実行時間の短い順に実行する． 理論的に最小の待ち時間を与える． 仮定：横取りがない． 例 ガント図 時刻０でほとんど同時にジョブ１，２，３，４が到着した場合． ジョブ２ ジョブ１ ジョブ３ ０ ３ ９ １６ ２４ ジョブ４

優先度方式（priority scheduling）



プロセスに優先度を付けて，優先度順に実行する．

横取りのある（preemtive）アルゴリズム



横取りのある最短ジョブ優先方式



ラウンドロビン（Round-Robin，巡回方式）



多重レベル待ち列（Multi-queue scheduling）



多重レベルフィードバック列（Multi-level feedback

queue）

横取りのある最短ジョブ優先方式

ジョブ 到着時刻 バースト時間 １ ０ ８ ２ １ ４ ３ ２ ９ ４ ３ ５ 最小残り時間優先方式（Shortest-Remaining-Time-First）とも言う． 例 ガント図 _{ジョブ２ ジョブ１ ジョブ３} ０ １ ５ ２６ 平均ターンアラウンド時間 ＝（（１７－０）＋（５－１）＋（２６－２）＋（１０－３））／４ ＝ １３ １０ ジョブ４ １７ 横取り ジョブ１ 横取りのない最短ジョブ優先方式の場合： 平均ターンアラウンド時間 ＝ ５７／４ ＝ １４．２５ 20

ラウンドロビン（Round-Robin，巡回スケジューリング）（１／３）

ジョブ バースト時間 １ ２４ ２ ３ ３ ３ 一定時間CPUを割り当てる． 一定時間： タイムスライス（time-slice， 量子時間） 終了しなければ，次に回す（レディキューの最 後尾につなぐ） 例 ジョブ２ ジョブ１ ジョブ３ ０ ２６ ３０ ガント図 平均ターンアラウンド時間＝４７／３ ＝ １６ ２２ １０ １４ ４ ７ １８ ジョブ１ ジョブ１ _ジョブ１ ジョブ１ ジョブ１ 下記は，タイムスライス＝４の場合のガント図 仮定：時刻０で，ジョブ１，２，３の順で到着 タイムスライスについて タイムスライス → ∞ ： FCFS（先着順サービス）

ラウンドロビン（Round-Robin，巡回スケジューリング）（２／３）

ジョブ バースト時間 １ １３ ２ ６ ３ １１ 例の追加（右表） 例 ジョブ２ ジョブ１ ジョブ３ ０ ２６ ３０ ガント図 平均ターンアラウンド時間＝（３０＋１８＋２９）／３ ＝ ７７／３ ２２ １２ １６ ４ ８ １８ ジョブ３ ジョブ１ _２ ジョブ１ ジョブ３ 下記は，タイムスライス＝４の場合のガント図 仮定：時刻０で，ジョブ１，２，３の順で到着 ２９ １ 22

ラウンドロビン（Round-Robin，巡回スケジューリング）（３／３）

■タイムスライスの終了時の処理 プロセスの入れ替え： コンテキストスイッチング（Context switching） コンテキストの入れ替え 古い（今実行していた）プロセスのレジスタ内容を退避 新しいプロセスのレジスタ内容をレジスタにロード オーバヘッドが生じる タイムスライスを短くするとコンテキストのオーバヘッドが大 図４．１６ 状態切換えを増加させるより小さな量子時間（タイムスライス）値（図：準備中_）

多重レベル待ち列

 タイプの異なるジョブ  フォアグランドジョブ（foreground，会話的ジョブ等）  バックグランドジョブ（background，バッチ等）  キュー毎に異なるスケジューリングアルゴリズム  _{CPUの割当方法：優先度，時間配分} システムタスク 会話型 編集 バッチ 学生バッチ 最高優先度 最高優先度 図４．１８ 多重待ち列スケジューリング方式 24

多重レベルフィードバック列

 キュー間の移動を許す．  自由度の高いスケジューリング  パラメータ  キューの数  各キューのスケジューリングアルゴリズム  移動の決定方策  最初に入れるキューの決定方法  パラメータの決定が困難 キュー２ キュー１ キュー０ タイムスライス＝１６ タイムスライス＝８

アルゴリズムの評価手法



解析的評価

決定性モデル

ジョブの振る舞いが決定的

確率的モデル

ジョブの振る舞いが確率的

待ち行列理論（Queueing theory）



シミュレーション

26