데커의 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

같이 보기[편집]