동기화 (Synchronization)
도입 (Introduction)
운영체제에서 스레드를 지원하는 시스템에서는 실제로 스케줄링되는 단위가 프로세스가 아니라 커널 스레드(kernel thread)이다. 그럼에도 불구하고 "프로세스 스케줄링"과 "스레드 스케줄링"이라는 용어는 혼용되어 사용되며, 일반적인 스케줄링 개념을 설명할 때는 "프로세스 스케줄링"이라는 표현이 선호된다.
멀티프로그래밍(Multiprogramming)의 핵심 목표는 CPU 이용률을 최대화하는 것이다. 한 프로세스가 I/O 요청 때문에 대기해야 하면, CPU 제어권은 레디 큐(ready queue)에 있는 다른 프로세스에게 넘어간다. 이렇게 여러 프로세스/스레드가 동시에 실행되면서, 공유 자원에 대한 접근 문제가 발생하게 된다. 이것이 바로 동기화(Synchronization) 문제의 출발점이다.
배경: 생산자-소비자 문제 (Producer-Consumer Problem)
문제 설정
생산자-소비자 문제는 동기화의 가장 대표적인 예시이다. 두 스레드가 공유 버퍼(shared buffer)를 통해 데이터를 주고받는 상황을 가정한다.
공유 변수:
item buffer[BUFFER_SIZE]; // 고정 크기의 순환 버퍼
int in = 0; // 생산자가 다음에 넣을 위치
int out = 0; // 소비자가 다음에 꺼낼 위치
int counter = 0; // 현재 버퍼에 들어있는 아이템 수생산자 (Producer, Thread 0):
while (true) {
/* 아이템을 생산하여 nextProduced에 저장 */
while (counter == BUFFER_SIZE)
; // 버퍼가 가득 차면 대기 (busy-wait)
buffer[in] = nextProduced; // 버퍼에 데이터 삽입
in = (in + 1) % BUFFER_SIZE; // in 포인터를 순환 이동
counter++; // ⚠️ 공유 변수 증가
}소비자 (Consumer, Thread 1):
while (true) {
while (counter == 0)
; // 버퍼가 비어있으면 대기 (busy-wait)
nextConsumed = buffer[out]; // 버퍼에서 데이터 꺼냄
out = (out + 1) % BUFFER_SIZE; // out 포인터를 순환 이동
counter--; // ⚠️ 공유 변수 감소
/* nextConsumed에 있는 아이템을 소비 */
}핵심 포인트
counter라는 공유 변수를 생산자는 증가시키고(counter++), 소비자는 감소시킨다(counter--). 이 두 연산이 동시에 실행될 때 문제가 발생한다. 고급 언어에서 counter++는 한 줄이지만, 기계어 수준에서는 여러 명령어로 분해된다.
경쟁 조건 (Race Condition)
기계어 수준의 분해
counter++는 CPU에서 실제로 다음과 같이 3단계로 실행된다:
register1 = counter // ① LOAD: 메모리에서 레지스터로 값 로드
register1 = register1 + 1 // ② ADD: 레지스터 값에 1 더하기
counter = register1 // ③ STORE: 레지스터 값을 메모리에 저장counter--도 마찬가지로 3단계로 분해된다:
register2 = counter // ① LOAD
register2 = register2 - 1 // ② SUB
counter = register2 // ③ STORE여기서 register1과 register2는 각 스레드가 사용하는 로컬 CPU 레지스터이다. 컨텍스트 스위칭이 일어나면 이 레지스터 값들은 각 스레드의 TCB(Thread Control Block)에 저장되었다가 복원된다.
interleaving 시나리오 — 잘못된 결과
초기값: counter = 5이고, 생산자가 한 번 증가, 소비자가 한 번 감소하면, 기대 결과는 counter = 5이다.
시나리오 1: counter = 4가 되는 경우
| 시점 | 실행 주체 | 명령어 | 상태 |
|---|---|---|---|
| T0 | 생산자 | register1 = counter | register1 = 5 |
| T1 | 생산자 | register1 = register1 + 1 | register1 = 6 |
| T2 | 소비자 | register2 = counter | register2 = 5 (아직 counter 미갱신) |
| T3 | 소비자 | register2 = register2 - 1 | register2 = 4 |
| T4 | 생산자 | counter = register1 | counter = 6 |
| T5 | 소비자 | counter = register2 | counter = 4 ❌ |
소비자의 STORE가 마지막에 실행되어 생산자의 결과를 덮어써 버린다. 결과: counter = 4.
보면 원래 T1에서 T2로 갈 때 context swithcing이 일어나 버린다는 것 그래서 동기화 시켜줘야함
시나리오 2: T4와 T5 순서를 바꾸면 counter = 6
| 시점 | 실행 주체 | 명령어 | 상태 |
|---|---|---|---|
| T4 | 소비자 | counter = register2 | counter = 4 |
| T5 | 생산자 | counter = register1 | counter = 6 ❌ |
이번에는 생산자의 STORE가 마지막에 실행되어 결과가 6이 된다.
경쟁 조건의 정의
경쟁 조건(Race Condition): 여러 스레드(또는 프로세스)가 같은 데이터에 동시에 접근하고 조작할 때, 실행 순서(즉, 어떤 순서로 접근이 이루어지느냐)에 따라 결과가 달라지는 상황을 말한다.
핵심은 기계어 명령어 사이에 컨텍스트 스위칭이 끼어들 수 있다는 점이다. 고급 언어의 한 줄(counter++)이 원자적(atomic)으로 실행된다고 착각하면 안 된다.
임계 구역 문제 (Critical-Section Problem)
임계 구역이란?
임계 구역(Critical Section)은 여러 프로세스/스레드가 공유 메모리 또는 공유 자원에 접근하는 코드 영역이다. 위 예시에서 counter++와 counter--가 바로 임계 구역에 해당한다.
동기화란?
동기화(Synchronization)란 경쟁 조건(임계 구역 문제)을 해결하기 위한 프로토콜(또는 메커니즘)이다. 임계 구역의 진입과 퇴출을 제어하여, 한 번에 하나의 프로세스만 임계 구역을 실행하도록 보장한다.
임계 구역의 구조
코드는 논리적으로 4개의 영역으로 나뉜다:
┌─────────────────────┐
│ Entry Section │ ← 임계 구역 진입 허가를 요청하는 코드
├─────────────────────┤
│ Critical Section │ ← 공유 자원에 접근하는 코드
├─────────────────────┤
│ Exit Section │ ← 임계 구역에서 나왔음을 알리는 코드
├─────────────────────┤
│ Remainder Section │ ← 나머지 코드 (공유 자원과 무관)
└─────────────────────┘- Entry Section: 임계 구역에 들어가기 전에 "나 들어갈게"라고 요청하는 부분
- Exit Section: 임계 구역에서 나올 때 "나 나왔어"라고 알리는 부분
임계 구역 문제의 해결 조건 3가지
올바른 동기화 솔루션은 반드시 다음 3가지 조건을 모두 만족해야 한다:
상호 배제 (Mutual Exclusion)
프로세스 Pi가 자신의 임계 구역을 실행 중이면, 다른 어떤 프로세스도 자신의 임계 구역을 실행할 수 없다. 즉, 동시에 임계 구역을 실행하는 프로세스는 최대 1개이다.
비유: 화장실 칸이 하나뿐인 경우, 누가 안에 들어가 있으면 다른 사람은 기다려야 한다.
진행 (Progress)
어떤 프로세스도 임계 구역을 실행하고 있지 않은 상태에서, 임계 구역에 들어가고 싶은 프로세스가 있다면, 다음에 임계 구역에 들어갈 프로세스의 선택이 무한히 미뤄져서는 안 된다. 즉, 아무도 안에 없으면 들어가고 싶은 프로세스 중 하나는 반드시 들어갈 수 있어야 한다.
비유: 화장실이 비어있는데 아무도 못 들어가는 상황이 있으면 안 된다.
한정 대기 (Bounded Waiting)
한 프로세스가 임계 구역 진입을 요청한 후, 그 요청이 승인되기 전까지 다른 프로세스가 임계 구역에 들어갈 수 있는 횟수에 한계(bound)가 있어야 한다. 즉, 특정 프로세스가 영원히 기다리는 기아(starvation) 상태가 발생하면 안 된다.
비유: 줄을 서서 기다리는데, 내 앞으로 무한히 새치기가 되면 안 된다.
그림
Peterson's Solution (피터슨 해법)
개요
Peterson's Solution은 소프트웨어 기반 임계 구역 해결 방법이다. 하드웨어 지원 없이 순수 코드로 구현된다.
전제 조건:
- LOAD와 STORE 명령이 원자적(atomic)이라고 가정 (중간에 끊기지 않음)
- 2개 프로세스 솔루션 (P0, P1만 해당)
공유 변수
int turn; // 누구 차례인지 나타냄
Boolean flag[2] = {FALSE, FALSE}; // 각 프로세스가 진입 의사를 표시turn: 두 프로세스가 동시에 진입하려 할 때, 누구에게 양보할 것인지 결정flag[i]: 프로세스 Pi가 임계 구역에 들어갈 준비가 되었음을 표시 (TRUE = 준비 완료)
알고리즘
프로세스 Pi (i=0, j=1):
do {
flag[i] = TRUE; // ① "나는 들어갈 준비가 됐다"
turn = j; // ② "하지만 상대방에게 양보한다"
while (flag[j] && turn == j)
; // ③ 상대가 준비되어 있고, turn이 상대 차례이면 대기
/* Critical Section (임계 구역) */
flag[i] = FALSE; // ④ "나는 다 썼다, 나간다"
/* Remainder Section */
} while (TRUE);프로세스 Pj (j=1, i=0):
do {
flag[j] = TRUE; // "나는 들어갈 준비가 됐다"
turn = i; // "상대방에게 양보한다"
while (flag[i] && turn == i)
; // 상대가 준비되어 있고, turn이 상대 차례이면 대기
/* Critical Section */
flag[j] = FALSE;
/* Remainder Section */
} while (TRUE);
왜 동작하는가?
while 루프의 탈출 조건을 분석해보자. Pi가 while 루프를 빠져나가려면 두 조건 중 하나만 거짓이면 된다:
flag[j] == FALSE: Pj가 임계 구역에 관심이 없음 → Pi가 진입turn == i: turn이 Pi 차례임 → Pi가 진입
상호 배제 증명: 두 프로세스가 동시에 임계 구역에 있을 수 없다. turn 변수는 하나의 값만 가질 수 있으므로(i 또는 j), 둘 다 flag가 TRUE이더라도 turn 값에 의해 한쪽만 while 루프를 탈출한다.
진행 증명: 아무도 임계 구역에 없으면(flag[j] = FALSE), Pi는 while 조건의 첫 부분이 거짓이므로 즉시 진입한다. turn 값이 마지막에 쓴 쪽의 값으로 결정되므로, 동시 진입 시도 시에도 한 쪽이 반드시 통과한다.
한정 대기 증명: Pi가 임계 구역을 마치고 나올 때 flag[i] = FALSE로 설정한다. Pj가 대기 중이었다면, while 루프의 flag[i] 조건이 거짓이 되어 즉시 진입할 수 있다. Pi가 다시 진입하려면 turn = j로 설정해야 하므로, Pj에게 한 번은 기회가 주어진다. 즉, 최대 1회만 기다리면 된다.
동기화의 실제 구현: 락 (Lock)
락의 개념
락(Lock)은 임계 구역 문제를 해결하기 위한 범용 메커니즘이다. Peterson's Solution 같은 소프트웨어적 방법은 2개 프로세스에만 적용 가능하고, 현대 하드웨어의 명령어 재배열 등으로 인해 실제로는 잘 작동하지 않을 수 있다. 따라서 현대 운영체제는 락 관련 API를 제공한다.
┌─────────────────────┐
│ acquire lock │ ← 락 획득 (Entry Section 역할)
├─────────────────────┤
│ Critical Section │
├─────────────────────┤
│ release lock │ ← 락 해제 (Exit Section 역할)
├─────────────────────┤
│ Remainder Section │
└─────────────────────┘- Locking (잠금): 호출자가 락을 획득(acquire)하여 임계 구역에 진입
- Unlocking (해제): 호출자가 락을 해제(release)하여 임계 구역에서 퇴출
뮤텍스 (Mutex)
정의
Mutex는 "Mutual Exclusion"의 줄임말이다. 락(locks), 뮤텍스 락(mutex locks), 래치(latches)라고도 불린다.
뮤텍스는 두 가지 상태만 가지는 특수한 변수이다:
- Locked 상태: 특정 스레드가 뮤텍스를 소유(hold/own)하고 있음
- Unlocked 상태: 아무 스레드도 뮤텍스를 소유하지 않음
뮤텍스의 동작 원리
여러 스레드가 동시에 뮤텍스를 획득하려고 경쟁하면, 락을 얻지 못한 스레드는 블록(block)된다. 뮤텍스는 내부적으로 대기 큐(waiting queue)를 가지고 있어서, 블록된 스레드들이 이 큐에서 대기한다.
핵심 특성: 뮤텍스는 소유권(ownership) 개념이 있다. 락을 획득한 스레드만이 그 락을 해제할 수 있다. 이 점이 세마포어와의 중요한 차이점이다.
POSIX Mutex API
int pthread_mutex_init(pthread_mutex_t *mutex); // 뮤텍스 초기화
int pthread_mutex_destroy(pthread_mutex_t *mutex); // 뮤텍스 소멸
int pthread_mutex_lock(pthread_mutex_t *mutex); // 락 획득 (블로킹)
int pthread_mutex_trylock(pthread_mutex_t *mutex); // 락 시도 (논블로킹)
int pthread_mutex_unlock(pthread_mutex_t *mutex); // 락 해제pthread_mutex_lock(): 락이 사용 가능하면 즉시 획득, 이미 잠겨있으면 해제될 때까지 블록pthread_mutex_trylock(): 락이 사용 가능하면 획득, 이미 잠겨있으면 블록하지 않고 에러 반환 (논블로킹)
하드웨어 동기화: TestAndSet
원자적 명령어의 필요성
소프트웨어 솔루션의 한계를 극복하기 위해, 현대 CPU는 원자적(atomic) 하드웨어 명령어를 제공한다. 이 명령어는 실행 도중 인터럽트되지 않으며, 멀티프로세서 환경에서도 다른 CPU가 끼어들 수 없다.
TestAndSet 명령어
boolean TestAndSet(boolean *target) {
boolean old = *target; // ① 현재 값을 읽어서 저장
*target = TRUE; // ② 값을 TRUE로 설정
return old; // ③ 원래 값을 반환
}이 세 단계가 하나의 원자적 명령어로 실행된다. 즉, 중간에 다른 스레드가 끼어들 수 없다. 이것이 핵심이다.
동작 원리를 풀어 쓰면:
*target이 FALSE였으면 → FALSE를 반환하고,*target을 TRUE로 바꿈 → "락을 획득했다"*target이 TRUE였으면 → TRUE를 반환하고,*target은 여전히 TRUE → "락 획득 실패, 이미 잠겨있다"
스핀 락 (Spin Lock)
개요
스핀 락(Spin Lock)은 단순 락(simple lock) 또는 단순 뮤텍스(simple mutex)라고도 한다. TestAndSet 같은 원자적 CPU 명령어로 구현된다.
핵심 특성: 락을 획득할 수 없을 때, 스레드는 바쁜 대기(busy-wait, spin)를 한다. 즉, while 루프를 돌면서 계속 락 상태를 확인한다.
구현
Boolean lock = FALSE; // 공유 변수: FALSE = 사용 가능
// 락 획득 함수
void spin_lock(lock* lock) {
while (TestAndSet(lock))
; // lock이 TRUE(잠김)이면 계속 회전
}
// 락 해제 함수
void spin_unlock(lock* lock) {
*lock = FALSE; // 단순히 FALSE로 설정하여 해제
}사용 패턴:
do {
while (TestAndSet(&lock))
; // Entry Section: 락 획득 시도 (바쁜 대기)
/* Critical Section */
lock = FALSE; // Exit Section: 락 해제
/* Remainder Section */
} while (TRUE);스핀 락의 동작 흐름
- Thread 0이
TestAndSet(&lock)호출 → lock이 FALSE이므로 FALSE 반환, lock은 TRUE가 됨 → while 탈출 → 임계 구역 진입 - Thread 1이
TestAndSet(&lock)호출 → lock이 TRUE이므로 TRUE 반환 → while 계속 회전 (바쁜 대기) - Thread 0이
lock = FALSE실행 → 락 해제 - Thread 1의 다음
TestAndSet(&lock)호출 → lock이 FALSE이므로 → 임계 구역 진입
스핀 락의 장단점
장점: 구현이 매우 단순하다. 컨텍스트 스위칭 오버헤드가 없다 (블록하지 않으므로).
단점: CPU 시간을 낭비한다. 락을 기다리는 동안 while 루프를 돌면서 CPU를 계속 사용하기 때문에, 다른 스레드가 CPU를 쓸 수 없다. 특히 단일 CPU 시스템에서는 치명적이다.
세마포어 (Semaphore)
동기 부여
하드웨어 기반 솔루션(TestAndSet 등)은 응용 프로그래머가 직접 사용하기에는 복잡하다. 세마포어는 이를 추상화한 보다 쉬운 동기화 도구이다.
정의
세마포어(Semaphore)는 정수형 변수 S이며, 오직 두 가지 원자적(atomic, indivisible) 연산으로만 접근할 수 있다:
// P 연산 (Proberen = 테스트, 네덜란드어)
wait(int* pCount) {
while (*pCount <= 0)
; // 값이 0 이하이면 대기
(*pCount)--; // 값 감소 (토큰 하나 획득)
}
// V 연산 (Verhogen = 증가, 네덜란드어)
signal(int* pCount) {
(*pCount)++; // 값 증가 (토큰 하나 반환)
}원자적이란? 한 프로세스가 세마포어 값을 wait() 또는 signal()로 수정하는 동안, 다른 프로세스는 동시에 같은 세마포어 값을 수정할 수 없다.
세마포어의 종류
카운팅 세마포어 (Counting Semaphore):
- 정수 값이 무제한 범위를 가진다
- 유한한 개수의 동일 자원 접근을 제어하는 데 사용
- 초기값 = 사용 가능한 자원의 수
예시: 프린터가 3대 있으면, 세마포어를 3으로 초기화. wait()를 호출하면 값이 감소하여 프린터 하나를 사용하고, signal()을 호출하면 값이 증가하여 프린터를 반환한다.
이진 세마포어 (Binary Semaphore):
- 정수 값이 0과 1 사이만 가능
- 뮤텍스 락과 동일한 역할
- 초기값 = 1로 설정하여 상호 배제 구현
Semaphore S; // 1로 초기화
wait(&S); // 임계 구역 진입 (S: 1 → 0)
/* Critical Section */
signal(&S); // 임계 구역 퇴출 (S: 0 → 1)카운팅 세마포어 예시
공유 메모리 영역이 2개(Memory Region 0, Memory Region 1)이고, 3개의 태스크(tAccessTask 1, 2, 3)가 접근하려는 상황:
- 세마포어 초기값 = 2 (자원 2개)
- tAccessTask 1이
wait()→ S = 1, 성공 → Memory Region 0 사용 - tAccessTask 2가
wait()→ S = 0, 성공 → Memory Region 1 사용 - tAccessTask 3이
wait()→ S ≤ 0, 블록됨 → 대기 - tAccessTask 1이
signal()→ S = 1 → tAccessTask 3이 깨어나서 자원 사용
세마포어의 구현 — 바쁜 대기 문제
바쁜 대기 세마포어의 문제점
위에서 본 wait() 구현은 바쁜 대기(busy-waiting, spin)를 사용한다:
wait(int* pCount) {
while (*pCount <= 0)
; // ← CPU를 계속 소비하면서 루프!
(*pCount)--;
}문제: 한 스레드가 임계 구역을 실행하는 동안, 다른 스레드는 wait()의 while 루프를 돌면서 CPU 시간을 낭비한다. 타임 슬라이스(time quantum)가 만료될 때까지 아무 의미 없이 CPU를 점유하므로, 다른 스레드가 CPU를 사용할 기회를 빼앗긴다.
바쁜 대기 시나리오 (3개 스레드)
int lock = 1; // 전역 변수 (이진 세마포어)
// Thread 0 // Thread 1 // Thread 2
wait(&lock); // (1) 성공 wait(&lock); // (3) 바쁜대기 wait(&lock); // (4) 바쁜대기
for(i=0;i<150;i++) for(i=0;i<150;i++) for(i=0;i<150;i++)
count++; // (2),(5) count--; // (7),(9) count=count++; // (11)
signal(&lock); // (6) signal(&lock); // (10) signal(&lock); // (12)타임라인:
- Thread 0이
wait()성공 → 임계 구역 진입 (loop 0~99) - 타임 슬라이스 만료 → Thread 1으로 전환
- Thread 1이
wait()호출 → S = 0이므로 while 루프 회전 (바쁜 대기!) → CPU 낭비 - 타임 슬라이스 만료 → Thread 2로 전환
- Thread 2도
wait()호출 → while 루프 회전 → CPU 낭비 - Thread 0에게 다시 CPU → 나머지 임계 구역 실행 (loop 100~149) →
signal()호출
Thread 1과 Thread 2가 각각 한 타임 슬라이스 전체를 아무 일도 하지 않고 루프만 돌며 소비했다.
해결: 블록(Block)으로 대체
바쁜 대기 대신, 세마포어를 획득할 수 없을 때 스레드를 잠재우는(sleep/block) 방식으로 구현한다.
세마포어 구조체:
typedef struct {
int value; // 세마포어 값
struct thread* list; // 대기 큐 (waiting queue)
} semaphore;개선된 wait():
wait(semaphore* S) {
if (S->value <= 0) {
// 세마포어를 획득할 수 없으면:
add this thread to S->list; // ① 대기 큐에 추가
block(); // ② 스레드를 잠재움 (blocked 상태로 전환)
// + 레디 큐의 다른 스레드를 스케줄링
}
S->value--; // 토큰 감소
}개선된 signal():
signal(semaphore* S) {
S->value++; // 토큰 증가
if (S->value > 0) {
// 대기 중인 스레드가 있으면:
remove a thread T from S->list; // ① 대기 큐에서 꺼냄
wakeup(T); // ② 해당 스레드를 깨움 (ready 상태로 전환)
}
}블록 vs 바쁜 대기의 핵심 차이
| 구분 | 바쁜 대기 (Busy-Waiting) | 블록 (Block) |
|---|---|---|
| 대기 방식 | while 루프를 돌며 CPU 소비 | waiting queue에 들어가고 CPU 양보 |
| CPU 사용 | 대기 중에도 CPU 점유 | 대기 중 CPU 사용 안 함 |
| 상태 전이 | ready ↔ running | running → blocked → ready |
| 적합한 경우 | 락 보유 시간이 매우 짧을 때 | 락 보유 시간이 길 때 |
block() 함수는 호출한 스레드를 잠재우고(sleep), 레디 큐에 있는 다른 스레드를 CPU에 올린다. 이렇게 하면 CPU가 낭비되지 않는다.
블록 세마포어 시나리오
Semaphore sem.value = 1;- Thread 0이
wait(&sem)→ S = 0, 성공 → 임계 구역 진입 (loop 0~99) - 타임 슬라이스 만료 → Thread 1으로 전환
- Thread 1이
wait(&sem)→ S ≤ 0 → 대기 큐에 들어가고 블록됨 → CPU를 바로 반납 - Thread 2로 전환 → Thread 2도
wait(&sem)→ 블록됨 - Thread 0에게 다시 CPU → 나머지 임계 구역 실행 →
signal(&sem)→ S = 1, 대기 큐에서 Thread 1을 깨움 - Thread 1이 ready → running → 임계 구역 실행
핵심 차이: Thread 1, 2가 블록되면 CPU를 즉시 반납하므로, Thread 0이 더 빨리 CPU를 돌려받아 임계 구역을 마칠 수 있다. 전체 처리 시간이 단축된다.
세마포어 구조 및 내부 동작 (Implementation of Synchronization)
세마포어 제어 블록 (SCB)
세마포어는 운영체제 내부에서 세마포어 제어 블록(Semaphore Control Block, SCB) 구조체로 관리된다:
- Semaphore Name or ID: 세마포어 식별자
- Value: Binary(0 또는 1) 또는 Count(카운팅 값). 사용 가능한 토큰의 수를 나타냄
- Task-Waiting List: 해당 세마포어를 기다리고 있는 스레드들의 큐
스레드 대기 리스트 (Thread-Waiting List)
바쁜 대기 세마포어의 문제를 해결하기 위한 핵심 구조이다.
스레드가 사용 불가능한 세마포어를 획득하려 하면:
1. FIFO 순서 또는 우선순위 순서로 대기 리스트에 삽입된다
2. 스레드의 상태가 blocked 상태로 변경된다
3. 디스패처(dispatcher)가 레디 큐에서 실행 가능한 스레드를 선택하여 CPU에 올린다
세마포어 내부 동작 상세 (semTake / semGive)
실제 RTOS(예: VxWorks)에서 사용하는 API 스타일로 설명하면:
SEM_ID semMutex;
int main(void) {
semMutex = semBCreate(name); // 이진 세마포어 생성 (초기값 = 1, full)
ThreadSpawn("Thread1", ThreadFunc1); // 스레드 생성
ThreadSpawn("Thread2", ThreadFunc2);
}
// Thread 2 (세마포어를 먼저 획득한 상황)
void ThreadFunc2(void) {
semTake(semMutex); // 세마포어 획득 → value: 1 → 0
// critical section
semGive(semMutex); // 세마포어 반환
}
// Thread 3 (세마포어 획득 시도)
void ThreadFunc3(void) {
semTake(semMutex); // 세마포어 획득 시도 → value = 0이므로 블록!
// critical section
semGive(semMutex);
}동작 흐름:
(0) Thread 2가 이미 세마포어를 획득한 상태 (value = 0)
(1) acquire 시도: Thread 3이 semTake(2) 호출 → value = 0이므로 획득 불가
(2) Blocked 상태로 전이: Thread 3은 blocked 상태로 변경되고, 세마포어의 Thread waiting list에 추가됨
(3) 디스패치: 디스패처가 Thread ready list에서 실행 가능한 스레드(Thread 1 또는 Thread 2)를 선택하여 CPU에 올림
세마포어 해제 시 동작
세마포어가 다시 사용 가능해질 때(세마포어를 보유한 스레드가 semGive() 호출):
(1) 세마포어 value가 1로 증가
(2) 커널이 Thread waiting list의 첫 번째 스레드(FIFO 또는 최고 우선순위)에게 세마포어를 넘겨줌
(2') 깨어난 스레드가:
- 최고 우선순위이면 → 즉시 running 상태로 전환 (선점)
- 그렇지 않으면 → ready 상태로 전환되어 레디 큐에 들어감
데드락 (Deadlock)
데드락 예시
두 개의 세마포어 S와 Q가 있고 (둘 다 초기값 = 1), 두 스레드가 서로 반대 순서로 획득하려 할 때:
// Thread 0 // Thread 1
wait(S); // (1) S 획득 성공 wait(Q); // (2) Q 획득 성공
... ...
wait(Q); // (3) Q 획득 시도 wait(S); // (4) S 획득 시도
// → Q는 Thread 1이 // → S는 Thread 0이
// 보유 → 블록! // 보유 → 블록!
... ...
signal(S); signal(Q);
signal(Q); signal(S);Thread 0은 S를 가지고 Q를 기다리고, Thread 1은 Q를 가지고 S를 기다린다. 둘 다 상대방이 보유한 자원을 기다리므로 영원히 진행할 수 없다. 이것이 데드락이다.
데드락의 정의
데드락(Deadlock): 블록된 프로세스들의 집합에서, 각 프로세스가 자원을 하나 이상 보유하고 있으면서, 동시에 그 집합 내 다른 프로세스가 보유한 자원을 기다리고 있는 상태.
데드락 발생의 4가지 필요 조건
데드락은 다음 4가지 조건이 동시에 성립할 때만 발생한다:
① 상호 배제 (Mutual Exclusion)
한 자원을 한 번에 하나의 프로세스만 사용할 수 있다.
② 점유 대기 (Hold and Wait)
최소 하나의 자원을 보유한 상태에서, 다른 프로세스가 보유한 추가 자원을 획득하기 위해 대기한다.
③ 비선점 (No Preemption)
자원은 그것을 보유한 프로세스가 자발적으로만 해제할 수 있다. 강제로 빼앗을 수 없다.
④ 순환 대기 (Circular Wait)
프로세스들 {P0, P1, ..., Pn} 사이에 순환 고리가 존재한다: P0 → P1이 보유한 자원 대기, P1 → P2가 보유한 자원 대기, ..., Pn → P0이 보유한 자원 대기.
이 4가지 중 하나라도 깨뜨리면 데드락을 예방할 수 있다.
자원 할당 그래프 (Resource-Allocation Graph)
데드락을 시각적으로 분석하기 위한 방향 그래프이다.
표기법:
- 원 (○): 프로세스 Pi
- 사각형 (□): 자원 유형 Rj (내부 점 = 인스턴스 수)
- Pi → Rj (요청 간선): Pi가 Rj의 인스턴스를 요청 중
- Rj → Pi (할당 간선): Rj의 인스턴스가 Pi에 할당됨
데드락 판별:
- 그래프에 사이클이 없으면 → 데드락 없음
- 각 자원 유형이 1개 인스턴스만 가지고 있을 때 사이클이 있으면 → 데드락 확정
- 각 자원 유형이 여러 인스턴스를 가지고 있을 때 사이클이 있으면 → 데드락 가능성 (반드시는 아님)
핵심 개념 비교 요약
| 개념 | 핵심 | 대기 방식 | 소유권 | 값의 범위 |
|---|---|---|---|---|
| Peterson's Solution | SW 기반, 2프로세스 한정 | 바쁜 대기 | 없음 | flag + turn |
| Spin Lock | HW 명령어 기반 (TestAndSet) | 바쁜 대기 | 없음 | boolean |
| Mutex | OS 제공 API | 블록 | 있음 (소유자만 해제) | locked/unlocked |
| Binary Semaphore | 정수 값 0~1 | 블록 | 없음 (누구나 signal 가능) | 0, 1 |
| Counting Semaphore | 정수 값 0~N | 블록 | 없음 | 0 ~ N |
Semaphore Structure — 세마포어의 내부 구조
세마포어는 단순 정수가 아니다
세마포어를 "정수 변수"라고만 이해하면 절반만 아는 거다. 실제로 커널이 관리하는 세마포어는 Semaphore Control Block(SCB)이라는 구조체이며, 세 가지 핵심 필드를 갖는다.
Semaphore Control Block (SCB):
+-------------------------+
| Semaphore Name or ID | <-- 세마포어 식별자 (예: Sem ID = 2)
+-------------------------+
| Value | <-- 사용 가능한 토큰 수
| (Binary or Count) | Binary: 0 또는 1
+-------------------------+ Counting: 0 ~ N
| Task-Waiting List | <-- 이 세마포어를 기다리며 잠든 스레드들
| [Task 1]->[Task 2]->...|
+-------------------------+각 필드의 역할
| 필드 | 역할 |
|---|---|
| Name / ID | 세마포어를 구분하는 식별자. 시스템 내에서 유일 |
| Value | 현재 사용 가능한 "토큰" 수. 0이면 더 이상 들어갈 수 없음 |
| Task-Waiting List | 세마포어를 획득하지 못해 block된 스레드들의 대기열 |
Task-Waiting List — Busy-Waiting 문제의 해결책
Busy-waiting 세마포어에서는 wait()에서 while(value <= 0) 루프를 돌며 CPU를 낭비했다. Task-Waiting List는 이 문제를 해결한다.
Busy-waiting 방식 (나쁜 방식):
wait(S) {
while (S->value <= 0)
; // CPU를 계속 소비하면서 대기 (spinning)
S->value--;
}Task-Waiting List 방식 (좋은 방식):
wait(S) {
if (S->value <= 0) {
이 스레드를 S->list에 추가;
block(); // CPU를 반납하고 잠듦
}
S->value--;
}차이: block()을 호출하면 스레드가 CPU를 반납하고 잠들기 때문에, 다른 스레드가 CPU를 사용할 수 있다. Busy-waiting처럼 CPU를 헛돌리지 않는다.
대기열 정렬 방식
Task-Waiting List에 스레드를 넣는 순서는 두 가지 방식 중 하나를 사용한다:
| 방식 | 설명 | 장단점 |
|---|---|---|
| FIFO | 먼저 기다린 스레드가 먼저 획득 | 공정하지만 우선순위 무시 |
| 우선순위 순 | 가장 높은 우선순위 스레드가 먼저 획득 | 중요한 작업이 먼저 실행되지만 기아(starvation) 가능 |
Semaphore Internals — 세마포어 동작의 전체 흐름
코드 구조
슬라이드의 예시 코드를 정리하면:
/* Thread 1 (main): 세마포어 생성 및 스레드 생성 */
SEM_ID semMutex;
int main(void) {
semMutex = semBCreate(name); // Binary 세마포어 생성 (초기값 1)
ThreadSpawn("Thread2", ThreadFunc2, ...); // Thread 2 생성
ThreadSpawn("Thread3", ThreadFunc3, ...); // Thread 3 생성
...
}
/* Thread 2: 세마포어 사용 */
void ThreadFunc2(void) {
semTake(semMutex); // = wait() : 세마포어 획득 시도
// critical section
...
semGive(semMutex); // = signal() : 세마포어 반환
}
/* Thread 3: 세마포어 사용 */
void ThreadFunc3(void) {
semTake(semMutex); // = wait() : 세마포어 획득 시도
// critical section
...
semGive(semMutex); // = signal() : 세마포어 반환
}용어 매핑:
| 슬라이드 용어 | 교과서 용어 | 의미 |
|---|---|---|
| semBCreate | sem_init (binary) | 바이너리 세마포어 생성 |
| semTake | wait() / P() | 세마포어 획득 (토큰 가져감) |
| semGive | signal() / V() | 세마포어 반환 (토큰 돌려줌) |
시나리오: Thread 3이 이미 사용 중인 세마포어를 획득하려 할 때
초기 상태: Thread 2가 이미 세마포어를 획득한 상태 (Value = 0)
[Step 0] 초기 상태
- Thread 2가 semTake() 성공 -> Value = 1 에서 0으로
- Thread 2는 critical section 실행 중 (CPU 사용 중)
세마포어 SCB:
+------------+
| Sem ID = 2 |
| Value = 0 |
| List: 비어있음 |
+------------+
Thread ready list: [Thread 1] -> [Thread 3]
CPU: Thread 2 실행 중[Step 1] Thread 3이 semTake(2) 호출 (acquire 시도)
- Value = 0이므로 획득 실패!
[Step 2] Thread 3은 Blocked 상태로 전환되고, 세마포어의 Waiting List에 추가
세마포어 SCB:
+------------+
| Sem ID = 2 |
| Value = 0 |
| List: [Thread 3] |
+------------+
Thread waiting list: [Thread 3] <-- 잠듦
Thread ready list: [Thread 1]
CPU: ???
[Step 3] 디스패처가 ready list에서 다음 스레드를 선택하여 실행
Thread ready list: [Thread 1] -> CPU로 디스패치
CPU: Thread 1 실행전체 상태 그림:
+-------------------+
| 세마포어 (ID=2) |
| Value = 0 |
| Waiting: [Thread3]|<---- Thread 3 여기서 잠들어 있음
+-------------------+
Thread Ready List CPU
[Thread 1] -> [Thread 2] ---> [ ]
^
(3) ready list에서
꺼내서 실행Semaphore Internals (Cont'd) — 세마포어가 풀릴 때
시나리오: Thread 2가 semGive()를 호출할 때
Thread 2가 critical section을 끝내고 semGive(semMutex)를 호출한다.
[Step 1] semGive() 호출 -> Value++ -> Value = 0 에서 1로
세마포어 SCB:
+------------+
| Sem ID = 2 |
| Value = 1 | <-- 토큰이 반환됨!
| List: [Thread 3] |
+------------+[Step 2] Value > 0이 되었으므로, Waiting List의 첫 번째 스레드(Thread 3)를 꺼냄
커널이 판단:
- Thread 3의 우선순위가 현재 시스템에서 가장 높은가?
[Case A] Thread 3이 가장 높은 우선순위
-> Thread 3을 바로 Running 상태로 전환 (즉시 실행)
[Case B] Thread 3보다 우선순위가 높은 다른 스레드가 있음
-> Thread 3을 Ready 상태로 전환 (ready list에 넣고 나중에 실행)[Step 2의 결과] Thread 3이 가장 높은 우선순위인 경우:
세마포어 SCB:
+------------+
| Sem ID = 2 |
| Value = 0 | <-- Thread 3이 토큰을 가져가서 다시 0
| List: 비어있음 |
+------------+
Thread Ready List: [Thread 1] -> [Thread 2]
CPU: Thread 3 실행 중 (critical section 진입)전체 상태 전이도
semTake() 성공
Ready ─────────────────────> Running (Critical Section)
^ |
| | semGive() 호출
| v
| semTake() 실패 세마포어 반환
| (Value <= 0) |
| | | Waiting List의 첫 스레드를
| v | 꺼내서 Ready 또는 Running으로
| Blocked |
| (Waiting List에서 대기) <---+
| |
| | semGive()에 의해 깨어남
+---------+semTake / semGive 내부 동작 상세
semTake (= wait) 의사코드
semTake(semaphore* S) {
// [1] 인터럽트 비활성화 또는 spinlock 획득 (원자성 보장)
if (S->value <= 0) {
// [2] 토큰 없음 -> 현재 스레드를 대기 리스트에 추가
add_this_thread_to(S->waiting_list);
// [3] 현재 스레드를 Blocked 상태로 전환
block();
// [4] 디스패처가 ready list에서 다른 스레드를 선택하여 실행
// (이 스레드는 여기서 멈춰 있음 -- 나중에 깨어나면 여기부터 재개)
}
S->value--;
// [5] 인터럽트 재활성화 또는 spinlock 해제
}semGive (= signal) 의사코드
semGive(semaphore* S) {
// [1] 인터럽트 비활성화 또는 spinlock 획득 (원자성 보장)
S->value++;
if (S->value > 0 && waiting_list_not_empty(S)) {
// [2] 대기 리스트에서 스레드 T를 꺼냄
T = remove_first_from(S->waiting_list);
// [3] T를 깨움
wakeup(T);
// [4] T의 우선순위에 따라:
// - 가장 높으면 -> Running 상태
// - 아니면 -> Ready 상태 (ready list에 삽입)
}
// [5] 인터럽트 재활성화 또는 spinlock 해제
}전체 시나리오 통합 예시
3개 스레드의 세마포어 경쟁 (슬라이드 예시 기반)
초기 조건: Binary 세마포어 (Value = 1), Thread 1/2/3 존재
시간 -->
[T=0] Thread 2가 semTake() 호출
Value: 1 -> 0 (획득 성공)
Thread 2: Running (critical section)
Ready list: [Thread 1, Thread 3]
[T=1] Thread 3이 스케줄링되어 semTake() 호출
Value = 0 -> 획득 실패!
Thread 3: Blocked (waiting list로 이동)
Ready list: [Thread 1]
Waiting list: [Thread 3]
[T=2] Thread 1이 스케줄링되어 semTake() 호출
Value = 0 -> 획득 실패!
Thread 1: Blocked (waiting list로 이동)
Ready list: (비어있음... Thread 2만 실행 가능)
Waiting list: [Thread 3, Thread 1]
[T=3] Thread 2가 critical section 완료, semGive() 호출
Value: 0 -> 1
Waiting list에서 Thread 3을 꺼냄 (FIFO 또는 우선순위)
Thread 3: Ready -> Running (가장 높은 우선순위라면)
Value: 1 -> 0 (Thread 3이 토큰 가져감)
[T=4] Thread 3이 critical section 완료, semGive() 호출
Value: 0 -> 1
Waiting list에서 Thread 1을 꺼냄
Thread 1: Ready -> Running
Value: 1 -> 0 (Thread 1이 토큰 가져감)
[T=5] Thread 1이 critical section 완료, semGive() 호출
Value: 0 -> 1
Waiting list 비어있음 -> 아무도 안 깨움
세마포어 사용 가능 상태로 남음Time Slice(Quantum) 만료와 세마포어의 관계
핵심 원리
타이머 인터럽트에 의해 time slice가 만료되어 스레드가 쫓겨나도, 세마포어는 반환되지 않는다. signal()/semGive()를 명시적으로 호출해야만 세마포어가 풀린다.
Thread 0: [semTake][====루프 0~99====]타임아웃...[====루프 100~149====][semGive]
^ ^
쫓겨나도 세마포어 여기서야 반환
여전히 보유 중
Thread 1: [semTake -> block!]...........................[깨어남][====루프====][semGive]
Thread 2: [semTake -> block!]...............................[깨어남][====루프====]time slice 만료 시 동작 순서
[1] 타이머 인터럽트 발생 (quantum 소진)
[2] CPU가 현재 스레드의 레지스터를 PCB에 저장 (context save)
[3] 스케줄러가 ready queue에서 다음 스레드 선택
[4] 선택된 스레드가 semTake() 호출
-> Value = 0 (이전 스레드가 아직 들고 있음)
-> block()되어 waiting list로 이동
[5] 결국 세마포어를 들고 있는 원래 스레드가 다시 스케줄링됨
[6] 원래 스레드가 작업 완료 후 semGive() 호출
[7] waiting list의 스레드가 깨어남이것이 mutual exclusion이 보장되는 이유: time slice가 끝나서 스레드가 중간에 쫓겨나도, 세마포어를 들고 있으므로 다른 스레드는 critical section에 진입할 수 없다.
스레드 상태 전이 요약
생성
|
v
+-------+ dispatch +---------+ semTake 실패 +---------+
| Ready |----------->| Running |--------------->| Blocked |
| |<-----------| | | |
+-------+ preempt +---------+ +---------+
^ (time slice | |
| 만료) semGive() semGive()에
| (자신이 완료) 의해 깨어남
| | |
+------------------------+----------------------+| 전이 | 원인 | 세마포어 변화 |
|---|---|---|
| Ready -> Running | 디스패처가 선택 | 없음 |
| Running -> Ready | time slice 만료 (preempt) | 세마포어 보유 유지 |
| Running -> Blocked | semTake() 실패 (Value <= 0) | waiting list에 추가 |
| Blocked -> Ready/Running | 다른 스레드가 semGive() 호출 | waiting list에서 제거 |
핵심 개념 정리 (시험 대비)
빈출 키워드 요약
| 키워드 | 한 줄 정의 |
|---|---|
| SCB (Semaphore Control Block) | 세마포어의 실체. Name/ID, Value, Waiting List로 구성된 커널 구조체 |
| Value | 사용 가능한 토큰 수. Binary(0/1) 또는 Counting(0~N) |
| Task-Waiting List | 세마포어 획득에 실패하여 block된 스레드들의 대기열 |
| semTake / wait / P | 토큰 획득 시도. 없으면 block되어 waiting list로 이동 |
| semGive / signal / V | 토큰 반환. waiting list의 스레드를 깨움 |
| block() | CPU를 반납하고 Blocked 상태로 전환. busy-waiting 방지 |
| wakeup(T) | Blocked 스레드를 Ready 또는 Running으로 전환 |
| Binary Semaphore | Value가 0 또는 1만 가능. Mutex와 유사 |
| Counting Semaphore | Value가 0~N. 여러 스레드가 동시에 자원 접근 가능 |
| Busy-waiting | while 루프로 CPU를 소비하며 대기. 비효율적 |
| FIFO ordering | 먼저 기다린 스레드가 먼저 획득. 공정성 보장 |
| Priority ordering | 우선순위 높은 스레드가 먼저 획득. starvation 가능 |
| Mutual Exclusion | time slice 만료로 쫓겨나도 세마포어는 보유 유지되어 상호 배제 보장 |
Busy-waiting vs Blocking 세마포어 비교
| 비교 항목 | Busy-waiting | Blocking (Task-Waiting List) |
|---|---|---|
| 대기 방식 | while 루프 (spinning) | block()으로 잠듦 |
| CPU 사용 | 대기 중에도 CPU 100% 사용 | 대기 중 CPU 0% 사용 |
| 다른 스레드 실행 | 불가 (CPU를 점유) | 가능 (CPU 반납) |
| 구현 복잡도 | 단순 | waiting list 관리 필요 |
| 적합한 상황 | 매우 짧은 대기 (멀티코어 spinlock) | 긴 대기 (일반적 세마포어) |
| context switch 비용 | 없음 | 있음 (block/wakeup 시) |
시험 대비 체크포인트
- Race condition이 발생하는 이유: 고급 언어의 한 줄(
counter++)이 기계어에서는 LOAD → ADD → STORE의 3단계로 분해되고, 그 사이에 컨텍스트 스위칭이 끼어들 수 있기 때문 - 임계 구역 해결의 3가지 조건: Mutual Exclusion, Progress, Bounded Waiting — 세 개 모두 만족해야 올바른 솔루션
- Peterson's Solution의 turn 변수 역할: 두 프로세스가 동시에 진입하려 할 때 누가 양보할지 결정 (마지막에 turn을 쓴 쪽이 양보)
- 바쁜 대기 vs 블록의 차이: 바쁜 대기는 CPU를 잡고 루프를 돌고, 블록은 CPU를 반납하고 waiting queue에서 잠듦
- 세마포어 wait()/signal()의 원자성: 반드시 원자적으로 실행되어야 하며, 그렇지 않으면 세마포어 자체에 race condition 발생
- 데드락 4가지 조건: 상호 배제, 점유 대기, 비선점, 순환 대기 — 4개 모두 동시 성립해야 데드락 발생
- Mutex vs Semaphore: 뮤텍스는 소유권 개념이 있어서 락을 잡은 스레드만 해제 가능, 세마포어는 누구나 signal 가능
