Chapter 5, Process Management, Ida A. Flynn and Ann McIver McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Company (1993)
Lesson B: Modeling Deadlocks, Strategies for Handling Deadlocks, Prevention, Avoidance, Detection, Recovery
Problem 6. Consider the following directed resource graph:
Problem 7. Consider the following directed resource graph:
d. Can the graph be reduced, partially or totally?
Apply the rules on page 115.
Rule 1: Initially, there is no process that is currently using a resource and not waiting for one. Go to Rule 2.
Rule 2: Find a process that is waiting only for resource classes that are not fully allocated. This is true of both process P1 and P2. Both are waiting for R2 which is not fully allocated. Satisfying either request will permit the associated process to run to completion. P1 and P2 are not contributing to any deadlock. The reduced system appears below.
Revisit Rule 1: There still are no processes currently using a resource and not waiting one.
Revisit Rule 2: There is no process that is waiting only for resource classes that are not fully allocated. Note that while P3 is waiting for resource class R2 that is not fully allocated, observe that P3 is also waiting for resource R3 which is fully allocated. This digraph cannot be further reduced according to the rules
This digraph is now irreducible. The original digraph was partially reduced.
b. Are there any deadlocked processes?
Yes, processes P3 and P4 are deadlocked. To confirm this, examine the four conditions for deadlock. See the listing of conditions given in class, or in the solution set for Chapter 5A.
c. (Reference the original digraph.) Three processes - P1, P2, and P3 - are requesting resources from R2.
(1) Which requests would you satisfy to minimize the number of processes involved in the deadlock?
No choices of resource allocation will change the number of processes involved in the deadlock.
Satisfying requests by processes P1 and P2 will permit those processes to run to completion faster, without affecting the processes that are involved in deadlock.
(2) Which requests would you satisfy to maximize the number of processes involved in deadlock?
Satisfying the request by process P3 for resource R2 will delay completion of one of processes P1 or P2, but will not change the number of processes involved in deadlock. Deadlock requires a circular wait condition which does not exist for P1 or P2.
a. Is this system, as a whole, deadlocked?
It is not clear what is meant by "this system, as a whole". A portion of the system is deadlocked, and a portion is not deadlocked.
e. Can the deadlock be resolved without selecting a victim?
No. By definition, a deadlock cannot be broken without changing one of the 4 conditions.
Problem 8. Consider a computing system with 13 tape drives. All jobs running on this system require a maximum of 5 tape drives to complete. They each run for long periods of time with just 4 tape drives and request the fifth one only at the very end of the run. The job stream is endless.
a. If your operating system supports a very conservative device allocation policy, no job will be started unless all tapes required have been allocated to it for the duration of its run.
(1) What is the maximum number of jobs that can be active at once?
Under the policy above, two (2) processes can be run simultaneously.
(2) What are the minimum and maximum number of tape drives that may be idle as a result of this policy?
The minimum number of tape drives that may be idle as a result of this policy is 3.
The maximum number of tape drives that may be idle as a result of this policy is 5.
(3) Explain your answer. See the diagram.
b. If your operating system supports the Banker's Algorithm:
[1] No process will be granted more resources than what the system has.
[2] Each process must be assigned a maximum limit of resources allocatable before the process is can be moved from the Hold queue to the Ready queue.
[3] No process will be allocated more resources than its maximum assigned limit. {There is not a rule that prohibits renegotiation of this assigned limit. For the dynamic state system, this might be valuable to a process doing sorts.}
[4] At any instant, the operating system cannot allocate more resources than it has.
(1) What is the maximum number of jobs that can be in progress at once?
The maximum number of jobs that can be in progress at once is 3.
(2) What are the minimum and maximum number of tape drives that may be idle as a result of this policy?
The minimum number of tape drives that may be idle as a result of this policy is zero (0).
The maximum number of tape drives that may be idle as a result of this policy is one (1).
(3) Explain your answer. See the figure above.
Remarks. The problem statement implies that the amount of time each job needs a fifth tape drive is significantly less than the total run time. If all jobs require the same total amount of run time, and the time requires for the fifth drive is less than a third of the total run time, then the allocation of 3 jobs will not result in a decrease in the rate of job completions once the initial startup transient has past. If the jobs vary in total run time, you may need to do some simulation studies to determine which approach results in overall faster average completion rate. With unequal total run times, you cannot count on synchronization to prevent delays. You could also do a statistical analysis without running a simulation if you could define the statistical distributions for job arrival time, job total run time, and fraction of total run time that a job needs the fifth tape drive. If you need to do such an analysis, you can get it done through a research university statistics department. They train graduate students to do statistical consulting by having them do real world problems. The actual analysis is a one-night homework problem. The real work is nailing down the proper assumptions in the initial problem definition.
Problems 9, 10, and 11. Safe State.
"A system is in a safe state if there exists a sequence of resource assignments and process execution that will permit all jobs to run to completion if each job requires its maximum number of resources." This definition is different than the one in the text. This definition is stated in terms of the system goal. The text's definitions are stated in terms of a condition sufficient to meet this goal.
The text's definition at the bottom of page 113: (Paraphrased) "A system is in a safe state if the number of remaining unallocated system resources can satisfy the process with the smallest remaining needs."
Discussion: I thought I could produce an example that would show the definition on page 113 was not sufficient for all cases. The example I produced was flawed because I did not consider the sequence of events that could lead to that example. Consistent application of the text's definition of safe state, beginning with the first job admitted by the operating system, will keep the system in a condition that all jobs will be able to run to completion.
Problems 9. System number 1 has 12 devices; only 1 device is available.
| Job # | # Devices Allocated |
Maximum Required |
Remaining Needs |
| 1 | 5 | 6 | 1 |
| 2 | 4 | 7 | 3 |
| 3 | 2 | 6 | 4 |
| 4 | 0 | 2 | 2 |
Using the definitions presented in the discussion of the Banker's Algorithm, answer these questions:
a. Determine the "remaining needs" for each job in each system. [See the table.]
b. Determine whether each of the systems is safe or unsafe.
This system is in a safe state.
c. If the system is in a safe state, list the sequence of requests and releases that will make it possible for all processes to run to completion.
Assign the remaining system device to job #1. After it runs to completion, and all that job's resources are returned to the available list, the system will then have at least 6 free resources.
Run job #3 and job #4 next. After job #3 completes, job #2 can be run to completion.
Run job #2 and job #4 next. After job #2 completes, job #3 can be run to completion.
d. If the system is in an unsafe state, show how it is possible for deadlock to occur.
The system is not initially in an unsafe state.
It is possible to place the system into an unsafe state by initially assigning the remaining device to job #2, #3, or #4. If all jobs then request one or more additional resources (each job within its maximum limit) without giving up any current resources, the system is deadlocked.
Problem 10. System number 2 has 14 devices; only 2 are available.
| Job # | # Devices Allocated |
Maximum Required |
Remaining Needs |
| 1 | 5 | 8 | 3 |
| 2 | 3 | 9 | 6 |
| 3 | 4 | 8 | 4 |
a. Determine the "remaining needs" for each job in each system. [See the table.]
b. Determine whether each of the systems is safe or unsafe.
This system is in an unsafe state.
c. If the system is in a safe state, list the sequence of requests and releases that will make it possible for all processes to run to completion.
d. If the system is in an unsafe state, show how it is possible for deadlock to occur.
Suppose that the remaining 2 system devices are allocated. Then if each of the three processes request one additional device, the system is deadlocked. It would be impossible for one of the jobs to run to completion and then release resources for the remaining processes to finish. If only two of the processes each request one additional device, the system is not deadlocked because it is still possible for the remaining process to complete execution, release resources, and permit the other processes to run to completion.
Problem 11. System number 3 has 12 devices; only 2 are available.
| Job # | # Devices Allocated |
Maximum Required |
Remaining Needs |
| 1 | 5 | 8 | 3 |
| 2 | 4 | 6 | 2 |
| 3 | 1 | 4 | 3 |
a. Determine the "remaining needs" for each job in each system. [See the table.]
b. Determine whether each of the systems is safe or unsafe.
This system is in a safe state.
c. If the system is in a safe state, list the sequence of requests and releases that will make it possible for all processes to run to completion.
Assign 2 devices to job #2. Job #2 runs to completion, releasing 6 resources. These 6 resources can then be allocated to jobs #1 and #3, permitting both to run to completion.
d. If the system is in an unsafe state, show how it is possible for deadlock to occur.
Problem 14. State how you would design and implement a mechanism to allow the operating system to detect which of the processes are starving.
Include a time stamp in the process control block to record when a process was placed in its current queue. Declare a process in starvation if a process is in a Wait queue longer than any other process has been in the system since first entering the Ready queue.
Problem 15. Given the four primary types of resources - CPU, memory, storage devices, and files - select for each one the most suitable technique for fighting deadlock and briefly explain why it is your choice.
To prevent a deadlock, you must eliminate one of the four necessary conditions leading to a deadlock. Note that the circular wait condition does not have to involve resources of all the same type.
a. CPU.
Permit preemption of processes by the operating system. In an interactive system, use a round-robin approach to allocating CPU time. In a batch environment, use process time limits declared when the job was submitted. When a job exceeds its limit, kill it.
In a multiple CPU system, treat the CPUs as other multiple-resource devices and impose the Banker's Algorithm. Impose time limits on each process, as done in the single CPU case.
b. Memory.
Use of virtual memory solves the mutual exclusion problem for physical memory.
Virtual memory does not eliminate completely the problem for competitive access to the same page. Consider the airline reservation system example. If a region of memory is protected by a semaphore, it could become a link in a circular wait condition. You need to break the resource holding condition. A time limit for memory resource holding may be in order, but this could be an expensive solution to a rare problem.
c. Storage Devices.
Restrict exclusive claims to a device to the smallest possible region. This can be aided by partitioning physically.
Use the Banker's Algorithm for controlling allocation of storage devices. This is really important for tape drives because of the time required to mount and dismount tapes.
Job time limits on process claims to CPU will also limit that job's claim on other resources.
d. Files.
Require preallocation for files stored on removable media, particularly tapes.
Restrict exclusive claims to a file to the smallest possible region. This can be aided by controlling exclusive access to the smallest possible logical partition.
Problem 16. State the limitations imposed on programs (and on systems) that have to follow a hierarchical ordering of resources; for example, disks, printers, terminals, and files.
Hierarchical ordering requires that the program know what resources are required. This is a problem when the resources required are determined by the data processed by the program. This approach leads to inefficient (and possibly costly) reservation of resources.
The author's answer: Hierarchical ordering of resources is used to suppress the circular wait condition. Resources are grouped into a hierarchy of levels. Once a process has been allocated resources at one level, it can request other resources but only at a higher level. It can release resources at a given level only after releasing all allocated resources at every higher level. After a process has been allocated and then has released resources at a given level then it can again request resources at that same level. Hierarchical allocation may be more costly to perform than preallocation, but it can reduce the waste associated with full preallocation. If the order in which a process needs resources is different from that in which the levels are ordered then this reduction will not develop. For example, if a printer is needed early in the execution and the disk drive is needed only at the end, but the disk drive is at a lower level than the printer, then the disk drive will have to be allocated early and remain unused until needed.