Storage Structure in Operating Systems

 Difficulty Level : Medium

 Last Updated : 19 Jan, 2022
Basically we want the programs and data to reside in main memory permanently.
This arrangement is usually not possible for the following two reasons:
1. Main memory is usually too small to store all needed programs and data
permanently.
2. Main memory is a volatile storage device that loses its contents when power
is turned off or otherwise lost.
There are two types of storage devices:-
 Volatile Storage Device –
It loses its contents when the power of the device is removed.
 Non-Volatile Storage device –
It does not loses its contents when the power is removed. It holds all the
data when the power is removed.
Secondary Storage is used as an extension of main memory. Secondary storage
devices can hold the data permanently.
Storage devices consists of Registers, Cache, Main-Memory, Electronic-
Disk, Magnetic-Disk, Optical-Disk, Magnetic-Tapes. Each storage system provides
the basic system of storing a datum and of holding the datum until it is retrieved at a
later time. All the storage devices differ in speed, cost, size and volatility. The most
common Secondary-storage device is a Magnetic-disk, which provides storage for
both programs and data.
In this fig Hierarchy of storage is shown –
In this hierarchy all the storage devices are arranged according to speed and cost. The
higher levels are expensive, but they are fast. As we move down the hierarchy, the
cost per bit generally decreases, where as the access time generally increases.
The storage systems above the Electronic disk are Volatile, where as those below are
Non-Volatile.
An Electronic disk can be either designed to be either Volatile or Non-Volatile.
During normal operation, the electronic disk stores data in a large DRAM array,
which is Volatile. But many electronic disk devices contain a hidden magnetic hard
disk and a battery for backup power. If external power is interrupted, the electronic
disk controller copies the data from RAM to the magnetic disk. When external power
is restored, the controller copies the data back into the RAM.
Hard Disk Drive (HDD) Secondary memory
 Difficulty Level : Easy
 Last Updated : 24 Jan, 2022
A hard disk is a memory storage device that looks like this:

The disk is divided into tracks. Each track is further divided into sectors. The point to
be noted here is that outer tracks are bigger in size than the inner tracks but they
contain the same number of sectors and have equal storage capacity. This is because
the storage density is high in sectors of the inner tracks whereas the bits are sparsely
arranged in sectors of the outer tracks. Some space of every sector is used for
formatting. So, the actual capacity of a sector is less than the given capacity.
Read-Write(R-W) head moves over the rotating hard disk. It is this Read-Write head
that performs all the read and writes operations on the disk and hence, the position of
the R-W head is a major concern. To perform a read or write operation on a memory
location, we need to place the R-W head over that position. Some important terms
must be noted here:
1. Seek time – The time taken by the R-W head to reach the desired track
from its current position.
2. Rotational latency – Time is taken by the sector to come under the R-W
head.
 3. Data transfer time – Time is taken to transfer the required amount of data.
It depends upon the rotational speed.
4. Controller time – The processing time taken by the controller.
5. Average Access time – seek time + Average Rotational latency + data
transfer time + controller time.

Disk Scheduling Algorithms

Disk scheduling is done by operating systems to schedule I/O requests arriving for
the disk. Disk scheduling is also known as I/O scheduling.
Disk scheduling is important because:

 Multiple I/O requests may arrive by different processes and only one I/O
request can be served at a time by the disk controller. Thus other I/O
requests need to wait in the waiting queue and need to be scheduled.
 Two or more request may be far from each other so can result in greater
disk arm movement.
 Hard drives are one of the slowest parts of the computer system and thus
need to be accessed in an efficient manner.
There are many Disk Scheduling Algorithms but before discussing them let’s have a
quick look at some of the important terms:

 Seek Time:Seek time is the time taken to locate the disk arm to a specified
track where the data is to be read or write. So the disk scheduling algorithm
that gives minimum average seek time is better.
 Rotational Latency: Rotational Latency is the time taken by the desired
sector of disk to rotate into a position so that it can access the read/write
heads. So the disk scheduling algorithm that gives minimum rotational
latency is better.
 Transfer Time: Transfer time is the time to transfer the data. It depends on
the rotating speed of the disk and number of bytes to be transferred.
 Disk Access Time: Disk Access Time is:

Disk Access Time = Seek Time +

Rotational Latency +
Transfer Time
  Disk Response Time: Response Time is the average of time spent by a
request waiting to perform its I/O operation. Average Response time is the
response time of the all requests. Variance Response Time is measure of
how individual request are serviced with respect to average response time.
So the disk scheduling algorithm that gives minimum variance response
time is better.
Disk Scheduling Algorithms

1. FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In

FCFS, the requests are addressed in the order they arrive in the disk
queue.Let us understand this with the help of an example.

Example:
1. Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is : 50
 1. So, total seek time:
=(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16)
=642

Advantages:

 Every request gets a fair chance

 No indefinite postponement
Disadvantages:

 Does not try to optimize seek time

 May not provide the best possible service

1. SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek
time are executed first. So, the seek time of every request is calculated in
advance in the queue and then they are scheduled according to their
calculated seek time. As a result, the request near the disk arm will get
executed first. SSTF is certainly an improvement over FCFS as it decreases
the average response time and increases the throughput of system.Let us
understand this with the help of an example.

Example:
1. Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is : 50

1.
So, total seek time:
1. =(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170)
=208
Advantages:

 Average Response Time decreases

 Throughput increases
Disadvantages:

 Overhead to calculate seek time in advance

 Can cause Starvation for a request if it has higher seek time as compared to
incoming requests
 High variance of response time as SSTF favours only some requests

1. SCAN: In SCAN algorithm the disk arm moves into a particular direction
and services the requests coming in its path and after reaching the end of
disk, it reverses its direction and again services the request arriving in its
path. So, this algorithm works as an elevator and hence also known
as elevator algorithm. As a result, the requests at the midrange are serviced
more and those arriving behind the disk arm will have to wait.

Example:
1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the
Read/Write arm is at 50, and it is also given that the disk arm should
move “towards the larger value”.

1.
Therefore, the seek time is calculated as:
1. =(199-50)+(199-16)
=332
Advantages:

 High throughput
 Low variance of response time
 Average response time
Disadvantages:

 Long waiting time for requests for locations just visited by disk arm

1. CSCAN: In SCAN algorithm, the disk arm again scans the path that has
been scanned, after reversing its direction. So, it may be possible that too
many requests are waiting at the other end or there may be zero or few
requests pending at the scanned area.
These situations are avoided in CSCAN algorithm in which the disk arm instead of
reversing its direction goes to the other end of the disk and starts servicing the
requests from there. So, the disk arm moves in a circular fashion and this algorithm is
also similar to SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).

Example:
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the
Read/Write arm is at 50, and it is also given that the disk arm should move “towards
the larger value”.

Seek time is calculated as:

=(199-50)+(199-0)+(43-0)
=391
Advantages:

 Provides more uniform wait time compared to SCAN

1. LOOK: It is similar to the SCAN disk scheduling algorithm except for the
difference that the disk arm in spite of going to the end of the disk goes only
to the last request to be serviced in front of the head and then reverses its
direction from there only. Thus it prevents the extra delay which occurred
due to unnecessary traversal to the end of the disk.

Example:
1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the
Read/Write arm is at 50, and it is also given that the disk arm should
move “towards the larger value”.

1.
So, the seek time is calculated as:
1. =(190-50)+(190-16)
=314

1. CLOOK: As LOOK is similar to SCAN algorithm, in similar way,

CLOOK is similar to CSCAN disk scheduling algorithm. In CLOOK, the
disk arm in spite of going to the end goes only to the last request to be
serviced in front of the head and then from there goes to the other end’s last
 request. Thus, it also prevents the extra delay which occurred due to
unnecessary traversal to the end of the disk.

Example:
1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the
Read/Write arm is at 50, and it is also given that the disk arm should
move “towards the larger value”

1.
So, the seek time is calculated as:
1. =(190-50)+(190-16)+(43-16)
=341