Content

Disks
- Disk Scheduling Algorithms
Redundant Array of Inexpensive Disks (RAID)

Disks

Structure
- Disk
  - Platters
    - 1 arm: move together
    - 1 head: access data in parallel
    - Concentric tracks: same track across different platters
      - Sectors: preamble + data + 16B of ECC
Disk access delays
- Seek time: move head to correct track
- Rotational delay: rotate to correct sector
- Transfer time: r/w bits of sector (fastest among all)
Disk performance trends
- Capacity: 2x every 2 years
- Transfer rate (BW): 2x every 2 years
- Seek & rotation time: 1/2 every 10 years
Disk performance
- Highest bandwidth for sequential access
- Worst bandwidth for random access
Disk scheduling
- Aims to minimize seek time (rotational delay hard to control)
Addressing disks
- Older disks: require OS to specify all parameters e.g. cylinder, track, sector, transfer size, etc.
- Modern disks: complicated e.g. not all sectors the same size, sectors are remapped, etc.
- Current disks: higher-level interface, exports data as logical array of sectors & maps logical sectors to its surface
Disk errors
- Latent sector errors, mis-directed writes
- Transient v.s. hard errors
- Some errors can be masked by ECC
- Bad sectors: physical damage; mapped to spare in factory, by disk controller

Disk Scheduling Algorithms

Aims to minimize seek time (rotational delay hard to control).

2 methods
- Reduce seek & rotation
- Read several sectors at once
Algorithms
- FCFS
  - Simple, fair, slow
- Shortest seek time first (SSF)
  - Starvation
- SCAN (elevator): serve next request in same direction (a bit to track arm direction)
  - Benefits tracks in the middle more
- C-SCAN: SCAN in one direction

Redundant Array of Inexpensive Disks (RAID)

Use many disks in parallel; increases storage bandwidth, improves reliability.

Stripe: unit of r/w to RAID
- Chunks/Strips: unit of r/w to a single disk
Improving storage bandwidth
- Chunks on different disks can be r/w in parallel
- Large chunk size:
  - Fewer seeks across disks -> better throughput
- More disks:
  - Bandwidth increases
- Large stripe size:
  - Internal fragmentation
  - Should be based on average file size

RAID Level 0: Disk Striping

Distributes data across several disks for speed. No redundancy.

| Strip 0 | | Strip 1 | | Strip 2 | | Strip 3 |
| Strip 4 | | Strip 5 | | Strip 6 | | Strip 7 |
| Strip 8 | | Strip 9 | | Strip 10| | Strip 11|

RAID Level 1: Mirroring

Backup. Write both, read either.
Utilization: 50%

| Strip 0 | | Strip 1 | | Strip 2 | | Strip 3 | | Strip 0 | | Strip 1 | | Strip 2 | | Strip 3 |
| Strip 4 | | Strip 5 | | Strip 6 | | Strip 7 | | Strip 4 | | Strip 5 | | Strip 6 | | Strip 7 |
| Strip 8 | | Strip 9 | | Strip 10| | Strip 11| | Strip 8 | | Strip 9 | | Strip 10| | Strip 11|

RAID Level 4: Dedicated Parity Disk

Calculate XOR value of chunks and store on parity disk. Utilization: (N-1)/N

# P0-3 = S0 ^ S1 ^ S2 ^ S3
# P'0-3 = S'0 ^ S1 ^ S2 ^ S3 = S'0 ^ S0 ^ P0-3

| Strip 0 | | Strip 1 | | Strip 2 | | Strip 3 | | P0-3 |
| Strip 4 | | Strip 5 | | Strip 6 | | Strip 7 | | P4-7 |
| Strip 8 | | Strip 9 | | Strip 10| | Strip 11| | P8-11|

RAID Level 5: Distributed Parity

Parity information distributed across all disks. Avoids bottleneck for parity disk.

| Strip 0 | | Strip 1 | | Strip 2 | | Strip 3 | | P0-3    |
| Strip 4 | | Strip 5 | | Strip 6 | | P4-7    | | Strip 7 |
| Strip 8 | | Strip 9 | | P8-11   | | Strip 10| | Strip 11|

Disk & RAID