Compare the following Disk scheduling algorithms using appropriate example. SSTF, FCFS, SCAN , C-SCAN, LOOK

636views

written 3.1 years ago by

binitamayekar ★ 6.6k

Comparative Difference between various Disk Scheduling Algorithms

FCFS	SSTF	SCAN	C-SCAN	LOOK
First Come-First Serve	Shortest Seek Time First	Elevator Algorithm	Circular SCAN	LOOK
It services the IO requests in the order in which they arrive.	Selects the disk I/O request which requires the least disk arm movement from its current position regardless of the direction.	The disk arm moves into a particular direction till the end, satisfying all the requests coming in its path, and then it turns back and moves in the reverse direction satisfying requests coming in its path.	The arm of the disk moves in a particular direction servicing requests until it reaches the last cylinder, then it jumps to the last cylinder of the opposite direction without servicing any request then it turns back and starts moving in that direction servicing the remaining requests.	The arm of the disk stops moving inwards or outwards when no more requests in that direction exist.
There is no starvation in this algorithm, every request is serviced.	It may cause starvation for some requests.	Starvation is still possible in this scheduling.	It will never cause starvation to any requests.	It avoids starvation of any requests.
The scheme does not optimize the seek time.	It reduces the total seek time as compared to FCFS.	It offers an improved variance of seek time as compared to SSTF.	It offers an improved variance of seek time as compared to SCAN.	It offers a more improved variance of seek time as compared to C-SCAN.
This is acceptable when the load on a disk is light and small systems where efficiency is not important.	It is a reasonable solution for batch processing systems but not applicable for interactive systems.	Under a light load, SCAN policy is best.	Under a heavy load, C-SCAN policy is best.	Under extremely heavy load, LOOK policy is best.
May not provide the best possible service in terms of good waiting & response time.	High variance is present in response & waiting time.	Low variance occurs in waiting & response time.	Uniform waiting time & better response time is provided.	Very low variance provided in waiting & response time.
It has extremely low throughput due to lengthy seeks.	It has higher throughput than FCFS.	It has higher throughput than FCFS, SSTF.	It maintains a high level of throughput by avoiding discrimination against the innermost and outermost cylinders.	It gives extremely high throughput by avoiding unnecessary seek operation.
*Disadvantages:* The short processes which are at the back of the queue have to wait for the long process at the front to finish	*Disadvantages:* There is an overhead of finding out the closest request. Frequent switching of the Head’s direction slows the algorithm.	*Disadvantages:* Long waiting time occurs for the cylinders which are just visited by the head. In SCAN the head moves till the end of the disk despite the absence of requests to be serviced.	*Disadvantages:* More seek movements are caused in C-SCAN compared to SCAN Algorithm. In C-SCAN even if there are no requests left to be serviced the Head will still travel to the end of the disk.	*Disadvantages:* Overhead of finding the end requests is present. Cylinders that are just visited by Head have to wait for a long time.

Example:

Consider a disk with 200 tracks (0-199) and that the disk request queue has random requests in it. The following track requests for I/O to blocks on cylinders:

60, 143, 15, 185, 85, 120, 33, 28, 146

Consider that the read/write head is initially at cylinder 70. Compute the total head movements for a 200 track disk (0-199)

FCFS	SSTF	SCAN	C-SCAN	LOOK
*Total Head Movements =* (70-60) + (143-60) + (143-15) + (185-15) + (185-85) + (120-85) + (120-33) + (33-28) + (146-28) = 736 cylinders	*Total Head Movements =* (70-60) + (85-60) + (120-85) + (143-120) + (146-143) + (185-146) + (185-33) + (33-28) + (28-15) = 305 cylinders	*Total Head Movements =* (199-70) + (199-15)= 313 cylinders.	*Total Head Movements =* (199-70) + (199-0) + (60-0) = 388 cylinders	*Total Head Movements =* (185-70) + (185-15)= 285 cylinders

ADD COMMENT EDIT