Fetch-and-add - Implementation

Implementation

The fetch-and-add instruction behaves like the following function. Crucially, the entire function is executed atomically: no process can interrupt the function mid-execution and hence see a state that only exists during the execution of the function. This code only serves to help explain the behaviour of fetch-and-add; atomicity requires explicit hardware support and hence can not be implemented as a simple high level function.

<< atomic >> function FetchAndAdd(address location) { int value := *location *location := value + 1 return value }

With fetch-and-add primitive a mutual exclusion lock can be implemented as:

record locktype { int ticketnumber int turn } procedure LockInit( locktype* lock ) { lock.ticketnumber := 0 lock.turn := 0 } procedure Lock( locktype* lock ) { int myturn := FetchAndAdd( &lock.ticketnumber ) while lock.turn ≠ myturn skip // spin until lock is acquired } procedure UnLock( locktype* lock) { FetchAndAdd( &lock.turn ) }

These routines provide a mutual-exclusion lock when following conditions are met:

• Locktype data structure is initialized with function LockInit before use
• Number of tasks waiting for the lock does not exceed INT_MAX at any time
• Integer datatype used in lock values can 'wrap around' when continuously incremented