28 Synchronisation Hardware

• Many systems provide hardware support for critical section
• Uniprocessors - could disable interrupts
  • Currently running code would execute without pre-emption.
  • Generally too inefficient on multiprocessor systems
  • Delay in one processor telling others to disable their interrupts
• Modern machines provide the special atomic hardware instructions (Atomic = non-interruptible) TestAndSet or Swap which achieve the same goal:
  • TestAndSet : Test memory address (i.e. read it) and set it in one instruction
  • Swap : Swap contents of two memory addresses in one instruction
• We can use these to implement simple locks to realise mutual exclusion.
• The general pattern for locks is :

do {
	[acquire lock]
		[critical section]
	[release lock]
		[remainder section]
} while (TRUE);

TestAndSet Instruction

boolean TestAndSet (boolean *target) {
	boolean original = *target; // Store the original value
	*target = TRUE; // Set the variable to TRUE
	return original: // Return the original value
}

• In a nutshell : this single CPU instruction sets a variable to TRUE and returns the original value.
• This is useful because, if it returns FALSE, we know that only our thread has changed the value from FALSE to TRUE; if it returns TRUE, we know we haven’t changed the value.

Solution using TestAndSet

• Shared boolean variable lock, initialised to false
• Solution :

do {
	while (TestAndSet(&lock)) ; // wait until we successfully
	// change lock from false to true
		[critical section]
	lock = FALSE; // Release lock
		[remainder section]
} while (TRUE);

• Note, though, that this achieves mutual exclusion but not bounded waiting - one process could potentially wait for ever due to the unpredictability of context switching.

Bounded-waiting Mutual Exclusion with TestAndSet()

• All data structures are initialised to FALSE.
• wants_in[] is an array of waiting flags, one for each process.
• lock is a boolean variable used to lock the critical section.

boolean wants_in[], key = FALSE, lock = FALSE; //all false to begin with
do {
	wants_in[i] = TRUE; // I (process i) am waiting to get in.
	key = TRUE; // Assume another has the key.
	while (wants_in[i] && key) { // Wait until I get the lock
		// (key will become false)
		key = TestAndSet(&lock); // Try to get the lock
	}
	wants_in[i] = FALSE; // I am no longer waiting: I'm in now
	[*** critical section ***]
	// Next 2 lines: get ID of next waiting process, if any.
	j = (i + 1) % NO_PROCESSES; // Set j to my right-hand process.
	while ((j != i) && !wants_in[j]) { j = (j + 1) % NO_PROCESSES };
	if (j == i) { // If no other process is waiting...
		lock = FALSE; // Release the lock
	} else { // else ....
		wants_in[j] = FALSE; // Allow j to slip in through the 'back door'
	}
	[*** remainder section ***]
} while (TRUE);