Disk Scheduling Algorithms with Examples
Disk Scheduling Algorithms:
Disk scheduling algorithms are the algorithms that are used for scheduling a disk. There are five types of Disk Scheduling Algorithms are available:
-
1. FCFS Disk Scheduling
2. SSTF Disk Scheduling
3. SCAN Disk Scheduling
4. C-scan Disk Scheduling
5. Look Disk Scheduling
FCFS Disk Scheduling:
The expansion of FCFS is First-Come, First-Served. It is the simplest disk scheduling algorithm of all. But it does not provide faster service.
Example: Consider a disk queue with requests for I/O to block cylinders.
[no-highlight]87, 160, 40, 140, 36, 72, 66, 15
In that order, if the disk head is initially at cylinder 60. Then the total head movement of is
=(60 to 87)+(87 to 160)+(160 to 40)+(40 to 140)+(140 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= 557/8 = 69.6 cylinders
[/no-highlight]
SSTF Disk Scheduling:
The expansion of SSTF is shortest seek time first. This algorithm selects the request with the minimum to seek time from the current head position.
Example: Consider the previous disk queue with requests for I/O to block cylinders.
[no-highlight]87, 160, 40, 140, 36, 72, 66, 15
The total head movements of this algorithm are
=(60 to 66)+(66 to 72)+(72 to 87)+(87 to 40)+(40 to 36)+(36 to 15)+(15 to 140)+(140 to 160)
= (6+6+15+37+4+21+135+20)
= 244 cylinders
∴ The average head movements are = 244/8 = 30.5 cylinders
[/no-highlight]
SCAN Disk Scheduling:
The SCAN algorithm is called ‘Elevator algorithm‘. In this, the disk arm starts at one end of the disk and moves towards the other end, while in the means time all request served until it gets other ends of the disk. At the other end, the direction of the head movement is reversed, and servicing is continuous. That’s why is this algorithm is called an elevator algorithm.
C-scan Disk Scheduling:
The main drawback in SCAN scheduling is the waiting time isn’t uniformly. Some requests are waiting much time, some requests are serviced immediately, we can overcome this drawback with the C-Scan algorithm. It is designed to provide a more uniform wait time. This algorithm moves the head from one end to the other end of the disk, servicing 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.
Look Disk Scheduling:
In Look Scheduling, 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.