피터슨의 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
피터슨의 알고리즘은 두 프로세스 간의 상호 배제를 구현하기 위해 `flag`와 `turn` 변수를 사용하는 알고리즘이다. 각 프로세스는 임계 구역에 진입하기 전에 자신의 `flag` 값을 true로 설정하고 `turn` 값을 상대방 프로세스에게 양보하며, 상대방 프로세스의 `flag` 값이 false이거나 `turn` 값이 자신의 차례가 될 때까지 대기한다. 이 알고리즘은 상호 배제, 진행, 한정된 대기 조건을 모두 만족하며, C 언어로 구현할 수 있다. 필터 알고리즘은 피터슨 알고리즘을 N개 이상의 프로세스에 적용할 수 있도록 일반화한 것으로, 각 프로세스의 레벨을 나타내는 `level` 변수와 각 레벨에서 마지막으로 들어온 프로세스를 추적하는 `last_to_enter` 변수를 사용한다. 최신 CPU 환경에서는 메모리 접근 순서를 보장하기 위해 메모리 장벽 명령을 사용해야 하며, 원자 연산을 지원하는 특수 명령어를 활용하여 더 효율적인 동기화를 구현할 수 있다.
더 읽어볼만한 페이지
- 동시성 제어 알고리즘 - 데커의 알고리즘
데커 알고리즘은 두 프로세스 간 상호 배제를 해결하기 위해 만들어진 최초의 소프트웨어 기반 알고리즘 중 하나로, 공유 자원에 대한 동시 접근을 막고 임계 영역 진입 우선순위를 조정하지만, 현대 운영체제에서는 효율성 문제로 잘 사용되지 않으나 상호 배제 개념 이해에 기여한다. - 동시성 제어 알고리즘 - 스핀락
스핀락은 락 획득을 위해 반복적으로 확인하며 대기하는 동기화 메커니즘으로, 성능 향상을 위한 최적화 기법과 하이퍼 스레딩 환경에서의 성능 향상 기법이 존재하지만, CPU 자원 낭비라는 단점으로 인해 다양한 대안 방식이 모색되고 있다.
| 피터슨의 알고리즘 | |
|---|---|
| 기본 정보 | |
| 이름 | 피터슨 알고리즘 |
| 종류 | 동시성 제어 |
| 문제 영역 | 상호 배제 |
| 고안자 | 개리 L. 피터슨 |
| 발표 년도 | 1981년 |
| 세부 사항 | |
| 요구 사항 | 두 개의 프로세스만 해당 공유 메모리에 대한 읽기 및 쓰기 작업은 원자적이어야 함 |
| 복잡도 | O(1) |
| 특징 | 간단하고 효율적 교착 상태 및 기아 상태 방지 |
| 구현 | |
| 사용 언어 | C C++ Java Python C# |
2. 알고리즘
피터슨 알고리즘은 두 프로세스 간의 상호 배제를 구현하기 위해 `flag`와 `turn` 두 변수를 사용한다. `flag[n]`의 값이 `true`이면 프로세스 `n`이 임계 구역에 진입하려 함을 나타낸다. 프로세스 P0은 P1이 임계 구역에 진입하려 하지 않거나(flag[1] == false), P1이 `turn`을 `0`으로 설정하여 P0에게 우선순위를 부여한 경우에 임계 구역에 진입할 수 있다.[1]
이 알고리즘은 선점형 환경에서도 작동하며, 임계 구역 문제 해결에 필요한 세 가지 필수 조건(상호 배제, 진행 조건, 한계 대기)을 충족한다.[1][3]
`turn`은 0 또는 1의 값을 가질 수 있으므로, 단일 비트로 표현할 수 있다. 즉, 이 알고리즘은 3비트의 메모리만 필요로 한다.[4]
2. 1. 변수 설명
`flag`는 각 프로세스가 임계 구역에 진입할 의사가 있는지 나타내는 불린 배열이다. `flag[n]`이 `true`이면 프로세스 `n`이 임계 구역에 진입하려 함을 의미한다. `turn`은 임계 구역에 진입할 차례를 나타내는 정수형 변수이다. `turn` 값은 현재 우선순위를 가진 프로세스의 식별자를 나타낸다.[1]2. 2. 작동 원리
피터슨의 알고리즘은 `flag`와 `turn`이라는 두 변수를 사용한다. `flag[n]`의 값이 `true`이면 프로세스 `n`이 임계 구역에 진입하려 함을 나타낸다. 프로세스 P0은 P1이 임계 구역에 진입하려 하지 않거나, P1이 `turn`을 `0`으로 설정하여 P0에게 우선순위를 부여한 경우에 임계 구역에 진입할 수 있다.[1]| P0 | P1 |
|---|---|
각 프로세스는 임계 구역에 진입하기 전에 자신의 `flag` 값을 `true`로 설정하고, `turn` 값을 상대방 프로세스에게 양보한다. 프로세스는 `while` 루프를 통해 상대방 프로세스의 `flag` 값이 `false`이거나 `turn` 값이 자신의 차례가 될 때까지 대기한다. 임계 구역 작업을 마친 프로세스는 자신의 `flag` 값을 `false`로 설정하여 다른 프로세스가 임계 구역에 진입할 수 있도록 한다.
`turn`은 두 가지 값 중 하나를 가질 수 있으므로, 단일 비트로 대체될 수 있으며, 이는 알고리즘이 3비트의 메모리만 필요로 함을 의미한다.[4]
2. 3. 의사 코드
flag와 turn이라는 두 변수를 사용하는 피터슨 알고리즘의 의사 코드는 다음과 같다.`flag[n]`의 값이 `true`이면, 프로세스 `n`이 임계 구역에 진입하려 함을 나타낸다. 프로세스 P0은 P1이 임계 구역에 진입하려 하지 않거나, P1이 `turn`을 `0`으로 설정하여 P0에게 우선순위를 부여한 경우에 임계 구역에 진입할 수 있다.[1]
| P0 | P1 |
|---|---|
이 알고리즘은 선점형 멀티태스킹 환경에서도 작동하며, 상호 배제, 진행, 제한된 대기의 세 가지 조건을 만족한다.[3]
`turn` 변수는 0 또는 1의 값을 가지므로, 단일 비트로 표현할 수 있다. 즉, 이 알고리즘은 3비트의 메모리만 필요로 한다.[4]
2. 4. 필수 조건 충족
이 알고리즘은 임계 구역 문제 해결에 필요한 세 가지 조건을 충족한다.[1] 세 가지 조건은 상호 배제, 진행, 한정된 대기이다.[3]상호 배제 (Mutual exclusion)P0과 P1은 동시에 임계 구역에 들어갈 수 없다. 만약 P0이 임계 구역에 있다면, `flag[0]`은 참이다. 또한, 다음 조건 중 하나를 만족해야 한다.[5]
- `flag[1]`이 `false` (P1이 임계 구역을 벗어났음을 의미)
- `turn`이 `0` (P1이 막 임계 구역에 진입하려 하지만, 기다리고 있음을 의미)
- P1이 `P1_gate` 레이블에 있음 ( `flag[1]`을 `true`로 설정한 후 `turn`을 `0`으로 설정하기 전, 즉 바쁜 대기를 하려는 시점)
따라서 두 프로세스 모두 임계 구역에 있다면, `flag[0]`과 `flag[1]`이 모두 참이고, `turn`이 `0`인 동시에 `1`이어야 한다. 이는 불가능하므로, 두 프로세스가 동시에 임계 구역에 있을 수 없다.
진행 (Progress)임계 구역에서 실행 중인 프로세스가 없고, 일부 프로세스가 임계 구역에 들어가기를 원한다면, 나머지 구역에서 실행 중이지 않은 프로세스만 다음에 어떤 프로세스가 임계 구역에 들어갈지 결정하는 데 참여할 수 있다. 이 선택은 무기한 연기될 수 없다.[3] 다른 프로세스가 임계 구역에 들어가고 싶다는 플래그를 설정한 경우, 프로세스는 즉시 임계 구역에 다시 들어갈 수 없다.
한정된 대기 (Bounded waiting)제한된 우회라고도 하며, 임계 구역에 진입하려는 의사를 표시한 후 다른 프로세스에 의해 프로세스가 우회되는 횟수가 제한됨을 의미한다. 피터슨의 알고리즘에서 프로세스는 임계 구역에 진입하기 위해 한 번의 턴 이상을 기다리지 않는다.
3. C 언어 구현 예시 (POSIX 스레드)
c
/*
- 피터슨 알고리즘의 ANSI C89 소스, KNF 스타일 구현.
- 저작권 (c) 2005, 매튜 몬도르
- 퍼블릭 도메인으로 릴리스 (GFDL로 라이선스 될 수 있음).
- 필요에 따라 버그를 수정하고 KNF 스타일과 이 주석을 유지하십시오.
- 코드를 원하는 대로 사용할 수 없는 경우 불편하다고 간주됩니다.
- /
#include
#include
#include
#include
struct pa_desc {
volatile int *f0, *f1;
int last;
};
void pa_init(void);
void pa_desc_init(struct pa_desc *, int);
void pa_desc_lock(struct pa_desc *);
void pa_desc_unlock(struct pa_desc *);
void *thread0_main(void *);
void *thread1_main(void *);
void threadx_critical(void);
int main(int, char **);
static volatile int pa_f0, pa_f1, pa_last;
/* 공유 */
#define BUCKETS 100
int gi, g[BUCKETS];
/*
- pa 시스템을 초기화합니다. pa 디스크립터를 초기화하기 전에 프로세스에서 한 번 호출해야 합니다.
- /
void
pa_init(void)
{
pa_f0 = pa_f1 = pa_last = 0;
}
/*
- 스레드에서 사용할 pa 디스크립터를 초기화합니다.
- 한 스레드는 id 0을 사용하고 다른 스레드는 id 1을 사용해야 합니다.
- /
void
pa_desc_init(struct pa_desc *d, int id)
{
assert(id == 0 || id == 1);
if (id == 0) {
d->f0 = &pa_f0;
d->f1 = &pa_f1;
d->last = 1;
} else if (id == 1) {
d->f0 = &pa_f1;
d->f1 = &pa_f0;
d->last = 0;
}
}
void
pa_desc_lock(struct pa_desc *d)
{
for (*d->f0 = 1, pa_last = d->last;
- d->f1 == 1 && pa_last == d->last; ) ;
}
void
pa_desc_unlock(struct pa_desc *d)
{
- d->f0 = 0;
}
/*
- 첫 번째 동시 스레드의 메인 루프
- /
/* ARGSUSED */
void *
thread0_main(void *args)
{
struct pa_desc d;
pa_desc_init(&d, 0);
for (;;) {
pa_desc_lock(&d);
threadx_critical();
pa_desc_unlock(&d);
}
/* NOTREACHED */
return NULL;
}
/*
- 두 번째 동시 스레드의 메인 루프
- /
/* ARGSUSED */
void *
thread1_main(void *args)
{
struct pa_desc d;
pa_desc_init(&d, 1);
for (;;) {
pa_desc_lock(&d);
threadx_critical();
pa_desc_unlock(&d);
}
/* NOTREACHED */
return NULL;
}
/*
- 두 스레드가 잠금 없이 실행하면 일반적으로 동시성 문제가 발생하는 중요한 함수.
- /
void
threadx_critical(void)
{
int i;
/* 일반적으로 이중 동시성 문제가 발생하는 작업을 수행합니다. */
for (i = 0; i < BUCKETS; i++)
g[i] = gi++;
for (i = 0; i < BUCKETS; i++)
(void) printf("g[%d] = %d\n", i, g[i]);
}
/*
- 피터슨 알고리즘을 사용하여 잠금 없이 이중 동시성을 달성할 수 있음을 보여주는 테스트 프로그램입니다. 두 개의 동시 스레드를 실행하여 공유 메모리 영역(gi, g[BUCKETS])에서 동시성에 민감한 작업을 자발적으로 수행합니다.
- /
/* ARGSUSED */
int
main(int argc, char **argv)
{
pthread_t tid1, tid2;
pthread_attr_t tattr;
gi = 0;
pa_init();
pthread_attr_init(&tattr);
pthread_attr_setdetachstate(&tattr, 0);
/* 참고: 실제 응용 프로그램은 오류 검사를 수행합니다. */
pthread_create(&tid1, &tattr, thread0_main, NULL);
pthread_create(&tid2, &tattr, thread1_main, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
/* NOTREACHED */
return EXIT_SUCCESS;
}
4. 필터 알고리즘 (N개 프로세스)
필터 알고리즘은 피터슨의 알고리즘을 2개 이상의 프로세스(N > 2)에 대해 일반화한 것이다.[6] 이 알고리즘에서는 부울 플래그 대신 프로세스마다 정수 변수를 사용하며, 이는 단일 작성자/다중 읽기(SWMR) 원자 레지스터에 저장된다. N-1개의 추가 변수 또한 유사한 레지스터에 필요하며, 배열로 표현될 수 있다.
4. 1. 변수 설명
`level`은 각 프로세스의 현재 레벨을 나타내는 N개의 정수 배열이다. `last_to_enter`는 각 레벨에서 마지막으로 들어온 프로세스를 나타내는 N-1개의 정수 배열이다.[6]4. 2. 작동 원리
필터 알고리즘은 피터슨의 알고리즘을 2개 이상의 프로세스()에 대해 일반화한 것이다.[6] 부울 플래그 대신, 프로세스당 정수 변수가 필요하며, 이는 단일-작성자/다중-읽기(SWMR) 원자 레지스터에 저장된다. 또한, 개의 추가 변수가 유사한 레지스터에 필요하다. 레지스터는 배열로 표현될 수 있다.```
level: N개의 정수 배열
last_to_enter: N − 1개의 정수 배열
```
변수는 최대 값을 가지며, 각 변수는 임계 구역 앞에 있는 별개의 "대기실"을 나타낸다. 프로세스는 한 방에서 다음 방으로 진행하며, 임계 구역인 방 에서 완료된다. 구체적으로, 잠금을 획득하기 위해 프로세스 는 다음을 실행한다.
```
i ← 프로세스 번호
'''for''' ℓ '''from''' 0 '''to''' N − 1 '''exclusive'''
level[i] ← ℓ
last_to_enter[ℓ] ← i
'''while''' last_to_enter[ℓ] = i '''and''' k ≠ i가 존재하고, level[k] ≥ ℓ
'''wait'''
```
임계 구역을 종료하여 잠금을 해제하려면 프로세스 가 를 −1로 설정한다.
이 알고리즘이 상호 배제를 보장하는 이유는 다음과 같다. 프로세스 는 보다 높은 레벨의 프로세스가 없거나, 다음 대기실이 비어 있을 때, 또는 일 때(즉, 다른 프로세스가 해당 대기실에 들어왔을 때) 내부 루프를 종료한다. 레벨 0에서 모든 개의 프로세스가 동시에 대기실 0에 들어가더라도, 개 이하의 프로세스가 다음 방으로 진행하며, 마지막 방에 있는 프로세스는 해당 방에 마지막으로 들어온 프로세스가 된다. 마찬가지로, 다음 레벨에서는 개가 진행되며, 등등 마지막 레벨에서는 하나의 프로세스만 대기실을 떠나 임계 구역에 들어갈 수 있으므로 상호 배제가 보장된다.
두 프로세스 피터슨 알고리즘과 달리, 필터 알고리즘은 경계된 대기를 보장하지 않는다.
5. 하드웨어 수준 고려 사항
최근 CPU는 성능 향상을 위해 메모리 접근 순서를 재정렬(아웃 오브 오더 실행)할 수 있다. 이러한 환경에서 피터슨 알고리즘이 올바르게 작동하려면 메모리 배리어 명령어를 사용하여 메모리 접근 순서를 명시적으로 지정해야 할 수 있다.
대부분의 CPU는 원자적 연산을 지원하는 특수 명령어를 제공한다. 예를 들어, x86 프로세서의 `XCHG` 명령어와 알파, MIPS, PowerPC 및 기타 아키텍처의 Load-Link/Store-Conditional 명령어가 있다. 이러한 명령어는 순수한 공유 메모리 접근 방식보다 더 효율적으로 동기화 기본 요소를 구축하는 방법을 제공한다.
참조
[1]
논문
"Myths About the Mutual Exclusion Problem"
[2]
간행물
Proof of a Mutual Exclusion Algorithm
Operating Systems Review
1990-01
[3]
서적
Operating Systems Concepts: Seventh Edition
John Wiley and Sons
[4]
서적
Concurrent Programming: Algorithms, Principles, and Foundations
Springer Science & Business Media
[5]
서적
On Concurrent Programming
Springer Verlag
[6]
서적
The Art of Multiprocessor Programming
Elsevier
[7]
간행물
Proof of a Mutual Exclusion Algorithm
Operating Systems Review
1990-01
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com