경쟁 조건이란?

운영체제는 동시에 여러 프로세스나 스레드를 실행시킨다. 그런데 이 프로세스들이 공유 데이터(shared data) 를 동시에 접근하게 된다면 문제가 발생할 수 있다. 대표적인 예가 생산자-소비자 문제 이다. 버퍼에 데이터를 넣고 빼는 과정에서 데이터의 일관성이 깨질 수 있는데, 이를 경쟁 조건(race condition) 이라고 한다.

다음 코드가 대표적인 경쟁 조건의 예시이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 생산자 코드
while (true) {
    while (count == BUFFER_SIZE);  // 버퍼가 가득 차면 대기
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    count++;
}

// 소비자 코드
while (true) {
    while (count == 0);  // 버퍼가 비었으면 대기
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count--;
}

위 코드에서 count++와 count-- 명령이 병행으로 실행되면, 예상치 못한 결과값이 발생한다.

임계구역 설정

경쟁 조건을 방지하기 위해 프로세스들이 동시에 공유 데이터에 접근하지 못하도록 제어해야 한다. 이때 공유 데이터의 영역을 임계구역(critical section) 이라고 한다.

임계구역 문제를 올바르게 해결하려면 반드시 다음 세 가지 조건이 필요하다.

• 상호 배제(Mutual Exclusion): 임계구역에는 한 번에 하나의 프로세스만 진입할 수 있어야 한다.
• 진행(Progress): 임계구역에 들어가려는 프로세스가 있다면 유한한 시간 내에 반드시 진입해야 한다.
• 한정된 대기(Bounded Waiting): 프로세스가 임계구역 진입을 무한정 기다리지 않도록 보장해야 한다.

Peterson의 해결책

고전적인 소프트웨어 기반 임계구역 문제 해결법으로 유명한 것이 바로 Peterson의 방법이다. 이 해결안은 두 개의 프로세스만을 대상으로 한다.

1
2
3
4
5
6
7
8
9

int turn;                  // 임계구역에 들어갈 순서를 정함
bool flag[2];              // 각 프로세스의 진입 의사 표시

// 프로세스 Pi의 진입구역(entry section)
flag[i] = true;            // Pi가 진입 준비 완료
turn = j;                  // 다른 프로세스가 먼저 진입 가능하도록 양보
while (flag[j] && turn == j); // 상대가 진입 준비 중이면 대기
// Critical section (임계구역)
flag[i] = false;           // 퇴출구역(exit section)

하지만 현대 컴퓨터 구조의 load와 store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson의 해결안이 이러한 구조에서 올바르게 실행된다고 보장할 수는 없다.

하드웨어적 지원을 통한 동기화

현대 운영체제는 경쟁 조건 해결을 위해 하드웨어의 도움을 받는다. 대표적인 기법들이 다음과 같다.

메모리 장벽

메모리 장벽(Memory Barrier)은 컴파일러나 프로세서가 명령어의 순서를 바꾸는 것을 막아준다. 메모리 장벽은 이를 통해 데이터의 일관성을 유지시킨다.

1
2
3
4

// 메모리 장벽을 이용한 예제
X = 100;
memory_barrier();  // 장벽
flag = true;

위 코드에서 메모리 장벽은 flag = true가 반드시 X = 100보다 늦게 실행됨을 보장한다.

하드웨어 명령어

두 가지 대표적인 원자적 연산(atomic operation)이 있다.

• Test_and_Set: 값을 검사하고 즉시 설정한다.

1
2
3
4
5

bool test_and_set(bool *target) {
    bool rv = *target;
    *target = true;
    return rv;
}

• Compare_and_Swap: 현재 값과 기대 값이 같으면 값을 바꾼다.

1
2
3
4
5
6

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

이 명령어들은 원자적으로 실행되므로, 프로세스 동기화에 매우 효과적이다.

세마포

세마포(Semaphore)는 mutex 락보다 더 범용적이며 강력한 동기화 도구다. 세마포는 두 가지 연산만으로 제어된다.

• wait() (P 연산): 세마포 값이 0 이상이면 감소시키고, 아니면 대기
• signal() (V 연산): 세마포 값을 증가시키고 대기 중인 프로세스를 깨운다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add_to_wait_queue();
        sleep();
    }
}

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        wakeup_from_wait_queue();
    }
}

세마포는 한정된 자원의 사용 제어, 생산자-소비자 문제 등 여러 상황에서 유용하게 사용된다.

모니터

모니터(Monitor)는 더 간편하게 동기화를 다룰 수 있도록 고급 언어 차원에서 제공되는 동기화 구조체이다. 오직 하나의 프로세스만이 모니터 내부에서 활동할 수 있게 보장한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

monitor ResourceAllocator {
    boolean busy = false;
    condition x;

    void acquire() {
        if (busy)
            x.wait();
        busy = true;
    }

    void release() {
        busy = false;
        x.signal();
    }
}

모니터는 조건변수(condition variable)를 통해 프로세스를 효율적으로 대기시킬 수 있다.

라이브니스 문제

동기화 과정에서 피해야 하는 라이브니스 문제 중 대표적인 두 가지는 다음과 같다.

교착 상태

교착 상태(Deadlock)는 서로의 자원을 무한정 기다리는 상태이다.

프로세스 A가 자원 X를, 프로세스 B가 자원 Y를 점유하고 있을 때, A가 Y를 기다리고 B가 X를 기다리면 둘 다 무한정 기다리게 된다.

우선순위 역전

우선순위 역전(Priority Inversion)은 높은 우선순위 프로세스가 낮은 우선순위 프로세스를 기다리는 현상이다.

낮은 우선순위 프로세스 L이 자원을 점유하고 있을 때, 높은 우선순위 프로세스 H가 자원을 요청하면 H가 L을 기다리게 된다. 그런데 이때 중간 우선순위 프로세스 M이 실행되면, L이 더 지연되어 H가 예상보다 오래 기다리는 현상이 발생한다.

이 문제를 해결하는 대표적인 방법으로는 우선순위 상속(priority inheritance) 프로토콜이 있다.