山东师范大学动态存储管理讲义.ppt

动态存储管理 8.1 概述 8.2 可利用空间表及分配方法 8.3 边界标识法 8.4 伙伴系统 一、内容提要? 1．动态存储管理指的是在用户需要时给分配内存，而在用户结束使用时，系统要收回用户所占空间。 2．可利用空间表的三种结构形式：结点固定大小；分几种规格；任意大小。 3．可利用空间表的两种组织形式：目录表，链表。 4．可利用空间表的分配方式：首次拟合法，最佳拟合法，最差拟合法。 5．可利用空间表的分配和回收的两种基本实现方法：边界标识法，伙伴系统。 二、学习重点 1、概念：可利用空间表及分配方式，紧缩存储，伙伴系统等。 2、边界表示法的分配及回收算法。 3、伙伴系统的分配及回收算法。 8.1 概述 8.2 可利用空间表及分配方法 8.3 边界标识法 8.3.1 可利用空间表的结构 8.3.2 分配算法 8.3.3 回收算法 边界表示法需要考虑的问题: 查找适合需要的块，需要较多的时间 查找适合需要的块的策略（最先/最佳/最坏），每种都有缺陷 碎片问题 8.4 伙伴系统 8.4.1 可利用空间表的结构 8.4.2 分配算法 8.4.3 回收算法 伙伴系统（buddy system）是操作系统中用到的一种动态存储管理方法。它和边界标识法类似，在用户提出申请时，分配一块大小“恰当”的内存区给用户；反之，在用户释放内存区时即收回。 伙伴系统的特点：无论是占用块或空闲块，其大小均为2的k次幂（k为某个正整数）。 （1）结点结构 表头结点 head llink tag kval rlink space nodesize first 结点：右头部head和space域组成。 head：为结点头部，是一个由4个域组成的记录。 llink：链域，指向同一链表中的前驱结点。 rlink：链域，指向同一链表中的后继结点。 tag：标志域，值为“0”表示空闲块，值为“1”表示占用块。 kval：其值为2的幂次k。 space：数据域，是一个大小为2k－1个字的连续内存空间。 表头结点：由两个域组成。 nodesize：表示该链表中空闲块的大小。 first：该链表的表头指针。 （2）C语言描述 #define m 16 //可利用空间总容量64k字的2的幂次，子表的个数为m+1 typedef struct WORD_b { WORD_b *llink; //头部域，指向前驱结点 int tag; //块标志，0：空闲，1：占用。 int skval; //块大小，值为2的幂次k WORD_b *rlink; //头部域，指向后继结点 OtherType other; //字的其他部分 } WORD_b, head; //WORD：内存字类型，结点的第一个字也称head typedef struct HeadNode { int nodesize; //该链表的空闲块的大小 WORD_b *first; //该链表的表头指针 } FreeList[m + 1]; //表头向量类型 （3）例子 例如，可利用空间表的初始状态如图8.8(a)所示，其中m个子表都为空表，只有大小为2m的链表中有一个结点，即整个存储空间。 (a) 表的初始状态 nodesize first 20 21 2k 2m 0 m (b) 分配前的表 (c) 分配后的表 图8.8 伙伴系统中的可利用空间表 20 2k-1 2m 0 K 2k 0 K 0 K 20 2k-1 2m 2k 0 K 0 K 0 K-1 （1）算法思想 当用户提出大小为n的内存请求时，首先在可利用表上寻找 结点大小与n相匹配的子表，若此子表非空，则将子表中任意一 个结点分配之即可；若此子表为空，则需从结点更大的非空子表 中去查找，直至找到一个空闲块，则将其中一部分分配给用户， 而将剩余部分插入相应的子表中。 （2）算法实现 算法8.2如下： WORD_b AllocBuddy (FreList avail, int n) { //avail[0..m]为可利用空间表，n为申请分配量，若有不 //小于n的空闲块，则分配相应的存储块，并返回其首 //地址；否则返