4.1 内存管理概述 53
内存资源的有效使用。前面两小节介绍了硬件支持的内存管理机制,尤其是如何将虚拟地
址或者逻辑地址转译成物理内存地址。这一节我们将首先讨论在一个地址空间内部如何有
效地进行动态内存管理,然后介绍常用的页面替换算法,以及在进程内存管理中常常用到
的工作集概念和相应的算法。
假设操作系统或者一个进程已经获得了一块连续地址的内存,系统或进程在执行过程
中需要利用这块内存来满足各种内存请求。由于内存请求存在动态性,即每次请求的内存
大小可能不相同,甚至差异很大,并且这些小内存块的生命周期也不尽相同,所以,系统
需要提供合适的算法来尽可能地满足这些动态的内存请求。在现代计算机系统中,堆
(heap)正是这样一个提供动态内存分配能力的内存抽象。操作系统使用堆来满足各种动
态内存请求,应用程序通过堆获得内存。我们常用的 C/C++基本运行库提供了堆内存管理
的能力,所以,C/C++程序中的 malloc/free 和 new/delete 可以直接在堆的接口上工作。
就本质而言,内存管理算法可以分为两大类:位图标记法和空闲链表法。位图标记法
的思路很简单:假设总的待分配内存的大小为 N 字节,管理内存的粒度为 M 字节,并且
N=M×K,也就是说,内存管理的基本单元为 M 字节,现在共有 K 个单元需要动态管理。
为了记录这 K 个内存单元的使用情况,位图标记法将使用一个共有 K 位的位图(bitmap),
其中每一位的值(0 或者 1)用来说明这一位所对应的内存单元是否空闲。由于位图精确
地记录了每一个内存单元的空闲或已被使用的情况,所以,当内存管理器接收到一个新的
内存申请时,只需扫描位图,就能确定是否有合适的空闲内存可以满足此请求。其做法是,
根据所请求内存的大小,确定需要多少个连续的内存单元来满足此请求,然后在位图中扫
描是否存在连续这么多 0 位,如找到了,则将它们所对应的内存分配给客户,并且将这些
位置成 1。在释放内存时,要求客户指定待释放内存的起始地址和大小,这样内存管理器
就可以计算出此次内存释放对应于位图中哪些连续位,并且将它们置成 0。
位图标记法的实现比较简单,但是需要额外的内存开销,通常为
8×
N
,所以,只需
适当地选取 M,就可以控制这部分额外开销。当然,用户请求的内存大小不一定是 M 字
节的倍数,因而在分配内存时有一定的浪费。平均而言,每次用户请求将导致 M/2 字节
的浪费。另外,内存管理器在分配内存时需要扫描连续多个 0 位,此操作并不高效(复杂
度为 O(K)),这是该算法的一个缺点。
另外一类动态内存管理方法使用链表来描述已分配的和空闲的内存块,称为空闲链表
法。在初始时,整个内存块被当做一个大的空闲块加入到空闲链表中。以后,当内存管理
器接收到一个内存分配请求时,将从空闲链表中找到一个合适的、能提供足够内存的空闲
块,并从该空闲块中分离出足够多的内存,交给客户,剩下的内存(如果还有的话)仍然
Windows
内核原理与实现