計算機システム概論・２回目 本日のトピック：プロセスについて プロセスとは プロセスのスケジューリングについて 多重プロセスの問題 排他制御 プロセス間通信

前回の復習：時分割処理 時分割処理（タイムシェアリング） プロセッサが，複数のプログラムを少しずつ実行する 短い時間（タイムスライス）で，プログラムを切替える 時間経過 遂次処理 時分割処理 仮想計算機 実際の 計算機 考え方次第では... ユーザに仮想計算機を割り当て， 仮想計算機の動作を，少しずつ シミュレートして進めていく

シミュレートとは シミュレート ＝ 模擬，真似 仮想計算機をシミュレートするとは... 計算機の中に別の仮想計算機（Ｖ）があると想定する Ｖは独自のプログラムを持っている Ｖがどのような振る舞いをするか，Ｖのプログラムに 従って（外部の計算機）が計算する （必要であれば）ユーザとＶと の間で，入出力の中継を行う Ｖ

仮想計算機とプロセス 仮想計算機が保持すべきもの 独自のプログラム 独自のメモリ状態 独自のレジスタ状態 独自の入出力管理状態 その仮想計算機の状態 その仮想計算機のユーザ名 他の仮想計算機との関係 ： プロセス＝仮想計算機 （他の意味づけも可能） 仮想計算機 実際の 計算機 プロセス

プロセスを「見る」 身近なＯＳで，実際にプロセスを見てみる Windows： タスクマネージャを起動 UNIX系OS: ps コマンドを利用 確認できること 多くのプロセスが同時並行的に実行されている ユーザのプロセス以外に，システムのプロセスが存在 システムプロセスは，ＯＳの機能をサポートするもの

プロセスの一生 プロセスは，動的に生成されたり消滅したりする プロセスの典型的な一生： ユーザまたはＯＳにより生成（起動）される (正確には，ユーザやＯＳのプロセスにより生成...後述） 必要な処理や計算を行う [活動中] 自主的に終了する， または外部から強制的に終了させられる

プロセスの状態 活動中のプロセスが取りうる状態は３種類ある： 実行中状態 プロセッサの時分割処理の順番がまわってきて， 処理が実際に進んでいる状態 実行待ち状態 プロセッサがまわってくるのを待っている状態 入出力待ち状態 入出力処理が終わるのを待っている状態 プロセスの状態は，ＯＳによって変更される

プロセスの状態遷移 強制終了 プロセス生成 実行待ち状態 順番がまわってくる タイムスライス終了 実行中状態 プロセス終了 入出力処理完了 入出力処理開始 入出力待ち状態 強制終了

プロセススケジューラ システムには，一般に複数のプロセスが存在する プロセスの交通整理が必要 プロセススケジューラ： プロセスの状態を制御するための，ＯＳの「部品」 どのプロセスを，どの状態にするか管理する 別のプロセスに切り替えるときに，プロセスを 実行する環境のセットアップを行う 現在実行中プロセスの状態を退避 新しく実行されるプロセスの状態を復帰

プロセススケジューラの動作概念図 スケジューラにより，プロセス状態が同期的に変更される 実行中状態にあるプロセスは一個だけ （プロセッサが複数あるシステムは除く） スケジューラの動作 P1 時間経過 入出力処理中 P2 P3 入出力処理中 P4 P5 実行中 実行待ち 入出力待ち

プロセススケジューラの仕組み 交通整理のために，スケジューラはプロセスを分類管理 実行中プロセス 実行待ちプロセス 入出力待ちプロセス P4 a c b プロセススケジューラの行う操作： 実行中プロセスを入出力待ちプロセスに(sleep) 入出力待ちプロセスを実行待ちプロセスに(wakeup) 実行中プロセスを切り替え (switch)

プロセススケジューラの動作イメージ プロセススケジューラは... 常にプロセスを監視しているわけではない 普段は眠っていて，何かのキッカケで起きて来て操作を行う プロセス スケジューラ タイマー 外部装置 キッカケ ＝ 割り込み 割り込みも何種類かある

割り込み１：ＡＰＩ呼び出し 入出力処理依頼 プロセスは，入出力装置に直接アクセスできない API （Application Program Interface）を介し，OS に処理を依頼 ⇒ 仕事を依頼したら，自分は「スリープ」状態に入る ...正確には，プロセススケジューラが，プロセスを「眠らせる」 OSの入出力処理部 プロセスA プロセスB API 入出力開始 実行中 実行待ち 入出力待ち 呼出元sleep switch

割り込み２：入出力完了 入出力完了 「Aさんに頼まれた仕事，終わったよ」 ⇒ プロセス A を「起こし」，順番待ち行列に並ばせる 入出力 プロセスB OSの割込み処理部 割込 制御横取り 2 1 wakeup 実行中 実行待ち 入出力待ち 3 制御返却 4

割り込み３：タイマー タイマ割込み処理からの呼び出し タイマ...タイムスライスの終了を知らせる プロセスA プロセスB OSの割込み処理部 制御横取り 2 1 switch 3 実行中 実行待ち

プロセススケジュールの戦略 プロセススケジューラの仕事： プロセスや入出力の進行にあわせ，交通整理をすること プロセスの切り替え(switch)を行うとき， どの実行待ちプロセスを処理するか決定すること ...いくつかの戦略が知られている スケジュール戦略を変えると，システムの振舞いが変わる

スケジューリングの性能指標（１） スケジュール戦略を考えるときに考慮すべき要素： CPU利用率 スループット：単位時間あたりの仕事量 ターンアラウンド時間： プロセスを起動してから完了するまでの時間 時間 プロセス起動 プロセス終了 ターンアラウンド時間

スケジューリングの性能指標（２） スケジュール戦略を考えるときに考慮すべき要素： 待ち時間： プロセスが，実行待ち状態で過ごす時間の合計 応答時間： 最初の処理が行われるまでの時間 時間 プロセス起動 プロセス終了 待 待ち時間 応答時間 平均値，最大値，最小値のどれに着目するかも重要

スケジュール戦略：単純な方式 横取りのない戦略（non-preemptive, 時分割処理は不要） 先着順 大きなプロセスの後ろは，長時間待たされる 早く終わりそうなものを先に済ます 実行時間をあらかじめ見積もるのは難しい 優先度順 優先度の決め方が問題 優先度の低いプロセスが，なかなか終わらない ⇒エージングによる優先度の調整： 長時間待っているプロセスの優先度を上げる

スケジュール戦略：やや複雑な方式 横取りのある戦略（preemptive, 時分割処理が必要） 「タイムスライスをどのように割り当てるか」 ラウンドロビン 実行待ちプロセスに公平に割り当てる A B C A B C A B C A B C 優先度順＋ラウンドロビン 優先度の高いプロセスは，割当の頻度を上げる A B A C A B A C A B A C ．．．プロセスAの優先度が高い場合

スケジュール戦略：さらに複雑な方式 横取りのある戦略（preemptive, 時分割処理が必要） 多段フィードバック方式 プロセスを優先度ごとにまとめる 同じ優先度の中ではラウンドロビン 一定時間内に実行が終わらなければ， プロセスの優先度が下げられる B C A E F D 優先度 高 低

多重プロセスの問題 ここまでの話： 個々のプロセスは，互いに独立している...という立場 ここからの話： 複数のプロセスが存在する場合特有の問題 （多重プロセスの問題） プロセスの生成について プロセスが互いに邪魔をしないための仕組み プロセスが互いに協力するための仕組み

プロセスの生成 プロセスは誰が作るのか... 基本的には，プロセスが新しいプロセスを作る プロセス１ プロセス２ プロセス３ プロセス４ プロセス５ プロセス６ ...プロセス３の親プロセス ...プロセス１の子プロセス

プロセスの構成例 RedHat Linux： ps – eo “%p %c %P” で表示された情報の一部を抜粋して図示 ユーザのプロセス 0: init 722: syslogd 747: portmap 775: rpc.statd 2: keventd 870: rpciod 3: ksoftirqd 871: lockd 4: kswapd 1031: xinetd 31840: in.telnetd 5: bdflush 1086: lpd 6: kupdated 1320: smbd 30676: smbd 7: jfsIO 1325: nmbd 1388: gdm 1396: gdm 1397: X 18169: tcsh 32097: ps ユーザのプロセス

UNIXにおけるプロセスの生成 forkシステムコールによるプロセス複製 execシステムコールによるプログラム切り替え fork fork : child = fork(); if (child == 0) exec(子プロセス); 親プロセスの処理 fork fork fork 複製 親 子 親 子 親プロセス 子プロセス

排他制御 複数のプロセスに共用される資源： 複数プロセスにより同時に参照される可能性がある 例：「整数値が書かれたファイルを参照し，値を１増やす」 3 3 P1 P1 P2 4 4 P2 5 4 期待する動作 少しタイミングがずれた場合 読んでから書くまで，他のプロセスにファイルを参照させない ようにプロセスを制御する必要がある ... 排他制御

クリティカルセクション クリティカルセクション（CS）： 他のプロセスとは，排他的に実行しなければならない部分 排他制御を適切に実行するためには... CSの最初と最後で，他プロセスに “stop”, “go”をかける CSに入るときは，“go” が出るまで待機する プロセス１ プロセス２ CS 待機 CS

排他制御を実現する仕組み 排他制御のため，stop, go をかける必要がある stop, go をかける操作も，排他的に実行の必要あり OSが stop, go の操作を提供することで，ジレンマを解決 stop, go 操作の実現方法：何通りか知られている lock, unlock セマフォ モニタ

デッドロック 同時に複数のstop, go が必要になる場合も ファイルＡをオープン プロセス１ ファイルＢをオープン ファイルＡをクローズ ファイルＢをクローズ プロセス２ Ａ Ｂ × どちらのプロセスも永久に進めない　⇒　デッドロック状態 stopのかけ方に順番を定める等，運用で回避する必要アリ

プロセス間の協調機構 排他制御と同じ仕組みを利用する方式： 排他制御：CSか否かの１ビットを他プロセスに伝える 基本的に同じ仕組みで，より大きな情報を伝達可能 ソケット： プロセスとプロセスをつなぐ「仮想通信路」 パイプ： ソケットの特殊な用法 UNIXで頻繁に利用される

本日のまとめ プロセスとは ＯＳにおけるプロセスの取り扱い プロセススケジューラについて 排他制御と協調機構 次回の講義...入出力機構について 課題（結果の提出不要）： 自分が普段使っているコンピュータで，どのような プロセスが走っているか確認せよ