CS 정리 | OS | 5. 병행제어 | 프로세스 동기화의 classical 문제와 monitor의 등장 | kocw 반효경 교수님

공유데이터의 사용이 원자적으로 수행되지 않아 발생하는 문제의 해결을 위해 세마포어(하드웨어적인 방법)를 이용한다. 세마포어는 lock을 걸거나(mutex) 자원을 세는 데 활용된다.

Deadlock and Starvation

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• 두 개의 자원을 동시에 갖고 있어야만 수행될 수 있는 프로세스 P0과 P1이 있다고 했을 때,
  • ex. S자원을 읽어서 Q자원에 써야할 때. 또는 그 반대
    
  • 위의 영원히 두 프로세스는 진행이 되지 않음
• Starvation
  • indefinite blocking : 프로세스가 세마포어 큐에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

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

Bounded-Buffer Problem

• producer-Consumer problem 으로도 불린다.

• Bounded-Buffer 크기가 유한한 공유데이터의 버터
  

• shared data

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

• Synchronization variables

  • mutual exlusion -> binary semaphore 필요 (shared data의 mutual exlusion을 위함)
  • resource count -> integer semaphore 필요 (남은 full/empty buffer의 수를 표시 및 count하기 위해)

mutex = lock을 걸기 위한 세마포어 변수

Readers-Writers Problem

• 하나의 프로세스가 DB(=공유 데이터)에 write 중일 때 다른 프로세스가 접근하면 안됨

• read는 동시에 여럿이 해도 됨

• 해결책

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

• reader 또한 db에 락을 걸 수 있다 (P(db))
  • 왜? 읽는 도중에 값이 업데이트 되면 안되기 때문에
• 문제점
  • starvation이 발생할 수 있는 코드임
    • 예를 들어 reader가 너무 많은 경우 writer가 영원히 db에 접근하지 못할 수도 있음
• 해결책
  • 신호등을 생각하자

Dining-Philosophers Problem

• 철학자는 식사를 해야한다. 식사는 양쪽의 젓가락을 모두 획득해야한다. 즉, 젓가락 5쌍은 공유 데이터이다. 또한 철학자 모두는 굶어 죽지 않아야한다.
• 문제점
  • 위 코드는 Deadlock 가능성이 있다.
    • ex. 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
• 해결 방안
  1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다. -> 적어도 데드락은 생기지 않음
  2. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 잡을 수 있게 한다.
  3. 비대칭
     • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡도록 한다.
• 해결 방안 2의 코드 (양쪽 젓가락을 모두 집을 수 있는 지에 초점을 둠)
  

🤔 프로세스 동기화를 조금 더 쉽게 할 순 없을까?
기존의 semaphore는 아래와 같은 문제점이 있다.

1. 코딩하기 힘들다
2. 정확성(correctness)의 입증이 어렵다
3. 자발적 협력(voluntary cooperation)이 필요하다
4. 한 번의 실수가 모든 시스템에 치명적인 영향을 미칠 수 있다
5. 단순히 P와 V연산을 제공해 줄 뿐, 동기화 문제에 대한 책임을 지지 않음

monitor

• 동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 고급 언어 synchronization 구조체
• 공유 데이터에 접근할 때에는 monitor 내부의 프로시저에 접근하게 된다. 이를 통해 모니터는 공유 데이터 동시 접근에 대한 모든 책임을 질 수 있다.

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능하다.
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음
• 사진에 보이는 x, y는 condition을 의미한다. (아래에서 이어서 설명)

monitor의 condition 변수

• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 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된 프로세스가 없으면 아무 일도 일어나지 않는다.

결국 condition 변수는 어떠한 값을 갖는 것이 아니라(반대로 세마포어는 자원이란 값을 가지고 있었음), 자신의 큐에 프로세스를 매달아서 sleep을 시키거나 큐에서 프로세스를 깨우는 역할만 한다.

monitor를 이용한 Dining Philsophers 예시