[OS] 병행 제어

Process Synchronization

OS에서 race condition이 발생하는 상황

1. kernel 수행 중 인터럽트 발생 시
   
   커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행
   -> 양쪽 다 커널 코드이므로 kernel address space 공유
2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
   

• 해결책
  커널모드에서 수행 중일 때는 CPU를 preempt하지 않음
  (커널모드 수행은 모두 수행하고 넘겨준다)
  커널모드에서 사용자 모드로 돌아갈 때 preempt

3. Multiprocessor에서 shared memory 내의 kernel data
   

The Critical-Section Problem

각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

• Algorithm 1
  

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

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

• Algorithm 2
  
  깃발만 들고 critical section을 수행하지 않은 경우 모두 다 깃발만 들고 들어가지 못하는 문제 발생

• Algorithm 3 (Peterson's Algorithm)
  

• Synchronization Hardware
  하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
  

Semaphores

동시에 접근하는 문제해결

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

Deadlock and Starvation

• Deadlock
  둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
  여러개가 얽힘.
• Starvation
  indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
  각각의 의미에서 굶어죽음

Bounded-Buffer Problem (Producer-Consumer Problem)

• Shared data
  buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
• Synchronization variables
  mutual exclusion -> Need binary semaphore
  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를 접근하는 코드의 mutual exclusion 보장을 위해 사용
  db ( Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할 )
  
  100개의 Reader가 도착하고 끝나기 전에 계속 Reader가 접근하게 된다면 Writer 입장에서 Starvation이 발생.

Dining-Philosophers Problem

다섯명의 철학자가 동시에 왼쪽 젓가락을 집으면 밥을 먹을 수 없음.
-> Deadlock 발생

해결방안

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.

• 젓가락을 두 개 모두 잡을 수 있을 때만 젓가락을 잡을 수 있게 한다.
  
  mutex는 state[5] 공유변수를 lock 걸기 위해 사용
  V연산을 통해 self[i]를 1로 만들어줌
  P연산을 통해 0으로 만듦
  Test 먼저 수행하여 젓가락을 집을 때 양쪽을 확인해서 젓가락을 집을 수 있으면 권한을 부여하고 P연산에서 젓가락을 얻어서 밥을 먹으면 된다.

• 비대칭
  짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.

Monitor

• Semaphore의 문제점
  • 코딩하기 힘들다.
  • 정확성의 입증이 어렵다.
  • 자발적 협력이 필요하다.
  • 한번의 실수가 모든 시스템에 치명적 영향
    
• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
  모니터가 동시 접근을 컨트롤 해줌.
• 모니터 내에세는 한번에 하나의 프로세스만 접근 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
• condition variable은 wait와 signal 연산에 의해서만 접근 가능
  • x.wait()
    x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.
  • x.signal()
    x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다.
    Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

Bounded-Buffer Problem

Dining Philosophers Example