[5. 병행제어1] Peterson's Algorithm에서 flag와 turn 코드의 순서가 바뀌었을 때 문제가 생기는 상황

[Yunhee000]

Peterson's Algorithm

do {
1     flag[i] = true;
3     turn = j;
5     while (flag[j] && turn == j);
7     critical section
9     flag[i] = false;
11  remainder section
} while (1);

다음과 같은 기존 코드에서 아래 코드와 같이 flag[i] = true; 와 turn = j; 코드의 순서를 바꾸면 어떤 상황에서 문제가 발생하는가?

// code 1
do {
1     turn = j;
3     flag[i] = true; //turn = i
5     while (flag[j] && turn == j);
7     critical section
9     flag[i] = false;
11  remainder section
} while (1);

A. turn의 변수가 계속 변함에 따라 두 개의 프로세스가 둘 다 critical section에 들어갈 수 있도록 허용하는 상황이 되어버릴 수 있다.

// code 2
do {
2     turn = i; //turn = i
4     flag[j] = true;
6     while (flag[i] && turn == i); // flag[i], [j] 다 true
8     critical section
10  flag[j] = false;
12  remainder section
} while (1);

1 -> 2 -> 4 -> 6 -> 3 -> 7 => 둘 다 critical section 진입
code 1과 code2를 보면 1번 줄이 실행되고 인터럽트가 발생해 2번 줄이 실행되면 turn 이 i가 된다. 이 후 4번이 실행되고 6번에서 while문을 통과하므로 2번 프로세스는 critical section에 진입한다. 이 때 인터럽트가 발생해 3번으로 오면 flag는 둘 다 true가 되고 아래 5번을 실행하면 turn = i인 상태로 while문을 통과해 1번 프로세스도 critical section에 진입할 수 있게 된다. 따라서 두 코드의 순서를 변경하면 두 개의 프로세스 모두 critical section에 들어가는 것을 허용하게 되어 문제가 발생한다.

Peterson's algorithm

turn, flag 두 개의 변수를 사용하여 critical section에 프로세스가 동시에 들어가 발생하는 문제를 해결한다. -> 동시에 flag가 true여도 turn으로 순서를 정한다.

[Yunhee000]

Reference) kkw