オペレーティングシステム - PFLab · 2019. 4. 14. · Concepts 8th Edition, Wiley • 成績 –試験の点数で決定 –試験は持ち込み不可 –授業に出席していた人で試験の結果が悪い人は追試

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

加藤真平

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

[email protected]

2019/4/15 1第2回オペレーティングシステム

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

2019/4/15 2

講義概要

• 受講生に求める基礎知識– C言語の理解

– コンピュータアーキテクチャの基礎の理解• メモリ管理、割り込み、CPUモード

• 参考図書– Silberschatz, Galvin, and Gagne, Operating System

Concepts 8th Edition, Wiley

• 成績– 試験の点数で決定

– 試験は持ち込み不可

– 授業に出席していた人で試験の結果が悪い人は追試験あり

• 出席をとるが出席点はなし第2回オペレーティングシステム

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

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）

2019/4/15 第2回オペレーティングシステム 3


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

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

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

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

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

• 2章のopen/read/write/closeはシステムコール

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


システムコールの仕組み

(1) システムコール関数の呼出し

(2) ライブラリ関数内で、 trap命令を発行

-レジスタにシステムコール番号

(3) カーネルモードに移行割込みハンドラを起動

(4) システムコール引数を検査しカーネル内へコピー

(5) システムコール番号と関数ポインタの表から呼び出しルーチンを特定

処理ルーチンの実行(6) システムコール処理結果をユーザ

空間へコピー

(7) 適切なプロセスのスケジュール

システムコール処理ルーチン #1

システムコール処理ルーチン #2

システムコール処理ルーチン #k

システムコール処理ルーチン #n

...

システムコール表

ディスパッチャ

(3) 割込みハンドラ

(1) システムコール関数の呼出し(#k)

(2) trap命令の発行

ユーザプログラム

カーネルモード

ユーザモード

(4) 引数のコピー

(5) システムコール処理の実行

(6) 返戻値のコピー

(7) プロセスのスケジュール

システムコールライブラリ関数


プロセス管理

• プロセスとは？– プログラムの実行単位

– 次のような資源を使用• CPU時間

• メモリ

• ファイル

• I/Oデバイス

• OSによるプロセス管理の例– プロセス生成・削除

– プロセス停止・再開

– プロセス間同期

– プロセス間通信

– デッドロック処理

ユーザプログラムコード

ユーザデータ領域

プロセス状態格納領域

カーネルプログラムコード

カーネル作業領域

ユーザヒープ領域

ユーザスタック領域ユ

ーザ空間

カーネル空間


プロセス管理

• プロセスごとに仮想空間を割り当て• 他のプロセスのメモリへのアクセス禁止

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

• プロセスの種類（後述）• 権限による分類

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

• 形態による分類• システムプロセス・デーモンプロセス• サーバープロセス






ユーザヒープ領域

ユーザスタック領域ユ

ーザ空間

カーネル空間

仮想記憶の仕組み• ページサイズ 1,024バイトの場合


プロセスのページ表ポインタ

オフセット論理ページ番号

物理ページ番号

Ｖ

ＩＶ

0

1

2

3

4

物理メモリ仮想メモリ

10bits

0x0

0x0400

0x0800

0x0c00

0x1000

0x1400

0x1800

1

0

2

I

Ｖ

ＩＩＩＩＩ

アクセスパターン

0x0200

0x0900

0x0d00

#define V 1

#define I 0

struct PTBL {

int valid;

int pno;

};

Struct PTBL[10] = {

{V, 1}, {I, 0}, {V, 0},

{I, 0}, {V, 2}, {I, 0},…};

Load Reg10, [0x1010] if (PTBL[0x1010>>10].valid)PhysMem[(PTBL[0x10１0>>10].pno<<10)+0x1010&0x3ff]

else 割り込み

プロセスと仮想記憶


プロセスのページ表ポインタ

オフセット論理ページ番号


Ｖ

ＩＶ 0

1

2

3

4

物理メモリ

10bits

1

0

2

I

Ｖ

ＩＩＩＩＩ

ページ表


Ｖ

ＩＶ 1

4

3

I

Ｖ

ＩＩＩＩＩ

ページ表

仮想メモリ

0x0

0x0400

0x0800

0x0c00

0x1000

0x1400

0x1800

プロセスの種類• 権限による分類

– ユーザプロセス

• 一般ユーザ

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

• 特権機能を使用可能

– 例：任意のユーザプロセスの停止、システム停止


プロセスの種類• 形態による分類

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

• システムプロセスでユーザからは見えないところで動いているプロセス＝デーモンプロセス

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

• httpデーモン、httpサーバ、httpシステムプロセス


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

• Linuxの場合

– topコマンド

– psコマンド

• ps axwwwl

• Windowsの場合

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


ユーザ

text, data,bss領域

カーネル領域

mmap領域

スタック

カーネル領域

mmap領域

ユーザ


スタック


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

カーネル領域

mmap領域

ユーザ


スタック

0x00000000

0x40000000

0xc0000000

0xffffffff

text: プログラムコードdata:初期データbss: 初期データのない領域

2019/4/15 第2回オペレーティングシステム

プロセス

カーネル領域

mmap領域

スタック

loginプロセス

login プログラムメモリイメージ

…

exec(“/bin/sh”, ….);

14


プロセス

カーネル領域

mmap領域

スタック

loginプロセス

login プログラムメモリイメージ

…

exec(“/bin/sh”, ….);execシステムコールが実行されると・・・

15


プロセス

カーネル領域

mmap領域

スタック

/bin/shプロセス

shプログラムメモリイメージ

pid = fork();

if (pid == 0) {

exec(cmd, …);

} else {

….

}

メモリイメージが書き換わり、新たなプロセスが実行

16


プロセス

カーネル領域

mmap領域

スタック

/bin/shプロセス


pid = fork();

if (pid == 0) {

exec(cmd, …);

} else {

….

}

forkシステムコールが実行されると・・・

17


プロセス

カーネル領域

mmap領域

スタック

/bin/shプロセス（親プロセス）


pid = fork();

if (pid == 0) {

exec(cmd, …);

} else {

….

}

カーネル領域

mmap領域

スタック

shプログラムpid = fork();

if (pid == 0) {

exec(cmd, …);

} else {

….

}

18

メモリが複製

/bin/shプロセス（子プロセス）


プロセス

カーネル領域

mmap領域

スタック

/bin/shプロセス（親プロセス）


pid = fork();

if (pid == 0) {

exec(cmd, …);

} else {

….

}

カーネル領域

mmap領域

スタック

shプログラムpid = fork();

if (pid == 0) {

exec(cmd, …);

} else {

….

}

19

複製元（親プロセス）：forkシステムコールの返り値は、子プロセスのID (identifier:識別子)

複製先（子プロセス）：forkシステムコールの返り値は、0

/bin/shプロセス（子プロセス）


プロセス

カーネル領域

mmap領域

ユーザ


スタック

loginプロセス shellプロセス

カーネル領域

mmap領域

ユーザ


スタック

lsプロセス

execシステムコールによりshellプログラムが起動

forkシステムコールによってプロセスを生成さらに、execシステムコールでlsプログラムを起動

カーネル領域

mmap領域

ユーザ


スタック

補足


• 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()時のデータ領域とスタック領域をコピー

スタック領域のみコピー(データ領域へのアクセスに注意が必要)

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

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







ユーザヒープ領域ユーザスタック領域

ユーザ空間

Aカーネル空間






ユーザヒープ領域ユーザスタック領域

ユーザ空間

Bカーネル空間

コンテキストスイッチ時にOSは何をするか？


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

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

– CPUレジスタ

– プライオリティ等のCPU スケジューリング情報

– ページテーブル等のメモリ管理情報 etc…

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

補足


演算ユニット

CPU

• コード(テキスト)領域

• プログラム

• データ領域

• data

– 初期化された静的変数

– 大域変数

• bss

– 初期化されない静的変数

– 大域変数

• heap

– 動的確保変数

• スタック領域

• auto変数

• 制御情報

code(text)

data

bss

heap

リターンアドレス

引数など

auto変数


引数など

auto変数

code(text)

data

bss

heap


引数など

auto変数


引数など

auto変数

メモリ空間とセクション

プログラムカウンタ(PC)

レジスタ

フレームポインタ

各領域のアドレス

切り換え時に必要な情報を保存


プロセスの状態

• New

– プロセス生成中

• Running

– 実行中

• Waiting

– 何かの事象待ち

• Ready

– 実行可能.

• Terminated

– 実行終了


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

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

– Job queue • 全プロセスリスト

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

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


プロセスの実行とキュー

head

tail registers

.

.

.

registers

.

.

.

Ready

queue PCB PCB‘

head

tail

I/O queue

CPUで実行

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

– プロセスがI/O要求

– 割り当てられたCPU時間(Time slice)が経過

– 子プロセスを生成

– 割り込みが発生

補足


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

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

待ちキュー

null

null

null

優先度

高

.

.

.

次に実行状態

待ちイベントが発生したら、実行可能状態へ

実行状態


スケジューラの種類

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

– バッチシステムでは、ジョブ（プロセス）が投入されると、それらは2次記憶に配置 (spool呼ぶ)

– スプールされたジョブの中からいくつかのジョブを取り出して実行可能キューに投入

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

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


短期スケジューラ

• 短期スケジューラ

– プロセスが待ち状態になるときに、次に実行すべきプロセスを決めるために起動

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

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

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


長期スケジューラ

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

• マルチプログラミングの度合いを制御– 同時に実行するプロセスの数を決定

– プロセス数を一定にするならば、長期スケジューラはプロセスが消滅したときにのみ実行

• 遅くても良い

• プロセスの性質に応じてスケジューリングする– I/O-bound プロセス

• I/O処理多 CPU使用少

– CPU-bound プロセス• CPU使用多（数値計算など）


TSSにおけるスケジューラ

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

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

– マルチプログラミングの度合いを減らすために、実行可能プロセスを実行可能キューから取り出し（swap out)


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

• プロセスはプロセスを生成することができる– 親プロセス：生成側 ⇔ 子プロセス：作られた側

– 子プロセスはさらにその子プロセスを生成可能• それにより、プロセスのツリー形成

• 資源の共有可能性– 親と子供は全ての資源を共有

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

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

• 実行関係– 親と子供は同時に実行

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


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

• メモリ空間

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

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

• UNIX系の例

– forkシステムコール

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

–実装上は共有＆Copy on Write

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

– execシステムコール

• プログラムを指定されたファイルから読み出し実行


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

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

• その際、子プロセスの終了コードの取得が可能

• プロセス終了時にするべきこと– プロセスが保持している資源の解放：メモリ領域、I/Oバッファなど

• 親プロセスはabortシステムコール(Unix系の場合kill)で子プロセスを終了させることが可能

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

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


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

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

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

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

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

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

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


スレッド

• Thread of Control

– プロセス内での一連の実行の流れ

– 単にスレッドとも

• プロセス内に複数スレッドを動かすような実行モデル

＝マルチスレッドモデル

• 多くの研究がなされたのは、マルチスレッドモデルは共有メモリ型並列コンピュータが一般に使えるようになった1970年後半から1980年代

補足


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

は小さい

– 切替が高速

– 但し、共有データのアクセスに注意が必要

• プログラムから見るとプログラム中の関数が別の処理として動作

code

data

stack

register

メモリ

スレッドプロセス

code

data

メモリ

stack

register

スレッドプロセス

stack

register

スレッド

stack

register

スレッド

main()

main()

func1()

func2()

func1() func2()

int func1()

{ ... }

int func2()

{ ... }

int main()

{

thread_create(func1);

thread_create(func2);

}

int func2()

{ ... }

int func1()

{ func2(); }

int main()

{

func1();

}

マルチスレッド

単一スレッド


スレッドの実現方法

• ユーザレベルスレッド

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

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

– オペレーティングシステムがカーネルで実現

ユーザレベルスレッド

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

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

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

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

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

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

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

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

main

threadA

threadB

threadC



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

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

– 入出力等でスレッドが待ち状態になると、同一プロセス内の他の実行可能スレッドが実行不可能 (I/Oブロック)

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

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

main

threadA

threadB

threadC


カーネルレベルスレッド

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

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

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

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

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

• ただし、プロセスの切替よりは軽量– メモリ空間の切りえは不要だから



マルチスレッド実現モデル• Many-to-One（多対１モデル）

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

• One-to-One（１対１モデル）– ひとつのユーザスレッドがカーネルで実現されているスレッドひとつに対応

• Many-to-Many（多対多モデル）– 複数のユーザレベルスレッドが複数のカーネルレベルスレッドに対応

マルチスレッドのモデル

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

– 一つのカーネルスレッドで複数のユーザスレッドを稼働

– ライブラリでスケジューリングするため高速

– カーネルの処理待ちできるのは

一つのスレッドのみ

• I/Oでブロック

• 実装

– Solaris Green Thread,

– GNU Portable Thread k

process


カーネルレベルスレッド

スケジューラ



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

– 一つのカーネルスレッドでただ一つのユーザスレッドが稼働

– 他のスレッドのI/Oブロックと無関係

– 複数プロセッサで稼働

– スレッド生成・管理のオーバヘッドが発生

• 実装

– Linux, Windows k

process


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



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

– 複数のユーザスレッドをその数以下のカーネルスレッドで稼働

– カーネルスレッドの数はアプリケーションやマシンに応じて決定

– スレッドをどう割り付けるかの制御が必要

k


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

スケジューラ

process



• 2レベルモデル

– 多対多モデルのバリエーション

– 一部のユーザレベルスレッドを特定のカーネルスレッドに固定(pin down)

• 実装– IRIX, HP-UX, Tru64 UNIX

– Solaris (before ver. 9)

k


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

スケジューラ

process



Linux Threads

• POSIX Pthreadが提供されている

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

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

• Pthread実現方法

– clone() システムコール


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

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

– マルチコアを活用可能• マルチコアの時代

– 半導体集積度が向上したが、クロックを上げられない（リーク電流＆熱問題）

– 余った回路の使い道としてチップ内に複数プロセッサを搭載


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

• 資源を共有可能– ファイルディスクリプタやメモリ領域の共有、メモリ管理のための構造体の共有、TLBの共有が可能

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

• 応答性の向上– 例えばマルチスレッドWEBブラウザでは、イメージを読み込んでいるスレッドとユーザの入力を同時に処理が可能

• シングルスレッドの場合は、selectを使ったevent driven処理

スレッド利用の場面


• サーバプロセスの応答性の向上

– サーバプログラム

• 要求ごとにスレッドを生成し、処理と結果の応答を担当

• 例：HTTPサーバ

–それぞれ別のスレッドでリクエストを処理

– ウィンドウシステム

• それぞれ別のスレッドでイベントを待つ処理



• CPU処理と入出力処理の分割

– プロセスＰの処理を、計算を行うスレッド(Th1)

と入出力を行うスレッド（Th2）に分割

• Th1とTh2は１つのプログラムを実行

– 入出力待ちの間，Th2は待ち状態になるがTh1の処理は継続

Th2(入出力)

Th1(計算)

通知

入出力待ち

依頼



• 並列計算

– 並列計算機を使って高速計算

– 例：行列の掛け算

• 各行を別スレッドで計算

• メモリ空間を共有するので、プロセス間通信するより高速

× ＝

（補足）カーネルもマルチ化の時代


OS

Image

OS

Image

OS

Image

OS

Image

従来型のカーネル（SMP）マルチカーネル（AMP）

VS

Documents

オペレーティングシステム - PFLab · 2019. 4. 14. · Concepts 8th Edition, Wiley • 成績 –試験の点数で決定 –試験は持ち込み不可 –授業に出席していた人で試験の結果が悪い人は追試