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
Synchronization Hardware
- TestAndSet (TAS) instruction
- Test와 Set을 한번에 수행하는 기계어
- Machine instruction
- Atomicity, Indivisible
- 실행 중 interrupt를 받지 않음(preemption이 되지 않음)
- Busy wating
- 비효율적
TestAndSet 명령어
boolean TestAndSet (boolean *target){
boolean temp = *target; // 이전 값 기록
*target = true; // true로 설정
return temp; // 값 반환
// 이 모든 걸 **한번에** 수행 (Machine instruction)
}ME with TAS Instruction
// lock 초기값 false
while(TAS(lock)){ // false를 return하고 true로 바꿔줌
// cs에 누군가 있으니까 true
// waiting...
}
// false를 return하기 때문에 cs접근
// cs 앞 부분// cs 뒷 부분
lock = false;일하는 동안 다른 프로세스 들어오면 true 반환하기 때문에 뺑뺑 돈다.
- 하지만 3개 이상의 프로세스의 경우에, Bounded wating 조건 위배
- Why?
- (1번이 나가면서 false로 바꿔주면 2번 아니면 3번 들어감. 3번 나가면서 false. 2번 아니면 4번 들어감. 2번은 계속 기다림)
- N-Process mutual exclusion
do{
wating[i] = true;
key = true;
while(waiting[i] && key)
key = TestAndSet(&lock);
// lock은 공유 변수지만 나머지 변수들은 각 프로세스 만의 변수
waiting[i] = false;
// 임계 영역
// 탈출 영역
j = (j + 1) % n;
while((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i){
lock = false;
}else {
waiting[j] = false;
// 나머지 영역
}
} while(true);HW Solutions
장점
- 구현이 간단
단점
- 여전히 Busy waiting
Busy waitting 문제를 해소한 상호 배제 기법
- Semaphore
- 대부분의 os들이 사용하는 기법
- Semaphore