オペレーティングシステム (プロセス管理)

Presentation on theme: "オペレーティングシステム (プロセス管理)"— Presentation transcript:

1 オペレーティングシステム (プロセス管理)
2006年10月16日

2 プロセスの生成と実行(30ページ) プロセスの生成 OSの成り立ちなどで異なる プログラムをコンパイルし実行可状態に置く
実行可能形式ファイルをロードする spawn 現在実行中のプログラムを複製する fork, rfork, clone,… 新しいプログラムはexecでオーバーレイする OSの成り立ちなどで異なる Unixは、複製によりプロセスを生成する

3 プロセスの関係 [大久保英嗣, オペレーティングシステムの基礎] 生成されたプロセスはすべて同時に動く

4 起動シーケンスの最終段階 static int init(void * unused) { lock_kernel(); /*
* Tell the world that we're going to be the grim * reaper of innocent orphaned children. * * We don't want people to have to make incorrect * assumptions about where in the task array this * can be found. */ child_reaper = current; /* Sets up cpus_possible() */ smp_prepare_cpus(max_cpus); do_pre_smp_initcalls(); smp_init(); do_basic_setup(); prepare_namespace(); * Ok, we have completed the initial bootup, and * we're essentially up and running. Get rid of the * initmem segments and start the user-mode stuff.. free_initmem(); unlock_kernel(); system_running = 1; if (open("/dev/console", O_RDWR, 0) < 0) printk("Warning: unable to open an initial console.\n"); (void) dup(0); 起動シーケンスの最終段階 /* * We try each of these until one succeeds. * * The Bourne shell can be used instead of init if we are * trying to recover a really broken machine. */ if (execute_command) run_init_process(execute_command); run_init_process("/sbin/init"); run_init_process("/etc/init"); run_init_process("/bin/init"); run_init_process("/bin/sh"); panic("No init found. Try passing init= option to kernel."); }

5 プロセスに対して行われる各種の基本操作 生成(spawn)や複製(fork) 消滅 シグナル送信 同期 タスク管理領域を生成するか複製するか
タスク管理領域を親のタスクが消す 消えるまでの間が消滅中状態(ゾンビ) シグナル送信 終了 停止 同期

6 プロセスに対する操作（forkによる生成）
[大久保英嗣, オペレーティングシステムの基礎]

7 プロセス間通信（３２ページ） パイプ（９３ページ） ソケット（１０７ページ） 共有メモリ(Shared Memory)
カーネルが作り出した仮想的な通信路 ソケット（１０７ページ） パイプの通信範囲を計算機間にまで広げたもの 共有メモリ(Shared Memory) 仮想記憶のところで説明します 擬似端末(Pseudo TTY) デバイスドライバにより作られた仮想的な端末

8 プロセスの同期 パイプを使う方法 mkfifo コマンドで名前つきパイプを作る 一方を cat コマンドで読み取りとして、
% mknod named_pipe % cat named_pipe aa bb cc dd % % cat > named_pipe aa bb cc dd ^D %

9 プロセスの同期（３６ページ） 並列処理には必要不可欠である 同期のための仕組みがある セマフォ ロック モニタ
SYS V IPC(Inter-Process Communication) ロック ＰＯＳＩＸ　Ｔｈｒｅａｄ モニタ Java が採用

10 このような逐次的資源が共有されるとき、Atomicに操作できるような機構が必要となる。
並行プロセス間で生じる問題 逐次的資源 たとえば、Read-modify-write のような、 　一連の操作をAtomicに行う必要のある資源。 このような逐次的資源が共有されるとき、Atomicに操作できるような機構が必要となる。 もし、そういう機構がなければプログラムが意図したとおりに動かない。

11 処理の粒度 マルチジョブ マルチタスク マルチCPU レコードの排他的利用 トランザクションを不可分な処理単位とする
メモリ上の共有領域の排他的利用 共有領域を使用するプログラムを排他的に実行 マルチCPU メモリ上の変数の排他的利用 プロセッサのバスサイクルを連続する

12 c1やc2は、自プロセスが 他プロセスに、臨界領域に入ること を知らせるための変数。 先に臨界領域に入ることを宣言した
プロセスが実際に臨界領域に入る。 両方が臨界領域に入ろうとしたとき、 turn変数により一方が譲る。 臨界領域に入っているとき、 c1かc2の一方だけがtrueである。 [大久保英嗣, オペレーティングシステムの基礎]

13 TAS命令（計算機アーキテクチャの授業で既出）
相互排除 TAS命令（計算機アーキテクチャの授業で既出） もっとも原始的なロックの実装(primitive)。 2値セマフォを実現する。 セマフォ P操作（ロック）とV操作（アンロック）により実現。 再帰的ロックとも呼ばれる。 モニタ（Java言語で使われている） 共有資源とそれを操作する手続きを一体化。 セマフォのわかりにくさを、構造化により解消。 構造化セマフォと呼ばれることもある。

14 TAS命令 メモリ上の変数をテストする処理、メモリ上の変数に値をセットする処理、これらを順に他の処理をはさむことなく(=Atomic)行う。
テストとは、0かそうでないかを調べてフラグに結果を反映する処理 Intel系では lock xchg 命令で代用する。 バスサイクルをlock（不可分かつ連続）して処理 バイナリセマフォ、２値セマフォ、を実現する。

15 変形セマフォ セマフォ変数 P操作 V操作 正の値は利用可能な資源の数 負の値は現在待ちに入っているプロセスの数
セマフォの値をatomicに１減らしテストする テスト結果が負になったときは、待ち状態に入る V操作 セマフォの値をatomicにテストし１増やす テスト結果が負のときは、待ち状態にあるプロセスをひとつ動作可能状態にする

16 競合を避けるため相互排除機構を持っている。
相互排除とデッドロック 競合を避けるため相互排除機構を持っている。 これが時に問題を起こす。 ２つのスレッドが資源Aと資源Bを同時にとりたいとき 　　　　資源が２つそろうまでは返さないぞ、というアルゴリズムだと… スレッド１ 資源Aを獲得 資源Bを獲得したい！ スレッド２ 資源Bを獲得 資源Aを獲得したい！

17 デッドロックの発生条件と防止 ２つのプロセスが資源R1と資源R2を同時にとりたいとき 逐次的資源に関する相互排除条件 待ち条件
資源要求は同時に行う 横取り不可条件 資源を同時に確保できない場合、解放し再度要求 循環待ち条件 資源を順序だてて取得する ２つのプロセスが資源R1と資源R2を同時にとりたいとき 　　資源が２つそろうまでは返さないぞ、というアルゴリズムだと… Deadlock! プロセスP１ プロセスP２ 資源R1を獲得 資源R2を獲得 資源R2を獲得したい！ 資源R1を獲得したい！

18 例：相互排除 /usr/src/linux/drivers/char/lp.c Atomic処理 スピンロック
カーネルロック(全域的ロック) mutexやセマフォ(局所的ロック)

19 例：相互排除の実装 Atomic処理 スピンロック カーネルロック(全域的ロック) mutexやセマフォ(局所的ロック)
/usr/src/linux/include/asm/atomic.h スピンロック /usr/src/linux/include/asm/lock.h カーネルロック(全域的ロック) /usr/src/linux/include/asm/smplock.h mutexやセマフォ(局所的ロック) /usr/src/linux/include/asm/semaphore.h

20 同じプロセスに属す限り、資源は共有しあう 軽量プロセス＝スレッドという定義もある。
プロセスとスレッド(38ページ) どちらも実行のひとつの単位である そういう意味では「タスク」とひとくくりに扱う。 スレッドはプロセスに属する点が異なる 同じプロセスに属す限り、資源は共有しあう 軽量プロセス＝スレッドという定義もある。 CPUが複数個存在する場合に、同じプロセスの複数のスレッドが実行できる。 高速処理や効率的な処理には良いが… 資源の競合が起きるかもしれない…

21 [大久保英嗣, オペレーティングシステムの基礎]