OS ch06. Process Synchronization

김민성·2026년 5월 1일
OS

운영체제(OS) 

목록 보기
6/6
post-thumbnail

운영체제에서는 여러 프로세스나 스레드가 동시에 실행될 수 있다. 이때 여러 프로세스가 같은 공유 데이터에 접근하면 실행 순서에 따라 결과가 달라질 수 있다. 즉 이번 장에서는 프로세스 동기화에 대해 다룬다.

Background

공유 데이터에 여러 프로세스가 동시에 접근하면, 데이터 일관성 문제가 발생한다. 대표적인 예시가 producer-consumer problem이다. producer-consumer 문제에서 producer는 버퍼에 데이터를 넣고, consumer는 버퍼에서 데이터를 꺼낸다. 이때 두 프로세스는 buffer라는 공유데이터와 count라는 공유변수를 함께 사용한다. count는 현재 버퍼에 들어있는 데이터 개수를 나타내는 변수이다.

Producer 코드

while (true) {
    /* produce an item and put in nextProduced */

    while (count == BUFFER_SIZE); // do nothing

    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    count++;
}
  • while (count == BUFFER_SIZE); - 버퍼가 가득 차 있으면 아무것도 안하고 기다린다.
  • buffer[in] = nextProduced; - 생산한 데이터를 buffer[in] 위치에 넣는다.
  • in = (in + 1) % BUFFER_SIZE - % BUFFER_SIZE를 쓰는 이유는 버퍼를 원형 버퍼처럼 사용하기 위해서다.
  • count++ - 버퍼 안에 들어 있는 데이터 개수를 1 증가시킨다.

Consumer 코드

while (1) {
    while (count == 0)
        ; // do nothing

    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count--;

    /* consume the item in nextConsumed */
}
  • while (count == 0); — 버퍼가 비어 있으면 아무것도 안하고 기다린다.
  • count-- — 버퍼 안의 데이터 개수를 1 감소시킨다.

즉 producer는 count++를, consumer는 count--를 수행하며 두 프로세스가 같은 공유 변수를 서로 다른 방향으로 동시에 수정할 수 있다.

Race Condition

고수준 언어에서 count++와 count--는 겉으로는 한 줄이지만 실제 기계어(assembly언어) 수준에서 CPU는 3단계 명령어로 쪼개져서 실행된다.

// count++
register1 = count;
register1 = register1 + 1;
count = register1;

// count--
register2 = count;
register2 = register2 - 1;
count = register2;

아래의 상황은 producer와 consumer가 각각 자기 레지스터에 계산한 결과를 count에 저장하는 상황이다.
count = 5인 초기 상태에서 실행 순서가 다음처럼 섞일 수 있다.

S0: producer  register1 = count        → register1 = 5
S1: producer  register1 = register1+1  → register1 = 6
S2: consumer  register2 = count        → register2 = 5
S3: consumer  register2 = register2-1  → register2 = 4
S4: producer  count = register1        → count = 6
S5: consumer  count = register2        → count = 4

생산자는 하나를 추가했고 소비자는 하나를 제거했으니 결과는 5여야 하지만, 실제 결과는 4다.
producer가 count=5를 읽은 뒤 count에 6을 쓰기 전에 consumer도 count=5를 읽어버려서 이후에 producer가 6 써봤자 그걸 모르는 consumer가 4로 덮어써버리는 것이다.

이처럼 여러 프로세스가 공유 데이터에 동시에 접근하고 실행 순서에 따라 결과가 달라지는 상황을 Race Condition이라고 한다.

Critical-Section Problem

각 프로세스의 일반적인 구조는 이렇다.

do {
    entry section
    critical section
    exit section
    remainder section
} while (1);
  • critical section(임계구역) — 여러 프로세스/스레드들이 공유변수나 공유데이터에 접근해 그 값을 수정하는 작업이 이뤄지는 코드구간. count++, count--처럼 공유 변수를 수정하므로 여러 프로세스가 동시에 실행하면 안 된다.
  • entry section(진입구역) — 임계구역에 들어갈 때 거치는 관문으로, 어느 한 순간에는 오직 하나의 프로세스만 임계구역에 들어갈 수 있도록 조건을 체크하고 진입 자격을 획득하는 역할을 한다. 통과하지 못한 프로세스는 이 진입구역에서 대기하게 된다.
  • exit section(탈출구역) — 임계구역에서 작업을 마치고 빠져나올 때 거치는 구역으로, 진입구역에서 대기하고 있던 다른 프로세스들이 임계구역에 들어갈 수 있도록 진입 차단 조건을 해제해주는 역할을 한다.
  • remainder section — 공유 데이터와 관련 없는 나머지 코드. 여러 프로세스가 동시에 실행해도 문제없다.

그림으로 표현하면 아래와 같다. 빨간색이 entry section, 파란색이 exit section, 저 실선 네모가 critical section이라고 이해하면 된다.

즉 critical section problem이란 여러 프로세스/스레드들이 동시에 critical section에 진입해 공유 데이터를 수정할 때 데이터 일관성이 깨지는 동기화 문제라고 할 수 있다.

세 가지 조건

임계구역 문제를 올바르게 해결하려면 다음 세 조건을 만족해야 한다.

1) Mutual Exclusion (상호 배제) — Pi가 critical section에서 실행 중이면, 다른 프로세스는 자신의 critical section에 들어갈 수 없어야 한다. 즉 한 번에 하나의 프로세스만 공유 데이터에 접근해야 한다.

2) Progress (진행) — critical section에 아무 프로세스도 없고 들어가고 싶은 프로세스들이 있다면, 다음에 누가 들어갈지 결정하는 과정이 무한히 미뤄지면 안 된다. 즉 들어가고자 하는 놈이 있다면 반드시 누군가는 들어가야 한다.

3) Bounded Waiting (한정 대기) — 어떤 프로세스가 요청한 뒤, 허용되기 전에 다른 프로세스들이 critical section에 들어가는 횟수에는 제한이 있어야 한다. starvation을 방지한다. 즉 정해진 횟수만큼 기다리면 내 차례가 된다는게 보장이 된다.

기본 가정으로, 각 프로세스는 0이 아닌 속도로 실행되고 프로세스들 사이의 상대적인 속도는 가정하지 않는다. 어떤 프로세스가 빠르고 느린지 알 수 없어도 알고리즘은 올바르게 동작해야 한다.

Peterson's Solution

두 개의 프로세스 사이에서만 적용할 수 있는 대표적인 동기화 해결책이다. 두 가지 변수 turn과 flag를 사용해 경합을 해결하며, LOAD와 STORE 명령은 atomic하다고 가정한다.

atomic: 더 이상 쪼개지지 않는, 즉 중간에 인터럽트될 수 없음을 말한다.

두 가지 공유 변수를 사용한다.

int turn;        // 누구 차례인지
Boolean flag[2]; // 누가 들어갈 준비가 됐는지
// Pi
do {
    flag[i] = TRUE;
    turn = j;
    while (flag[j] && turn == j)
        ;
    CRITICAL SECTION
    flag[i] = FALSE;
    REMAINDER SECTION
} while (TRUE);

// Pj
do {
    flag[j] = TRUE;
    turn = i;
    while (flag[i] && turn == i)
        ;
    CRITICAL SECTION
    flag[j] = FALSE;
    REMAINDER SECTION
} while (TRUE);

Pi와 Pj의 코드는 대칭적이므로 Pi 코드만 보고 흐름을 파악해보면 아래와 같다.

Pi 프로세스가 critical section에 들어가고 싶다면 자신의 flag를 true로 설정한 뒤, 진입 차례는 Pj에게 먼저 양보한다. 만약 Pj도 들어갈 준비가 돼있고 Pj의 차례라면 Pi는 while문에 걸려 대기하게 된다.

Pi가 critical section에서 작업을 마치고 나올 때 자신의 flag를 false로 바꾸고, 이로 인해 대기하고 있떤 Pj의 while문 조건이 깨지면서 Pj가 진입하게 되는 구조이다.

세 가지 조건을 만족하는가

프로세스가 단 2개만 존재하는 상황에서는 3가지 조건 모두 완벽히 만족된다. 특히 3번 조건인 bounded waiting의 경우 프로세스가 2개뿐이면 한 프로세스가 경합에서 이겨 먼저 들어갔다 나오면, 대기 중이던 다른 프로세스에게 곧바로 진입 기회가 주어진다. 반면 뒤에서 학습할 TestAndSet이나 Swap 같은 하드웨어 명령어를 사용하는 동기화 기법에서도 프로세스가 2개일 때는 3번 조건이 만족되지만, 프로세스가 3개 이상으로 늘어날 경우 특정 프로세스만 계속 진입하는 일이 일어날 수도 있다.

Bakery Algorithm

Peterson's Solution은 2개의 프로세스에 대한 해결책이다. 그 한계를 넘어 n개의 다중 프로세스 환경에서 critical section 문제를 해결하기 위해 고안된 알고리즘이 Bakery Algorithm이다. 빵집에서 손님들이 번호표를 뽑고 기다리면 번호표 숫자가 가장 작은 사람부터 서비스를 받는 일상적인 방식에서 착안한 해결책이다.

  • critical section에 들어가고 싶은 프로세스는 먼저 번호표를 발급받는다.
  • 가장 작은 번호를 가진 프로세스가 먼저 들어간다.
  • 여러 프로세스가 동시에 번호표를 발급받다보면 찰나의 순간에 같은 번호표 값을 부여받는 상황이 생길수도 있으므로, 이럴땐 PID로 비교한다. PID 값이 작은 놈이 우선이다. (번호표 먼저 비교, 번호표 같으면 PID로 비교)

이때 critical section에 진입하려는 프로세스는 현재까지 다른 프로세스들에게 발급된 번호표 중 가장 큰 값(max)을 찾아, max+1 의 값을 자신의 번호표 값으로 발급받는다.

두 가지 공유 변수를 사용한다.

boolean choosing[n];  // 프로세스가 현재 번호표를 발급받고 있는 상황인지
int number[n];        // 번호표 값

// choosing의 초기값은 false, 번호표 값의 초기값은 0이다.

Pi입장에서 코드 로직을 살펴보면 아래와 같다.

do {
    choosing[i] = true;

    number[i] = max(number[0], number[1], ..., number[n-1]) + 1;

    choosing[i] = false;

    for (j = 0; j < n; j++) {

        while (choosing[j])
            ; // then do nothing

        while ((number[j] != 0) &&
               (number[j], j) < (number[i], i))
            ; // then do nothing
    }

    // critical section

    number[i] = 0;

    // remainder section

} while (1);

Pi가 critical section에 들어가려면 먼저 자신의 choosing 값을 true로 바꿔 번호표를 뽑는 중임을 알린다. 가장 높은 번호표 값에 +1을 해서 할당받은 뒤 choosing 값을 false로 되돌린다.

이후 Pi는 다른 모든 프로세스들과 자신의 순서를 순차적으로 비교한다. 만약 다른 프로세스가 번호표를 뽑는 중이라면 대기하고, 다른 프로세스가 자신보다 더 작은 번호표를 가졌거나 번호표가 같더라도 더 작은 PID를 갖고있다면, 그 우선순위가 높은 프로세스가 작업을 마칠때까지 while문에 걸려 대기하게 된다.

마침내 자신의 차례가 되어 작업을 무사히 마친 Pi는 빠져나오면서 자신의 번호표 값을 다시 0으로 초기화한다. 번호표 값이 0이라는 것은 현재 critical section에 진입할 의사가 없음을 의미하므로, 이를 통해 대기 중이던 다음 순번의 프로세스들이 빗장을 풀고 진입할 수 있게 된다.

Synchronization Hardware

소프트웨어 알고리즘 외에도 하드웨어 수준에서 동기화를 지원하는 방법이 있다.

Uniprocessor 환경

단일프로세서 환경에서는 프로세스가 critical section에 들어갈 때 단순히 시스템의 인터럽트를 꺼버리는 방식으로 동기화 문제를 해결한다. CPU가 하나일 때 인터럽트 발생을 막아버리면, 현재 critical section에 들어간 프로세스가 스스로 빠져나올 때까지는 다른 프로세스에게 CPU 제어권이 절대 넘어가지 않기 때문이다.

Multiprocessor 환경

멀티프로세서 환경에서 여러 CPU가 각각 서로 다른 프로세스들을 병렬로 처리하다보면, 여기저기서 빈번히 critical section 진입을 시도할텐데 이때마다 전체 시스템의 인터럽트를 껐다 켰다 반복하는 것은 시스템의 자원을 낭비하는 비효율적인 방법이며, 나아가 시스템의 확장성에도 큰 문제가 발생한다.

이러한 문제를 방지하기 위해 멀티프로세서 환경에서는 무식하게 인터럽트를 끄는 대신, 중간에 끊기지 않고 한번에 실행됨이 보장되는 Atomic 하드웨어 명령어인 TestAndSet이나 Swap 같은 인스트럭션을 사용한다. 이를 이용해 특정 순간에 하나의 프로세스만 자물쇠(lock)를 획득해 critical section에 진입하게 만든다.

TestAndSet

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

target의 현재 값을 저장하고, target을 TRUE로 바꾸고, 원래 값을 반환한다. 이 전체 과정이 atomic하게 실행된다.

boolean lock = false;

do {
    while (TestAndSet(&lock))
        ;           // 반환값이 true면 이미 lock 잡힘 → 대기

    // critical section

    lock = FALSE;

    // remainder section
} while (TRUE);

반환값이 false이면 lock을 잡는 데 성공한 것이므로 while문을 빠져나와 critical section에 들어간다. 기다리는 동안 while문을 계속 도는 것을 busy waiting 또는 spinlock이라고 한다. 구현이 단순하고 critical section이 매우 짧으면 빠르지만, 기다리는 동안 CPU를 낭비한다는 단점이 있다. 또한 mutual exclusion은 만족하지만 bounded waiting은 보장하지 못할 수 있다.

Swap

void Swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}
boolean lock = false;
boolean key;

do {
    key = TRUE;
    while (key == TRUE)
        Swap(&lock, &key);

    // critical section

    lock = FALSE;

    // remainder section
} while (TRUE);

첫 번째 프로세스가 Swap을 실행하면 lock = true, key = false가 된다. key가 false이므로 while문을 빠져나와 critical section에 들어간다. 다른 프로세스가 시도하면 이미 lock = true이므로 Swap 후에도 key가 true로 남아 계속 기다린다. critical section을 끝낸 프로세스가 lock = FALSE를 수행하면 다음 프로세스가 들어갈 수 있다.

Semaphores

앞서 살펴봤듯 소프트웨어 알고리즘과 하드웨어 명령은 busy waiting을 유발할 수 있다. 이 문제점을 개선해 busy waiting이 필요없는 추상화된 동기화 도구가 Semaphore다.

Semaphore S는 정수 변수이고, wait()과 Signal() 이 두 가지 atomic 연산으로만 접근할 수 있다. 예전에는 각각 P(), V()라고 불렀다.

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

signal(S) {        
    S++;
}

wait(S)는 critical section 진입 전 entry section에서 조건을 확인하는데 사용한다. S가 0 이하면 대기하고, 0보다 크면 값을 1 감소시킨 뒤 critical section에 진입한다.

signal(S)는 exit section에서 호출되며, 세마포어 값을 1 증가시켜 대기 중이던 다른 프로세스가 진입할 수 있는 환경을 만들어준다.

semaphore 종류

  • Counting semaphore- 값의 범위에 제한이 없어 계속 증가하거나 감소할 수 있는 정수형 변수로, 여러 개의 자원을 관리할 때 사용된다. 자원이 5개면 S = 5로 둘 수 있다.
  • Binary semaphore- 0과 1 두가지 값만 가질 수 있으며, 상호 배제를 달성하기 위한 mutex lock으로도 불린다.

아래 예시를 살펴보자.

Semaphore S = 1;

wait(S);
Critical Section
signal(S);

세마포어의 초기값을 1로 설정하고, 프로세스가 critical section에 들어가기 전 wait를 통해 값을 0으로 만들어 다른 프로세스의 접근을 막는다. 작업이 끝난 후에는 signal을 호출해 다시 값을 1로 변경해 다른 프로세스가 들어올 수 있도록 한다.

또한 아래 그림처럼 세마포어를 통해 특정 프로세스의 작업이 항상 다른 프로세스보다 먼저 실행되도록 순서를 지정할 수 있다. 세마포어 초기값을 0으로 설정한 뒤, 먼저 실행해야 하는 작업 뒤에 signal 연산을 두고 나중에 실행할 작업 앞에 wait연산을 배치해 구현한다.

Semaphore 구현 자체도 동기화가 필요하다

wait()와 signal()도 공유 변수 S를 수정하므로 두 프로세스가 동시에 같은 semaphore에 접근하면 안 된다. 즉 두 프로세스가 같은 semaphore에 대해 wait()과 signal()을 동시에 실행하지 못하도록 보장해야한다. 이때 단일 CPU에서는 interrupt를 disable하여 보호하고, 다중 CPU에서는 spinlock을 사용한다.

spinlock은 일종의 busy waiting으로, busy waiting 방식은 구현이 쉽고 간단하며, 기다려야하는 시간이 매우 짧은 경우 바로 진입할 수 있어 유용하다.

하지만 critical section에서 수행해야할 작업이 많아 다른 프로세스가 오랜시간 그 안에 머물게 되면, 밖에서 기다리는 프로세스는 아무 의미없이 조건만 확인하며 CPU자원을 낭비하게 되므로 비효율적이다. 따라서 대기시간이 길어질 것으로 예상되는 경우에는 busy waiting 방식을 피하고, 프로세스를 중지(block)시켜 semaphore의 waiting queue에 넣은 뒤 나중에 깨워주는(wake up) context switching 방식 사용이 권장된다.

Busy Waiting 없는 Semaphore 구현

각 semaphore마다 waiting queue를 연결해서, 자원이 없으면 프로세스를 block시키고 자원이 생기면 wakeup시키는 방식이다.

  • block: wait연산 시 critical section에 들어갈 수 없으면, 해당 프로세스를 중지시키고 semaphore의 waiting queue에 집어넣고 대기시킴
  • wakeup: critical section을 빠져나온 프로세스가 signal연산을 호출하면, waiting queue에 있던 프로세스를 깨워서 ready queue로 보내 다시 CPU를 할당받을 수 있게 함

waiting queue의 각 항목은 다음 두가지 데이터를 가진다.

  • value: semaphore 변수값
  • pointer to next record in the list: 다음 프로세스가 어딨는지 나타내는 포인터. linked list 자료구조 생각하면 이해하기 편할것같다.
wait(S) {
    value--;
    if (value < 0) {
        add this process to waiting queue;
        block();
    }
}
  1. 먼저 semaphore의 value값을 1 감소시킨다.
  2. 감소시킨 값이 0보다 작다면, 남은 자원이 없다는 뜻이므로 해당 프로세스를 waiting queue에 넣고 block시킨다.
  3. 값이 0 이상이라면 block 되지 않고 바로 critical section에 진입한다.
signal(S) {
    value++;
    if (value <= 0) {
        remove a process P from the waiting queue;
        wakeup(P);
    }
}
  1. critical section에서 작업을 마치면 semaphore의 value값을 1 증가시킨다.
  2. 증가시킨 값이 0 이하라면, 여전히 waiting queue에서 기다리고 있는 프로세스가 존재한다는 뜻이다.
  3. 이때는 waiting queue에서 대기 중인 프로세스 하나를 빼낸 뒤, wakeup 연산을 통해 critical section에 들어갈 수 있는 환경을 만들어준다.

아래 시나리오를 통해 살펴보자.
초기값 S=1

  1. P1의 진입 시도(wait): 가장 먼저 P1이 wait(S) 연산을 실행한다. 초기값 S=1에서 1을 감소시켜 S=0이 되고, 값이 0보다 작지 않으므로 P1은 무사히 critical section에 진입하며, 이때 waiting queue는 비어있다.

  2. P2의 진입 시도(wait) 및 block: P1이 critical section에 있는동안 P2가 이어서 wait(S)를 실행한다. S값을 1감소시켜 -1이 되고, 값이 음수가 되었으므로 P2는 critical section에 들어가지 못하고 waiting queue에 집어넣어지며 block 상태가 된다. (현재 큐 상태: [P2])

  3. P3의 진입 시도(wait) 및 block: 연이어 P3가 wait(s)를 실행해 S값은 -2로 감소하고, P3 역시 값이 0보다 작으므로 진입하지 못하고 waiting queue에 들어가 P2 뒤에 줄을 서게 된다. (현재 큐 상태: [P2,P3])

  4. P1의 탈출(signal) 및 P2의 wakeup: 작업을 마친 P1이 critical section을 빠져나오며 signal(S)를 실행한다. 이로 인해 S값은 하나 증가해 -1이 되고, 증가된 값이 여전히 음수이므로 waiting queue에 기다리는 프로세스가 있다는 뜻이며 queue의 가장 맨 앞에 있던 P2를 꺼내 wakeup시킨다. 깨어난 P2는 critical section에 진입할 수 있게 된다. (현재 큐 상태: [P3])

  5. P4의 진입 시도(wait) 및 block: P2가 critical section에서 작업하는 도중, 새로운 프로세스 P4가 wait(S)을 실행한다. S값은 -1에서 -2로 감소하고, P4 역시 block되어 waiting queue에 쌓이게 된다. (현재 큐 상태: [P3,P4])

  6. P2의 탈출(signal) 및 P3의 wakeup: P2가 작업을 마치고 나오며 signal(s)를 실행해 S값을 -1로 증가시킨다. 마찬가지로 waiting queue에서 가장 먼저 기다리고 있던 P3를 깨워 critical section에 진입하게 만들어준다. (현재 큐 상태: [P4])

  7. P3의 탈출(signal) 및 P4의 wakeup: P3가 작업을 마치고 signal(S)를 실행하면 S값은 0이 된다. 마지막으로 waiting queue에 남아있던 P4가 빠져나와 critical section에 들어가게 되며, 이때 waiting queue는 다시 텅 빈 상태가 된다.

Deadlock과 Starvation

Semaphore를 잘못 사용하면 문제가 생긴다.

Deadlock: 두 프로세스가 서로가 가진 자원을 기다리면서 영원히 서로를 기다리기만 하는 상황이다.

두 개의 semaphore 변수 S,Q(초기값 1) 가 있을때, 프로세스 P0가 wait(S)를 통해 S를 선점하고, 동시에 프로세스 P1이 wait(S)를 요청하면, 이미 값이 0이 되어있기 때문에 두 프로세스 모두 더이상 진도를 나가지 못하고 block된다. lock을 풀어줄 수 있는 signal 연산은 코드 아래쪽에 있지만, 둘다 도달하지 못해 영원히 갇히게 된다.

Starvation: 프로세스가 실행에 필요한 자원이나 CPU를 영원히 할당받지 못해 굶어죽는 현상이다.

프로세스가 deadlock에 빠지게 되면, 조건을 만족시킬 방법이 없으므로 semaphore의 waiting queue에서 끝없이 대기해야만 하는 starvation이 발생한다.

Classic Problems of Synchronization

대표적인 동기화 문제는 세 가지다.

  • Bounded-Buffer Problem — 크기가 제한된 버퍼를 두고 producer와 consumer가 함께 사용하는 문제
  • Readers and Writers Problem — reader는 여러 명이 동시에 접근해도 되지만, writer는 독점 접근이 필요한 문제
  • Dining-Philosophers Problem — 원형 테이블에 앉은 철학자들이 포크를 공유하며 식사하는 문제. deadlock과 starvation 설명에 자주 사용된다.

Bounded-Buffer Problem

버퍼가 N개 있을 때 producer와 consumer가 함께 사용하는 문제다. 세 개의 semaphore를 사용한다.

Semaphore mutex = 1;  // 버퍼 상호 배제
Semaphore full = 0;   // 데이터가 들어 있는 버퍼 칸 수
Semaphore empty = N;  // 비어 있는 버퍼 칸 수

Producer

do {
    // produce an item

    wait(empty);    // 빈 공간 있는지 확인
    wait(mutex);    // 버퍼 접근 권한 획득

    // add the item to the buffer

    signal(mutex);  // 버퍼 접근 권한 반납
    signal(full);   // 소비 가능한 item 증가
} while (true);

Consumer

do {
    wait(full);     // 소비할 item 있는지 확인
    wait(mutex);    // 버퍼 접근 권한 획득

    // remove an item from buffer

    signal(mutex);  // 버퍼 접근 권한 반납
    signal(empty);  // 빈 공간 증가

    // consume the removed item
} while (true);

순서가 중요하다. producer는 반드시 wait(empty) 후에 wait(mutex)를 해야 한다. 버퍼가 꽉 찬 상태에서 mutex를 먼저 잡고 기다리면 consumer가 버퍼에서 데이터를 꺼낼 기회를 막는다. consumer도 마찬가지로 wait(full) 후에 wait(mutex)를 해야 한다.

n = 3일 때 producer가 연속 실행되면 이렇게 변한다.

초기:        empty=3, full=0
1번 실행 후: empty=2, full=1
2번 실행 후: empty=1, full=2
3번 실행 후: empty=0, full=3  → 이후 wait(empty)에서 대기

세 semaphore의 역할 정리:

  • empty — producer가 버퍼에 넣을 수 있는지 제어
  • full — consumer가 버퍼에서 꺼낼 수 있는지 제어
  • mutex — 버퍼 자체에 대한 동시 접근 방지

OS별 동기화 구현 (case study)

Solaris

다중 작업 환경을 지원하기 위해 다양한 lock 매커니즘을 제공한다.

  • Adaptive Mutex: 상황에 맞춰 동작을 바꾸는 기법이다. critical section 코드가 짧고 락을 가진 프로세스가 현재 실행 상태라면 대기 시간이 짧을 것으로 판단해 spinlock방식을 사용한다. 반면 실행 상태가 아니거나 단일프로세서 환경이라면 프로세스를 중지시키고 waiting queue에 넣는 방식을 사용한다.
  • Condition Variable and Readers-Writers lock: 코드가 긴 경우에는 조건 변수를 사용하거나, 읽기와 쓰기를 구분해 읽기 작업에 한해서는 여러 프로세스의 동시 접근을 허용하는 reader-writer lock을 제공한다.
  • Turnstile: 놀이공원의 회전문처럼 락을 얻기 위해 기다리는 스레드들의 순서를 정해주어 한번에 오직 하나의 프로세스만 통과하도록 제어하는 일종의 큐이다.

Windows XP

CPU의 개수에 따라 동기화 기법을 다르게 적용한다.

단일 프로세서에서는 interrupt mask를 사용해 global resource 접근을 보호한다. 멀티프로세서에서는 spinlock을 사용한다. dispatcher object를 통해 mutex, semaphore 기능을 제공하고, condition variable과 유사한 event 기능도 제공한다.

Linux

짧은 critical section은 interrupt를 disable하여 보호한다. semaphore, spin lock, kernel preemption 제어를 제공한다. spin lock은 멀티프로세서 환경에서 critical section이 짧을 때 유용하다.

Pthreads

운영체제와 독립적으로 작동하는 API로서, 기본적으로 mutex lock과 condition variable을 동기화 기법으로 제공한다. 확장 버전에서는 reader-writer lock과 busy waiting 방식의 spinlock도 추가로 제공해 상황에 맞게 사용할 수 있도록 지원한다.

profile
김민성
JUST DO IT
이전 포스트

OS ch05. CPU Scheduling

0개의 댓글