Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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:

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

More Operating Systems notes