Rashtreeya Sikshana Samithi Trust RV Institute of

Technology and Management ®

(Affiliated to VTU, Belagavi)

JP Nagar, Bengaluru – 560076

Department of Computer Science and Engineering

Course Name: Operating Systems Course

Code: BCS303
III Semester
2022 Scheme

III Semester, OPERATING SYSTEMS- BCS303 1

III Semester, OPERATING SYSTEMS- BCS303 2
 RV Institute of Technology & Management®

OPERATING Module

MODULE III
3.1 Process Synchronization

3.1.1 Background

Since processes frequently needs to communicate with other processes therefore, there is a
need for a well- structured communication, without using interrupts, among processes.
A situation where several processes access and manipulate the same data concurrently and
the outcome of the execution depends on the particular order in which the access takes place,
is called a race condition.
To guard against the race condition, ensure only one process at a time can be manipulating
the variable or data. To make such a guarantee process need to be synchronized in some way.

3.1.2 The Critical-Section Problem

Consider a system consisting of n processes {P0, P1, ..., Pn−1}. Each process has a
segment of code, called a critical section, in which the process may be changing common
variables, updating a table, writing a file, and so on. when one process is executing in its
critical section, no other process is allowed to execute in its critical section.
The critical-section problem is to design a protocol that the processes can use to cooperate.
Each process must request permission to enter its critical section. The section of code
implementing this request is the entry section.
The critical section may be followed by an exit section. The remaining code is the
remainder section. The general structure of a typical process Pi is shown in Fig. 2.14
A solution to the critical-section problem must satisfy the following three requirements:
Mutual exclusion. If process Pi is executing in its critical section, then no other processes
can be executing in their critical sections.
Progress. If no process is executing in its critical section and some processes wish to enter
their critical sections, then only those processes that are not executing in their remainder
sections can participate in deciding which will enter its critical section next, and this selection
cannot be postponed indefinitely.

Bounded waiting. There exists a bound, or limit, on the number of times that other
processes are allowed to enter their critical sections after a process has made a request to enter
its critical section and before that request is granted.

Fig. 2.14 General structure of a typical process P,.

Two general approaches are used to handle critical sections in operating systems:

Preemptive kernels: A preemptive kernel allows a process to be preempted while it is

running in kernel mode.

Non-preemptive kernels: A non-preemptive kernel does not allow a process running in

kernel mode to be preempted; a kernel-mode process will run until it exits kernel mode,

III Semester, OPERATING SYSTEMS- BCS303 3

 RV Institute of Technology & Management®

OPERATING Module
blocks, or voluntarily yields control of the CPU.

3.1.3 Peterson’s Solution

A classic software-based solution to the critical-section problem known as Peterson’s

solution. It addresses the requirements of mutual exclusion, progress, and bounded
waiting. It Is two process solution. Assume that the LOAD and STORE instructions are
atomic; that is, cannot be interrupted.

The two processes share two variables:

int turn; Boolean
flag [2];

The variable turn indicates whose turn it is to enter the critical section. The flag array is
used to indicate if a process is ready to enter the critical section. flag[i] = true implies that
process Pi is ready.

The structure of process Pi in Peterson’s solution: It

proves that Mutual exclusion is preserved
[Link] Progress requirement is satisfied
[Link] Bounded-waiting requirement is met

3.1.4 Synchronization Hardware

Software-based solutions such as Peterson’s are not guaranteed to work on modern

computer architectures. Simple hardware instructions can be used effectively in solving
the critical- section problem. These solutions are based on the locking — that is,
protecting critical regions through the use of locks.

Solution to Critical Section problem using locks

Modern machines provide special atomic hardware instructions Atomic = non-

interruptable

Fig. 2.16 Mutual-exclusion implementation with TestAndSet ().

3.2 Semaphores

The hardware-based solutions to the critical-section problem are complicated as well as

generally inaccessible to application programmers. So operating-systems designers build
software tools to solve the critical-section problem, and this synchronization tool called
as Semaphore. Semaphore S is an integer variable.

Two standard operations modify S: wait() and signal(). Originally called P() and V().Can
only be accessed via two indivisible (atomic) operations.

Must guarantee that no two processes can execute wait () and signal () on the same
semaphore at the same time.

Usage:
Semaphore classified into:
Counting semaphore: Value can range over an unrestricted domain.

Binary semaphore (Mutex locks): Value can range only between from 0 & 1. It provides
mutual exclusion.
Consider 2 concurrently running processes:

S1;
III Semester, OPERATING SYSTEMS- BCS303 4
 RV Institute of Technology & Management®

OPERATING Module
signal(synch);
In process P1, and the statements wait(synch); S2;

Because synch is initialized to 0, P2 will execute S2 only after P1 has invoked

signal(synch), which is after statement S1 has been executed.

Implementation:

The disadvantage of the semaphore is busy waiting i.e While a process is in critical
section, any other process that tries to enter its critical section must loop continuously in
the entry code. Busy waiting wastes CPU cycles that some other process might be able to
use productively. This type of semaphore is also called a spin lock because the process
spins while waiting for the lock.

Solution for Busy Waiting problem:

Modify the definition of the wait() and signal()operations as follows: When a process
executes the wait() operation and finds that the semaphore value is not positive, it must
wait. Rather than engaging in busy waiting, the process can block itself. The block
operation places a process into a waiting queue associated with the semaphore, and the
state of the process is switched to the waiting state. Then control is transferred to the CPU
scheduler, which selects another process to execute.

A process that is blocked, waiting on a semaphore S, should be restarted when some other
process executes a signal() operation. The process is restarted by a wakeup() operation,
which

changes the process from the waiting state to the ready state. The process is then placed in
the ready queue.

To implement semaphores under this definition, define a semaphore as follows:

typedef struct {int value;

struct process *list;
} semaphore;

Each semaphore has an integer value and a list of processes list. When a process must
wait on a semaphore, it is added to the list of processes. A signal () operation removes one
process from the list of waiting processes and awakens that process. Now, the wait ()
semaphore operation can be defined as:

wait (semaphore *S) {

S->value--;
if (S->value < 0) {
add this process to S->list; block ();
}
}

and the signal () semaphore operation can be defined as

signal (semaphore *S) {

S->value++;
if (S->value <= 0) {
remove a process P from S->list; wakeup(P);
}

The block () operation suspends the process that invokes it. The wakeup(P) operation
resumes the execution of a blocked process P.

III Semester, OPERATING SYSTEMS- BCS303 5

 RV Institute of Technology & Management®

OPERATING Module
3.2.1 Deadlocks and Starvation

The implementation of a semaphore with a waiting queue may result in a situation where
two or more processes are waiting indefinitely for an event that can be caused by only one
of the waiting processes, these processes are said to be deadlocked.

Consider below example: a system consisting of two processes, P0 and P1, each accessing
two semaphores, S and Q, set to the value 1:
Suppose that P0 executes wait(S) and then P1 executes wait(Q). When P0 executes
wait(Q), it must wait until P1 executes signal(Q). Similarly, when P1 executes wait(S), it
must wait until P0 executes signal(S). Since these signal () operations cannot be executed,
P0 and P1 are deadlocked.

Another problem related to deadlocks is indefinite blocking, or starvation, a situation in

which processes wait indefinitely within the semaphore. Indefinite blocking may occur if
we add and remove processes from the list associated with a semaphore in LIFO (last-in,
first-out) order.

3.3 Classic Problems of Synchronization

3.3.1 The Bounded-Buffer Problem:

N buffers, each can hold one item Semaphore mutex initialized to the value 1
Semaphore full initialized to the value 0
Semaphore empty initialized to the value N Code for producer is given below
(Fig. 2.17):

Fig. 2.17 The structure of the producer process.

Code for consumer is given below (fig. 2.18):

III Semester, OPERATING SYSTEMS- BCS303 6

 RV Institute of Technology & Management®

OPERATING Module
Fig. 2.18 The structure of the consumer process.

3.3.2 The Readers–Writers Problem

A data set is shared among a number of concurrent processes Readers – only read the data
set; they do not perform any updates Writers– can both read and write

Problem – allow multiple readers to read at the same time

Only one single writer can access the shared data at the same time
Several variations of how readers and writers are treated – all involve priorities.

First variation – no reader kept waiting unless writer has permission to use shared object

In the solution to the first readers-writers problem, the reader processes share the following
data structures:

semaphore mutex, wrt; int readcount;

count is initialized to 0. The semaphore wrt is common to both reader and writer processes. The mutex semaphore is used to e

ses are currently reading the object. The semaphore wrt functions as a mutual-exclusion semaphore for the writers. It is also u

Fig. 2.19 The structure of a writer process

The code for a writer process is shown in Fig. 2.19. The code for a reader process is shown in Fig. 2.20.

III Semester, OPERATING SYSTEMS- BCS303 7

 RV Institute of Technology & Management®

OPERATING Module

Fig. 2.20 The structure of a reader process.

III Semester, OPERATING SYSTEMS- BCS303 8

 RV Institute of Technology & Management®

OPERATING Module

Second variation- Once writer is ready, it performs the operation.

3.3.3 Shared Data

he readers-writers problem and its solutions has been generalized to provide reader- writer
locks on some systems. Acquiring a reader-writer lock requires specifying the mode of the
lock: either read or write access. When a process only wishes to read shared data, it
requests the reader-writer lock in read mode; a process wishing to modify the shared data
must request the lock in write mode.

Multiple processes are permitted to concurrently acquire a reader-writer lock in read

mode; only one process may acquire the lock for writing as exclusive access is required
for writers. Reader-writer locks are most useful in the following situations:

• In applications where it is easy to identify which processes only read shared data and which
threads only write shared data.
• In applications that have more readers than writers.

This is because reader-writer locks generally require more overhead to establish than
semaphores or mutual exclusion locks, and the overhead for setting up a reader- writer
lock is compensated by the increased concurrency of allowing multiple readers.

3.3.4 Dining-Philosophers Problem

Consider five philosophers who spend their lives thinking and eating. The philosophers
share a circular table surrounded by five chairs, each belonging to one philosopher. In the
center of the table is a bowl of rice, and the table is laid with five single chopsticks (Fig.
2.21).

A philosopher gets hungry and tries to pick up the two chopsticks that are closest to her
(the chopsticks that are between her and her left and right neighbors). A philosopher may
pick up only one chopstick at a time. When a hungry philosopher has both her chopsticks
at the same time, she eats without releasing the chopsticks. When she is finished eating,
she puts down both chopsticks and starts thinking again.

It is a simple representation of the need to allocate several resources among several

processes in a deadlock-free and starvation-free manner.

Solution: One simple solution is to represent each chopstick with a semaphore. A

philosopher tries to grab a chopstick by executing a wait () operation on that semaphore.
She releases her chopsticks by executing the signal () operation on the appropriate
semaphores. Thus, the shared data are

semaphore chopstick [5];

III Semester, OPERATING SYSTEMS- BCS303 9

 RV Institute of Technology & Management®

OPERATING Module

where all the elements of chopstick are initialized to 1.

Several possible remedies to the deadlock problem are replaced by:

1. Allow at most four philosophers to be sitting simultaneously at the table.

2. Allow a philosopher to pick up her chopsticks only if both chopsticks are available.

Fig. 2.21 The situation of the dining

The structure of philosopher i is shown in Fig.

Fig. 2.22 The structure of philosopher

i.

Although this solution guarantees that no two neighbors are eating

simultaneously, it nevertheless must be rejected because it could create a
deadlock. Suppose that all five philosophers become hungry simultaneously and
each grabs her left chopstick. All the elements of chopstick will now be equal to

III Semester, OPERATING SYSTEMS- BCS303 10

 RV Institute of Technology &
Management®

OPERATING SYSTEMS Module

3. Use an asymmetric solution—that is, an odd-numbered philosopher picks up first her

left chopstick and then her right chopstick, whereas an even numbered philosopher
picks up her right chopstick and then her left chopstick.

3.4 Monitors

Incorrect use of semaphore operations:

Suppose that a process interchanges the order in which the wait () and signal ()
operations on the semaphore mutex are executed, resulting in the following execution:

signal(mutex);
...
critical section
...
wait(mutex);
Suppose that a process replaces signal(mutex) with wait(mutex). That is, it executes

wait(mutex);
...
critical section
...
wait(mutex);

In this case, a deadlock will occur.

Suppose that a process omits the wait(mutex), or the signal(mutex), or both. In this
case, either mutual exclusion is violated or a deadlock will occur.

Solution:

Monitor: An abstract data type—or ADT—encapsulates data with a set of functions to

operate on that data that are independent of any specific implementation of the ADT.

A monitor type is an ADT that includes a set of programmers defined operations that are
provided with mutual exclusion within the monitor. The monitor type also declares the
variables whose values define the state of an instance of that type, along with the bodies of
functions that operate on those variables. The monitor construct ensures that only one
process at a time is active within the monitor.
The syntax of a monitor type is shown in Fig.2.23

To have a powerful Synchronization schemes a condition construct is added to the

Monitor. So, synchronization scheme can be defined with one or more variables of type
condition.
condition x, y;

III SEM OPERATING SYSTEM (BCS303) 11

 RV Institute of Technology &
Management®

OPERATING SYSTEMS Module

Fig. 2.23 Schematic view of a monitor

The only operations that can be invoked on a condition variable are wait () and signal ().
The operation [Link](); means that the process invoking this operation is suspended until
another process invokes [Link]();

The [Link]() operation resumes exactly one suspended process. If no process is

suspended, then the signal () operation has no effect; that is, the state of x is the same as if
the operation had never been executed. Contrast this operation with the signal () operation
associated with semaphores, which always affects the state of the semaphore.

Fig. 2.24 Monitor with condition variables.

III SEM OPERATING SYSTEM (BCS303) 12

 RV Institute of Technology &
Management®

OPERATING SYSTEMS Module

3.4.1 Dining-Philosophers Solution Using Monitors

A deadlock-free solution to the dining-philosophers problem using monitor concepts. This

solution imposes the restriction that a philosopher may pick up her chopsticks only if both
of them are available.

Consider following data structure:

enum {THINKING, HUNGRY, EATING} state[5];

Philosopher i can set the variable state[i] = EATING only if her two neighbors are not eating: (state[(i+4) % 5

And also declare:

Condition self[5];

This allows philosopher i to delay herself when she is hungry but is unable to obtain the chopsticks she needs.
A monitor solution to the dining-philosopher problem (Fig. 2.25):

Fig. 2.25 A monitor solution to the dining-philosopher problem

III SEM OPERATING SYSTEM (BCS303) 13

 RV Institute of Technology &
Management®
OPERATING SYSTEMS Module III

3.4.2 Implementing a Monitor Using Semaphores

For each monitor, a semaphore mutex (initialized to 1) is provided. A process must execute
wait(mutex) before entering the monitor and must execute signal(mutex) after leaving the monitor.

Since a signaling process must wait until the resumed process either leaves or waits, an additional
semaphore, next, is introduced, initialized to 0. The signaling processes can use next to suspend
themselves. An integer variable next count is also provided to count the number of processes suspended
on next. Thus, each external function F is replaced by

Mutual exclusion within a monitor is ensured.

For each condition x, we introduce a semaphore x sem and an integer variable x count, both initialized
to 0. The operation x. wait() can now be implemented as

x_count++;
if (next_count > 0) signal(next);
else signal(mutex);
wait(x_sem); x_count--; The operation

[Link]() can be implemented as

3.4.3 Resuming Processes within a Monitor

If several processes are suspended on condition x, and an [Link]() operation is executed by some
process, then to determine which of the suspended processes should be resumed next, one simple
solution is to use a first-come, first-served (FCFS) ordering, so that the process that has been waiting
the longest is resumed

first. For this purpose, the conditional-wait construct can be used. This construct has the form
[Link](c);where c is an integer expression that is evaluated when the wait() operation is executed.
The value of c, which is called a priority number, is then stored with the name of the process that
is suspended. When [Link]() is executed, the process with the smallest priority number is

III Semester, Operating Systems-BCS303 Page 14 of 33

 RV Institute of Technology &
Management®
resumed next.

1. A process might access a resource without first gaining access permission to the resource.
2. A process might never release a resource once it has been granted access to the resource.
3. A process might attempt to release a resource that it never requested.
4. A process might request the same resource twice (without first releasing the resource)

3.5Dead Locks

In a multiprogramming environment, several processes may compete for a finite number of

resources. A process requests resources; and if the resources are not available at that time, the
process enters a waiting state. Sometimes, a waiting process is never again able to change state,
because the resources it has requested are held by other waiting processes. This situation is called a
deadlock.

3.5.1 System Model

For the purposes of deadlock discussion, a system can be modeled as a collection of limited
resources, which can be partitioned into different categories, to be allocated to a number of processes,
each having different needs.

Resource categories may include memory, printers, CPUs, open files, tape drives, CD- ROMS, etc.

III Semester, Operating Systems-BCS303 Page 15 of 33

 RV Institute of Technology &
Management®
By definition, all the resources within a category are equivalent, and a request of this category can be
equally satisfied by any one of the resources in that category. If this is notthe case (
i.e. if there is some difference between the resources within a category ), then that category needs to
be further divided into separate categories. For example, "printers" may need to be separated into
"laser printers" and "color inkjet printers".

Some categories may have a single resource.

In normal operation a process must request a resource before using it, and release it when it is done,
in the following sequence:

1. Request - If the request cannot be immediately granted, then the process must wait until the
resource(s) it needs become available. Example: system calls open( ), malloc( ), new(
), and request( ).

2. Use - The process uses the resource.

Example: prints to the printer or reads from the file.

3. Release - The process relinquishes the resource. so that it becomes available for other
processes.

Example: close(), free( ), delete( ), and release( ).

for all kernel-managed resources, the kernel keeps track of what resources are free and which are
allocated, to which process they are allocated, and a queue of processes waiting for this resource to
become available. Application-managed resources can be controlled using mutexes or wait( ) and
signal( ) calls, ( i.e. binary or counting semaphores. )

A set of processes is deadlocked when every process in the set is waiting for a resource that is
currently allocated to another process in the set ( and which can only be released when that other
waiting process makes progress. )

3.6 Deadlock Characterization

3.6.1 Necessary Conditions:

There are four conditions that are necessary to achieve deadlock:

 Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any
other process requests this resource, then that process must wait for the resource to be
released.

 Hold and Wait - A process must be simultaneously holding at least one resource and
waiting for at least one resource that is currently being held by some other process.

 No preemption - Once a process is holding a resource ( i.e. once its request has been
granted ), then that resource cannot be taken away from that process until the process
voluntarily releases it.

III Semester, Operating Systems-BCS303 Page 16 of 33

 RV Institute of Technology &
Management®
 Circular Wait - A set of processes { P0, P1, P2, . . ., PN } must exist such that every
P[i ] is waiting for P[ ( i + 1 ) % ( N + 1 ) ]. ( Note that this condition implies the hold-
and- wait condition, but it is easier to deal with the conditions if the four are
considered separately.

3.6.2 Resource-Allocation Graph

In some cases deadlocks can be understood more clearly through the use of Resource- Allocation
Graphs, having the following properties:

*A set of resource categories, { R1, R2, R3, . . ., RN }, which appear as square nodes on the graph.
Dots inside the resource nodes indicate specific instances of the resource. ( E.g. two dots might
represent two laser printers. )

*A set of processes, { P1, P2, P3, . . ., PN }

*Request Edges - A set of directed arcs from Pi to Rj, indicating that process Pi has requested Rj,
and is currently waiting for that resource to become available.

*Assignment Edges - A set of directed arcs from Rj to Pi indicating that resource Rj has been
allocated to process Pi, and that Pi is currently holding resource Rj.

Note that a request edge can be converted into an assignment edge by reversing the direction of the
arc when the request is granted. (However, note also that request edges point to the category box,
whereas assignment edges emanate from a particular instance dot within the box.)

III Semester, Operating Systems-BCS303 Page 17 of 33

 RV Institute of Technology &
Management®
Fig. 3.1 Resource-allocation graph.
*If a resource-allocation graph contains no cycles, then the system is not deadlocked. (When looking for
cycles, remember that these are directed graphs.) See the example in Fig. 3.1 above.
*If a resource-allocation graph does contain cycles AND each resource category contains only a single
instance, then a deadlock exists.
*If a resource category contains more than one instance, then the presence of a cycle in the
resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one.
Consider, for example, Fig. 3.2 and 3.3 below:

Fig. 3.3 Resource-allocation graph with a deadlock

Fig. 3.4 Resource-allocation graph with a cycle but no deadlock.

3.7 Methods for Handling Deadlocks

Generally speaking there are three ways of handling deadlocks:

III Semester, Operating Systems-BCS303 Page 18 of 33

 RV Institute of Technology &
Management®
Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.

Deadlock detection and recovery - Abort a process or preempt some resources when
deadlocks are detected.
Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them
happen and reboot as necessary than to incur the constant overhead and system performance penalties
associated with deadlock prevention or detection. This is the approach that both Windows and UNIX take

In order to avoid deadlocks, the system must have additional information about all processes. In
particular, the system must know what resources a process will or may request in the future. ( Ranging
from a simple worst-case maximum to a complete resource request and release plan for each process,
depending on the particular algorithm. )

Deadlock detection is fairly straightforward, but deadlock recovery requires either

aborting processes or preempting resources, neither of which is an attractive alternative.

If deadlocks are neither prevented nor detected, then when a deadlock occurs the system will
gradually slow down, as more and more processes become stuck waiting for resources currently held by
the deadlock and by other waiting processes. Unfortunately, this slowdown can be indistinguishable from
a general system slowdown when a real-time process has heavy computing needs.

3.8 Deadlock Prevention

Deadlocks can be prevented by preventing at least one of the four required conditions:

Mutual Exclusion
Shared resources such as read-only files do not lead to deadlocks. Unfortunately, some resources, such as
printers and tape drives, require exclusive access by a single process.

Hold and Wait

To prevent this condition processes must be prevented from holding one or more resources while
simultaneously waiting for one or more others. There are several possibilities for this:
Require that all processes request all resources at one time. This can be wasteful of system resources
if a process needs one resource early in its execution and doesn't need some other resource until
much later.

Require that processes holding resources must release them before requesting new resources, and then re-
acquire the released resources along with the new ones in a single new request. This can be a problem if
a process has partially completed an operation using a resource and then fails to get it re-allocated after
releasing it.

Either of the methods described above can lead to starvation if a process requires one or more popular
resources.

No Preemption

Preemption of process resource allocations can prevent this condition of deadlocks, when it is possible.
III Semester, Operating Systems-BCS303 Page 19 of 33
 RV Institute of Technology &
Management®
One approach is that if a process is forced to wait when requesting a new resource, then all other
resources previously held by this process are implicitly released, (preempted), forcing this process to re-
acquire the old resources along with the new resources in a single request, similar to the previous
discussion.

Another approach is that when a resource is requested and not available, then the system looks to see
what other processes currently have those resources and are themselves blocked waiting for some other
resource. If such a process is found, then some of their resources may get preempted and added to the list
of resources for which the process is waiting.

Either of these approaches may be applicable for resources whose states are easily saved and restored,
such as registers and memory, but are generally not applicable to other devices such as printers and tape
drives.

Circular Wait

 One way to avoid circular wait is to number all resources, and to require that processes request
resources only in strictly increasing ( or decreasing ) order.
 In other words, in order to request resource Rj, a process must first release all Ri such that i
>= j.

 One big challenge in this scheme is determining the relative ordering of the different resources

3.9 Deadlock Avoidance

 The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by
preventing at least one of the aforementioned conditions.
 This requires more information about each process, AND tends to lead to low device utilization. ( i. e.
it is a conservative approach. )
 In some algorithms the scheduler only needs to know the maximum number of each resource that a
process might potentially use. In more complex algorithms the scheduler can also take advantage of
the schedule of exactly what resources may be needed in what order.
 When a scheduler sees that starting a process or granting resource requests may lead to future
deadlocks, then that process is just not started or the request is not granted.
 A resource allocation state is defined by the number of available and allocated resources, and the
maximum requirements of all processes in the system.

Safe State

 A state is safe if the system can allocate all resources requested by all processes ( up to their stated
maximums ) without entering a deadlock state.
 More formally, a state is safe if there exists a safe sequence of processes { P0, P1, P2, ..., PN} such
that all of the resource requests for Pi can be granted using the resources currently allocated to Pi
and all processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and then Pi will be able to
III Semester, Operating Systems-BCS303 Page 20 of 33
 RV Institute of Technology &
Management®
finish also, using the resources that they have

Fig. 3.5: Safe, unsafe, and deadlocked state spaces

 If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to
deadlock (Fig. 3.5). (All safe states are deadlock free, but not all unsafe states lead to deadlocks.
)

For example, consider a system with 12 tape drives, allocated as follows. Is this a safe state? What is
the safe sequence?

Maximum Current
Needs Allocation
P0 10 5
P1 4 2
P2 9 2

i: What happens to the above table if process P2 requests and is granted one more tape drive?

Key to the safe state approach is that when a request is made for resources, the request is granted only if
the resulting allocation state is a safe one.

At time for, the system is in a safe state. The sequence < P0, P1, P2> satisfies the safety condition.
Process P1 can immediately be allocated all its tape drives and then return them (the system will then
have 5 available tape drives); then process P0 can get all its tape drives and return them (the system will
then have 10 available tape drives); and finally process P2 can get all its tape drives and return them (the
system will then have all 12 tape drives available).

A system can go from a safe state to an unsafe state. Suppose that, at time t1, process P2 requests and is
allocated one more tape drive. The system is no longer in a safe state. At this point, only process P1, can
be allocated all its tape drives. When it returns them, the system willhave only 4 available tape drives.
Since process P0, is allocated 5 tape drives but has a maximum of 10, it may request 5 more tape drives.
Since they are unavailable, process P1 must wait. Similarly, process P2 may request an additional 6
tape drives and have to wait, resulting in a deadlock. Our mistake was in granting the request from
process Pi for one more tape drive. If we had made P2 wait until either of the other.

III Semester, Operating Systems-BCS303 Page 21 of 33

 RV Institute of Technology &
Management®

3.9.2 Resource-Allocation Graph Algorithm

If resource categories have only single instances of their resources, then deadlock states can be detected
by cycles in the resource-allocation graphs.

In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation graph
with claim edges, noted by dashed lines, which point from a process to a resource that it may request in
the future.
In order for this technique to work, all claim edges must be added to the graph for any particular process
before that process is allowed to request any resources. (Alternatively, processes may only make
requests for resources for which they have already established claim edges, and claim edges cannot be
added to any process that is currently holding resources. )
When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly, when a
resource is released, the assignment reverts back to a claim edge.

This approach works by denying requests that would produce cycles in the resource-allocation graph,
taking claim edges into effect.

Consider for example (Fig. 3.6) what happens when process P2 requests resource R2:

Fig. 3.6 Resource allocation graph for dead lock avoidance

The resulting resource-allocation graph would have a cycle in it, and so the request cannot be granted (Fig.
3.7).

Fig. 3.7 An Unsafe State in a Resource Allocation Graph

III Semester, Operating Systems-BCS303 Page 22 of 33

 RV Institute of Technology &
Management®

OPERATING SYSTEMS Module IIII

3.9.3 Banker's Algorithm

 For resource categories that contain more than one instance the resource-allocation graph method
does not work, and more complex (and less efficient) methods must be chosen.

 The Banker's Algorithm gets its name because it is a method that bankers could use to assure that
when they lend out resources they will still be able to satisfy all their clients. ( A banker won't
loan out a little money to start building a house unless they are assured that they will later be able
to loan out the rest of the money to finish the house. )

 When a process starts up, it must state in advance the maximum allocation of resources it may
request, up to the amount available on the system.

 When a request is made, the scheduler determines whether granting the request would leave the
system in a safe state. If not, then the process must wait until the request can be granted safely.

[Link] Data Structures for the Banker’s Algorithm

Let n = number of processes, and m = number of resources types. N

Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj
available n

Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resourcetype
Rjn

Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rjn Need: n

x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its taskNeed [i,j] =

Max[i,j] – Allocation [i,j]

[Link] Safety Algorithm

1. Let Work and Finish be vectors of length m and n, respectively.

Initialize: Work = Available Finish [i] = false for i = 0, 1, …, n- 1

2. Find and i such that both:

(a) Finish [i] = false

(b) Needi <= Work

If no such i exists, go to step 4

III Semester, Operating Systems-BCS303 Page 23 of 33

 RV Institute of Technology &
Management®
3. Work=Work+Allocationi

Finish[i] = true go to step 2

4. If Finish [i] == true for all i, then the system is in a safe state

[Link] Resource-Request Algorithm for Process Pi

Request = request vector for process Pi . If Requesti [j] = k then process Pi wants k instances of resource type
Rj

1. If Requesti <= Needi

go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim

2. If Requesti £ Available, go to step 3. Otherwise Pi must wait, since resources are not available

3. Pretend to allocate requested resources to Pi by modifying the state as follows:

Available = Available – Request;

Allocationi=Allocationi+Requesti;

Needi = Needi – Requesti;

If safe Þ the resources are allocated to Pi

If unsafe Þ Pi must wait, and the old resource-allocation state is restored

[Link] An Illustrative Example

Consider the following situation:

III Semester, Operating Systems-BCS303 Page 24 of 33

 RV Institute of Technology &
Management®

The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria.

Example: P1 Request (1,0,2) Check that Request £ Available (that is, (1,0,2) <= (3,3,2) Þ tru

Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement.

3.10 Deadlock Detection

If deadlocks are not avoided, then another approach is to detect when they have occurred and recover
somehow.
In addition to the performance hit of constantly checking for deadlocks, a policy / algorithm must be in
place for recovering from deadlocks, and there is potential for lost work when processes must be aborted
or have their resources preempted.

3.10.1 Single Instance of Each Resource Type

i. If each resource category has a single instance, then we can use a variation of the resource-
allocation graph known as a wait-for graph.
ii. A wait-for graph can be constructed from a resource-allocation graph by eliminating the
resources and collapsing the associated edges, as shown in the Fig. 3.8 below.
iii. An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a resource that
process Pj is currently holding.

Fig. 3.8 (a) Resource Allocation Graph Fig. 3.8(b) Corresponding Wait for Graph

III Semester, Operating Systems-BCS303 Page 25 of 33

 RV Institute of Technology &
Management®
[Link] before, cycles in the wait-for graph indicate deadlocks. This algorithm must maintain the wait-
for graph, and periodically search it for cycles.

3.10.2 Several Instances of a Resource Type Available:

A vector of length m indicates the number of available resources of each type.

Allocation: An n x m matrix defines the number of resources of each type currently allocated to
each process.

Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process
Pi is requesting k more instances of resource type. Rj .

3.10.3 Detection Algorithm

1. Let Work and Finish be vectors of length m and n, respectively Initialize:

(a) Work = Available(b) For i = 1,2, …, n,

(b) if Allocationi != 0, then

Finish[i]=false; otherwise, Finish[i] = true

2. Find an index i such that both:

(a) Finish[i] == false

(b) Requesti <=Work

If no such i exists, go to step 4

3. 3. Work = Work +

Allocationi Finish[i] = true go

to step 2

4. If Finish[i] == false, for some i, 1 <= i <=n, then the system is in

deadlock state. Moreover, if Finish[i] == false, then Pi is deadlocked

Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked
state.

3.10.4 Example of Detection Algorithm

Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances)

Snapshot at time

III Semester, Operating Systems-BCS303 Page 26 of 33

 RV Institute of Technology &
Management®

OPERATING SYSTEMS Module IIII

Now suppose that process P2 makes a request for an additional instance of type C, yielding the
state shown below. Is the system now deadlocked?

3.10.5 Detection-Algorithm Usage

i. When should the deadlock detection be done? Frequently, or infrequently?

The answer may depend on how frequently deadlocks are expected to occur, as well as the possible
consequences of not catching them immediately. ( If deadlocks are not removed immediately when they
occur, then more and more processes can "back up" behind the deadlock, making the eventual task of
unblocking the system more difficult and possibly damaging to more processes. )

ii. There are two obvious approaches, each with trade-offs:

[Link] deadlock detection after every resource allocation which cannot be immediately granted. This has
the advantage of detecting the deadlock right away, while the minimum number of processes are involved
in the deadlock. ( One might consider that the process whose request triggered the deadlock condition is
the "cause" of the deadlock, but realistically all of the processes in the cycle are equally responsible for
the resulting deadlock. ) The down side of this approach is the extensive overhead and performance hit
caused by checking for deadlocks so frequently.

[Link] deadlock detection only when there is some clue that a deadlock may have occurred, such as when
CPU utilization reduces to 40% or some other magic number. The advantage is that deadlock detection
is done much less frequently, but the down side is that it becomes impossible to detect the processes
involved in the original deadlock, and so deadlock recovery can be more complicated and damaging to
more processes.

3. As I write this, a third alternative comes to mind: Keep a historical log of resource allocations, since
that last known time of no deadlocks. Do deadlock checks periodically ( once an hour or when CPU
usage is low?), and then use the historical log to trace through and determine when the deadlock occurred
and what processes caused the initial deadlock.
III Semester, Operating Systems-BCS303 Page 27 of 33
 RV Institute of Technology &
Management®
Unfortunately I'm not certain that breaking the original deadlock would then free up the resulting log
jam. )

3.11 Recovery from Deadlock

There are three basic approaches to recovery from deadlock:

 Inform the system operator, and allow him/her to take manual intervention.
 Terminate one or more processes involved in the deadlock
 Preempt resources.

Process Termination

Two basic approaches, both of which recover resources allocated to terminated processes:

Terminate all processes involved in the deadlock. This definitely solves the deadlock, but at
the expense of terminating more processes than would be absolutely necessary.

Terminate processes one by one until the deadlock is broken. This is more conservative, but
requires doing deadlock detection after each step.

In the latter case there are many factors that can go into deciding which processes to terminate next:

Process priorities.

 How long the process has been running, and how close it is to finishing.
 How many and what type of resources is the process holding. ( Are they easy
to preempt and restore? )
 How many more resources does the process need to complete.
 How many processes will need to be terminated
 Whether the process is interactive or batch.

3.11.1 Resource Preemption

When preempting resources to relieve deadlock, there are three important issues to be addressed:

[Link] Selecting a victim - Deciding which resources to preempt from which processes
involves many of the same decision criteria outlined above.

[Link] Rollback - Ideally one would like to roll back a preempted process to a safe state prior to the
point at which that resource was originally allocated to the process. Unfortunately, it can be
difficult or impossible to determine what such a safe state is, and so the only safe rollback is to
roll back all the way back to the beginning. (I.e. abort the process and make it start over.)

[Link] Starvation - How do you guarantee that a process won't starve because its resources are
III Semester, Operating Systems-BCS303 Page 28 of 33
 RV Institute of Technology &
Management®
constantly being preempted? One option would be to use a priority system, and increase the
priority of a process every time its resources get preempted. Eventually it should get a high
enough priority that it won't get preempted any more.

III Semester, Operating Systems-BCS303 Page 29 of 33