Operating Systems

Disk Anatomy:
┌─────────────────────────────────┐
│         Multiple Platters        │
│   ┌───────────────────────┐     │
│   │    Track (cylinder)    │     │
│   │  ┌─────────────────┐  │     │
│   │  │     Sector      │  │     │
│   │  │   (512B-4KB)    │  │     │
│   │  └─────────────────┘  │     │
│   └───────────────────────┘     │
│         Read/Write Head          │
└─────────────────────────────────┘

Terms:
- Platter: Circular disk surface
- Track: Concentric circle on platter
- Sector: Smallest unit (typically 512B)
- Cylinder: Same track on all platters

Access Time = Seek Time + Rotational Latency + Transfer Time

Seek Time: Move head to correct track (dominant)
Rotational Latency: Wait for sector to rotate under head
Transfer Time: Read/write the data

Example:
Seek = 10ms, Rotation = 5ms (avg), Transfer = 0.1ms
Total = 10 + 5 + 0.1 = 15.1ms

Service in request order

Queue: 98, 183, 37, 122, 14, 124, 65, 67
Head starts at: 53

Movement: 53→98→183→37→122→14→124→65→67

Total head movement = 
|53-98| + |98-183| + |183-37| + |37-122| + 
|122-14| + |14-124| + |124-65| + |65-67|
= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2
= 640 cylinders

Service closest request first

Queue: 98, 183, 37, 122, 14, 124, 65, 67
Head at: 53

Nearest to 53: 65 (distance 12)
Nearest to 65: 67 (distance 2)
Continue picking closest...

Movement: 53→65→67→37→14→98→122→124→183

Total = 12+2+30+23+84+24+2+59 = 236 cylinders
(Much better than FCFS!)

Problem: Starvation of far requests

Move in one direction, service all requests
At end, reverse direction

Queue: 98, 183, 37, 122, 14, 124, 65, 67
Head at 53, moving toward 0

Movement: 53→37→14→0→65→67→98→122→124→183

Goes to end (0), then reverses
Total = 53 + 183 = 236 cylinders

Like an elevator going up/down

Move in one direction only
Jump back to beginning without servicing

Queue: 98, 183, 37, 122, 14, 124, 65, 67
Head at 53, moving toward 199

Movement: 53→65→67→98→122→124→183→199→0→14→37

Provides more uniform wait time

Like SCAN/C-SCAN but don't go to disk end
Only go as far as last request

LOOK: Go to 183 (not 199), reverse to 14 (not 0)
C-LOOK: Go to 183, jump to 14 (not 0)

File stored in consecutive blocks

Directory Entry: [Filename] [Start] [Length]
myfile.txt        10        5

Blocks: 10, 11, 12, 13, 14

Pros: Simple, fast sequential & random access
Cons: External fragmentation, file can't grow

Each block points to next block

Directory: [Filename] [Start] [End]
myfile.txt    10        20

Block 10 → Block 15 → Block 18 → Block 20 → NULL

Pros: No external fragmentation, can grow
Cons: Slow random access, pointer overhead

Index block contains pointers to all data blocks

Directory: [Filename] [Index Block]
myfile.txt     100

Index Block 100: [10, 15, 18, 20, 25, ...]

Pros: Good random access, no fragmentation
Cons: Index block overhead

All files in one directory
Problem: Name conflicts, hard to organize

[file1] [file2] [file3] [file4]

User directories under root

/root
  /user1
    [file1] [file2]
  /user2
    [file1] [file3]

Same filename allowed for different users

Nested directories

/
├── home
│   ├── user1
│   │   └── docs
│   └── user2
├── etc
└── var

Most common in modern systems

1 bit per block: 0 = free, 1 = allocated

Blocks: 0 1 2 3 4 5 6 7
Bitmap: 1 1 0 1 0 0 1 1

Find free: Scan for 0 bits
Efficient for finding contiguous space

Free blocks linked together

Free List Head → Block 2 → Block 4 → Block 5 → NULL

No extra space needed (use free blocks)
Slow to find contiguous space