Filesystem Navigation, Files, Links and Archives

filesystem hierarchy

The single Linux directory tree rooted at /, with standard locations for programs, configuration, devices, data and variable state.

absolute and relative path

An absolute path begins at /; a relative path is resolved from the process’s current working directory.

inode

An inode stores a filesystem object's metadata and block references; a directory maps a human-readable filename to the inode number.

directory entry

A mapping from a filename to an inode within a directory; the inode stores the file’s metadata and block references.

hard link

A hard link is another directory entry for the same inode, so all hard-link names refer to one underlying file and share its data and metadata.

symbolic link

A symbolic link is a separate file whose content is a pathname; it can cross filesystems and can become dangling when its target is removed.

find and locate

find walks the live directory tree and evaluates predicates and actions

grep and sort

grep selects lines matching a pattern, while sort orders records under a locale and key definition

archive and compression

Archiving combines file names, metadata and contents into one stream, while compression removes redundancy

Makefile

A declarative file of targets, prerequisites and recipes used by make to rebuild only outputs whose inputs changed.

File Management

What is a File?

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

File Attributes:

Attribute	Description
Name	Human-readable identifier
Type	Extension indicating content type
Location	Path to file on filesystem
Size	Current size in bytes
Creator / Owner	Who created it
Permissions	Read/Write/Execute for owner/group/others
Timestamps	Created, Modified, Accessed times
Inode	Unique identifier in Unix filesystems

File Types

Type	Extension	Description
Text	.txt, .c, .py, .md	Human-readable characters
Binary	.exe, .so, .o	Machine-readable binary
Image	.jpg, .png, .gif	Image data
Audio	.mp3, .wav, .flac	Audio data
Video	.mp4, .avi, .mkv	Video data
Archive	.zip, .tar, .gz	Compressed collections
Database	.db, .sqlite	Structured data

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

Filesystem	OS	Description
FAT32	Windows/USB	Old; max file 4GB; widely compatible
exFAT	Cross-platform	USB drives; large files supported
NTFS	Windows	Journaling; permissions; compression
ext4	Linux	Journaling; most common Linux fs
APFS	macOS/iOS	Modern; encryption; snapshots
ZFS	Solaris/FreeBSD	Advanced; checksums; copy-on-write
Btrfs	Linux	Next-gen; snapshots; RAID
HFS+	Old macOS	Legacy Apple filesystem

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

Algorithm	Average Movement	Starvation	Fairness
FCFS	High	No	Yes
SSTF	Low	Yes	No
SCAN	Medium	No	Good
C-SCAN	Medium	No	Better
LOOK	Low-Medium	No	Good
C-LOOK	Low-Medium	No	Best