Secondary storage devices are those devices whose memory is non
volatile, meaning, the stored data will be intact even if the system is
turned off. Here are a few things worth noting about secondary
storage.
• Secondary storage is also called auxiliary storage.
• Secondary storage is less expensive when compared to
primary memory like RAMs.
• The speed of the secondary storage is also lesser than that of
primary storage.
• Hence, the data which is less frequently accessed is kept in the
secondary storage.
• A few examples are magnetic disks, magnetic tapes,
removable thumb drives etc.
Magnetic Disk Structure
In modern computers, most of the secondary storage is in the form
of magnetic disks. Hence, knowing the structure of a magnetic disk
is necessary to understand how the data in the disk is accessed by
the computer.
Powered By
Play
Unmute
%1.70 :Loaded
Fullscreen
Structure of a magnetic disk
A magnetic disk contains several platters. Each platter is divided
into circular shaped tracks. The length of the tracks near the centre
is less than the length of the tracks farther from the centre. Each
track is further divided into sectors, as shown in the figure.
Tracks of the same distance from centre form a cylinder. A read-
write head is used to read data from a sector of the magnetic disk.
The speed of the disk is measured as two parts:
• Transfer rate: This is the rate at which the data moves from
disk to the computer.
• Random access time: It is the sum of the seek time and
rotational latency.
Seek time is the time taken by the arm to move to the required
track. Rotational latency is defined as the time taken by the arm to
reach the required sector in the track.
Even though the disk is arranged as sectors and tracks physically,
the data is logically arranged and addressed as an array of blocks of
fixed size. The size of a block can be 512 or 1024 bytes. Each logical
block is mapped with a sector on the disk, sequentially. In this way,
each sector in the disk will have a logical address.
Disk Scheduling Algorithms
On a typical multiprogramming system, there will usually be
multiple disk access requests at any point of time. So those requests
must be scheduled to achieve good efficiency. Disk scheduling is
similar to process scheduling. Some of the disk scheduling
algorithms are described below.
FCFS stands for First-Come, First-Served, which is a scheduling algorithm used in
operating systems to determine the order in which tasks are executed by the CPU. In
FCFS, the process that arrives first is served first by the CPU.
Here is a step-by-step explanation of how FCFS works:
1. When a process enters the system, it is added to the end of the queue.
2. The CPU scheduler picks the first process from the front of the queue and
assigns the CPU to that process.
3. The process runs until it either completes its execution or is interrupted by an
I/O request.
4. If the process completes its execution, it is removed from the queue, and the
CPU scheduler picks the next process from the front of the queue.
5. If the process is interrupted by an I/O request, it is moved to a waiting queue,
and the CPU scheduler picks the next process from the front of the queue.
6. When the I/O request is completed, the process is moved back to the end of
the original queue.
7. This process continues until all the processes in the queue have completed
their execution.
FCFS is a simple and easy-to-understand scheduling algorithm, but it may not be the
most efficient one. For example, it can lead to a situation where a long-running
process holds the CPU for an extended period, causing other processes to wait for a
long time. This situation is known as convoy effect, which can lead to poor overall
system performance.
FCFS Scheduling Algorithm
It is the simplest Disk Scheduling algorithm. It services the IO requests in the order in
which they arrive. There is no starvation in this algorithm, every request is serviced.
Disadvantages
o The scheme does not optimize the seek time.
o The request may come from different processes therefore there is the possibility of
inappropriate movement of the head.
Example
Consider the following disk request sequence for a disk with 100 tracks 45, 21, 67, 90,
4, 50, 89, 52, 61, 87, 25
Head pointer starting at 50 and moving in left direction. Find the number of head
movements in cylinders using FCFS scheduling.
Solution
Number of cylinders moved by the head
= (50-45)+(45-21)+(67-21)+(90-67)+(90-4)+(50-4)+(89-50)+(61-52)+(87-61)+(87-25)
= 5 + 24 + 46 + 23 + 86 + 46 + 49 + 9 + 26 + 62
= 376
SSTF Scheduling Algorithm
Shortest seek time first (SSTF) algorithm selects the disk I/O request which requires the
least disk arm movement from its current position regardless of the direction. It
reduces the total seek time as compared to FCFS.
It allows the head to move to the closest track in the service queue.
Disadvantages
o It may cause starvation for some requests.
o Switching direction on the frequent basis slows the working of algorithm.
o It is not the most optimal algorithm.
Example
Consider the following disk request sequence for a disk with 100 tracks
45, 21, 67, 90, 4, 89, 52, 61, 87, 25
Head pointer starting at 50. Find the number of head movements in cylinders using
SSTF scheduling.
Solution:
Number of cylinders = 5 + 7 + 9 + 6 + 20 + 2 + 1 + 65 + 4 + 17 = 136
SSTF stands for Shortest Seek Time First, which is a scheduling algorithm used in operating
systems to determine the order in which I/O requests are serviced by the disk. In SSTF, the
request with the shortest seek time is served first by the disk.
Here's how SSTF works:
1. When a new I/O request arrives, the disk arm starts moving to the cylinder where the
request is located.
2. While the disk arm is moving, any new requests that arrive are sorted in order of their
distance from the current position of the disk arm.
3. When the disk arm reaches the cylinder with the closest request, that request is serviced.
4. After the request is serviced, the disk arm returns to its original position and the process
repeats from step 1.
The main advantage of SSTF is that it reduces the average response time for I/O requests
compared to the FCFS (First-Come-First-Served) scheduling algorithm, as it minimizes the
amount of time the disk arm has to move between requests. However, it can suffer from
starvation, where some requests may never be serviced if there are always requests closer to the
current position of the disk arm.
In practice, SSTF is often used in combination with other scheduling algorithms, such as SCAN or
C-SCAN, to balance the trade-off between response time and fairness.
SCAN and C-SCAN algorithm
Scan Algorithm
It is also called as Elevator Algorithm. In this algorithm, the disk arm moves into a
particular direction till the end, satisfying all the requests coming in its path,and then
it turns backand moves in the reverse direction satisfying requests coming in its path.
It works in the way an elevator works, elevator moves in a direction completely till the
last floor of that direction and then turns back.
Example
Consider the following disk request sequence for a disk with 100 tracks
98, 137, 122, 183, 14, 133, 65, 78
Head pointer starting at 54 and moving in left direction. Find the number of head
movements in cylinders using SCAN scheduling.
Number of Cylinders = 40 + 14 + 65 + 13 + 20 + 24 + 11 + 4 + 46 = 237
C-SCAN algorithm
In C-SCAN algorithm, the arm of the disk moves in a particular direction servicing
requests until it reaches the last cylinder, then it jumps to the last cylinder of the
opposite direction without servicing any request then it turns back and start moving
in that direction servicing the remaining requests.
Example
Consider the following disk request sequence for a disk with 100 tracks
98, 137, 122, 183, 14, 133, 65, 78
Head pointer starting at 54 and moving in left direction. Find the number of head
movements in cylinders using C-SCAN scheduling.
No. of cylinders crossed = 40 + 14 + 199 + 16 + 46 + 4 + 11 + 24 + 20 + 13 = 387
SCAN and C-SCAN are disk scheduling algorithms used in operating systems to determine the
order in which I/O requests are serviced by the disk.
SCAN (also known as Elevator) Algorithm:
In the SCAN algorithm, the disk arm moves in one direction (either towards the innermost or
outermost track) and services all the requests in that direction until it reaches the end of the disk.
It then reverses direction and services all the requests in the opposite direction.
Here's how SCAN works:
1. When a new I/O request arrives, it is added to a queue.
2. The queue is sorted in order of increasing cylinder number.
3. The disk arm starts at one end of the disk and moves in the direction of the requests.
4. While the disk arm is moving in that direction, it services all the requests in that direction.
5. When it reaches the end of the disk, it reverses direction and services all the remaining
requests in the opposite direction.
6. After all the requests in the queue have been serviced, the process starts over from the
beginning.
The main advantage of SCAN is that it prevents starvation of requests that are located far from
the current position of the disk arm. However, it may cause some delay for requests that are
located at the opposite end of the disk from the current position of the arm.
C-SCAN (Circular SCAN) Algorithm:
C-SCAN is a variant of the SCAN algorithm where the disk arm moves only in one direction
(either towards the innermost or outermost track) and services all the requests in that direction.
When it reaches the end of the disk, it immediately returns to the other end of the disk without
servicing any requests on the way back.
Here's how C-SCAN works:
1. When a new I/O request arrives, it is added to a queue.
2. The queue is sorted in order of increasing cylinder number.
3. The disk arm starts at one end of the disk and moves in the direction of the requests.
4. While the disk arm is moving in that direction, it services all the requests in that direction.
5. When it reaches the end of the disk, it immediately returns to the other end of the disk
without servicing any requests on the way back.
6. After all the requests in the queue have been serviced, the process starts over from the
beginning.
The main advantage of C-SCAN is that it provides more predictable service times than SCAN, as
all the requests are serviced in a uniform manner. However, it may cause some delay for requests
that are located at the opposite end of the disk from the current position of the arm.
Selection of Disk Scheduling Algorithm
The selection of a disk scheduling algorithm depends on various factors, including the
characteristics of the system and the performance requirements of the application. Here are
some factors to consider when selecting a disk scheduling algorithm:
1. Access Pattern: The disk scheduling algorithm should match the access pattern of the
application. For example, if the application requires frequent access to adjacent sectors,
then the SSTF algorithm may be a good choice.
2. Disk Load: The disk scheduling algorithm should be able to handle the expected disk
load. For example, if the system has a high disk load, then the SCAN or C-SCAN
algorithms may be more suitable, as they can handle a large number of requests
efficiently.
3. Response Time: The disk scheduling algorithm should provide an acceptable response
time for the application. For example, if the application requires fast response times, then
the SSTF or LOOK algorithms may be more suitable, as they can minimize the average
seek time.
4. Fairness: The disk scheduling algorithm should provide fair access to the disk for all
processes. For example, the SCAN algorithm may cause starvation for requests that are
located far from the current position of the disk arm, while the C-SCAN algorithm may
provide more predictable service times for all requests.
5. Implementation Complexity: The disk scheduling algorithm should be easy to implement
and maintain. For example, the FCFS algorithm is simple to implement, but it may not
provide optimal performance in all situations.
In practice, it may be necessary to use a combination of different disk scheduling algorithms to
achieve the desired performance and fairness characteristics. Additionally, the choice of disk
scheduling algorithm may also depend on the specific hardware and operating system
environment.
