动态分区存储管理课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 存储器管理,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 存储器管理,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 存储器管理,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 存储器管理,4.3.3,动态分区分配,1,分区分配法的思想和数据结构,固定分区主存利用率不高，使用起来不灵活，所以出现了可变分区的管理技术。,动态分区原则：存储空间的划分是在作业装入时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。,动态分区，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。,4.3.3,动态分区分配,进程,A,（,8K,）,进程,D,（,124K,）,进程,B,（,16K,）,进程,C,（,64K,）,OS,进程,A(8K),进程,B(16K),进程,C(64K),进程,D(124K),OS,进程,A(8K),进程,B(16K),进程,C(64K),OS,进程,A(8K),进程,B(16K),OS,进程,A(8K),内存分配变化过程,OS,A,（,8K,）,8K,空闲区,B,（,16K,）,E,（,50K,）,D,（,124K,）,14K,空闲区,F,（,16K,）,OS,A,（,8K,）,8K,空闲区,空闲区,16K,E,（,50K,）,F,（,16K,）,空闲合并,124+14,=138K,进程,E,（,50K,）,进程,F,（,16K,）,进入内存,进程,B,（,16K,）,进程,D,（,124K,）,完成,OS,A,（,8K,）,24K,空闲区,B,（,16K,）,C,完成（,64K,）,空闲区,D,（,124K,）,4.3.3,动态分区分配,动态分区存储管理可采用多种数据结构对内存进行管理,图 可用表、自由链及请求表,动态分区优缺点,优点：,内存利用率提高，避免了内碎片,缺点：,出现了外碎片（分区之间未被利用的空间）,2,动态分区分配与回收,对于请求表中要求内存长度,从可用表和自由链中找出合适的空闲区。,分配空间区之后,更新可用表或自由链。,进程或作业释放内存资源时,和相邻的空间区进行链合并,更新可用表或自由链。,3,动态分区分配算法,最先适应法,(FF,FirstFit),要求可用表或自由链按起始,地址递增,的次序排列。,从表头查询，一旦找到大小满足的分区就结束探索。,例题：如图所示是某一个时刻,J1,、,J2,、,J3,、,J4,在内存中的分配情况、空闲区表和已分区表，它们的长度分别是,15KB,、,10KB,、,12KB,、,10KB,。,J5,和,J6,两,个新作业的长度分别为,5KB,和,13KB,。按照最先适应算法进行内存分配，描述分配后内存、空闲区表以及已分区表的情况。,3,动态分区分配算法,最先适应算法分配前的状态,起始地址,长度,状态,0K,15K,J1,38K,10K,J2,68K,12K,J3,110K,10K,J4,已分区表,0,J1,J4,J3,J2,15,38,48,68,80,110,120,起始地址,长度,状态,15K,23K,未分配,48K,20K,未分配,80K,30K,未分配,空闲区表,J5,和,J6,两个新作业的长度分别为,5KB,和,13KB,。,3,动态分区分配算法,最先适应算法分配后的状态,起始地址,长度,状态,0K,15K,J1,38K,10K,J2,68K,12K,J3,110K,10K,J4,15K,5K,J5,20K,13K,J6,已分区表,起始地址,长度,状态,33K,5K,未分配,48K,20K,未分配,80K,30K,未分配,空闲区表,38,48,110,J6,J1,J4,J3,J2,0,15,68,80,120,J5,33,J5,和,J6,两个新作业的长度分别为,5KB,和,13KB,。,从该空闲区中截取所需,大小，修改调整可用表,从空闲区表第一,表目顺序查找,从可用表中移去该,表目，调整可用表,取下一表项,无法分配,该 空闲区,长度,SIZE,？,该 空闲区,长度,=SIZE,？,表目查完？,返回分配起始地址,否,否,是,是,是,否,图 最先适应算法,请求,SIZE,大小的分区,3,动态分区分配算法,最先适应法,缺点：,由于查找总是从表首开始，前面的空闲区被分割的很小时，能满足分配要求的可能性就越小，查找次数越多,碎片问题,3,动态分区分配算法,最佳适应法,(BF,Best Fit),要求可用表（空闲表）或自由链按分区,大小递增,的次序排列。,从表头查询，一旦找到大小满足的分区就结束探索,。,3,动态分区分配算法,分配前的状态,起始地址,长度,状态,0K,15K,J1,38K,10K,J2,68K,12K,J3,110K,10K,J4,已分区表,起始地址,长度,状态,15K,23K,未分配,48K,20K,未分配,80K,30K,未分配,空闲区表,J5,和,J6,两个新作业的长度分别为,5KB,和,13KB,。,起始地址,长度,状态,48K,20K,未分配,15K,23K,未分配,80K,30K,未分配,空闲区表,0,J1,J4,J3,J2,15,38,48,68,80,110,120,最佳适应算法分配后的状态,起始地址,长度,状态,0K,15K,J1,38K,10K,J2,68K,12K,J3,110K,10K,J4,48K,5K,J5,53K,13K,J6,已分区表,起始地址,长度,状态,66K,2K,未分配,15K,23K,未分配,80K,30K,未分配,空闲区表,J6,J3,J1,J4,J2,0,15,38,48,68,80,110,120,J5,66,J5,和,J6,两个新作业的长度分别为,5KB,和,13KB,。,3,动态分区分配算法,最佳适应法,优点：,分配后所剩余的空白块会最小,平均而言，只要查找一半的表格便能找到,缺,点：,由于空闲区是按大小而不是按地址排序，因此释放时，要在整个链表上搜索地址相邻的空闲区,空闲区分配后剩余部分成为碎片,3,动态分区分配算法,最坏适应算法,(WF),按空闲区,大小递减,的顺序组成空闲区可用表或自由链。,最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。,分配前的状态,起始地址,长度,状态,0K,15K,J1,38K,10K,J2,68K,12K,J3,110K,10K,J4,已分区表,起始地址,长度,状态,15K,23K,未分配,48K,20K,未分配,80K,30K,未分配,空闲区表,J5,和,J6,两个新作业的长度分别为,5KB,和,13KB,。,起始地址,长度,状态,80K,30K,未分配,15K,23K,未分配,48K,20K,未分配,空闲区表,0,J1,J4,J3,J2,15,38,48,68,80,110,120,最坏适应算法分配后的状态,起始地址,长度,状态,0K,15K,J1,38K,10K,J2,68K,12K,J3,110K,10K,J4,80K,5K,J5,85K,13K,J6,已分区表,起始地址,长度,状态,15K,23K,未分配,48K,20K,未分配,98K,12K,未分配,空闲区表,J5,和,J6,两个新作业的长度分别为,5KB,和,13KB,。,15,38,48,68,80,110,120,J1,J4,J3,J2,0,J5,J6,98,3,动态分区分配算法,最坏适应算法,优点：,分配时只需查找一次就可以成功,缺,点：,最后剩余的分区越来越小，无法运行大程序,3,动态分区分配算法,循环首次适应算法,(next fit),该算法是由首次适应算法演变而成的。在为进程分配内存空间时，,不再是,每次都从,链首,开始查找，而是,从上次找到,的空闲分区的,下一个,空闲分区开始查找，直至找到一个能满足要求的空闲分区。,为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区。,该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。,3,动态分区分配算法,快速适应算法,(quick fit),该算法又称为分类搜索法，是将空闲分区根据其,容量大小进行分类,，如,2 KB,、,4 KB,、,8 KB,等。,对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型和该类型空闲分区链表表头的指针。,3,动态分区分配算法,该算法的优点是查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。,另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。,该算法的缺点是在分区归还主存时算法复杂，系统开销较大。,4,动态分区时的回收与拼接,当某一个用户作业完成释放所占分区时，系统应进行回收。,在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，,若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；,若不相邻，应将空闲区插入到空闲区链表的适当位置。,4,动态分区时的回收与拼接,4,动态分区时的回收与拼接,释放区邻接的分区情况可能是：释放区邻接的是另一进程的已分配区，或者是空闲区。,下面以首次适应法说明了系统回收该进程占用区存在的四种可能情况。,设进程的释放区为,R,，与,R,相邻的两个空闲区分别为,F1,和,F2,。,R,的首地址送,LOC,，,R,的尾地址送,LOC1,，,R,的大小送,SIZE,。,(a),若释放区,R,与,F1,相邻接，即其低地址部分邻接一空闲区。将,R,与,F1,合并，合并后的空闲区仍记为,F1,。,4,动态分区时的回收与拼接,低地址 高地址,空闲区,F1,进程,P,占用区,2,低地址 高地址,占用区,2,空闲区,F1,(a),合并后,4,动态分区时的回收与拼接,如何判断释放区,R,是否与某个空闲区相邻呢？,只要从链首开始查找即可：若,F1,的首地址,+F1,的大小,=R,的首地址，说明,R,与,F1,相邻接。,只要修改,F1,的大小,=F1,的大小,+LOC,，其它参数不变和在链中的位置不变。,4,动态分区时的回收与拼接,(b),若释放区,R,与,F2,相邻接，即其高地址部分邻接一空闲区。将,R,与,F2,合并，合并后的空闲区记仍记为,F2,。,判断释放区,R,是否与,F2,空闲区相邻，只要从链首开始查找。,若,LOC+SIZE=F2,的首地址，说明,R,与,F2,相邻接。需修改,F2,的首地址,=LOC,，,F2,的大小,=F2,的大小,+SIZE,。,4,动态分区时的回收与拼接,(b),合并后,低地址 高地址,占用区,1,进程,P,空闲区,F2,低地址 高地址,空闲区,F2,占用区,1,4,动态分区时的回收与拼接,(c),若释放区,R,的高、低地址部分都邻接一个空闲区。,应将三个分区合并为一个大空闲区，并记为,F1,。先将,R,与,F2,合并，记为,F2,。,再将,F 2,与,F1,合并，并将,F2,从链中删除。,空闲区,F1,释放区,R,空闲区,F2,空闲区,F1,合并后,4,动态分区时的回收与拼接,(d),若释放区,R,上下都不邻接空闲区，将其插入空闲区链的适当位置即可。,（最先适应法）：,int malloc(struct map*mp,int,size),/,空闲表指针,mp,，作业大小,size,register int regint;,register struct map*bp;,/,从,mp,开始，只要,size,不等于,0,，逐个地址检查,动态分区的分配算法提示：,m_addr,