1. Two Process Mutual Exclusion
1) version 1
✔️ p0과 p1 두 개의 프로세스만 존재한다고 가정해 보자. 둘 다 Critical Section에 진입하려 하는 상황이다.
'turn' 변수는 0/1의 값을 가지는데, 0이면 p0이 진입할 수 있고 1이면 p1이 진입할 수 있다.
➡️ p0이 CS에 진입하려고 할 때, enterCS 코드에서 turn을 체크하고 turn이 1이면 0이 될 때까지 while loop를 돌며 기다린다. turn = 0이면 while loop를 나와서 CS에 돌아갈 수 있다.
➡️ CS를 나온 후, exitCS 코드에서 turn = 1로 설정한다.
❗BUT❗만약 p1이 CS에 있을 때, 갑자기 CPU를 Preemption 당했다고 생각해 보자.
이 경우 turn 은 아직 1이기 때문에, p0이 cpu를 잡고 CS에 들어가려고 해도 turn은 1이므로, CS에 들어갈 수 없다.
즉 이 방식은 Mutual Exclusion 문제가 해결되었지만 ❌'progress requirement'❌를 만족하지 못한다.
2) version 2
✔️ 두 변수 flag0, flag1 는 TRUE/FALSE 값을 가진다. CS에 p0이 있으면 flag0이 true가 되고, 없으면 false가 된다.
➡️ p0이 enterCS 코드에서 flag1을 검사하는데, flag1이 true면 while loop을 돌며 기다린다. 그리고 flag1이 false가 되면 자신의 flag0을 true로 설정한 후 cs를 들어간다.
➡️ cs를 나올 때에는 자신의 flag0을 false로 설정한다.
이 경우 항상 상대방 플래그를 검사하고 나서 진입하고, 진입할 땐 자신의 플래그를 설정한다.
❗BUT❗ 이 방식은 'mutual exclusion' 방식을 만족하지 못한다.
flag0, flag1이 모두 false일 때, p0이 상대방 플래그가 false인 것을 체크하고 While문을 진입하지 않고 자신의 flag0을 true로 만들려고 하기 직전에, 갑자기 preemption 되었다고 가정해 보자.
p1이 cpu를 잡게 되고 enterCS 코드에서 상대방 flag가 0인 것을 확인한 후, 자기 flag를 true로 만들고 진입한다. 그 때 또 나오지 못하고 p0에 의해 preemption 되었다면, p0은 자신의 flag0을 true로 만들고 cs에 들어간다.
이 경우 동시에 critical section에 진입한 것이므로 ❌mutual exclusion❌을 충족하지 못한 것이다.
3) version 3
version2의 enterCS 코드의 순서를 바꾸어서 자신의 flag를 먼저 true로 만들고, while문으로 상대방 플래그를 검사하는 방식.
❗BUT❗ mutual exclusion 문제는 해결되었지만, ❌'progress requirement'❌를 만족하지 못한다.
p0이 자신의 flag를 true로 만든 후 while문을 진입하기 전에 preemption되면, p1은 자신의 flag를 true로 만든 후 while문에 진입하려고 하는데 상대방이 flag = 1이므로 진입하지 못한다. 그리고 나서 다시 p0이 cpu를 잡아도 p1의 flag가 1이므로, 둘다 영원히 while 루프를 탈출하지 못한다.
4) version 4. Dekker's algorithm
📌 Mutual Exclusion과 Progress requirement를 모두 만족하는 최초의 알고리즘
변수는 flag0, flag1, turn이 있다.
flag0 = true; // 자신의 flag를 true로 만들고 while문 진입
while (flag1) { // 상대방 flag도 true 인 경우
(version 3에선 자신도, 상대방도 루프에 갇힘)
if (turn == 1) // 만약 turn = 1이면, 상대방의 차례
flag0 = false // 자신의 flag = 0으로 만듦 (기다릴게!)
while (turn == 1) // 루프를 돌며 기다림
...
flag0 = true // 나의 turn이 되어 돌아오면 while 탈출, 자신의 flag true 설정
// 자신의 flag0 = true 설정 이후에도, 다시 while문으로 돌아가서 상대방 flag를 검사해야 한다. 그 떄 상대방 flag도 false어야 cs 진입 가능
..
turn = 1;
flag0 = false;
}
// 만약 상대방 flag가 0이라면 바로 CS 진입5) version 5. Peterson's algorithm
📌 Mutual Exclusion과 Progress requirement를 모두 만족하는 보다 간단한 알고리즘
flag0 = true;
turn = 1; // 상대방의 turn = 1로 만듦
while (flag1 && turn == 1) // 상대방 flag1과 turn 모두 1이면 루프 돈다
..
// 만약 상대방 flag1 == 0이면 while문 탈출
2. N개의 Process Mutual Exclusion
Dijkstra Algorithm, Knuth's Algorithm, Eisenberg and McGuire's Algorithm
등등 여러가지 있지만, 이해하는 데 매우 오래 걸릴 수 있다. 세부 알고리즘 내용은 생략한다. 다익스트라 알고리즘의 경우 다음과 같다! (자세한 내용 생략, 그냥 둘러보기)
