File systems

Files and file attributes

Definition. A file is a named logical unit of stored information. Metadata may include type, size, owner, permissions, timestamps, and storage locations. File operations include create, open, read, write, seek, close, and delete; APIs may use descriptors or handles.

Example. An open file descriptor indexes a per-process table that refers to a system-wide open-file object.

Exam point. A file name is a directory entry; it is not necessarily stored inside the file's data blocks.

Solved examples

Example 1 — open-file state. Process P opens the same file twice and receives descriptors 3 and 4.

1. Each open may create a separate per-process descriptor entry.
2. Entries may refer to distinct open-file descriptions with independent offsets.
3. If a descriptor is duplicated, entries may instead share one open-file description.
4. Do not assume independent file offsets without knowing whether the open instance is shared.

Example 2 — file position. A descriptor's current offset is 10; a read returns 4 bytes.

1. The read begins at offset 10.
2. It returns bytes 10 through 13.
3. The sequential offset advances by 4.
4. New offset is 14, assuming a successful four-byte read.

Directory structures and paths

Definition. A directory maps names to file-system objects. A path names a sequence of directory entries from a root or current directory. Hard links create additional names for the same inode-like object; symbolic links store a path reference and can become dangling.

Example. /a/b/file traverses root, a, b, then file.

Exam point. Deleting one hard link removes a name; file data remains while references exist under the file system's link-count rules.

Solved examples

Example 1 — path traversal. Current directory is /home/u; resolve ../v/data.

1. .. moves to /home.
2. v selects /home/v.
3. data selects /home/v/data.
4. Resolved path is /home/v/data.

Example 2 — hard link count. File inode has link count 2. One directory name is removed.

1. The removed name no longer refers to the inode.
2. Link count becomes 1.
3. The inode and data remain accessible through the other hard link, absent other deletion semantics.
4. The final link removal is what may make the file reclaimable.

File allocation methods

Definition. Contiguous allocation stores a file in consecutive blocks; linked allocation chains blocks; indexed allocation stores pointers in an index block or inode. Each method trades off sequential access, random access, fragmentation, metadata overhead, and file growth.

Method	Sequential access	Random access	Main cost
Contiguous	fast	fast	external fragmentation and growth difficulty
Linked	natural	slow without traversal	pointer overhead and reliability
Indexed	efficient	direct via index	index-block overhead

Example. A linked file's block 8 may be found by following eight links from its first block if no index is present.

Exam point. Indexed allocation's maximum file size depends on pointer width, block size, and number of index levels.

Solved examples

Example 1 — contiguous location. File begins at block 40 and occupies 6 blocks. Find its last block and block for logical offset 4, zero-based.

1. Blocks are 40,41,42,43,44,45.
2. Last physical block=40+6−1=45.
3. Logical block 4 maps to 40+4=44.
4. Answer: last block 45; offset 4 maps to 44.

Example 2 — indexed capacity. Block size 1024 bytes, pointer size 4 bytes, one index block. Find maximum data bytes.

1. Pointers per index block=1024/4=256.
2. It addresses 256 data blocks.
3. Data capacity=256·1024=262,144 bytes.
4. Maximum is 256 KiB, ignoring index metadata outside the data count.

Inodes and multi-level indexing

Definition. An inode stores metadata and pointers to a file's data blocks, while directory entries map names to inode numbers. Direct pointers cover small files; single, double, and triple indirect pointers scale to larger files.

Example. With 12 direct pointers, one single-indirect pointer, and 256 pointers per index block, capacity is (12+256) blocks.

Exam point. Count index blocks separately if the question asks total allocated blocks rather than maximum data blocks.

Solved examples

Example — inode maximum. Block size 1024 B, pointer size 4 B, 10 direct pointers and one single-indirect pointer. Find data-block capacity.

1. Single-indirect block has 1024/4=256 pointers.
2. Direct plus indirect data blocks=10+256=266.
3. Data bytes=266·1024=272,384 B.
4. Capacity is 266 blocks; the index block itself is additional metadata storage.

Free-space management

Definition. File systems track unused blocks with a bitmap, linked free list, grouping, or counting. A bitmap uses one bit per block and supports finding runs; a linked list is simple but may require traversal. Allocation and release must update metadata consistently.

Example. A disk with 1,000,000 blocks needs a bitmap of 1,000,000 bits, or 125,000 bytes, ignoring overhead.