PDF版

オペレーティング
システム
第7回
---並行プロセス
排他制御基礎
続き
---同期をとろうとすると
(排他制御をしようとすると)
デッドロックの可能性が生じる
---sleep&wakeupで
同期をとろうとして
デッドロックが生じる理由
↓
sleepすべきかどうかの判断と
sleep実行が非アトミック
---そこで
dijkstraによって
発明されたのが
---[[EM:セマフォ]]
構造体
（１）非負整数
（２）待ち行列
---プリミティブ
（基本命令）
down(&S)　（P(S)）
up(&S)　（V(S)）
Sはセマフォのこと
---down(&S)
[[PRE:
if Sの整数値が正 {
整数値を1減らす
実行継続
} else { /* Sの整数値が0 */
Sの待ち行列に登録
待ち状態に遷移
}
]]
---up(&S)
[[PRE:
if Sの待ち行列が空でない {
待ちプロセスを1つ実行可能状態へ遷移
upしたプロセスも実行可能状態へ遷移
} else {
Sの整数値を1増やす
実行継続
}
]]
---ポイント
down命令，up命令はアトミック
↓
TS命令を使って作る
---セマフォによる排他制御
Entry Sequence
↓
down(&S)
Exit Sequence
↓
up(&S)
Sの整数値の初期値は1
2以上にはならない
---Sの整数値が0か1のみ
↓
[[EM:バイナリセマフォ]]
≒
[[EM:ミューテックス]]
mutex
---mutexのプリミティブ
lock(mutex)
unlock(mutex)
---lock(mutex)
mutexをロック
すでにロックされていれば
後からロックしようとした
プロセスは待ち状態に遷移
---unlock(mutex)
mutexをアンロック
待ち状態のプロセスがあれば
1つを選んで/すべて
実行可能状態に遷移させる
---mutexの使い方
[[PRE:
lock(mutex)
クリティカルセクション
unlock(mutex)
]]
---実験してみよう
---[[PRE:
01: #include <stdio.h>
02: #include <stdlib.h>
03: #include <pthread.h>
04:
05: #define N 10000000
06:
07: pthread_mutex_t mutex;
08:
09: int n = 0;
10:
11: int read_data()
12: {
13: return n;
14: }
15:
16: void write_data(int x)
17: {
18: n = x;
19: }
20:
21: void *inc(void *param)
22: {
23: int i, x;
24:
25: puts("starting inc thread");
26: for (i = 0; i < N; i++) {
27:
pthread_mutex_lock(&mutex);
28:
x = read_data();
29:
x++;
30:
write_data(x);
31:
pthread_mutex_unlock(&mutex);
32: }
33: }
34:
35: void *dec(void *param)
36: {
37: int i, x;
38:
39: puts("starting dec thread");
40: for (i = 0; i < N; i++) {
41:
pthread_mutex_lock(&mutex);
42:
x = read_data();
43:
x--;
44:
write_data(x);
45:
pthread_mutex_unlock(&mutex);
46: }
47: }
48:
49: int main()
50: {
51: pthread_t it, ot;
52:
53: pthread_mutex_init(&mutex, NULL);
54: printf("n = %d\n", n);
55: pthread_create(&it, NULL, &inc, NULL);
56: pthread_create(&ot, NULL, &dec, NULL);
57: pthread_join(it, NULL);
58: pthread_join(ot, NULL);
59: printf("n = %d\n", n);
60: return 0;
61: }
]]
---セマフォによる同期
生産者・消費者問題
---[[PRE:
#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
p01: void producer(void)
c01: void consumer(void)
p02: {
c02: {
p03: int item;
c03: int item;
p04: while (1) {
c04: while (1) {
p05:
item = produce_item(); c05:
down(&full);
p06:
down(&empty);
c06:
down(&mutex);
p07:
down(&mutex);
c07:
item = remove_item();
p08:
insert_item(item);
c08:
up(&mutex);
p09:
up(&mutex);
c09:
up(&empty);
p10:
up(&full);
c10:
consume_item(item);
p11: }
c11: }
p12: }
c12: }
]]
---前のプログラムをリライト
（１）c05-c07　→　down(&count)
（２）countをfullにリネームしてセマフォ化
（３）セマフォempty=N-countを導入
（４）p06-p08　→　down(&empty)
（５）c09-c10　→ up(&empty)
（６）p10-p11　→ up(&count)
（７）バッファの読み書きをmutexで保護
---セマフォの問題点
↓
間違えやすい
---間違ったプログラム
[[PRE:
#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
p01: void producer(void)
c01: void consumer(void)
p02: {
c02: {
p03: int item;
c03: int item;
p04: while (1) {
c04: while (1) {
p05:
item = produce_item(); c05:
down(&full);
p06:
down(&mutex);
c06:
down(&mutex);
p07:
down(&empty);
c07:
item = remove_item();
p08:
insert_item(item);
c08:
up(&mutex);
p09:
up(&mutex);
c09:
up(&empty);
p10:
up(&full);
c10:
consume_item(item);
p11: }
c11: }
p12: }
c12: }
]]
---正しいプログラム
[[PRE:
#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
p01: void producer(void)
c01: void consumer(void)
p02: {
c02: {
p03: int item;
c03: int item;
p04: while (1) {
c04: while (1) {
p05:
item = produce_item(); c05:
down(&full);
p06:
down(&empty);
c06:
down(&mutex);
p07:
down(&mutex);
c07:
item = remove_item();
p08:
insert_item(item);
c08:
up(&mutex);
p09:
up(&mutex);
c09:
up(&empty);
p10:
up(&full);
c10:
consume_item(item);
p11: }
c11: }
p12: }
c12: }
]]
---producerの
2つのdown命令の
順番が入れ替わっている
---もし
producerが
down(&mutex)に成功し，
down(&empty)で待ち状態に
なったら
---consumerが
down(&mutex)で
待ち状態になる
↓
デッドロック

Download Report