Peterson's algorithm

Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary Peterson in 1981 at the University of Rochester. While Peterson's original formulation worked with only two processes, the algorithm can be generalised for more than two, as discussed in "Operating Systems Review, January 1990 ('Proof of a Mutual Exclusion Algorithm', M Hofri)"."

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:

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 1 and either flag [1] is false or turn is 0. In both cases, P1 cannot be in its critical section.

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.

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.

C implementation example using two POSIX threads

/* Example code that simulates two sequences of bank transactions in parallel. The critical section is the money transfer from one account to the other (there may be no money disappearing or suddenly appearing).
*/

#include
#include
#include
#include

volatile int flag [2] ;volatile int turn;

volatile int rich_guy = 30000;volatile int poor_guy = 0;

void prologue(int self){ flag [self] = 1; turn = !self; while (flag [!self] && turn = !self);}

void epilogue(int self){ flag [self] = 0; }

bool transfer_money(){ int money; money = rand() % (1000); if (money > rich_guy) money = rich_guy; printf("($%d) ", money); poor_guy += money; rich_guy -= money; return (rich_guy <= 0);}

void *bank_transaction(void *x){ int id = (int)x; bool done; do { prologue(id); printf("Transaction %d will transfer money... ", id); done = transfer_money(); epilogue(id); } while (!done); return NULL;}

int main(void){ pthread_t transaction [2] ; printf("Rich guy has $%d " "Poor guy has $%d " "Starting two parallel bank transfers... ", rich_guy, poor_guy); pthread_create(&transaction [0] , NULL, bank_transaction, (void *)0); pthread_create(&transaction [1] , NULL, bank_transaction, (void *)1); puts("Waiting for transactions..."); pthread_join(transaction [0] , NULL); pthread_join(transaction [1] , NULL); printf("Done. " "Rich guy has $%d " "Poor guy has $%d ", rich_guy, poor_guy); return 0;}

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 that, by locking the memory bus, can be used to provide mutual exclusion in SMP systems.

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.

External links

* [http://paul.luminos.nl/documents/show_document.php?d=339 Java implementation of Peterson's algorithm] , including documentation and source code

See also

* Dekker's algorithm
* Lamport's bakery algorithm