[운영체제] 5. Process Synchronization (3)

키워드

semaphores, busy-wait, block/wakeup, deadlock, starvation

 

Semaphores

P(S):
  while (S <= 0) do no-op;
  S--;
  
V(S):
  S++;

• 프로그래머 관점에서 concurrency control을 잘하기 위한 방법을 제공하기 위한 수단으로
  P 연산과 V 연산으로 구성된 일종의 추상 자료형
• integer variable (정수값을 가질 수 있음) - 자원의 개수
• operator. 즉, 연산은 두가지가 정의되고 있음
  • P(S): semaphores 값을 획득하는 과정(또는 공유 데이터를 획득하는 과정)
  • V(S): 사용 후 반납하는 과정
• 이전에 lock을 걸고 푸는 것을 semaphore를 이용해 간단히 프로그래머가 제공받을 수 있음
  • P 연산 시: lock을 거는 과정
  • V 연산 시: lock을 푸는 과정
• 어떤 공유 자원을 획득하고 반납하는 것을 semaphore가 처리해줌
• atomic 연산에 의해서만 접근 가능
  * atomic 연산: synchronization 문제가 발생하지 않도록 보장하는 연산
• semaphore는 구체적인 구현이 아닌 추상적으로 연산 자체를 정의하는 것임
• 마찬가지로 자원이 없을 때 P 연산 시 busy waiting 문제 발생

• busy-wait (=spin lock): lock을 획득하지 못하면 lock을 얻을 때까지 계속 while문을 회전
• Block & Wakeup (=sleep lock): lock을 못얻으면 block 상태(잠듦)

 

Block/Wakeup Implementation

• semaphore를 획득할 수 없으면 block 시킴
• 누군가 semaphore를 쓰고나서 반납하면 block된 프로세스중 하나를 wakeup(P)
• semaphore를 기다리며 잠들어있는 프로세스를 연결
  
  
• P(S) 연산
  • 자원에 여분이 있다면 획득
  • 자원에 여분이 없다면 block
• V(S) 연산
  • 자원의 반납뿐 아니라 기다리면서 잠들어있는 프로세스가 있다면 wakeup 해줌
• busy waiting에서의 P, V 연산과 다른 모습을 볼 수 있다.
• 자원의 개수를 세는 의미하고는 다름
  • 음수면 누군가 자원을 기다린다는 의미
  • 양수면 자원에 여분이 있기 때문에 기다리지 않고 사용중

 

Busy-wait vs Block/Wakeup

• 보통은 Block/Wakeup을 쓰는게 더 효율적
• 굳이 나누자면, Block/Wakeup에도 overhead가 존재
  • 프로세스의 상태를 ready 상태에서 block 상태로 바꿔야 함
  • 자원이 반납되면(공유 데이터에 여분이 생기면) block 상태를 ready 상태로 바꿔줘야 함
• 때문에 critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 
  busy-wait 오버헤드보다 더 커질 수 있음
• 하지만 critical section의 길이가 긴 경우 Block/Wakeup이 필수

 

Two Types of Semaphores

• Binary Semaphore(=mutex)
  • 자원의 개수가 하나인 경우(semaphore 변수 값이 하나인 경우)
  • 즉, 보통 lock을 걸 때 자원의 개수를 하나로 세팅해 사용
  • ex) 0 또는 1
  • 주로 mutual exclusion (lock/uplock)에 사용
• Counting Semaphore
  
  • Binary Semaphore와 달리 semaphore 변수 값이 0이나 1이 아닌 5나 10과 같은 값이 주어지는 경우
  • 자원의 개수가 여러 개 있어서 여분이 있으면 그냥 가져다 쓸 수 있음
  • 도메인이 0 이상인 임의의 정수 값
  • 주로 resource counting에 사용

 

Deadlock and Starvation

• semaphore를 쓰며 주의해야할 점

Deadlock

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

• P0에서 P(S) 획득 후 CPU를 P1에 뺏겨 P(Q) 획득 후, P(S)를 하려고 보니
  이미 P(S)를 P0에서 가지고 있기 때문에 영원히 기다리게 됨
• 자원 획득 순서를 똑같이 맞춰 문제 해결 가능
• 프로그래머가 유의해서 작성해야 하는 부분

Starvation

• indefinite blocking
• 영원히 자원을 얻지 못하고 무한히 기다려야 하는 상황
• 프로세스가 suspend된 이유에 해당하는 semaphore 큐에서 빠져나갈 수 없는 현상
• deadlock도 starvation에 해당되긴 하지만
  특정 프로세스들만 자기들끼리 자원을 공유하며 다른 프로세스에게 영원히 자기 차례가 오지 못하게 하는걸 
  특별히 starvation이라고 부름 -> 식사하는 철학자 문제에서 더 자세히

 

Dining-Philosophers Problem

(=식사하는 철학자 문제)

• starvation
  • 한쪽에서 식사를 위해 양쪽의 젓가락을 잡은 경우 그 옆에 사람은 식사를 마칠 때까지 기다리지만
  • 만약 식사가 끝난 직후 옆옆 사람이 양쪽 젓가락을 잡고 식사를 시작하고, 그게 반복되면 
  • 그 중간의 사람은 영원히 식사를 할 수 없게 됨
• deadlock
  • 만약 모든 사람이 동시에 왼쪽 젓가락을 잡아 버리면 다섯 명이 모두 영원히 식사를 하지 못하게 됨