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

Transcription

1 1.PFLab( 加藤研 ) のウェブサイトからダウンロードできます 2. 紙資料も配布します オペレーティングシステム 加藤真平東京大学大学院情報理工学系研究科 shinpei@is.s.u-tokyo.ac.jp 2018/4/23 第 3 回オペレーティングシステム 1

2 講義概要 受講生に求める基礎知識 C 言語の理解 コンピュータアーキテクチャの基礎の理解 メモリ管理 割り込み CPUモード 参考図書 Silberschatz, Galvin, and Gagne, Operating System Concepts 8th Edition, Wiley 成績 試験の点数で決定 試験は持ち込み不可 授業に出席していた人で試験の結果が悪い人は追試験あり 出席をとるが出席点はなし 2018/4/23 第 3 回オペレーティングシステム 2

3 講義スケジュール ( 予定 ) 1. OSの概要 (4/9) 2. プロセス管理 (4/16) 3. プロセス間交信 スレッド (4/23) 4. プロセス同期 (5/7) 5. CPUスケジューリング (5/14) 6. CPUスケジューリング (5/21) 7. メモリ管理 (5/28) 8. メモリ管理 & I/Oシステム (6/4) 9. I/Oシステム (6/11) 10. ファイルシステム (6/18) 11. プロテクション & セキュリティ (6/25) 12. バッチシステム & 分散システム & まとめ (7/2) 13. 予備日 (7/9) 14. 試験 (7/23) 論文も読んでみましょう ACM SOSP USENIX OSDI USENIX ATC USENIX NSDI ACM ASPLOS 2018/4/23 第 3 回オペレーティングシステム 3

4 スレッド Thread of Control プロセス内での一連の実行の流れ 単にスレッドとも プロセス内に複数スレッドを動かすような実行モデル = マルチスレッドモデル 多くの研究がなされたのは マルチスレッドモデルは共有メモリ型並列コンピュータが一般に使えるようになった 1970 年後半から 1980 年代 2018/4/23 第 3 回オペレーティングシステム 4

5 補足 プロセスメモリ data code プロセス スレッド register func2() stack func1() main() スレッド 単一スレッド int func1() {... int func2() {... int main() { thread_create(func1); thread_create(func2); スレッド int func2() {... int func1() { func2(); int main() { func1(); マルチスレッド スレッド スレッドの Context( 管理実体 ) は小さい 切替が高速 但し 共有データのアクセスに注意が必要 プログラムから見るとプログラム中の関数が別の処理として動作 register register register メモリ data code stack main() stack func1() stack func2() 2018/4/23 第 3 回オペレーティングシステム 5

6 スレッドの実現方法 ユーザレベルスレッド ユーザライブラリで実現 カーネルレベルスレッド オペレーティングシステムがカーネルで実現 2018/4/23 第 3 回オペレーティングシステム 6

7 ユーザレベルスレッド ユーザモードで動作するライブラリで実現 多くの場合 setjmp()/longjmp() で実装 フレーム情報の保存と復元 各スレッドは別の起点フレームを保持 カーネルレベルスレッドより軽量 高速のコンテクスト切り換え 大量のスレッド生成が可能 スケジューリングの方針等の変更が手軽 threadc threadb threada 2018/4/23 第 3 回オペレーティングシステム 7 main

8 ユーザレベルスレッド スケジューリングの面倒をカーネルが見ない 処理を横取りできない or 横取りの実現が面倒 入出力等でスレッドが待ち状態になると 同一プロセス内の他の実行可能スレッドが実行不可能 (I/O ブロック ) システムコールライブラリの wrapper 等で対処 実行コアが複数でも並列に実行不可能 threadc threadb threada 2018/4/23 第 3 回オペレーティングシステム 8 main

9 カーネルレベルスレッド カーネル内でプロセスと同様の手法でスレッドを管理 サイズ : スレッド制御ブロック (Thread Control Block)< PCB スレッドはカーネルによるスケジューリングの対象 コンテクストスイッチ等の操作は カーネルモードで実行 カーネルモードとユーザモードの切り替えオーバヘッドが発生 ただし プロセスの切替よりは軽量 メモリ空間の切りえは不要だから 2018/4/23 第 3 回オペレーティングシステム 9

10 マルチスレッド実現モデル Many-to-One( 多対 1 モデル ) 複数のユーザレベルスレッドがカーネルで実現されているスレッドひとつに対応 One-to-One(1 対 1 モデル ) ひとつのユーザスレッドがカーネルで実現されているスレッドひとつに対応 Many-to-Many( 多対多モデル ) 複数のユーザレベルスレッドが複数のカーネルレベルスレッドに対応 2018/4/23 第 3 回オペレーティングシステム 10

11 マルチスレッドのモデル Many-to-One( 多対 1 モデル ) 一つのカーネルスレッドで複数のユーザスレッドを稼働 ライブラリでスケジューリングするため高速 カーネルの処理待ちできるのは 一つのスレッドのみ I/O でブロック process スケジューラ ユーザレベルスレッド 実装 Solaris Green Thread, GNU Portable Thread k カーネルレベルスレッド 2018/4/23 第 3 回オペレーティングシステム 11

12 マルチスレッドのモデル process One-to-One (1 対 1 モデル ) 一つのカーネルスレッドでただ一つのユーザスレッドが稼働 実装 他のスレッドの I/O ブロックと無関係 複数プロセッサで稼働 スレッド生成 管理のオーバヘッドが発生 Linux, Windows k k k k ユーザレベルスレッド カーネルレベルスレッド 2018/4/23 第 3 回オペレーティングシステム 12

13 マルチスレッドのモデル Many-to-Many( 多対多モデル ) 複数のユーザスレッドをその数以下のカーネルスレッドで稼働 カーネルスレッドの数はアプリケーションやマシンに応じて決定 スレッドをどう割り付けるかの制御が必要 process スケジューラ ユーザレベルスレッド k k k カーネルレベルスレッド 2018/4/23 第 3 回オペレーティングシステム 13

14 マルチスレッドのモデル 2 レベルモデル 多対多モデルのバリエーション 一部のユーザレベルスレッドを特定のカーネルスレッドに固定 (pin down) process ユーザレベルスレッド 実装 IRIX, HP-UX, Tru64 UNIX Solaris (before ver. 9) スケジューラ k k k カーネルレベルスレッド 2018/4/23 第 3 回オペレーティングシステム 14

15 Linux Threads POSIX Pthread が提供されている スレッドライブラリの標準規格 (IEEE c) 多くのUnix 系システムで実装 Pthread 実現方法 clone() システムコール 2018/4/23 第 3 回オペレーティングシステム 15

16 マルチスレッドの利点 (1/2) 並列コンピュータ上でのプロセッサの有効利用 共有メモリ型並列コンピュータ上で プロセッサを有効利用が可能 マルチコアを活用可能 マルチコアの時代 半導体集積度が向上したが クロックを上げられない ( リーク電流 & 熱問題 ) 余った回路の使い道としてチップ内に複数プロセッサを搭載 2018/4/23 第 3 回オペレーティングシステム 16

17 マルチスレッドの利点 (2/2) 資源を共有可能 ファイルディスクリプタやメモリ領域の共有 メモリ管理のための構造体の共有 TLB の共有が可能 TLB の共有によりコンテキストスイッチ時に TLB flush が不必要 応答性の向上 例えばマルチスレッド WEB ブラウザでは イメージを読み込んでいるスレッドとユーザの入力を同時に処理が可能 シングルスレッドの場合は select を使った event driven 処理 2018/4/23 第 3 回オペレーティングシステム 17

18 スレッド利用の場面 サーバプロセスの応答性の向上 サーバプログラム 要求ごとにスレッドを生成し 処理と結果の応答を担当 例 :HTTPサーバ それぞれ別のスレッドでリクエストを処理 ウィンドウシステム それぞれ別のスレッドでイベントを待つ処理 2018/4/23 第 3 回オペレーティングシステム 18

19 スレッド利用の場面 CPU 処理と入出力処理の分割 プロセス P の処理を 計算を行うスレッド (Th1) と入出力を行うスレッド (Th2) に分割 Th1 と Th2 は 1 つのプログラムを実行 入出力待ちの間,Th2 は待ち状態になるが Th1 の処理は継続 Th2( 入出力 ) Th1( 計算 ) 依頼 入出力待ち 通知 2018/4/23 第 3 回オペレーティングシステム 19

20 スレッド利用の場面 並列計算 並列計算機を使って高速計算 例 : 行列の掛け算 各行を別スレッドで計算 メモリ空間を共有するので プロセス間通信するより高速 = 2018/4/23 第 3 回オペレーティングシステム 20

21 ( 補足 ) カーネルもマルチ化の時代 従来型のカーネル (SMP) マルチカーネル (AMP) VS OS Image OS Image OS Image OS Image 2018/4/23 第 3 回オペレーティングシステム 21

22 協調プロセス 独立プロセス : お互い影響なし 協調プロセス : プロセス同士で影響 協調プロセスの利点 性能向上 ある仕事を複数のサブタスクにわけて並列実行 ワーカー パイプライン データ並列 モジュラリティ 機能毎にプロセスが作られていれば それらを組み合わせて複雑な処理が実現可能 ps axwwl grep pts/1 more プロセスのリストをとりだし pts/1 デバイスを使用しているプロセスを探し more で表示した例 2018/4/23 第 3 回オペレーティングシステム 22

23 協調プロセス間のやり取り プロセス間でメモリを共有 プロセス間交信機能を提供 シグナルの使用など 2018/4/23 第 3 回オペレーティングシステム 23

24 共有メモリ上の Bounded-Buffer item nextproduced; while (1) { while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing */ buffer[in] = nextproduced; in = (in + 1) % BUFFER_SIZE; item nextconsumed; while (1) { while (in == out) ; /* do nothing */ nextconsumed = buffer[out]; このプログラムは正しく動かない! 後で説明 out = (out + 1) % BUFFER_SIZE; 2018/4/23 第 3 回オペレーティングシステム 24

25 プロセス間交信 協調プロセスを実現する別の方式 IPC(Inter Process Communication) とも プロセス間でのデータ交換および同期で使用 共有メモリを使用しない通信手段 IPC の基本操作 : 通信路の確立 send(message) receive(message) 通信路の後始末 2018/4/23 第 3 回オペレーティングシステム 25

26 blocking vs nonblocking synchronous vs asynchronous Blocking vs Nonblocking I/O 要求をすぐに処理できない時の対応の仕方による差 すぐに処理できないときの例 Receive/Read 時にデータが未到着 Send/Write 時に OS 内バッファがいっぱい Synchronous vs asynchronous I/O 要求側と I/O 処理側の関係による差 2018/4/23 第 3 回オペレーティングシステム 26

27 blocking vs nonblocking synchronous vs asynchronous blocking nonblocking synchronous receive read データが到着していなければ到着するまで待機 データが到着していなければ 到着しない旨通知 send write 処理が完了するまで待機 処理できない旨通知 asynchronous receive read データが到着たら通知 Send write バッファが一杯にならない限りは nonblocking バッファが一杯の時の挙動は様々 2018/4/23 第 3 回オペレーティングシステム 27

28 シグナル プロセスに対してある事象を通知 Unix や Linux の場合 kill システムコール (2) によりシグナルを通知 シグナルを受け付けるための関数は signal あるいは sigaction システムコール (2) により設定可能 シグナルの種類の確認 $ man 7 signal Unix 系では SIGHUP シグナルを受け取るとデータベースファイルを読み直すといった処理を行うようにプログラムを作ることが慣例 $ kill HUP <process ID> #include <stdio.h> #include <signal.h> int flag; void handle_sighup(int signum, siginfo_t *info, void *p) { printf("handle_sighup is invoked n"); flag = 0; main() { struct sigaction oldsigaction; struct sigaction newsigaction; newsigaction.sa_flags = SA_SIGINFO; sigemptyset(&newsigaction.sa_mask); newsigaction.sa_sigaction = handle_sighup; sigaction(sighup, &newsigaction, &oldsigaction); flag = 1; printf("start flag = %d n", flag); while (flag) { ; printf("start flag = %d n", flag); 2018/4/23 第 3 回オペレーティングシステム 28

29 協調プロセス実現 ここまでで説明した手法 共有メモリ IPC シグナル 2018/4/23 第 3 回オペレーティングシステム 29

30 共有メモリを使ったプロセス同期 背景 複数のプロセスが共有メモリ領域に読み書きするとデータの一貫性がなくなる データ一貫性のために何らかの機構が必要 クリティカルセクション問題 同期のためのハードウェア セマフォア (Semaphores) 古典的同期問題 2018/4/23 第 3 回オペレーティングシステム 30

31 Bounded-Buffer Producer Process Shared Data item nextproduced; #define BUFFER_SIZE 10 int in = 0; typedef struct { while (1) {... while (counter == BUFFER_SIZE) item; ; /* do nothing */ item buffer[buffer_size]; int counter = 0; buffer[in] = nextproduced; in = (in + 1) % BUFFER_SIZE; counter++; Consumer Process item nextconsumed; 以下の式は不可分 (atomic) に実行され int out = 0; るべき while (1) { counter++; while (counter == 0) counter--; ; /* do nothing */ 不可分操作 (Atomic operation) とは その操作が終了するまでは他の命令が nextconsumed = buffer[out]; 実行されないこと out = (out + 1) % BUFFER_SIZE; 次のスライドを参照 counter--; 2018/4/23 第 3 回オペレーティングシステム 31

32 Bounded Buffer count++ はどう実行されるか 1. register1 counter 2. register1 register counter register1 CPU 0 register 10 counter 10 count--はどう実行されるか I. register1 counter II. register1 register1 1 III. counter register1 実行順序によるcounter 値の違い : CPU 1 register I II. III. 1. I. II. III I. II. III. 2018/4/23 第 3 回オペレーティングシステム 32

33 ( 補足 ) マルチスレッドでの競合 int x = 1; int func1() { x=x-1; int func2() { x=x-1; 最後に x はいくつ? -1? プロセススレッド M スレッド 1 スレッド 2 int main() { create_thread(func1); create_thread(func2); return (x); メモリ x=1 code register register register stack stack stack main() func1() func2() 2018/4/23 第 3 回オペレーティングシステム 33

34 ( 補足 ) マルチスレッドでの競合 x = x - 1 の処理は 1. レジスタに x の値を読んできて (load) 2. レジスタに -1 を加えて (add -1) 3. レジスタの中身を x に書き戻し (store) つまり Thread の場合も同じことが起きうる CPU が一つなら起きない? -1 x /4/23 第 3 回オペレーティングシステム 34

35 ( 補足 ) コンテキストスイッチにおける競合 CPU は横取りされる! code (text) 演算ユニット code (text) x を読んだあと 書き戻す前に横取りされたら? data bss heap プログラムカウンタ (PC) レジスタ data bss heap フレームポインタ TCB (PCB) TCB (PCB) 保存と復元 auto 変数リターンアドレス引数など auto 変数リターンアドレス引数など 各領域のアドレス CPU auto 変数リターンアドレス引数など auto 変数リターンアドレス引数など 2018/4/23 第 3 回オペレーティングシステム 35

36 Race Condition( 競合状態 ) Race condition 複数のプロセスが共有メモリを同時にアクセス ( 読み書き ) している時 ( 状態で ) その共有メモリの最終的な値が 最後にその共有メモリのアクセスを終了したプロセスに依存すること 複数のプロセスが先の counter 値を変更している時は Race Condition Race condition を回避するために プロセス同士の同期が必要 2018/4/23 第 3 回オペレーティングシステム 36

37 補足 Th1: x = x - 1; Th2: x = x - 1; 1. load x 2. add store x P1(P2) だけに注目すれば 1,2,3 の順 実行例 : Th1 Th2 Th1 Th2 Th1 Th スケジューリングや時の運で決まる x: -1 x: 0 x: /4/23 第 3 回オペレーティングシステム 37

38 クリティカルセクション問題 Critical Section: 複数のプロセスがある共有メモリ領域を競合するアクセスをしている (read と write) 時 競合アクセスしているプログラム部分 Critical Section 問題 あるプロセスが Critical Section を実行しているとき 他のプロセスにはその Critical Section を実行しないようにさせること Critical Section= きわどい領域 2018/4/23 第 3 回オペレーティングシステム 38

39 クリティカルセクション問題における要求事項 1. Mutual Exclusion( 排他制御 ) もしプロセス Pi がクリティカルセクションを実行しているとき 他のプロセスがそのクリティカルセクションの実行が不可能 2. Progress もしどのプロセスもクリティカルセクションを実行していなくて かつ ある複数のプロセスがクリティカルセクションに入りたいとき どれかは必ず選ばれて実行 3. Bounded Waiting あるプロセスがクリティカルセクションに入りたいと要求してから有限時間でクリティカルセクションに突入 2018/4/23 第 3 回オペレーティングシステム 39

40 ここでの仮定 クリティカルセクション内で実行が中断 (I/O wait やスケジューリング等 ) する場合 マルチプロセッサ上での話 なお シングルプロセッサにおけるクリティカルセクション問題は以下で解決が可能 クリティカルセクションに入る前に割り込み禁止に変更 クリティカルセクションから出る時に割り込み可能に変更ただしクリティカルセクションの中で実行が中断してはいけない ( スケジューラを呼んではいけない ) 2018/4/23 第 3 回オペレーティングシステム 40

41 同期のためのハードウエア (1) Test and Set 命令 メモリ領域に 1 をセットし 昔のメモリ領域の値を返す ( 以下のプログラム参照 ) これを処理をアトミック ( 不可分 ) に処理 boolean TestAndSet(boolean *target) { boolean rv = *target; *target = 1; return rv; 2018/4/23 第 3 回オペレーティングシステム 41

42 共有データ : Test-and-Set 命令を使った Mutual Exclusionの実現 boolean lock = false; Process P i do { while (TestAndSet(&lock)) ; critical section lock = false; remainder section 2018/4/23 第 3 回オペレーティングシステム 42

43 同期のためのハードウエア (2) Swap 命令 2 つの変数の値を不可分に入れ替え void Swap(boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp; 2018/4/23 第 3 回オペレーティングシステム 43

44 Swap 命令を使った Mutual Exclusion の実現 共有データ (initialized to false): Process P i boolean lock; boolean waiting[n]; do { key = true; while(key == true) Swap(&lock,&key); critical section lock = false; remainder section 2018/4/23 第 3 回オペレーティングシステム 44

45 Lock-free と Wait-free を用いた同期 Wait-free な実装 すべてのプロセスが 任意の有限ステップで終わる命令を ほかのプロセスの実行速度に無関係に実行できることが保証されていること つまりクリティカルセクションにおいて test_and_set や swap などを用いた Lock を行う実装は Wait-free ではない Lock-free な実装 いくつかのプロセスが 任意の有限ステップで終わる命令を ほかのプロセスの実行速度に無関係に実行できることが保証されていること Lock-free アルゴリズムでは 飢餓状態になるスレッドが発生してもよい Wait-free な実装では Lock-free になっているが その逆は真ではない 2018/4/23 第 3 回オペレーティングシステム 45

46 Compare and Swap Compare/Swap 命令 対象のアドレスの値をある値と比較し もしそれが同じなら新たな値をそのアドレスに書き込み ( 以下のプログラムを参照 ) これを不可分 ( アトミック ) に処理 int CAS (int *target, int old, int new) { int temp = *target; if (temp == old) *target = new; return temp; shared_obj shared_obj *old_sop, *new_sop, *t_sop; new_sop = malloc( ); do { old_sop = sop; modify(new_sop, old_sop); t_sop = CAS(sop, old_sop, new_sop); while (t_sop!= old_sop); /* modified by others */ free(old_sop); *sop = malloc( ); shared_obj *old_sop, *new_sop, *t_sop; new_sop = malloc( ); do { old_sop = sop; modify(new_sop, old_sop); t_sop = CAS(sop, old_sop, new_sop); while (t_sop!= old_sop); /* modified by others */ free(old_sop); 2018/4/23 第 3 回オペレーティングシステム 46

47 ABA 問題 ABA は略語ではない ABAはある変数の値 ABAは ある変数の値がAからBに変更され 再びAに戻ること shared_obj *old_sop, *new_sop, *t_sop; new_sop = malloc( ); do { old_sop = sop; modify(new_sop, old_sop); t_sop = CAS(sop, old_sop, new_sop); while (t_sop!= old_sop); /* modified by others */ free(old_sop); new_sop = malloc( ); do { 同じメモリ領域が割り当てられている old_sop = sop; modify(new_sop, old_sop); t_sop = CAS(sop, old_sop, new_sop); while (t_sop!= old_sop); /* modified by others */ shared_obj *old_sop, *new_sop, *t_sop; new_sop = malloc( ); do { old_sop = sop; modify(new_sop, old_sop); t_sop = CAS(sop, old_sop, new_sop); while (t_sop!= old_sop); /* some process has modified */ 2018/4/23 第 3 回オペレーティングシステム 47

48 回避策 tag ビットの導入 ABA 問題 例 : ある共有オブジェクトが常に 32 バイトアラインされているとき 下位 5 ビットは常に 0 それを tag として活用 この場合の tag ビットが扱える数は有限なので ABA 問題を完全には解決できていない 2018/4/23 第 3 回オペレーティングシステム 48

49 方法 RCU (Read-Copy Update) RCU 参照側クリティカルセクションでは 共有メモリにはポインタ経由でアクセス システムはそのポインタの使用状況をすべて追跡 変更が加わるたびにコピーが作られ それに対して変更を適用 変更前のデータ構造の読み込みがすべて終了した段階で ポインタを新たに作成したコピーに対するものに変更 2018/4/23 第 3 回オペレーティングシステム 49

50 RCU (Read-Copy Update) rcu_assign() Updater Reader rcu_dereference() synchronize_rcu() call_rcu() rcu_read_lock() rcu_read_unlock() Reclaimer updates into removal and "reclamation" phases rcu_read_lock() Reader が参照側クリティカルセクションに入る前に呼び出し rcu_read_unlock() 参照側クリティカルセクションから抜けるときに呼び出し synchronize_rcu() / call_rcu() Updater コードの終わりと reclaimer コードの終わりをマーク すべての参照側クリティカルセクションの完了をまつ なお 後続の RCU 参照側クリティカルセクションの終了を待つ必要なし rcu_assign_pointer() Updater はこの関数を利用することで RCU で保護されたポインタに新たな値を代入 rcu_dereference() Reader はこの関数を利用して RCU で保護されたポインタを確保 2018/4/23 第 3 回オペレーティングシステム 50

51 特徴 RCU (Read-Copy Update) Wait-free な読み込みが可能 RCU は 古い状態のデータ構造を一定期間そのまま残す必要があるため 大量のメモリを使用する可能性あり 2018/4/23 第 3 回オペレーティングシステム 51

52 Locking の問題点 Transactional Memory メニーコア環境下で効率的に処理を行うことは困難 Compare_and_Swap の問題点 複数の変更がある場合 アルゴリズムが複雑化 Transactional Memory 一部のメモリ領域に対して シリアライズされた 読み込みー変更ー書き込み という操作が可能 Lock-free 2018/4/23 第 3 回オペレーティングシステム 52

53 pthread_mutex_lock(pthread_mutex_t *mutex) The mutex object referenced by mutex shall be locked by calling pthread_mutex_lock(). If the mutex is already locked, the calling thread shall block until the mutex becomes available. This operation shall return with the mutex object referenced by mutex in the locked state with the calling thread as its owner. If the mutex type is PTHREAD_MUTEX_NORMAL, deadlock detection shall not be provided. Attempting to relock the mutex causes deadlock. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, undefined behavior results. If the mutex type is PTHREAD_MUTEX_ERRORCHECK, then error checking shall be provided. If a thread attempts to relock a mutex that it has already locked, an error shall be returned. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error shall be returned. If the mutex type is PTHREAD_MUTEX_RECURSIVE, then the mutex shall maintain the concept of a lock count. When a thread successfully acquires a mutex for the first time, the lock count shall be set to one. Every time a thread relocks this mutex, the lock count shall be incremented by one. Each time the thread unlocks the mutex, the lock count shall be decremented by one. When the lock count reaches zero, the mutex shall become available for other threads to acquire. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error shall be returned. If the mutex type is PTHREAD_MUTEX_DEFAULT, attempting to recursively lock the mutex results in undefined behavior. Attempting to unlock the mutex if it was not locked by the calling thread results in undefined behavior. Attempting to unlock the mutex if it is not locked results in undefined behavior. 2018/4/23 第 3 回オペレーティングシステム 53

54 pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) The pthread_cond_wait() functions shall block on a condition variable. They shall be called with mutex locked by the calling thread or undefined behavior results. These functions atomically release mutex and cause the calling thread to block on the condition variable cond; atomically here means "atomically with respect to access by another thread to the mutex and then the condition variable". That is, if another thread is able to acquire the mutex after the about-to-block thread has released it, then a subsequent call to pthread_cond_broadcast() or pthread_cond_signal() in that thread shall behave as if it were issued after the about-to-block thread has blocked. Upon successful return, the mutex shall have been locked and shall be owned by the calling thread. pthread_cond_signal(pthread_cond_t *cond) The pthread_cond_signal() function shall unblock at least one of the threads that are blocked on the specified condition variable cond (if any threads are blocked on cond). 2018/4/23 第 3 回オペレーティングシステム 54

55 Pthread (1/2) int pthread_create(pthread_t *thread, pthread_attr_t * attr, void * (*start_routine)(void *), void * arg); void pthread_exit(void *retval); int pthread_join(pthread_t th, void **thread_return); int pthread_detach(pthread_t th); pthread_t pthread_self(void); int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutex attr_t *mutexattr); int pthread_mutex_lock(pthread_mutex_t *mutex)); int pthread_mutex_trylock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex); int pthread_mutex_destroy(pthread_mutex_t *mutex); int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr); Int pthread_cond_signal(pthread_cond_t *cond); int pthread_cond_broadcast(pthread_cond_t *cond); Int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); int pthread_cond_timedwait(pthread_cond_t *cnd, pthread_mutex_t *mtx, const struct timespec *at); int pthread_cond_destroy(pthread_cond_t *cond); int pthread_barrier_init ( pthread_barrier_t * barri, const pthread_barrierattr_t * attr, unsigned int cnt ); int pthread_barrier_destroy ( pthread_barrier_t * barrier ); int pthread_barrier_wait ( pthread_barrier_t * barrier ); 2018/4/23 第 3 回オペレーティングシステム 55

56 Pthread (2/2) ipthread_attr_init, pthread_attr_destroy, pthread_attr_setdetachstate, pthread_attr_getdetachstate, pthread_attr_setschedparam, pthread_attr_getschedparam, pthread_attr_setschedpolicy, pthread_attr_getschedpolicy, pthread_attr_setinheritsched, pthread_attr_getinheritsched, pthread_attr_setscope, pthread_attr_getscope pthread_attr_init, pthread_setschedparam, pthread_getschedparam, pthread_equal 2018/4/23 第 3 回オペレーティングシステム 56

57 Bounded Buffer using pthread (1/3) #include <stdlib.h> #include <stdio.h> #include <pthread.h> #define N_ITEM 8 #define N_PRODUCER 4 #define N_CONSUMER 4 #define BSIZE 8 int buf[bsize]; int count; int in, out; int waiting; pthread_mutex_t bbmutex; pthread_cond_t bbcond; pthread_barrier_t pbarrier; void bbinit() { pthread_mutex_init(&bbmutex, NULL); pthread_cond_init(&bbcond, NULL); in = out = waiting = 0; main() { int i, cc; pthread_t pth[n_producer+n_consumer]; void *retval; pthread_barrier_init(&pbarrier, 0, N_PRODUCER+N_CONSUMER); for (i = 0; i < N_PRODUCER; i++) { cc = pthread_create(&pth[i], NULL, producer, 0); if (cc!= 0) { perror("main"); exit(-1); for (i = 0; i < N_CONSUMER; i++) { cc = pthread_create(&pth[i + N_PRODUCER], NULL, consumer, 0); if (cc!= 0) { perror("main"); exit(-1); for (i = 0; i < (N_PRODUCER + N_CONSUMER); i++) { pthread_join(pth[i], &retval); pthread_detach(pth[i]); if (cc!= 0) { perror("main"); exit(-1); exit(0); 2018/4/23 第 3 回オペレーティングシステム 57

58 Bounded Buffer using pthread (2/3) void *producer(void *arg) { int ret = 0; int i; pthread_barrier_wait(&pbarrier); for (i = 0; i < (N_CONSUMER*N_ITEM)/N_PRODUCER; i++) put(i); pthread_exit(&ret); return 0; void *consumer(void *arg) { int ret = 0; int val; int i; pthread_barrier_wait(&pbarrier); for (i = 0; i < N_ITEM; i++) { val = get(i); pthread_exit(&ret); return 0; 2018/4/23 第 3 回オペレーティングシステム 58

59 Bounded Buffer using pthread (3/3) int get() { int val; pthread_mutex_lock(&bbmutex); retry: if (count > 0) { val = buf[out]; --count; out = (out + 1) % BSIZE; if (waiting) { pthread_cond_signal(&bbcond); else { waiting++; pthread_cond_wait(&bbcond, &bbmutex); --waiting; goto retry; pthread_mutex_unlock(&bbmutex); return val; void put(int val) { pthread_mutex_lock(&bbmutex); retry: if (count < BSIZE) { buf[in] = val; count++; in = (in + 1) % BSIZE; if (waiting) { pthread_cond_signal(&bbcond); else { waiting++; pthread_cond_wait(&bbcond, &bbmutex); --waiting; goto retry; pthread_mutex_unlock(&bbmutex); return; 2018/4/23 第 3 回オペレーティングシステム 59