[바미] 피터슨 알고리즘

피터슨 알고리즘?

피터슨 알고리즘(Peterson's Algorithm)은 두 개의 프로세스가 공유 자원에 동시에 접근하지 못하도록 하는 교착 상태를 피하기 위한 동기화 알고리즘입니다. 이 알고리즘은 상호 배제(mutual exclusion) 문제를 해결하는 데 사용되며, 프로세스가 교대로 임계 구역(critical section)에 진입할 수 있도록 보장합니다. 피터슨 알고리즘은 두 개의 프로세스 간에 작동하지만, 그 개념을 확장하면 더 많은 프로세스에서도 사용할 수 있습니다.

---

알고리즘의 핵심

피터슨 알고리즘은 두 개의 변수를 사용하여 다음과 같은 상호 배제를 구현합니다.

1. flag 배열: 각 프로세스가 임계 구역에 들어가고자 하는 의도를 나타냅니다. 예를 들어, flag[0]는 프로세스 0의 의도를, flag[1]는 프로세스 1의 의도를 나타냅니다.
2. turn 변수: 현재 임계 구역에 들어갈 차례가 누구인지 나타냅니다. turn 변수를 통해 두 프로세스가 번갈아 가면서 임계 구역에 진입할 수 있습니다.

---

알고리즘 구현

class PetersonAlgorithm {
  constructor() {
    this.flag = [false, false];
    this.turn = 0;
  }

  async enterCriticalSection(process) {
    const other = 1 - process;
    this.flag[process] = true;
    this.turn = other;

    while (this.flag[other] && this.turn === other) {
      // 바쁜 대기
      await new Promise(resolve => setTimeout(resolve, 0)); // 컨텍스트 스위치를 통해 차단 방지
    }

    // 임계 구역
    console.log(`프로세스 ${process}가 임계 구역에 들어갑니다`);

    // 임계 구역 실행 시간 시뮬레이션
    setTimeout(() => {
      this.leaveCriticalSection(process);
    }, Math.random() * 1000);
  }

  leaveCriticalSection(process) {
    this.flag[process] = false;
    console.log(`프로세스 ${process}가 임계 구역을 떠납니다`);
  }
}

const peterson = new PetersonAlgorithm();

function process0() {
  setInterval(() => {
    peterson.enterCriticalSection(0);
  }, Math.random() * 2000 + 500); // 0.5초에서 2.5초 사이의 랜덤 간격
}

function process1() {
  setInterval(() => {
    peterson.enterCriticalSection(1);
  }, Math.random() * 2000 + 500); // 0.5초에서 2.5초 사이의 랜덤 간격
}

// 두 프로세스 시작
process0();
process1();

---

알고리즘의 동작 순서

임계 구역에 들어가기 위한 준비 단계

this.flag[process] = true;

여기에서 프로세스 process가 임계 구역에 들어가고자 함을 나타냅니다.

this.turn = other;

여기에서 상대방 프로세스에게 양보하여, 임계 구역에 들어갈 수 있는 기회를 제공합니다.

상대방 프로세스가 임계 구역에 있거나 들어가려는 의도가 있는지 확인하는 단계

while (this.flag[other] && this.turn === other);

상대방 프로세스 other가 임계 구역에 들어가려는 의도가 있고, 그 차례인 경우, 대기합니다.

이 대기 동안 프로세스는 바쁜 대기(Busy wait)를 수행하지만, JavaScript에서는 비동기적으로 await를 사용하여 다른 작업을 처리할 수 있도록 합니다.

임계 구역에 진입

console.log(프로세스 ${process}가 임계 구역에 들어갑니다);

프로세스가 임계 구역에 진입했음을 나타냅니다.

 

그리고 임계 구역에서 실행하고자 하는 코드를 실행하게 됩니다. 아래 예제에서는 setTimeout을 사용하여 임계 구역에서의 작업 시간을 시뮬레이션합니다.

임계 구역을 나가기

this.flag[process] = false;

프로세스가 임계 구역에서 나왔음을 표시합니다.

console.log(프로세스 ${process}가 임계 구역을 떠납니다);

프로세스가 임계 구역을 떠났음을 나타냅니다.

---

피터슨 알고리즘의 특성

상호 배제 (Mutual Exclusion)

두 프로세스가 동시에 임계 구역에 들어가지 않도록 보장합니다.

진행 (Progress)

임계 구역에 들어가려는 프로세스가 없는 경우, 어떤 프로세스도 임계 구역에 들어갈 수 있어야 합니다. 

즉, 대기 중인 프로세스가 임계 구역에 들어갈 수 있도록 합니다.

한정 대기 (Bounded Waiting)

각 프로세스는 임계 구역에 들어가기 위해 무한정 기다리지 않습니다. 

즉, 프로세스가 임계 구역에 들어가는 차례가 오면, 상대방 프로세스는 일정 시간 내에 임계 구역을 양보하게 됩니다.

---

피터슨 알고리즘의 한계

하드웨어 제약

피터슨 알고리즘은 모든 프로세스가 메모리에 접근하는 동안 정확한 순서대로 실행되어야 합니다. 따라서, 이 알고리즘은 메모리의 일관성이 보장되는 환경에서만 제대로 작동합니다. 메모리 일관성을 보장하지 않는 시스템에서는 피터슨 알고리즘의 신뢰성이 떨어질 수 있습니다.

 

확장성 문제

피터슨 알고리즘은 오직 두 프로세스 사이에서만 자원을 독점적으로 사용할 수 있게 해줍니다. 세 개 이상의 프로세스가 동시에 작동해야 하는 상황에서는 이 알고리즘이 효과적이지 않습니다. 이러한 경우에는 더 많은 프로세스를 지원하는 램포트의 빵집 알고리즘과 같은 대안이 필요합니다.

---

피터슨 알고리즘의 장점

단순성과 명료성

피터슨 알고리즘은 이해하고 구현하기 비교적 쉽습니다. 두 개의 프로세스 간의 상호 배제를 해결하는 간단하고 명료한 방법을 제공합니다.

 

소프트웨어 기반 솔루션

하드웨어 지원 없이 소프트웨어만으로 상호 배제를 달성할 수 있습니다. 이는 하드웨어 기반의 락이나 세마포어 없이도 프로세스 간의 동기화를 가능하게 합니다.

 

상호 배제 보장

피터슨 알고리즘은 두 개의 프로세스가 동시에 임계 구역에 들어가지 않도록 보장합니다. 이를 통해 자원의 일관성과 무결성을 유지할 수 있습니다.

공정성

이 알고리즘은 번갈아 가며 임계 구역에 들어갈 수 있도록 보장하여 특정 프로세스가 임계 구역에 독점적으로 접근하는 것을 방지합니다. 이는 무한 대기를 피하는 데 도움이 됩니다.

학습적 가치

피터슨 알고리즘은 동시성 제어와 관련된 기본 개념을 학습하는 데 매우 유용합니다. 상호 배제, 진입/퇴출 프로토콜, 바쁜 대기 등의 개념을 이해하는 데 도움이 됩니다.

 

피터슨 알고리즘은 단순성, 공정성, 상호 배제 보장 등의 장점 때문에 두 개의 프로세스가 자원을 공유할 때 매우 유용합니다.

특히, 학습 환경이나 간단한 동시성 문제가 있는 소규모 시스템에서는 매우 유효한 알고리즘이기 때문에 피터슨 알고리즘은 위 한계에도 불구하고 사용되고 있습니다.