Python实现操作系统Best Fit内存分配:blockSize异常排查及优化咨询
问题根因与修复方案
核心引用错误的原因
Python中列表属于可变对象,直接执行memorySize = blockSize仅为变量绑定同一块内存地址,不会创建独立的内存副本。后续对memorySize的扣减操作,本质上直接修改了blockSize指向的原始数组,最终导致三类异常:
- 前后两次打印的
blockSize不一致,初始值被持续篡改 - 最终计算内部碎片时,用的是被修改后的剩余内存值,而非内存块的初始规格,计算结果完全不符合操作系统对内部碎片的定义
- 更隐蔽的是,当作业未找到适配块、
allocation[k]为-1时,Python的负索引特性会让代码直接取数组最后一个元素计算,不会触发索引越界报错,但输出的碎片值完全错乱。
修复方法
只需将数组赋值逻辑改为生成独立副本即可,可选三种等效写法:
memorySize = blockSize.copy()memorySize = list(blockSize)memorySize = blockSize[:]
(因为列表内存储的都是整数这类不可变值,浅拷贝完全满足需求,无需深拷贝)
可落地算法改进建议
- 增加分配失败的容错逻辑:原代码未处理作业找不到适配内存块的场景,需增加判断分支,对未分配的作业输出明确提示,避免负索引导致的错误计算。
- 降低查找最优块的时间复杂度:原实现每次处理作业都需要全量遍历所有内存块,整体时间复杂度为O(m*n)(m为内存块数,n为作业数)。可将空闲内存块按大小预排序后,通过二分查找定位第一个满足作业大小要求的最小块,时间复杂度可优化到O(n log m),适合内存块规模较大的场景。
- 补充碎片统计逻辑:原代码仅计算内部碎片,可额外统计所有空闲小内存块的总大小,直观体现Best Fit容易产生大量细碎无法利用的外部碎片的特性,方便对比不同分配算法的优劣。
- 支持动态内存回收:原实现为静态固定内存块分配逻辑,适配实际操作系统场景时,可给每个内存块增加分配状态标记,作业执行结束后释放对应块的内存,相邻空闲块可做合并处理(类似伙伴系统逻辑),进一步减少外部碎片。
- 明确同尺寸块的选择规则:当多个内存块大小刚好都适配作业需求时,原逻辑默认选遍历到的第一个块,可补充规则(如优先选择地址更高的块),避免频繁修改低地址区域的可用内存,降低后续分配的寻址开销。
修复后可运行的完整代码
def bestFit(blockSize, m, jobSize, n): allocation = [-1] * n # 解耦:生成独立的动态内存大小副本,不修改原始初始块数组 memorySize = blockSize.copy() print("初始内存块规格:", blockSize) for i in range(n): bestId = -1 for j in range(m): if memorySize[j] >= jobSize[i]: if bestId == -1: bestId = j # 选择当前可用的最小适配块 elif memorySize[bestId] > memorySize[j]: bestId = j if bestId != -1: allocation[i] = bestId memorySize[bestId] -= jobSize[i] print("分配后剩余内存规格:", memorySize) print("\n作业号 | 作业大小 | 分配的初始内存块 | 内部碎片") for k in range(n): if allocation[k] == -1: print(f" {k} {jobSize[k]} 未分配 -") else: init_block_size = blockSize[allocation[k]] internal_fragment = init_block_size - jobSize[k] print(f" {k} {jobSize[k]} {init_block_size} {internal_fragment}") # 测试用例 blockSize = [100, 500, 200, 300, 600] processSize = [212, 417, 112, 426] bestFit(blockSize, len(blockSize) , processSize, len(processSize))
运行上述代码可验证:初始
blockSize数组全程保持原始值,内部碎片计算逻辑符合操作系统定义,输出结果与标准Best Fit算法的预期完全一致。
内容的提问来源于stack exchange,提问作者Neyney
相关产品推荐
相关产品推荐

