ENVS 1800 Lecture 12: ENVS 1800 Tutorial 12 Notes
ENVS 1800 Tutorial 12 Notes – N-step C-Scan Scheduling, Scan Scheduling and Shortest
Distance First Scheduling
Introduction
Shortest Distance First Scheduling
• The shortest distance first (SDF) scheduling algorithm looks at all the requests in the
queue and processes the one nearest to the current location of the head.
• This algorithm suffers from the possibility of indefinite postponement.
• If the head is near the middle track on the disk, a request near the edge of the disk may
never get serviced if requests continue to join the queue.
Scan Scheduling
• The scan scheduling algorithm attempts to satisfy the limitation of SDF scheduling.
• The head scans back and forth across the disk surface, processing requests as it goes.
• Although this method is fairer than SDF, it suffers from a different limitation, namely,
that blocks near the middle tracks are processed twice as often as blocks near the edge.
• To see this more clearly, consider the diagram
• Consider the head moving smoothly back and forth across the disk at a constant speed.
• The diagram shows the time at which the head crosses various tracks.
• Note that the middle track is crossed in both directions, at about equal intervals.
• Tracks near either the inside or outside track
• However, are crossed twice in quick succession.
• Then there is a long interval in which they are not touched.
• A track at the very edge, inside or outside, is touched only once for every two times that
a track in the middle is touched.
N-step C-Scan Scheduling
• Two changes improve the n-step c-scan scheduling algorithm.
find more resources at oneclass.com
find more resources at oneclass.com