Subject: Operating Systems

Topic; File Management

Difficulty: Hard

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.

1. 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.

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.

Figure 5:First Come -First Serve

Advantages:

i. Every request gets a fair chance

ii. No indefinite postponement

Disadvantages:

i. Does not try to optimize seek time

ii. May not provide the best possible service

1. 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.

Figure 6:Shortest Seek Time First

Advantages:

i. Average Response Time decreases

ii. Throughput increases

Disadvantages:

i. Overhead to calculate seek time in advance

ii. Can cause Starvation for a request if it has higher seek time as compared to incoming requests

iii. High variance of response time as SSTF favours only some requests

3. 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.