--- title: "File allocation methods; free space management" subject: "Operating System" chapter: 5 key: "semester_6/operating_system:file-allocation-free-space-methods" source: https://www.bctengineer.com/q/semester_6/operating_system/file-allocation-free-space-methods site: BCT Engineering --- # File allocation methods; free space management Operating System · Chapter 5: File Systems - Asked in: 2070 Magh, 2+6 marks; 2071 Bhadra, 6+4 marks; year not given (asked 2 times) - Video: [File System Implementation: Allocation Methods & Free Space Management Explained!](https://www.youtube.com/watch?v=pzrZYiSWSXc) — CodeLucky - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/file-allocation-free-space-methods - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-5 ## Question Describe different file allocation methods (with advantages and disadvantages of each). Explain free disk space management with example. ## Short answer Contiguous allocation is fast but suffers external fragmentation; linked avoids fragmentation yet is slow for random access; FAT keeps pointers in memory; indexed (i-node) supports direct access with index overhead. Free space is managed by bit map, linked list, grouping, or counting. ## Answer #### File allocation methods The file allocation method decides which disk blocks belong to a file. The main methods are: **1. Contiguous allocation** - each file occupies a set of consecutive blocks. The directory stores the start block and length. ```text file A: blocks 0-3 file B: blocks 4-6 free 7-... [A][A][A][A][B][B][B][ ][ ] ``` - Advantages: simple; very fast sequential and direct access (only one seek); only start and length are stored. - Disadvantages: external fragmentation (needs compaction); file size must be known in advance; file growth is difficult. **2. Linked-list allocation** - each block contains a pointer to the next block; the directory stores the first block. ```text [blk 9 |->2] [blk 2 |->14] [blk 14 |->nil] ``` - Advantages: no external fragmentation; files can grow easily; no need to know size. - Disadvantages: random access is very slow (must follow the chain); the pointer takes space in each block (so the data size is no longer a power of 2); one lost pointer breaks the file (poor reliability). **3. Linked list with a table in memory (FAT)** - the pointers are moved out of the data blocks into a File Allocation Table in memory; entry *i* gives the block after block *i*. - Advantages: full block available for data; random access is faster (chain followed in memory). - Disadvantages: the whole table must be in memory (a 1 TB disk with 1 KB blocks needs 10⁹ entries), so it does not scale. **4. Indexed allocation (i-node)** - each file has an index block (i-node) that lists the addresses of all its blocks (UNIX adds indirect blocks for large files). ```text i-node: [b1][b2][b3]...[single indirect]-->[b..][b..] ``` - Advantages: supports direct access, no external fragmentation, only the i-nodes of open files need to be in memory. - Disadvantages: index block overhead (even for a small file); very large files need multiple levels of indirection. #### Free disk space management The OS must keep track of which disk blocks are free. Common methods: **1. Bit map (bit vector)** - one bit per block: 1 = free, 0 = allocated (or the reverse). Example: for a disk of 16 blocks where blocks 2, 3, 5, 8, 9 are free: ```text block: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 bit : 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 ``` Simple and easy to find *n* consecutive free blocks. Size = number of blocks / 8 bytes: a 16 GB disk with 1 KB blocks has 16 M blocks, so the map needs 16 Mbit = 2 MB. **2. Linked list of free blocks** - each free block holds the address of the next free block; the OS keeps only the head. No extra space is used, but traversing the list is slow. ```text head -> [2 |->3] -> [3 |->5] -> [5 |->8] -> [8 |->9] -> nil ``` **3. Grouping** - the first free block stores the addresses of *n* free blocks; the last of those holds the addresses of the next *n*. Many free blocks can be found quickly. **4. Counting** - store the address of the first free block and the number of contiguous free blocks following it, e.g. (2,2), (5,1), (8,2). Short list when free space is contiguous. **5. Free list in blocks (pointer blocks)** - Tanenbaum: a block holds as many free block numbers as fit (e.g. 255 in a 1 KB block with 4-byte numbers); when it empties, the next list block is read. Bit map needs more memory than the list on a nearly full disk, but is better on a nearly empty disk. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is a disadvantage of contiguous allocation? A. Slow sequential access B. External fragmentation and difficulty growing files C. Pointers in each block D. Huge table in memory Answer: B. File size must be known and free space fragments, needing compaction. (Key point: Contiguous allocation) 2. Why does FAT not scale to large disks? A. The whole table must be in memory (1 TB disk, 1 KB blocks needs 10^9 entries) B. It needs one pointer per byte C. It cannot do random access D. It uses bitmaps Answer: A. One entry per block must stay in memory. (Key point: FAT limitation) 3. A 16 GB disk with 1 KB blocks has how large a bit map? A. 16 Mbit = 2 MB B. 16 MB C. 16 KB D. 128 MB Answer: A. 16 GB / 1 KB = 16 M blocks, one bit each = 16 Mbit = 2 MB. (Key point: Bitmap size) 4. The counting method stores what? A. The address of every free block B. First free block address and the number of contiguous free blocks after it C. A bit per block D. Only the head pointer Answer: B. E.g. (2,2),(5,1),(8,2); good when free space is contiguous. (Key point: Counting method) ## Related in Operating System - [File system layout; free block management](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layout-free-blocks) — Operating System, chapter 5 - [File system vs virtual memory; contiguous allocation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-vs-virtual-memory-contiguous-tape) — Operating System, chapter 5 - [File and attributes; allocation methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-attributes-allocation-methods) — Operating System, chapter 5 - [File allocation and access methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-allocation-access-methods) — Operating System, chapter 5 - [File attributes; directory systems; free blocks](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-attribute-directory-free-blocks) — Operating System, chapter 5 - [Linked list file system; block size impact](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-linked-list-block-size) — Operating System, chapter 5 ## Related in other subjects - [Numerical: cordless phone free space path loss](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Acordless-phone-path-loss) — Wireless Communication, chapter 3, asked 2× - [Friis equation and free space path loss](https://www.bctengineer.com/question.md?key=semester_6%2Fpropagation_and_antenna%3Afriis-path-loss-free-space) — Propagation and Antenna, chapter 5, asked 2× - [Free space propagation and Friis derivation](https://www.bctengineer.com/question.md?key=semester_6%2Fpropagation_and_antenna%3Afree-space-friis-complete) — Propagation and Antenna, chapter 5, asked 2× - [Poynting numerical, wave in free space](https://www.bctengineer.com/question.md?key=semester_3%2Felectromagnetism%3Apoynting-numerical-em-wave-free-space) — Electromagnetism, chapter 4