Disk Scheduling algorithms


First Come First Served Scheduling

In this algorithm, the request which arrived first is the first to be served. There is no reordering of the queue. Once the request has arrived, its place in the  schedule is fixed. The place of the request cannot be displaced due to the arrival of higher priority request.
 
  • The one drawback in FCFS scheduling do a lengthy seek if the next waiting request to service is at a long distant, even though another request have just arrived present on the same cylinder to which the read-write head is currently positioned.
  • It results in random seek pattern, if the requests are uniformly distributed throughout the disk.
  • The positional relationships between requests are ignored in this method. No optimization of seek pattern is attempted.
  • When there are only few requests or in light load situation this method is appreciable.


FCFS saturate the device and response times become large. It offers small variance. Fig above depicts this method of scheduling.In the figure the scheduling is based on First come first served basis. The number indicates the order of request arrived

Shortest Seek Time First Scheduling

In SSTF, the request that results in the shortest seek distance is serviced next, even if that request is not the first one in the queue. Disk arm is positioned next at the request, either inward or outward, that minimizes arm movement. It is a cylinder oriented scheme.
 
  • SSTF seek patterns tend to be highly localized with the result that the innermost and outermost tracks can receive poor service compared with the mid-range tracks.
  • It has high throughput compared to FCFS.
  • The mean response time is minimized for moderate loads.
  • The drawback in this scheduling method is results in higher variances because of the discrimination against the outermost and innermost tracks.
  • This higher variance is tolerable when considering higher throughput and less response time.
  • It is mainly used in batch processing systems where throughput is important.

Fig above explains this disk scheduling scheme.

Want to know about other algorithms in disk scheduling? Visit again…