램포트의 빵집 알고리즘 (Lamport's Bakery Algorithm)

램포트의 빵집 알고리즘 (Lamport’s Bakery Algorithm)

램포트의 빵집 알고리즘(Lamport’s Bakery Algorithm)은 N개 프로세스의 상호 배제(Mutual Exclusion) 문제를 해결하기 위한 소프트웨어 기반 알고리즘이다. 1974년 레슬리 램포트(Leslie Lamport)가 제안했으며, 빵집에서 번호표를 받아 순서대로 서비스받는 방식에서 아이디어를 얻었다.

램포트의 빵집 알고리즘은 병행 프로그래밍의 이론적 토대를 제공했지만, 현대 시스템에서는 주로 하드웨어 지원 동기화 기법이 사용된다. 단, 분산 시스템이나 임베디드 환경에서는 여전히 연구 및 적용 사례가 존재한다.

핵심 원리

번호표 시스템

• 각 프로세스는 임계 영역 진입 전 고유한 번호표를 받는다.
• 번호표는 단조 증가(monotonically increasing) 방식으로 발급되며, 동시 접근 시 프로세스 ID로 우선순위 결정한다.

단조 증가(monotonically increasing)란 함수나 수열이 항상 증가하거나 일정한 값을 유지하는 성질을 의미한다. 즉, 감소하는 구간 없이 유지되거나 증가하는 경우를 말한다.

동작 단계

1. 번호표 선택

   1 2 3

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

   • 프로세스 i가 번호표를 선택할 동안 다른 프로세스가 방해하지 못하도록 choosing[i] 플래그 사용.

2. 대기 조건

   1 2 3 4

   for 모든 프로세스 j ≠ i: while choosing[j]: pass # j가 번호표 선택 중이면 대기 while (number[j] != 0) and ((number[j], j) < (number[i], i)): pass # 더 낮은 번호표 또는 동일 시 낮은 ID 대기

   • 모든 프로세스의 번호표와 ID를 비교해 자신의 차례까지 대기.

3. 임계 영역 실행

   1 2	# Critical Section 실행 print(f"프로세스 {i}가 임계 영역 실행 중")

4. 종료 및 초기화

   1	number[i] = 0 # 번호표 반납

   • 실행 완료 후 번호표를 0으로 재설정해 다른 프로세스가 진입 가능하게 함.

특징 분석

실제 구현 사례

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Python 구현 예시 (3개 스레드)
import threading

choosing = [False] * 3
number = [0] * 3

def bakery_algorithm(thread_id):
    global choosing, number
    
    # 번호표 선택
    choosing[thread_id] = True
    number[thread_id] = max(number) + 1
    choosing[thread_id] = False
    
    # 대기 조건 검사
    for i in range(3):
        if i == thread_id:
            continue
        while choosing[i]:
            pass
        while number[i] != 0 and (number[i], i) < (number[thread_id], thread_id):
            pass
    
    # 임계 영역 실행
    print(f"스레드 {thread_id} 임계 영역 진입")
    number[thread_id] = 0  # 초기화

# 스레드 생성 및 실행
threads = [threading.Thread(target=bakery_algorithm, args=(i,)) for i in range(3)]
for t in threads:
    t.start()
for t in threads:
    t.join()

• 실행 결과:
  스레드 0 임계 영역 진입 → 스레드 1 임계 영역 진입 → 스레드 2 임계 영역 진입
  (실제 실행 시 번호표 순서에 따라 출력 순서 변동)

현대 시스템에서의 활용

• Linux 커널: ticket spinlock으로 구현되어 스핀락 경쟁 시 공정성 보장.
• 분산 시스템: 공유 메모리가 없는 환경에서 타임스탬프 기반 동기화에 응용.
• 교육용: 상호 배제 개념을 이해하기 위한 표준 예제로 사용.

한계와 개선 방향

• Atomic Operation 도입: CAS(Compare-And-Swap) 명령어를 활용해 Busy Waiting 감소.
• 하이브리드 접근: 세마포어와 결합해 대기 큐를 사용하는 방식으로 전환.
• 최적화 대응: 메모리 배리어(Memory Barrier) 추가로 CPU 최적화 우회.

참고 및 출처