The capacity of any disk is limited (e.g., 500 GB, 1TB etc.). Thus, to accommodate our new files, the space freed by deleted files is reused by the system by maintaining a free-space list.
The free-space list keeps a record of all the free blocks of the disk. Whenever a new file is created by the user, the operating system searches for free blocks in the free-space list and allocates some blocks to the new file.
On deletion of a file, the blocks associated with that file are added to the free-space list. The free-space list is not always implemented as a list. Some common methods to implement free-space list:
- Bit Vector
- Linked List
Free space is implemented using bit vector
Each block is represented by one bit
1 means free
0 means allocated
which means that block 2,3,4,7,9,10,11,15 are free
- Easy to find first free block
- Easy to find n consecutive free blocks
- Entire vector is to be kept in main memory – not possible for larger disks
- 1-Tb disk with 4Kb block size requires 32 Mb to store bit map
Link all the free blocks
Keep pointer to first free block in disk
Traverse each block to find out the next free block.
E.g. in the above example, the pointer will point to first free block i.e., 2, Block 2 will contain the pointer to next free block i.e., 3 and so on
- Traversal is not easy and requires more time.
Store addresses of n free blocks in the first free block
The first n-1 out of these are free while nth block contains addresses of another n free blocks.
E.g., Block 2 contains address of next 5 free blocks (3, 4, 5, 9, 10) out of which blocks 3, 4, 5 and 9 are free while block 10 contains the address of next five free blocks.
This approach is used hen several blocks are freed or allocated simultaneously (if contiguous memory allocation is used)
Keep address of first free block and the number(n) of free contiguous free blocks that follow
address count 2 3 8 5
which means that starting from block 2, the next 3 blocks i.e., 3, 4 and 5 are free (total 4 blocks). Similarly, starting from block 8, the next 5 blocks are free.
- Easy to locate group of free blocks
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 Allocation Methods Disk Management