데커 알고리즘

Dekker's algorithm

Dekker의 알고리즘은 동시 프로그래밍에서 상호 배제 문제에 대한 최초의 정확한 해결책이다. 이 해결책은 네덜란드 수학자 Th. J. Dijkstra가 순차 프로세스 설명과[1] 순차적 프로세스 협력에 관한 그의 원고를 출판하지 않은 논문에서 인용한 것이다.[2] 두 개의 스레드가 단일 사용 리소스를 충돌 없이 공유할 수 있도록 하며, 공유 메모리만 사용하여 통신할 수 있다.

순진한 턴테이블 알고리즘의 엄격한 교체를 피하며, 최초의 상호 배제 알고리즘 중 하나였다.

개요

두 프로세스가 동시에 중요 섹션으로 진입하려고 하는 경우 알고리즘은 누구의 차례인지에 따라 하나의 프로세스만 허용한다. 한 프로세스가 이미 중요 섹션에 있는 경우, 다른 프로세스는 첫 번째 프로세스가 종료될 때까지 대기할 것이다. 이것은 두 개의 깃발을 사용하여 행해진다. 프로세스 0과 1의 중요 부분에 각각 진입하려는 의도를 나타내는__to_enter[1]와 두 프로세스 중 누가 우선권을 가지고 있는지를 나타내는 변수 턴을 원한다.

데커 알고리즘

Dekker의 알고리즘은 다음과 같이 가성으로 표현할 수 있다.[3] 

    변수 wants_to_enter : 턴 2개 턴 : 정수 wants_to_enter[0] 0 false wants_to_enter[1] ← false turn ← 0 // 또는 1 
p0: wants_to_enter[0] wants_to_enter[1] {wants 0 { wants_to_enter[0] rolls false } { waiting wait } {wants_to_enter[0] true } //critical 섹션 ...tend 1 want_to_to_thearmiss //fals 섹션 
p1: wants_to_enter[1] wants_to_enter[0] {wants 1 { wants_to_enter[1] waiting wait } { wants_to_inter[1] true } //ritical 섹션 ...walse 0 want_to_to_enter[1] //free 섹션

공정은 루프 상태에서 외측에 의해 시험되는 중요한 부분으로 진입하려는 의도를 나타낸다. 다른 공정이 의도를 표시하지 않은 경우, 임계 구간은 현재 선회 여부와 관계없이 안전하게 진입할 수 있다. 둘 중 어느 과정도 플래그를 설정하기 전에 중요해질 수 없기 때문에 상호 배제는 여전히 보장될 것이다. 이것은 또한 중요해지려는 의도를 철회한 과정에서는 기다림이 일어나지 않기 때문에 진전을 보장한다. 또는 다른 프로세스의 변수가 설정된 경우 루프가 입력되고 턴 변수가 누가 중요해질 수 있는지 결정한다. 우선순위가 없는 프로세스는 우선순위가 다시 부여될 때까지(내부 중 루프) 중요 섹션에 들어가려는 의도를 철회한다. 우선순위가 있는 프로세스는 루프에서 벗어나 핵심 섹션으로 진입한다.

데커의 알고리즘은 상호 배척, 교착상태로부터의 자유, 기아로부터의 자유를 보장한다. 왜 마지막 재산이 남아 있는지 봅시다. p0이 "while wants_to_enter[1]" 루프 안에 영원히 고착되어 있다고 가정합시다. 교착상태로부터 자유가 있기 때문에 결국 p1은 임계 구간으로 진행되어 턴 = 0을 설정한다(그리고 턴 값은 p0이 진행되지 않는 한 변하지 않는다). 결국 p0은 내부 "while turn 0" 루프에서 벗어날 것이다(그 루프에 고착된 적이 있는 경우). 그 후에는 want_to_enter[0]를 true로 설정하고 want_to_enter[1]가 false가 될 때까지 기다리는 것으로 정착할 것이다(턴 = 0이기 때문에 while loop에서는 결코 동작을 하지 않을 것이다). 다음에 p1이 임계 섹션으로 들어가려고 할 때, "while wants_to_enter[0]" 루프에서 작업을 실행하도록 강제될 것이다. 특히, 최종적으로 wants_to_enter[1]를 false로 설정하여 "while turn 1" 루프(턴이 0으로 유지되기 때문에)에 갇히게 된다. 다음에 제어장치가 p0으로 넘어가면 "while wants_to_enter[1]" 루프를 종료하고 임계 섹션으로 들어간다.

턴 = 0인지 확인하지 않고 "while wants_to_enter[1]" 루프에서 동작을 수행하여 알고리즘을 수정했다면 아사 가능성이 있다. 따라서 알고리즘의 모든 단계가 필요하다.

메모들

이 알고리즘의 한 가지 장점은 특별한 시험-세트(원자성 읽기/수정/쓰기) 지침이 필요하지 않기 때문에 언어와 기계 아키텍처 간 이동성이 높다는 것이다. 한 가지 단점은 두 가지 공정에 한정되어 있고 공정 중단 대신 바쁜 대기 시간을 활용한다는 점이다. (바쁜 대기 시간을 사용하는 것은 프로세스가 중요 섹션 내에서 최소한의 시간을 소비해야 함을 시사한다.)

현대의 운영체제는 Dekker의 알고리즘보다 일반적이고 유연한 상호배제 원형을 제공한다. 그러나, 두 프로세스 사이에 실제 경합이 없는 경우, Dekker의 알고리즘을 사용할 때 중요 섹션의 출입이 매우 효율적이다.

현대의 많은 CPU들은 그들의 지시를 비질서한 방식으로 실행한다; 심지어 메모리 액세스도 재주문할 수 있다(메모리 순서 참조. 이 알고리즘은 메모리 장벽을 사용하지 않으면 이러한 CPU가 장착된 SMP 기계에서는 작동하지 않을 것이다.

또한, 많은 최적 컴파일러는 플랫폼에 관계 없이 이 알고리즘을 실패하게 하는 변환을 수행할 수 있다. 많은 언어에서, 컴파일러는 플래그 변수가 loop에서 결코 접근되지 않음을 탐지하는 것이 합법적이다. 그런 다음 루프 인바리어트 코드 운동이라는 프로세스를 사용하여 루프에서 해당 변수에 대한 쓰기를 제거할 수 있다. 또한 많은 컴파일러들이 턴 변수가 내측 루프에 의해 절대 수정되지 않는다는 것을 감지하고 유사한 변환을 수행하여 잠재적 무한 루프를 발생시키는 것도 가능할 것이다. 이러한 변환 중 하나를 수행하면, 알고리즘은 아키텍처에 관계 없이 실패할 것이다.

이 문제를 완화하기 위해 휘발성 변수는 현재 실행 중인 컨텍스트 범위 밖에서 수정할 수 있는 것으로 표시해야 한다. 예를 들어, C# 또는 Java에서는 이러한 변수에 '휘발성'이라는 주석을 달 수 있다. 그러나 C/C++ "휘발성" 속성은 컴파일러가 적절한 순서에 따라 코드를 생성한다는 것을 보장할 뿐이며, 해당 코드의 순서 내 실행을 보장하는 데 필요한 메모리 장벽은 포함하지 않는다는 점에 유의하십시오. C++11 원자 변수는 적절한 순서 요건을 보장하는 데 사용될 수 있다. 기본적으로 원자 변수에 대한 연산은 순차적으로 일관되기 때문에 원하는_to_enter 및 턴 변수가 원자라면 순진한 구현은 "그냥 효과가 있을" 것이다. 또는 별도의 울타리를 명시적으로 사용하여 여유로운 주문을 사용하여 부하 및 저장 작업을 보장할 수 있다.

참고 항목

참조

  1. ^ Dijkstra, Edsger W. Over de sequentialiteit van procesbeschrijvingen (EWD-35) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (번역) (미등록, 1962 또는 1963); 프로세스 설명의 순차성에 대한 영어 번역
  2. ^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (번역) (1965년 9월)
  3. ^ Alagarsamy, K. (2003). "Some Myths About Famous Mutual Exclusion Algorithms". ACM SIGACT News. 34 (3): 94–103. doi:10.1145/945526.945527. S2CID 7545330.