데커의 알고리즘

데커의 알고리즘(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

 같이 보기 
 피터슨의 알고리즘
 램포트의 빵집 알고리즘

분류:동시성 제어 알고리즘
분류:에츠허르 데이크스트라