别再死记硬背了！用Python手把手带你模拟操作系统恐龙书CH09的三种内存分配算法

用Python实战模拟操作系统内存分配算法：从恐龙书CH09到代码实现

当你翻开《操作系统概念》（俗称恐龙书）第9章，面对first-fit、best-fit、worst-fit这些内存分配算法时，是否觉得纸上谈兵难以理解？本文将通过Python代码带你把抽象理论转化为可视化的实践。我们将从零开始构建内存分配模拟器，用动态演示替代静态计算，让你在调试代码的过程中真正掌握内部碎片、外部碎片等核心概念。

1. 环境准备与基础模型搭建

在开始模拟三种分配算法前，我们需要先建立内存分区的基础表示。Python的类机制非常适合模拟这种系统级概念。下面是一个最小化的内存块实现：

class MemoryBlock: def __init__(self, start, size, allocated=False): self.start = start # 起始地址 self.size = size # 块大小(KB) self.allocated = allocated # 分配状态 self.process_id = None # 占用进程ID def __repr__(self): status = f"进程{self.process_id}" if self.allocated else "空闲" return f"[{self.start}:{self.start+self.size}KB] {status}"

为了模拟完整的分配场景，我们还需要一个内存管理器类来维护所有分区：

class MemoryManager: def __init__(self, partitions): # 初始化内存分区 self.blocks = [] current = 0 for size in partitions: self.blocks.append(MemoryBlock(current, size)) current += size def visualize(self): for block in self.blocks: print(block)

测试这个基础框架非常简单：

partitions = [300, 600, 350, 200, 750, 125] # 恐龙书CH09的示例分区 manager = MemoryManager(partitions) manager.visualize()

提示：在Jupyter Notebook中运行时可结合IPython.display实现动态可视化更新，这对观察算法执行过程特别有帮助。

2. 首次适应算法(First-Fit)实现与优化

First-fit算法的核心思想是顺序查找第一个足够大的空闲分区。让我们用Python实现这个看似简单但暗藏玄机的算法：

def first_fit(self, process_id, size): for i, block in enumerate(self.blocks): if not block.allocated and block.size >= size: # 找到合适分区 remaining = block.size - size if remaining > 0: # 产生碎片 new_block = MemoryBlock(block.start+size, remaining) self.blocks.insert(i+1, new_block) block.size = size block.allocated = True block.process_id = process_id return True return False # 分配失败

这个基础实现已经可以处理恐龙书CH09的9.6题目案例。让我们模拟书中的分配序列：

processes = [(115, 'P1'), (500, 'P2'), (358, 'P3'), (200, 'P4'), (375, 'P5')] manager = MemoryManager([300, 600, 350, 200, 750, 125]) for size, pid in processes: manager.first_fit(pid, size) print(f"\n分配 {pid}({size}KB) 后内存状态:") manager.visualize()

关键观察点：

• 分配115KB时，选择的是第一个300KB分区而非最合适的125KB
• 后续的500KB只能放入600KB分区，造成100KB外部碎片
• 最终内存中散布着多个小碎片(185KB,100KB,150KB等)

注意：实际系统中会设置最小分配单元，比如4KB，小于此值的请求也会分配整个单元，这就产生了内部碎片。

3. 最佳适应(Best-Fit)算法深度剖析

Best-fit算法试图最小化剩余碎片，其实现需要遍历所有空闲分区：

def best_fit(self, process_id, size): best_index = -1 min_remain = float('inf') for i, block in enumerate(self.blocks): if not block.allocated and block.size >= size: remain = block.size - size if remain < min_remain: min_remain = remain best_index = i if best_index != -1: block = self.blocks[best_index] if min_remain > 0: new_block = MemoryBlock(block.start+size, min_remain) self.blocks.insert(best_index+1, new_block) block.size = size block.allocated = True block.process_id = process_id return True return False

用相同的数据集测试best-fit表现：

manager = MemoryManager([300, 600, 350, 200, 750, 125]) for size, pid in processes: manager.best_fit(pid, size) print(f"\nBest-fit分配 {pid}({size}KB):") manager.visualize()

算法特性分析：

表格显示best-fit虽然减少了每次分配的浪费，但会导致内存中散布许多难以利用的小碎片。这也是为什么现代操作系统往往采用更复杂的分配策略。

4. 最差适应(Worst-Fit)算法实践与对比

Worst-fit算法的设计理念与best-fit相反——总是选择最大的可用分区：

def worst_fit(self, process_id, size): worst_index = -1 max_remain = -1 for i, block in enumerate(self.blocks): if not block.allocated and block.size >= size: remain = block.size - size if remain > max_remain: max_remain = remain worst_index = i if worst_index != -1: block = self.blocks[worst_index] if max_remain > 0: new_block = MemoryBlock(block.start+size, max_remain) self.blocks.insert(worst_index+1, new_block) block.size = size block.allocated = True block.process_id = process_id return True return False

测试9.12题目中的更复杂场景：

partitions = [100, 170, 40, 205, 300, 185] processes = [(200, 'P1'), (15, 'P2'), (185, 'P3'), (75, 'P4'), (175, 'P5'), (80, 'P6')] manager = MemoryManager(partitions) for size, pid in processes: if not manager.worst_fit(pid, size): print(f"!! {pid}({size}KB) 分配失败") manager.visualize()

运行结果分析：

• 175KB的进程P5分配失败，因为此时最大空闲块只有170KB
• 与best-fit相比，worst-fit留下的空闲块大小更均匀
• 在长期运行的系统上，worst-fit通常表现不如first-fit

5. 高级话题：碎片整理与算法优化

理解了基础算法后，我们可以探讨更高级的内存管理技术。以下是一个简单的碎片统计方法：

def fragmentation_report(self): external = sum(block.size for block in self.blocks if not block.allocated and block.size < 10) # 小于10KB视为碎片 internal = sum(block.size - block.process.size for block in self.blocks if block.allocated) print(f"外部碎片: {external}KB, 内部碎片: {internal}KB")

三种算法的碎片对比（基于9.6题目数据）：

实际系统中还会采用以下优化策略：

• 伙伴系统：通过2^n大小的块减少外部碎片
• slab分配：针对常用小对象优化
• 压缩技术：动态移动内存内容消除外部碎片

# 简单的内存压缩实现示例 def compact(self): free_blocks = [b for b in self.blocks if not b.allocated] allocated_blocks = [b for b in self.blocks if b.allocated] # 重新计算地址 current = 0 for block in allocated_blocks: block.start = current current += block.size # 合并空闲块 if free_blocks: total_free = sum(b.size for b in free_blocks) self.blocks = allocated_blocks + [MemoryBlock(current, total_free)]

通过这个Python模拟项目，我们不仅验证了恐龙书上的理论结果，更重要的是理解了算法背后的设计取舍。下次当你看到malloc/free的调用时，就能想象到底层内存管理器正在执行的复杂决策过程。