Answer the following questions from the Chapter 6 reading in your textbook. Be through and complete with your answers. You may work on these questions with a partner (no more than two working together), but both students must submit the document individually on Beachboard Dropbox along with both students names on each submission.

1. Students working at individual PCs in a computer laboratory send their files to be printed by a server that spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?

2. In the preceding question, which resources are preemptable and which are nonpreemptable?

3. The four conditions (mutual exclusion, hold and wait, no preemption and circular wait) are necessary for a resource deadlock to occur. Give an example to show that these conditions are not sufficient for a resource deadlock to occur. When are these conditions sufficient for a resource deadlock to occur?

4. Suppose four cars each approach an intersection from four different directions simultaneously. Each corner of the intersection has a stop sign. Assume that traffic regulations require that when two cars approach adjacent stop signs at the same time, the car on the left must yield to the car on the right. Thus, as four cars each drive up to their individual stop signs, each waits (indefinitely) for the car on the left to proceed. Is this anomaly a communication deadlock? Is it a resource deadlock?

5. Consider the following state of a system with four processes, P1, P2, P3, and P4, and five types of resources, RS1, RS2, RS3, RS4, and RS5: 0 1 1 1 2 1 1 0 2 1 C= 0 1 0 1 0 R= 0 1 0 2 1 E = (24144) 0 0 0 0 1 0 2 0 3 1 A = (01021) 2 1 0 0 0 0 2 1 1 0

Using the deadlock detection algorithm described in Section 6.4.2 of your textbook, show that there is a deadlock in the system. Identify the processes that are deadlocked.

6. Explain how the system can recover from the deadlock in previous problem using

(a) recovery through preemption.

(b) recovery through rollback.

(c) recovery through killing processes.

7. A system has two processes and three identical resources. Each process needs a maximum of two resources. Is deadlock possible? Explain your answer.

8. The bankers algorithm is being run in a system with m resource classes and n processes. In the limit of large m and n, the number of operations that must be performed to check a state for safety is proportional to m^a n^b. What are the values of a and b?

9 A distributed system using mailboxes has two IPC primitives, send and receive. The latter primitive specifies a process to receive from and blocks if no message from that process is available, even though messages may be waiting from other processes. There are no shared resources, but processes need to communicate frequently about other matters. Is deadlock possible? Discuss.

10. One way to prevent deadlocks is to eliminate the hold-and-wait condition. In the textbook it was proposed that before asking for a new resource, a process must first release whatever resources it already holds (assuming that is possible). However, doing so introduces the danger that it may get the new resource but lose some of the existing ones to competing processes. Propose an improvement to this scheme.