Ray`s Tech Lab

피터슨의 알고리즘

컴퓨터 시스템에서 여러 프로세스가 동시에 실행될 때, 공유 자원에 대해 여러 프로세스에서 동시 접근이 가능하다면 데이터 불일치 등의 문제가 발생할 수 있습니다. 이 때 공유 자원에 대해 동시 접근이 발생 가능한 영역을 임계 영역(Critical section)이라 부르며, 이 임계 영역에서 비롯되는 문제들을 막으려면 다음과 같은 요구사항을 만족해야 합니다.

1. 상호 배제 (Mutual Exclusion)

: 한 번에 하나의 프로세스만이 임계 구역에 들어갈 수 있어야 합니다.

2. 진행 (Progress)

: 임계 구역에 들어가려는 프로세스가 없을 때, 어느 프로세스도 임계 구역에 들어갈 수 있어야 합니다.

3. 한정 대기 (Bounded Waiting)

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

피터슨의 알고리즘(Peterson's Algorithm)은 위 요구사항들을 만족하는 고전적인 알고리즘으로, 두 프로세스 간의 상호 배제를 위해 만들어졌습니다. 1980년대에 게리 피터슨(Gary L. Peterson)에 의해 제안됐으며, 상호 배제 문제를 간단하고 효율적으로, 이해하기 쉽고 최소한의 변수만을 사용하여 구현할 수 있다는 장점이 있습니다.

피터슨의 알고리즘은 flag 배열과 turn 변수를 사용하여 두 프로세스가 임계 영역에 동시에 진입(즉 경쟁 상태 발생)하는 것을 방지합니다. flag 배열은 각 프로세스가 임계 구역에 들어가기를 원하는지를 표시하며, turn 변수는 임계 구역에 들어갈 차례인 프로세스를 나타내는데요. 이 간단한 구조 덕에 직관적이고 구현하기 쉬운 상호 배제 해결책으로 널리 알려져 있습니다.

피터슨의 알고리즘 동작 순서

피터슨의 알고리즘은 다음과 같은 순서로 각 작업이 순서대로 임계 영역에 들어가게 합니다. 

1. 임계 구역 진입 요청

: 프로세스가 임계 구역(critical section)에 들어가고자 할 때, 자신의 flag를 true로 설정하여 진입 의사를 표시합니다.

2. 양보 설정

: 프로세스는 turn 변수를 상대방 프로세스의 번호로 설정하고, 이를 통해 상대방 프로세스에게 양보할 의사를 나타냅니다.

3. 대기 상태

: 프로세스는 상대방 프로세스의 flag가 true이고, turn이 상대방 프로세스의 번호인 동안 계속해서 기다립니다(상대방 프로세스가 임계 구역에 들어가고자 할 경우 상대방에게 우선권을 주기 위함)

4. 임계 구역 진입

: 상대방 프로세스가 임계 구역에 들어가고자 하지 않거나, turn이 자신의 번호로 설정될 때까지 기다린 후 임계 구역에 진입합니다.

5. 임계 구역 종료

: 임계 구역에서의 작업을 마치면, 자신의 flag를 false로 설정하여 임계 구역에서 나왔음을 알립니다.

6. 비임계 구역 작업

: 비임계 구역에서 다른 작업을 수행합니다.

코드로 나타내면 다음과 같습니다.

// 변수 선언
boolean flag[2] = {false, false};
int turn;

function process0() {
    while (true) {
        // 1. 임계 구역 진입 요청
        flag[0] = true;
        
        // 2. 양보 설정
        turn = 1;
        
        // 3. 대기 상태
        while (flag[1] == true && turn == 1) {
            // busy-wait
        }
        
        // 4. 임계 구역 진입
        // 임계 구역에서 수행할 작업
        print("Process 0 in critical section")

        // 5. 임계 구역 종료
        flag[0] = false;

        // 6. 비임계 구역 작업
        // 비임계 구역에서 수행할 작업
        print("Process 0 in non-critical section")
    }
}

function process1() {
    while (true) {
        // 1. 임계 구역 진입 요청
        flag[1] = true;
        
        // 2. 양보 설정
        turn = 0;
        
        // 3. 대기 상태
        while (flag[0] == true && turn == 0) {
            // busy-wait
        }

        // 4. 임계 구역 진입
        // 임계 구역에서 수행할 작업
        print("Process 1 in critical section")

        // 5. 임계 구역 종료
        flag[1] = false;

        // 6. 비임계 구역 작업
        // 비임계 구역에서 수행할 작업
        print("Process 1 in non-critical section")
    }
}

피터슨의 알고리즘 문제점

1. 두 개 프로세스에서만 적용 가능

: 피터슨의 알고리짐은 기본적으로 두 개의 프로세스 사이에서만 상호 배제를 보장합니다. 2개보다 많은 프로세스를 다룰 경우 알고리즘을 확장해야 하지만, 코드가 복잡해지고 효율성이 떨어질 수 있습니다.

2. Busy waiting

: 피터슨의 알고리즘은 다른 프로세스가 임계 영역에 들어가있는 동안 다른 프로세스는 무한 루프를 통해 대기(Busy waiting)하는데, 이는 CPU 자원의 낭비 및 효율성 저하의 원인이 됩니다. 또한 실시간 시스템인 경우, Busy waiting은 일종의 지연 현상을 초래할 수도 있습니다.