Page 140 - DCAP103_Principle of operating system

Unit 4: Process Management-III

Let R = {XI, R2, ..., R,) be the set of resource types. We assign to each resource type a unique Notes
integer number, which allows us to compare two resources and to determine whether one
precedes another in our ordering. Formally, we define a one-to-one function F: R + N, where N
is the set of natural numbers. For example, if the set of resource types R includes tape drives,
disk drives, and printers, then the function F might be defined as follows:
F(tape drive) = 1,

F(disk drive) = 5,
F(printer) = 12.
We can now consider the following protocol to prevent deadlocks. Each process can request
resources only in an increasing order of enumeration. That is, a process can initially request any
number of instances of a resource type, say Xi. After that, the process can request instances of
resource type Ri if and only if F(Rj) > F(Ri). If several instances of the same resource type are
needed, a single request for all of them must be issued. For example, using the function defined
previously, a process that wants to use the tape drive and printer at the same time must first
request the tape drive and then request the printer. Alternatively, we can require that, whenever
a process requests an instance of resource type Rj, it has released any resources Ri such that
F(Ri) 2 F(Rj). If these two protocols are used, then the circular-wait condition cannot hold. We
can demonstrate this fact by assuming that a circular wait exists (proof by contradiction). Let
the set of processes involved in the circular wait be {Po, PI, ..., P,), where Pi is waiting for a
resource Xi, which is held by process Pi+l. (Modulo arithmetic is used on the indexes, so that
P, is waiting for a resource R, held by Po.) Then, since process Pi+l is holding resource Ri while
requesting resource Ri+l, we must have F(Ri) < F(Ri+1), for all i. But this condition means that
F(Ro) < F(R1) < ... < F(R,) < F(Ro). By transitivity, F(Ro) < F(Ro), which is impossible. Therefore,
there can be no circular wait.

The function F should be defined according to the normal order of usage of the
resources in a system. For example, since the tape drive is usually needed before
the printer, it would be reasonable to define F(tape drive) < F(printer).
4.6.11 Safe State

A state is safe if the system can allocate resources to each process (up to its maximum) in some
order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a
safe sequence. A sequence of processes <PI, P2, ..., P,> is a safe sequence for the current allocation
state if, for each Pi, the resources that Pi can still request can be satisfied by the currently available
resources plus the resources held by all the Pi, with j < i. In this situation, if the resources that
process Pi needs are not immediately available, then Pi can wait until all Pi have finished. When
they have finished, Pi can obtain all of its needed resources, complete its designated task, return
its allocated resources, and terminate. When Pi terminates, Pi+l can obtain its needed resources,
and so on. If no such sequence exists, then the system state is said to be unsafe. A safe state is
not a deadlock state. Conversely, a deadlock state is an unsafe state. Not all unsafe states are
deadlocks. An unsafe state may lead to a deadlock. As long as the state is safe, the operating
system can avoid unsafe (and deadlock) states. In an unsafe state, the operating system cannot
prevent processes from requesting resources such that a deadlock occurs. The behaviour of the
processes controls unsafe states. To illustrate, we consider a system with 12 magnetic tape drives
and 3 processes—Po, PI, and P2. Process Po requires 10 tape drives, process PI may need as
many as 4, and process P2 may need up to 9 tape drives. Suppose that, at time t0, process Po is
holding 5 tape drives, process PI is holding 2, and process PZ is holding 2 tape drives. (Thus,
there are 3 free tape drives.)

LOVELY PROFESSIONAL UNIVERSITY 133