[운영체제 Step 11] - 상호배제 솔루션(1)

이전시간엔 상호배제의 구문을 짜기 위해 여러 가지 아이디어를 가지고 와서 시도해보았습니다.

결론적으로 제대로 해결되는 것 없이, 계속해서 새로운 문제가 파생되는 모양새가 드러났습니다.

과거 우리의 선배들은 이런 문제에 일찌감치 직면하였고 이에 대한 해결책을 여러 가지 방면으로 연구하셨습니다.

그러므로 이번 포스팅에선 어떻게 앞선 문제들을 해결할 수 있을지 알아보겠습니다.

첫번째로 볼 알고리즘은 Dekker's Algorithm입니다.

최초의 두 프로세스간 ME를 보장하는 알고리즘입니다.

아이디어는 대충 감이오시나요?

앞에서 썼던 아이디어는 flag와 turn중 하나를 썼는데 Dekker는 둘 다를 사용했음을 확인할 수 있습니다.

일단 flag[0] = true라는 것을 모두에게 알립니다. 그리고 P0의 if문을 보면, 만약 turn = 1이면 flat[0] = false로 바꾸고 turn = 1인동안 while문을 실행하고 다 빠져나왔을 때 flag[0] = true로 바꿉니다.

그리고 그때 되어서야 CS에 P0이 들어갑니다.

자 turn이 0인데, repeat문에서 자꾸 돌고 있고 0이 안온다고 가정해보겠습니다.

그럼 0이 위에서 계속 돌다가 죽어버렸습니다.

이후 P1으로 넘어갔을 때 flag[1] = true로 바꾸고 flag[0] == false이므로 while문을 실행하지 않고 바로 CS로 진입합니다.

즉, Progress문제는 위배하지 않았습니다.

또한, 둘 다 깃발을 들고 있어도 안에서 turn을 한 번 더 봄으로써 앞에서 발생했었던 Progress 문제, ME, Bounded time문제를 해결할 수 있습니다.

하지만 로직이 너무 복잡하다는 단점이 있었습니다.

그래서 Peterson's Algorithm이 등장합니다.

깃발 드는것 까지는 위의 알고리즘과 똑같습니다.

그래서 turn = 1, turn = 0을 주며 서로가 서로에게 먼저 들어가라고 양보를 하고 있습니다.

결국 늦게 양보한 프로세스가 나중에 들어가게 됩니다.

while문을 보시면, flag가 참이고 turn도 1이면 그때 실행하고 CS에 들어가는 걸 알 수 있습니다.

지금까지는 2개의 프로세스에 대한 ME를 알아보았고, 이제는 실용성이 있는 N개짜리의 알고리즘을 살펴보겠습니다.

다익스트라 알고리즘은 최초로 프레세스 N개의 상호배제 문제를 SW적으로 해결했습니다.

코딩테스트에서도 상당히 자주 나오는 기법이니 알아두시면 좋겠습니다.

다익스트라 알고리즘! 하면 종류가 정말 다양하지만 여기서는 ME를 해결하는 알고리즘을 알아보겠습니다.

다익스트라 알고리즘에서도 flag[]를 사용하는데요. 

이 flag는 3가지로 정의가 됩니다.

첫 번째로 idle은 프로세스가 안에 들어오려고 안할 때를 상정합니다.

두 번째로 want-in은 CS로 들어가려는 첫 번째 단계입니다.

즉, 의사를 표현하여 CS에 들어가려고 하는 단계입니다.

마지막 세 번째로, CS에 진입 직전 또는 CS내에 있을 때를 의미합니다.

자 다익스트라 알고리즘을 코드로 보겠습니다.

당연히 N개의 프로세스를 다루기 때문에 여러 프로세스 모두에게 적용이 되겠습니다.

위의 flag[i] ~ endwhile 까지가 1단계, flag[i] ~ endwhile 까지가 2단계입니다.

1단계를 먼저 보시면, flag[i] = want-in이라고 표현합니다. 그러면 flag[i] 는 의사가 있다는 것이 됩니다.

그리고 밑의 while문에서 만약 i의 턴이 아니면 계속 while문을 돌립니다.

그래서, while문을 계속 돌며 이 turn 상태가 종료될 때 까지 기다렸다가 종료되면 turn = i로 바꾸고 while문을 끝냅니다.

그렇게 turn을 자신의 turn으로 가져왔고 2단계 진입을 준비합니다.

근데 turn을 뺏었는데, 2단계로 가는 사이 다른 프로세스가 선점을 통해 뺏을 수도 있겠죠??

그래서 이 사이에 여러 번 걸러지면서 2단계로 이어질 수 있게 제작되었습니다.

그리고 2단계가 되면 flag를 in-cs상태로 바꿉니다.

이후 j라는 변수를 사용하는데, 이 j는 while문을 써서 표현할 것인데, j가 n보다 작고 j = i이거나 flag[j]가 in-cs가 아닐 때 j에 1씩 더해줍니다.

즉, flag[j]가 in-cs 상태가 아니면서 j == i인 상태. 즉, 나 혼자서만 in-CS상태가 되어야만 CS상태에 들어갈 수 있습니다.

여기서 만약 j >= n이면(누군가 있으면) 다시 제일 위의 repeat으로 올라가고 반복수행을 하게됩니다.

이런 경우도 있을 수 있겠죠.

A와 B 둘 다 in-CS에 있어서 둘 다가 repeat으로 올라갔다가 다시 CS에 들어가겠죠. 그럴 땐 CS에 들어가는건 한 개만 올라가게 됩니다.

하지만 보셨다시피 뺑뺑 도는 roop구문이 너무 많이 시행되었습니다.

그래서 속도가 느리다는 단점이 있었습니다.

또한 구현이 복잡하고 ME가 실행 중 선점이 되어 오버헤드가 발생할 수 있습니다.

하지만 공유 데이터를 수정할 때는 인터럽터를 억제함으로써 선점을 막을 수 있겠습니다만 이번에도 오버헤드가 발생할 수 있겠습니다.

그리고 제일 중요한 용어가 여기서 나옵니다.

위의 구문에서처럼 IN-CS에 들어가기 위해 기다리면서 계속 반복해서 도는 현상이 잦았습니다.

이는 굉장히 비효율적인데, 이를 Busy Waiting이라고 부릅니다.

감사합니다.