[운영체제] KOCW 6.1 - Ch6: Process Synchronization

Deadlock and Starvation

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

--> Problem: Starvation

• Solution: P(S) --> Q(S)로 순서를 고정시킨다.

 

---

Classical Problems of Synchronization

1. Bounded-Buffer Problem (Producer-Consumer Problem)
2. Readers-Writers Problem
3. Dining-Philosophers Problem

1) Bounded-Buffer Problem

1) Bounded-Buffer: Problem

▶ 생산자 문제

1. 빈 buffer(자원)가 없을 때
2. 두 생산자가 동일한 buffe(shared data)에 data를 집어넣는 문제

▶ 소비자 문제

1. 찬 buffer(자원)가 없을 때
2. 두 소비자가 동일한 buffer(shared data)의 data를 꺼내가는 문제

1) Bounded-Buffer: Solution

▶ Solution:

1. P(empty), V(full) --> 빈/찬 곳이 없는 문제 해결
2. P(mutex), V(mutex) --> 공유데이터에 동시에 접근하는 문제 해결

 

2) Readers-Writers Problem

▷ Problem:

• Reader: DB(공유데이터) 동시접근 (O)
• Writer: DB(공유데이터) 동시접근 (X)

▷ Solution:

• Reader: 다 DB에 접근하게 해준다.
• Writer: 대기중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• Writer: 일단 Writer가 DB에 접근하고 있으면, Reader들은 접근이 금지된다.

▶ db: 공유데이터 DB의 mutual exclusion 보장

• P(db), V(db)

▶ readcount: 현재 DB에 접근중인 Reader의 수를 세는 공유변수

• readcount > 0: 다른 reader가 DB에 접근하고 있다.
• readcount = 0: DB에 접근하는 다른 reader는 없다.

▶ mutex: 공유변수 readcount의 mutual exclusion 보장

• P(mutex), V(mutex)

2) Readers-Writers Problem --> Solution

▷Problem: Starvation

- reader lock을 걸었을 때(P(db)), writer는 reader가 다 읽고 나서야 접근할 수 있다.

--> Solution: 예) 신호등(일정 시간 간격을 설정한다.)

---

스윗 교수님 .. <3

---

3) Dining-Philosophers Problem

3) Dining-Philosophers Problem

▷ Problem: deadlock(아무도 자신이 가진 chopstick을 내어놓지 않는다.)

 

▷ Solution:

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
• 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다. (= deadlock and starvation; P(S), P(Q) 순서를 정하는 것)

 

▶ Solution: 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

3) Dining-Philosophers Problem --> Solution

pickup --> test --> putdown