/**/ Free-Space List Management - Dextutor Operating System

Free-Space List Management

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:

  1. Bit Vector
  2. Linked List
  3. Grouping
  4. Counting

Bit Vector


Free space is implemented using bit vector
Each block is represented by one bit
1 means free
0 means allocated
E.g 0011100101110001…………
which means that block 2,3,4,7,9,10,11,15 are free

Advantage

  • Simple
  • Easy to find first free block
  • Easy to find n consecutive free blocks

Disadvantage

  • 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

Linked list


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

Disadvantage

  • Traversal is not easy and requires more time.

Grouping


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.

Counting


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
E.g., 001111001111110000111
Free-space list

  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.

Advantage

  • Easy to locate group of free blocks

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 Allocation Methods           Disk Management

Leave a Comment