1. Mutual Exclusion을 위한 하드웨어적 지원은 어떤 것을 할 수 있을까?!
1) SW 해결방식의 문제
Dekker, Peterson, Digkstra 등 여러 알고리즘은 w소프트웨어적w으로 Mutual Exclusion 문제를 해결하기 위한 것인데, while문을 돌기 때문에 속도도 느리고 Mutual Exclusion Primitive를 실행하는 도중에 preemption 되기도 한다는 단점이 있다.
2) 인터럽트를 중지시켜서 Hardware적 해결이 가능할까?
➡️ Uniprocessor 환경에서는 CS에 진입할 때에는 interrupt를 Enable/disable 해 버림으로써, 간단하게 Mutual Exclusion 문제가 해결된다.
➡️ 그러나 Multiprocessor 환경에서는 프로세서가 자신의 CPU의 인터럽트를 disable 시킬 순 있지만 다른 프로세서까지 인터럽트를 disable 시키는 것은 어렵다.
2. Mutual Exclusion을 지원하기 위한 Hardware support
📌 Special Machine instructions
ME를 지원하기 위한 기계어 명령을 지원하겠다.
새로운 기계어 명령을 추가하면 하드웨어가 바뀌고 명령을 이해하기 위한 CIRCUIT, 마이크로 프로그램 등이 추가된다.📌 Example
- TS instruction(test and set)
- Swap Instruction
이 이에도 Fetch and add, Compare and swap 등 여러 하드웨어 instruction 등이 있다.
3. Test and Set Instruction (TS 기계어 명령)
- TS 는 사실 기계어 명령인데, 편의를 위해 C언어로 나타낸 것
boolean TS(boolean *target) { // boolean 값을 가지는 target pointer
boolean rv = *target; // target이 가리킨값 (true/false)을 rv에 옮김
*target = true; // target에는 true를 넣음
return rv; // target의 원래 값 rv return한다.➡️ target이 가리키는 오브젝트에 대해서, 그 값에 true를 넣고 실제 값을 리턴한다.
이 과정은 실제로는 하나의 기계어 명령이기 때문에, 인터럽트 받지 않고 atomic 하게 이뤄진다.
📌 n개의 프로세스 기준 Test & Set instruction
p1부터 pn까지 모든 프로세스가 공유할 수 있는 변수 lock 이 있다고 생각해보자. lock = True면 cs에 어떤 프로세스가 있다는 것을 의미한다.
➡️enterCS에서 while(TS(&lock)) ; 은 lock에 있는 값을 빼 내면서, lock에는 true를 넣는 것이다 !
✔️ CS에 아무도 없었다면(False) => lock의 False value가 나오면서 True가 lock에 들어간다.
✔️ CS에 누군가 있으면(True) => lock의 True value가 나오면서 True가 lock에 들어간다. (값 유지)➡️ atomic한 Hardware instruction TS를 통해 아주 간단하게 구현할 수 있다는 점 !
(But, 이것은 bounded waiting 문제를 해결할 순 없다)
4. Swap Instruction
➡️ a가 가리키는 오브젝트와 b가 가리키는 오브젝트를 서로 맞바꾸는 것 !
a를 b가 가리키는 오브젝트를 가리키게 만들고, b를 a가 가리키는 오브젝트를 가리키게 만든다.
void swap(boolean *a, boolean *b) {
boolean tmp = *a; // a가 가리키던 값
*a = *b; // a를 b가 기리키던 값을 가리키게 함
*b= tmp; // b를 a가 가리키던 값을 가리키게 함
}이 코드는 실제로 기계어 명령이므로, atomic하게 한방에 처리된다.
📌 n개의 프로세스 기준 Swap Instruction
n개의 프로세스가 cs에 어떤 프로세스가 있는지를 나타내는 lock 변수를 공유한다.
➡️각 프로세스는 자기만의 변수 key를 가지고 있다. key의 값이 true이며 lock과 key의 값을 맞바꾼다.
➡️만약 key == true이고, lock == false이면, 값이 맞바뀌어서 key == false, lock == true가 된다. 그렇게 while문을 탈출하게 되면 CS에 들어가게 된다.
이 코드는 실제로 기계어 명령이므로, atomic하게 한방에 처리된다.
(But, 이것은 bounded waiting 문제를 해결할 순 없다)
5. 정리 : Mutual Exclusion의 문제
1) Busy Waiting & Inefficiency
cpu를 사용하고 있는데, 다른 걸 하는 게 아니라 critical section에 들어가지 못하고 while문을 돌면서 계속 loop를 돌고만 있으면 매우 비효율적이다. 차라리 critical section을 실행중인 프로세스가 cpu를 잡고 빨리 section을 나오게 하는 것이 효과적인데, 그러지 않으므로 비효율적인 busy waiting을 하는 현상이다.
2) busy waiting을 방지하는 mutual exclusion
cs에 진입을 원하는 프로세스를 sleep 상태로 보내고 (cpu를 잡고 loop를 돌면서 busy waiting을 하는 것이 아니라), 이후에 프로세스가 cs를 벗어나면 wakeup 시켜주겠다는 방법이다. Semaphore, Sequencer(=event counter = ticket lock) 의 방법이 있다.
