Race Condition이란, 여러 개의 프로세스가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과값이 달라질 수 있는 현상이다.
이 한 문장이 race condition에 대한 모든 것이다. Race condition을 번역하면 '경쟁 상태'라고 한다. 영어 쓰기가 귀찮아서 앞으로 경쟁 상태로 부르도록 하겠다. 경쟁 상태는 컴퓨터 입장에서 아주 큰 문제다. 왜 큰 문제냐? 똑같은 코드를 100번 돌리면 실행 결과가 항상 같아야 하는데, 경쟁 상태가 발생하면 결과가 달라질 수 있기 때문이다. 이러한 문제를 방지하기 위해 공유 메모리를 쓰는 프로세스끼리 '동기화'를 해줘야 한다. 정리하면 공유 메모리를 쓰는 프로세스끼리는 경쟁상태가 발생할 수 있는데, 이에 대한 해결책이 동기화다.
Race Condition 예시
Producer-Consumer 상황을 생각해보자. Producer는 공유 메모리에 데이터를 쓰는 쓰레드고, consumer는 공유 메모리에서 데이터를 가져가는 쓰레드다. 아래 코드가 딱 그런 상황이다.
int counter = 0; // 전역 변수
item nextProduced;
item nextConsumed;
// PRODUCER thread
while(TRUE){
while(counter == BUFFER_SIZE);
buffer[in] = newxtProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
// CONSUMER thread
while(TRUE){
while(counter == 0);
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}
다른 부분은 제쳐두고 counter++, counter-- 부분만 보자. 만약에 두 쓰레드가 counter++, counter--를 각각 실행했다고 가정해보자. 순서는 상관없다. 아래와 같은 상황에서 counter의 결과값이 항상 3임을 보장할 수 있을까?
counter = 3
counter++; // Producer thread
counter--; // Consumer thread
counter = 3 ??
그렇지 않다. 왜냐하면 counter++, counter--은 세 가지 assembly code로 이루어져 있기 때문이다. 단계는 각각 아래와 같다.
// counter++
register1 = counter // load from memory
register1 = register + 1
counter = register1 // store in memory
// counter--
register2 = counter // load from memory
register2 = register - 1
counter = register2 // store in memory
counter++, counter--이 차례대로 실행되는 과정을 다시 한번 풀어 써보자. 코드는 아래와 같다.
T0: producer execute register1 = counter {register1 = 3}
T1: producer execute register1 = register1 + 1 {register1 = 4}
T2: producer execute counter = register1 {counter = 4}
T3: consumer execute register2 = counter {register2 = 4}
T4: consumer execute register2 = register2 - 1 {register2 = 3}
T5: consumer execute counter = register2 {counter = 3}
counter의 값이 3이 되는 경우는 T0~T5가 순서대로 실행될 때다. 그러나 producer와 consumer는 서로 다른 쓰레드다. 만약에 T1 수행 중에 context switch가 일어나 T3이 실행된다면? 아래의 경우를 한번 살펴보자
T0: producer execute register1 = counter {register1 = 3}
T1: producer execute register1 = register + 1 {register1 = 4}
context switch P1 → P2
T2: consumer execute register2 = counter {register2 = 3}
T3: consumer execute register2 = register2 - 1 {register2 = 2}
context switch P2 → P1
T4: producer execute counter = register1 {counter = 4}
context switch P1 → P2
T5: consumer execute counter = register2 {counter = 2}
counter의 최종값이 2가 되었다. 이렇게 실행 순서에 따라 순서가 달라지는 현상을 경쟁 상태(race condition)라고 한다. 경쟁 상태의 근본적인 원인은 다시 한번 말하지만 '메모리 공유'다!
경쟁상태의 해결방안 : 동기화
경쟁상태는 메모리를 공유하기 때문에 발생한다!! 해결 방안은? 동기화!!
counter 예시에서 경쟁상태가 발생하지 않게 하는 방법이 있다. 바로 '쓰레드의 순차적 실행'을 보장해주면 된다. 이것을 '동기화'라고 부른다. 조금만 더 자세하게 들어가보자. 순서를 보장해주기 위해서는 한 가지 장치만 있으면 된다.
모두 살면서 한 번쯤은 옷을 살때 탈의실에서 옷을 갈아입은 적이 있을 것이다. 갑자기 이 말을 하는 이유는, 탈의실만한 비유가 없기 때문이다. 우리는 탈의실을 사용할 때 아래의 한 가지 규칙을 항상 지키고 있다.
- 탈의실에는 오직 한 명만 들어갈 수 있다
이 규칙 어겨본 사람 있는지..? 옷 갈아입다가 다른 사람이 비집고 들어와서 어쩔 수 없이 상의탈의한 채로 밖에서 기다리는 사람은 없다. 탈의실에 한번 들어가면 옷을 벗든지 입든지 일단 모든 과정이 끝나기 전까지 나오지 않는 것은 확실하다.
여기서 단어만 조금 바꿔주자. 동기화에서 탈의실을 'critical section(임계 구역)'이라고 한다. 그리고 오직 한 명만 들어갈 수 있는 것을 'mutually exclusive(상호 배제)'라고 한다.
뭔가 영어가 더 직관적이라 영어로도 적어놨다.
Q: How can we avoid the race condition?
A: We must synchronize the execution of the threads. Need to guarantee mutually exclusive access to critical sections.
임계구역(Critical Section)
임계구역은 특별한 게 아니라 그냥 코드의 일부일 뿐이다. 경쟁상태가 발생할 수 있는 코드의 조각들을 임계구역으로 이해하면 된다. 쓰레드 또는 프로세스간 공유하고 있는 변수가 있는 코드 조각으로 이해해도 된다. counter 예시에서 counter의 세 단계가 임계구역이 된다. 그리고 counter 예시와 같이 임계구역에서 경쟁상태가 발생한 것을 '임계구역 문제(Critical Section Problem)'라고 부른다. 임계구역 문제를 해결한다는 것은 경쟁상태를 해결한다는 것과 같은 말이다.
임계구역은 아래의 세 가지 요구조건을 만족시켜야 유효한 알고리즘이 된다. 생각해보면 당연한 것들이다.
1. Mutual Exclusion(상호 배제) → 하나의 자원에는 하나의 프로세스만 접근할 수 있어야 한다
2. Progress(진행) → 임계구역이 비었으면 자원을 사용할 수 있어야 한다(deadlock free)
3. Bounded Waiting(한계 대기) → 존버하면 언젠가는 임계구역에 진입할 수 있어야 한다(starvation free)
임계구역은 일반적으로 아래와 같은 구조로 이루어져있다.
do{
/*
entry section (진입 구역)
*/
/*
critical section (임계 구역)
*/
/*
exit section (퇴출 구역)
*/
/*
remainder section (나머지 구역)
*/
} while(TRUE)
다음 시간에는 Critical Section Problem을 해결하는 세 가지 방법에 대해 다뤄볼 예정이다. 모두 기본적으로 위와 같은 임계구역 구조를 가지며 임계구역의 세 가지 요구조건을 만족한다. 설명은 다음 글에서!
- Software C.S : Peterson's Solution
- Hardware C.S : Mutex Locks
- Semaphores
'CS > 운영체제' 카테고리의 다른 글
| [ 운영체제 ] 동기화 방법2 - TestAndSet(), Mutex Locks (0) | 2022.01.25 |
|---|---|
| [ 운영체제 ] 동기화 방법1 - Peterson's Solution (0) | 2022.01.25 |
| [ 운영체제 ] CPU Burst Prediction (0) | 2022.01.22 |
| [ 운영체제 ] 프로세스 스케줄링(Process Scheduling) (0) | 2022.01.21 |
| [ 운영체제 ] 쓰레드(Thread) (0) | 2022.01.19 |
