17-1 Consider a wide range of examples of objects or resources that are allocated by a system to meet the demands of the application or applications that it runs. Consider the extent to which these demands are predictable in advance. Consider real-time systems, multi-user (distributed) operating systems, database management systems etc.

This chapter focuses on algorithms that can be used to solve general resource allocation problems. There are often simpler solutions to specific concurrent programming problems, such as the dining philosophers problem. Other large concurrent programs, with many locks, semaphores or monitors, for example, will require a more general approach.

The subject is often discussed for the resources allocated dynamically by operating systems such as certain devices, disk space, memory and so on. In batch systems a "job" had to specify its resource requirements as part of the job control information. In interactive systems information is passed from compiler to linking loader to OS to indicate some of the resource requirements of a program that is to run, for example the amount of memory it will need.

In database systems the resources that are allocated dynamically are the data objects stored by the system.

17-2 What are deadlock, livelock and starvation? Give examples.

Deadlock implies that a blocked cycle of processes exists. Each holds at least one resource and is requesting another resource which is held by another process belonging to the cycle. Chapter 17 gives some examples.

Livelock implies that a process is not blocked but that it will never progress to its next stage. An example is busy waiting on a flag that no other process will ever change. Another is an incorrect entry protocol for a critical region where the processes execute the protocol indefinitely but none enters the region.

Starvation implies that a process is being unfairly treated with respect to other processes. A process may be blocked waiting for a resource that, for some reason, is always given to some other process.

17-3 What are the four conditions that must hold for deadlock to exist in an object allocation system? Which of these are system policies? Which is concerned with a specific sequence of events that happens to have occurred?

This is reinforcing the material presented in 17.4. It is not always possible, depending on the application. For some applications one can ensure that one of the conditions does not hold.

17-4 Consider the following alternative specifications of the resource requirements of a process. In each case the process makes requests dynamically for the objects it needs.

a) We can only detect deadlock.

b) We can avoid deadlock.

c) If this is a system-defined order so that all processes acquire their resources in the same order we have prevented deadlock by making a cycle impossible.

d) First assume a static number of processes such as in a process control system. It is possible to define a total schedule for the processes comprising steps or phases such that a process moves to a new phase when it releases a resource or requires a resource. A system state comprises a phase of each process. An algorithm is desired to take the system from its starting state to its finishing state (or the end of a period after which it restarts) without entering an unsafe state.

17-5 Devise the following solutions to the dining philosophers problem of Section 17.4:

The problem is a classic in the literature on concurrent programming. Although it is intended primarily to point out the dangers of writing symmetric solutions for concurrent processes (problems may arise if each process i executes the same program) we shall also use it to illustrate the general approach to deadlock detection and avoidance given in Chapter 17. We first give some solutions to the specific problem using semaphores and monitors.

The following variables are shared by all processes:

varfork: array (0..4) of semaphore % initialised to (1, 1, 1, 1, 1)

We use @+ to indicate addition modulo 5, where the processes have id’s 0..4.

A first attempt at a solution is for each process (identifier i) to execute the following program:

The problem is that the processes might run concurrently in strict synchronisation so that each succeeds in picking up its left fork then requests its right fork. We then have deadlock.

A solution is to use an additional semaphore to achieve exclusive execution of the two WAIT operations:

We can invent stories about the philosophers entering the room with the table one at a time in order to eat, in which case we would put SIGNAL (guard) after the two SIGNAL(fork) operations in the above solution instead of before eat, so that the philosophers eat in the room, put down their forks and leave it. Carriero and Gelernter (1989) give this solution in terms of the Linda primitives (Section 12.9.2).

Although this solution avoids the problem of deadlock it is unnecessarily conservative in restricting concurrency. We could allow some combinations of philosophers to eat together, for example, 0 can eat with 2 or 3 but not with 1 or 4. If we allow four processes to enter the room at once, any one might be delayed, waiting for a fork, but would eventually be able to eat:

If we break the symmetry of the processes’ programs we can avoid the possibility of a cycle of deadlocked processes. We can do this by making one process acquire its forks in the opposite order to the others, or we can make processes with odd identifiers pick up the forks in one order and even ones in the other order:

The semaphore WAIT operation does not allow us to explore solutions where we release the first fork if the second is already in use.

Let us now move on to monitor solutions to the problem. Going back to our first attempt, a similar monitor "solution" is:

Our solution which allows only one process at once into the room can be rewritten with a monitor representing the room:

And a philosopher executes:

The monitor shows the degree to which concurrency is restricted more clearly than the semaphore solution. The possibility of contention for resources is removed.

If we allow four at a time to eat we cannot put eat inside a monitor. We have to make our story include a means for philosophers to acquire permission to start eating.

And each process (i) executes:

Other monitor solutions are possible. Students may be asked to devise a monitor solution which causes a process to free its left fork if its right fork is busy and one which allows a process to acquire both forks in one call to a monitor procedure acquire-forks (i).

Notice that the monitors which avoid the possibility of deadlock are written to solve this specific problem. In the monitor fork-allocation, where deadlock is possible, there is no knowledge of the resource requirements of the processes in the monitor. It attempts to satisfy each request that arrives and blocks a process if its resource request cannot be satisfied.

fork-allocation could be extended to run a deadlock detection algorithm when it cannot satisfy a resource request. The array fork can be expanded into an allocation matrix and a request matrix request (0..4,0..4) must also be maintained. It is therefore necessary for the process id as well as the required fork id to be passed as an argument to the procedure acquire-fork. The pseudo-code below gives the general idea. The code is becoming long because we are taking the general approach of Section 17.6 to solving the problem.

We can extend this general approach by making information available within the monitor on the total resource requirements of each process. This might be done statically or, more generally, to require a process to register its total requirements at the monitor before claiming any resource. The general deadlock prevention algorithm could then be run before any request was granted. Again, the program is becoming very long. For example, when processes 0,1,2 and 3 have each acquired one fork and process 4 requests a fork we have:

The deadlock avoidance algorithm of Section 17.7 could be run on this data and would show that it is not safe to grant this request.

This example shows the students the general algorithms discussed in Chapter 17 in the context of a simple, specific example.