Scribd
Upload
54 views3 pages

Lec09 PDF

This document discusses deadlock in operating systems. It defines deadlock as a situation where a collection of processes are all waiting for resources held by each other in a cyclic manner, preventing any progress. There are four conditions required for deadlock: mutual exclusion of resources, no preemption of allocated resources, processes holding resources while waiting for additional resources (the hold and wait condition), and a wait-for graph forming a cycle between processes. Common approaches to dealing with deadlock include prevention, avoidance through algorithms like the Banker's Algorithm, and detection and resolution, though prevention and avoidance strategies can reduce resource utilization efficiency.

Uploaded by

Hummels1000
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
54 views3 pages

Lec09 PDF

This document discusses deadlock in operating systems. It defines deadlock as a situation where a collection of processes are all waiting for resources held by each other in a cyclic manner, preventing any progress. There are four conditions required for deadlock: mutual exclusion of resources, no preemption of allocated resources, processes holding resources while waiting for additional resources (the hold and wait condition), and a wait-for graph forming a cycle between processes. Common approaches to dealing with deadlock include prevention, avoidance through algorithms like the Banker's Algorithm, and detection and resolution, though prevention and avoidance strategies can reduce resource utilization efficiency.

Uploaded by

Hummels1000
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

CS 414 : Operating Systems

UNIVERSITY OF VIRGINIA
Department of Computer Science

Spring 2008

Topic 9: Deadlock

g Readings for this topic: Chapter 7

g Deadlock is one area where there is a lot of theory, but most of them are ignored in practice.

Why?

g Simple approaches vs complex glorious approaches

g Deadlock example: semaphores.

g Define deadlock: a situation where each of a collection of processes is waiting for something

from other processes in the collection. Since all are waiting, none can provide any of the

things being waited for.

g How do you know there’s a deadlock?

g Facts about deadlock:

g The semaphore example is a relatively simple-minded case. Things may be much more

complicated.

g A deadlock can happen with any kind of non-preemptible resources.

g In general, don’t know the resource needs in advance. If only we could predict the fu-

ture....

g Deadlock can occur over separate resources, as in semaphore example, or over pieces of

a single resource, as in memory, or even over totally separate classes of resources (tape

drives and memory).

g Whenever there is waiting, there’s potential for deadlock. Hard for OS to control.

— 9.1 —
g Four conditions for deadlock:

g Mutual exclusion: resources cannot be shared.

g No preemption. once given, a resource cannot be taken away.

g Hold and wait: processes don’t ask for resources all at once (i.e., multiple independent

requests).

g Circular wait: circularity in the graph of who has what and who wants what.

g Solutions to the deadlock problem fall into three general categories:

g Detection and resolution: determine when the system is deadlocked and then take dras-

tic action. Requires termination of one or more processes in order to release their

resources. Usually not very practical.

g Prevention: organize the system so that it is impossible for deadlock ever to occur.

May lead to less efficient resource utilization in order to guarantee no deadlocks.

g Avoidance: divide into safe and unsafe state (Banker’s algorithm). Each process de-

clare max resource requirement for each resource type, and the system maintains neces-

sary information to avoid unsafe state.

g Deadlock prevention: must find a way to eliminate one of the four necessary conditions for

deadlock:

g Don’t allow exclusive access. This is probably not reasonable for many applications.

g Create enough resources so that there’s always plenty for all.

g Don’t allow waiting. (phone company solution) This punts the problem back to the user.

g Allow preemption. Preempt student’s thesis disk space?

g Attack hold & wait: Make process ask for everything at once. Either get them all or wait for

— 9.2 —
them all. Tricky to implement: must be able to wait on many things without locking anything.

Problems?

g Attack circular wait: Define an ordering among resources and enforce it. Make ordered or

hierarchical requests (e.g., ask for all S’s, then all T’s, etc.). All processes must follow the

same ordering scheme. Problem?

g Integrated approach to deadlock: combine basic approaches, since none of the basic ap-

proaches alone is appropriate for entire spectrum of resource allocation in OS.

g Partition resources into classes that are hierarchically ordered. -> resource ordering

g Within each class, use one of the basic approaches.

g In general, prevention of deadlock is expensive and/or inefficient. Detection is also expensive

and recovery is difficult (what if process has things in a weird state?).

g Is it possible to have a deadlock involving only 1 process?

g Does the existence of a cycle in the wait-for graph guarantee a deadlock?

g Is starvation different from deadlock?

— 9.3 —

You might also like