0x06. 프로세스 동기화

배경

프로세스 간 통신 방식에는 메시지 전달(Message Passing) 과 공유 메모리(Shared Memory) 가 있다. 이 중 공유 메모리 방식은 빠르지만, 여러 프로세스가 동시에 같은 데이터에 접근하면 충돌이 발생할 수 있다.

대표적인 예가 생산자-소비자 문제(Producer-Consumer Problem) 다. 생산자와 소비자가 공유 메모리를 통해 통신하는 구조에서, 공유 변수를 동시에 수정하면 예기치 않은 결과가 발생한다.

동기화 문제

핵심은 수정 연산 중에 컨텍스트 스위칭이 발생할 수 있다는 점이다.

구체적인 문제 상황을 살펴보자.

• counter의 초기값이 5라고 가정한다
• 생산자가 counter를 증가시키고, 소비자가 counter를 감소시키는 연산을 동시에 수행한다
• 이상적으로 counter는 다시 5가 되어야 하지만, 실제로는 그렇지 않을 수 있다

프로세스 동기화

경쟁 상태(Race Condition) 란, 여러 프로세스가 같은 데이터에 동시에 접근하고 조작하여 실행 순서에 따라 결과가 달라지는 상황이다. 일종의 버그라고 볼 수 있다.

동기화(Synchronization) 는 이런 경쟁 상태를 방지하기 위해 프로세스들의 실행 시점을 조율하는 것이다. 예를 들어, 한 번에 하나의 프로세스만 공유 데이터에 접근하도록 보장하는 방식이 있다.

임계 구역 문제 (The Critical-Section Problem)

임계 구역 문제(Critical Section Problem) 는 프로세스들이 협력하기 위해 사용할 프로토콜을 설계하는 문제다.

시스템에서 $n$개의 프로세스 $P_0, \dots, P_\{n-1\}$이 동시에 실행 중이고, 각 프로세스는 공유 데이터에 접근하려 한다. 이때 각 프로세스의 코드는 다음 네 가지 영역으로 구성된다.

• 임계 구역(Critical Section): 공유 자원(공통 변수, 파일 등)을 변경할 수 있는 코드 영역
• 나머지 구역(Remainder Section): 공유 자원을 변경하지 않는 코드 영역
• 진입 구역(Entry Section): 임계 구역 진입 허가를 요청하는 코드 영역
• 퇴출 구역(Exit Section): 임계 구역을 떠남을 알리는 코드 영역

임계 구역의 구조

프로세스는 임계 구역 내에서만 공유 데이터를 수정한다. 그리고 한 시점에 오직 하나의 프로세스만 자신의 임계 구역에 존재할 수 있다.

공유 데이터에 접근하는 순간부터가 임계 구역이다.

프로세스의 일반적인 구조는 다음과 같다.

임계 구역 문제의 세 가지 요구 조건

1. 상호 배제(Mutual Exclusion)

한 프로세스가 임계 구역에서 실행 중이면, 다른 프로세스는 자신의 임계 구역에서 실행할 수 없다. 다른 프로세스는 진입 구역에서 대기해야 한다.

2. 진행(Progress)

임계 구역에서 실행 중인 프로세스가 없고 일부 프로세스가 진입을 원하면, 나머지 구역에 있지 않은 프로세스만 다음 진입 결정에 참여할 수 있다. 이 결정은 무기한 연기(Indefinite Postponement) 될 수 없다. 즉, 잠금을 해제하지 않고 떠나는 상황이 없어야 한다.

3. 한정 대기(Bounded Waiting)

한 프로세스가 임계 구역 진입을 요청한 후, 그 요청이 허용되기 전까지 다른 프로세스가 임계 구역에 진입하는 횟수에 한계가 있어야 한다.

커널과 임계 구역 문제

커널(Kernel) 은 임계 구역 문제의 대표적인 사례다. 열린 파일 목록, PCB의 연결 리스트 같은 커널 데이터 구조가 공유 자원에 해당한다.

이를 처리하는 두 가지 접근 방식이 있다.

• 비선점형 커널(Non-preemptive Kernel): 커널 모드에서 실행 중인 프로세스에 대해 스위칭이 발생하지 않는다. 경쟁 상태가 원천적으로 차단된다.
  • 예: Windows 2000, Windows XP, 초기 UNIX, Linux 2.6 이전
• 선점형 커널(Preemptive Kernel): 임계 구역 문제에 대한 해결책을 함께 구현한다. 실시간 프로그래밍에 적합하고 응답성이 좋다.
  • 예: Linux 2.6 이상, Solaris, IRIX

Peterson's Solution

Peterson's Solution은 임계 구역 문제에 대한 소프트웨어 해결책이다. load/store 명령어의 재배열 문제로 인해 일부 아키텍처에서는 정확히 동작하지 않을 수 있지만, 문제 이해에 큰 도움이 된다.

두 프로세스 $P_0$과 $P_1$ (또는 $P_i$와 $P_j$)이 사용하며, 다음 두 가지 공유 데이터를 둔다.

• int turn; : 임계 구역에 진입할 수 있는 프로세스를 나타낸다 (초기값 0)
• boolean flag[2]; : flag[i]가 true이면 $P_i$가 임계 구역에 진입할 준비가 되었다는 뜻이다

잘못된 알고리즘 1

do {
    while (turn != i);     // Entry: 내 차례가 아니면 대기
        critical section
    turn = j;              // Exit: 상대에게 차례를 넘김
        remainder section
} while (1);

상호 배제는 보장되지만, 진행(Progress)은 보장되지 않는다. 준비 상태를 체크하는 변수가 없기 때문이다. 예를 들어, $P_1$이 임계 구역에 진입하려 하지만 $P_0$이 나머지 구역에 머물러 있으면 turn이 1로 전환되지 않는다.

잘못된 알고리즘 2

do {
    flag[i] = true;
    while (flag[j]);
        critical section
    flag[i] = false;
        remainder section
} while (1);

flag[i] = true와 while(flag[j])의 위치를 바꾸면 동시 접근이 가능해진다. 여기서도 상호 배제는 보장되지만, 진행은 보장되지 않는다. $P_0$과 $P_1$이 동시에 진입하면 flag[0]과 flag[1]이 모두 true가 되어 무한 대기에 빠질 수 있다.

Peterson's Solution의 완성

이 알고리즘은 세 가지 조건을 모두 만족한다.

참고로, 컴파일러가 명령어 순서를 바꿀 수 있다. 예를 들어 flag[1] = 1과 turn = 0의 순서가 바뀌면 문제가 생길 수 있다.

상호 배제 증명:

$P_i$와 $P_j$가 동시에 임계 구역에 진입했다면 flag[0] = flag[1] = true인데, turn은 0 또는 1 중 하나만 될 수 있으므로 둘 다 동시에 while 루프를 탈출할 수 없다.

진행과 한정 대기 증명:

$P_i$의 차단 조건은 flag[j] == true && turn == j다.

• $P_j$가 임계 구역 진입 준비가 안 되었으면 flag[j] == false이므로 $P_i$가 진입할 수 있다
• $P_j$가 while문에서 대기 중이면, turn은 $i$ 또는 $j$ 중 하나다
  • turn == i이면 $P_i$가 진입한다
  • 그렇지 않으면 $P_j$가 진입한 뒤, 퇴출 시 flag[j] = false로 설정하고 turn = i로 변경하므로 $P_i$가 진입할 수 있다
• 따라서 $P_i$는 최대 한 번의 $P_j$ 진입만 기다리면 된다 (한정 대기)

현대 아키텍처에서의 문제:

성능 향상을 위해 프로세서나 컴파일러가 의존성이 없는 읽기/쓰기 연산의 순서를 재배열할 수 있다. 공유 데이터를 사용하는 멀티스레드 애플리케이션에서 이런 재배열은 일관성 없는 결과를 초래할 수 있다.

예를 들어 다음과 같은 상황을 보자.

공유 변수: boolean flag = false; int x = 0;

Thread 1:              Thread 2:
1. while(!flag);       1. x = 100;
2. print x;            2. flag = true;

Thread 2의 1번과 2번 사이에 의존성이 없으므로 재배열될 수 있다. 그러면 Thread 1이 flag == true를 확인했을 때 x가 아직 0일 수 있다.

하드웨어 동기화 지원

메모리 모델 (Memory Model)

메모리 모델(Memory Model) 은 컴퓨터 아키텍처가 애플리케이션에 어떤 메모리 보장을 제공하는지를 결정한다. 두 가지 범주가 있다.

• 강 순서(Strongly Ordered): 한 프로세서에서의 메모리 수정이 즉시 모든 다른 프로세서에 보인다
• 약 순서(Weakly Ordered): 한 프로세서에서의 메모리 수정이 다른 프로세서에 즉시 보이지 않을 수 있다

메모리 장벽 (Memory Barrier)

메모리 장벽(Memory Barrier, Memory Fence) 은 메모리 변경 사항이 모든 다른 프로세서에 전파되도록 강제하는 명령어다. 주로 저수준에서 커널 개발자들이 사용한다.

메모리 장벽 이전의 모든 load/store 연산이 완료된 후에야 이후의 load/store 연산이 수행된다.

앞서 본 재배열 문제를 메모리 장벽으로 해결할 수 있다.

Thread 1:                          Thread 2:
while (!flag)                      x = 100;
    memory_barrier();              memory_barrier();
print x;                           flag = true;

하드웨어 명령어와 락

임계 구역 문제의 해결에는 락(Lock) 이 필요하다. 경쟁 상태는 임계 구역을 락으로 보호함으로써 방지할 수 있다.

하드웨어 지원은 락 구현을 더 쉽고 효율적으로 만든다.

락 변수를 이용한 상호 배제

공유 변수 lock을 사용하는 방식이다.

• boolean lock = 0; (초기값)
• lock이 false이면 어떤 프로세스든 임계 구역에 진입할 수 있다. 진입 시 lock을 true로 설정한다.
• lock이 true이면 다른 프로세스는 lock이 false가 될 때까지 대기해야 한다.

그런데 이 방식에는 문제가 있다.

lock을 확인하고 설정하는 사이에 컨텍스트 스위칭이 발생하면 두 프로세스가 동시에 진입할 수 있다. 즉, 상호 배제가 보장되지 않는다. 확인과 잠금이 분리되면 안 된다.

인터럽트 비활성화

단일 프로세서 시스템에서는 인터럽트를 비활성화하여 임계 구역 문제를 해결할 수 있다. 이는 커널 모드에서만 가능하며, 비선점형 커널과 같은 효과를 낸다. 스위칭이 불가능하므로 동기화 문제가 발생하지 않는다.

하지만 문제가 있다.

• 다중 프로세서 환경에서는 비효율적이다
• 일부 시스템에서는 클럭이 인터럽트에 의해 갱신되므로 인터럽트를 끄면 문제가 생긴다

원자적 하드웨어 명령어

하드웨어가 원자적 명령어(Atomic Instruction) 를 제공하면 락 구현이 훨씬 쉬워진다. 원자적 명령어란 여러 연산을 하나의 분리 불가능한 단위로 묶는 것이다.

TestAndSet: 변수를 true로 설정하고 이전 값을 반환한다.

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

Swap: 두 변수의 값을 교환한다.

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

Compare and Swap (CAS): *value == expected일 때만 *value를 new_value로 설정한다.

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

TestAndSet을 이용한 상호 배제

// 공유 변수: boolean lock = false;

do {
    while (TestAndSet(&lock));

    /* critical section */

    lock = false;

    /* remainder section */
} while(1);

동작 예시:

1. lock = 0, $P_1$이 TestAndSet(&lock)을 호출하면 0을 반환하고 lock = 1로 설정. $P_1$이 임계 구역 진입
2. $P_2$가 진입을 시도하면 TestAndSet(&lock)이 1을 반환. $P_2$는 대기
3. $P_1$이 퇴출하며 lock = 0으로 설정
4. $P_2$가 TestAndSet(&lock)에서 0을 반환받아 임계 구역 진입

Swap을 이용한 상호 배제

// 공유 변수: boolean lock = false;

do {
    key = true;  // 지역 변수
    while (key == true)
        Swap(&lock, &key);

    /* critical section */

    lock = false;

    /* remainder section */
} while(1);

동작 예시:

1. lock = 0, $P_1$의 key = 1. Swap(&lock, &key) 실행 후 lock = 1, key = 0. while 탈출, $P_1$ 임계 구역 진입
2. $P_2$의 key = 1. Swap 실행 후 lock = 1, key = 1. 여전히 대기
3. $P_1$ 퇴출, lock = 0
4. $P_2$의 Swap 실행 후 key = 0, lock = 1. while 탈출, $P_2$ 임계 구역 진입

CAS를 이용한 상호 배제

// 공유 변수: boolean lock = false;

while (true) {
    while (compare_and_swap(&lock, 0, 1) != 0);

    /* critical section */

    lock = 0;

    /* remainder section */
}

동작 예시:

1. lock = 0. $P_1$이 compare_and_swap(&lock, 0, 1)을 호출하면 0을 반환하고 lock = 1. 임계 구역 진입
2. $P_2$ 시도 시 lock이 1이므로 compare_and_swap은 1을 반환. 대기
3. $P_1$ 퇴출, lock = 0. $P_2$ 진입

한정 대기를 보장하는 상호 배제

앞선 알고리즘들은 상호 배제는 보장하지만, 한정 대기(Bounded Waiting) 는 보장하지 않을 수 있다. $n$개 프로세스에서 한정 대기를 보장하려면 어떻게 해야 할까?

예를 들어 $P_0, P_1, P_3, P_5$가 임계 구역 진입을 원하고, 현재 $P_1$이 임계 구역에 있다고 하자.

굵은 선은 공유 자원을 원하는 프로세스, 가는 선은 그렇지 않은 프로세스를 나타낸다.

핵심 아이디어는 프로세스가 임계 구역을 떠날 때, 다음에 진입할 프로세스를 지정하는 것이다. 오른쪽 방향으로 순회하며 처음 만나는 대기 중인 프로세스에게 차례를 넘긴다.

공유 변수는 다음과 같다.

• boolean lock; : 상호 배제용
• boolean waiting[n]; : waiting[i]가 true이면 $P_i$가 임계 구역에 진입하고 싶지만 아직 진입하지 못한 상태

TestAndSet 기반 알고리즘:

while (TRUE) {
    waiting[i] = TRUE;
    key = TRUE;  // 지역 변수
    while (waiting[i] && key)
        key = TestAndSet(&lock);
    waiting[i] = FALSE;

    /* critical section */

    j = (i + 1) % n;
    // j != i : 탐색 완료, !waiting[j] : 대기 중인 프로세스 찾기
    while (j != i && !waiting[j])
        j = (j + 1) % n;

    if (j == i)
        lock = FALSE;       // 대기 중인 프로세스가 없으면 락 해제
    else
        waiting[j] = FALSE;  // 다음 순서의 프로세스 j만 진입 허용

    /* remainder section */
}

CAS 기반 알고리즘:

while (true) {
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key)
        key = compare_and_swap(&lock, 0, 1);
    waiting[i] = false;

    /* critical section */

    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;

    if (j == i)
        lock = 0;
    else
        waiting[j] = false;

    /* remainder section */
}

원자적 변수 (Atomic Variables)

원자적 변수(Atomic Variable) 는 정수, 불리언 같은 기본 자료형에 대해 원자적 연산을 제공하는 특수 변수다. 경쟁 상태 걱정 없이 안전하게 사용할 수 있다.

• 특수 자료형 + 연산의 형태로 제공된다
• 상호 배제를 보장하는 데 사용할 수 있다
• 일반적으로 CAS 명령어로 구현된다

void increment(atomic int *v) {
    int temp = 0;
    do {
        temp = *v;
    } while (temp != compare_and_swap(v, temp, temp + 1));
    // 다른 프로세스가 중간에 접근했는지 확인
}

동작 예시 (두 프로세스가 동시에 increment 호출):

1. v = 5
2. $temp_1$ = 5, $temp_2$ = 5
3. $P_1$의 CAS 성공: v = 6
4. $P_2$의 CAS 실패 (temp = 5인데 v = 6이므로), 다시 시도: $temp_2$ = 6
5. $P_2$의 CAS 성공: v = 7

원자적 변수 내부의 값은 직접 수정이 불가능하고, 반드시 제공되는 원자적 연산을 통해서만 변경할 수 있다.

뮤텍스와 세마포어

앞서 살펴본 하드웨어 명령어 기반의 해결책은 저수준이다. 운영체제는 더 상위 수준의 동기화 도구로 뮤텍스(Mutex)와 세마포어(Semaphore)를 제공한다.

뮤텍스 락 (Mutex Lock)

뮤텍스 락은 상호 배제를 구현하는 동기화 도구다. 불리언 변수 available로 구성되며, available = true이면 잠금 해제, available = false이면 잠금 상태를 의미한다. 앞서 다룬 lock 변수와는 반대 의미이므로 주의해야 한다.

뮤텍스에 대한 원자적 연산은 두 가지다.

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

release() {
    available = true;
}

뮤텍스 락을 이용한 동기화 구조는 다음과 같다.

이를 통해 상호 배제가 보장되고 경쟁 상태를 방지할 수 있다.

세마포어 (Semaphore)

세마포어(Semaphore) 는 정수 변수 S로, 두 가지 원자적 연산 wait()와 signal()을 통해서만 접근 가능하다. S의 초기값은 사용 가능한 자원의 수로, 1 이상의 양의 정수다.

wait(S) {              // acquire에 대응
    while (S <= 0);    // 락을 기다림
    S--;               // 락을 획득
}

signal(S) {            // release에 대응
    S++;               // 락을 해제
}

S를 재사용 가능한 입장 티켓에 비유할 수 있다. 티켓이 남아 있으면 임계 구역에 들어갈 수 있고, 없으면 기다려야 한다.

세마포어의 구현

앞서 정의한 wait()에는 문제가 있다. while(S <= 0); 부분이 스핀락(Spinlock, Busy Waiting) 으로 CPU 시간을 낭비한다.

대안은 스핀락 대신 블록(Block) 방식을 사용하는 것이다. wait(S)를 호출한 프로세스가 진입할 수 없으면, 대기 큐에 넣고 스스로 차단(block)되어 CPU 시간을 사용하지 않는다.

새로운 세마포어 정의:

typedef struct {
    int value;
    struct process *list;  // 대기 큐(연결 리스트)의 헤드
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block();  // CPU 시간을 사용하지 않고 대기
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {  // 대기 중인 프로세스가 있는지 확인
        remove a process P from S->list;
        wakeup(P);  // 대기 중인 프로세스 깨움
    }
}

세마포어의 핵심은 원자성(Atomicity) 이다. 원자성은 흔히 상호 배제를 통해 보장된다.

• 단일 프로세서 환경: 인터럽트 비활성화로 보장 (커널 모드, 스위칭 불가)
• 다중 프로세서 환경: 스핀락을 사용한다
  • 모든 프로세서의 인터럽트를 비활성화하면 성능 저하가 심하다
  • 세마포어의 wait/signal 코드는 매우 짧기 때문에, 짧은 스핀락으로도 충분히 효율적이다

모니터 (Monitor)

세마포어의 한계

세마포어는 여전히 저수준 도구다. wait()과 signal()의 호출 순서를 프로그래머가 직접 관리해야 하므로 실수가 발생하기 쉽다.

모니터란?

모니터(Monitor) 는 동기화를 지원하는 고수준 언어 구조(High-level Language Construct) 다.

• 비공개 데이터(Private Data): 모니터 내부의 메서드를 통해서만 접근 가능하다
• 공개 메서드(Public Methods): 상호 배제가 자동으로 제공된다

한 시점에 오직 하나의 프로세스만 모니터 내에서 활성 상태일 수 있다. 프로그래머가 동기화를 직접 신경 쓸 필요가 없다는 점이 세마포어 대비 큰 장점이다.

조건 변수 (Condition Variables)

모니터 내부에서 추가적인 동기화 메커니즘이 필요할 때 조건 변수(Condition Variable) 를 사용한다.

• 선언: condition x, y;
• 대기: x.wait(); (프로세스를 sleep 상태로 전환)
• 시그널: x.signal(); (대기 중인 프로세스를 깨움. 대기 중인 프로세스가 없으면 아무 일도 하지 않음)

문제 상황:

프로세스 P가 x.signal()로 다른 프로세스 Q를 깨우면, P와 Q가 동시에 모니터 안에서 실행하게 된다. 모니터의 상호 배제 원칙에 위배된다.

해결 방식:

• Signal and wait: P가 Q를 깨운 뒤, P가 대기한다 (Q가 모니터를 떠나거나 대기할 때까지)
• Signal and continue: P가 Q를 깨운 뒤, Q가 대기한다 (P가 모니터를 떠나거나 대기할 때까지)

세마포어를 이용한 모니터 구현

두 개의 세마포어가 필요하다.

• semaphore mutex = 1; : 모니터의 상호 배제용
• semaphore next = 0; : signal을 보낸 프로세스가 대기하기 위한 용도 (초기값 0이므로 즉시 sleep)
• int next_count = 0; : next에서 대기 중인 프로세스 수

외부 프로시저 F의 구조:

wait(mutex);
    ...
    body of F;
    ...
if (next_count > 0)
    signal(next);       // 대기 중인 프로세스가 있으면 깨움
else
    signal(mutex);      // 없으면 모니터 락 해제

조건 변수의 구현:

각 조건 변수 x에 대해 다음 데이터가 필요하다.

• semaphore x_sem = 0; (초기값 0이므로 wait 시 즉시 sleep)
• int x_count = 0;

x.wait() {
    x_count++;
    if (next_count > 0)
        signal(next);     // 기다리고 있는 프로세스를 깨움
    else
        signal(mutex);    // 다른 프로세스가 모니터에 들어갈 수 있게 해제
    wait(x_sem);          // 자신은 sleep
    x_count--;
}

x.signal() {
    if (x_count > 0) {
        next_count++;
        signal(x_sem);    // 대기 중인 프로세스 깨움
        wait(next);       // 자신(시그널을 보낸 프로세스)은 sleep
        next_count--;
    }
}

데드락 (Deadlock)

두 개 이상의 프로세스가 서로가 가진 자원을 기다리면서 무한히 대기하는 상태를 데드락(Deadlock) 이라 한다.

HGU 전산전자공학부 김인중 교수님의 23-1 운영체제 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.