1、算法与数据结构Algorithms and Data Structures 第八章 动态存储管理第八章第八章 动态存储管理动态存储管理8.1 概述内存是很重要的、很昂贵的资源，如何合理高效地使用这一资源是一个比较复杂的问题。早期使用低级语言编程，内存管理是由程序员自己负责。程序员负担重，管理水平因人而异，管理效率低，容易出错。随着操作系统和高级语言的发展，情况不断改善。内存管理分别由操作系统、高级语言的编译系统和程序员分工合作管理。通常编译系统负责静态储存管理，操作系统负责整个内存管理和动态储存管理。程序员级的管理：用户程序中所用的储存结构有两种，静态结构 ： 空间量在编译后，即可确定 动态结
2、构： 程序运行中申请空间，编译时无法确定。静态储存由编译系统管理。动态储存由程序员和操作系统管理，但程序员的管理非常简单。程序员的工作就是在需要的时候向系统申请空间，在不需要时释放要来的动态储存空间：C语言中： malloc(size), 申请 size字节的内存；free(p), 释放 p， 归还给系统；C+中： new objectType(), 申请空间；free(p), 释放 p， 归还给系统；Java语言中： new objectType(), 申请空间； 用户程序：# include iostd.libInt main() *r=new int100;free (r);操作系统分配
3、 OS_AllocMemory(r,size,flags)回收 OS_ReclaimMemory(r) FreeMemFreeMemrFreeMem编译系统级管理在编译中，编译系统为程序设置了一个虚拟空间，它管理的是虚拟空间。用户程序：int x,y;float r,s;char str10; 虚拟空间： x: 4bytesy: 4bytesstr: 10bytesr: 4bytess: 4bytes048121626内存程序装入时，重定位编译原理与技术中将做介绍。操作系统级管理：存储管理是操作系统的重要部分之一，操作系统对储存的管理是才是真实的管理，而且这一管理是很复杂的。操作系统的存储管理
4、为程序代码和静态数据分配空间为程序动态分配空间回收不用的动态空间回收空间程序代码和静态数据空间分配回收执行程序执行完毕或撤消执行程序程序New Otype()Free(p)从外部来看，操作系统存储管理系统就是提供存储空间分配和回收服务，但内部实现方法却十分复杂，不同的操作系统采用不同的策略和方法，这些问题将在后续课程操作系统中详细介绍。这里我们只是站在数据结构的角度来讨论动态存储管理的基本方法，即存储空间的分配和回收基础技术、存储空间的逻辑结构和物理结构。8.2 可利用空间表初试状态OS bootOS 占用空间free tagsizelink一个连续的存储空间称为 “块 ” blockTag：
5、 标记空间是否分配Size： 空间大小Link： 指向下一个空闲块初试状态：除了操作系统占用的空间外，其它空间形成一个空闲块。当空闲块多时，用 link 链成一个链表，该链表就是可利用空间表。初试此表中只有一个空闲块。表指针是 free。经过多次分配、回收之后，形成了多个空闲块，它们之间不连续，如图所示：Free used1 used2 used3 used4 used52 3 4 5 6Free 113 6 5 4 2可 利用空间表的链接顺序有：（ 1）按块的首地址有低到高链接；（ 2）按块的大小有小到大链接；（ 3）按块的大小有大到小链接；分配： 一般有 3种策略，设申请空间的大小为 n（ 1） 首次拟合法： 从表头开始搜索，遇到第一个尺寸等于大于 n的块进行分配；（ 2） 最佳拟合法： 搜索整个表，将最小的等于大于 n的块进行分配；（ 3） 最差拟合法： 搜索整个表，将最大块进行分配（等于大于 n ）；
