Shortest seek first

Shortest seek first (or shortest seek time first) is a secondary storage scheduling algorithm to determine the motion of the disk read-and-write head in servicing read and write requests.

An operating system using shortest seek first puts requests for data from the drive into a queue, and services them in order of how long it would take the drive to physically position its drive head over the correct cylinder and sector to read the data. This algorithm prioritizes requests for data that would take less time to handle, which is quicker than handling the requests in the order they are received. However, many requests for data that are physically around the same region in the hard drive will starve requests that are further away.

Algorithm

A basic description of the shortest seek first algorithm is as follows:[1]

  1. Create a priority queue of unserviced requests. The priority queue is ordered such that requests with a lower distance between the sector and cylinder currently under the head and the sector and cylinder of the request will be serviced first.
  2. While the priority queue is not empty, process the first request in the queue.

Description

Magnetic disk storage

Open hard disk drive exposing a stack of magnetic discs and actuator arms positioned in between them
The actuator arms sit between and slightly above the surface of the disks in order to read and write information to them

The shortest seek first algorithm targets hard disk drives (HDD) featuring magnetic disks. In an HDD, magnetic disks are arranged in a stack, like a stack of CDs, which have information recorded onto them using a magnet.[2]

Data is written to the disks and read by a series of heads, attached to actuator arms, which sit in between and just slightly above the surface of each disk. The arm system physically moves the heads across the disks to access data.[3]

Each disk is subsequently divided into circular tracks, which are themselves divided into sectors. For example, when reading data, the arms physically extend out to a particular cylinder, in what is called the seek time, while the disks rotate beneath them. The time it takes for the disk to rotate to the desired sector is called the "rotational latency."[3]

Implementation

Shortest seek first is a specific case of the shortest job next scheduling algorithm. It is motivated by the reasonable assumption that time can be saved by prioritizing requests in a way that minimizes the time spent moving the actuator arms.[1]

The drive maintains an incoming buffer of requests, and tied with each request is the cylinder number of the request. Lower cylinder numbers indicate the cylinder is closer to the spindle, while higher numbers indicate the cylinder is further away.[1]

The shortest seek first algorithm determines which request is closest to the current position of the head, and services that request next.[1]

Analysis

Shortest seek first represents an improvement over the First come, first served algorithm by prioritizing requests that involve less actuator arm movement.[4]

However, since the buffer is always getting new requests, these can skew the service time of requests that may be furthest 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.[5]

See also

References

  1. 1 2 3 4 Silberschatz, Galvin & Gagne 2005, p. 458
  2. ↑ Silberschatz, Galvin & Gagne 2005, p. 451
  3. 1 2 Silberschatz, Galvin & Gagne 2005, p. 452
  4. ↑ Silberschatz, Galvin & Gagne 2005, p. 459
  5. ↑ Andrew S. Tanenbaum; Herbert Bos (2015). Modern Operating Systems. Pearson. ISBN 978-0-13-359162-0.

Bibliography

  • Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2005). Operating System Concepts (7th ed.). John Wiley & Sons. ISBN 0471694665.
This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.