이번 주 범위: 프로세스 동기화, 교착 상태, 메모리 관리
1. 동기화가 필요한 이유
여러 프로세스나 스레드가 공유 데이터에 동시에 접근하면, 실행 순서에 따라 결과가 달라질 수 있다. 이렇게 접근 순서에 따라 결과가 달라지는 상황을 **경쟁 상태(Race Condition)**라고 한다. 경쟁 상태가 언제나 오류를 뜻하는 것은 아니지만, 적절히 제어하지 않으면 갱신 손실이나 데이터 불일치가 발생한다. 따라서 공유 데이터에 접근하는 실행 순서를 제어해 **일관성(Consistency)**을 보장하는 **동기화(Synchronization)**가 필요하다.
Race Condition: 실행 순서에 따라 결과가 달라질 수 있는 상황 Critical Section: 공유 데이터에 접근하여 Race Condition이 발생할 수 있는 코드 구간 Synchronization: 실행 순서와 접근을 제어하는 메커니즘
1.1 Race Condition이 발생하는 대표적인 상황
1) 커널 모드 실행 중 인터럽트가 발생하는 경우
count++은 실제로 load → add → store와 같은 여러 명령으로 실행될 수 있다. 값을 읽은 뒤 저장하기 전에 인터럽트가 발생해 인터럽트 처리 루틴이 같은 값을 변경하면, 복귀한 코드가 이전 값을 기준으로 저장하면서 인터럽트의 갱신을 덮어쓸 수 있다.
단일 프로세서의 커널에서는 해당 임계 구역 동안 인터럽트를 비활성화하는 방식으로 막을 수 있다. 다만 이 구간은 시스템 응답성을 떨어뜨리므로 반드시 짧아야 하며, 다른 CPU의 실행까지 막지는 못하므로 멀티프로세서 환경에서는 이것만으로 충분하지 않다.
2) 시스템 콜 수행 중 Context Switch가 발생하는 경우
사용자 프로세스의 주소 공간은 서로 분리되어 있지만, 시스템 콜을 수행하는 동안에는 여러 프로세스가 같은 커널 주소 공간의 데이터를 사용할 수 있다.
커널이 공유 데이터를 갱신하는 도중 선점되어 다른 프로세스가 같은 데이터에 접근하면 경쟁 상태가 발생할 수 있다. 이를 막기 위해 임계 구역에서 선점을 제한하거나 공유 데이터별로 락을 사용한다. 현대의 선점형 커널은 커널 전체를 비선점으로 만드는 대신 필요한 범위에 세밀한 동기화를 적용한다.
3) 멀티프로세서에서 공유 커널 데이터에 접근하는 경우
여러 CPU가 같은 값을 동시에 읽고 수정하면 마지막으로 저장한 값만 남아 갱신이 손실될 수 있다. 한 CPU의 인터럽트를 비활성화해도 다른 CPU는 계속 실행되므로 문제를 해결할 수 없다.
커널 전체에 하나의 락을 두는 방식은 단순하지만 병렬성을 크게 낮춘다. 일반적으로는 공유 데이터나 자료구조마다 락을 두어 필요한 범위만 보호한다.
1.2 애플리케이션에서 자주 보는 Race Condition
Read-Modify-Write
여러 스레드가 같은 값을 읽고 계산한 뒤 다시 쓰는 과정에서 서로의 변경을 덮어쓴다. 카운터 증가가 대표적인 예이며 원자적 연산이나 락이 필요하다.
Check-Then-Act
조건을 검사한 뒤 그 조건이 유지된다고 가정하고 행동하지만, 검사와 행동 사이에 다른 스레드가 상태를 바꿀 수 있다. 예를 들어 “파일이 없으면 생성한다”는 두 동작을 따로 수행하면 다른 스레드가 그 사이에 같은 파일을 만들 수 있다.
TOCTOU(Time-of-Check to Time-of-Use)
Check-Then-Act의 보안 취약점 형태다. 파일 권한이나 경로를 확인한 시점과 실제 사용하는 시점 사이에 공격자가 대상을 바꾸면 권한 상승이나 정보 노출로 이어질 수 있다. 검사와 사용을 하나의 원자적 연산으로 묶거나 안전한 파일 디스크립터 기반 API를 사용해 방지한다.
2. Critical Section Problem
**임계 구역(Critical Section)**은 공유 데이터나 자원에 접근하는 코드 구간이다. 올바른 해결책은 다음 세 조건을 만족해야 한다.
- Mutual Exclusion(상호 배제): 한 프로세스가 임계 구역을 실행 중이면 다른 프로세스는 동시에 진입할 수 없다.
- Progress(진행): 임계 구역이 비어 있고 진입하려는 프로세스가 있다면, 진입할 프로세스를 무기한 미루지 않고 선택해야 한다.
- Bounded Waiting(한정 대기): 진입 요청 후 다른 프로세스가 먼저 진입할 수 있는 횟수에 한계가 있어야 한다. 즉, 기아(Starvation)가 발생하지 않아야 한다.
3. 소프트웨어 기반 해결: Peterson’s Algorithm
Peterson 알고리즘은 두 프로세스 사이의 상호 배제를 설명하는 고전적인 소프트웨어 알고리즘이다. 각 프로세스의 진입 의사를 나타내는 flag와, 충돌할 때 누구에게 양보할지를 나타내는 turn을 사용한다.
// 프로세스 Pi, 상대 프로세스는 Pj
flag[i] = true;
turn = j;
while (flag[j] && turn == j) {
// busy waiting
}
// critical section
flag[i] = false;flag[i] = true: Pi가 임계 구역에 들어가고 싶다는 뜻이다.turn = j: 동시에 진입을 시도하면 Pj에게 우선권을 양보한다.while (flag[j] && turn == j): Pj도 진입을 원하고 Pj의 차례라면 기다린다.- 임계 구역을 빠져나오며
flag[i] = false로 진입 의사를 해제한다. 고전적인 순차 일관성 가정에서는 상호 배제·진행·한정 대기를 만족한다. 하지만 기다리는 동안 CPU를 계속 사용하는 Busy Waiting이 발생한다. 또한 현대 CPU와 컴파일러는 메모리 연산을 재배치할 수 있으므로 실제 코드에서는 메모리 배리어나 적절한 원자적 연산 없이 그대로 사용할 수 없다.
4. 하드웨어 지원: Atomic Instruction
현대 CPU는 읽기와 쓰기를 분리하지 않고 하나의 원자적 연산으로 수행하는 명령을 제공한다. 대표적으로 Test-and-Set과 Compare-and-Swap(CAS)가 있다.
while (test_and_set(&lock)) {
// busy waiting
}
// critical section
lock = false;원자적 명령을 이용하면 상호 배제를 간단히 구현할 수 있지만, 단순한 Test-and-Set 락은 공정성을 보장하지 않으므로 한정 대기 조건을 만족하지 않을 수 있다. 또한 락이 풀릴 때까지 반복 확인하므로 Busy Waiting이 발생한다.
5. Mutex와 Spinlock
**Mutex(Mutual Exclusion Lock)**는 한 번에 하나의 스레드만 임계 구역에 진입하도록 하는 상호 배제 도구다. 락 획득과 해제는 원자적으로 동작해야 한다.
구현에 따라 락 획득에 실패한 스레드는 잠들어 대기할 수도 있고 짧게 회전한 뒤 잠들 수도 있다. 따라서 Mutex 자체를 곧 Busy Waiting이라고 보는 것은 정확하지 않다.
반면 Spinlock은 락이 풀릴 때까지 반복 확인하며 기다리는 락이다.
- 임계 구역이 매우 짧고 락 보유자가 곧 실행을 끝낼 가능성이 높을 때 유리하다.
- 문맥 교환 비용을 피할 수 있지만 대기 중 CPU를 소모한다.
- 단일 CPU에서 락 보유자가 실행되지 못하는 상황이라면 비효율적이다.
- 멀티프로세서 커널의 짧은 임계 구역에서 주로 사용한다.
6. Semaphore
**세마포어(Semaphore)**는 정수 값과 두 원자적 연산으로 자원의 개수와 실행 순서를 제어하는 동기화 도구다.
wait(S)또는P(S): 자원을 요청한다. 사용할 수 없으면 대기한다.signal(S)또는V(S): 자원을 반납하거나 대기 중인 실행 흐름을 깨운다.
6.1 종류
- Counting Semaphore: 여러 개의 동일한 자원을 관리한다. 초기값은 사용 가능한 자원의 수다.
- Binary Semaphore: 값이 0과 1인 세마포어로 상호 배제에 사용할 수 있다.
Binary Semaphore와 Mutex는 완전히 같지 않다.
Mutex는 일반적으로 락을 획득한 스레드만 해제할 수 있는 소유권(Ownership) 개념이 있다. 세마포어는 다른 실행 흐름이 signal할 수 있어 자원 개수 제어뿐 아니라 작업 간 **신호 전달(Signaling)**에도 사용할 수 있다.
6.2 Busy Waiting과 Block/Wakeup
세마포어는 Busy Waiting 방식과 Block/Wakeup 방식 모두로 구현할 수 있다. 일반적인 운영체제의 세마포어는 기다리는 프로세스를 대기 큐에 넣어 재운 뒤, 자원이 생기면 깨우는 방식으로 CPU 낭비를 줄인다.
wait(S) {
S.value--;
if (S.value < 0) {
add this process to S.wait_queue;
block();
}
}
signal(S) {
S.value++;
if (S.value <= 0) {
remove a process P from S.wait_queue;
wakeup(P);
}
}이 표현에서는 음수 값의 절댓값이 대기 중인 프로세스 수를 나타낸다. wait와 signal 내부에서 세마포어 값과 대기 큐를 조작하는 부분 자체도 원자적으로 보호되어야 한다.
임계 구역이 매우 짧다면 sleep/wakeup과 문맥 교환 비용이 더 클 수 있으므로 Spinlock이 유리할 수 있고, 대기가 길다면 Block/Wakeup이 유리하다.
7. 고전적인 동기화 문제
7.1 Producer-Consumer Problem(Bounded-Buffer Problem)
생산자는 공유 버퍼에 데이터를 넣고 소비자는 데이터를 꺼낸다.
- 버퍼 접근은 한 번에 하나만 허용한다:
mutex = 1 - 빈 칸의 수를 센다:
empty = N - 채워진 칸의 수를 센다:
full = 0
// Producer
wait(empty);
wait(mutex);
insert_item();
signal(mutex);
signal(full);
// Consumer
wait(full);
wait(mutex);
remove_item();
signal(mutex);
signal(empty);mutex는 버퍼 자체를 보호하고, empty와 full은 생산자와 소비자의 실행 순서를 조정한다. 락 획득 순서를 잘못 배치하면 교착 상태가 발생할 수 있다.
7.2 Readers-Writers Problem
여러 Reader는 동시에 읽을 수 있지만 Writer가 쓰는 동안에는 다른 Reader와 Writer가 접근하면 안 된다.
- Reader 우선: Reader가 계속 들어오면 Writer가 기아 상태에 빠질 수 있다.
- Writer 우선: Writer가 계속 들어오면 Reader가 기아 상태에 빠질 수 있다.
- 공정한 방식: 도착 순서 등을 이용해 양쪽의 기아를 방지한다. 핵심은 데이터 일관성을 보장하면서 읽기의 병렬성을 최대한 허용하는 것이다.
7.3 Dining-Philosophers Problem
다섯 철학자가 식사하려면 양쪽 젓가락을 모두 획득해야 한다. 모든 철학자가 왼쪽 젓가락부터 하나씩 집으면 서로 오른쪽 젓가락을 기다리며 교착 상태에 빠질 수 있다.
대표적인 해결 방법은 다음과 같다.
- 동시에 테이블에 앉는 철학자를 4명으로 제한한다.
- 두 젓가락을 모두 얻을 수 있을 때만 획득한다.
- 짝수와 홀수 철학자의 젓가락 획득 순서를 다르게 한다.
- 젓가락에 전역적인 순서를 부여하고 항상 같은 순서로 획득한다.
8. Monitor와 Condition Variable
**모니터(Monitor)**는 공유 데이터와 그 데이터에 접근하는 프로시저, 동기화 규칙을 하나로 캡슐화한 고수준 동기화 구조다. 모니터 내부에서는 한 번에 하나의 스레드만 실행되도록 언어나 런타임이 상호 배제를 보장한다.
프로그래머가 매번 직접 wait(mutex)와 signal(mutex)를 배치하는 부담을 줄일 수 있지만, 실제 구현 내부에서는 여전히 락과 대기 큐 같은 저수준 기법이 사용된다.
Condition Variable은 특정 조건이 충족될 때까지 스레드를 재우고 깨우는 도구다.
condition.wait(): 호출한 스레드를 대기시키며 모니터 락을 원자적으로 반납한다. 깨어난 뒤 락을 다시 획득한다.condition.signal(): 대기 중인 스레드 하나를 깨운다.- 조건은 깨어난 뒤에도 바뀔 수 있으므로 일반적으로
if가 아니라while로 다시 검사한다.
세마포어와 조건 변수의 차이 세마포어는 값에 신호가 누적될 수 있지만 조건 변수는 상태 자체를 저장하지 않는다. 따라서 조건 변수는 항상 공유 상태를 나타내는 조건식과 락을 함께 사용해야 한다.
9. 교착 상태(Deadlock)
교착 상태는 여러 프로세스가 서로 상대방이 보유한 자원을 기다리면서, 어떤 프로세스도 더 이상 진행하지 못하는 상태다. 예를 들어 프로세스 P1이 자원 A를 획득한 뒤 B를 기다리고, P2가 B를 획득한 뒤 A를 기다리면 두 프로세스는 영원히 대기할 수 있다.
Deadlock과 Starvation의 차이
- Deadlock: 관련된 프로세스들이 서로를 기다려 모두 진행하지 못하는 상태
- Starvation: 특정 프로세스가 우선순위나 자원 배분 정책 때문에 계속 선택받지 못하는 상태
9.1 자원 사용 과정
프로세스는 일반적으로 다음 순서로 자원을 사용한다.
- Request: 자원을 요청한다. 사용할 수 없으면 대기한다.
- Use: 할당받은 자원을 사용한다.
- Release: 사용을 마친 자원을 반납한다. 운영체제의 자원은 CPU·메모리처럼 선점 가능한 자원과, Mutex·프린터처럼 사용 도중 강제로 회수하기 어려운 비선점 자원으로 나눌 수 있다. 교착 상태는 주로 비선점 자원에서 문제가 된다.
9.2 Deadlock의 필요조건: Coffman Conditions
다음 네 조건이 동시에 성립해야 교착 상태가 발생할 수 있다.
- Mutual Exclusion(상호 배제): 하나의 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
- Hold and Wait(점유 대기): 프로세스가 최소 하나의 자원을 가진 채 다른 자원을 기다린다.
- No Preemption(비선점): 다른 프로세스가 가진 자원을 강제로 빼앗을 수 없다.
- Circular Wait(순환 대기): 프로세스들이 원형으로 서로가 가진 자원을 기다린다.
네 조건은 교착 상태의 필요조건이다. 하나라도 깨뜨리면 교착 상태를 예방할 수 있지만, 네 조건이 모두 성립한다고 해서 매 순간 반드시 교착 상태인 것은 아니다.
9.3 Resource Allocation Graph
자원 할당 그래프는 프로세스와 자원의 관계를 방향 그래프로 표현한다.
P → R: 프로세스 P가 자원 R을 요청하고 있다.R → P: 자원 R이 프로세스 P에 할당되어 있다. 자원마다 인스턴스가 하나뿐일 때 그래프에 사이클이 있으면 교착 상태다. 자원 인스턴스가 여러 개라면 사이클은 교착 상태의 필요조건일 뿐 충분조건은 아니다.
9.4 Deadlock 처리 방법
1) Prevention(예방)
네 필요조건 중 하나가 성립하지 않도록 설계한다.
- Mutual Exclusion 제거: 공유 가능한 자원이라면 동시에 사용하도록 한다. 모든 자원에 적용할 수는 없다.
- Hold and Wait 제거: 필요한 자원을 한꺼번에 요청하거나, 새 자원을 요청하기 전에 가진 자원을 모두 반납한다.
- No Preemption 제거: 추가 자원을 얻지 못하면 보유 자원을 강제로 반납하게 한다. 상태를 쉽게 저장·복구할 수 있는 자원에 적합하다.
- Circular Wait 제거: 자원에 전역적인 순서를 부여하고 항상 오름차순으로 획득한다. 예방은 단순하지만 자원 이용률과 동시성을 낮추거나 기아를 유발할 수 있다.
2) Avoidance(회피)
자원을 할당한 뒤에도 시스템이 **안전 상태(Safe State)**에 남는 경우에만 할당한다. 이를 위해 각 프로세스의 최대 자원 요구량을 미리 알아야 한다.
- Safe State: 모든 프로세스를 완료시킬 수 있는 하나 이상의 안전 순서가 존재한다.
- Unsafe State: 현재 즉시 교착 상태라는 뜻은 아니지만, 이후 교착 상태에 빠질 가능성이 있다.
- Deadlock State: 실제로 프로세스들이 서로의 자원을 기다리며 진행하지 못한다.
Banker’s Algorithm
여러 인스턴스를 가진 자원에 사용하는 대표적인 회피 알고리즘이다.
Available: 현재 사용 가능한 자원 수Max: 각 프로세스가 최대로 요구할 자원 수Allocation: 각 프로세스에 현재 할당된 자원 수Need = Max - Allocation: 각 프로세스가 추가로 필요로 하는 자원 수 자원 요청이 들어오면 가상으로 할당한 뒤, 남은 자원으로 모든 프로세스가 특정 순서에 따라 완료될 수 있는지 검사한다. 안전 순서가 존재할 때만 실제로 할당한다.
3) Detection and Recovery(탐지와 회복)
교착 상태 발생을 허용한 뒤 주기적으로 탐지한다. 탐지 후에는 다음 방식으로 복구할 수 있다.
- 교착 상태에 관련된 프로세스를 하나 또는 전부 종료한다.
- 일부 프로세스에서 자원을 선점한다.
- 프로세스를 이전 체크포인트로 되돌린다. 희생 프로세스를 선택할 때는 우선순위, 수행한 시간, 남은 시간, 보유 자원 수, 재실행 비용 등을 고려한다. 같은 프로세스만 반복해 희생시키면 기아가 발생할 수 있다.
4) Ignore(무시)
교착 상태가 드물고 예방·탐지 비용이 더 크다고 판단하면 운영체제가 특별히 처리하지 않는다. 이를 흔히 Ostrich Algorithm이라고 부른다. 범용 운영체제는 일부 자원에 대해 이 접근을 취하며, 애플리케이션이 타임아웃이나 재시작으로 대응하기도 한다.
9.5 Dining Philosophers와 Deadlock
모든 철학자가 왼쪽 젓가락을 하나씩 집은 상황은 네 필요조건을 모두 만족한다.
| 필요조건 | Dining Philosophers에서의 모습 |
| Mutual Exclusion | 젓가락 하나를 한 철학자만 사용한다. |
| Hold and Wait | 왼쪽 젓가락을 든 채 오른쪽 젓가락을 기다린다. |
| No Preemption | 다른 철학자의 젓가락을 강제로 빼앗지 않는다. |
| Circular Wait | 각 철학자가 옆 철학자의 젓가락을 원형으로 기다린다. |
TLB Miss와 Page Fault는 다르다. TLB Miss는 변환 정보가 TLB에 없다는 뜻이며 페이지 테이블에는 있을 수 있다. Page Fault는 필요한 페이지 자체가 물리 메모리에 없다는 뜻이다.
페이지 테이블이 너무 커지는 문제를 줄이기 위해 계층적 페이지 테이블, 해시 페이지 테이블, 역 페이지 테이블 등을 사용할 수 있다.
10.5 Segmentation
세그멘테이션은 프로그램을 코드·데이터·스택·힙처럼 의미가 있는 가변 크기 단위인 Segment로 나눈다. 주소는 segment number + offset으로 구성된다.
- 장점: 논리 단위별 보호와 공유가 자연스럽다.
- 단점: 세그먼트 크기가 가변적이므로 외부 단편화가 발생할 수 있다.
| 구분 | Paging | Segmentation |
| 분할 기준 | 고정 크기 | 논리적 의미의 가변 크기 |
| 주소 | Page Number + Offset | Segment Number + Offset |
| 주요 단편화 | 내부 단편화 | 외부 단편화 |
| 장점 | 할당과 관리가 단순함 | 보호·공유가 논리 구조와 잘 맞음 |
| 알고리즘 | 기준 | 특징 |
| FIFO | 가장 먼저 적재됨 | 단순하지만 Belady’s Anomaly 가능 |
| Optimal | 앞으로 가장 늦게 사용됨 | 최적이지만 실제 구현 불가 |
| LRU | 가장 오래 사용되지 않음 | 성능이 좋지만 추적 비용이 큼 |
| Clock | Reference Bit | 낮은 비용으로 LRU 근사 |
