DOC PREVIEW
U of I CS 241 - Operating Systems Deadlock Issues

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 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 19 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 19 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 19 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 19 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 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS241 Operating SystemsDeadlock Issues (1)ContentAdministrative NotesResource (1)Resource (2)Using Semaphore to Share ResourceBut Deadlock can Happen!DeadlockDeadlock DefinitionConditions for DeadlockNecessary and Sufficient Conditions for DeadlockMutual ExclusionWait-for ConditionNo Preemption ConditionCircular Wait ConditionReminderCS241 Operating SystemsDeadlock Issues (1)Klara NahrstedtLecture 162/24/20062/20/2006CS 241 - System Programming, Klara Nahrstedt2Contentz Deadlock Conceptz Deadlock Conditions2/20/2006CS 241 - System Programming, Klara Nahrstedt3Administrative NoteszMP2 on scheduling is runningz Quiz 4 todayz Read Tanenbaum Chapter 3.3.1 and 3.3.22/20/2006CS 241 - System Programming, Klara Nahrstedt4Resource (1)zA resource is a commodity needed by a process. z Resources can be either: –serially reusable: e.g., CPU, memory, disk space, I/O devices, files. acquire Æ use Æ release –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.2/20/2006CS 241 - System Programming, Klara Nahrstedt5Resource (2)z Resources can also be either: –preemptible: e.g., CPU, central memory or– non-preemptible: e.g., tape drives. zAnd resources can be either: – shared among several processes or– dedicated exclusively to a single process.2/20/2006CS 241 - System Programming, Klara Nahrstedt6Using Semaphore to Share ResourceProcess Q();{ A.Down();B.Down();use both resourceB.Up();A.Up(); }Process P();{ A.Down();B.Down();use both resourceB.Up();A.Up(); }02 6345External 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);52/20/2006CS 241 - System Programming, Klara Nahrstedt7But Deadlock can Happen!Process P();{ A.Down();B.Down();use both resourcesB.Up();A.Up(); }Process Q();{ B.Down();A.Down();use both resourcesA.Up();B.Up(); }3211External Semaphore A(1), B(1);1External Semaphore A(0), B(1);2External Semaphore A(0), B(0);32/20/2006CS 241 - System Programming, Klara Nahrstedt8DeadlockMechanism for DeadlockControl2/20/2006CS 241 - System Programming, Klara Nahrstedt9Deadlock DefinitionzWhat 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). zIs 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.2/20/2006CS 241 - System Programming, Klara Nahrstedt10Conditions for DeadlockzWhat conditions should exist in order to lead to a deadlockz Real life analogy such asz“You take the monitor, I grab the keyboard”zCars in intersection2/20/2006CS 241 - System Programming, Klara Nahrstedt11Necessary and Sufficient Conditions for DeadlockzMutual exclusion–Processes claim exclusive control of the resources they requirezWait-for condition–Processes hold resources already allocated to them while waiting for additional resourceszNo preemption condition–Resources cannot be removed from the processes holding them until used to completionzCircular wait condition–A circular chain of processes exists in which each process holdsone or more resources that are requested by the next process in the chain2/20/2006CS 241 - System Programming, Klara Nahrstedt12Mutual ExclusionzProcesses claim exclusive control of the resources they require2/20/2006CS 241 - System Programming, Klara Nahrstedt13Wait-for ConditionzProcesses hold resources already allocated to them while waiting for additional resources2/20/2006CS 241 - System Programming, Klara Nahrstedt14P(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 32/20/2006CS 241 - System Programming, Klara Nahrstedt15No Preemption ConditionzResources cannot be removed from the processes holding them until used to completion2/20/2006CS 241 - System Programming, Klara Nahrstedt16Its difficult to take a tape drive away from a process that is busy writing a tape2/20/2006CS 241 - System Programming, Klara Nahrstedt17Circular Wait ConditionzA circular chain of processes exists in which each process holds one or more resources that are requested by the next process in the chain2/20/2006CS 241 - System Programming, Klara Nahrstedt18P(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 32/20/2006CS 241 - System Programming, Klara Nahrstedt19ReminderzMP2 is running, deadline Feb 27z Read Tanenbaum 3.3.1 and


View Full Document

U of I CS 241 - Operating Systems Deadlock Issues

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 Operating Systems Deadlock Issues
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 Operating Systems Deadlock Issues 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 Operating Systems Deadlock Issues 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?