实验四连续动态存管理模拟实现.ppt课件.ppt

1、实验四 连续动态存管理模拟实现一、实验目的1） 理解内存管理相关理论；2） 掌握连续内存管理理论；3） 掌握动态连续内存管理理论。二、实验内容本实验主要针对操作系统中内存管理相关理论进行实验，要求实验者编写一个程序，该程序管理一块虚拟内存，实现内存分配和回收功能。1） 模拟管理 64M 的内存块；2） 设计内存分配函数；3） 设计内存回收函数；4） 实现动态分配和回收操作；5） 可动态显示每个内存块信息。三、实验原理连续内存分配：为一个用户程序分配一个连续的内存空间，它分为单一连续分配，固定分区分配和动态分区分配，在本实验中，我们主要讨论动态分区分配。动态连续分配：根据进程的实际需要，动态地为

2、之分配内存空间。在实现可变分区分配时，将涉及到分区分配中的所用的数据结构、分区分配算法和分区的分配与回收操作这几个问题。 1) 分区分配中的数据结构(1) 空闲分区表：一张数据表，用于记录每个空闲块的情况，如起始地址、大小，使用情况等。(2) 空闲分区链：为了实现对空闲分区的分配，把所有的空闲内存块连成一个双 向链，便于分配和回收。2) 分区分配算法(1) 首次适应算法：从链首出发，寻找满足申请要求的内存块。(2) 循环首次适应算法：从上次查找的下一个空闲块开始查找，直到找到满足要求的内存块。(3) 最佳适应算法：在每次查找时，总是要找到既能满足要求又最小的内存块给分配给用户进程。为了方便查找

3、，所有的空闲内存块按从小到大的顺序存放在空闲链表中。3) 内存分配操作利用分配算法查找到满足要求的内存块，设请求内存大小为 u.size，而分配的内存块大小为 m.size，如果 m.size-u.sizesize （size 为设定的不可再分割的内存大小），则不再切割；反之，按 u.size 分配给申请者，剩余的部分仍留在内存链中。4) 4) 回收内存回收内存根据回收区地址，从空闲链表中找到相应的插入点。根据回收区地址，从空闲链表中找到相应的插入点。(1) (1) 回收区与插入点的前一个空闲分区相邻，此时将回收区与前一分区合并，不为回收区与插入点的前一个空闲分区相邻，此时将回收区与前一分区合

4、并，不为回收区分配新表项。回收区分配新表项。(2) (2) 回收区与插入点的后一个空闲分区相邻，将回收区与后一分区合并成一个新区，回收区与插入点的后一个空闲分区相邻，将回收区与后一分区合并成一个新区，回收区的首址最为新分区的首址。回收区的首址最为新分区的首址。(3) (3) 回收区与前（回收区与前（F1F1）后）后(F2)(F2)分区相邻，则把三个分区合并成一个大的分区，使分区相邻，则把三个分区合并成一个大的分区，使 F1 F1 的首址作为新分区的首址，修改的首址作为新分区的首址，修改 F1 F1 大小，撤销大小，撤销 F2 F2 表项。表项。(4) (4) 回收区不与任何分区相邻，为回收区建

5、立一个新表项。回收区不与任何分区相邻，为回收区建立一个新表项。四设计思路和方法： 连续分配方式，是指为一个用户程序分配一个连续的内存空间，该连续内存空间指的的是物理内存1、单一连续分配 我们把内存（此时指的是内存条）分为系统内存区和用户区两部分，系统区供OS使用，用户区供用户使用，单一连续分配，就是把用户区当成了一个整体用，所以，该内存管理方式只适用于单用户单任务的操作系统。 2、固定分区分配 固定分区的思想：把用户区提前分成固定大小的几个整体，每个整体都可以用来装入一个作业。我们在划分用户区时，可以采用分区大小相等和分区大小不相等的方式划分，为了方便操作系统把相应的内存分给某个程序，因此，我

6、们通常将分区按大小进行排队，并为之建立一张分区使用表，表中内容为：每个分区的起始位置、大小及状态（是否分配）。此分区方式可以实现多道程序的同时运行，但是，由于每个分区的大小是固定，必然会造成存储空间的浪费。 3、动态分区分配、动态分区分配 动态分区分配的思想：程序在装入内存中时，需要多少内存，我就给他多少内存。要实动态分区分配的思想：程序在装入内存中时，需要多少内存，我就给他多少内存。要实现这个问题，我们要解决三个难题。现这个问题，我们要解决三个难题。 怎么记录物理上不相连的内存？怎么记录物理上不相连的内存？ 采用这种分区方式，刚开始的时候，用户内存是一整块，但是，不断打开程序和关闭程采用这种

7、分区方式，刚开始的时候，用户内存是一整块，但是，不断打开程序和关闭程序后，就会出现一块一块的内存，那么我们应该怎样管理这种情况呢？我们采用某种数序后，就会出现一块一块的内存，那么我们应该怎样管理这种情况呢？我们采用某种数据类型来记录这些空闲的内存块，常用的数据结构类型有空闲分区表和空闲分区链，。据类型来记录这些空闲的内存块，常用的数据结构类型有空闲分区表和空闲分区链，。闲分区和固定分区的表的原理是一样的，只不过这种表的灵活更强；空闲分区链是在物闲分区和固定分区的表的原理是一样的，只不过这种表的灵活更强；空闲分区链是在物理上不相邻的空闲空间的始尾写上了他的前一个块的地址和后一个块的地址，它还存储

8、理上不相邻的空闲空间的始尾写上了他的前一个块的地址和后一个块的地址，它还存储了其他的用于控制分区分配的信息。了其他的用于控制分区分配的信息。 如何分配空闲内存如何分配空闲内存 我们采用了一些分区算法，这些算法主要是针对的是存在了不连续的分区块的首次适应我们采用了一些分区算法，这些算法主要是针对的是存在了不连续的分区块的首次适应算法：在空闲内存中找到适合程序所需内存的第一块内存时，就给它分配所需内存大小，算法：在空闲内存中找到适合程序所需内存的第一块内存时，就给它分配所需内存大小，每次都是从空闲内存的开始查找；循环首次适应算法：从上次找到的空闲分区的下一个每次都是从空闲内存的开始查找；循环首次适

9、应算法：从上次找到的空闲分区的下一个空闲分区开始找；最佳适应算法：把空闲内存中能够满足程序所需，又是最小的内存物空闲分区开始找；最佳适应算法：把空闲内存中能够满足程序所需，又是最小的内存物理块时，就给它分配；最坏适应算法：从内存空闲中跳一个最大的空闲区分配给程序；理块时，就给它分配；最坏适应算法：从内存空闲中跳一个最大的空闲区分配给程序；快速适应算法：主要思想是，设置多个空闲分区链表，记录出每个独立内存块的信息，快速适应算法：主要思想是，设置多个空闲分区链表，记录出每个独立内存块的信息，其中，把内存大小相同的记录在一个表中。其中，把内存大小相同的记录在一个表中。 如何回收如何回收 回收的主要思

10、想是把连续的空闲内存合在一起。回收的主要思想是把连续的空闲内存合在一起。首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业

11、所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。空闲分区链是按地址递增的次序链接的，当要分配内存空间时，就查表，在各空闲分区中查找满足大小要求的可用块，只要找到第一个足以满足要求的空间就停止查找，并把它分配出去，如果该空闲空间与所需空间大小一样，则将该分区的状态改为1，即已被分配，若还有剩余，则将剩余空间重新划为一个空闲分区，有新的起始地址，状态为0。 最佳适应算法的空闲链是按照空闲块的大小为序、按增量方式排列的，即小块在前，大块在后，它在满足需要的前提下，尽量分配最小的

12、空闲块，这样每次查找分配时第一次找到的能满足要求的必然的最佳的，若空闲空间大小与要分配的大小相差不多时，可直接将其状态改为1即可，若有剩余，则将剩余空闲空间重新划分为一个空闲区，并根据空闲区的大小对链表进行重新排序。 首次适应算法的回收过程相对简单，因为分区链是按照地址顺序链接的，因此释放内存时只需要判断要释放的分区前后是否也为空闲区，然后根据情况看是要跟前边或后边或前后都合并为一个大的空闲区，如果前后分区都已分配，则直接将该分区状态改为0即可。 最佳适应算法回收时，因为它的分区链是按照空间大小排列的，因此不仅要看要释放分区前后是否为空闲，还要判断其地址是否前后相接，若地址不相接，则即使要释放

13、分区前后均为空闲区，也不能进行合并，而且每次释放后要根据释放空间的大小对链表进行重新排序。数据定义 动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示： struct memory struct memory *former; /前向指针 int address;/分区起始地址 int num;/作业号 int size;/分配内存大小 int state;/状态字 struct memory *next; /后向指针 ; 前向指针和后向指针分别用于与当前分区的前后分区相链接，add

14、ress用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，num为分配的作业号，size表示分配的内存大小。 4处理流程 分配算法 其中各个条件分别为： P1: ptr-next=NULL P2: ptr-size=assign-size P3: current!=NULL P4: current-size=assign-size¤t-state=0 P5: ptr-size=assign-size P6: (ptr-next)-next!=NULL&is_optimist=true 回收算法 则各条件分别为： P1: current!=NULL P2:

15、current-state=1¤t-num=i P3: current=NULL P4: current-next=NULL P5: previous-state=0 P6: (current-next)-next=NULL P7: previous-state=0&(current-next)-state=0 P8: (current-next)-state=0 P9: is_optimist=true 若为最佳适应算法，则各条件分别为： P1: current!=NULL P2: current-state=1¤t-num=i P3: current=NULL P4

16、: current-next=NULL P5: previous-state=0&(previous-address+previous-size)=current-addr ess) P6: (current-next)-next=NULL P7: previous-state=0&(current-next)-state=0&(previous-address+pr evious-size)=current-address)&(current-size+current-address)=(current-next)-address) P8:(current-next)-state=0&(cu

17、rrent-size+current-address)=(current-next)-address) 四、程序流程为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下： 起 址长 度状 态第一栏14 K12 K未 分 配第二栏32 K96 K未 分 配 其中：起址指出一个空闲区的主存起始地址。 长度指出从起始地址开始的一个连续空闲的长度。 状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的五流程图分配算法流程图：回收算法流程图：六、实验源程序#include #include #include #define n 10 /*假定系统允许的最大作业

18、为，假定模拟实验中n值为10*/#define m 10 /*假定系统允许的空闲区表最大为m，假定模拟实验中m值为10*/#define minisize 100structfloat address; /*已分分区起始地址*/float length; /*已分分区长度，单位为字节*/int flag; /*已分配区表登记栏标志，用0表示空栏目*/used_tablen; /*已分配区表*/structfloat address; /*空闲区起始地址*/float length; /*空闲区长度，单位为字节*/int flag; /*空闲区表登记栏标志，用0表示空栏目，用1表示未分配*/fr

19、ee_tablem; /*空闲区表*/void allocate(char J,float x)/*采用首次适应算法分配x大小的空间*/ int i,k; float ad; k=-1;for(i=0;i=x&free_tablei.flag=1) if(k=-1|free_tablei.lengthfree_tablek.length) k=i; if(k=-1)/*未找到可用空闲区，返回*/ printf(无可用空闲区n); return; /*找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于msize大小，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize大

20、小，则从空闲区划出一部分分配*/if(free_tablek.length-x=minisize)free_tablek.flag=0;ad=free_tablek.address;x=free_tablek.length;elsefree_tablek.length=free_tablek.length-x;ad=free_tablek.address+free_tablek.length;/*修改已分配区表*/i=0;while(used_tablei.flag!=0&i=n) /*无表目填写已分分区*/printf(无表目填写已分分区，错误n);/*修正空闲区表*/if(free_tab

21、lek.flag=0)/*前面找到的是整个空闲分区*/free_tablek.flag=1;else/*前面找到的是某个空闲分区的一部分*/free_tablek.length=free_tablek.length+x;return;else/*修改已分配表*/used_tablei.address=ad;used_tablei.length=x;used_tablei.flag=J;return;/*主存分配函数结束*/void reclaim(char J)/*回收作业名为J的作业所占主存空间*/int i,k,j,s,t;float S,L;/*寻找已分配表中对应登记项*/s=0;whi

22、le(used_tables.flag!=J|used_tables.flag=0)&s=n)/*在已分配表中找不到名字为J的作业*/printf(找不到该作业n);return;/*修改已分配表*/used_tables.flag=0;/*取得归还分区的起始地址S和长度L*/S=used_tables.address;L=used_tables.length;j=-1;k=-1;i=0;/*寻找回收分区的空闲上下邻，上邻表目k，下邻表目j*/while(im&(j=-1|k=-1)if(free_tablei.flag=1)if(free_tablei.address+free_tablei

23、.length=S)k=i;/*找到上邻*/if(free_tablei.address=S+L)j=i;/*找到下邻*/i+;if(k!=-1)if(j!=-1)/* 上邻空闲区，下邻空闲区，三项合并*/free_tablek.length=free_tablej.length+free_tablek.length+L;free_tablej.flag=0;else/*上邻空闲区，下邻非空闲区，与上邻合并*/free_tablek.length=free_tablek.length+L;elseif(j!=-1)/*上邻非空闲区，下邻为空闲区，与下邻合并*/free_tablej.addre

24、ss=S;free_tablej.length=free_tablej.length+L;else/*上下邻均为非空闲区，回收区域直接填入*/*在空闲区表中寻找空栏目*/t=0;while(free_tablet.flag=1&t=m)/*空闲区表满,回收空间失败,将已分配表复原*/printf(主存空闲表没有空间,回收空间失败n);used_tables.flag=J;return;free_tablet.address=S;free_tablet.length=L;free_tablet.flag=1;return;/*主存回收函数结束*/main( )int i,a;float x;ch

25、ar J;/*空闲分区表初始化：*/free_table0.address=10240;free_table0.length=102400;free_table0.flag=1;for(i=1;im;i+)free_tablei.flag=0;/*已分配表初始化：*/for(i=0;in;i+)used_tablei.flag=0;while(1)printf(选择功能项（0-退出,1-分配主存,2-回收主存,3-显示主存）n);printf(选择功项(03) :);scanf(%d,&a);switch(a)case 0: exit(0); /*a=0程序结束*/case 1: /*a=1分

26、配主存空间*/printf(输入作业名J和作业所需长度x: );scanf(%*c%c%f,&J,&x);allocate(J,x);/*分配主存空间*/break;case 2: /*a=2回收主存空间*/printf(输入要回收分区的作业名);scanf(%*c%c,&J);reclaim(J);/*回收主存空间*/break;case 3: /*a=3显示主存情况*/*输出空闲区表和已分配表的内容*/printf(输出空闲区表：n起始地址 分区长度 标志n);for(i=0;im;i+)printf(%6.0f%9.0f%6dn,free_tablei.address,free_tabl

27、ei.length, free_tablei.flag);printf( 按任意键,输出已分配区表n);getch();printf( 输出已分配区表：n起始地址 分区长度 标志n);for(i=0;in;i+)if(used_tablei.flag!=0)printf(%6.0f%9.0f%6cn,used_tablei.address,used_tablei.length, used_tablei.flag);elseprintf(%6.0f%9.0f%6dn,used_tablei.address,used_tablei.length, used_tablei.flag);break;default:printf(没有该选项n);/*case*/*while*/*主函数结束*/谢谢观赏Make Presentation much morfunWPS官方微博kingsoftwps