可变分区分配与回收——采用最坏算法,操作系统课程设计.doc

哈尔滨理工大学课程设计（操作系统）题目：可变分区分配与回收采用最坏算法 班级： 计算机科学与技术学院 计算机系10-8班姓名：张兢 1004010813指导教师：高雪瑶系主任： 林克正 2013年03月01日 哈尔滨理工大学课程设计报告一、 课程设计目的1、背景主存是CPU可直接访问的信息空间，合理而有效的使用贮存将在很大程度上影响整个计算机系统的性能。本课题要求模拟实现分区式主存管理机制。模拟实现各种分区管理方法以及相应的主存分配以及回收算法。2、目的通过该课题进一步加深对可变分区存储机制的理解。加深对存储器动态分区分配算法的认识。掌握“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”的内存分配过程。掌握内存的回收策略。二、 课题任务描述1、设计可用的内存空闲空间，并能动态输入用户作业所需的内存大小。2、编程模拟各种分配算法的实施过程，允许自行选择如“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”等常用算法，要求实现不少于三种算法。3、实现内存的回收。要求考虑回收时的内存合并问题。三、 课题研发相关知识 （包含所用库函数的介绍）1、 首次适应算法（first fit）FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能男足要求的空闲分区位置；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。但是，低址部分不断被划分，会留下许多难以利用的很小的空闲分区。2、 最佳适应算法（best fit）所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。这样，在存储器中会留下许多难以利用的小空闲区。3、 最坏适应算法（worst fit）要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中小作业有力，查找效率很高。但是它会使存储器中缺乏大的空闲分区。4、 回收内存当进程运行完毕释放内存时，系统根据会收取的首址，从空闲区链中找到相应的插入点，并考虑回收区前后是否有空闲分区，如果有，则把两个分区合并成一个大的空闲分区。5、库函数的介绍1）stdio 就是指 “standard buffered input&output 意思就是说带缓冲的标准输入输出！ 所以了，用到标准输入输出函数时，就要调用这个头文件！2）Stdlib.h即standard library 标准库文件。Stdlib头文件里包含了C,C+语言的最常用的系统函数。Stdlib.h里面定义了五中类型，一些宏和通用工具函数。 类型例如：size_t ,wchar_t, div_t, ldiv_t,lldiv_t; 宏例如：EXIT_FALIRE,EXIT_SUCCESS,RAND_MAX和MB_CUR_MAX。 以下是一些常用的函数：dec 置基数为10 相当于%d；hex 置基数为16 相当于%X；oct 置基数为8 相当于%o；setw(n) 设域宽为n个字符四、 课题设计：总体结构、所使用的数据结构、主要功能的流程图、程序的技术路线1、 总体结构 本系统采用了首次适应算法、最佳适应算法和最坏适应算法模拟存储器动态分区。系统利用其中某种分配算法，从空闲分区链中找到满足请求内存大小的分区并分配内存给作业。假设总的内存大小为size，作业请求的内存大小为request,内存碎片最小为f。当requestsize时，内存溢出，出现系统错误；当request=size时，在内存中根据上述算法寻找最佳的内存分区分配给作业。寻找到合适的内存分区之后，如果size-requestf，就在此分区上分割request大小的内存给作业，剩余内存继续留在当前的分区中。当进程运行完毕，系统找到该进程并释放其内存，根据所释放内存的位置对内存进行合并。系统流程图：如图1YNNYNY开始输入option选择分配算法option=3?根据option的值选择相应算法，输入opeope=0?ope=1?ope=2?ope=3?NN退出分配内存回收内存返回上一级输入错误YY图1系统框架图：如图2存储器动态分区分配模拟系统首次适应算法最佳适应算法最坏适应算法退出系统分配内存回收内存返回上一级菜单图22、 数据结构（1）定义的全局变量：#define SIZE 1000 / 内存初始大小#define MINSIZE 5 / 碎片最小值enum STATE Free, Busy /枚举类型，记录分区是否空闲的状态量（2）定义的结构体：struct subAreaNode。记录分区的主要数据。（3）函数1）void intSubArea()：分配初始分区内存。2）int firstFit(int taskId, int size)：首次适应算法实现函数，taskId为作业名，size为作业申请的内存大小。3）int bestFit(int taskId, int size)：最佳适应算法实现函数，taskId为作业名，size为作业申请的内存大小。4）int worstFit(int taskId, int size)：最坏适应算法实现函数，taskId为作业名，size为作业申请的内存大小。5）int freeSubArea(int taskId)：内存回收函数，该函数主要用于实现内存的回收，根据回收内存的位置对分区进行合并操作。其中taskId为所需回收内存的作业号。6）void showSubArea()：显示空闲分区链情况。包括起始地址 ，空间大小 。工作状态 。作业号。7）int main()：主函数，主要用于显示操作界面，调用各个子函数等功能。3、主要功能的流程图（1）首次适应算法First_fit(int,int); 流程图（图3）图3NYY开始p = subHead.nxt，从链表的第一个节点开始寻找p是否为空p是否空闲，p-size大小是否满足作业需求p-size与作业需求大小之差是否小于等于内存碎片p中内存大小全部分配给作业N执行完毕结束Y分割分区p，并把剩余内存存入新的结点N（2）最佳适应算法Best_fit(int,int); 流程图（图4）图4YYN开始subAreaNode*p= subHead.nxtP是否空P是否满足最佳分配空间YNp=p-nxttar=ptar为空？Ntar-size-size是否小于等于内存碎片tar全部分配给作业结束Y切割tar，分配给作业，并把剩余内存重新链入链表N（3）最坏适应算法Worst_fit(int,int); 流程图（图5）NYYN开始subAreaNode*p= subHead.nxtmm=1P是否空且mm=1P是否满足最佳分配空间YNp=p-nxttar=p,mm=0tar为空？tar-size-size是否小于等于内存碎片tar全部分配给作业结束Y切割tar，分配给作业，并把剩余内存重新链入链表N遍历空闲链表，p=subHead.nxt寻找最大的空闲分区，tar=p;图5YY4. 程序的技术路线 本程序采用C语言编写，在windows下的Visual C+中编译，模拟可变分区存储管理方式的内存分配与回收。假定系统的最大内存空间为1000kb，判断是否划分空闲区的最小限值为MINSIZE=5。初始化用户可占用内存区的首地址为0，大小为0B。定义一个结构体及其对象subHead实现内存的分配回收及分配表和空闲表的登记。用最佳分配算法实现动态分配时，调用int bestFit(int taskId, int size)内存分配函数，设定循环条件查找最佳空闲分区，根据找到的空闲区大小和作业大小判断是整个分配给作业还是切割空闲区后再分配给作业，并在“内存分配表”和“空闲分区表”中作登记。调用int freeSubArea(int taskId)函数实现内存的回收。顺序循环“内存分配表”找到要回收的作业，设置标志位flag，当flag=1时表示回收成功。回收内存时需考虑内存的4种合并方式，即合并上下分区、合并上分区、合并下分区、上下分区都不合并。五、 带有详细注解的源程序#include#include#include#define SIZE 1000 / 内存初始大小#define MINSIZE 5 / 碎片最小值enum STATE Free, Busy ;static int ss=0,ee=0;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 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 size; p = p-nxt; if(tar != NULL) / 找到要分配的空闲分区 if(tar-size - size 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 worstFit(int taskId, int size) subAreaNode *tar = NULL; int tarSize;int mm=1; subAreaNode *p = subHead.nxt; while(p != NULL&mm=1) / 寻找最佳空闲区间 if(p-state = Free & p-size = size) tar = p; tarSize = p-size; mm=0; elsep = p-nxt; p=subHead.nxt; while(p != NULL) / 寻找最大空闲区间 if(p-state = Free & p-size = tarSize & p-size=size) tar = p; tarSize = p-size;/遍历找到最大空闲区间p=p-nxt; else p = p-nxt; if(tar != NULL) / 找到要分配的空闲分区 if(tar-size-sizestate = 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; /* int start(int task)clock_t s;s=(int)clock();return s;int end(int task)clock_t s;s=(int)clock();return s;*/ 显示空闲分区链情况void showSubArea() printf(*n); printf(* 当前的内存分配情况如下： *n); printf(*n); printf(* 起始地址 | 空间大小 | 工作状态 | 作业号 *n); subAreaNode *p = subHead.nxt; while(p != NULL) printf(*-*n); printf(*); printf(%5d k |, p-addr); printf(%5d k |, p-size); printf( %5s |, p-state = Free ? Free : Busy); if(p-taskId 0) printf(%5d , p-taskId); else printf( ); printf(*n); p = p-nxt; printf(*n);int main() int option, ope, taskId, size; / 初始化空闲分区链 intSubArea(); / 选择分配算法l1: while(1) printf(*n); printf(请选择要模拟的分配算法:n0 表示首次适应算法n1 表示最佳适应算法n2 表示最坏适应算法n3 退出n); printf(*n); scanf(%d, &option);system(cls); if(option = 0) printf(你选择了首次适应算法，下面进行算法的模拟n); break; else if(option = 1) printf(你选择了最佳适应算法，下面进行算法的模拟n); break; else if(option = 2) printf(你选择了最坏适应算法，下面进行算法的模拟n); break; else if(option = 3)exit(0);else printf(错误：请输入 0/1nn); / 模拟动态分区分配算法 while(1) printf(n); printf(*n); printf( 1: 分配内存n 2: 回收内存n 3: 返回上一级菜单n 0: 退出 nn); printf(*n); scanf(%d, &ope);system(cls); if(ope = 0) break; if(ope = 1) / 模拟分配内存 printf(请输入作业号： ); scanf(%d, &taskId); printf(请输入需要分配的内存大小(KB)： ); scanf(%d, &size); if(size 0) / 父进程继续创建子进程p2； while (p2 = fork () = -1); if (p2 0) / 父进程 / 设置信号处理方式，依照参数signum指定的信号编号设置处理函数； / 指定信号到达时跳转到参数handler指定的函数执行； / 返回值：成功：返回先前信号处理函数指针；出错：SIG_ERR(-1)； signal (SIGINT, func_father); wait (0);/ 等待子进程1结束 wait (0);/ 等待子进程2结束 printf (Parent process is killed!n); exit (0); else/ 子进程p2 signal (SIGINT, SIG_IGN);/ 忽略本应给父进程的按键中断； signal (SIGUSR2, func_p2); / 接收父进程的消息后转到处理函数； k = 0; while (k = 0);/ 等待子进程2收到父进程的消息后置k=1 printf (Child Process 2 is Killed by Parent!n); exit(0); else/ 子进程p1 signal (SIGINT, SIG_IGN); / 忽略本应给父进程的按键中断； signal (SIGUSR1, func_p1); / 接收父进程的消息后转到处理函数； k = 0; while (k = 0);/ 等待子进程1收到父进程的消息后置k=1 printf (Child Process 1 is Killed by Parent!n); exit(0); return 0;16 运行结果及分析当按下Ctrl + C后，产生消息响应。17 心得体会通过本次实验，掌握了如何创建进程以及进程的软中断。题目2 进程的管道通信21 题目的主要研究内容及预期达到的目标实现进程的管道通信。22 题目研究的工作基础或实验条件（1）硬件环境：Linux平台。（2）软件环境：标准C语言。23 设计思想使用系统调用pipe()建立一条管道线;两个子进程P1和P2分别向管道各写一句话： Message from Child l! Message from Child 2! 父进程从管道中读出来自于两个子进程的信息,显示在屏幕上。 要求父进程先接收子进程P1的消息,再接收子进程P2的消息。24 流程图25 主要程序代码#include #include #include int pid1,pid2;/ pid_t pid1,pid2; main( ) int fd2; / 打开文件的文件描述符数组fd0读，fd1写； char outpipe100,inpipe100; pipe (fd); / 先创建管道，再创建子进程 while (pid1 = fork( ) = -1); / fork () = -1创建子进程失败 if (pid1 = 0) / Child1 lockf (fd1,1, 0); / 建立互斥文件锁 sprintf (outpipe,Message from Child l !); / 把串放入数组outpipe中 write (fd1, outpipe, 50); / 把outpipe所指内存写