File System in OS: Allocation Methods and Inodes

A disk is just a long array of numbered blocks. A file system is what turns those blocks into named files in directories, with sizes, owners and permissions, and keeps that structure consistent as files grow, shrink and disappear. It has to answer three questions for every file: what is it called and who may use it, which blocks hold its data, and which blocks are still free.

Files and their attributes

A file is a named collection of related information stored on secondary storage; it is the smallest unit a user can write to storage. The OS keeps these attributes for every file:

The basic file operations are create, open, read, write, reposition (seek), close, delete and truncate. Because searching the directory on every access would be slow, open() looks the file up once and returns a file descriptor, an index into a per-process open-file table. That entry holds the current file position and points into a system-wide table that holds the file's attributes and a count of how many processes have it open.

Access methods

Sequential access is easy to simulate on a direct-access file, by keeping a current position; the reverse is slow.

Directory structures

A directory maps file names to the files themselves, either holding their attributes or pointing to them.

Tree-structured directories give path names: absolute paths start at the root (/home/asha/notes.txt), relative paths start at the current working directory (notes.txt). Unix file systems are acyclic graphs in practice, thanks to two kinds of link:

• A hard link is a second directory entry naming the same inode. The inode keeps a link count, and the data is freed only when it falls to zero. Hard links cannot cross file systems, and directories cannot be hard-linked apart from the . and .. entries the system creates, which keeps the graph free of cycles.
• A symbolic (soft) link is a tiny file that contains a path. It can point anywhere, even across file systems or to a directory, but it dangles if the target is deleted or moved.

1. notes.txt and copy.txt are two directory entries for the same inode, so its link count is 2 and neither name is the original. short has an inode of its own whose data is just the name notes.txt, looked up each time it is opened.
2. rm notes.txt removes one directory entry: the count drops to 1 and copy.txt still reaches the data, freed only when the count reaches 0. short still holds notes.txt, a name that no longer exists, so it dangles.

Allocation methods

How a file's data is placed on disk decides how fast it can be read and how well space is used. Assume the disk has numbered blocks and nothing is cached except the directory entry. Here is one five-block file placed each way, and what it takes to reach its logical block 3:

1. Contiguous: the file is blocks 14 to 18 and the directory keeps the start and length. Logical block 3 is at 14 + 3 = 17, found by arithmetic: one read.
2. Linked: the blocks are scattered and each holds the number of the next. Reaching logical block 3 means reading 9, 16, 1 for their pointers first: 4 reads, and block 50 would take 51.
3. Indexed: block 4 lists the file's blocks in order. Read it, take entry 3, which is block 10, and read that: two reads for any block, at the cost of a whole block for the index.

Contiguous allocation

Each file occupies a run of consecutive blocks; the directory stores the start block and length, so logical block i is simply at start + i.

• Sequential and random access are both fast: one computation, one read, minimal head movement.
• External fragmentation builds up as files are created and deleted, exactly as with contiguous memory allocation.
• Files are hard to grow: the next blocks may be taken, so the file must be moved or its size declared in advance.

Extents, used by ext4 and NTFS, keep the benefit while allowing growth: a file is a short list of contiguous runs, each recorded as (start, length).

Linked allocation

Each file is a linked list of blocks scattered anywhere; the directory holds the first and last block, and each block holds a pointer to the next.

• No external fragmentation, and files grow freely.
• Random access is slow: reaching logical block i means reading the i blocks before it to follow the pointers.
• Each block loses a few bytes to the pointer.

Indexed allocation

All of a file's block addresses are gathered into one index block, the directory points to it, and entry i holds the address of logical block i.

• Fast random access and no external fragmentation.
• The index block costs space even for a tiny file, and a large file needs more than one index block: a linked list of index blocks, a multilevel index, or the combined scheme of the Unix inode below.

Reads needed to fetch logical block 50 of a file:

Comparison

Inodes in Unix file systems

Unix file systems such as ext2 and ext3 use a combined indexed scheme. Each file has an inode holding its type, permissions, owner, size, timestamps, link count and 15 block pointers: 12 direct pointers to data blocks, then a single indirect pointer to a block full of data-block pointers, a double indirect one level deeper and a triple indirect one level deeper again. Small files are reached with no extra reads, while the indirect levels let files grow very large.

1. The inode holds the file's attributes (no name) and 15 pointers. Twelve point straight at data, 48 KB; the indirect ones point at blocks of 1,024 pointers, one, two and three levels deep, reaching 4 MB, 4 GB and 4 TB.
2. Byte 60,000 is in logical block 14. Blocks 12 to 1,035 go through the single indirect block, at entry 14 − 12 = 2: read that block, then the data. Two reads.
3. Byte 10,485,760 (10 MB) is in block 2,560, past 1,035, so in the double indirect range at position 1524: entry 1 of the first index block, entry 500 of the second, then the data. Three reads.

Worked example: maximum file size. Blocks are 4 KB and a block pointer is 4 bytes, so one block holds 4096 ÷ 4 = 1,024 pointers.

That is the textbook limit of the pointer structure. Real file systems add other limits, such as the width of the size field, and ext4 replaces the indirect blocks with extents by default.

Worked example: reads to reach a byte, with the inode already in memory. Logical blocks 0 to 11 are direct, 12 to 1,035 go through the single indirect block, and 1,036 to 1,049,611 through the double indirect block. Byte 60,000 is in block 60000 ÷ 4096 = 14, single indirect: 2 reads. Byte 10,485,760 (10 MB) is in block 2,560, double indirect: 3 reads.

Note what the inode does not hold: the file name. Names live in directories, which map names to inode numbers. That is why renaming a file within one file system only edits directory entries, and why hard links are possible.

Free-space management

The file system must know which blocks are free.

Bitmap example. If 1 means free, the bitmap 0 0 1 1 1 0 0 1 for blocks 0 to 7 says blocks 2, 3, 4 and 7 are free; the free run 2 to 4 is visible at a glance. For a 1 TB disk with 4 KB blocks there are 2⁴⁰ ÷ 2¹² = 2²⁸ blocks, so the bitmap is 2²⁸ bits = 32 MB, which is why large file systems split it into groups and load only parts.

FAT (File Allocation Table)

FAT is linked allocation with the pointers moved out of the data blocks into one table at the start of the volume. The table has one entry per cluster (a group of sectors): an entry holds the number of the file's next cluster, an end-of-file mark, or 0 for a free cluster. The directory entry stores a file's first cluster.

Caching the whole table turns linked allocation's worst problem, slow random access, into a walk through RAM, and the FAT doubles as the free-space list. FAT32 uses 28-bit cluster numbers and limits a single file to 4 GB minus 1 byte, which is why larger drives use exFAT or NTFS, but its simplicity keeps it on memory cards and USB drives.

Consistency and journaling

A crash in the middle of an update, say after a block is allocated but before the inode points to it, leaves the structures inconsistent. Older systems ran a checker such as fsck over the whole disk at boot. Journaling file systems, including ext4, NTFS and XFS, first write each update as a transaction to a log, the journal, and only then to its real place. After a crash only the journal needs replaying, which takes seconds instead of a full scan. Most journal only metadata by default; ext4's default ordered mode also writes data blocks before the metadata that points to them is committed.

Common mistakes

• Saying the inode stores the file name. The name is in the directory entry.
• Treating linked allocation and FAT as unrelated. FAT is linked allocation with the links kept in a table.
• Forgetting that contiguous allocation suffers external fragmentation, not internal.
• Saying a hard link and a symbolic link behave the same when the original is deleted. The hard link still works; the symbolic link dangles.
• Computing pointers per block as block size in bits divided by pointer size in bytes. Use bytes for both: 4096 ÷ 4 = 1,024.
• Thinking a journal makes every write safe. Journaling protects the file system's structure; whether file data is protected depends on the mode.

Interview questions

Which allocation method is best for random access, and why? Contiguous allocation: the address of any logical block is start + i, so one read reaches it. Indexed allocation is close behind, needing one extra read for the index block, while linked allocation must follow every pointer before the wanted block.

How large can a file be with 12 direct, one single, one double and one triple indirect pointer, 4 KB blocks and 4-byte pointers? Each block holds 1,024 pointers, so the file can have 12 + 1,024 + 1,024² + 1,024³ blocks of 4 KB: 48 KB + 4 MB + 4 GB + 4 TB, just over 4 TB.

What happens to a file's data when you delete one of its hard links? Only that directory entry is removed and the inode's link count drops by one. The data is freed when the count reaches zero and no process still has the file open.

Why does FAT allow faster random access than plain linked allocation? In plain linked allocation each next-pointer is inside a data block, so following the chain means reading those blocks from disk. FAT keeps all the pointers in one table that can be cached, so the chain is followed in memory and only the wanted block is read.

What is the difference between a file descriptor and an inode? An inode describes a file on disk and exists whether or not anyone is using it. A file descriptor is a small integer a process gets from open(), indexing its open-file table, which records the current position and refers to the in-memory copy of the inode.

Why do file systems use bitmaps for free space? A bitmap is compact enough to keep in memory and makes it fast to find a free block, or a run of free blocks near a file, by scanning words for set bits. Allocating contiguous runs keeps files less fragmented and reads faster.

Next, read Disk Scheduling Algorithms, or test yourself with the Operating Systems (Intermediate) skill test.