Process Synchronization 3: Producer-Consumer, Readers-Writers, Dining-Philosophers Problem

• 지금 다루는 여러 알고리즘이나 semaphore, spinlock, mutex 등은 모두 다양한 상황에서 발생할 수 있는 process syncronization 문제를 해결하는 방법임
• semaphore를 이용하여 전통적인 3가지 synchronization 문제를 해결할 수 있음

---

Producer-Consumer Problem

• 용량 제한이 있는 버퍼를 데이터를 저장하는 생산자와 데이터를 읽는 소비자가 공유해서 사용할 때 생기는 문제
• buffer 메모리에 일괄적으로 처리되어야 하는 문자나 데이터가 쌓이는데, 이 데이터들을 미리 가져가거나, 데이터를 적재 중인데 다른 데이터가 또 들어오는 문제를 해결해야 함, 동기화가 필요

• 생산자
  • empty buffer가 있는지 확인 후 획득(없으면 P연산에서 대기) ⇒ empty--
  • 버퍼에 접근 못 하도록 mutex ⇒ lock
  • 데이터 저장
  • 비어 있는 buffer를 가리키는 포인터 바꾸기(다음 producer가 사용 가능하도록)
  • mutex 반납 ⇒ unlock
  • 가득 찬 buffer가 있다는 것을 알림(소비자가 사용할 수 있도록) ⇒ full++
• 소비자는 반대로

#define BUFFER_SIZE 10

int buffer[BUFFER_SIZE];
int in = 0; // 생산자가 데이터를 넣는 위치를 가리키는 인덱스
int out = 0; // 소비자가 데이터를 빼는 위치를 가리키는 인덱스
int count = 0; // 현재 버퍼에 있는 데이터 개수
bool full = false;
bool empty = true;

// 생산자 함수
void producer() {
    while (true) {
        // 생산할 데이터를 생성
        int data = produce_data();

        // 버퍼가 가득 찰 때까지 기다림
        while (full) {
            // 버퍼가 가득 찼으므로 생산자는 대기
        }

        // 생산자가 버퍼에 데이터를 넣음
        buffer[in] = data;
        in = (in + 1) % BUFFER_SIZE;
        count++;

        // 버퍼가 비어있지 않음을 표시
        empty = false;

        // 버퍼가 가득 찼음을 표시
        if (count == BUFFER_SIZE) {
            full = true;
        }
    }
}

// 소비자 함수
void consumer() {
    while (true) {
        // 버퍼가 비어있을 때까지 기다림
        while (empty) {
            // 버퍼가 비어있으므로 소비자는 대기
        }

        // 소비자가 버퍼에서 데이터를 빼옴
        int data = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        count--;

        // 버퍼가 가득 차있지 않음을 표시
        full = false;

        // 버퍼가 비어있음을 표시
        if (count == 0) {
            empty = true;
        }

        // 데이터를 소비
        consume_data(data);
    }
}

Q.소비자는 버퍼의 데이터를 앞에서부터 차례대로 읽는 건가? 그래서 위 코드에서 생산자와 소비자의 읽고 쓰는 버퍼의 위치가 (idx + 1) % BUFFER_SIZE로 구현되는 건가?

---

Readers-Writers Problem

• read는 여러 프로세스가 동시에 진행해도 되지만 write는 동시에 진행할 수 없음
• write는 모든 프로세스에 대해 배타적이고 read는 read하려는 프로세스에 대해서는 허용 가능
  

• Reader

  • readcount의 연산이 꼬이지 않도록 P(mutex)후 진입
  • 만약 현재 read 하려는 첫 프로세스라면 db에 대한 lock을 걸어줌 P(db) ⇒ writer에 대한 block, read는 가능
  • count변수 증가 연산이 끝나면 V(mutex)하여 다른 프로세스들이 count 변수 사용하도록 허용
  • db를 읽고 있는 다른 프로세스들이 없으면 db를 unlock 해줌 V(db)

• 이 코드는 다른 reader들이 writer보다 늦게 도착했더라도 따로 막지 않아서 reader가 이미 lock을 걸어 놓은 상태에서 writer는 다른 reader이 빠져나와서 lock을 풀어줄 때까지 기다리도록 구현되어 있음 ⇒ starvation 발생 가능

• 해결방법은? reader가 무한정 들어오는 것을 막는 우선순위 Q나 Timer 등을 둘 수 있음

---

Dining-Philosophers Problem

• 여러 프로세스들이 공유 자원을 사용하려고 할 때 생기는 문제에 대한 비유

• 모든 철학자가 동시에 왼쪽 젓가락을 집고, 이후 오른쪽 젓가락을 집으려 하면 모두 젓가락을 집을 수 없음

• 어떤 철학자도 식사를 시작하지 못 하는 deadlock 발생
  
  

• 각 프로세스의 상태를 나타내는 state 변수

• 각 프로세스가 식사를 할 수 있는지 나타내는 self 변수

• 각 프로세스 간 임계영역 진입을 위한 mutex 변수

• pickup, test, putdown 순서로 진행

• 젓가락을 집는 pickup 호출 후 자신의 상태를 hungry로 변경

• 양 옆 모두 밥을 먹지 않고, 내가 배고픈 상태인 조건을 만족하면 상태를 eating으로 변경

• test 함수에서는 내가 먹을 수 있는 상태가 되면 self 변수 값을 1로 만들어 주는 V 연산을 함.

  • 보통 semaphore는 사용할 수 있는 자원의 개수나 혹은 사용하러 들어가기 전 P연산을 통해 사용 가능한 자원 여부에 lock을 걸어주는 방식으로 동작하는데 철학자의 문제에서는 특이하게 V연산으로 사용하고 있다는 표시를 해줌.

• 만약 if문의 조건을 만족하지 못 해서 V연산을 하지 못 했다면 P(self[i]) 연산에서 내가 진입할 수 있는 조건을 만족하지 못 하므로 계속 대기상태에 있음

  • P연산에는 while문이 있다는 것을 잊지 말자. 추상형!

• 인접한 철학자가 식사를 다 하고 젓가락을 내려 놓는 것을 통해 다른 철학자가 밥을 먹을 수 있다고 self 연산을 바꿔 줄 것 ⇒ putdown에서 양 옆 철학자에 대한 test 코드를 실행함

  • 해당 test 코드에서 그 프로세스는 현재 젓가락을 내려놓은 i + 반대방향 철학자가 젓가락을 내려 놓았는지 확인 후 맞다면 V연산을 통해 self 값을 바꿔주어 P연산을 빠져나와 식사가 가능하도록 해줌

Q.어떤 프로세스의 state의 변경은 다른 프로세스도 할 수 있으므로 공유변수여서 mutex가 필요하다고 강의에서 설명하는데 짧게 언급해서 무슨 말인지 잘 모르겠다.

• 한 프로세스가 젓가락을 내려 놓는 연산을 할 때 양 옆 젓가락에 대한 test 연산을 진행해서 해당 젓가락이 eating 상태로 바뀔 수 있는 조건이면 바뀌도록 하기 때문에 공유 데이터임! 따라서 mutex가 필요!