Chapter 10 Low level synchronisation: Implementation

Chapter 10 Low Level Synchronisation Primitives: Implementation

Exercises

10-1 Support for synchronisation between processes and the hardware was described in Section 4.4. Concurrent processes also need to synchronise with each other. Discuss the approach of extending the methods described for process-hardware synchronisation to encompass process-process synchronisation. What kind of interactions could, and could not, be supported by the designs you devise?

Section 10.1 proceeds along these lines. This question asks the students to take the same starting point. Other designs than the one presented may be suggested.

10-2 Examine the processor handbooks of your local machines. Explore any composite instruction definitions with a view to using them to implement semaphore operations, in particular, WAIT(semaphore).

You may find composite instructions in the instruction sets, such as:

TAS (test and set a variable)

INC ( increment a value and set a condition code register)

CAS Register1, Register2, Memory

a) Write the entry and exit protocols for a critical region using each of the above instructions.

b) Show how the instructions may be used to achieve condition synchronisation so that a process may delay until a condition becomes true.

You may assume that processes co-operate; that some other process which exits the critical region or makes the desired condition true will take action to inform the delayed process.

The protocols should be presented at the machine instruction level so that the instructions involved and possible interleaving can be seen clearly.

TAS is discussed in the main text.

The VAX processor handbook gives seven instructions which may be used for this purpose: BBSSI, BBCCI, ADAWI, INSQHI, INSQTI, REMQHI, REMQTI.

Hewlett Packard’s PA-RISC provides a "load and clear" instruction. You can load a value into a register then test it there. If you find the value is already zero, someone else has the lock; if non-zero you acquired the lock by setting it to zero. The exit protocol is simply to make the value non-zero again.

Consider the use of a simple compare and swap instruction. The instructions of the specific machine should be substituted in the following. my-value and shared-lock may take the values locked or free.

entry: my-value := locked;

CAS (shared-lock, my-value);

branch on equal to entry;

in-CR: [critical region]

exit: shared-lock := free;

10-3 The SIGNAL and WAIT operations, provided as primitives by a kernel, are defined to be atomic. Discuss how this atomicity can be implemented. Consider the following cases:

hardware which provides a test and set or other composite instruction,

a uniprocessor, both when a composite instruction is available and when none is available

a multiprocessor with no composite instruction.

This is a review question to reinforce this important topic. A discussion of the first two points is given in Chapter 10. Two mutual exclusion protocols are given in the appendix. The DEC Alpha architecture provides hardware support for the atomic setting of a control variable which is not via a composite instruction but through special read (with "lock") and (conditional) write instructions, see Section 10.2.2.