オペレーティングシステム

(1)

オペレーティングシステム

加藤真平

東京大学大学院情報理工学系研究科

[email protected]

PFLab（加藤研）のウェブサイトからダウンロードできます。 ⇒http://www.pf.is.s.u-tokyo.ac.jp/ja/classes/

(2)

講義概要

• 受講生に求める基礎知識

– C言語の理解

– コンピュータアーキテクチャの基礎の理解

• メモリ管理、割り込み、CPUモード

• 参考図書

– Silberschatz, Galvin, and Gagne, Operating System

Concepts 8th Edition,

Wiley

• 成績

(3)

講義スケジュール（予定）

1. OSの概要（4/8） 2. プロセス管理（4/15） 3. プロセス間交信、スレッド（4/22） 4. プロセス同期（5/13） 5. CPUスケジューリング 1（5/20）

6. CPUスケジューリング 2 & トランザクション処理&メモリ管理１（5/27） 7. メモリ管理2（6/3） 8. 休講予定（6/10） 9. メモリ管理&I/Oシステム（6/17） 10. I/Oシステム（6/24） 11. ファイルシステム（7/1） 12. プロテクション＆セキュリティ (7/8) 13. バッチシステム＆分散システム&まとめ（7/22） 14. 試験（7/29）

(4)

システムコール（プリミティブ）

• システムコールはユーザプログラムとOSとのインター

フェイス

– 割り込み命令によって実現

– C,C++などのプログラミング言語向けインターフェイスを提供

– Unix系ではマニュアル2章がシステムコール、3章が言語ライ

ブラリ

• 2章のopen/read/write/closeはシステムコール • 3章のfopen/fread/fwrite/fcloseはシステムコールを使用し、ライブラリレベルでバッファを処理

(5)

システムコールの仕組み

(1) システムコール関数の呼出し (2) ライブラリ関数内で、 trap命令を発行 - レジスタにシステムコール番号 (3) カーネルモードに移行割込みハンドラを起動 (4) システムコール引数を検査しカーネル内へコピー (5) システムコール番号と関数ポインタの表から呼び出しルーチンを特定 処理ルーチンの実行 (6) システムコール処理結果をユーザ空間へコピー (7) 適切なプロセスのスケジュールシステムコール処理ルーチン #1 システムコール処理ルーチン #2 システムコール処理ルーチン #k システムコール処理ルーチン #n ... システムコール表ディスパッチャ (3) 割込みハンドラ (1) システムコール関数の呼出し(#k) (2) trap命令の発行ユーザプログラムカーネルモードユーザモード (4) 引数のコピー (5) システムコール処理の実行 (6) 返戻値のコピー (7) プロセスのスケジュールシステムコールライブラリ関数

(6)

プロセス管理

• プロセスとは？

– プログラムの実行単位

– 次のような資源を使用

• CPU時間 • メモリ • ファイル • I/Oデバイス

• OSによるプロセス管理の例

– プロセス生成・削除

– プロセス停止・再開

ユーザプログラムコードユーザデータ領域プロセス状態格納領域カーネルプログラムコードカーネル作業領域ユーザヒープ領域ユーザスタック領域

ユーザ空間

(7)

プロセス管理

• プロセスごとに仮想空間を割り当て

• 他のプロセスのメモリへのアクセス禁止

• バグ等でプロセスが異常終了しても、他のプロセスには影響なし

• プロセスの種類（後述）

• 権限による分類

• ユーザプロセス • スーパーユーザープロセス

• 形態による分類

• システムプロセス・デーモンプロセス • サーバープロセスユーザプログラムコードユーザデータ領域プロセス状態格納領域カーネルプログラムコードカーネル作業領域ユーザヒープ領域ユーザスタック領域

ユーザ空間

カーネル空間

(8)

仮想記憶の仕組み

• ページサイズ 1,024バイトの場合プロセスのページ表ポインタオフセット論理ページ番号物理ページ番号ＶＩＶ 0 1 2 3 4 物理メモリ仮想メモリ 10bits 0x0 0x0400 0x0800 0x0c00 0x1000 0x1400 1 0 2 I ＶＩＩＩＩＩアクセスパターン 0x0200 0x0900 0x0d00 #define V 1 #define I 0 struct PTBL { int valid; int pno; }; Struct PTBL[10] = {

(9)

プロセスと仮想記憶

プロセスのページ表ポインタオフセット論理ページ番号物理ページ番号ＶＩＶ ₀ 1 2 3 4 物理メモリ 10bits 1 0 2 I ＶＩＩＩＩＩページ表物理ページ番号ＶＩＶ 1 4 3 I ＶＩＩＩＩＩページ表仮想メモリ 0x0 0x0400 0x0800 0x0c00 0x1000 0x1400 0x1800

(10)

プロセスの種類

• 権限による分類

– ユーザプロセス

• 一般ユーザ

– スーパーユーザプロセス(ルート権限を有するプロセス)

• 特権機能を使用可能 – 例：任意のユーザプロセスの停止、システム停止

(11)

プロセスの種類

• 形態による分類

– システムプロセス、デーモンプロセス

• オペレーティングシステムサービスを提供しているプロセスでスーパーユーザモード（CPUの特権モードとは違う）で動いているプロセスの総称 • システムプロセスでユーザからは見えないところで動いているプロセス＝デーモンプロセス

– サーバプロセス

• クライアント・サーバモデルに基づいたサービスを提供しているプロセス＝サーバプロセス • httpデーモン、httpサーバ、httpシステムプロセス

(12)

どんなプロセスが動いている？

• Linuxの場合

– topコマンド

– psコマンド

• ps axwwwl

• Windowsの場合

– Ctl+Alt+Delして、タスクマネジャーを選択

(13)

ユーザ text, data,bss 領域カーネル領域 mmap領域スタックカーネル領域 mmap領域ユーザ text, data,bss 領域スタック

x86系Linuxの仮想メモリ空間使用

カーネル領域 mmap領域ユーザ text, data,bss 領域スタック 0x00000000 0x40000000 0xc0000000 0xffffffff text: プログラムコード data:初期データ bss: 初期データのない領域

(14)

プロセス

mmap領域スタック loginプロセス login プログラムメモリイメージ … exec(“/bin/sh”, ….);

(15)

プロセス

カーネル領域 mmap領域スタック loginプロセス login プログラムメモリイメージ … exec(“/bin/sh”, ….); execシステムコールが実行されると・・・

(16)

プロセス

mmap領域スタック /bin/shプロセス sh プログラムメモリイメージ pid = fork(); if (pid == 0) { exec(cmd, …); } else { …. } メモリイメージが書き換わり、新たなプロセスが実行

(17)

プロセス

カーネル領域 mmap領域スタック /bin/shプロセス sh プログラムメモリイメージ pid = fork(); if (pid == 0) { exec(cmd, …); } else { …. } forkシステムコールが実行されると・・・

(18)

プロセス

mmap領域スタック /bin/shプロセス（親プロセス） sh プログラムメモリイメージ pid = fork(); if (pid == 0) { exec(cmd, …); } else { …. } カーネル領域 mmap領域スタック sh プログラム pid = fork(); if (pid == 0) { exec(cmd, …); } else { …. } メモリが複製 /bin/shプロセス（子プロセス）

(19)

プロセス

カーネル領域 mmap領域スタック /bin/shプロセス（親プロセス） sh プログラムメモリイメージ pid = fork(); if (pid == 0) { exec(cmd, …); } else { …. } カーネル領域 mmap領域スタック sh プログラム pid = fork(); if (pid == 0) { exec(cmd, …); } else { …. } 複製元（親プロセス）：forkシステムコールの返り値は、子プロセスのID (identifier:識別子) 複製先（子プロセス）：forkシステムコールの返り値は、0 /bin/shプロセス（子プロセス）

(20)

プロセス

mmap領域ユーザ text, data,bss 領域スタック loginプロセス shellプロセスカーネル領域 mmap領域ユーザ text, data,bss 領域スタック lsプロセス execシステムコールによりshellプログラムが起動 forkシステムコールによってプロセスを生成さらに、 mmap領域ユーザ text, data,bss 領域スタック

(21)

補足

• fork()について

– オープン済みのファイル記述子は共有 – vfork() – メモリ保護によりアクセス時にコピー(copy on write) – 現在ではobsolete(既に古い） – 現在はfork()がメモリ保護を用いたcopy on writeで実現されている共有 code data stack code data stack コピーコピー共有共有 code data stack code data stack コピー古典的なfork() 特殊なfork() → スレッド(後述) fork()時のデータ領域とスタック領域をコピースタック領域のみコピー(データ領域へのアクセスに注意が必要)

(22)

プロセス実行の切り替え

• Linux/Unixでは、コマンド実行毎にプロセス作成

• プロセス実行の切り替え＝プロセスコンテキストスイッチ、

コンテキストスイッチ

ユーザプログラムコードユーザデータ領域プロセス状態格納領域カーネルユーザヒープ領域ユーザスタック領域ユーザ空間 A ユーザプログラムコードユーザデータ領域プロセス状態格納領域カーネルユーザヒープ領域ユーザスタック領域ユーザ空間 B コンテキストスイッチ時にOSは何をするか？

(23)

Process Control Block (PCB)とプロセス切り替え

• PCBにプロセス毎に必要な情報を格納する

– プロセスの状態 – CPUレジスタ – プライオリティ等のCPU スケジューリング情報 – ページテーブル等のメモリ管理情報

etc…

プロセスコンテキストの様子

(24)

補足

演算ユニット • コード(テキスト)領域 • プログラム • データ領域 • data – 初期化された静的変数 – 大域変数 • bss – 初期化されない静的変数 – 大域変数 • heap – 動的確保変数 code (text) data bss heap リターンアドレス auto変数 code (text) data bss heap リターンアドレス引数など auto変数

メモリ空間とセクション

プログラムカウンタ(PC) レジスタフレームポインタ各領域のアドレス

(25)

プロセスの状態

• New

– プロセス生成中

• Running

– 実行中

• Waiting

– 何かの事象待ち

• Ready

– 実行可能.

• Terminated

– 実行終了

(26)

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

• プロセススケジューリングキューの種類

– Job queue

• 全プロセスリスト

– Ready queue

• 実行可能状態のプロセスリスト

– Device queues

• I/O待ち状態プロセスリスト

(27)

プロセスの実行とキュー

head tail registers . . . registers . . . Ready queue PCB PCB‘ head tail I/O queue CPUで実行

• プロセスの実行中に起こること

– プロセスがI/O要求 – 割り当てられたCPU時間(Time slice)が経過 – 子プロセスを生成 – 割り込みが発生

(28)

補足

最高優先度の実行可能キュー最低優先度の実行可能キュー null null 優先度高 . . .

次に実行状態

待ちイベントが発生し

たら、実行可能状態へ

実行状態

(29)

スケジューラの種類

• 長期スケジューラ (job scheduler)

– バッチシステムでは、ジョブ（プロセス）が投入されると、

それらは2次記憶に配置 (spool呼ぶ)

– スプールされたジョブの中からいくつかのジョブを取り出し

て実行可能キューに投入

• 短期スケジューラ (CPU scheduler)

– どのプロセスを次に実行するか決定す

(30)

短期スケジューラ

• 短期スケジューラ

– プロセスが待ち状態になるときに、次に実行すべきプロセス

を決めるために起動

– プロセスが実行を続けている場合でも、Time Slice毎に起動

– 処理が速いことが必要条件

• 100ミリ秒毎に10ミリ秒もかかると、10/(100+10)= 9%がオーバヘッドになってしまう普通は数十から数百マイクロ秒のオーダ

(31)

長期スケジューラ

• 秒あるいは分毎に実行される

• マルチプログラミングの度合いを制御

– 同時に実行するプロセスの数を決定

– プロセス数を一定にするならば、長期スケジューラはプロセ

スが消滅したときにのみ実行

• 遅くても良い

• プロセスの性質に応じてスケジューリングする

– I/O-bound プロセス

• I/O処理多 CPU使用少

– CPU-bound プロセス

• CPU使用多（数値計算など）

(32)

TSSにおけるスケジューラ

• TSS(Time Sharing System)は長期スケジューラなし

• 長期スケジューラの替わりに中期スケジューラがある

場合あり

– マルチプログラミングの度合いを減らすために、実行可能プ

ロセスを実行可能キューから取り出し（swap out)

(33)

プロセス生成一般論(1/2)

• プロセスはプロセスを生成することができる

– 親プロセス：生成側 ⇔ 子プロセス：作られた側

– 子プロセスはさらにその子プロセスを生成可能

• それにより、プロセスのツリー形成

• 資源の共有可能性

– 親と子供は全ての資源を共有

– 子プロセスは親プロセスの一部の資源を共有

– 親子で共有する資源なし

• 実行関係

– 親と子供は同時に実行

– 親プロセスは子プロセスの終了を待つことが可能

(34)

プロセス生成一般論(2/2)

• メモリ空間

– 子プロセスは親プロセスのメモリ空間の複製を保持

– 子プロセスはプログラムを読み込み実行

• UNIX系の例

– forkシステムコール

• 子プロセスははじめ親プロセスのメモリ空間の複製を保持

– 実装上は共有＆Copy on Write

• 子プロセスは親プロセスのファイルディスクリプタの複製

を保持

– execシステムコール

(35)

プロセスの終了一般論

• プロセスは最後にexitシステムコールをして、プロセスを終了

– exitシステムコール時に終了コードを渡すことが可能 – 親プロセスは、子プロセスの終了をwaitシステムコールで待機が可能 • その際、子プロセスの終了コードの取得が可能

• プロセス終了時にするべきこと

– プロセスが保持している資源の解放：メモリ領域、I/Oバッファなど

• 親プロセスはabortシステムコール(Unix系の場合kill)で子プロセス

を終了させることが可能

• 親プロセスが終了すると子プロセスも終了させられるシステムも

存在

– Cascading termination – Linuxの場合は？ • 親プロセスが終了すると子プロセスは、initプロセスが親に

(36)

UNIX におけるプロセスツリー

• カーネルの初期化が終了すると、/sbin/initプログラムを探し、プ

ロセスを起動

• initプロセスは以下の処理を実行

– /etc/rc.d/rc.sysinitスクリプトの実行

– /etc/inittabスクリプトの実行

– /etc/rc.d/rc.localスクリプトの実行

• initプロセスの下に新たなプロセスが生成

(37)

スレッド

• Thread of Control

– プロセス内での一連の実行の流れ – 単にスレッドとも

• プロセス内に複数スレッドを動

かすような実行モデル

＝マルチスレッドモデル

• 多くの研究がなされたのは、マ

ルチスレッドモデルは共有メモ

リ型並列コンピュータが一般に

使えるようになった1970年後半

から1980年代

(38)

補足

• スレッドのContext(管理実体)

は小さい

– 切替が高速

– 但し、共有データのア

クセスに注意が必要

• プログラムから見るとプロ

グラム中の関数が別の処理

として動作

code data stack register メモリスレッドプロセスメモリ register スレッドプロセス register スレッド register スレッド main() func1() func2() int func1() { ... } int func2() { ... } int main() { thread_create(func1); thread_create(func2); } int func2() { ... } int func1() { func2(); } int main() { func1(); } マルチスレッド単一スレッド

(39)

スレッドの実現方法

• ユーザレベルスレッド

– ユーザライブラリで実現

• カーネルレベルスレッド

(40)

ユーザレベルスレッド

• ユーザモードで動作するライブラリで実現

– 多くの場合setjmp()/longjmp()で実装

• フレーム情報の保存と復元

• 各スレッドは別の起点フレームを保持

• カーネルレベルスレッドより軽量

– 高速のコンテクスト切り換え

– 大量のスレッド生成が可能

• スケジューリングの方針等の変更が手軽

threadB threadC

(41)

ユーザレベルスレッド

• スケジューリングの面倒をカーネルが見ない

– 処理を横取りできない or 横取りの実現が面倒

– 入出力等でスレッドが待ち状態になると、

同一プロセス内の他の実行可能スレッドが

実行不可能 (I/Oブロック)

• システムコールライブラリのwrapper等で対処

– 実行コアが複数でも並列に実行不可能

main threadA threadB threadC

(42)

カーネルレベルスレッド

• カーネル内でプロセスと同様の手法でスレッドを管理

– サイズ：スレッド制御ブロック（Thread Control Block）＜ PCB

• スレッドはカーネルによるスケジューリングの対象

– コンテクストスイッチ等の操作は、カーネルモードで実行

– カーネルモードとユーザモードの切り替えオーバヘッドが発生

• ただし、プロセスの切替よりは軽量

(43)

マルチスレッド実現モデル

• Many-to-One（多対１モデル）

– 複数のユーザレベルスレッドがカーネルで実現されているス

レッドひとつに対応

• One-to-One（１対１モデル）

– ひとつのユーザスレッドがカーネルで実現されているスレッド

ひとつに対応

• Many-to-Many（多対多モデル）

– 複数のユーザレベルスレッドが複数のカーネルレベルスレッド

に対応

(44)

マルチスレッドのモデル

• Many-to-One（多対１モデル）

– 一つのカーネルスレッドで複数のユーザスレッドを稼働 – ライブラリでスケジューリングするため高速 – カーネルの処理待ちできるのは一つのスレッドのみ • I/Oでブロック

• 実装

process ユーザレベルスレッドスケジューラ

(45)

マルチスレッドのモデル

• One-to-One

（1対1モデル）

– 一つのカーネルスレッドで

ただ一つのユーザスレッド

が稼働

– 他のスレッドのI/Oブロッ

クと無関係

– 複数プロセッサで稼働

– スレッド生成・管理のオー

バヘッドが発生

• 実装

– Linux, Windows k process ユーザレベルスレッドカーネルレベルスレッド k k k

(46)

マルチスレッドのモデル

• Many-to-Many（多対多モデル）

– 複数のユーザスレッドをその数以下のカーネルスレッドで稼働 – カーネルスレッドの数はアプリケーションやマシンに応じて決定 – スレッドをどう割り付けるかの制御が必要ユーザレベルスレッドスケジューラ process

(47)

マルチスレッドのモデル

• 2レベルモデル

– 多対多モデルのバリエーション – 一部のユーザレベルスレッドを特定のカーネルスレッドに固定(pin down)

• 実装

– IRIX, HP-UX, Tru64 UNIX – Solaris (before ver. 9)

k ユーザレベルスレッドカーネルレベルスレッド k k スケジューラ process

(48)

Linux Threads

• POSIX Pthreadが提供されている

– スレッドライブラリの標準規格 (IEEE 1003.1c)

– 多くのUnix系システムで実装

• Pthread実現方法

– clone() システムコール

(49)

マルチスレッドの利点(1/2)

• 並列コンピュータ上でのプロセッサの有効利用

– 共有メモリ型並列コンピュータ上で、プロセッサを有効利用

が可能

– マルチコアを活用可能

• マルチコアの時代 – 半導体集積度が向上したが、クロックを上げられない（リーク電流＆熱問題） – 余った回路の使い道としてチップ内に複数プロセッサを搭載

(50)

マルチスレッドの利点(2/2)

• 資源を共有可能

– ファイルディスクリプタやメモリ領域の共有、メモリ管理の

ための構造体の共有、TLBの共有が可能

• TLBの共有によりコンテキストスイッチ時にTLB flushが不必要

オペレーティングシステム