1. FCFS (First Come First Served)
The FCFS algorithm serves requests in the order they arrive in the queue, similar to a queue (first in, first out). This algorithm processes each request in the order it appears in the request queue.
- Advantage: Simple to implement and easy to understand.
- Disadvantage: Can lead to higher seek times if requests are scattered across the disk.
Example:
Request Queue: 34, 12, 50, 180, 90
Current Head Position: 50
FCFS would service requests in the order listed, resulting in a total seek time of:
(50 - 34) + (34 - 12) + (12 - 50) + (50 - 180) + (180 - 90) = 324
2. SSTF (Shortest Seek Time First)
SSTF prioritizes the request with the shortest seek time from the current head position. The algorithm chooses the request that is closest to the current head position, minimizing seek time and movement.
- Advantage: Generally reduces seek time compared to FCFS.
- Disadvantage: Can lead to starvation for requests far from the head, as the head keeps serving closer requests.
Example:
Request Queue: 98, 183, 30, 110, 50
Current Head Position: 50
SSTF would service requests in this order:
50 -> 30 -> 50 -> 98 -> 110 -> 183 (assuming the head moves right first)
Total seek time: (50 - 30) + (30 - 98) + (98 - 110) + (110 - 183) = 201 (better than FCFS)
3. SCAN (Elevator Algorithm)
SCAN is known as the "elevator algorithm" because it works like an elevator servicing floors in a building. The algorithm moves the head in one direction (e.g., right) and services requests along the way until it reaches the end of the disk. It then reverses direction and services requests on the way back.
- Advantage: Efficient for scenarios where requests are clustered in specific areas.
- Disadvantage: Can be slow for randomly distributed requests.
Example:
Request Queue: 82, 170, 43, 140, 200, 120
Current Head Position: 50 (moving right)
SCAN would service requests in this order:
50 -> 82 -> 120 -> 140 -> 170 -> 200 -> 43 (assuming head reverses after reaching 200)
4. C-SCAN (Circular SCAN)
C-SCAN treats the disk as a circular track. Once the head reaches the end of the disk, it immediately jumps back to the beginning and continues servicing requests in the same direction. This algorithm provides a more uniform wait time for each request.
- Advantage: Eliminates the need for extra seek time at the end of the disk platter.
- Disadvantage: Similar limitations as SCAN for randomly distributed requests.
Example:
Request Queue: 82, 170, 43, 140, 200, 120
Current Head Position: 50 (moving right)
C-SCAN would service requests in this order:
50 -> 82 -> 120 -> 140 -> 170 -> 200 -> Immediately jumps back to 43
5. LOOK
LOOK is similar to SCAN but stops before reaching the end of the disk. Once the head reaches the last request in the current direction, it reverses and services only the pending requests in the new direction.
- Advantage: Reduces seek time compared to SCAN by not servicing requests in the opposite direction during a pass.
- Disadvantage: Shares limitations with SCAN for random requests.
Example:
Request Queue: 82, 170, 43, 140, 200, 120
Current Head Position: 50 (moving right)
LOOK would service requests in this order:
50 -> 82 -> 120 -> 140 -> 170, then reverse direction: 170 -> 43 -> 200
6. C-LOOK (Circular LOOK)
C-LOOK is an enhanced version of LOOK, treating the disk as a circular track. The head jumps from the end in the current direction to the beginning and immediately starts servicing requests in the new direction.
- Advantage: Improves upon LOOK by eliminating unnecessary movement at the end of the disk and reduces seek time compared to SCAN.
- Disadvantage: Similar to LOOK, it might not be ideal for randomly distributed requests.
Example:
Request Queue: 82, 170, 43, 140, 200, 120
Current Head Position: 50 (moving right)
C-LOOK would service requests in this order:
50 -> 82 -> 120 -> 140 -> 170 -> Immediately jumps back to 43 and continues servicing -> 200