操作系统存储器管理OS4(3)

《操作系统存储器管理OS4(3)》由会员分享，可在线阅读，更多相关《操作系统存储器管理OS4(3)（43页珍藏版）》请在文档大全上搜索。

1、第四章 存储器管理2Reviewv单一连续分配方式单一连续分配方式内存分为两个区域：系统区，用户区。用户区一次只能装入一道程序。内存分为两个区域：系统区，用户区。用户区一次只能装入一道程序。v固定分区分配方式固定分区分配方式 将内存用户空间划分成若干个固定大小的区域，在每个分区中只装入一道作业，这样，用将内存用户空间划分成若干个固定大小的区域，在每个分区中只装入一道作业，这样，用户空间分成了几个分区，便允许有几道作业并发运行。户空间分成了几个分区，便允许有几道作业并发运行。有大小相等和大小不等两种分区方式。有大小相等和大小不等两种分区方式。可以使用分区使用表对存储空间进行管理可以使用分区使用表

2、对存储空间进行管理v动态分区分配方式动态分区分配方式3Reviewv动态分区分配方式动态分区分配方式 根据进程的实际需要，动态地为之分配内根据进程的实际需要，动态地为之分配内存空间。存空间。v数据结构数据结构 空闲空闲分分区表区表：每个每个空闲空闲分分区区占一个表目，表目中包括分区占一个表目，表目中包括分区序号、分区始址及分区大小等数据项。序号、分区始址及分区大小等数据项。 空闲区空闲区（块）（块）链表链表：将所有的空闲区链成一个链表：将所有的空闲区链成一个链表。 位示图表示法位示图表示法 MapMap（i i，j j）：用一位（：用一位（bitbit）表示一个空闲表示一个空闲块（页框）（块（

3、页框）（0 0：空闲，：空闲，1 1：占用）：占用）4【 动态分区分配算法分类】动态分区分配算法分类】顺序搜索法顺序搜索法分类搜索法分类搜索法快速适应算法快速适应算法分区分配算法分区分配算法首次适应算法首次适应算法循环首次适应算法循环首次适应算法最佳适应算法最佳适应算法最坏适应算法最坏适应算法分区分配操作分区分配操作从头开始查表从头开始查表检索完否检索完否?m.sizeu.sizem.size-u.sizesize?从该分区中划出从该分区中划出u.size大小的分区大小的分区将该分区分配给请求者将该分区分配给请求者修改相关的数据结构修改相关的数据结构返回返回返回返回继续检索下一个表项继续检索下

4、一个表项将该分区从链中移出将该分区从链中移出YNYm.size表示空闲表示空闲分区大小分区大小u.size表示请求表示请求分区大小分区大小size表示事先规定表示事先规定的不可再分割的剩余的不可再分割的剩余分区大小分区大小图图4-7 内存分配流程内存分配流程YNN64.3 4.3 连续分配方式连续分配方式哈希算法哈希算法5单一连续分配单一连续分配1固定分区分配固定分区分配2动态分区分配动态分区分配3伙伴系统伙伴系统4可重定位分区分配可重定位分区分配6对换对换77伙伴系统伙伴系统4固定分区固定分区限制了活动进程的数目，内存空间利用率很低限制了活动进程的数目，内存空间利用率很低。动态分。动态分区方

5、式区方式算法复杂算法复杂，回收空闲分区时需要进行分区合并等，系统开回收空闲分区时需要进行分区合并等，系统开销较大销较大。伙伴系统是两者之间的折衷。伙伴系统是两者之间的折衷。思想：思想：无论已分配分区或空闲分区，其大小均为无论已分配分区或空闲分区，其大小均为2 2的的k k次幂，次幂，k k为整数，为整数，1km1km，其中：其中：2 21 1表示分配的最小分区的大小，表示分配的最小分区的大小，2 2m m表示分配的最大分区的大小，通常表示分配的最大分区的大小，通常2 2m m是整个可分配分区的大小。是整个可分配分区的大小。系统开始运行时，是一个大小为系统开始运行时，是一个大小为2 2m m的空

6、闲分区。在系统运行过程中，由于不断的空闲分区。在系统运行过程中，由于不断地划分，可能会形成若干个不连续的空闲分区。将这些空闲分区根据分区的大地划分，可能会形成若干个不连续的空闲分区。将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了区双向链表。这样，不同大小的空闲分区形成了k k（ 1km1km ）个空闲分区链）个空闲分区链表。表。8伙伴系统伙伴系统42KB4KB32KB分配时，如果需要分配时，如果需要16KB32KB16KB回收时，过程相反

7、回收时，过程相反9伙伴系统伙伴系统42KB4KB32KB分配时，如果需要分配时，如果需要8KB32KB16KB8KB回收时，过程相反回收时，过程相反10伙伴系统伙伴系统4分配时：当需要为进程分配一个长度为分配时：当需要为进程分配一个长度为n的存储空间时，首先计算一个的存储空间时，首先计算一个i值，使值，使2 2i-1i-1n2n2i i，然后在空闲分区大小为，然后在空闲分区大小为2 2i i的空闲分区链表中查找。若找到，即把该的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为空闲分区分配给进程。否则，表明长度为2 2i i的分区已经耗尽，则在分区大小为的分区已经耗尽，则在

8、分区大小为2 2i+1i+1的分区链表中寻找。若存在的分区链表中寻找。若存在2 2i+1i+1的一个空闲分区，则把该空闲分区分为相等的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为个加入分区大小为2 2i i的空闲分区链表中。的空闲分区链表中。若大小为若大小为2 2i+1i+1的分区也不存在，则需要查找大小为的分区也不存在，则需要查找大小为2 2i+2i+2的空闲分区。若找到则对的空闲分区。若找到则对其进行两次分割：第一次，将其分割为其进行两次分割：第一

9、次，将其分割为2 2i+1i+1的两个分区，一个用于分配，一个的两个分区，一个用于分配，一个加入到大小为加入到大小为2 2i+1i+1的空闲链表中；第二次，将第一次用于分配的空闲区分割为的空闲链表中；第二次，将第一次用于分配的空闲区分割为2 2i i的两个分区，一个用于分配，一个加入到大小为的两个分区，一个用于分配，一个加入到大小为2 2i i的空闲链表中。依此类推。的空闲链表中。依此类推。回收时：一次回收可能需要进行多次合并，如回收大小为回收时：一次回收可能需要进行多次合并，如回收大小为2 2i i的空闲分区时，若的空闲分区时，若事先已存在事先已存在2 2i i的空闲分区时，则应将其与伙伴分

10、区合并为大小为的空闲分区时，则应将其与伙伴分区合并为大小为2 2i+1i+1的分区，若的分区，若事先已存在事先已存在2 2i+1i+1的空闲分区时，又应继续与其伙伴分区合并为大小为的空闲分区时，又应继续与其伙伴分区合并为大小为2 2i+2i+2的空闲的空闲分区，依此类推。分区，依此类推。11伙伴系统伙伴系统4在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。合并空闲分区所花费的时间。回收空闲分区时需要合并，时间性能比分类搜索算法差，但比顺序搜索算法好。回收空闲分区时需要合并，时间性能

11、比分类搜索算法差，但比顺序搜索算法好。空间性能优于分类搜索法，比顺序搜索法略差。空间性能优于分类搜索法，比顺序搜索法略差。常用于多处理机系统。常用于多处理机系统。12哈希算法哈希算法5哈希算法利用哈希快速查找的优点，以及空闲分区在可利用空哈希算法利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一表项记录了一个对应的空闲分为关键字的哈希表，该表的每一表项记录了一个对应的空闲分区链表表头指针。区链表表头指针。分配时，根据所需空闲分区大小，通过哈希函数计算，即可得分配时