피터슨의 알고리즘
피터슨의 알고리즘(Peterson's algorithm)은 상호 배제를 위한 병렬 프로그래밍 알고리즘으로서, 공유 메모리를 활용하여 여러 개의 프로세스가 하나의 자원을 함께 사용할 때 문제가 발생하지 않도록 해준다. 수학자 개리 피터슨(Gary Peterson)은 이 알고리즘을 1981년에 로체스터 대학에서 발표하였다. 발표 당시의 알고리즘은 프로세스가 2개인 경우만 적용 가능하고, 이후 3개 이상의 경우에도 적용할 수 있는 방법이 논의되고 있다.
의사 코드
[편집]bool flag[2] // 불린 배열(Boolean array) int turn // 정수형 변수
flag[0] = false // false은 임계 구역 사용을 원하지 않음을 뜻함. flag[1] = true turn = 0 // 0 은 0번 프로세스를 가리킴, 1은 1번 프로세스를 가리킴
P0: flag[0] = true // 임계 구역 사용을 원함 turn = 1 // 1번 프로세스에게 차례가 감 while( flag[1] && turn == 1 ) { // flag[1] 이 turn[1] 을 가지고 있으므로 //현재 사용중임 // 임계 구역이 사용 가능한지 계속 확인 }// 임계 구역 ... // 임계 구역의 끝 flag[0] = false P1: flag[1] = true turn = 0 while( flag[0] && turn == 0 ) { // 임계 구역이 사용 가능한지 계속 확인 }// 임계 구역 ... // 임계 구역의 끝 flag[1] = false
이 알고리즘은 flag와 turn 변수를 사용한다. flag 값이 true이면 프로세스가 임계 구역에 들어가려고 하는 것을 나타낸다. 이 알고리즘은 임계 구역의 3가지 필수 기준(상호 배제, 진행 조건, 한계 대기)을 충족한다.
/* * ANSI C89 source, KNF style implementation of Peterson's Algorithm. * * Copyright (c) 2005, Matthew Mondor * Released in the public domain (may be licensed under the GFDL). * * Please fix any bugs as needed, preserving the KNF style and this comment, * unless considered inconvenient in which case you can do whatever you want * with the code. */ #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <pthread.h> 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); } /* 도달하지 않음 */ 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); } /* 도달하지 않음 */ return NULL; } /* * 두 스레드를 잠금(locking)없이 수행할 때 * 병행성 처리를 정상적으로 하도록 하는 임계 함수 */ 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]); } /* * 이 테스트 프로그램은 피터스 알고리즘을 사용하여, 잠금(locking) 기능 없이도 * 이중 병행 작업을 수행할 수 있다. 즉, 별도의 안전장치없이 동시에 수행할 경우 * 발생하는 공유 메모리 문제를 방지할 수 있다. */ /* 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); /* 도달하지 않음 */ return EXIT_SUCCESS; } 같이 보기
[편집]외부 링크
[편집]- (영어) 자바 환경에서 피터슨의 알고리즘 구현: 문서와 소스 코드를 담고 있다.