상호배제와 임계구역: 공유자원을 안전하게 동기화하는 방법

공유자원을 동시에 건드릴 때 생기는 문제

여러 프로세스가 같은 자원을 함께 쓰면 접근 순서에 따라 결과가 달라질 수 있다. 상호배제(Mutual Exclusion)는 한 프로세스가 공유자원을 사용하는 동안 다른 프로세스의 접근을 막아 이런 충돌을 제어하는 동기화 기법이다. 임계구역에 대한 배타적 접근을 보장해 Race Condition을 방지하고, 데이터의 무결성과 일관성을 유지한다.

임계구역은 공유자원에 접근하는 코드 영역만을 뜻하지 않는다. 진입을 요청하고, 사용을 마친 뒤 빠져나오며, 일반 코드를 수행하는 흐름까지 함께 봐야 한다.

진입구역(Entry Section): 임계구역 진입 허가 요청
임계구역(Critical Section): 공유자원 접근 영역
퇴출구역(Exit Section): 임계구역 사용 종료 신호
나머지구역(Remainder Section): 일반 코드 실행 영역

⤢✕

안전한 상호배제가 갖춰야 할 성질

임계구역 제어는 단순히 동시에 들어오지 못하게 하는 데서 끝나지 않는다. 다음 조건이 함께 성립해야 한다.

상호배제(Mutual Exclusion): 한 번에 하나의 프로세스만 임계구역 진입
진행(Progress): 임계구역이 비어있으면 대기 중인 프로세스가 진입 가능
유한대기(Bounded Waiting): 무한정 대기하지 않고 유한 시간 내 진입 보장
동일속도(No Assumption): 프로세스의 실행 속도에 대한 가정 없음

조건을 놓치면 문제의 형태도 달라진다. 상호배제가 깨지면 Race Condition과 데이터 불일치가 발생하고, 진행 조건을 만족하지 못하면 데드락(Deadlock)이 생길 수 있다. 유한대기가 보장되지 않으면 특정 프로세스가 계속 밀리는 기아(Starvation) 상태가 나타난다. 실행 속도에 의존하면 동작은 시스템 환경에 묶인다.

⤢✕

하드웨어 명령으로 락을 구현하는 방식

Test and Set은 변수의 검사와 설정을 원자적으로 처리하는 명령을 이용한다. 하드웨어 수준에서 락을 만들 수 있어 구조는 단순하지만, 락이 풀릴 때까지 반복 검사하는 Busy Waiting 문제가 있다.

boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}

Swap(Exchange)은 두 변수의 값을 원자적으로 맞바꾸는 방식이다. 프로세스의 키(Key)와 락(Lock) 값을 교환하며, Test and Set과 비슷한 원리로 하드웨어 명령어에서 구현한다.

인터럽트를 금지하는 방법도 있다. 임계구역에 들어갈 때 인터럽트를 비활성화해 문맥교환(Context Switch)을 막는다. 다만 시스템 응답성이 낮아지고 멀티프로세서 환경에서는 비효율적이다.

소프트웨어와 OS 수준의 동기화 도구

두 프로세스만을 대상으로 한 알고리즘 가운데 Dekker 알고리즘은 최초의 소프트웨어 기반 상호배제 알고리즘이다. 플래그(Flag) 배열과 턴(Turn) 변수를 사용하며 4가지 조건을 모두 만족하지만, 로직이 복잡해 구현 난이도가 높다.

Peterson 알고리즘은 Dekker 알고리즘을 단순화한 형태다. 플래그와 턴 변수로 공정성을 보장하며, 2개 프로세스 환경에서 이해하고 구현하기가 상대적으로 쉽다.

// Peterson's Algorithm
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
// Critical Section
flag[i] = false;

N개 프로세스 환경에서는 Lamport의 빵집 알고리즘(Bakery Algorithm)이 번호표(Ticket) 개념을 사용해 일반화된 해결책을 제시한다. FIFO 순서로 공정성을 보장하며 분산 시스템에도 적용할 수 있다. Knuth 알고리즘 역시 N개 프로세스를 지원하지만, 복잡한 상태 전이 메커니즘 때문에 역사적 의의와 달리 실무에서는 비효율적이다.

세마포어(Semaphore)는 Dijkstra가 제안한 동기화 도구다. P 연산(wait)은 자원을 획득하고, V 연산(signal)은 자원을 해제한다. 세마포어는 카운팅 세마포어와 이진 세마포어로 구분된다.

// Semaphore Operations
P(S) {
    while (S <= 0);  // Busy waiting
    S--;
}

V(S) {
    S++;
}

모니터(Monitor)는 추상 데이터 타입(ADT)으로 구현하는 고수준 동기화 도구다. 조건 변수(Condition Variable)를 사용하며 Java의 synchronized, C#의 lock 등에 활용된다.

⤢✕

환경에 따라 달라지는 기법 선택

하드웨어 기반 기법은 빠르고 간단하지만 Busy Waiting을 고려해야 한다. 소프트웨어 기반 기법은 이식성이 좋지만 구현이 복잡하고 오버헤드가 존재한다.

세마포어는 저수준 도구여서 유연하지만 사용 실수가 발생하기 쉽다. 모니터는 더 높은 수준의 안전성을 제공하지만 언어 지원이 필요하다. 단일 또는 멀티프로세서 환경인지, 성능 요구사항은 무엇인지, 개발 편의성과 안전성 및 이식성을 어느 정도로 요구하는지를 함께 판단해 선택한다.

상호배제는 운영체제의 프로세스 동기화에서 공유자원 접근을 안전하게 만드는 기본 장치다. Test and Set과 Swap 같은 하드웨어 기법, Dekker와 Peterson 알고리즘, Semaphore와 Monitor는 서로 다른 제약과 환경에서 이 목적을 구현한다.