Lecture 39

Hard disk drives

• Persistent data storage
• Consists of a large number of sectors (512-byte blocks) that can be read/written
• Single sector write is atomic
• Best to access sectors contiguously

Crux 6: How to store and access data on disk?

How do modern hard-disk drives store data? What is the interface? How is the data actually laid out and accessed? How does disk scheduling improve performance?

A Disk With Just A Single Track

Platter

• A circular hard surface on which data is stored persistently
• Each platter has two surfaces

Spindle

• Spindle is connected to a motor that spins the platters around.
• The rate of rotations is measured in RPM

Track

• Concentric circles of sectors
• Data is encoded on each surface in a track.
• A single surface contains many thousands and thousands of tracks.

Disk head

• One head per surface
• Read/write uses the disk head
• Attached to a single disk arm, which moves across the surface.

To read/write

\[T_{I/O} = T_{seek} + T_{rotate} + T_{transfer}\]

\(T_{seek} + T_{rotate}\): Aim to minimize

I/O example

\(T_{seek} = 10ms\), Rate of transfer \(= 100MB/s\)

• Bottomline: Randomness hurts

Disk Scheduling

The scheduling problem

• which I/O request to schedule next?

Alternative 1: SSTF (Shortest Seek Time First)

• Order the queue of I/O requests by track
• Pick request on the nearest track to complete first

• Implementation issue: drive geometry is not available to the OS; rather, it sees an array of blocks.
• Fix: Nearest-block first
• Another issue: Starvation

Crux 7: How to handle disk starvation

How can we implement SSTF-like scheduling but avoid starvation?

Elevator

• Move back and forth across the disk servicing requests in order across the tracks.
  • Sweep : single pass across the disk (from outer to inner tracks, or inner to outer)
    • If a request comes for a block on a track that has already been serviced, it is queued until the next sweep

Variants

• F-SCAN
  • Freeze the queue to be serviced when it is doing a sweep
  • Avoid starvation of far-away requests
• C-SCAN (Circular SCAN)
  • Sweep from outer-to-inner, and then inner-to-outer, etc.

• Problem with elevator type scheduler?
• Does not account for disk rotation costs

Incorporating rotational delay

• Suppose head is at sector 30

• Which is better: schedule sector 16 (middle track) first or sector 8 (outer track)?
• Correct answer: It depends
• If rotation is faster than seek, then schedule request 16 first
• If seek is faster than rotation, then schedule request 8 first

• SPTF (Shortest Positioning Time First): Better scheduler?

I/O merging

• Reduce the number of requests sent to the disk
  • imagine a series of requests to read blocks 33, then 8, then 34
  • It makes sense to merge the request for blocks 33 and 34 into a single two-block request