05-deadlock

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

PowerPoint Presentation:

A Seminar ON DEADLOCK CS-508 SUBMITTED TO RAJIV GANDHI PROUDYOGIKI VISHWAVIDYALAYA (M.P) IN PARTIAL FULFILLMENT OF THE REQUIREMENT FOR DEGREE Of BACHELOR OF ENGINEERING IN(5 TH SEM.) COMPUTER SCIENCE 2010 Submitted to Submitted By Miss Rekha Agrawal Madhuri Rajawat Lecturer of cse/IT 0914cs081063

DEADLOCK:

DEADLOCK 2

Contents:

Contents Deadlock Description Real life Example Necessary Deadlock Conditions Resource Allocation Graph Deadlock Handling Deadlock and Starvation with Semaphores. 3

Deadlock:

Deadlock Simplest example: Two processes require two resources to complete (and release the resources) There are only two instances of these resources If they acquire one resource each, they block indefinitely waiting for each other to release the other resource => DEADLOCK , one of the biggest problems in multiprogramming. 4 R1 P1 P2 R2

Necessary Deadlock Conditions:

Necessary Deadlock Conditions ME : at least one process exclusively uses a resource Hold and wait : a process possesses at least one resources and requires more, which are held by others No preemption : resources are released only in voluntary manner by processes holding them Circular wait : P 1  P 2  P 3  …  P N  P 1 5

Resource-Allocation Graph:

Resource-Allocation Graph An easy way to illustrate resource allocation and visually detect the deadlock situation(s) Example: N+1 resources N processes Every process needs 2 resources Upon acquiring 2 resources, a process releases them Is there a deadlock? 6 • • • • P1 P2 P3 ?

REAL LIFE Examples:

REAL LIFE Examples bridge traffic can only be in one direction. Each entrance of the bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (resource preemption). 7

Handling Deadlocks:

Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection and Recovery 8

Deadlock Prevention:

Deadlock Prevention Recall necessarily deadlock conditions Deadlock prevention algorithms assure at least one these conditions do not hold, thus preventing occurrence of the deadlock. Possible Disadvantages: Low device utilization Reduced system’s throughput [1] p. 250 9

Deadlock avoidance:

Deadlock avoidance Do not grant a resource request if this allocation have the potential to lead to a deadlock. It is implemented by having the resource allocator examine the effect of granting a particular request. A state is safe,if the system can allocate resources to each process in some order and avoid deadlock. 10

Deadlock Detection and Recovery:

Deadlock Detection and Recovery Instead of preventing or avoiding deadlocks we allow them to happen and also provide mechanisms to recover. Problems: How often do we run detection algorithms? How do we recover? What is the cost of detection and recovery? Always grant resource request when possible. Periodically check for deadlocks. If a deadlock exists, recover from it. 11

Deadlocks and Starvation with Semaphores :

Deadlocks and Starvation with Semaphores Semaphores act like resources in this case, which can be acquired and (never) released. One example as book suggests: [1] P. 204 12 P1 wait(sem1) wait(sem2) … signal(sem1) signal(sem2) P2 wait(sem2) wait(sem1) … signal(sem2) signal(sem1)

Deadlocks and Starvation with Semaphores (2):

Deadlocks and Starvation with Semaphores (2) Starvation , or indefinite blocking , is when a process is waiting on a semaphore where nobody is ever going to release it. Another example of both deadlock and starvation: 13 process A { process B { wait(mutex) wait(mutex) ... ... wait(synch) signal(synch) ... ... wait(synch) ... ... ... signal(mutex) signal (mutex) } } For this case assume: mutex = 1 synch = 0 Try starting processes in any order and see where they block.

THANK YOU:

THANK YOU 14

authorStream Live Help