Disk Scheduling Algorithms - aryanjoshi0823/5143-Operating-System GitHub Wiki

Disk scheduling is a technique operating systems use to manage the order in which disk I/O (input/output) requests are processed. Disk scheduling is also known as I/O Scheduling. The main goals of disk scheduling are to optimize the performance of disk operations, reduce the time it takes to access data and improve overall system efficiency.

Disk scheduling algorithms are crucial in managing how data is read from and written to a computer’s hard disk. These algorithms help determine the order in which disk read and write requests are processed, significantly impacting the speed and efficiency of data access.

Disk Scheduling Algorithms:

a)First-Come, First-Served (FCFS):

  • In the FCFS disk scheduling algorithm, the request that arrives first is serviced first.
  • Above figure 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.

b)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. Above figure 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. -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.

c)SCAN/Elevator:

  • 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. Above figure shows the movements made by the disk head in the SCAN algorithm for the given sequence of requests.

  • 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.

d)Circular SCAN (C-SCAN):

  • C-SCAN ensures more uniform wait times than SCAN. The disk head moves from one end to the other, servicing requests along the way. Upon reaching the end, it returns to the start without servicing requests, treating the cylinders as a circular list.

  • Initially, the head starts at position 53 and services requests for cylinders 65, 67, 98, 122, 124, and 183. It then reverses direction without servicing requests, moves to the other end, and reverses again to service cylinders 14 and 37, reducing their wait time. However, unnecessary movements from 183 to the disk's end and from 0 to 14 are inefficient. The C-LOOK algorithm eliminates these unnecessary movements.

e)LOOK:

  • LOOK Algorithm 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.

  • 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”.
  • So, the total overhead movement (total distance covered by the disk arm) is calculated as: = (190-50) + (190-16) = 314

e) 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. Above figure 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.