CS 134

Key Points: Disk Storage and Scheduling

Disk Storage Fundamentals

  1. Basic Geometry:
    • Disks organized into tracks, sectors, and platters
    • Multiple platters share head assembly (stack of tracks = a cylinder)
    • Outer tracks have more physical space than inner tracks
    • Zone Bit Recording exploits this space for higher capacity
  2. Access Timing:
    • Seek time for head movement between tracks
    • Rotational latency waiting for sector to arrive
    • Transfer time to read/write data
    • Head acceleration/deceleration affects seek patterns
  3. Physical Considerations:
    • Inner tracks more error-prone due to density (unless we use ZBR)
    • Multiple platters increase failure probability
    • Need to balance capacity vs. reliability
  4. Logical Block Addressing (LBA):
    • Maps logical block numbers to physical disk locations
      • Facilitates more complex disk geometries
      • Even allows the mapping to change over time (e.g., remapping bad sectors)
    • Simplifies disk access for OS and applications
    • Obscures physical disk layout from software

Disk Scheduling Algorithms

  1. First Come, First Served (FCFS):
    • Simple but inefficient
    • Can cause excessive head movement
    • No optimization for seek or rotation time
  2. Shortest Seek Time First (SSTF):
    • Minimizes head movement
    • Better overall throughput
    • Can lead to request starvation
  3. Elevator Algorithms:
    • SCAN (full traversal) and LOOK (partial traversal)
    • Prevents starvation
    • Middle tracks get preferential service
  4. Circular Variants:
    • C-SCAN and C-LOOK avoid middle track bias
    • Better for sequential access patterns
    • More compatible with LBA addressing

Modern Disk Controllers

  1. Command Queuing:
    • Native/Tagged Command Queuing (NCQ/TCQ)
    • Controllers reorder requests internally
    • OS and controller work in partnership
  2. Disk Caching:
    • Read-ahead for sequential access
    • Write buffering for performance
    • Must consider power failure implications
  3. Health Monitoring:
    • SMART attributes track disk health
    • Reallocated sectors and error rates
    • Temperature and performance metrics

Remember

  • Physical disk characteristics significantly impact performance
    • Disks are a random-access medium, but unlike memory, position matters; it's not uniform cost!
  • Different scheduling algorithms balance various trade-offs
  • No single algorithm is perfect for all situations
  • Modern controllers add complexity but improve performance
  • Caching and command queuing require OS cooperation
  • Must balance performance against reliability concerns

(When logged in, completion status appears here.)