Module5

MODULE 5

DEADLOCKS

A process requests resources, 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.

SYSTEM MODEL

 A system consists of a finite number of resources to be distributed among a number of

competing processes. The resources are partitioned into several types, each consisting of
some number of identical instances. Memory space, CPU cycles, files, and I/0 devices
are examples of resource types.
 A process must request a resource before using it and must release the resource after
using it. A process may request as many resources as it requires carrying out its
designated task. The number of resources requested may not exceed the total number of
resources available in the system.

Under the normal mode of operation, a process may utilize a resource in only the following
sequence:
1. Request: The process requests the resource. If the request cannot be granted
immediately, then the requesting process must wait until it can acquire the resource.
2. Use: The process can operate on the resource.
3. Release: The process releases the resource.

A set of processes is in a deadlocked state when every process in the set is waiting for an event
that can be caused only by another process in the set. The events with which we are mainly
concerned here are resource acquisition and release. The resources may be either physical
resources or logical resources

To illustrate a deadlocked state, consider a system with three CD RW drives.

Suppose each of three processes holds one of these CD RW drives. If each process now
requests another drive, the three processes will be in a deadlocked state.
Each is waiting for the event "CD RW is released," which can be caused only by one of the
other waiting processes. This example illustrates a deadlock involving the same resource type.

1
 Module5

Deadlocks may also involve different resource types. For example, consider a system with one
printer and one DVD drive. Suppose that process Pi is holding the DVD and process Pj is
holding the printer. If Pi requests the printer and Pj requests the DVD drive, a deadlock occurs.

DEADLOCK CHARACTERIZATION

Necessary Conditions

A deadlock situation can arise if the following four conditions hold simultaneously in a system:

1. Mutual exclusion: At least one resource must be held in a non-sharable mode, that is,
only one process at a time can use the resource. If another process requests that resource,
the requesting process must be delayed until the resource has been released.

2. Hold and wait: A process must be holding at least one resource and waiting to acquire
additional resources that are currently being held by other processes.

3. No preemption: Resources cannot be preempted; that is, a resource can be released only
voluntarily by the process holding it, after that process has completed its task.

4. Circular wait: A set {P0, Pl, ... , Pn} of waiting processes must exist such that Po is
waiting for a resource held by P1, P1 is waiting for a resource held by P2, ... , Pn-1 is
waiting for a resource held by Pn and Pn is waiting for a resource held by Po.

Resource-Allocation Graph

Deadlocks can be described in terms of a directed graph called System Resource-Allocation

Graph

The graph consists of a set of vertices V and a set of edges E. The set of vertices V is
partitioned into two different types of nodes:
 P = {P1, P2, ...,Pn}, the set consisting of all the active processes in the system.
 R = {R1, R2, ..., Rm} the set consisting of all resource types in the system.

A directed edge from process Pi to resource type Rj is denoted by Pi → Rj it signifies that

process Pi has requested an instance of resource type Rj and is currently waiting for that
resource.
A directed edge from resource type Rj to process Pi is denoted by Rj → Pi it signifies that an
instance of resource type Rj has been allocated to process Pi.
 A directed edge Pi → Rj is called a Request Edge.
 A directed edge Rj → P i is called an Assignment Edge.

2
 Module5

Pictorially each process Pi as a circle and each resource type Rj as a rectangle. Since resource
type Rj may have more than one instance, each instance is represented as a dot within the
rectangle.
A request edge points to only the rectangle R j, whereas an assignment edge must also designate
one of the dots in the rectangle.

When process Pi requests an instance of resource type Rj, a request edge is inserted in the
resource-allocation graph. When this request can be fulfilled, the request edge is
instantaneously transformed to an assignment edge. When the process no longer needs access
to the resource, it releases the resource; as a result, the assignment edge is deleted.

The resource-allocation graph shown in Figure depicts the following situation.

The sets P, K and E:

 P = {P1, P2, P3}
 R= {R1, R2, R3, R4}
 E = {Pl →Rl, P2 → R3, Rl → P2, R2 → P2, R2 → P1, R3 → P3 }

Resource instances:
 One instance of resource type R1
 Two instances of resource type R2
 One instance of resource type R3
 Three instances of resource type R4

Process states:
 Process P1 is holding an instance of resource type R2 and is waiting for an instance of
resource type R1.
 Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an
instance of R3.
 Process P3 is holding an instance of R3.

3
 Module5

If the graph does contain a cycle, then a deadlock may exist.

 If each resource type has exactly one instance, then a cycle implies that a deadlock has
occurred. If the cycle involves only a set of resource types, each of which has only a
single instance, then a deadlock has occurred. Each process involved in the cycle is
deadlocked.
 If each resource type has several instances, then a cycle does not necessarily imply that
a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a
sufficient condition for the existence of deadlock.

To illustrate this concept, the resource-allocation graph depicted in below figure:

Suppose that process P3 requests an instance of resource type R2. Since no resource instance is
currently available, a request edge P3 → R2 is added to the graph. At this point, two minimal
cycles exist in the system:
1. P1 →R1 → P2 → R3 → P3 → R2→P1
2. P2 →R3 → P3 → R2 → P2

Figure: Resource-allocation graph with a deadlock.

Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is
held by process P3. Process P3 is waiting for either process P1 or process P2 to release resource
R2. In addition, process P1 is waiting for process P2 to release resource R1.

Consider the resource-allocation graph in below Figure. In this example also have a cycle:
P1→R1→P3→R2→P1

Figure: Resource-allocation graph with a cycle but no deadlock

4
 Module5

However, there is no deadlock. Observe that process P4 may release its instance of resource
type R2. That resource can then be allocated to P3, breaking the cycle.

METHODS FOR HANDLING DEADLOCKS

The deadlock problem can be handled in one of three ways:

1. Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a
deadlocked state.
2. Allow the system to enter a deadlocked state, detect it, and recover.
3. Ignore the problem altogether and pretend that deadlocks never occur in the system.

To ensure that deadlocks never occur, the system can use either deadlock prevention or a
deadlock-avoidance scheme.

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

Deadlock-avoidance requires that the operating system be given in advance additional

information concerning which resources a process will request and use during its lifetime. With
this additional knowledge, it can decide for each request whether or not the process should
wait. To decide whether the current request can be satisfied or must be delayed, the system
must consider the resources currently available, the resources currently allocated to each
process, and the future requests and releases of each process

If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm,

then a deadlock situation may arise. In this environment, the system can provide an algorithm
that examines the state of the system to determine whether a deadlock has occurred and an
algorithm to recover from the deadlock.

In the absence of algorithms to detect and recover from deadlocks, then the system is in a
deadlock state yet has no way of recognizing what has happened. In this case, the undetected
deadlock will result in deterioration of the system's performance, because resources are being
held by processes that cannot run and because more and more processes, as they make requests
for resources, will enter a deadlocked state. Eventually, the system will stop functioning and
will need to be restarted manually.

5
 Module5

DEADLOACK PREVENTION

Deadlock can be prevented by ensuring that at least one of the four necessary conditions cannot
hold.

Mutual Exclusion
 The mutual-exclusion condition must hold for non-sharable resources. Sharable
resources, do not require mutually exclusive access and thus cannot be involved in a
deadlock.
 Ex: Read-only files are example of a sharable resource. If several processes attempt to
open a read-only file at the same time, they can be granted simultaneous access to the
file. A process never needs to wait for a sharable resource.
 Deadlocks cannot prevent by denying the mutual-exclusion condition, because some
resources are intrinsically non-sharable.

Hold and Wait

To ensure that the hold-and-wait condition never occurs in the system, then guarantee that,
whenever a process requests a resource, it does not hold any other resources.
 One protocol that can be used requires each process to request and be allocated all its
resources before it begins execution.
 Another protocol allows a process to request resources only when it has none. A process
may request some resources and use them. Before it can request any additional
resources, it must release all the resources that it is currently allocated.

Ex:
 Consider a process that copies data from a DVD drive to a file on disk, sorts the file, and
then prints the results to a printer. If all resources must be requested at the beginning of
the process, then the process must initially request the DVD drive, disk file, and printer.
It will hold the printer for its entire execution, even though it needs the printer only at
the end.
 The second method allows the process to request initially only the DVD drive and disk
file. It copies from the DVD drive to the disk and then releases both the DVD drive and
the disk file. The process must then again request the disk file and the printer. After
copying the disk file to the printer, it releases these two resources and terminates.

The two main disadvantages of these protocols:

1. Resource utilization may be low, since resources may be allocated but unused for a long
period.
2. Starvation is possible.

6
 Module5

No Preemption
The third necessary condition for deadlocks is that there be no preemption of resources that
have already been allocated.

To ensure that this condition does not hold, the following protocols can be used:
 If a process is holding some resources and requests another resource that cannot be
immediately allocated to it, then all resources the process is currently holding are
preempted.
 The preempted resources are added to the list of resources for which the process is
waiting. The process will be restarted only when it can regain its old resources, as well
as the new ones that it is requesting.

If a process requests some resources, first check whether they are available. If they are, allocate
them.
If they are not available, check whether they are allocated to some other process that is waiting
for additional resources. If so, preempt the desired resources from the waiting process and
allocate them to the requesting process.
If the resources are neither available nor held by a waiting process, the requesting process must
wait. While it is waiting, some of its resources may be preempted, but only if another process
requests them.
A process can be restarted only when it is allocated the new resources it is requesting and
recovers any resources that were preempted while it was waiting.

Circular Wait
One way to ensure that this condition never holds is to impose a total ordering of all resource
types and to require that each process requests resources in an increasing order of enumeration.

To illustrate, let R = {R1, R2, ... , Rm} be the set of resource types. Assign a unique integer
number to each resource type, which allows to compare two resources and to determine
whether one precedes another in ordering. Formally, it defined as a one-to-one function
F: R ->N, where N is the set of natural numbers.

Example: if the set of resource types R includes tape drives, disk drives, and printers, then the
function F might be defined as follows:
F (tape drive) = 1
F (disk drive) = 5
F (printer) = 12

Now consider the following protocol to prevent deadlocks. Each process can request resources
only in an increasing order of enumeration. That is, a process can initially request any number
of instances of a resource type -Ri. After that, the process can request instances of resource type
Rj if and only if F(Rj) > F(Ri).

7
 Module5

DEADLOCK AVOIDANCE

 To avoid deadlocks an additional information is required about how resources are to be

requested. With the knowledge of the complete sequence of requests and releases for
each process, the system can decide for each request whether or not the process should
wait in order to avoid a possible future deadlock
 Each request requires that in making this decision the system consider the resources
currently available, the resources currently allocated to each process, and the future
requests and releases of each process.
 The various algorithms that use this approach differ in the amount and type of
information required. The simplest model requires that each process declare the
maximum number of resources of each type that it may need. Given this a priori
information, it is possible to construct an algorithm that ensures that the system will
never enter a deadlocked state. Such an algorithm defines the deadlock-avoidance
approach.

Safe State

 Safe state: A state is safe if the system can allocate resources to each process (up to its
maximum) in some order and still avoid a deadlock. A system is in a safe state only if
there exists a safe sequence.

 Safe sequence: A sequence of processes <P1, P2, ... , Pn> is a safe sequence for the
current allocation state if, for each Pi, the resource requests that Pi can still make can be
satisfied by the currently available resources plus the resources held by all Pj, with j <i.

In this situation, if the resources that Pi needs are not immediately available, then Pi can wait
until all Pj have finished. When they have finished, Pi can obtain all of its needed resources,
complete its designated task, return its allocated resources, and terminate. When Pi terminates,
Pi+1 can obtain its needed resources, and so on. If no such sequence exists, then the system
state is said to be unsafe.

A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state. Not all
unsafe states are deadlocks as shown in figure. An unsafe state may lead to a deadlock. As long
as the state is safe, the operating system can avoid unsafe states

8
 Module5

Figure: Safe, unsafe, and deadlocked state spaces.

Resource-Allocation-Graph Algorithm

 If a resource-allocation system has only one instance of each resource type, then a
variant of the resource-allocation graph is used for deadlock avoidance.
 In addition to the request and assignment edges, a new type of edge is introduced, called
a claim edge.
 A claim edge Pi ->Rj indicates that process Pi may request resource Rj at some time in
the future. This edge resembles a request edge in direction but is represented in the
graph by a dashed line.
 When process Pi requests resource Rj, the claim edge Pi ->Rj is converted to a request
edge. When a resource Rj is released by Pi the assignment edge Rj->Pi is reconverted to
a claim edge Pi->Rj.

Figure: Resource-allocation graph for deadlock avoidance.

Note that the resources must be claimed a priori in the system. That is, before process Pi starts
executing, all its claim edges must already appear in the resource-allocation graph.
We can relax this condition by allowing a claim edge Pi ->Rj to be added to the graph only if
all the edges associated with process Pi are claim edges.

Now suppose that process Pi requests resource Rj. The request can be granted only if
converting the request edge Pi ->Rj to an assignment edge Rj->Pi does not result in the
formation of a cycle in the resource-allocation graph.

9
 Module5

There is need to check for safety by using a cycle-detection algorithm. An algorithm for
detecting a cycle in this graph requires an order of n2 operations, where n is the number of
processes in the system.
 If no cycle exists, then the allocation of the resource will leave the system in a safe state.
 If a cycle is found, then the allocation will put the system in an unsafe state. In that case,
process Pi will have to wait for its requests to be satisfied.

To illustrate this algorithm, consider the resource-allocation graph as shown above. Suppose
that P2 requests R2. Although R2 is currently free, we cannot allocate it to P2, since this action
will create a cycle in the graph.
A cycle, indicates that the system is in an unsafe state. If P1 requests R2, and P2 requests R1,
then a deadlock will occur.

Figure: An unsafe state in a resource-allocation graph

Banker's Algorithm

The Banker’s algorithm is applicable to a resource allocation system with multiple instances of
each resource type.
 When a new process enters the system, it must declare the maximum number of
instances of each resource type that it may need. This number may not exceed the total
number of resources in the system.
 When a user requests a set of resources, the system must determine whether the
allocation of these resources will leave the system in a safe state. If it will, the resources
are allocated; otherwise, the process must wait until some other process releases enough
resources.

10
 Module5

To implement the banker's algorithm the following data structures are used.

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

Available: 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 available.

Max: An n x m matrix defines the maximum demand of each process. If Max [i,j] = k, then
process Pi may request at most k instances of resource type Rj

Allocation: An n x m matrix defines the number of resources of each type currently allocated to
each process. If Allocation[i,j] = k then Pi is currently allocated k instances of 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 Rj to complete its task.

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

Safety Algorithm

The algorithm for finding out whether or not a system is in a safe state. This algorithm can be
described as follows:

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 an index i such that both:

(a) Finish[i] = false
(b) Needi Work
If no such i exists, go to step 4

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

This algorithm may require an order of m x n2 operations to determine whether a state is safe.

11
 Module5

Resource-Request Algorithm

The algorithm for determining whether requests can be safely granted.

Let Requesti be the request vector for process Pi. If Requesti [j] == k, then process Pi wants k
instances of resource type Rj. When a request for resources is made by process Pi, the following
actions are taken:

1. If RequestiNeedigo 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. Have the system 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

Example

Consider a system with five processes Po through P4 and three resource types A, B, and C.
Resource type A has ten instances, resource type B has five instances, and resource type C has
seven instances. Suppose that, at time T0the following snapshot of the system has been taken:

12
 Module5

The content of the matrix Need is defined to be Max - Allocation

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

Suppose now that process P1 requests one additional instance of resource type A and two
instances of resource type C, so Request1 = (1,0,2). Decide whether this request can be
immediately granted.

Check that Request  Available

(1,0,2)  (3,3,2)  true

Then pretend that this request has been fulfilled, and the following new state is arrived.

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

13
 Module5

DEADLOCK DETECTION
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm,
then a deadlock situation may occur. In this environment, the system may provide:
 An algorithm that examines the state of the system to determine whether a deadlock has
occurred
 An algorithm to recover from the deadlock

Single Instance of Each Resource Type

 If all resources have only a single instance, then define a deadlock detection algorithm
that uses a variant of the resource-allocation graph, called a wait-for graph.
 This graph is obtained from the resource-allocation graph by removing the resource
nodes and collapsing the appropriate edges.
 An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj
to release a resource that Pi needs. An edge Pi → Pj exists in a wait-for graph if and only
if the corresponding resource allocation graph contains two edges Pi →Rq and Rq→Pi for
some resource Rq.

Example: In below Figure, a resource-allocation graph and the corresponding wait-for graph is
presented.

Figure: (a) Resource-allocation graph. (b) Corresponding wait-for graph.

 A deadlock exists in the system if and only if the wait-for graph contains a cycle. To
detect deadlocks, the system needs to maintain the wait-for graph and periodically
invoke an algorithm that searches for a cycle in the graph.
 An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is
the number of vertices in the graph.

14
 Module5

Several Instances of a Resource Type

A deadlock detection algorithm that is applicable to several instances of a resource type. The
algorithm employs several time-varying data structures that are similar to those used in the
banker's algorithm.

 Available: A vector of length m indicates the number of available resources of each

type.
 Allocation: Ann 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[i][j]
equals k, then process P; is requesting k more instances of resource type Rj.

Algorithm:

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

(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi 0, then Finish[i] = false;
otherwise, Finish[i] = true

2. Find an index isuch that both:

(a) Finish[i] == false
(b)RequestiWork

If no such i exists, go to step 4

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

Example of Detection Algorithm

Consider a system with five processes Po through P4 and three resource types A, B, and C.
Resource type A has seven instances, resource type B has two instances, and resource type C
has six instances. Suppose that, at time T0, the following resource-allocation state:

15
 Module5

After executing the algorithm, Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for
all i
Suppose now that process P2 makes one additional request for an instance of type C. The
Request matrix is modified as follows:

The system is now deadlocked. Although we can reclaim the resources held by process Po, the
number of available resources is not sufficient to fulfill the requests of the other processes.
Thus, a deadlock exists, consisting of processes P1, P2, P3, and P4.

Detection-Algorithm Usage

The detection algorithm can be invoked on two factors:

1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock when it happens?

If deadlocks occur frequently, then the detection algorithm should be invoked frequently.
Resources allocated to deadlocked processes will be idle until the deadlock can be broken.

If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph
and so we would not be able to tell which of the many deadlocked processes “caused” the
deadlock.

16
 Module5

RECOVERY FROM DEADLOCK

The system recovers from the deadlock automatically. There are two options for breaking a
deadlock one is simply to abort one or more processes to break the circular wait. The other is to
preempt some resources from one or more of the deadlocked processes.

Process Termination
To eliminate deadlocks by aborting a process, use one of two methods. In both methods, the
system reclaims all resources allocated to the terminated processes.

1. Abort all deadlocked processes: This method clearly will break the deadlock cycle, but
at great expense; the deadlocked processes may have computed for a long time, and the
results of these partial computations must be discarded and probably will have to be
recomputed later.
2. Abort one process at a time until the deadlock cycle is eliminated: This method
incurs considerable overhead, since after each process is aborted, a deadlock-detection
algorithm must be invoked to determine whether any processes are still deadlocked.

If the partial termination method is used, then we must determine which deadlocked process (or
processes) should be terminated. Many factors may affect which process is chosen, including:

1. What the priority of the process is

2. How long the process has computed and how much longer the process will compute
before completing its designated task
3. How many and what types of resources the process has used.
4. How many more resources the process needs in order to complete
5. How many processes will need to be terminated?
6. Whether the process is interactive or batch
Resource Preemption

To eliminate deadlocks using resource preemption, we successively preempt some resources

from processes and give these resources to other processes until the deadlock cycle is broken.
If preemption is required to deal with deadlocks, then three issues need to be addressed:

1. Selecting a victim. Which resources and which processes are to be preempted? As in

process termination, we must determine the order of preemption to minimize cost. Cost
factors may include such parameters as the number of resources a deadlocked process is
holding and the amount of time the process has thus far consumed during its execution.
2. Rollback. If we preempt a resource from a process, what should be done with that
process? Clearly, it cannot continue with its normal execution; it is missing some needed
resource. We must roll back the process to some safe state and restart it from that state.
Since it is difficult to determine what a safe state is, the simplest solution is a total
rollback: abort the process and then restart it.
3. Starvation. How do we ensure that starvation will not occur? That is, how can we
guarantee that resources will not always be preempted from the same process?

17
 Module5

SECONDARY STORAGE STRUCTURES

OVERVIEW OF MASS-STORAGE STRUCTURE

Magnetic Disks

 Magnetic disks provide the bulk of secondary storage for modern computer systems.
 Each disk platter has a flat circular shape, like a CD. Common platter diameters range
from 1.8 to 5.25 inches.
 The two surfaces of a platter are covered with a magnetic material. The information
stored by recording it magnetically on the platters.

Figure: Moving-head disk mechanism

 The surface of a platter is logically divided into circular tracks, which are subdivided
into sectors. Sector is the basic unit of storage. The set of tracks that are at one arm
position makes up a cylinder.
 The number of cylinders in the disk drive equals the number of tracks in each platter.
 There may be thousands of concentric cylinders in a disk drive, and each track may
contain hundreds of sectors.
o Seek Time:-Seek time is the time required to move the disk arm to the required
track.
o Rotational Latency (Rotational Delay):- Rotational latency is the time taken for
the disk to rotate so that the required sector comes under the r/w head.
o Positioning time or random access time is the summation of seek time and
rotational delay.
o Disk Bandwidth:- Disk bandwidth is the total number of bytes transferred divided
by total time between the first request for service and the completion of last

18
 Module5

transfer.
o Transfer rate is the rate at which data flow between the drive and the computer.
As the disk head flies on an extremely thin cushion of air, the head will make contact with the
disk surface. Although the disk platters are coated with a thin protective layer, sometimes the
head will damage the magnetic surface. This accident is called a head crash.

Magnetic Tapes

 Magnetic tape is a secondary-storage medium. It is a permanent memory and can hold

large quantities of data.
 The time taken to access data (access time) is large compared with that of magnetic disk,
because here data is accessed sequentially.
 When the nth data has to be read, the tape starts moving from first and reaches the n th
position and then data is read from nth position. It is not possible to directly move to the
nth position. So tapes are used mainly for backup, for storage of infrequently used
information.
 A tape is kept in a spool and is wound or rewound past a read-write head. Moving to the
correct spot on a tape can take minutes, but once positioned, tape drives can write data at
speeds comparable to disk drives.

DISK STRUCTURE

 Modern disk drives are addressed as a large one-dimensional array. The one-
dimensional array of logical blocks is mapped onto the sectors of the disk sequentially.
 Sector 0 is the first sector of the first track on the outermost cylinder. The mapping
proceeds in order through that track, then through the rest of the tracks in that cylinder,
and then through the rest of the cylinders from outermost to innermost.

The disk structure (architecture) can be of two types –

1. Constant Linear Velocity (CLV)
2. Constant Angular Velocity (CAV)
1. CLV – The density of bits per track is uniform. The farther a track is from the center of
the disk, the greater its length, so the more sectors it can hold. As we move from outer
zones to inner zones, the number of sectors per track decreases. This architecture is used
in CD-ROM and DVD-ROM.

2. CAV – There is same number of sectors in each track. The sectors are densely packed in
the inner tracks. The density of bits decreases from inner tracks to outer tracks to keep
the data rate constant.

19
 Module5

DISK ATTACHMENT

Computers can access data in two ways.

1. via I/O ports (or host-attached storage)
2. via a remote host in a distributed file system ( or network-attached storage)

1. Host-Attached Storage:

 Host-attached storage is storage accessed through local I/O ports.

 Example: the typical desktop PC uses an I/O bus architecture called IDE or ATA.
This architecture supports a maximum of two drives per I/O bus.
 The other cabling systems are – SATA (Serially Attached Technology Attachment),
SCSI (Small Computer System Interface) and fiber channel (FC).
 SCSI is a bus architecture. Its physical medium is usually a ribbon cable. FC is a
high- speed serial architecture that can operate over optical fiber or over a four-
conductor copper cable. An improved version of this architecture is the basis of
storage-area networks (SANs).

2. Network-Attached Storage

 A network-attached storage (NAS) device is a special-purpose storage system that is

accessed remotely over a network as shown in the figure.
 Clients access network-attached storage via a remote-procedure-call interface. The
remote procedure calls (RPCs) are carried via TCP or UDP over an IP network
usually the same local-area network (LAN) carries all data traffic to the clients.
 Network- attached storage provides a convenient way for all the computers on a
LAN to share a pool of storage files.

20
 Module5

3. Storage Area Network (SAN)

 A storage-area network (SAN) is a private network connecting servers and storage

units.
 The power of a SAN lies in its flexibility. Multiple hosts and multiple storage arrays
can attach to the same SAN, and storage can be dynamically allocated to hosts.
 A SAN switch allows or prohibits access between the hosts and the storage. Fiber
Chanel is the most common SAN interconnect.

DISK SCHEDULING

Different types of disk scheduling algorithms are as follows:

1. FCFS (First Come First Serve)
2. SSTF (Shortest Seek Time First)
3. SCAN (Elevator)
4. C-SCAN
5. LOOK
6. C-LOOK
7.
1. FCFS scheduling algorithm:
This is the simplest form of disk scheduling algorithm. This services the request in the order
they are received. This algorithm is fair but do not provide fastest service. It takes no special
care to minimize the overall seek time.
Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14,

21
 Module5

124, 65, 67

If the disk head is initially at 53, it will first move from 53 to 98 then to 183 and then to 37,
122, 14, 124, 65, 67 for a total head movement of 640 cylinders. The wild swing from 122
to 14 and then back to 124 illustrates the problem with this schedule.

2. SSTF (Shortest Seek Time First) algorithm:

This selects the request with minimum seek time from the current head position. SSTF
chooses the pending request closest to the current head position.
Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14,
124, 65, 67

If the disk head is initially at 53, the closest is at cylinder 65, then 67, then 37 is closer than
98 to 67. So it services 37, continuing we service 14, 98, 122, 124 and finally 183. The total
head movement is only 236 cylinders. SSTF is a substantial improvement over FCFS, it is
not optimal.

22
 Module5

3. SCAN algorithm:
In this the disk arm starts moving towards one end, servicing the request as it reaches each
cylinder until it gets to the other end of the disk. At the other end, the direction of the head
movement is reversed and servicing continues. The initial direction is chosen depending
upon the direction of the head.
Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14,
124, 65, 67

If the disk head is initially at 53 and if the head is moving towards the outer track, it
services 65, 67, 98, 122, 124 and 183. At cylinder 199 the arm will reverse and will move
towards the other end of the disk servicing 37 and then 14. The SCAN is also called as
elevator algorithm
4. C-SCAN (Circular scan) algorithm:
C-SCAN is a variant of SCAN designed to provide a more uniform wait time.
Like SCAN, C-SCAN moves the head from end of the disk to the other servicing the
request along the way. When the head reaches the other end, it immediately returns to the
beginning of the disk, without servicing any request on the return.
Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14,
124, 65, 67.

23
 Module5

If the disk head is initially at 53 and if the head is moving towards the outer track, it
services 65, 67, 98, 122, 124 and 183. At cylinder 199 the arm will reverse and will move
immediately towards the other end of the disk, then changes the direction of head and serves
14 and then 37.
Note: If the disk head is initially at 53 and if the head is moving towards track 0, it services
37 and 14 first. At cylinder 0 the arm will reverse and will move immediately towards the
other end of the disk servicing 65, 67, 98, 122, 124 and 183.

5. Look Scheduling algorithm:

Look and C-Look scheduling are different version of SCAN and C-SCAN respectively.
Here the arm goes only as far as the final request in each direction. Then it reverses, without
going all the way to the end of the disk. The Look and C-Look scheduling look for a request
before continuing to move in a given direction.
Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14,
124, 65, 67

Figure: C-LOOK disk scheduling.

If the disk head is initially at 53 and if the head is moving towards the outer track, it
services 65, 67, 98, 122, 124 and 183. At the final request 183, the arm will reverse and will
move towards the first request 14 and then serves 37.

24
 Module5

SELECTION OF A DISK-SCHEDULING ALGORITHM

 SSTF is commonly used and it increases performance over FCFS.

 SCAN and C-SCAN algorithm is better for a heavy load on disk. SCAN and C-SCAN
have less starvation problem.
 SSTF or Look is a reasonable choice for a default algorithm.
 Selection of disk scheduling algorithm is influenced by the file allocation method, if
contiguous file allocation is chosen, then FCFS is best suitable, because the files are
stored in contiguous blocks and there will be limited head movements required.
 A linked or indexed file may include blocks that are widely scattered on the disk,
resulting in greater head movement.
 The location of directories and index blocks is also important. Since every file must be
opened to be used, and opening a file requires searching the directory structure, the
directories will be accessed frequently.
 Suppose that a directory entry is on the first cylinder and a file's data are on the final
cylinder. The disk head has to move the entire width of the disk. If the directory entry
were on the middle cylinder, the head would have to move, at most, one-half the width.
Caching the directories and index blocks in main memory can also help to reduce the
disk-arm movement, particularly for read requests.

25