--- title: "File allocation and access methods" subject: "Operating System" chapter: 5 key: "semester_6/operating_system:file-allocation-access-methods" source: https://www.bctengineer.com/q/semester_6/operating_system/file-allocation-access-methods site: BCT Engineering --- # File allocation and access methods Operating System · Chapter 5: File Systems - Asked in: 2074 Bhadra, 4+6 marks - Video: [Allocation Methods | File Allocation Methods | Contiguous | linked | indexed | chain | os | files](https://www.youtube.com/watch?v=gK6L3v1b8AM) — Sudhakar Atchala - 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-access-methods - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-5 ## Question Discuss various file allocation and access methods. Compare their advantages and disadvantages. ## Short answer File allocation methods include contiguous (fast sequential/direct access but external fragmentation and file-size knowledge needed), linked (no fragmentation but slow random access), FAT (pointers in memory for faster random access but scaling issues), and indexed (direct access via i-node, no fragmentation, overhead). Access methods are sequential, direct, and indexed sequential; allocation method affects access efficiency. ## 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. #### File access methods | Method | Description | Advantages | Disadvantages | |---|---|---|---| | **Sequential access** | Records are read/written in order, one after another (read next, write next, rewind). Used with tapes and editors | Simple; efficient for whole-file processing | Slow to reach a particular record | | **Direct (random) access** | The file is a numbered sequence of fixed-length blocks/records; any block can be read directly (`read n`, `position to n`) | Fast access to any record; good for databases | Needs fixed record structure; more complex | | **Indexed (index sequential) access** | An index holds keys and pointers to blocks; first search the index, then access the record | Quick keyed lookup, supports both sequential and direct access | Index takes space and has to be maintained | The allocation method affects which access is efficient: contiguous allows both sequential and direct access; linked allocation supports sequential access well but direct access poorly; indexed allocation supports direct access. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which is a disadvantage of linked-list allocation? A. Random access is slow because the chain must be followed, and one lost pointer breaks the file B. It causes external fragmentation C. The file size must be known in advance D. It needs an in-memory table Answer: A. Each block must be read to find the next; pointers inside blocks are fragile. (Key point: Linked allocation weakness) 2. Why does FAT not scale to large disks? A. Each data block loses space to pointers B. The whole table with one entry per block must be in memory C. Files must be contiguous D. It needs a multi-level index Answer: B. A 1 TB disk with 1 KB blocks needs about 10^9 entries. (Key point: FAT scalability) 3. Which is true of indexed (i-node) allocation? A. It has poor direct access B. It needs the whole index of every file in memory C. It supports direct access with no external fragmentation, but has index overhead and needs indirection for large files D. It needs file size known in advance Answer: C. Only open files' i-nodes need be in memory; small files still pay for an index block. (Key point: Indexed allocation) 4. Which access method uses an index of keys pointing to records? A. Sequential access B. Direct access C. Tape access D. Indexed sequential access Answer: D. An index is searched first, then the record's block is read directly. (Key point: Access method) 5. Which allocation method supports direct access poorly? A. Linked allocation B. Contiguous allocation C. Indexed allocation D. None, all support it equally Answer: A. Linked allocation suits sequential access, but direct access requires following the chain. (Key point: Allocation vs access) ## Related in Operating System - [File allocation methods; free space management](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-allocation-free-space-methods) — Operating System, chapter 5, asked 2× - [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 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 - [Directory, file path, access methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adirectory-file-path-access-methods) — Operating System, chapter 5 - [File system layers; linked list vs index](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layers-linked-list-vs-index) — Operating System, chapter 5 - [File system layout; i-node vs linked list](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layout-inode-vs-linked-list) — Operating System, chapter 5 ## Related in other subjects - [Random access file transaction processing](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Arandom-access-transaction) — Object Oriented Programming, chapter 8 - [File I/O operations, errors, random access](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afile-io-errors-random-access) — Computer Programming, chapter 10 - [Spread spectrum multiple access; FDMA vs CDMA](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aspread-spectrum-ma-fdma-cdma) — Wireless Communication, chapter 7 - [Multiple access; FDMA vs CDMA](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Amultiple-access-fdma-vs-cdma) — Wireless Communication, chapter 7