Disk Scheduling Algorithms
-- Tony Abou-Assaleh
Introduction
In most systems there are many process that are running simultaneously. Often, many
processes request I/O operations from/to the hard drive. The algorithm used to select
which request is going to be satisfied first is called "disk scheduling
algorithm." In order to be able to understand and evaluate these algorithms one
should be familiar with the way hard drives work.
How Hard Drives Work
A hard drive is a collection of plates called platters. Both sides of each platter are
covered with some kind of a magnetization medium that allows ones and zeros to be stored.
Each surface is divided into circles called tracks. Further more, each track is divided
into smaller pieces called sectors. Disk I/O is done sector by sector. A group of tracks
that are positioned on top of each other is called a cylinder. There is a head connected
to an arm for each surface, which handles all I/O operations. Usually, all arms are
attached to each other so the heads are always in the same cylinder.
For each I/O request, first, a head must be selected. This is done electronically, and
the time it takes is not significant. Then the head is moved over the destination track.
After that, the disk is rotated to position the desired sector under the head. Finally,
the I/O operation is performed. Arm movements and disk rotations are where the delay
occurs.
There are two objectives for any disk scheduling algorithm:
1. Minimize the throughput - the average number of requests satisfied per time unit.
2. Maximize the response time - the average time that a request must wait before it is
satisfied.
The following algorithms are discussed in this article:
1. First In First Out (FIFO)
2. Shortest Seek Time First (SSTF)
3. SCAN
4. Circular SCAN (C-SCAN)
5. LOOK
6. Circular LOOK (C-LOOK)
7. Round-Robin
8. Priority Scheduling
9. Fair Share
10. Shortest Job First
11. Exponential Queue
1. First In First Out (FIFO)
This is the simplest algorithm. It processes requests in the same order as they arrive.
This technique improves the response time. However, the throughput is not efficient. It
involves a lot of near random head and disk movements. This algorithm is used only in
small systems where I/O efficiency is not very important.
2. Shortest Seek Time First (SSTF)
After each request is received, the controller selects the request that is closest to
the current location of the head. The throughput is much better than in FIFO. However,
some process may have to wait long time until it's request(s) are satisfied if new
requests with shorter seek time keep arriving.
3. SCAN
In this algorithm the head always constantly moves from the most inner cylinder to the
outer cylinder, then it changes its direction back towards the center. As the head moves,
if there is a request for the current disk position it is satisfied. The throughput is
better than in FIFO. The SCAN algorithm is more fair that SSTF.
4. Circular SCAN (C-SCAN)
This is an improved SCAN algorithm. In SCAN, the most outer and most inner cylinders
have less opportunity to be accessed than the ones in the middle. C-SCAN eliminates this
by satisfying requests only when the head moves in one direction, and not satisfying any
requests when it moves back.
5. LOOK
As in SCAN, requests are served when the head moves in both directions. The difference
is that LOOK uses information about the requests to change the direction of the head when
it knows that there are no requests beyond the current point. This improves both the
throughput and the response time.
6. Circular LOOK (C-LOOK)
This is a variation of LOOK where requests are satisfied only when the head moves
outwards, as in C-SCAN.
7. Round-Robin
The CPU time is divided into slices. Each process is served within the time slice and
moved to the back of the queue. The efficiency of this algorithm depends on the length of
the time slices and the length of the I/O requests. Variations of this algorithm are used
in most systems.
8. Priority Scheduling
The system may assign priorities to requests that are more intensive for I/O
operations. There are many variations of this algorithm, which use different criteria for
specifying priorities and how they change. For instance, a system may give higher priority
to large requests as they may block the process from running. The priority of requests
that have been served for a long time may decrease and the priority of requests that have
been waiting for a long time may increase. This algorithm is mostly used in multitasking
systems with a single user.
9. Fair Share
This algorithm is used in systems with multiple users. Its idea is similar to the Round
Robin. However, the time slices are provided for individual users rather than processes.
This algorithm guarantees that each user gets an equal amount of I/O processing time. The
Fair Share algorithm is usually combined with some other algorithm that schedules the I/O
requests within the time slots for each user.
10. Shortest Job First
This is a greedy algorithm that orders the request in the queue based on their expected
completion time. It requires that the completion time be known in advance. The queuing
theory shows that this mechanism improves both the throughput and the response time.
Difficulties occur when it is not possible to predetermine the completion time of requests
or when the completion time changes as the request waits in the queue.
11. Exponential Queue
When a new request arrives, it is given a very high priority (e.g. 100) and a very
small time slice (e.g. 1ms). After the time slice is used, the priority is decreased by
one and the time slice is doubled. The Exponential Queue algorithm highly increases the
over all performance of the system. Therefore, it is mainly used in interactive systems.
Conclusion
In general, there is a trade-off between the throughput and the response time. Some
algorithms focus more on the throughput. Others give more importance to the response time.
The type of the system and the type of I/O requests, in terms of size and frequency, would
determine the most suitable algorithm. A good algorithm would find the golden point
somewhere in between the throughput and the response time. For complicated system, a
combination of more than one algorithm maybe necessary to provide fair efficiency for all
users.
References
Eager, R. D. and Lister, A. M. (1945). "Fundamentals of Operating
Systems". Springer-Verlag, New York, 1995
Copyright (c) Tony Abou-Assaleh 1999.
|
