[운영체제] 프로세스 동기화 -3

프로세스 동기화 -3

# Bounded-Buffer Problem (Producer-Consumer Problem)
# Readers and Writers Problem
# Dining-Philosophers Problem
# Monitor

---

✍️ 본 포스팅은 이화여자대학교 반효경 교수님의 "운영체제" 강의를 들으며 정리한 내용입니다.

 

---

이번 포스팅에서는 프로세스 동기화와 관련된 고전적인 3가지 문제에 대해서 알아보겠습니다~

 

＊Bounded-Buffer Problem (생산자 소비자 문제)

• Shared data : Buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
• Synchronization variables
  
  • mutual exclusion -> Need binary semaphore (shared data의 락을 걸고 푸는데 사용)
  • resource count -> Need integer semaphore (남은 full/empty buffer의 수 표시에 사용)
• 설명
  • 두 종류의 프로세스가 존재한다. Producer(생산자)와 Consumer(소비자)
  • 위 그림의 처음에는 모두 빈 구멍(Buffer) 상태
  • Buffer의 채워진 부분은 Producer가 빈 버퍼를 보고 데이터를 만들어 채워넣은 것이다.
  • 두 Producer가 동시에 같은 버퍼를 채우면 안되기에
    -> 공유 메모리에 락을 걸어 다른 프로세스의 접근을 막아야 한다. (첫번째 문제)
  • 버퍼 채우기가 끝나면 락을 풀어 공유 메모리에 다른 프로세스가 접근 가능해진다.
  • 반대로 두 Consumer가 동시에 같은 full Buffer 데이터를 가져가면 안되기에
    -> 공유 메모리에 락을 걸어 다른 프로세스의 접근을 막아야 한다. (두번째 문제)

---

- Bounded-Buffer Problem 예제 코드

• Producer
  1. 넣고자하는 item X 생산
  2. P 연산을 통해 빈 버퍼가 있는지 확인 -> 빈 버퍼가 있으면 빈 버퍼를 하나 획득
  3. P 연산을 통해 버퍼 전체에 락을 건다
  4. 버퍼에 데이터를 집어넣는다
  5. V 연산을 통해 버퍼 전체에 걸었던 락을 푼다
  6. full 버퍼를 증가 시킨다. (full 버퍼는 Consumer 입장에서의 자원)
• Consumer
  1. P 연산을 통해 full buffer가 있으면 full buffer를 하나 획득
  2. P 연산을 통해 버퍼 전체에 락을 건다
  3. 공유 버퍼에서 데이터를 하나 꺼내간다
  4. V 연산을 통해 버퍼 조작이 끝나면 걸었던 락을 푼다
  5. V 연산을 통해 빈 버퍼를 증가시킨다. (빈 버퍼는 Producer 입장에서의 자원)

---

＊Readers-Writers Problem

• Readers(읽기 프로세스) / Writers(쓰는 프로세스) 두 프로세스가 존재한다.
• 공유 데이터를 DB라고 명명
• 한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨
• read는 동시에 여럿이 해도 됨
• Solution
  • Writer가 DB에 접근 허가 못 얻은 상태에서는 모든 대기중인 Reader들을 DB에 접근하게 해줌
  • Writer는 대기중인 Reader가 하나도 없을 때 DB 접근이 가능
  • Writer가 DB에 접근 중이면 Reader들과 다른 Writer는 접근이 금지됨
  • Writer가 DB에서 빠져나가면 Reader들과 다른 Writer 접근 허용
• Problem
  • Reader가 끊임없이 들어오면 Writer는 영원히 쓰지 못하게 되는 Starvation 현상이 발생 가능

- Readers-Writers Problem 코드 예시

• DB : 공유 데이터
• db : DB에 접근 시 lock을 걸 때 사용하는 변수
• readcount : Reader가 몇명 읽고 있는지 나타내는 변수. 모든 Reader가 변경 가능한 공유 변수
• mutex : readcount를 증가시킬 때, 여러 Reader가 동시에 readcount 변수에 접근하면 안되므로
  readcount에 대한 lock을 걸 때 쓰는 변수
• Writer
  1. 다른 프로세스가 witer 중이면 P연산을 통과 못하고 기다린다
  2. 접근이 가능해지면 P 연산으로 lock을 건다
  3. DB에 쓰는 작업을 한다
  4. 작업이 끝났으면 V 연산으로 lock을 푼다
• Reader
  1. P 연산을 통해 공유 변수 readcount에 대해 lock을 건다
  2. readcount가 1이면 (처음 읽으러 들어왔으면) DB 전체에 lock을 건다
  3. 1이 아니라면 다른 프로세스가 이미 락을 건 상태이므로 락을 다시 걸지 않음
  4. readcount 작업이 끝나면 V 연산으로 다시 lock을 푼다
  5. DB를 읽는다
  6. P 연산으로 다시 readcount에 lock을 걸고
  7. 읽기가 끝났으므로 readcount를 1 뺀다
  8. readcount가 0이라면 (내가 마지막으로 나가는거면) V 연산으로 DB 전체 lock을 푼다
  9. V 연산으로 readcount에 lock을 푼다

---

＊Dining-Philosophers Problem

• 철학자의 저녁식사 문제
• 철학자들은 생각하는 일과 배고파지면 밥먹는 일 두가지를 한다
• 배가 고파지면 자신의 왼쪽, 오른쪽 젓가락 2개를 들고 밥을 먹는다
• 배가 불러졌으면 다시 젓가락을 놓고 생각을 한다
• i : 철학자의 번호
• 각 value (젓가락 수)는 1로 초기화되있다 (같은 위치에 젓가락은 1개)
• P(chopstick[i] : 왼쪽 젓가락을 사용가능할 때까지 기다렸다가 가능해지면 든다
• P(chopstick[(i+1) % 5] : 오른쪽 젓가락을 사용가능할 때까지 기다렸다가 가능해지면 든다
• 밥을 먹는다
• V(chopstick[i] : 왼쪽 젓가락을 다시 놓는다
• V(chopstick[(i+1) % 5] : 오른쪽 젓가락을 다시 놓는다
• 생각한다
• 무한 반복

---

- 위 Solution의 문제점

• Deadlock 가능성이 존재
• 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우 : 밥을 아무도 영원히 못먹게됨

- 해결 방안

1. 4명의 철학자만이 테이블에 동시에 앉도록 한다
2. 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다
3. 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다

- 두번째 방법의 코드 예시

• semaphore self[i] : 값이 1이면 i번 철학자가 젓가락 두개를 다 잡을 수 있음을 의미
• enum {thinking, hungry, eating} state[i] :  i번 철학자의 상태를 나타냄
• semaphore mutex : state는 다른 철학자의 상태에 영향을 끼칠 수 있는 공유 변수이기에 lock을 걸 변수가 필요함
• pickup(i) : 철학자 i가 젓가락을 잡는 코드
  1. P 연산으로 상태 바꾸기 전 lock 걸기
  2. 자신의 상태를 hungry로 바꿈
  3. test(i) 호출 : 젓가락 두 개 다 잡을 수 있는 상황인지 확인
     • 왼쪽 철학자, 오른쪽 철학자 모두 밥먹고 있지 않고, 자신이 배고플 때만
     • 자신의 상태를 밥먹는 상태(eating)로 바꿔준다
     • V 연산으로 i번 철학자가 젓가락 잡는 권한을 얻는다(self(i)를 1로 바꿈)
  4. V 연산으로 lock을 푼다
  5. P 연산으로 1이었던 self(i)를 다시 0으로 바꿔 권한을 제거한다.
  6. 만약 test(i)에서 권한을 못 얻었다면 마지막 P연산에서 권한을 얻은 상태일 때까지 기다린다.
• eat() : 젓가락을 들었으니 이제 밥을 먹는다 
• putdown(i) : 젓가락을 내려놓는 코드
  1. P 연산으로 상태 바꾸기 전 lock 걸기
  2. 자신의 상태를 thinking로 바꿈
  3. 왼쪽 철학자와 오른쪽 철학자에 대한 test 함수 호출
     -> 배고픈데, 아까 젓가락 못들었으면 들 수 있게 권한 부여 시도
  4. V 연산으로 걸었던 lock을 푼다
• think() : 생각한다
• 무한 반복

---

＊Monitor

- Semaphore의 문제점

• 코딩하기 힘들다
• 정확성의 입증이 어렵다
• 자발적 협력이 필요하다
• 한번의 실수가 모든 시스템에 치명적인 영향을 미친다
• 예시

- Monitor란

• 동시 수행중인 프로세스 사이에서 추상 data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
• 한 프로세스가 공유 데이터 접근을 위해 Monitor 내부 코드를 실행중이면
  -> 다른 프로세스는 Monitor 코드를 실행하지 못하고 Monitor 밖 Queue에 줄서서 기다려야한다
• 다른 프로세스가 Monitor 코드에 접근하려면, 이미 실행중인 프로세스가 작업을 모두 마치고 나가던지
  Monitor 내부 작업을 하다가, 조건 충족이 안되어 잠들거나 해야한다
• Monitor 내부에 공유 데이터들을 선언
• Monitor 내부에 공유 데이터에 접근하는 함수를 구현해 놓음
• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음(lock을 걸 필요 X)
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해
  -> condition variable 사용 : condition x, y;
• Condition variable은 wait과 signal 연산에 의해서만 접근 가능
  -> x.wait(); : 프로세스 재우기
  • x.wait()을 호출한 프로세스는 다른 프로세스가 x.signal()을 호출하기 전까지 중지된다
• x.signal() : 프로세스 깨우기 : 는 정확히 하나의 중지된 프로세스를 재개시킨다.
  중지된 프로세스가 없으면 아무 일도 일어나지 않는다.

- Produce / Consumer 문제를 Monitor 사용해 해결한 코드 예제

• buffer[N] : 버퍼를 N개만큼 선언
• condition
  • full : full 버퍼를 기다리는 프로세스들을 줄세우는 역할
  • empty : empty 버퍼를 기다리는 프로세스들을 줄세우는 역할
• produce(int x) : 생산자가 사용하는 함수
  • 빈 버퍼가 없다면 빈 버퍼를 기다리는 줄에 세워지고 잠든다
  • 빈 버퍼가 있다면 빈 버퍼에 데이터를 집어 넣어 준다
  • full 버퍼가 있을 때까지 잠들어있는 프로세스(소비자)가 있으면 깨워준다
• consume(int x) : 소비자가 사용하는 함수
  • full 버퍼가 없다면 full 버퍼를 기다리는 줄에 세워지고 잠든다
  • full 버퍼가 있다면 full 버퍼에서 데이터를 꺼내간다
  • 빈 버퍼가 있을 때까지 잠들어있는 프로세스(생산자)가 있으면 깨워준다

- 식사하는 철학자 문제를 Monitor 사용해 해결한 코드 예제

• Each Philosopher: 각각의 철학자가 수행하는 일 -> 젓가락을 들고, 밥먹고, 젓가락 놓고, 생각한다.
• pickup(int i)
  • 아까와 달리 Monitor 내부에서 state[i] 상태를 바꿔주기에 lock 걸 필요가 없음
  • test(i)에서 조건 충족안되면 젓가락 들기 권한을 줄세우고 재운다
• test(int i)
  • 왼쪽 젓가락 오른쪽 젓가락 들 수 있는지 확인 후 가능하면 eating 상태로 바꿔줌
  • self[i]를 통해 잠들고 있던 해당 철학자를 깨워 젓가락 들 수 있게 권한 부여한다
• putdown(int i)
  • thinking 상태로 바꾼다
  • 자신 때문에 잠들어 있을 왼쪽 철학자와 오른쪽 철학자에 젓가락 들기 권한 부여를 시도한다