- entry section - critical section에 진입하고자 하는 코드
- critical section 진입
- exit section - critical section에 나온 이후 코드
Critical Section의 프로그래밍적 해결 방법
- Mutual Exclusive (상호 배제)
- 프로세스 P가 critical section을 수행 중이면 다른 모든 프로세스들은 critical section에 진입해서는 안된다.
- Progress (진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 진입하고자 하는 프로세스가 있으면 들어가게 해줘야 한다.
- Bounding Waiting (한정된 대기)
- 프로세스가 critical section에 진입 요청한 후부터 들어갈때까지 다른 프로세스가 critical section에 들어가는 횟수에 한계가 있어야 한다.
Algorithm 1
- Mutual Execlusive - O
- Progress - X
- 다른 프로세스(P1)가 턴을 넘겨줘야 P0 프로세스가 Critical Section에 접근할 수 있다.
Algorithm 2
- Mutual Execlusive - O
- Progress - X
Algorithm 3 (Peterson’s Algorithm)
- 상대방이 critical section에 관심 없다면 or 내 차례라면 critical section에 진입
아래 세 조건을 모두 만족함
- Mutual Execlusive
- Progress
- Bounding Waiting
단점
- Busy Waiting(=spin lock) - 계속 CPU와 Memory를 쓰면서 Wait
Synchronization Hardware
- 하드웨어적으로 Test & Modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
test_and_set(): 원래 값을 읽고 해당 값을 1로 세팅한다.- lock이 0이었다면 lock을 걸고 critical section에 진입
- lock이 1이었다면 1을 읽으면서 (1로 세팅하면서) 기다리고 있음.
- lock이 0이 되는 경우 1로 세팅하고 critical section에 진입
Semaphore
- 앞의 방식들을 추상화시킴
- Semaphore S
- integer variable
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능
- P(S) : 자원이 있으면 세마포어 변수를 획득 (Busy Waiting 문제는 생김)
- V(S) : 자원을 다 사용하고 반납하는 과정
Busy Waiting 해결 - Block/wakeup
- 임계 구역 진입을 위해 무한루프를 돌며 대기하는 것 대신, 프로세스를 중지시키고 큐에 넣는다
-
P 연산 : S가 0이하면 waiting하는 프로세스를 중지시키고 waiting queue 에 넣는다
-
V 연산 : 어떤 프로세스가 임계 구역에서 나오면 signal()함수로 대기 큐에 있는 프로세스를 waiting queue에서 빼고 깨워 ready queue에 넣는다.
-
Busy Waiting vs Block/Wakeup
= Critical Section 길이 vs Block/Wakeup overhead (상태를 변경하는데에 따른 오버헤드)
- Critical Section의 길이가 긴 경우
Block/Wakeup이 적당 - Critical Section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가
Busy Waiting오버헤드보다 더 커질 수 있음 - 일반적으로는 Block/Wakeup 방식이 더 좋음
Two Types of Semaphore
- Counting Semaphore
- 자원의 개수가 여러 개
- Binary Semaphore
- 0 또는 1을 가질 수 있는 세마포어
Deadlock and Starvation
Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
Starvation
- indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 상황. 특정 프로세스만 자원을 공유하고 자원을 갖지 못하는 프로세스가 생기는 경우
ex) Dining-Philosophers Problem
