Chapter 11 Low level synchronisation: Algorithms
Exercises
11.1 - 11.6 are on the case study (from edition 1 appendix)
11-7 What are the problems of designing a system with a strict hierarchical structure? What are the advantages?
Each level in the hierarchy provides a service interface to higher levels. The model is of downward request and upward reply. It is difficult to choose a strict hierarchical ordering of functions. You may impose arbitrary restrictions by choosing some particular ordering as in THE.
"Haberman A. N. et al. "Modularisation and Hierarchy in a Family of Operating Systems" Comm. ACM 19(5) May 76 discusses the issues and suggests how the problems might be avoided.
The Venus operating system (Liskov, 1972) had the following levels (bottom up):
0: hardware,
1: instruction interpreter,
2: CPU scheduling,
3: I/O channels,
4: virtual memory,
5: device drivers and schedulers,
6: user processes.
Does this choice of layers solve the problems discussed for THE in Section 11.2? See Liskov 1972.
11-8 A buffer-object manager is to be implemented. Buffers are to be managed as a pool of fixed sized objects. A producer process first acquires an empty buffer, then performs a number of write operations into it until it is full. A consumer process first acquires a full buffer then performs a number of reads from it until it is empty.
Each object has a header part, for holding information on the use of the buffer (such as a count and a pointer), for links so that the buffers can be chained, etc. and a body part for holding data. A chain of empty buffer objects and a chain of full buffer objects are to be maintained. The object manager detects when a buffer becomes full.
Interface operations are proposed as follows:
buff-id := acquire-empty-buffer () % executed by producers
buff-id := acquire-full-buffer ( ) % executed by consumers
return-code := write-buffer (buff-id,bytes) % executed by producers
bytes := read-buffer (buff-id,byte-count) % executed by consumers
free-buffer (buff-id) % executed by consumers
Discuss the following:
use of the proposed interface operations and possible modifications,
the information that might usefully be kept in each buffer header,
how a full buffer, on writing, and an empty buffer, on reading,
should be detected and indicated to the invoker,
how exclusive access to a buffer-object might be ensured,
how the various chains might be updated correctly, secure from
concurrent access,
how the scheme compares with a cyclic buffer (see Section 11.3) for concurrent accesses by producers and consumers.
This type of arrangement can be used for terminal I/O. UNIX, for example, has c-blocks as buffers in a c-list data structure. Details can be found in Bach M. J. (1986), p331-334 and Chapter 9 of Leffler S J et al. (1989).
The appendix of this book sets up a buffer pool for disk blocks and discusses the problems of concurrent access to the shared data structures set up to manage the pool.
11-9 The classic sleeping barber problem is given as exercise 9 of Chapter 11. Solve this problem using semaphores.
waiting : integer :=0; %customers waiting to be cut
guard : semaphore :=1; % to delimit a critical region to protect waiting
customers : semaphore:= 0; %counting semaphore of customers barber : semaphore :=0; %is barber waiting for a customer (1) or not (0)
the barber executes the following program:
WAIT(customers); %sleeps if there are none WAIT (guard);
waiting := waiting - 1; %otherwise, changes waiting under exclusion
SIGNAL(barber); % and indicates his readiness to cut hair
SIGNAL (guard);
cut hair
a customer executes:
WAIT (guard); %test and set waiting under exclusion
if waiting < chairs % if there is a free chair to sit and wait
then { waiting := waiting+1;
SIGNAL(customers) %indicate one more customer
SIGNAL(guard) %release the exclusion on waiting
WAIT(barber); %use the barber resource
have haircut; }
else SIGNAL(guard); % if there are no free chairs just release
the exclusion on waiting and go away.
11-10 The classic dining philosophers problem is described in Section 17.5 and Exercise 17,5. Attempt the suggested solutions using semaphores.
A number of solutions are given with the solutions to Chapter 17’s exercises as part of a small project exploring this problem.