Peterson's algorithm
From Wikipedia, the free encyclopedia
Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows just two processes to share a single-use resource without conflict, using only shared memory for communication. [Note: Peterson's Algorithm can be generalised for more than two processes, as discussed in "Operating Systems Review, January 1990 ('Proof of a Mutual Exclusion Algorithm', M Hofri)".]
When working at the hardware level, Peterson's algorithm is typically not needed to achieve atomic access. Dual-ported RAM (DPRAM) comes equipped with a test-and-set or equivalent instruction, which processors use when accessing memory. Therefore concurrent operations maintain correct state during simultaneous accesses. Special software techniques are not required. It was formulated by Gary Peterson in 1981 at the University of Rochester.
Contents |
[edit] The algorithm
flag[0] = 0
flag[1] = 0
turn = 0
p0: flag[0] = 1 p1: flag[1] = 1
turn = 1 turn = 0
while( flag[1] && turn == 1 ); while( flag[0] && turn == 0 );
// do nothing // do nothing
// critical section // critical section
... ...
// end of critical section // end of critical section
flag[0] = 0 flag[1] = 0
The algorithm uses two variables, flag and turn. A flag value of 1 indicates, that the process wants to enter the critical section. The variable turn holds the id of the process whose turn it is. 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 of mutual exclusion:
[edit] Mutual exclusion
P0 and P1 can never be in the critical section at the same time: If P0 is in its critical section, then either flag[1] is false or turn is 0. In both cases, P1 cannot be in its critical section.
[edit] Progress requirement
If process P0 does not want to enter its critical section, P1 can enter it without waiting. There is not strict alternating between P0 and P1.
[edit] Bounded waiting
A process will not wait longer than one turn for entrance to the critical section: After giving priority to the other process, this process will run to completion and set its flag to 0, thereby allowing the other process to enter the critical section.
[edit] C implementation example using two POSIX threads
/*
* 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 {
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 int pa_f0, pa_f1, pa_last;
/* Shared */
#define BUCKETS 100
int gi, g[BUCKETS];
/*
* Initializes the pa system. To be called by the process once before
* initializing pa descriptors.
*/
void
pa_init(void)
{
pa_f0 = pa_f1 = pa_last = 0;
}
/*
* Initializes a pa descriptor for use by a thread.
* One thread should use id 0 and the other one 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;
}
/*
* Main loop of the first concurrent thread
*/
/* 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;
}
/*
* Main loop of the second concurrent thread
*/
/* 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;
}
/*
* Critical function which would normally have concurrency issues if two
* threads executed it without locking.
*/
void
threadx_critical(void)
{
int i;
/* Do something which would normally have dual concurrency issues */
for (i = 0; i < BUCKETS; i++)
g[i] = gi++;
for (i = 0; i < BUCKETS; i++)
(void) printf("g[%d] = %d\n", i, g[i]);
}
/*
* Test program which demonstrates that dual concurrency can be achieved
* without locking using Peterson's algorithm. We run two concurrent threads
* which voluntarily perform concurrency sensitive operations on a shared
* memory region (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);
/* Note: a real application would perform error checking */
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;
}
[edit] Note
Many modern CPUs reorder instruction execution and memory accesses to improve execution efficiency. 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 an out-of-order processor generally require use of such operations to work correctly to keep sequential operations from happening in an incorrect order.
Most such CPU's 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.
[edit] External links
- Java implementation of Peterson's algorithm, including documentation and source code
==
