Method of Mutual Exclusion - Dekker Algorithm

1. Dekker Algorithm

// 프로세스가 공유하는 데이터 flag[] : boolean 배열, turn : int
flag[0] = false;
flag[1] = false;
turn = 0; // 공유 변수, 0 or 1
// 프로세스 P0의 임계 영역 진입 절차
flag[0] = true; // 프로세스 P0가 임계 영역에 들어감을 알림
while (flag[1] == true) { // P1의 임계 영역 진입 여부 확인
    if (turn == 1) { // P1이 진입할 차례가 되면 플래그를 재설정하여 P1에 진입 순서 양보
        flag[0] = false;
        while (turn == 1) { // turn을 바꿀 때까지 대기
            // 바쁜 대기
        }
        flag[0] = true; // P1이 임계 영역에 재진입 시도
    }
}
/* 임계 영역 */
turn = 1; // P1에 진입 순서 제공
flag[0] = false; // P0의 임계 영역 사용 완료 설정
/* 나머지 영역 */
// 프로세스 P1
flag[1] = true;
while (flag[0] == true) { // P0의 임계 영역 진입 여부 확인
    if (turn == 0) { // P0이 진입할 차례가 되면 플래그를 재설정하여 P0에 진입 순서 양보
        flag[1] = false;
        while (turn == 0) { // turn을 바꿀 때까지 대기
            // 바쁜 대기
        }
        flag[1] = true; // P1이 임계 영역에 재진입 시도
    }
}
/* 임계 영역 */
turn = 0; // P0에 진입 순서 제공
flag[1] = false; // P1의 임계 영역 사용 완료 설정
/* 나머지 영역 */

특징
- 특별한 하드웨어 명령문이 필요하지 않다.
- 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계 영역에 들어가려는 것을 막지 않는다.
- 임계 영역에 들어가기를 원하는 프로세서를 무한정 기다리게 하지 않는다.
- 프로세서 두 개가 동시에 임계 영역에 진입하도록 플래그를 설정하면 교착 상태가 발생할 수 있다.

2. 그 외의 알고리즘들

Dijkstra : 최초로 프로세스 n개의 상호 배제 문제를 소프트웨어적으로 해결했다. 실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 세마포 방법으로, 가장 짧은 평균 대기 시간을 제공한다.
Knuth : 이전 알고리즘 관계를 분석한 후 일치하는 패턴을 찾아 패너트이 반복을 줄여서 프로세스에 프로세서를 할당하는 방법. 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야 한다.
Lamport : 사람들로 붐비는 빵집에서 번호표를 뽑아 빵을 사려고 기다리는 사람들에 비유해서 만든 알고리즘. 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그 중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당하는 방법
Hansen (Brinch Hansen) : 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것으로 대기 시간과 실행 시간을 이용하는 모니터 방법. 분산 처리 프로세서 간의 병행성 제어를 많이 발표했다.