Grant Novota
About Projects Peaks Blog Links Resume

Storage Management

24 Jul 2019

Magnetic Media

Using magnetic media, we can set a bit to 1 or 0 by applying a strong enough magnetic field to a small region of a magnetic film and this region will retain its magnetic sense even when power is removed. To read a sequence of bits, we either move the magnetic head over hte magnetic media or rotate the media under the (static) magnetic head, which is the easier approach. This supports both random and sequential access. Additionally, an array of magnetic disk platters increases bit sotrage at marginal cost in space and new disk heads.

Disk Scheduling

Any technique that can reduce seek times and rotational latency is a big win in terms of improving disk access times. Disk scheduling is designed to reduce seek times and rotational latency.

Disk operations take time to be processed. At any given time there will be multiple requests to access data from different places on the disk. These requests are stored in the queue and the OS can choose to intelligently serve or schedule these requests so as to minimize latency.

We want to find an algorithm that minimizes seek time.

Suppose we are given a series of disk I/O requests for different disk blocks that reside on the following different cylinder/tracks in the following order:

  • 98, 183, 37, 122, 14, 124, 65, 67 (initial track location is 53)

The total number of trackes traversed is used as an evaluation metric of the algorithms.

First Come First Serve (FCFS) Disk Scheduling

  • Requests would be scheduled in the same order as the order of arrival.
  • The total number of cylinders/tracks traversed by the disk head under the FCFS algorithm would be:
    • 53-98 + 98-183 + 183-37 + 37-122 +…= 640 cylinders
  • Observations:
    • Disk R/W head would move less if 37 and 14 could be serviced together, similarly for 122 and 124.
    • Easy to implement, but slow.

SSTF Disk Scheduling

  • Shortest Seek Time First (SSTF) scheduling selects the next request with the minimum seek time from the current R/W head position.
  • Requests are serviced in this order:
    • 65, 67, 37, 14, 98, 122, 124, 183
  • Locally optimal, but not globally optimal.
    • Would be better to move disk head from 53 to 37 then 14, then 65.
  • Another drawback: starvation.
    • While the disk head is positioned at 37, a series of new nearby requests may come into queue for 39, 35, 38, …

OPT Disk Scheduling

  • OPT looks to minimize the back and forth traversing.
  • Move the disk head from the current position to the closest edge track, and sweep through once (either innermost to outermost, or outermost to innermost).
  • This should minimize the overlap of back and forth and give the minimum number of tracks covered.
  • Requests are serviced in the following order:
    • 53, 37, 14, 65, 67, 98, 122, 124, 183
  • OPT ignores the initial direction and changes direction.
    • Total # of cylinders traversed = 39 down + 169 up = 208 cylinders.
  • The problem with OPT is that you have to recalculate every time there’s a new request for a disk track.
  • Best approximation to OPT is probably to just scan the disk in one direction, and then change the direction of scanning.

SCAN Disk Scheduling

  • Move the read/write head in once direction from the innermost to outermost track then reserve direction.
    • Sweeping across the disk in alternate directions.
  • Requests are serviced in the following order:
    • 53, 65, 67, 98, 122, 124, 183, 200, 37, 14
  • Advantages:
    • Approximates OPT.
    • Starvation free solution.
    • Handles dynamic arrival of new requests.
    • Simple to implement.
  • Disadvantages:
    1. SCAN only approximates OPT.
      • There is significantly more overlap compared to the OPT service sequence.
    2. Unnecessarily goes to extreme edges of disk even if no requests there.
    3. Unfair for tracks on the edges of the disk (both inside and outside).
      • Writes to the edge tracks take the longest since after SCAN has reversed directions at one edge, the writes on the other edge always wait the longest to be served.
      • After two full scans back and forth, middle tracks get serviced twice, edge tracks only once.

C-SCAN Disk Scheduling

  • Treat disk as queue of tracks.
    • When reaching one edge, move the R/W head all the way back to the other edge.
    • Continue scanning in the same direction rather than reserving direction.
  • Circular SCAN, or C-SCAN
  • After reaching an edge, writes at the opposite edge get served first. This is more fair in service times for all tracks.
  • Requests are serviced in the following order:
    • 53, 65, 67, 98, 122, 124, 183, 200, 1, 14, 37
    • For a total distance of 384 tracks.
  • Note how no scanning is done as the disk head is repositioned from 200 all the way down to 1 to ensure circularity.

LOOK Disk Scheduling

  • Don’t travel to the extreme edge if no requests there.
  • Look at the furthest request in the current direction.
    • Only move the disk head that far then reverse direction.
  • No starvation in this algorithm.
  • Requests are serviced in the following order:
    • 53, 65, 67, 98, 122, 124, 183, 37, 14
    • Total # of cylinders traversed = 130 up + 169 down = 299 cylinders.

C-LOOK Disk Scheduling

  • Improve LOOK by making it more fair -> circular.
  • After moving disk head to furthest request in current direction.
    • Move disk head directly all the way back to the further request in the other direction, then continue scanning in the same direction.
  • Requests are serviced in the following order:
    • 53, 65, 67, 98, 122, 124, 183, 14, 37
    • Total # of cylinders traversed = 130 up + 169 down + 23 up = 322 cylinders.

Disk Scheduling in Practice

In the previous examples, the number of cylinders traversed by SCAN, LOOK, and C-LOOK are much lower if the initial direction was down.

We can’t keep changing direction because it can cause starvation/unfairness. Preserving directionality of the scan is important for fairness, but we sacrifice some performance.

Either SSTF or LOOK are resonable choices as default disk scheduling algorithms. These algorithms for reducing seek times are typically embedded in the disk controller today. There are also other algorithms for reducing rotational latency; also embedded in the disk controller.

Top