Free Space Management

FREE SPACE MANAGEMENT

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

ü To keep track of free disk space, the system maintains a free-space list.

ü The free-space list records all free disk blocks – those not allocated to some file or directory.

ü 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.

ü When a file is deleted, its disk space is added to the free-space list.

1. Bit Vector

o   The free-space list is implemented as a bit map or bit vector.

o   Each block is represented by 1 bit. If the block is free, the bit is 1; if the block is allocated, the bit is 0.

o   For example, consider a disk  where block

o   2,3,4,5,8,9,10,11,12,13,17,18,25,26 and 27 are free, and the rest of the block are allocated. The free space bit map would be

o   001111001111110001100000011100000 …

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

2. Linked List

v 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 disk and caching it in memory.

v This first block contains a pointer to the next free disk block, and so on. In our example, we would keep a pointer to block 2, as the first free block. Block 2 would contain a pointer to block 3, which would point to block 4, which would point to block 5, which would point to block 8, and so on.

v However, this scheme is not efficient; to traverse the list, we must read each block, which requires substantial I/O time. The FAT method incorporates free-block accounting data structure. No separate method is needed.

3. Grouping

v A modification of the free-list approach is to store the addresses of n free blocks in the first free block.

v The first n-1 of these blocks are actually free.

v The last block contains the addresses of another n free blocks, and so on.

v The  importance  of  this  implementation  is  that  the  addresses  of  a  large number of

free blocks can be found quickly.

4. Counting

v We  can  keep  the  address  of the  first  free  block  and the  number n  of  free contiguous blocks that follow the first block.

Each entry in the free-space list then consists of a disk address and a count.

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

Recovery

Files and directories are kept both in main memory and on disk, and care must be taken to ensure that system failure does not result in loss of data or in data inconsistency.

1. Consistency Checking

· The directory information in main memory is generally more up to date than is the corresponding information on the disk, because cached directory information is not necessarily written to disk as soon as the update takes place.

ü        Frequently, a special program is run at reboot time to check for and correct disk inconsistencies.

ü        The consistency checker—a systems program such as  chkdsk in MS-DOS—compares

the data in the directory structure with the data blocks on disk and tries to fix any inconsistencies it finds. The allocation and free-space-management algorithms dictate what types of problems the checker can find and how successful it will be in fixing them.

2. Backup and Restore

· Magnetic disks sometimes fail, and care must be taken to ensure that the data lost in such a failure are not lost forever. To this end, system programs can be used to back up data from disk to another storage device, such as a floppy disk, magnetic tape, optical disk, or other hard disk.

Recovery from the loss of an individual file, or of an entire disk, may then be a matter of restoring the data from backup.

A typical backup schedule may then be as follows:

§  Day 1: Copy to a backup medium all files from the disk. This is called a full backup.

§  Day 2: Copy to another medium all files changed since day 1. This is an incremental backup.

§  Day 3: Copy to another medium all files changed since day 2.

§  Day N: Copy to another medium all files changed since day N— 1. Then go back to Day 1.