Chapter 12 IPC with shared memory
Exercises
12-1 How would a compiler use semaphores to implement critical regions in a concurrent programming language?
Create a semaphore for each data structure declared to be shared.
At the start of a region ( region shared-data begin )
use WAIT (semaphore-for-that-shared-data).
At the end use SIGNAL (semaphore-for-that-shared-data).
12-2 Why is it inefficient to implement condition synchronisation within a critical region using an expression involving programming language variables?
The programmer may AWAIT an arbitrary expression achieving some value. We assume that the variables involved in an AWAIT statement are those accessed under exclusion in the critical region. The programmer is not required to SIGNAL when a condition is made true, so the language implementor must arrange to test all conditions whenever a process exits from a critical region in case a condition has been made true by the exiting process.
In contrast, in monitors which use condition variables, the programmer must declare the conditions on which processes may WAIT and explicit SIGNALs are required, using WAIT(condition-variable), SIGNAL(condition-variable). Guarded commands (Dijkstra, 1975) showed the way to a higher level approach than condition variables.
12-3 In (Hoare, 1974) it was proposed that the scheduling of processes waiting on a condition variable in a monitor could be priority based rather than just first come first served - a "scheduled wait". Syntax such as WAIT(condition-name, priority) could be used to indicate the ordering of waiting processes on a condition queue. Using this construct, write an alarm clock monitor with procedures wakeme(n:integer) and tick. The tick procedure is invoked on a timer interrupt at regular intervals to maintain a value of system time. The wakeme procedure is to allow a process to request that it should be blocked for a number of units of time and then woken up again. The process "priority" is to be used to order the time at which the process is awakened.
The solution from Hoare’s paper, Comm. ACM 17(4) Oct 74 is:
alarmclock: monitor
begin now : integer :=0;
wakeup : condition;
procedure wakeme (n: integer);
begin alarmsetting: integer;
alarmsetting :=now+n;
while now<alarmsetting do WAIT (wakeup, alarmsetting);
SIGNAL (wakeup); % in case the next process is due to wake up
% at the same time end;
procedure tick;
begin now := now+1;
SIGNAL (wakeup)
end; end alarmclock:
12-4 The process priority described above for exercise 3 can also be used to wake up processes in a suitable order for writing to the cylinders of a disk. Assume that a sweep or "elevator" algorithm is to be used to control the disk heads: that is, the heads are to move across the surface to the outermost required cylinder in one direction then are to move back in the opposite direction. The heads sweep smoothly across the surfaces and back, stopping at cylinders en-route for processes to make data transfers. Write a monitor with a procedure to request that the heads be moved to a given cylinder and to block the invoking process until its required cylinder is reached, and a procedure that is called by a process after it has finished making a data transfer to a given cylinder.
The solution from Hoare’s paper, Comm. ACM 17(4) Oct 74 is given below. We have type cylinder = 0 ..cylmax;
The solution also uses QUEUE (condition-name) which yields true if any process is waiting on the queue and false otherwise. A solution may be programmed to use simple counts instead, as in Chapter 12, because managing a count and performing a SIGNAL or WAIT are atomic within a monitor procedure.
diskhead: monitor
begin headpos: cylinder := 0;
direction: (up, down) := up;
busy: boolean := false;
upsweep, downsweep : condition;
procedure request (dest : cylinder);
begin if busy then
{if headpos<dest or headpos=dest and direction = up
then WAIT (upsweep, dest) else WAIT (downsweep, cylmax-dest) };
busy := true; headpos := dest end request;
procedure release;
begin busy := false;
if direction = up then
{if QUEUE (upsweep)
then SIGNAL (upsweep)
else { direction := down; SIGNAL (downsweep) }
}
else if QUEUE (downsweep)
then SIGNAL (downsweep)
else {direction := up; SIGNAL (upsweep) }
end release; end diskhead;
12-5 Rewrite the "readers and writers" monitor operations to give priority to waiting readers over waiting writers. The application is such that it is better to read stale data quickly than to wait for up-to-date data.
read-write: monitor
entry-procedures startread, endread, startwrite, endwrite
var ar : integer % we now need to know if there are active readers
busy-writing : boolean;
free-to-read, free-to-write : condition;
% in startread a reader now waits for a writing writer tofinish
procedure startread ()
begin ar := ar +1;
if busy-writing then WAIT (free-to-read);
SIGNAL (free-to-read) % If one reader can read, all can read. Each
end startread; % reader wakes up another until none is left.
% in endread the last reader signals a writer
procedure endread ()
begin ar := ar-1;
if ar = 0 then SIGNAL(free-to-write) end endread;
% in startwrite a writer now waits for a writing writer to finish or for no waiting readers
procedure startwrite ()
begin if busy-writing or ar > 0 then WAIT (free-to-write);
busy-writing := true
end startwrite;
% in endwrite any waiting reader is now given priority over any waiting writer
procedure endwrite ()
begin busy-writing := false;
if ar>0 then SIGNAL(free-to-read)
else SIGNAL (free-to-write)
end endwrite;
end read-write;
12-6 Why is a monitor inadequate for managing many shared objects of the same type? How could mutually exclusive access by processes to the same data object be provided?
The mechanism for achieving exclusive access to shared data used in a monitor is to enforce that only one process at a time may be active within the monitor. That is, the exclusion is associated with executing the code of the operations through which the data object is accessed. We have seen a possible implementation in terms of semaphores. Each operation starts with a WAIT on the single semaphore which guards the data encapsulated by the monitor and ends with a SIGNAL on that semaphore.
A semaphore could be associated with each data object of the shared type encapsulated by the "monitor". Each operation must have an argument which specifies which object of that type is to be invoked. The operation includes a WAIT on the appropriate semaphore. Simultaneous accesses to different objects can now go ahead in parallel but each object is accessed under exclusion.
12-7 Why is "synchronisation at the level of operations" desirable?
How might this approach be supported in a concurrent programming language? Consider the cases of both passive modules (or objects) and active modules (or objects).
Condition synchronisation within the operations of a monitor is low level to code and (comparable with semaphores) is difficult to program correctly. Also, the programmer is relied on to maintain the invariants on the state of the shared data whenever a WAIT is executed. There are also problems associated with the semantics of a SIGNAL within a monitor operation - which process should run after a SIGNAL?
Synchronisation at the level of operations avoids all of these problems. Path expressions provide a syntax for declaring (statically) the order in which operations may be executed and which operations may run in parallel. Guarded commands provide an approach through which a server process may determine dynamically which of its operations it may execute on behalf of its clients. Several concurrent programming languages are based on them (Ada, DP).
12-8 Discuss how dynamic process creation can be used to avoid unnecessary delay in a monitor based system.
A process which calls a monitor procedure risks delay. If the process has work it can do in parallel with the execution of the monitor procedure it may create a child process to make the call and synchronise with it to pick up the results of the call.
12-9 The sleeping barber problem.
(We assume that the barber and his customers are male).
A barber provides a hair-cutting service. He has a shop with two doors, an entrance and an exit. He spends his time serving customers one-at-a-time. When none are in the shop, the barber sleeps in the barber’s chair.
When a customer arrives and finds the barber sleeping, the customer awakens the barber and sits in the barber’s chair to receive his haircut. After the cut is done, the barber sees the customer out through the exit door.
If the barber is busy when a customer arrives, the customer waits in one of the chairs provided for the purpose. If they are all occupied he goes away.
After serving a customer the barber looks to see if any are waiting and if so proceeds to serve one of them. Otherwise, he sleeps again in his chair.
Write a solution to the problem for the barber process and the customer processes.
A solution along the lines of the semaphore solution given for exercise 9-6 is as follows (note the translation from semaphore program to monitor program):
barbershop: monitor
waiting : integer := 0; % customers waiting to be cut
customers : condition :=0; % for the barber to wait for a customer
barber : condition := 0; % for a customer to wait for the barber
procedure seek-customer( ) % called by the barber
begin if waiting=0 then WAIT (customers); % sleeps if there are none
waiting := waiting-1; % one less customer waiting
SIGNAL (barber); % frees a waiting customer
end seek-customer ;
procedure get-haircut( ) % called by a customer
begin if waiting < chairs % is there a free chair to sit and wait?
% if there are no free chairs just go away
then { waiting := waiting+1; % one more customer waiting
SIGNAL (customers) % in case the barber is asleep
WAIT (barber); % wait for your turn with the barber
}
end get-haircut;
end barbershop;
Additional exercises
12-10 Solve the dining philosophers problem using a monitor, see Section 17.4.2 and exercise 17-5.
A number of solutions are given with the solutions to Chapter 17’s exercises as part of a small project exploring this problem.
12-11 Rewrite the solution to the readers and writers problem given in Figure 12.1, using conditional critical regions, to avoid a separate region in which writers write. Hint: the Boolean writelock may be managed within the four critical regions and incorporated into AWAIT statements. Compare your solution with the monitor solution given in Section 12.2.3.