# Free-Space Management
## Free Space
- Free-space list
- 紀錄所有free disk blocks
- Scheme
- Bit vector
- Linked list (same as linked allocation)
- Grouping (same as linked index allocation)
- Counting (same as contiguous allocation)
- FS管理free space的方式通常和file一樣
### Bit vector
- Bit Vector（==bitmap==）: ==每個block用一個bit表示==

bit[i] = 1// occupied
bit[i] = 0// free

- 優點
- 簡單，效率
- 硬體支援bit-manipulation instruction
- 缺點
- bitmap為了效能必須==快取==
- A 1-TB（4KB block） disk needs 32MB bitmap
- $[1024\times1024\times1024\setminus4](block\_num)\setminus\\8(B)\setminus1024(KB)\setminus1024(MB) = 32MB$

### Linked List
- 所有的free blocks link在一起（same as linked allocation）
- 讓==第一個free block pointer==在disk和快取中的==特別位置==
- Traversing list會是沒有效率的
- 沒有需要traversing; 所有的link-pointers放在==table（FAT）==
### Grouping
- 與==linked-index allocation==一樣
- 將n free blocks的address放在1st block
- 前（n-1） pointers是free blocks
- 最後一個pointers是另一個grouping block
### Counting
- 與[contiguous allocation](https://hackmd.io/s/rkZE0cv7f#contiguous-allocation)一樣
- keep first free block的address和contiguous free blocks的數量