피터슨 알고리즘 (Peterson's Algorithm)

피터슨 알고리즘 (Peterson’s Algorithm)

피터슨 알고리즘(Peterson’s Algorithm)은 두 프로세스의 **상호 배제(Mutual Exclusion)**를 보장하기 위한 소프트웨어 기반 동기화 알고리즘이다.
1981년 개리 피터슨(Gary L. Peterson)이 제안한 이 알고리즘은 간결성과 이론적 엄밀성으로 운영체제 및 병행 프로그래밍 분야에서 널리 연구된다.

피터슨 알고리즘은 이론적 완결성을 인정받지만, 현대 시스템에서는 주로 하드웨어 기반 동기화 기법(예: TAS, CAS)이 사용됩니다. 그러나 병행 프로그래밍의 근본 원리를 이해하는 데 여전히 핵심적인 역할을 한다.

핵심 구성 요소

1. 플래그 배열(flag)
   • 각 프로세스의 임계 영역 진입 의사 표시 (flag, flag 초기값 False)
2. 턴 변수(turn)
   • 임계 영역 진입 순서 결정 (0 또는 1 값을 가짐)

동작 원리

1. 진입 의사 표시:
   프로세스 i가 임계 영역 진입 전 flag[i] = True 설정.

2. 턴 양보:
   turn = 1 - i로 상대 프로세스에 진입 기회 우선 부여.

3. 대기 조건:

   1 2	while flag[1 - i] and turn == 1 - i: pass # Busy Waiting

4. 임계 영역 실행:
   조건 충족 시 임계 영역 코드 실행.

5. 종료:
   flag[i] = False로 재설정.

이론적 검증

Python 구현 예시

 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

import threading

flag = [False, False]
turn = 0

def process_0():
    global flag, turn
    flag[0] = True
    turn = 1
    while flag[1] and turn == 1:
        pass
    print("Process 0 in critical section")
    flag[0] = False

def process_1():
    global flag, turn
    flag[1] = True
    turn = 0
    while flag[0] and turn == 0:
        pass
    print("Process 1 in critical section")
    flag[1] = False

# 스레드 실행
t0 = threading.Thread(target=process_0)
t1 = threading.Thread(target=process_1)
t0.start(); t1.start()
t0.join(); t1.join()

실행 결과:

1
2

Process 0 in critical section
Process 1 in critical section

결과는 실행 순서에 따라 변동 가능

장단점 분석

현대 시스템에서의 한계

1. 메모리 재배치 문제:
   CPU/컴파일러 최적화로 인해 코드 실행 순서 변경 가능 → volatile 키워드 필요.
2. 멀티코어 동기화 실패:
   캐시 일관성 문제로 인해 플래그 값 갱신 지연 → 메모리 배리어(Memory Barrier) 추가 필요.
3. 성능 저하:
   Busy Waiting이 CPU 자원을 지속 점유 → 세마포어(Semaphore)나 뮤텍스(Mutex)로 대체 권장.

교육적 가치

• 상호 배제 개념 학습: 임계 영역 문제의 3대 조건(상호 배제, 진행, 한정된 대기) 이해에 적합.
• 병행 프로그래밍 기초: 스핀락(Spinlock)과 소프트웨어 동기화 메커니즘의 원리 체험.
• 알고리즘 확장 모델: N-프로세스 버전(램포트 빵집 알고리즘)으로의 개념 확장 가능.

참고 및 출처