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

같이 보기 [ 編輯 ]

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

이 글은 컴퓨터 科學에 關한 토막글 입니다. 여러분의 知識으로 알차게 文書를 完成해 갑시다.