Semaphores

Semaphores

---

semaphore는 mutex와 유사하게 동작하는 동기화 문제를 해결하기 위한 방법.

여러 process가 공유 resource에 접근할 때, 한 process가 critical section에서 수행중이라면 다른 process는 자신의 ciritical section에 들어가지 못하게 해야한다.

 

semaphore는 critical section에 들어가기 전 semaphore를 통해 resource에 접근 가능한 지 확인을 하며 동기화 문제를 해결한다.

 

mutex보다 process들이 자신들의 행동을 더 정교하게 동기화할 수 있는 방법을 제공한다.

 

P연산과 V연산

---

Semaphore S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 atomic operation인 wait()와 signal()로만 접근할 수 있는데, 여기서 wiat() 연산은 검사하다를 의미하는 네덜란드어 proberen에서 P, signal() 연산은 증가하다를 의미하는 verhogen에서 V라고 지어졌다.

 

wait()와 signal()의 정의는 다음과 같다.

wait(): P연산, resource를 할당하는 연산

wait(S) {
	
    while(S <= 0); // busy wait
    S--;
}

signal(): V연산, resource를 해제하는 연산

signal(S) {

	S++;
}

 

한 thread가 semaphore 값을 변경하면, 다른 어떤 thread도 동시에 동일한 semaphore 값을 변경할 수 없다.

wait(S)의 경우, S의 정수 값을 검사하는 작업(S<=0)과 그에 따라 실행할 수 있는 변경(S--)하는 작업 또한 interrupt 되지 않고 실행되어야 한다.

 

사용법

---

counting semaphore

counting semaphore의 값은 제한 없는 영역(domain)을 갖는다. 유한한 개수를 가진 resource에 대한 접근을 제어하는 데 사용될 수 있다. semaphore는 가용한 resource의 개수로 초기화된다. 각 resource를 사용하려는 process는 semaphore에 wait() 연산을 수행하며, 이 때 semaphore의 값은 감소한다. process가 resource를 방출할 때는 signal() 연산을 수행하고 semaphore는 증가하게 된다. semaphore의 값이 0이 되면 모든 resource가 사용 중임을 나타낸다. 이후 resource를 사용하려는 process는 semaphore 값이 0보다 커질 때까지 봉쇄된다.

 

binary semaphore

binary semaphore의 값은 0과 1 사이의 값만 가능하다. 그렇기 때문에 mutex lock과 유사하게 동작한다. (그냥 mutex라 봐도 좋다)

 

동기화 문제를 해결하기 위한 semaphore 사용

P1은 S1 명령문을, P2는 S2 명령문을 병렬적으로 수행하려는 두 process가 있다고 하자. S2는 S1이 끝난 후 수행되어야 한다고 하자. 이 때 P1과 P2가 synch 변수를 공유하도록 하고 synch를 0으로 초기화 한다.

P1

S1;
signal(synch);

P2

wait(synch);
S2;

 

P1에서 S1이 수행되고 signal(synch)를 통해 synch 값이 1로 증가되면 그제서야 P2에서 S2가 수행될 수 있다.

* critical section에 들어가지 못하는 process는 busy waitng 해주어야 한다.

 

 

Implementation

---

문제는 CPU를 받아서 waiting만 해주게 되는 것이다. critical section에서 overhead가 굉장히 크다면 다른 process가 cirical section에서 수행할 동안 단순히 busy waiting만 해주는 것은 CPU의 활용도를 떨어뜨릴 수 있다.

그래서 busy waiting으로 하는 대신, critical section에 들어가지 못하는 process가 있다면 block시키도록 한다. 아에 그 process에게 CPU를 할당하지 않고 ready queue의 다른 process가 CPU 할당을 하도록 만들어주는 방법이 no-busy waiting을 가능하게 하는 semaphore scheme이다.

 

with no busy waiting

critical section에 들어가지 못해서, busy waiting을 하지 않는 process들을 위한 waiting queue가 선언되어야 한다.

waiting queue에 있는 각 entry는

• value (of type integer / semaphore value)
• pointer to next record in the list

Two operations

• block
• wakeup

 

busy waiting 문제를 해결하기 위해 우선 wait()와 signal() 연산을 새롭게 정의해야 한다. wait()연산 실행 후 semaphore 값이 양수가 아니면 busy waiting을 하는 것이 아닌 process를 일시 정지하도록 하고 process 상태는 대기 상태로 전환한다.

semaphore S 변수 값을 대기하면서 일시 중지된 process는 다른 process가 signal() 연산을 실행하면 재시작 된다. process는 wakeup() 연산에 의해 재시작되는데 process를 wait 상태에서 ready 상태로 변경한다. 그리고 process는 ready queue에 들어가게 된다.

 

이러한 정의들을 따르는 semaphore를 구현하기 위해 semaphore는 다음과 같이 정의한다.

typedef struct {
	
    int value;
    struct process *list;
} semaphore;

wait()

wait(semaphore *S) {
	
    S->value--;
    if(S->value < 0) {
    	add this process to S->list;
        block();
    }
}

S->value가 0보다 작으면 waiting queue에 넣는다 => block을 한다.

다른 process에게 CPU가 넘어간다.

이 때 block에 따른 context switch가 발생한다.

signal()

signal(semaphore *S) {
	
    S->value++;
    if(S->value <= 0) {
    	remove a process P from S->list;
        wakeup(P);
    }
}

critical section을 빠져나오게 되면 value 값을 증가시킨다.

waiting queue에서 process를 remove 해주고 wakeup으로 ready queue에 넣어준다. (바로 running state가 될 수 없다)

 

*만일 critical section이 매우 짧으면 waiting queue에 넣는 방식이 더 손해가 될 수 있다.

 

 

Deadlock and Starvation

---

semaphore를 쓰게 되면 deadlock이 발생할 수도 있기 때문에 이 부분을 잘 고려해서 설계해야 한다.

 

starvation - indefinite blocking

두 process P0, P1이 있다고 하자. S=1, Q=1로 초기화 되었다고 하자.

P0

wait(S);
wait(Q);

// critical section

signal(S);
signal(Q);

P1

wait(Q);
wait(S);

// critical section

signal(Q);
signal(S);

 

S = 1, Q = 1

P0가 먼저 wait(S)를 하면서

S = 0, Q = 1

그 순간 CPU가 P1으로 넘어가서 wait(Q)를 하면

S = 0, Q = 0

다시 P0로 CPU가 넘어가서 wait(Q)를 하면

S = 0, Q = -1 ---> 이 때 P0에서 block이 된다.

다시 P1으로 넘어가서 wait(S)를 하면

S = -1, Q = -1 ---> 이 때 P1에서 block이 된다.

 

P0와 P1 둘 다 block이 되면서 어떠한 process도 수행되지 못하는 상태가 된다(deadlock)

 

priority inversion

priority가 L < M < H가 있고 L과 H가 둘 다 resource R을 요구한다고 하자.

L이 먼저 요청을 해서 R을 가진 상태.

 

H는 L이 release하기 전까지 wait 상태가 된다.

그런데 M이 수행되면서 L은 M에게 CPU를 빼앗기게 된다.(preemption)

H는 priority가 높지만 할 수 있는 것은 busy waiting밖에 없게된다.

이는 L의 priority를 높여주어야 해결할 수 있다. (priority-inheritance protocol)