操作系统课程设计-模拟设计页式存储管理的分配与回收

操作系统课程设计报告——页式存储姓名：***班级：J计算机1302学号：**********指导老师：***日期：2016/1/12一、目的和要求1.理解页式存储的基本概念2.通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

3. 3.根据模拟的页式管理设计，掌握在页式存储管理中最基本的两种种页面调度算法FIFO、LRU。

但在两种种算法中均要求在调度程序中产生的页面序列是随机产生的，而不是人为的输入，在执行时只需改变页面的大小及内存容量就可以得到不同的页面序列，另外还需要说明随机的性能和其性能可能对算法的影响，并对随机性要有一定的参数控制能力。

此外，计算并输出FIFO、LRU算法在不同内存容量下的命中率。

具体参数：访问串的长度，访问串，页面个数。

分别用2种不同的方法实现页面的置换，并输出相关信息。

二、基本原理1.页式存储基本原理将各进程的虚拟空间划分成若干个长度相等的页(page)，页式管理把内存空间按页的大小划分成片或者页面（page frame），然后把页式虚拟地址与内存地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。

页式管理采用请求调页或预调页技术实现了内外存储器的统一管理。

页的划分：2.静态/虚拟分页管理页式管理是一种内存空间存储管理的技术，页式管理分为静态分页管理和虚拟分页管理。

①静态页式存储管理：用户在作业开始执行之前，讲改作业的程序和数据全部装入到主存中，然后，操作系统统通过页表和硬件地址变换实现逻辑地址到屋里地址的转换，从而执行用户程序。

静态分页管理的第一步是为要求内存的作业或进程分配足够的页面。

系统通过存储页面表、请求表以及页表来完成内存的分配工作。

页表：内存中的一块固定存储区。

页式管理时每个进程至少有一个页表。

请求表：用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置；存储页面表：整个系统有一个存储页面表，其描述了物理存储空间的分配使用状况。

内存的动态存储管理一、实验内容编写程序实现动态分区存储管理方式的主存分配与回收。

具体内容包括：首先确定主存空间分配表；然后采用最先适应算法完成主存空间的分配与回收；最后编写主函数对所做工作进行测试二、实验原理模拟存储管理中内存空间的管理和分配内存空间的管理分为固定分区管理方式，可变分区管理方式，页式存储管理，段式存储管理。

题目：模拟内存分配与回收三、实验步骤（或过程）在Microsoft Visual C++ 6.0环境下运行1．设计一个空闲分区表，空闲分区表通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲分区低端的空间。

2．设计一个内存分区表，可用链表管理，用以表示当前以内存使用情况。

3．设计一个进程申请队列以及进程完成后的释放顺序，实现主存的分配和回收。

4．要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。

最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。

检查空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，小于。

若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否有“大于”的情况代码实现如下：#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define n 64 //定义内存的大小int a[n],count=0;//数组a用来保存内存使用状况1为已分配0为未分配，count用来记name数组中元素个数char name[n];//已分配内存的名称（字符类型）typedef struct linknode{char pid;int start;int length;struct linknode *left,*right;}de_node; //进程节点结构体定义//head1表示未分配内存队列头指针，head2便是已分配进程队列头指针de_node *head1,*head2=NULL;struct linknode* creat()//创建一个进程节点{int len,flag1=1;//用于表示进程是否可以创建char id;struct linknode* p;p = (de_node *)malloc(sizeof(de_node));//试图在系统内存中开辟空间创建一个进程 if (p==NULL) //p为空，说明系统没有可用内存用于创建此模拟进程{ printf("系统没有足够的内存可供使用！\n");//输出return(NULL);//返回空指针}printf("请输入进程id(字符类型)和长度:");//为进程输入id和分配的长度scanf("%c %d",&id,&len);fflush(stdin);//清除输入缓存if((id>='a'&&id<='z'||id>='A'&&id<='Z')&&(len>0)){for(int i=0;i<count;i++)//判断输入的进程名，如果已使用，返回空指针，并释放p指针if(name[i]==id){printf("此名称进程已存在！！");flag1=0;//标志位为0，表示下面对p指向内容不做修改free(p);return NULL;}if(len==0) {//如果输入要分配的进程长度为0，释放p,返回空指针printf("输入长度为0！\n");free(p);return(NULL);}if(flag1){//标志位1，可以对p指向内容进行修改p->pid=id; //idp->start=0; //初始开始内存位置，在以后会修改p->length=len;//长度p->left=NULL;//左指针p->right=NULL;//右指针name[count++]=id;//将id存入数组，count自加return(p);}//返回创建的进程的地址}else {printf("输入进程格式有误\n");free(p);return (NULL);}}//分配内存空间void distribute(de_node *p){ de_node *q=head1,*temp;int flag=0;do{//do_while循法//判断当前指向的内存空间的长度是否满足p所申请的长度,大于就分配if(q->length>=p->length) {p->start=q->start;//把进程的内存开始地址指向内存的可用开始地址处q->start+=p->length;//可用地址起始改变q->length-=p->length;//可用内存长度修改for(int i=p->start;i<p->start+p->length;i++)//将已分配的内存空间全部置1 a[i]=1;flag=1;//表示内存可分配//队列不止一个进程，第一个满足条件，并且刚好分配完，修改指针指向if(q->length==0&&q->right!=q){ if(q==head1)//如果第一个满足，修改头指针指向head1=q->right;q->left->right=q->right;q->right->left=q->left;free(q);//把这个已分配完的空间指针释放}}if(flag==1)//已做完处理直接跳出循环break;if(flag==0)//当前指向的内存不满足，指向下一个，继续判断是否满足q=q->right;}while(q!=head1);//搜索一遍可用内存序列if(flag==0){//没有可用的内存printf("没有满足的内存！\n");count--;//由于创建时加1，但在分配内存时失败，把1又减掉free(p);//把这个未分配到内存的进程释放}if(flag==1){//表示上面已分配好内存，并已修改内存链表，下面修改已分配内存的进程队列temp=head2;//把已分配内存的进程队列赋值给临时指针if(temp==NULL)//如果还还没有存在的任何的进程，说明当前是第一个{ head2=p;//让头指针指向第一个进程p->left=p;//双向队列第一个左右指针都指向自己p->right=p;//双向队列第一个左右指针都指向自己}else if(temp!=NULL){//已存在队列，把当前直接链到第一个，与上面的区别是指针指向 head2=p;//让头指针指向p指向的进程p->left=temp->left;//p进程左边为原来第一个的左边p->right=temp;//p进程右边指向第一个temp->left->right=p;//原来第一个的左边为ptemp->left=p;//原来第一个的左边的进程为p}}}//对进程的回收void reclaim(){ char id;int flag=0;de_node *q=head2,*p=head1;if(head2==NULL)//表示当前没有进程{ printf("已没有进程！\n");}else {//已分配内存队列如果不为空printf("输入要回收的进程id：");//输入要回收进程的idscanf("%c",&id);fflush(stdin);for(int i=0;i<count;i++)//双重循环把要回收的进程找出来，并把记录的id去掉 if(name[i]==id){//判断当前的进程是否满足要求for(int j=i;j<count;j++)name[j]=name[j+1];//向前覆盖name[j+1]=NULL;//置空count--;//减一}//判断是否总共只有一个进程且是够刚好也满足条件if(q->pid==id&&q->right==q&&head2==q){ head2=NULL;//把已分配队列直接置空flag=1;//表示找到满足条件的进程}if(flag==0){//上面的都没找到do{if(q->pid==id){//如果找到if(q==head2)head2=q->right;q->left->right=q->right;//修改指针指向q->right->left=q->left;flag=1;break;}else q=q->right;}while(q!=head2);}//如果找到或是遍历一遍结束if(flag==0) printf("没有此进程号！！！\n");//没有找到满足的进程if(flag==1){//表示找到了for(int i=q->start;i<q->start+q->length;i++)//释放占有的内存a[i]=0;//接下来修改可用内存的队列，while(q->start>p->start&&p->right!=head1){//从第一个开始找到回收回来的内存开始地址大的那个队列p=p->right;}if(p==head1)//表示比第一个的开始还小，那么就要修改头地址head1=q;//其他情况不用修改头地址，只需找到应该的位置，把此进程插进去 q->left=p->left;//修改指针的指向q->right=p;p->left->right=q;p->left=q;if(q->start+q->length==p->start)//可以与后面合并的情况{ q->length+=p->length;//修改指针的指向p->right->left=q;q->right=p->right;free(p);}if(q->left->start+q->left->length==q->start)//可以与前面合并的情况{ q->left->length+=q->length;//修改指针的指向q->left->right=q->right;q->right->left=q->left;free(q);}}}}//打印输出void print(){ de_node *q=head2,*p=head1;if(count==0)printf("没有进程占有内存。

学号：28课程设计模拟设计页式存储管理的分题目配与回收学院计算机科学与技术专业计算机科学与技术班级XX姓名XX指导教师XXX2011年01月09日课程设计任务书学生姓名： XX 专业班级：计算机0902班指导教师： XXX 工作单位：计算机科学与技术学院题目: 模拟设计页式存储管理的分配与回收初始条件：1．预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会页式管理内存的分配和回收过程。

2．实践准备：掌握一种计算机高级语言的使用。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．采用页式管理方案实施内存分配和回收。

能够处理以下的情形⑴能够输入给定的内存页面数，页面大小，进程的个数及每个进程的页数。

⑵要求当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后内存空间的使用情况（被进程占用的页面，空闲的页面）。

2．设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。

时间安排：设计安排一周：周1、周2：完成程序分析及设计。

周2、周3：完成程序调试及测试。

周4、周5：验收，撰写课程设计报告。

（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日武汉理工大学《操作系统》课程设计说明书模拟设计页式存储管理的分配与回收1需求分析页式管理是一种内存空间存储管理的技术，页式管理分为静态页式管理和动态页式管理。

操作系统课程设计内存管理一、课程目标知识目标：1. 理解内存管理的基本概念，掌握内存分配、回收的原理及方法；2. 掌握虚拟内存的原理，了解分页、分段等内存管理技术；3. 了解操作系统中内存保护、共享、碎片处理等相关问题。

技能目标：1. 能够运用所学知识，分析并设计简单的内存管理算法；2. 能够通过编程实践，实现基本的内存分配与回收功能；3. 能够运用虚拟内存技术，解决实际问题。

情感态度价值观目标：1. 培养学生对操作系统中内存管理知识的学习兴趣，激发学生主动探索精神；2. 培养学生的团队协作意识，学会与他人共同解决问题；3. 增强学生的信息安全意识，了解内存管理在操作系统安全中的重要性。

课程性质分析：本课程为操作系统课程设计的一部分，侧重于内存管理方面的知识。

内存管理是操作系统核心功能之一，对于提高系统性能、保障系统安全具有重要意义。

学生特点分析：学生为计算机科学与技术等相关专业的高年级本科生，具备一定的操作系统基础知识，具备一定的编程能力，但可能对内存管理的深入了解和应用尚有不足。

教学要求：1. 结合实际案例，深入浅出地讲解内存管理的基本原理和方法；2. 采用任务驱动法，引导学生通过实践，掌握内存管理技术；3. 注重培养学生的动手能力和创新能力，提高学生解决实际问题的能力。

二、教学内容1. 内存管理概述：介绍内存管理的基本概念、任务和目标；- 教材章节：第2章 内存管理概述- 内容：内存分配、回收原理，内存保护、共享机制。

2. 内存管理技术：讲解物理内存管理和虚拟内存管理技术；- 教材章节：第3章 内存管理技术- 内容：分页管理、分段管理、段页式管理，内存碎片处理。

3. 内存管理算法：分析常见的内存分配和回收算法；- 教材章节：第4章 内存管理算法- 内容：首次适应算法、最佳适应算法、最坏适应算法等。

4. 操作系统内存管理实例分析：结合具体操作系统，分析其内存管理实现；- 教材章节：第5章 操作系统内存管理实例- 内容：Linux内存管理、Windows内存管理。

模拟实现操作系统内存分配与回收的算法背景概述随着计算机技术的不断发展，操作系统在计算机领域中的地位日益凸显。

操作系统作为计算机系统的核心，负责管理硬件资源，包括内存。

内存管理是操作系统的重要任务之一，它涉及到如何有效地分配和回收内存，以满足程序和系统的需求。

在操作系统中，内存管理通常通过虚拟内存和物理内存来实现。

虚拟内存通过地址空间映射将逻辑地址转换为物理地址，以便用户程序可以使用抽象的地址空间来访问物理内存。

物理内存则涉及到实际的物理存储设备的分配和管理。

操作系统中实现内存分配与回收的算法主要依赖于动态内存分配（Dynamic Memory Allocation）机制。

动态内存分配是一种在运行时分配和释放内存的方法，它是操作系统和许多高级编程语言的核心组件。

动态内存分配需要处理的问题包括内存碎片化、内存泄漏和溢出等。

为了解决这些问题，操作系统通常使用一种称为“分页”或“分段”的虚拟内存技术，将物理内存划分为固定大小的页或段，并在需要时进行页面置换或段替换。

本文将介绍一种模拟实现操作系统内存分配与回收的算法背景概述。

我们将从以下几个方面进行阐述：虚拟内存和物理内存的基本概念、动态内存分配机制、页面置换算法以及内存回收策略。

首先，虚拟内存和物理内存是操作系统中处理内存分配和回收的基本概念。

虚拟内存通过地址空间映射将程序的逻辑地址转换为物理地址，以实现抽象的地址空间访问物理内存。

这样可以隐藏物理内存的复杂性，并为程序员提供一种简单的方式来管理内存。

物理内存则是指实际的物理存储设备，如RAM、硬盘等。

动态内存分配是操作系统中实现内存管理的关键技术之一。

它允许程序在运行时请求和释放内存，避免了静态内存分配的局限性，如静态分配的内存不能重复使用，需要手动释放等。

动态内存分配通常使用数据结构如链表、哈希表等来跟踪分配的内存块，并使用垃圾收集机制来自动回收不再使用的内存。

页面置换算法是操作系统中实现动态内存分配的核心技术之一。

存档资料成绩：华东交通大学理工学院课程设计报告书所属课程名称计算机操作系统题目主存空间的分配与回收分院电信分院专业班级计算机科学与技术（1）班学号学生姓名指导教师2012 年 6 月20 日目录第1章课程设计内容及要求. (3)第2章需求分析 (4)第3章概要设计 (5)第4章详细设计 (8)第5章调试分析与测试结果 (11)第6章课程设计心得 (16)第7章参考文献 (17)附录 (18)第一章课程设计内容及要求1.1 课程设计的目的通过该课程设计使学生理解在不同的存储管理方式下，以及使学生加深对如何实现主存空间的分配与回收原理的理解。

也使学生初步具有研究、设计、编制和调试操作系统模块的能力。

1.2 课程设计内容主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机的性能。

通过本次实验可以帮助理解主存空间的分配与回收的几种算法：①掌握最先适应分配算法；②掌握最优适应分配算法；③掌握最坏适应分配算法。

第二章需求分析2.1 软件及硬件需求适用于现在各种计算机，建议内存不少于128M。

开发环境：VMware虚拟机软件，ubuntu 11.10系统，Gcc编译器。

2.2 设计需求内存的分配与回收是内存管理的主要功能之一。

无论采取哪一种管理和控制方式，能否把外存中的数据和程序调入内存，取决于内否在内存中为他们安排合适的位置。

因此，存储管理模块要为每一个并发执行的进程分配内存空间。

另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。

但由于作业大大小不一，所以系统为作业分配内存大小不一，在释放时造成系统资源的浪费。

因此，采取首次适应算法，以及那少内存的浪费。

第三章概要设计3.1 设计思想初始化系统的内存分区说明表；输入当前作业或进程的使用内存情况，检索系统内的内存分区说明表，判断是否可分配，也就是查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。

实验二存储管理动态分区分配及回收算法一、实验目的通过分区管理实验，了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。

通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类操作系统，并懂得在操作系统的支持下建立自己的应用系统。

二、实验要求本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并掌握分配算法的特点，提高编程技巧和对算法的理解和掌握。

三、实验过程1．准备（一）主程序1、定义分区描述器node，包括 3个元素：（1）adr——分区首地址（2）size——分区大小（3）next——指向下一个分区的指针2、定义 3个指向node结构的指针变量：（1）head1——空闲区队列首指针（2）back1——指向释放区node结构的指针（3）assign——指向申请的内存分区node结构的指针3、定义 1个整形变量：free——用户申请存储区的大小（由用户键入）（二）过程1、定义check过程，用于检查指定的释放块（由用户键入）的合法性2、定义assignment1过程，实现First Fit Algorithm3、定义assignment2过程，实现Best Fit Algorithm4、定义acceptment1过程，实现First Fit Algorithm的回收算法5、定义acceptment2过程，实现Best Fit Algorithm的回收算法6、定义print过程，打印空闲区队列（三）执行程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。

（四）输出要求每执行一次，输出一次空闲区队列情况，内容包括：编号首址终址大小2.主要流程和源代码实验二源代码#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 32767typedef struct node {int id;int adr;int size;struct node *next;}Node;Node *head1,*head2,*back1,*back2,*assign;int request;int check(int add,int siz,char c){Node *p,*head;int check=1;if(add<0||siz<0)check=0;/*地址和大小不能为负*/if(c=='f'||c=='F')head=head1;elsehead=head2;p=head->next;while((p!=NULL)&&check)if(((add<p->adr)&&(add+siz>p->adr))||((add>=p->adr)&&(add<p->adr+p->size))) check=0;elsep=p->next;if(check==0)printf("\t输入释放区地址或大小有错误！！！\n");return check;}void init(){Node *p;head1=(Node*)malloc(sizeof(Node));head2=(Node*)malloc(sizeof(Node));p=(Node*)malloc(sizeof(Node));head1->next=p;head2->next=p;p->size=MAX_SIZE;p->adr=0;p->next=NULL;p->id=0;}Node* assignment1(int num,int req){Node *before,*after,*ass;ass=(Node*)malloc(sizeof(Node));before=head1;after=head1->next;ass->id=num;ass->size=req;while(after->size<req){before=before->next;after=after->next;}if(after==NULL){ass->adr=-1; }else{if(after->size==req){before->next=after->next;ass->adr=after->adr;}else{after->size-=req;ass->adr=after->adr;after->adr+=req;}}return ass;}void acceptment1(int address,int siz,int rd){Node *before,*after;int insert=0;back1=(Node*)malloc(sizeof(Node));before=head1;after=head1->next;back1->adr=address;back1->size=siz;back1->id=rd;back1->next=NULL;while(!insert&&after){//将要被回收的分区插入空闲区（按首址大小从小到大插入）if((after==NULL)||((back1->adr<=after->adr)&&(back1->adr>=before->adr))) {before->next=back1;back1->next=after;insert=1;}else{before=before->next;after=after->next;}}if(insert){if(back1->adr==before->adr+before->size){//和前边分区合并before->size+=back1->size;before->next=back1->next;free(back1);}else if(after&&back1->adr+back1->size==after->adr){//和后边分区合并back1->size+=after->size;back1->next=after->next;back1->id=after->id;free(after);after=back1;}printf("\t首先分配算法回收内存成功！\n");}elseprintf("\t首先分配算法回收内存失败！\n");}Node* assignment2(int num,int req){Node *before,*after,*ass,*q;ass=(Node*)malloc(sizeof(Node));q=(Node*)malloc(sizeof(Node));before=head2;after=head2->next;ass->id=num;ass->size=req;while(after->size<req){before=before->next;after=after->next;}if(after==NULL){ass->adr=-1;}else{if(after->size==req){before->next=after->next;ass->adr=after->adr;}else{q=after;before->next=after->next;ass->adr=q->adr;q->size-=req;q->adr+=req;before=head2;after=head2->next;if(after==NULL){before->next=q;q->next=NULL;}else{while((after->size)<(q->size)){before=before->next;after=after->next;}before->next=q;q->next=after;}}}return (ass);}void acceptment2(int address,int siz,int rd) {Node *before,*after;int insert=0;back2=(Node*)malloc(sizeof(Node)); before=head2;after=head2->next;back2->adr=address;back2->size=siz;back2->id=rd;back2->next=NULL;if(head2->next==NULL){//空闲队列为空head2->next=back2;head2->size=back2->size;}else{//空闲队列不为空while(after){if(back2->adr==after->adr+after->size) {//和前边空闲分区合并before->next=after->next;after->size+=back2->size;back2=after;}else{before=before->next;after=after->next;}}before=head2;after=head2->next;while(after){if(after->adr==back2->adr+back2->size) {//和后边空闲区合并before->next=after->next;back2->size+=after->size;}else{before=before->next;after=after->next;}}before=head2;after=head2->next;while(!insert){//将被回收的块插入到恰当的位置（按分区大小从小到大）if(after==NULL||((after->size>back2->size)&&(before->size<back2->size))) {before->next=back2;back2->next=after;insert=1;break;}else{before=before->next;after=after->next;}}}if(insert)printf("\t最佳适应算法回收内存成功！\n");elseprintf("\t最佳适应算法回收内存失败！！\n");}void print(char choice)//输出空闲区队列信息{Node *p;if(choice=='f'||choice=='F')p=head1->next;elsep=head2->next;if(p){printf("\n空闲区队列的情况为：\n");printf("\t编号\t首址\t终址\t大小\n");while(p){printf("\t%d\t%d\t%d\t%d\n",p->id,p->adr,p->adr+p->size-1,p->size);p=p->next;}}}void menu()//菜单及主要过程{char chose;int ch,num,r,add,rd;while(1){system("cls");printf("选择最先适应算法请输入F，选择最佳适应算法请输入B，退出程序请输入E\n\n"); printf("请输入你的选择:");scanf("%c",&chose);if(chose=='e'||chose=='E')exit(0);else{system("cls");while(1){if(chose=='f'||chose=='F')printf("最先适应算法(First-Fit)模拟:\n");if(chose=='b'||chose=='B')printf("最佳适应算法(Best-Fit)模拟:\n");printf("1.分配内存,2.回收内存,3.查看内存,4.返回\n\n");printf("请输入你的选择:");scanf("%d",&ch);fflush(stdin);switch(ch){case 1:printf("输入申请的分区大小：");scanf("%d",&r);if(chose=='f'||chose=='F')assign=assignment1(num,r);elseassign=assignment2(num,r);if(assign->adr==-1){printf("分配内存失败！\n");}elseprintf("分配成功！分配的内存的首址为:%d\n",assign->adr);break;case 2:printf("输入释放的内存的首址：");scanf("%d",&add);printf("输入释放的内存的大小：");scanf("%d",&r);printf("输入释放的内存的编号：");scanf("%d",&rd);if(check(add,r,chose)) {if(chose=='f'||chose=='F') acceptment1(add,r,rd); elseacceptment2(add,r,rd);}break;case 3:print(chose);break;case 4:menu();break;}}}}}void main()//主函数{init();menu();}四、实验结果五、实验总结通过这次课程设计我练习了用C语言写系统软件，对操作系统中可变分区存储管理有了更深刻的了解。

实习四 主存储器空间的分配和回收一，实习题目本实习模拟在两种存储管理方式下的主存分配和回收。

第一题：在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。

[提示]：可变分区方式是按作业需要的主存空间大小来分割分区的。

当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，假设有，则按需要量分割一个分区分配给该作业；假设无，则作业不能装入。

随着作业的装入、撤离，主存空间被分成许多个分区，有为了 说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：第一栏 第二栏其中，起址——指出一个空闲区的主存起始地址。

长度——指出从起始地址开始的一个连续空闲的长度。

状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白〔无效〕，可用来登记新的空闲区〔例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态〕。

由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。

上述的这张说明表的登记情况是按提示〔1〕中的例所装入的三个作业占用的主存区域后填写的。

(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。

有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。

为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。

为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。

为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

(3) 采用最先适应算法〔顺序分配算法〕分配主存空间。

按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。

操作系统实验报告存储器的分配与回收算法实现姓名：学号：班级：.一、实验名称及要求1、实验名称：存储器的分配与回收算法实现2、实验要求：学生应正确地设计有关的数据结构与各个功能模块，画出程序的流程图，编写程序，程序执行结果应正确。

3、实验方式：学生通过实验室的微机上机，实际调试程序。

4、实验环境：Windows操作系统环境下的个人微机Ｃ或Ｃ＋＋程序设计语言二、实验内容1本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。

2采用最先适应法、最佳适应法、最坏适应法分配主存空间。

3当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。

若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。

4当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。

5运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。

三、实验程序#include <iostream.h>#include <malloc.h>#include <stdlib.h>typedef struct FreeLink{//定义自由链struct FreeLink *prior;char name;int start;int size;.bool flag;struct FreeLink *next;}* ptr,*head;head top;ptr p;void print(){//将内存分配情况打印到屏幕上p=top;cout<<"************************内存分配情况表************************"<<endl;cout<<"区号\t\t"<<"起始位置\t"<<"区间长度\t"<<"区间状态\t"<<endl;do{cout<<p->name<<"\t\t"<<p->start<<"\t\t"<<p->size<<"\t\t";if(p->flag==false){cout<<"空闲"<<endl;}else{cout<<"已占用"<<endl;}p=p->next;}while(p!=NULL);}void clear(){//结束操作时清空“内存”以备其他操作do{p=top;top=top->next;free(p);}while(top!=NULL);}void asc(ptr &p){//最佳适应法的内存分配函数int min;ptr op;FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink));cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;min=256;fl->flag=true;do{if(p->flag==false&&p->size<=min&&p->size>=fl->size){ min=p->size;op=p;}p=p->next;}while(p!=NULL);if(op->size>fl->size){fl->start=op->start;op->start=fl->start+fl->size;op->size=op->size-fl->size;fl->next=op;fl->prior=op->prior;op->prior->next=fl;op->prior=fl;goto flag1;}if(op->size==fl->size){op->flag=fl->flag;op->name=fl->name;free(fl);goto flag1;}cout<<"内存过小，分配失败！"<<endl;goto flag2;flag1: cout<<"分配成功！"<<endl;flag2: ;}void dec(ptr &p){//最坏适应法的内存分配函数int max;ptr op;FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink));cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;max=fl->size;fl->flag=true;do{if(p->flag==false&&p->size>=max){max=p->size;op=p;}p=p->next;}while(p!=NULL);if(op->size>fl->size){fl->start=op->start;op->start=fl->start+fl->size;op->size=op->size-fl->size;fl->next=op;fl->prior=op->prior;op->prior->next=fl;op->prior=fl;goto flag3;}if(op->size==fl->size){op->flag=fl->flag;op->name=fl->name;free(fl);goto flag3;}cout<<"内存过小，分配失败！"<<endl;goto flag4;flag3: cout<<"分配成功！"<<endl;flag4: ;}void splice(ptr &p){//若被操作的内存有相邻空闲区则将空闲区拼接合并int x;if(p->prior->flag==false&&p->next->flag==false)x=1;if((p->prior->flag==false&&p->next->flag==true)||(p->prior->flag==false&& p->next==NULL))x=2;if((p->prior->flag==true&&p->next->flag==false)||(p->prior==NULL&&p->next ->flag==false))x=3;if((p->prior->flag==true&&p->next->flag==true)||(p->prior==NULL&&p->next->flag==true)||(p->prior->flag==true&&p->next==NULL))x=4;switch(x){case 1:p->next->prior=p->prior;p->prior->next=p->next;p->prior->size=p->prior->size+p->size+p->next->size;p->prior->next=p->next->next;if(p->next->next!=NULL)p->next->next->prior=p->next->prior;free(p->next);free(p);break;case 2:if(p->next==NULL){p->prior->next=p->next;}else{p->next->prior=p->prior;p->prior->next=p->next;}p->prior->size=p->prior->size+p->size;free(p);break;case 3:if(p->prior==NULL){top=p->next;p->next->prior=NULL;p->next->start=p->start;p->next->size=p->next->size+p->size;}else{p->next->prior=p->prior;p->prior->next=p->next;p->next->start=p->start;p->next->size=p->next->size+p->size;}free(p);break;case 4:p->name='@';p->flag=false;break;}}void allocate(ptr &p){//最先适应法的内存分配函数FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink));cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;fl->flag=true;do{if(p->flag==false&&p->size>fl->size){fl->start=p->start;p->start=fl->start+fl->size;p->size=p->size-fl->size;fl->next=p;fl->prior=p->prior;p->prior->next=fl;p->prior=fl;goto a;}if(p->flag==false&&p->size==fl->size){p->flag=fl->flag;p->name=fl->name;free(fl);goto a;}p=p->next;}while(p!=NULL);cout<<"内存过小，分配失败！"<<endl;goto b;a: cout<<"分配成功！"<<endl;b: ;}void recover(ptr &p){//内存回收函数char n = ' ';cout<<"请输入要回收的内存对应的进程名";cin>>n;do{if(p->flag==true&&p->name==n){splice(p);goto c;}p=p->next;}while(p!=NULL);cout<<"内存并未分配给对应进程，回收失败！"<<endl;goto d; c: cout<<"内存回收成功！"<<endl;d: ;}int ffa(){//最先适应法char choice=' ';print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink));pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl; goto f;e: cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl; f: cin>>pcb->size;if(pcb->size>256) goto e;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true){do{p=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case '1':allocate(p);print();break;case '2':recover(p);print();break;case '3':clear();return 0;break;}}}int bfa(){//最佳适应法char choice=' ';print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink));pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl; goto h;g: cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl; h: cin>>pcb->size;if(pcb->size>256) goto g;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true){do{p=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case '1':asc(p);print();break;case '2':recover(p);print();break;case '3':clear();return 0;break;}}}int wfa(){//最坏适应法char choice=' ';print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink));pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl; goto j;i: cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl; j: cin>>pcb->size;if(pcb->size>256) goto i;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true){do{p=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case '1':dec(p);print();break;case '2':recover(p);print();break;case '3':clear();return 0;break;}}}int main(){//主函数char choice = ' ';ptr free=(FreeLink *)malloc(sizeof(FreeLink));top=free;top->name='@';top->start=0;top->size=256;top->flag=false;top->prior=NULL;top->next=NULL;cout<<"***************Memory allocation and recovery algorithm***************"<<endl;cout<<"************************存储器的分配与回收算法************************"<<endl;while(true){do{cout<<"请从下列选项中进行选择"<<endl;cout<<"1.最先适应算法"<<endl;cout<<"2.最优适应算法"<<endl;cout<<"3.最坏适应算法"<<endl;cout<<"4.退出"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3'&&choice!='4');switch(choice){case '1':ffa();break;case '2':bfa();break;case '3':wfa();break;case '4':return 0;break;}}}四、实验结果最先适应法最佳适应法最坏适应法五．实验总结知道了存储器的分配与回收算法实现方法，采用最先适应法、最佳适应法、最坏适应法分配主存空间。