[운영체제] 6-2. Semaphore

오늘은 critical section problem을 해결할 수 있는 HW support 방법 중 하나인 Semaphore에 대해서 알아봅시다.

 

---

Semaphore

semaphore는 이전 글에서 소개드린 testset의 단점인 busy waiting을 해결하고, bounded waiting 또한 깔끔하게 해결할 수 있는 방식입니다.

 

testset과 마찬가지로, semaphore도 atomic operation을 이용하여 critical section problem을 해결합니다.

 

Semaphore는 하나의 정수와, 큐를 갖는 구조를 의미합니다. 이들의 쓰임은 아래에서 확인합시다.

Semaphore에서는 특별한 함수 semWait(s)과 semSignal(s)을 사용합니다. 

 

semWait(s)은 semaphore의 값을 1 감소 시킵니다. 이는 atomic operation이며 운영체제에 따라 P(s), Wait(s), down(s)라고도 합니다.

semSignal(s)는 semaphore의 값을 1 증가시킵니다. 이 또한 atomic operation이며 운영체제에 따라 V(s), Signal(s), up(s), sem_post(s)라고도 합니다.

 

 

 

Semaphore의 작동 원리

간단한 예시와 함께 semaphore의 원리를 소개하고자 합니다.

 

기차 여러대가 하나의 기찻길을 지나가야합니다. 기찻길이 하나이므로 이 길을 지날 때는 규칙을 지키면서 운행해야합니다.

만약 기관사가 공유하는 기찻길을 지나가야한다면, 우선 출발하기 전 내려서 가운데 바구니 있는 곳으로 갑니다. 바구니와 돌은 각각 하나씩 있다고 가정합시다.

 

만약 바구니에 돌이 있다면 그 바구니에서 돌을 꺼낸 후, 기차로 돌아와 공유 기찻길을 지납니다. 다 지나간 후에, 내려서 꺼낸 돌을 다시 바구니에 집어넣습니다. 그리고 만약 바구니 옆에서 자고있는 기관사가 있다면 바구니에 가장 가깝게 자고있는 기관사를 깨웁니다.

 

만약 바구니에 돌이 없다면 그 바구니 옆에서 낮잠을 자게 됩니다. 만약 자고있는 기관사를 누군가 꺠운다면, 바구니 안에 돌이 있을 것이므로 그 돌을 빼고 운행을 시작합니다.

 

 

이러한 방식으로 semaphore는 critical section problem을 해결합니다.

앞선 예시에서 공유하는 기찻길은 critical section을 의미하고, 바구니가 semaphore를 의미합니다. 1이면 돌이 바구니에 있는 것이고, 0이면 바구니에 돌이 없는 것이죠.

또한 기차는 프로세스가 되겠습니다.

 

 

 

그럼 이제, semaphore가 어떻게 코드로 구현되어있는 지 확인해봅시다.

 

class Semaphore{
	int count;
    Queue queue;
}

void semWait(Semaphore s){
	s.count--;
    if(s.count < 0){
    	현재 프로세스를 s.queue에 넣습니다.
        현재 프로세스의 state를 block으로 변경합니다.
    }
}

void semSignal(Semaphore s){
	s.count++;
    if(s.count <= 0){
    	s.queue에서 pop을 해줍니다.
        pop한 프로세스를 ready queue에 넣습니다.
    }
}

 

semaphore의 작동방식은 이러한 의사코드와 같습니다.

 

semWait에서 s.count--는 semaphore의 값을 감소하는 것을 의미하고 s.count < 0이라는 것은 이전에 semaphore가 0이었다는 뜻이고, 이는 critical section을 진행할 수 없음을 의미합니다. 따라서 block으로 변경됩니다.

 

semSignal에서 s.count++은 semaphore의 값을 증가시키며, s.count <= 0이라는 것은 아직 자신의 프로세스보다 먼저 critical section을 진행하기 위해 기다리는 사람이 있다는 것을 의미합니다. 따라서, semaphore의 queue에서 pop을 해준 뒤, 해당 프로세스를 ready queue에 넣습니다.

 

 

Semaphore의 적용

혹시 지금까지의 흐름을 잘 이해하지 못하셨다면, 아래의 실제 적용 코드를 통해서 확인해봅시다.

 

int n = 10; // process의 개수
Semaphore s = 1;

void p(int i){
	while(true){
    	semWait(s);
        /* critical section */
        semSignal(s);
    }
}

void main(){
	parbegin(p(1), p(2), ..., p(n));
}

적용 코드는 위와 같습니다. critical section을 해결하기 위해 semWait를 이용하여 바구니에서 돌을 뺀 후, critical section을 진행합니다. 만약, 누군가가 이미 critical section을 실행 중이라면, 바구니에 돌이 없기 때문에 해당 프로세스는 block 상태가 될 것입니다.

 

또한 critical section의 실행을 끝냈다면, semSignal(s)를 통해서 바구니에 돌을 다시 집어넣게 됩니다.

 

이러한 방식으로 semaphore를 사용합니다.

 

 

벌써 눈치채신 분들도 있겠지만, semaphore에서 semWait(s)와 semSignal(s)의 순서는 정해져있지 않습니다. 이 둘의 총 개수만 일치하면 되는 것이지, semWait(s)를 무조건 먼저 실행하고 semSignal(s)를 후에 실행하는 이러한 규칙을 지정되어 있지 않습니다.

실제 예시를 봐도, 바구니에 돌이 있는 상태를 누군가가 critical section을 실행 중이라는 것으로 볼 수 있으니 말이죠.

 

---

오늘은 운영체제의 핵심 개념, critical section problem의 방법 중 하나인 semaphore에 대해서 알아봤습니다. 다음 시간에는 semaphore를 이용해서 어떻게 활용하는지를 확인해보겠습니다. 감사합니다.