Syncronization Algorithms#
동기화 알고리즘은 병행 시스템에서 **상호 배제(Mutual Exclusion)**를 보장하기 위한 핵심 메커니즘이다.
데커 알고리즘 (Dekker’s Algorithm)#
목적: 2개 프로세스의 상호 배제
메커니즘:
flag 배열(진입 의사) + turn 변수(진입 순서)- 교착 상태 방지를 위한 플래그 재설정과 턴 변경
예시:
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
| class DekkerLock:
def __init__(self):
# 각 프로세스의 진입 시도를 나타내는 플래그
self.flag = [False, False]
# 현재 임계 영역을 사용할 차례인 프로세스 번호
self.turn = 0
def lock(self, process_id):
other = 1 - process_id # 다른 프로세스의 ID
# 진입 시도 표시
self.flag[process_id] = True
# 다른 프로세스가 진입 시도 중이면 대기
while self.flag[other]:
if self.turn != process_id:
# 자신의 차례가 아니면 진입 시도 포기
self.flag[process_id] = False
# 자신의 차례가 될 때까지 대기
while self.turn != process_id:
pass
# 다시 진입 시도
self.flag[process_id] = True
def unlock(self, process_id):
# 차례를 다른 프로세스에게 넘김
self.turn = 1 - process_id
# 진입 시도 표시 해제
self.flag[process_id] = False
|
피터슨 알고리즘 (Peterson’s Algorithm)#
목적: 2개 프로세스의 간단한 상호 배제
메커니즘:
flag 배열 + turn 변수 단일 관리- 데커 알고리즘보다 코드 복잡도 감소
예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class PetersonLock:
def __init__(self):
# 각 프로세스의 진입 의도를 나타내는 플래그
self.flag = [False, False]
# 현재 차례
self.turn = 0
def lock(self, process_id):
other = 1 - process_id # 다른 프로세스의 ID
# 진입 의도 표시
self.flag[process_id] = True
# 다른 프로세스에게 차례 양보
self.turn = other
# 다른 프로세스가 진입을 원하고
# 현재 다른 프로세스의 차례이면 대기
while self.flag[other] and self.turn == other:
pass
def unlock(self, process_id):
# 진입 의도 해제
self.flag[process_id] = False
|
램포트 빵집 알고리즘 (Lamport’s Bakery Algorithm)#
목적: N개 프로세스의 공정한 상호 배제
메커니즘:
- 번호표(
number[]) + choosing[] 플래그 - FIFO 공정성 보장
예시:
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
| class BakeryLock:
def __init__(self, n):
self.n = n # 프로세스 수
# 번호표 선택 중임을 나타내는 플래그
self.choosing = [False] * n
# 각 프로세스의 번호표 번호
self.number = [0] * n
def lock(self, process_id):
# 번호표 선택 과정 시작
self.choosing[process_id] = True
# 가장 큰 번호표 값보다 1 큰 값 선택
self.number[process_id] = max(self.number) + 1
self.choosing[process_id] = False
# 모든 다른 프로세스와 비교
for j in range(self.n):
# 다른 프로세스가 번호표 선택 중이면 대기
while self.choosing[j]:
pass
# 우선순위 비교하여 대기
while (self.number[j] != 0 and
(self.number[j] < self.number[process_id] or
(self.number[j] == self.number[process_id] and j < process_id))):
pass
def unlock(self, process_id):
# 번호표 반납
self.number[process_id] = 0
|
뮤텍스 (Mutex)#
목적: 범용 상호 배제
메커니즘:
- Lock/Unlock 기반의 하드웨어 지원 동기화
- 대기 큐를 사용한 Blocking 방식
예시:
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
| from threading import Lock
class MutexExample:
def __init__(self):
# 뮤텍스 객체 생성
self.mutex = Lock()
# 공유 자원
self.shared_resource = 0
def critical_section(self):
# 뮤텍스 잠금 획득
self.mutex.acquire()
try:
# 임계 영역 작업 수행
self.shared_resource += 1
print(f"Current value: {self.shared_resource}")
finally:
# 뮤텍스 잠금 해제
self.mutex.release()
# context manager를 사용한 더 안전한 방식
def better_critical_section(self):
with self.mutex:
self.shared_resource += 1
print(f"Current value: {self.shared_resource}")
|
각 알고리즘의 예시#
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
| # 데커 알고리즘 사용 예시
dekker = DekkerLock()
def process_dekker(pid):
for _ in range(5):
dekker.lock(pid)
# 임계 영역 작업
dekker.unlock(pid)
# 빵집 알고리즘 사용 예시
bakery = BakeryLock(3) # 3개 프로세스
def process_bakery(pid):
for _ in range(5):
bakery.lock(pid)
# 임계 영역 작업
bakery.unlock(pid)
# 피터슨 알고리즘 사용 예시
peterson = PetersonLock()
def process_peterson(pid):
for _ in range(5):
peterson.lock(pid)
# 임계 영역 작업
peterson.unlock(pid)
# 뮤텍스 사용 예시
mutex_example = MutexExample()
def process_mutex():
for _ in range(5):
mutex_example.better_critical_section()
|
종합 비교 분석#
| 기준 | 데커 알고리즘 | 피터슨 알고리즘 | 램포트 빵집 알고리즘 | 뮤텍스 |
|---|
| 지원 프로세스 수 | 2개 | 2개 | N개 | N개 |
| 동기화 방식 | 플래그 + 턴 변수 | 플래그 + 턴 변수 | 번호표 시스템 | Lock/Unlock |
| Busy Waiting | 사용 (CPU 자원 낭비) | 사용 | 사용 | 미사용 (대기 큐) |
| 공정성 | 턴 기반 순환 | 턴 기반 순환 | FIFO(선착순) | 구현 방식에 따라 다름 |
| 확장성 | 2개로 제한 | 2개로 제한 | 이론상 무제한 | 높음 |
| 하드웨어 지원 필요 | No | No | No | Yes (Atomic Operation) |
| 현대 시스템 적용 | 거의 없음 (교육용) | 거의 없음 | Linux ticket_spinlock | 광범위 (OS/DBMS 등) |
| 주요 단점 | 복잡한 조건 검사 | 2개 프로세스 한정 | 높은 메모리 오버헤드 | Context Switching 비용 |
바쁜 대기(Busy Waiting)
바쁜 대기는 프로세스나 스레드가 특정 조건이 만족될 때까지 계속해서 조건을 검사하면서 CPU 자원을 소비하며 대기하는 상태를 의미한다. 이는 마치 누군가가 문을 계속 두드리면서 열릴 때까지 확인하는 것과 유사하다.
적용 사례별 권장 알고리즘#
- 2개 프로세스 간단 동기화: 피터슨 알고리즘
- N개 프로세스 공정한 접근: 램포트 빵집 알고리즘
- 실제 시스템 구현: 뮤텍스 또는 세마포어
- 교육/이론 연구: 데커 알고리즘
참고 및 출처#