File Management; Disk Scheduling Algorithms

File Management

What is a File?

A file is a named collection of related information that is stored on secondary storage.

File Attributes:

File Types

What is a Filesystem?

A filesystem is the way files are organized and stored on a storage device.

Filesystem Structure:

Storage Device
    ↓
Partition Table (MBR / GPT)
    ↓
Partition 1: Filesystem
    ├── Boot Block
    ├── Super Block (metadata about filesystem)
    ├── Inode Table (file metadata)
    └── Data Blocks (actual file content)

Common Filesystems

Disk Space Allocation Methods

26.1 Contiguous Allocation

• Each file occupies consecutive disk blocks
• Fast sequential and random access

Problem: External fragmentation; difficult to grow files

File A: blocks 0,1,2,3
File B: blocks 5,6,7
File C: blocks 10,11,12,13
Free: 4, 8, 9 → scattered small free spaces

26.2 Linked Allocation

• Each block contains a pointer to next block
• No external fragmentation; files can grow easily
• Problem: No random access (must follow links); overhead per block

File A: block 0 → block 7 → block 12 → block 4 → NULL

26.3 Indexed Allocation

• An index block stores all block addresses for a file
• Supports random access

Problem: Index block overhead; size limit

Index Block:    [ 3, 7, 12, 4, NULL ]
File Data:       block 3, block 7, block 12, block 4

FAT (File Allocation Table): A linked list stored in a table at the start of the partition.

UNIX Inode: Stores direct block pointers + indirect block pointers + double/triple indirect.

Disk Scheduling Algorithms

Why Disk Scheduling?

Disk access has mechanical delay (seek time + rotational latency). Scheduling algorithms minimize head movement.

Disk Seek Time: Time to move arm to correct track.

Goal: Minimize total head movement (measured in cylinders/tracks traversed).

27.1 FCFS — First Come First Served

Simple: Service requests in arrival order.

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

Order:       53→98→183→37→122→14→124→65→67
Head movement: 45+85+146+85+108+110+59+2 = 640 cylinders

27.2 SSTF — Shortest Seek Time First

Service the request closest to current head position first.

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

Order: 53→65→67→37→14→98→122→124→183
Head movement: 12+2+30+23+84+24+2+59 = 236 cylinders

Problem: Can starve requests far from head (nearest requests always served first).

27.3 SCAN (Elevator Algorithm)

Head moves like an elevator — in one direction servicing all requests, then reverses.

Head at 53, moving toward higher cylinders
Requests: 98,183,37,122,14,124,65,67

Order: 53→65→67→98→122→124→183→37→14
(Go to end, then reverse)

27.4 C-SCAN (Circular SCAN)

Moves in one direction to end, then jumps back to beginning without servicing on return.

• More uniform wait times than SCAN
• Return jump counted as head movement but no requests served

27.5 LOOK / C-LOOK

Like SCAN/C-SCAN but head only goes as far as the last request (doesn't go to physical end of disk).

More efficient than SCAN/C-SCAN in practice.

Algorithm Comparison