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

(1)

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

加藤真平

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

[email protected]

2018/4/23 第3回オペレーティングシステム 1

１．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/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

(4)

スレッド

• Thread of Control

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

– 単にスレッドとも

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

かすような実行モデル

＝マルチスレッドモデル

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

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

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

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

から1980年代

(5)

補足

• スレッドの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(); } マルチスレッド単一スレッド

(6)

スレッドの実現方法

• ユーザレベルスレッド

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

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

(7)

ユーザレベルスレッド

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

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

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

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

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

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

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

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

main threadA threadB threadC 2018/4/23 第3回オペレーティングシステム 7

(8)

ユーザレベルスレッド

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

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

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

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

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

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

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

threadA threadB threadC

(9)

カーネルレベルスレッド

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

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

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

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

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

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

– メモリ空間の切りえは不要だから

(10)

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

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

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

レッドひとつに対応

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

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

ひとつに対応

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

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

に対応

(11)

マルチスレッドのモデル

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

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

複数のユーザスレッドを稼働

– ライブラリでスケジューリング

するため高速

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

一つのスレッドのみ

• I/Oでブロック

• 実装

– Solaris Green Thread,

– GNU Portable Thread

k

process ユーザレベルスレッドカーネルレベルスレッド

スケジューラ

(12)

マルチスレッドのモデル

• One-to-One

（1対1モデル）

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

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

が稼働

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

クと無関係

– 複数プロセッサで稼働

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

バヘッドが発生

• 実装

– Linux, Windows

k process ユーザレベルスレッドカーネルレベルスレッド k k k

(13)

マルチスレッドのモデル

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

– 複数のユーザスレッドを

その数以下のカーネル

スレッドで稼働

– カーネルスレッドの数は

アプリケーションやマシン

に応じて決定

– スレッドをどう割り付けるか

の制御が必要

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

スケジューラ

process 2018/4/23 第3回オペレーティングシステム 13

(14)

マルチスレッドのモデル

• 2レベルモデル

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

– 一部のユーザレベル

スレッドを特定のカーネル

スレッドに固定(pin down)

• 実装

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

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

スケジューラ

process

(15)

Linux Threads

• POSIX Pthreadが提供されている

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

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

• Pthread実現方法

– clone() システムコール

(16)

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

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

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

が可能

– マルチコアを活用可能

• マルチコアの時代

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

流＆熱問題）

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

(17)

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

• 資源を共有可能

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

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

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

• 応答性の向上

– 例えばマルチスレッドWEBブラウザでは、イメージを読み込

んでいるスレッドとユーザの入力を同時に処理が可能

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

(18)

スレッド利用の場面

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

– サーバプログラム

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

• 例：HTTPサーバ

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

– ウィンドウシステム

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

(19)

スレッド利用の場面

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

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

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

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

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

処理は継続

Th2(入出力) Th1(計算) 通知入出力待ち依頼

(20)

スレッド利用の場面

• 並列計算

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

– 例：行列の掛け算

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

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

するより高速

×

＝

(21)

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

2018/4/23 第3回オペレーティングシステム 21 OS Image OS Image OS Image OS Image

従来型のカーネル（SMP）

マルチカーネル（AMP）

VS

(22)

協調プロセス

• 独立プロセス：お互い影響なし

• 協調プロセス：プロセス同士で影響

• 協調プロセスの利点

– 性能向上

• ある仕事を複数のサブタスクにわけて並列実行

– ワーカー、パイプライン、データ並列

– モジュラリティ

• 機能毎にプロセスが作られていれば、それらを組み合わ

せて複雑な処理が実現可能

– ps axwwl | grep pts/1 | more

(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; }

このプログラムは正しく動かない！

後で説明

(25)

プロセス間交信

• 協調プロセスを実現する別の方式

• IPC(Inter Process Communication)とも

• プロセス間でのデータ交換および同期で使用

• 共有メモリを使用しない通信手段

• IPC の基本操作:

– 通信路の確立

– send(message)

– receive(message)

– 通信路の後始末

(26)

blocking vs nonblocking

synchronous vs asynchronous

• Blocking vs Nonblocking

– I/O要求をすぐに処理できない時の対応の仕方による差

– すぐに処理できないときの例

• Receive/Read時にデータが未到着

• Send/Write時にOS内バッファがいっぱい

• Synchronous vs asynchronous

– I/O要求側とI/O処理側の関係による差

(27)

blocking vs nonblocking

synchronous vs asynchronous

blocking

nonblocking

synchronous

receive

read

データが到着していなけれ

ば到着するまで待機

データが到着していなければ、

到着しない旨通知

send

write

処理が完了するまで待機

処理できない旨通知

asynchronous

receive

read

データが到着たら通知

Send

write

バッファが一杯にならない限り

はnonblocking

バッファが一杯の時の挙動は

様々

(28)

シグナル

• プロセスに対してある事象を通知

• UnixやLinuxの場合、killシステム

コール(2)によりシグナルを通知

• シグナルを受け付けるための関数

はsignalあるいはsigactionシステム

コール(2)により設定可能

• シグナルの種類の確認

$ man 7 signal

• Unix系では、SIGHUPシグナルを

受け取るとデータベースファイル

を読み直すといった処理を行うよ

うにプログラムを作ることが慣例

#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) {

; }

(29)

協調プロセス実現

• ここまでで説明した手法

– 共有メモリ

– IPC

– シグナル

(30)

共有メモリを使ったプロセス同期

• 背景

– 複数のプロセスが共有メモリ領域に読み書きすると

データの一貫性がなくなる

– データ一貫性のために何らかの機構が必要

• クリティカルセクション問題

• 同期のためのハードウェア

• セマフォア（Semaphores）

• 古典的同期問題

(31)

Bounded-Buffer

item nextProduced;

int in = 0;

while (1) {

while (counter == BUFFER_SIZE)

; /* do nothing */

buffer[in] = nextProduced;

in = (in + 1) % BUFFER_SIZE;

counter++;

}

_{item nextConsumed；}

int out = 0;

while (1) {

while (counter == 0)

; /* do nothing */

nextConsumed = buffer[out];

out = (out + 1) % BUFFER_SIZE;

counter--;

}

#define BUFFER_SIZE 10

typedef struct {

. . .

} item;

item buffer[BUFFER_SIZE];

int counter = 0;

• 以下の式は不可分(atomic)に実行され

るべき

counter++;

counter--;

• 不可分操作（Atomic operation）とは、

その操作が終了するまでは他の命令が

実行されないこと

• 次のスライドを参照

Producer Process

Consumer Process

Shared Data

(32)

Bounded Buffer

• count++はどう実行されるか

1. register1 ← counter

2. register1 ← register1 + 1

3. counter ← register1

• count--はどう実行されるか

I. register1 ← counter

II. register1 ← register1 – 1

III. counter ← register1

counter

10 1. → I. → 2. → 3. → II. → III.

CPU 0

register

10 CPU 1

register

10 実行順序によるcounter値の違い：

1. → I. → ＩＩ. → ＩＩＩ. → 2. → 3.

(33)

（補足）マルチスレッドでの競合

• 最後にxはいくつ？

– -1 ?

code x=1 メモリ stack register スレッド M プロセス stack register スレッド 1 stack register スレッド 2

main() func1() func2()

int x = 1; int func1() { x=x-1; } int func2() { x=x-1; } int main() { create_thread(func1); create_thread(func2); return (x); }

(34)

• x = x - 1の処理は…

1. レジスタに x の値を読んできて (load)

2. レジスタに

-1 を加えて (add -1)

3. レジスタの中身を

x に書き戻し (store)

• つまりThreadの場合も同じことが起きうる

➡ CPUが一つなら起きない？

x

-1

（補足）マルチスレッドでの競合

(35)

（補足）コンテキストスイッチにおける競合

2018/4/23 第3回オペレーティングシステム 35 演算ユニット CPU code (text) data bss heap リターンアドレス引数など auto変数リターンアドレス引数など auto変数 code (text) data bss heap リターンアドレス引数など auto変数リターンアドレス引数など auto変数プログラムカウンタ(PC) レジスタフレームポインタ各領域のアドレス

CPUは横取りされる！

TCB (PCB) TCB (PCB)

保存と復元

xを読んだあと、書き戻す

前に横取りされたら？

(36)

Race Condition(競合状態)

• Race condition

– 複数のプロセスが共有メモリを同時にアクセス（読み書き）

している時（状態で）、その共有メモリの最終的な値が、最

後にその共有メモリのアクセスを終了したプロセスに依存す

ること

– 複数のプロセスが先のcounter値を変更している時は、Race

Condition

• Race conditionを回避するために、プロセス同士の同期

が必要

(37)

補足

• Th1: x = x - 1; Th2: x = x - 1;

1. load x

2. add -1

3. store x

Th1 Th2

1

2

3 x: -1

Th1 Th2

1

2

3 x: 0

1

2

3 x: 0

Th1 Th2

実行例：

P1(P2)だけに

注目すれば

1,2,3の順

スケジューリング

や時の運で決まる

(38)

クリティカルセクション問題

• Critical Section：複数のプロセスがある共有メモリ領域

を競合するアクセスをしている（readとwrite）時、競

合アクセスしているプログラム部分

• Critical Section問題

– あるプロセスがCritical Sectionを実行しているとき、他のプロ

セスにはそのCritical Sectionを実行しないようにさせること

• Critical Section＝「きわどい領域」

(39)

クリティカルセクション問題における要求事項

1. Mutual Exclusion（排他制御）

– もしプロセスPi がクリティカルセクションを実行している

とき、他のプロセスがそのクリティカルセクションの実行

が不可能

2. Progress

– もしどのプロセスもクリティカルセクションを実行してい

なくて、かつ、ある複数のプロセスがクリティカルセク

ションに入りたいとき、どれかは必ず選ばれて実行

3. Bounded Waiting

– あるプロセスがクリティカルセクションに入りたいと要求

してから有限時間でクリティカルセクションに突入

(40)

ここでの仮定

• クリティカルセクション内で実行が中断（I/O waitやス

ケジューリング等)する場合

• マルチプロセッサ上での話

• なお、シングルプロセッサにおけるクリティカルセク

ション問題は以下で解決が可能

– クリティカルセクションに入る前に割り込み禁止に変更

– クリティカルセクションから出る時に割り込み可能に変更

ただしクリティカルセクションの中で実行が中断してはいけな

い（スケジューラを呼んではいけない）

(41)

同期のためのハードウエア（１）

• Test and Set命令

– メモリ領域に１をセットし、昔のメモリ領域の値を返す（以

下のプログラム参照）

– これを処理をアトミック（不可分）に処理

boolean TestAndSet(boolean *target) { boolean rv = *target;

*target = 1; return rv; }

(42)

Test-and-Set命令を使った

Mutual Exclusionの実現

• 共有データ:

• Process P

_i

boolean lock = false;

do {

while (TestAndSet(&lock)) ;

critical section

lock = false;

remainder section

}

(43)

同期のためのハードウエア（2）

• Swap命令

– ２つの変数の値を不可分に入れ替え

void Swap(boolean a, boolean b) {

boolean temp = *a;

a = b;

*b = temp;

}

(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

}

(45)

Lock-free と Wait-freeを用いた同期

• Wait-freeな実装

– すべてのプロセスが、任意の有限ステップで終わる命令を、ほかのプロ

セスの実行速度に無関係に実行できることが保証されていること

– つまりクリティカルセクションにおいてtest_and_setやswapな

どを用いたLockを行う実装は、Wait-freeではない

• Lock-freeな実装

– いくつかのプロセスが、任意の有限ステップで終わる命令を、ほかのプ

ロセスの実行速度に無関係に実行できることが保証されていること

– Lock-freeアルゴリズムでは、飢餓状態になるスレッドが発生してもよい

– Wait-freeな実装ではLock-freeになっているが、その逆は真ではない

(46)

Compare and Swap

• Compare/Swap 命令

• 対象のアドレスの値をある値と比較し、もしそれが同じなら新たな値

をそのアドレスに書き込み（以下のプログラムを参照）

• これを不可分（アトミック）に処理

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);

do {

old_sop = sop;

shared_obj

*sop = malloc(…);

int CAS (int *target, int old, int new) {

int

temp = *target;

if (temp == old) *target = new;

return temp;

(47)

ABA問題

• ABA は略語ではない

• ABAはある変数の値

• ABAは、ある変数の値がAからBに変更され、再びAに戻ること

do {

old_sop = 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;

t_sop = CAS(sop, old_sop, new_sop); } while (t_sop != old_sop); /* modified by others */

do {

old_sop = sop;

} while (t_sop != old_sop); /* some process has modified */

同じメモリ領域が割り当てられている

(48)

ABA問題

• 回避策

– “tag”ビットの導入

• 例：ある共有オブジェクトが常に32バイトアラインさ

れているとき、下位5ビットは常に0

• それをtagとして活用

• この場合のtagビットが扱える数は有限なので、ABA問

題を完全には解決できていない

(49)

RCU (Read-Copy Update)

• 方法

– RCU参照側クリティカルセクションでは、共有メモリにはポイ

ンタ経由でアクセス

– システムはそのポインタの使用状況をすべて追跡

– 変更が加わるたびにコピーが作られ、それに対して変更を適用

– 変更前のデータ構造の読み込みがすべて終了した段階で、ポイ

ンタを新たに作成したコピーに対するものに変更

(50)

RCU (Read-Copy Update)

‒ rcu_read_lock()

‒ Readerが参照側クリティカルセクションに入る前に呼び出し

‒ rcu_read_unlock()

‒ 参照側クリティカルセクションから抜けるときに呼び出し

‒ synchronize_rcu() / call_rcu()

‒ Updaterコードの終わりとreclaimerコードの終わりをマーク ‒ すべての参照側クリティカルセクションの完了をまつ ‒ なお、後続のRCU参照側クリティカルセクションの終了を待つ必要なし

‒ rcu_assign_pointer()

‒ Updaterはこの関数を利用することで、RCUで保護されたポインタに新たな値を代入

‒ rcu_dereference()

‒ Readerはこの関数を利用して、RCUで保護されたポインタを確保

Updater

Reader

Reclaimer

rcu_read_lock()

rcu_read_unlock()

rcu_dereference()

rcu_assign()

synchronize_rcu()

call_rcu()

(51)

• 特徴

– Wait-freeな読み込みが可能

– RCUは、古い状態のデータ構造を一定期間そのまま残す必

要があるため、大量のメモリを使用する可能性あり

(52)

Transactional Memory

• Lockingの問題点

– メニーコア環境下で効率的に処理を行うことは困難

• Compare_and_Swapの問題点

– 複数の変更がある場合、アルゴリズムが複雑化

• Transactional Memory

– 一部のメモリ領域に対して、シリアライズされた「読み込

みー変更ー書き込み」という操作が可能

– Lock-free

(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.

(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.

• 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).

(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 );

(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

(57)

Bounded Buffer using pthread (1/3)

2018/4/23 第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); } 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;

(59)

Bounded Buffer using pthread (3/3)

2018/4/23 第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; } 59

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