In my Operating Systems class, we have to present one algorithm as our final project. A mock model for any of the OS algorithms. I choose an algorithm which is an improved/variation of regular SSTF algorithm. It is called Circular SSTF. I have already implemented SSTF in python. But I can’t figure out a way to implement Circular SSTF. Any help or tips on that will be much appreciated.
Here’s an explanation of both the algorithms.
Given Suppose that the requests are : 98, 183, 37, 122, 14, 124, 65, 67.
- Assume that in the beginning, the disk head is at cylinder 53.
- Suppose that the device queue length is 20 requests.
- Assume that moving the head from one track to the next takes 1 ms.
- Ignore the service time.
Based on SSTF algorithm the OS will allocate the requests in the following manner,
The order is : 53, 65, 67, 37, 14, 98, 122, 124, 183. Total head
movement : 12+2+30+23+84+24+2+59 = 236 tracks.
In this algorithm, we first check which of the requests is closer to the current head (53 in this case). The closest is 65 and then 65 becomes the current head, the closest to that is 67 and then 67 becomes the current hear and thus the algorithm is continued.
Based on Circular SSTF algorithm the OS will allocate the request in the following manner,
The order is : 53, 65, 67, 37, 14, 183, 124, 122, 98.
Total head movement : 12+2+30+23+31+59+2+24 = 183 tracks.
In the Circular SSTF the algorithm will switch if the too many requests are closer to either of the end (0-199). Thus, instead of going to 98 from 14 the algorithm forces to serve 183 because it is closer to the other end.
Also, sorry for my bad english. Been a while since I’d to write something this elaborative and technical.
Edit 1. Described the algorithms and removed the code as it could cause unnecessary confusion.
Advertisement
Answer
The key difference between SSTF and Circular SSTF would be how the difference between head and sector is calculated. While it is simple modular difference for SSTF, in Circular SSTF it becomes:
def difference(head, sector, end=199):
diff1 = abs(head-sector) # going straight from head to sector
diff2 = head + (end-sector) # going to 0 and then from end to sector
diff3 = (end-head) + sector # going to end and then going from 0 to sector
return min([diff1, diff2, diff3])
Ran your input against this, returned
The order will be: 65 67 37 14 183 124 122 98 Output with SSTF algorithm: Head Movement: 182