Bounded-Buffer Problem
- Producer-Consumer Problem이라고도 불린다.
buffer의 사이즈가 n일 때, 각각의 버퍼는 하나의 아이템을 가질 수 있다.
- Producer : Buffer를 가득 채우는 것이 목표
- Consumer : Buffer를 빨리 비우는 것이 목표
변수 초기화
int n; //pool의 수
semaphore mutex = 1; //상호배제를 위한 Binary Semaphore
semaphore empty = n; // n -> 0
semaphore full = 0; // 0 -> n
Binary Semaphore : 상호 배제를 위해 이용. 값을 1로 초기화
Counting Semaphore : empty buffer는 n으로 초기화, full buffer는 0으로 초기화
Producer process
while (true) {
...
/* produce an item in next produced */
...
wait(empty); //empty-1
wait(mutex);
...
/* add next produced to the buffer */
while(count == bufferSize);
buffer[in] = next_produced; //채워넣는다.
...
signal(mutex);
signal(full); //full+1
}-
wait(empty)
Consumer가 buffer를 한 칸 비울 때 까지 대기 -
wait(mutex)
Producer가 여러 개일 때, buffer에 진입하면 Race Condition이 발생할 수 있다.
따라서 상호 배제를 위한 wait(mutex)실행
→ buffer가 한 칸 비어있고, 한 producer만 buffer에 진입한 것이 보장된다.
-
signal(mutex)
Critical Section의 Key 반납 -
signal(full)
buffer가 한 칸 찼다는 의미 → Consumer에게 전달
Consumer process
while (true) {
wait(full);
wait(mutex);
...
/* remove an item from buffer to next consumed */'
while(count==0);
next_consumed = buffer[out];//빈 버퍼를 넣는다.
...
signal(mutex);
signal(empty);
...
/* consume the item in next consumed */
...
}-
wait(full)
buffer가 한 칸 찰 때까지 대기. Producer가 signal(full)신호를 보내면 wait종료 -
wait(mutex)
Consumer가 여러 개일 때, buffer에 진입하면 Race Condition이 발생할 수 있다.
따라서 상호 배제를 위한 wait(mutex)실행
→ buffer가 한 칸 찼고, 한 consumer만 buffer에 진입한 것이 보장된다.
-
signal(mutex)
Critical Section의 Key 반납 -
signal(empty)
buffer가 한 칸 비었다는 의미 → Producer에게 전달
Readers-Writers Problem
Reader는 데이터를 읽기만 하는 프로세스, Writer는 읽고 수정하는 프로세스이다.
→ writer + writer, writer + reader 데이터에 동시에 접근 시 문제 발생 가능
How can we solve this problem?
만약, DB를 Critical Section으로 지정해서 하나의 프로세스만 접근할 수 있도록 상호 배제를 보장한다면 어떨까?
→ Reader는 데이터를 수정하지 않기 때문에 Data Consistency가 보장된다. 따라서 Mutex는 굉장히 비효율적일 것이다.
→ Reader는 동시에 접근할 수 있도록 하고, Writer는 상호 배제를 보장한다.
First readers-writers problem
- Reader에게 우선권 부여
- reader가 데이터 접근에 대한 우선권을 가진다.
- 계속해서 reader에 대한 접근 요청이 일어나면 writer에 기아 상태(starvation)에 빠질 수 있다.
Second readers-writers problem
- Writer에게 우선권 부여
- writer가 데이터 접근에 대한 우선권을 가진다.
- 계속해서 writer에 대한 접근 요청이 일어나면 reader에 기아 상태(starvation)에 빠질 수 있다.
Code
Semaphore mutex = 1; // 다수의 Reader로부터 r_count 접근 보호
Semaphore rw_mutex = 1; // Reader와 Writer의 상호 배제
int read_count = 0; // 실행중인 Reader 개수- Writer process
while (true) {
wait(rw mutex);
...
/* writing is performed */
...
signal(rw mutex);
}- 다른 Reader나 Writer가 실행 중이면 rw_mutex의 값이 0이니 대기한다.
- 실행 중인 프로세스가 없으면 rw_mutex의 값이 1이니 본인이 rw_mutex의 문을 잠그고 실행된다.
- Reader process
while (true) {
wait(mutex);
read_count++;
if (read_count == 1) // Reader가 있으니까 Writer는 기다리도록 하자.
wait(rw_mutex);
signal(mutex);
...
/* reading is performed */
...
wait(mutex);
read_count--;
if (read_count == 0)
signal(rw_mutex); //이제 Writer가 들어갈 수 있다.
signal(mutex);
}-
reader는 read_count를 업데이트할 때마다 잠금을 획득한다.
-
reader가 Critical Section에 접근하려면 read_count를 증가한 다음 접근하고 빠져나올 때는 read_count를 감소한다.
-
rw_mutex는 Critical Section에 들어가는 첫 번째 reader와 Critical Section을 나가는 마지막 reader에서 사용됩니다.
- 첫 번째 reader가 Critical Section에 진입하면 writer는 차단된다. 이 후 새로운 reader만 Critical Section에 진입 가능하다.
- 마지막 reader가 Critical Section을 나오면 read_count가 0이고 writer가 Critical Section에 접근할 수 있는 기회를 가질 수 있으므로 signal(rw_mutex)를 실행하여 writer에게 신호를 보낸다.
- 첫 번째 reader가 Critical Section에 진입하면 writer는 차단된다. 이 후 새로운 reader만 Critical Section에 진입 가능하다.
참고 :
Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.
