Explain techniques of disk scheduling.

Mumbai University > Computer Engineering > Sem 5 > Operating System

Marks: 10M

Years: Dec 2015

1 Answer

Various types of disk scheduling algorithms are as follows:

1. FCFS(First Come First Served) Scheduling:

  • Request are served in the order of their arrival.

  • Consider an e.g. a disk queue with request for I/O to block cylinders. 98, 183, 37, 122, 14, 124, 65, 67 in that order. If the disk head is at initially at cylinder 53, it will move 53 to 98 and then 183, 37 so on.

  • Total head movement =640 cylinders.

enter image description here

2. Shortest seek time first (SSTF) scheduling:

  • We can minimized the head movement by servicing the request closest to the current position of head.

  • Consider an e.g. same as the above one. 98, 183, 37, 122, 14, 124, 65, 67. Current head position at 53.

  • So closest request to initial head position 53 is at cylinder 65. Once we are at cylinder 65, next closest request is at cylinder 67, then request 37 as compared to 98. The request are served as shown in fig below.

enter image description here

3. SCAN Scheduling:

  • The two scheduling algorithms which we have discussed above serves the request in one direction.

  • The disk arm starts at one end of the disk and moves towards the other end. Servicing request as it reaches each cylinder until it get to the other end of the disk. At the other end, the direction of head movement is reserved and servicing continues.

  • Before applying SCAN to schedule request direction of head movement is necessary to know. e.g. 98, 183, 37, 122, 14, 124, 65, 67.

  • Current head position at cylinder 53.

  • Direction of head movement is towards 0. The head will service the requests at 37 and 14. At cylinder 0, the arm will reverse and move towards other end of the disk servicing request at 65, 67, 98, 122, 124 and 183.

  • This algorithm is also called as an elevator algorithm. It is because the disk arm behaves like an elevator in a building, first serving all the request going up and then reversing to service request the other way.

  • If a request arrives in the queue just in front of the head it will be serviced immediately, a request arriving just behind the head will have to wait until the arm moves to the ends of the disk, reverse direction come back.

enter image description here

4. C-SCAN scheduling:

  • In the above algorithm, if there are few request in front of head, these request will be served immediately. The heaviest density of request is at the other end of the disk. The request have waited longer.

  • This scheduling algorithm provides more uniform wait time C-SCAN moves the head from one end of the disk to the other, servicing request along the way. When the head reaches the other end, it immediately returns to the beginning of the disk without servicing any request on the return trip.

  • Consider an e.g. Queue=98, 183, 37, 122, 14, 124, 65, 67. Head starts at 53.

enter image description here

5. Look and C Look scheduling algorithm:

  • As we have seen in SCAN and C-SCAN the disk arm moves across the full width of the disk. But practically algorithm is not implemented this way.

  • Practically, the arm goes only as far as the final request in each direction. Then it reverses its direction, without first going all the way to the end of the disk. Let us see the same example for look scheduling queue: 98, 183, 37, 122, 14, 124, 65, 67. Head starts: 53

  • Look and C-Look are the versions of SCAN and C-SCAN because they look for a request before continuing to move in a given direction.

enter image description here

Please log in to add an answer.