[ KOCW 운영체제와 정보기술의 원리 | 반효경 ] Process Synchronization ( Semaphores)

 

✨ Semaphores

Two Types of Semaphores

 

Counting Semaphore

• 도메인이 0 이상인 임의의 정수 값
• 주로 resource counting에 사용

Binary semaphore (=mutex)

• 0 또는 1 값만 가질 수 있는 semaphore
• 주로 mutual exclusion (lobk/unlock)에 사용

공유 자원을 획득하고 반납하는 것을 추상화시켜서 진행해준다

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

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

V(S): S ++

S가 5개면 자원이 5개라는 뜻.
P 연산을 하면 자원이 하나씩 사라진다는 뜻. 없을 때는 자원을 돌면서 기다린다
V연산을 하면 자원 4개에서 5개가 된다.

그러나 여기서도 busy-wait 문제는 발생한다

만약 누군가가 critical section에 들어있으면 계속 while문을 돌아야 함

 

 

구현 방식

 

Block / Wakeup

• block : 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
• wakeup(P) : block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김

P(S) : 자원에 여분이 있다면 획득하고, 여분이 없다면 block() 상태로 들어감

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

   block()
   }

V(S) : 자원을 반납하는데, 혹시 자원을 기다리며 자고있는 block() 샅애의 프로세스가 있다면 바로 그 프로세스를 실행함

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

   }

여기서 S.value는 자원의 개수를 세는 것과는 좀 다르다.
음수가 되면 누군가가 자원을 기다리고 있다는 것.
양수라면 자원을 기다리는 누군가가 없다는 것

사실 Block/wakeup도 overhead가 있다.

• Critical section의 길이가 긴 경우 Block/Wakeup이 적당
• Critical section의 길이가 매우 짧으면 Block/Wakeup 오버헤드가 busy-wait오버헤드보다 더 커질 수 있음
• 일반적으로는 Block/wakeup 방식이 더 좋다

 

Deadlock and Starvation

 

Deadlock

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

이런 상태를 가정해보자
Process1 => P(S); P(Q) ... V(S); V(Q);
Process2 => P(Q); P(S) ... V(Q); V(S);

두 Process가 각각 하나씩 자원을 획득한다
(Process1은 S, Process2는 Q)
그런데 둘 다 다음으로 필요한 자원은 진작 서로가 획득해버린 자원이다.

그렇게 계~~속 서로 주..면안될까..?🥺 하다가 Deadlock 상태가 되버린다

 

요약
상대방이 가진 것을 기다리면서 본인의 자원을 내놓지 않아 영원히 기다리는 상태

 

어떻게 해결할까?
자원을 얻는 순서를 일정하게 해주면 된다.

Process1 => P(S); P(Q) ... V(S); V(Q);
Process2 => P(S); P(Q) ... V(S); V(Q);
둘 다 S라는 자원을 먼저 획득하도록 짜여진다면 Deadlock을 해결할 수 있다.

Process1이 S를 획득하고 CPU를 빼앗기지만 Process2도 S를 먼저 획득하기 때문에 다음 Process1은 Q를 획득하면 된다

Q를 획득하려면 S부터 획득해! 😠

 

 

Starvation

indefinite blocking.
프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
사실 Deadlock도 Starvation이라고 부를 수 있다.

그러나 여기서 말하는 Starvation은 몇 process가 자원을 차지해서 어떤 process는 굶는 현상 😢