操作系统实验 实验3 存储器分配与回收

1.实验目的

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

2.实验要求

        用C语言实现首次适应算法的动态分区分配过程alloc()和回收过程free()。

一、实验内容：

1．实验内容

用C语言实现首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲区说明表；在进行内存分配时，系统优先使用空闲区低端的空间。

（1）相关知识及其分析

    当有一个新作业要求装入主存时，必须查空闲区说明表，从中找一个满足作业大小要求的低址空闲区。有时找到的空闲区可能大于作业需求量，这时应将该空闲区的低地址部分分配给请求作业，另一部分仍作为空闲区留在空闲区表中，以利于大作业的装入。

为了便于实现首次适应算法，在空闲区表中，按空闲区首址从低到高进行登记。为了保证快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。空闲说明表如表2所示。

        其分配/回收流程图参见本书第4章图4.7，4.8所示。

实验代码如下：

#include <stdio.h>
#include <iostream>
#define N 5
using namespace std;
// 定义一个结构体freearea，用于表示空闲区
// startaddress表示空闲区始址
// size表示空闲区大小
// state表示空闲区状态，0为空表目，1为可用空闲块
struct freearea {int startaddress;int size;int state;
};// 定义全局变量freeblock，是一个包含N个freearea结构体的数组
// 初始化freeblock数组，设置各个空闲区的起始地址、大小和状态
struct freearea freeblock[N] = { {20, 20, 1}, {80, 50, 1}, {150, 100, 1}, {300, 30, 0}, {600, 100, 1} };// 内存分配函数，applyarea为作业申请的内存量
// 使用首次适应算法，遍历空闲区表寻找合适的空闲区进行分配
int alloc(int applyarea) {int i;// 遍历空闲区表for (i = 0; i < N; i++) {// 如果当前空闲区状态为可用（state为1）且大小大于等于申请量if (freeblock[i].state == 1 && freeblock[i].size >= applyarea) {// 记录当前空闲区的起始地址int allocated_start = freeblock[i].startaddress;// 如果空闲区大小大于申请量，分割空闲区if (freeblock[i].size > applyarea) {// 调整剩余空闲区的起始地址freeblock[i].startaddress += applyarea;// 调整剩余空闲区的大小freeblock[i].size -= applyarea;}// 如果空闲区大小恰好等于申请量，将其状态设置为空表目（state为0）else {freeblock[i].state = 0;}// 返回分配的内存起始地址return allocated_start;}}// 没有找到合适的空闲区，返回-1表示分配失败return -1;
}// 内存回收函数，用于将释放的内存重新加入空闲区表
void setfree() {int s, l, i, j;// 提示用户输入释放区的开始地址printf("input free area startaddress:\n");// 读取用户输入的释放区的开始地址if (scanf("%d", &s) != 1) {// 处理输入错误的情况，这里简单提示输入错误并清空输入缓冲区printf("Invalid input for startaddress. Please enter a valid integer.\n");while (getchar() != '\n');return;}// 提示用户输入释放区的大小printf("input free area size:\n");if (scanf("%d", &l) != 1) {// 处理输入错误的情况，这里简单提示输入错误并清空输入缓冲区printf("Invalid input for size. Please enter a valid integer.\n");while (getchar() != '\n');return;}// 清除输入缓冲区中的换行符，避免影响后续输入while (getchar() != '\n');// 初始化插入位置为0int insert_pos = 0;// 找到释放区应插入的位置（按起始地址排序）while (insert_pos < N && freeblock[insert_pos].state == 1&& freeblock[insert_pos].startaddress < s)insert_pos++;// 检查前一个空闲区的索引，如果存在且状态为可用，则记录其索引，否则设为-1int prev_index = (insert_pos > 0 && freeblock[insert_pos - 1].state == 1)? insert_pos - 1 : -1;// 检查后一个空闲区的索引，如果存在且状态为可用，则记录其索引，否则设为-1int next_index = (insert_pos < N && freeblock[insert_pos].state == 1)? insert_pos : -1;// 如果前一个空闲区存在且其结束地址等于释放区的开始地址if (prev_index != -1 && freeblock[prev_index].startaddress + freeblock[prev_index].size == s) {// 合并到前一个空闲区，增加前一个空闲区的大小freeblock[prev_index].size += l;// 如果后一个空闲区存在且释放区的结束地址等于后一个空闲区的开始地址if (next_index != -1 && s + l == freeblock[next_index].startaddress) {// 合并三个空闲区（前一个+释放区+后一个）freeblock[prev_index].size += freeblock[next_index].size;// 将后一个空闲区标记为空表目freeblock[next_index].state = 0;}}// 如果后一个空闲区存在且释放区的结束地址等于后一个空闲区的开始地址else if (next_index != -1 && s + l == freeblock[next_index].startaddress) {// 合并到后一个空闲区，更新后一个空闲区的起始地址和大小freeblock[next_index].startaddress = s;freeblock[next_index].size += l;}// 如果不与任何空闲区相邻else {// 遍历空闲区表for (j = 0; j < N; j++) {// 找到一个空表目if (freeblock[j].state == 0) {// 将释放区信息填入空表目freeblock[j].startaddress = s;freeblock[j].size = l;// 将该表目状态设置为可用freeblock[j].state = 1;break;}}}
}// 调整空闲区表函数，使空闲区按起始地址升序排列，空表目放在最后面
void adjust() {int i, j, swapped;struct freearea middata;// 第一阶段：使用冒泡排序按起始地址升序排列可用空闲区for (i = 0; i < N - 1; i++) {// 标记本次循环是否进行了交换操作swapped = 0;// 遍历未排序的空闲区for (j = 0; j < N - i - 1; j++) {// 如果当前和下一个空闲区都为可用，且当前空闲区起始地址大于下一个空闲区起始地址if (freeblock[j].state == 1 && freeblock[j + 1].state == 1 &&freeblock[j].startaddress > freeblock[j + 1].startaddress) {// 交换两个空闲区的信息middata = freeblock[j];freeblock[j] = freeblock[j + 1];freeblock[j + 1] = middata;// 标记进行了交换操作swapped = 1;}}// 如果本次循环没有进行交换操作，说明已经有序，提前结束排序if (!swapped) break;}// 第二阶段：将空表目移到表的末尾for (i = 0; i < N - 1; i++) {// 遍历未排序的空闲区for (j = 0; j < N - i - 1; j++) {// 如果当前空闲区为空表目，下一个空闲区为可用if (freeblock[j].state == 0 && freeblock[j + 1].state == 1) {// 交换两个空闲区的信息middata = freeblock[j];freeblock[j] = freeblock[j + 1];freeblock[j + 1] = middata;}}}
}// 打印空闲区表函数，以表格形式输出当前所有空闲区的信息
void print() {int i;// 打印表格头部横线printf("        |---------------------------------------------------------------|\n");// 打印表格头部标题printf("        |        start        size        state        |\n");// 打印表格头部横线printf("        |---------------------------------------------------------------|\n");// 遍历空闲区表for (i = 0; i < N; i++) {// 打印每个空闲区的起始地址、大小和状态printf("        |         %3d         %3d         %3d          |\n",freeblock[i].startaddress, freeblock[i].size, freeblock[i].state);// 打印表格行分隔横线printf("        |---------------------------------------------------------------|\n");}
}// 主函数，程序的入口点
int main() {int applyarea, start;char end;// 提示用户是否有作业请求内存printf("\n is there any job request memory? y or n:");// 主循环：处理多个作业的内存请求while ((end = getchar()) == 'y' || end == 'Y') {// 输出提示信息，说明当前空闲内存情况printf("at first the free memory is this:\n");// 调整空闲区表，确保按序排列adjust();// 打印当前空闲区状态print();// 提示用户输入作业请求的内存大小printf("input request memory size:");// 读取用户输入的作业请求的内存大小if (scanf("%d", &applyarea) != 1) {// 处理输入错误的情况，这里简单提示输入错误并清空输入缓冲区printf("Invalid input for applyarea. Please enter a valid integer.\n");while (getchar() != '\n');continue;}// 调用内存分配函数，获取分配的内存起始地址start = alloc(applyarea);// 调整空闲区表adjust();// 输出提示信息，说明分配后的空闲内存情况printf("after allocation, the free memory is this:\n");// 打印分配后的空闲区状态print();// 如果分配失败（返回值为-1）if (start == -1)// 输出提示信息，说明没有合适的内存printf("there is no fit memory, please wait\n");else {// 输出作业的内存起始地址printf("job's memory start address is:%d\n", start);// 输出作业的大小printf("job size is:%d\n", applyarea);// 输出提示信息，说明作业正在运行printf("job is running.\n");// 输出提示信息，说明作业已终止printf("job is terminated.\n");// 调用内存回收函数setfree();// 调整空闲区表adjust();// 输出提示信息，说明内存回收后的空闲内存情况printf("after memory recovery, the free memory is this:\n");// 打印回收后的空闲区状态print();}// 提示用户是否有其他作业等待printf("is there any job that is waiting? y or n:");}// 程序正常结束，返回0return 0;
}

二、实验过程及结果记录

情况一：成功分配内存且空闲区大小大于申请量

初始空闲区状态如输出所示，请求 30 大小的内存，从起始地址 80 的空闲区分配，该空闲区大小为 50 大于申请量，分割后剩余大小为 20 。

作业运行并终止后，输入释放区地址 80 和大小 30 ，内存回收后空闲区恢复初始状态。

情况二：成功分配内存且空闲区大小等于申请量

请求 20 大小的内存，从起始地址 20 的空闲区分配，该空闲区大小等于申请量，分配后该空闲区状态设为 0 。

作业运行并终止后，用户输入释放区地址 20 和大小 20 ，内存回收后空闲区恢复初始状态。

情况三：分配内存失败

修改部分：

        修改代码在 adjust 函数中，使用冒泡排序将空闲区按起始地址升序排列，并将空表目移到表的末尾。代码中使用 swapped 标记是否进行了交换操作，提前结束排序以提高效率。而原代码也进行了类似的排序和移动空表目操作，但没有使用 swapped 标记提前结束排序。

原代码：

	void adjust(){int i,j;struct freearea middata;for(i=0;i<N;i++)		/*将空闲区按始地址顺序在表中排列*/for(j=0;j<N;j++)if(freeblock[j].startaddress>freeblock[j+1].startaddress){middata.startaddress=freeblock[j].startaddress;middata.size=freeblock[j].size;middata.state=freeblock[j].state;freeblock[j].startaddress=freeblock[j+1].startaddress;freeblock[j].size=freeblock[j+1].size;freeblock[j].state=freeblock[j+1].state;freeblock[j+1].startaddress=middata.startaddress;freeblock[j+1].size=middata.size;freeblock[j+1].state=middata.state;}for(i=0;i<N;i++)	/*将空表目放在表后面*/for(j=0;j<N;j++)if(freeblock[j].state==0&&freeblock[j+1].state==1){middata.startaddress=freeblock[j].startaddress;middata.size=freeblock[j].size;middata.state=freeblock[j].state;freeblock[j].startaddress=freeblock[j+1].startaddress;freeblock[j].size=freeblock[j+1].size;freeblock[j].state=freeblock[j+1].state;freeblock[j+1].startaddress=middata.startaddress;freeblock[j+1].size=middata.size;freeblock[j+1].state=middata.state;}}

修复代码：

    // 第一阶段：使用冒泡排序按起始地址升序排列可用空闲区for (i = 0; i < N - 1; i++) {// 标记本次循环是否进行了交换操作swapped = 0;// 遍历未排序的空闲区for (j = 0; j < N - i - 1; j++) {// 如果当前和下一个空闲区都为可用，且当前空闲区起始地址大于下一个空闲区起始地址if (freeblock[j].state == 1 && freeblock[j + 1].state == 1 &&freeblock[j].startaddress > freeblock[j + 1].startaddress) {// 交换两个空闲区的信息middata = freeblock[j];freeblock[j] = freeblock[j + 1];freeblock[j + 1] = middata;// 标记进行了交换操作swapped = 1;}}// 如果本次循环没有进行交换操作，说明已经有序，提前结束排序if (!swapped) break;}
// 调整空闲区表函数，使空闲区按起始地址升序排列，空表目放在最后面
void adjust() {int i, j, swapped;struct freearea middata;// 第一阶段：使用冒泡排序按起始地址升序排列可用空闲区for (i = 0; i < N - 1; i++) {// 标记本次循环是否进行了交换操作swapped = 0;// 遍历未排序的空闲区for (j = 0; j < N - i - 1; j++) {// 如果当前和下一个空闲区都为可用，且当前空闲区起始地址大于下一个空闲区起始地址if (freeblock[j].state == 1 && freeblock[j + 1].state == 1 &&freeblock[j].startaddress > freeblock[j + 1].startaddress) {// 交换两个空闲区的信息middata = freeblock[j];freeblock[j] = freeblock[j + 1];freeblock[j + 1] = middata;// 标记进行了交换操作swapped = 1;}}// 如果本次循环没有进行交换操作，说明已经有序，提前结束排序if (!swapped) break;}// 第二阶段：将空表目移到表的末尾for (i = 0; i < N - 1; i++) {// 遍历未排序的空闲区for (j = 0; j < N - i - 1; j++) {// 如果当前空闲区为空表目，下一个空闲区为可用if (freeblock[j].state == 0 && freeblock[j + 1].state == 1) {// 交换两个空闲区的信息middata = freeblock[j];freeblock[j] = freeblock[j + 1];freeblock[j + 1] = middata;}}}
}

三、实 验 小 结

心得体会：

        在本次关于存储器分配与回收的实验中，我通过用 C 语言实现首次适应算法的动态分区分配过程 alloc () 和回收过程 free ()，对动态分区存储管理方式有了更深入的理解和实践体验，同时也在编程技能和问题分析能力方面得到了锻炼，收获颇丰。

        从知识掌握角度来看，通过实验，我清晰地认识到动态分区分配方式中数据结构和分配算法的工作原理。空闲区说明表作为管理空闲内存的关键数据结构，其记录的起始地址、长度和状态信息，为内存的分配与回收提供了重要依据。首次适应算法优先使用空闲区低端空间的策略，让我明白了如何高效地利用内存资源，在实际操作中，我体会到这种算法的优势在于尽可能地保留高端的大空闲区，为后续大作业的装入创造条件。同时，在实现内存回收时，处理空闲区合并的逻辑，使我对内存空间的连续化管理有了更深刻的认识，理解了如何避免内存碎片的产生。

        在编程实践方面，本次实验极大地提升了我的代码编写和调试能力。在实现 alloc () 函数时，通过遍历空闲区表并根据作业需求进行空闲区的分配和分割，锻炼了我对循环结构和条件判断语句的运用能力；而 free () 函数中复杂的空闲区合并逻辑，涉及到多个条件判断和索引操作，让我学会如何在复杂的业务逻辑中保持清晰的思路。此外，在调试过程中，我遇到了如数组越界、输入错误处理不完善等问题，通过逐步排查和分析，最终解决了这些问题，这一过程让我掌握了许多实用的调试技巧，也培养了我耐心和细致的编程习惯。

        不过，这次实验也暴露出我存在的一些不足。一方面，在代码优化上还有很大的提升空间。例如，在调整空闲区表顺序的 adjust () 函数中，虽然最终实现了功能，但代码的效率和简洁性仍有待提高。即使使用冒泡排序并添加了 swapped 标记提前结束排序，冒泡排序在数据量较大时效率较低，后续可以学习和尝试更高效的排序算法，如快速排序或归并排序，以提升程序性能。另一方面，在处理用户输入时，虽然进行了基本的错误处理，但对于一些异常情况的考虑还不够全面，输入验证的健壮性有待加强。

        总的来说，本次实验是一次非常有意义的实践活动，不仅巩固了课堂所学的理论知识，还让我在实际操作中发现问题、解决问题，积累了宝贵的经验。在今后的学习中，我会更加注重知识的实际应用，不断提升自己的编程水平和解决复杂问题的能力，为深入学习操作系统及其他计算机专业知识打下坚实的基础。