데커 알고리즘(Dekker's algorithm)

데커 알고리즘(Dekker's algorithm)은 flag와 turn이라는 변수로 임계영역에 들어갈 프로세스(혹은 스레드)를 결정하는 방식이다. 

flag값은 프로세스 중 임계 구역에 들어가길 원하는지 나타내는 변수이고, 

turn 변수는 누가 임계영역에 들어갈 차례(양보)인지 나타내는 변수이다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <iostream> #include <thread>   using namespace std;   int cnt; bool flag[2] = { false, false }; int turn;   void func0() {     for (int i = 0; i < 10000; i++) {         flag[0] = true;         while (flag[1] == true) {             if (turn == 1) {                 flag[0] = false;                 while (turn == 1) {}                 flag[0] = true;             }         }           cnt++;           turn = 1;         flag[0] = false;     } } void func1() {     for (int i = 0; i < 10000; i++) {         flag[1] = true;         while (flag[0] == true) {             if (turn == 0) {                 flag[1] = false;                 while (turn == 0) {}                 flag[1] = true;             }         }           cnt++;           turn = 0;         flag[1] = false;     } }   int main() {     thread t1(func0);     thread t2(func1);       t1.join();     t2.join();       cout << " cnt :: " << cnt << endl;       return 0; }   Colored by Color Scripter

cs

func0만 보면 func1은 자동으로 이해가 된다.

1. flag[0] = true로 설정하여 0번 스레드가 임계 영역 진입을 할 것이라고 표시한다.

2. 이때 flag[1] == true여서 1이 임계 영역에 진입할 것이라고 같이 선언했다면 

turn == 1인지 확인한다. 즉, 1이 이미 임계영역에 들어갔는지 확인한다.

3. 만약 turn == 1이면 flag[0] = false로 바꾸어 임계 영역에 0번 스레드가 진입하지 않겠다 선언하고 

turn == 1일때동안 while문에서 갇혀있는다.

4. turn == 0이 되면 flag[0] = true로 바꾸어 임계영역 진입을 선언하고 임계 영역에서 수행을 한다.

5. 마지막으로 나오면 trun = 1로 바꾸고 flag[0] = false로 바꾸어준다.