# File Systems and Disk Scheduling — FCFS, SSTF, SCAN, C-SCAN Solved

Source: https://skills101.in/learn/operating-systems/file-systems-and-disk-scheduling — Skills101 free tutorial (Operating Systems). Updated 2026-11-09.

This lesson covers how the OS **organises files** on a disk and how it **orders disk requests** to reduce slow head movement.

## Part A — File systems

A **file system** (NTFS, ext4, APFS, FAT32) decides how files are named, stored, found and protected.

### File allocation methods

| Method | How | Pros | Cons |
|---|---|---|---|
| **Contiguous** | a file uses consecutive blocks | fast sequential & random access | external fragmentation; hard to grow |
| **Linked** | each block points to the next | no external fragmentation; easy to grow | slow random access; a broken link loses the rest |
| **Indexed** | an index block lists all of the file's blocks | fast random access; no fragmentation | index block overhead |

Unix/Linux use **inodes** — an indexed structure that stores the file's metadata (size, owner, permissions, timestamps) and pointers to its blocks (direct, single, double and triple indirect). The **file name is not in the inode**; directories map names → inode numbers.

### Directory structures

- **Single-level** — all files in one directory (name clashes).
- **Two-level** — one directory per user.
- **Tree** — folders inside folders (what you use daily).
- **Acyclic graph** — trees plus shared links (shortcuts / hard and soft links).

**Hard link vs soft link:** a hard link is another name for the same inode (survives deleting the original name); a soft (symbolic) link is a small file containing a path (breaks if the target is deleted).

## Part B — Disk scheduling

On a hard disk, moving the read head between tracks (**seek time**) is the slowest part. Scheduling orders requests to reduce total head movement. (SSDs have no moving head, so this matters far less for them.)

**Example used below:** tracks 0–199, head at **53**, request queue **98, 183, 37, 122, 14, 124, 65, 67**.

### FCFS — in arrival order

53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67. Total head movement = **640** cylinders. Fair, but lots of zig-zag.

### SSTF — Shortest Seek Time First

Always go to the **nearest** pending request.

![SSTF from head 53: 65, 67, 37, 14, 98, 122, 124, 183 — 236 cylinders of movement](https://skills101.in/learn-img/operating-systems/disk-sstf.svg)

Path: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183. Total = **236**. Much better, but requests at the far ends can **starve** if new nearby requests keep arriving.

### SCAN (elevator) — sweep one way, then reverse

Moving towards 0 first: 53 → 37 → 14 → **0** → 65 → 67 → 98 → 122 → 124 → 183. Total = 53 + 183 = **236**.

### C-SCAN (circular SCAN) — sweep one way, jump back, sweep again

Moving up: 53 → 65 → 67 → 98 → 122 → 124 → 183 → **199**, jump to **0**, → 14 → 37.
Movement while servicing = **183** cylinders (plus the 199-cylinder return jump if your exam counts it, for 382). C-SCAN gives **more uniform waiting** than SCAN.

| Algorithm | Total movement (this example) | Note |
|---|---|---|
| FCFS | 640 | fair, slow |
| SSTF | 236 | fast, may starve |
| SCAN | 236 | no starvation |
| C-SCAN | 183 (+199 jump) | most uniform wait |

(LOOK and C-LOOK are SCAN/C-SCAN variants that turn around at the last **request** instead of the disk's end.)

## Common mistakes

- Forgetting that SCAN goes all the way to the end (0 or 199) before reversing; LOOK doesn't.
- Not stating whether the C-SCAN return jump is counted — say it explicitly in exams.
- Thinking deleting a hard link's original name deletes the data.

## Quick recap

- Allocation: contiguous (fast, fragments), linked (flexible, slow random), indexed (inodes).
- Disk scheduling reduces seek time: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK.
- SSTF can starve far requests; SCAN/C-SCAN avoid starvation.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/file-systems-and-disk-scheduling