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 ?
120 milliseconds
Understanding SSTF Disk Scheduling
The question asks us to calculate the total time taken to satisfy a sequence of disk requests using the Shortest Seek Time First (SSTF) disk scheduling algorithm. We are given the initial position of the disk head and the time required to move between adjacent cylinders.
The Shortest Seek Time First (SSTF) algorithm selects the request with the minimum seek time from the current head position. This means it chooses the request that is closest to the current cylinder number. SSTF aims to minimize the total seek time but can sometimes lead to starvation for requests located far away from the current head position.
Applying SSTF Algorithm Step-by-Step
We start with the disk head at cylinder 20. The sequence of pending requests is 10, 22, 20, 2, 40, 6, and 38.
Initial Head Position: 20
Pending Requests: {10, 22, 20, 2, 40, 6, 38}
Let's track the movement and calculate the total distance:
| Step | Current Cylinder | Pending Requests | Distances to Pending Requests | Closest Request | Distance Moved | Total Distance (Cylinders) |
|---|---|---|---|---|---|---|
| 1 | 20 | {10, 22, 20, 2, 40, 6, 38} | $|10-20|=10, |22-20|=2, |20-20|=0, |2-20|=18, |40-20|=20, |6-20|=14, |38-20|=18$ | 20 | $|20-20|=0$ | 0 |
| 2 | 20 | {10, 22, 2, 40, 6, 38} | $|10-20|=10, |22-20|=2, |2-20|=18, |40-20|=20, |6-20|=14, |38-20|=18$ | 22 | $|22-20|=2$ | $0 + 2 = 2$ |
| 3 | 22 | {10, 2, 40, 6, 38} | $|10-22|=12, |2-22|=20, |40-22|=18, |6-22|=16, |38-22|=16$ | 10 | $|10-22|=12$ | $2 + 12 = 14$ |
| 4 | 10 | {2, 40, 6, 38} | $|2-10|=8, |40-10|=30, |6-10|=4, |38-10|=28$ | 6 | $|6-10|=4$ | $14 + 4 = 18$ |
| 5 | 6 | {2, 40, 38} | $|2-6|=4, |40-6|=34, |38-6|=32$ | 2 | $|2-6|=4$ | $18 + 4 = 22$ |
| 6 | 2 | {40, 38} | $|40-2|=38, |38-2|=36$ | 38 | $|38-2|=36$ | $22 + 36 = 58$ |
| 7 | 38 | {40} | $|40-38|=2$ | 40 | $|40-38|=2$ | $58 + 2 = 60$ |
The total seek distance travelled by the disk head is 60 cylinders.
Calculating Total Seek Time in Disk Scheduling
We are given that it takes 2 milliseconds to move from one cylinder to an adjacent one.
Total time taken = Total seek distance $\times$ Time per cylinder movement
Total time taken = $60 \text{ cylinders} \times 2 \text{ ms/cylinder}$
Total time taken = $120 \text{ milliseconds}$
Therefore, the total time taken to satisfy all the requests using the SSTF algorithm is 120 milliseconds.
Disk Scheduling Algorithms Revision
Disk scheduling algorithms are used to decide the order in which disk I/O requests are serviced. Their goal is to minimize total seek time and improve disk throughput.
Common Disk Scheduling Algorithms include:
- First-Come, First-Served (FCFS)
- Shortest Seek Time First (SSTF)
- SCAN (Elevator Algorithm)
- C-SCAN (Circular SCAN)
- LOOK
- C-LOOK
Each algorithm has its own advantages and disadvantages regarding fairness, throughput, and variance in response time.
Additional Information on Disk Management
Disk management is crucial for operating system performance. Efficient disk scheduling is part of this management. Factors affecting disk performance include seek time, rotational latency, and transfer time.
- Seek Time: The time taken for the disk arm to move to the cylinder containing the desired sector. SSTF primarily focuses on optimizing this.
- Rotational Latency: The time taken for the desired sector to rotate under the disk head.
- Transfer Time: The time taken to actually read or write the data once the head is at the correct cylinder and sector.
SSTF is often better than FCFS in terms of average seek time but can lead to starvation, where requests far from the current head position might wait indefinitely if new requests near the head keep arriving.
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 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.
