Disk scheduling also known as I/O scheduling is done by operating systems to schedule I/O requests arriving for the disk. There is a number of disc scheduling algorithms available. Out of those, we will discuss only five popular algorithms, which are:
- FCFS Scheduling
- SSTF Scheduling
- SCAN Scheduling
- C-SCAN Scheduling
- LOOK Scheduling
1. FCFS Scheduling
The FCFS (First Come, First-Served) scheduling algorithm is the simplest disk scheduling algorithm of all. But it does not provide the fastest service. For example, disk queue with requests for I/O to block on cylinders.
87, 170, 40, 150, 36, 72, 66, 15
If the disk head is initially at cylinder 60. It will first move from 62 to 87 then 87 to 170, 170 to 40, then 150, 36, 72,66, and finally 15. Consider the below figure for a better understanding.
The total head movement can be calculated as
= (60 to 87) + (87 to 170) + (170 to 40) + (40 to 150) + (150 to 36) + (36 to 72) + (72 to 66) + (66 to 15)
= (27 + 83 + 130 + 110 + 114 + 36 + 6 + 51)
= 557 cylinders
The average head movements are:
Average Movements = Total number of head movements / Number of requests
= 557/8
= 69.6 cylinders.The algorithm is very simple to implement. But the performance is not satisfactory, the average head movements are very high.
2. SSTF Scheduling
The SSTF (Shortest Seek Time First) scheduling algorithm selects the request with minimum seek time from the current head position. For example, consider the previous request queues 87, 170, 40, 150, 36, 72, 66, 15, and the head position initially at 60. The closest request to the head position is cylinder 66, then 66 to 72, 72 to 87, and so on. We will continue this process for all given request queues. Consider the below figure for a better understanding.
The Queue is 87, 170, 40, 150, 36, 72, 66, and 15 where the head starts at 60.
The total head movements in this algorithm are:
= (60 to 66) + (66 to 72) + (72 to 87) + (87 to 40) + (40 to 36) + (36 to 15) + (15 to 150) + (150 to 170)
= 6 + 6 + 15 + 47 + 4 + 21 + 135 + 20
The average head movements are:
Average Movements = Total number of head movements / Number of requests
= 254/8
= 31.75 cylinders.By comparing this algorithm with FCFS, it gives a substantial improvement in performance.
3. SCAN Scheduling
The SCAN algorithm is also called the Elevator algorithm. In this algorithm, the disk arm starts at one end of the disk and moves toward the other end. While in the meantime all requests are serviced until it gets to another end of the disk. At the other end, the direction of head movement is reversed, and the service continues. Because of such head movement of the disk, it is called Elevator Algorithm. Consider our previous example for a better understanding.
The Queue is 87, 170, 40, 150, 36, 72, 66, and 15 where the head starts at 60.
The head movements start from the 60th cylinder. Assume that the direction is towards the outsides so the head will service 66, 72, 87, 150, and 170. At cylinder 180 the arm will reverse and move toward the other end of the disk and will service requests 40, 36, 15.
Let's calculate the head movements.
= (60 to 66) + (66 to 72) + (72 to 87) + (87 to 150) + (150 to 170) + (170 + 180) + (180 + 40) + (40 + 36) + (36 to 15)
= 6 + 6 + 15 + 63 + 20 + 10 + 140 + 4 + 21
= 285 cylinders
Average Movements = Total number of head movements / Number of requests
= 285 / 8
= 35.63 cylinders.By comparing this algorithm with FCFS, it gives a substantial improvement in performance. But it is not better, compare with SSTF.
4. C-SCAN Scheduling
The main drawback of SCAN scheduling is the waiting time is not uniform. Some requests are waiting much time and some requests are serviced immediately. We can overcome this drawback with C-SCAN (Circular Scan) scheduling algorithm. This algorithm is designed to provide a more uniform wait time. In this algorithm, the head moves from one end to another end of the disk and services the request along 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. The queue is 87, 170, 40, 150, 36, 72, 66, 15, and starting point 60. The average head movements in this algorithm are more than in the SCAN scheduling. But it provides a more uniform wait time.
5. Look Scheduling
In the SCAN, and C-SCAN algorithms the disk arm moves across the full width of the disk. But in this algorithm, the arm goes only as far as the final request in each direction. Then it reverses the direction immediately without reaching the end of the disk. Consider the figure for a better understanding.
The queue is 87, 170, 40, 150, 36, 72, 66, 15, and starting point is 60.