프로세스들의 일반적인 구조
do {
entry section //lock, 프로세스들이 동시에 critical section에 들어가는걸 막기 위함
critical section //공유데이터에 접근하는 부분
exit section
reminder section
} while(1);Critical Section
'임계 영역'이라고도 한다. 서로 다른 두 프로세스, 혹은 스레드 등의 처리 단위가 같이 접근해서는 안 되는 공유 영역을 뜻한다. 보호되지 않는 임계 구역에 두 처리 단위가 동시에 접근할 때 발생하는 문제를 '임계 구역 문제'라고 한다. 임계 구역을 시작하는 코드 부분을 '입장 구역(entry section)', 임계 영역을 종료하는 코드 부분을 '퇴장 구역(exit section)'이라고 한다. 임계 영역이 아닌 부분은 '나머지 구역(remainder section)'이라고 한다.
synchronization variable
프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다
critical section 문제를 해결하기 위한 충족 조건
1. Mutual Exclusion (상호 배제)
어떤 프로세스가 critical section을 수행 중이면 다른 모든 프로세스는 그 critical section에 접근하면 안된다.
2. Progress
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해줘야 한다.
3. Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
= critical section에 못 들어가고 지나치게 오래 기다리는 상태(starvation)가 없어야 한다.
두 프로세스 간의 critical section 문제 해결 (software적으로 lock을 걸었다가 푸는) algorithm
Algorithm 1
synchronization variable
int turn;
initially turn = 0;
process P0
do {
while (turn != 0);
critical section //turn이 0이 되면 process0의 차례
turn = 1; //critical section에서 나오면 turn을 1로 만들어 줌
remainder section
} while(1);Mutual Exclusion 조건은 만족하나 Progress 조건은 만족하지 못한다.
=> 상대 프로세스가 critical section을 수행해야지만 차례가 오기 때문에 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있어도 critical section에 들어가지 못한다.
Algorithm 2
synchronization variable
boolean flag[2];
initially flag[모두] = false;
critical section에 들어갈 준비가 되면 if (flag[i] == true)를 만족해야 한다.
process Pi
do {
flag[i] = true; //flag를 true로 세팅 후
while (flag[j]); //상대 프로세스가 flag가 true라면 wait
critical section //차례가 오면 수행
flag[i] = false; //수행 후 flag를 false로 세팅하여 다른 프로세스가 들어올 수 있도록 함.
remainder section
} while(1);Mutual Exclusion 조건은 만족하나 Progress 조건은 만족하지 못한다.
=> 프로세스가 서로 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능하다. flag를 서로 true로 설정하고 상대가 critical section을 들어갔다가 false로 설정하기만을 기다린다.
Algorithm 3
Peterson's Algorithm
Combined synchronization variables of algorithms 1, 2
process Pi
do {
flag[i] = true; //flag를 true로 세팅 후
turn = j; //turn을 상대방의 turn으로 설정
while (flag[j] && turn == j); //상대방이 critical section에 대해 의사가 있는 경우(flag) && 상대방의 turn인 경우 -> wait
critical section
flag[i] = false; //수행 후 flag를 false로 세팅하여 다른 프로세스가 들어올 수 있도록 함.
remainder section
} while(1);Mutual Exclusion 조건, Progress 조건, Bounded Waiting 조건 모두 만족
문제 : Busy Waiting (=spin lock) (계속 CPU와 memory를 쓰면서 wait)
-> lock이 반환될 때까지 계속 확인하면서 기다리며 critical section에 진입이 불가능한 경우, 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락을 가리킨다. 스핀락이라는 이름은 락을 획득할 때까지 해당 스레드가 빙빙 돌고 있다(spinning)는 것을 의미한다.
Synchronization Hardware
하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하면 앞의 문제는 간단하게 해결이 가능하다.
Mutual Exclusin with Test & Set
Synchronization variable :
boolean lock = false;
Process Pi
do {
while (Test_and_Set(lock));
critical section
lock = false;
remainder section
}
