7.3 空間配置與碎片整理#

class BitmapFS:
    def __init__(self, total=64):
        self.total = total
        self.blocks = [None] * total     # None=空閒, 否則 (檔名, 邏輯序)
        self.io = 0

    def alloc(self, name, n, scattered=False):
        """scattered=True 模擬碎片化的配置"""
        import random
        free = [i for i, b in enumerate(self.blocks) if b is None]
        if len(free) < n: raise RuntimeError("空間不足")
        random.seed(7 if scattered else None)
        picks = random.sample(free, n) if scattered else free[:n]
        for i, blk in enumerate(picks):
            self.blocks[blk] = (name, i)

    def frag_ratio(self, name):
        locs = [i for i, b in enumerate(self.blocks) if b and b[0] == name]
        order = sorted(locs, key=lambda i: self.blocks[i][1])
        jumps = sum(1 for a, c in zip(order, order[1:]) if c != a + 1)
        return jumps / max(len(order) - 1, 1), order

    def defrag(self, name):
        order = [i for i, b in enumerate(self.blocks)
                 if b and b[0] == name]
        order.sort(key=lambda i: self.blocks[i][1])
        n = len(order)
        # 找連續空段
        run, start = 0, None
        for i in range(self.total):
            run = run + 1 if self.blocks[i] is None or self.blocks[i][0] == name else 0
            if run == n:
                start = i - n + 1; break
        if start is None:
            return False                  # 沒有連續空間，需先搬其他檔案
        for j, old in enumerate(order):
            tgt = start + j
            if tgt == old: continue
            self.io += 2                  # 讀舊 + 寫新
            self.blocks[tgt] = (name, j)
            if self.blocks[old] and self.blocks[old][0] == name:
                self.blocks[old] = None
        return True

fs = BitmapFS(total=64)
fs.alloc("A", 6); fs.alloc("B", 8); fs.alloc("C", 6)
# 製造碎片：刪掉 B 的一部分概念用散置配置模擬
fs2 = BitmapFS(total=64)
fs2.alloc("A", 6, scattered=True); fs2.alloc("C", 6, scattered=True)
r1, order1 = fs2.frag_ratio("A")
print(f"整理前碎片率: {r1:.0%}，區塊位置 {order1}")
fs2.defrag("A")
r2, order2 = fs2.frag_ratio("A")
print(f"整理後碎片率: {r2:.0%}，區塊位置 {order2}，搬移 I/O: {fs2.io}")