[운영체제] 세마포어(Semaphore)

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

세마포어(Semaphore)는 여러 프로세스(혹은 스레드)가 공유자원을 사용할 때 생기는 임계구역 문제를 해결하기 위한 방법 중 하나이다. 앞서서 가장 간단한 Mutex Lock 기법을 보았는데, 여기서 좀 더 나아가서 다수의 프로세스들을 임계구역에 접근시킬 수 있는 기법이다.

Concept

세마포어는 기본적으로 그냥 정수이다. 그리고 이 정수가 의미하는 것은 임계구역에 접근이 가능한 프로세스의 개수 이다. 만약 어떤 공용화장실이 있고, 해당 화잘실에는 N개의 칸이 있다고 했을때, 이 N개의 해당하는 것이 세마포인 것이다.

세마포어가 값을 어떻게 가지는지에 따라서 우리는 Counting Semaphore 와 Binary Semaphore로 구분하는데, Counting Semaphore 는 semaphore의 값이 2 이상인, 즉 한번에 접근 가능한 프로세스가 다수인 경우를 의미하고, Binary Semaphore는 한번에 접근 가능한 프로세스가 하나뿐인 경우를 의미한다.

signal() - 임계구역에 빈자리 생겼어!

뮤텍스와 마찬가지로 세마포어 역시 임계구역의 진입과 탈출을 기준으로 모든 프로세스들에게 임계구역의 상태를 알리게된다. Signal 연산은 공용변수인 Semaphore 값을 하나 늘린다. 작업이 끝났으니 빈자리가 하나 생겼음을 알리는 것이다. 자세한 구현은 뒤에서 알아보자.

wait() - 임계구역에 자리 없으면 기다릴게!

wait 연산은 Semaphore 값을 하나 줄이는 작업을 한다. 만약 임계구역에 정해진 숫자만큼의 프로세스가 모두 들어가있다면 Semaphore의 값은 0 이 될 것이다. 이때 임계구역 진입을 요구하는 프로세스가 나타나게 되면 값이 하나 더 줄어들어서 -1 이 될텐테 잘생각해보면 결국 음수 값은 몇개의 프로세스가 임계구역 진입을 위해 대기하고 있는지 표시하게된다.

큐를 이용한 Semaphore 구현

뮤텍스에서 문제가 되었던 부분은 aquire 연산이 수행되는 과정에서 생기는 Busy Waiting 이었다. 하지만 임계구역 진입을 위해서 프로세스가 대기를 하긴 해야하는데, 항상 Busy Waiting 을 사용해야할까? 세마포어 접근법에서는 임계구역의 진입을 대기하는 프로세스를 반복문으로 대기시키지 않고 별도의 대기 큐를 만들어서 관리한다.

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();            // 프로세스 대기상태로 만들기
    }
}

wait 연산은 세마포어가 가진 값을 하나 줄인다. 이때 세마포어의 값이 음수가 된다면, 해당 프로세스가 임계구역으로 진입할 자리가 없다는 것을 의미한다. 따라서 이 프로세스를 세마포어의 큐에 넣고 block() 명령을 통해서 프로세스의 상태를 대기(waiting) 상태로 만든다. 이제 이 프로세스는 누군가가 자신의 상태를 준비(ready) 상태로 만들 때까지 리스트에서 대기한다.

wait() 연산은 프로세스가 임계구역 진입을 요청하는 연산이기 때문에 임계구역의 앞에서 실행이되어야 할 것이다.

signal

signal(semaphore *S) {
    S -> value++;            // 세마포어 값 올리기
    if (S -> value <= 0){    // 음수이거나 0이면 대기중인 프로세스가 있다는 것
        remove a process P from S -> list; // 대기 큐에서 꺼내서
        wakeup(P);          // 깨운다
    }
}

signal 연산은 세마포어가 가진 값을 하나 증가시킨다. 개인적으로 value <= 0 이 부분이 이해가 잘 안되었는데, 하나의 프로세스가 끝나고 임계구역에 빈자리가 생겼음을 요청했을 때, 세마포어의 값이 음수이거나 0이라면 대기 큐에서 대기중인 프로세스가 있다는 것을 의미한다. 따라서 대기 큐에서 프로세스를 꺼내서 wakeup() 명령을 수행한다. 프로세스를 깨우게 되면 해당 프로세스의 상태는 대기(waiting) 에서 준비(ready)로 변경되고, 운영체제의 준비 큐로 이동해서 스케줄링을 기다리게 된다.

signal() 연산은 프로세스가 임계구역을 빠져나오면서 대기중인 프로세스에게 임계구역 진입을 신호하는 것이기 때문에 임계구역 뒤에서 실행되어야 할 것이다.

Atomic Operation

세마포어에서 가장 중요한 것은 wait() 과 signal() 연산이 Atomic한 연산이 되어야 한다는 것이다. Atomic 한 연산이라는 것은 이 연산이 쪼개어지지 않고 한번 실행되면 무조건 다른 명령의 간섭없이 종료까지 실행된다는 것이다.

Atomic한 연산이 되어야하는 이유는 wait 의 value가 감소되고 있는 중에 context switch 가 발생하게되면, 세마포어를 사용하는 것에 아무의미가 없어지기 때문이다. 그런데 위에서 구현된 내용을 보면 wait() 과 signal() 은 atomic하지 않고 몇단계에 걸쳐서 연산을 수행한다.

따라서 우리는 이 연산들이 atomic한 성격을 가지도록 해야하는데, 만약 세마포어를 사용하는 시스템이 single CPU 시스템이라면 단순하게 interrupt 를 disable 하는 방식으로 context switch 의 발생을 막을 수 있다. 하지만 다수의 프로세스가 동시에 동작하는 SMP(Symmetric Multi-Programming) 시스템에서 context switch 를 중단시키는 것은 실행중인 다수의 프로세스에게 부정적인 영향으로 작용한다.

대안으로 test-and-set 이나 compare-and-swap 으로 세마포어의 연산의 앞뒤를 lock해주는 방법을 사용할 수 있다. 단점으로 지적되던 busy waiting 이 발생하긴 하겠지만, 프로세스를 대기시키기 위해 사용하지 않고 연산을 수행하는 동안에만 lock 하기 때문에 시스템에 큰 무리가 되지는 않을 것이다.