[Operating System] Peterson's Algorithm vs Binary Semaphore

Peterson's Algorithm vs Binary Semaphore

Peterson's Algorithm은 임계 구역 문제를 소프트웨어만으로 해결하기 위한 대표적인 알고리즘이다. 반면 Binary Semaphore는 운영체제가 제공하는 동기화 기법으로, 실제 시스템에서 상호 배제를 구현할 때 사용된다.

둘 다 Mutual Exclusion(상호 배제)를 보장한다는 공통점이 있지만 구현 방식과 사용 목적에는 큰 차이가 존재한다.

Peterson's Algorithm은 두 개의 프로세스가 공유 자원에 접근할 때 상호 배제를 보장하기 위해 설계된 알고리즘이다.

bool flag[2];
int turn;

두 개의 변수를 사용한다.

변수	의미
`flag[i]`	프로세스 `i`가 임계 구역 진입을 원하는지 나타낸다.
`turn`	충돌이 발생했을 때 양보할 프로세스를 나타낸다.

프로세스 i는 임계 구역 진입 전에 다음과 같은 코드를 수행한다.

flag[i] = true;
turn = j;

while(flag[j] && turn == j);

상대 프로세스도 진입을 원하고 있으며 상대방 차례라면 대기한다.

Peterson's Algorithm은 다음 세 가지 조건을 모두 만족한다.

하지만 다음과 같은 한계가 존재한다.

한계	설명
프로세스 수 제한	두 개의 프로세스만 지원한다.
Busy Waiting	대기 중에도 CPU를 계속 사용한다.
Memory Reordering	현대 CPU의 메모리 재정렬 환경에서는 그대로 사용하기 어렵다.

따라서 실제 운영체제보다는 임계 구역 문제의 개념을 설명하기 위한 교육용 알고리즘으로 사용된다.

Binary Semaphore는 값이 0 또는 1만 가질 수 있는 세마포어이다.

Semaphore mutex = 1;

임계 구역 진입 시

wait(mutex);

임계 구역 종료 시

signal(mutex);

를 수행한다.

동시에 하나의 프로세스만 임계 구역에 진입할 수 있으므로 Mutex와 유사하게 동작한다.

Binary Semaphore는 일반적으로 운영체제가 제공하는 대기 큐를 사용한다.

wait()
↓
진입 불가
↓
Sleep 상태
↓
signal()
↓
Wake Up

따라서 대기 중인 프로세스는 CPU를 소비하지 않는다.

Peterson's Algorithm은 Busy Waiting 기반으로 동작한다.

while(flag[j] && turn == j);

임계 구역에 진입할 수 있을 때까지 계속 조건을 검사한다.

대기
↓
조건 검사
↓
대기
↓
조건 검사

CPU를 지속적으로 사용하게 된다.

반면 Binary Semaphore는 진입이 불가능한 경우 프로세스를 Block 상태로 전환한다.

대기 큐 진입
↓
Sleep
↓
Wake Up

따라서 불필요한 CPU 사용이 발생하지 않는다.

Peterson's Algorithm

P1
P2

두 개의 프로세스만 고려한다.

Binary Semaphore

P1
P2
P3
...
Pn

여러 프로세스 및 스레드를 지원할 수 있다.

Peterson's Algorithm은 임계 구역 문제를 설명하기 위한 이론적 해결책에 가깝다.

반면 Binary Semaphore는 운영체제에서 실제로 제공하는 동기화 기법이며, 다양한 시스템 자원에 대한 접근 제어에 사용된다.

예를 들어 다음과 같은 곳에 활용된다.

사용 사례	설명
공유 버퍼	여러 스레드가 같은 buffer에 동시에 접근하지 못하게 한다.
파일 접근	파일을 동시에 수정하는 상황을 제한한다.
데이터베이스 연결	connection pool 접근 수를 제어한다.
프로세스 동기화	여러 프로세스의 실행 순서를 조절한다.

항목	Peterson's Algorithm	Binary Semaphore
구현 방식	Software Algorithm	OS Synchronization Primitive
프로세스 수	2개	여러 개
Busy Waiting	O	X
Sleep / Wake Up	X	O
Mutual Exclusion	O	O
Progress	O	구현에 따라 O
Bounded Waiting	O	구현에 따라 O
실제 사용	거의 없음	매우 많음

Peterson's Algorithm은 임계 구역 문제를 해결하는 대표적인 소프트웨어 알고리즘이며, Binary Semaphore는 이를 실제 시스템 환경에서 사용할 수 있도록 발전한 동기화 기법이라고 볼 수 있다.