[OS] 운영체제 7. Process Synchronization 2 : 세마포어(semaphore)

Semaphores 

임계영역 문제를 해결하기 위한 알고리즘(참고)들을 추상화 시킴

 

[Semaphore S]

integer variable

아래 두가지 atomic 연산에 의해서만 접근 가능

 

P(S) 자원 있으면 가져감

while(S<=0) do no-op;  //wait : busy-wait
S--;

V(S) 반납

S++;

 

[세마포를 사용한 임계영역문제 해결 : busy-wait (=spin lock)]

Synchronization variable
semaphore mutex; // mutual exclusion

do {
   P(mutex);        // if positive, decrement & enter, otherwise, wait
   critical section
   V(mutex);        // Increment semaphore
   remainder section
} while(1);

 

[세마포를 사용한 임계영역문제 해결 : block-wakeup]

Semaphore 정의]
여기서 value는 상호배제를 위한 flag용도가 아닌 가용한 자원의 수

typedef struct
{
   int value;             // semaphore
   struct process *L;   // process wait queue
}

block 과 wakeup을 다음과 같이 가정]

block :

커널은 block을 호출한 프로세스를 suspend 시킨다

이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다

 

wakeup(P) :

block된 프로세스 P를 wakeup 시킨다

이 프로세스의 PCB를 ready queue로 옮긴다

 

 

P(S)

S.value--;
if(S.value < 0){
   add this process to S.L;
   block();
}

V(S)
부등호가 <= 인 이유는,
value가 0보다 작을 경우 자원을 기다리는 프로세스가 있음을 의미하므로 value가 0보가 작을 때 wake up 함

S.value++;
if(S.value <= 0){
   remove a process P from S.L;
   wakeup(P);
}

일반적으로 Busy-wait보단 Block/wakeup를 사용

Critical section 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수도 있다

 

[ 두가지 유형의 Semaphores ]

1) Counting semaphore 

도메인이 0 이상인 임의의 정수값

주로 resource counting(가용한 자원 수 카운트용)에 사용

 

2) Binary semaphore (=mutex)

0 또는 1 값만 가질 수 있는 semaphore

주로 mutual exclusion (lock/unlock)에 사용

 

※ Deadlock (교착상태)

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

 

※ Starvation (기아)

indefinite blocking.

세마포어 큐에서 빠져나갈 수 없는 현상

(deadlock 도 일종의 starvation)

 

[Deadlock, Starvation의 예 : Dining-Philosophers Problem]

 

한 사람이 양쪽의 젓가락 한짝씩 들어서 한 쌍을 만들어야 식사가 가능하다고 할 때,

Dead lock 은 모든 사람들이 자신의 자리에서 오른쪽(왼쪽) 젓가락을 사용하여 모두가 식사를 시작하지 못하는 상황

Starvation 은 사람 A의 좌우 사람이 젓가락을 가지고 식사를 하여 A 가 식사를 시작하지 못하는 상황

 

 

※ 이화여대 반효경 교수님의 운영체제 강의 정리