Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67. Suppose SSTF disk scheduling algorithm implemented to meet the requests then the total number of head movements are ______ if the disk head is initially at 53.
236
Understanding Disk Scheduling with SSTF
Disk scheduling algorithms are used in operating systems to determine the order in which disk I/O requests are serviced. This helps to minimize the total seek time, which is the time it takes for the disk arm to move to the cylinder containing the requested data. The Shortest Seek Time First (SSTF) algorithm selects the request with the minimum seek time from the current head position.
Applying the SSTF Algorithm
We are given a disk queue with I/O requests for the following cylinders: 98, 183, 37, 122, 14, 124, 65, 67. The disk head is initially positioned at cylinder 53. We need to calculate the total head movements using the SSTF algorithm.
The SSTF algorithm works by always choosing the request that is closest to the current head position. Let's trace the steps:
- Initial Position: Head is at cylinder 53.
- Pending Requests: 98, 183, 37, 122, 14, 124, 65, 67.
Now, we find the shortest distance from the current position (53) to each pending request:
- To 98: \(|98 - 53| = 45\)
- To 183: \(|183 - 53| = 130\)
- To 37: \(|37 - 53| = |-16| = 16\)
- To 122: \(|122 - 53| = 69\)
- To 14: \(|14 - 53| = |-39| = 39\)
- To 124: \(|124 - 53| = 71\)
- To 65: \(|65 - 53| = 12\)
- To 67: \(|67 - 53| = 14\)
The shortest distance is 12, corresponding to cylinder 65. So, the head moves to 65.
Let's track the head movements step-by-step using a table:
| Current Position | Requests to Service | Distances from Current Position | Next Request (Shortest Seek) | Movement | Total Movement |
|---|---|---|---|---|---|
| 53 | 98, 183, 37, 122, 14, 124, 65, 67 | |98-53|=45, |183-53|=130, |37-53|=16, |122-53|=69, |14-53|=39, |124-53|=71, |65-53|=12, |67-53|=14 | 65 (Distance 12) | 12 | 12 |
| 65 | 98, 183, 37, 122, 14, 124, 67 | |98-65|=33, |183-65|=118, |37-65|=28, |122-65|=57, |14-65|=51, |124-65|=59, |67-65|=2 | 67 (Distance 2) | 2 | 12 + 2 = 14 |
| 67 | 98, 183, 37, 122, 14, 124 | |98-67|=31, |183-67|=116, |37-67|=30, |122-67|=55, |14-67|=53, |124-67|=57 | 37 (Distance 30) | 30 | 14 + 30 = 44 |
| 37 | 98, 183, 122, 14, 124 | |98-37|=61, |183-37|=146, |122-37|=85, |14-37|=23, |124-37|=87 | 14 (Distance 23) | 23 | 44 + 23 = 67 |
| 14 | 98, 183, 122, 124 | |98-14|=84, |183-14|=169, |122-14|=108, |124-14|=110 | 98 (Distance 84) | 84 | 67 + 84 = 151 |
| 98 | 183, 122, 124 | |183-98|=85, |122-98|=24, |124-98|=26 | 122 (Distance 24) | 24 | 151 + 24 = 175 |
| 122 | 183, 124 | |183-122|=61, |124-122|=2 | 124 (Distance 2) | 2 | 175 + 2 = 177 |
| 124 | 183 | |183-124|=59 | 183 (Distance 59) | 59 | 177 + 59 = 236 |
The sequence of cylinder visits is: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183.
The total head movement is the sum of the movements in each step:
\( \text{Total Movement} = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 \)
Therefore, the total number of head movements using the SSTF disk scheduling algorithm is 236.
Revision Table: SSTF Disk Scheduling Concepts
| Concept | Description | Goal |
|---|---|---|
| Disk Scheduling | Methods used by operating systems to order disk I/O requests. | Optimize disk performance (reduce seek time, rotational latency, and transfer time). |
| SSTF (Shortest Seek Time First) | A disk scheduling algorithm that selects the pending request closest to the current head position. | Minimize total head movement (seek time). |
| Head Movement | The distance the disk head travels from one cylinder to another. Calculated as the absolute difference between the cylinder numbers. | A key metric used to evaluate disk scheduling algorithms; lower is generally better. |
Additional Information on Disk Scheduling Algorithms
While SSTF aims to minimize total head movement, it can suffer from starvation, where requests far from the head might wait indefinitely if there is a constant stream of requests close to the head. Other disk scheduling algorithms include:
- FCFS (First-Come, First-Served): Services requests in the order they arrive. Simple, but can lead to large head movements.
- SCAN (Elevator Algorithm): Moves the head in one direction, servicing requests along the way, until it reaches the end of the disk or the last request in that direction, then 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 services requests only when moving in one direction.
- LOOK and C-LOOK: Variations of SCAN and C-SCAN that only travel as far as the last request in a direction, rather than going all the way to the end of the disk.
The choice of disk scheduling algorithm depends on the workload and the desired balance between minimizing seek time, preventing starvation, and fairness.
Important Questions from Disk Scheduling - Teaching
Disc is divided into several concentric circles called _______.
In _______ disk scheduling algorithm, the disk head moves from one end to other end of the disk, serving the requests along the way. When the head reaches the other end, it immediately returns to the beginning of the disk without serving any requests on the return trip.
The total storage capacity of a floppy disk having 80 tracks and storing 128 bytes/sector is 163.840 bytes. How many sectors does this disk have?
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in the following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is current at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from the cylinder to adjacent one and the shortest seek time first policy is used?Consider a disk system having 60 cylinders. Disk requests are received by a disk drive for cylinders 10, 22, 20, 2, 40, 6, and 38, in that order. Assuming the disk head is currently at cylinder 20, what is the time taken to satisfy all the requests if it takes 2 milliseconds to move from one cylinder to an adjacent one and Shortest Seek Time First (SSTF) algorithm is used ?
