6. Process Synchronization

- 데이터의 접근

---

- Race condition(경쟁 상태)

하나는 1 증가 연산, 하나는 1 감소 연산

정상동작 : 하나를 더하고 하나를 빼면 원래의 값이 나옴

오동작 : 증가 연산과 감소 연산 동시 진행 후 증가 연산 값이 저장하고 감소 연산 값을 저장하면 감소 연산 값만 저장됨

---

- Process Synchronization 문제

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있음
• 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)를 정해주는 메커니즘이 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• Race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 함

---

- The Critical-Section Problem(임계구역)

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• Problem
  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함

---

- Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

• 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다 → synchronization variable

---

-프로그램적 해결법의 충족 조건

• Mutual Exclusion(상호 배제)
  : 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
• Progress(진행)
  : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
• Bounded Waiting(유한 대기)
  : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

• 가정
  1. 모든 프로세스의 수행 속도는 0보다 크다.
  2. 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

<Algorithm 1>

• Synchronization variable

• Process P0

1번 프로세스에서 0으로 바뀌면 그 때 critical section으로 들어가고, 후에 turn을 1로 바꿔서 프로세스1에게 상태를 넘김.

• Mutual Exclusion(상호 배제) 성립, But Progress(진행)를 만족하지 못함.
  ex) 아무도 critical section에 들어가지 않았을 경우, 다음 프로세스에게 넘기지 못하는 문제 발생

<Algorithm 2>

• Synchronization variable

• Process Pi

• Mutual Exclusion(상호 배제) 성립, But Progress(진행)를 만족하지 못함.
  ex) 두 개의 프로세스가 2행까지 수행 후 끊임없이 양보하는 상황이 발생할 수 있음

<Algorithm 3> (= 피터슨 알고리즘[Peterson's Algorithm])

• Combined synchronization variables of algorithms 1 and 2.
• Process Pi

turn은 상대방에게 준 후 상대방의 상태와 나의 상태를 보고 critical section 사용

• 프로그램 충족 조건 3가지 모두 만족
• Busy Waiting! (계속 CPU와 memory를 쓰면서 wait)

---

- Synchronization hardware

• 하드웨어적으로 Test&Modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단하게 해결 가능하다.

만일 a가 0일 경우 0이 읽힌 후(Read) 1로 바뀜(True), 반대로 a가 1일 경우 1이 읽히고(Read) 1로 세팅(True).

• Mutual Exclusion with Test&Set

 

- Semaphore

• 위의 방식들을 추상화
• 추상자료형(object와 operation으로 이루어짐)
• Semaphore S
  • integer vcariable
  • 아래 두가지 atomic 연산에 의해서만 접근 가능
    • P연산 - 획득하는 과정
    • V연산 - 반납하는 과정

• atomic하게 움직이지만 busy-wait문제는 발생

- Critical Section of n Processes

• busy-wait는 효율적이지 못함(=spin lock)
• Block&Wakeup 방식의 구현(=sleep lock)

- Block/Wakeup Implementation

• Semaphore를 다음과 같이 정의

• block과 wakeup을 다음과 같이 가정 (3장 프로세스의 상태 참고)
  • block
    - 커널은 block을 호출한 프로세스를 suspend시킴
    - 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup(P)
    - block된 프로세스 P를 wakeup시킴
    - 이 프로세스의 PCB를 ready queue로 옮김

• Semaphore 연산이 다음과 같이 정의됨.

 

- Which is better?

• Busy-wait VS Block/Wakeup: 일반적으로 Block/Wakeup방법이 더 효율적
• Block/wakeup overhead vs Critical section 길이
  • Critical section길이가 긴 경우 Block/Wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 Busy-wait오버헤드보다 더 커질 수 있음

- Two Types of Semaphores

• Counting semaphore
  • 도메인이 0이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion(lock/unlock)에 사용

- Deadlock and Starvation

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• ex) S와 Q가 1로 초기화된 semaphore

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

---

- Classical Problems of Synchronization

• Bounded-Buffer Problem(Producer-Consumer Problem)

∴Shared data 

- buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)

∴Synchronization variables

- mutual exclusion → Need binary semaphore(shared data의 mutual exclusion을 위해)

- resource count → Need integer semaphore

• 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 자체를 올바르게 접근하게 하는 역할

• Dining-Philosophers Problem

- 솔루션의 문제점

• Deadlock 가능성이 있다(모든 철학자가 배가 고파져 왼쪽 젓가락을 집어버린 경우)

- 해결 방안

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

---

-Monitor

- Semaphore의 문제점

• 코딩하기 힘들다
• 정확성(correctness)의 입중이 어렵다
• 자발적 협력(moluntary cooperation)이 필요하다
• 한번의 실수가 모든 시스템에 치명적 영향

-Monitor란?

• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기위해 condition variable 사용
• condition variable은 wait와 signal연산에 의해서만 접근 가능