We all save our files in the hard disk. Hence, to make the maximum out of the disk space the files have to be stored in an efficient manner. This also ensures quick access when the data from these files is required. There are three file allocation method:
- Contiguous File Allocation
- Linked File Allocation
- Indexed File Allocation
Contiguous Allocation
In contiguous file allocation method each file:
- File occupy contiguous blocks
- Directory entry contains
- Filename
- Starting block
- Length (total blocks)
- Access possible
- Sequential
- Direct
- Problems
- Finding space for new file
- External fragmentation
- Determining space requirement of a file
In the above example
- File “sum” occupies blocks 2, 3 and 4.
- File“jeep” occupies blocks 7, 8, 9, 10 and 11
- File “song” occupies blocks 15 and 16.
Linked Allocation
In linked file allocation method each file:
- Directory structure contains
- Pointer to the first and last block of file
- Advantages
- No external fragmentation
- No issue with increase in file size
- Disadvantages
- Only sequential access
- Reliability – loss of a pointer
- Space required for pointers
- Solution: make cluster of blocks
- Problem: internal fragmentation
In the above example
- For file “car” the first data block is 8
- Block 8 contains data and a pointer to the next data block, which is block 3.
- Block 3 points to the next data block i.e. 16
- Block 16 is the last block as pointed in the directory entry.
Indexed Allocation
For each file, the indexed file allocation method:
- Clubs all the pointers into one block – index block
- Directory entry contains
- Filename
- Index block number
- Access
- Direct
- Issue
- Size of index block
- Sol: multilevel indexing
In the above example
- Block 8 is the index block which contains pointers to all the data blocks i.e., 10, 4, 12 and 19.
- -1 entry in block 8 means it can contain entries to two other data blocks.
- Indexing can be single level (in above example), two level or multi level depending upon the file size
Performance
- Contiguous
- Requires only 1 access to get a disk block
- Linked
- Requires i disk reads to read ith block
- Indexed
- Depends on
- level of indexing
- Size of file
- Position of desired block
- Depends on
Example of File Allocation Method
Consider a file currently consisting of 100 blocks. Assume that the file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.
a. The block is added at the beginning.
b. The block is added in the middle.
c. The block is added at the end.
Share your answers in the comments section below
PPT
The above discussion is summarized in the form of a PPT with animations below.
Note: Click within the slide area for animations. Clicking on the “next” slide button will not display any animation
Previous Next File Management Free Space Management