1. Background
1.1 Race Condition
여러 프로세스가 공유 데이터(Shared data)에 동시에 접근하고 조작하면 데이터 불일치(Data inconsistency)가 발생할 수 있다.
Race condition: 공유 데이터의 최종 값이 어떤 프로세스가 마지막에 끝나느냐에 따라 달라지는 상황
1.2 Race Condition 예제
Memory: X = 2
CPU1 (P1): X = X + 1 CPU2 (P2): X = X - 1
P1: Load X, R1 P2: Load X, R2
Inc R1 Dec R2
Store X, R1 Store X, R2
명령어가 Interleave되면 결과가 달라진다:
- 정상적이면 X = 2 (증가 후 감소)
- Interleave되면 X = 1 또는 X = 3이 될 수 있음
해결책: 동시(Concurrent) 프로세스를 동기화(Synchronize)해야 한다
2. Critical-Section Problem
2.1 정의
n개의 프로세스가 공유 데이터를 사용하기 위해 경쟁할 때, 공유 데이터에 접근하는 코드 영역을 Critical section(임계 영역)이라 한다.
do {
entry section // 진입 허가 요청
critical section // 공유 데이터 접근
exit section // 퇴출 처리
remainder section // 나머지 코드
} while (1);
문제: 한 프로세스가 Critical section에서 실행 중이면, 다른 프로세스는 자신의 Critical section에서 실행할 수 없도록 보장해야 한다.
2.2 해결 조건 (3가지 필수)
| 조건 | 설명 |
|---|---|
| Mutual Exclusion (상호 배제) | Pi가 Critical section에서 실행 중이면, 다른 프로세스는 자신의 Critical section에 진입할 수 없다 |
| Progress (진행) | Critical section에 아무도 없고, 진입하고 싶은 프로세스가 있으면, 진입할 프로세스의 선택이 무한히 연기되어서는 안 된다 |
| Bounded Waiting (한정 대기) | 프로세스가 Critical section 진입을 요청한 후, 그 요청이 허가되기 전에 다른 프로세스가 Critical section에 진입하는 횟수에 한계(Bound)가 있어야 한다 |
3. Critical Section 알고리즘 (두 프로세스)
3.1 Algorithm 1 - Turn 변수
// Shared variable
int turn = 0; // initially 0
// Process P0
do {
while (turn != 0) ; /* 내 차례가 아니면 대기 */
critical section
turn = 1; /* 상대방 차례로 넘김 */
remainder section
} while (1);- Mutual exclusion: 충족
- Progress: 불충족 - Swap-turn 방식이라 두 프로세스가 반드시 번갈아 실행해야 함. P0이 더 자주 실행해야 하는데 P1이 실행하지 않으면 P0도 진입 못함
3.2 Algorithm 2 - Flag 배열
// Shared variables
boolean flag[2] = {false, false};
// Process Pi
do {
flag[i] = true; /* 나 들어가겠다고 선언 */
while (flag[j]) ; /* 상대도 들어가려 하면 대기 */
critical section
flag[i] = false; /* 나 나왔다 */
remainder section
} while (1);- Mutual exclusion: 충족
- Progress: 불충족 -
flag[i] = flag[j] = true가 동시에 발생하면 둘 다 영원히 대기 (Deadlock)
3.3 Algorithm 3 - Peterson’s Algorithm
Algorithm 1과 2의 공유 변수를 결합한 올바른 해법:
// Shared variables
boolean flag[2] = {false, false};
int turn;
// Process Pi
do {
flag[i] = true; /* 나 들어갈 의도 있다 */
turn = j; /* 상대방 차례로 양보 */
while (flag[j] && turn == j) ; /* 상대방도 원하고 상대방 차례면 대기 */
critical section
flag[i] = false;
remainder section
} while (1);- 3가지 조건 모두 충족
- 두 프로세스 문제를 정확히 해결
- 세 개 이상의 프로세스로 쉽게 확장 가능
- 단점: Busy waiting - 대기 중에도 CPU를 사용함
4. Lock 기반 해결
do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);문제: 특정 순간에 하나의 프로세스만 Lock을 획득하도록 어떻게 보장할 것인가?
5. Synchronization Hardware
5.1 하드웨어 지원
- Uniprocessor: Interrupt를 비활성화하면 선점이 불가능 - 간단하지만 Multiprocessor에서는 비효율적
- 현대 하드웨어: Atomic(Non-interruptible) 명령어 제공
5.2 Test-and-Set
메모리의 값을 원자적(Atomically)으로 테스트하고 수정:
boolean TestAndSet(boolean &target) {
boolean rv = target; // 원래 값을 반환값에 저장
target = true; // 무조건 true로 설정
return rv; // 원래 값 반환
}Test-and-Set을 이용한 Mutual Exclusion:
// Shared data
boolean lock = false;
// Process Pi
do {
while (TestAndSet(lock)) ; // lock이 false였으면 -> true로 바꾸고 진입
// lock이 true였으면 -> 계속 대기
critical section
lock = false; // 나올 때 풀어줌
remainder section
}5.3 Swap
두 변수를 원자적으로 교환:
void Swap(boolean &a, boolean &b) {
boolean temp = a;
a = b;
b = temp;
}Swap을 이용한 Mutual Exclusion:
// Shared data
boolean lock = false;
// Process Pi
do {
key = true; // 내 의도 = 진입하고 싶다
while (key == true)
Swap(lock, key); // lock과 key를 교환
// lock이 false였으면 -> key=false가 되어 루프 탈출, lock=true
critical section
lock = false;
remainder section
}6. Semaphore
6.1 정의
Semaphore S는 정수형 변수로, 두 가지 원자적(Atomic) 연산으로만 접근할 수 있다:
P(S): // wait
while (S <= 0) do no-op; // 양수가 될 때까지 대기 (busy-wait)
S--; // 감소시키고 진입
V(S): // signal
S++; // 증가6.2 동기화 도구로서의 Semaphore
두 프로세스 간 실행 순서 제어:
Pi의 영역 A가 Pj의 영역 B보다 먼저 실행되어야 할 때:
Semaphore S = 0;
Pi: Pj:
A (critical section) P(S) <- S가 양수가 될 때까지 대기
V(S) <- S 증가 B (critical section)
6.3 n개 프로세스의 Critical Section
// Shared data
semaphore mutex = 1; // 초기값 1: 아무도 CS에 없음
// Process Pi
do {
P(mutex); // 양수면 감소시키고 진입, 0이면 대기
critical section
V(mutex); // 증가시켜 다음 프로세스가 진입 가능하게 함
remainder section
} while (1);6.4 Semaphore 구현
P()와 V()는 그 자체로 Critical section 문제를 가진다 - 같은 Semaphore에 대해 두 프로세스가 동시에 P()와 V()를 실행하면 안 된다.
Busy waiting 방식의 문제:
- 구현 코드가 짧고, Critical section이 짧으면 대기 시간이 적음
- 하지만 애플리케이션이 Critical section에서 오래 머물면 P()에서 오래 대기 - 비효율적
6.5 Block/Wakeup 구현
Busy waiting 대신 프로세스를 Block시키는 방식:
typedef struct {
int value; // Semaphore 값
struct process *L; // 대기 프로세스 Queue
} semaphore;P(S):
S.value--; // 일단 감소
if (S.value < 0) { // 음수면 진입 불가
add this process to S.L; // 대기 큐에 추가
block; // 프로세스 Block (Waiting 상태)
}
V(S):
S.value++; // 증가
if (S.value <= 0) { // 대기 중인 프로세스가 있으면
remove a process P from S.L; // 대기 큐에서 꺼내서
wakeup(P); // Ready 상태로 전환
}Block/wakeup 방식에서 S.value의 절대값이 음수이면, 그 절대값은 대기 중인 프로세스 수를 나타낸다.
7. OS에서 Critical Section 문제가 발생하는 경우
7.1 Interrupt Handler vs Kernel
Kernel이 커널 변수(count)를 수정하는 중에 Interrupt가 발생하여 Interrupt handler가 같은 변수를 수정하면 Race condition 발생.
해결: Kernel 변수 접근 중에 Interrupt를 Disable/Enable
7.2 Kernel Mode에서의 Preemption
프로세스가 System call을 수행하며 Kernel mode에서 커널 데이터에 접근하는 중에 CPU가 선점되면 Race condition 발생.
해결: Kernel mode 실행 중에는 CPU를 선점하지 않음 - UNIX는 System call이 끝날 때까지(Kernel을 빠져나올 때까지) 대기
7.3 Multiprocessor
여러 CPU가 메모리의 같은 커널 변수에 동시 접근하면 Race condition 발생. Interrupt disable/enable로는 해결 불가.
해결:
- 전체 Kernel을 하나의 큰 Critical section으로 취급 - 한 번에 하나의 CPU만 Kernel에 진입 (성능 저하)
- 각 커널 공유 변수마다 개별 Semaphore로 보호 - Kernel이 여러 작은 Critical section으로 나뉨 (더 효율적)