상호 배제 여러 가지 기법들 : HW solution
상호 배제를 보장하기 위해 하드웨어에서 제공하는 방법에 대해서 알아보도록 하겠습니다.
TestAndSet (TAS) instruction
TestAndSet 명령어는 동시성을 제어 어하기 위한 동기화 명령어 중 하나로서, 하드웨어의 도움을 받아 수행됩니다.
이 명령어는 test 와 set을 한 번에 수행하는 기계어(machine instruction)입니다.
// target을 검사하고, target 값을 true로 변경
boolean TestAndSet (boolean *target) { //<- 한번에 수행 (machine instruction)
boolean temp = *target; // 이전 값 기록
*target = true; // true로 설정
return temp; // 값 반환
}기계어이기 때문에 원자성(atomicity)을 가지며 실행 중 interrupt를 받지 않아 명령어 수행 중에 선점(preemption)이 되지 않습니다.
TAS를 이용한 상호배제 구현
다음은 TAS를 활용하여 상호 배제를 구현한 예제입니다.
boolean lock = false;
do {
while(TestAndSet(&lock)); // lock을 걸어줌, lock이 풀릴때 까지 다른 프로세스는 CS에 접근 못함.
// Critical Section
lock = false; // lock을 풀어줌
} while(ture);설명
- 가장 먼저 TestAndSet을 실행하는 프로세스가 while(TestAndSet(&lock)); 루프에서 lock = ture로 바꾸고 false를 반환받아 while문을 빠져나오며 임계 구역에 진입합니다.
- 다른 프로세스는 lock = false가 될때까지 while루프를 빠져나오지 못하고 계속 대기하게 됩니다.
- 임계구역에 진입했던 프로세스는 임계구역을 빠져나오면서 lock=false를 수행하여 lock을 풀어주면 대기하던 다른 프로세스가 임계구역에 진입하게 됩니다.
이 알고리즘은 프로세스가 3개 이상인 경우 한 프로세스가 계속해서 임계구역에 진입하지 못하는 경우가 발생할 수 있습니다. 그렇기 때문에 bounded waiting 조건을 위배하게 됩니다.
N개의 프로세스에서 상호배제 구현
다음은 대기열(waiting)을 추가하여 bounded waiting 문제를 해결한 알고리즘입니다.
boolean lock = flase;
do { // 프로세스 Pi의 진입 영역
waiting[i] = true; // 프로세스 i를 대기열에 넣음.
key = true;
while (waiting[i] && key) // 대기가 풀리거나 lock이 풀릴 때까지 대기함.
key = TestAndSet(&lock); // lock 값을 key에 반환. key와 lock은 같은 값으로 보면 됨.
waiting[i] = false; // CS에 접근할 수 있으므로 대기를 풀어줌. 이 코드가 없다면 무한 대기를 하게 됨.
// Critical Section
j = (i + 1) % n;
while ((j != i) && !waiting[j]) // 대기 중인 프로세스를 찾음
j = (j + 1) % n;
if (j == i) // 대기 중인 프로세스가 없으면
lock = false; // 다른 프로세스의 진입을 허용할 수 있게 lock을 풀어줌.
else // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입하게 함.
waiting[j] = false; // Pj가 임계 영역에 진입할 수 있도록 대기를 품.
} while (true);
HW솔루션의 장단점
장점
- 하드웨어가 한번에 수행되는것을 보장해 주기 때문에 SW솔루션에 비해 구현이 간단합니다.
단점
- Busy waiting 문제가 있어 비효율적입니다.
