Process Synchronization 2(Semaphores)

Semaphores

추상 자료형이란 object와 operation으로 구성된다.

세마포어도 추상 자료형이다. 정수 값을 가질 수 있고  해당 정수 값이 자원의 개수라고 생각하면 된다. 

operation은 2가지 연산이 정의되어 있다. P연산과 V연산이 정의된다.

해당 연산은 공유자원을 획득하고 반납하는 것을 처리해준다. 

P연산은 세마포어 변수 값을 획득하는 과정이고 V연산은 다 사용하고 나서 반납하는 과정이다. 

lock을 걸고 푸는 방식은 semaphore 변수가 1인 경우를 생각하면 된다. P연산을 lock을 거는 과정 V연산은 lock을 푸는 과정이다. 

Semaphore S

• P(S): while(S<=0)do no-op;(기다리는 과정) S--;
• V(S): S++;

P연산과 V연산은 atomic 하게 연산이 수행된다는 것을 가정하고 있다. 

만약에 자원이 없을 때 P연산을 하게 되면 while 문만 돌다가 cpu시간을 다 쓰고 반납하게 되며 busy-wait가 생긴다. 

//Synchronization variable
semaphore mutex;	//initially 1, 1개가 CS에 들어갈 수 있다. 

//Process Pi
do{
    P(mutex);	
    critical section
    V(mutex);	//increment semaphore
    remainder section
}while(1);

이미 누군가 critical section에 들어가 있으면 P연산을 하면서 while문을 돌면서 cpu시간을 쓰는 busy wait을 하게 된다. (=spin lock) 해당 방식을 효율적이지 못하다. lock을 얻지 못하면 while문을 돌면서 lock을 기다리는 것이다. 

Block & Wakeup 방식은 sleep lock이다. sleep lock은 lock을 못 얻으면 해당 프로세스는 cpu를 쓰는 것이 아니고 blocked상태가 되어 잠들어버린다. 

 

Block/Wakeup 방식

- semaphore를 다음과 같이 정의 

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

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

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

- semaphore 연산이 이제 다음과 같이 정의됨

P(S): S.value--;	//prepare to enter
	  if(S.value<0)	//oops.negative, i cannot enter
      {
      	add this process to S.L;
        block();
      }
V(S): S.value++;
	  if(S.value<=0){	//자원을 내놓았는데도 음수라는 말은 block된 프로세스가 많다는 말이므로 wakeup 해야 한다.
      		remove a process P from S.L;
            wakeup(P);
      }

S는 세마포어 변수. P연산에서는 세마포어 값에서 1을 빼준다. 해당 값이 음수면 자원의 여분이 없다는 말이므로 이 프로세스를 S.L 큐에 연결시킨 후 block 시킨다. 

S.value는 현재 자원의 상황을 말한다. 

 

세마 포어 구현 방식에 있어서 busy-wait을 쓸 것인가 block/wakeup을 쓸 것인가.

보통 block/wakeup을 쓰는 것이 더 효율적이다. 

Block/wakeup도 오버헤드가 있다.

ready 상태에서 blocked 상태로 바꾸고, 나중에 자원이 반납되어 공유데이터에 여유가 생기면 blocked 상태에 있는 것들을 ready로 바꿔줘야 한다. 이러한 작업에서 오버헤드가 생기기 때문에 critical section의 길이가 매우 짧은 경우에는 Block/Wakeup을 하지 않고 busy-wait를 하면 오버헤드가 오히려 작을 수 있다. 

CS의 길이가 길면 한번 lock을 걸고 굉장히 오랫동안 lock을 풀지 않아 계속 while문만 돌면서 기다리는 busy-wait은 비효율적이다. 

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

semaphore의 두가지 타입.

 

- Binary semaphore(=mutex)

• 0 또는 1 값만 가질 수 있는 semaphore
• 주로 mutual exclusion(lock/unlock)에 사용
• 세마포어 변수 값이 1개인 경우. 자원의 개수가 1개인 경우. 
• 보통 lock을 걸 때 자원의 개수를 1개로 세팅해서 사용한다. 

- counting semaphore

• 도메인이 0이상인 임의의 정수 값.
• 주로 resource counting에 사용. 여분의 자원을 세는 용도
• 자원의 개수가 여러 개 있어서 여분이 있으면 가져다 쓸 수 있는 경우. 

세마포어 사용 시 주의할 점

 

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

S와 Q가 1로 초기화된 semaphore라고 하면 P0와 P1이 S와 Q를 각각 잡고 놓지 않으며 상대방을 무한히 기다리게 된다. 

P0: P(S) P(Q)..... V(S) V(Q)

P1: P(Q) P(S)..... V(Q) V(S)

 

해결법은 자원을 획득하는 순서를 맞춰주면 된다. S를 얻고 Q를 얻는다는 순서를 맞춰주면 된다. Q를 얻기 전에는 꼭 S를 얻어야 하므로 deadlock에 걸리지 않게 된다. 

 

- Starvation : 특정한 프로세스가 영원히 자원을 얻지 못하고 무한히 기다려야 하는 상황을 starvation이라고 부른다. deadlock도 일종의 starvation으로 볼 수도 있다.