Understanding Disk Scheduling and SSTF

Disk scheduling is a crucial part of operating systems that manages the order in which disk I/O requests are serviced. The goal is typically to minimize the total head movement and thus the access time, improving the overall performance of the disk.

The question asks us to apply the Shortest Seek Time First (SSTF) disk scheduling policy. SSTF chooses the request closest to the current head position. This strategy aims to minimize the immediate seek time but can sometimes lead to starvation for requests located far away from the current position.

Analyzing the Disk Access Requests

We are given the following information:

• Number of cylinders: 100 (cylinders 0 to 99).
• Initial head position: Cylinder 50.
• Sequence of requests: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20.
• Time taken to move between adjacent cylinders: 1 ms.

We need to find the total time taken to service all requests using the SSTF algorithm.

Applying the Shortest Seek Time First (SSTF) Algorithm

The SSTF algorithm works by selecting the request that has the minimum distance from the current head position among all pending requests. We start at cylinder 50 and service the requests one by one based on this policy.

Let's trace the execution:

1. Start at 50. Pending requests: {4, 34, 10, 7, 19, 73, 2, 15, 6, 20}. Calculate distances from 50:
   • |50 - 4| = 46
   • |50 - 34| = 16
   • |50 - 10| = 40
   • |50 - 7| = 43
   • |50 - 19| = 31
   • |50 - 73| = 23
   • |50 - 2| = 48
   • |50 - 15| = 35
   • |50 - 6| = 44
   • |50 - 20| = 30
   The minimum distance is 16 to cylinder 34. Move from 50 to 34. Head movement: \(|50 - 34| = 16\). Current position: 34. Requests serviced: {34}.
2. Current position: 34. Pending requests: {4, 10, 7, 19, 73, 2, 15, 6, 20}. Calculate distances from 34:
   • |34 - 4| = 30
   • |34 - 10| = 24
   • |34 - 7| = 27
   • |34 - 19| = 15
   • |34 - 73| = 39
   • |34 - 2| = 32
   • |34 - 15| = 19
   • |34 - 6| = 28
   • |34 - 20| = 14
   The minimum distance is 14 to cylinder 20. Move from 34 to 20. Head movement: \(|34 - 20| = 14\). Current position: 20. Requests serviced: {34, 20}.
3. Current position: 20. Pending requests: {4, 10, 7, 19, 73, 2, 15, 6}. Calculate distances from 20: |20-4|=16, |20-10|=10, |20-7|=13, |20-19|=1, |20-73|=53, |20-2|=18, |20-15|=5, |20-6|=14. The minimum distance is 1 to cylinder 19. Move from 20 to 19. Head movement: \(|20 - 19| = 1\). Current position: 19. Requests serviced: {34, 20, 19}.
4. Current position: 19. Pending requests: {4, 10, 7, 73, 2, 15, 6}. Calculate distances from 19: |19-4|=15, |19-10|=9, |19-7|=12, |19-73|=54, |19-2|=17, |19-15|=4, |19-6|=13. The minimum distance is 4 to cylinder 15. Move from 19 to 15. Head movement: \(|19 - 15| = 4\). Current position: 15. Requests serviced: {34, 20, 19, 15}.
5. Current position: 15. Pending requests: {4, 10, 7, 73, 2, 6}. Calculate distances from 15: |15-4|=11, |15-10|=5, |15-7|=8, |15-73|=58, |15-2|=13, |15-6|=9. The minimum distance is 5 to cylinder 10. Move from 15 to 10. Head movement: \(|15 - 10| = 5\). Current position: 10. Requests serviced: {34, 20, 19, 15, 10}.
6. Current position: 10. Pending requests: {4, 7, 73, 2, 6}. Calculate distances from 10: |10-4|=6, |10-7|=3, |10-73|=63, |10-2|=8, |10-6|=4. The minimum distance is 3 to cylinder 7. Move from 10 to 7. Head movement: \(|10 - 7| = 3\). Current position: 7. Requests serviced: {34, 20, 19, 15, 10, 7}.
7. Current position: 7. Pending requests: {4, 73, 2, 6}. Calculate distances from 7: |7-4|=3, |7-73|=66, |7-2|=5, |7-6|=1. The minimum distance is 1 to cylinder 6. Move from 7 to 6. Head movement: \(|7 - 6| = 1\). Current position: 6. Requests serviced: {34, 20, 19, 15, 10, 7, 6}.
8. Current position: 6. Pending requests: {4, 73, 2}. Calculate distances from 6: |6-4|=2, |6-73|=67, |6-2|=4. The minimum distance is 2 to cylinder 4. Move from 6 to 4. Head movement: \(|6 - 4| = 2\). Current position: 4. Requests serviced: {34, 20, 19, 15, 10, 7, 6, 4}.
9. Current position: 4. Pending requests: {73, 2}. Calculate distances from 4: |4-73|=69, |4-2|=2. The minimum distance is 2 to cylinder 2. Move from 4 to 2. Head movement: \(|4 - 2| = 2\). Current position: 2. Requests serviced: {34, 20, 19, 15, 10, 7, 6, 4, 2}.
10. Current position: 2. Pending requests: {73}. Calculate distances from 2: |2-73|=71. The minimum distance is 71 to cylinder 73. Move from 2 to 73. Head movement: \(|2 - 73| = 71\). Current position: 73. Requests serviced: {34, 20, 19, 15, 10, 7, 6, 4, 2, 73}.

Calculating Total Head Movement

Let's sum the head movements for each step:

Total head movement = \(16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71 = 119\) cylinders.

Calculating Total Time Taken

The time taken to move from one cylinder to an adjacent one is given as 1 ms.

Total time = Total head movement \(\times\) Time per cylinder movement

Total time = \(119 \text{ cylinders} \times 1 \text{ ms/cylinder} = 119 \text{ ms}\).

Therefore, the total time taken to satisfy all requests using the SSTF policy is 119 ms.

Revision Table: SSTF Disk Scheduling Key Points

Additional Information: Comparing Disk Scheduling Algorithms

SSTF is one of several disk scheduling algorithms. Other common algorithms include:

• FCFS (First-Come, First-Served): Services requests in the order they arrive. Simple, but can result in large head movements.
• SCAN (Elevator Algorithm): The head moves in one direction, servicing all requests in its path, until it reaches the end of the disk or the farthest request in that direction. Then it reverses direction.
• C-SCAN (Circular SCAN): Similar to SCAN, but after reaching one end, it immediately returns to the other end without servicing requests on the return trip. It then starts scanning from the other end. This provides a more uniform wait time compared to SCAN.
• LOOK and C-LOOK: Variants of SCAN and C-SCAN where the head only goes as far as the farthest request in each direction, rather than going all the way to the end of the disk.

Each algorithm has its own trade-offs in terms of average seek time, variance in seek time, and fairness (preventing starvation).