程序代写代做代考 database algorithm chain 05-Deadlocks

05-Deadlocks

Peter R. Pietzuch
prp@doc.ic.ac.uk

Deadlocks

What is deadlock & how it occurs
Detecting potential deadlocks

– resource allocation graphs
Recovery techniques
Prevention techniques
Livelock and starvation

22

Deadlocks

Example: two processes want to scan a document,
and then save it on a CD

down(scanner);
down(cd_writer);
scan_and_record();
up(cd_writer);
up(scanner);

down(cd_writer);
down(scanner);
scan_and_record();
up(scanner);
up(cd_writer);

P0 P1

Deadlock?

33

Dining Philosophers

Each philosopher
needs 2 chopsticks
in order to eat

44

Dining Philosophers

Does this work?

What if everybody takes
chopstick[i] at same time?

55

Deadlock

Set of processes is deadlocked if each process is waiting for
an event that only another process can cause

Resource deadlock is most common, 4 conditions must hold:
1. Mutual exclusion: each resource is either available

or assigned to exactly one process
2. Hold and wait : process can request resources while

it holds other resources, requested earlier
3. No preemption: resources given to a process cannot

be forcibly revoked
4. Circular wait: two or more processes in a circular

chain, each waiting for a resource held by the next
process

66

Resource Allocation Graphs

Directed graph models resource allocation
– Directed arc from resource to process means that the

process is currently owning that resource
– Directed arc from process to resource means that the

process is currently blocked waiting for that resource

Cycle = deadlock

77

Dining Philosophers – Deadlock Cycle

Owns chopstick

Waiting for
chopstick

88

Strategies For Dealing With Deadlock

Ignore it
– “The Ostrich Algorithm”
– Contention for resources is low à deadlocks infrequent

Detection and recovery
Dynamic avoidance by careful resource allocation
Prevention by negating 1 of the 4 conditions

99

Detection and Recovery

Detects deadlock and recovers after the fact
Dynamically builds resource ownership graph and looks for cycles
When an arc has been inspected it is marked and not visited again

We are doing a depth-
first search from each
node in the graph,
checking for cycles.

1. For each node do:
2. Initialise L to the empty list
3. Add the current node to L and check if it

appears in L two times. Yes: cycle!
4. From current node check if any unmarked

outgoing arc
Yes: goto 5, No: goto 6

5. Pick unmarked outgoing arc, mark it, follow it
to new current node and goto 3

6. If this is initial node then no cycles detected,
terminate
else reached dead end, remove it, go back

to previous node and make it current and
goto 3

[Tanenbaum, MOS 6.4.1]

A

S

B

DC T

U

E

VGF

W

R

Detection – Example

§ A holds R and wants S
§ B holds nothing wants T
§ C holds nothing wants S
§ D holds U wants S and T
§ E holds T and wants V
§ F holds W and wants S
§ G holds V and wants U

Cycle?

• Starting at R, initialise L = [ ]
• Add R to list and move to A

(only possibility)
• Add A giving L = [R,A]
• Go to S so L = [R,A,S]
• S has not outgoing arcs à dead end,

backtrack to A
• A has no outgoing arcs, backtrack to R
• Restart at A, add A to L à dead end
• Restart at B, follow outgoing arcs until

D, now L = [B,T,E,V,G,U,D]
• Make random choice:

– S à dead end and backtrack to D
– Pick T update L = [B,T,E,V,G,U,D,T]

• Cycle: Deadlock found, STOP

R

Detection – Example (2)

A

S

B

DC
T

U

E

VGF

W

1212

Recovery

Pre-emption:
– Temporarily take resource from owner and give to

another

Rollback:
– Processes are periodically checkpointed (memory

image, state)
– On a deadlock, roll back to previous state

Killing processes:
– Select random process in cycle and kill it!

• OK for compile jobs, not so good for database, why?

1313

Circular Chain Deadlock Question

Suppose that there is a resource deadlock in a system. Can
the set of processes deadlocked include processes that are
not in the circular chain in the corresponding resource
allocation graph?

Menti.com Q1 99 89 93

1515

Strategies For Dealing With Deadlock

Ignore it
Detection and recovery
Dynamic avoidance

– System grants resources when it knows that it is safe to
do so

Prevention

1616

Banker’s Algorithm (Dijkstra 1965)

Four customers A, B, C and D
– Credit unit = £1K

Banker knows that all customers don’t
need max credit

– So reserves only 10 (instead of 22)
units

Each customer randomly asks for credit

• Four customers A, B, C and D
§ Credit unit = £1K

• Banker knows that all customers don’t
need max credit
§ So reserves only 10 (instead of 22) units

• Each customer randomly asks for credit
• For each process A-D,

§ Has = number of resource items allocated
§ Max = number of items required.

1717

Banker’s Algorithm – Save vs. Unsafe States

Safe state:
– Are there enough resources to satisfy any (maximum) request

from some customer?
– Assume that customer repays loan, and then check next

customer closest to the limit, etc.
A state is safe iff there exists a sequence of allocations that
guarantees that all customers can be satisfied

SAFE UNSAFE

1818

Banker’s Algorithm – Safe vs. Unsafe States

SAFE

UNSAFE

A state is safe iff there exists a sequence of
allocations that guarantees all customers can be satisfied

1919

Banker’s Algorithm – Safe vs. Unsafe States

Request granted only if it leads to a safe state
Unsafe state does not have to lead to deadlock, but
banker cannot rely on this behaviour

Algorithm can be generalized to handle multiple
resource types

SA
FE

U
N

SA
FE

2020

Bankers Algorithm Question

A system has 12 magnetic tape drives and 3 processes :
P0, P1, and P2.

What is a safe sequence for running the processes?

Process Has Max Need
P0 5 10
P1 2 4
P2 2 9

Menti.com Q2 99 89 93

2121

Strategies For Dealing With Deadlock

Ignore it
Detection and recovery
Dynamic avoidance
Prevention

– Attack one of the four deadlock conditions:
• Mutual exclusion,
• Hold and wait
• No preemption
• Circular wait

2222

Deadlock Prevention

Attacking the Mutual Exclusion Condition
– E.g., share the resource

Attacking the Hold and Wait Condition
– Require all processes to request resources before start

• If not all available then wait

– Issue: need to know what you need in advance
Attacking the No-Preemption condition

– E.g., forcing a process to give up printer half way through.
Usually not good

Attacking Circular Wait Problem
– Force single resource per process, if needs second, must release

first.
• Optimality issues

– Number resources, processes must ask for resources in this order
• Issue: large number of resources…can be difficult to

organise

2323

Dining Philosophers – Ordering Resources

1

2

3
4

5

• Request resources in specific
order

• Philosopher gets chopstick 4
and can then ask for 5, but if
he gets 5 first he cannot ask
for chopstick 4.

• The process holding the
highest resource will never ask
for a resource already
assigned.

2424

Communication Deadlock

E.g., process A sends message to B and blocks waiting on
B’s reply

B didn’t get A’s message then A is blocked and B is
blocked waiting on message è deadlock!

Ordering resources, careful scheduling not useful here

What should we use?
– Communication protocol based on timeouts

2525

Livelock

process_A process_B
{ {

Enter_region (resource1) Enter_region (resource2)
Enter_region (resource2) Enter_region (resource1)
Use(resource1, resource2) Use(resource1, resource2)
Leave_region (resource2) Leave_region (resource1)
Leave_region (resource1) Leave_region (resource2)

} }

• Example 2: System receiving and processing incoming messages.
Processing thread has lower priority and never gets a chance to run
under high load (receive livelock)

• Example 1: Enter_region() tests mutex then either grabs resource or
reports failure. If attempt fails, it tries again. Processes loop after
gaining first resource but failing second.

• Livelock: Processes/threads are not blocked, but they or the system
as a whole does not make progress

2626

Starvation

Concerns policy
Who gets what resource when
Many jobs want printer, who gets it?

– Smallest file? Suits majority, fast turnaround, but
what about occasional large job?

– FCFS is more fair in this case

2727

Single Processor Deadlock?

Can a single-processor system have no processes ready
and no process running?
Is this a deadlocked system? Explain your answer.

2929

Deadlock Question

Two processes, A and B, each need three records, 1, 2,
and 3, in a database. If A asks for them in the order 1, 2,
3, and B asks for them in the same order, deadlock is not
possible. However, if B asks for them in the order 3, 2, 1,
then deadlock is possible. With three resources, there are
3! = 6 possible combinations each process can request
resources.
What fraction of all combinations is guaranteed to be
deadlock free?

Menti.com Q3 99 89 93

3131

Deadlock Summary

Deadlocks occur from:
§ Accessing limited resources – not enough to go round
§ Incorrect programming of synchronisation

Resource allocation graphs can detect potential cyclic
deadlock

Recovery: pre-emption, rollback, kill process
Prevention

§ Use safe resource allocation strategy
§ Avoid unnecessary mutual exclusion – share instead
§ Ordered resource allocation

Livelock: no progress – incorrect programming?
Starvation: often due to priority