Process Synchronization

Semaphores

• Lock/Unlock 기능을 간단하게 제공
• 공유자원의 획득 및 반납 과정

Semaphore S

• integer variable S(자원의 개수)
• P(S) : while (S<=0) do no-op; S--; //공유 데이터 획득 과정
• V(S) : S++; // 공유 데이터 반납 과정

Deadlock and Starvation

Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

Starvation : indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

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

Bounded-Buffer Problem(Producer-Consumer Problem), 공유 버퍼

Readers and Writers Problem

Dining-Philosophers Problem

철학자는 생각과 식사 만 함. 공유 데이터는 젓가락.

문제점

모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버리는 경우, 아무도 먹지 못하고 Deadlock의 가능성.

해결 방안

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

젓가락을 두 개 모두 집을 수 있을 때를 확인

• semaphore self = 1인 경우에 모든 젓가락을 집을 수 있는 경우
  ex) semaphore self[3] = 1 // 3번 철학자는 2개의 젓가락 모두 집을 수 있음.
• mutex // lock을 걸기 위한 변수
• pickup() // 젓가락 들기
• putdown() // 젓가락 놓기

Monitor

Semaphore의 문제점

• 코딩하기 힘듦.
• 정확성(correctness)의 입증의 어려움.
• 자발적 협력(voluntary cooperation)이 필요.
• 한 번의 실수가 모든 시스템에 치명적 영향

Monitor

동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct.

• 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음.
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 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된 프로세스가 없으면 아무 일도 일어나지 않음.

Deadlocks

Deadlock은 자원의 부족으로 발생.
Deadlock이 발생하기 위한 4가지 조건. 모두 충족해야 발생.

Resource-Allocation Graph

Deadlock의 처리 방법

위의 두 가지는 deadlock을 미연에 방지하는 방법.
아래 두 가지는 deadlock이 생기도록 놔둠.
위로 갈수록 강한 방법.

Deadlock Avoidance

Resource Allocation Graph algorithm

자원의 instance가 하나밖에 없는 상황