Lamport's Bakery 알고리즘으로 다중 프로세스 임계 영역 제어하기

프로세스가 동시에 공유 자원에 접근하려 할 때, Bakery 알고리즘은 번호표를 통해 임계 영역 진입 순서를 정한다. 번호가 작은 프로세스가 앞서고, 번호가 같으면 PID가 낮은 프로세스가 우선한다. Leslie Lamport가 1974년 제안한 이 방식은 빵집이나 은행의 대기 번호표처럼 동작하며, 하드웨어 지원 없이 소프트웨어만으로 상호 배제를 보장한다.

번호표로 임계 영역 경쟁을 정렬하는 방식

임계 영역 문제에서는 공유 자원 접근 과정에서 상호 배제, 진행, 한정 대기를 만족해야 한다. Peterson's Algorithm은 2개 프로세스만 지원하며, Test-and-Set이나 Compare-and-Swap 같은 방식은 하드웨어 지원을 전제로 한다.

Bakery 알고리즘은 N개 프로세스를 대상으로 순수 소프트웨어 방식의 동기화를 구성한다. 요청 순서에 따른 공정성(FIFO)을 제공하며, 번호표 비교만으로 진입 순서를 결정한다.

프로세스가 임계 영역 진입을 원하면 현재 발급된 번호 중 최대값에 1을 더한 번호표를 선택한다. 동시에 번호표를 선택한 프로세스들은 같은 번호를 가질 수 있고, 이때 PID가 우선순위를 가른다.

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

우선순위는 번호표와 프로세스 식별자를 묶은 튜플로 비교한다.

(number[i], i) < (number[j], j)

첫 번째 요소인 번호표가 먼저 비교되고, 번호가 같을 때 두 번째 요소인 PID를 비교한다. 모든 다른 프로세스보다 우선순위가 높아질 때까지 프로세스는 Busy Waiting으로 대기한다.

choosing과 number가 맡는 역할

choosing 배열은 각 프로세스가 번호표를 고르는 중인지 나타낸다.

choosing[i]: 프로세스 i가 번호표를 선택 중인지 여부

이 배열은 boolean 배열이다. true는 번호표 선택 중임을, false는 선택이 끝났거나 아직 선택하지 않았음을 뜻한다. 다른 프로세스는 대상 프로세스가 번호표 선택을 마칠 때까지 기다리므로 동시 선택 시 충돌을 방지하고 원자성을 보장한다.

number 배열은 각 프로세스가 가진 현재 번호표를 보관한다.

number[i]: 프로세스 i의 현재 번호표

정수 배열에서 0은 번호표가 없고 임계 영역 밖에 있음을 뜻한다. 양수는 현재 번호표다. 이 값은 우선순위와 대기 순서, 진입 가능 여부를 판단하는 기준이 된다.

초기 상태는 다음과 같다.

choosing[i] = false for all i
number[i] = 0 for all i

진입 요청부터 번호표 반납까지

프로세스 i는 먼저 번호표 선택 상태를 표시한다.

choosing[i] = true;

이후 전체 번호표에서 최대값을 찾고, 그 값에 1을 더해 자신의 번호표로 사용한다.

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

번호표 선택이 끝나면 choosing 값을 해제한다.

choosing[i] = false;

그다음 다른 모든 프로세스를 확인한다. 다른 프로세스가 번호표를 고르는 중이면 기다리고, 이미 번호표를 가진 프로세스의 우선순위가 더 높으면 계속 대기한다.

for (j = 0; j < n; j++) {
    // j가 번호표 선택 중이면 대기
    while (choosing[j]);

    // j의 우선순위가 높으면 대기
    while ((number[j] != 0) &&
           ((number[j], j) < (number[i], i)));
}

대기 조건을 통과한 프로세스만 공유 자원에 접근한다.

// 임계 영역 실행
// 공유 자원 접근

작업을 마치면 번호표를 0으로 되돌려 다음 프로세스가 진입할 수 있게 한다.

number[i] = 0;

전체 흐름은 다음 코드로 표현할 수 있다.

// 프로세스 i
do {
    // Entry Section
    choosing[i] = true;
    number[i] = max(number[0], ..., number[n-1]) + 1;
    choosing[i] = false;

    for (j = 0; j < n; j++) {
        while (choosing[j]);
        while ((number[j] != 0) &&
               ((number[j], j) < (number[i], i)));
    }

    // Critical Section
    // 공유 자원 접근

    // Exit Section
    number[i] = 0;

    // Remainder Section

} while (true);

동일한 번호표를 고른 프로세스가 있을 때 PID 비교가 순서를 확정하는 모습은 다음과 같다.

⤢✕

같은 번호표를 받은 프로세스의 순서

초기 배열 상태는 다음과 같다.

choosing = [false, false, false]
number = [0, 0, 0]

프로세스 0, 1, 2가 동시에 진입을 요청하면 모두 번호 1을 선택할 수 있다.

// 프로세스 0
choosing[0] = true
number[0] = 1
choosing[0] = false

// 프로세스 1
choosing[1] = true
number[1] = 1 (동일 번호)
choosing[1] = false

// 프로세스 2
choosing[2] = true
number[2] = 1 (동일 번호)
choosing[2] = false

번호표가 같으므로 튜플의 두 번째 값인 PID가 비교 대상이 된다.

(number[0], 0) = (1, 0)
(number[1], 1) = (1, 1)
(number[2], 2) = (1, 2)

(1, 0) < (1, 1) < (1, 2)

따라서 프로세스 0, 프로세스 1, 프로세스 2 순으로 임계 영역에 들어간다.

1. 프로세스 0 임계 영역 진입 → 실행 → number[0] = 0
2. 프로세스 1 임계 영역 진입 → 실행 → number[1] = 0
3. 프로세스 2 임계 영역 진입 → 실행 → number[2] = 0

이 과정을 시간 순서로 보면 다음과 같다.

시간 1: P0, P1, P2 번호표 발급 (모두 1)
시간 2: 우선순위 확인 (PID 순)
시간 3: P0 임계 영역 진입, P1/P2 대기
시간 4: P0 완료, number[0] = 0
시간 5: P1 임계 영역 진입, P2 대기
시간 6: P1 완료, number[1] = 0
시간 7: P2 임계 영역 진입
시간 8: P2 완료, number[2] = 0

공정성과 운영상 제약

Bakery 알고리즘은 먼저 요청한 프로세스가 먼저 진입하는 FIFO 특성으로 공정성을 제공하며 기아를 방지한다. 하드웨어 지원 없이 동작하고, 동일한 번호표를 허용하면서도 PID로 순서를 정할 수 있어 번호 관리가 복잡하지 않다. 2개 이상 프로세스를 지원하므로 Peterson's Algorithm의 범위를 넘는다.

다만 대기 과정은 Busy Waiting이므로 CPU 사이클 낭비, 스핀락, 에너지 소비, 성능 저하 문제가 따른다. choosing 배열과 number 배열은 프로세스 수에 비례하는 메모리를 사용한다. 번호는 계속 증가하므로 정수 범위 초과 가능성과 주기적 재설정도 고려해야 한다. 또한 O(n) 대기 루프는 프로세스 수가 증가할수록 느려지고, 캐시 미스와 확장성 한계로 이어질 수 있다.

소규모 시스템과 동기화 개념을 이해하는 교육 목적에는 적합하다. 대규모 시스템에서는 세마포어나 뮤텍스를 권장하며, 실시간 시스템에서는 Busy Waiting의 문제를 함께 검토해야 한다.