Notes › Operating Systems
File Systems and Disk Scheduling
A file system decides how files are named, stored and found on a disk. Disk scheduling decides the order in which pending disk requests are served so the read/write head moves as little as possible.
Files and directories
- A file = named data + metadata (size, owner, permissions, timestamps, location of its blocks).
- Operations: create, open, read, write, seek, close, delete, truncate.
- Access methods: sequential (tape-like), direct/random (jump to block n), indexed.
| Directory structure | Idea | Problem |
|---|---|---|
| Single-level | one directory for everyone | name clashes |
| Two-level | one directory per user | no grouping inside a user |
| Tree | folders inside folders (absolute & relative paths) | sharing files is awkward |
| Acyclic graph | tree + links (shortcuts / hard links) | deleting a shared file, dangling links |
Allocation methods — where do a file's blocks live?
| Method | How | ✅ | ❌ |
|---|---|---|---|
| Contiguous | blocks next to each other; store start + length | fast sequential & random access | external fragmentation, hard to grow a file |
| Linked | each block points to the next | no external fragmentation, easy to grow | slow random access, a broken pointer loses the rest |
| FAT (File Allocation Table) | linked list kept in one table in memory | faster random access than plain linked | table must be cached; big for large disks |
| Indexed | an index block lists all block addresses | fast random access, no external fragmentation | index block overhead; large files need multi-level indexes |
Unix inodes
Every file has an inode holding its metadata and block pointers (the file name lives in the directory entry, not in the inode).
inode: mode, owner, size, timestamps, link count
12 direct pointers ─► data blocks
1 single indirect ─► block of pointers ─► data
1 double indirect ─► pointers ─► pointers ─► data
1 triple indirect
Small files use only direct pointers (fast); huge files still fit thanks to indirect levels.
Example: block size 4 KB, pointer 4 bytes → one block holds 1024 pointers. Max size ≈ 12×4 KB + 1024×4 KB + 1024²×4 KB + 1024³×4 KB ≈ 4 TB.
Hard link vs soft link: a hard link is another directory entry pointing to the same inode (link count +1); a soft/symbolic link is a small file that stores a path (it breaks if the target is deleted).
Free-space management
| Method | Idea |
|---|---|
| Bit vector (bitmap) | 1 bit per block (1 = free); easy to find runs of free blocks |
| Linked list | free blocks point to each other |
| Grouping | first free block stores addresses of n free blocks |
| Counting | store (start, count) for runs of free blocks |
Disk structure and access time
A hard disk has platters → tracks → sectors; tracks at the same position on all platters form a cylinder.
Access time = seek time + rotational latency + transfer time. Seek time (moving the arm) dominates — so scheduling tries to minimise total head movement. (SSDs have no moving head, so these algorithms matter much less there.)
Disk scheduling — one worked example
Request queue (cylinders): 98, 183, 37, 122, 14, 124, 65, 67 · head at 53 · disk cylinders 0–199 · head moving towards higher numbers for SCAN-type algorithms.
| Algorithm | Order served | Total head movement |
|---|---|---|
| FCFS | 98 183 37 122 14 124 65 67 | 640 |
| SSTF | 65 67 37 14 98 122 124 183 | 236 |
| SCAN (elevator) | 65 67 98 122 124 183 → 199 → 37 14 | 331 |
| C-SCAN | 65 67 98 122 124 183 → 199 → 0 → 14 37 | 382 (incl. the 199-cylinder return jump) |
| LOOK | 65 67 98 122 124 183 → 37 14 | 299 |
| C-LOOK | 65 67 98 122 124 183 → 14 37 | 322 (incl. the 183→14 jump) |
How each works:
- FCFS — serve in arrival order. Fair, but the head swings wildly.
- SSTF (Shortest Seek Time First) — always go to the nearest request. Much less movement, but far-away requests can starve.
- SCAN — move in one direction to the end of the disk, serving requests, then reverse (like a lift).
- C-SCAN — go to the end, jump back to the start without serving, continue in the same direction. More uniform waiting time.
- LOOK / C-LOOK — like SCAN / C-SCAN but turn around at the last request, not the disk end.
Some textbooks don't count the C-SCAN/C-LOOK return jump; check what your exam expects (C-SCAN would then be 183, C-LOOK 153).
Quick sums to verify FCFS: |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.
RAID (Redundant Array of Independent Disks)
| Level | Idea | Survives | Usable space (n disks) |
|---|---|---|---|
| RAID 0 | striping | no failure | n |
| RAID 1 | mirroring | 1 disk (of the pair) | n/2 |
| RAID 5 | striping + distributed parity | 1 disk | n − 1 |
| RAID 6 | double parity | 2 disks | n − 2 |
| RAID 10 | mirror + stripe | 1 per mirror pair | n/2 |
Journaling
Before changing the file system, the OS writes what it intends to do in a journal (log). After a crash it replays or discards the log instead of scanning the whole disk. Examples: ext4, NTFS, APFS.
Interview one-liners
- An inode stores metadata and block pointers, not the file name.
- SSTF is not optimal and can starve requests; SCAN/LOOK avoid starvation.
- Seek time is the biggest part of disk access time.
- Hard link → same inode; soft link → a path.
- Related: Page Replacement Algorithms, Memory Management, Paging and Virtual Memory.