Sunday 20 December 2020

OS Free Space Management: Bit Vector, Linked List, Grouping and Counting

 

v FREE SPACE MANAGEMENT:

 

o   Since disk space is limited we need to reuse the space from deleted files for new files if possible.

o   To keep track of free disk space the system maintains free space list. The free space list records all free disk blocks- those not allocated to some file or directory.

o   To create a file we search the free space list for the required amount of space and allocate that space to the new file. This space is then removed from the free space list.

o   When a file is deleted its disk space is added to free space list.  The free space list despite its name might not be implemented as a list.

 

1.     Bit Vector:

o   Frequently the free space list is implemented as a bit map or bit vector. Each block is represented by 1 bit.

 

o   If the block is free, the bit is 1; if the block is allocated, the bit is 0. For example consider a disk where disc blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 and 27 are free and the rest of the blocks are allocated.  The free space bit map would be:0011111001111110001100000011100000...

 

o   The main advantage of this approach is its relative simplicity and efficiency in finding the first free block or ‘n’ consecutive free blocks on the disk.

 

o   Many computers supply bit manipulation instructions that can be used effectively for that purpose.  For example,  the Intel family starting with 80386 and the Motorola family starting with 68020 have instructions that return the offset in a word of first bit with value 1.

 

2.    Linked List:

o   Another approach to free space management is to link together all the free disk blocks, keeping a pointer to the first free block in a special location on the disc and caching it in the memory.

 

o   This first block contains a pointer to the next free disk block and so on. However this scheme is not efficient; to traverse the list, we must read each block, which requires substantial IO time.

 

o   The FAT method incorporates free block accounting into the allocation data structure. No separate method is needed.

 

3.     Grouping:

o   A modification of the free-list approach is to store the address of ‘n’ free blocks in the first free block.

o   The first n-1 of these blocks are actually free. The last block contains the addresses of other ‘n’ free blocks and so on.

o   The importance of this implementation is that the addresses of a large number of free blocks can be found quickly unlike in the standard linked list approach.

 

4.     Counting:

o   Another approach is to take advantage of the fact that generally several contiguous blocks may be located or freed simultaneously particularly when space is allocated with the contiguous allocation algorithm or through clustering.

o   So rather than keeping a list of ‘n’ free disk addresses, we keep the addresses of the first free block and the number ‘n’ of free contagious blocks that follow the first block.

o   Each entry in the free space list then consists of a disc address and count.

o   Although each entry requires more space than would a simple disc address, the overall list will be shorter as long as the count is generally greater than 1.


No comments:

Post a Comment