Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any other process

requests this resource, then that process must wait for the resource to be released.
Hold and Wait - A process must be simultaneously holding at least one resource and waiting for at least
one resource that is currently being held by some other process.
No preemption - Once a process is holding a resource ( i.e. once its request has been granted ), then that
resource cannot be taken away from that process until the process voluntarily releases it.
Circular Wait - A set of processes { P0, P1, P2, . . ., PN } must exist such that every P[ i ] is waiting for
P[ ( i + 1 ) % ( N + 1 ) ]. ( Note that this condition implies the hold-and-wait condition, but it is easier to
deal with the conditions if the four are considered separately. )

Resource-Allocation Graph
In some cases deadlocks can be understood more clearly through the use of Resource-Allocation
Graphs, having the following properties:
*A set of resource categories, { R1, R2, R3, . . ., RN }, which appear as square nodes on the
graph. Dots inside the resource nodes indicate specific instances of the resource. ( E.g. two dots might
represent two laser printers. )
*A set of processes, { P1, P2, P3, . . ., PN }
*Request Edges - A set of directed arcs from Pi to Rj, indicating that process Pi has requested Rj,
and is currently waiting for that resource to become available.
*Assignment Edges - A set of directed arcs from Rj to Pi indicating that resource Rj has been
allocated to process Pi, and that Pi is currently holding resource Rj.
Note that a request edge can be converted into an assignment edge by reversing the direction of the arc
when the request is granted. ( However note also that request edges point to the category box, whereas
assignment edges emanate from a particular instance dot within the box. )
For example:

91
*If a resource-allocation graph contains no cycles, then the system is not deadlocked. ( When looking for
cycles, remember that these are directed graphs. ) See the example in Figure 7.2 above.

*If a resource-allocation graph does contain cycles AND each resource category contains only a single
instance, then a deadlock exists.
*If a resource category contains more than one instance, then the presence of a cycle in the resource-
allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for
example, Figures 7.3 and 7.4 below:

Fig: Resource Allocation Graph with cycle

3.3.3. Methods for Handling Deadlocks

Generally speaking there are three ways of handling deadlocks:

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

In order to avoid deadlocks, the system must have additional information about all processes. In
particular, the system must know what resources a process will or may request in the future. ( Ranging
from a simple worst-case maximum to a complete resource request and release plan for each process,
depending on the particular algorithm. )
Deadlock detection is fairly straightforward, but deadlock recovery requires either aborting
processes or preempting resources, neither of which is an attractive alternative.

If deadlocks are neither prevented nor detected, then when a deadlock occurs the system will
gradually slow down, as more and more processes become stuck waiting for resources currently held by

92
the deadlock and by other waiting processes. Unfortunately this slowdown can be indistinguishable from
a general system slowdown when a real-time process has heavy computing needs.

3.3.4. Deadlock Prevention

Deadlocks can be prevented by preventing at least one of the four required conditions:
Mutual Exclusion
Shared resources such as read-only files do not lead to deadlocks.
Unfortunately some resources, such as printers and tape drives, require exclusive access by a single
process.
Hold and Wait
To prevent this condition processes must be prevented from holding one or more resources while
simultaneously waiting for one or more others. There are several possibilities for this:

i. Require that all processes request all resources at one time. This can be wasteful of system
resources if a process needs one resource early in its execution and doesn't need some other
resource until much later.
ii. Require that processes holding resources must release them before requesting new resources, and
then re-acquire the released resources along with the new ones in a single new request. This
can be a problem if a process has partially completed an operation using a resource and then
fails to get it re-allocated after releasing it.
iii. Either of the methods described above can lead to starvation if a process requires one or more
popular resources.
No Preemption
Preemption of process resource allocations can prevent this condition of deadlocks, when it is possible.
i. One approach is that if a process is forced to wait when requesting a new resource, then all other
resources previously held by this process are implicitly released, ( preempted ), forcing this process to re-
acquire the old resources along with the new resources in a single request, similar to the previous
discussion.
ii. Another approach is that when a resource is requested and not available, then the system looks to see
what other processes currently have those resources and are themselves blocked waiting for some other
resource. If such a process is found, then some of their resources may get preempted and added to the list
of resources for which the process is waiting.
iii. Either of these approaches may be applicable for resources whose states are easily saved and restored,
such as registers and memory, but are generally not applicable to other devices such as printers and tape
drives.
Circular Wait
i. One way to avoid circular wait is to number all resources, and to require that processes request
resources only in strictly increasing ( or decreasing ) order.
ii. In other words, in order to request resource Rj, a process must first release all Ri such that i >= j.
iii. One big challenge in this scheme is determining the relative ordering of the different resources

Deadlock Avoidance
The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by preventing
at least one of the aforementioned conditions.
This requires more information about each process, AND tends to lead to low device utilization. ( I.e. it is

93
a conservative approach. )
In some algorithms the scheduler only needs to know the maximum number of each resource that a
process might potentially use. In more complex algorithms the scheduler can also take advantage of the
schedule of exactly what resources may be needed in what order.
When a scheduler sees that starting a process or granting resource requests may lead to future deadlocks,
then that process is just not started or the request is not granted.
A resource allocation state is defined by the number of available and allocated resources, and the
maximum requirements of all processes in the system.
Safe State
i. A state is safe if the system can allocate all resources requested by all processes ( up to their stated
maximums ) without entering a deadlock state.
ii. More formally, a state is safe if there exists a safe sequence of processes { P0, P1, P2, ..., PN } such
that all of the resource requests for Pi can be granted using the resources currently allocated to Pi and all
processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and free up their resources, then Pi will
be able to finish also, using the resources that they have freed up. )
iii. If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock. (
All safe states are deadlock free, but not all unsafe states lead to deadlocks. )

Fig: Safe, unsafe, and deadlocked state spaces.

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

Maximum Needs Current Allocation

P0 10 5
P1 4 2
P2 9 2

94
 i: What happens to the above table if process P2 requests and is granted one more tape drive?
ii. Key to the safe state approach is that when a request is made for resources, the request is granted only
if the resulting allocation state is a safe one.

Resource-Allocation Graph Algorithm

i. If resource categories have only single instances of their resources, then deadlock states can be detected
by cycles in the resource-allocation graphs.
ii. In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation graph
with claim edges, noted by dashed lines, which point from a process to a resource that it may request in
the future.
iii. In order for this technique to work, all claim edges must be added to the graph for any particular
process before that process is allowed to request any resources. ( Alternatively, processes may only make
requests for resources for which they have already established claim edges, and claim edges cannot be
added to any process that is currently holding resources. )
iv. When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly when
a resource is released, the assignment reverts back to a claim edge.
v. This approach works by denying requests that would produce cycles in the resource-allocation graph,
taking claim edges into effect.
Consider for example what happens when process P2 requests resource R2:

Fig: Resource allocation graph for dead lock avoidance

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

Fig: An Unsafe State in a Resource Allocation Graph

95
 Banker's Algorithm
i. For resource categories that contain more than one instance the resource-allocation graph
method does not work, and more complex ( and less efficient ) methods must be chosen.
ii. The Banker's Algorithm gets its name because it is a method that bankers could use to assure
that when they lend out resources they will still be able to satisfy all their clients. ( A banker
won't loan out a little money to start building a house unless they are assured that they will later
be able to loan out the rest of the money to finish the house. )
iii. When a process starts up, it must state in advance the maximum allocation of resources it may
request, up to the amount available on the system.
iv. When a request is made, the scheduler determines whether granting the request would leave
the system in a safe state. If not, then the process must wait until the request can be granted
safely.
Data Structures for the Banker’s Algorithm

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

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

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

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

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

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

Safety Algorithm

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

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

2. Find and i such that both:

(a) Finish [i] = false

(b) Needi <= Work

If no such i exists, go to step 4

3. 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

Resource-Request Algorithm for Process Pi

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

1. If Requesti <= Needi

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

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

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

Available = Available – Request;

Allocationi = Allocationi + Requesti;

Needi = Needi – Requesti;

lIf safe Þ the resources are allocated to Pi

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

An Illustrative Example
Consider the following situation:

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

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

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

3.3.6. Deadlock Detection

i. If deadlocks are not avoided, then another approach is to detect when they have occurred and recover
somehow.
ii. In addition to the performance hit of constantly checking for deadlocks, a policy / algorithm must be in
place for recovering from deadlocks, and there is potential for lost work when processes must be aborted
or have their resources preempted.
6.1 Single Instance of Each Resource Type
i. If each resource category has a single instance, then we can use a variation of the resource-allocation
graph known as a wait-for graph.
ii. A wait-for graph can be constructed from a resource-allocation graph by eliminating the resources and
collapsing the associated edges, as shown in the figure below.
iii. An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a resource that process
Pj is currently holding.

Fig: Resource Allocation Graph Fig: Corresponding Wait for Graph

98
As before, cycles in the wait-for graph indicate deadlocks.
This algorithm must maintain the wait-for graph, and periodically search it for cycles.

Several Instances of a Resource Type Available:

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

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

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

Detection Algorithm

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

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

if Allocationi != 0, then

Finish[i] = false;

otherwise,

Finish[i] = true

2. Find an index i such that both:

(a) Finish[i] == false

(b) Requesti <=Work

If no such i exists, go to step 4

3. 3. Work = Work + Allocationi

Finish[i] = true go to step 2

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

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

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

Example of Detection Algorithm

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

99
Snapshot at time T0:

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

Detection-Algorithm Usage
i. When should the deadlock detection be done? Frequently, or infrequently?
The answer may depend on how frequently deadlocks are expected to occur, as well as the possible
consequences of not catching them immediately. ( If deadlocks are not removed immediately when they
occur, then more and more processes can "back up" behind the deadlock, making the eventual task of
unblocking the system more difficult and possibly damaging to more processes. )
ii. There are two obvious approaches, each with trade-offs:
1.Do deadlock detection after every resource allocation which cannot be immediately granted. This has
the advantage of detecting the deadlock right away, while the minimum number of processes are involved
in the deadlock. ( One might consider that the process whose request triggered the deadlock condition is
the "cause" of the deadlock, but realistically all of the processes in the cycle are equally responsible for
the resulting deadlock. ) The down side of this approach is the extensive overhead and performance hit
caused by checking for deadlocks so frequently.
2.Do deadlock detection only when there is some clue that a deadlock may have occurred, such as when
CPU utilization reduces to 40% or some other magic number. The advantage is that deadlock detection is
done much less frequently, but the down side is that it becomes impossible to detect the processes

100
involved in the original deadlock, and so deadlock recovery can be more complicated and damaging to
more processes.
3.( As I write this, a third alternative comes to mind: Keep a historical log of resource allocations, since
that last known time of no deadlocks. Do deadlock checks periodically ( once an hour or when CPU usage
is low?), and then use the historical log to trace through and determine when the deadlock occurred and
what processes caused the initial deadlock. Unfortunately I'm not certain that breaking the original
deadlock would then free up the resulting log jam. )
7. Recovery From Deadlock
There are three basic approaches to recovery from deadlock:
i. Inform the system operator, and allow him/her to take manual intervention.
ii. Terminate one or more processes involved in the deadlock
iii. Preempt resources.
Process Termination
1. Two basic approaches, both of which recover resources allocated to terminated processes:

i. Terminate all processes involved in the deadlock. This definitely solves the deadlock, but at the
expense of terminating more processes than would be absolutely necessary.
ii. Terminate processes one by one until the deadlock is broken. This is more conservative,
but requires doing deadlock detection after each step.
2. In the latter case there are many factors that can go into deciding which processes to terminate
next:
i. Process priorities.
ii. How long the process has been running, and how close it is to finishing.
iii. How many and what type of resources is the process holding. ( Are they easy to preempt and
restore? )
iv. How many more resources does the process need to complete.
v. How many processes will need to be terminated
vi. Whether the process is interactive or batch.

Resource Preemption
When preempting resources to relieve deadlock, there are three important issues to be addressed:
Selecting a victim - Deciding which resources to preempt from which processes involves many of the
same decision criteria outlined above.
Rollback - Ideally one would like to roll back a preempted process to a safe state prior to the point at
which that resource was originally allocated to the process. Unfortunately it can be difficult or
impossible to determine what such a safe state is, and so the only safe rollback is to roll back all the
way back to the beginning. ( I.e. abort the process and make it start over. )
Starvation - How do you guarantee that a process won't starve because its resources are constantly
being preempted? One option would be to use a priority system, and increase the priority of a process
every time its resources get preempted. Eventually it should get a high enough priority that it won't
get preempted any more.

101
 UNIT IV
Mass-Storage Structure
Overview of Mass-Storage Structure

Magnetic Disks
Traditional magnetic disks have the following basic structure:

 One or more platters in the form of disks covered with magnetic media. Hard disk platters
are made of rigid metal, while "floppy" disks are made of more flexible plastic.
 Each platter has two working surfaces. Older hard disk drives would sometimes not use
the very top or bottom surface of a stack of platters, as these surfaces were more
susceptible to potential damage.
 Each working surface is divided into a number of concentric rings called tracks. The
collection of all tracks that are the same distance from the edge of the platter, (i.e. all
tracks immediately above one another in the following diagram) is called a cylinder.
 Each track is further divided into sectors, traditionally containing 512 bytes of data each,
although some modern disks occasionally use larger sector sizes. (Sectors also include a
header and a trailer, including checksum information among other things. Larger sector
sizes reduce the fraction of the disk consumed by headers and trailers, but increase
internal fragmentation and the amount of disk that must be marked bad in the case of
errors. )
 The data on a hard drive is read by read-write heads. The standard configuration (shown
below) uses one head per surface, each on a separate arm, and controlled by a common
arm assembly which moves all heads simultaneously from one cylinder to another. (Other
configurations, including independent read-write heads, may speed up disk access, but
involve serious technical difficulties.)
 The storage capacity of a traditional disk drive is equal to the number of heads (i.e. the
number of working surfaces), times the number of tracks per surface, times the number of
sectors per track, times the number of bytes per sector. A particular physical block of data
is specified by providing the head-sector-cylinder number at which it is located.

102
 Fig: Moving-head disk mechanism

 In operation the disk rotates at high speed, such as 7200 rpm (120 revolutions per
second.) The rate at which data can be transferred from the disk to the computer is
composed of several steps:
o The positioning time, a.k.a. the seek time or random access time is the time
required to move the heads from one cylinder to another, and for the heads to
settle down after the move. This is typically the slowest step in the process and
the predominant bottleneck to overall transfer rates.
o The rotational latency is the amount of time required for the desired sector to
rotate around and come under the read-write head. This can range anywhere from
zero to one full revolution, and on the average will equal one-half revolution. This
is another physical step and is usually the second slowest step behind seek time.
(For a disk rotating at 7200 rpm, the average rotational latency would be 1/2
revolution / 120 revolutions per second, or just over 4 milliseconds, a long time
by computer standards.
o The transfer rate, which is the time required to move the data electronically from
the disk to the computer. (Some authors may also use the term transfer rate to
refer to the overall transfer rate, including seeks time and rotational latency as
well as the electronic data transfer rate.)
 Disk heads "fly" over the surface on a very thin cushion of air. If they should accidentally
contact the disk, then a head crash occurs, which May or may not permanently damage
the disk or even destroy it completely. For this reason it is normal to park the disk heads
when turning a computer off, which means to move the heads off the disk or to an area of
the disk where there is no data stored.

103
  Floppy disks are normally removable. Hard drives can also be removable, and some are
even hot-swappable, meaning they can be removed while the computer is running, and a
new hard drive inserted in their place.
 Disk drives are connected to the computer via a cable known as the I/O Bus. Some of the
common interface formats include Enhanced Integrated Drive Electronics, EIDE;
Advanced Technology Attachment, ATA; Serial ATA, SATA, Universal Serial Bus,
USB; Fiber Channel, FC, and Small Computer Systems Interface, SCSI.
 The host controller is at the computer end of the I/O bus, and the disk controller is built
into the disk itself. The CPU issues commands to the host controller via I/O ports. Data is
transferred between the magnetic surface and onboard cache by the disk controller, and
then the data is transferred from that cache to the host controller and the motherboard
memory at electronic speeds.

Solid-State Disks - New

 As technologies improve and economics change, old technologies are often used in
different ways. One example of this is the increasing use of solid state disks, or SSDs.
 SSDs use memory technology as a small fast hard disk. Specific implementations may
use either flash memory or DRAM chips protected by a battery to sustain the information
through power cycles.
 Because SSDs have no moving parts they are much faster than traditional hard drives,
and certain problems such as the scheduling of disk accesses simply do not apply.
 However SSDs also have their weaknesses: They are more expensive than hard drives,
generally not as large, and may have shorter life spans.
 SSDs are especially useful as a high-speed cache of hard-disk information that must be
accessed quickly. One example is to store file system meta-data, e.g. directory and anode
information that must be accessed quickly and often. Another variation is a boot disk
containing the OS and some application executables, but no vital user data. SSDs are also
used in laptops to make them smaller, faster, and lighter.
 Because SSDs are so much faster than traditional hard disks, the throughput of the bus
can become a limiting factor, causing some SSDs to be connected directly to the system
PCI bus for example.

Magnetic Tapes
 Magnetic tapes were once used for common secondary storage before the days of hard
disk drives, but today are used primarily for backups.
 Accessing a particular spot on a magnetic tape can be slow, but once reading or writing
commences, access speeds are comparable to disk drives.
 Capacities of tape drives can range from 20 to 200 GB and compression can double that
capacity.

104
Disk Structure
 The traditional head-sector-cylinder, HSC numbers are mapped to linear block addresses
by numbering the first sector on the first head on the outermost track as sector 0.
Numbering proceeds with the rest of the sectors on that same track, and then the rest of
the tracks on the same cylinder before proceeding through the rest of the cylinders to the
center of the disk. In modern practice these linear block addresses are used in place of the
HSC numbers for a variety of reasons:
1. The linear length of tracks near the outer edge of the disk is much longer than for
those tracks located near the center, and therefore it is possible to squeeze many
more sectors onto outer tracks than onto inner ones.
2. All disks have some bad sectors, and therefore disks maintain a few spare sectors
that can be used in place of the bad ones. The mapping of spare sectors to bad
sectors in managed internally to the disk controller.
3. Modern hard drives can have thousands of cylinders, and hundreds of sectors per
track on their outermost tracks. These numbers exceed the range of HSC numbers
for many (older) operating systems, and therefore disks can be configured for any
convenient combination of HSC values that falls within the total number of
sectors physically on the drive.
 There is a limit to how closely packed individual bits can be placed on a physical media,
but that limit is growing increasingly more packed as technological advances are made.
 Modern disks pack many more sectors into outer cylinders than inner ones, using one of
two approaches:
o With Constant Linear Velocity, CLV, the density of bits is uniform from
cylinder to cylinder. Because there are more sectors in outer cylinders, the disk
spins slower when reading those cylinders, causing the rate of bits passing under
the read-write head to remain constant. This is the approach used by modern CDs
and DVDs.
o With Constant Angular Velocity, CAV, the disk rotates at a constant angular
speed, with the bit density decreasing on outer cylinders. (These disks would have
a constant number of sectors per track on all cylinders.)

Disk Attachment
Disk drives can be attached either directly to a particular host (a local disk) or to a network.

Host-Attached Storage
 Local disks are accessed through I/O Ports as described earlier.
 The most common interfaces are IDE or ATA, each of which allow up to two drives per
host controller.
 SATA is similar with simpler cabling.

105