피터슨(Peterson's algorithm) 알고리즘

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

데커 알고리즘과 상당히 유사하지만 상대방(다른 프로세스 혹은 스레드)에게 진입기회를 양보한다는 차이가 있다. 

flag값은 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수이고, 

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

#include <iostream>
#include <thread>
 
using namespace std;
 
int cnt;
bool flag[2] = { false, false };
int turn = 0;
 
void func0() {
    for (int i = 0; i < 10000; i++) {
        flag[0] = true;
        turn = 1;
        while (flag[1] == true && turn == 1) {}
 
        cnt++;
        printf("cnt1 :: %d\n", cnt);
 
        flag[0] = false;
    }
}
void func1() {
    for (int i = 0; i < 10000; i++) {
        flag[1] = true;
        turn = 0;
        while (flag[0] == true && turn == 0) {}
 
        cnt++;
        printf("cnt2 :: %d\n", cnt);
 
        flag[1] = false;
    }
}
 
int main() {
    thread t1(func0);
    thread t2(func1);
 
    t1.join();
    t2.join();
 
    cout << "cnt : :" << cnt << endl;
 
    return 0;
}
 

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

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

2. 이때 turn = 1을 주며 1번 프로세스가 먼저 들어가라고 양보해준다.

3. 만약 이때 컨텍스트 스위칭이 되지 않았다면 while문에 갇히게 된다.

4. 1번 프로세스가 이제 모든 작업을 끝내면 turn = 0, flag[1] = false가 되므로 0번 프로세스가 다시 돌 수 있다.