세마포어 (Semaphore) & 뮤텍스 (Mutex)
세마포어와 뮤텍스는 여러 프로세스나 스레드가 공유 자원에 동시에 접근하지 못하도록 출입을 관리하는 도구입니다. 경쟁 상태를 막기 위해 임계 구역 앞에 세워 두는 문지기라고 생각하면 됩니다.
한눈에 보기
- 비유: 뮤텍스는 화장실 열쇠 하나입니다. 열쇠를 가진 사람만 들어갈 수 있고, 다 쓰면 그 사람이 직접 열쇠를 돌려놓습니다.
- 세마포어는 주차장 입구의 "남은 자리 수" 전광판입니다. 자리가 3개면 3대까지 들어갈 수 있고, 0이 되면 다음 차는 자리가 날 때까지 기다립니다. 나가는 차가 있으면 숫자가 다시 올라갑니다.
- 정리하면 뮤텍스는 "딱 한 명만", 세마포어는 "정해진 수만큼"을 허용합니다.
임계 구역 (Critical Section)
여러 프로세스가 데이터를 공유하며 실행될 때, 각 프로세스에서 공유 데이터에 접근하는 코드 부분을 임계 구역이라고 합니다. 여럿이 동시에 이 부분을 실행하면 잘못된 결과가 나올 수 있으므로, 한 프로세스가 임계 구역을 실행하는 동안 다른 프로세스는 들어오지 못하게 해야 합니다.
임계 구역 문제를 올바르게 해결하려면 상호 배제, 진행, 한정 대기 세 가지 조건을 만족해야 합니다. 각 조건의 뜻은 경쟁 상태 글에 정리해 두었습니다.
세마포어 (Semaphore)
세마포어는 공유 자원에 동시에 접근할 수 있는 수를 정수 하나(S)로 관리하는 방법입니다. 네덜란드의 컴퓨터 과학자 다익스트라가 만들었습니다.
P 연산과 V 연산
세마포어는 두 가지 연산으로만 다룹니다.
| 연산 | 언제 | 하는 일 | 다른 이름 |
|---|---|---|---|
| P(S) | 임계 구역에 들어가기 전 | S가 0이면 기다리고, 1 이상이면 S를 1 줄이고 들어감 | wait, acquire |
| V(S) | 임계 구역에서 나올 때 | S를 1 늘려서 자원을 반납하고, 기다리는 프로세스를 깨움 | signal, release |
사용하는 모양은 이렇습니다.
P(S)
--- 임계 구역 ---
V(S)P와 V의 동작을 의사 코드로 쓰면 다음과 같습니다.
procedure P(S) # 처음 S 값은 1이라고 가정
while S == 0: # S가 0이면 1이 될 때까지 기다림
wait
S = S - 1 # S를 0으로 만들어 다른 프로세스가 못 들어오게 함
--- 임계 구역 ---
procedure V(S) # 지금 S는 0
S = S + 1 # S를 다시 1로 돌려 자리를 비움여기서 중요한 점이 하나 있습니다. P와 V는 각각 중간에 끊기지 않고 한 번에 실행되어야(원자적, atomic) 합니다. 만약 두 프로세스가 동시에 "S가 1이네" 하고 확인한 다음 둘 다 S를 줄이면, 둘 다 임계 구역에 들어가 버립니다. 그래서 운영체제는 P와 V를 실행하는 동안 인터럽트를 막거나, CPU가 제공하는 원자적 명령어를 써서 이 두 연산이 쪼개지지 않게 보장합니다.
예시로 따라가기
처음 S 값은 1이고, 같은 임계 구역을 실행하려는 프로세스 A와 B가 있다고 해 보겠습니다.
| 순서 | 일어나는 일 | S |
|---|---|---|
| 1 | 먼저 도착한 A가 P(S)를 실행, S를 0으로 만들고 임계 구역에 들어감 | 0 |
| 2 | 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이라서 기다림 | 0 |
| 3 | A가 임계 구역을 마치고 V(S)를 실행 | 1 |
| 4 | B가 기다림에서 빠져나와 S를 0으로 만들고 임계 구역에 들어감 | 0 |
바쁜 대기와 블록 방식
위 의사 코드처럼 while을 돌며 S를 계속 확인하는 방식을 바쁜 대기(busy waiting) 또는 스핀락이라고 합니다. 기다리는 동안에도 CPU를 계속 써서 낭비가 생깁니다.
그래서 실제 운영체제의 세마포어는 보통 기다리는 프로세스를 대기 큐에 넣고 잠재웁니다(block). 그리고 V가 실행될 때 큐에서 하나를 꺼내 깨웁니다(wakeup). 기다리는 시간이 아주 짧을 것으로 예상될 때는 잠들고 깨는 비용보다 잠깐 도는 게 싸서, 멀티 프로세서에서는 스핀락도 여전히 씁니다.
세마포어의 두 종류
| 종류 | S의 범위 | 쓰임 |
|---|---|---|
| 이진 세마포어 (Binary) | 0 또는 1 | 한 번에 하나만 들어가게 할 때 |
| 카운팅 세마포어 (Counting) | 0 이상의 정수 | 같은 자원이 여러 개 있을 때 (예: DB 연결 5개, 프린터 3대) |
코드로 보기: 카운팅 세마포어
자리가 2개인 방에 손님 6명이 들어가려고 합니다. 각자 0.1초씩 머뭅니다.
import threading
import time
seats = threading.Semaphore(2) # 동시에 2명까지만 들어갈 수 있는 방 (S = 2)
inside = 0
max_inside = 0
count_lock = threading.Lock()
def visitor(name):
global inside, max_inside
with seats: # P(S): 자리가 없으면 여기서 기다림
with count_lock:
inside += 1
max_inside = max(max_inside, inside)
time.sleep(0.1) # 방 안에서 일하는 시간
with count_lock:
inside -= 1
# 블록을 나가면 V(S): 자리 반납
start = time.time()
threads = [threading.Thread(target=visitor, args=(f"손님{i}",)) for i in range(6)]
for t in threads:
t.start()
for t in threads:
t.join()
print("동시에 방 안에 있던 최대 인원:", max_inside)
print(f"6명 모두 끝나는 데 걸린 시간: 약 {time.time() - start:.1f}초")실행 결과입니다.
동시에 방 안에 있던 최대 인원: 2
6명 모두 끝나는 데 걸린 시간: 약 0.3초6명이 한꺼번에 들어갔다면 0.1초, 한 명씩 들어갔다면 0.6초가 걸렸을 겁니다. 2명씩 세 번 나눠 들어가서 0.3초가 걸렸습니다.
뮤텍스 (Mutex)
뮤텍스는 임계 구역을 가진 스레드들의 실행 시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술입니다. 이름은 상호 배제(Mutual Exclusion)의 줄임말입니다.
두 가지 동작으로 접근을 조율합니다.
- lock: 임계 구역에 들어갈 권한을 얻습니다. 다른 스레드가 이미 임계 구역을 실행 중이면 끝날 때까지 기다립니다.
- unlock: 임계 구역을 다 썼다고 알립니다. 기다리던 다른 스레드가 들어갈 수 있게 됩니다.
코드로 보기: 경쟁 상태 고치기
경쟁 상태 글에서 4,000이 나와야 하는데 1,000 근처가 나왔던 예제에 락만 추가했습니다.
import threading
import time
balance = 0
lock = threading.Lock() # 뮤텍스: 한 번에 한 스레드만 통과
def deposit(times):
global balance
for _ in range(times):
with lock: # lock() ... 블록이 끝나면 자동으로 unlock()
current = balance # ---- 임계 구역 시작 ----
time.sleep(0)
balance = current + 1 # ---- 임계 구역 끝 ----
threads = [threading.Thread(target=deposit, args=(1000,)) for _ in range(4)]
for t in threads:
t.start()
for t in threads:
t.join()
print("기대값: 4000")
print("실제값:", balance)기대값: 4000
실제값: 4000여러 번 실행해도 항상 4,000이 나옵니다. with lock:을 쓰면 중간에 오류가 나도 락이 자동으로 풀려서, 락을 안 풀고 빠져나가는 실수를 막을 수 있습니다.
뮤텍스와 이진 세마포어의 차이
뮤텍스는 상태가 잠김/풀림 두 가지뿐이라 이진 세마포어라고 부르기도 합니다. 하지만 엄밀히 보면 중요한 차이가 있습니다.
| 비교 | 뮤텍스 | 이진 세마포어 |
|---|---|---|
| 주인 | 있음. 잠근 스레드만 풀 수 있음 | 없음. 아무나 V(S)를 할 수 있음 |
| 주된 목적 | 임계 구역 보호 (상호 배제) | 상호 배제 + 스레드끼리 "이제 해도 돼" 신호 보내기 |
| 허용 인원 | 1 | 1 (카운팅 세마포어는 여러 명) |
"주인이 있다"는 차이를 코드로 확인해 보겠습니다. Python의 threading.Lock은 단순한 락이라 주인 검사를 하지 않으므로, 주인을 기억하는 RLock으로 확인했습니다.
import threading
owned = threading.RLock() # 주인(잠근 스레드)을 기억하는 락
sem = threading.Semaphore(1) # 이진 세마포어 (값이 0 또는 1)
owned.acquire() # 메인 스레드가 잠금
sem.acquire() # 메인 스레드가 S를 1 -> 0으로
def other_thread():
sem.release() # 다른 스레드가 V(S)
print("세마포어: 다른 스레드가 풀어도 문제없음")
try:
owned.release() # 다른 스레드가 남의 락을 풀려고 함
except RuntimeError as e:
print("주인 있는 락: 주인이 아닌 스레드가 풀면 오류 ->", e)
t = threading.Thread(target=other_thread)
t.start()
t.join()세마포어: 다른 스레드가 풀어도 문제없음
주인 있는 락: 주인이 아닌 스레드가 풀면 오류 -> cannot release un-acquired lock세마포어는 주인이 없기 때문에 "생산자 스레드가 데이터를 만들면 V, 소비자 스레드는 P로 기다리기"처럼 서로 다른 스레드끼리 순서를 맞추는 신호로도 쓸 수 있습니다. 뮤텍스는 잠근 사람이 풀어야 하므로 이런 용도에는 맞지 않습니다.
뮤텍스 알고리즘
운영체제나 하드웨어의 도움 없이, 공유 변수만으로 상호 배제를 만드는 고전 알고리즘들이 있습니다. 실제로 쓰이기보다는 "상호 배제를 어떻게 보장하는가"를 이해하는 교과서 예제로 자주 나옵니다.
아래 코드는 모두 Python으로 다시 작성했고, 임계 구역에서 1을 더하는 작업을 반복해 실제로 실행해 봤습니다. (Python은 GIL 덕분에 메모리 읽기/쓰기 순서가 보장되어 이 알고리즘들이 그대로 동작합니다. C나 Java로 멀티코어에서 돌리면 CPU가 명령 순서를 바꿀 수 있어서 메모리 배리어나 volatile 같은 추가 장치가 필요합니다.)
1. 데커 (Dekker) 알고리즘
두 프로세스용입니다. flag와 turn 두 변수로 누가 임계 구역에 들어갈지 정합니다.
flag[i]: i번 프로세스가 임계 구역에 들어가고 싶어 하는지turn: 둘 다 들어가고 싶을 때 누구 차례인지
flag = [False, False]
turn = 0
def worker(i, times):
global turn
j = 1 - i # 상대방 번호
for _ in range(times):
flag[i] = True # 들어가고 싶다고 손들기
while flag[j]: # 상대도 손을 들고 있으면
if turn == j: # 그리고 상대 차례라면
flag[i] = False # 일단 손을 내리고
while turn == j: # 내 차례가 올 때까지 기다렸다가
pass
flag[i] = True # 다시 손들기
# ------- 임계 구역 -------
turn = j # 차례를 상대에게 넘기고
flag[i] = False # 손 내리기두 스레드가 1,000번씩 더하도록 돌려 보니 매번 2000이 나왔습니다.
2. 피터슨 (Peterson) 알고리즘
데커와 비슷하지만 더 간단합니다. 들어가기 전에 먼저 상대에게 차례를 양보하는 것이 차이입니다. 둘이 동시에 양보하면 나중에 양보한 쪽의 말이 turn에 남으므로, 먼저 양보한 쪽이 들어가게 됩니다.
flag = [False, False]
turn = 0
def worker(i, times):
global turn
j = 1 - i
for _ in range(times):
flag[i] = True # 들어가고 싶다고 표시
turn = j # "너 먼저 해" 하고 양보
while flag[j] and turn == j: # 상대가 원하고, 차례도 상대면 기다림
pass
# ------- 임계 구역 -------
flag[i] = False # 다 썼다고 알림이것도 두 스레드가 1,000번씩 더해서 매번 2000이 나왔습니다.
아래는 피터슨 알고리즘을 프로세스 하나의 입장에서 그린 순서도입니다. 위 코드와 줄마다 맞춰 보면 이렇습니다.
| 그림의 상자 | 위 코드 |
|---|---|
| I want to enter | flag[i] = True |
| It is not my turn | turn = j (상대에게 양보) |
| 마름모 두 개를 도는 고리 | while flag[j] and turn == j (바쁜 대기) |
| critical section | 임계 구역 |
| I don't want to enter | flag[i] = False |
그림 출처: Wikimedia Commons (Lpandelis, CC BY-SA 4.0)
3. 제과점 (Bakery) 알고리즘
빵집에서 번호표를 뽑는 방식입니다. 여러 프로세스(N개) 를 다룰 수 있고, 가장 작은 번호표를 가진 프로세스가 먼저 임계 구역에 들어갑니다.
- 번호표를 뽑는 순간이 겹치면 같은 번호가 나올 수 있습니다. 그때는 프로세스 번호가 작은 쪽이 먼저 들어갑니다.
- 번호표를 뽑는 중인 프로세스가 있으면, 그 번호가 정해질 때까지 기다렸다가 비교합니다.
N = 3
choosing = [False] * N # 번호표를 뽑는 중인지
number = [0] * N # 번호표 (0이면 들어갈 생각 없음)
def worker(i, times):
for _ in range(times):
choosing[i] = True
number[i] = max(number) + 1 # 지금 있는 번호 중 가장 큰 번호 + 1
choosing[i] = False
for j in range(N):
while choosing[j]: # j가 번호표를 뽑는 중이면 기다림
pass
# j가 번호표가 있고, (번호, 프로세스 번호)가 나보다 작으면 기다림
while number[j] != 0 and (number[j], j) < (number[i], i):
pass
# ------- 임계 구역 -------
number[i] = 0 # 번호표 반납(number[j], j) < (number[i], i)는 "번호표가 더 작거나, 번호표가 같으면 프로세스 번호가 더 작은가"를 한 번에 비교하는 식입니다. 스레드 3개가 500번씩 더하도록 돌려서 매번 1500이 나왔습니다.
세 알고리즘 비교
| 알고리즘 | 프로세스 수 | 핵심 아이디어 |
|---|---|---|
| 데커 | 2개 | 손들기(flag)와 차례(turn). 상대 차례면 손을 내리고 기다림 |
| 피터슨 | 2개 | 들어가기 전에 먼저 상대에게 양보 |
| 제과점 | N개 | 번호표가 작은 순서대로, 같으면 프로세스 번호 순서대로 |
주의할 점
- 락이나 세마포어를 잘못된 순서로 여러 개 잡으면 서로 기다리다 멈추는 데드락이 생길 수 있습니다.
- P만 하고 V를 빼먹으면 자리가 영영 반납되지 않아 다른 프로세스가 계속 기다립니다. Python의
with문처럼 자동으로 풀어 주는 문법을 쓰는 것이 안전합니다. - 락을 너무 넓게 걸면 스레드가 여러 개여도 사실상 한 줄로 서서 일하게 되어 느려집니다. 임계 구역은 꼭 필요한 부분만 짧게 잡습니다.
정리
| 개념 | 비전공자 버전 요약 |
|---|---|
| 임계 구역 | 공유 데이터를 건드리는 코드. 한 번에 정해진 수만 들어가야 함 |
| 세마포어 | 남은 자리 수(S)로 출입을 관리하는 주차장 전광판 |
| P / V 연산 | 들어갈 때 자리 하나 차지, 나올 때 자리 하나 반납 |
| 원자성 | P와 V는 중간에 끊기지 않고 한 번에 실행되어야 함 |
| 카운팅 세마포어 | 같은 자원이 여러 개일 때, 그 개수만큼 동시에 허용 |
| 뮤텍스 | 열쇠가 하나뿐인 화장실. 잠근 사람만 열 수 있음 |
| 이진 세마포어와 차이 | 뮤텍스는 주인이 있고, 세마포어는 아무나 풀 수 있음 |
| 데커 / 피터슨 | 두 프로세스가 손들기와 양보로 순서를 정함 |
| 제과점 알고리즘 | 번호표가 작은 순서대로 들어감 (N개 프로세스 가능) |