Operating-System/Experiment/OS_exp/experiment_03/实验三_报告.md

实验三 存储管理——动态不等长存储资源分配算法

一、实验内容

理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。

1. 分析 UNIX 最先适应（FF）map 结构、malloc、mfree
2. 实现最佳适应（BF）、最坏适应（WF）

二、实验设计

2.1 数据结构

struct map {
    int m_addr;   // 空闲块起始地址
    int m_size;    // 空闲块大小
};
struct map map[MAPSIZE];  // 空闲分区表

空闲分区表按地址顺序排列，最后一个条目 m_size = 0 表示表尾。

2.2 函数设计

函数	功能
init()	初始化存储区，建立第一个空闲块
show_map()	显示当前空闲分区表
BF_malloc()	最佳适应算法分配
WF_malloc()	最坏适应算法分配
mfree()	释放存储区，合并相邻空闲块

2.3 调用关系

main()
├── init() 初始化空闲分区表
├── 输入算法选择 (b=BF, w=WF)
└── 循环菜单
    ├── 1: BF_malloc() / WF_malloc() 分配
    ├── 2: mfree() 释放
    └── 0: 退出

三、编码实现

3.1 最佳适应算法（BF）

int BF_malloc(struct map *mp, int size) {
    register int a, s;
    register struct map *bp, *bpp;

    for (bp = mp; bp->m_size; bp++) {
        if (bp->m_size >= size) {
            a = bp->m_addr;
            s = bp->m_size;
            // 遍历寻找最小且 >= size 的空闲块
            for (bpp = bp; bpp->m_size; bpp++) {
                if (bpp->m_size >= size && bpp->m_size < s) {
                    a = bpp->m_addr;
                    s = bpp->m_size;
                    bp = bpp;
                }
            }
            // 分配：地址后移，大小减少
            bp->m_addr += size;
            if ((bp->m_size -= size) == 0) {
                // 大小为0，删除该条目
                do {
                    bp++;
                    (bp-1)->m_addr = bp->m_addr;
                } while (((bp-1)->m_size = bp->m_size));
            }
            return a;
        }
    }
    return -1;  // 分配失败
}

关键点：

• 两次循环：外层找候选，内层找最小
• 分配后如果大小为0，需要压缩表

3.2 最坏适应算法（WF）

int WF_malloc(struct map *mp, int size) {
    register int a, s;
    register struct map *bp, *bpp;

    for (bp = mp; bp->m_size; bp++) {
        if (bp->m_size >= size) {
            a = bp->m_addr;
            s = bp->m_size;
            // 遍历寻找最大且 >= size 的空闲块
            for (bpp = bp; bpp->m_size; bpp++) {
                if (bpp->m_size > s) {
                    a = bpp->m_addr;
                    s = bpp->m_size;
                    bp = bpp;
                }
            }
            bp->m_addr += size;
            if ((bp->m_size -= size) == 0) {
                do {
                    bp++;
                    (bp-1)->m_addr = bp->m_addr;
                } while (((bp-1)->m_size = bp->m_size));
            }
            return a;
        }
    }
    return -1;
}

与BF的区别：

• 内层循环条件是 bpp->m_size > s（找最大）
• 选择剩余空间最大的空闲块

3.3 释放与合并（mfree）

void mfree(struct map *mp, int aa, int size) {
    register struct map *bp;
    register int t, a;
    a = aa;

    // 找到插入位置（按地址顺序）
    for (bp = mp; bp->m_addr <= a && bp->m_size != 0; bp++);

    // 情况1：与前一个块合并
    if (bp > mp && (bp-1)->m_addr + (bp-1)->m_size == a) {
        (bp-1)->m_size += size;
        // 情况1.1：再与后一个块合并
        if (a + size == bp->m_addr) {
            (bp-1)->m_size += bp->m_size;
            while (bp->m_size) {
                bp++;
                (bp-1)->m_addr = bp->m_addr;
                (bp-1)->m_size = bp->m_size;
            }
        }
    }
    // 情况2：与后一个块合并
    else if (a + size == bp->m_addr && bp->m_size) {
        bp->m_addr -= size;
        bp->m_size += size;
    }
    // 情况3：插入为新块
    else if (size) {
        do {
            t = bp->m_addr;
            bp->m_addr = a;
            a = t;
            t = bp->m_size;
            bp->m_size = size;
            bp++;
        } while ((size = t));
    }
}

3.4 编译与运行

g++ exp03_source.cpp -o memory
./memory

运行示例：

Please input starting addr and total size: 0,1000
Please input, b for BF, w for WF: b
Current memory map...
Address      Size
<0           1000>

Please input, 1 for request, 2 for release, 0 for exit: 1
Please input size: 200
alloc memory at address:0, size:200

四、实验结果

4.0 测试命令

# 编译
g++ exp03_source.cpp -o memory

# 运行（按提示输入）
./memory

# 输入内容：
0,1000
b
1
200
1
100
2
0,300
1
150
0

4.1 最佳适应（BF）示例

初始: [0,1000]

分配300: [300,700]  (分配地址0)
分配100: [400,600]  (分配地址300，选最小满足的)
分配200: [600,400]  (分配地址400)
释放[0,300]: [0,300][600,400]  (合并后)
分配150: [0,150][600,400]  (选最小满足的300)

特点： 分配后剩余的空闲块较大，但会产生很多小碎片

4.2 最坏适应（WF）示例

初始: [0,1000]

分配300: [300,700]  (分配地址0)
分配100: [400,600]  (分配地址700，选最大)
分配200: [600,400]  (分配地址400)
释放[0,300]: [0,300][600,400]
分配150: [0,150][300,150][600,400]  (从最大600分配)

特点： 尽量保持大空闲块，但可能导致大请求无法满足

4.3 释放合并示例

释放地址150，大小150:
- 与[0,150]相邻 → 合并为[0,300]
- 与[300,150]相邻 → 合并为[0,450]

五、实验结果思考与体会

5.1 三种算法对比

算法	分配策略	优点	缺点
FF	选第一个满足的	简单快速	容易产生碎片
BF	选最小满足的	碎片最小	需遍历全部
WF	选最大满足的	大块优先	大请求易失败

5.2 思考问题解答

问题1：按大小排序优化

可以维护一个按大小排序的空闲块链表，分配时直接取第一个，释放时插入对应位置。这样 BF 可以 O(n) 优化。

问题2：伙伴堆（Buddy Heap）

伙伴堆是一种特殊的动态存储算法：

• 每个空闲块大小为2的幂
• 分配时找到最小的2^k >= size
• 释放时与"伙伴"合并（地址相临且大小相同）
• 优点：合并简单，缺点：内碎片严重

5.3 实验体会

1. 存储管理核心问题：如何平衡分配速度和碎片大小

2. 数据结构选择：空闲分区表简单但查询效率低，可考虑使用空闲分区链表或位图

3. 合并时机：释放时立即合并还是延迟合并各有利弊

4. UNIX 风格设计：使用 map 结构体模拟内核存储管理，理解了操作系统底层存储管理机制

5. 算法选择：根据实际应用场景选择合适的分配算法

   • 实时系统需要快速响应 → FF
   • 内存充足追求利用率 → BF
   • 需要大块内存 → WF