operating system feb 28

332 Chapter 6 / ConCurrenCy: DeaDloCk anD Starvation

6.13 KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS

Key Terms

banker’s algorithm circular wait consumable resource deadlock deadlock avoidance deadlock detection deadlock prevention

fatal region hold and wait joint progress diagram memory barrier message mutual exclusion pipe

preemption resource allocation graph reusable resource safe state spinlock starvation unsafe state

Review Questions

6.1. Give examples of reusable and consumable resources. 6.2. What are the three conditions that must be present for deadlock to be possible? 6.3. What are the four conditions that create deadlock? 6.4. How can the hold-and-wait condition be prevented? 6.5. Why can’t you disallow mutual exclusion in order to prevent deadlocks? 6.6. How can the circular wait condition be prevented? 6.7. List some of the methods that may be adopted to recover from deadlocks.

Problems

6.1. Show that the four conditions of deadlock apply to Figure 6.1a. 6.2. Show how each of the techniques of prevention, avoidance, and detection can be applied

to Figure 6.1. 6.3. For Figure 6.3, provide a narrative description of each of the six depicted paths, similar

to the description of the paths of Figure 6.2 provided in Section 6.1. 6.4. Give two alternative execution sequences for the situation depicted in Figure 6.3, show-

ing that deadlock does not occur. 6.5. Given the following state of a system: The system comprises of five processes and four resources. P1–P5 denotes the set of processes. R1–R4 denotes the set of resources. Total Existing Resources:

R1 R2 R3 R4 6 3 4 3

M06_STAL4290_09_GE_C06.indd 332 5/9/17 4:39 PM

6.13 / key terMS, revieW QueStionS, anD proBleMS 333

Snapshot at the initial time stage:

Allocation Claim R1 R2 R3 R4 R1 R2 R3 R4

P1 3 0 1 1 6 2 1 1

P2 0 1 0 0 0 2 1 2

P3 1 1 1 0 3 2 1 0

P4 1 1 0 1 1 1 1 1

P5 0 0 0 0 2 1 1 1

a. Compute the Available vector. b. Compute the Need Matrix. c. Is the current allocation state safe? If so, give a safe sequence of the process.

In addition, show how the Available (working array) changes as each process terminates.

d. If the request (1, 1, 0, 0) from P1 arrives, will it be correct to grant the request? Justify your decision.

6.6. In the code below, three processes are competing for six resources labeled A to F. a. Using a resource allocation graph (see Figures 6.5 and 6.6), show the possibility of

a deadlock in this implementation. b. Modify the order of some of the get requests to prevent the possibility of any dead-

lock. You cannot move requests across procedures, only change the order inside each procedure. Use a resource allocation graph to justify your answer.

void P0()

{

while (true) {

get(A);

get(B);

get(C);

// critical region:

// use A, B, C

release(A);

release(B);

release(C);

}

}

void P1()

{

while (true) {

get(D);

get(E);

get(B);

// critical region:

// use D, E, B

release(D);

release(E);

release(B);

}

}

void P2()

{

while (true) {

get(C);

get(F);

get(D);

// critical region:

// use C, F, D

release(C);

release(F);

release(D);

}

}

6.7. A spooling system (see Figure 6.17) consists of an input process I, a user process P, and an output process O connected by two buffers. The processes exchange data in blocks of equal size. These blocks are buffered on a disk using a floating boundary between the input and the output buffers, depending on the speed of the processes.

M06_STAL4290_09_GE_C06.indd 333 5/9/17 4:39 PM

334 Chapter 6 / ConCurrenCy: DeaDloCk anD Starvation

The communication primitives used ensure that the following resource constraint is satisfied:

i + o … max

where max = maximum number of blocks on disk i = number of input blocks on disk o = number of output blocks on disk

The following is known about the processes: 1. As long as the environment supplies data, process I will eventually input it to the

disk (provided disk space becomes available). 2. As long as input is available on the disk, process P will eventually consume it and

output a finite amount of data on the disk for each block input (provided disk space becomes available).

3. As long as output is available on the disk, process O will eventually consume it. Show that this system can become deadlocked. 6.8. Suggest an additional resource constraint that will prevent the deadlock in Problem 6.7,

but still permit the boundary between input and output buffers to vary in accordance with the present needs of the processes.

6.9. In the THE multiprogramming system [DIJK68], a drum (precursor to the disk for secondary storage) is divided into input buffers, processing areas, and output buffers, with floating boundaries, depending on the speed of the processes involved. The cur- rent state of the drum can be characterized by the following parameters:

max = maximum number of pages on drum i = number of input pages on drum

p = number of processing pages on drum o = number of output pages on drum

reso = minimum number of pages reserved for output resp = minimum number of pages reserved for processing

Formulate the necessary resource constraints that guarantee that the drum capacity is not exceeded, and that a minimum number of pages is reserved permanently for output and processing.

6.10. In the THE multiprogramming system, a page can make the following state transitions:

1. empty S input buffer (input production) 2. input buffer S processing area (input consumption) 3. processing area S output buffer (output production) 4. output buffer S empty (output consumption) 5. empty S processing area (procedure call) 6. processing area S empty (procedure return)

a. Define the effect of these transitions in terms of the quantities i, o, and p. b. Can any of them lead to a deadlock if the assumptions made in Problem 6.6 about

input processes, user processes, and output processes hold?

Figure 6.17 A Spooling System

I PInput bu�er OOutput

bu�er

M06_STAL4290_09_GE_C06.indd 334 5/9/17 4:39 PM

6.13 / key terMS, revieW QueStionS, anD proBleMS 335

6.11. At an instant, the resource allocation state in a system is as follows: 4 processes P1–P4 4 resource types: R1–R4 R1 (5 instances), R2 (3 instances), R3 (3 instances), R4 (3 instance) Snapshot at time T0:

Allocation Request Available R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4

P1 0 0 1 0 2 0 0 2 2 1 1 2

P2 2 0 0 1 1 3 0 1

P3 0 1 1 0 2 1 1 0

P4 1 1 0 0 4 0 3 1

Run the deadlock detection algorithm and test whether the system is deadlocked or not. If it is, identify the processes that are deadlocked.

6.12. Suggest a deadlock recovery strategy for the situation depicted in Figure 6.10. 6.13. A pipeline algorithm is implemented so a stream of data elements of type T produced

by a process P0 passes through a sequence of processes P1, P2, c, Pn - 1, which operates on the elements in that order. a. Define a generalized message buffer that contains all the partially consumed data

elements, and write an algorithm for process Pi (0 … i … n - 1), of the form repeat receive from predecessor; consume element; send to successor: forever

Assume P0 receives input elements sent by Pn - 1. The algorithm should enable the processes to operate directly on messages stored in the buffer so copying is unnecessary.

b. Show that the processes cannot be deadlocked with respect to the common buffer. 6.14. Suppose the following two processes, foo and bar, are executed concurrently and

share the semaphore variables S and R (each initialized to 1) and the integer variable x ( initialized to 0).

void foo( ) {

do {

semWait(S);

semWait(R);

x++;

semSignal(S);

SemSignal(R);

} while (1);

}

void bar( ) {

do {

semWait(R);

semWait(S);

x--;

semSignal(S;

SemSignal(R);

} while (1);

}

a. Can the concurrent execution of these two processes result in one or both being blocked forever? If yes, give an execution sequence in which one or both are blocked forever.

b. Can the concurrent execution of these two processes result in the indefinite post- ponement of one of them? If yes, give an execution sequence in which one is indefi- nitely postponed.

M06_STAL4290_09_GE_C06.indd 335 5/9/17 4:39 PM

336 Chapter 6 / ConCurrenCy: DeaDloCk anD Starvation

6.15. Consider a system consisting of four processes and 9 instances of a single resource. The current state of the claim (C) and allocation (A) matrices is:

C = §2 6 9 5

¥ a = §1 2 2 3

¥ Is the system in a safe state? If so, will it remain in a safe state if the available resources

are allocated to the last process in sequence? 6.16. Consider the following ways of handling deadlock: (1) banker’s algorithm, (2) detect

deadlock and kill thread, releasing all resources, (3) reserve all resources in advance, (4) restart thread and release all resources if thread needs to wait, (5) resource order- ing, and (6) detect deadlock and roll back thread’s actions. a. One criterion to use in evaluating different approaches to deadlock is which

approach permits the greatest concurrency. In other words, which approach allows the most threads to make progress without waiting when there is no dead- lock? Give a rank order from 1 to 6 for each of the ways of handling deadlock just listed, where 1 allows the greatest degree of concurrency. Comment on your ordering.

b. Another criterion is efficiency; in other words, which requires the least processor overhead. Rank order the approaches from 1 to 6, with 1 being the most efficient, assuming deadlock is a very rare event. Comment on your ordering. Does your ordering change if deadlocks occur frequently?

6.17. Consider a variation of the dining philosophers problem where the number of philoso- phers is even. Can you devise a deadlock-free solution to the problem? Assume that all other requirements are like those in the original problem.

6.18. Suppose there are two types of philosophers. One type always picks up his left fork first (a “lefty”), and the other type always picks up his right fork first (a “righty”). The behavior of a lefty is defined in Figure 6.12. The behavior of a righty is as follows:

begin

repeat

think;

wait ( fork[ (i+1) mod 5] ); wait ( fork[i] );

eat;

signal ( fork[i] );

signal ( fork[ (i+1) mod 5] ); forever end;

Prove the following: a. Any seating arrangement of lefties and righties with at least one of each avoids

deadlock. b. Any seating arrangement of lefties and righties with at least one of each prevents

starvation. 6.19. Figure 6.18 shows another solution to the dining philosophers problem using monitors.

Compare to Figure 6.14 and report your conclusions.

M06_STAL4290_09_GE_C06.indd 336 5/9/17 4:39 PM

6.13 / key terMS, revieW QueStionS, anD proBleMS 337

6.20. Some of the Linux atomic operations are listed in Table 6.2. Can you identify some ben- efits of implementing these operations in uniprocessor and multiprocessor systems? Write a simple program depicting the use of an atomic integer data type in implement- ing counters.

6.21. Consider the following fragment of code on a Linux system. read_lock(&mr_rwlock);

write_lock(&mr_rwlock);

Where mr_rwlock is a reader–writer lock. What is the effect of this code?

Figure 6.18 Another Solution to the Dining Philosophers Problem Using a MonitorVideoNote

monitor dining_controller; enum states {thinking, hungry, eating} state[5]; cond needFork[5] /* condition variable */

void get_forks(int pid) /* pid is the philosopher id number */

{

state[pid] = hungry; /* announce that I’m hungry */

if (state[(pid+1) % 5] == eating || (state[(pid-1) % 5] == eating) cwait(needFork[pid]); /* wait if either neighbor is eating */

state[pid] = eating; /* proceed if neither neighbor is eating */

}

void release_forks(int pid) {

state[pid] = thinking;

/* give right (higher) neighbor a chance to eat */

if (state[(pid+1) % 5] == hungry) && (state[(pid+2) % 5]) != eating)

csignal(needFork[pid+1]);

/* give left (lower) neighbor a chance to eat */

else if (state[(pid–1) % 5] == hungry) && (state[(pid–2) % 5]) != eating)

csignal(needFork[pid–1]);

}

void philosopher[k=0 to 4] /* the five philosopher clients */

{

while (true) { <think>;

get_forks(k); /* client requests two forks via monitor */

<eat spaghetti>;

release_forks(k); /* client releases forks via the monitor */

}

}

M06_STAL4290_09_GE_C06.indd 337 5/9/17 4:39 PM

338 Chapter 6 / ConCurrenCy: DeaDloCk anD Starvation

6.22. The two variables a and b have initial values of 1 and 2, respectively. The following code is for a Linux system:

Thread 1 Thread 2

a = 3; — mb(); — b = 4; c = b; — rmb(); — d = a;

What possible errors are avoided by the use of the memory barriers?

M06_STAL4290_09_GE_C06.indd 338 5/9/17 4:39 PM