Chapter 6, 7 Process Synchronization

Outline

---

① Background

② The Critical-Section Problem

③ Peterson's Solution

④ Hardware support for synchronization

⑤ Semaphores

⑥ Monitors

⑦ Liveness

⑧ Synchronization examples

 

① Background

---

● Too much milk problem

공유 자원: 냉장고

● Race Condition

  -> 여러 개의 프로세스가 동일한 자료를 접근/조작

  -> 실행결과가 접근 순서에 따라 바뀜

  -> data consistency를 유지하려면 cooperating processes를 순서에 맞게 실행하도록 보장해야 함

② The Critical-Section Problem

---

● 임계 구역 (Critical section)

공유 데이터가 접근되는 영역

 

1. 진입 구역 (entry section)

2. 퇴출 구역 (exit section)

3. 나머지 구역 (remainder section)

 

요구조건

1. Mutual exclusion

  -> 어떤 프로세스가 임계구역에서 실행 중이면

  -> 다른 프로세스들은 진입하면 안됨

 

2. Progress

  -> 임계구역에 실행 중인 프로세스가 없으면

  -> entry section의 프로세스 중 하나 임계구역으로 진입

 

3. Bounded waiting

  -> 일정 시간 후에 임계구역 진입을 보장해야 함

 

③ Peterson's Solution

---

두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결함.

int turn;            -> 임계구역으로 진입할 순번

boolean flag[2];  -> 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타냄

 

1. Mutual exclusion

  -> While loop에서 flag[i], flag[j]는 항상 true값이고 turn에 의해서 실행이 결정됨.

  -> turn값은 한번에 한 개의 값만 가질 수 있으므로(i or j) 한번에 하나의 프로세스만 critical section으로 진입.

 

2. Progress

  -> turn == i이면 Pi 가 임계구역 진입

  -> turn == j이면 Pj 가 임계구역 진입

  -> 만약 Pi가 먼저 실행되고 임계구역에서 빠져나오면 flag[i] == FALSE로 바꾸므로

  -> Pj는 while loop에서 벗어나서 임계구역으로 진입할 수 있음.

 

3. Bounded waiting

  -> exit section에서 특정 flag 값을 false로 바꿔주어서 while loop를 벗어날 수 있게 보장

  ->  Pi 프로세스가 끝나면 Pj 프로세스가 다음에 실행되는 것이 보장됨.

 

※ Mutex 만으로는 bounded waiting 보장 안됨

   Waiting array와 같은 추가적인 자료구조 필요

④ Hardware support for synchronization

---

● Peterson's solution 문제점

1. busy waiting

2. 구현 어려움

 

● 다중 처리기

특별한 하드웨어 명령어 제공

1. test_and_set()

2. compare_and_swap()

 

※ 둘 다 bounded waiting 보장 안함

   waiting array 있어야 함

⑤ Semaphores

---

semaphore S: 정수 변수

wait(), signal()로 접근 가능

 

1. counting semaphore

  -> domain 범위 제한 (x)

  -> mutual exclusion 보장 (x)

 

2. binary semaphore

  -> domain 범위 0 또는 1

  -> mutex lock

 

● Spin lock, busy waiting

  -> while 사용할 경우 process running 상태

  -> CPU 계속 사용 중

wait(S) {     while(S <= 0) ;    // no-op     S--; }

● Semaphores without busy waiting

  -> 프로세스를 waiting 상태로 전환

  -> busy waiting 대신 waiting queue 사용

 

1. block()

  -> 특정 프로세스를 waiting 상태로 전환하고 waiting queue에 넣음

  -> 제어권 넘김

 

2. wakeup()

  -> waiting queue에 있는 프로세스 중 하나를 제거하고 ready queue에 넣음

 

● 비교

1. 임계구역 짧음

  -> spin lock이 더 나음

  -> 상태 전환 시간이 waiting 시간보다 더 걸림

 

2. 임계구역 긺

  -> without busy waiting이 더 나음

 

⑥ Monitors

---

데이터와 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어서 보호

 

● Semaphore의 문제점

1. Difficult to code

2. Difficult to prove correctness

3. Requirs voluntary cooperation

4. Single misuse affects entire system

 

● 특징

1. 추상화된 데이터 형 (ADT)

2. 모니터 안에 항상 하나의 프로세스만이 활성화

 

● 조건

  -> 특정 시점에 오직 하나의 프로세스만이 모니터에서 활성화 되어야함. (mutual exclusion property)

  -> 다른 프로세스들은 큐에 넣고 기다리게 함

 

● 구현

1. shared data

  -> monitor 내의 operation들이 공유하는 데이터

 

2. operation

  -> monitor 내에서 접근하는 함수

 

3. initialization code

  -> 초기화 코드

  -> entry queue에서 다른 프로세스들이 기다리게 하기 위해서 추가적인 요소 필요

 

4. condition variable: 활성화되지 않은 프로세스들을 기다리게 하도록 지원하는 변수

  1) x.wait(): 해당 operation을 호출한 프로세스는 일시정지됨(entry queue에 추가)

  2) x.signal(): x.wait()를 호출했던 프로세스들 중 하나를 다시시작함(entry queue에서 제거)

 

⑦ Liveness

---

● Liveness

시스템은 반드시 프로세스들의 실행 생명 주기 동안 진행되는 것을 보장해야 한다

(A system must satisfy to ensure that processes make progress during their execution life cycle)

 

● Deadlock

두 개 이상의 프로세스가 waiting process 중 하나에 의해서만 발생할 수 있는 사건을 무한정 기다리는 상황

 

● Bounded-Buffer Problem

1. Binary semaphore

  -> Mutex semaphore: critical section 진입 가능 여부 확인. (초기값: 1)

 

2. Counting semaphore

  -> Full semaphore: buffer에 들어있는 item의 개수. (초기값: 0)

  -> Empty semaphore: buffer의 빈 공간의 개수. (초기값: n)

 

 

● Dining-Philosophers Problem

shared-data: 밥 (data set)

semaphore: 젓가락[5] (초기화: 1)

while(true) {     wait(chapstick[i]);                   // 왼쪽 젓가락 사용 대기     wait(chapstick[(i + 1) % 5]);      // 오른쪽 젓가락 사용 대기     ...     signal(chapstick[i]);                 // 왼쪽 젓가락 반환     signal(chapstick[(i + 1) % 5]);    // 오른쪽 젓가락 반환 }

해결방안

1. 한 번에 4명만 앉도록

2. 젓가락 2개 집는 걸 atomic 하게

3. asymmetric solution

  -> 짝수: 왼쪽 젓가락 먼저, 오른쪽 젓가락 나중에

  -> 홀수: 오른쪽 젓가락 먼저, 왼쪽 젓가락 나중에

 

⑧ Synchronization examples

---

● POSIX mutex

● POSIX semaphore