33 Disk Scheduling Algorithm
Mary Anitha Rajam
36.1 Introduction
The design of a file system comprises of the user and programmer interface to the file system, internal data structures and algorithms used by the operating system for the implementation of the file system and the structure of the secondary storage which accommodates the file systems. In this module, we focus on the secondary storage part of the file system. In this module, we understand the physical structure of secondary storage devices and learn and evaluate disk scheduling algorithms.
36.2 Disk Structure
Disks provide the bulk of secondary storage for modern computer systems. Disk drives are addressed as large 1-dimensional arrays of logical blocks, where the logical block is the smallest unit of transfer. The 1-dimensional array of logical blocks is mapped into the sectors of the disk sequentially. Sector 0 is the first sector of the first track on the outermost cylinder. Mapping proceeds in order through that track, then the rest of the tracks in that cylinder, and then through the rest of the cylinders from outermost to innermost. Likewise, logical address can be converted into cylinder number, track number and sector number.
36.3 Disk Scheduling
The operating system is responsible for using hardware efficiently. For the disk drives, this means having a fast access time and large disk bandwidth.
Access time has two major components – seek time and rotational latency. Seek time is the time for the disk to move the head to the cylinder containing the desired sector. Rotational latency is the additional time for the disk to rotate the desired sector to the disk head. It is required to minimize the seek time for better efficiency.
Disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer. The disk bandwidth must be as large as possible.
When a process needs I/O from or to the disk, the process issues a system call to the operating system. The system call indicates whether the operation is input (read) or output (write), what the disk address for the transfer is (the location in the disk from where data is to be read or to where data is to be written), what the memory address for the transfer is (the location in the main memory from where data is to be moved to the disk or to where data is moved from the disk) and what the number of bytes to be transferred is.
If the desired disk drive and controller are available, the request is serviced immediately. If the disk drive or controller is busy, the request is placed in the queue of pending requests. The operating system services the requests one after the other. When one request is completed, the operating system chooses which pending request to service next. How does the operating system make this choice? This choice is done in different ways using different algorithms called the disk scheduling algorithms.
Several algorithms exist to schedule the servicing of disk I/O requests. We illustrate them with a request queue 98, 183, 37, 122, 14, 124, 65, 67 where each of these numbers represents the cylinder numbers from/to where reading/writing has to be done. Suppose there are 200 cylinders in the disk numbered from 0 to 99. The current position of the head is at cylinder number 53.
We now look at how the disk head is moved for different disk scheduling algorithms. We also look at the total number of moves made by the disk head in each type of disk scheduling algorithm. The overhead due to rotational latency is not considered here.
36.3.1 First-Come First-Served (FCFS)
In the FCFS disk scheduling algorithm, the request that arrives first is serviced first. Figure 36.1 shows the movement of the disk head for this algorithm. Initially, the disk head is at cylinder 53. Then it is moved to cylinder 98, from there to 183, then to 37 and so on, servicing in the order in which the requests had arrived. We can see that there is a request for 122 and another request for 124. But, since a request arrived for 14 in between the two requests, the head had to swing back and forth unnecessarily. Similarly, it can be seen that are a lot of head movements happening back and forth unnecessarily. The head moves through 640 cylinders in total.
The total seek time can be reduced if the head services the requests close to the current head position, before moving further,
Fig. 36.1 Movement of the disk head for FCFS scheduling (Source: [1])
36.3.2 Shortest-Seek-Time-First (SSTF)
The shortest-seek-time-first (SSTF) scheduling algorithm selects the request with the minimum seek time from the current head position. It chooses the pending request close to the current head position. Figure 36.2 shows the movements made by the disk head in the SSTF algorithm for the given sequence of requests. Initially, the head is at position 53. Of all the pending requests 98, 183, 37, 122, 14, 124, 65 and 67, the cylinder closest to 53 is 65.
Therefore, the head moves to 65 and services the request. From 65, the closest cylinder is 67 and the head moves from 65 to 67. From 67, the closest cylinder is 37 and the head moves from 67 to 37. Similarly, the head moves to 14, 98, 122, 124 and finally to 183. The total head movement in this algorithm is 236 cylinders. It can be seen that the head movement is much less in this algorithm compared to that of FCFS.
Fig. 36.2 Movement of the disk head for SSTF scheduling (Source: [1])
But the disadvantage of this algorithm is that it may cause starvation of some requests. If requests keep arriving close to the current head position, then the requests for cylinders that are farther away from the current head position may not be serviced at all.
36.3.3 SCAN
In the SCAN disk scheduling algorithm, the disk arm starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the other end of the disk. The head movement is then reversed and the servicing continues. This algorithm is sometimes called the elevator algorithm. Figure 36.3 shows the movements made by the disk head in the SCAN algorithm for the given sequence of requests.
Fig. 36.3 Movement of the disk head for SCAN scheduling (Source: [1])
Initially, the head is at position 53. The head moves towards one end of the disk servicing the requests for cylinders 37, 14 on the way. The head movement is then reversed and the head moves towards the other end servicing the requests for the cylinders 65, 67, 98, 122, 124 and 183 on the way. It is seen that there is a total head movement of 208 cylinders.
In this algorithm, while the head is returning back after moving to one end, if there are many recently arrived requests close to this end, only after servicing these requests the head moves to the other end. In this case, even though the requests close to the other end had arrived much earlier, those requests would have to wait for a longer amount of time.
36.3.4 C-SCAN
The C-SCAN provides a more uniform wait time than SCAN. In the C-SCAN algorithm, the head moves from one end of the disk to the other servicing requests on the way. When the head reaches the other end, it immediately returns to the beginning of the disk, without servicing any requests on the return trip. This algorithm treats the cylinders as a circular list that wraps around from the last cylinder to the first one. Figure 36.4 shows the movements made by the disk head in the C-SCAN algorithm for the given sequence of requests.
Fig. 36.4 Movement of the disk head for C-SCAN scheduling (Source: [1])
Initially, the head is at position 53. The head moves towards one end of the disk servicing the requests for cylinders 65, 67, 98, 122, 124 and 183 on the way. The head movement is then reversed and the head moves towards the other end but does service requests in this direction. After going to the other end, the head again reverses and services the requests for the cylinders 14 and 37. Therefore, the waiting time of the requests 14 and 37 are reduced.
In this example, we see that the head moves from cylinder 183 till the end unnecessarily, because there are no requests waiting. Similarly, the movement of the head from 0 to 14 is unnecessary. These movements of the head can be avoided. This variation was brought in the C-LOOK scheduling algorithm.
36.3.5 C-LOOK
The C-LOOK scheduling algorithm is a variant of the C-SCAN scheduling algorithm. In this algorithm, the arm only goes as far as the last request in each direction, then reverses direction immediately. The arm does not go all the way to the end of the disk. Figure 36.4 shows the movements made by the disk head in the C-LOOK algorithm for the given sequence of requests. It is seen that the head does not beyond cylinder 183. After servicing cylinder 183, it returns back. Similarly, the head does move till 0 in the reverse direction. It moves only till cylinder 14 and reverses.
Fig. 36.5 Movement of the disk head for C-LOOK scheduling (Source: [1])
36.3.5 Selecting a Disk-Scheduling Algorithm
Having seen a number of disk scheduling algorithms, we now see which algorithm performs the best. SSTF is common and has a natural appeal because it increases performance over FCFS. SCAN and C-SCAN perform better for systems that place a heavy load on the disk – because less starvation. When there is heavy load in the disk, if SSTF is used, it will continue to serve the requests close to the current position of the disk. The requests that are farther away from the current position will starve.
The performance of the algorithms depends on the number and types of requests also. Suppose there is only one outstanding request. Then all the algorithms behave like FCFS.
The requests for disk service can also be influenced by the file-allocation method. For a contiguously allocated file, the contents of the file are stored in contiguous disk blocks and therefore, there is limited head movement.
For linked or indexed file, the contents of a file can be kept in any disk block in the disk. This may need greater head movement when compared to contiguous allocation.
The location of directories and index blocks is also important. The directories have the name of the file and the details present in the file control block (inode in the case of UNIX/Linux). The file control block has the addresses of the disk blocks where the contents of the file are stored. To open a file, it is necessary to search the directory structure, get the file control block, get the addresses of the disk blocks containing data, access the disk blocks and get the file’s data. If directory entry is on the first cylinder and the file’s data are on the final cylinder, greater head movement is needed. Therefore, caching directories and index blocks in main memory help to reduce disk-arm movement.
Disk-scheduling algorithm should be written as a separate module of the operating system, allowing it to be replaced with a different algorithm, if necessary.
Thus, it is seen that either SSTF or LOOK is a reasonable choice for the default algorithm. SSTF causes less head movement and LOOK works well when there is a heavy load.
Disk-scheduling algorithms discussed here consider only the seek distances. The rotational latency is not taken into account. For modern disks, rotational latency can also be as large as the seek time. Therefore, disk-scheduling algorithms are implemented in the controller hardware built into the disk drive. When the operating system sends requests, the controller queues the requests and schedules them to improve both the seek time and rotational latency.
36.4 Summary
In this module we learnt different disk scheduling algorithms such as FCFS, SSTF, SCAN, C-SCAN and C-LOOK. We also discussed about the performance of the disk scheduling algorithms.
References
[1] Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.
[2] Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
[3] Gary Nutt, “Operating Systems”, Third Edition, Pearson Education, 2009.