데커 알고리즘 (Dekker's Algorithm)

데커 알고리즘 (Dekker’s Algorithm)

데커 알고리즘(Dekker’s Algorithm)은 두 프로세스 간 **상호 배제(Mutual Exclusion)**를 보장하기 위해 1965년 네덜란드의 수학자 Theodorus Dekker가 개발한 최초의 소프트웨어 상호 배제(mutual exclusion) 알고리즘이다.
이 알고리즘은 두 개의 프로세스가 공유 자원에 동시에 접근하는 것을 방지하여 경쟁 상태(race condition)를 해결하는 방법을 제시한다.
공유 자원에 대한 안전한 접근을 위해 **플래그(flag)**와 턴(turn) 변수를 활용하며, 하드웨어적 명령어 없이 소프트웨어만으로 구현 가능하다.

데커 알고리즘은 상호 배제 문제 해결의 역사적 중요성을 가지지만, 현대 시스템에서는 **세마포어(Semaphore)**나 **뮤텍스(Mutex)**와 같은 더 효율적인 동기화 기법이 주로 사용된다.

데커 알고리즘의 핵심 구성 요소

1. 플래그(flag)

   • 각 프로세스가 임계 영역(Critical Section) 진입 의사를 표시하는 변수이다.
   • flag[0]과 flag[1]이 있으며, 초기값은 false이다.

2. 턴(turn)

   • 임계 영역에 진입할 프로세스의 순서를 결정하는 변수이다.
   • 0 또는 1의 값을 가지며, 프로세스 간 충돌 시 우선권을 부여한다.

1
2
3

# 두 프로세스가 임계 영역 진입을 원하는지 표시하는 플래그
flag = [False, False]  # 각 프로세스의 진입 시도 여부
turn = 0  # 현재 차례(0 또는 1)

작동 원리

1. 진입 의사 표시:
   프로세스가 임계 영역에 진입하려면 먼저 자신의 flag를 true로 설정한다.

2. 상대 프로세스 확인:
   상대방 프로세스의 flag가 true인지 확인한다.

   • 상대방이 진입 의사가 없으면(flag = false) 즉시 임계 영역에 진입한다.
   • 상대방도 진입 의사를 표시했다면 turn 변수를 확인한다.

3. 턴(turn) 기반 양보:

   • turn이 상대방을 가리키면 자신의 flag를 false로 변경하고, turn이 변경될 때까지 대기한다.
   • turn이 자신을 가리키면 다시 flag를 true로 설정하고 임계 영역에 진입한다.

4. 임계 영역 종료:
   임계 영역 실행 후 flag를 false로 재설정하고, turn을 상대방으로 변경한다.

예제 코드 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class DekkersAlgorithm:
    flag = [False, False]
    turn = 0

    def process0(self):
        self.flag[0] = True
        while self.flag[1]:
            if self.turn == 1:
                self.flag[0] = False
                while self.turn == 1:
                    pass  # Busy waiting
                self.flag[0] = True
        # Critical Section
        print("Process 0 in critical section")
        self.turn = 1
        self.flag[0] = False

    def process1(self):
        self.flag[1] = True
        while self.flag[0]:
            if self.turn == 0:
                self.flag[1] = False
                while self.turn == 0:
                    pass  # Busy waiting
                self.flag[1] = True
        # Critical Section
        print("Process 1 in critical section")
        self.turn = 0
        self.flag[1] = False

• 동작 특징:
  • Busy Waiting: CPU를 점유하며 대기하므로 리소스 효율이 낮음.
  • Deadlock 방지: turn 변수를 통해 교착 상태를 회피.

강점과 한계

적용 사례

• 초기 운영체제: 다중 프로세서 시스템에서 공유 메모리 동기화.
• 임베디드 시스템: 제한된 리소스 환경에서 경량화된 상호 배제 필요 시.
• 교육용 예제: 상호 배제 개념 설명과 병행 프로그래밍 기초 학습.

참고 및 출처