Disk-scheduling algorithms

• Disk Scheduling

The seek time is the time for the disk arm to move the heads to the cylinder containing the desired sector.
The rotational latency is the additional time for the disk to rotate the desired sector to the disk head.


Disk-scheduling algorithms.

• FCFS Scheduling

The simplest form of disk scheduling is the first-come, first-served (FCFS) algorithm. This algorithm is intrinsically fair, but it generally does not provide the fastest service.

• SSTF Scheduling

It seems reasonable to service all the requests close to the current head position before moving the head far away to service other requests. This assumption is the basis for the shortest-seek-time-first (SSTF) algorithm.

• SCAN Scheduling

The SCAN algorithm is sometimes called the elevator algorithm, since the disk arms behaves just like an elevator in a building, first servicing all the requests going up and then reversing to service requests the other way.

• C-SCAN Scheduling

Circular SCAN (C-SCAN) scheduling is a variant of SCAN designed to provide a more uniform wait time
When the head reaches the other end, however, it immediately returns to the beginning of the disk, without servicing any requests on the return trip

• LOOK Scheduling

LOOK scheduling improves upon SCAN by looking ahead at the queue of pending requests, and not moving the heads any farther towards the end of the disk than is necessary.


http://siber.cankaya.edu.tr/ozdogan/OperatingSystems/ceng328/node263.html

• TYPES OF DISK SCHEDULING ALGORITHMS 

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


2. 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
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
The reason for this is if there were a lot of requests close to eachother the other requests will never be handled since the distance will always be greater.

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

4. 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 track, but still this isn't the mose sufficient.


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

http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

• https://www.cs.washington.edu/education/courses/451/04au/section/section7.pdf

• The set of requests is 98 183 37 122 14 124 65 67

and the disk head starts at cylinder 53. 

Where direction is important (LOOK and SCAN), the disk head is moving outward.

Order of Service

algorithm request order

fcfs 98 183 37 122 14 124 65 67

pickup 65 67 98 122 124 183 37 14

sstf 65 67 37 14 98 122 124 183

scan 37 14 65 67 98 122 124 183

look 37 14 65 67 98 122 124 183

c-scan 65 67 98 122 124 183 14 37

c-look 65 67 98 122 124 183 14 37

Head Motion

This chart shows how far the disk heads move to service each request, and the mean and standard deviation of the head motion.

algorithm total number of cylinders moved total avg stdev

fcfs 45 85 146 85 108 110 59 2 640 80.00 44.47

pickup 12 2 31 24 2 59 146 23 299 37.38 47.57

sstf 12 2 30 23 84 24 2 59 236 29.50 28.62

scan 16 23 79 2 31 24 2 59 236 29.50 26.97

look 16 23 51 2 31 24 2 59 208 26.00 20.72

c-scan 12 2 31 24 2 59 231 23 384 48.00 76.18

c-look 12 2 31 24 2 59 169 23 322 40.25 55.16

http://nob.cs.ucdavis.edu/classes/ecs150-2008-02/handouts/io/io-example.html