CS计算机代考程序代写 scheme data structure database chain concurrency algorithm PowerPoint Presentation

PowerPoint Presentation

Computer Systems
Deadlocks

Dr. Mian M. Hamayun
m.m. .uk

Slide #2 of 49

Lecture Objective

The objective of this lecture is to
develop a basic understanding of deadlocks and

the techniques used to deal with them.

Slide #3 of 49

Lecture Outline

 Introduction

 Reusable vs. Consumable Resources

 Deadlock Conditions

 Resource Allocation Graphs

 Deadlock Handling
 Deadlock Prevention

 Deadlock Avoidance

 Deadlock Detection

 Summary

Slide #4 of 49

A Treasury of the Railroad Folklore

“When two trains approach each other at a crossing,
both shall come to a full stop and neither shall start up
again until the other has gone.”

Statute passed by the Kansas State Legislature, early in

the 20th

century.

— A TREASURY OF RAILROAD FOLKLORE,

B. A. Botkin and . #5 of 49

What is a Deadlock?

Slide #6 of 49

Deadlock – How it can happen?

Slide #7 of 49

Deadlock – How it may not happen!

Slide #8 of 49

Reusable Resources

 Used by only one process at a time and not depleted by
that use.
 Processors, I/O channels, main and secondary memory,

devices, and data structures such as files, databases, and
semaphores

 Processes obtain resources that they later release for
reuse by other processes

 Deadlock occurs if each process holds one resource
and requests the other

Slide #9 of 49

Reusable Resources – Example#1

Slide #10 of 49

Reusable Resources – Example#2

Space is available for allocation of 200Kbytes, and the
following sequence of events occur

Deadlock occurs if both processes progress to their
second request

Slide #11 of 49

Consumable Resources

 Created (produced) and destroyed (consumed)
 Interrupts, signals, messages, and information in I/O buffers

 For Example: Deadlock may occur if a Receive
message is blocking

 May take a rare combination of events to cause deadlock

Slide #12 of 49

What is a Deadlock?

 A deadlock is a permanent blocking of a set of
processes competing for resources

 It is a circular resource conflict between a set of
processes
 Each process currently holds a resource requested by another

process

 Each process waits for another process to release its resource

 Involve conflicting needs for resources by two or more
processes

 No efficient solution!

Slide #13 of 49

Conditions for a Deadlock

There are 4 deadlock conditions that, when they all hold,
will necessarily lead to a deadlock

Three Preconditions:

1) Mutual Exclusion
 Only one process may use a resource at a time

2) Hold-and-wait
 Process can hold resources, while it is waiting for other

resources to become available.

3) No Preemption
 Processes cannot be interrupted to free their resources by

force

Slide #14 of 49

Conditions for a Deadlock

Occurrence of a particular sequence of events that leads
to a Circular Wait

4) Circular Wait
 Processes wait for each other to release resources they

want to acquire, they form a kind of “closed chain of
processes”

Slide #15 of 49

Resource Allocation Graphs

 Directed graph that depicts the state of a system of
resources and processes

Slide #16 of 49

Resource Allocation Graphs

Slide #17 of 49

Resource Allocation Graphs

Slide #18 of 49

Deadlock Conditions

 A deadlock occurs when a circular wait occurs and
cannot be resolved

 A circular wait cannot be resolved when conditions 1 to
3 hold!

 Therefore
 If conditions 1 to 3 occur, then there is a possibility of a

deadlock

 If conditions 1 to 4 occur, then there will necessarily be a
deadlock

Slide #19 of 49

Handling Deadlocks

 Deadlock Prevention
 Avoid at least one of the 4 deadlock conditions

 Deadlock Avoidance
 The reservation of resources that would lead to deadlock,

are not granted

 Deadlock Detection
 There is no restriction on resource allocation

 There is a periodic check whether a deadlock is occurring

 In case a deadlock is detected, recovery mechanisms are
employed

Slide #20 of 49

DEADLOCK
PREVENTION

Slide #21 of 49

Deadlock Prevention

The operating system is designed to prevent deadlocks
from occurring

 Indirect deadlock prevention
 Avoid occurrence of one of the conditions 1, 2, 3 i.e. Mutual

exclusion, hold and wait, no preemption

 Direct deadlock prevention
 Avoid Circular Waits (condition 4)

Slide #22 of 49

Indirect Deadlock Prevention

 Mutual Exclusion Prevention
 This cannot be avoided, as a lack of mutual exclusion may

lead to race conditions

 Hold and Wait Prevention
 Pre-allocation of all required resources in advance

 Block a process until all resources become available
► Long delays for processes, low concurrency

► Inefficient utilization of resources

► A process may not know in advance what resources it will
require

Slide #23 of 49

Indirect Deadlock Prevention

 No Preemption Prevention – May be implemented in
different ways.
 If a process holding a resource is denied another resources

the first may also be preempted.

 If a process needs a resource that is being used by another
process then preempt that resource.

 Practically possible only when state of a resource can be
saved and restored, such as a processor (storing the
processor status word, context switch)

Slide #24 of 49

Direct Deadlock Prevention

 Prevent Circular Wait from occurring
 One way to prevent this is to associate an index with each

resource. Processes are then required to acquire resource
with lower index before acquiring resource of higher index
(resource ordering).

 Consider two processes (A & B) competing for 2 resources
(Ri & Rj, where i < j). Suppose A acquires Ri first then it will be able to proceed as B is not allowed to acquire Rj.  Usually Inefficient! Slide #25 of 49 DEADLOCK AVOIDANCE Slide #26 of 49 Deadlock Avoidance  Assures that a deadlock never occurs!  A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock?  Requires knowledge of future process requests Slide #27 of 49 Deadlock Avoidance – Approaches Allow the three necessary conditions but make intelligent decisions while allocating resources. 1) Process Initiation Denial  Do not start a process if its demands might lead to deadlock 2) Resource Allocation Denial  Do not grant an incremental resource request to a process if this allocation might lead to deadlock Slide #28 of 49 Deadlock Avoidance Slide #29 of 49 Deadlock Avoidance Properties of the Resource Matrix System 1) Rj = Vj + ∑iAij for all j All resources are either allocated or available. 2) Cij R≤ j for all i,j No process can claim more than the total system resource. 3) Aij C≤ ij for all i,j No process is allocated more than its claim. Slide #30 of 49 Deadlock Avoidance Process Initiation Denial  A new process P (n+1) is initiated, only if: Rj C≥ (n+1)j + ∑iCij for all j  The process P (n+1) is started if the maximum claim of all currently running processes i plus the claims of the new process P (n+1) can be met.  This scheme assumes the worst i.e. it assumes that all processes will demand the resources at the same time. Slide #31 of 49 Deadlock Avoidance Resource Allocation Denial (Banker’s Algorithm)  A process i is allocated a resource j only if the system remains in safe state.  Safe State: A state in which there exists at least one sequence of allocation to processes which does not result in a deadlock.  State of system is reflected by the current allocation of resources to processes Slide #32 of 49 Finding a Safe Sequence? Basic Question:  Can any of the participating processes run to completion with the units of resources available?  Can the difference between the maximum requirement and current allocation of any process be met with the available resources? Condition to be met by process i, using resource j: Cij – Aij V≤ j for all j The number of claimed units of resource j, minus the already allocated units of resource j, must not be more than what is still available. Slide #33 of 49 Deadlock Avoidance – Example # 1 Slide #34 of 49 Deadlock Avoidance – Example # 1 Slide #35 of 49 Deadlock Avoidance – Example # 1 Slide #36 of 49 Deadlock Avoidance – Example # 1 Slide #37 of 49 Deadlock Avoidance – Example # 1 Slide #38 of 49 Deadlock Avoidance – Example # 2 Slide #39 of 49 Deadlock Avoidance – Example # 2 Don’t Grant this Request! Slide #40 of 49 Deadlock Avoidance – Summary  It is not necessary to preempt and rollback processes, as in deadlock detection (coming later).  Less restrictive than deadlock prevention  Maximum resource requirement must be stated in advance  Processes under consideration must be independent; no synchronization requirements  There must be a fixed number of resources to allocate  No process may exit while holding resources Slide #41 of 49 DEADLOCK DETECTION & RECOVERY Slide #42 of 49 Deadlock Detection (Algorithm) 1) Unmark (assume deadlocked (T)) all processes and define a matrix Q representing future requests of each process. 2) Mark (not deadlocked (F)) all processes that have all zeros in their allocation matrix A (means these have finished) 3) Initialize a temporary vector W (work vector) equal to V (available resource vector) 4) Find an index i such that process i is unmarked (assumed deadlocked) and where W such that Qik ≤ Wk for 1 k m≤ ≤ . 5) If such a row is found then update W as Wk = Wk + Aik for all 1 ≤ k m≤ and mark (not deadlocked) process i. Go to step 4 above. 6) If no row is found stop the algorithm. 7) All unmarked processes are the deadlocked processes. Slide #43 of 49 Deadlock Detection – Example Slide #44 of 49 Deadlock Detection – Example Slide #45 of 49 Deadlock Detection – Example Slide #46 of 49 Deadlock Recovery 1) Abort all processes involved in a deadlock. 2) Roll back each deadlocked process to some previous state and then restart the processes 3) Abort deadlocked processes one by one until deadlock exists no more. 4) Preempt the resources one by one until the deadlock exists no more. The preemption or aborting should be done on some criteria and not at random (Ex: First i.e. processor time used, output produced, resources held etc.). Slide #47 of 49 Integrated Deadlock Strategy It’s a Combination of Approaches. For example:  Group Resources (in resource classes)  Swappable Space: blocks of memory on secondary storage for use in swapping processes  Process Resources: assignable devices, such as tape drives, files (I/O) etc.  Main Memory: assignable to processes in pages or segments  Apply different strategies  Swappable space: deadlock prevention (all required resources allocated at once, maximum storage requirements to be known)  Process resources: deadlock avoidance (processes declare ahead of time the resources they will require). Prevention is also possible by resource ordering.  Main memory: deadlock prevention by preemption. Slide #48 of 49 Summary Slide #49 of 49 References / Links Chapter #7: Deadlocks, Operating System Concepts (9th Edition) by , Galvin and Chapter #6: Concurrency: Deadlocks and Starvation, Operating Systems: Internals and Design Principles (7th edition) by Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 45 Slide 46 Slide 47 Slide 48 Slide 49