动态分区存储管理..课件

第四章 存储器管理 4.3.3 动态分区分配动态分区分配1分区分配法的思想和数据结构分区分配法的思想和数据结构固定分区主存利用率不高，使用起来不灵活，固定分区主存利用率不高，使用起来不灵活，所以出现了可变分区的管理技术。所以出现了可变分区的管理技术。动态分区原则：存储空间的划分是在作业装动态分区原则：存储空间的划分是在作业装入时进行的。从可用的自由存储空间内，划出入时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配一个大小正好等于作业大小的存储区，并分配给这一作业。给这一作业。动态分区，在系统初启时，除了操作系统中动态分区，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。常驻内存部分之外，只有一个空闲分区。第四章 存储器管理 4.3.3 动态分区分配动态分区分配进程进程 A A（8K8K）进程进程 D D（124K124K）进程进程 B B（16K16K）进程进程 C C（64K64K）OSOS进程进程A(8K)A(8K)进程进程B(16K)B(16K)进程进程C(64K)C(64K)进程进程D(124K)D(124K)OSOS进程进程A(8K)A(8K)进程进程B(16K)B(16K)进程进程C(64K)C(64K)OSOS进程进程A(8K)A(8K)进程进程B(16K)B(16K)OSOS进程进程A(8K)A(8K)第四章 存储器管理 内存分配变化过程内存分配变化过程OSA（8K）8K空闲区空闲区B（16K）E（50K）D（124K）14K空闲区空闲区F（16K）OSA（8K）8K空闲区空闲区空闲区空闲区16KE（50K）F（16K）空闲合并空闲合并124+14=138K进程进程E（50K）进程进程F（16K）进入内存进入内存进程进程B（16K）进程进程D（124K）完成完成OSA（8K）24K空闲区空闲区B（16K）C完成（完成（64K）空闲区空闲区D（124K）第四章 存储器管理 4.3.3 动态分区分配动态分区分配动态分区存储管理可采用多种数据结构对内存进行动态分区存储管理可采用多种数据结构对内存进行管理管理图 可用表、自由链及请求表 第四章 存储器管理 动态分区优缺点动态分区优缺点优点：优点：内存利用率提高，避免了内碎片内存利用率提高，避免了内碎片 缺点：缺点：出现了外碎片（分区之间未被利用出现了外碎片（分区之间未被利用的空间）的空间）第四章 存储器管理 2动态分区分配与回收动态分区分配与回收对于请求表中要求内存长度对于请求表中要求内存长度,从可用表从可用表和自由链中找出合适的空闲区。和自由链中找出合适的空闲区。分配空间区之后分配空间区之后,更新可用表或自由链。更新可用表或自由链。进程或作业释放内存资源时进程或作业释放内存资源时,和相邻的和相邻的空间区进行链合并空间区进行链合并,更新可用表或自由更新可用表或自由链。链。第四章 存储器管理 3动态分区分配算法 最先适应法最先适应法(FF,FirstFit)要求可用表或自由链按起始要求可用表或自由链按起始地址递增地址递增的次的次序排列。序排列。从表头查询，一旦找到大小满足的分区就从表头查询，一旦找到大小满足的分区就结束探索。结束探索。例题：如图所示是某一个时刻例题：如图所示是某一个时刻J1J1、J2J2、J3J3、J4J4在在内存中的分配情况、空闲区表和已分区表，它们内存中的分配情况、空闲区表和已分区表，它们的长度分别是的长度分别是15KB15KB、10KB10KB、12KB12KB、10KB10KB。J5J5和和J6J6两两个新作业的长度分别为个新作业的长度分别为5KB5KB和和13KB13KB。按照最先适。按照最先适应算法进行内存分配，描述分配后内存、空闲区应算法进行内存分配，描述分配后内存、空闲区表以及已分区表的情况。表以及已分区表的情况。第四章 存储器管理 3动态分区分配算法最先适应算法分配前的状态最先适应算法分配前的状态起始地址起始地址 长度长度状态状态0K15KJ138K10KJ268K12KJ3110K10KJ4已分区表已分区表0J1J4J3J21538486880110120起始地址起始地址 长度长度状态状态15K23K未分配未分配48K20K未分配未分配80K30K未分配未分配空闲区表空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。第四章 存储器管理 3动态分区分配算法最先适应算法分配后的状态最先适应算法分配后的状态起始地址起始地址长度长度状态状态0K15KJ138K10KJ268K12KJ3110K10KJ415K5KJ520K13KJ6已分区表起始地址起始地址长度长度状态状态33K5K未分配未分配48K20K未分配未分配80K30K未分配未分配空闲区表3848110J6J1J4J3J20156880120J533J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。第四章 存储器管理 从该空闲区中截取所需从该空闲区中截取所需大小，修改调整可用表大小，修改调整可用表从空闲区表第一从空闲区表第一表目顺序查找表目顺序查找从可用表中移去该从可用表中移去该表目，调整可用表表目，调整可用表取下一表项取下一表项无法分配无法分配该该 空闲区空闲区长度长度SIZE？该该 空闲区空闲区长度长度=SIZE？表目查完？表目查完？返回分配起始地址返回分配起始地址否否否否是是是是是是否否图图 最先适应算法最先适应算法请求请求SIZESIZE大小的分区大小的分区第四章 存储器管理 3动态分区分配算法 最先适应法最先适应法缺点：缺点：由于查找总是从表首开始，前面的空闲区由于查找总是从表首开始，前面的空闲区被分割的很小时，能满足分配要求的可能被分割的很小时，能满足分配要求的可能性就越小，查找次数越多性就越小，查找次数越多 碎片问题碎片问题第四章 存储器管理 3动态分区分配算法最佳适应法最佳适应法(BF,Best Fit)要求可用表（空闲表）或自由链按分区要求可用表（空闲表）或自由链按分区大小递增大小递增的次序排列。的次序排列。从表头查询，一旦找到大小满足的分区从表头查询，一旦找到大小满足的分区就结束探索就结束探索。第四章 存储器管理 3动态分区分配算法分配前的状态分配前的状态起始地址起始地址长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分区表起始地址起始地址 长度长度 状态状态15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。起始地址起始地址 长度长度 状态状态48K48K20K20K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空闲区表0J1J4J3J21538486880110120第四章 存储器管理 最佳适应算法分配后的状态起始地址起始地址长度长度状态状态0K15KJ138K10KJ268K12KJ3110K10KJ448K5KJ553K13KJ6已分区表起始地址起始地址长度长度状态状态66K2K未分配未分配15K23K未分配未分配80K30K未分配未分配空闲区表J6J3J1J4J201538486880110120J566J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。第四章 存储器管理 3动态分区分配算法最佳适应法最佳适应法优点：优点：分配后所剩余的空白块会最小分配后所剩余的空白块会最小 平均而言，只要查找一半的表格便能找到平均而言，只要查找一半的表格便能找到缺点：缺点：由于空闲区是按大小而不是按地址排序，因此由于空闲区是按大小而不是按地址排序，因此释放时，要在整个链表上搜索地址相邻的空闲区释放时，要在整个链表上搜索地址相邻的空闲区 空闲区分配后剩余部分成为碎片空闲区分配后剩余部分成为碎片第四章 存储器管理 3动态分区分配算法最坏适应算法最坏适应算法(WF)按空闲区按空闲区大小递减大小递减的顺序组成空闲区可用表的顺序组成空闲区可用表或自由链。或自由链。最坏适应算法的思想与最佳适应算法相反，最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲区就是找到的分区。该算法前面的最大的空闲区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。变成一个新小一点的空闲区。第四章 存储器管理 分配前的状态分配前的状态起始地址起始地址长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分区表起始地址起始地址长度长度 状态状态15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。起始地址起始地址 长度长度 状态状态80K80K30K30K未分配未分配15K15K23K23K未分配未分配48K48K20K20K未分配未分配空闲区表0J1J4J3J21538486880110120第四章 存储器管理 最坏适应算法分配后的状态起始地址起始地址长度长度状态状态0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ6已分区表起始地址起始地址长度长度状态状态15K23K未分配未分配48K20K未分配未分配98K12K未分配未分配空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。1538486880110120J1J4J3J20J5J6 98第四章 存储器管理 3动态分区分配算法最坏适应算法最坏适应算法优点：优点：分配时只需查找一次就可以成功分配时只需查找一次就可以成功缺点：缺点：最后剩余的分区越来越小，无法运行最后剩余的分区越来越小，无法运行大程序大程序第四章 存储器管理 3动态分区分配算法循环首次适应算法循环首次适应算法(next fit)该算法是由首次适应算法演变而成的。在为进程该算法是由首次适应算法演变而成的。在为进程分配内存空间时，分配内存空间时，不再是不再是每次都从每次都从链首链首开始查找，开始查找，而是而是从上次找到从上次找到的空闲分区的的空闲分区的下一个下一个空闲分区开空闲分区开始查找，直至找到一个能满足要求的空闲分区。始查找，直至找到一个能满足要求的空闲分区。为实现该算法，应设置一起始查寻指针，用于指为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区。示下一次起始查寻的空闲分区。该算法能使内存中的空闲分区分布得更均匀，从该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。大的空闲分区。第四章 存储器管理 3动态分区分配算法快速适应算法快速适应算法(quick fit)该算法又称为分类搜索法，是将空闲分区该算法又称为分类搜索法，是将空闲分区根据其根据其容量大小进行分类容量大小进行分类，如，如2 KB、4 KB、8 KB等。等。对于每一类具有相同容量的所有空闲分区，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型和该类型空闲项对应了一种空闲分区类型和该类型空闲分区链表表头的指针。分区链表表头的指针。第四章 存储器管理 3动态分区分配算法该算法的优点是查找效率高，仅需要根据该算法的优点是查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内区，满足对大空间的需求，也不会产生内存碎片。存碎片。该算法的缺点是在分区归还主存时算法复该算法的缺点是在分区归还主存时算法复杂，系统开销较大。杂，系统开销较大。第四章 存储器管理 4动态分区时的回收与拼接当某一个用户作业完成释放所占分区时，系当某一个用户作业完成释放所占分区时，系统应进行回收。统应进行回收。在可变式分区中，应该检查回收区与内存中在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的若不相邻，应将空闲区插入到空闲区链表的适当位置。适当位置。第四章 存储器管理 4动态分区时的回收与拼接第四章 存储器管理 4动态分区时的回收与拼接释放区邻接的分区情况可能是：释放区邻接释放区邻接的分区情况可能是：释放区邻接的是另一进程的已分配区，或者是空闲区。的是另一进程的已分配区，或者是空闲区。下面以首次适应法说明了系统回收该进程占下面以首次适应法说明了系统回收该进程占用区存在的四种可能情况。用区存在的四种可能情况。设进程的释放区为设进程的释放区为R R，与，与R R相邻的两个空闲区相邻的两个空闲区分别为分别为F1F1和和F2F2。R R的首地址送的首地址送LOCLOC，R R的尾地址的尾地址送送LOC1LOC1，R R的大小送的大小送SIZESIZE。第四章 存储器管理(a)(a)若释放区若释放区R R与与F1F1相邻接，即其低地址部分邻相邻接，即其低地址部分邻接一空闲区。将接一空闲区。将R R与与F1F1合并，合并后的空闲区合并，合并后的空闲区仍记为仍记为F1F1。4动态分区时的回收与拼接低地址 高地址空闲区 F1进程 P 占用区2低地址 高地址占用区2空闲区 F1(a)合并后第四章 存储器管理 4动态分区时的回收与拼接如何判断释放区如何判断释放区R R 是否与某个空闲区相邻呢？是否与某个空闲区相邻呢？只要从链首开始查找即可：若只要从链首开始查找即可：若F1F1的首地址的首地址+F1+F1的大小的大小=R=R的首地址，说明的首地址，说明R R与与F1F1相邻接。相邻接。只要修改只要修改F1F1的大小的大小=F1=F1的大小的大小+LOC+LOC，其它参，其它参数不变和在链中的位置不变。数不变和在链中的位置不变。第四章 存储器管理 4动态分区时的回收与拼接(b)(b)若释放区若释放区R R与与F2F2相邻接，即其高地址部分邻接一空相邻接，即其高地址部分邻接一空闲区。将闲区。将R R与与F2F2合并，合并后的空闲区记仍记为合并，合并后的空闲区记仍记为F2F2。判断释放区判断释放区R R 是否与是否与F2F2空闲区相邻，只要从链首空闲区相邻，只要从链首开始查找。开始查找。若若LOC+SIZE=F2LOC+SIZE=F2的首地址，说明的首地址，说明R R与与F2F2相邻接。需相邻接。需修改修改F2F2的首地址的首地址=LOC=LOC，F2F2的大小的大小=F2=F2的大小的大小+SIZE+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 int malloc(struct map*mp,intmp,int size)size)/空闲表指针空闲表指针mpmp，作业大小，作业大小sizesizeregister int regint;register int regint;register struct map register struct map*bp;bp;/从从mpmp开始，只要开始，只要sizesize不等于不等于0 0，逐个地址检查，逐个地址检查 动态分区的分配算法提示：动态分区的分配算法提示：m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空闲区空闲区已分配已分配空闲区空闲区已分配已分配空闲区空闲区已分配已分配mp第四章 存储器管理 for(bp=mp;bp-m_size;bp+)for(bp=mp;bp-m_size;bp+)if(bp-m_size=size)if(bp-m_size=size)regint=bp-m_addr;regint=bp-m_addr;bp-m_addr+=size;bp-m_addr+=size;if(bp-m_size-=size)=0)/if(bp-m_size-=size)=0)/赋值并判断赋值并判断dodo bp+;bp+;(bp-1)-m_addr=bp-m_addr;(bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);while(bp-1)-m_size=bp-m_size);return(regint);return(regint);return(0);return(0);m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空闲区空闲区已分配已分配已分配已分配空闲区空闲区已分配已分配mpbp