用Python模拟四种动态分区分配算法（附完整代码和可视化结果）

用Python模拟四种动态分区分配算法附完整代码和可视化结果在计算机操作系统的内存管理中动态分区分配算法是解决进程内存需求的核心机制。不同于固定分区分配的僵化动态方式能根据进程实际需求灵活划分内存空间但这也带来了碎片化、分配效率等新挑战。本文将带您用Python从零实现四种经典算法——首次适应(FF)、最佳适应(BF)、最坏适应(WF)和邻接适应(NF)并通过动态可视化直观比较它们的性能差异。无论您是准备操作系统考试的学生还是需要优化资源调度的开发者这种代码驱动的学习方式都能让抽象算法变得触手可及。1. 动态分区分配基础模型内存分配算法的本质是解决如何从空闲区域中选择合适区块的问题。我们首先构建一个基础模拟环境class MemoryBlock: def __init__(self, start, size, statusfree): self.start start # 起始地址 self.size size # 区块大小 self.status status # free/allocated self.process_id None class MemoryManager: def __init__(self, total_memory): self.blocks [MemoryBlock(0, total_memory)] self.total_memory total_memory self.algorithm FF # 默认首次适应算法关键参数说明区块状态每个内存块标记为free或allocated进程绑定分配时记录占用该区块的进程ID算法切换通过algorithm参数指定当前使用的分配策略提示在实际系统中内存分配信息通常以链表或位图形式存储。我们的简化模型使用列表结构便于算法演示。2. 四大算法实现与对比2.1 首次适应算法(First Fit)FF算法从内存低地址开始搜索选择第一个满足大小要求的空闲区块def first_fit(self, process_id, size): for i, block in enumerate(self.blocks): if block.status free and block.size size: # 分割剩余空间 remaining block.size - size if remaining 0: new_block MemoryBlock(block.start size, remaining) self.blocks.insert(i1, new_block) block.size size block.status allocated block.process_id process_id return True return False特点分析优点实现简单保留高地址大区块缺点低地址易产生碎片时间复杂度O(n)需要线性扫描2.2 最佳适应算法(Best Fit)BF算法总是选择能满足需求的最小空闲区块def best_fit(self, process_id, size): best_index -1 min_remain float(inf) for i, block in enumerate(self.blocks): if block.status free 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] # 分割逻辑与FF相同... return True return False内存碎片对比表算法类型内部碎片外部碎片大区块保留首次适应中等较多较好最佳适应较少最多较差2.3 最坏适应算法(Worst Fit)WF算法反其道而行总是选择最大的可用空闲区块def worst_fit(self, process_id, size): worst_index -1 max_size -1 for i, block in enumerate(self.blocks): if block.status free and block.size size: if block.size max_size: max_size block.size worst_index i # 分配逻辑类似...2.4 邻接适应算法(Next Fit)NF算法改进自FF从上一次分配位置继续搜索def next_fit(self, process_id, size): if not hasattr(self, last_index): self.last_index 0 start_index self.last_index for i in range(len(self.blocks)): idx (start_index i) % len(self.blocks) block self.blocks[idx] # 检查与分配逻辑... self.last_index idx3. 可视化内存状态使用Matplotlib动态展示内存变化def visualize_memory(self): fig, ax plt.subplots(figsize(10, 2)) colors {free: lightgreen, allocated: salmon} for block in self.blocks: ax.barh(0, block.size, leftblock.start, height0.5, colorcolors[block.status]) ax.text(block.start block.size/2, 0, f{block.size}K, hacenter, vacenter) ax.set_yticks([]) ax.set_xlim(0, self.total_memory) plt.show()典型运行结果示例[FF] 分配后内存布局 ▓▓▓▓░░░░▓▓▓▓░░░░▓▓▓▓ (▓已分配, ░空闲) [BF] 相同请求序列 ▓▓░▓▓░░░▓▓▓▓░░░▓▓▓▓4. 完整测试案例模拟进程请求序列并比较算法表现def test_scenario(): mem MemoryManager(1024) # 1GB内存 processes [ (P1, 128), (P2, 256), (P3, 64), (P4, 512), (P5, 128), (P6, 256) ] # 测试不同算法 for algo in [FF, BF, WF, NF]: mem.algorithm algo print(f\n {algo}算法测试 ) for pid, size in processes: mem.allocate(pid, size) mem.visualize_memory() # 释放部分进程 mem.deallocate(P2) mem.deallocate(P4)关键观察指标分配成功率能否满足所有请求内存利用率已使用内存占比碎片化程度无法利用的小区块数量在实现过程中发现NF算法在长期运行后容易出现高地址碎片而BF算法虽然能提高初期利用率但后期可能无法满足大进程请求。FF算法在多数场景下表现均衡这也是许多实际系统采用它的原因。