This document discusses different implementations of free space lists for disk storage management including bit vector, linked list, grouping, and counting. It provides examples and compares the advantages and limitations of each approach. The bit vector approach uses a bitmap to track free blocks but requires extra space. Linked lists link free blocks together through pointers but are inefficient for contiguous allocation. Grouping stores addresses of free blocks in the first block. Counting stores the address and number of contiguous free blocks in each list entry.
This document discusses different implementations of free space lists for disk storage management including bit vector, linked list, grouping, and counting. It provides examples and compares the advantages and limitations of each approach. The bit vector approach uses a bitmap to track free blocks but requires extra space. Linked lists link free blocks together through pointers but are inefficient for contiguous allocation. Grouping stores addresses of free blocks in the first block. Counting stores the address and number of contiguous free blocks in each list entry.
This document discusses different implementations of free space lists for disk storage management including bit vector, linked list, grouping, and counting. It provides examples and compares the advantages and limitations of each approach. The bit vector approach uses a bitmap to track free blocks but requires extra space. Linked lists link free blocks together through pointers but are inefficient for contiguous allocation. Grouping stores addresses of free blocks in the first block. Counting stores the address and number of contiguous free blocks in each list entry.
This document discusses different implementations of free space lists for disk storage management including bit vector, linked list, grouping, and counting. It provides examples and compares the advantages and limitations of each approach. The bit vector approach uses a bitmap to track free blocks but requires extra space. Linked lists link free blocks together through pointers but are inefficient for contiguous allocation. Grouping stores addresses of free blocks in the first block. Counting stores the address and number of contiguous free blocks in each list entry.
Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 16
Seminar On
Disk Free Space Management
20BCS016 ASHWIN SAMPATH
20BCS019 BADHRINATHAN.S.B
20BCS020 BHARATH S
20BCS024 DEEPTHI A S
Various Implementation of Free Space List • Bit Vector • Linked List • Grouping • Counting Bit Vector • It has Free Space list it implemented as a bit map or bit vector • If the block is free the bit is set to 1 • If the block is allocated to the bit is set to 0 Bit Vector Example • 2,3,4,5,8,9,10,11,12,13,17,18,25,26 & 27 are free and the rest of the blocks are allocated . • The free space bit map would be • 0011110011111100011000110000011100000……… (n blocks)
bit[l]= 0 block[l] free
1 block[l] occupied Block number calculation (number of bits per word)* (number of 0-Value words)+ Offset of first 1 bit Bit map requires extra space Example : I. Disk Size = 1.3 GB II. Block Size = 512 bytes III. Need a bit map of over 332 KB to track it free blocks Advantage
Relatively Simple and efficient
Easy to get contiguous files
Linked List Link all free disk blocks together Keep a pointer to the first free block in special location on the disk and caching it in memory Cannot get contiguous space easily No waste of space This block contains a pointer to next free block Linked Free Space List on Disk Example : A. Pointer to block two as the first free block B. Block two would contain a pointer to block three C. Which would point to block four D. Which would point 5,8,9,10,11,12,13,17,18,25,26,27 Linked list (free list) • Cannot get contiguous space easily • No waste of space • Not efficient for faster access • Substantial input/output Bit Vector 11000011000000111001111110001111
Counting 2 4 8 6 17 2 25 3 Grouping o Store addresses of n free blocks in the first free block o The first n-1 of these are actually free o The last block contains the address as of another free blocks. Advantage • Large number of free blocks can be found quickly Counting Based on the fact that several contiguous blocks may be allocated and freed simultaneously Holds the address of the first free block and number “n” of free contiguous blocks that follow the first block Each entry is the free space list consist of a disk address and count Counting Entry in a free space list consists of • Disk address • Count What it’s limits 1. Each entry requires more space than a simple disk address 2. The over all list be shorter, as long as the count is greater than one This Photo by Unknown Author is licensed under CC BY-NC
