1. 实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

2. 实验内容

2.1 实验说明

• 用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程 alloc() 和回收过程 free()。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。

• 假设初始状态下，可用的内存空间为 640KB，并有下列的请求序列：

  1. 作业 1 申请 130KB
  2. 作业 2 申请 60KB
  3. 作业 3 申请 100KB
  4. 作业 2 释放 60KB
  5. 作业 4 申请 200KB
  6. 作业 3 释放 100KB
  7. 作业 1 释放 130KB
  8. 作业 5 申请 140KB
  9. 作业 6 申请 60KB
  10. 作业 7 申请 50KB
  11. 作业 6 释放 60KB

请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。

2.2 程序清单

• 最佳适应算法：

首先，定义一个 p 指针，让 p 指针遍历空闲分区链表，当找到第一个满足进程请求空间大小的空闲区时，记录此位置，并且保存请求大小与空闲分区实际大小的差值记为 a，然后让 p 指针继续遍历空闲分区链表，每当满足请求内存大小小于空闲区大小时，就记录两者的差值并且记录为 b，比较 a 与 b 的大小关系，当 a > b 时，将 b 的值赋予 a，并且修改记录位置为此空闲区的位置。若 a <= b,不做操作。继续遍历链表，重复上面的操作，直到 p->next 指向 null 为止。

• 首次适应算法：

首次适应算法比较简单，只要找到满足条件的空闲区，就将此区的空间分配给进程。首先，用 p 指针遍历链表，找到第一个空间大于或者等于请求大小的位置，将此空间分配给进程，当此空闲区大小大于请求空间大小时，将空闲区分为两部分，一部分分配给进程，另一部分为空闲区，它的大小为之前空闲区大小减去分配给进程的空间大小。

• 内存回收算法：

内存回收时，回收分区与空闲分区有四种关系。第一种情况为回收分区 r 上邻一个空闲分区，此时应合并为一个连续的空闲区，其始址为 r 上邻分区的首地址，大小为两者大小之和。第二种情况为回收分区 r 与下邻空闲分区相邻，合并后仍为空闲区，该空闲区的始址为回收分区 r 的地址，大小为两者之和。第三种情况为回收分区 r 与上下空闲分区都相邻，此时将这三个区域合并，始址为 r 上邻区域的地址，大小为三个分区大小之和。第四种情况为回收分区 r 的上下区域都不是空闲区域，此时建立一个新的空闲分区，并加入到空闲分区链中。

实验所用的测试数据如下表所示：

作业序号	作业 ID	操作(0->申请 1->释放)	内存大小
1	1	50	130
2	2	30	60
3	3	25	100
4	2	20	60
5	4	15	200
6	3	10	100
7	1	5	130
8	5	20	140
9	6	15	60
10	7	10	50
11	6	5	60

实验代码：

▶

Code

/*
 * 内存分区分配与回收模拟程序
 *
 * 从数据文件读入一批内存请求, 每行格式: 序号 作业号 操作 内存大小
 * 操作 0 表示申请, 1 表示释放; 内存大小以 KB 为单位, 释放时该列可忽略
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MEMORY_SIZE 640                 // 可用内存总大小
#define MAX_PART_NUM (MEMORY_SIZE + 2)  // 分区表容量上限
#define MAX_REQ_NUM 50                  // 请求序列的最大长度
#define FREE_ID -1                      // 空闲分区标记
#define NO_FIT -1                       // 没有可分配空闲分区时的返回值

// 请求操作类型
#define OP_ALLOC 0  // 申请内存
#define OP_FREE 1   // 释放内存

/* 单个内存分区信息 */
typedef struct partition_s {
    int id;    // 分区号, FREE_ID 表示空闲分区, 否则表示所属作业号
    int base;  // 分区起始地址
    int size;  // 分区大小
} partition_t;

/* 单个内存请求 */
typedef struct request_s {
    int no;    // 序号
    int job;   // 作业号
    int op;    // 操作: OP_ALLOC 申请 / OP_FREE 释放
    int size;  // 内存大小
} request_t;

typedef int (*select_policy)(const partition_t parts[], int count, int need);

// 从文件读入的请求表, 作为只读基准数据, 供各算法使用
request_t g_reqs[MAX_REQ_NUM];
int       g_req_count = 0;

/**
 * @brief 打印读入的原始请求数据
 */
static void print_request_data()
{
    printf("原始请求数据\r\n");
    printf("---------------------------------------------------------------------\r\n");
    printf("\t序号\t作业号\t操作\t\t内存大小\r\n");
    for (int i = 0; i < g_req_count; i++) {
        printf("\t%-8d\t%-8d\t%s\t\t%-8d\r\n", g_reqs[i].no, g_reqs[i].job, g_reqs[i].op == OP_ALLOC ? "申请" : "释放",
               g_reqs[i].size);
    }
}

/**
 * @brief 从数据文件读入全部请求
 *
 * @return true  读取成功
 * @return false 读取失败或文件中没有有效数据
 */
static bool read_request_data()
{
    char fname[128];
    printf("请输入作业数据文件名: ");
    scanf("%s", fname);

    FILE *fp = fopen(fname, "r");
    if (fp == NULL) {
        printf("打开文件 %s 失败\r\n", fname);
        return false;
    }

    // 逐行读取直到文件结束或达到上限, 每行: 序号 作业号 操作 内存大小
    int no, job, op, size;
    g_req_count = 0;
    while (g_req_count < MAX_REQ_NUM && fscanf(fp, "%d %d %d %d", &no, &job, &op, &size) == 4) {
        g_reqs[g_req_count].no   = no;
        g_reqs[g_req_count].job  = job;
        g_reqs[g_req_count].op   = op;
        g_reqs[g_req_count].size = size;
        g_req_count++;
    }
    fclose(fp);

    if (g_req_count == 0) {
        printf("文件中没有有效的请求数据\r\n");
        return false;
    }
    return true;
}

/**
 * @brief 打印一张内存分区表
 *
 * @param parts 分区表
 * @param count 分区个数
 */
static void show_memory(const partition_t parts[], int count)
{
    printf("\r\n内存分配状况\r\n");
    printf("---------------------------------------------------------------------\r\n");
    printf("\t分区号\t起始地址\t分区大小\t状态\r\n");
    for (int i = 0; i < count; i++) {
        const partition_t *p = &parts[i];
        char               id_str[16];
        if (p->id == FREE_ID) {
            snprintf(id_str, sizeof(id_str), "FREE");
        } else {
            snprintf(id_str, sizeof(id_str), "%d", p->id);
        }
        printf("\t%-6s\t%-8d\t%-8d\t%s\r\n", id_str, p->base, p->size, p->id == FREE_ID ? "空闲" : "已分配");
    }
    printf("---------------------------------------------------------------------\r\n");
}

/**
 * @brief FF 算法: 按地址顺序选择第一个能满足需求的空闲分区
 *
 * @param parts 分区表
 * @param count 分区个数
 * @param need  所需内存大小
 * @return int 选中分区下标, 没有合适分区时返回 NO_FIT
 */
static int pick_first_fit(const partition_t parts[], int count, int need)
{
    for (int i = 0; i < count; i++) {
        if (parts[i].id == FREE_ID && parts[i].size >= need) {
            return i;
        }
    }
    return NO_FIT;
}

/**
 * @brief BF 算法: 在所有空闲分区中选择大小与需求最接近的一个
 * 即选择满足 size >= need 的最小分区, 因此要求越大的分区越不会被选中
 *
 * @param parts 分区表
 * @param count 分区个数
 * @param need  所需内存大小
 * @return int 选中分区下标, 没有合适分区时返回 NO_FIT
 */
static int pick_best_fit(const partition_t parts[], int count, int need)
{
    int best = NO_FIT;
    for (int i = 0; i < count; i++) {
        if (parts[i].id != FREE_ID || parts[i].size < need) {
            continue;
        }
        if (best == NO_FIT || parts[i].size < parts[best].size) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief 按给定分配策略为作业分配一块内存
 * 先由策略选出一个空闲分区: 若其大小恰好等于需求则直接占用;
 * 若大于需求, 则将右侧剩余部分拆成一个新的空闲分区插在其后.
 *
 * @param parts  分区表
 * @param count  分区个数指针, 拆分时会修改
 * @param job_id 作业号, 不能为 FREE_ID
 * @param need   所需内存大小, 必须大于 0
 * @param pick   空闲分区选择策略
 * @return true  分配成功
 * @return false 分配失败
 */
static bool alloc_memory(partition_t parts[], int *count, int job_id, int need, select_policy pick)
{
    if (job_id == FREE_ID || need <= 0) {
        return false;
    }

    int loc = pick(parts, *count, need);
    if (loc == NO_FIT) {
        return false;
    }

    partition_t *p = &parts[loc];
    // 空闲分区恰好能容纳需求, 直接占用整个分区
    if (p->size == need) {
        p->id = job_id;
        return true;
    }

    // 空闲分区大于需求: 整体后移, 把多余部分建成一个新空闲分区
    for (int i = *count; i > loc + 1; i--) {
        parts[i] = parts[i - 1];
    }
    parts[loc + 1].id   = FREE_ID;
    parts[loc + 1].base = p->base + need;
    parts[loc + 1].size = p->size - need;
    p->id               = job_id;
    p->size             = need;
    (*count)++;
    return true;
}

/**
 * @brief 释放指定作业占用的内存分区, 并合并相邻的空闲分区
 * 先找到作业所在分区并标记为空闲, 若下一个分区空闲则与之合并,
 * 若上一个分区空闲则再向上合并, 从而让空闲分区始终尽可能大.
 *
 * @param parts  分区表
 * @param count  分区个数(指针, 合并时会修改)
 * @param job_id 要释放的作业号
 * @return true  释放成功
 * @return false 分区表中不存在该作业号
 */
static bool recycle_memory(partition_t parts[], int *count, int job_id)
{
    int loc = NO_FIT;
    for (int i = 0; i < *count; i++) {
        if (parts[i].id == job_id) {
            loc = i;
            break;
        }
    }
    if (loc == NO_FIT) {
        return false;
    }
    parts[loc].id = FREE_ID;

    // 与下一个空闲分区合并
    if (loc + 1 < *count && parts[loc + 1].id == FREE_ID) {
        parts[loc].size += parts[loc + 1].size;
        for (int i = loc + 1; i < *count - 1; i++) {
            parts[i] = parts[i + 1];
        }
        (*count)--;
    }
    // 与上一个空闲分区合并
    if (loc > 0 && parts[loc - 1].id == FREE_ID) {
        parts[loc - 1].size += parts[loc].size;
        for (int i = loc; i < *count - 1; i++) {
            parts[i] = parts[i + 1];
        }
        (*count)--;
    }
    return true;
}

/**
 * @brief 用指定分配策略在一张全新的分区表上顺序执行整条请求序列
 *
 * @param algo_name 算法名称
 * @param pick      空闲分区选择策略
 */
static void run_simulation(const char *algo_name, select_policy pick)
{
    partition_t parts[MAX_PART_NUM];
    int         count = 1;
    parts[0].id       = FREE_ID;
    parts[0].base     = 0;
    parts[0].size     = MEMORY_SIZE;

    printf("\r\n%s 算法执行过程\r\n", algo_name);
    printf("---------------------------------------------------------------------\r\n");
    printf("\t序号\t作业号\t操作\t\t内存大小\t结果\r\n");
    for (int i = 0; i < g_req_count; i++) {
        const request_t *r = &g_reqs[i];
        printf("\t%-8d\t%-8d\t%s\t\t%-8d\t", r->no, r->job, r->op == OP_ALLOC ? "申请" : "释放", r->size);

        if (r->op == OP_ALLOC) {
            if (alloc_memory(parts, &count, r->job, r->size, pick)) {
                printf("分配成功\r\n");
            } else {
                printf("分配失败\r\n");
            }
        } else {
            if (recycle_memory(parts, &count, r->job)) {
                printf("释放成功\r\n");
            } else {
                printf("释放失败\r\n");
            }
        }
        show_memory(parts, count);
    }
}

int main()
{
    // 读取一次请求数据, 供所有算法使用
    if (!read_request_data()) {
        return EXIT_FAILURE;
    }
    print_request_data();

    // 分别在各自独立的分区表副本上运行两种分配算法
    run_simulation("FF 首次适应", pick_first_fit);
    run_simulation("BF 最佳适应", pick_best_fit);
    return EXIT_SUCCESS;
}

同目录下创建 job.txt，用于储存作业数据，内容如下：

1 1 0 130
2 2 0 60
3 3 0 100
4 2 1 60
5 4 0 200
6 3 1 100
7 1 1 130
8 5 0 140
9 6 0 60
10 7 0 50
11 6 1 60

3. 分析与思考

存储管理是指对外部存储资源和内存进行管理，可以完成存储分配、存储共享、存储保护、存储扩充、地址映射等重要功能，对操作系统的性能有很重要的影响。在计算机科学中，存储管理是操作系统的一个重要组成部分，它负责管理计算机内存和外部存储器的使用。