OS: Semaphore 예제

두 개 이상의 프로세스가 동시에 공유 자원에 접근할 때, 접근 순서에 따라 결과가 달라지는 Race condition 문제가 발생할 수 있다. 예를 들어 2개의 프로세스가 count 변수에 접근한다고 생각해 보자.

int count = 0;

void process_A() {
    Load R, count;
    Add R, 1;
    Store R, count;
}

void process_B() {
    Load R, count;
    Add R, 1;
    Store R, count;
}

Process A → B 순서로 접근하면 count는 2가 되어야 한다. 그런데 A가 R을 Load 한 상태에서 preemption 되었다고 하자. 그럼 B도 count가 0인 상태로 가져간다. 두 프로세스 모두 0 + 1을 계산해 count에 저장한다. 결국 count는 2가 아닌 1이 된다.

두 개 이상의 프로세스가 동시에 접근하지 못하도록 하는 문제를 mutual exclusion이라고 한다. 동시에 접근할 때 문제가 발생할 수 있는 코드 영역을 critical section이라고 한다.

Semaphore

Semaphore는 정수형 변수를 이용해 mutual exclusion을 해결하는 방법이다.

P(S): S가 0보다 크면 S--. 그렇지 않으면 프로세스를 Queue에서 wait 시킨다.
V(S): Queue에 기다리는 프로세스가 있으면 wakeup 한다. 그렇지 않으면 S++.

P와 V는 indivisible/atomic 한 연산이다. 실행이 시작되면 간섭받지 않고 끝까지 완료한다. S는 semaphore 변수다.

값이 0 또는 1인 binary semaphore를 사용하면 mutual exclusion과 synchronization을 해결할 수 있다. 0 또는 자연수인 counting semaphore를 사용하면 producer-consumer나 reader-writer 같이 복잡한 문제를 풀 수 있다.

Mutual Exclusion

int s = 1; // semaphore

void Process {
    P(s);
    /* Critical Section */
    V(s);
}

Critical section에 진입하기 전, semaphore를 0으로 바꾼다. Critical section을 나올 때 semaphore를 1로 되돌린다.

1: critical section에 진입한 프로세스가 없는 경우 (초기값)
0: critical section에 프로세스가 있는 경우

만약 프로세스 A가 P()를 실행하고 criticial section에 진입한 상태라고 생각해 보자. 다른 프로세스가 접근하기 위해 P()를 실행하면, queue에 가서 wait 하게 된다 (P 설명 참고).

프로세스 A가 V()를 하면 queue에서 기다리던 process를 wakeup 하고 critical section에 진입할 수 있다. 이때 semaphore는 여전히 0이다.

모든 프로세스가 critical section에서 빠져나오면 queue가 비어있다. 따라서 V()에 의해 semaphore는 1로 돌아온다.

Synchronization

Synchronization은 두 프로세스가 서로의 정보를 일치시키는 일이다. 프로세스 A에 대한 정보를 B가 알도록 하고, 그 반대도 마찬가지다.

예를 들어, 반드시 A가 먼저 실행되고, B가 실행되어야 하는 상황이 있다고 하자. 프로세스가 A가 완료되면 B는 'A가 완료되었다'라는 정보를 알아야 한다.

위 예시에서 A가 먼저 실행되고, B가 실행된다면 문제가 되지 않는다. 하지만 그 반대 상황을 생각해 보자.

B가 먼저 실행되면 P()를 통해 queue에서 wait 한다. A가 실행을 완료하고 V()를 하면 queue에서 wait하던 프로세스를 wakeup한다. 따라서 A가 완료되었다는 정보를 B가 알 수 있게 된다.

0: A를 실행하지 않은 상태 (초기값)
1: A를 실행 중인 상태

Producer-consumer

N개의 buffer가 circular buffer 형태로 존재할 때,

Producer: buffer에 정보를 생성한다.
Consumer: buffer에 작성된 정보를 소비한다.

이 문제에서 producer와 consumer가 충돌하면 안 된다.

producer-producer: 두 producer가 동시에 접근하면 하나의 버퍼에 정보를 덮어쓰는 현상이 발생한다. (mutual exclusion)
producer-consumer: producer가 정보를 완전히 생성한 뒤 consumer가 접근해야 한다. (synchronization)
consumer-consumer: 두 consumer가 동시에 접근하면 하나의 정보를 두 번 소비하는 오류가 발생한다. (mutual exclusion)

int nFull = 0; // 채워진 buffer 개수
int nEmpty = N; // 비어있는 buffer 개수
int mutexP = 1; // producer binary mutex
int mutexC = 1; // producer binary mutex
buffer[N];
int in = 0; // producer가 접근할 buffer 위치
int out = 0; // consumer가 접근할 buffer 위치

위에서 봤듯 producer-consumer 간 mutual exclusion을 위해 각각 binary semaphore를 사용한다.

void Producer() {
    Create message M;
    P(mutexP);
    /* Enter critical section */
    
    P(nEmpty);
    buffer[in] = M;
    in = (in + 1) % N;
    V(nFull);
    
    /* Exit critical section */
    V(mutexP);
}

mutexP는 critical section 내 mutual exclusion이 지켜지도록 하는 semaphore다.

P(nEmpty)는 빈 공간을 1개 줄인다. 만약 빈 공간이 없다면, 공간이 생길 때까지 producer는 wait한다.

V(nFull)은 채워진 공간을 1개 늘린다. 만약 wait 하고 있는 reader가 있다면, wakeup 한다.

여기서 nEmpty와 nFull은 synchronization 문제를 담당하는 semaphore다.

void Consumer() {
    P(mutexC);
    /* Enter critical section */
    
    P(nFull);
    M = buffer[out];
    out = (out + 1) % N;
    V(nEmpty);
    
    /* Exit critical section */
    V(mutexC);
    Consume message M;
}

동일하게 mutexC는 consumer 간 mutual exclusion이 지켜지도록 하는 semaphore다.

P(nFull)은 채워진 공간을 1개 늘린다. 만약 소비할 정보가 0개라면 wait 한다.

V(nEmpty)는 빈 공간을 1개 늘린다. 만약 wait 하고 있는 producer가 있다면 wakeup 한다.

Semaphore 4개를 이용해 producer-consumer 간 mutual exclusion과 synchronization 문제를 해결했다.

Reader-writer

reader-writer 문제는 reader가 동시에 여러 번 접근하는 것을 허용한다. 반면 writer는 producer처럼 한 번에 하나씩 접근해야 한다. 쓰는 동작보다 읽는 동작이 훨씬 많을 때 유용한 구조이다.

writer-writer: writer가 동시에 접근하면 안 된다. (mutual exclusion)
writer-reader: writer가 접근했을 때는 reader가 접근하지 않는다. (mutual exclusion)

int mutexW = 1; // binary semaphore
int mutexR = 1; // binary semaphore
int nReader = 0;

void Reader() {
    P(mutexR);
    /* Enter critical section */
    if (nReader == 0) {
        P(mutexW);
    }
    nReader++;
    /* Exit critical section */
    V(mutexR);
    
    Read something;
    
    P(mutexR);
    /* Enter critical section */
    nReader--;
    if (nReader == 0) {
        V(mutexW);
    }
    /* Exit critical section */
    V(mutexR);
}

Reader는 writer와 충돌을 피하기 위해 P(mutexW)를 실행한다. nReader==0을 확인하는 이유는 여러 reader가 동시에 접근할 때, 처음 접근한 reader만 mutexW를 잡고 있으면 되기 때문이다. 어느 reader가 잡고 있든 writer는 접근하지 못한다.

읽는 동작은 여러 reader가 동시에 접근해도 되기 때문에 mutex를 걸지 않는다.

마지막에 빠져나오는 reader가 mutexW를 해제한다.

읽기 동작 전후로 mutexW를 관리해 writer와 충돌이 생기지 않도록 했다. 동시에 nReader 값도 동시에 접근하면 안 되기 때문에 mutexR 안에서 처리한다.

void Writer() {
    P(mutexW);
    /* Enter critical section */
    
    Write something;
    
    /* Exit critical section */
    V(mutexW);
}

writer는 항상 mutual exclusion을 만족해야 한다. 따라서 mutexW를 이용해 한 번에 하나씩 접근하도록 한다.

Sleeping barber

이발사 한 명, 이발 의자 하나, 대기 고객을 위한 의자 N개가 있다.

손님이 없으면 이발사는 잠든다.
손님은 도착해서
- 이발사가 자고 있으면 깨운다.
- 이발사가 일하고 있으면 대기석에 앉아 기다린다.
- 대기석이 꽉 차면 미용실을 떠난다.
이발사는 이발이 끝나면 다음 손님이 있는지 확인한다.
- 대기 손님이 없으면 잠든다.

잠자는 이발사 문제라고 불리며, mutual exclusion과 synchronization 문제로 정의할 수 있다.

손님은 이발사가 자고 있으면 깨운다. (synchronization)
이발사는 이발이 끝나면 다음 손님을 이발한다. (synchronization)
이발사가 일하고 있으면 손님은 대기한다. (mutual exclusion)

이발사가 잠드는 동작과 손님이 대기하는 동작은 queue에서 wait 하는 상태로 생각할 수 있다. 따라서 모든 조건을 semaphore로 해결할 수 있다.

int barberReady = 0; // binary semaphore
int custReady = 0; // counting semaphore
int mutexFreeSeat = 1; // binary semaphore
int nFreeSeat = N;

barberReady와 custReady는 barber-customer 간 synchronization을 위한 semaphore다. mutexFreeSeat는 nFreeSeat의 mutual exclusion을 위한 semaphore다.

void Barber() {
    while(true) {
        P(custReady);
        
        P(mutexFreeSeat);
        /* Enter critical section */
        nFreeSeat++;
        V(barberReady);
        /* Exit critical section */
        V(mutexFreeSeat);
        
        // Haircut
    }
}

이발사는 먼저 custReady를 확인하고 잘지 말지 결정한다. 대기 손님이 있다면 custReady에서 1을 뺀다.

mutexFreeSeat을 잡고 nFreeSeat를 변경한다. 대기 중인 손님이 있다면 wakeup 한다.

void Customer{
    P(mutexFreeSeat);
    /* Enter critical section */
    if (nFreeSeat > 0) {
        nFreeSeat--;
        V(custReady);
        /* Exit critical section */
        V(mutexFreeSeat);
        
        P(barberReady);
    } else {
        /* OR Exit here */
        V(mutexFreeSeat);
    }
}

남은 자리가 있다면 손님은 대기석에 앉고, custReady를 통해 이발사를 깨운다.

P(barberReady)를 통해 이발사가 준비될 때까지 기다린다. 정확히는 이발사가 nFreeSeat을 변경할 때까지 기다린다. 이발사가 준비되면 V를 통해 깨워준다.

남은 자리가 없다면 mutex만 반납하고 아무 동작 없이 끝낸다.

다양한 예제를 통해 semaphore로 mutual exclusion과 synchronization 문제를 해결하는 과정을 살펴보았다.

저작자표시 비영리 동일조건