synchronisation hardware

Question 1

describe synchronisation hardware

Answer 1

Many systems provide hardware support for critical section
Uniprocessors - could disable interrupts
Currently running code would execute without preemption
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

Question 2

modern machines provide
special atomic instructions what are they

Answer 2

Swap
TestAndSet

Question 3

what does TestAndSet do

Answer 3

Test memory address (i.e. read it) and set it in
one instruction

Question 4

what does Swap do

Answer 4

Swap contents of two memory addresses in one
instruction

Question 5

what does atomic mean

Answer 5

non - interruptable

Question 6

what are Testandset and swap used for

Answer 6

used to implement simple locks to realise mutual exclusion

Question 7

The general pattern for using locks is:

Answer 7

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

Question 8

code for TestAndSet instruction

Answer 8

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

Question 9

boolean TestAndSet (boolean *target) {
boolean original = *target;
*target = TRUE;
return original:
}
what does the code do and why is the code useful

Answer 9

• 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.

Question 10

what is the solution code using text and set

Answer 10

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

Question 11

what does this code achieve
do {
while (TestAndSet(&lock)) ;
//waits until lock changes from false to true
[critical section]
lock = FALSE; // Release lock
[remainder section]
} while (TRUE);

Answer 11

achieves mutual exclusion but not bounded waiting - one process could potentially wait for ever
due to the unpredictability of context switching

Question 12

Bounded-waiting Mutual Exclusion with TestAndSet()

Answer 12

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

Question 13

code for bounded-waiting Mutual Exclusion with TestAndSet()

Answer 13

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);