Classical Problems of Synchronization

Bounded-Buffer Problem

(=Producer-Consumer Problem、生産者消費者問題)
=共有バッファサイズが限られている環境での問題
生産者-消費者問題

両生産者又は消費者が同時にデータにアクセスする場合

.

消費者/生産者はおらず、生産者/消費者のみが文章(資源不足)

を持っている.
共有バッファには、次の2つのプロセスがあります.

バッファにデータを入れる

Empty buffer(リソース)はありますか?(待機不要)

ロック

共有データ

Empty bufferにおけるデータ入力とバッファ動作

ロック

を開く

完全バッファ(ポインタ)

を追加
Consumer(バッファからデータを取り出す)

フルバッファ(リソース)はありますか?(待機不要)

ロック

共有データ

Full Bufferからデータを取り出すバッファ動作

を行う.

ロック

を開く
Empty buffer(ポインタ)を追加

同期の問題はいつ発生しますか?

リソースへの同時アクセス
Producerの場合

アイドルバッファの2人の生産者は、バッファが空であることを見て、バッファを同時に充填しようとした.

共有バッファにロックを提供し、他の生産者または消費者がバッファにアクセスしないようにする必要があります.

Consumerの場合:

の1つのバッファデータについて、2つのConsumerは同時に取り出して食べようとした.

共有バッファにロックを提供し、他の生産者または消費者が作業中のバッファ

にアクセスすることを防止する.

Bounded Bufferによる問題

リソースの観点から
Producer

アイドルバッファは、リソース

である.

バッファが満たされている場合、

はリソースなし(空き領域なし)です.
Consumer

充填バッファはリソース

である.

バッファが全て空の場合、

となる.
Shared Data

Buffer自体とBuffer操作変数(空/満Bufferの開始位置)

Synchronized Variable

ロック制御変数=バイナリ信号量

が必要

Resource(バッファ)count変数=必要整数信号量(空き/フルバッファ数)

// - Producer
do {
    produce an item in x
        ...
    P(empty);             // 빈 퍼버가 있는지 확인
    P(mutex);             // 있다면, lock을 건다
        ...
    add x to buffer
        ...
    V(mutex);             // lock을 푼다
    V(full);              // full buffer의 개수 1 증가
}
​
// - Consumer
do {
    P(full);              // full 버퍼가 있는지 확인
    P(mutex);             // 있다면, lock을 건다
        ...
    remove an item from buffer to y
        ...
    V(mutex);             // lock을 푼다
    V(empty);             // empty buffer의 개수 1 증가
        ...
    consume the item in y
}

リーダ-ライタの問題

=readerとwriterの2つのプロセスがデータベースを共有する環境

質問する

あるプロセスがデータベース(共有リソース)に書き込まれている場合、別のプロセスはにアクセスできません.

読み、複数同時読み(=>すべての場合ロックが無効)

解決策

作成者は、データベースへのアクセス許可を取得することなく、待機中のすべてのリーダがデータベース

にアクセスできるようにする.

リーダーは、データベース

にアクセスできます.

ライタは、1つのリーダが待機していない場合に、

へのデータベースアクセスを許可する.

作成者がデータベースにアクセスしていると、リーダーは

へのアクセスを禁止されます.

ライタは、リーダ

にアクセスするためにデータベースを離れる必要があります.
Shared Data

DB自体

read count=現在データベースにアクセスしているリーダーの数

Synchronized Variable

反発体=リードカウントにアクセスするコード反発(リードがリードカウントをロックする)

を確保する.

db=リーダとライタが共有データベースに正しくアクセスできる役割(データベースのロック)

// - Writer
P(db);                  // writer가 들어가면 lock을 건다
...
writing DB is performed
...
V(db);                  // lock을 풀어줌
​
// - Reader
P(mutex);               // readcount를 증가시키기 위한 lock 걸기
readcount++;            // readcount 1 증가
if (readcount == 1) P(db); // 내가 처음 들어온 reader라면 DB lock 걸기
V(mutex);               // readcount에 대한 lock 풀기
...
reading DB is performed
...
P(mutex);               // readcount를 감소시키기 위한 lock 걸기
readecount--;
if (readcount == 0) V(db); // 내가 마지막 reader라면 DB lock 풀기
V(mutex);               // readcount에 대한 lock 풀기

致命的な問題

飢餓が発生する可能性があります

読者群が非常に多い中、最後の読者が去る前に、また多くの読者群が来ていました…=writerは、データベース

にいつアクセスできるか分かりません.

改善方法
△信号があれば、いつか過ごせる!

Dining Philosopher Problem(食事哲学者問題)

5人の哲学者は2つの行為をすることができる:思考と/または食事.
隣の哲学者の間で箸を共有するのは、左右の2つの箸を手に入れてこそ食事ができる.

Synchronization variables

semaphore chopsticks[5]; (初期値はいずれも1:

)

Philosopher i
do {
    P(chopstick[i]);            // 왼쪽 젓가락을 잡는 행위
    P(chopstick[(i+1) % 5]);    // 오른쪽 젓가락을 잡는 행위
    ...
    eat();                      // 밥 먹는 중..
    ...
    V(chopstick[i])             // 왼쪽 젓가락 놓기
    V(chopstick[(i+1) % 5])     // 오른쪽 젓가락 놓기
    ...
    think();
}

に質問

=デッドロックの可能性(すべての哲学者が同時にお腹が空いたら、左箸を取った)

ソリューション

4人の哲学者だけが机の上に同時に座っている.

両方の箸を挟むことができる時だけ箸を挟むことができます.

非対称(偶数/奇数)哲学者は左/右箸から挟む(同じ箸!)

へんすう

enum { thinking, hungry, eating } state[5]; (상태표현)
semaphore self[5] = 0; (젓가락 두 개 확보 가능해 밥먹을 권리 부여)
semaphore mutex = 1; (상태를 동시에 바꾸지 못하도록 lock걸기)

// Philosopher i
do {
    pickup(i);
    eat();
    putdown(i);
    think();
}
​
void pickup(int i) {
    P(mutex);           // 상태 바꾸기 전 lock 걸기
    state[i] = hungry;  // hungry로 상태 변경
    test(i);            // 젓가락 둘 다 집을 수 있는지 테스트
    V(mutex);           // lock 풀고
    P(self[i]);         // 밥 먹을 수 있는 권리 해제(1->0)
}
​
void test(int i) {
    if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating) {// 양쪽 철학자가 먹고있지 않고 내가 배고플 때
        state[i] = eating; // eating으로 상태 변경
        V(self[i]);        // 밥 먹을 수 있는 권리 부여(0->1)
    }
}
​
void putdown(int i) {
    P(mutex);
    state[i] = thinking;
    test((i+4)%5);      // 혹시 나 땜에 못먹었는지 양쪽 철학자 테스트
    test((i+1)%5);
    V(mutex);
}

Semaphoreの質問

符号化が困難

正確性を証明するのは難しい

アクティブな協力が必要

エラーはすべてのシステムに致命的です
=V,P演算を誤って置き換えると,反発性が損なわれる.同じ演算をうっかり使うと、Deadlock.

資料の出所

班孝敬教授OSオンライン講座