[운영체제 공룡책] Mutex Locks, Semaphores

Posted: 2025.06.27 Updated: 2025.06.27

운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.

동기화 도구들

Mutex Locks

임계구역을 보호하고 경쟁 조건을 방치하기 위해 사용한다.
프로세스가 임계구역에 들어가기 전에 반드시 락을 획득해야 하고 임계구역을 빠져나올 때 락을 반환해야 한다.

acquire() 함수로 락을 획득하고 release() 함수로 락을 반환한다.
available 변수로 락의 가용 여부를 표시한다.

락이 가용할 때 acquire() 호출이 성공해 락이 사용 불가 상태가 된다.
사용 불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄된다.

acquire() 혹은 release() 함수 호출은 원자적으로 수행해야 한다.
따라서 CAS를 사용하여 구현할 수 있다.

while (true) {
    acquire lock
        critical section
    release lock
        remainder section
}

acquire() {
    while (!available)
        ; /* busy wait */
    available = false;
}

release() {
    available = true;
}

이러한 방식에서는 프로세스가 임계구역에 있는 동안 임계구역에 들어가기 원하는 다른 프로세스는 acquire() 함수를 호출하는 반복문을 계속 실행하는 바쁜 대기(busy waiting)를 해야 한다.
계속된 루프를 실행하면 실제 다중 프로그래밍 시스템에서 문제가 될 수 있다.

락을 사용할 수 있을 때까지 프로세스가 회전하므로 스핀락(spinlock)이라고도 한다.
문맥 교환에 시간이 많이 소요될 때 문맥 교환이 필요하지 않다는 장점이 있다.
잠깐동안 락을 유지해야 하는 경우 사용할 수 있다.

세마포(Semaphores)

표준 원자적 연산 wait()과 signal()로만 접근할 수 있는 세마포 S 정수 변수를 사용한다.
한 스레드가 세마포 값을 변경할 때, 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다.

wait() {
    while (S <= 0)
        ; // busy wait
    S--;
}

signal(S) {
    S++;
}

세마포 사용법

카운팅(counting)과 이진(binary) 세마포를 구분한다.

이진 세마포의 값은 0과 1의 값만 가능하며, mutex 락과 유사하게 동작한다.

카운팅 세마포의 값은 제한 없는 영역(domain)을 갖는다.
유한한 개수를 가진 자원에 대한 접근을 제어할 때 사용될 수 있다.
각 자원을 사용하려는 프로세스에 wait() 연산을 수행하고, 세마포의 값을 감소시킨다.
프로세스가 자원을 방출할 때 signal() 연산을 수행하고, 세마포의 값을 증가시킨다.
세마포 값이 0이 되면 모든 자원이 사용중이므로 이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄된다.

세마포 구현

mutex 락과 다르게 busy waiting을 하지 않도록 구현하기 위해 wait(), signal() 연산의 정의를 수정할 수 있다.

프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닐 때, 프로세스가 자신을 일시 중지 시킨다.
이때, 프로세스를 세마포에 연관된 대기 큐에 넣고 프로세스의 상태를 대기 상태로 전환하는 일시 중지 연산이 수행된다.
제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위해 선택한다.

세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야한다.
프로세스의 상태를 대기 상태에서 준비 완료 상태로 변경해주는 wakeup() 연산으로 재시작할 수 있다.
그리고 프로세스는 준비 완료 큐에 넣어진다.

typedef struct {
    int value;
    struct process *list;
} semaphore

프로세스가 세마포를 기다려야 할 때, 이 프로세스를 세마포의 프로세스 리스트에 추가한다.
signal() 연산으로 프로세스 리스트에서 한 프로세스를 꺼내 깨워준다.

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

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

sleep() 연산은 자기를 호출한 프로세스를 일시 중지시킨다.
wakeup(P) 연산은 일시중지된 프로세스 P의 실행을 재개시킨다.
이 두 연산은 운영체제 기본 시스템콜로 제공된다.

wait() 연산과 signal() 연산을 두 프로세스가 동시에 실행할 수 없도록 보장해야 한다.
단일 처리기 환경에서는 wait() 연산, signal() 연산 실행 중에 인터럽트를 금지하여 해결할 수 있다.
다중 코어 환경에서는 모든 처리 코어에서 인터럽트를 금지해야 하지만, 모든 코어에서 인터럽트를 금지하는 건 어려우며 성능이 심각하게 감소된다.
따라서 compare_and_swap() 또는 스핀락과 같은 기법을 제공해야 한다.

현재 wait() 연산과 signal() 연산은 busy waiting을 완전히 제거하지 못했으며, busy waiting을 진입 코드에서 임계구역으로 이동시켰다.
따라서 임계구역은 거의 항상 비어있고, busy waiting은 드물게 발생하며, 시간이 아주 짧다.

Better Jeong