DOC PREVIEW
U of I CS 241 - Introduction to Deadlock

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to DeadlockCS241 AdministrativeContent of This LectureResource (1)Resource (2)Using Semaphore to Share ResourceBut Deadlock can Happen!DeadlockAnother Example - Remember Dining Philosophers?Dining Philosopher ChallengeSeems simple enough …?… Deadlock (Each P. holds left fork)Deadlock DefinitionConditions for DeadlockNecessary and Sufficient Conditions for DeadlockMutual ExclusionWait-for ConditionSlide 18No Preemption ConditionSlide 20Circular Wait ConditionSlide 22Deadlock Modeling (1)Deadlock Modeling (2)Deadlock Modeling (3)Deadlock Modeling (4)Resource Allocation Graph (multiple resource types)Deadlock ModelStrategiesSummaryCS 241 Spring 2007System Programming 1Introduction to DeadlockLecture 21Klara Nahrstedt2CS241 AdministrativeRead Stallings Chapter 63Content of This LectureGoals:Understanding deadlockHow to avoid deadlocksThings covered in this lectureDeadlock conceptsDeadlock conditions4Resource (1)A resource is a commodity needed by a process. Resources can be either: serially reusable: e.g., CPU, memory, disk space, I/O devices, files. acquire  use  release Real life analogy?consumable: produced by a process, needed by a process; e.g., messages, buffers of information, interrupts. create  acquire  use Resource ceases to exist after it has been used, so it is not released. Real life analogy?5Resource (2)Resources can also be either: preemptible: e.g., CPU, central memoryWhat does it mean?non-preemptible: e.g., tape drives.Any other examples? And resources can be either: shared among several processes ordedicated exclusively to a single process.6Using Semaphore to Share ResourceProcess P();{ A.Down(); B.Down(); use both resource B.Up(); A.Up(); }Process Q();{ A.Down(); B.Down(); use both resource B.Up(); A.Up(); }423External Semaphore A(1), B(1);External Semaphore A(0), B(1);2External Semaphore A(0), B(0);3External Semaphore A(0), B(1);4External Semaphore A(1), B(1);55067But Deadlock can Happen!Process P();{ A.Down(); B.Down(); use both resources B.Up(); A.Up(); }Process Q();{ B.Down(); A.Down(); use both resources A.Up(); B.Up(); }3211External Semaphore A(1), B(1);1External Semaphore A(0), B(1);2External Semaphore A(0), B(0);38DeadlockMechanism for DeadlockControl9Another Example - Remember Dining Philosophers?10Dining Philosopher Challenge{ Think | Eat }N Philosophers circular table with N chopsticksTo eat the Philosopher must first pickup two chopsticksith Philosopher needs ith & i+1th chopstickOnly put down chopstick when Philosopher has finished eatingDevise a solution which satisfies mutual exclusion but avoids starvation and deadlock11Seems simple enough …?while(true) { think() sem_wait(chopstick[i]) sem_wait(chopstick[(i+1) % N]) eat() sem_post(chopstick[(i+1) % N]) sem_post(chopstick[i])}12… Deadlock (Each P. holds left fork)while(true) { think() sem_wait(chopstick[i]) sem_wait(chopstick[(i+1) % N]) eat() sem_post(chopstick[(i+1) % N]) sem_post(chopstick[i])}13Deadlock DefinitionWhat is a deadlock?A process is deadlocked if it is waiting for an event that will never occur. Typically, but not necessarily, more than one process will be involved together in a deadlock (the deadly embrace). Is deadlock the same as starvation (or indefinitely postponed)? A process is indefinitely postponed if it is delayed repeatedly over a long period of time while the attention of the system is given to other processes. I.e., logically the process may proceed but the system never gives it the CPU.14Conditions for DeadlockWhat conditions should exist in order to lead to a deadlockReal life analogy such as“You take the monitor, I grab the keyboard”Cars in intersection15Necessary and Sufficient Conditions for DeadlockMutual exclusionProcesses claim exclusive control of the resources they requireWait-for conditionProcesses hold resources already allocated to them while waiting for additional resourcesNo preemption conditionResources cannot be removed from the processes holding them until used to completionCircular wait conditionA circular chain of processes exists in which each process holds one or more resources that are requested by the next process in the chain16Mutual ExclusionProcesses claim exclusive control of the resources they requireHow to break it?17Wait-for ConditionProcesses hold resources already allocated to them while waiting for additional resourcesHow to break it?18P(s1)P(s2)WorkV(s2)V(s1)P(s2)P(s3)WorkV(s3)V(s2)P(s3)P(s1)WorkV(s1)V(s3)BlockedProcess 1 Process 2 Process 319No Preemption ConditionResources cannot be removed from the processes holding them until used to completionHow to break it?20Its difficult to take a tape drive away from a process that is busy writing a tape21Circular Wait ConditionA circular chain of processes exists in which each process holds one or more resources that are requested by the next process in the chain How to break it?22P(s1)P(s2)WorkV(s2)V(s1)P(s2)P(s3)WorkV(s3)V(s2)P(s3)P(s1)WorkV(s1)V(s3)BlockedProcess 1 Process 2 Process 323Deadlock Modeling (1) Resource allocation graphGraph have two kinds of nodesProcesses Resources Graph’s arcs have two meanings:Arc from resource node to process node = process holds resource (i.e., resource has been assigned to process and process is holding it)Arc from process node to resource node = process requests resource (i.e., process is currently blocked waiting for that resource)24Deadlock Modeling (2)Modeled with directed graphsresource R assigned to process Aprocess B is requesting/waiting for resource Sprocess C and D are in deadlock over resources T and Uassignrequest25How deadlock occursA B CDeadlock Modeling (3)26Deadlock Modeling (4)How deadlock can be avoided(o) (p) (q)27Resource Allocation Graph(multiple resource types)28Deadlock Model29StrategiesStrategies for dealing with Deadlocksdetection and recoverydynamic avoidance careful resource allocationprevention negating one of the four necessary conditions30Summary Principles of Deadlock Examples of Deadlock Deadlock ConditionsDeadlock


View Full Document

U of I CS 241 - Introduction to Deadlock

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Introduction to Deadlock
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Deadlock and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Deadlock 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?