First-Come-First-Served (FCFS) Algorithm

In the FCFS algorithm, disk I/O requests are serviced in the order they arrive. The disk arm moves to the requested track and services the request without considering the distance to the next request. FCFS is simple to implement but can lead to high average seek times, especially if there are large variations in seek times between requests.

Example: Consider a disk with requests to access tracks 98, 183, 37, 122, 14, and the current position of the disk arm is at track 53. The FCFS algorithm would service the requests in the order they are listed, regardless of the actual distance between tracks.

Advantages: FCFS is easy to implement and ensures fairness, as requests are serviced in the order they are received.

Disadvantages: FCFS can lead to poor performance due to high seek times, especially if there are large variations in seek times between requests.

Shortest Seek Time First (SSTF) Algorithm

SSTF selects the request with the shortest seek time from the current position of the disk arm. This algorithm aims to minimise the total seek time by always servicing the nearest request next. SSTF can result in a significant reduction in average seek time compared to FCFS but may suffer from starvation, where requests at the outer tracks are frequently skipped.

Example: Using the same example as before, if the disk arm is at track 53 and the requests are to access tracks 98, 183, 37, 122, and 14, SSTF would service the request to track 37 first, as it has the shortest seek time from track 53.

Advantages: SSTF can significantly reduce average seek time compared to FCFS, leading to improved disk performance.

Disadvantages: SSTF may suffer from starvation, where requests at the outer tracks are frequently skipped in favour of servicing requests closer to the current position of the disk arm.

SCAN Algorithm

The SCAN algorithm (also known as the elevator algorithm) moves the disk arm in one direction across the disk, servicing requests along the way. When the arm reaches the end of the disk, it reverses direction and scans back to the other end. SCAN aims to minimise the average seek time by servicing requests in a back-and-forth manner.

Example: Using the same example, if the disk arm is at track 53 and the requests are to access tracks 98, 183, 37, 122, and 14, SCAN would first service requests in the direction of movement (e.g., tracks 98, 122), then reverse direction and service requests in the other direction (e.g., tracks 37, 14).

Advantages: SCAN can provide a good balance between fairness and performance by servicing requests in a back-and-forth manner.

Disadvantages: SCAN may not be optimal for systems with high variance in request distribution, as requests at the ends of the disk may experience longer wait times.

C-SCAN Algorithm

The C-SCAN algorithm is a variant of SCAN that only scans in one direction, servicing requests until it reaches the end of the disk, at which point it jumps back to the beginning of the disk and continues scanning. C-SCAN aims to reduce the variance in service times compared to SCAN by ensuring that all requests are serviced in the same direction.

Example: Using the same example, if the disk arm is at track 53 and the requests are to access tracks 98, 183, 37, 122, and 14, C-SCAN would first service requests in the direction of movement (e.g., tracks 98, 122), then jump back to the beginning of the disk and continue servicing requests in the same direction (e.g., tracks 14, 37).

Advantages: C-SCAN can reduce the variance in service times compared to SCAN by ensuring that all requests are serviced in the same direction.

Disadvantages: C-SCAN may lead to increased average seek times compared to SCAN, especially if there are requests at both ends of the disk.

LOOK Algorithm

The LOOK algorithm is a variant of SCAN that services requests only until it reaches the last request in the current direction, at which point it reverses direction without reaching the end of the disk. LOOK aims to reduce the average seek time compared to SCAN by avoiding unnecessary scanning to the ends of the disk.

Example: Using the same example, if the disk arm is at track 53 and the requests are to access tracks 98, 183, 37, 122, and 14, LOOK would first service requests in the direction of movement (e.g., tracks 98, 122), then reverse direction and service requests in the other direction (e.g., tracks 37, 14), stopping before reaching the ends of the disk.

Advantages: LOOK can reduce the average seek time compared to SCAN by avoiding unnecessary scanning to the ends of the disk.

Disadvantages: LOOK may not be optimal for systems with high variance in request distribution, as requests at the ends of the disk may experience longer wait times.

C-LOOK Algorithm

The C-LOOK algorithm is a variant of LOOK that only scans in one direction, servicing requests until it reaches the last request in that direction before jumping back to the beginning of the disk. C-LOOK aims to reduce the variance in service times compared to LOOK by ensuring that all requests are serviced in the same direction.

Example: Using the same example, if the disk arm is at track 53 and the requests are to access tracks 98, 183, 37, 122, and 14, C-LOOK would first service requests in the direction of movement (e.g., tracks 98, 122), then jump back to the beginning of the disk and continue servicing requests in the same direction (e.g., tracks 14, 37).

Advantages: C-LOOK can reduce the variance in service times compared to LOOK by ensuring that all requests are serviced in the same direction.

Disadvantages: C-LOOK may lead to increased average seek times compared to LOOK, especially if there are requests at both ends of the disk.

Various Disk Scheduling Policies

Algorithm	Description	Advantages	Disadvantages
First-Come-First-Served	Services requests in the order they arrive.	Simple implementation ensures fairness.	May result in high average seek times.
Shortest Seek Time First	Selects the request with the shortest seek time from the current position of the disk arm.	Minimises average seek time.	May suffer from starvation.
SCAN	Moves the disk arm in one direction across the disk, servicing requests along the way, then reverses direction and scans back.	Provides a good balance between fairness and performance.	May not be optimal for systems with high variance in request distribution.
C-SCAN	Scans in one direction until it reaches the end of the disk, then jumps back to the beginning.	Reduces variance in service times.	May lead to increased average seek times.
LOOK	Services requests only until it reaches the last request in the current direction, then reverses direction.	Reduces average seek time compared to SCAN.	Requests at the ends of the disk may experience longer wait times.
C-LOOK	Scans in one direction until it reaches the last request, then jumps back to the beginning.	Reduces variance in service times.	May lead to increased average seek times.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article.