임계영역을 위한 해결책
하나의 공유변수를 이용한다.
2개의 프로세스가 Pi와 Pj라고 가정한다.
while(turn != i); //아무것도 하지 않는다. - entry_protocol
[critical_section]; //임계영역에 들어간다.
turn = j; //j로 차례를 바꿔준다. -exit_protocol
[non-critical_section];[실생활]
잠금장치가 없는 비행기 화장실로 생각해보자. 비행기 화장실 문에는 안에 사람이 있는지 없는지 확인할 수 있는 표시등이 있다. 일단 화장실을 사용하려면 표시등을 확인해야 한다. 만약 표시등이 빨간색(사용중)으로 되어 있다면 기다려야 한다. 그리고 표시등이 초록색(사용가능)이라면 들어가서 내가 화장실을 사용하고 있다는 것을 다른 사람에게 알려줘야 하므로 빨간색으로 바꿔준다. 그리고 다 사용하고 나서 나올 때 초록색으로 변경해 줘야 한다. 다음 사람이 사용할 때 빨간색으로 되어 있으면 안에 사람이 있는 줄 알고 사용하지 못할 것이다.
이 경우에는 deadlock와 starvation이 없다. 하지만 어떤 프로세스가 임계영역을 오랫동안 수행하지 않는다면, 필요시 상대 프로세스가 임계영역을 수행할 수 없다. Pi가 임계영역을 사용해야 j로 바꿔주는데, 수행하지 않으면 Pj가 사용을 하지 못한다.
Dekker's Algorithm
-상호배제를 만족시키는 해결책
Boolean flag[2];
int turn;
flag[i] = TRUE;
while(flag[j])
{
if(turn == j)
{
flag[i] = FALSE;
while(turn == j);
flag[i] = TRUE;
}
}
[critical_section]
turn = j;
flag[i] = FALSE;먼저 flag[i]를 true로 설정해서 i가 임계영역에 들어갈 것이라고 표시한다.
flag[j]가 true여서 임계영역에 들어갈 것이라고 했다면
turn = j인지 확인한다.(j가 이미 임계영역인지 확인한다.)
그렇다면 i가 들어가지 않겠다고 표시한다.
j의 턴일 동안 아무것도 하지 않는다.
turn이 i가 되면 flag[i]를 true로 바꿔서 임계영역에 진입한다. --entry protocol
임계영역을 수행 후
j의 차례가 된다.
flag[i]는 false로 바꾸어 진입하지 않는다고 선언한다. --exit protocol
Pi가 매우 빠른 프로세스인 경우 starvation이 발생할 수 있다.
이 알고리즘을 단순화시킨 것이 Peterson's simple Algorithm이다.
Peterson's simple Algorithm
공유변수 turn과 각 프로세스에 자기가 critical section을 수행 중이라는 flag를 할당하는 경우를 조합한 알고리즘이다.
두개의 프로세스가 Pi와 Pj라고 가정한다.
1. Boolean flag[2];
2. int turn;
3. flag[i] = TRUE;
4. turn = j;
5. while(flag[j] && turn == i);
6. [critical section]
7. flag[i] = FALSE;
8. [non-critical section]- flag[i]를 TRUE로 설정해서 임계영역에 들어간다는 것을 표시해준다. --entry protocol
- turn = j로 바꿔준다.
- j가 실행중이고 turn이 j이면 아무것도 하지 않는다.
- j가 끝내면 임계영역에 들어간다. turn = i
- 임계영역 탈출 후 사용하지 않는다는 표시를 해준다. turn이 i이고 flag[i] = FALSE이므로 Pi가 다시 임계영역에 들어갈 수 있다.
