[ 운영체제 ] 동기화 방법3 - Semaphores

세마포어는 Mutex의 spin lock 문제를 해결해주는 동기화 방법이다. 참고로 세마포어는 유명하신 '다익스트라' 님께서 고안해내신 알고리즘이다. 다익스트라 알고리즘의 그 다익스트라 맞다. 정말 대단하신 분인 것 같다.

 

Mutex에서 lock은 boolean 값으로 참 또는 거짓의 값만 가진다. 반면에 세마포어에서는 boolean 대신 integer 값의 변수를 이용한다. 엄밀히 말해서 세마포어는 구조체 형태인데, 구조는 아래와 같다. 

 

typedef struct{
    int value; // 사용 가능한 자원의 수
    struct process *list; // waiting queue
}semaphore;

 

 

세마포어의 집입 구역과 퇴출 구역은 각각 wait() 함수와 signal() 함수가 담당한다. 세마포어는 구조체의 value 값에 따라 Binary Semaphore와 Counting Semaphore로 나뉘는데, 종류에 따라 wait() 함수와 signal() 함수가 다르게 정의된다. 

1. Binary Semaphore

세마포어 구조체의 value 값이 1로 초기화된 경우다. 아까 위에서 value는 '사용 가능한 자원의 수'라고 했다. value가 1이라는 것은 여러 개의 프로세스가 하나의 자원을 가지고 경쟁한다는 뜻이다. 따라서 Mutex Lock와 거의 비슷하다고 할 수 있다. 다만 세마포어는 waiting queue를 가지고 있어 busy waiting 현상을 방지할 수 있다는 점만 다르다. Binary Semaphore의 경우 wait(), signal() 함수는 아래와 같다.

 

wait(semaphore *S){
    if(S->value == 0){
        add this process to S->list; // wait state
        block(); 
    }
    else s->value = 0;
}

signal(semaphore *S){
    if(not empty S->list){
    remove a process P from S->list; // ready state
    wakeup(P);
    }
    else S->value = 1;
}

2. Counting Semaphore

세마포어 구조체의 value 값이 1보다 큰 값으로 초기화된 경우다. 여러 프로세스에 제한된 양의 자원을 할당해 줄 때 유용하게 쓸 수 있다. 사용가능한 자원이 두 개 이상이므로 임계 구역에 진입 가능한 프로세스도 두 개 이상이다. Counting Semaphore의 경우 wait(), signal() 함수는 아래와 같다.

 

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

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

 

 

Spinlock이 무조건 나쁠까?

 

이 질문에 대한 답변을 해보자. 세마포어는 Block & Wakeup 구조로 spinlock의 문제를 해결하고 있다. 그런데 과연 spinlock이 무조건 나쁘다고 할 수 있을까? Block & Wakeup 구조는 context switch 현상이 발생한다. 그런데 context switch도 오버헤드가 발생한다는 사실을 잊으면 안 된다. 따라서 아래와 같이 정리할 수 있다.

 

• 임계 구역이 매우 짧고, 진입하고자 하는 프로세스가 많지 않아 busy waiting 할 시간이 적으면, busy waiting 하는 구조가 유리하다
• 임계 구역이 매우 길고, 진입하고자 하는 프로세스가 매우 많다면, Block & Wakeup 구조가 유리하다

결국 두 방법 모두 오버헤드가 발생하고, 오버헤드 시간이 더 짧은 방법이 유리한 방법인 것이다. 따라서 각 상황에 맞는 올바른 알고리즘을 설계할 필요가 있다. 

 

어쨌든 세마포어는 Block & Wakeup 구조를 통해 spinlock 문제를 해결했다. 그러나 Block & Wakeup 구조 때문에 또 다른 문제가 발생한다. 

 

세마포어 단점

1. Deadlocks and Starvation

데드락 상태

 

S와 Q는 각각 1로 초기화된 binary semaphore라고 가정하자. 두 개의 프로세스가 위와 같은 순서로 binary semaphore를 호출하면 어떻게 될까?

 

첫 번째 순서를 먼저 보자. P0은 wait(S)를 호출했으므로 S의 value는 0이 되고, P1은 wait(Q)를 호출했으므로 Q의 value도 0이 된다. 

 

wait(semaphore *S){
    if(S->value == 0){
        add this process to S->list; // wait state
        block(); 
    }
    else s->value = 0;
}

 

두 번째 순서를 보자. P0은 wait(Q)를 호출한다. Q의 value 값은 0이므로 P0은 block 상태가 된다. P1도 wait(S)를 호출하면 같은 이유로 block 상태가 된다. 어느 하나가 signal을 호출해야 ready queue에서 빠져나올 수 있는데 둘 다 block 상태이기 때문에 서로 영원히 기다리는 기이한 현상이 발생해버렸다. 이를 deadlock이라고 한다. 데드락은 다다음 글부터 자세히 다룰 예정이기 때문에 우선 넘어가자. 서로 영원히 기다리므로 starvation 문제도 덤으로 생긴다. 

2. Priority Inversion (우선순위 역전 현상)

우선순위가 높은 프로세스가 block 되어 우선순위가 낮은 프로세스가 점유하고 있는 자원을 wait 하고 있는 경우 우선순위가 낮은 프로세스가 먼저 실행되는 문제다. 아래와 같은 상황을 가정해보자.

세 개의 프로세스 L, M, H 가 있고, 우선 순위는 L < M < H (높은 게 먼저 실행)

 

 

1. L이 자원 R을 사용중이므로 H는 block()
2. L이 CPU를 사용중이다
3. R을 사용하지 않는 M이 ready state가 되어 우선순위에 따라 CPU를 뺐어버린다
4. M의 실행이 끝나고 L이 다시 CPU를 쓴다
5. L은 볼 일 다보고 signal 호출
6. H가 R 점유하고 CPU 사용

우선순위가 가장 높은 프로세스 H가 제일 마지막에 실행되고 있다. 이렇게 우선순위에 위배되는 현상을 바로 Priority Inversion(우선순위 역전) 현상이라고 한다. 이 문제는 PIP(Priority Inheritance Protocol)로 해결 가능하다.

 

PIP 알고리즘은 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스의 자원을 대기하고 있을 때, 자신의 우선순위를 상속하는 방법이다. 즉, 위 그림에서 H가 L이 끝나기를 기다리고 있으므로 H가 L에게 자신의 우선순위를 상속한다. 

이렇게 되면 M은 우선순위에 따라 CPU를 선점할 수 없게 된다. 우선순위를 상속 받은 L이 작업을 다 끝내고 signal을 호출하면, H가 R을 점유하고 우선순위에 따라 M에 우선하여 CPU를 차지하게 된다. H의 작업이 다 끝나야 비로소 M이 CPU를 차지한다. 참고로 우선순위를 상속받은 L은 작업을 마치고 다시 원래 우선순위로 돌아온다. 

 

 

예전에 미국 NASA에서 화성 탐사선 패스파인더호를 화성에 착륙시킨 후 자동차처럼 생긴 로봇을 통해 화성사진을 보내오던 적이 있었다. 그런데 이후 고장이 나서 별다른 추가 정보를 얻지 못했다. 이 로봇의 고장 원인이 바로 우선순위 역전 현상이었다. 높은 우선순위의 작업들이 낮은 우선순위의 작업들의 수행에 밀려 작동을 못하게 되어 고장이 났다고 한다.