경쟁 상태와 상호 배제: Thread Safe, 데커·피터슨 알고리즘

병행 프로세스

운영체제는 프로세서를 빠르게 전환해 여러 프로세스가 동시에 실행되는 것처럼 보이게 한다. 병행성은 시스템의 신뢰도와 처리 능력을 높이는 데 중요하지만 문제도 있다.

• 각 프로세스는 서로의 존재를 모른다. (비동기적)
• 병행 수행 중인 비동기적 프로세스들이 공유 자원에 동시에 접근하면 문제가 발생한다.

동시성과 병렬성

• 동시성(Concurrency): 코어가 하나여도 Context Switching으로 여러 작업이 동시에 처리되는 것처럼 보이게 하는 것
• 병렬성(Parallelism): 2개 이상의 코어로 작업을 실제로 동시에 실행하는 것

어느 쪽이든 여러 작업이 어떤 자원을 공유하는지 고려해야 하며, 그렇지 않으면 다음 문제가 생긴다.

• Race Condition(경쟁 상태): 여러 프로세스가 하나의 자원에 접근해 서로의 실행 결과에 영향을 주는 현상
• Deadlock(교착 상태): 프로세스들이 서로 자원을 점유한 채 상대방의 작업이 끝나기를 무한히 기다리는 현상
• Starvation(기아): 특정 프로세스가 우선순위가 낮거나 스케줄링 정책 때문에 원하는 자원을 계속 할당받지 못하는 현상

이 글은 경쟁 상태와 그 해결책인 상호 배제를 다루고, 교착 상태는 별도의 글에서 다룬다.

생산자-소비자 문제

생산자 프로세스가 생산한 정보를 소비자 프로세스가 소비하는, 비동기적으로 수행되는 모델이다. 생산자는 버퍼가 꽉 차면 더 생산할 수 없고, 소비자는 버퍼가 비면 소비할 수 없다.

유한 버퍼를 사용하는 코드는 다음과 같다. 공유 데이터부터 선언한다.

#define BUFFER_SIZE 10
typedef struct {
    DATA data;
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

생산자 프로세스는 새로 생산한 원소를 지역 변수 nextProduced에 담아 버퍼에 넣는다.

item nextProduced;

while (true) {
    // 버퍼가 가득 차 있으면 while 문에 머문다
    while (counter == BUFFER_SIZE);
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

소비자 프로세스는 버퍼에서 꺼낸 원소를 지역 변수 nextConsumed에 저장한다.

item nextConsumed;

while (true) {
    // 버퍼가 비어 있으면 아무 일도 하지 않는다
    while (counter == 0);
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

경쟁 상태

두 프로세스가 counter를 동시에 조작하면 경쟁 상태(Race Condition) 가 된다. 경쟁 상태란 둘 이상의 프로세스가 공유 데이터를 병행적으로 읽거나 쓸 때, 접근 순서에 따라 실행 결과가 달라지는 상황이다. 마지막에 남는 데이터의 결과를 보장할 수 없다.

이를 막으려면 병행 프로세스들을 동기화해야 한다. 동기화의 목적은 데이터의 일관성이고, 핵심은 한 번에 여러 동작이 실행되지 않게 하는 것이다. 즉 counter를 한순간에 하나의 프로세스만 조작하도록 해야 한다.

상호 배제

• 임계 영역(Critical Section): 공유 자원에 접근하는 코드 영역
• 상호 배제(Mutual Exclusion): 여러 프로세스가 동시에 임계 영역에 진입하지 못하게 막는 것

공유 자원이 사용 중일 때 다른 프로세스가 접근하지 못하게 막는 방법이다. 읽기 연산만 한다면 공유 데이터에 동시에 접근해도 문제가 없다.

상호 배제가 만족해야 하는 조건은 다음과 같다.

1. 두 프로세스가 동시에 공유 자원에 진입할 수 없다.
2. 프로세스의 속도나 프로세서 수에 영향을 받지 않는다.
3. 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있다.
4. 프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안 된다.

Thread Safe

멀티 스레드 환경에서 어떤 함수나 변수, 객체에 여러 스레드가 동시에 접근해도 프로그램 실행에 문제가 없는 것을 Thread Safe하다고 한다. 하나의 함수가 한 스레드에서 실행 중일 때 다른 스레드가 같은 함수를 호출해 함께 실행되더라도, 각 스레드에서 수행 결과가 올바르게 나와야 한다.

Thread Safe를 보장하는 방법

1. Re-entrancy (재진입성): 함수가 한 스레드에서 실행 중일 때 다른 스레드가 호출해도 각각 올바른 결과를 얻도록, 함수에서 사용하는 변수를 스레드마다 독립적으로 쓰게 설계한다.
2. Thread-local storage: 공유 자원 사용을 최대한 줄이고 각 스레드만 접근할 수 있는 저장소를 사용한다. 스레드끼리 공유하는 Heap과 Data 영역 접근을 최소화하고, 스레드마다 독립적인 Stack 영역의 자원을 쓰는 것이다.
3. Immutable object: 공유 자원을 써야 한다면 불변 객체를 사용한다.
4. Mutual exclusion: 공유 자원을 꼭 수정해야 한다면 세마포 같은 락으로 접근을 통제한다.
5. Atomic operation: 공유 자원에 접근할 때 원자적 연산이나 원자적으로 정의된 접근 방법을 사용한다.

멀티 스레드 환경에서 싱글톤을 선언할 때 쓰는 Lazy Initialization + Double-checked Locking도 같은 맥락의 기법이다.

소프트웨어로 구현하는 상호 배제

데커의 알고리즘

두 프로세스가 공유 메모리로 통신하며 충돌 없이 단일 자원을 공유하게 하는 알고리즘이다. 임계 영역에 진입하려는 프로세스는 플래그를 설정하고 대기한다.

• 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스의 임계 영역 진입을 막지 않는다.
• 임계 영역에 들어가려는 프로세스를 무한정 기다리게 하지 않는다.

피터슨의 알고리즘

플래그와 차례(turn) 변수로 상호 배제를 구현하는 알고리즘이다.

bool flag[2] = {false, false};  // true: 임계 영역 사용을 원함
int turn;                       // 0은 P0, 1은 P1의 차례를 뜻함

// P0
flag[0] = true;                 // 임계 영역 사용을 원함
turn = 1;                       // 차례를 P1에게 양보
while (flag[1] && turn == 1) {
    // P1이 사용을 원하고 차례도 P1이면, 사용 가능해질 때까지 계속 확인
}
// 임계 영역
flag[0] = false;                // 임계 영역 사용 완료

// P1
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0) {
    // 임계 영역이 사용 가능한지 계속 확인
}
// 임계 영역
flag[1] = false;

소프트웨어 해법의 한계

• 속도가 느리고 구현이 복잡하다.
• Busy waiting: 진입 가능한지 확인하려고 기다리는 동안에도 while 문을 계속 수행하며 CPU를 쓴다. 락이 풀릴 때까지 lock 변수를 확인하며 CPU를 돌면서 기다리는 Spin Lock도 같은 방식이다.

Busy waiting은 락을 얻지 못한 프로세스를 대기 큐에 넣고 재우는 방식으로 해결한다. 세마포와 뮤텍스, 모니터가 그 도구다.

원자적 연산으로 구현하는 동기화

원자적 연산은 중간에 인터럽트되거나 중단될 수 없는 연산이다. 하드웨어가 제공하는 원자적 연산을 이용하면 동기화를 구현할 수 있다.

• Test-and-set: 공유 변수의 값을 확인하고 변경하는 연산을 원자적으로 수행한다.
• Compare-and-swap (CAS): 값을 기대하는 값과 비교해, 일치할 때만 새 값으로 교환하는 연산을 원자적으로 수행한다.

멀티코어에서 동기화하는 방식은 크게 둘로 나뉜다.

• 락: 뮤텍스, 세마포, 모니터
• 락-프리 알고리즘: 락을 쓰지 않고, 연산한 뒤 변수의 값이 처음 읽은 값과 일치하는지 비교해 일치하지 않으면 반영하지 않는다. (CAS 활용)

volatile

• C, C++: 컴파일러가 해당 변수에 대한 접근을 최적화하지 못하게 막아, 개발자의 의도대로 매번 메모리에서 읽고 쓰게 한다.
• Java: 변수의 값을 CPU 캐시가 아닌 메인 메모리에서 읽고 쓰게 한다. 다만 상호 배제를 지원하지 않으므로 경쟁 상태가 발생할 수 있고, 이를 해결하려면 synchronized를 사용해야 한다.

참고

• 운영체제: 그림으로 배우는 구조와 원리 (한빛아카데미)