Subscribe by Email

Saturday, June 8, 2013

Explain the methods for free space management? – Part 1

- For efficient working of the programs and the entire operating system, it is important that the memory of the system should be managed. 
- When the files and programs are allocated memory space, some free space is left in the storage area. 
- It is required that these free spaces must be managed properly. 
- Since there is a limitation to the disk space, this same space has to be used again and again after deleting and creating new files. 
- A free space list is maintained by the operating system for keeping the track of the available free space. 
- All the free disk spaces are listed in free space list. 
- For the creation of a new file this free space list is searched in order to get the amount of space needed and then if the space is available, it is allocated to the file to be created. 
- In the case of deletion, after deleting the file, its space is added to the list of free spaces.

Methods for Free Space Management

There are 4 methods for the management of free space namely:
- Bit vector
- Linked list
- Grouping
- Counting

What is Bit Vector?
- Quite a many times, the free space list about which we mentioned above, is implemented as the bit vector (also known as the bitmap). 
- Here, 1 bit is used for representing each block. 
- If a particular block has been allocated to some file or program, its representative bit is set to 0 and when the block is available, the bit is set to one.
- Consider an example, suppose the following disk blocks are free and rest are allocated: 1, 2, 4, 5, 6, 7, 9, 10, 12, 13, 14, 18, 19, 21, 26, 27, 28. 
- Then for this allocation we have the following free – space bit map:
- This method of free space management is relatively simple and has good efficiency. 
- This method is known for its efficiency to locate the n consecutive free blocks or the first free block available in the storage area. 
- But this method can be inefficient if it is not kept in the main memory of the system. 
- Also, when required occasionally for the recovery needs, this map can also be written to the disk. 
- Keeping such maps in the physical memory is an easy thing if the system has a small memory but this is not always possible in the case of the systems with larger memories.

What is a Linked list?
- In this method, all the free spaces are linked together and the first block in this linked list is assigned a pointer which is stored in the cache memory. 
Similarly, the pointer to the second block is stored in the first block.

What is Grouping?
- This method is a modified version of the free list approach and it stores the addresses of the all the free blocks in the first block that is free. 
- Here, actually the first n- 1 blocks only are free and the address of another n free blocks is stored in the last block. 
- This lets the system to find the addresses of a number of free blocks which is not possible in the case where the approach being used is the linked list approach.

What is Counting?
- This approach takes advantage of the simultaneous allocation or freeing of the contiguous blocks through clustering or by using contiguous allocation algorithm. 
- Thus, it requires only to keep the address of the first free block and the rest of the blocks follow it. 

No comments:

Facebook activity