Deadlocks: Part I Prevention and AvoidanceReview: Dining Philosopher’sReview: Rules of the GameWhat can go wrong?Starvation vs DeadlockGoals for TodaySystem ModelFor example: SemaphoresDeadlocksFour Conditions for DeadlockReminder: Resource Allocation Graph (from Monday)Res. Alloc. Graph ExampleDealing with DeadlocksSlide 14Deadlock PreventionSlide 16Breaking Circular WaitTwo phase lockingDeadlock AvoidanceSafe StateSafe State ExampleSlide 22Slide 23Res. Alloc. Graph AlgorithmRes. Alloc. Graph issues:Banker’s AlgorithmSlide 27Slide 28Slide 29Basic AlgorithmSafety CheckBanker’s Algorithm: ExampleSlide 33Slide 34SummarySummary (2)Deadlocks: Part IPrevention and Avoidance2Review: Dining Philosopher’s•Dijkstra–A problem that was invented to illustrate a different aspect of communication–Our focus here is on the notion of sharing resources that only one user at a time can own•Philosophers eat/think•Eating needs two forks•Pick one fork at a timeIdea is to capture the concept of multiple processescompeting for limited resources3Review: Rules of the Game•The philosophers are very logical–They want to settle on a shared policy that all can apply concurrently–They are hungry: the policy should let everyone eat (eventually)–They are utterly dedicated to the proposition of equality: the policy should be totally fair4What can go wrong?•Starvation–A policy that can leave some philosopher hungry in some situation (even one where the others collaborate)•Deadlock–A policy that leaves all the philosophers “stuck”, so that nobody can do anything at all•Livelock–A policy that makes them all do something endlessly without ever eating!5Starvation vs Deadlock•Starvation vs. Deadlock–Starvation: thread waits indefinitely•Example, low-priority thread waiting for resources constantly in use by high-priority threads–Deadlock: circular waiting for resources•Thread A owns Res 1 and is waiting for Res 2Thread B owns Res 2 and is waiting for Res 1–Deadlock Starvation but not vice versa•Starvation can end (but doesn’t have to)•Deadlock can’t end without external interventionRes 2Res 1ThreadBThreadAWaitForWaitForOwnedByOwnedBy6Goals for Today•Discussion of Deadlocks•Conditions for its occurrence•Solutions for preventing and avoiding deadlock7System Model•There are non-shared computer resources–Maybe more than one instance–Printers, Semaphores, Tape drives, CPU•Processes need access to these resources–Acquire resource•If resource is available, access is granted•If not available, the process is blocked–Use resource–Release resource•Undesirable scenario:–Process A acquires resource 1, and is waiting for resource 2–Process B acquires resource 2, and is waiting for resource 1 Deadlock!8For example: Semaphoressemaphore: mutex1 = 1 /* protects resource 1 */ mutex2 = 1 /* protects resource 2 */Process A code: { /* initial compute */ P(mutex1) P(mutex2) /* use both resources */ V(mutex2) V(mutex1)} Process B code: { /* initial compute */ P(mutex2) P(mutex1) /* use both resources */ V(mutex2) V(mutex1)}9Deadlocks•Definition: Deadlock exists among a set of processes if –Every process is waiting for an event –This event can be caused only by another process in the set•Event is the acquire of release of another resourceOne-lane bridge10Four Conditions for Deadlock•Coffman et. al. 1971•Necessary conditions for deadlock to exist:–Mutual Exclusion•At least one resource must be held is in non-sharable mode–Hold and wait•There exists a process holding a resource, and waiting for another–No preemption•Resources cannot be preempted–Circular wait•There exists a set of processes {P1, P2, … PN}, such that–P1 is waiting for P2, P2 for P3, …. and PN for P1All four conditions must hold for deadlock to occur11Reminder: Resource Allocation Graph (from Monday)•Deadlock can be described using a resource allocation graph, RAG•The RAG consists of:–set of vertices V = P R, •where P={P1,P2,…,Pn} of processes and R={R1,R2,…,Rm} of resources.–Request edge: directed edge from a process to a resource, •PiRj, implies that Pi has requested Rj.–Assignment edge: directed edge from a resource to a process, •RjPi, implies that Rj has been allocated to Pi.•If the graph has no cycles, deadlock cannot exist. •If the graph has a cycle, deadlock may exist.12Res. Alloc. Graph Example............ .. .R1 R3R3R4R2P3P2P1R1P1 P2 P3P4R2 R4Cycles:P1-R1-P2-R3-P3-R2-P1P2-R3-P3-R2-P2and there is deadlock.Same cycles, but no deadlock13Dealing with Deadlocks•Reactive Approaches:–Periodically check for evidence of deadlock•For example, using a graph reduction algorithm–Then need a way to recover•Could blue screen and reboot the computer•Could pick a “victim” and terminate that thread–But this is only possible in certain kinds of applications–Basically, thread needs a way to clean up if it gets terminated and has to exit in a hurry!•Often thread would then “retry” from scratch•Despite drawbacks, database systems do this14Dealing with Deadlocks•Proactive Approaches:–Deadlock Prevention•Prevent one of the 4 necessary conditions from arising•…. This will prevent deadlock from occurring–Deadlock Avoidance•Carefully allocate resources based on future knowledge•Deadlocks are prevented•Ignore the problem–Pretend deadlocks will never occur–Ostrich approach… but surprisingly common!15Deadlock Prevention•Can the OS prevent deadlocks?•Prevention: Negate one of necessary conditions–Mutual exclusion:•Make resources sharable•Not always possible (spooling?)–Hold and wait•Do not hold resources when waiting for another Request all resources before beginning executionProcesses do not know what all they will needStarvation (if waiting on many popular resources)Low utilization (Need resource only for a bit)•Alternative: Release all resources before requesting anything new–Still has the last two problems16Deadlock Prevention•Prevention: Negate one of necessary conditions–No preemption: •Make resources preemptable (2 approaches)•Preempt requesting processes’ resources if all not available•Preempt resources of waiting processes to satisfy request•Good when easy to save and restore state of resource–CPU registers, memory virtualization•Bad if in middle of critical section and resource is a lock–Circular
View Full Document
Unlocking...