OS에서 race condition은 언제 발생하는가?
- kernel 수행 중 인터럽트 발생 시
- Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
- Multiprocessor에서 shared memory 내의 kernel data
Process Synchronization 문제
-
공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생
-
일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해야함
-
Race condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
- concurrent process는 동기화되어야 한다.
The Critical-Section Problem
- n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
프로그램적 해결법의 충족 조건
-
Mutual Exclusion
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들을 그들의 critical section에 들어가면 안된다. -
Progress
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다. -
Bounded Waiting
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. -
가정
- 모든 프로세스의 수행 속도는 0보다 크다- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
Initial Attempts to Solve Problem
do {
entry section
critical section
exit section
remainder section
} while (1);Peterson's Algorithm
do {
flag[i] = true;
turn = j;
while (flag[i] && turn == j);
critical section
flag[i] = False
remainder section
} while (1);Busy waiting (spin lock, 계속 CPU와 memory를 쓰면서 wait)
Synchronization Hardware
하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 간단히 해결
Synchronization variable:
boolean lock = False;
Process P
do {
while (Test_and_Set(lock));
critical section
lock = false;
remainder section
} while (1);Semaphores
두 가지 atomic 연산에 의해서만 접근 가능
P(S): while (S <= 0) do no-op;
S--;
V(S): S++;Critical Section of n Processes
Synchronization variable:
semaphore mutext;
Process P:
do {
P(mutex);
critical section
V(mutex);
remainder section
} while (1);Which is better?
- Critical section의 길이가 긴 경우 Block/Wakeup이 적당
- Critical section의 길이가 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
- 일반적으로는 Block/Wakeup 방식이 더 좋음
Two Types of Semaphores
- Counting semaphore
- 도메인이 0 이상인 임의의 정수값- 주로 resource counting에 사용
- Binary semaphore (=mutext)
- 0 또는 1 값만 가질 수 있는 semaphore- 주로 mutual exclusion (lock/unlock)에 사용
Deadlock and Starvation
- Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
- Starvation: 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
Classical Problems of Synchronization
Bounded-Buffer Problem (Producer-Consumer Problem)
- Producer
1. Empty 버퍼가 있나요? (없으면 기다림)- 공유 데이터에 lock을 건다
- Empty buffer에 데이터 입력 및 buffer 조작
- Lock을 푼다
- Full buffer 하나 증가
- Consumer
1. full 버퍼가 있나요? (없으면 기다림)- 공유 데이터에 lock을 건다
- Full buffer에서 데이터 꺼내고 buffer 조작
- Lock을 푼다
- empty buffer 하나 증가
Shared data: buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
Synchronization variables
- mutual exclusion -> Need binary semaphore
- resource count -> Need integer semaphore (남은 full/empty buffer의 수 표시)
예시)
semaphore full = 0, empty = n, mutex = 1;
Producer (Consumer는 반대로, P(full), V(empty))
do { ...
produce an item in x
...
P(empty);
P(mutex);
...
add x to buffer
...
V(mutex)
V(full);
} while (1);Readers and Writers Problem
한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨
read는 동시에 여럿이 해도 됨
solution
- Writer가 DB에 접근 허가를 아직 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
- Reader들은 다 DB에 접근하게 해준다
- Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다
- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다
Shared data: DB 자체, readcount(현재 DB에 접근 중인 Reader의 수)
Synchronization variables
- mutex: 공유 변수 readcount를 접근하는 코드의 mutual exclusion 보장을 위해 사용
- db: Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
예시)
semaphore mutext = 1, db = 1;
Writer (starvation 발생 가능)
P(db);
...
writing DB is performed
...
V(db);Reader
P(mutext);
readcount++;
if (readcount == 1)
V(mutex);
...
reading DB is performed
...
P(mutex);
readcount--;
if (readcount == 0)
V(db);
V(mutex);Dining-Philosophers Problem
Synchronization variables
semaphore chopstick[5];
Philosopher i
do {
P(chopstick[i];
P(chopstick[(i+1)%5]);
...
eat();
V(chopstick[i]);
V(chopstick[(i+1)%5]);
...
think();
...
} while (1);모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우, Deadlock 가능성이 있다.
solution
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 하게 한다
semaphore self[5] = 0; mutex = 1;
Philosopher i
do {
pickup(i);
eat();
putdown(i);
think();
} while(1);
void putdown(int i) {
P(mutex);
state[i] = thinking;
test((i+4) % 5);
test((i+1) % 5);
V(mutex);
}
void pickup(int i) {
P(mutex);
state[i] = hungry;
test(i);
V(mutex);
P(self[i]);
}
void test(int i) {
if (state[(i+4) % 5] != eating && state[i] == hungry && state[(i+1) % 5 != eating) {
V(self[i]);
}
}Monitor
Semaphore의 문제점
- 코딩하기 힘들다
- 정확성의 입증이 어렵다
- 자발적 협력이 필요하다
- 한 번의 실수가 모든 시스템에 치명적 영향
Mutual exclusion 깨짐
V(mutex)
Critical Section
P(mutex)Deadlock
P(mutex)
Critical Section
P(mutex)동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
모니터 내에서는 한 번에 하나의 프로세스 만이 활동 가능
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
condition variable은 wait와 signal 연산에 의해서만 접근 가능
monitor bounded_buffer
{ int buffer[N];
condition full, empty;
void produce (int x)
{ if there is no empty buffer
empty.wait();
add x to an empty buffer
full.signal();
}
void consume (int *x)
{ if there is no full buffer
full.wait()
remove an item from buffer and store it to *x
empty.signal();
}
}monitor dining_philospher
{
enum {thinking, hungry, eating} state[5];
codition self[5];
void pickup(int i) {
state[i] = hungry;
test(i);
if (state[i] != eating)
self[i].wait();
}
void putdown(int i) {
state[i] = thinking;
test((i+4) % 5);
test((i+1) % 5);
}
void test(int i) {
if ((state[(i+4) % 5] != eating) && (state[(i] == hungry) && (state[(i+1) % 5] != eating)) {
state[i] = eating;
self[i].signal();
}
void init() {
for (int i=0; i<5; i++)
state[i] = thinking;
}
}
Each Philosopher:
{
pickup(i);
eate();
putdown(i);
think;
} while(1)