搜索
第8章动态存储管理8.1概述8.2可利用空间表8.3边界标识法练习与作业在前面各章数据结构的学习中，对每一种数据结构虽然介绍了它们在内存储器中的映象，但只是借助高级语言中的变量说明加以描述，并没涉及具体的存储分配。而实际上，结构中的每个数据元素都占有一定的内存位置．在程序执行的过程中，数据元素的存取是通过对应的存储单元来进行的。在早期的计算机上，这个存储管理的工作是由程序员自己完成的，在程序执行之前．首先需要用机器语言或汇编语言编写的程序输送到内存的某个固定区域上，并预先给变量和数据分配好对应的内存地址(绝对地址或相对地址)。在有了高级语言之后，程序员不需要直接和内存地址打交道，程序中使用的存储单元都由逻辑变量(标识符)来表示．它们对应的内存地址都是由编译程序在编译或执行时进行分配。当计算机是被单个用户使用时，那么整个内存除操作系统占用一部分之外，都归这个用户的程序使用。但在多用户分时并发系统中．多个用户程序共享一个内存区域，此时每个用户程序使用的内存就由操作系统来进行分配了。对操作系统和编译程序来说，存储管理是一个复杂而又重要的问题。动态存储管理的基本问题是：系统如响应用户提出的“请求”分配内存?又如何回收那些用户不再使用而“释放”的内存，以备新的”请求”产生时重新进行分配?提出请求的用户要求分配的内存量大小不同例如，在编译程序中是一个或几十字，而在系统中则是几千、几万，甚至是几十万。通常，系统每次分配给用户(不论大小）都是一个地址连续的内存区。将系统已分配给用户使用的地址连续的内存区为“占用块”，称未曾分配的地址连续的内存区为“可利用空间块”或“空闲块”。不管什么样的动态存储管理系统．在刚开工时，整个内存区是一个“空闲块”。随着用户进入系统，先后提出存储请求，系统依次进行分配。因此，在系境运行的初期，整个内存区基本上分隔成两大部分，低地址区包含若干占用块；高地址区(即分配后的剩余部分)是一个“空闲块·。经过一段时间以后，有的用户运行结束，它所占用的内存区变成空闲块，这使整个内存区呈现出占用块和空闲块交错的状态。U0U1U2U3U4U5U0U3U5有新的用户进入系统请求分配内存，那么系统将如间做呢？系统继续从高地址的空闲块中进行分配，面不理会已分配给用户的内存区是否已空闲，直到分配无法进行(即剩的空闲块不能满足分配的请求)时，系统才去回收所有用户不再使用的空闲块，并且重新组织内存，将所有空闲的内存区连接在一起成为一个大的空闲块。用户一旦运行结束，便将它所占内存区释放成为空闲块．同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适’的空闲块分配之。系统需要建立一张记录所有空闲块的“可利用空间表”，其结构可以是“目录表”，也可以是“链表”。010000310005900099999250003900001000015000空闲310008000空闲5900041000空闲起始地址内存块大小使用情况015000100000800031000041000^59000av返回本节主要学习利用基于链表结构的可利用空间表进行动态存储分配的方法。一、可利用空间表的三种结构可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。当用户请求分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统即回收并将它插入到可利用空间表中。因此，可利用空间表亦称作“存储池”。根据系统运行的不同情况，可利用空间表可以有下列三种不同的结构形式：系统运行期间所有用户请求分配的存储量大小相同。动态存储分配策略：在系统开始运行时将归它使用的内存区按所需大小分割成若于大小相同的块，然后用指针链接成一个可利用空间表。由于表中节点大小相同，则分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户释放内存时，系统只要将用户释放的空闲块插入在表头即可，可见这种情况下的可利用空间表实质上是一个链栈。系统运行期间用户请求分配的存储量有若干种大小的规格。动态存储分配策略：建立若干个可利用空间表，同一链表中的结点大小相同。例如，某动态存储管理系统中的用户将请求分配2个字、4个字或8个字的内存块，则系统建立三个结点大小分别为3个字、5个字和9个字的链表，它们的表头指针分别为av2、av4和av8．tagtypelinkvalue标志域类型域链域tag＝0空闲块1占用块tag＝0大小为2个字1大小为4个字2大小为8个字000000^……av2010101^……av4020202^……av8分配和回收策略：和第一种情况类似，只是当结点大小和请求分配的量相同的链表为空时，需查询结点较大的链表，并从中取出一个结点，将其中一部分内存分配给用户，而将剩余部分插入到相应大小的链表中。回收时，也只要将释放的空闲块插入到相应大小的链表的表头中去即可。需要处理的一个特殊的问题：即当结点与请求相符的链表和结点更大的链表均为空时，分配不能进行，而实际上内存空间并不一定不存在所需大小的连续空间，只是由于在系统运行过程中，频繁出现小块的分配和回收、使得大结点链表中的空闲块被分隔成小块后插入在小结点的链表中，此时若要使系统继续运行，就必须重新组织内存，即执行“存储紧缩”的操作。系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。因此，可利用空间表中的结点即空闲块的大小也是随意的。通常，操作系统中的可利用空间表属这种类型。例如：U0U1U2U3U4U5U0U3U5tagsizelinkspacetag＝0空闲块1占用块size：指示空闲块的存储量假设某用户需大小为n的内存，而可利用空间表中仅有一块大小为m≥n的空闲块，刚只需将其中大小为n的一部分分配给申请分配的用户，同时将剩余大小为m—n的部分作为一个节点留在链表中即可。然而，若可利用空间表中有若干个不小于n的空闲块时，该分配哪一块呢?通常，可有三种不同的分配策略：1、首次拟合法：从在头指针开查找可利田空间表，将找到的第一个大小不小于n的空闲块的—部分分配给用户。可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序。在回收时，只将释放的空闲块插入在链表的表头即可。150000100008000031000^41000059000av例如，如上图所示的空间状态下，一个用户进入系统并申请7K的内存，如何进行分配？系统在可利用空间表中进行查询，发现第一个空闲块即满足要求，则将此块中大小为7K的一部分分配之，剩余8k的空闸块仍在链表中．150000100008000031000^41000059000av70001180002、最佳拟合法。将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n且最接近n的空闲块进行分配。150000100001000031000^41000059000av7000132000150000100008000031000^41000059000av预先设定可利用空间表的结构按空间块的大小自小至大有序，由此．只需找到第一块大于n的空闲块即可进行分配，但在回收时，必须将释放的空闹块插入到合适的位置上去。3、最差拟合法：将可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户。150000100008000031000^34000059000av7000193000150000100008000031000^41000059000av为了节省时间，此时的可利用空间表的结构按空闲块的大小自大至小有序。这样，每次分配无需查找，只需从链表中删除第一个结点，并将其中一部分分配给用户，而剩余部分作为一个新的结点插入到可利用空间表的适当位置上去。当然，在回收时亦需将释放的空间块插入到链表的适当位置上去。三种方法的比较：各有所长。最佳拟合法适用于请求分配大小范围较广的系统。问题是在分配的过程中找到大小最相近的空闲块，因此容易产生无法利用的较小内存片，同时，也保留较大的内存块以备后续使用。最差拟合法每次都从内存量最大的结点中进行分配，从而使链表中的结点大小趋于均匀，四此它适用于请求分配的内存大小范围较窄的系绕。首次拟合法的分配是随机的，因此它介于两者之间，通常适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息的情况。从时间上来比较，首次拟合在分配时需查询可利用空间表而回收时仅需插入在表头即可；最差拟合恰相反，分配时无需查询链表，而回收时为将新的空闲块插入在链表中适当的位置上，需先进行查找；最佳拟合无论分配和回收，均需查找链表，因此最费时间。选取原则：不同的情景需采用不同的方法．因素：用户的逻辑要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性等等。返回边界标识法是操作系统中用以进行动态分配的一种存储管理方法，属于第三种情况。将所有的空闲块链接在一个双重循环链表中：分配可按首次拟和，也可按最佳拟和进行。特点：每个内存区的头部和底部两个边界分别设有标识，以标识该区域为占用块或是空闲块，以便在回收空间十判定相邻位置是否为空闲块，使得地址连续的空闲空间组合成一个尽可能大的空闲块。一、可利用空间表的结构：taguplinkrlinksizetagllinkheadfootspacespace：地址连续存储单元head边界：tag——0空闲1占用size——整个节点大小，包括head和footllink——前驱节点rlink——后继节点Foot边界：tag——0空闲1占用uplink——指向本节点首地址表中不设置表头节点，表头指针可以在任意节点。数据类型描述：typedefstructWORD{//内存字union{WORD*link;WORD*uplink;}inttag;intsize;WORD*rlink;……}WORD,head,foot,*Space;二、分配算法：采用首次拟和法，即从pav开始查找第一个容量不小于请求存储量n的空闲块进行分配。约定：1、若找到空闲块大小为m(m=n)，则，若m-n=e，则将m全部分配给用户；否则，只分配n。避免极小分配不出的空闲块对查找的影响。2、若每次都从同一个节点开始分配，会导致存储量较少的节点密集在头指针附近，也会增加查找时间，约定每次都从不同节点开始查找，因此，另指针pav指向刚进行分配的节点的后继。SpaceAllocBoundTag(Space&pav,intn){for(p=pav;p&&p-sizen&&p-rlink!pav;p=p-rlink);if(!p||p-sizen)returnNULL;else{f=FootLoc(p);//指向底部pav=p-rlink;if(p-size-n=e){if(pav==p)pav=NULL;else{pav-llink=p-llink;p-llink-rlink=pav;}p-tag=f-tag=1;}else{f-tag=1;p-size=p-size-n;//修改分配块底部f=FootLoc(p);//p减小重新定位f-tag=0;f-uplink=p;p=f+1;p-tag=1;p-size=n；}returnp;}}三、回收算法：通过标志位判定占用块的左右近邻是否为空闲块，是否需要进行空闲块合并。若释放空闲块头部地址为p，则低地址近邻的底部地址为p-1，高地址近邻的头部地址为p+p-size，判定tag。共存在四种情况：1、左右均为占用块：将新的空闲块插入到任何位置。p-tag=0;FootLoc(p)-uplink=p;FootLoc(p)-tag=0;if(!pav)pav=p-llink=p-rlink=p;else{q-pav-llink;p-rlink=pav;p-llink=q;p-rlink=pav-llink=p;pav=p;}}2、左近邻空闲，右近邻占用：改变左近邻空闲块的节点大小并重新设置底部字。n=p-size;s=(p-1)-