Mutual Exclusion Solutions
- SW solutions
- Dekker's algorithm (Peterson's alogorithm)
- Dijstra's algorithm, Knuth's algo, Eisenberg and McGuire's algo, Lamport's algo
- HW solution
- TestAndSet(TAS) instruction
- OS supported SW solution
- Spinlock
- Semaphore
- Eventcount/sequencer
- Language-Level solution
- Monitor
SW와 HW solution의 busy waiting을 해결하기 위해
SpinLock
- 정수 변수 (조금 특별한!)
- 초기화, P(), V() 연산으로만 접근 가능한 변수
- 위 연산들은 atomic한 연산 (os가 보장해줌)
P(S){ // S: 물건 개수
//물건 뺏기
while(S <= 0) do // 물건이 없다면 기다린다
endwhile;
S ← S - 1;
}V(S){
// 물건 넣기
S ← S + 1;
}(active 라는 spin lock이 있음 cs 앞에서 P(active)하고 cs 뒤에서 V(active)해준다 )
(진작에 이걸로하지 왜 SW solution사용했음? ㅋㅋ)
(이런 과정이 있었기 때문에 os supported solution이 나올 수 있었던거다~)
- 문제점
(Pi가 CPU에서 일하다가 나왔어 그리고 Pj가 들어감. 그런데 Pi가 다시 들어가려고해, 근데 Pj는 나올 수 가 없어. 왜냐하면 atomic하기 때문에 )- 멀티 프로세서 시스템에서만 사용가능 (CPU1 - Pi, CPU2 - Pj)
- 여전히 Busy waiting!