If you are new to disk scheduling then please read about basics of disk scheduling first and then read this post.
Today we will be discussing about SCAN disk scheduling - operating system tutorial. In the last post where I discussed about SSTF disk scheduling we saw that starvation was a major issue due to which the request far away from read/write head had to starve. Let's see how SCAN disk scheduling avoids starvation:
SCAN Disk Scheduling
In this we move the read/write head from one end to the other end fulfilling the requests which came in between and when we reach the end the we start moving from this end to other end. This process continues until we don't fulfill all request. This method is also called elevator algorithm.
Let's solve a problem for better understanding of the concept.
Let say we have the following requests:
98,183,41,122,14,124,65,67
Show the order of fulfilling the requests using SCAN algorithm. Assume read/write head is at 53.
soln.
2. We move towards right and satisfy the request 65.
3. We continue moving towards right until end comes. Now we reach 67 so we satisfy 67.
4. We continue moving towards right until end comes. Now we reach 98 so we satisfy 98.
5. We continue moving towards right until end comes. Now we reach 122 so we satisfy 122.
6. We continue moving towards right until end comes. Now we reach 124 so we satisfy 124.
7. We continue moving towards right until end comes. Now we reach 183 so we satisfy 183.
8. Now we have reached 199 which is the end so we move backwards again until we reach the last request.
9. We move towards left until last request comes. Now we reach 41 so we satisfy 41.
10. We continue moving towards left until last request comes. Now we reach 14 so we satisfy 14.
11. Since 14 was the last request so we stop here.
12. Total seek movements are (65-53)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)+(199-183)+(199-41)+(41-14) = 331.
Advantages
1. Simple and easy to understand.
2. No request suffers from starvation.
3. Low variance and average waiting time.
Disadvantages
1. If head is moving towards one direction then the tracks which were most close to the read/write head will have no more request at-least for sometime and the tracks whose requests were satisfied most early will most likely come up with another request then these requests will have to starve for a longer time.
2. The read/write head is moved unnecessarily to the end of the disk even if it was no request.