Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981. While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.

The algorithm 
The algorithm uses two variables: flag and turn. A flag[n] value of true indicates that the process n wants to enter the critical section. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting turn to 0.

The algorithm satisfies the three essential criteria to solve the critical-section problem. The while condition works even with preemption.

The three criteria are mutual exclusion, progress, and bounded waiting.

Since turn can take on one of two values, it can be replaced by a single bit, meaning that the algorithm requires only three bits of memory.

Mutual exclusion 
P0 and P1 can never be in the critical section at the same time. If P0 is in its critical section, then flag[0] is true. In addition, either flag[1] is false (meaning that P1 has left its critical section), or turn is 0 (meaning that P1 is just now trying to enter the critical section, but graciously waiting), or P1 is at label P1_gate (trying to enter its critical section, after setting flag[1] to true but before setting turn to 0 and busy waiting). So if both processes are in their critical sections, then we conclude that the state must satisfy flag[0] and flag[1] and turn = 0 and turn = 1. No state can satisfy both turn = 0 and turn = 1, so there can be no state where both processes are in their critical sections.
(This recounts an argument that is made rigorous in.)

Progress 
Progress is defined as the following: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in making the decision as to which process will enter its critical section next. Note that for a process or thread, the remainder sections are parts of the code that are not related to the critical section. This selection cannot be postponed indefinitely. A process cannot immediately re-enter the critical section if the other process has set its flag to say that it would like to enter its critical section.

Bounded waiting 
Bounded waiting, or bounded bypass, means that the number of times a process is bypassed by another process after it has indicated its desire to enter the critical section is bounded by a function of the number of processes in the system. In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section.

Filter algorithm: Peterson's algorithm for more than two processes 

The filter algorithm generalizes Peterson's algorithm to  processes. Instead of a boolean flag, it requires an integer variable per process, stored in a single-writer/multiple-reader (SWMR) atomic register, and  additional variables in similar registers. The registers can be represented in pseudocode as arrays:

 level : array of N integers
 last_to_enter : array of N − 1 integers

The  variables take on values up to , each representing a distinct "waiting room" before the critical section. Processes advance from one room to the next, finishing in room , which is the critical section. Specifically, to acquire a lock, process  executes

 i ← ProcessNo
 for ℓ from 0 to N − 1 exclusive
     level[i] ← ℓ
     last_to_enter[ℓ] ← i
     while last_to_enter[ℓ] = i and there exists k ≠ i, such that level[k] ≥ ℓ
         wait

To release the lock upon exiting the critical section, process  sets  to −1.

That this algorithm achieves mutual exclusion can be proven as follows. Process  exits the inner loop when there is either no process with a higher level than , so the next waiting room is free; or, when , so another process joined its waiting room. At level zero, then, even if all  processes were to enter waiting room zero at the same time, no more than  will proceed to the next room, the final one finding itself the last to enter the room. Similarly, at the next level,  will proceed, etc., until at the final level, only one process is allowed to leave the waiting room and enter the critical section, giving mutual exclusion.

Unlike the two-process Peterson algorithm, the filter algorithm does not guarantee bounded waiting.

Note
When working at the hardware level, Peterson's algorithm is typically not needed to achieve atomic access. 
Some processors have special instructions, like test-and-set or compare-and-swap, which, by locking the memory bus, can be used to provide mutual exclusion in SMP systems.

Most modern CPUs reorder memory accesses to improve execution efficiency (see memory ordering for types of reordering allowed). Such processors invariably give some way to force ordering in a stream of memory accesses, typically through a memory barrier instruction. Implementation of Peterson's and related algorithms on processors that reorder memory accesses generally requires use of such operations to work correctly to keep sequential operations from happening in an incorrect order. Note that reordering of memory accesses can happen even on processors that don't reorder instructions (such as the PowerPC processor in the Xbox 360).

Most such CPUs also have some sort of guaranteed atomic operation, such as XCHG on x86 processors and load-link/store-conditional on Alpha, MIPS, PowerPC, and other architectures. These instructions are intended to provide a way to build synchronization primitives more efficiently than can be done with pure shared memory approaches.

See also 
 Dekker's algorithm
 Eisenberg & McGuire algorithm
 Lamport's bakery algorithm
 Szymański's algorithm
 Semaphores

Footnotes

External links
https://elixir.bootlin.com/linux/latest/source/arch/arm/mach-tegra/sleep.S Peterson's algorithm implementation

Concurrency control algorithms
Articles with example C code
피터슨의 알고리즘(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가지 필수 기준(상호 배제, 진행 조건, 한계 대기)을 충족한다.

두 POSIX 스레드를 활용하여 C언어로 구현한 예 

/*
 * 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;
}

같이 보기 
 데커의 알고리즘
 램포트의 빵집 알고리즘

외부 링크 
  자바 환경에서 피터슨의 알고리즘 구현: 문서와 소스 코드를 담고 있다.

동시성 제어 알고리즘