데커의 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
데커의 알고리즘은 두 개의 프로세스가 임계 구역에 동시에 접근하려 할 때, 상호 배제를 보장하는 동기화 알고리즘이다. 이 알고리즘은 `wants_to_enter` 플래그와 `turn` 변수를 사용하여 구현되며, 두 프로세스 중 하나만 임계 구역에 진입하도록 제어한다. 데커의 알고리즘은 교착 상태와 기아 상태를 방지하지만, 현대적인 CPU 및 컴파일러 환경에서는 메모리 배리어와 최적화 문제로 인해 제대로 작동하지 않을 수 있다.
더 읽어볼만한 페이지
- 동시성 제어 알고리즘 - 스핀락
스핀락은 락 획득을 위해 반복적으로 확인하며 대기하는 동기화 메커니즘으로, 성능 향상을 위한 최적화 기법과 하이퍼 스레딩 환경에서의 성능 향상 기법이 존재하지만, CPU 자원 낭비라는 단점으로 인해 다양한 대안 방식이 모색되고 있다. - 동시성 제어 알고리즘 - 다중 버전 동시성 제어
다중 버전 동시성 제어(MVCC)는 데이터베이스 시스템에서 데이터의 여러 버전을 관리하여 읽기 작업이 쓰기 작업 중에도 중단 없이 수행되도록 동시성을 관리하는 기술이다. - 에츠허르 데이크스트라 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다. - 에츠허르 데이크스트라 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다.
| 데커의 알고리즘 |
|---|
2. 작동 원리
데커의 알고리즘은 두 개의 플래그와 한 개의 순서 변수를 사용하여 상호 배제를 구현한다.[3] 이 알고리즘은 두 프로세스가 동시에 임계 영역에 진입하려 할 때, `turn` 변수 값에 따라 하나의 프로세스만 허용한다. 만약 한 프로세스가 이미 임계 영역에 있다면, 다른 프로세스는 바쁜 대기를 통해 첫 번째 프로세스가 종료될 때까지 기다린다.
프로세스는 임계 구역에 진입하려는 의도를 외부 while 루프를 통해 확인한다. 다른 프로세스가 의도 플래그를 설정하지 않은 경우, 현재 turn 값에 관계없이 임계 구역에 안전하게 진입할 수 있다. 이는 두 프로세스 모두 플래그를 설정하기 전에 임계 상태가 될 수 없기 때문에(최소한 하나의 프로세스가 while 루프에 진입함을 의미) 상호 배제가 보장됨을 뜻한다. 또한, 임계 상태가 되려는 의도를 철회한 프로세스에서는 대기가 발생하지 않으므로 진행이 보장된다. 다른 프로세스의 변수가 설정된 경우 while 루프에 진입하며, turn 변수가 누가 임계 상태가 될 수 있는지 결정한다. 우선순위가 없는 프로세스는 우선순위를 다시 받을 때까지 임계 구역에 진입하려는 의도를 철회하고(내부 while 루프), 우선순위가 있는 프로세스는 while 루프에서 탈출하여 임계 구역에 진입한다.
데커의 알고리즘은 상호 배제, 교착 상태, 기아로부터 자유롭다.[3] p0이 `while wants_to_enter[1]` 루프 안에 영원히 갇히는 경우를 가정해 보자. 교착 상태로부터 자유로우므로, 결국 p1은 임계 구역으로 진행하여 `turn = 0`으로 설정한다(p0이 진행하지 않는 한 turn 값은 변경되지 않음). 결국 p0은 내부 `while turn ≠ 0` 루프에서 벗어난다 (이 루프에 갇힌 적이 있다면). 그 후 `wants_to_enter[0]`을 true로 설정하고 `wants_to_enter[1]`이 false가 되기를 기다린다 (`turn = 0`이므로 while 루프에서 작업을 수행하지 않음). 다음에 p1이 임계 구역에 진입하려고 시도할 때, `while wants_to_enter[0]` 루프의 작업을 실행해야 한다. 특히, 결국 `wants_to_enter[1]`을 false로 설정하고 `while turn ≠ 1` 루프에 갇히게 된다 (turn이 0으로 유지되므로). 다음에 제어가 p0으로 전달되면, `while wants_to_enter[1]` 루프를 종료하고 임계 구역에 진입한다.
만약 알고리즘이 `while wants_to_enter[1]` 루프의 작업을 `turn = 0`인지 확인하지 않고 수정하면 기아의 가능성이 있다. 따라서 알고리즘의 모든 단계가 필요하다.[3]
2. 1. 변수 설명
`wants_to_enter`: 크기가 2인 불린(boolean) 배열이다. `wants_to_enter[0]`는 프로세스 0이, `wants_to_enter[1]`는 프로세스 1이 임계 영역에 진입하려는 의도를 나타낸다. `wants_to_enter[i]`가 `true`이면, i번째 프로세스가 임계 영역에 들어가려고 함을 의미한다.[3]`turn`: 정수 변수이다. 현재 어떤 프로세스에게 임계 영역 진입 우선권이 있는지 나타낸다. `turn` 값이 0이면 프로세스 0에게, 1이면 프로세스 1에게 우선권이 있다.[3]
2. 2. 알고리즘 개요
이 알고리즘은 두 프로세스가 동시에 임계 영역에 들어가려고 할 때 하나만 들어가도록 한다. 한 프로세스가 이미 임계 영역에 있다면, 다른 프로세스는 이전 프로세스가 끝나기를 기다려야 한다.[3]두 개의 플래그(`wants_to_enter[0]`, `wants_to_enter[1]`)와 `turn` 변수를 사용하여 구현된다. `wants_to_enter` 플래그는 각 프로세스(0 또는 1)가 임계 영역에 진입하려는 의도를 나타내고, `turn` 변수는 두 프로세스 중 누가 우선순위를 갖는지 나타낸다.
각 프로세스는 임계 영역에 진입하기 전에 자신의 `wants_to_enter` 플래그를 `true`로 설정한다. 만약 상대 프로세스의 `wants_to_enter` 플래그가 `true`이면, 현재 `turn` 값을 확인한다. `turn` 값이 자신의 프로세스 번호와 다르면, 자신의 `wants_to_enter` 플래그를 `false`로 설정하고, `turn` 값이 자신의 프로세스 번호와 같아질 때까지 기다린다. `turn` 값이 자신의 프로세스 번호와 같으면, 임계 영역에 진입한다. 임계 영역 작업을 완료한 후에는 `turn` 값을 상대 프로세스 번호로 변경하고, 자신의 `wants_to_enter` 플래그를 `false`로 설정한다.
이러한 방식은 상호 배제를 보장한다. 두 프로세스 모두 플래그를 설정하기 전에 임계 영역에 진입할 수 없기 때문이다. 또한, 한 프로세스가 임계 영역에 진입하려는 의도를 철회하면 다른 프로세스는 대기 없이 진행할 수 있으므로 진행도 보장된다.
데커의 알고리즘은 상호 배제, 교착 상태 및 기아로부터 자유롭다.
3. 의사 코드
데커의 알고리즘은 다음과 같이 의사 코드로 표현할 수 있다.[3]
| colspan="2" | | |
프로세스는 임계 구역에 진입하려는 의도를 나타내며, 이는 외부 while 루프에 의해 테스트된다. 다른 프로세스가 의도 플래그를 설정하지 않은 경우, 현재 turn 값에 관계없이 임계 구역에 안전하게 진입할 수 있다. 상호 배제는 여전히 보장된다. 이는 두 프로세스 모두 플래그를 설정하기 전에 임계 상태가 될 수 없기 때문이다(최소한 하나의 프로세스가 while 루프에 진입함을 의미). 또한, 이는 진행을 보장한다. 임계 상태가 되려는 의도를 철회한 프로세스에서는 대기가 발생하지 않기 때문이다. 또는 다른 프로세스의 변수가 설정된 경우 while 루프에 진입하며, turn 변수가 누가 임계 상태가 될 수 있는지 결정한다. 우선순위가 없는 프로세스는 우선순위를 다시 받을 때까지 임계 구역에 진입하려는 의도를 철회한다(내부 while 루프). 우선순위가 있는 프로세스는 while 루프에서 탈출하여 임계 구역에 진입한다.
데커의 알고리즘은 상호 배제, 교착 상태로부터의 자유, 기아로부터의 자유를 보장한다. 마지막 속성이 어떻게 유지되는지 살펴보면 다음과 같다. p0이 `while wants_to_enter[1]` 루프 안에 영원히 갇히는 경우를 가정한다. 교착 상태로부터의 자유가 있으므로, 결국 p1은 임계 구역으로 진행하여 `turn = 0`으로 설정한다(p0이 진행하지 않는 한 turn 값은 변경되지 않음). 결국 p0은 내부 `while turn ≠ 0` 루프에서 벗어날 것이다(이 루프에 갇힌 적이 있다면). 그 후 `wants_to_enter[0]`을 true로 설정하고 `wants_to_enter[1]`이 false가 되기를 기다리는 상태가 된다(`turn = 0`이므로 while 루프에서 작업을 수행하지 않음). 다음에 p1이 임계 구역에 진입하려고 시도할 때, `while wants_to_enter[0]` 루프의 작업을 실행해야 한다. 특히, 결국 `wants_to_enter[1]`을 false로 설정하고 `while turn ≠ 1` 루프에 갇히게 된다(turn이 0으로 유지되므로). 다음에 제어가 p0으로 전달되면, `while wants_to_enter[1]` 루프를 종료하고 임계 구역에 진입한다.
알고리즘이 `while wants_to_enter[1]` 루프의 작업을 `turn = 0`인지 확인하지 않고 수정하면 기아의 가능성이 있다. 따라서 알고리즘의 모든 단계가 필요하다.
4. 특징
데커의 알고리즘은 상호 배제, 교착 상태로부터의 자유, 기아로부터의 자유라는 세 가지 중요한 속성을 보장한다.[3]
p0이 `while wants_to_enter[1]` 루프 안에 영원히 갇히는 상황을 가정해 보자. 교착 상태가 발생하지 않으므로, 결국 p1은 임계 구역으로 진행하여 `turn = 0`으로 설정한다. (p0이 진행하지 않으면 turn 값은 변하지 않는다.) 결국 p0은 내부 `while turn ≠ 0` 루프에서 벗어난다. (만약 이 루프에 갇힌 적이 있다면). 그 후 `wants_to_enter[0]`을 true로 설정하고 `wants_to_enter[1]`이 false가 되기를 기다린다. (`turn = 0`이므로 while 루프에서 작업을 수행하지 않는다.)
다음에 p1이 임계 구역에 진입하려고 시도할 때, `while wants_to_enter[0]` 루프의 작업을 실행해야 한다. 특히, 결국 `wants_to_enter[1]`을 false로 설정하고 `while turn ≠ 1` 루프에 갇히게 된다. (turn이 0으로 유지되므로). 다음에 제어가 p0으로 전달되면, `while wants_to_enter[1]` 루프를 종료하고 임계 구역에 진입한다.
만약 알고리즘이 `while wants_to_enter[1]` 루프의 작업을 `turn = 0`인지 확인하지 않고 수정하면 기아가 발생할 수 있다. 따라서 알고리즘의 모든 단계가 필요하다.
5. 한계 및 주의사항
최근의 많은 CPU는 명령을 아웃 오브 오더 실행한다. 이러한 CPU를 사용한 멀티프로세서 환경에서는 메모리 배리어가 없으면 이 알고리즘이 동작하지 않는다.
또한, 많은 최적화 컴파일러가 이 코드를 변경하기 때문에, 플랫폼에 관계없이 동작하지 않을 수 있다. 많은 언어에서 플래그 변수 ''f0''과 ''f1''이 루프 내에서 전혀 사용되지 않는 것을 감지한다. 또한, 많은 컴파일러는 ''turn'' 변수가 내부 루프 내에서 갱신되지 않는 것도 감지하여 변환하므로, 결과적으로 무한 루프를 형성할 수 있다. 이러한 변환이 이루어지면, 이 알고리즘은 아키텍처에 관계없이 동작하지 않게 된다.
PCI-Express 등의 버스는 읽고 쓰는 순서를 변경하는 경우가 있다. 쓰기 후 읽기의 경우에는 읽기 전까지 쓰기가 완료되도록 하는 등의 성질을 이용하여 구현해야 할 필요가 있다.
6. 현대적 관점
데커의 알고리즘은 두 프로세스가 동시에 임계 영역에 진입하지 않도록 하는 알고리즘이다. 한 프로세스가 이미 임계 영역에 있으면 다른 프로세스는 이전 프로세스가 끝날 때까지 기다려야 한다.[3]
이 알고리즘은 `wants_to_enter[0]`, `wants_to_enter[1]`라는 두 개의 플래그와 `turn` 변수를 사용하여 구현된다. `wants_to_enter` 플래그는 각 프로세스가 임계 영역에 진입하려는 의도를 나타내고, `turn` 변수는 두 프로세스 중 어떤 프로세스가 우선권을 가지는지 나타낸다.[3]
두 프로세스가 동시에 임계 구역에 진입하려고 하면, 알고리즘은 `turn` 값에 따라 한 프로세스만 허용한다. 이미 임계 구역에 있는 프로세스가 있다면, 다른 프로세스는 바쁜 대기를 하며 첫 번째 프로세스가 종료될 때까지 기다린다.[3]
데커의 알고리즘은 상호 배제, 교착 상태 및 기아 상태가 발생하지 않음을 보장한다. p0이 `while wants_to_enter[1]` 루프에 영원히 갇히는 경우를 가정해 보자. 교착 상태가 없으므로, 결국 p1은 임계 구역으로 진행하여 `turn = 0`으로 설정한다. (p0이 진행하지 않으면 `turn` 값은 변경되지 않는다.) 결국 p0은 내부 `while turn ≠ 0` 루프에서 벗어난다. 그 후 `wants_to_enter[0]`을 true로 설정하고 `wants_to_enter[1]`이 false가 되기를 기다린다. (`turn = 0`이므로 while 루프에서 작업을 수행하지 않는다.) p1이 다음에 임계 구역에 진입하려고 할 때, `while wants_to_enter[0]` 루프의 작업을 실행해야 한다. 특히, 결국 `wants_to_enter[1]`을 false로 설정하고 `while turn ≠ 1` 루프에 갇히게 된다. (turn이 0으로 유지되므로) 다음에 제어가 p0으로 전달되면, `while wants_to_enter[1]` 루프를 종료하고 임계 구역에 진입한다.[3]
참조
[1]
간행물
Over de sequentialiteit van procesbeschrijvingen
http://www.cs.utexas[...]
1962
[2]
간행물
Cooperating sequential processes
1965-09
[3]
논문
Some Myths About Famous Mutual Exclusion Algorithms
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com