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

## 一、实验内容

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

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

## 二、实验设计

### 2.1 数据结构

```cpp
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）

```cpp
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）

```cpp
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）

```cpp
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 编译与运行

```bash
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 测试命令

```bash
# 编译
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