1、主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表 例如： 操作系统（1
2、0KB） 0 10k 作业1（10KB） 20k 作业4（25KB） 45k 空闲区1（20KB） 65k 作业2（45KB） 110k 空闲区2（146KB） 256k 空闲区说明表格式如下： 起始地址 状态 长度 20KB 分 配未第一栏 45 K 146 KB 配 110 K 未分第二栏 空 表目 ? 目 空表 ? ? 其中，起址指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度指出从起始地址开始的一个连续空闲的长度。状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的 某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目，可用来登记新的空闲区（例如，作
3、业完成后，它所占的区域就是空白（无效）。由成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏 目，否则造成表格“溢出”无法登记。、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个2足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区，留在空闲区表中。为了尽量减少由于分割造成的空闲区，尽可能分配低地址部分的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其
4、地址顺序从低到高登记，即每个后，总是继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩” 让“空表目”项留在表格的后部。3、采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。4、当一个作业执行完成撤离时，作业所占的分区应该归还给系统，归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，
5、在上述中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。2）程序结构（流程图） 首次适应分配模拟算法 主存回收算法 3）实现步骤 实现动态分区的分配与回收，主要考虑三个问题：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。1 设计记录主存使用情况的数据表格 由 于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表 格的设计必
6、须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时，空闲区有时会变成两个分区：空闲区 和已分分区，回收主存分区时，可能会合并空闲区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分 配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区贬词空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分 配与回收主要时对空闲区的操作。这样为了便于对主存空间的分配与回收，就建立两张分区表记录主存的使用情况：“已分配区表”记录作业占用分区，“空闲区 表”记录空闲区。这两张表的实现
7、方法一般由两种：链表形式、顺序表形式。在本实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固 定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因此在多数情况下， 无论是“已分配表区”还是“空闲区表”都是空闲栏目。已分配区表中除了分区起始地址、长果为某个 ，如，如果是空闲栏目，内容为“空”度外，也至少还有一项“标志”作业占用分区的登记项，内容为该作业的作业名；空闲区表除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某 个空闲区的登记项，内容为“未分配”。在实际系统中，这两个
8、表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此，“已分配区表”和“空闲区表”在 实验中有如下的结构定义。已分配区表的定义：#define n 10 /假定系统允许的最大作业数量为n struct float address; /已分分区起始地址 float length; /已分分区长度，单位为字节 int flag; /已分配表区登记栏标志，用0表示空栏目， used_tablen; /已分配区表 空闲区表的定义：#define m 10 /假定系统允许的空闲区表最大为m /空闲区起始地址 /空闲区长度，单位为字节 /空闲区表登记栏目用0表示空栏目，1表示未分配?free_tabl
9、em; /空闲区表 其中分区起始地址和长度数值太大，超出了整形表达范围，所有采用float类型。2 在设计的表格上进行主存分配 当 要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找一个能容纳该作业的空闲区。如果找到的空闲区正好等于该作业的长度，则把该分区全部 分配给该作业。这时应该把该空闲区登记栏中的标志改为“空”，同时在已分配区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址、长度和 作业名。如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分用来装入作业，另一部分你仍然为空闲区，这时只要修改空闲区的长度，且把新装入的作 业登记到已分配区表中。主存分配
10、算法目前一般采用三种算法：首次适应算法、循环首次适应算法、最佳适应算法。本实验中采用最佳适应算法为作业分配主存。最佳适应算法会出现空闲分区分割后剩下的空闲分区很小以至于无法使用的情况，为了 在一定程度上解决这个问题，如果空闲分区的大小比作业要求的长度略大一点，不再将空闲区分区分割成已分分区和空闲分区两部分，而是将整个空闲区分配给作业。 在实现最佳适应算法时，可把空闲分区按长度递增方式登记在空闲区表中。分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业要求的最小分区。这样查找 速度快，但是为使空闲区按照长度递增登记在空闲表中，就必须在分配回收时进行空闲区的调整。空闲区表调整时移动标模的代价要
11、高于查询整张表的代价，所以实 验中不采用空闲区有序登记在空闲表中的方法。3 动态分区方式下的主存回收 动态分区方式下回收主存空间时应该检查是否有与归还区相邻的空闲区域。若有，则应该合并成一个空闲区。一个归还区可能有上邻空闲区，也可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区也无下邻空闲区。 在实现回收时，首先将作业归还的区域在已分配表中找到，将该栏目的状态变为“空”，然后检查空闲区表中标志为“未分配”栏目，查找是否又相邻空闲区；最后合并空闲区，修改空闲区表。假定归还作业的分区起始地址为S，长度为L，则：1） 归还区又下邻空闲区 如果SL正好等于空闲区表中某个登记栏目（假
12、定为第j栏）的起始地址则表明归还区有一个下邻空闲区。这时候只需要修改第j栏登记项的内容： 起始地址S；第j栏长度第j栏长度L 则第j栏指示的空闲区时归还区和下邻空闲区合并后的大空闲区。2） 归还区又上邻空闲区 如果空闲区表中某个登记栏目（假定为第k栏）的“起始地址长度”正好等于S，则表明归还区有一个上邻空闲区。这时要修改第k栏登记项的内容（起始地址不变）： 第k栏长度第k栏长度L；于是第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区。3） 归还区既有上邻空闲区又有下邻空闲区 如果SL正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时还有某个登记栏目（假定为第k栏）的“起始地址
13、长度”正好等于S，这表明归还区既有一个上邻空闲区又又一个下邻空闲区。此时对空闲区的修改如下： 第k栏的长度第k栏的长度第j栏的长度L；（第k 栏的起始地址不变） 第j栏的状态“空”（将第j栏的登记项删除） 这样，第k栏指示的空闲区是归还区和上、下邻空闲区合并后的大空闲区；原来的下邻空闲区登记项（第j栏）被删除，置为“空”。4） 归还区既无上邻空闲区又无下邻空闲区 如果在检查空闲区表时，无上述三种情况出现，则表明归还区既无上邻空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下： 第t栏起始地址S； 第t栏的长度L； 第t栏的状态“
14、未分配”；这样，第t栏指示的空闲区是归还区。 由于是实验，没有真正的主存要分配，所有在实验中，首先应建立一张空闲区表，初始状态只有一个空闲登记项（假定的主存空闲区）和一张所有状态都为“空”的 已分配区表，假定主存空间100KB，全部为空闲区（实际上操作系统需要占用一部分）；然后，可以选择进行主存分配或回收，如果是分配，要求输入作业名和 所需主存空间大小；如果是回收，输入回收作业名；循环进行主存分配和回收后，如果需要，则显示两张表的内容，以检查主存的分配和回收是否正确。4）实验测试及分析：6、实验心得体会 这次实验比较复杂，用了很多时间，但同时收获了很多，对主存空间分配认识加深了很多 附录：源代
15、码 #includestdlib.h#define OK 1 /完成 #define ERROR 0 /出错 typedef int Status;typedef struct free_table/定义一个空闲区说明表结构 int num; /分区序号 long address; /起始地址 long length; /分区大小 int state; /分区状态 ElemType;typedef struct Node/ 线性表的双向链表存储结构 ElemType data; struct Node *prior; /前趋指针 struct Node *next; /后继指针 Node,*L
16、inkList;LinkList first; /头结点 LinkList end; /尾结点 int flag;/记录要删除的分区序号 Status Initblock（）/开创带头结点的内存空间链表 first=（LinkList）malloc（sizeof（Node）; end=（LinkList）malloc（sizeof（Node）; first-prior=NULL;next=end; end-prior=first;next=NULL;data.num=1;data.address=40;data.length=600;data.state=0; return OK; void
17、sort（）/分区序号重新排序 Node *p=first-next,*q; q=p-next; for（;p!=NULL;p=p-next） for（q=p-q;q=q- if（p-data.num=q-data.num） q-data.num+=1; /显示主存分配情况 void show（） int flag=0;/用来记录分区序号 Node *p=first; p-data.num=0;data.address=0;data.length=40;p-data.state=1; sort（）; printf（tt主存空间分配情况n）; printf（*nn）; 牰湩晴尨分区序号t起始地址
18、t分区大小t分区状态nn）; while（p） printf（%dtt%dtt%d,p-data.num,p-data.address,p-data.length）;data.state=0） printf（ t空闲nn）; else printf（ t已分配nn）; p=p-/首次适应算法 Status First_fit（int request） /为申请作业开辟新空间且初始化 LinkList temp=（LinkList）malloc（sizeof（Node）; temp-data.length=request; if（p-data.state=0）&（p-data.length=re
19、quest） /有大小恰好合适的空闲块 break; else if（p-data.state=0） & （p-data.lengthrequest） /有空闲块能满足需求且有剩余 prior=p-prior;next=p;data.address=p-data.address;data.num=p-data.num;prior-next=temp;prior=temp;data.address=temp-data.address+temp-data.length;data.length-=request; p-break; return ERROR;/最佳适应算法 Status Best_f
20、it（int request） int ch; /记录最小剩余空间 Node *q=NULL; /记录最佳插入位置 while（p） /初始化最小空间和最佳位置 =request） ） if（q=NULL） q=p; ch=p-data.length-request; else if（q-data.length data.length） if（q=NULL） return ERROR;/没有找到空闲块 data.length=request） else prior=q-next=q;temp-data.address=q-data.num=q-data.address+=request;dat
21、a.length=ch;/最差适应算法 Status Worst_fit（int request） /记录最大剩余空间 while（p） /初始化最大空间和最佳位置 data.state=0 &data.length data.length=1;return OK;/分配主存 Status allocation（int a） int request;/申请内存大小 牰湩晴尨请输入申请分配的主存大小（单位:KB）:）; scanf（%d,&request）; if（request0 |request=0） 牰湩晴尨分配大小不合适，请重试！ switch（a） case 1: /默认首次适应算法 if（First_fit（request）=OK） printf（ *分配成功！*）; else printf（ *内存不足，分配失败！ case 2: /选择最佳适应算法 if（Best_fit（request）=OK） printf（ *分配成功！ case 3: /选择最差适应算法 if（Worst_fit（request）=OK） printf（ *分配成功！
