D-OS-Ch14ea-Bit_Vector_Free_Space_Management

Bit Vector Free-Space Management

Bit vector / bitmap 用 1 bit 表示 1 個 storage block 的狀態：

1 → free
0 → allocated

---

Allocation

找 free block 時掃 bitmap；找 contiguous free range 時找連續 1 bits。CPU bit operations 可讓 word-level 掃描很快。

概念式計算：

block number = bits_per_word × zero_words_before + bit_offset

---

Tradeoff

• 優點：compact、簡單、容易找 contiguous blocks，適合 D-OS-Ch14da-Contiguous_Allocation / D-OS-Ch14daa-Extent。
• 缺點：大 device 的 bitmap 仍可能很大；若 bitmap 不能 cache 在 memory，allocation 會變慢；分散 delete 可能更新很多 bitmap pages。

例如 1 TB、4 KB blocks 約需 32 MB bitmap：可接受，但不是免費，尤其有很多 volumes 或 huge storage pools 時。