OS II- Lec 1/Deadlocks

Deadlocks
In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock. It said, in part: “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.”
In this chapter, we describe methods that an operating system can use to prevent or deal with deadlocks. Although some applications can identify programs that may deadlock, operating systems typically do not provide deadlock-prevention facilities, and it remains the responsibility of programmers to ensure that they design deadlock-free programs. Deadlock problems can only become more common, given current trends, including larger numbers of processes, multithreaded programs, many more resources within a system, and an emphasis on long-lived file and database servers rather than batch systems.
CHAPTER OBJECTIVES
• To develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasks. ?
• To present a number of different methods for preventing or avoiding deadlocks in a computer system. ?
Table of Contents
1.1 System Model 2
1.2 Deadlock Characterization 3
1.2.1 Necessary Conditions 4
1.2.2 Resource-Allocation Graph 4
1.3 Methods for Handling Deadlocks 7
1.4 Deadlock Prevention 8
1.4.1 Mutual Exclusion 8
1.4.2 Hold and Wait 9
1.4.3 No Preemption 9
1.4.4 Circular Wait 10
1.5 Deadlock Avoidance Error! Bookmark not defined.
1.5.1 Safe State Error! Bookmark not defined.
1.5.2 Resource-Allocation-Graph Algorithm Error! Bookmark not defined.
1.5.3 Banker’s Algorithm Error! Bookmark not defined.
1.6 Deadlock Detection Error! Bookmark not defined.
1.6.1 Single Instance of Each Resource Type Error! Bookmark not defined.
1.6.2 Several Instances of a Resource Type Error! Bookmark not defined.
1.6.3 Detection-Algorithm Usage Error! Bookmark not defined.