2023年主存空间的分配与回收实验报告.pdf

实 验 报 告课程名称：操作系统实验名称：主存空间的分派与回收学8 号：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _学生姓名：_ _ _ _ _ _ _ _ _王钊_ _ _ _ _ _ _ _ _ _ _班，级：信管1 10 1班指导教师:吴联世实验日期：2 0 2 3 年 1 2 月 5日1、实验目的：熟悉主存的分派与回收。理解在不同的存储管理方式下,如何实现主存空间的分派与回收。掌握动态分区分派方式中的数据结构和分派算法及动态分区存储管理方式及其实现过程。2、实验规定实验规定使用可变分区存储管理方式,分区分派中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分派中所用的算法采用初次适应算法、循环初次适应算法、最佳适应算法三种算法来实现主存的分派与回收。同时，规定设计一个实用和谐的用户界面，并显示分派与回收的过程。3、实验环境硬件：CPU：AMD QL6 4内存:2G B显卡:ATI 4 57 0 硬盘：日立250G软件：Windows 2 0 2 3/XP。开发工具：VC+6.0。4、实验内容1）实现原理主存的分派和回收的实现是与主存储器的管理方式有关的。所谓分派,就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运营完毕时将作业或进程所占的主存空间归还给系统。可变分区管理是指在解决作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间,若有,则按需要量分割一个分区分派给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完毕，主存空间被提成许多大大小小的分区,有的分区被作业占用，而有的分区是空闲的。为了说明那些分区是空闲的,例如：可以用来装入新作业,必须有一张空闲说明表长度一一指出从起始地址开始的一个连续空闲的长度。状态一一有两种状态,一种是“未分派”状态，指出相应的由起址指出的某个长度的区域是空闲区；另一 种 是“空表目”状态，表达表中相应的登记项目是 空 白（无效），可用来登记新的空闲区（例如，作业完毕后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则导致表格“溢出”无法登记。2、当有一个新作业规定装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区也许大于作业需要量，这时应把本来的空闲区变成两部分:一部分分给作业占用；另一部分又成为一个较小的空闲区，留在空闲区表中。为了尽量减少由于分割导致的空闲区，尽也许分派低地址部分的空闲区,而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序从低到高登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总 是 让“空表目”项留在表格的后部。3、采用最先适应算法（顺序分派算法）分派主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足规定的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分派，所以把主存区分派给作业后并不实际启动装入程序装入作业，而用输出“分派情况”来代替。4、当一个作业执行完毕撤离时，作业所占的分区应当归还给系统，归还的分区假如与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在上述中列举的情况下，假如作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。2）程序结构（流程图）初次适应分派模拟算法主存回收算法3）实现环节实现动态分区的分派与回收,重要考虑三个问题:第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分派算法；第三，在设计的数据表格基础上设计主存回收算法。1.设计记录主存使用情况的数据表格由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分派和回收变动。总之,所有分区情况随时也许发生变化,数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应当涉及分区在主存中的起始地址和长度。由于分派时，空闲区有时会变成两个分区：空 闲 区 和 已 分 分 区，回收主存分区时，也许会合并空闲区，这样假如整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分派时查找空闲区进行分配，然后填写已分派区表，重要操作在空闲区；某个作业执行完后，将该分区贬词空闲区，并将其与相邻的空闲区合并，重要操作也在空闲区。由此可见，主存的分配与回收重要时对空闲区的操作。这样为了便于对主存空间的分派与回收,就建立两张分区表记录主存的使用情况：“已分派区表”记录作业占用分区，“空 闲 区 表”记录空闲区。这两张表的实现方法一般由两种：链表形式、顺序表形式。在本实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分派区表”还 是“空闲区表”都必须事先拟定长度。它们的长度必须是系统也许的最大项数，系统运营过程中才不会犯错，因此在多数情况下，无 论 是“已分派表区”还 是“空闲区表”都是空闲栏目。已分派区表中除了分区起始地址、长度外，也至少尚有一项“标志”，假如是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表除了分区起始地址、长度外，也要有一项“标志”，假如是空闲栏目，内容为“空”，假如为某 个空闲区的登记项，内 容 为“未分派”。在实际系统中，这两个表格的内容也许还要多，实验中仅仅使用上述必须的数据。为此，“已分派区表”和“空闲区表”在 实验中有如下的结构定义。已分派区表的定义：#d e f i n e n 1 0 假定系统允许的最大作业数量为ns t r u c t f l o a t a d d r e s s;floa t le ng t h;i n t fla g；已分分区起始地址已分分区长度，单位为字节已分派表区登记栏标志，用0表达空栏目,u s e d _t a b 1 e n；已分派区表空闲区表的定义:#d e fines t r u c tfloa ta d d r e s s；f l o at le ngt h；int f 1 a g；/假定系统允许的空闲区表最大为m空闲区起始地址/空闲区长度,单位为字节/空闲区表登记栏目用0表达空栏目，1表达未分派？f r e e _ t a b le m；/空闲区表其中分区起始地址和长度数值太大，超过了整形表达范围，所有采用floa t类型。2.在设计的表格上进行主存分派当要装入一个作业时，从空闲区表中查找标志为“未分派”的空闲区，从中找一个能容纳该作业的空闲区。假如找到的空闲区正好等于该作业的长度，则把该分区所有 分派给该作业。这时应当把该空闲区登记栏中的标志改为“空”，同时在已分派区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址、长 度和作业名。假如找到的空闲区大于作业长度，则把空闲区提成两部分，一部分用来装入作业，另一部分你仍然为空闲区，这时只要修改空闲区的长度，且把新装入的作业登记到已分派区表中。主存分派算法目前一般采用三种算法:初次适应算法、循环初次适应算法、最佳适应算法。本实验中采用最佳适应算法为作业分派主存。最佳适应算法会出现空闲分区分割后剩下的空闲分区很小以至于无法使用的情况，为了在一定限度上解决这个问题，假如空闲分区的大小比作业规定的长度略大一点，不再将空闲区分区分割成已分分区和空闲分区两部分，而是将整个空闲区分派给作业。在实现最佳适应算法时，可把空闲分区按长度递增方式登记在空闲区表中。分派时顺序查找空闲表,查找到的第一个空闲区就是满足作业规定的最小分区。这样查找速度快，但是为使空闲区按照长度递增登记在空闲表中，就必须在分派回收时进行空闲区的调整。空闲区表调整时移动标模的代价要高于查询整张表的代价,所以实验中不采用空闲区有序登记在空闲表中的方法。3 .动态分区方式下的主存回收动态分区方式下回收主存空间时应当检查是否有与归还区相邻的空闲区域。若有，则应当合并成一个空闲区。一个归还区也许有上邻空闲区，也也许有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区也无下邻空闲区。在实现回收时，一方面将作业归还的区域在已分派表中找到，将该栏目的状 态 变 为“空”，然后检查空闲区表中标志为“未分派”栏目，查找是否又相邻空闲区；最后合并空闲区,修改空闲区表。假定归还作业的分区起始地址为S,长度为L,则：1）归还区又下邻空闲区假 如S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址则表白归还区有一个下邻空闲区。这时候只需要修改第j栏登记项的内容：起 始 地 址=S ；第j栏长度=第j栏长度+L则第j栏指示的空闲区时归还区和下邻空闲区合并后的大空闲区。2）归还区又上邻空闲区假如空闲区表中某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S,则表白归还区有一个上邻空闲区。这时要修改第k栏登记项的内容（起始地址不变）：第k栏长度=第卜栏长度+L；于是第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区。3）归还区既有上邻空闲区又有下邻空闲区假如S +L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时尚有某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S,这表白归还区既有一个上邻空闲区又又一个下邻空闲区。此时对空闲区的修改如下：第k栏的长度=第k栏的长度+第j栏的长度+L；（第k栏的起始地址不变）第j栏的状态=空”（将 第j栏的登记项删除）这样，第k栏指示的空闲区是归还区和上、下邻空闲区合并后的大空闲区；本来的下邻空闲区登记项（第j栏）被 删 除 置 为“空二4）归还区既无上邻空闲区又无下邻空闲区假如在检查空闲区表时，无上述三种情况出现，则表白归还区既无上邻空闲区又无下邻空闲区。这时，应当在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则 第t栏的内容修改如下：第t栏起始地址=S;第t栏的长度=上第t栏的状态=未分派”；这样,第t栏指示的空闲区是归还区。由于是实验，没有真正的主存要分派，所有在实验中，一方面应建立一张空闲区表，初始状态只有一个空闲登记项（假定的主存空闲区）和一张所有状态都为“空”的已分派区表，假定主存空间1 0 0 K B,所有为空闲区（事实上操作系统需要占用一部分）；然后，可以选择进行主存分派或回收，假如是分派，规定输入作业名和所需主存空间大小；假如是回收，输入回收作业名；循环进行主存分派和回收后，假如需要，则显示两张表的内容，以检查主存的分派和回收是否对的。X-|4）实验测试及分析:#.息她.存信.酬存内LJ矗画业却的配作到业闲邠片的.化聚空己碎.始业成禽毒初当当用1234567用选择H7退出.-口 X请选择错误输入？J存X内的信筋存内1,J取您业咨的配.作闲餐化聚空已碎.始业成4盛刖塞初兀当当患1234s6?用选择1-7：2选择Y,可以自由选择进入分区的作业名。选择N,取消操作?(Y/N)：6、实验心得体会这次实验比较复杂,用了很多时间，但同时收获了很多，对主存空间分派结识加深了很多附录：源代码#in c lude#include#d efin e OK 1 /完毕#define ERROR 0/犯错typ e d e f i nt Status;typed e f s t ru c t f r ee_table定义一个空闲区说明表结构(i n tn u m;分区序号1 o n g a d dr e s s;起始地址lo n g 1 en g th;分区大小int sta t e;/分区状态ElemTy p e;t y pe d e f s t r u c t Node线性表的双向链表存储结构ElemType dat a;st r uct Node*p rio r；/前趋指针s truct N ode*n e xt；/后继指针No d e,*Li n k List；L i nkLis t firs t;头结点LinkLis t end;/尾结点i nt flag;/记录要删除的分区序号Stat us I ni t bio c k()开创带头结点的内存空间链表(first=(Lin k L i st)m a 1 1 o c(s i z eof(Node);e n d=(L i nkList)mall o c(s izeo f(Nod e);first pr i o r=N ULL；fi r st-nex t=e nd;end-prior=fi r st;en d-next=NU LL;end-d a t a.num=l;end-data.a dd r es s=40;en d-d ata.leng t h=600；en d-da t a.s t a t e=0;r eturn O K;)v o id sor t()分区序号重新排序N ode*p=f i rst-n e x t,*q;q=p next;f o r(；p!=NULL;p=p-n ext)f or(q=p-n e xt;q；q=q-ne x t)Q i f(p-data.num=q-d ata.num)(q-d a t a.num+=l;/显示主存分派情况v oid s h o w()i nt fl a g=0;用来记录分区序号Node*p=f i r st;p-data.num=0;p-d a t a.address=0;p d a ta.1 eng t h=40;p-d ata.st a te=l;so r t();pr i n t f(n t t 主存空间分派情况n”)；D r i ntf(u*nn”)；P r int f(分区序号t起始地址t分区大小 t 分区状态nn)；while(p)p rintf(d t t%d t t%d,p-d a t a.num,p-d a ta.a d dres s,p-d a ta.len g th);if(p-d a ta.s tate=O)p r i n t f(”tt 空闲 n n);e Ise p r intf(H t t 已分派 nn );p=p-n e x t；printf(*求*nnn);)/初次适应算法Status F i rst_ f it(in t request)(/为申请作业开辟新空间且初始化Node*p=first-next;Li n kLi s t temp=(Li n kL i st)mall o c(si z eof(N o d e);t emp-data.l e ngth=requ e s t;t e mp-da t a.st a te=l；p-d a ta .num=l;whi 1 e(p)i f(p-data.sta t e=0)&(p-d a t a.length=reque s t)/有大小恰好合适的空闲块p-dat a.s tate=1;ret u rn OK;b r e a k;)else i f(p-data.s t ate=O)&(p-data.leng t h reques t)有空闲块能满足需求且有剩余tem p-p r i o r=p-pr i or;temp-ne x t=p;tem p-d a ta.add r ess=p-d a ta.a d dress;t e m p-d a ta.num=p-d a t a.num；p-prior-nex t=tem p；p-p r io r=t em p;p-d a ta.a ddr e ss=t e mpda t a.a d dr e ss+t em p-data.Ie n gth;p-data.1 e ngth-=re q u e st;p-d a ta.n um+=l;re t u rn OK;br e a k；p=p-ne x t;)re t urn ERRO R;)/最佳适应算法St a t u s Be s n t reques t)int ch;/记录最小剩余空间Node*p=fir s t;Node*q=NULL;/记录最佳插入位置LinkLi s t t emp=(Lin k Lis t)mallo c(s i z e o f(N o d e);tem p-d at a.1 e n g th=r e q u e s t；tem p -data.s t ate=1;opd a t a.num=l;w h ile(p)初始化最小空间和最佳位置(i f(p d ata.state=O)&(p-d a ta.length=request)(i f(q=NULL)(q=p；c h=p-d a t a.1 en g th-requ e st;)e 1 se i f(qdata.l e n g th p-d a t a.1 e ngth)(q二 p；c h=p-dat a.length-requ e s t;)p=p-next;i f(q=NULL)retu r n ERRO R;/没有找到空闲块els e if(q-data.1 e ngth=requ e s t)q-data.s t a t e=1;r e t urn OK;)elsetemp-p rio r=q-prior;t emp-n ext=q;tem p-d a ta.ad d ress=q-data.a d d r e s s;tem p-data.num=q-data.num;q-prio r n ext=t e mp;q-p r io r=t emp;q-data.address+=reques t;q-da t a.1 eng t h=c h;q-d a ta.n um+=l；re t u r n OK;)re t u rn OK;)/最差适应算法Sta t us W o rst_ fit(int r equ e st)(in t c h；记录最大剩余空间Node*p=f i r s t-n ext;N o d e*q=N U LL;/记录最佳插入位置LinkLi s t temp=(Li n k L i st)m a I 1 oc(sizeof(N o de);temp-d a t a.le n g t h=reques t；t emp-data.s t a t e=1;0 p-d a ta.n um=1;while(p)/初始化最大空间和最佳位置i f(p-d ata.s tate=O&(p-dat a.1 ength=r e q u e st)|i f(q=NULL)(q=p;c h=p-data.length-r equ e s t;)else if(q-data.Ie n gth da t a.le n gth)(q二 p；ch=p-d ata.1 e ngth-requ e st;)p=pnext；)if(q=NULL)ret urn ERROR;/没有找到空闲块e 1 se i f(q-d a t a.le n g th =reque s t)q-d ata.len g th=l；r e tu r n OK;)e 1 setem p p rior=q-pr i or；temp-n e xt=q;tem p-d at a.a d d ress=q-data.ad d re s s；temp-d ata.n u m=q data.n u m;q-prior-n e xt=temp;q-p r io r=temp;q d ata.address+=r e q uest;q-d ata.length=c h；q-data.num+=l;r eturn OK;return 0 K;)/分派主存Status allocat i o n(int a)(int request;申请内存大小printff请输入申请分派的主存大小(单位:KB):);scanf(n%d&requ e st);if(request n ext)(i f(q=p)(i f(q-pr i or-data.state=O&q-n extd a t a.stat e!=0)q-pr i or-dat a.1 e n gth+=q-data.lengt h;q-pr i or-nex t=q-next;q-n e x tprio r=q-prior;q=q-prior;q-data.s t at e=0;q-dat a.n u m=fl a g-1;。)if(q-prio r-dat a.state!=O&q-ne x tdata.s tate=0)(q d ata.le n g t h+=q-next-da t a.le n gth；q-n ex t=q-next-next;q-next-n e xt p r i o r=q;q-d ata.state=O;q-d ata.num=f 1 a g;。)i f(q-prior-data.s t ate=0&q-n ext-dat a.s t a te=0)q-prior-data.1 e ngth+=q-d a ta.l e n g th;q-pri o r-next=q-ne x t；q-n e xt-p rior=q prior;q=q-prior;q-d a ta.s tate=0；q-da t a.n u m=fl a g-1i f(q-p r i or d at a.st a te!=0&q-ne x t-d at a.s t a te!=0)q-d a ta.s t a t e=0re t urn OK;)S t atus de a 1 2(Nod e*p)解决回收空间(N o d e q=first;for(;q!=N ULL;q=q-n e xt)s if(q=p)(if(q-prior-d a t a.st a t e=0&q-nex t-da t a.state!=0)e q-p r iordata.leng t h+=q-d a ta.len g th;q-p r ior-n e xt=q-next;q-next-p r io r=q-p r i or;q=p-p r ior;q d ata.s t ate=0;q-d at a.num=flag-l;。)i f(q-prior-d ata.s t a t e!=0&q-next-d a t a.state=0)(q-d a t a.s t ate=0;)if(q-prior-d a ta.s t ate=0&q-next-d a ta.sta t e=0)(6q-pri o rdata.1 e n g th+=q-da t a.1 ength;q-prior-n ex t=q-n e xt;q-ne x t-prio r=q-p r i o r；q=q-p r i o r;q-data.state=0;q-data.n u m=flag 1 i f(q-p r i o rdata.state!=0&q-ne x t-dat a.s t ate!=0)。q d ata.s tate=0；。r eturn OK;)主存回收Sta t u s recovery(in t f la g)(Node*p=f i r s t；f o r(;p!=NU LL;p=pn e x t)(匕 if(p-d a ta.num=f 1 ag)(if(p-pri o r=first)0(。i f(p-n e xt!=e n d)/当前P 指向的下一个不是最后一个时(。a i f(p-n e x t-da t a.s ta t e=0)与后面的空闲块相连6(p d a t a.len g th+=p-ne x t-data.l e ngth;p-nex t n e x t p r i o r=p；p next=p n ex t-next;p-d ata.s tate=O；pdata.n um=flag;)。e Is e p-d ata.stat e=0;0 0 i f(p-nex t=end)/当前P 指向的下一个是最后一个时p-d a t a.s ta t e=0;。/结束 if(p p rior=bl o c k_f i r st)的情况els e if(p-p r ior!=f i r st)(。i f(p-n e x t!=end)6。o dea 1 l(p)；6)o else(d e al 2(p);a)。结束 i f(p prior!=blo c k_ f i r s t)的情况。结束 if(p-d a ta.num=fl a g)的情况p r 回收成功*M);r e t u rn OK;)/主函数v o id ma i n()(in t i;/操作选择标记inta；算法选择标记prin t f(”*n”)printf(t t 用以下三种方法实现主存空间的分派n)；p r i n t f(nt(1 )初次适应算法t(2)最佳适应算法t(3)最差适应算法n)；op r i n t f(*n”)；print f(n”);p r in t f(”请输入所使用的内存分派算法：”);s c a n f(%d,&a)；whi 1 e(a3)(prin tf(输入错误，请重新输入所使用的内存分派算法:n )；s c a nf(u%d ,&a);oswi t ch(a)(o c as e 1 ：prin t f(nt*使用初次适应算法:*n );b r ea k;c as e 2:p r intf(M n t*使用最佳适应算法:*n H);break;c a s e 3:pri n t f(nt*使用最坏适应算法:*n);bre a k;I n itblock();/开创空间表wh i le(1)(s h ow();prin t f(t 1：分派内存t2:回收内存t 0:退出n )；p r in tf(请输入您的操作:)；s c an f(0%d”,&i);if(i=l)a 1 1 o c ation(a);/分派内存el s e if(i=2)/内存回收(P rint f(请输入您要释放的分区号:)；sea n f(%d,&flag)；recovery(flag);)else if(i=0)(pnntf(n 退出程序坨);brea k;/退出e Ise/输入操作有误P ri n tf(输入有误，请重试！);con t i n u e;