Extended Lectures for DeadLock Lec5

DEADLOCK
_______________________________________________________
This Lecture continues our survey of concurrency by looking at two problems that plague all efforts to support concurrent processing:deadlock and starvation.We begin with a discussion of the underlying principles of deadlock and the related problem of starvation.Then we examine the three common approaches to dealing with deadlock: prevention,detection,and avoidance.We then look at one of the classic problems used to illustrate both synchronization and deadlock issues:the dining philosophers problem. As with Chapter 5,the discussion in this chapter is limited to a consideration of concurrency and deadlock on a single system.Measures to deal with distributed deadlock problems are assessed in Chapter 18.
6.1 PRINCIPLES OF DEADLOCK
Deadlock can be defined as the permanent blocking of a set of processes that either compete for system resources or communicate with each other.A set of processes is deadlocked when each process in the set is blocked awaiting an event (typically the freeing up of some requested resource) that can only be triggered by another blocked process in the set. Deadlock is permanent because none of the events is ever triggered. Unlike other problems in concurrent process management, there is no efficient solution in the general case. All deadlocks involve conflicting needs for resources by two or more processes. A common example is the traffic deadlock. Figure 6.1a shows a situation in which four cars have arrived at a four-way stop intersection at approximately the same time.The four quadrants of the intersection are the resources over which control is needed.