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