Chapter 7.1: DeadlocksChapter 7: DeadlocksChapter ObjectivesThe Deadlock ProblemThe Notion of DeadlockThe Notion of Deadlock - moreBridge Crossing ExampleSystem ModelDeadlock CharacterizationResource-Allocation GraphResource-Allocation Graph (Cont.)Example of a Resource Allocation GraphResource Allocation Graph With A DeadlockSlide 14Resource Allocation Graph With A Cycle But No DeadlockBasic FactsDeadlock – many facesMethods for Handling DeadlocksDeadlock PreventionDeadlock Prevention (Cont.)Slide 21End of Chapter 7.1Chapter 7.1: DeadlocksChapter 7.1: Deadlocks7.2Silberschatz, Galvin and Gagne ©2005Operating System ConceptsChapter 7: DeadlocksChapter 7: DeadlocksChapter 7.1The Deadlock ProblemSystem ModelDeadlock CharacterizationMethods for Handling DeadlocksDeadlock PreventionChapter 7.2Deadlock AvoidanceDeadlock Detection Recovery from Deadlock7.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsChapter ObjectivesChapter 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.7.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsThe Deadlock ProblemThe Deadlock ProblemThe difficulty in a multiprogramming environment is simply that we have many processes in concurrent and sometime simultaneous execution.Oftentimes these tasks need to access resources which, by their very nature are shared.Essentially, when one process holds some resources and is awaiting other resources, which are held by another process perhaps awaiting the same resources currently held by the initial process, we have deadlock.A little more formally, deadlock may be described as a set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.Example System has two tape drives.P1 and P2 each hold one tape drive and each needs another one.7.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsThe Notion of DeadlockThe Notion of DeadlockThe requesting and releasing of resources are system calls – not interrupts.Requesting and releasing of resources not managed by the operating system can be handled by wait() and signal() on semaphores or through the acquiring and releasing of a mutual exclusion locks, often called mutex locks.For shared resources that are managed by the kernel, the kernel checks to make sure that the process or thread has requested and has been allocated the resource.Often system tables are employed to keep track of each resource in the system. Many examples of using these tables later in this chapter.Resource allocation tables (graphs) indicate numbers and classes of resources, whether they are allocated or free, and if allocated, to which process allocated; if a process / thread is awaiting for a resource, a process is generally queued up awaiting the resource to be freed up.7.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsThe Notion of Deadlock - moreThe Notion of Deadlock - moreIt is easy to understand how deadlock can occur.But for an efficiently running computing system, we must be concerned over resource allocation and resource release.Important to note that resources may / often are physical devices such as disk drives, printers, tape drives, etc.In many cases, we have identical devices put into ‘categories.’In other cases, shared resources may be considered ‘logical;’ that is, files, semaphores, and even inter-process communication facilities (mailboxes, sockets, ...)7.7Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBridge Crossing ExampleBridge Crossing ExampleTraffic only in one direction.Each section of a bridge can be viewed as a resource.If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).Several cars may have to be backed up if a deadlock occurs.Starvation is possible.7.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSystem ModelSystem ModelYou will see a lot of the following notation within this chapter:Ri for some resource, Pi for some process, Available resources (a vector), Max, a matrix capturing processes and resources allocated to each process, Allocated (matrix – resources allocated to each process), Need (another similar matrix) and more.Resource types R1, R2, . . ., Rm May refer to: CPU cycles, memory space, I/O devicesEach resource type Ri has Wi instances.Each process utilizes a resource as follows:request use ReleaseBut there’s also ‘resource needs’ ‘resources allocated’ ‘available resources for a given class of resources’ etc.So the controlling of deadlock is often complex.7.9Silberschatz, Galvin and Gagne ©2005Operating System ConceptsDeadlock CharacterizationDeadlock CharacterizationMutual exclusion: only one process at a time can use a resource.that is, the resource is not sharable. Enough said.Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.This, of course, is a bigee, since the process holding the resource will not release the resource until it acquires additional resources so it can finish its execution. So, ….Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.While all four of these are not mutually exclusive, they must all hold!!Let’s get to the fun stuff… Deadlock is a serious condition where processes never complete their execution and where system resources are tied up preventing jobs from finishing and other jobs from even starting.Deadlock can arise if four conditions hold simultaneously.7.10Silberschatz, Galvin and Gagne ©2005Operating System ConceptsResource-Allocation GraphResource-Allocation GraphV is partitioned into two types:P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.R = {R1, R2, …, Rm}, the set