![[OS] 9. Process Synchronization and Mutual Exclusion 2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FSYr1H%2Fbtreo5G1K8o%2FIqtfsEPRfYVKrvxwxcPx6K%2Fimg.jpg)
지난 강의에서는 상호 배제를 구현하기 위한 노력들을 살펴 봤었다. 그 이후에 어떠한 소프트웨어적인 해결책을 내놓았는지 하나씩 살펴보자.
Dekker's algorithm
이 알고리즘은 프로세스가 두 개일 때, Mutual Exclusion을 보장하는 최초의 알고리즘이다.
앞의 버전 0, 1보다 더 발전한 모양으로, 해당 문제들을 처음으로 해결해냈다.
진행되는 플로우를 살펴보자.
먼저 P0이 작업을 하려고 flag를 true로 바꾸었다고 해보자. 이 때 flag[1]에 따라 작업을 수행할 수 있는지 여부가 정해지는 데, P1도 flag를 true로 전환 시킨 상태라고 가정해보자.
그렇다면 while문 안으로 들어가서 현재 turn을 통해 누구의 차례인지 알아낼 수 있다. turn이 1이라면 P1의 차례이기 때문에 P0은 flag[0]을 false로 바꿔주게 된다. 그 이후 계속 turn을 살피다가 turn이 0이 되면 작업을 수행할 수 있게 된다. 여기서 P1이 작업을 마치게 되면 turn과 flag를 동시에 바꿔주기 때문에 P0은 turn을 확인하여 작업을 수행할 수 있고, flag를 다시 들어서 작업 중임을 표시해준다.
기존 버전 1,2의 문제를 모두 해결할 수 있는데 하나씩 봐보자.
[in Version 1]
> P0이 진입하지 않는 경우
->> 그래도 P1은 정상 진입할 수 있다. flag[0]이 false일 것이기에 while문을 거치지 않고 바로 CS 영역에 들어가 작업을 수행할 수 있다.
> P0이 두 번 연속 진입하려는 경우
->> P0은 당연히 첫 진입은 정상적으로 가능하다. 첫 진입 이후 turn = 1, flag[0] = false 처리를 해주는데, 두 번째 진입 때도 장애물 없이 바로 진입할 수 있는 것을 볼 수 있다. 왜냐 while문에서 걸리지 않기에 바로 작업을 수행할 수 있는 것이다.
[in Version 2]
> P0이 진입 이후 선정 당했는데 P1이 들어올 때
->> 만약 P0이 진입하자마자 선점당해서 flag[0] = true 처리만 해줬다고 생각해보자. P1은 마찬가지롤 깃발을 올리고 while문에 진입하게 된다. turn이 0이기에 P1의 깃발을 다시 내려주고 대기하게 된다. 이후 P0이 복귀하면 P0은 바로 작업을 수행할 수 있고, P1은 P0이 작업을 마치면 정상적으로 작업을 수행할 수 있다. 즉 동시에 CS 영역에 들어가는 경우도 없다는 것을 알 수 있다.
Peterson's Algorithm
Dekker's algorithm보다 조금 더 간결하게 구현한 걸 볼 수 있다.
P0의 두 번째 줄을 보면 turn을 1로 하여 다른 프로세스에 양보하고 있는 모습을 볼 수 있다. 즉 상대 차례라면 기다리고 들어가겠다는 것이다!
이제 프로세스가 2개가 아니라 N개인 경우에 어떻게 ME를 구현할 수 있는지 알아보자.
Dijkstra's Algorithm
마찬가지로 flag를 사용하는데, 조금 복잡하게 사용하고 있다.
- idle : 프로세스가 들어왔는지 여부
- want-in : 프로세스가 CS 영역에 들어가기 위한 첫 번째 단계 (의사를 밝히는 단계)
- in-CS : CS 영역에 진입하기 위한 2단계. 거의 들어가기 직전의 단계
1단계를 먼저 봐보자.
우선 CS 영역에 들어가고 싶다는 의사를 밝히는 것을 볼 수 있다! 그리고 turn != i, 즉 내 차례가 아니면 기다린다고 하는 것이다. 현재 차례인 프로세스가 일이 끝날 때 까지(flag[turn] == idle) 기다리게 된다. 끝나게 되면 바로 turn을 내 것으로 가져온다. 그 이후 2단계로 진입한다.
2단계 깃발을 먼저 들어준다.
j는 타 프로세스를 지칭할 수 있느 인덱스 정도로 봐도 될 것 같다. 그렇기에 j = i 즉 j 가 나인 경우는 패스하고, j가 CS 영역에 없어야 한다. 즉 i인 나만 CS 영역에 있어야 한다는 것이다. 그러면 j는 n까지 다 돌고 반복문을 벗어나게 되고, 즉 in-CS에는 나 혼자만 있다면 들어가게 되는 것이다. 그리고 CS 영역을 벗어나면 idle을 통해 flag를 처리해준다!
우리가 아는 경로 문제에서의 다익스트라 알고리즘과는 다른 알고리즘이라는 것을 알 수 있다!
(이 사람 덕(?)에 많은 걸 공부하게 되었을지도...)
SW Solution의 문제
지금까지 SW 해결책들을 봤는데 아쉽게도 문제점이 있다.
- 속도가 느리다.
- 구현이 복잡하다.
- 다익스트라만 봐도 구현이 조금 복잡한 것을 알 수 있다.
- ME primitive 실행 중 preemption 될 수 있다. (오버헤드 발생)
- Busy waiting
- 기다리는데 계속 돌며 제자리 반복하는 것 = 비효율적
- 다익스트라에서 flag[turn] == idle 부분에서 계속 루프를 도는 경우가 발생할 수 있다.
Ref: https://www.youtube.com/watch?v=lY43KR3IItw&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=13