---

Anatomy of a disk

• Stack of magnetic platters
  • Rotate together on a central spindle @3,600-15,000 RPM
  • Drives speed drifts slowly over time
  • Can't predict rotational position after 100-200 revolutions
• Disk arm assembly
  • Arms rotate around pivot, all move together
  • Pivot offers some resistance to linear shocks
  • Arms contain disk heads--one for each recording surface
  • Heads read and write data to platters

(page 1)

---

Storage on a magnetic platter

• Platters divided into concentric tracks
• A stack of tracks of fixed radius is a cylinder
• Heads record and sense data along cylinders
  • Significant fractions of encoded stream for error correction
• Generally only one head active at a time
  • Disks usually have one set of read-write circuitry
  • Must worry about cross-talk between channels
  • Hard to keep multiple heads exactly aligned

(page 2)

---

Disk positioning system

• Move head to specific track and keep it there
  • Resist physical socks, imperfect tracks, etc.
• A seek consists of up to four phases
  speedup--accelerate arm to max speed or half way pointcoast--at max speed (for long seeks)slowdown--stops arm near destinationsettle--adjusts head to actual desired track
• Very short seeks dominated by settle time (~1 ms)
• Short (200-400 cyl.) seeks dominated by speedup
  • Accelerations of ~40g

(page 3)

---

Seek details

• Head switches comparable to short seeks
  • May also require head adjustment
  • Settles take longer for writes than reads
• Disk keeps table of pivot motor power
  • Maps seek distance to power and time
  • Disk interpolates over entries in table
  • Table set by periodic ``thermal recalibration''
  • ~500 ms recalibration every ~25 min, bad for AV
• ``Average seek time'' quoted can be many things
  • Time to seek 1/3 disk, 1/3 time to seek whole disk,

Average time of all seek seeks or seek distances

(page 4)

---

Sectors

• Disk interface presents linear array of sectors
  • Generally 512 bytes, written atomically
• Disk maps logical sector #s to physical sectors
  Zoning--puts more sectors on longer tracksTrack skewing--sector 0 pos. varies for sequential I/OSparing--flawed sectors remapped elsewhere
• OS doesn't know logical to physical sector mapping
  • Larger logical sector # difference means larger seek
  • Highly non-linear relationship (and depends on zone)
  • OS has no info on rotational positions
  • Can empirically build table to estimate times

(page 5)

---

Disk interface

• Controls hardware, mediates access
• Computer, disk often connected by bus (e.g., SCSI)
  • Multiple devices may contentd for bus
  • SCSI devices can disconnect during requests (+200 µs)
• Command queuing: Give disk multiple requests
  • Disk can schedule them using rotational information
• Disk cache used for read-ahead
  • Otherwise, sequential reads would incur whole revolution
  • Cross track boundaries? Can't stop a head-switch
• Some disks support write caching
  • But data not stable--not suitable for all requests

(page 6)

---

Scheduling: First come first served (FCFS)

• Process disk requests in the order they are received
• Advantages
  • Easy to implement
  • Good fairness
• Disadvantages
  • Cannot exploit request locality
  • Increases average latency, decreasing throughput

(page 7)

---

Shortest positioning time first (SPTF)

• Always pick request with shortest seek time
• Advantages
  • Exploits locality of disk requests
  • Higher throughput
• Disadvantages
  • Starvation
  • Don't always know what request will be fastest
• Improvement: Aged SPTF
  • Give older requests higher priority
  • Adjust ``effective'' seek time with weighting factor:

Teff = Tpos - W * Twait



(page 8)

---

``Elevator'' scheduling (SCAN)

• Sweep across disk, servicing all requests passed
  • Like SPTF, but next seek must be in same direction
  • Switch directions only if no further requests
• Advantages
  • Takes advantage of locality
  • Bounded waiting
• Disadvantages
  • Cylinders in the middle get better service
  • Might miss locality SPTF could exploit
• CSCAN: Only sweep in one direction
  Very commonly used algorithm in Unix

(page 9)

---

VSCAN(r)

• Continuum between SPTF and SCAN
  • Like SPTF, but slightly uses ``effective'' positioning time
  • If request in same direction as previous seek: Teff = Tpos
  • Otherwise: Teff = Tpos + r * Tmax

• when r = 0, get SPTF, when r = 1, get SCAN
• E.g., r = 0.2 works well
• Advantages and disadvantages
  • Those of SPTF and SCAN, depending on how r is set

(page 10)

---

Proportional scheduling

• Goal: Prioritize processes
  • More important tasks should get more resources
  • Fix a target ratio for resource utilization, e.g., 2:1
• Generally implementated using feedback
  • Track difference between desired and actual usage
  • Actual will fluctuate form desired over time
  • Weight scheduler with difference
• Example: Background thread scans DB for statistics
  • Want more throughput for critical transactions

(page 11)