데커의 알고리즘

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

같이 보기

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