CSE 131 Lecture Notes - Lecture 22: Linked List, Root Directory, Inode
Document Summary
Use a linked list to keep track of free memory blocks and information about it. Keep a bit vector, with one entry per file block. Number bits from 0 to n-1, where n is the number of blocks available for files on the disk. If bit[j] == 0, block j is free. If bit[j] == 1, block j is in use by a file. If ords are 32 bits long, calculate appropriate bit by: Search for free blocks by looking for words with bits unset: Easy to find consecutive blocks for a single file. Bit map must be stored on disk and consumes space. Ex: assume 4 kb blocks, 256 gb disk -> 64m blocks. 64 m bits = 2^26 = 2^23 bytes = 8 mb overhead. Ex: 1 tb total, 4 kb block size. 1 tb / 4k = 2^44 / 2^12 = 2^28 = 256 mb size bit vector. Use a linked list to manage free blocks.
