[OS] 6장 - Process Synchronization
반효경 교수님의 운영체제 강의를 참고하였습니다.
(https://core.ewha.ac.kr/publicview/C0101020140318134023355997?vmode=f)
프로그램적 해결법의 충족조건
- Mutual Exclusion(상호 배제)
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다
- Progress(진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
- Bounded Waiting(유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
- ex) 프로세스 3개중 2개가 번갈아가면서 접근하고 1개는 계속 기다리는 경우
Algorithm 1
- Synchronization variable
- turn = 0 → Pi can enter its critical section if(turn == i)
- turn이 0이라는 의미는 0번째 프로세스가 critical section에 접근할 수 있다는 의미
- P0의 경우
do {
while(turn != 0); // waiting
critical section
turn = 1; // change turn
remainder section
} while(1);
- Mutual Exclusion은 충족되나, Progress는 되지 않음, 극단적인 경우 P0는 빈번하고 P1는 1번만 들어갈 경우 P0는 영원히 들어가지 못함.
Algorithm 2
- Synchronization variables
- boolean flag[2];
- initial flag = false
- Pi ready to enter its critical section
- Process Pi
do {
flag[i] = true;
while(flag[j]);
critical section
flag[i] = false;
remainder section
} while(1);
- 둘 다 2행까지 수행 후 끊임없이 대기하는 상태 발생
- Mutual
Algorithm 3(Peterson’s Algorithm)
- algorithm 1과 algorithm 2를 합쳐 놓음
do {
flag[i] = true;
//i번째 프로세스가 임계구역에 들어가고 싶다는 것을 알림
turn = j;
//i번째 프로세스가 선언한 다음 j차례로 돌려줌으로써
//내가 쓰기 전에 먼저 접근하고 싶은 프로세스가 있는지 확인
while(flag[j] && turn == j); // 내 차례거나 상대방
//critical section에 접근하기 위해서는 나 외에 다른 프로세스가 기다리지 말거나
//flag[j]=false 즉, 내 차례여야 한다.
critical section;
flag[i] = false;
remainder section
} while(1)
- 3가지 조건 다 만족
- Busy waiting(=spin lock) = CPU와 memory를 계속 사용하면서 wait
Semaphore
- S
-
integer variable : 공유 자원의 갯수
-
P(S)
- critical section 값을 획득하는 과정
while(S<=0) do no-operation; //busy waiting S--; -
V(S)
- 반납하는 과정
S++; -
S, V연산은 atomic 하다고 가정을 하는 것
-
번외로 P와 V연산의 의미는 세마포어를 개발한 다익스트라가 네덜란드어인 Probeer와 Verhoog에서 따왔다고 한다.
Critical section of n processes
- 컴퓨터가 S, V연산을 지원해 준다면
semaphore mutex;
do {
P(mutex);
critical section
V(mutex);
remainder section
while(1);
- busy-wait는 효율적이지 못함(=spin lock)
- Block & Wake up 방식의 구현이 있음(=sleep lock)
- 컴퓨터가 P, V연산을 지원하면 피터슨 알고리즘 같이 구현할 atomic한 것을 신경쓰지 않아도 됨
Block / Wakeup Implementation
- 세마포어를 다음과 같이 정의
typedef struct {
int value; /* semaphore*/
struct process *L; /* process wait queue */
} semaphore;
- block과 wakeup을 다음과 같이 가정
- block
- 커널은 block을 호출한 프로세스를 suspend시킴
- 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
- wakeup(P)
- block된 프로세스 P를 wakeup 시킴
- 이 프로세스의 PCB를 ready queue로 옮김
- block
P(S):
S.value--; /* prepare to enter */
if(S.value < 0) {
add this process to S.L;
block();
}
V(S):
S.value++;
if(S.value <= 0) { // value <= 0이 자원을 기다리는 프로세스가 있음을 의미 P(S)에서 value--
remove a process P from S.L;
wakeup(P);
}
Two Types of Semaphore
- Counting semaphore
- 도메인이 0이상인 임의의 정수값
- 주로 resource counting에 사용
- Binary semaphore(=mutex)
- 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion(lock/unlock)에 사용
Deadlock and Starvation
- Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
- Starvation
- indefinite locking, 프로세스가 suspend된 이유에 해당하는 세마포어에 큐에서 빠져나갈 수 없는 현상
Monitor
- Semaphore의 문제점
- 코딩하기 힘들다
- 정확성(correctness)의 입증이 어려움
- 자발적 협력(voluntary cooperation)이 필요함
- 한번의 실수가 모든 시스템에 치명적 영향
- 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
- monitor 프로시저 자체는 atomic하게 구현되어 있음
- semaphore와 다르게 lock 걸 필요가 없음
- 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
- wait
- invoke한 프로세스는 다른 프로세스가 signal()을 invoke하기 전까지 suspend
- signal
- 정확하게 하나의 suspend된 프로세스를 resume
- suspend된 프로세스가 없으면 아무일도 일어나지 않음
- wait