Process Synchronization2

Semaphores

• 앞의 방식들을 추상화시킴
• Semaphore S
  • integer variable
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

• S가 5일때 P연산을 하면 자원을 하나 가져가고 V를 하면 반환. 즉, P = lock, S = unlock

Critical section of n Processes

• Synchronization variable
  • semaphore mutex; // initially 1
• Process Pi

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

Block & Wakeup Implementation

• Semaphore를 다음과 같이 정의

• Block & Wakeup 을 다음과 같이 가정
  • Block
    • 커널은 block을 호출한 프로세스를 suspend 시킴
    • 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • Wakeup(P)
    • blcok된 프로세스 P를 wakeup시킴
    • 이 프로세스의 PCB를 ready queue로 옮김

• Block & Wakeup 방식의 P() & V() 연산

Which is Better?

• Busy-wait v.s Block & Wakeup
• Block & Wakeup overhead v.s Critical section 길이
  • Critical section의 길이가 긴 경우 Block & Wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 Block & Wakeup 오버헤드가 busy-wait 오버헤드보다 커질 수 있음
  • 일반적으로는 Block & Wakeup 방식이 더 좋음

Two types of semaphores

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

Deadlock and Starvation

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

 각 프로세스가 하나씩 차지하고 있을때 서로 상대방 것을 요구할 때 무한히 상대방것을 요구만 할 수 있으며, 이상황을 데드락이라 한다.

 

 

 

 

 

 

 

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