Shortest seek first
Encyclopedia
Shortest seek first is a secondary storage
scheduling
algorithm to determine the motion of the disk's arm and head in servicing read and write requests.
) algorithm. The drive maintains an incoming buffer of requests, and tied with each request is a cylinder number of the request. Lower cylinder numbers indicate that the cylinder is closer to the spindle, while higher numbers indicate the cylinder is farther away.
The shortest seek first algorithm determines which request is closest to the current position of the head, and then services that request next.
However, since the buffer is always getting new requests, these can skew the service time of requests that may be farthest away from the disk head's current location, if the new requests are all close to the current location; in fact, starvation
may result, with the faraway requests never being able to make progress.
The elevator algorithm
is one way of reducing arm movement/response time, and ensuring consistent servicing of requests
Disk storage
Disk storage or disc storage is a general category of storage mechanisms, in which data are digitally recorded by various electronic, magnetic, optical, or mechanical methods on a surface layer deposited of one or more planar, round and rotating disks...
scheduling
I/O scheduling
Input/output scheduling is a term used to describe the method computer operating systems decide the order that block I/O operations will be submitted to storage volumes...
algorithm to determine the motion of the disk's arm and head in servicing read and write requests.
Description
This is a direct improvement upon a first-come first-served (FIFOFIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
) algorithm. The drive maintains an incoming buffer of requests, and tied with each request is a cylinder number of the request. Lower cylinder numbers indicate that the cylinder is closer to the spindle, while higher numbers indicate the cylinder is farther away.
The shortest seek first algorithm determines which request is closest to the current position of the head, and then services that request next.
Analysis
The shortest seek first algorithm has the direct benefit of simplicity and is clearly advantageous in comparison to the FIFO method, in that overall arm movement is reduced, resulting in lower average response time.However, since the buffer is always getting new requests, these can skew the service time of requests that may be farthest away from the disk head's current location, if the new requests are all close to the current location; in fact, starvation
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
may result, with the faraway requests never being able to make progress.
The elevator algorithm
Elevator algorithm
The elevator algorithm is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests....
is one way of reducing arm movement/response time, and ensuring consistent servicing of requests