피터슨의 알고리즘

'''피터슨의 알고리즘'''(Peterson's algorithm)은 상호 배제를 위한 병렬 프로그래밍 알고리즘으로서, 공유 메모리를 활용하여 여러 개의 프로세스가 하나의 자원을 함께 사용할 때 문제가 발생하지 않도록 해준다. 수학자 개리 피터슨(Gary Peterson)은 이 알고리즘을 1981년에 로체스터 대학에서 발표하였다. 발표 당시의 알고리즘은 프로세스가 2개인 경우만 적용 가능하고, 이후 3개 이상의 경우에도 적용할 수 있는 방법이 논의되고 있다.
  '''bool''' flag2 // 불린 배열(Boolean array)
  '''int''' turn // 정수형 변수
  flag0   = false // false은 임계 구역 사용을 원하지 않음을 뜻함.
  flag1   = true
  turn      = 0 // 0 은 0번 프로세스를 가리킴, 1은 1번 프로세스를 가리킴
  '''P0''': flag0 = true // 임계 구역 사용을 원함
      turn = 1 // 1번 프로세스에게 차례가 감
      '''while'''( flag1 '''&&''' turn == 1 )
      {
           // flag1 이 turn1 을 가지고 있으므로
           //현재 사용중임
           // 임계 구역이 사용 가능한지 계속 확인
      }// 임계 구역
      ...
     // 임계 구역의 끝
    flag0 = false
 '''P1''': flag1 = true
     turn = 0
     '''while'''( flag0 '''&&''' turn == 0 )
     {
          // 임계 구역이 사용 가능한지 계속 확인
     }// 임계 구역
     ...
     // 임계 구역의 끝
     flag1 = 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 
#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, gBUCKETS;
/*
 * 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 
* 데커의 알고리즘
* 램포트의 빵집 알고리즘
*   자바 환경에서 피터슨의 알고리즘 구현: 문서와 소스 코드를 담고 있다.
분류:동시성 제어 알고리즘