데커의 알고리즘

데커의 알고리즘(Dekker's algorithm)은 네덜란드의 수학자 테오도루스 데커가 상호 배제를 위해 고안한 병행 프로그래밍 알고리즘이다. 이 알고리즘은 의사소통을 위해 공유 메모리를 사용하여 두 프로세스(또는 스레드)가 하나의 자원을 혼란 없이 공유할 수 있게 한다.

데커의 알고리즘은 검사 및 조정(test-and-set) 명령과 같은 원자적 명령이 없는 경우에도 사용할 수 있으며, 바쁜 대기(busy waiting) 알고리즘에 속한다.

소개

이 알고리즘은 두 프로세스가 동시에 임계 영역에 들어가려고 할 때 하나만 들어가도록 한다. 한 프로세스가 이미 임계 영역에 있다면, 다른 프로세스는 전 프로세스가 끝나기를 기다려야 한다. f0과 f1 두 개의 플래그(각각 임계영역에 들어갈 의향, 두 프로세스 사이의 우선권을 나타낸다.)를 사용하여 구현할 수 있다. ,

의사 코드

 f0 := false
 f1 := false
 turn := 0   // or 1

 p0:                                 p1:
     f0 := true                         f1 := true
     while f1 {                          while f0 {
         if turn ≠ 0 {                       if turn ≠ 1 {
             f0 := false                         f1 := false
             while turn ≠ 0 {                    while turn ≠ 1 {
             }                                   }
             f0 := true                          f1 := true
          }                                  }
     }                                    }

    // 임계 구역                              // 임계 구역 
    ...                                   ...
    // 나머지 구역                            // 나머지 구역
    turn := 1                             turn := 0
    f0 := false                           f1 := false

같이 보기

• 피터슨의 알고리즘
• 램포트의 빵집 알고리즘