Microsoft PowerPoint - os ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - os ppt [互換モード]"

ほのかおおはし
5 years ago
Views:

1 2. プロセス概要マルチプログラミングプロセスの管理スケジューリング方式 2008/5/13 プロセス 1 複数の仕事を処理するつの法論執筆メール処理データ整理会議論執筆論執筆論執筆論執筆時間メール処理メール処理メール処理メール処理仕事が捗るのはどちらの方法か人を待たせないのはどちらかデータ整理データ整理データ整理データ整理会議会議会議 2008/5/13 プロセス 2 1

2 スケジューリング (1): ジョブスケジューラ今日ではほとんど使われないが, スーパーコンピュータ等で残っているバッチ処理 ( 不在処理 ) Ex. 何時何分からの処理をする NQS, LSF 等時間 Job A Job B Job C Input Output Input Output Input Output 2008/5/13 プロセス 3 マルチプログラミング現在のコンピュータは, 同時に複数の仕事をうマルチプログラミング CPU が実するプログラムを切り替える ( 数数百ミリ秒 ) 擬似並処理 (pseudoparallelism) ある時点で CPU はつのプログラムを実ユーザは並処理をしていると錯覚マルチプロセッサハードウェアにより並処理複数の CPU が物理メモリを共有 2008/5/13 プロセス 4 2

3 マルチプログラミングメール処理ダウンロード表計算時間プロセスとは, 並処理を扱いやすくするための概念モデル 2008/5/13 プロセス 5 スケジューリング (2): プロセススケジューラマルチプログラミングを実現する基本的仕組み対話型処理では必須では, 具体的にプロセスとは? 時間メール処理メール処理メール処理ダウンロードダウンロードダウンロードダウンロード表計算表計算表計算表計算 2008/5/13 プロセス 6 3

プロセスプロセスとは実中のプログラムプログラムカウンタ, レジスタ, 変数の現在値を保持概念的には, 個々のプロセスが仮想 CPU を持つメモリ上に展開 OS がプロセスを管理メモリプロセスが並処理をっているとメーラ考えるとシステムを理解しやすいエディタ実際は,

4 プロセスプロセスとは実中のプログラムプログラムカウンタ, レジスタ, 変数の現在値を保持概念的には, 個々のプロセスが仮想 CPU を持つメモリ上に展開 OS がプロセスを管理メモリプロセスが並処理をっているとメーラ考えるとシステムを理解しやすいエディタ実際は, マルチプログラミング実プロセス A ディスク B メーラ表計算 C 時間エディタ 2008/5/13 プロセス 7 プロセスの管理 OS はプロセス覧を保持プロセステーブルプロセス ID プロセスの状態優先順位 CPU 利用時間ユーザの権限確保したメモリ開いているファイル 2008/5/13 プロセス 8 4

5 プロセスの生成基本イベントメモリ領域の確保ディスクからプログラムを読み込みメモリ上へ展開プロセステーブルへ新規プロセスの登録プロセスの生成 : システムコールを使用 UNIX: fork システムコール呼び出し側プロセスのクローンを作成子プロセスは execve システムコール ( 指定した実可能プログラムをロードして実 ) を呼び出し, 環境構築 MS Windows: CreateProcess システムコールプロセスの作成とプログラムのロード親と子プロセスは個別のメモリアドレス空間を持つ 2008/5/13 プロセス 9 プロセスの終了基本イベント当該プロセスが使っていたメモリ領域の開放プロセステーブルからの削除プロセスが終了する状況通常終了 ( 自主的 ) UNIX: exit,windows: ExitProcess システムコールエラー終了 ( 自主的 ) 致命的エラー ( 非自主的 ) 他のプロセスにより kill 2008/5/13 プロセス 10 5

6 プロセスの状態待ち状態 (blocked) 原理的にプロセスを実できない ( 待ちなど ) 実可能状態 (ready) 実可能だが, 時的に CPU が割り当てられていない実状態 (running) 現に CPU を使用している Running Blocked Ready 2008/5/13 プロセス 11 プロセスの状態の遷移 1. プロセスが実を継続できない 2. 実中のプロセスが分な時間実されたスケジューラが判断 3. 他のプロセスが分な時間実された 4. 外部イベントが発生した ( 割り込み ) Running 1 2 Blocked 4 3 Ready 2008/5/13 プロセス 12 6

カーネルモードとユーザモード I/O 処理によるブロック, 割込時にプロセスの切替をいたい I/O 処理はOSを経由させるプロセスが直接 I/O 処理をできないようにするカーネルモード ( 特権モード ): 全ての機械語命令が実可能ユーザモード ( 般モード ):I/O 命令などの実を禁 OSカーネルプロセスA プロセスB CPU 実モードカーネルモードユーザモード OS の処理を

7 カーネルモードとユーザモード I/O 処理によるブロック, 割込時にプロセスの切替をいたい I/O 処理はOSを経由させるプロセスが直接 I/O 処理をできないようにするカーネルモード ( 特権モード ): 全ての機械語命令が実可能ユーザモード ( 般モード ):I/O 命令などの実を禁 OSカーネルプロセスA プロセスB CPU 実モードカーネルモードユーザモード OS の処理をうときカーネルモードユーザプロセスを実するときユーザモード 2008/5/13 プロセス 13 プロセスの OS 内での実現 (1) プロセスの実割込み / ブロックスケジューリングプロセスの実割り込み / ブロックが発生 ( ユーザモードカーネルモード ) プロセスの状態 : running ready/blocked 割込の種類毎のプログラム番地カーネルモードで実 2008/5/13 プロセス 14 7

8 プロセスの OS 内での実現 (2) OSはプロセスをプロセステーブルにより管理プロセス制御ブロック : プロセステーブル内に保持される各プロセスに関する情報 2008/5/13 プロセス 15 プロセスの切り替えコンテキストスイッチプログラムの実状態実中の箇所 (PC) 現時点でのデータプロセッサメール処理表計算メール処理表計算時間表計算 2008/5/13 プロセス 16 8

9 プロセス間をどう切り替える? スケジューリングアルゴリズムに求められる要件公平さ : 各プロセスに CPU 時間を公平に分け与えるポリシーの実 : 決められたポリシーを実するバランス : システムの全パートを動作させるスループット : 定時間内に処理できるジョブ数を最大化するターンアラウンド時間 : ジョブ投から実終了までの平均待ち時間を最小化する CPU 利用効率 : 常に CPU を駆動させる応答時間処理要求にすばやく応答するデッドライン : 決められた時間までに処理を完了する上記はトレードオフの関係にあるものもある目的毎に最適化例 ) スループット vs 応答時間 2008/5/13 プロセス 17 プロセススケジューリング式 (1) バッチシステム対象のスケジューリング方式 FCFS: First-Come First-Served ジョブが投された順番に実する方式 SJF: Shortest Job First 短い処理時間のジョブから先に実する方式処理終了までの平均待時間が FCFS より短くなる Shortest Remaining Job Next 残りの処理時間が最小のものから先に実新規投されたジョブAの処理時間が, 実中のジョブB 残り処理時間より小さいなら,Aを実 2008/5/13 プロセス 18 9

10 FCFS と SJF の例 FCFS ターンアラウンド時間 ( 実終了までの平均待時間 ) =( )/4=14 分 SJF ターンアラウンド時間 =( )/4=11 分全てのジョブが同時投された場合 2008/5/13 プロセス 19 プロセススケジューリング式 (2) 対話型システムを対象にしたスケジューリング方式 CPU を利用できる時間を定の時間間隔 (quantum) に分け, 複数プロセスに順に割り当てることで疑似並処理を実現ラウンドロビン (RR: Round-Robin) 全てのプロセスに公平にCPUを割当て各プロセスはquantumの分だけ処理をう時間経過後 ( または処理終了 / ブロックで ) 他のプロセスに切り替え実現方法は簡単実可能プロセスのリストを保持優先度順スケジューリングプロセスに優先度 (priority) をつけ, 最もい優先度を持つプロセスを実同じ優先度のプロセス同ではラウンドロビン問題点 : 低い優先度のプロセスが全く実されない状態 ( 飢餓状態 (starvation)) に陥る可能性がある 2008/5/13 プロセス 20 10

11 RR と優先度順スケジューリングの例ラウンドロビンによるスケジューリング優先度順スケジューリング 2008/5/13 プロセス 21 Quantum の適切なさコンテキストスイッチのオーバヘッド各種レジスタ, メモリマップ, 各種テーブルの保存復元などの処理が必要コンテキストスイッチの時間が1ミリ秒, quantumが4ミリ秒だとしたら? CPU 時間の 20% が無駄に使用 Quantum=100ミリ秒としたら, オーバヘッドは 1% だが,10 個のプロセスがある時に, 応答時間が最大 1 秒に... quantum の適切なさコンテキストスイッチに 1 ミリ秒かかる場合, quantum=20 50 ミリ秒が妥当 2008/5/13 プロセス 22 11

資源飢餓 (Resource Starvation) マルチタスクに関連した問題であり, プロセスが必要な資源を永久に獲得できない状況デッドロックによっても発生例 ) ダイクストラの食事する哲学者の問題哲学者の動作 : 食べる / 瞑想する食べるためには,2 本のフォークが必要度にはつのフォークしかとれない 5 人の哲学者がにフォークをとる 1 本のフォークしか取れない

12 資源飢餓 (Resource Starvation) マルチタスクに関連した問題であり, プロセスが必要な資源を永久に獲得できない状況デッドロックによっても発生例 ) ダイクストラの食事する哲学者の問題哲学者の動作 : 食べる / 瞑想する食べるためには,2 本のフォークが必要度にはつのフォークしかとれない 5 人の哲学者がにフォークをとる 1 本のフォークしか取れないデッドロックが発生スケジューリングアルゴリズムに問題がある場合に発生優先度順スケジューリングで, 優先度の低いプロセスにCPUが割り当てられない優先度を定期的に割り当てなおす, などの方策が必要 2008/5/13 プロセス 23 優先度の逆転 (Priority Inversion) スケジューリングにおいて, 優先順位の低いプロセスが優先順位のいプロセスが必要としているリソースを占有しているときに発生する状態原理プロセス A, B, C ( 優先順位 A, B, C) A は C の結果を必要とする B が C の直前に動作し,C を飢餓状態に陥れる A は最も優先度がいのにいつまでも実されない解決例優先度継承 : 依存関係のあるプロセスの中で最もい優先度を継承 2008/5/13 プロセス 24 12

13 第 1 回ミニレポート提出期限 :5/20 授業開始時形式 :A4 用紙に印刷したもの ( 手書きでも OK) 以下のプロセス A E を,FCFS,SJF,RR でスケジューリングする. プロセス A: 投時間 0, 処理時間 4 プロセス B: 投時間 0, 処理時間 2 プロセス C: 投時間 3, 処理時間 1 プロセス D: 投時間 3, 処理時間 1 プロセス E: 投時間 3, 処理時間 1 (1) A E のターンアラウンド時間を求め, 比較せよ. (2) C E のみのターンアラウンド時間を求め, 比較せよ同じ投時刻のものは A, B, C, D, E の投順と考えよ RR の切り替えオーバヘッドは無視して良い. また quantum は 0.5 とせよ. 2008/5/13 プロセス 25 まとめマルチプログラミング複数のプログラムを ( かけ上 ) 同時に実する仕組みプロセスの管理プロセスの生成, 終了はシステムコールを使用複数のプロセスの情報をプロセステーブルに保持スケジューリング時分割処理なし :FCFS,SJF 時分割処理あり :RR, 優先度スケジューリング 2008/5/13 プロセス 26 13

14 付録 : プロセススケジューリング式 (3) リアルタイムスケジューリング異なるデッドライン処理内容を持つ複数プロセスがCPUを奪い合う各プロセスがデッドラインに間に合うように調整が必要デッドラインを持つ周期プロセスの例周期, 処理時間 A:(30ms, 10ms) B:(40ms, 15ms) C:(50ms, 5ms) 全てのプロセスがスケジューリング可能 ( デッドライン内に処理を完了 ) な条件 C m i 1 P i = 1 i : 周期,C i : 処理時間 P 2008/5/13 i プロセス 27 Rate Monotonic Scheduling (RMS) 周期的に動作するプロセスのみに使用できるアルゴリズム各プロセスに優先度 (=1/ 周期 ) を与える常に最優先度を持つプロセスを実あるプロセスの処理中に, もっとい優先度を持つプロセスが実可能になると, そのプロセスがCPUを横取りする以下の条件を満たすプロセスに対し使用可能 1. 各周期プロセスは周期内に処理を終える必要がある 2. 各周期プロセスは他のプロセスに依存していない 3. 各周期の処理に必要なCPU 時間は同じ 4. 周期的でないプロセスはデッドラインを持たない 5. CPUの横取り (preemption) はオーバヘッドなしで可能 2008/5/13 プロセス 28 14

15 Earliest Deadline First (EDF) 任意のデッドラインを持つプロセスに有効周期的でなくても良いアルゴリズム各プロセスは処理を要求する時にデッドラインを申告スケジューラは処理待ちのプロセスをデッドラインが早い順に整列最も早いデッドラインを持つプロセスに処理が移る新しく処理要求をったプロセスが最も早いデッドラインを持つ時は, 現在実中のプロセスからCPUを横取りする 2008/5/13 プロセス 29 RMS と EDF によるスケジューリング例 (1) CPU の横取り (preemption) 発生 2008/5/13 プロセス 30 15

16 RMS と EDF によるスケジューリングの例 (2) C i i= = + + = なので, スケジュール可能なハズ... 1 Pi プロセス数 =3の場合,RMSではCPU 利用率 78% しか達成できない (EDFは100%) 2008/5/13 プロセス 31 16

05-scheduling.ppt

05-scheduling.ppt オペレーティングシステム ~ スケジューリング ~ 山田浩史 hiroshiy @ cc.tuat.ac.jp 2014/06/01 復習 : プロセス実行状態にあるプログラムのことプログラムの実行に必要なものをひっくるめて指すテキスト領域データ領域スタック領域 CPU のレジスタ値プログラムカウンタなど OS はプロセス単位で管理するメモリ Hard Disk CPU プロセス execute