[운영체제] 세마포어(Semaphores)와 세마포어의 활용

세마포어(Semaphores)란?

 

지금까지 Critical Section Ploblem을 소프트웨어/하드웨어적으로 해결하는 방법을 찾아봤다. 소프트웨어적인 방법으로는 세 가지 솔루션이 있었고, 하드웨어적인 방법에는 Testset 인스트럭션을 사용했다.

 

 

조금 더 나은 방안은 하드웨어적으로 해결하는 것이라 하였는데, Testset 역시나 Busy Wating을 해야하는 큰 단점이 있다.

 

 

세마포어는 Busy Wating을 해결하는 효율적인 방법을 제시한다. 세마포어 자체만으로는 Int 값을 저장할 뿐인 구조체일 뿐이지만, _semWait (s)_와 _semSignal (s)_을 통해서 손쉽게 Critical Section Ploblem을 해결한다.

 

 

• semWait (s)
  • semiphore의 값을 1 감소 시킨다.
  • 운영체제에 따라 P(s), Wait(s), down(s)으로도 불린다.
• semSignal (s)
  • 운영체제에 따라 called V(s), Signal (s), sem_post(s)으로도 불린다.

 

각 함수들은 하드웨어의 지원을 받아 atomic 하게 동작한다.

 

 

Testset은 하나의 프로세스가 공유 자원에 대해 점유하고 있다면 다른 프로세스는 _while_문을 통해 의미 없는 time slice를 소모했다. 그러나 세마포어는 다르다. 세마포어를 통해 프로세스는 어떠한 프로세스가 공유 자원을 점유하고 있다는 사실을 안다. 해당 사실을 바탕으로 프로세스는 대기 큐(Block Queue)에 들어가 우선순위에 따라 기다린다. _semWait_가 바로 이렇게 대기 큐에 들어가거나 자원을 차지하는 것 중 하나를 결정한다. 

 

 

공유 자원을 점유하고 있던 프로세스가 해당 자원을 다 사용했다고 해보자. 이때 _semSignal_을 사용한다. 이 함수는 대기 큐에 만약 프로세스가 있다면, 우선순위에 해당되는 프로세스를 Block 상태에서 Ready Queue로 이동시킨다.

 

 

Ready Queue로 들어간 프로세스는 _semWait_에서 Block 된 상태에서 풀려나기 때문에 Critical Section 내의 자원을 가지는 것이 가능해진다.

 

 

코드를 통해 살펴보자.

 

semaphore

struct semaphore {
    int count;
    queueType queue;
}

 

 

 

semWait(semaphore s)

void semWait (semaphore s) {
    s.count--;
    if (s.count < 0) {
        /* 프로세스를 대기 큐(s.queue)로 집어넣는다. */
        /* 프로세스 Block */
    }
}

 

 

 

semSignal (semaphore s)

void semSignal (semaphore s) {
    s.count++;
    if (s.count <= 0) {
        /* 대기 큐(s.queue)로부터 프로세스 제거 */
        /* 프로세스를 Ready Queue로 넣는다. */
    }
}

 

 

대기 큐가 왜 semaphore 구조체 안에 있을까? 이전에 봤던 프로세스 상태도를 떠올려보자. 대기 큐는 하나로만 이루어진 게 아니다. 여러 이벤트들에 대해 각기 다른 대기 큐가 있다.

 

 

s.queue 또한 semaphore에서 발생하는 이벤트에 대한 대기 큐일 뿐이다.

 

 

 

 

 

 

세마포어에서 자주 사용하는 패턴

 

 

코드만으로 본다면 동작을 예상하기 어렵다. 실제로 세마포어는 초기에 저장되는 값에 따라 논리적인 의미가 달라진다. 가장 일반적인 경우부터 알아보자.

 

 

 

 

1. 간단하게 Mutual Exclusion을 보장하는 패턴

 

제일 많이 사용하는 패턴이다. semaphore에 초기값 1을 저장한다.

 

const int n = /* 프로세스 갯수 */
semaphore s = 1;
void P(int i) {
    while (true) {
        semWait (s);
        /* critical section */
        semSignal (s);
        /* remainder */
    }
}

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

 

 

_semWait_에 1 값이 전달된다면, _count_가 하나 줄어들어 세마포어는 0의 값을 가진다. Context Switch 된 프로세스는 critical section에 접근할 때 _count_가 0 미만의 값을 가진다. 따라서 Context Switch된 프로세스는 대기 큐에 들어가며 Block 상태로 이동한다.

 

 

다시 Context Switch 되어 기존 프로세스로 돌아와보자. critical section의 모든 작업이 끝나고, _semSignal_이 호출된 상황이다. count는 다시 하나 증가한다.

 

 

만약 이 프로세스가 critical section에 있는 동안 다른 프로세스가 아무도 _semWait_을 호출하지 않았다면 semaphore는 1이다. 이런 상태에서 Context Switch되어 다른 프로세스가 Critical Section에 접근해도 아무런 문제가 없다.

 

 

하나의 프로세스가 critical section에 있는 동안 다른 프로세스가 _semWait_을 호출했다고 해보자. 호출한 프로세스는 semaphore를 하나 빼어 -1이 되고, Block 상태로 이동한다. 기존의 critical section에 있던 프로세스가 끝났다. 그러면 _semSignal_로 인해 semaphore는 0이 되지만, 대기 큐에 프로세스가 존재해 조건문 안으로 진입한다.

 

 

조건문으로 인해 대기 큐에 존재하던 프로세스는 Ready Queue로 이동한다. Ready Queue에 있는 프로세스는 이제 Critical Section으로 이동이 가능하다.

 

 

 

 

 

 

 

2. 프로세스 간 우선순위를 보장하는 패턴

 

하나의 프로세스가 다른 프로세스보다 먼저 실행해야 한다면 semaphore를 0으로 두자. 또한 코드의 위치는 아래 그림과 같이 두자.

 

 

 

조건만 만족시킨다면 어떠한 상황이든, Pi가 Pk보다 먼저 동작한다.

 

 

1. Pk가 먼저 실행된 경우

 

_semWait_으로 인해 semaphore는 -1이다. 따라서 Pk는 Block 된다. Pi는 따로 _semWait_이 없다. 따라서 코드를 진행하다가 _semSignal_를 이내 만난다. _semSignal_로 인해 semaphore는 0이 되고, Pk는 Ready Queue로 빠져나가 코드 실행이 가능해진다.

 

 

2. Pi가 먼저 실행된 경우

 

Pi는 _semWait_이 없으니 _semSignal(flag)_를 만날 때까지 편하게 실행한다. 혹여나 Pk로 바뀌더라도 1. 의 과정을 통해 Pi가 먼저 실행됨이 보장된다. _semSignal(flag)_를 먼저 만나면 semaphore는 1이 되며 Pk로 바뀌어도 Pk는 대기큐로 들어가지 않는다.

 

 

 

 

 

※ Producer/Consumer 문제 해결하기

 

앞서 Race Condition이 발생했던 Producer/Consumer 문제를 세마 포어를 통해 해결해 보자.

 

 

Semaphore

semaphore counter = 0;
semaphore empty = BUFFER_SIZE;
semaphore mut_ex = 1;

 

 

Producer

while (true) {
    produce();
    semWait(empty);
    semWait(mut_ex);
    append();
    semSignal(mut_ex);
    semSignal(counter);
}

 

 

 

Consumer

while (true) {
    semWait(counter);
    semWait(mut_ex);
    take();
    semSignal(mut_ex);
    semSignal(empty);
    consume();
}

 

 

_mut ex_는 1 패턴을 적용시킨 것이다. 각 작업을 수행하는데 Race Condition이 일어나지 않도록 해준다.

_counter_는 Producer가 우선적으로 실행하도록 한다.

_empty_는 BUFFER SIZE만큼 채워져 있는데, 버퍼보다 더 많은 Produce()가 일어나지 않게 한다.

 

 

 

3. Readers/Writers Problem을 해결하는 패턴

 

여러 프로세스가 읽는 것은 가능하지만, 읽는 프로세스가 어느 하나라도 있다면 수정을 해서는 안된다. 세마포어를 사용한다면, 이를 보장하는 패턴을 손쉽게 만드는 게 가능하다.

 

 

Writer

void writer() {
    while (true) {
        semWait(wsem);
        WRITEUNIT();
        semSignal(wsem);
    }
}

 

 

Reader

void reader() {
    while (true) {
        semWait(rsem);
        readcount++;
        if (readcount == 1) semWait (wsem);
        semSignal(rsem);
        
        READUNIT();
        
        semWait (rsem);
        readcount--;
        if (readcount == 0) semSignal(wsem);
        semSignal (rsem);
    }
}

 

 

_rsem_과 _wsem_은 각각 reader와 writer에 대한 세마포어 변수 값이다. 이 값들은 각각 1로 초기화한다.

먼저 _semWait(rsem)_과 _semSignal(rsem)_이 사용되는데, 이는 _readcount_를 증가시키는 일이 다른 reader들과 경쟁관계가 일어나면 안 되기 때문이다.

 

 

_readcount_가 1이라는 것은 reader 하나가 처음 들어왔다는 뜻이고, writer가 미리 들어가 있는 가능성을 고려해야 한다. writer가 미리 들어가 있다면 reader는 writer가 나올 때까지 기다려야 하므로 _semWait(wsem)_을 한다. 반대로 writer가 들어가 있지 않다면 reader가 먼저 _semWait(wsem)_을 호출했으므로, writer는 들어갈 수 없다.

reader가 읽는 동안 수정할 수 없고, writer가 수정하는 동안 reader는 읽을 수 없는 것이다.

 

 

여기까지의 과정을 통과한다면, read작업이 일어나도 좋다. READUNIT() 함수를 호출해 주자.

이제 모든 read작업이 끝났다. 그러면 _readcount_는 하나 줄어들어야 하기 때문에 마찬가지로 1 패턴을 적용시켜 주자. _readcount_가 0인 조건은 더 이상 자기 자신 프로세스 뒤에 다른 read 프로세스가 없는 상태다. 앞서 _semWait(wsem)_으로 reader가 읽는 동안 수정하지 않도록 설정해 주었기 때문에 writer가 다시 수정할 수 있도록 풀어주어야 한다. 이런 역할을 해주는 게 _semSignal(wsem)_이다.

 

 

 

 

 

 

Binary Semaphore, Lock

 

세마포어 값을 0과 1만 가지는 세마포어를 Binary Semaphore(= mutex)라고 한다.

이미 critical section에 어느 프로세스가 들어가 있다면, 어떤 프로세스도 들어갈 수 없다.

기존에 배운 것과 다른 점은 ready queue의 개념으로 대기하는 프로세스 간의 우선순위가 정해지지 않는다. 따라서 이론 상 bounded wating이 적용되지 않는다.

 

 

Lock도 결국 Binary Semaphore를 나타낸다. 이름만 다를 뿐이지 실제로 동작은 같다. Linux에서는 lock을 처리하는 Thread Library가 있다. phread mutex unlock과 pthread mutex lock이 있으며 bounded wating을 보장한다.

 

 

 

 

 

 

 

 

Monitors

 

 

프로그래머들이 보다 쉽게 동기화 문제를 해결할 수 있는 고수준의 동기화 메커니즘이다.