Chapter 10 Low level synchronisation: Implementation
Objectives
To show how an operation on a data object shared by concurrent processes can be made atomic.
Points to emphasise
- We have seen many examples of shared data objects in systems implementation, such as I/O and communications buffers, memory management tables and file system tables. These are accessed by concurrent processes.
- A system must be able to enforce mutually exclusive access to shared, writeable data objects. The hardware may provide support and this approach is the first to consider for efficiency and simplicity.
- Forbidding interrupts to achieve mutual exclusion is a possible option for a single-CPU system only. This approach is simple and easy and should not be scorned if the timing requirements on the system allow it to be used and a multiprocessor implementation is not required.
- A composite read-modify-write instruction can be used to achieve mutual exclusion on a multiprocessor (Figure 9.10). These are often available, both in CISC and RISC architectures.
- The semaphore data type is a formalisation of the flag or Boolean we have been attempting to use to solve our concurrency problems.
Possible difficulties
The material is substantial and difficult. In my experience it can’t be understood unless an individual spends a lot of time in personal study working through the algorithms. The distinction between kernel level and language level implementation of semaphores may present difficulties.
Teaching hints
- I have now covered the algorithms for achieving n-process mutual exclusion without hardware support within the chapter. Section 9.3 attempts to guide the reader slowly and carefully through two of these algorithms and makes them consider parallel execution (on a multiprocessor or uniprocessor with pre-emptive scheduling) by means of exercises. The original CACM papers are short, often only one page, and students might be interested to see the liberal use of goto’s in the 60’s and early 70’s.
- Look at the instruction sets of local machines for composite instructions or other support for concurrency such as locking the memory bus for a composite read-modify-write. A posting to the newsgroup comp.arch showed ho* the branch delay slot of the MIPS R2/3000 can be used to create a composite instruction, in the absence of any other support for concurrency control on that machine.