Operating Systems Cheatsheet

File Systems

Use this Operating Systems reference while you build software engineering projects, review code for technical interview prep, or polish examples for a software engineer resume.

File System Concepts

A file system organizes and stores data on persistent storage. It provides naming, organization (directories), access control, and reliability.

File: named collection of related data. From the OS view: a sequence of bytes with metadata.

File Attributes (Metadata)

Attribute	Description
Name	Human-readable string
Identifier	Unique inode/file ID within FS
Type	Regular, directory, symlink, device, …
Location	Disk block pointers
Size	In bytes (logical) and blocks (physical)
Permissions	Owner/group/other × r/w/x
Timestamps	`atime` (access), `mtime` (modify), `ctime` (metadata change)
Link count	Number of directory entries pointing to this inode

File Operations (POSIX)

Syscall	Description
`open(path, flags, mode)`	Open/create file; returns fd
`read(fd, buf, n)`	Read n bytes
`write(fd, buf, n)`	Write n bytes
`lseek(fd, offset, whence)`	Move file position
`close(fd)`	Release file descriptor
`stat(path, &sb)`	Get file metadata
`unlink(path)`	Remove directory entry (delete when link count = 0)
`rename(old, new)`	Atomic rename
`truncate(path, size)`	Set file size
`fsync(fd)`	Force data to disk

File Types (POSIX)

Type	`ls` char	Description
Regular	`-`	Data file
Directory	`d`	Maps names → inodes
Symbolic link	`l`	Stores a path string
Block device	`b`	Random-access device (disk)
Character device	`c`	Stream device (terminal)
FIFO / named pipe	`p`	IPC with file interface
Socket	`s`	IPC with network interface

Directory Structure

Structure	Description	Examples
Single-level	One flat directory for all users	Early CP/M
Two-level	Separate directory per user	UNIX early
Hierarchical (tree)	Directories contain files + subdirectories	Linux, Windows
Acyclic graph	Shared subdirectories via hard/soft links	POSIX
General graph	Cycles allowed	Requires cycle detection

Hard Links vs Symbolic Links

Property	Hard Link	Symbolic Link
Points to	Inode directly	Path string
Survives target rename?	Yes	No (dangling link)
Survives target delete?	Yes (inode stays until count = 0)	No
Cross filesystem?	No	Yes
On directories?	No (usually)	Yes
Size	No extra space	Size of path string

link("a.txt", "b.txt");      // hard link
symlink("a.txt", "link.txt"); // symbolic link
unlink("b.txt");              // removes directory entry; inode if count→0

Disk Block Allocation Methods

Contiguous Allocation

File occupies consecutive blocks on disk.

Pros: fast sequential read (single seek), simple indexing
Cons: external fragmentation; file cannot grow easily

Linked Allocation

Each block contains a pointer to the next block.

Pros: no fragmentation; files grow freely
Cons: sequential access only; pointer overhead; reliability (one bad pointer corrupts chain)
FAT (File Allocation Table): linked allocation with pointers in a separate table (not in data blocks)

Indexed Allocation

A dedicated index block holds all block pointers for the file.

Pros: direct access; no fragmentation
Cons: index block overhead; maximum file size = pointers per block × block size

UNIX inode (Multi-Level Index)

inode holds 12–15 block pointers:

Pointer type	Levels	Blocks reachable (4KB block, 4B ptr → 1024 ptrs/block)
Direct (12)	0	12 blocks = 48 KB
Single indirect	1	1024 blocks = 4 MB
Double indirect	2	1024² = 4 GB
Triple indirect	3	1024³ = 4 TB

inode
├── direct[0..11]  → data block
├── single_indirect → [ptr ptr … ptr] → data blocks
├── double_indirect → [ptr … ptr] → [ptr … ptr] → data
└── triple_indirect → 3 levels of index

Free Space Management

Method	Description	Lookup speed
Bit vector (bitmap)	1 bit per block; 0=free, 1=used	O(1) with hardware scan
Linked list	Free blocks chained together	O(n)
Grouping	First free block stores n free block addresses	O(1) for batch
Counting	(first_free_block, count) pairs	Compact for runs

UNIX Filesystem (ext2/ext3/ext4) Layout

| Boot block | Superblock | Block Group 0 | Block Group 1 | … |

Block Group:
| Group descriptor | Block bitmap | Inode bitmap | Inode table | Data blocks |

Superblock: total blocks, free blocks, inode count, block size, magic number. Block group: locality optimization — inode + its data blocks in same group → fewer seeks.

Journaling (ext3/ext4, NTFS, XFS)

Prevents FS corruption on crash by writing intentions to a journal before actual changes.

Mode	What is journaled	Overhead
Writeback	Metadata only; data may precede metadata	Low; may expose stale data
Ordered	Metadata only; data written before metadata commit	Default in ext3
Data journaling	Both data and metadata	Safe; 2× write overhead

Journal commit sequence: 1. Write data to journal (log) 2. Commit record written 3. Write data to actual disk location (checkpoint) 4. Mark journal space as free

Virtual File System (VFS)

Linux VFS provides a uniform interface over heterogeneous FS types (ext4, XFS, tmpfs, FAT, NFS, …).

Application: open(), read(), write()
    ↓
VFS layer: generic inode, dentry, file, superblock objects
    ↓           ↓           ↓
  ext4       tmpfs        NFS
  driver     driver       driver
    ↓
  Block device layer → disk

Four VFS objects:

Object	Represents
`superblock`	Mounted filesystem metadata
`inode`	File/directory metadata
`dentry`	Directory entry (name → inode mapping, cached)
`file`	Open file instance (position, flags)

File Permissions (POSIX)

-rwxr-xr--  1 alice staff 4096 Jan 1 12:00 script.sh
 ↑↑↑↑↑↑↑↑↑
 │└─────── owner: rwx (7)
 │   └──── group: r-x (5)
 │      └─ other: r-- (4)
 └ type: - = regular

Octal: chmod 754 script.sh

Special bits:

Bit	On file	On directory
setuid (04000)	Run as file owner	—
setgid (02000)	Run as file group	New files inherit group
sticky (01000)	—	Only owner can delete entries