操作系统 连续式与分页式主存管理的模拟实现.doc

.深 圳 大 学 实 验 报 告 课程名称： 计算机操作系统 实验项目名称： 连续式与分页式主存管理的模拟实现 学院： 计算机与软件 专业： 软件工程 指导教师： 报告人： 学号： 班级： 实验时间： 实验报告提交时间： 教务部制1. 实验目的模拟在连续分配与分页管理两种方式下，主存空间的分配与回收，帮助学生加深了解存储器管理的工作过程。注意，该实验为模拟实验，并不要求进行真正的内存分配与回收，主要是编写程序模拟其中过程即可。2. 实验内容 l 连续式分配1、 在连续分配方式下，设计一个动态分区分配与回收的内存管理程序。2、 动态分区分配按作业需要的主存大小来分割分区。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。3、 设置一张全局分区状态表说明当前内存分配状态，例如下所示：05k10k14k26k32k 640k操作系统区作业1作业3空闲区作业2 空闲区 4、 设置一张空闲分区表描述当前空闲分区分布状况，可采用数组或链表来实现，链表请参考课本P108的数据结构设计。数组可参考以下格式：  起 址长 度状 态第一栏14 K12 K未 分 配第二栏32 K96 K未 分 配MM  空 表 目  空 表 目  M起址指出一个空闲区的主存起始地址。长度指出从起始地址开始的一个连续空闲的长度。状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区， 5、 尝试采用首次适应算法、循环首次适应算法、最佳适应算法其中的一种或多种算法实现动态分区分配。算法思想请参考课本P108-109的分区分配算法。6、 在作业撤销后，系统需要回收分区。在空闲分区表中找到一个空表目登记回收分区的起址和长度，并且修改表目状态为未分配。注意：由于分区的个数不定，所以空闲分区表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。7、 在回收分区时，应考虑相邻空闲分区合并，具体请参考课本P109的回收内存四种情况。8、 在完成一次作业装入后，都需要输出：本次分配的分区起址与长度，全局分区状态表，空闲分区表的内容。若在分配中发生分割，需要说明分割后新空白分区的起址与长度。9、 在完成一次作业撤销后，都需要输出：本次回收的分区起址与长度，全局分区状态表，空闲分区表的内容。若发生相邻空闲分区合并，需要说明哪几个分区合并在一起，合并后的起址与长度l 分页式管理1、 设计一个基本分页存储管理程序2、 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时按页分散存放在主存的空闲块中。3、 系统用一张块表记录物理块分配的情况，如下图所示，其中状态0表示未分配，1表示已分配。另外增加一个空闲块数，记录当前可用的物理块总数。  状态第0块1第1块1第2块0第3块1第4块0MM  4、 需要为每个作业设置一张页表，记录页号与块号的对应关系。页 号块 号0168172256MM5、 作业装入内存时，分配过程如下：a) 将空闲块数乘上每块空间，计算出可用空间总数，然后与作业需要空间比较，若不能满足需要，提示不能装入。b) 若能满足需要，为作业创建页表，在块表中寻找足够的空白块，将页号与块号一一对应，并填入页表。同时修改块表中各个块的状态c) 修改空闲块数，记录剩下空白块总数。6、 作业撤销后，需要回收物理块，回收过程如下：a) 根据页表，修改块表中对应各个物理块的状态b) 修改空闲块数，记录回收后空白块总数。c) 撤销页表7、 每次作业装入或回收，都需要输出块表、页表的内容，发生变化的块号，以及空闲块数。若块表太大，可以用二维表格的方式输出，或只输出发生变化的块号。3. 实验要求1、 至少完成上述实验内容中的一个。2、 自行设定内存总空间，大小单位为KB，分页管理需要设定每个页的大小。3、 随机设置当前内存分配状态。4、 自行设计作业队列，队列中至少要有3个作业，设定各个作业空间大小，大小要适中。5、 输出结果要尽量详细清晰，如果输出内容比较多，可以考虑把输出结果保存到文件中，通过文件来查看。6、 程序代码要尽量加入注释，提高程序的清晰度与可读性。7、 在实验报告中，一方面可以对实验结果进行分析，一方面可以对两种分配方式进行比较，分析它们的优劣。#include <iostream.h> #include <windows.h> #define LEN sizeof (struct node) struct elemtype int sizef; /开始地址 int flag; /状态标示1表示占用 int length; /内存长度 char name12; /文件名 ; struct node /初始化节点 elemtype size; struct node *next; struct node *next2; /空闲链指向的下一个节点 ; struct node *initlist() /初始化链表 struct node *head =(struct node*) malloc (LEN); return (head); ; void input(struct node *l, int t) /自行输入 int r,temp=0; l->size.sizef = 0; l->size.flag = 1; for (r=0; r<t; r+) l = l->next = initlist(); cout << "区大小" cin >> l->size.length; cout << "是否占用,占用用1，否用0" << endl; cin >> l->size.flag; if(l->size.flag = 1) cout << "作业名" cin >> l->size.name; else strcpy(l->size.name, "空闲区"); l->size.sizef = l->size.length + temp; temp = l->size.sizef; l->size.flag = 1; l->next = NULL; cout << endl; void had_input(struct node *l) /已经输入好的作业 l->size.sizef = 0; l->size.flag = 1; l = l->next = initlist(); l->size.sizef = 5; l->size.flag = 1; l->size.length = 15; strcpy(l->size.name, "作业1"); l = l->next = initlist(); l->size.sizef = 20; l->size.flag = 1; l->size.length = 12; strcpy(l->size.name, "作业3"); l = l->next = initlist(); l->size.sizef = 32; l->size.flag = 0; th = 14; strcpy(l->size.name, "空闲区"); l = l->next = initlist(); l->size.sizef = 46; l->size.flag = 1; l->size.length = 26; strcpy(l->size.name, "作业2"); l = l->next = initlist(); l->size.sizef = 52; l->size.flag = 0; l->size.length = 32; strcpy(l->size.name, "空闲区"); l = l->next = initlist(); l->size.sizef = 104; l->size.flag = 0; l->size.length = 51; strcpy(l->size.name, "空闲区"); l = l->next = initlist(); l->size.sizef = 135; l->size.flag = 0; l->size.length = 45; strcpy(l->size.name, "空闲区"); l = l->next = initlist(); l->size.sizef = 180; l->size.flag = 1; strcpy(l->size.name, "空闲区"); l->next = NULL; void output (struct node *l) /输出占用情况 cout << l->size.sizef << " 操作系统区" <<endl; while (l->next != NULL) l = l->next; cout << l->size.sizef << " " << l->size.name <<endl; void output2(struct node *l) /输出空闲列表并设置空闲链 int f=1; struct node *p = initlist(); p ->next = l; cout << " 起 址 长 度 状 态" << endl ; while (l->next != NULL) if (l->size.flag = 0) p->next->next2 = l; /设置空闲链 cout << f <<" " << l->size.sizef << " " << l->size.length << " 未 分 配" << endl; f+; p->next = l; l = l->next; p->next->next2 = l; /空闲链最后一个节点指向原链结尾 cout << "M" << " " << "空 表 目" << endl; int search1(struct node *l, int t,char name2) /首次适应算法查找 struct node *p = initlist(); while (l->next != NULL) if (l->size.length>=t && l->size.flag=0) strcpy(l->size.name, name2); l->size.flag = 1; if (l->size.length - t !=0) /插入且修改剩余空闲区 p->size.sizef = l->size.sizef + t; p->size.flag = 0; p->size.length = l->size.length - t; strcpy(p->size.name, "空闲区"); p->next = l->next; l->next = p; return 1; else return 1; l = l->next; return 0; int search2(struct node *l,int t,char name2) /循环首次适应算法 struct node *p = initlist(); while (l->next != NULL) if (l->size.length>=t && l->size.flag=0) strcpy(l->size.name, name2); l->size.flag = 1; if (l->size.length - t !=0) /插入且修改剩余空闲区 p->size.sizef = l->size.sizef + t; p->size.flag = 0; p->size.length = l->size.length - t; strcpy(p->size.name, "空闲区"); p->next = l->next; l->next = p; return 1; else return 1; l = l->next2; return 0; int search3(struct node *l,int t,char name2) /最佳适应算法 int flag =0, temp = 1000; struct node *p = initlist(); while (l->next != NULL) /查找最佳空闲区间 if (temp>=l->size.length && l->size.length>=t && l->size.flag=0) temp = l->size.length; p->next = l; flag = 1; l = l->next2; if (flag = 1) l = p->next; strcpy(l->size.name, name2); l->size.flag = 1; if (l->size.length - t !=0) /插入且修改剩余空闲区 p->size.sizef = l->size.sizef + t; p->size.flag = 0; p->size.length = l->size.length - t; strcpy(p->size.name, "空闲区"); p->next = l->next; l->next = p; return 1; return 0; void up(node *l,node *p) /合并上空闲区 p->next = l->next; p->size.length = p->size.length +l->size.length; free(l); void down(node *l,node *p) /合并下空闲区 l->next = p->next; l->size.length = p->size.length +l->size.length; strcpy(l->size.name, "空闲区"); l->size.flag = 0; free(p); int callback(node *l,int n) /回收空间 struct node *p = l; while(l->next != NULL) if (l->size.sizef = n && l->size.flag = 1) /查找到对应的首地址 if (p->size.flag=1 && l->next->size.flag=1) /不进行合并 strcpy(l->size.name, "空闲区"); l->size.flag = 0; return 1; if (p->size.flag=0 && l->next->size.flag=0) /对上下空闲表进行合并 down(l,l->next); up(l,p); return 1; if (p->size.flag=0) /对上空闲表进行合并 up(l,p); return 1; if (l->next->size.flag=0) /对下空闲表进行合并 down(l,l->next); return 1; p = l; l = l->next; cout << "错误的首地址或者溢出" << endl; return 0; void main() int w=1,b; /分区数目 int t,a,i; /输入的分区 char state; node *l = initlist(); cout << "是否自己输入？是（Y）否（任意健）" << endl; /选择输入 cin >> state; if (state='Y' | state='y') cout << "输入分几个区" /转自行输入 cin >> t; input(l,t); output(l); else had_input(l); /转已经输入好的 output(l); output2(l); while (w) cout << "退出？是（Y）否（任意健）" << endl; /是否退出 cin >> state; if (state='Y' | state='y') exit(1); cout << "选择算法适应算法（F）" << endl <<"循环首次适应算法（R）"<< endl << "最佳适应算法（T）"<< endl << "不进行插入（任意键）" << endl; cin >> state; if (state='F'|state='f'|state='R'|state='r'|state='T' | state='t') cout << "插入几个作业？" << endl; cin >> a; for (i=0; i<a; i+) int te=b; char name212; int length2; cout << "作业名" cin >> name2; cout << "作业长度" cin >> length2; if (state='F' | state='f') b = search1(l,length2,name2); /适应算法查找 if (state='R' | state='r') b = search2(l,length2,name2); /循环首次适应算法 if (state='T' | state='t') b = search3(l,length2,name2); /最佳适应算法 if(b = 1) cout << "插入成功" << endl; else if(b = 0) cout << "没有找到合适的空间，插入失败" <<endl; else cout <<"没有进行插入"<<endl; output(l); output2(l); cout << "回收几个空间？" << endl; cin >> a; for (i=0; i<a; i+) cout << "输入回收的开始地址" cin >> t; t = callback(l,t); /回收空间 output(l); output2(l); 深圳大学学生实验报告用纸如上两图可以看到经过选择适应算法插入一个作业2后，第三区的空闲起始地址改变了从70改为80，长度也从35改为25，因为插入的作业2的大小为10.再插入大小为5的作业3后起址变为85，长度变为20.同时因为回收区间的起始地址溢出所以什么都没改变。经过循环适应算法插入大小为6的作业4后，第三区的空闲起始地址变为91，大小为14.输入任意键及程序自己分配分区。插入大小为10的作业后第一空闲区的起始地址加了十，同时长度也减了十。分配大小为9的作业5后，因为第一个空闲分区的大小已经不够放这个作业，所以把该作业放到第二个空闲分区，因此第二个空闲分区的起始地址从52变成61，剩余长度也从32变成23.插入作业6后，第一个空闲分区的起始地址从42变成45，剩余空间长度也从4变成1.通过最佳适应算法插入大小为22的作业8后，第二个空闲分区的起始地址从61变成83，同时剩余空间长度从23变成1。通过最佳适应算法插入大小为44的作业9后，第四个空闲分区的起始地址从135变成179，同时剩余的长度也从45变成1.回收两个空间，第一次因为起始地址错误，所以回收失败。第二次回收空间，起始地址为135，刚好为第四空闲分区的起始地址，所以回收成功，第四空闲分区被合并到第三个空闲分区，所以第三个空闲分区的剩余长度从51变成91.通过本次实验让我们懂得了计算机操作系统动态分区的分配以及内存的回收，同时因为本次实验，要分析的代码以及结果比较多，所以只完成了第一个内容，第二个内容还没有实现。指导教师批阅意见：成绩评定： 指导教师签字： 年 月 日备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。.