Page 137 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes Processes PI, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is
held by process P3. Process P3, on the other hand, is waiting for either process PI or process P2
to release resource R2. In addition, process PI is waiting for process P2 to release resource R1.
Now consider the resource-allocation graph in Figure 4.11. In this example, we also have a cycle.
However, there is no deadlock. Observe that process P4 may release its instance of resource
type R2. That resource can then be allocated to P3, breaking the cycle.
P → R → P → R → P 1
1
1
2
3
In summary, if a resource-allocation graph does not have a cycle, then the system is not in a
deadlock state. On the other hand, if there is a cycle, then the system may or may not be in a
deadlock state. This observation is important when we deal with the deadlock problem.

4.6.4 Methods for Handling Deadlocks

Principally, we can deal with the deadlock problem in one of three ways. We can use a protocol
to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state. We
can allow the system to enter a deadlock state, detect it, and recover.

We can ignore the problem altogether, and pretend that deadlocks never occur in the system.
This solution is used by most operating systems, including UNIX. We shall elaborate briefly on
each method. Then, we shall present detailed algorithms. To ensure that deadlocks never occur,
the system can use either a deadlockprevention or a deadlock-avoidance scheme.

4.6.5 Deadlock Prevention

Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions
cannot hold. These methods prevent deadlocks by constraining how requests for resources can
be made.

4.6.6 Deadlock Avoidance
Deadlock avoidance, on the other hand, requires that the operating system be given in advance
additional information concerning which resources a process will request and use during its
lifetime. With this additional knowledge, we can decide for each request whether or not the
process should wait. To decide whether the current request can be satisfied or must be delayed,
the system must consider the resources currently available, the resources currently allocated to
each process, and the future requests and releases of each process. If a system does not employ
either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may
occur. In this environment, the system can provide an algorithm that examines the state of the
system to determine whether a deadlock has occurred, and an algorithm to recover from the
deadlock (if a deadlock has indeed occurred). We discuss these issues in if a system does not
ensure that a deadlock will never occur, and also does not provide a mechanism for deadlock
detection and recovery then we may arrive at a situation where the system is in a deadlock
state yet has no way of recognizing what has happened. In this case, the undetected deadlock
will result in the deterioration of the system performance, because resources are being held by

130 LOVELY PROFESSIONAL UNIVERSITY