OS: File Systems

What two primitive operations should a disk support?

Read block k and write block k.

Name three kinds of files.

Byte sequence, record sequence, tree.

What is sequential access?

Reading bytes/records in order from the beginning; cannot jump.

What is random access?

Reading bytes/records in any order, using seek operations.

List five file attributes.

Protection, owner, size, timestamps, read-only flag.

Give 5 file operations.

Create, delete, open, close, read (also write, append, seek).

Problem with single-level directory?

Name collisions and lack of per-user namespaces.

Advantage of hierarchical directories?

Organization and unique pathnames using a root.

What does an inode store?

Metadata: mode, owner, size, timestamps, pointers to data blocks.

What are direct and indirect pointers?

Direct pointers point to data blocks; indirect pointers point to blocks that contain more pointers.

How does contiguous allocation perform sequential reads?

Very fast — data is contiguous.

Main problem with contiguous allocation?

External fragmentation.

What is the FAT?

File Allocation Table — a table storing next-block pointers for files (linked-list on disk).

Bitmap vs free-list: which is faster for checking single-block free?

Bitmap (constant-time bit test in memory).

What does journaling log?

Operations (usually metadata or metadata+data) before applying them.

RAID 0 key property?

Striping without redundancy — higher throughput, no fault tolerance.

RAID 1 key property?

Mirroring — copies on two disks, high reliability and read performance.

RAID 4 vs RAID 5 difference?

RAID 4 uses dedicated parity disk; RAID 5 distributes parity.

Which RAID tolerates two disk failures?

RAID 6.

What's internal fragmentation?

Wasted space within an allocated block because file size < block size.

What's external fragmentation?

Free space split into small pieces that cannot satisfy large allocation requests.

Why use cylinder groups?

To keep related inodes and data blocks near each other to reduce seek time.

What is soft block limit in quotas?

A threshold that can be exceeded temporarily, typically with warnings.

What is a superblock?

Filesystem metadata block describing layout, size, and key offsets.

What data structure speeds up directory lookups?

Directory cache or hashed directory structure.

Why is parity distributed in RAID 5 helpful?

It avoids a single parity-disk bottleneck and balances writes.

What is a dump bit map?

A bitmap marking files/dirs changed since last dump for incremental backups.

How to recover using a journal?

Replay committed journal entries to complete interrupted operations.

How does fsck detect missing blocks?

By scanning inodes and block references versus the free list.

What is an extent?

A contiguous run of blocks allocated as a unit.

File system goals

File systems store large amounts of data persistently, allow concurrent access, and ensure data survives process termination. They expose operations to create, read, write, and manage metadata.

File types & access

Files can be byte streams, record sequences, or trees. Sequential access reads in order, while random access supports seeking for databases and general-purpose OS I/O.

File attributes & operations

Files have attributes like protection, owner, size, timestamps, and flags such as read-only or hidden. Operations include create, delete, open, close, read, write, append, seek, and attribute queries.

Directory structures

Directories organize files as single-level, two-level, or hierarchical trees. Paths resolve names to directory entries and ultimately to file metadata (e.g., inode).

Allocation strategies

Contiguous allocation stores file blocks consecutively (fast sequential access, fragmentation). Linked allocation uses pointers (no external fragmentation, poor random access). FAT stores pointers in a central table. Indexed allocation (inodes) stores pointers in an index structure with direct and indirect pointers for scalability and random access.

Implementing directories & long names

Directories can store attributes directly or pointer to inodes. Long filenames can be stored inline (wastes space) or in an external heap with references (more complex management).

Free-space management

Free blocks tracked via free lists or bitmaps. Bitmaps are compact and allow easy contiguous-search algorithms; free lists are simple but slower for random access.

Quotas & accounting

Quotas enforce per-user block/file limits with soft and hard thresholds, tracking current usage and warnings.

Backups & dumps

Backups (tape, snapshot) protect from disaster and user mistakes. Logical dump algorithms use bitmaps to record changed files since last backup for incremental dumps.

File system consistency

Inconsistencies include missing blocks, duplicate free-list entries, and duplicate data blocks. Tools like fsck reconcile metadata and data structures.

Journaling

Journaling logs operations before applying them to ensure recovery after crashes by replaying the log; can be metadata-only or full-data.

Performance optimizations

Use block caches, place inodes strategically, and use cylinder groups to improve locality and reduce seek times.

RAIDs

RAID levels trade off performance and redundancy: RAID 0 (striping, no redundancy), RAID 1 (mirroring), RAID 4 (block striping + dedicated parity), RAID 5 (distributed parity), RAID 6 (double distributed parity). Choose based on throughput needs and fault tolerance.