Operating System プロセスのスケジューリング

プロセスのスケジューリング

2015-06

プロセスとは（復習）

p 

プロセス（

process）とは

n  起動して“実行中”のプログラム n  コンピュータの中で“動いているもの”（CPUを使っているもの） n  「タスク」（task）ともいう p 

OSによるプロセスの管理

n  プロセスの生成（プログラムの開始とメモリ確保） n  プロセスの消滅（プログラムの停止とメモリ開放） n  プロセスの切り替え，優先順位の管理，などなど… p 

プロセスの“正体”を，よりハードウェア的に考えると

…

n  「動いている」or「実行中」 ＝ CPUで演算処理をしている n  プログラムとデータがある ＝ メモリの領域を占めている

マルチタスク（マルチプロセス）

p 

マルチタスクとは？

n  1つのCPUで複数のプログラムを（見かけ上）“同時に”実行させる n  前のプログラムが終わっていなくても，新しいプログラムを起動できる p 

マルチタスクの基本アイデア

n  あるプログラムがディスクの入出力などを待っているあいだは，別の プログラムが空いているCPUを使えるようにする n  プロセスを非常に高速なタイムスライス（ミリ秒単位）で切り替えて， 同時に実行しているように見せかける プロセスA プロセスB プロセスC プロセスD 入出力待ちや時間 切れで一時停止

マルチタスクの利点

p 

実行効率の向上

n  CPUの時間を，無駄なく有効に活用できる n  OSカーネルやデバイスドライバの機能も実現しやすい p 

マルチユーザ機能

n  複数のユーザがコンピュータを利用するようなサーバが実現できる n  1人での使用でも，同時に複数のソフトウェアを使えるようになる p 

多様な機能のプロセス

n  バックグラウンド（裏）で動作し続けるような処理が実現できる n  あるプロセスを実行中に，それより優先度の高いプロセスが発生した 場合，中断して対応できる n  指定時間に自動的に起動するプログラムなどが作りやすい

マルチタスクの種類

p 

ノンプリエンプティブなマルチタスク

n  別名： 協調型マルチタスク，疑似マルチタスク n  OSがCPUの時間管理をしない n  各プロセスは，適当なタイミングで自主的・明示的にCPUの使用権を 次のプロセスに譲らなければならない n  OSは実行中のプロセスからCPUを横取り（プリエンプション）できない n  プロセスは，システムコール（API）で自主的に実行権を手放す n  例： 16bit時代のWindowsやMacintosh p 

プリエンプティブなマルチタスク

n  本来のマルチタスク n  OSがタイマー割り込みを利用してCPUの時間管理をする n  OSは，所定のタイムスライス（ミリ秒単位）ごとに，実行中のプロセス からCPUを横取り（プリエンプション）して，次のプロセスを切り替える

プロセスの状態遷移

p 

マルチタスクにおけるプロセスの一生

n  単純なOSの例

実行可能状態 Ready 実行状態 Run 待ち状態 Wait 事象の発生 事象（割り込みなど） の発生待ち プリエンプション （横取り・交替） ディスパッチ （割り当て） 消滅（終了） 生成 （メモリ割り当て）

UNIX/Linuxの状態遷移

実行可能状態 （CPUの空き待ち） 実行状態 （CPUを占有） 待ち状態 事象の発生 事象（入出力割り込み等） の発生待ち プリエンプション （横取り・交替） ディスパッチ （割り当て） 終了 生成 （メモリ割り当て） ゾンビ状態 （結果だけ保持） 消滅 停止状態 （休眠状態） ユーザや他の プロセスからの停止 停止解除 （システムコール）

実行プロセスの切り替え

p 

Run → Ready

n  OSが現在のプロセスを中断し，順番を次にまわす（プリエンプション） p 

Run → Wait

n  プロセスがデバイスなどの応答待ちに入って中断する p 

Ready → Run

n  OSがCPUに新しいプロセスを割り当てる（ディスパッチ） n  キュー（待ち行列）で順番を管理 p 

スケジューリング

n  CPUでプロセスを実行する時間（順番）を管理すること n  優先するプロセスを早く実行させたり，順番と時間を管理する n  用途に応じた様々なスケジューリングアルゴリズムがある

プロセスキュー

p 

プロセスの実行順序をどうやって管理しているか

n  プロセスキュー＝カーネル内にあるプロセスの順番表 n  プロセス制御ブロックへのポインタが，実行順につながれている 実行中 プロセス プロセス プロセス プロセス プロセス プロセス プロセス プロセス プロセス プロセス プロセス プロセス 優先度 高 優先度 低 待ちキュー 実行可能 キュー

キュー

（

_Queue）

p 

キュー（

Queue）とは

n  「待ち行列」と訳される （代数学の行列（matrix）とは無関係） n  何かを待っている行列を表すデータ構造 n  □ ← ● ● ● ● ● ● ● ● ●　（スーパーのレジなど） p 

FIFO（先入先出方式）

n  First In First Out

n  基本的には，先着順に処理されるデータ構造

n  反対： LIFO （Last In First Out） ＝ スタック　

p 

実行可能キュー（

OS用語）

n  別名「レディキュー」「ランキュー」

マルチタスクの実現方法

p 

メモリはプロセスごとに分割できる

n  メモリは番地があって土地みたいなもの n  複数のプログラムを，主記憶に同時に読み 込んでおくことは容易 p 

しかし，

CPUは分割できない

n  1つのCPUコアが実行できる命令は1つ n  実行プロセスを，高速に次々と切り替える 機能が必要になる p 

コンテクストスイッチ（文脈切り替え）

n  実行プロセスのコンテクスト（途中経過）を カーネル内に一時退避し， n  退避してあった別のプロセスのコンテクスト プロセスA プロセスB OS（カーネル） 空き ... CPU 実行中

12 プロセスの「実行コンテクスト」 （実行文脈）という

実行コンテクスト

コード領域 プログラム本体 静的データ領域 空き スタック領域 （一時変数） ヒープ領域 プロセス空間（プロセスに割り当てられたメモリ空間） 実行中のCPUの状態 汎用レジスタ1 　値1 汎用レジスタ2 　値2 汎用レジスタ3 　値3 ・・・ プログラムカウンタ 　番地A スタックポインタ 　番地B フラグレジスタ 　フラグ状態 番地A 番地B 現在実行 中の命令 スタック のトップ

プロセス

スケジューリング

p 

スケジューリングとは

n  スケジューリング ＝ スケジュールを決める n  CPUでプロセスを実行する時間（順番）を管理すること n  用途に応じた様々なスケジューリングアルゴリズムがある p 

スケジューリングの目的

n  CPUの利用効率をより高める n  人間等への応答時間をよくする n  仕事の優先度（緊急度）を反映させる p 

プリエンプション（横取り）

n  OSが実行プロセス（CPU利用）を強制的に切り替えること n  多くのスケジューリングアルゴリズムは，プリエンプションが前提

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

p 

先着順スケジューリング

n  FCFS: First Come First Service

p 

最短時間順スケジューリング

n  SJF: Shortest Job First

p 

実行期限順スケジューリング

n  EDF: Earliest Deadline First

p 

優先度スケジューリング

p 

ラウンドロビンスケジューリング

先着順スケジューリング

p 

FCFSスケジューリング

n  First Come First Service

n  最初に来たプロセスから，最初にサービスを受ける p 

プリエンプションの有無

n  なし ⇒ 基本的にはシングルタスクのための単純なスケジューリング p 

現実にたとえてみると

…

n  ゲームセンターで，ゲーム機に早く並んだ人から順にゲームができる n  前の人が終わるまで，次の人はずっと待っている p 

特徴

n  原理が単純で，実現が容易である n  問題点は？

最短時間順スケジューリング

p 

SJFスケジューリング

n  Shortest Job First

n  最も短い時間で終わる仕事から順番にやる

p 

プリエンプションの有無

n  基本的には，なし （いったん始めたプロセスは中断しない）

n  プリエンプション有りに改良 ⇒ Shortest Remaining Time First

p 

現実世界にたとえてみると

…

n  量の少ない宿題から早く片付ける

p 

特徴

n  利点： プロセスの平均待ち時間が最小になる

実行期限順スケジューリング

p 

EDFスケジューリング

n  Earliest Deadline First

n  “締め切り”が一番近いプロセスから実行する p 

プリエンプション

n  より締め切りの近いプロセスが発生したら，それに切り替わる p 

現実社会にたとえてみると

…

n  出発時刻の早い飛行機の人から，優先的に搭乗手続きをする p 

特徴

n  ロボットの制御など，リアルタイム（実時間）で動くシステム向け n  実装が難しく，全体として最悪のケースが予測しにくい n  その他？

優先度スケジューリング

p 

優先度スケジューリング

n  設定された優先度が高いプロセスから実行する n  優先度が同じ場合は，FCFSなど他のスケジューリングで割り当てる p 

プリエンプション

n  より優先度の高いプロセスが発生したら，それに切り替わる p 

現実社会にたとえてみると

n  社員食堂に並んでいて，上司が来たら順番を譲らなければならない p 

特徴

n  リアルタイムOS向き （ITRONはFCFS＋優先度） n  いつまでも後回しになるかわいそうなプロセスが発生 ＝ 飢餓状態

ラウンドロビンスケジューリング

p 

Round-Robinスケジューリング

n  タイマー割り込みを利用し，全プロセスを一定時間のタイムスライス （数十～数百ミリ秒）で切り替えて少しずつ順に実行していく n  「持ち回り」のことを英語ではRound-robinという p 

プリエンプション

n  タイムスライスが経過したプロセスは横取りされ，次に順番を譲る p 

特徴

n  平等・均一で，人間相手のシステムに向いている p 

優先度つきラウンドロビン

n  UNIX，Linux，Windows等ではRRに優先度を組み合わせている

演習課題（後日提出）

p 

課題

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

n  学校で以下のような宿題が出された。 n  これらをOSの「FCFS」，「SJF」，「EDF」，「ラウンドロビン」の各方式 と同様な考え方でスケジューリングすると，どのような順序に処理して どのような結果になるか説明しなさい。 科目 出題日 締め切り かかる時間 A 6月1日 6月11日 5日間 B 6月2日 6月30日 7日間 C 6月4日 6月15日 3日間 D 6月5日 6月8日 1日間 n  問題の単純化のため，1日に取り組める宿題の数は1つだけとする。 n  また，宿題は出題されたその日から取り組めるものとする。

演習課題（後日提出）

p 

課題

6b HOSにおけるFCFS+優先度スケジューリング

n  この課題の狙いは，実際のプログラミングによって，FCFSスケジュー リングと優先度スケジューリングの仕組みを理解することである。 n  HOSはシンプルな組み込みOSなので，基本的なスケジューリングは， FCFS（先着順）と優先度によるものである。 n  FCFSはタスクの起動順，優先度はタスクの設定情報によって決まる。 p 

手順

n  sample\win-scheduling を（そのまま）実行する。 n  実行結果を示し，なぜそのような動作するのか，スケジューリングの 観点から考察（理由を説明）せよ。 n  各タスクの優先度や start 関数での実行順序を変更していくつかの 組み合わせを試し，それらの効果について考察せよ。

演習課題（後日提出）

p 

課題

6c HOSにおけるノンプリエンプティブなマルチタスク

n  この課題の狙いは，ノンプリエンプティブな（協調的な）マルチタスクの 動作とそのためのプログラミング作法を理解することである。 n  プリエンプティブでないOSでは，プロセス（タスク）が適当なタイミング で自主的に実行権を手放すことで円滑なマルチタスクを実現する。 n  HOSの場合，レディーキューを回して次のタスクを実行する rot_rdq

（rotate ready queue）というサービスコール（API）を利用する。

p 

手順

n  課題6bで変更した sample\win-scheduling を元に戻す。 n  ソースコードでコメントアウトされている各タスクの rot_rdq 関数を有 効にし，タスクが自主的に実行権を次のタスクに譲るようにせよ。 n  実行結果を示し，なぜそのような動作するのか，スケジューリングの 観点から考察（理由を説明）せよ。

演習課題（後日提出）

p 

課題

6d HOSにおけるラウンドロビンスケジューリング

n  この課題の狙いは，ラウンドロビンスケジューリングによるプリエンプ ティブな（真の）マルチタスクの仕組みを理解することである。 n  ラウンドロビンスケジューリングでは，OSが一定周期で実行プロセス を順番に（かつ強制的に）切り替えていく必要がある。 n  そのためにタイマー割り込みでスケジューラーを駆動し，プロセスの 切り替えを行う。HOSでは割り込み対応版の irot_rdqを使う。 p 

手順

n  課題6cで変更した sample\win-scheduling を元に戻す。 n  （擬似）タイマー割り込み処理である ostimer.c の中でコメントアウト されている if 文と irot_rdq の部分を有効にして実行する。 n  実行結果を示し，なぜそのような動作するのか，スケジューリングの

次回：小テストとプログラミング実習

p 

小テスト（

45分？）

n  第1回〜第6回に関する知識・用語問題 p 

プログラミング実習

n  第1回〜第6回の演習課題の解説と実習 n  レポート提出はその次の回

HOS（μ

ITRON

）のタスク管理

サービスコール 意味 説明

cre_tsk create task タスクの生成

acre_tsk 同上（ID自動割り当て）

act_tsk activate task タスクの起動

iact_tsk 同上（割り込み用）

can_act cancel activation タスク起動予約の取り消し ext_tsk exit task 自タスクの終了

ter_tsk terminate task タスクの強制終了 chg_pri change priority タスク優先度の変更 get_pri get priority タスク優先度の参照 rot_rdq rotate ready queue 実行可能キューの回転 irot_rdq

HOS（μ

ITRON

）のタスク管理

サービスコール 意味 説明

dly_tsk delay task 自タスクの遅延

slp_tsk sleep task 自タスクの休止（起床要求待ち）

tslp_tsk 同上（タイムアウトあり）

wup_tsk wake up task タスク起床要求

iwup_tsk 同上（割り込み用）

can_wup cancel wakeup タスク起床要求の取り消し rel_wai release wait 待ち状態の強制解除

irel_wai 同上（割り込み用）

sus_tsk suspend task 強制待ち状態への以降 rsm_tsk resume task 強制待ち状態からの再開