프로세스 동기화와 모니터

Process Synchronization

Initial Attempts to Solve Problem

• software적 해결방법(알고리즘)
  • Peterson's Algorithm은 매우 좋은 해결방법이었지만 busy-waiting(spin-lock)이 발생
• hardware적으로 락을 설정하여 이 문제를 해결(testAndSet)
  • 하지만 이는 프로그래머가 매번 사용하기에 부적절함
• 위의 방식들을 추상화 시킨 Semaphores의 등장

Semaphores

• 추상 자료형, 정수형을 가질 수 있음(자원의 개수를 표현)
  • 자원의 개수가 1개인 경우 이를 가져가면(P연산) Lock이 됨
• 2가지의 atomic 연산
  • P(S): Semaphores 변수값(공유 데이터)획득, 자원이 없으면 while, 있으면 S--
  • V(S): 반환, S++
• 구현 방식
  • busy-wait: 효율적이지 못함(=spin lock)
  • Block & Wakeup: (=sleep lock)

Block & Wakeup Implementation

Deadlock & Starvation

• Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• Starvation(Indefinite blocking): 특정 프로세스가 자원을 받지못하는 현상

Classical Problems of Syncronization

1. Bounded-Buffer Problem
2. Readers-Writers Problem
3. Dining-Philosophers Problem

Semaphore를 이용하여 위의 문제들을 해결할 수 있다.
Semaphore는 코딩하기 어렵고, 정확성의 입증이 어려우며, 자발적 협력이 필요하다.
또한 한번의 실수가 모든 시스템에 치명적으로 작용하기 때문에 모니터가 도입되었다.

모니터

Semaphore와 다르게 Monitor는 자체적으로 하나의 프로세스만 접근이 가능하기 때문에 Lock이 필요없다.

모니터란?

모니터는 concurrent programming에서 쓰레드가
1. mutual exclusion을 보장
2. 조건에 따라 대기(wait) 상태로 전환(block)

기능을 가질 수 있게 해주는 프로그래밍 언어차원에서의 기능이다.

모니터 사용 시기

• 한번에 하나의 쓰레드만 실행되어야 할 때
• 여러 쓰레드와 협업(cooperation)이 필요할 때

모니터의 구성 요소

• mutex lock: critical section에서 mutual exclusion을 보장하는 장치

  • mutex lock을 취득해야 critical section에 진입할 수 있음
  • mutex lock을 취득하지 못한 쓰레드는 큐에 들어간 후 대기(wating) 상태로 전환

• condition variable

  • waiting queue를 가짐
  • 조건이 충족되길 기다리는 쓰레드들이 대기상태로 머무는 곳

• condition variable의 주요 동작(operation)

  • wait: 쓰레드가 자기 자신을 대기열에 넣고 대기 상태로 전환
  • signal: 대기열에서 대기중인 쓰레드를 하나 깨움
  • broadcast: 대기열에서 대기중인 쓰레드를 모두 깨움

모니터 사용 예시

acquire(m); // 모니터의 락 취득
while (!p) { // 조건 확인
	wait(m, cv); // 조건 충족 안되면 대기
}
// 임계 영역 코드
signal(cv2); // Or: broadcast(cv2);
             // cv2 는 cv와 같을 수도 있음
release(m); // 모니터의 락 반환

모니터의 큐(queue)

• entry queue: critical section에 진입을 기다리는 큐
• wating queue: 조건이 충족되길 기다리는 큐

bounded producer/ consumer problem

• buffer가 가득차서 producer가 이를 계속 확인해야하는 문제
• buffer가 비어서 consumer가 이를 계속 확인해야하는 문제
  
  이를 모니터를 이용하여 해결할 수 있음

자바에서의 모니터

• 자바에서는 모든 객체는 내부적으로 모니터를 가진다.

• synchronized 키워드를 이용하여 모니터의 mutual exclusion 기능을 이용할 수 있다.

• 자바의 모니터는 condition variable를 하나만 가짐

  • wait
  • notify(signal)
  • notifyAll(broadcast)

크로스오버 표