6. 프로세스 동기화
데이터의 접근
데이터를 읽음 → 연산 수행 → 결과 내보냄
하나의 공유 데이터에 동시에 접근하려고 할 때 문제
Race Condition (경쟁 상태)
- 커널 수행 중 인터럽트 발생 시
- 해결: 커널 공유 데이터를 건드리기 전 disable interrupt
- 프로세스가 시스템 콜을 하여 커널 모드로 수행중인데 문맥 교환이 일어나는 경우
- 커널 데이터(공유 데이터)에 접근하는 도중 CPU 빼앗길 경우
- 해결: 커널 모드에서 수행중인 경우 CPU를 빼앗지 않음
- Multiprocessor에서 공유 메모리 내의 커널 데이터
- 여러 프로세스에서 시스템 콜을 하여 커널 데이터를 사용하는 경우
- 해결: 한번에 하나의 CPU만 커널에 들어갈 수 있게 함
커널 내부에 있는 공유 데이터 접근시 lock/unlock
Process Synchronization 문제
공유 데이터 동시 접근 → 데이터의 불일치 문제
일관성 유지를 위해 협력 프로세스 간의 실행 순서를 정해야 함
The Critical-Section Problem
Critical Section: 각 프로세스의 코드에서 공유 데이터를 접근하는 코드
한 프로세스가 critical section에 있을 때 다른 프로세스는 접근할 수 없음
프로그램적 해결법의 충족 조건
- Mutual Exclusion (상호 배제)
한 프로세스가 사용중이면 다른 프로세스는 사용할 수 없음 - Progress (진행)
아무도 critical section에 있지 않으면 들어갈 수 있어야 함 - Bounded Waiting (유한 대기)
프로세스가 요청하면 기다리는 시간이 유한해야 함
Algorithm 1
Synchronization variable turn
ex) turn == 0 → 상대방 차례 / turn == 1 → 내 차례
do {
while (turn != 0) ; /* My turn? */
critical section
turn = 1; /* Now it's your turn */
remainder section
} while (1);Mutual Exclusion 만족
Progress 만족 X
반드시 교대로 들어가야 하기 때문에 상대방이 turn을 내 값으로 바꿔줘야만 들어갈 수 있음
Algorithm 2
Synchronization variable boolean flag[2]
상대방 flag == False 될때까지 기다림
do {
flag[i] = true; /* Pretend I am in */
while (flag[j]) ; /* Is he also in? then wait */
critical section
flag[i] = false; /* I am out now */
remainder section
} while (1);Mutual Exclusion 만족
Progress 만족 X
둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능
Algorithm 3 (Peterson’s Algorithm)
Synchronization variable turn, boolean flag[2]
do {
flag[i] = true; /* My intention is to enter */
turn = j; /* Set to his turn */
while (flag[i] && turn == j) ; /* wait only if... */
critical section
flag[i] = false;
remainder section
} while (1);모든 조건 만족
Busy Waiting (= Spin Lock)
계속 CPU와 memory를 쓰면서 wait (while문 반복)
Synchronization Hardware
하드웨어적으로 Test & Set를 atomic하게 수행할 수 있도록 지원하는 경우 문제 간단히 해결
Synchronization variable: boolean lock = false;
do {
while (Test_and_Set(lock)) ;
critical section
lock = false;
remainder section
}Test_and_set(lock)
lock의 값을 읽음 → lock == 0 → lock = 1로 변경하고 critical section 들어감 → 빠져나올 때 lock = 0으로 변경
Semaphores
추상 자료형 - object, operation으로 구성
Semaphore S - integer variable
공유 자원 counting, 자원이 남아있는지 확인
- P(S): 자원을 획득하는 과정 - lock을 걸어줌
while (S <= 0) /* 자원이 없음 */ do no-op; S--; /* 자원 사용 */ - V(S): 자원을 반납하는 과정 - lock을 풀어줌
S++; /* 자원 반납 */
Synchronization variable: semaphore mutex; (1로 초기화)
do {
P(mutex); /* If positive, dec-&-enter, Otherwise, wait */
critical section
V(mutex); /* Increment semaphore */
remainder section
} while (1);busy-wait 문제 → Block & Wakeup 방식
Block / Wakeup Implementation
Semaphore를 구조체처럼 정의
typedef struct {
int value; /* semaphore */
struct process *L; /* process wait queue */
} semaphore;- block
커널이 block을 호출한 프로세스 suspend
PCB를 semaphore에 대한 wait queue에 넣음 - wakeup(P)
block된 프로세스 P를 wakeup 시킴
PCB를 ready queue로 옮김
P(S):
S.value--; /* prepare to enter */
if (S.value < 0) { /* Oops, negative, I cannot enter */
add this process to S.L;
block();
}V(S):
S.value++;
if (S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}S.value ≤ 0 → 자원의 여분이 없어서 어떤 프로세스가 잠들어 있음
S.value > 0 → 자원이 남아 있음
Two types of Semaphores
- Counting semaphore
자원의 수를 세서 도메인을 0 이상으로 설정
주로 recource counting에 사용 - Binary semaphore
0 또는 1 값만 가질 수 있는 semaphore
주로 mutual exclusion (lock/unlock)에 사용
Deadlock and Starvation
- Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상. 여러 프로세스가 얽혀서 더 이상 진행 X
- Starvation: Indefinite blocking
Bounded-Buffer Problem
Producer-Consumer Problem
Producer: data 생성해서 버퍼에 넣음
Consumer: data 꺼내감
- Shared data: buffer 자체, buffer 조작 변수
- Synchronization variables:
semaphore full = 0empty = nmutex = 1
Producer
do {
...
produce an item in x
...
P(empty);
P(mutex);
...
add x to buffer
...
V(mutex);
V(full);
...
} while(1);Consumer
do {
P(full);
P(mutex);
...
remove an item from buffer to y
...
V(mutex);
V(empty);
...
comsume the item in y
...
} while(1);Readers-Writers Problem
한 프로세스가 DB에 write 중일 때 다른 프로세스 접근 X
read는 동시에 여럿이 해도 됨
- Shared data:
DB 자체int readcount = 0; - Synchronization variables:
semaphore mutex = 1;db = 1;
Writer
P(db);
...
writing DB is performed
...
V(db);Reader
P(mutex);
readcount++;
if (readcount == 1)
P(db) /* block writer */
V(mutex); /* readers follow */
...
reading DB is performed
...
P(mutex);
readcount--;
if (readcount == 0)
V(db); /* enable writer */
V(mutex);Starvation 발생 가능
Dining-Philosophers Problem
Synchronization variables: semaphore chopstick(5);
Deadlock 가능성이 있음 (모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집은 경우)
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 함
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 함
- 비대칭: 짝수/홀수 철학자는 왼쪽/오른쪽 젓가락부터 집도록 함
enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0; 젓가락을 모두 집을 수 있는 상태인지
semaphore mutex = 1;
Philosopher
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) {
state[i] = eating;
V(self[i]);
}
}Monitor
Semaphore의 문제점
코딩이 힘듦, 정확성 입증이 어려움, 자발적 협력이 필요, 한 번의 실수가 모든 시스템에 치명적 영향
Monitor
공유 데이터에 대한 동시접근을 모두 책임짐
모니터 안에 정의되어 있는 함수로만 접근 가능
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용 condition x, y;
x. wait(); - 프로세스 blocked 상태
x.signal(); - blocked 상태의 프로세스 호출
- Bounded-Buffer Problem
condition variable - 값을 가지지 않고 프로세스를 재우거나 깨우는 역할만 수행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(); } }
- Dining Philosophers Example
monitor dining_philosopher { enum {thinking, hungry, eating} state[5]; condition 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); eat(); putdown(i); think(); } while(1);
