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

Operating System プロセスのスケジューリング 2015-06 1

プロセスとは ( 復習 ) p プロセス (process) とは n 起動して 実行中 のプログラム n コンピュータの中で 動いているもの (CPU を使っているもの ) n タスク (task) ともいう p OS によるプロセスの管理 n プロセスの生成 ( プログラムの開始とメモリ確保 ) n プロセスの消滅 ( プログラムの停止とメモリ開放 ) n プロセスの切り替え, 優先順位の管理, などなど p プロセスの 正体 を, よりハードウェア的に考えると n 動いている or 実行中 = CPU で演算処理をしている n プログラムとデータがある = メモリの領域を占めている 2

マルチタスク ( マルチプロセス ) p マルチタスクとは? n 1 つの CPU で複数のプログラムを ( 見かけ上 ) 同時に 実行させる n 前のプログラムが終わっていなくても, 新しいプログラムを起動できる p マルチタスクの基本アイデア n あるプログラムがディスクの入出力などを待っているあいだは, 別のプログラムが空いているCPUを使えるようにする n プロセスを非常に高速なタイムスライス ( ミリ秒単位 ) で切り替えて, 同時に実行しているように見せかける入出力待ちや時間プロセスA 切れで一時停止 プロセス B プロセス C プロセス D 起動 時間 終了 3

マルチタスクの利点 p 実行効率の向上 n CPU の時間を, 無駄なく有効に活用できる n OS カーネルやデバイスドライバの機能も実現しやすい p マルチユーザ機能 n 複数のユーザがコンピュータを利用するようなサーバが実現できる n 1 人での使用でも, 同時に複数のソフトウェアを使えるようになる p 多様な機能のプロセス n バックグラウンド ( 裏 ) で動作し続けるような処理が実現できる n あるプロセスを実行中に, それより優先度の高いプロセスが発生した場合, 中断して対応できる n 指定時間に自動的に起動するプログラムなどが作りやすい 4

マルチタスクの種類 p ノンプリエンプティブなマルチタスク n 別名 : 協調型マルチタスク, 疑似マルチタスク n OS が CPU の時間管理をしない n 各プロセスは, 適当なタイミングで自主的 明示的に CPU の使用権を次のプロセスに譲らなければならない n OS は実行中のプロセスから CPU を横取り ( プリエンプション ) できない n プロセスは, システムコール (API) で自主的に実行権を手放す n 例 : 16bit 時代の Windows や Macintosh p プリエンプティブなマルチタスク n 本来のマルチタスク n OS がタイマー割り込みを利用して CPU の時間管理をする n OS は, 所定のタイムスライス ( ミリ秒単位 ) ごとに, 実行中のプロセスから CPU を横取り ( プリエンプション ) して, 次のプロセスを切り替える n 例 : 現代のほとんどのコンピュータ 5

プロセスの状態遷移 p マルチタスクにおけるプロセスの一生 n 単純な OS の例 事象の発生 待ち状態 Wait 事象 ( 割り込みなど ) の発生待ち 生成 ( メモリ割り当て ) 実行可能状態 Ready ディスパッチ ( 割り当て ) プリエンプション ( 横取り 交替 ) 実行状態 Run 消滅 ( 終了 ) 6

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

実行プロセスの切り替え p Run Ready n OS が現在のプロセスを中断し, 順番を次にまわす ( プリエンプション ) p Run Wait n プロセスがデバイスなどの応答待ちに入って中断する p Ready Run n OSがCPUに新しいプロセスを割り当てる ( ディスパッチ ) n キュー ( 待ち行列 ) で順番を管理 p スケジューリング n CPUでプロセスを実行する時間 ( 順番 ) を管理すること n 優先するプロセスを早く実行させたり, 順番と時間を管理する n 用途に応じた様々なスケジューリングアルゴリズムがある 8

プロセスキュー p プロセスの実行順序をどうやって管理しているか n プロセスキュー = カーネル内にあるプロセスの順番表 n プロセス制御ブロックへのポインタが, 実行順につながれている 優先度高 実行中プロセス プロセス 実行可能キュー プロセスプロセスプロセスプロセス 優先度低 プロセス プロセス 待ちキュー プロセスプロセスプロセスプロセス 9

キュー (Queue) p キュー (Queue) とは n 待ち行列 と訳される ( 代数学の行列 (matrix) とは無関係 ) n 何かを待っている行列を表すデータ構造 n ( スーパーのレジなど ) p FIFO( 先入先出方式 ) n First In First Out n 基本的には, 先着順に処理されるデータ構造 n 反対 : LIFO (Last In First Out) = スタック p 実行可能キュー (OS 用語 ) n 別名 レディキュー ランキュー n CPU の空きを待っている実行可能状態のプロセスの待ち行列 10

マルチタスクの実現方法 p メモリはプロセスごとに分割できる n メモリは番地があって土地みたいなもの n 複数のプログラムを, 主記憶に同時に読み込んでおくことは容易 p しかし,CPU は分割できない n 1 つの CPU コアが実行できる命令は 1 つ n 実行プロセスを, 高速に次々と切り替える機能が必要になる CPU 実行中 OS( カーネル ) プロセス A プロセス B p コンテクストスイッチ ( 文脈切り替え ) n 実行プロセスのコンテクスト ( 途中経過 ) をカーネル内に一時退避し, n 退避してあった別のプロセスのコンテクストを読み出して中断したところから続行する... 空き メモリマップ 11

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

プロセススケジューリング p スケジューリングとは n スケジューリング = スケジュールを決める n CPUでプロセスを実行する時間 ( 順番 ) を管理すること n 用途に応じた様々なスケジューリングアルゴリズムがある p スケジューリングの目的 n CPUの利用効率をより高める n 人間等への応答時間をよくする n 仕事の優先度 ( 緊急度 ) を反映させる p プリエンプション ( 横取り ) n OSが実行プロセス (CPU 利用 ) を強制的に切り替えること n 多くのスケジューリングアルゴリズムは, プリエンプションが前提 13

スケジューリングアルゴリズム p 先着順スケジューリング n FCFS: First Come First Service p 最短時間順スケジューリング n SJF: Shortest Job First p 実行期限順スケジューリング n EDF: Earliest Deadline First p 優先度スケジューリング p ラウンドロビンスケジューリング n RR: Round-robin 14

先着順スケジューリング p FCFS スケジューリング n First Come First Service n 最初に来たプロセスから, 最初にサービスを受ける p プリエンプションの有無 n なし 基本的にはシングルタスクのための単純なスケジューリング p 現実にたとえてみると n ゲームセンターで, ゲーム機に早く並んだ人から順にゲームができる n 前の人が終わるまで, 次の人はずっと待っている p 特徴 n 原理が単純で, 実現が容易である n 問題点は? 15

最短時間順スケジューリング p SJF スケジューリング n Shortest Job First n 最も短い時間で終わる仕事から順番にやる p プリエンプションの有無 n 基本的には, なし ( いったん始めたプロセスは中断しない ) n プリエンプション有りに改良 Shortest Remaining Time First p 現実世界にたとえてみると n 量の少ない宿題から早く片付ける p 特徴 n 利点 : プロセスの平均待ち時間が最小になる n 問題点? 所要時間は実行前に見積もれないことが多い 16

実行期限順スケジューリング p EDF スケジューリング n Earliest Deadline First n 締め切り が一番近いプロセスから実行する p プリエンプション n より締め切りの近いプロセスが発生したら, それに切り替わる p 現実社会にたとえてみると n 出発時刻の早い飛行機の人から, 優先的に搭乗手続きをする p 特徴 n ロボットの制御など, リアルタイム ( 実時間 ) で動くシステム向け n 実装が難しく, 全体として最悪のケースが予測しにくい n その他? 17

優先度スケジューリング p 優先度スケジューリング n 設定された優先度が高いプロセスから実行する n 優先度が同じ場合は,FCFSなど他のスケジューリングで割り当てる p プリエンプション n より優先度の高いプロセスが発生したら, それに切り替わる p 現実社会にたとえてみると n 社員食堂に並んでいて, 上司が来たら順番を譲らなければならない p 特徴 n リアルタイムOS 向き (ITRONはFCFS+ 優先度 ) n いつまでも後回しになるかわいそうなプロセスが発生 = 飢餓状態 18

ラウンドロビンスケジューリング p Round-Robin スケジューリング n タイマー割り込みを利用し, 全プロセスを一定時間のタイムスライス ( 数十 ~ 数百ミリ秒 ) で切り替えて少しずつ順に実行していく n 持ち回り のことを英語では Round-robin という p プリエンプション n タイムスライスが経過したプロセスは横取りされ, 次に順番を譲る p 特徴 n 平等 均一で, 人間相手のシステムに向いている p 優先度つきラウンドロビン n UNIX,Linux,Windows 等では RR に優先度を組み合わせている 19

演習課題 ( 後日提出 ) 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 また, 宿題は出題されたその日から取り組めるものとする 20

演習課題 ( 後日提出 ) p 課題 6b HOS における FCFS+ 優先度スケジューリング n この課題の狙いは, 実際のプログラミングによって,FCFS スケジューリングと優先度スケジューリングの仕組みを理解することである n HOS はシンプルな組み込み OS なので, 基本的なスケジューリングは, FCFS( 先着順 ) と優先度によるものである n FCFS はタスクの起動順, 優先度はタスクの設定情報によって決まる p 手順 n sample\win-scheduling を ( そのまま ) 実行する n 実行結果を示し, なぜそのような動作するのか, スケジューリングの観点から考察 ( 理由を説明 ) せよ n 各タスクの優先度や start 関数での実行順序を変更していくつかの組み合わせを試し, それらの効果について考察せよ 21

演習課題 ( 後日提出 ) p 課題 6c HOS におけるノンプリエンプティブなマルチタスク n この課題の狙いは, ノンプリエンプティブな ( 協調的な ) マルチタスクの動作とそのためのプログラミング作法を理解することである n プリエンプティブでない OS では, プロセス ( タスク ) が適当なタイミングで自主的に実行権を手放すことで円滑なマルチタスクを実現する n HOS の場合, レディーキューを回して次のタスクを実行する rot_rdq (rotate ready queue) というサービスコール (API) を利用する p 手順 n 課題 6b で変更した sample\win-scheduling を元に戻す n ソースコードでコメントアウトされている各タスクの rot_rdq 関数を有効にし, タスクが自主的に実行権を次のタスクに譲るようにせよ n 実行結果を示し, なぜそのような動作するのか, スケジューリングの観点から考察 ( 理由を説明 ) せよ 22

演習課題 ( 後日提出 ) p 課題 6d HOS におけるラウンドロビンスケジューリング n この課題の狙いは, ラウンドロビンスケジューリングによるプリエンプティブな ( 真の ) マルチタスクの仕組みを理解することである n ラウンドロビンスケジューリングでは,OS が一定周期で実行プロセスを順番に ( かつ強制的に ) 切り替えていく必要がある n そのためにタイマー割り込みでスケジューラーを駆動し, プロセスの切り替えを行う HOS では割り込み対応版の irot_rdq を使う p 手順 n 課題 6c で変更した sample\win-scheduling を元に戻す n ( 擬似 ) タイマー割り込み処理である ostimer.c の中でコメントアウトされている if 文と irot_rdq の部分を有効にして実行する n 実行結果を示し, なぜそのような動作するのか, スケジューリングの観点から考察 ( 理由を説明 ) せよ 23

次回 : 小テストとプログラミング実習 p 小テスト (45 分?) n 第 1 回 第 6 回に関する知識 用語問題 p プログラミング実習 n 第 1 回 第 6 回の演習課題の解説と実習 n レポート提出はその次の回 24

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 同上 ( 割り込み用 ) 25

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 強制待ち状態からの再開 frsm_tsk force resume task 強制待ち状態からの強制再開 26