) Philosophers - Process Synchronization 2

Semaphores

추상자료형 : object + operation

Semaphore S

• 변수 S는 정수값 (자원의 개수)
• 두 가지 atomic 연산에 의해서만 접근 가능

//공유 데이터를 획득하는 과정
//lock을 거는 과정
P(S) : while (S <= 0) do no-op; //wait
		S--;

//공유 데이터를 반납하는 과정
//lock을 푸는 과정
V(S) : S++;

Critical Section에 Semaphores 사용

Synchronization variable
	semaphore mutex; //initially 1 : 1개가 Critical Section에 들어갈 수 있다.

Process Pi
do {
	P(mutex); //busy-wait(=spin lock) 발생
    critical section
    V(mutex);
    remainder section
} while(1);

busy-wait는 효율적이지 못함

Block & Wakeup 방식 (=sleep lock)

그림에서는 프로세스가 오래 걸리는 작업을 하면 프로세스의 상태를 blocked로 설정한다. 그래서 CPU를 얻을 수 있는 권한 자체가 없어진다. 그 프로세스는 해당하는 작업만 할 수 있으며 작업이 끝나면 다시 CPU에 접근이 가능한 ready queue로 돌아올 수 있는 권한이 생긴다.

마찬가지로 spin lock으로 인한 CPU 낭비를 줄이기 위해 while문을 통한 계속적인 확인이 아닌, 공유데이터에 대한 프로세스 자체를 blocked 시켜서 CPU를 반납하고 잠들어있다가 공유데이터를 가지고 있던 프로세스가 내놓으면 그때 ready queue로 들어와 CPU에 접근이 가능하다.

Semaphore 정의

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

block, wakeup

• block : 세마포어를 획득할 수 없으면 프로세스를 block. 커널은 block을 호출한 프로세스를 suspend 시킨다. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
• wakeup(P) : 세마포어를 반납하는 경우 block된 프로세스를 wakeup. 이 프로세스의 PCB를 ready queue로 옮긴다.
  

//자원에 여분이 있으면 획득, 없으면 block
P(S) : 	S.value--;
		if (S.value < 0) //자원의 여분이 없는 경우
        {
        	add this process to S.L;
            block();
        }

//자원을 다쓰고 반납, 자원을 기다리다가 잠들어 있는 프로세스가 있으면 wakeup 
V(S) :  S.value++; //자원을 다쓰면
		if (S.value <= 0) //자원을 내놓았는데도 0이하이면 잠들어 있는 프로세스가 있는 경우
        {
			remove a process P from S.L;
            wakeup(P);
        }

Which is Better?

Busy-wait vs Block/Wakeup
보통은 Block & Wakeup이 효율적이다.

하지만 Block & Wakeup도 오버헤드가 있다.

오버헤드(overhead)는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리를 말한다.

Block/Wakeup overhead vs Critical section 길이
Critical section의 길이가 긴 경우, Block/Wakeup이 적당하다.
Critical section의 길이가 매우 짧은 경우, Block/Wakeup 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있다.

Two Types of Semaphore

Counting semaphore

• 도메인이 0이상인 임의의 정수값
• 주로 여분의 자원의 수를 카운팅할 때 사용

Binary semaphore(=mutex)

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

Deadlock and Starvation

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
상대방이 가진 것을 기다리면서 자신의 것은 내어놓지 않는 상태

Starvation

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