[go: up one dir, main page]
Scribd
Upload
193 views19 pages

Free Space Management

The document discusses different techniques for managing free space in a file system: linked list, grouping, bit vector, and counting. A linked list tracks individual free blocks. Grouping stores multiple block addresses in each list node. A bit vector uses an array of bits where each bit represents a disk block. Counting stores the starting block and number of free blocks in each cluster. The techniques vary in space efficiency, ability to find contiguous free blocks, and overhead.

Uploaded by

Rehman Butt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
193 views19 pages

Free Space Management

The document discusses different techniques for managing free space in a file system: linked list, grouping, bit vector, and counting. A linked list tracks individual free blocks. Grouping stores multiple block addresses in each list node. A bit vector uses an array of bits where each bit represents a disk block. Counting stores the starting block and number of free blocks in each cluster. The techniques vary in space efficiency, ability to find contiguous free blocks, and overhead.

Uploaded by

Rehman Butt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 19

Free Space Management

File System Implementation


Introduction
• The file system needs to track free blocks

• When a file is created, blocks are allocated

• When a file gets deleted, blocks are returned


The Free List
• File system maintains a list of free blocks

• Implementation of free list


– Linked list
– Grouping
– Bit vector
– Counting
Linked List
• A linked list of free blocks

• Contains all the free blocks in the disk

• Grows when a file is deleted

• Shrinks when a file is created


Linked List ...

Source: Operating Systems by Silberschatz et al


Grouping
• Grouping is a variation of the linked list

• Each node contains N pointers

• First N – 1 pointers point to simple free blocks

• The last pointer points to the next node


Grouping ...
Advantage of Grouping

• In grouping, a single disk block provides


addresses of roughly N free blocks

• In the simple linked list, to find N free blocks


we need to read roughly N disk blocks
Bit Vector
• Bit vector is an array of bits

• There is a bit for each disk block

• Normally 0 means occupied and 1 means free


Advantage of Bit Vector
• Bit vector helps in finding contiguous blocks

• Bits of contiguous blocks are placed


contiguously
Contiguous Blocks Increase Efficiency

• It is efficient to read/write contiguous blocks

• The read/write head does not need much


movement
Cost of Bit Vector

• Bit vector requires space

• Linked list is contained in the free blocks


Exercise
• What will be size of the bit vector, considering
the following parameters:
– Disk size: 100 GB
– Block size: 4 KB
Solution
# of blocks: 100 * 1024 * 1024 KB / 4 KB
= 25 * 1024 * 1024

Size of bit vector: 25 * 1024 * 1024 bits


= (25 * 1024 * 1024) / 8 bytes
= 3.12 MB
Counting
• Each entry of the free-list provides
information about a cluster of free blocks

• An entry contains two integers: starting block


no, and no of free blocks
Counting ...
• Counting is better than bit-vector when free
blocks are available in the form of large
clusters

• (Exercise in the online session)


A Note about FAT
• There is no need to use a separate free-list

• The free blocks can be marked in the FAT itself


Summary
• Linked list

• Grouping

• Bit vector

• Counting
The End

You might also like