Subject: Operating System

Topic: STORAGE MANAGEMENT

Difficulty: Hard

In operating systems, seek time is very important. Since all device requests are linked in queues, the seek time is increased causing the system to slow down. Disk Scheduling Algorithms are used to reduce the total seek time of any request.

Types of disk scheduling algorithms

• First Come-First Serve (FCFS)

• Shortest Seek Time First (SSTF)

• Elevator (SCAN)

• Circular SCAN (C-SCAN)

• LOOK And C-LOOK

Given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199 let us now discuss the different algorithms.

First Come -First Serve (FCFS):

All incoming requests are placed at the end of the queue. Whatever number that is next in the queue will be the next number served. Using this algorithm doesn't provide the best results. To determine the number of head movements you would simply find the number of tracks it took to move from one request to the next. For this case it went from 50 to 95 to 180 and so on. From 50 to 95 it moved 45 tracks.

If you tally up the total number of tracks you will find how many tracks it had to go through before finishing the entire request. In this example, it had a total head movement of 640 tracks.

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.

The disadvantage of this algorithm is noted by the oscillation from track 50 to track 180 and then back to track 11 to 123 then to 64. As you will soon see, this is the worse algorithm that one can use.

Shortest Seek Time First (SSTF):

In this case request is serviced according to next shortest distance. Starting at 50, the next shortest distance would be 62 instead of 34 since it is only 12 tracks away from 62 and 16 tracks away from 34.

The process would continue until all the process are taken care of. For example the next case would be to move from 62 to 64 instead of 34 since there are only 2 tracks between them and not 18 if it were to go the other way.

Although this seems to be a better service being that it moved a total of 236 tracks, this is not an optimal one. There is a great chance that starvation would take place. The reason for this is if there were a lot of requests close to each other the other requests will never be handled since the distance will always be greater.

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.

Elevator (SCAN):

This approach works like an elevator does. It scans down towards the nearest end and then when it hits the bottom it scans up servicing the requests that it didn't get going down. If a request comes in after it has been scanned it will not be serviced until the process comes back down or moves back up. This process moved a total of 230 tracks. Once again this is more optimal than the previous algorithm, but it is not the best.

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.

Circular Scan (C-SCAN)

Circular scanning works just like the elevator to some extent. It begins its scan toward the nearest end and works it way all the way to the end of the system. Once it hits the bottom or top it jumps to the other end and moves in the same direction. Keep in mind that the huge jump doesn't count as a head movement. The total head movement for this algorithm is only 187 tracks, but still this isn't the more sufficient.

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.

* LOOK And C-LOOK*

This is just an enhanced version of C-SCAN. In this the scanning doesn't go past the last request in the direction that it is moving. It too jumps to the other end but not all the way to the end. Just to the furthest request. C-SCAN had a total movement of 187 but this scan (C-LOOK) reduced it down to 157 tracks.

From this you were able to see a scan change from 644 total head movements to just 157. You should now have an understanding as to why your operating system truly relies on the type of algorithm it needs when it is dealing with multiple processes.

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.