Process Synchronization(3)-프로세스 동기화

Classical Problems of Synchronization

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

 

Bounded-Buffer Problem (Producer-Consumer Problem)

• Buffer가 유한한 환경에서 생산자-소비자 문제
• 생산자 프로세스와 소비자 프로세스는 여러 개가 존재

• Shared data
  • buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
• Synchronization variables
  • mutual exclusion
    •  Need binary semaphore (shared data의 mutual exclusion을 위해)
  • resource count
    • Need integer semaphore (남은 full/empty buffer의 수 표시)
• 문제
  • 생산자가 동시에 buffer에 데이터를 넣는 경우/ 소비자가 동시에 buffer에서 데이터를 꺼내는 경우 발생
    • 해결 방법 : Semaphore를 이용한 mutual exclusion, lock을 통해 문제 해결
  • 모든 Buffer가 꽉 찬 상태에서 또 다른 생산자가 도착하여 데이터를 집어넣을 빈 buffer가 없는 경우 발생→ 소비자가 와서 빈 buffer가 생길 때까지 기다려야 함.
    • 유한한 크기의 buffer이기 때문에 발생하는 문제
  • 모든 Buffer가 빈 상태에서 또 다른 소비자가 데이터를 필요로 하는 경우 발생→ 생산자가 와서 buffer를 채울 때까지 기다려야 함.
    • 해결 방법 : Semaphore를 이용한 resource count, full/empty buffer의 수를 표시하여 해결
    • 바로 위 문제와 반대의 상황
• Semaphore를 이용한 Bounded-Buffer Problem 의사 코드

*생산자 : empty 상태의 buffer를 P연산으로 얻어오고, full 상태의 buffer를 V연산으로 반남

**소비자 : full 상태의 buffer를 P연산으로 얻어옴, empty 상태의 buffer를 V연산으로 반납

 

Readers-Writers Problem

• 한 process가 DB에 write 중일 때 다른 process가 접근하면 안 됨
• read는 동시에 여럿이 해도 됨
• solution
  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해 준다.
  • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
• Shared data
  • DB
  • readcount: 현재 DB에 접근 중인 Reader의 수
• Synchronization variables
  • mutex
    • 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용
  • db
    • Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
• 문제
  • Reader가 읽고 있을 때 새로운 Reader가 오면 같이 읽을 수 있게 해 주고, Writer가 도착하면 기다리도록 해야 함
    • 해결방법 : Semaphore의 mutex와 db를 이용하여 readcount와 DB 자체에 대한 lock 제어
• Semaphore를 이용한 Readers-Writers Problem 의사 코드

*Writer: DB에 접근 중일 때 DB 전체 lock

**Reader: DB에 접근 중일 때 최초의 Reader(readcount==1)가 lock설정, 마지막 Reader가 lock 해제, readcount도 공통 자원이기 때문에 readcount에 대한 lock도 필요함(mutex)

***Starvation은 Reader가 다 빠져나가기 전에 새로운 Reader가 자꾸 들어오면 Writer가 지나치게 기다리는 상황이 발생함. → 일정 수준의 Reader가 들어오면 더 이상의 Reader가 들어오는 것을 막는 방식으로 해결 가능

 

Dining-Philosophers Problem

• 밥을 먹으려면 왼쪽, 오른쪽에 있는 젓가락을 둘 다 가져야 함.
• 젓가락은 동시에 두 명이 잡을 수 없고, 한 명만 잡고 있을 수 있음

• 위 Solution의 문제점
  • DeadLock의 가능성 존재
  • 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
• 해결방법
  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
  • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 만듦 → 비대칭
• 해결방법 예제 코드(방법 2)

 

Monitor의 등장

• Semaphore의 문제점
  • 코딩하기가 힘들다
  • 정확성(correctness)의 입증이 어렵다.
  • 자발적 협력(voluntary cooperation)이 필요하다.
  • 한 번의 실수가 모든 시스템에 치명적인 영향을 끼친다.
  
• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

 

Monitor의 특징

• 모니터 내에서는 한번의 하나의 프로세스만이 활동 가능(lock 필요 없음)
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
  • condition x, y;
• Condition variable은 wait와 signal 연산에 의해서만 접근 가능
  • x.wait();
    • x.wait()을 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
  • x.signal();
    • x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다. Suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.

 

Monitor의 원리

 

Monitor를 이용한 Bounded-Buffer Problem 해결

• full, empty는 값을 가지는 게 아니라 wait, signal을 통해서 깨우고 재울 뿐 해당 자원이 없다면 아무 일도 일어나지 않는다는 것을 기억!

 

Monitor를 이용한 Dining Philosophers Example

• thinking, hungry, eating 상태가 Bounded-Buffer 문제에서의 full, empty와 비슷한 역할을 함

 

 

 

 

출처

KOCW :  이화여대 반효경 교수님 <운영체제, 2014>