You need to enable JavaScript to run this app. Python实现操作系统Best Fit内存分配:blockSize异常排查及优化咨询
优惠活动
大模型
产品
解决方案
定价
更多

Python实现操作系统Best Fit内存分配:blockSize异常排查及优化咨询

问题根因与修复方案

核心引用错误的原因

Python中列表属于可变对象,直接执行memorySize = blockSize仅为变量绑定同一块内存地址,不会创建独立的内存副本。后续对memorySize的扣减操作,本质上直接修改了blockSize指向的原始数组,最终导致三类异常:

  1. 前后两次打印的blockSize不一致,初始值被持续篡改
  2. 最终计算内部碎片时,用的是被修改后的剩余内存值,而非内存块的初始规格,计算结果完全不符合操作系统对内部碎片的定义
  3. 更隐蔽的是,当作业未找到适配块、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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.27 08:36:03