Scheduling PoliciesDisk blocks2Disk performance parameters To read or write, the disk head must be positioned at the desired track and at the beginning of the desired sector Seek time Time it takes to position the head at the desired track Rotational delay/latency Time its takes for the head to reach the beginning of the sector 3Timing of a disk I/O transfer45The set of all the tracks in the same relative position on the platter is referred to as a cylinder.6Disk performance parameters Access time Sum of seek time and rotational delay The time it takes to get in position to read or write Data transfer occurs as the sector moves under the head7Disk scheduling policies Seek time is the reason for differences in performance For a single disk there will be a number of I/O requests If requests are selected randomly, we will have poor performance8Disk scheduling The order in which the disk requests are made affects the time it takes to traverse the tracks and hence the seek time Disk scheduling aims at reducing the seek time (also called traversal time) We explore a variety of disk scheduling policies9Assumptions for scheduling policies Number of tracks = 200 Innermost track is track 0 Outermost track is track 199 Current position of head is track 100 Request sequence: 55, 58, 39, 18, 90, 160, 150, 38, 18410First-in, First-out (FIFO) Process makes disk I/O requests sequentially Fair to all processes Approaches random scheduling in performance if there are many processes11Priority Goal is not to optimize disk use but to meet other objectives Giving priority to shorter jobs Giving priority to interactive jobs Decision made outside of the disk management software Short batch jobs may have higher priority Provide good interactive response time12Last-in, First-out Good for transaction processing systems Disk I/O request from the most recent user is satisfied first There should be little arm movement Possibility of starvation since a job may never regain the head of the line13Shortest Service Time First Select the disk I/O request that requires the least movement of the disk arm from its current position Always choose the minimum Seek time14SCAN (Elevator) in text but LOOK Move the arm in one direction, until there are no more tracks or no more requests in that direction Reverse direction and repeat Does not exploit locality Biased against the most recently used tracks Favors the innermost and outermost tracks Eliminate starvation SCAN vs LOOK http://www.dcs.ed.ac.uk/home/stg/pub/D/disk.html http://www.cs.jhu.edu/~yairamir/cs418/os8/sld019.htm15SCAN (actually LOOK)16SCAN goes to outermost track as well as to innermost trackC-SCAN (Circular) or C-LOOK Restricts scanning to one direction only When the last track has been visited in one direction, the arm is returned to the opposite end of the disk and the scan begins again17C-SCAN (actually C-LOOK)18N-step-SCAN Arm-stickiness occurs with SCAN and C-SCAN Split the queue into smaller queues of length N While servicing a sub-queue, new requests are added to another sub-queue Must completely service a sub-queue before moving to another sub-queue19FSCAN Maintain two sub-queues While servicing one sub-queue, add new requests to the other Service of new requests deferred until all old requests have been processed20Disk scheduling policies21SCAN here is actually
View Full Document
Unlocking...