OPERATING SYSTEM

MODULE-III
PART-1
PROCESS COORDINATION
Synchronization:
 The Critical section problem
 Peterson’s solution
 Synchronization hardware
 Semaphores
 Classical problems of synchronization
 Monitors.

Process Coordination

Synchronization:- Process synchronization is a mechanism to ensure a systematic sharing of

resources amongst concurrent processes.
Concurrent access to shared data may result in data inconsistency.
Racing problem:- 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.
Example:
Let there are two processes P0 and P1, accessing a common integer variable A :
Initially the value of A=1000
P0: Read (A);
A: = A – 100;
Write (A);
P1: Read (A);
A: = A + 200;
Write (A);
P0 and P1 execute in one of the following two sequences:
(a) P0 followed by P1
(b) P1 followed by P0
But, suppose P0 and P1 are permitted to execute in any arbitrary fashion, then any of the
following could occur.
Possibility 1:
Possibility of execution for the above example in the sequence P0, P1, P0, P1. Now, the end-
value of A will be 1200, which is wrong.
1
 OPERATING SYSTEM

Possibility 2:
Possibility of the execution sequence: P0, P1, P0, now, the end-value of A will be 900, which
is again wrong.
In such a situation, when the end-result of execution of two or more concurrent processes is
arbitrary and depends on the relative order of their execution, is called a Racing problem.

Critical Selection
Each process having a segment of code in which the process may be changing common
variables, updating a table, writing a file and so on. This segment of code is said to be
‘critical selection’. Like in the above example, the processes P0 and P1 are executing their
respective critical selections, to modify the value of A.

do
Entry section

critical section

Exit program

remainder section
while (condition)

Solutions to the critical section:

1. Mutual Exclusion: Only one process can execute their critical sections at a time. No
other processes can be executing in their critical at any time.
2. Progress: If no processes is executing in its critical section and some process wish to
enter their critical section then only those processes that are not executing in their
remainder sections can participating deciding which will enter its critical section next.
3. Bounded waiting: There exit a bound 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
selection and before that request is granted, the upper bound is 1.

Peterson’s algorithm
Peterson’s solution is restricted to two processes that alternate execution between their
critical sections and remainder sections.

Program Peteronals;
Var favoredprocess: (first, second);
P1wantstoenter, P2 wants to enter :Boolean;
Procedure processone;

2
 OPERATING SYSTEM

Begin
While true do
Begin
P1 wantstoenter :=true;
Favoredprocess :=second;
While P2wantstoenter
and favoredprocess=second do
criticalselectionone;
P1 wantstoenter :=false;
otherwiseone
End
End;
Procedure processtwo;
Begin
While true do
Begin
P2wantstoenter :=true;
Favored process :=first;
While P1 wantstoenter
and favoredprocess=first do;
criticalsectiontwo;
P2wantstoenter :=false;
otherwise two
End
End;
Begin
P1 wantstoenter =false;
P2 wantstoenter = false;
Parbegin
Processone;
Processtwo;
Pareend
End
Synchronization Hardware:
Peterson’s algorithm is a software solution to the Mutual Exclusion problem. This section
presents a hardware solution for the Mutual Exclusion. The basic idea in this method is to
have a single hardware instruction that read a variable, and stores its value in a save area, and
sets the variable to a certain value. This instruction is said to be “testandset”.
Testandset(a,b) reads the value of Boolean b, copies it into a, and then sets b to true.
Program testandset
Var active :boolean;
3
 OPERATING SYSTEM

Procedure Processone;
Var one canoteenter : boolean;
Begin
While true do
Begin
Onecannotenter:= true;
While onecannotenter do
Testandset (onecannotenter, active);
Criticalsectionone;
Active = false;
Otherwiseone
End
End;
Procedure processtwo;
Var two canoteenter : boolean;
Begin
While true do
Begin
Twocannotenter:= true;
While twocannotenter do
Testandset (twocannotenter, active);
Critical sectiontwo;
Active = false;
Otherwise two
End
End;
Begin
Active = false
Parbegin
Processend;
Processtwo;
Parend.
End
Semaphores
The solution of a critical-section problem is a semaphore. This is a synchronization tool. A
semaphore S is an integer variable that, apart from initialization, is accessed only though two
standard atomic operation : wait and signal. These operations were originally termed P and V.
the classical definitions of wait and signals are:
Wait(s) : Decrements the value of its argument S, as soon as it would become non-negative,
completion of WAIT operation must be in divisible.
Wait(s) : while S <= 0 do no-op;
S:= S-1;
4
 OPERATING SYSTEM

Signal(s): increments the value of its argument, S as an indivisible operation

Signal(s) : S:= S+1;
Semaphores are very convenient for inter process synchronization as a means for signaling.
Semaphore must be used carefully. A misplaced wait or signal or reserved wait and signal
operations may result in indefinite waiting or deadlocks. The wait and signal primitives are
assumed to be atomic.
Binary semaphore: If the semaphore is allowed to take the values 0 or 1 is said to be binary-
semaphore.
Algorithm:
Type semaphore =record
Count : integer;
Queue : list of process
End;
Var s : semaphore;
Wait(s)
[Link]:= [Link]-1;
if [Link] < 0
then begin
place this process in [Link];
block this process
end;
Signal(s)
[Link] := [Link] + 1
If [Link] <=0
Then begin
Remove a process P from [Link];
Place process p on ready list
End;
Classical problems of synchronization:
1. The Dining Philosopher problem:-
Description: Five philosophers are seated around a circular table. Each philosopher has a
plate of ‘Noodles’. The Noodle is so slipper, that a philosopher needs two forks to eat it .But
only one fork is available for each philosopher, between each pair of plates is one fork.

PH5 PH4

P5 F4 P4
P P
F5 F3

PH1 P1
P P3 P PH3
F1 F2
P2
P

PH2 5
 OPERATING SYSTEM

Dining philosopher problem

PH1,PH2,PH3,PH4,PH5 are the 5 philosophers p1,p2,p3,p4,p5 are the 5 plates of noodles,
F1,F2,F3,F4,F5 are the 5 forks.
The philosophers work is just eating and thinking. When a philosopher gets hungry, he tries
to acquire his left and right fork, one at a time, in either order. If it successful in acquiring
two forks, he eats for a while, then puts down the forks, and continues to think.

Algorithm:
#define N 5 /* number of philosophers */
#define LEFT (I+N-l) % N /* number of l’s left neighbor */
#define RIGHT(I+l)%N /* number of l’s right neighbor */
#defineTHINKING 0 /* philosopher is thinking */
#define HUNGRY 1 /* philosopher is trying to get forks */
#define EATING 2 /* philosopher is eating */
typedef int semaphore; /* semaphores are a special kind of int */
int state[N]; /* array to keep track of everyone’s state */
Semaphore mutex =1; /* mutual exclusion for critical regions */
Semaphore s[N]; /* one semaphore per philosopher */
Void philosopher (int l) /* l; philosopher number, from o to N-1 */
{
While(TRUE) { /* repeat forever*/
think(); /* philosopher is thinking */
take_forks(i); /* acquire two forks or block */
eat(); /*yum-yum, spaghetti */
put_forks(i); /*put both forks back on table */
}
}
Void take_forks(int l) /* l: philosopher number, from 0 to N-1 */
{
down(&mutex); /* enter critical region */
state[l]=HUNGRY; /* record fact that philosopher l is hungry */
test(i); /* try to acquire 2 forks */
up(&mutex); /* exit critical region */
down(&s[l]); /* block if forks were not acquired */
}

6
 OPERATING SYSTEM

void put_forks(i) /* l: philosopher number, from 0 to N-1 */

{
down(&mutex); /* enter critical region */
State[l]=THINKING; /*philosopher has finished eating */
test(LEFT); /* see if left neighbur can now eat */
test(RIGHT); /* see if right neighbor can now eat */
up(&mutex); /* exit critical region */
}
void test(i) /* l: philosopher number, from 0 to N-1 */
{
if(State[l]==HUNGRY && state[LEFT]!=EATING&&state[RIG HT]!=EATING){
state[l]=EATING;
up(&s[l]);
}

2. The readers and writers problem

It is acceptable to have multiple processes reading the database at the same time, but one
process is updating (writing) the database. No other process may have access to the database,
not even readers. This is the problem of ‘reader and writers’.
Example: airline reservation system
Algorithm:
typedef int semaphore; /* use your imagination */
Semaphore mutex=1 /*(controls access to ‘rc’ */
Semaphore db=1 /* controls access to the database*/
Int rc=0; /* #of processes reading or writing to */
Void reader(void)
{
While(TRUE) /* repeat forever */
{
Down(&mutex) /*get exclusive access to ‘rc’ */
rc=rc+1; /* one reader more now */
If(rc==1)down (&db) /* if this is the first reader.. */
up(&mutex); /* release exclusive access to ‘rc’ */
read_data_base(); /* access the data */
down((&mutex); /* get exclusive access to ‘rc’ */
rc=rc-1; /* one reader fewer now */
if(rc==0)up(&db); /* if this is the last reader…..*/
up(&mutex); /*release exclusive access to ‘rc’ */
use_data_read() /* noncritical region */
}
}

7
 OPERATING SYSTEM

void write (void)

{
While(TRUE) /* repeat forever */
{
Think_up_data(); /* non critical region */
down(&db); /* get exclusive access */
write_data_base(); /* update the data */
up(&db); /* release exclusive access */
}
}

3. The Producer-consumer problem

In this problem two processes share a common, fixed-size buffer. One of them the producer,
puts information into the buffer, and the other one, the consumer, take it out. For example the
I/O processor produces the information and puts the information in I/O buffers. The printer
consumes the information from the buffer. So here the producer is I/O processor and the
consumer is the printer.
The problems arise when the producer wants to put a new item in the buffer, but it is already
full (assume that it is limited buffer). The solution is for the producer has to wait until the
consumer has consumed at least one buffer. Similarly if the consumer wants to remove an
item from the buffer and sees that the buffer is empty, it goes to sleep until the producer puts
something in the buffer and wakes it up. Consider the following algorithm for the above
problem.
Algorithm:
#DEFINE N 50
int cout=0;
void produer(void)
{
int item;
while (TRUE)
{
item=produce-item();
if(cout==N)wait();
insert_item(item);
count-cout+1;
if(count==1)wakeup(consumer);
}
}
8
 OPERATING SYSTEM

void consumer
{
int item;
while (TRUE)
{
if(count==0)wait();
item=remove-item();
count=count-1;
if(count==n-1)wakeup(producer);
consumer-item(item);
}
}

Monitors
Another synchronization construct is the monitor type. A monitor is a collection of
procedures, variables and data structures that are all grouped together in special kind of
module or package. Monitors have an important property that makes them useful for
achieving mutual execution: only one process can be achieve in a monitor at any instance.
The syntax of the monitor is consider below
Type monior_name=monitor
Variable declarations
Procedure entry p1 (….);
Begin
……
end;
Procedure entry p2(….);
Begin
……..
end;
producer entry pn(…)
Begin
……
end;
begin
initialization code
end

9
 OPERATING SYSTEM

Process may call be procedures in a monitor whenever they want to, but they cannot directly
access the monitor internal data structures from procedures declared outside the monitor.
When a process calls a monitor procedure, the first few instructions of the procedure will
check to see if any other process is currently active with in the monitor. If no other process is
using the monitor, the calling process may enter.
A monitor supports synchronization by the use of condition variables that are contained
within the monitor and accessible only within the monitor. Two functions operate on
condition variables.
Wait( C): Suspend execution of the calling process on condition ‘C’. The monitor is
now available for use by another process.
Signal ( c): Resume execution of some process suspend after a wait on the same
condition. If therefore several such processes, choose one of them; if there is
no such process, do nothing.

Diagram:
Monitor

Operation n1
Shared Entry queue
DATA

Operation n2





Operation nn Conditions variables

Condition Queues

Monitor abstraction

10
 OPERATING SYSTEM

MODULE-III
PART-2
DEADLOCKS
 System model
 Deadlock Characterization
 Methods for Handling Deadlocks
 Deadlock Prevention
 Deadlock Detection
 Deadlock avoidance
 Recovery from Deadlock.

Deadlock

Definition
A set of two or more processes are deadlocked if they are blocked (i.e., in the waiting state)
each holding a resource and waiting to acquire a resource held by another process in the set.
Or A process is deadlocked if it is waiting for an event which is never going to happen.

Example: a system has two tape drives, two processes are deadlocked if each holds one tape
drive and has requested the other..

Conditions Necessary for Deadlock:

All of the following four necessary conditions must hold simultaneously for deadlock to occur:
 Mutual exclusion: only one process can use a resource at a time.
 Hold and wait: a process holding at least one resource is waiting to acquire additional
resources which are currently held by other processes.
 No preemption: a resource can only be released voluntarily by the process holding it.
 circular wait: a cycle of process requests exists (i.e., P0 is waiting for a resource hold
by P1 who is waiting for a resource held by Pj ... who is waiting for a resource held by
P(n-1) which is waiting for a resource held by Pn which is waiting for a resource held
by P0).
Circular wait implies the hold and wait condition. Therefore, these conditions are not
completely independent.

11
 OPERATING SYSTEM

Resource-Allocation Graph algorithm (Directed Graph)

Resource allocation graph is a directed graph where the vertices requested the resources and
processes.
A resource is represented by square, dots inside representing different
instances in that resource.
A process is represented by a circle.

Rj
Request Edge:- Pi

Rj
Pi
Assignment Edge:-
Which instance is assigned to the process.
Processes wait for graph (PWFG):
PWFG can be obtained by collapsing resources symbols in the RAG.

P0 P1

An edge from process P0 to P1 indicates that process P0 is waiting for a resource

currently held by P1.
NOTE:
 A cycle is not sufficient proof of the presence of deadlock.
 If a resource allocation graph contains no cycles, then no process is deadlocked.
 If a resource allocation graph contains a cycle, then a deadlock may exist.

Methods for Handling Deadlock

1. Deadlock Prevention

 prevent mutual exclusion

o use only sharable resources (e.g., a read-only file)
 prevent hold and wait
 Do not pick up one chopstick if you cannot pick up the other
 for a process that copies data from DVD drive to a file on disk and then
prints it from there:
1. Request DVD drive 2. Request disk [Link] printer
 prevent no preemption
when a process must wait, it must release its resources
 prevent circular wait
Impose a total ordering on resources, only allow requests in an increasing order
Usually a deadlock prevention approach is simply unreasonable.

12
 OPERATING SYSTEM

2. Deadlock Detection

Deadlock detection can be obtained by two methods.

A. Single instance of each resource type
B. Several instance of each resource type
Single instance of each resource type:
Many resources share only a single instance then the deadlock can be detected by a resource
allocation graph called wait for graph.
Wait for graph can be obtained from resource allocation graph by removing the resource
nodes and giving appropriate edges.
Solution:
Each resource must consist of single instance of its own.
A. Resource-allocation-graph B. Corresponding-wait-for-graph

Several instances of a resource type:

Resource consists of multiple instances. This problem can’t be solved by wait for graph.
Solution:
Banker’s Algorithm.

3. Deadlock Avoidance
Deadlock Avoidance Algorithms
 Resource-Allocation Graph algorithm
 Banker's algorithm

Sample Resource-Allocation Graph

RAG without deadlock RAG with a cycle and deadlock

13
 OPERATING SYSTEM

RAG with a cycle but no deadlock Possibility of Deadlock

Problem:-1 Solution:
Consider the following RAG. Equivalent process waits for graph (PWFG)
R0 R2

P0 P1 P2

P P P No Deadlock Exist

R1
The RAG contains no cycle, thus indicating that no Deadlock Exists. Since P2 is not waiting
for any resource & its execution can be completed.
Problem:-2 Solution: Process Wait for Graph:-
R0 R2
P0 P1

P2
P0 P1 P2

There is a cycle in the RAG i.e

P0 R0 P1 R2 P2 R1 P0
There is another cycle i.e
P1 R2 P2 R1 P1
R1
Thus, there is a Deadlock.
Problem:-3 Equivalent process Wait for Graph:-
R0
P0 P1

P0 P1 P2

There is a cycle in the RAG i.e

R1 P0 R0 P1 R1 P0
P2

There is one resource i.e. R1 having two instances. So, there is likelihood of Deadlock. Since
P2 is not waiting for any resource & it can be completed. Once P1 releases R0.P0 can be
completed. Thus there is no Deadlock.
14
 OPERATING SYSTEM

Banker's Algorithm
We use this algorithm for multiple instance of resource type where resource allocation graph
is not applicable. Let n be the number of processes in the system, and m be the number of
resource types. We basically use data structure to understand banker’s algorithm:
 Available:-
Available=m, this is a vector of length m indicates the number of Available resources
of each type.
If Available[j]=k, there are k instances of resource type Rj.
 Max:-
This N x M matrix which indicates the maximum requirement of system resources of
each process.
If Max[i,j]=k
it indicates that Pi would need maximum k instances of resource Rj during its entire
execution.
 Allocation:-
An N x M matrix defines the number of resources of each type currently allocated to
each process.
If allocation[i,j]=k
The process Pi is currently allocated k instances of resource type Rj.
 Need:-
An N x M matrix indicates the remaining resource need of each process.
If Need[i,j]=k
then Pi may need k more instances of resource type Rj to complete its task.
Note that Need[i,j]=max[i,j]-allocation[i,j].
Banker's Algorithm consists of two algorithms:
a. Safety algorithm
b. Resource-request-algorithm
Safety algorithm (to check for a safe state):
The algorithm for find out whether or not a system is in safe state can be described as
follows:
The variable available (integer array) and finish (Boolean array), the vector of length m & n respectively.
Step1: initialize available=m & finish[i]=false for i=1, 2, 3 …….n
Step2: Find an i; such that both:
o finish[i] == false
o Need[i] <= Available
If no such i exists, go to step 4
Step3: Available = Available + allocation[i];
finish[i] = true;
go to step 2
Step4: If finish[i] == true for all i, then the system is in a safe state, otherwise unsafe.
15
 OPERATING SYSTEM

Resource-request-algorithm:
Request:
This is a matrix of dimension N x M which indicates pending request of resources in respect
of all processes.
Request[i][j]=k: implies that process Pi has requested additional allocation of k instances of
resource Rj.
Request Rejection/Validation:
If Request[i][j]<= need [i][j] is true,
Then Request[i][j] will be valid else Request[i][j] will be rejected as invalid.
Step1: If request[i][j] <= Need[i][j], go to step 2; otherwise, raise an error condition,
(since the process is exceeds its maximum claim).
Step2: If request[i][j] <= Available[j], then go to step 3, otherwise Pi must wait.
(since resource is not available).
Step3: Available[j] = Available[j] - request[i][j]
allocation[i][j] = allocation[i][j] + request[i][j]
Need[i][j] = Need[i][j] - request[i][j]
Problem: 1
i) Consider a system with 5 processes (P0 ... P4) and 3 resources types (A(10) B(5) C(7)).
Resource-allocation state at time t0:
Allocation Max
Process
A B C A B C
P0 0 1 0 7 5 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
Is the system in a safe state? If so, which sequence satisfies the safety criteria?
Solution:
Now we have to calculate the Available matrix of the resources.
Available= Total-Allocation
A =10-(2+3+2) =3 B =5-(1+1) =3 C =7-(2+1+2) =2
Available matrix is (3, 3, 2)
The Need matrix is:
Need
Process
A B C
P0 7-0=7 5-1=4 3-0=3
P1 3-2=1 2-0=2 2-0=2
P2 9-3=6 0-0=0 2-2=0
P3 2-2=0 2-1=1 2-1=1
P4 4-0=4 3-0=3 3-2=1

16
 OPERATING SYSTEM

Process P0
Need Available
A B C A B C
7 4 3 3 3 2
Since Need>Available, It does not satisfy the condition.,P0 is not in safe state.
Process P1
Need Available
A B C A B C
1 2 2 3 3 2
Since Need<=Available, It satisfies the condition,
New Available=Available + Allocation
=3 3 2 + 2 0 0=5 3 2
P1 is in safe state.
Process P2
Need Available
A B C A B C
6 0 0 5 3 2
Since Need>Available, It does not satisfy the condition, P2 is not in safe state.
Process P3
Need Available
A B C A B C
0 1 1 5 3 2
Since Need<=Available, It satisfies the condition.
New Available=Available + Allocation
=5 3 2 + 2 1 1= 7 4 3
P3 is in safe state.
Process P4
Need Available
A B C A B C
4 3 1 7 4 3
Since Need<=Available
It satisfies the condition.
New Available=Available + Allocation
=7 4 3 + 0 0 2= 7 4 5
P4 is in safe state.
Process P2
Need Available
A B C A B C
6 0 0 7 4 5
Since Need<=Available
It satisfies the condition.
New Available=Available + Allocation
=7 4 5 + 3 0 2=10 4 7
P2 is in safe state.
17
 OPERATING SYSTEM

Process P0
Need Available
A B C A B C
7 4 3 10 4 7
Since Need<=Available
It satisfies the condition.
New Available=Available + Allocation
=10 4 7 + 0 1 0=10 5 7
P0 is in safe state.
So the safe sequence is < P1, P3, P4, P2, P0 >
ii) Now suppose, P1 requests an additional instance of A and 2 more instances of
type C. Request[1] = (1,0,2)
i.e A B C
1 0 2
Solution:
1. check if request[1] <= Need[i]
Request [1] Need [1]
A B C A B C
1 0 2 1 2 2
Yes it satisfies the condition.
2. check if request[1] <= Available[i]
Request [1] Available [1]
A B C A B C
1 0 2 3 2 2
Yes it satisfies the condition.
Hence immediate grant of resources.
3. Do pretend updates to the state.
i.e update the Available and allocation:
Available=Available - Request
=3 3 2 - 1 0 2 = 2 3 0
Allocation= Allocation + Request
=2 0 0 + 1 0 2 = 3 0 2
Allocation Max Available
Process
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 3 0 2 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
Is the system in a safe state? If so, which sequence satisfies the safety criteria?
18
 OPERATING SYSTEM

Solution:
Need
Process
A B C
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
Process P0
Need Available
A B C A B C
7 4 3 3 3 2
Since Need>Available, It does not satisfy the condition, P0 is not in safe state.
Process P1
Need Available
A B C A B C
0 2 0 3 3 2
Since Need<=Available, It satisfies the condition
New Available=Available + Allocation = 3 3 2 + 3 0 2= 6 3 4
P1 is in safe state.
Process P2
Need Available
A B C A B C
6 0 0 6 3 4
It satisfies the condition.
New Available=Available + Allocation = 6 3 4 + 3 0 2= 9 3 6
P2 is in safe state.
Process P3
Need Available
A B C A B C
0 1 1 9 3 6
Since Need<=Available
It satisfies the condition.
New Available=Available + Allocation = 9 3 6 + 2 1 1=11 4 7
P3 is in safe state.
Process P4
Need Available
A B C A B C
4 3 1 11 4 7
Since Need<=Available
It satisfies the condition.
New Available=Available + Allocation
=11 4 7+ 0 0 2= 11 4 9
P4 is in safe state.
19
 OPERATING SYSTEM

Process P0
Need Available
A B C A B C
7 4 3 11 4 9
Since Need<=Available
It satisfies the condition.
New Available=Available + Allocation
=11 4 9 + 0 1 0=11 5 9
P0 is in safe state.
So the safe sequence is < P1, P2, P3, P4, P0 >

iii) Will a request of (3, 3, 0) by P4 be granted?

Solution:
Request[4] Need[4]
A B C A B C
3 3 0 4 3 1
Here Request[4]<=Need[4]
It satisfies the condition.
Request[4] Available
A B C A B C
3 3 0 3 3 2
Here Request[4]<=Available
It satisfies the condition.
Allocation of P4 =0 0 2 + 3 3 0=3 3 2
Hence do immediate grant of resources.
iv) Will a request of (0, 2, 0) by P0 be granted?
Solution:
Request [0] Need [0]
A B C A B C
0 2 0 7 4 3
Here Request [0] <=Need [0]
It satisfies the condition.
Request [0] Available
A B C A B C
0 2 0 3 3 2
Here Request [0] <=Available
It satisfies the condition.
Allocation of P0 = 0 1 0+0 2 0 = 0 3 0
Hence do immediate grant of resources.
20
 OPERATING SYSTEM

4. Deadlock Recovery

How to deal with deadlock:

 inform operator and let them decide how to deal with it manually
 let the system recover from the deadlock automatically:
o Abort or more of the deadlocked processes to break the circular wait
o Preempt some resources from one or more of the processes to break the
circular wait

A. Process termination
Aborting a process is not easy; involves clean-up (e.g., file, printer).
 abort all deadlocked processes (disadvantage: wasteful)
 abort one process at a time until the circular wait is eliminated
B. Resource Preemption
Incrementally preempt and re-allocate resources until the circular wait is broken.
 Selecting a victim
 Rollback the process to a safe state and restart it from that state.
 Process waits for indefinite time for resource and under goes starvation.

Problem: 2
Assume that there are five processes in the system and 4 resources namely. TD- Tape
Drive, DD- Disk Drive, PR- Printer, SC- Scanner. Let the number of Available
resources be TD1, DD0, PR2 and SC0.
Maximum Number of Resources
Resources Allocated
Process Required
TD DD PR SC TD DD PR SC
P1 3 0 1 1 4 1 1 1
P2 0 1 0 0 0 2 1 2
P3 1 1 1 0 4 2 1 0
P4 1 1 0 1 1 1 0 1
P5 0 0 0 0 2 1 1 0

Need Matrix, Need[i]=Max[i]-Allocation[i]

Process TD DD PR SC
P1 1 1 0 0
P2 0 1 1 2
P3 3 1 0 0
P4 0 0 0 0
P5 2 1 1 0
Process P1
Need Available
1 1 0 0 1 0 2 0
Need >Available so, P1 is not in safe state
21
 OPERATING SYSTEM

Process P2
Need Available
0 1 1 2 1 0 2 0
Need >Available so, P2 is not in safe state
Process P3
Need Available
3 1 0 0 1 0 2 0
Need >Available so, P3 is not in safe state
Process P4
Need Available
0 0 0 0 1 0 2 0
Need <Available so, P4 is in safe state
New Available = Available + allocation
=1 0 2 0 + 1 1 0 1
=2 1 2 1
Process P5
Need Available
2 1 1 0 2 1 2 1
Need <=Available so, P5 is in safe state
New Available = Available + allocation
=2 1 2 1 + 0 0 0 0
=2 1 2 1
Process P1
Need Available
1 1 0 0 2 1 2 1
Need <=Available so, P1 is in safe state
New Available = Available + allocation
=2 1 2 1 + 3 0 1 1
=5 1 3 2
Process P2
Need Available
0 1 1 2 5 1 3 2
Need <Available so, P2 is in safe state
New Available = Available + allocation
=5 1 3 2 + 0 1 0 0
=5 2 3 2
Process P3
Need Available
3 1 0 0 5 2 3 2
Need <Available so, P3 is in safe state
New Available = Available + allocation
=5 2 3 2 + 1 1 1 0
=6 3 4 2
Safe Sequence is<P4 P5 P1 P2 P3>
22
 OPERATING SYSTEM

MODULE-IV
PART-1
MEMORY MANAGEMENT:
 Memory Management strategies
 Logical versus Physical Address space
 Swapping
 Contiguous Allocation
 Paging
 Segmentation.

Memory management

Memory management:
The major functions of OS are memory management. It controls the allocation/De-allocation
of physical memory. It keeps track of memory occupancy, loading of programs into free
memory space, getting the memory to execute the processes etc.

In the multiprogramming environment the user space is divided into number of partitions.
Each partition is for one process. The task of sub division is carried out dynamically by the
operating system; this task is known as “Memory Management”.

Logical vs. Physical Address Space

 Logical address: Set of all logical addresses that can be referenced by a process,
generated by the CPU; also referred to as virtual address.
 Physical address: Set of physical addresses, occupied by a process in the main memory.
Physical address space=Logical address space + Contents of the relocation register.
Virtual and physical addresses are the same in compile-time and load-time and differ in
execution-time address-binding scheme.

Memory allocation:

A. Contiguous memory allocation: A memory-resident program occupies a single

contiguous block of physical memory.
I. Fixed Partitioning: A memory is divided into fixed number of partitions. The
partition sizes are depending on the operating system.
 Internal Fragmentation: Since a program may not exactly fit the allocated
partition, some space may be left unoccupied after loading the program. This
space is wasted and it is termed as internal fragmentation.

23
 OPERATING SYSTEM

Partition Description Table (PDT): This table indicates the base and the size of
each partition along with its status (whether F (Free) or A (Allocated).
(0-50K)
Partition Partition Partition Partition
OS (0-45K)
Id Base Size Status Internal Fragmentation: 10K
0 0 50K A (50-100K)
Free
1 50K 50K F (100-150K)
Process B (100-140K)
2 100K 50K A
Internal Fragmentation: 10K
3 150K 100K A (150-250K)
Process A (150-230K)
4 250K 250K F Internal Fragmentation: 20K
(250-500K)
(PDT)
Free
(Physical Memory Space)
 External Fragmentation: A partition of main memory is wasted for the entire partition.
(0-50K)
Partition Partition Partition Partition
Id Base Size Status OS (0-50K)

0 0 50K A (50-110K)
Process A (50-110K)
1 50K 60K F
(110-130K)
2 110K 20K A Free (External Fragmentation: 0K)
3 130K 40K A (150-250K)
Process A (150-250K)
4 170K 830K F
(250-500K)
Free

Advantages of Fixed Partition: (Physical Memory Space)

• Implementation is very simple.
• Processing overhead is low.

Disadvantages Fixed Partition:

• The degree of multiprogramming is fixed since the number of partition is fixed.
• Suffers from internal fragmentation.
II. Variable Partitioning: This scheme is free from the limitation encountered in the
case of fixed partitioning.
Its functions are:
 Initially the entire available memory is treated as a single partition.
 The incoming program requiring memory allocation is queued up.
 A waiting program is loaded only when a free partition is big enough to fit the program.
 When a program is loaded it is allocated a space exactly equal to its size.
 The balanced unoccupied space in the allocated partition is treated as another
free partition.
 When a process terminate, it releases the partition occupied.
24
 OPERATING SYSTEM

 If the released partition is contiguous to another free partition, then both the
free partition are club together into a single free partition.
 When a free partition is too small to accommodate any program it is called
external fragmentation and that memory is lost.
Compaction: Compaction is a technique of collecting all the free spaces together
in one block.
 There may be exist more than one fragment, lost due to external
fragmentation. The fragments can be joined together using compaction.
 The space retrieved by compaction may from a partition big enough to
accommodate some more waiting program.
Different strategies for partition allocation:
• First fit
• Best fit
• Worst fit
First fit: It refers to the allocation of the 1st encountered partition that may be big
enough to the program being loaded.
Advantage:
1. It wants both for fix & variable partition scheme.
2. Search time is small.
Disadvantage:
1. Memory loss on account of fragmentation likely to be high.

Best fit: It refers to the allocation of the smallest available free partition that may
be big enough to accommodate the program.
Advantage:
• It wants both for fix & variable partition allocation scheme.
• Memory loss will be lower than in case of first fit.
Disadvantage:
• Search time will be longer as compare to first fit.

Worst fit: It refers to the allocation of the largest partition out of the ones which
are available may be bigger enough to accommodate the program. The spirit
behind the scheme is that the balance space left in the allocated partition may be
big enough to load another small program and in that eventually memory loss due
to fragmentation may be lower than fragmentation.
Advantage:
• Provide a smaller memory loss on account of fragmentation.
Disadvantage:
• Search time will be longer as compare to first fit but is same as in the case of best fit.

Note: This algorithm is designed only for variable partition allocation.

25
 OPERATING SYSTEM

III. Dynamic Partitioning: The partitions are created dynamically, so that each
process is loaded into partition of exactly the same size at that process.
 Non- Contiguous memory allocation: A memory-resident program occupies non-
contiguous block of physical memory.
It offers the following advantages over, contiguous memory allocation:
 Permits sharing of code and data amongst processes.
 There is no external fragmentation of physical memory.
 Supports virtual memory concept.

However, non-contiguous memory allocation involves a complex implementation and

involves additional costs in terms of memory and processing.

Non- contiguous memory allocation can be implemented by the concept of:

 Paging
 Segmentation
 Segmentation with paging

Paging: The logical address space of a process is divided into blocks of fixed size called
pages. Also the physical memory is divided into blocks of fixed size called frames. In a
system, the page and frame will be same size. The information about page number in
which a page resident is entered into page table. The page table is indexed by page
number.

Structure of page scheme:-

Frame No.
CPU P D F D Page0 0
PageN 1
Page Frame PageN-1 2
number number 3
4
5
.
P F .
.
n-2
n-1
n
Page map table
Main memory or Physical memory
(Structure of paging scheme)

26
 OPERATING SYSTEM

O.S. 0
Page 0 P. No F. No 1
Page 1 0 10 2
Page 2 1 3 Page 1(J1) 3
Page 2(J2) 4
2 7 5
Logical memory
for job 1
Page table for job 1
6
Page 1(J2)
Page 2(J1) 7
Page 0 P. No F. No Page 0(J2) 8

Page 1 0 8 Page 3(J2) 9

Page 2 1 6 Page 0(J1) 10
Page 3 2 4
Logical memory 3 9
for job 2
Page table for job 2

The mapping between page number and frame number done by page map table. The page
map table specifies which page is loaded in which frame between displacement is common.
For example:
There are two jobs in the ready queue the job sizes are 12KB and 16KB. The page size of
4KB. The available memory is 40KB. So, job1 is divided in 3 pages and job2 is divided into
4 pages. Each process maintains 3 pages of job1 loaded in different location in main
memory. The capacity of main memory in the example is 10 frames. But available jobs are
two (7pages), so the remaining 3 frames are free. The scheduler can use frames to some
other jobs.

Shared pages:-
In multiprogramming environment, it is possible to share the common code by number of
processes at the same time, instead of maintain the number of copies of same code. The page
which is shared by the number of processes is said to be shared pages.
For example:
Out of 10 users 3 users wishes to execute a text editor they want to take their bio data in text
editor. Assume that text editor requires 150kb and the user bio data requires 50KB of data
space. So they would need (150+50)*3 = 600KB.

But in shared paging 300KB (150+150) enough to manage 3 jobs instead of 600KB.

27
 OPERATING SYSTEM
Text Editor1 3 TE2 0
Text Editor2 0 1

B.Data1 2
5
TE1 3
Process P1 Page table for P1
4
Text Editor1 3
B. Date1 5
Text Editor2 0
B. Date2 6
B.Data2
6 7
Process P2 Page table for P2 8

Text Editor1
B. Date3 9
3
Text Editor2 10
0
11
B.Data3
9
12
Process P3 Page table for P3
Main memory
(Sharing code in paging environment)
Advantages
• It supports the time sharing system.
• It does not effect from fragmentation.
• It supports virtual memory.
• Sharing of common code is possible.
Disadvantages
• This scheme may suffer ‘page breaks’. For example the logical address space is
17KB, the page size is 4KB. So this job requires 5 frames. But the fifth frame
consisting of only one KB. So the remaining 3KB is wasted. It is said to be page
breaks.
• If the number of pages are high, it is difficult to maintain page tables.
Segmentation:-
A segment can be defined as logical group of instruction, such as subroutine, array or data
area. Every program (job) is a collection of these segments. Segmentation is the technique
for managing these segments.

0 0 0
. Sum=sum+X . .
. X=X+1 .
. . .
. . 100
100 Segment A
100
Segment main Segment X (Array)
Segmented address space

The physical memory is divided in segment of varying segments. Each segment is assigned a
unique segment number. Memory management is done through a segment table which is
indexed by segment number.

28
 OPERATING SYSTEM

For each segment it has an entry that provides:

1. Base address of segment
Segmentation Table
2. Size of segment

Segment No. Base Address Seg Size

1
2
.
.
b z
s
s-1
Program Physical
Logical Address
(Logical Address s d +
Address Space

d<z
? Yes (Valid)

No (Error)

The logical address contain segment number ‘S’ and offset within the segment ‘d’. Using the
segment number the system obtained the base address of the segment. Then it makes a check
to determine whether offset is within the segment size or not. If yes, then offset ‘d’ is valid
and physical address is computed, else it is error.

Example of segmentation:-
0 Main
Stack Seg No Limit Base 900
Program
1000 0 1000 1500 Segment 1
Segment 0 1050
1 150 900
0
Array 2 300 2500 1500
150 Segment 0
Segment 1 3 350 3900 2500
0 Segment 2
Segment Table 2800
Stack
300 3900
Segment 2
0 Segment 3
Subroutine 4250
350 500
Segment 3
Main memory
Local address space Example of Segmentation

Segmentation with paging:

It is better possible to combine these two schemes to improve on each. The combined
scheme was ‘page the segment’. Each segment is divided into pages and each segment
maintains a page table. So, the logical address is divided into 3 parts. <s,p,d>.
Where s Segment number, p Page number, d Displacement.
Advantage:- The main advantage of this scheme is to avoid fragmentation.
29
 OPERATING SYSTEM

Segmentation Table Base Address of

Segmentation Size of Segmentation
Segment No. Page Table Page Table

1
2
.
.
B M
s
s-1
Program Physical
Logical Physical
(Logical s p d f d Address
Address Address
Address Space
Segmentation
P<M Page Table
No (Error) ?
0
1
Yes (Valid) 2
.

P Frame # (f)

M-1

The segment number‘s’ is to access the segment entry in the segment page table. Each
segment will have separate page table. The page number ‘p’ is used to access the frame ‘f’ in
the page table, provided p<N, else it is invalid page number. The frame number ‘f’ is
combined with offset ‘d’ to compute the physical address.

For example:- Frame

No
Page No Seg No 0
Stack
0 5 Page 1
MAIN 1 7 (1.0) 2
table for
2 9 Seg 0 3
3 11 (1.1) 4
Segment 0 (0.0) 5
Page No Seg No (1.2) 6
(0.1) 7
ARRAY 0 2 Page
1 4 (1.3) 8
table for (0.2) 9
2 6 Seg 1 10
Segment 1 3 8
(0.3) 11
(2.0) 12
Page No Seg No
(2.1) 13
STACK 0 12 Page (2.2) 14
1 13
table for 15
2 14 Seg 2 16
Segment 2
3 17 (2.3) 17
Local address space
30
Paged Segmentation
 OPERATING SYSTEM

The logical address is divided into two segments numbered 0 and 1. And each segment
maintains a page table for mapping techniques. The frame number 6 shows the address (1,2).
Hence 1 stands for segment number and 2 stands for page number.

Comparison between paging and segmentation

Paging Segmentation

1. The main memory partitioned in to

1. The main memory partitioned into
frames or blocks.
segments.

2. The logical address space divided into

2. The logical address space divided into
pages by compiler or memory
segments specified by the programmer.
management unit (MMU).
3. This scheme suffering from external
3. This scheme suffering from internal
fragmentation.
fragmentation or breaks.
4. The OS maintains the particulars of
4. The OS maintains a free frames list need
available memory.
not to search for free frame.

5. The OS maintains a page map table for

5. The OS maintains a segment map table for
mapping between frames and pages.
mapping purpose.

6. This scheme does not support the user’s

view of memory. 6. It supports user view of memory.

7. Processor uses the page number and

7. Processor uses the segment number and
displacement to calculate absolute
displacement to calculate the absolute
address.
address.

8. Multilevel paging is possible.

8. Multilevel segmentation is also possible.

31
 OPERATING SYSTEM

MODULE-IV
PART-2

VIRTUAL MEMORY
 Background
 Demand paging
 Performance of Demand paging
 Page Replacement
 Page Replacement Algorithms
 Allocation of frames
 Thrashing
 Demand Segmentation.

Virtual memory
It is a technique that allows execution of process even the logical address space is greater
than physical available memory. The advantages of this memory are efficient memory
utilization and programs can be loaded partially in the main memory so more programs could
be run at the same. So efficient CPU utilization and better through put is possible.
Demand Paging:- It is the application of virtual memory which is a combination of paging
and swapping. In this scheme a page is not loaded into the main memory from secondary
memory until it is needed. So a page is loaded into the main memory on demand. So, this
scheme is said to be demand paging.
For example:-
Assume that the logical address space is 72KB, and the page and frame size is 8KB. So, the
logical address space is divided into 9 pages, numbered form 0 to 8. The available main
memory is 40KB. i.e 5 frames are available and the remaining 4 pages are loaded in the
secondary storage devices. Whenever those pages required the OS swaping those pages into
main memory.
Performance of Demand Paging:-
Demand paging can significantly affect the performance of computer system. To see why,
lets compute the effective access time for a demand paged memory. For most computer
system the memory access time denoted as ‘ma’ ranges from 2 to 100ns. As long as we have
no page fault. The effective access time is equal to the memory access time. If however a

32
 OPERATING SYSTEM

page fault occurs we must first need the relevant page from the disk and then access the
desired word.
Let ‘p’ be the probability of a page fault (0<p<=1). We would expect ‘p’ to be close to 0 or
to expect a few page fault. The effective access time is equal to,
(1-p)*ma + p * page fault time

Page replacement:-
It means select a victim page in the main memory, replace that page with the required page
from the disk.

Page Replacement Algorithm:-

It selects the victim pages each OS has its own page replacement policy.
It is of five types:-
 First In First Out (FIFO)
 Least Recently Used (LRU)
 Optimal
 Least Frequently used (LFU)
 Most Frequently used (MFU)

FIFO:-

It replaces the page that has been in the memory longest. The oldest page will be at the head
of the queue. Whenever a page fault occurs the page of the top of the queue is made victim
and the new page is put at the tail of the queue.

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 4 4 4 0 0 0 7 7 7

0 0 0 3 3 3 2 2 2 1 1 1 0 0

1 1 1 0 0 0 3 3 3 2 2 2 1

FIFO Page-replacement algorithm

Limitation:-

It may often eject some pages that may be currently active. Such pages would need to be
moved in again in the near future.
If the system has global page replacement program having longest number of allocated pages
would have higher page fault rate, since the probability of oldest page belonging to this
program could be very high. This phenomenon is called Belady’s anomaly and it defines
intuition.

33
 OPERATING SYSTEM

LRU:-
The criterion of this algorithm is “Replace a page that has not been used for a longest period
of time”. This strategy is the “Page replacement algorithm looking backward in time rather
than forward”
The victim page is which has been used least recently.
One implementation of this algorithm could be by using a stack. Whenever a new page is
brought in, it is placed at the top of the stack also whenever a resident page is accessed it is
removed from its current position and moved to the top of the stack. Whenever a page is to
be replaced victim page chosen from the bottom of the stack.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 4 4 4 0 1 1 1

0 0 0 0 0 0 3 3 3 0 0

1 1 3 3 2 2 2 2 2 7

Optimal:- LRU Page-replacement algorithm

The criteria of this algorithm is “Replace a page that will not use for the longest period of time”
This algorithm should replace a page which is to be referenced in the most distance future.
Since it require knowledge of the future its ideal from is not practically realizable.
The significant of this algorithm is only theoretical.

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 7

0 0 0 0 4 0 0 0

1 1 3 3 3 1 1

Optimal Page-replacement algorithm

LFU:-
It selects a page for replacement if the page has not been used often in the past or replace
page that page has smallest count.
Frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3
1 1 1 1 1 1 1 3 3 1 1 1 1 1 1 1
2 2 3 3 3 2 2 2 2 2 2 4 5 6 7

MFU:-
The criteria of this algorithm are to replace page that has the maximum frequency count of all
pages. The implementation of this algorithm is fairly expensive.
34
 OPERATING SYSTEM

Thrashing:-

A process is said to be thrashing, if it spending more time in paging than in execution. For
example:- whenever a new page is brought in, a page that may be currently active has to be
sent out. The victim page would need to be brought is again shortly. This leads to sending in
and out of some set of pages, in a quick succession. Such a process could spent more time in
paging than executing. This phenomena is known as thrashing. This will result in a poor
through put of the system.
If the number of process submitted to the CPU for execution, are increased the CPU
utilization will also increases. But increasing the process continuously at a certain time the
CPU utilization falls sharply (the CPU treated this overload) and sometimes reaches to zero.
This situation is said to be “thrashing”.

Thrashing

CPU Utilization

0
Degree of multi programming

Safe, Unsafe and dead lock state spaces

Remedy of thrashing:-
The operating system has to swap out some of the active process, thus realizing some
occupied frames that can be made available to the other active process. When some of the
active processes are completed, the swapped out process can be swapped in and their
execution resumed.

Demand segmentation:-

It can also be used to provide virtual memory. Burroughs' computer systems have used
demand segmentation. The IBM OS/2 operating system also uses demand segmentation.
However, segment-replacement algorithms are more complex than are page-replacement
algorithms because the segments have variable sizes.

35
 OPERATING SYSTEM

MODULE-V
PART-1
DISK STRUCTURE
 Overview of Mass Storage Structure
 Disk Structure
 Disk Scheduling
 Disk Management
 Swap-Space Management
 RAID

Disk Structure
A hard disk is a collection of platters; each disk platter has a flat circular shape, like a
compact disk (CD).Common platter diameter range from 1.8 to 5.25 inches. The two surface
of a platter are covered with a magnetic material. We store information by recording it
magnetically on the platters.
A read/write head located just above each surface of every platter. The space of platter is
logically divided in to circular ‘Tracks’. The tacks are divided in to ‘Sectors’. The set of
tracks that are at one arm position forms a ‘Cylinder’. The heads are attached to a disk arm,
which all the head unit.

[Disk Structure]

36
 OPERATING SYSTEM

Seek time
The time required to reach the desired track by read/write head is the ‘seek time’. The seek
time consists of two key components. The internal startup time and the time taken to traverse
the cylinders. That has to cross once the access arm is up to speed. The linear formula for
seek time is
Ts =m* n+s
Where
Ts= Estimated seek time.
n=Number of tracks traversed.
m=Constant that dependent on the disk drive.
s=startup time.
Rotational delay
The time required to reach the desired sector by the read/write head is called rotational delay.
Generally the average rotational delay will be between 100 and 200m seconds.
Transfer time
The transfer time is depends on the rotation speed of the disk. The formula for transfer time is
T= B / R * N
Where
T= Transfer time
B=Number of bytes to be transferred.
N=number of bytes on track.
R=rotation speed in revolutions per second.
Thus the total average access time can be expressed as
Tu= Ts + 1 / 2R + B / RN where Ts is the average seek time.

Disk scheduling algorithms

There are number of disk scheduling algorithms available. Out of those 5 algorithms are
popular. We discuss these algorithms in this section. These are
1. First Come First Serve (FCFS) Scheduling
2. Shortest Seek Time First (SSTF) Scheduling
3. Scan Scheduling
4. C-Scan Scheduling
5. Look Scheduling
1. FCFS Scheduling:- The expansion of FCFS is first-come, first-served. It is simplest disk
scheduling algorithm of all .But it does not provide the fastest service. Consider for
example. A disk queue with requests for I/O to block on cylinders.
87, 170, 40, 150, 36,72,66,15

37
 OPERATING SYSTEM

In the order, If the disk head is initially 60. It will first move from 60 to 87, the 87 to
170,170 to 40,150,36,72,66 and finally to 66 to 15. Consider the figure for better
understanding for a total had movement of
(60 to 87 + 87 to 170 + 170 to 40 + 40 to 150 + 150 to 36+ 36 to 72 + 72 to 66 + 66 to 15)
=27 + 83 + 130 + 110 + 114 + 36 + 6 + 51
=557 cylinders.
The average head movements are 557/8=69.6 cylinders.
Queue is 87, 170, 40, 150, 36, 72, 66, 15 (head starts at 60)

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

87

170

40

150

36
72
66
15

FCFS Scheduling

The algorithm is very simple to implement. But the performance is not satisfactory, the
average had movements are very high.

2. SSTF Scheduling:- The expansion of SSTF is shortest seek time first. This algorithm
selects the request with the minimum seek time from the current head position. For
example consider the previous request queue (87, 170, 40, 150, 36, 72, 66, 15). The head
position initially is 60, the closest request to the head position is at cylinder 66. The
closest request to 66 to 72, the closest request to 72 is 87. Continue this process consider
the figure for better understanding.
Queue 87, 170, 40, 150, 36, 72, 66, 15 (head starts at 60)
The total head movements in this algorithm is
= (60 to 66)+ (66 to 72)+ (72 to 87)+ (87 to 40)+ (40 to 36)+ (36 to 15)+ (15 to 150)+
(150 to 170)
=6 + 6 + 15 + 37 + 4 + 21 + 135 + 20
=244 cylinders.
The average head movements are 244/8=30.5 cylinders.
Compare this algorithm with FCFS, it gives a substantial improvement in performance.
38
 OPERATING SYSTEM
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

66 72
87

40
36

15

150 170

SSTF Scheduling
3. SCAN Scheduling:- The scan algorithm is called ‘Elevator’ algorithm. In this the disk
arm starts at one end of the disk and moves towards the other end, while in the mean time
all requests are servicing until it gets other end of the disk. At the other end the direction
of head movement is reversed and servicing continuous. That’s why this algorithm is
called elevator algorithm. Consider our previous algorithm for better understanding.
Queue 87, 170, 40, 150, 36, 72, 66, 15
The head movements starts from 60th cylinder, assume that the direction towards outsides,
so the head will service 66, 72, 87, 150 and 170. At cylinder 180 the arm will reverse and
will move towards the other end of the disk. Servicing the request 36, 15 (consider the
figure). Now calculate the head movements.
Average movements= total number of head movements / number of requests.
= ((60 to 66) + (66 to 72) + (72 to 87) + (87 to 150)+ (150 to 170)+ (170 to 180)+ (180 to
36)+ (36 to 15))/8
= (6 + 6 +15 + 63 + 20 + 10 + 144 + 21) / 8
=285/8 cylinders.
=30.6 cylinders.
Compare this algorithm with FCFS; it gives a substantial improvement in performance.
But it is not better, compare with SSTF.

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

66 72
87

150 170

36
15

SCAN Scheduling
39
 OPERATING SYSTEM

4. C-SCAN Scheduling: - The main draw back in scan scheduling is the waiting time is not
uniformly. Some requests are waiting much time, some requests are servicing
immediately. We can overcome this draw back with c-scan (Circular Scan) scheduling
algorithm. It is designed to provide a more uniform wait time. In this algorithm moves
the head from one end to other end of the disk, servicing the request along the way.
When the head reaches the other end, it immediately returns to the begin of the disk,
without servicing any requests on the return trip (figure).
The algorithm treats the cylinders as circular list.
Queue 87, 170, 40, 150, 36, 72, 66, 15
Starting point 60.
Average movements= total number of head movements / number of requests.
Avg head movement=(6+6+15+63+20+29+199+15+21+4)/8 = 378/8 = 47.25

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

66 72
87

150 170

15
36 40

C-SCAN Scheduling

The average head movement in this algorithm is more than in the scan scheduling. But it
provides more uniform wait time.

5. Look Scheduling: - When the head reaches at the final request in one direction, it reverse
back to the other direction by servicing other request without reach the end of the disk.
Consider the figure for better understanding.
Queue 87, 170, 40, 150, 36, 72, 66, 15
Starting point 60.

40
 OPERATING SYSTEM

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

66 72
87

150 170

40
36
15

Look Scheduling

Average movements= total number of head movements / number of requests.

Average head movement = (6+6+15+63+20+130+4+21)/8 = 265/8 = 33.125

6. C-Look Scheduling: - In the previous algorithms (scan, C-scan) the disk arm moves across
the full width of disk. But in this algorithm the arm goes only as far as final request in each
direction. Then it reverses the direction immediately, without reach the end of the disk.
Consider the figure for better understanding.
Queue 87, 170, 40, 150, 36, 72, 66, 15
Starting point 60.

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

66 72
87

150 170

15 36 40

C-Look Scheduling

Average movements= total number of head movements / number of requests.

Avg head movement = (6+6+15+63+20+155+21+4)/8=290/8=36.25

41
 OPERATING SYSTEM

Disk Management:-
The operating system should perform some other activities related to disk management.
These involve initialization of the disk, booting from disk, and bad-block recovery etc.
Disk initialization:-
Disk comes as a rough magnetic media. In order to allow operations on disk, it should be
initialized. Three main steps of initialization are:
 Low-level formatting
 Partitioning
 Logical formatting
Low-level formatting:-Its purpose is to divide disk into sectors. Each sector is capable of
storing the same amount of byte, which is also known as block size. Sectors are separated
from each other by special header and trailer chunks of bits that are put to each sector during
the low-level formatting. No-doubt, that these bits introduce an overhead (wastage of storage
space). This overhead is big when the sector size is small. Therefore, low-level formatting
(usually done at factory) can be repeated manually to change the sector size (or block size).
Partitioning: - The operating system may need to record its own data structures on the disk.
This is done in two steps:- partitioning and logical formatting. Partitioning means that the
disk is partitioned into one or more groups.
Logical formatting
Its purpose is to make a file system on the disk. The operating system stores the file
management structures and directory table on the disk. Logical formatting step may be by
passed if all the applications on the computer use raw I/O disk access than using file access.
Swap-Space Management
It is another important task of the operating system. We know that virtual memory when
implemented using demand segmentation uses swap space on the disk. Therefore, the
optimized use of swap-space contributes a lot to the performance of virtual memory system.
Swap space may be carved out of the normal file system or more commonly, it can be in
separate disk partition.
Swap space Location
If the swap space is the large file within the file system, we can all the file operations like
create, rename, etc., to manipulate it. This is an easy implementation but suffers from
external fragmentation as it may leave unused space holes on the disk that cannot be further
used by a single process or a page. If swap-space is created in a separated disk partition, a
separate swap-space manager can be used to allocate or de-allocate the blocks. This manager
can use algorithms to optimize speed. The only problem with this approach is that it creates a
fixed amount of swap space during disk partition, which cannot be enhanced easily.
Swap-Space Size
The size of swap space depends upon the extent of its usage. Some systems may use swap
space to hold the entire process image whereas other may simply use it to hold paging that
have been pushed out of the main memory.

42
 OPERATING SYSTEM

RAID:
 RAID, an acronym for Redundant Arrays of Inexpensive Disks.
 It is a technology that provides increased storage reliability through redundancy,
combining multiple relatively low-cost, less-reliable disk drives components into a
logical unit where all drives in the array are interdependent.
 RAID is now used as computer data storage schemes that can divide and replicate
data among multiple disk drives.
 The schemes or architectures are named by the word RAID followed by a number
(e.g., RAID 0, RAID 1).
 The various designs of RAID systems involve two key goals:
 Increase data reliability
 Increase input/output performance.
 When multiple physical disks are set up to use RAID technology, they are said to be
in a RAID array. This array distributes data across multiple disks, but the array is
addressed by the operating system as one single disk. RAID can be set up to serve
several different purposes.
RAID Architecture:
It consists of different RAID levels as follows:
RAID Level 0:
RAID level 0 refers to disk arrays with striping at the level of blocks, but without any
redundancy (such as mirroring or parity bits).
RAID Level 1:
RAID level 1 refers to disk mirroring.
RAID Level 2:
RAID level 2 is also known as memory-style error-correcting code
RAID level 3:
RAID level 3, or bit-interleaved parity organization, improves on level 2 by noting that,
unlike memory systems, disk controllers can detect whether a sector has been read correctly,
so a single parity bit can be used for error correction, as well as for detection.
RAID Level 4:
RAID level 4, or block-interleaved parity organization, uses block-level striping, as in RAID
0, and in addition keeps a parity block on a separate disk for corresponding blocks from N
other disks.
RAID level 5:
RAID level 5, or block-interleaved distributed parity, differs from level 4 by spreading data
and parity among all N + 1 disk, rather than storing data in N disks and parity in one disk.
RAID Level 6:
RAID level 6, also called the P+Q redundancy scheme, is much like RAID level 5, but stores
extra redundant information to guard against multiple disk failures.
RAID level 0 + 1:
RAID level 0 + 1 refers to a combination of RAID levels 0 and 1. RAID 0 provides the
performance, while RAID 1 provides the reliability.

43
 OPERATING SYSTEM

MODULE-V
PART-2
STORAGE MANAGEMENT
 File System Concept
 Access Methods
 File System Structure
 File System Structure
 File System Implementation
 Directory implementation
 Efficiency and Performance
 Recovery
 NFS

Storage Management

The File concept:-

The OS provides a uniform logical view of information storage on various secondary storage
media like magnetic disks, magnetic tapes and optical disks. The uniform logical storage unit
is called File. OS maps the files onto secondary storage devices. A file could contain a
source program, an object program, an executable binary code, text, numerical data, records
of related data, graphics information or audio data etc. A file is the smallest allotment of
secondary storage device.
Example:-Disk, logically a file is a sequence of logical records i.e a sequence of bits and
bytes.

File System
The file system consists of two distinct sub-components:
 Collection of files, each storing related data.
 Directory Structure, which organizes and provides information about all the files.

At the lowest level, device drivers communicate directly with peripheral devices or their
controllers or channels. A device driver is responsible for starting I/O operations on a device
and processing the completion of I/O request. The next level is the ‘Basic file system’. It is
the interface with the environment outside of the computer system. The ‘basic I/O super
visor’ is responsible for all file I/O initiation and termination. ‘Logical I/O’ enables users and
applications to access records.

44
 OPERATING SYSTEM

File Organization:-
File Organization refers to the manner in which the records of a file are organized on the
secondary storage. Logically, a file is a set of logical records. It is allocated a disk storage
space in terms of physical blocks (block size normally 512 bytes). Last block of a file may
not be fully occupied, resulting in loss of some storage space, called Internal Fragmentation.
So, larger the block size, larger will be disk space lost due to internal fragmentation. There is
no way of recovering this loss.
The most common file-organization schemes are:
 Sequential
 Direct
 Indexed
 Partitioned
Sequential:-
The file records are stored strictly in the same order as they occur physically in the file.
Direct:-
The system supports random or direct access of any record in the file.
Indexed:-
The records are arranged in a logical sequence according to a key contained in each record.
Partitioned:-
This refers to a file of sequential sub-files. Each sequential sub-file is called a member of the
partitioned file.
Major Function of OS in respect of File System:-
1. Creation, manipulation and deletion of files and directories.
2. Protection of file system control
3. Controlled sharing of files.
4. Support backup and recovery of files.
5. Support encryption and decryption of sensitive files.

Directory Structure
Single Level Directory
This is simplest directory structure. All files are contained in the same directory structure.

Root Directory

A B C D

Single level directory

45
 OPERATING SYSTEM

Two level Directory

This solution can be used to create multiple user file Directories (UFDs),one for each user,
under a Master File Directory(MFD).The MFD is indexed by the user name or user account
number , to provide an access to the relevant UFD.

Root Directory

User 1 User 2 User 3

A B B A B C

A two level directory system

Tree Structure directory.

The two-level directory is in fact a two-level tree .The tree structured directory is a
generalization of the two-level Directory and it forms a tree of an arbitrary height. This
permits the users to create their own sub-directories. Each file in the system has a unique
access path name. Path name of a file is its unique identification.

Root Directory

User 1 User 2 User 3

Sub Directory A B Sub Directory

Sub-sub Sub-sub Sub-sub Sub-sub

Directory Directory Directory Directory

A B C D
A hierarchical directory system

46
 OPERATING SYSTEM

Acyclic Graph Directory

Suppose multiple users are working on a project, the project files can be stored in a common
sub-directory of the multiple users. This type directory is called Acyclic Graph Directory.
The common directory will be declared a shared directory. Same way, system may provide
shared files. However, the graph contains no cycles.

General Graph Directory

General graph directory permits cycles. One major disadvantage is that a poorly designed
search algorithm may get into infinite loop while searching for a file.

Root Directory

User 1 User 2 User 3

Sub Directory A B Sub Directory

Sub-sub Sub-sub Sub-sub Sub-sub

Directory Directory Directory Directory

A B C D

Graph directory structure

47
 OPERATING SYSTEM

Disk space allocation methods:

1. Contiguous allocation: - A file occupies a set of contiguous blocks on the disk.

Advantages
 Accessing is easy
 The number of disk seeks to access all blocks of a file is minimal, since the blocks
reside on same or neighboring tracks.
Disadvantages
 Finding space for a new file is time consuming.
 Subsequent extension of a file may become difficult.
 Suffers from external fragmentation. System may often need disk defragmentation to
recover the disk space rendered un-usual due to external fragmentation.
2. Linked allocation:-A file is a linked-list of disk blocks. The disk blocks may be
scattered all over the disk storage space. The file directory contains pointers to the first
and last blocks of a file. Each linked block contains pointer to the next block in the list.

0 1 2 3
File [Link]
START 3
4 5 6 7 END 15

8 9 10 11 The title is stored in blocks

3,6,1,8,9,15 in that order
12 13 14 15

Storage

Advantages
 This method does not suffer from external fragmentation. Only last block allotted to a
file may not fully occupied (internal fragmentation). So, disk storage space is
optimally utilized.

Disadvantages
 Accessing such files is more time consuming, since address of next block needs to be
determined.
 Number of disk seeks to access all blocks of a file may be large. Sophisticated disk
scheduling will be required to optimize the head movement during seeks.
 The allocated blocks cannot be accessed randomly, since the pointers to blocks are
scattered with the blocks.

48
 OPERATING SYSTEM

3. Indexed Allocation: - The method eliminates the problem of linked allocation that the
allocated blocks cannot be accessed directly or randomly. Indexed allocation solves the
problem by bringing all the pointers together in an index block. Each file has its own
index block, which is an array of disk block addresses. The directory contains the address
of the index block of each file. Main issue is to determine the size of index block. It has
to be chosen catering for largest files. However for small files, some entries would
remain vacant.
The problem can be solved by using:

(a) Linked index blocks:-An index block is normally one block size, for larger files,
more than one index blocks may be used by linking together the index blocks.

File
Index [Link]
0 1 2 3 Block 11

4 5 6 7
3
6
8 9 10 11
1
12 13 14 15
8
9
15
Storage

(b) Hierarchical indexing:-This method has first level index blocks pointing to a set of
second level index blocks, which in turn point to allocated disk blocks.

5
8
. 0 1 2 3
.
.
4 5 6 7
.
.
8 9 10 11 File [Link]
.
12 1st level
10 12 13 14 15 Index 6
.
.
. Storage

49
 OPERATING SYSTEM

(c) Index nodes (I-Nodes):-This scheme is used in UNIX. Each file has an I-Node
stored on the disk. When a file is opened, its I-Node is loaded form disk to main
memory. The I-Node contains file attributes and some addresses of the disk blocks
allocated to the file. For small files, addresses of all the allocated disk blocks are
accommodated in the I-Node itself. However, for medium and large sized files, it is
not possible to accommodate all the disk address in the I-Node itself.
I-NODE
Attributes
Pointers
to
Disk Block
Address Disk Blocks

Single Indirect Disk Block

Pointers Pointers

Double Indirect
Pointers

Attributes
Disk Block Pointers to
Address Disk Blocks

Single Indirect Disk Block

Pointers Addresses

Double Indirect
Pointers

I-NODE

Attributes

Pointers to
Disk Block Disk Blocks
Address

Disk Block
Single Indirect Addresses
Pointers

Disk Block
Double Indirect
Addresses
Pointers
I-NODE

50
 OPERATING SYSTEM

File Access Methods

1. Sequential Access:-
It is based on a tape-model of file. When a file opened, file pointer is positioned at the
beginning of file. When a block has been read, pointer automatically shifted to the next
record.
0 1 2 3 4

Movement of Pointer
BOF EOF
(Beginning of File) (End of File)
Next block
to be read
Advantages
 Simple implementation.

Disadvantages
 Sequential access is not efficient. Average access time of a record is equal to the time
to access half of the file.

2. Direct Access or Random Access or Relative Access:-

This access is possible, only if a file is made up of fixed-length logical records. A
read/write request will include a record number. The record numbers are kept sequential.
Such files are indexed by record number and support random or direct accessing of
records, jumping from one record to another forward or backward.

Fixed Length
Records

The pointer can be directly moved to

Pointer to The beginning of any record randomly
access
3. Indexed Access:-The records are arranged in a logical sequence according to a key
contained in each record. The system maintains an index containing the physical address
of certain records. By using the key attribute, the records can be indexed directly. This is
most commonly used method in DBMS files.

Key value
Key values=2
0
The key can be user-ID,
1 User-Name or any other
2 Key values=0
key attribute, which may
3 be unique

Records Indexed
by key value

51
 OPERATING SYSTEM

4. Indexed Sequential Access Method (ISAM):-

It used a small master index that points to disk blocks of a secondary index. The
secondary disk blocks in turn point to the actual disk blocks allocated to a file. The file is
kept sorted on a defined key. To find match for a key, we first make a binary search in
the master index table, which provides a block number of the secondary index. The
secondary block is read into memory and a binary is made in the secondary index to
determine address of the file block containing the key value. Finally, the block is
searched sequentially to determine the record containing the key value.

File [Link]
Master 10 0 1 2 3
Index
4 5 6 7
Master Pointer to secondary
Index Index 8 9 10 11

11 12 13 14 15

9 Disk Block
Pointers
Storage

Efficiency and Performance:-

Efficiency
 Inode
 Clustering
 pointers

inode:

The efficient use of disk space is heavily dependent on the disk allocation and directory
algorithms in use. For instance, UNIX inodes are preallocated on a partition. Even an
"empty" disk has a percentage of its space lost to inodes. However, by preallocating the
inodes and spreading them across the partition, we improve the file system's performance.
This improved performance is a result of the UNIX allocation and free-space algorithms,
which try to keep a file's data blocks near that file's inode block to reduce seek time.

Clustering:
It aids in file-seek and file-transfer performance at the cost of internal fragmentation. To
reduce this fragmentation, UNIX varies the cluster size as a file grows. Large clusters are
used where they can be filled, and small clusters are used for small files.
52
 OPERATING SYSTEM

Pointers:
Most systems use either 16- or 32-bit pointers throughout the operating system. These pointer
sizes limit the length of a file to either 216 (64 KB) or 232 bytes (4 GB). Some systems
implement 64-bit pointers to increase this limit to 264 bytes, which is a very large number
indeed. However, 64-bit pointers take more space to store, and in turn make the allocation
and free space-management methods use more disk space.

Performance
Once the basic file-system algorithms are selected, we can still improve performance in
several ways.
1. On-board cache:
Most disk controllers include local memory to form an on-board cache that is sufficiently
large to store entire tracks at a time. Once a seek is performed, the track is read into the disk
cache starting at the sector under the disk head (alleviating latency time). The disk controller
then transfers any sector requests to the operating system. Once blocks make it from the disk
controller into main memory, the operating system may cache the blocks there.
2. Disk cache:
Some systems maintain a separate section of main memory for a disk cache, where blocks
are kept under the assumption that they will be used again shortly.

3. Page cache:
The page cache uses virtual-memory techniques to cache file data as pages rather than as file
system-oriented blocks. Caching file data using virtual addresses is far more efficient than
caching through physical disk blocks.

4. Unified virtual memory:

Several systems, including Solaris, some new Linux releases, and Windows NT and 2000,
use page caching to cache both process pages and file data. This is known as unified virtual
memory.

Unified buffer cache:

Some versions of UNIX provide a unified buffer cache. Consider the two alternatives of
opening and accessing a file. One approach is to use memory mapping the second is to use
the standard system calls read and write.

Memory I/O using Memory I/O using

mapped I/O read () and write () mapped I/O read () and write ()

Page cache
buffer cache

buffer cache File system

File system
I/O without a unified buffer cache I/O using a unified buffer cache
53
 OPERATING SYSTEM

Double caching:
The memory mapping call requires using two caches-the page cache and buffer cache. A
memory mapping proceeds by reading in disk blocks from the file system and storing them in
the buffer cache. Because the virtual memory system cannot interface with the buffer cache,
the contents of the file in the buffer cache must be copied into the page cache. This situation
is known as double caching and requires caching file-system data twice

Recovery:
Files and directories are kept both in main memory and on disk, and care must be taken to
ensure that a system failure does not result in loss of data or in data inconsistency.
 Consistency Checking
 The consistency checker
 Backup and Restore

Consistency Checking:
Whenever the cause of corruption, a file system must first direct the problem and then correct
them. For detection, a scan of all the metadata on each file system can confirm or deny the
consistency of the system. At the start of any metadata change, a status bit is set to indicate
that the metadata is in flux. If all updates to the metadata complete successfully, the file
system can clear that bit. If, however, the status bit remains set, a consistency checker is run.

The consistency checker:

A systems program such as fsck in UNIX or chkdsk in windows-compares the data in the
directory structure with the data in the directory structure with the data blocks on disk and
tries to fix any inconsistencies it finds.

Backup and Restore:

System programs can be used to back up data from disk to another storage device, such as a
floppy disk, magnetic tape, optical disk, or other hard disk. To minimize the copying needed,
we can use information from each file’s directory entry. For instance, if the backup program
knows even the last backup of a file was done, and the file’s last write date in the directory
indicates that the file has not changed since that date and then the file does not need to be
copied again.

54
 OPERATING SYSTEM

Network file systems (NFS):

NFS is a good example of a widely used, well-implemented client-server network file system.
NFS is both an implementation and a specification of a software system for accessing remote
files across LANs (or even WANs).
The mount protocol establishes the initial logical connection between a server 1 and a client.
A mount operation includes the name of the remote directory to be mounted and the name of
the server machine storing it.
u: u:

user user

local local

dir1
dir1

Mounting in NFS (a) Mounts (b) Cascading mounts.

The NFS Protocol

The NFS protocol provides a set of RPCs for remote file operations.
The procedures support the following operations:
 Searching for a file within a directory
 Reading a set of directory entries
 Manipulating links and directories
 Accessing file attributes
 Reading and writing files

Client Server

System-calls interface

VFS Interface VFS Interface

Other types of UNIX file NFS NFS UNIX file

file system system client Server system

RPC/XDR RPC/XDR

disk disk
network

Schematic view of the NFS architecture

55