-Mutal Exclusion( 상호 배제 )
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세들은 그들의
critical section에 들어가면 안된다
-Progress( 진행 )
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다
-Bounded Waiting( 유한대기 )
- 프로세스가 critical section 에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다
-가정
- 모든 프로세스의 수행 속도는 0보다 크다
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
- Progress 조건을 충족하지 못함
- 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능
- Mutal Exclusion,Progress,Bounded Waiting 모든 조건을 충족
- Busy Waiting(=spin lock) 계속 CPU와 memort 를 쓰면서 wait 함 비효율적인 방식임
- 앞의 방식들을 추상화 시킴
- Semaphore S
-integer variable
-위의 두 가지 atomic 연산에 의해서만 접근 가능
- busy-wait는 효율적이지 못함
- Block & Wakeup 방식의 구현(next page)
Semaphore 연산이 이제 다음과 같이 정의됨
P연산에서 S의 값을 빼서 자원이 없는상태로 만들고 block 시킴
다쓰고나서 S의 값을 ++시키는데 ++시켰음에도 불구하고 S의 값이 0이하이면 잠들어있는 프로세스하나를 불러서 깨운다. 만약 양수 일경우에는 자원을 쓰고있다는 뜻이다.
Busy-wait v.s. Block/wakeup
- Critical section의 길이가 긴 경우 Blcok/Wakeup이 적당
- Critical seciton의 길이가 매우 짧은 경우 Block/Wakeup이 적당
- 일반적으로는 Block/wakeup 방식이 더 좋음
Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
S와Q가 1로 초기화된 semaphore라 하자
P0에서 S라는 semaphore를 먼저 받고 그다음 CPU가 P1으로 넘어가서 Q라는 semaphore를 받았다. 그러고 P0은 Q라는 semaphore를 받고싶은데 P1에서 Q라는 semaphore를 가지고 있어서 받을수없어서 무한히 기다리게 된다. 이렇게 상대방이 가진 것을 기다리고 자기것은 주지않는 현상을 Deadlock라고 한다.
Starvation
- indefinite blcoking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
