DeadLock Detect&Recovery

DEADLOCKS
Resources
Introduction To Deadlocks
The Ostrich Algorithm
Deadlock Detection & Recovery
Review
• Memory-Mapped I/O
– Map all the control registers into the memory space
– Each control register is assigned a particular and unique memory address
• DMA
– A memory address register
– A byte count register
– One or more control registers
– 3 modes: Word-at-a-time, Block, Fly-by
• Precise vs. Imprecise Interrupt
– Precise: Leave the machine in a well-defined state
• PC is saved in a known place
• All instructions before the one pointed to by the PC have fully executed
• No instruction beyond the one pointed to by the PC has been executed
• Execution state of the instruction pointed to by the PC is known
– Imprecise: Does not meet all requirements as precise
Review
• I/O Software
– Goals
• Device Independent, Error handling, Synchronous vs. Asynchronous,
Buffering, Dedicated device allocation
– I/O with DMA
– Layers
• User level I/O software: pooling with daemon scheduling (Asynchronous)
• Device independent
– Uniform naming, Uniform interface, Independent block size
– Buffering
– Error handling, Dedicated device allocation
• Device Drivers: help OS control specified devices depending on standard
interface
• Interrupt Handlers: handle interrupt to determine what the system
should do
• Disk arm scheduling Review
– Seek time
• FCFS: Process request sequentially
• SSF: the least movement of the disk arm from its current head position
• Elevator
– Approach: Arm moves in one direction only, satisfying all
outstanding requests until it reaches the last track in that direction
– Implementation: When the highest numbered cylinder with a
pending request has been services, the arm goes to lowest number
cylinder with a pending request and then continues moving in an
upward direction
– Rotational delay
• If two or more requests for the same cylinder are pending, the driver
can issue a request for the sector that will pass under the head next
• The OS should maintain a pending request table for each drive, a seek
should be issued to move its arm to the cylinder where it will be needed
next
– Actual data transfer time (SATA)
Review
• Disk arm scheduling
– Error handling
• Bad sector
– Sectors do not correctly read back the value just written to them
– Controllers remap the bad sector to the spare and/or Shift all the
sectors up one
– OS must first acquire a list of bad sectors, then it can build
remapping tables
• Seek errors
– Move the arm as far out as it will go and reset the controller’s
internal idea of the current cylinder to 0
Review
• Disk arm scheduling
– Disk Consistency
• Stable write: Write block on drive 1, then reading it back to verify. The
driver 2 is written and reread until it succeeds
• Stable read: First read block on drive 1 in n times. If all of these give bad
ECCs, reading on drive 2
• Crash recovery: scans both disks comparing corresponding blocks. Bad
block is overwritten with the good blocks or block from driver 1 is
written onto drive 2
• Optimizing: using Nonvolatile/ Volatile RAM to replace in using driver 2
• Thin Client
• Power Manager
– The programs to use less energy, even if this means providing a
poorer user experience
– Display, HDD, CPU, Memory, Wireless, Driver Interface
Review
• Clocks
– 02 types
• Using volt power
• a crystal oscillator, a counter, and a holding register
– 2 modes: one shot mode, square wave mode
– Functions
• Maintaining the time of day (real time).
• Preventing processes monopolizing CPU
• Accounting for CPU usage
• Handling alarm system call
• Providing watchdog timers
• Doing profiling, monitoring, statistics gathering
• User Interfaces
– Input software (Keyboard software: scan code, echoing, tab handling, device
equivalent
– Output software (Text window, X Window, GUI, Bitmaps, Fonts)
– Mouse software
Objectives
• Resources
– Preemptable and Nonpreemptable Resources
– Resource Acquisition
• Introduction To Deadlocks
– Conditions for Resource Deadlocks
– Deadlock Modeling
• The Ostrich Algorithm
• Deadlock Detection & Recovery
– Deadlock Detection with One Resource of Each Type
– Deadlock Detection with Multiple Resources of Each Type
– Recovery from Deadlock
Overviews
• Context
– Computer systems are full of resources that can only be used by
one process at a time
– All OS have the ability to (temporarily) grant a process
exclusive access to certain resources
– A process needs exclusive access do not one resource, but
several
• A set of blocked processes each holding a resource and
waiting to acquire a resource held by another process
in the set, thus they will remain so forever (deadlocks).
– Deadlock does not occur only on local machine but also across
machines
– Deadlocks can occur in a variety of different situations such as
requesting dedicated I/O devices, on hardware or software
resources
Resources
• Refer the objects as hardware devices, data
records, files, etc .. that must be granted,
acquired, used and released
• A computer will normally have many different
resources
– Some resource is the identical instances may be
available
– Some resource is copied of a resource available
• There are two type resources
– Preemptable
– Nonpreemptable
Resources
Preemptable
• Is resources that can be taken away from the process
owning it with no ill effects (either on system or others)
• Preemptable resources can be resolved deadlocks by
reallocating resources from one process to another
• Ex:
– A system with 256 MB of user memory, one printer, and two of
256 MB processes that each want to print some thing
– Process A requests and gets the printer, then starts to compute the
values to print. Before it has finished with the computation, it
exceeds its time quantum and is swapped out (Process A has the
printer, but it locates on disk)
– Process B now runs and tries, unsuccessfully to acquire the printer
(Process B locates on memory, but it cannot access the printer)
→ Process A take away the B’s memory by swapping process B out
& swapping process A in. After finished, process A releases both
Resources
Nonpreemptable
• Is resources that cannot taken away from its
current owner without causing the computation
to fail
• Ex
– If the process has begun to burn a CD-ROM, suddenly
taking the CD recorder away from it and giving it to
another process will result in a garbled CD
• Deadlocks involve nonpreemptable resources
Resources
Resource Acquisition
• The sequence of events required to use resource
– Request the resource
– Use the resource
– Release the resource
• One of way allowing user manager of resources is
to associate a semaphore with each resource
– The semaphores are all initialized to 1
– A down to acquire the resource, using the resource
– A up on the resource to release resource
Resources
Tanenbaum, Fig. 6-1.

Resources
Deadlock

Introduction to Deadlocks
• A set of processes is deadlocked if each process in the set
is waiting for an event that only another process in the set
can cause
– None of processes can run
– None of them can release any resources
– None of them can be awakened
→ All the processes continue to wait forever
• Assume
– Processes have only a single thread and
– There are no interrupts possible to wake up a blocked processes
Conditionals for Resource Deadlocks
• Resource Deadlocks
– A resource that is owned by a deadlocked process
• Four conditions must hold for there to be a deadlock
– Mutual exclusion condition
• Each resource is either currently assigned to exactly one process or is
available
– Hold and wait condition.
• A process currently holding at least one resource is waiting to acquire
additional resources held by other processes
– No preemption condition.
• A resource can be released only voluntarily by the process holding it, after
that process has completed its task
– Circular wait condition
• There must be a circular chain of two or more process, each of which is
waiting for a resource held by the next member of chain
Deadlock Modeling
• Four conditions for resource deadlocks
can be modeled using directed graphs
(Holt – 1972)
• The graphs have two kinds of nodes
– Processes that are shown as circles
– Resources that are shown as squares
– A directed arc from a resource to process
• The process is holding an instance of resource
– A directed arc from a process to resource
• The process is currently blocked and requests
instance of resource

Deadlock Modeling – Examples
Tanenbaum, Fig. 6-3


Tanenbaum, Fig. 6-4

Deadlock Modeling
• Resource graphs are a tool that
–Let see of a given request/ release request sequence
leads to deadlock
–Help carrying out the requests and releases step by
step, and after every step check the graph to see if it
contains any cycles to check deadlock or not
–Can generalized to handle either single resource or
multiple resource
• Basic facts
–If graph contains no cycles → no deadlock
–If graph contains a cycle
• If only one instance per resource type, then deadlock
• If several instances per resource type, possibility of deadlock
Deadlock Modeling
• Strategies for dealing with deadlocks
– Just ignore the problem
• Maybe if you ignore it, it will ignore you
– Detection and recovery.
• Let deadlocks occur, detect them, take action.
– Dynamic avoidance by careful resource allocation.
– Prevention, by structurally negating one of the four
required conditions
The Ostrich Algorithms
• Just ignore the problem
– Stick your head in the sand and pretend is no problem at
all
– Different people react in different ways
• Mathematicians
– Totally unacceptable and must prevent deadlocks at all
costs
• Engineers
– Would not be willing pay a large penalty in performance
or convenience to eliminate deadlocks
• OS blocks caller that requests the busy device
– The device driver decide blocking or returning an error
code
Deadlock Detection with One Resource of Each Type

Deadlock Detection with One Resource of Each Type
• Algorithm for detecting deadlock:
1. For each node, N in the graph, perform the following five steps
with N as the starting node.
2. Initialize L to the empty list, designate all arcs as unmarked.
3. Add current node to end of L, check to see if node now appears
in L two times. If it does, graph contains a cycle (listed in L),
algorithm terminates.
4. From given node, see if any unmarked outgoing arcs. If so, go
to step 5; if not, go to step 6.
5. Pick an unmarked outgoing arc at random and mark it. Then
follow it to the new current node and go to step 3.
6. If this is initial node, graph does not contain any cycles,
algorithm terminates. Otherwise, dead end. Remove it, go back
to previous node, make that one current node, go to step 3
Deadlock Detection with Multiple Resource of Each Type
• A matrix-based algorithm among n processes, P1 through Pn
and m resource classes, E1 through Em
• Let E be the existing resource vector that gives the total
number of instance of each resource in existence
• Let A be the available resource vector, with Ai giving the
number of instances of resource i that are current available/
unsigned
• Let C be the current allocation matrix, with
– The i-th row of C tells how many instances of each resource class
Pi currently holds
– Cij is the number of instances of resource j that Pi holds
• Let R be the request matrix, with
– The i-th row of P tells how many instances of each resource class
Pi currently wants
– Rij is the number of instances of resource j that Pi wants
C
i 1
ij  Aj  E j
• Each process is initially said to be unmarked
• Deadlock detection algorithm
1. Look for an unmarked process, Pi, for which the Ri is less than
or equal to A.
2. If such a process is found, add Ci to A, mark the process, and
go back to step 1.
3. If no such process exists, the algorithm terminates
• As the algorithm progresses, processes will be marked,
indicating that they are able to complete and are thus not
deadlocked
• When the algorithm terminates, any unmarked processes
are known to be deadlocked
• This algorithm assumes a worst-case scenario: all
processes keep all acquired resources until they exit
No Process deadlock
Progress: 3, 2, 1
Process 1, 2 deadlock
Progress: 3
2 1 0 1

E  (7, 4, 6) A  (0, 0, 0)
0 1 0 0 0 0 
2 0 0  2 0 2
  
C  3 0 3 R  0 0 0 
   
 2 11  1 0 0 
0 2 2 0 0 2 
No Process deadlock
E  (7, 4, 6) A  (0, 0, 0)
0 1 0 0 0 0 
2 0 0  2 0 2
  
C  3 0 3 R  0 0 1 
   
 2 11  1 0 0 
0 2 2 0 0 2 
Process 2, 3, 4, 5 deadlock
Recovery from Deadlock
• Recovery through Preemption
– The ability to take a resource away from a process,
have another process use it, and then give it back
without the process noticing it is highly dependent on
the nature of the resource
• It may be possible to temporarily take a resource away from
its current owner and give it to another process
• Choosing the process to suspends largely on which ones have
resources that can easily be taken back
• In many cases, manual intervention may be required, especially
in batch processing OS running on mainframes
→Is frequently difficult or impossible
Recovery through Rollback
• Checkpoint
– Is supported the system designers and machine operators know
that deadlocks are likely
– Contains not only the memory image, but also the resource state
assigning currently to the process
→ Checkpointing a process
– Process’s state is written to a file so that it can be restarted later
– To be most effective, new checkpoints should not overwrite old
ones but should be written to new files, so as the process execute,
a whole sequence accumulates
• Recovery
– When a deadlock is detected, a process is reset to an earlier
checkpoint that did not have the resource
– Then, the resource is assigned to one of the deadlock processes
– If the restarted process tries to acquire the resource again, it will
have to wait until resource becomes available
Recovery through Killing Processes
• Kill one or more process(es) in the cycle (it’s crudest but
simplest)
• First approach
– Repeating until the cycle is broken
– Kill process in the cycle
– Check the cycle, if so, go back to the first line
• Second approach
– A process not in a cycle can be chosen as the victim in order to
release its resource
– The process to be killed is carefully chosen because it is holding
resources that some process in the cycle needs
• Notes: The process victim should be chosen only if it can be
rerun from the beginning with no ill effects
Summary
• Resources
• Introduction To Deadlocks
• The Ostrich Algorithm
• Deadlock Detection & Recovery
Q&A
Next Lecture
• Deadlock Avoidance
• Deadlock Prevention
• Other Issues

DeadLock Detect&Recovery

Uploaded by

Copyright:

Available Formats

DeadLock Detect&Recovery

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DeadLock Detect&Recovery

Uploaded by

Copyright:

Available Formats

DEADLOCKS

Tanenbaum, Fig. 6-1.

Tanenbaum, Fig. 6-2.

Tanenbaum, Fig. 6-3.

Tanenbaum, Fig. 6-3

Tanenbaum, Fig. 6-4.

Tanenbaum, Fig. 6-4

Tanenbaum, Fig. 6-5.

Tanenbaum, Fig. 5-46.

Tanenbaum, Fig. 6-7.

You might also like