程序代写 CMPUT 379 (E.S. Elmallah)

See chapter 7 in [SGG 9/E]
1. Some definitions
2. Deadlockprevention
3. Deadlockavoidance

Copyright By PowCoder代写 加微信 powcoder

4. Deadlockdetectionandrecovery
CMPUT 379 (E.S. Elmallah)
1. Some Definitions
A deadlock: two (or more) processes waiting
indefinitely for an event that will never occur. A useful classification of resources:
o A preemptable resource can be taken away and returned back with no ill effect (e.g., memory, and CPU)
o A non-preemptable resource can’t be taken away unless it is released voluntarily (e.g., a tape drive, a file opened for write)
CMPUT 379 (E.S. Elmallah)

Necessary Conditions for Deadlocks
In a deadlock, the following conditions hold:
o Mutual Exclusion: at least one resource is held in a nonsharable mode.
• In our example: at least one stepping stone is held for exclusive use.
o No preemption: each resource in the deadlock can’t be preempted (i.e., taken away without being voluntarily released).
• In our example: stepping stones can’t be taken temporarily.
o Hold an wait: At least one process holds at least one resource and is waiting to acquire additional resources held by other processes.
o Circular wait: · · ·
CMPUT 379 (E.S. Elmallah)
So, how can one prevent a deadlock?
Strategies for handling deadlocks
o Ignore: (e.g., Windows and Unix)
o Prevent: (using military-style policies: e.g., limit access, impose restrictions, restrain requests, enforce resource priority, etc.)
o Avoid: (be flexible but proceed cautiously) o Detect and Recover
CMPUT 379 (E.S. Elmallah)

Resource Allocation Graphs
Pi is waiting for an instance of resource Rj :
Instance 4 of Rj is held by Pi:
So, how can one detect a deadlock?
o Case: Each resource has exactly one instance:
CMPUT 379 (E.S. Elmallah)
o Case: Some resources have several instances:
CMPUT 379 (E.S. Elmallah)

2. Deadlock Prevention
To prevent, we try to disallow any of the following conditions.
Mutual Exclusion. In general, this condition cannot be disallowed.
Preemption. Here is a possible protocol:
o “If a requested resource cannot be granted immediately, then force the process to release all currently held resources. Later, the process should request them again”
o The above protocol assumes that resources can be released (at any arbitrary point of time).
CMPUT 379 (E.S. Elmallah)
Hold and Wait. Impose the following regime:
o “If a process is holding a resource, it cannot request
another resource.”
o That is, a process files a single request to acquire a set of resources. It should then release all of them before filing another request.
Circular Wait.
o Impose a total ordering of all resource types: e.g., f (tape drive) = 1, f (disk drive) = 5, f (printer) = 12, etc.
o Require that each process requests resources in an increasing order of enumeration.
CMPUT 379 (E.S. Elmallah)

3. Deadlock Avoidance
The Bankers Algorithm [Habermann ’69]
Each resource type has one or more instances/units.
 Example:
o resource type A (tape drive) has 12 units,
o resource type B (disk drive) has 5 units, etc. o Wewrite|A|=12,|B|=5,etc.
Each process declares (a priori) the maximum number of instances of each type that it may need.
CMPUT 379 (E.S. Elmallah)
What is a resource-allocation state ? o Description: |A| = 10, |B| = 5, and |C| = 7
o Consistency conditions: for each Pi and resource type X:
CMPUT 379 (E.S. Elmallah)

What is an execution sequence ?
o An ordering of the processes < P(0), P(1), · · ·, P(n−1) > where P(0) should finish first, followed by P(1), then P(2), etc.
What is a deadlock state ?
o A state where all processes are in a circular-wait . o Example. |A|= 3
CMPUT 379 (E.S. Elmallah)
What is a safe state ?
o A state for which there exists at least one execution
sequence that allows all processes to finish. o Example. |A| = 12
What is an unsafe state ?
CMPUT 379 (E.S. Elmallah)

Does “unsafe”  “deadlock”? o Example. |A| = 12
o No deadlock yet (P1 can finish), but · · ·
So, to avoid deadlock you better stay within the
safe area.
Definition: Given two vectors x and y, we say x ≤ y if, for every possible index i, x[i] ≤ y[i].
o Q:Does“notx≤y”imply“x>y”? CMPUT 379 (E.S. Elmallah)
Safety Testing
Given a state S =
o n processes {P0, P1, · · · , Pn−1},
o for each Pi , array mi [· · ·] (max. demands), and o array hi [· · ·] (held resources).
CMPUT 379 (E.S. Elmallah)

testSafety (S)
1. Compute the available resources: i.e., for each
resource X,
2. Mark all processes unfinished
3. Repeat until either you get stuck, or all processes can be finished:
a. Find an unfinished process Pi whose worst case request vector Requesti (= mi −hi ) can be satisfied, i.e., Requesti ≤ Available
b. finished, and return all its resources to array Available
4. Return “safe” if all processes can be finished 15 CMPUT 379 (E.S. Elmallah)
Testing a Request Vector
 Given a state S, and a request vector Requesti, is it safe to allocate all resources in Requesti ?
testRequest (S, Requesti )
1. Return“invalid”if
2. Let S’ be the state that would result if we grant all requests in Requesti while in state S ;
3. Call testSafety (S’ ); return “safe” if S’ is a safe state
CMPUT 379 (E.S. Elmallah)

4. Deadlock Detection and Recovery Detection: Modify function testSafety(S) to
detect deadlocks.
Recovery: See the textbook for a discussion on: o Recovery through termination
o Recovery through preemption
o Recovery through checkpointing and rollback
CMPUT 379 (E.S. Elmallah)

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com