《操作系统》课程实验报告实验名称：动态分区存储管理
姓名：
学号：
地点：
指导老师：
专业班级：
一、实验目的：
1、熟悉并掌握动态分区分配的算法。
2、熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。
二、实验内容：用高级语言模拟实现动态分区存储管理，要求：
1、分区分配算法至少实现首次适应算法、最佳适应算法和最坏适
应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。
2、分区的初始化——可以由用户输入初始分区的大小。（初始化后
只有一个空闲分区，起始地址为0，大小是用户输入的大小）
3、分区的动态分配过程：由用户输入作业号和作业的大小，实现
分区过程。
4、分区的回收：用户输入作业号，实现分区回收，同时，分区的
合并要体现出来。（注意：不存在的作业号要给出错误提示！）
5、分区的显示：任何时刻，可以查看当前内存的情况（起始地址
是什么，大小多大的分区时空闲的，或者占用的，能够显示出
来）
6、要求考虑：（1）内存空间不足的情况，要有相应的显示；
（2）作业不能同名，但是删除后可以再用这个名字；
（3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。
三、实验代码
#include
#include
#define SIZE 800 // 内存初始大小
#define MINSIZE 5 // 碎片最小值
enum STATE { Free, Busy };
struct subAreaNode {
int addr; // 起始地址
int size; // 分区大小
int taskId; // 作业号
STATE state; // 分区状态
subAreaNode *pre; // 分区前向指针
subAreaNode *nxt; // 分区后向指针
}subHead;
// 初始化空闲分区链
void intSubArea()
{
// 分配初始分区内存
subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode)); // 给首个分区赋值
fir->addr = 0;
fir->size = SIZE;
fir->state = Free;
fir->taskId = -1;
fir->pre = &subHead;
fir->nxt = NULL;
// 初始化分区头部信息
subHead.pre = NULL;
subHead.nxt = fir;
}
// 首次适应算法
int firstFit(int taskId, int size)
{
subAreaNode *p = subHead.nxt;
while(p != NULL)
{
if(p->state == Free && p->size >= size) {
// 找到要分配的空闲分区
if(p->size - size <= MINSIZE) {
// 整块分配
p->state = Busy;
p->taskId = taskId;
} else {
// 分配大小为size的区间
subAreaNode *node = (subAreaNode
*)malloc(sizeof(subAreaNode));
node->addr = p->addr + size;
node->size = p->size - size;
node->state = Free;
node->taskId = -1;
// 修改分区链节点指针
node->pre = p;
node->nxt = p->nxt;
if(p->nxt != NULL) {
p->nxt->pre = node;
}
p->nxt = node;
// 分配空闲区间
p->size = size;
p->state = Busy;
p->taskId = taskId;
}
printf("内存分配成功！\n");
return 1;
}
p = p->nxt;
}
printf("找不到合适的内存分区，分配失败...\n");
return 0;
}
// 最佳适应算法
int bestFit(int taskId, int size)
{
subAreaNode *tar = NULL;
int tarSize = SIZE + 1;
subAreaNode *p = subHead.nxt;
while(p != NULL)
{
// 寻找最佳空闲区间
if(p->state == Free && p->size >= size && p->size < tarSize) { tar = p;
tarSize = p->size;
}
p = p->nxt;
}
if(tar != NULL) {
// 找到要分配的空闲分区
if(tar->size - size <= MINSIZE) {
// 整块分配
tar->state = Busy;
tar->taskId = taskId;
} else {
// 分配大小为size的区间
subAreaNode *node = (subAreaNode
*)malloc(sizeof(subAreaNode));
node->addr = tar->addr + size;
node->size = tar->size - size;
node->state = Free;
node->taskId = -1;
// 修改分区链节点指针
node->pre = tar;
node->nxt = tar->nxt;
if(tar->nxt != NULL) {
tar->nxt->pre = node;
}
tar->nxt = node;
// 分配空闲区间
tar->size = size;
tar->state = Busy;
tar->taskId = taskId;
}
printf("内存分配成功！\n");
return 1;
} else {
// 找不到合适的空闲分区
printf("找不到合适的内存分区，分配失败...\n");
return 0;
}
}
// 回收内存
int freeSubArea(int taskId)
{
int flag = 0;
subAreaNode *p = subHead.nxt, *pp;
while(p != NULL)
{
if(p->state == Busy && p->taskId == taskId) {
flag = 1;
if((p->pre != &subHead && p->pre->state == Free)
&& (p->nxt != NULL && p->nxt->state == Free)) {
// 情况1：合并上下两个分区
// 先合并上区间
pp = p;
p = p->pre;
p->size += pp->size;
p->nxt = pp->nxt;
pp->nxt->pre = p;
free(pp);
// 后合并下区间
pp = p->nxt;
p->size += pp->size;
p->nxt = pp->nxt;
if(pp->nxt != NULL) {
pp->nxt->pre = p;
}
free(pp);
} else if((p->pre == &subHead || p->pre->state == Busy)
&& (p->nxt != NULL && p->nxt->state == Free)) {
// 情况2：只合并下面的分区
pp = p->nxt;
p->size += pp->size;
p->state = Free;
p->taskId = -1;
p->nxt = pp->nxt;
if(pp->nxt != NULL) {
pp->nxt->pre = p;
}
free(pp);
} else if((p->pre != &subHead && p->pre->state == Free) && (p->nxt == NULL || p->nxt->state == Busy)) {
// 情况3：只合并上面的分区
pp = p;
p = p->pre;
p->size += pp->size;
p->nxt = pp->nxt;
if(pp->nxt != NULL) {
pp->nxt->pre = p;
}
free(pp);
} else {
// 情况4：上下分区均不用合并
p->state = Free;
p->taskId = -1;
}
}
p = p->nxt;
}
if(flag == 1) {
// 回收成功
printf("内存分区回收成功...\n");
return 1;
} else {
// 找不到目标作业，回收失败
printf("找不到目标作业，内存分区回收失败...\n");
return 0;
}
}
// 显示空闲分区链情况
void showSubArea()
{
printf(" 当前的内存分配情况如下： \n");
printf("\n");
printf("起始地址\t空间大小\t工作状态\t作业号 \n");
subAreaNode *p = subHead.nxt;
while(p != NULL)
{
printf("\n");
printf("%d k\t ", p->addr);
printf("%d k\t ", p->size);
printf("%s \t ", p->state == Free ? "Free" : "Busy"); if(p->taskId > 0) {
printf("%d ", p->taskId);
} else {
printf(" ");
}
printf("\n");
p = p->nxt;
}
}
int main()
{
int option, ope, taskId, size;
// 初始化空闲分区链
intSubArea();
// 选择分配算法
while(1)
{
printf("请选择要模拟的分配算法： 0 表示首次适应算法，1 表示最佳适应算法\n");
scanf("%d", &option);
if(option == 0) {
printf("你选择了首次适应算法，下面进行算法的模拟\n");
break;
} else if(option == 1) {
printf("你选择了最佳适应算法，下面进行算法的模拟\n");
break;
} else {
printf("错误：请输入 0/1\n\n");
}
}
// 模拟动态分区分配算法
while(1)
{
printf("\n");
printf("*********************************************\n"); printf(" 1: 分配内存 2: 回收内存 0: 退出 \n");
printf("*********************************************\n"); scanf("%d", &ope);
if(ope == 0) break;
if(ope == 1) {
// 模拟分配内存
printf("请输入作业号： ");
scanf("%d", &taskId);
printf("请输入需要分配的内存大小(KB)： ");
scanf("%d", &size);
if(size <= 0) {
printf("错误：分配内存大小必须为正值\n");
continue;
}
// 调用分配算法
if(option == 0) {
firstFit(taskId, size);
} else {
bestFit(taskId, size);
}
// 显示空闲分区链情况
showSubArea();
} else if(ope == 2) {
// 模拟回收内存
printf("请输入要回收的作业号： ");
scanf("%d", &taskId);
freeSubArea(taskId);
// 显示空闲分区链情况
showSubArea();
} else {
printf("错误：请输入 0/1/2\n");
}
}
printf("分配算法模拟结束\n");
return 0;
}
四、实验结果
五、实验总结
本实验极大的帮助我们理解了动态分区作业存储管理的实现过程。在对作业采用最优适应算法的同时，还外加代码弥补了最优适应算法会产生极小的零碎空闲区的弊端。在作业存储时，当前作业的起始地址=原空闲区起始地址+原空闲区
偏移地址-当前作业的偏移地址；由此可知当前作业在空闲区内是从空闲区的高地址开始分配。在对作业回收时，作业临区的回收采用if、else语句及其嵌套语句，清楚合理的实现了作业回收。并且进一步加深对c语言和数据结构的理解。
实验三动态分区存储管理方式的主存分配回收 一、实验目的 深入了解动态分区存储管理方式主存分配回收的实现。 二、实验预备知识 存储管理中动态分区的管理方式。 三、实验内容 编写程序完成动态分区存储管理方式的主存分配回收的实现。实验具体包括： 首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配和回收；最后编写主函数对所做工作进行测试。 四、提示与讲解 动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 实现动态分区的分配和回收，主要考虑的问题有三个： 第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。 首先，考虑第一个问题： 设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。 由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主
存中的起始地址和长度。由于分配时空闲区有时会变成两个分区： 空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。 由此可见，主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况，一张表格记录作业占用分区的 “已分配区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区 表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分配区表”还是“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此, “已分配区表”和“空闲区表”在实验中有如下的结构定义。 已分配区表的定义： #define n 10// 假定系统允许的最大作业数量为n struct {float address;// 已分分区起始地址 float length; // 已分分区长度，单位为字节 int flag;// 已分配区表登记栏标志, “0表”示空栏目，实验中只支持一个字符的作业名}used_table[n];// 已分配区表 空闲区表的定义：
一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方 案的理解，熟悉可变分区存储管理的内存分配和回收。 二．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 三．实验背景材料 实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。 首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分
配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #definen10//假定系统允许的最大作业数量为n struct {floataddress;//已分分区起始地址 floatlength;//已分分区长度、单位为字节 intflag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n];//已分分区表 “空闲区表”的结构定义 #definem10//假定系统允许的空闲区最大为m struct {floataddress;//空闲区起始地址
实验五动态分区存储管理 一、实验目的 深入了解采用动态分区存储管理方式的内存分配回收的实现。通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉动态分区存储管理的内存分配和回收。 二、实验内容 编写程序完成动态分区存储管理方式的内存分配回收。 具体包括：确定内存空间分配表； 采用最优适应算法完成内存空间的分配和回收； 编写主函数对所做工作进行测试。 三、设计思路 整体思路： 动态分区管理方式将内存除操作系统占用区域外的空间看成一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所采用的算法： 采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体： 为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分 区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。
可变分区存储管理 设计思路： 整体思路： 可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个 空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所才用的算法： 采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值min size，如果空闲区的大小减去作业需求长度得到的值小于等于min size，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体： 为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。 关于分配留下的内存小碎片问题： 当要装入一个作业时，从“空闲分区表”中查找标志为“ 1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于min size，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“ 0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于
理工大学信息工程与自动化学院学生实验报告 （ 2013 —2014 学年第一学期） 课程名称：操作系统开课实验室：信自楼444 2013年 11月28 日 注：报告容按下列的要求进行。 一、实验目的 通过编写固定分区存储管理的模拟程序，加深对操作系统存储管理功能中的固定分区管理方式、主存分配表等相应知识的理解。 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的存分配和回收。 二、实验题目 1.设计一个固定分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 2.必须建立分区表，记录空闲区与占用区的状况。 3.流程图按选定的算法自己完成。
三、算法设计的思想或流程图 本系统将存用户空间划分为五个大小不固定的分区，其分区大小由用户输入决定。在每个分区只装入一道作业，这样把用户空间划分为几个分区，便允许几道作业并发运行。当有一个空闲分区时，便可以从外存的后备队列中选择一个适当大小的作业装入该分区，当该作业结束时又可以从后备作业队列中找出另一作业调入该分区。 每个存空间是一个Node型的对象。Node类有一个三个参数的构造函数。分别为：分区号、起始地址、大小。然后就是一些属性的get、set方法和一个打印其属性的函数。四个数据域分别为：属性m_No用来表示该存空间的序号。属性m_Addr用来表示存分区的起始地址。属性m_Size用来表示存空间的大小。属性m_State表示存空间的是否已分配的状态标志。若该存空间已分配，m_TaskNo表示占有该存空间的任务序号。否则没有实际意义。 在用户申请任务的存空间时，提示用户输入任务号和其需要的存空间大小。 流程图 主程序：
实验五动态分区存储管理模拟 一、实验目的 深入了解可变分区存储管理式主存分配回收的实现。 二、实验预备知识 可变分区存储管理式不预先将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当进程要求装入主存时，根据进程需要主存空间的大小查询主存各个空闲区，当从主存空间找到一个大于或等于该进程大小要求的主存空闲区时，选择其中一个空闲区，按进程需求量划出一个分区装入该进程。进程执行完后，它所占的主存分区被回收，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 这个实验主要需要考虑三个问题： (1)设计记录主存使用情况的数据表格，用来记录空闲区和进程占用的区域； (2)在设计的数据表格基础上设计主存分配算法； (3)在设计的数据表格基础上设计主存回收算法。 首先，考虑第一个问题：设计记录主存使用情况的数据表格，用来记录空闲区和进程占用的区域。 由于可变分区的大小是由进程需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收而变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配
时查找空闲区进行分配，然后填写已分分区表，主要操作在空闲区；某个进程执行完成后，将该分区变成空闲区，并将其与相邻空闲区合并，主要操作也在空闲区。由此可见，主存分配和回收主要是对空闲区的操作。 这样，为了便于对主存空间的分配和回收，就建立两分区表记录主存使用情况，一表格记录进程占用分区的“已分分区表”；一是记录空闲区的“空闲区表”。这两表的实现法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分分区表”还是“空闲区表”都有空闲栏目。已分分区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，容为“空”，如果为某个进程占用分区的登记项，容为该进程的进程名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，容为“空”，如果为某个空闲区的登记项，容为“未分配”。在实际系统中，这两个表格的容可能还要更多，实验中仅仅使用上述必须的数据。为此，“已分分区表”和“空闲区表”在实验中有如下的结构定义： 已分分区表的定义： #define n 10 //假定系统允的进程数量最多为n struct { float address; //已分分区起始地址 float length; //已分分区长度，单位为字节
#include
操作系统原理 课程设计报告 题目：动态分区分配存储管理系统 所在学院：计算机科学与技术学院 班级： 11级计算机科学与技术(非师) 学号： 20111202052 姓名：吴创连 指导教师：黄侠剑 2014年3月18
目录 1 引言 (1) 2 需求分析 (1) 3 概要设计 (1) 4 详细设计 (1) 4.1问题描述和分析 (1) 4.2程序流程图 (2) 4.3数据结构体分析 (3) 4.4主要程序代码分析 (4) 5 调试与操作说明 (11) 5.1初始界面 (11) 5.2模拟内存分配 (12) 5.3回收内存界面 (12) 5.4最佳适应算法的实现 (13) 5.5最坏适应算法的实现 (13) 6总结与体会 (13)
1 引言 操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。 存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。 2 需求分析 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。常用的数据结构有动态分区表和动态分区链。在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（最佳适应算法，最坏适应算法），在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容。 3 概要设计 本程序采用机构化模块化的设计方法，共分为两大模块。 1．最佳适应算法实现 它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。 2.最坏算法实现 最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 4 详细设计 4.1 问题描述和分析 系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小
实验报告 操作系统 可变分区存储管理方式的内存分配回收 班级：XXXXXXXXXXXX 学号：XXXXXXXXXXXX 姓名：XXXXXX 日期：XXXX.XX.XX
版本历史Revisions History
目录1引言4 1.1实验目的4 1.2参考文档4 2可变分区存储管理5 2.1实验原理分析5 2.2设计思路5 2.3源程序6 2.4重要结构体说明10 2.5重要变量说明10 2.6结果11 2.7测试方法对结果的分析11 2.8接口12 2.8.1接口设计说明12 2.9任务设计12 2.9.1流程图12
1 引言 1.1实验目的 通过首次适应算法、最佳适应算法和最坏适应算法实现主存空间的分配，可以使开发人员更好地理解存储分配算法。 1.2参考文档 1.操作系统 2. 3.1节空闲存储区表 2.操作系统2. 3.2节首次适应法（1.分配算法，2.回收算法）
2 可变分区存储管理 2.1实验原理分析 在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是 一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被 占用，而有的分区时空闲的。为了方便主存空间的分配和去配，用于管理的数据结 构可由两张表组成：“已分配区表”和“未分配区表”。在“未分配表中”将空闲 区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进 程要求的最小分区进行分配。这时从已分配表中找出一个空栏目登记新作业的起始 地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。当作业撤离时 已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有 相邻空闲区再将其连接后登记。 2.2设计思路 1、分配算法： 采用首次适应法为作来分配大小为size的内存空间时，总是从表的起始端的低地址 部分开始查找，当第一次找到大于或等于申请大小的空闲区时，就按所需大小分配 给作业。如果分配后原空闲区还有剩余空间，就修改原存储区表项的m_size和 m_addr，使它记录余下的“零头”。如果作业所需空间正好等于该空闲区大小，那 么该空闲区表项的m_size就成为0，接下来要删除表中这个“空洞”，即将随后的 各非零表项依次上移一个位置。 2、回收算法： 当某一作业回收以前所分配到的内存时，就要将该内存区归还给系统，使其成为空 闲区而可被其它作来使用。回收时如释放区与邻近的空闲区相衔接，要将它们合并 成较大的空闲区，否则空闲区将被分割得超来越小，最终导致不能利用；另外，空 闲区个数越来越多，也会使空闲区登记表溢出。
计算机科学与工程学院学生实验报告 专业计算机科学与技术班级 学号姓名 课程名称操作系统课程类型专业必修课 实验名称动态分区存储管理的模拟实现 实验目的： 1.熟悉动态分区存储管理方式下，主存空间的分配和回收算法。 2.提高C语言编程能力。 实验内容： 假设主存当前状态如右表所示： 系统采用最佳适应分配算法为作业分配主存空间， 而且具有紧凑技术。请编程完成以下操作： (1). 输出此时的已分配区表和未分配区表； (2). 装入 Job3(15K)，输出主存分配后的已分配 区表和未分配区表； (3). 回收 Job2所占用的主存空间，输出主存回收 后的已分配区表和未分配区表； (4).装入 Job4(130K)，输出主存分配后的已分配 区表和未分配区表。 实验要求 1.数据结构参考定义如下，也可根据需要进行改进： (1)已分配区表： #define n 10 /*假定系统允许的最大作业数量为n，n值为10*/ struct {int number; /*序号*/ int address; /*已分配分区起始地址，单位为KB */ int length; /*已分配分区长度，单位KB*/ float flag; /*已分配区表登记栏标志，0：空表项，否则为作业名；*/
}used_table[n]; /*已分配区表*/ (2)未分配区表： #define m 10 /*假定系统允许的空闲区表最大为m，m值为10*/ struct {int number; /*序号*/ int address; /*空闲区起始地址，单位为KB */ int length; /*空闲区长度，单位为KB*/ int flag; /*空闲区表登记栏标志，0：空表项；1：空闲区*/ }free_table[m]; /*空闲区表*/ 2.以allocate命名主存分配所用的过程或函数（算法参考课件），要将各种情况考虑周全。 3.以reclaim命名主存回收所用的过程或函数（算法参考课件），要将各种情况考虑周全。 4.画出算法实现的N-S流程图。 5.程序调试、运行成功后，请老师检查。 实验步骤： 1.分配内存，结果如下图：
free_quantity++; fscanf(文件指针，格式字符串，输入表列)； } return 1; } return 0; } void sort() { int i,j,p; for(i=0;i 动态分区分配管理系统 学院 专业 学号 学生姓名 指导教师姓名 2014年3月14 日 目录 1程序设计的内容和相关的要求---------------------------------2 2程序总的功能说明--------------------------------------------3 3程序的模块的说明--------------------------------------------4 4程序设计的流程图--------------------------------------------5 5程序的操作说明及运行结果-----------------------------------7 6源程序-------------------------------------------------------11 7心得体会----------------------------------------------------27 1程序设计的内容和相关的要求： 课程设计的目的：操作系统课程设计是计算机学院重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 ● 进一步巩固和复习操作系统的基础知识。 ● 培养学生结构化程序、模块化程序设计的方法和能力。 ● 提高学生调试程序的技巧和软件设计的能力。 ● 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能 力。 实现的任务：编写一个动态分区分配程序。 设计内容： 用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法 1.首次适应算法 2.循环首次适应算法 设计要求： 1.内存中有0-100M的空间为用户程序空间，最开始用户空间是空闲的； 2.作业数量、作业大小、进入内存空间、运行时间需要通过界面进行输入； 3.可读取样例数据（要求存放在外部文件夹中）进行作业数量、作业大小、进图内存时间、运行时间的初始化； 4.根据作业进图内存的时间，采用简单的先进先出原则进行从外村到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。（为了简化，不考虑cpu的调度与切换，运行时间为作业在内存中驻留的时间）； 5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作，所有过程均有动态图形变化的显示； 6.采用可视化界面，可随时暂停显示当前内存分配和使用情况图。 2程序总的功能说明： 本程序可以从界面直接输入作业并进行动态的内存分配，也可以自动地生成作业文件并自行调度进行内存分配，每次分配可以选择两种算法（首次适应算法和循环首次算法）中的一种，每次作业结束后可以进入操作主界面进行再次作业的操作。 首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去； 存储管理练习题一 一、单项选择题 1.采用可重入程序是通过使用（）的法来改善响应时间的。 A 减少用户数目 B 改变时间片长短 C 加快对换速度 D 减少对换信息量 （D可重入程序是指该程序被某进程调用，但还未结束，又被另一个进程调用。 可重入程序是通过减少对换信息量来改善系统响应时间的。 可重入程序主要通过共享来使用同一块存储空间的，或者通过动态的式将所需的程序段映射到相关进程中去，其最大的优点是减少了对程序段的调入调出。由此来减少对换信息量。 ） 2.段式存储管理中，用于记录作业分段在主存中的起始地址和长度的是（） A 基址寄存器和很长寄存器 B 段表 C 界限寄存器 D 上、下限寄存器 答案：B 3.固定分区存储管理中，CPU在执行作业的指令时，均会核对不等式（）是否成立，若不成立，则产生地址越界中断事件，中止该指令的执行。 A 界限寄存器≤绝对地址≤最址 B 下限地址≤绝对地址<上限地址 C 基址寄存器容≤绝对地址≤限长寄存器容 D基址寄存器容<绝对地址<限长寄存器容 答案：B 固定分区存储管理（适合多道程序设计） 1.分区的定义 固定分区存储管理是把主存储器中可分配的用户区域预先划分成若干个连续区，每一个连续区称为一个分区。 2.固定分区存储管理的特点 （1）分区大小固定 （2）分区数目固定。 3.主存空间的分配与回收 存储管理设置“分区分配表”来说明各分区的分配和使用情况。表中指出各分区的起始地址和长度，并为每个分区设置一个标志位。标志位为“0”表示分区空间，非“0”表示分区已被占用。当有作业要装入分区，存储管理分配主存区域时，根据作业地址空间的长度与标志为“0”的分区的长度比较，当有分区长度能容纳该作业时，则把作业装入该分区，且把作业名填到占用标志位上。否则，该作业暂时不能装入。作业运行结束后，根据作业名查分区分配表，把该分区的占用标志置成“0”以示空闲。 4.地址转换和存储保护 因作业存放区域不会改变，可采用静态重定位式把作业装入所在的分区号，且把该分区的下限地址和上限地址分别送入下限寄存器和上限寄存器中。处理器执行该作业的指令时必须核对：“下限地址≤绝对地址≤上限地址”如此等式不成立，产生“地址越界”中断事件。 5.为了提高主存空间的利用率，可以采用如下几种措施： （1）根据经常出现的作业的大小和数量来划分分区，尽可能使各个分区被充分利用。 （2）划分分区时按分区的大小顺序排列，低地址部分是较小的分区，高地址部分是较大的分区。 （3）按作业对主存空间的需求量排成多个作业队列，每个作业队列中的各作业依次装入一个一个固定的分区中，每次装一个作业；不同作业队列中的作业分别依次装入不同的分区中；不同的分区中可同时装入作业；某作业队列为空时； 动态分区分配存储管理系统 学院 专业 学号 学生姓名 指导老师 2014年3月19日 目录 一、设计目的与内容 (3) 1、设计目的 (3) 2、设计内容 (3) 3、设计要求 (3) 二、算法的基本思想 (3) 1、首次适应算法 (3) 2、循环首次适应算法 (3) 三、主要功能模块流程图 (4) 1、主函数流程图....................................................................................................................... .4 2、首次适应算法流程图........................................................................................................... .5 3、循环首次适应算法流程图................................................................................................... .6 四、系统测试..................................................................................................................................... .7 输入界面，按要求输入： (7) 五、结论 (8) 六、源程序 (9) 昆明理工大学信息工程与自动化学院学生实验报告 （ 2013 —2014 学年第一学期） 课程名称：操作系统开课实验室：信自楼444 2013年 11月28 日 注：报告内容按下列的要求进行。 一、实验目的 通过编写固定分区存储管理的模拟程序，加深对操作系统存储管理功能中的固定分区管理方式、主存分配表等相应知识的理解。 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。 二、实验题目 1.设计一个固定分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 2.必须建立分区表，记录空闲区与占用区的状况。 3.流程图按选定的算法自己完成。 三、算法设计的思想或流程图 本系统将内存用户空间划分为五个大小不固定的分区，其分区大小由用户输入决定。在每个分区只装入一道作业，这样把用户空间划分为几个分区，便允许几道作业并发运行。当有一个空闲分区时，便可以从外存的后备队列中选择一个适当大小的作业装入该分区，当该作业结束时又可以从后备作业队列中找出另一作业调入该分区。 每个内存空间是一个Node型的对象。Node类有一个三个参数的构造函数。分别为：分区号、起始地址、大小。然后就是一些属性的get、set方法和一个打印其属性的函数。四个数据域分别为：属性m_No用来表示该内存空间的序号。属性m_Addr用来表示内存分区的起始地址。属性m_Size用来表示内存空间的大小。属性m_State表示内存空间的是否已分配的状态标志。若该内存空间已分配，m_TaskNo表示占有该内存空间的任务序号。否则没有实际意义。 在用户申请任务的内存空间时，提示用户输入任务号和其需要的内存空间大小。 流程图 主程序： 青岛农业大学 理学与信息科学学院 操作系统课程设计报告 设计题目仿真实现动态可变分区存储管理模拟系统 —最佳适应算法和最先适应算法 学生专业班级计算机科学与技术2011级03班 学生姓名（学号）张明珠（H20110684 ） 设计小组其他同学姓名（学号）刘玉婷（H20110661） 宋璇（H20110162） 指导教师牟春莲 完成时间 2014. 06.15 实习（设计）地点信息楼218 2014年6月16日 一、课程设计目的 操作系统的理论知识只有通过操作系统的实际操作和编程才能真正地理解 和掌握，没有实践操作系统的操作和编程，学习操作系统就是纸上谈兵。操作系统课程设计是在学习完《操作系统》课程后进行的一次全面、综合实习，是计算机科学与技术专业的重要实践性教学环节。通过课程设计，达到如下目的： 1、巩固和加深对操作系统原理的理解，提高综合运用本课程所学知识的能力。 2、培养学生选用参考书，查阅手册及文献资料的能力；培养独立思考、深 入研究、分析问题、解决问题的能力。 3、通过实际操作系统的分析设计、编程调试，掌握系统软件的分析方法和 工程设计方法。 4、能够按要求编写课程设计报告书，能正确阐述设计过程和实验结果、正 确绘制系统和程序框图。 5、通过课程设计，培养学生严谨的科学态度、严肃认真的工作作风和团队 协作精神。 二、设计任务 题目描述： 仿真实现动态可变分区存储管理模拟系统。内存调度策略可采用最先适应算法、最佳适应法等，并对各种算法进行性能比较。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业.设计要求： 1．采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： ⑴随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。 内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0。 ⑵主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能。成员分工： 张明珠申请内存、查看进程之间的前后的区域状态、释放进程 《操作系统》课程实验报告实验名称：动态分区存储管理 姓名： 学号： 地点： 指导老师： 专业班级： 一、实验目的： 1、熟悉并掌握动态分区分配的算法。 2、熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。 二、实验内容：用高级语言模拟实现动态分区存储管理，要求： 1、分区分配算法至少实现首次适应算法、最佳适应算法和最坏适 应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。 2、分区的初始化——可以由用户输入初始分区的大小。（初始化后 只有一个空闲分区，起始地址为0，大小是用户输入的大小） 3、分区的动态分配过程：由用户输入作业号和作业的大小，实现 分区过程。 4、分区的回收：用户输入作业号，实现分区回收，同时，分区的 合并要体现出来。（注意：不存在的作业号要给出错误提示！） 5、分区的显示：任何时刻，可以查看当前内存的情况（起始地址 是什么，大小多大的分区时空闲的，或者占用的，能够显示出 来） 6、要求考虑：（1）内存空间不足的情况，要有相应的显示； （2）作业不能同名，但是删除后可以再用这个名字； （3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。 三、实验代码 #include 操作系统课程设计 动态分区分配存储管理 吕 霆 计算机10-01班 设计题目 学 号 专业班级 学生姓名 指导教师 第一章课程设计概述 1.1 设计任务: 动态分区分配存储管理 1.2 设计要求 建立描述内存分配状况的数据结构； 建立描述进程的数据结构； 使用两种方式产生进程：（a）自动产生，（b）手工输入； 在屏幕上显示内存的分配状况、每个进程的执行情况； 建立分区的分配与回收算法，支持紧凑算法； 时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位； (b) 响应WM_TIMER； 将一批进程的执行情况存入磁盘文件，以后可以读出并重放； 支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法。1.3 设计目的 旨在让我们更好的了解动态分区管理方面的知识. 第二章原理及算法描述 2.1动态分区分配算法原理 首次适应算法 * 算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中 * 实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对应作业的值 循环首次适应算法 * 算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区开始查找 * 实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位置 最佳适应算法 * 算法概述：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区 分配给作业 * 实现方法：我们决定每次分配先把空闲分区按从小到大的顺序排列，然后将第一个匹配分区分配给作业 最坏适应算法 * 算法概述：每次为作业分配内存时，总是挑选一个最大的空闲分区分割给作业使用 * 实现方法：算法与最佳适应算法几乎相同，仅在排序时把空闲分区表按从大到小的顺序排列，所以未作详细注释 回收分区 当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一; 1)回收区与插入点的前一个空闲分区F1相邻接,此时应将回收区与插入点的前一分 区合并,不必为回收区分配新表项,而只需修改其前一分区F1的大小. 2)回收分区与插入点的后一空闲分区F2相邻接,此时也可将两分区合并,形成新的 空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和. 3)回收区同时与插入点的前,后两个分区邻接,此时将三个分区合并,使用F1的表项 和F1的首址,取消F2的表项,大小为三者之和. 4)回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填 写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置. 紧凑算法 通过移动内存中的作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法. 第三章开发环境 此程序是本人利用c++语言在vs2012的开发环境中实现的 第四章程序实现--数据结构 #include 动态分区分配管理系统
存储管理练习题一(带答案)
动态分区分配存储管理系统
固定分区存储管理
动态可变分区存储管理模拟系统解析
动态分区存储管理
操作系统课程设计动态分区分配存储管理
相关主题
文本预览