피터슨(Peterson) 알고리즘은 두 개의 프로세스가 임계구역(Critical Section)에 동시에 접근하지 못하도록 보장하는 동기화 알고리즘입니다. 이 알고리즘은 소프트웨어만으로 상호 배제를 구현할 수 있어, 간단하면서도 이론적으로 강력한 방법으로 알려져 있습니다. 피터슨 알고리즘은 다음 세 가지 조건인 상호 배제(mutual exclusion), 진행(progress), 한정된 대기(bounded waiting)를 만족합니다.
피터슨 알고리즘 작동 원리
피터슨 알고리즘은 두 개의 공유 변수(flag와 turn)를 사용하여 두 프로세스가 상호 배제를 유지하며 임계구역에 진입하도록 합니다.
1. flag: 각 프로세스는 자신이 임계구역에 들어가기를 원할 때 flag 변수를 true로 설정합니다.
2. turn: 두 프로세스 중 누구에게 임계구역을 우선 허용할지를 나타내는 변수입니다. 이 변수는 프로세스 간 양보를 위한 일종의 ‘권리’ 표시입니다.
피터슨 알고리즘의 동작 순서
피터슨 알고리즘을 프로세스 P0와 P1의 예로 설명하겠습니다.
1. 임계구역에 진입 요청 (flag 설정):
• P0가 임계구역에 들어가기를 원하면, flag[0] = true로 설정하고 turn = 1로 설정합니다.
• 이는 P1이 들어가기를 원할 경우 P1에게 우선권이 있음을 의미합니다.
2. 임계구역 진입 조건 확인:
• P0는 임계구역에 진입하기 전에 flag[1] == true와 turn == 1 조건을 확인합니다.
• 만약 P1이 임계구역에 들어가고자 하여 flag[1]이 true이고 turn이 1인 경우, P0는 대기합니다.
• 반대로, P1이 임계구역에 들어가고자 하지 않거나 turn이 0이면 P0는 임계구역에 진입합니다.
3. 임계구역 수행:
• P0가 임계구역에 들어가면, P1은 대기 상태가 됩니다. 이 상태에서는 flag와 turn 값이 변경되지 않으므로 다른 프로세스가 들어올 수 없습니다.
4. 임계구역 종료 후 해제 (flag 해제):
• P0는 임계구역 작업을 마치면 flag[0] = false로 설정하여, P1이 임계구역에 들어갈 수 있도록 합니다.
5. 반복 (P1에 대해서도 동일하게 적용):
• P1이 임계구역에 진입하고자 하면, flag[1] = true로 설정하고 turn = 0으로 설정합니다. 이후 P0과 동일한 절차를 통해 P1이 임계구역에 들어갑니다.
피터슨 알고리즘의 장점
• 상호 배제 보장: 두 프로세스 중 하나만 임계구역에 진입할 수 있습니다.
• 진행 보장: 임계구역에 진입할 수 있는 프로세스가 있다면, 진행을 방해하는 프로세스가 없으면 곧바로 임계구역에 들어갈 수 있습니다.
• 한정된 대기 보장: 특정 프로세스가 무한정 대기하지 않도록, 양측에서 번갈아가며 기회를 가질 수 있도록 합니다.피터슨 알고리즘의 한계
• 두 개의 프로세스만 지원: 피터슨 알고리즘은 두 개의 프로세스만을 지원합니다. 다중 프로세스 환경에서는 적용이 어렵습니다.
• 메모리 일관성 문제: 현대의 멀티코어 시스템에서는 메모리 일관성 문제로 인해 피터슨 알고리즘이 제대로 작동하지 않을 수 있습니다. 이는 주기적으로 메모리를 최신 상태로 유지해야 하기 때문입니다.피터슨 알고리즘은 간단하면서도 임계구역 문제를 해결하는 좋은 예입니다. 다만, 현재의 멀티코어 CPU 환경에서는 하드웨어 동기화 기법을 통해 상호 배제를 구현하는 경우가 더 많습니다.
