3320 l09

Information about 3320 l09

Published on September 17, 2007

Author: WoodRock

Source: authorstream.com

Content

Deadlocks in Distributed Systems:  Deadlocks in Distributed Systems Deadlocks in distributed systems are similar to deadlocks in single processor systems, only worse. They are harder to avoid, prevent or even detect. They are hard to cure when tracked down because all relevant information is scattered over many machines. People sometimes might classify deadlock into the following types: Communication deadlocks -- competing with buffers for send/receive Resources deadlocks -- exclusive access on I/O devices, files, locks, and other resources. We treat everything as resources, there we only have resources deadlocks. Four best-known strategies to handle deadlocks: The ostrich algorithm (ignore the problem) Detection (let deadlocks occur, detect them, and try to recover) Prevention (statically make deadlocks structurally impossible) Avoidance (avoid deadlocks by allocating resources carefully) The FOUR Strategies for handling deadlocks:  The FOUR Strategies for handling deadlocks The ostrich algorithm No dealing with the problem at all is as good and as popular in distributed systems as it is in single-processor systems. In distributed systems used for programming, office automation, process control, no system-wide deadlock mechanism is present -- distributed databases will implement their own if they need one. Deadlock detection and recovery is popular because prevention and avoidance are so difficult to implement. Deadlock prevention is possible because of the presence of atomic transactions. We will have two algorithms for this. Deadlock avoidance is never used in distributed system, in fact, it is not even used in single processor systems. The problem is that the banker’s algorithm need to know (in advance) how much of each resource every process will eventually need. This information is rarely, if ever, available. Hence, we will just talk about deadlock detection and deadlock prevention. Distributed Deadlock Detection:  Distributed Deadlock Detection Since preventing and avoiding deadlocks to happen is difficult, researchers works on detecting the occurrence of deadlocks in distributed system. The presence of atomic transaction in some distributed systems makes a major conceptual difference. When a deadlock is detected in a conventional system, we kill one or more processes to break the deadlock --- one or more unhappy users. When deadlock is detected in a system based on atomic transaction, it is resolved by aborting one or more transactions. But transactions have been designed to withstand being aborted. When a transaction is aborted, the system is first restored to the state it had before the transaction began, at which point the transaction can start again. With a bit of luck, it will succeed the second time. Thus the difference is that the consequences of killing off a process are much less severe when transactions are used. Centralized Deadlock Detection:  Centralized Deadlock Detection We use a centralized deadlock detection algorithm and try to imitate the nondistributed algorithm. Each machine maintains the resource graph for its own processes and resources. A centralized coordinator maintain the resource graph for the entire system. When the coordinator detect a cycle, it kills off one process to break the deadlock. In updating the coordinator’s graph, messages have to be passed. Method 1) Whenever an arc is added or deleted from the resource graph, a message have to be sent to the coordinator. Method 2) Periodically, every process can send a list of arcs added and deleted since previous update. Method 3) Coordinator ask for information when it needs it. False Deadlocks:  False Deadlocks One possible way to prevent false deadlock is to use the Lamport’s algorithm to provide global timing for the distributed systems. When the coordinator gets a message that leads to a suspect deadlock: It send everybody a message saying 'I just received a message with a timestamp T which leads to deadlock. If anyone has a message for me with an earlier timestamp, please send it immediately' When every machine has replied, positively or negatively, the coordinator will see that the deadlock has really occurred or not. Distributed Deadlock Detection:  Distributed Deadlock Detection The Chandy-Misra-Haas algorithm: Processes are allowed to request multiple resources at once -- the growing phase of a transaction can be speeded up. The consequence of this change is a process may now wait on two or more resources at the same time. When a process has to wait for some resources, a probe message is generated and sent to the process holding the resources. The message consists of three numbers: the process being blocked, the process sending the message, and the process receiving the message. When message arrived, the recipient checks to see it it itself is waiting for any processes. If so, the message is updated, keeping the first number unchanged, and replaced the second and third field by the corresponding process number. The message is then send to the process holding the needed resources. If a message goes all the way around and comes back to the original sender -- the process that initiate the probe, a cycle exists and the system is deadlocked. Chandy-Misra-Haas Algorithm:  Chandy-Misra-Haas Algorithm There are several ways to break the deadlock: The process that initiates commit suicide -- this is overkilling because several process might initiates a probe and they will all commit suicide in fact only one of them is needed to be killed. Each process append its id onto the probe, when the probe come back, the originator can kill the process which has the highest number by sending him a message. (Hence, even for several probes, they will all choose the same guy) Distributed Deadlock Prevention:  Distributed Deadlock Prevention A method that might work is to order the resources and require processes to acquire them in strictly increasing order. This approach means that a process can never hold a high resource and ask for a low one, thus making cycles impossible. With global timing and transactions in distributed systems, two other methods are possible -- both based on the idea of assigning each transaction a global timestamp at the moment it starts. When one process is about to block waiting for a resource that another process is using, a check is made to see which has a larger timestamp. We can then allow the wait only if the waiting process has a lower timestamp. The timestamp is always increasing if we follow any chain of waiting processes, so cycles are impossible --- we can used decreasing order if we like. It is wiser to give priority to old processes because they have run longer so the system have larger investment on these processes. they are likely to hold more resources. A young process that is killed off will eventually age until it is the oldest one in the system, and that eliminates starvation. Wait-die Vs. Wound-wait:  Wait-die Vs. Wound-wait As we have pointed out before, killing a transaction is relatively harmless, since by definition it can be restarted safely later. Wait-die: If an old process wants a resource held by a young process, the old one will wait. If a young process wants a resource held by an old process, the young process will be killed. Observation: The young process, after being killed, will then start up again, and be killed again. This cycle may go on many times before the old one release the resource. Once we are assuming the existence of transactions, we can do something that had previously been forbidden: take resources away from running processes. When a conflict arises, instead of killing the process making the request, we can kill the resource owner. Without transactions, killing a process might have severe consequences. With transactions, these effects will vanish magically when the transaction dies. Wound-wait: (we allow preemption andamp; ancestor worship) If an old process wants a resource held by a young process, the old one will preempt the young process -- wounded and killed, restarts and wait. If a young process wants a resource held by an old process, the young process will wait.

Related presentations


Other presentations created by WoodRock

VoIP endfassung
18. 06. 2007
0 views

VoIP endfassung

Lone Wolf Presentation
22. 04. 2008
0 views

Lone Wolf Presentation

Guersenfinal
17. 04. 2008
0 views

Guersenfinal

10 bridge
16. 04. 2008
0 views

10 bridge

Reveiwfinal spring
14. 04. 2008
0 views

Reveiwfinal spring

ch03 edit
13. 04. 2008
0 views

ch03 edit

Howcroft CME
10. 04. 2008
0 views

Howcroft CME

ARPA07distribute
09. 04. 2008
0 views

ARPA07distribute

PowerPoint Presentation 2007
07. 04. 2008
0 views

PowerPoint Presentation 2007

Central Asia short
30. 03. 2008
0 views

Central Asia short

APALSAGeneralMeeting
27. 03. 2008
0 views

APALSAGeneralMeeting

elements compounds mixtures
04. 01. 2008
0 views

elements compounds mixtures

Moodle for english teachers
27. 06. 2007
0 views

Moodle for english teachers

YagerDOE2005
17. 09. 2007
0 views

YagerDOE2005

JESSICA2 HKJU Dec 18 2002
17. 09. 2007
0 views

JESSICA2 HKJU Dec 18 2002

wipo smes del 07 www 76775
24. 09. 2007
0 views

wipo smes del 07 www 76775

LDAP Integration
24. 09. 2007
0 views

LDAP Integration

SAR presentation Final
24. 09. 2007
0 views

SAR presentation Final

Politics ml Z
02. 10. 2007
0 views

Politics ml Z

sparkles
04. 10. 2007
0 views

sparkles

Extreme Makeover
17. 09. 2007
0 views

Extreme Makeover

current status ebxml cppa tc
29. 10. 2007
0 views

current status ebxml cppa tc

ast201 2007 lect11
28. 11. 2007
0 views

ast201 2007 lect11

judicial
28. 08. 2007
0 views

judicial

Laptop Security
28. 08. 2007
0 views

Laptop Security

hammer fatriv
28. 08. 2007
0 views

hammer fatriv

Air Monitoring
23. 10. 2007
0 views

Air Monitoring

CONFINED
07. 11. 2007
0 views

CONFINED

Kansas GRB 5
15. 11. 2007
0 views

Kansas GRB 5

ATS
16. 11. 2007
0 views

ATS

Lecture 4 Bioterrorism Dunne
17. 11. 2007
0 views

Lecture 4 Bioterrorism Dunne

wieser sybase
20. 11. 2007
0 views

wieser sybase

rushdie
21. 11. 2007
0 views

rushdie

Napoleon I
26. 11. 2007
0 views

Napoleon I

SonnetOL
11. 08. 2007
0 views

SonnetOL

Steve Lafferty optimized
11. 08. 2007
0 views

Steve Lafferty optimized

Tibetian test 2
11. 08. 2007
0 views

Tibetian test 2

Plumbing an Information Space
02. 01. 2008
0 views

Plumbing an Information Space

Tree of Life 3 11 03
11. 08. 2007
0 views

Tree of Life 3 11 03

savas dangerous offenders
11. 08. 2007
0 views

savas dangerous offenders

Memory Revisited
12. 10. 2007
0 views

Memory Revisited

Dermatology Revision
05. 01. 2008
0 views

Dermatology Revision

FROM THE DISCOVERY OF HELIX
16. 10. 2007
0 views

FROM THE DISCOVERY OF HELIX

504d AACR poster 2005 cfg
30. 10. 2007
0 views

504d AACR poster 2005 cfg

Zeeberg
17. 09. 2007
0 views

Zeeberg

sweep
11. 08. 2007
0 views

sweep

Industrialization Ideology
26. 10. 2007
0 views

Industrialization Ideology

CS438 08 Bridges
28. 12. 2007
0 views

CS438 08 Bridges

sa advocacy
24. 09. 2007
0 views

sa advocacy

CausalArguments
26. 11. 2007
0 views

CausalArguments

JostDeutschAwards
07. 01. 2008
0 views

JostDeutschAwards

Class24ImlicatureExp
19. 02. 2008
0 views

Class24ImlicatureExp

Lars Nord Presentation at HA2005
08. 10. 2007
0 views

Lars Nord Presentation at HA2005

ConEvals
27. 02. 2008
0 views

ConEvals

moodle themes
27. 06. 2007
0 views

moodle themes

Moodle lokalp
27. 06. 2007
0 views

Moodle lokalp

Moodle na UE final
27. 06. 2007
0 views

Moodle na UE final

SIRESENAC06
06. 03. 2008
0 views

SIRESENAC06

Seance 4 Alissa fr
24. 10. 2007
0 views

Seance 4 Alissa fr

SKita gesture
11. 08. 2007
0 views

SKita gesture

8 lessons learnt from nms
18. 03. 2008
0 views

8 lessons learnt from nms

WORKING IN THE EU INSTITUTIONS
20. 03. 2008
0 views

WORKING IN THE EU INSTITUTIONS

semantic web applications
25. 03. 2008
0 views

semantic web applications

FutureofNews
05. 10. 2007
0 views

FutureofNews

sxu 1 05 06
11. 08. 2007
0 views

sxu 1 05 06

canarias
23. 10. 2007
0 views

canarias

Reintegration ProgramFinal
28. 12. 2007
0 views

Reintegration ProgramFinal

G Abaee
22. 11. 2007
0 views

G Abaee

tromsoe
11. 08. 2007
0 views

tromsoe

glazerbusan
12. 10. 2007
0 views

glazerbusan

Stockholm Tutorial June 2001
12. 03. 2008
0 views

Stockholm Tutorial June 2001

TF Rschede
18. 06. 2007
0 views

TF Rschede

telwisa 5
18. 06. 2007
0 views

telwisa 5

Teitler Framework
18. 06. 2007
0 views

Teitler Framework

STRUMENTI tris DI ATTUAZIONE
18. 06. 2007
0 views

STRUMENTI tris DI ATTUAZIONE

strategic plan
18. 06. 2007
0 views

strategic plan

STEROIDS
18. 06. 2007
0 views

STEROIDS

Slide musso taranto
18. 06. 2007
0 views

Slide musso taranto

V 005 Gierke
18. 06. 2007
0 views

V 005 Gierke

Vorlesung BGB AT 1
18. 06. 2007
0 views

Vorlesung BGB AT 1

violenza
18. 06. 2007
0 views

violenza

Varma
18. 06. 2007
0 views

Varma

usenix
18. 06. 2007
0 views

usenix

unter Mitglieder wenn das geht
18. 06. 2007
0 views

unter Mitglieder wenn das geht

Unterrichtsbeobachtu ng
18. 06. 2007
0 views

Unterrichtsbeobachtu ng

Traechtigkeit
18. 06. 2007
0 views

Traechtigkeit

todoslossantosanual
02. 11. 2007
0 views

todoslossantosanual

vortrag we mu 220602
18. 06. 2007
0 views

vortrag we mu 220602

SOR Legal Updates 2006 141962 7
11. 08. 2007
0 views

SOR Legal Updates 2006 141962 7

Bigwood 1
13. 03. 2008
0 views

Bigwood 1

lrec metadata
14. 11. 2007
0 views

lrec metadata

termininfo D2D Konferenz2006
18. 06. 2007
0 views

termininfo D2D Konferenz2006

typologie
18. 06. 2007
0 views

typologie

antalya
03. 09. 2007
0 views

antalya

sermonpp thy will be done
11. 08. 2007
0 views

sermonpp thy will be done

gabriel
24. 09. 2007
0 views

gabriel

tack2
24. 09. 2007
0 views

tack2

VORTRAG BW
18. 06. 2007
0 views

VORTRAG BW

The Perils of Childhood Obesity
11. 08. 2007
0 views

The Perils of Childhood Obesity

GT TurkeyCountryPresent ation
23. 10. 2007
0 views

GT TurkeyCountryPresent ation

Open Everything 3 9
01. 10. 2007
0 views

Open Everything 3 9

arnaud
28. 09. 2007
0 views

arnaud

file1180026507
22. 10. 2007
0 views

file1180026507

yasinsky
24. 09. 2007
0 views

yasinsky

healthy body esteem
03. 10. 2007
0 views

healthy body esteem

moodle presentation epfl final
27. 06. 2007
0 views

moodle presentation epfl final

37 Yale SA Program Overview 07
24. 09. 2007
0 views

37 Yale SA Program Overview 07

song slides
11. 08. 2007
0 views

song slides

Stuttgart
18. 06. 2007
0 views

Stuttgart

site wsa
29. 02. 2008
0 views

site wsa

pearson
24. 09. 2007
0 views

pearson

09 s4 fr
11. 03. 2008
0 views

09 s4 fr

EPS
17. 10. 2007
0 views

EPS

OARS CRJ 2006
24. 09. 2007
0 views

OARS CRJ 2006

7Paul Hopkin
11. 12. 2007
0 views

7Paul Hopkin

Sofia 29 09 30 02
23. 11. 2007
0 views

Sofia 29 09 30 02

CSI NetSec2004
29. 10. 2007
0 views

CSI NetSec2004

santTOPch11
11. 08. 2007
0 views

santTOPch11

HumanCapitalFINAL
24. 09. 2007
0 views

HumanCapitalFINAL

Carmelo Polino
22. 10. 2007
0 views

Carmelo Polino

Poeplau ECLOUD07
03. 01. 2008
0 views

Poeplau ECLOUD07

peytonap
17. 09. 2007
0 views

peytonap

BUTE 2005feb Milano COST291
16. 10. 2007
0 views

BUTE 2005feb Milano COST291