预计阅读本页时间:-
第3章 存储管理
内存(RAM)是计算机中一种需要认真管理的重要资源。就目前来说,虽然一台普通家用计算机的内存容量已经是20世纪60年代早期全球最大的计算机IBM 7094的内存容量的10 000倍以上,但是程序大小的增长速度比内存容量的增长速度要快得多。正如帕金森定律所指出的:“不管存储器有多大,程序都可以把它填满”。在这一章中,我们将讨论操作系统是怎样对内存创建抽象模型以及怎样管理内存的。
每个程序员都梦想拥有这样的内存:它是私有的、容量无限大的、速度无限快的,并且是永久性的存储器(即断电时不会丢失数据)。当我们期望这样的内存时,何不进一步要求它价格低廉呢?遗憾的是,目前的技术还不能为我们提供这样的内存。也许你会有解决方案。
除此之外的选择是什么呢?经过多年探索,人们提出了“分层存储器体系”(memory hierarchy)的概念,即在这个体系中,计算机有若干兆(MB)快速、昂贵且易失性的高速缓存(cache),数千兆(GB)速度与价格适中且同样易失性的内存,以及几兆兆(TB)低速、廉价、非易失性的磁盘存储,另外还有诸如DVD和USB等可移动存储装置。操作系统的工作是将这个存储体系抽象为一个有用的模型并管理这个抽象模型。
广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元
操作系统中管理分层存储器体系的部分称为存储管理器(memory manager)。它的任务是有效地管理内存,即记录哪些内存是正在使用的,哪些内存是空闲的;在进程需要时为其分配内存,在进程使用完后释放内存。
本章我们会研究几个不同的存储管理方案,涵盖非常简单的方案到高度复杂的方案。由于最底层的高速缓存的管理由硬件来完成,本章将集中介绍针对编程人员的内存模型,以及怎样优化管理内存。至于永久性存储器——磁盘——的抽象和管理,则是下一章的主题。我们会从最简单的管理方案开始讨论,并逐步深入到更为缜密的方案。
3.1 无存储器抽象
最简单的存储器抽象就是根本没有抽象。早期大型计算机(20世纪60年代之前)、小型计算机(20世纪70年代之前)和个人计算机(20世纪80年代之前)都没有存储器抽象。每一个程序都直接访问物理内存。当一个程序执行如下指令:
MOV REGISTER1,1000
计算机会将位置为1000的物理内存中的内容移到REGISTER1中。因此,那时呈现给编程人员的存储器模型就是简单的物理内存:从0到某个上限的地址集合,每一个地址对应一个可容纳一定数目二进制位的存储单元,通常是8个。
在这种情况下,要想在内存中同时运行两个程序是不可能的。如果第一个程序在2000的位置写入一个新的值,将会擦掉第二个程序存放在相同位置上的所有内容,所以同时运行两个程序是根本行不通的,这两个程序会立刻崩溃。
不过即使存储器模型就是物理内存,还是存在一些可行选项的。图3-1展示了三种变体。在图3-1a中,操作系统位于RAM(随机访问存储器)的底部;在图3-1b中,操作系统位于内存顶端的ROM(只读存储器)中;而在图3-1c中,设备驱动程序位于内存顶端的ROM中,而操作系统的其他部分则位于下面的RAM的底部。第一种方案以前被用在大型机和小型计算机上,现在很少使用了。第二种方案被用在一些掌上电脑和嵌入式系统中。第三种方案用于早期的个人计算机中(例如运行MS-DOS的计算机),在ROM中的系统部分称为BIOS(Basic Input Output System,基本输入输出系统)。第一种方案和第三种方案的缺点是用户程序出现的错误可能摧毁操作系统,引发灾难性后果(比如篡改磁盘)。

当按这种方式组织系统时,通常同一个时刻只能有一个进程在运行。一旦用户键入了一个命令,操作系统就把需要的程序从磁盘复制到内存中并执行;当进程运行结束后,操作系统在用户终端显示提示符并等待新的命令。收到新的命令后,它把新的程序装入内存,覆盖前一个程序。
在没有内存抽象的系统中实现并行的一种方法是使用多线程来编程。由于在引入线程时就假设一个进程中的所有线程对同一内存映像都可见,那么实现并行也就不是问题了。虽然这个想法行得通,但却没有被广泛使用,因为人们通常希望能够在同一时间运行没有关联的程序,而这正是线程抽象所不能提供的。更进一步地,一个没有内存抽象的系统也不大可能具有线程抽象的功能。
在不使用内存抽象的情况下运行多道程序
但是,即使没有内存抽象,同时运行多个程序也是可能的。操作系统只需要把当前内存中所有内容保存到磁盘文件中,然后把下一个程序读入到内存中再运行即可。只要在某一个时间内存中只有一个程序,那么就不会发生冲突。这样的交换概念会在下面讨论。
在特殊硬件的帮助下,即使没有交换功能,并发地运行多个程序也是可能的。IBM 360的早期模型是这样解决的:内存被划分为2KB的块,每个块被分配一个4位的保护键,保护键存储在CPU的特殊寄存器中。一个内存为1MB的机器只需要512个这样的4位寄存器,容量总共为256字节。PSW(Program Status Word,程序状态字)中存有一个4位码。一个运行中的进程如果访问保护键与其PSW码不同的内存,360的硬件会捕获到这一事件。因为只有操作系统可以修改保护键,这样就可以防止用户进程之间、用户进程和操作系统之间的互相干扰。
然而,这种解决方法有一个重要的缺陷。如图3-2所示,假设我们有两个程序,每个大小各为16KB,如图3-2a和图3-2b所示。前者加了阴影表示它和后者使用不同的内存键。第一个程序一开始就跳转到地址24,那里是一条MOV指令。第二个程序一开始跳转到地址28,那里是一条CMP指令。与讨论无关的指令没有画出来。当两个程序被连续地装载到内存中从0开始的地址时,内存中的状态就如同图3-2c所示。在这个例子里,我们假设操作系统是在高地址处,图中没有画出来。

程序装载完毕之后就可以运行了。由于它们的内存键不同,它们不会破坏对方的内存。但在另一方面会发生问题。当第一个程序开始运行时,它执行了JMP 24指令,然后不出预料地跳转到了相应的指令,这个程序会正常运行。
但是,当第一个程序已经运行了一段时间后,操作系统可能会决定开始运行第二个程序,即装载在第一个程序之上的地址16 384处的程序。这个程序的第一条指令是JMP 28,这条指令会使程序跳转到第一个程序的ADD指令,而不是事先设定的跳转到CMP指令。由于对内存地址的不正确访问,这个程序很可能在1秒之内就崩溃了。
这里关键的问题是这两个程序都引用了绝对物理地址,而这正是我们最需要避免的。我们希望每个程序都使用一套私有的本地地址来进行内存寻址。下面我们会展示这种技术是如何实现的。IBM 360对上述问题的补救方案就是在第二个程序装载到内存的时候,使用静态重定位的技术修改它。它的工作方式如下:当一个程序被装载到地址16 384时,常数16 384被加到每一个程序地址上。虽然这个机制在不出错误的情况下是可行的,但这不是一种通用的解决办法,同时会减慢装载速度。而且,它要求给所有的可执行程序提供额外的信息来区分哪些内存字中存有(可重定位的)地址,哪些没有。毕竟,图3-2b中的“28”需要被重定位,但是像
MOV REGISTER1,28
这样把数28送到REGISTER1的指令不可以被重定位。装载器需要一定的方法来辨别地址和常数。
最后,正如我们在第1章中指出的,计算机世界的发展总是倾向于重复历史。虽然直接引用物理地址对于大型计算机、小型计算机、台式计算机和笔记本电脑来说已经成为很久远的记忆了(对此我们深表遗憾),但是缺少内存抽象的情况在嵌入式系统和智能卡系统中还是很常见的。现在,像收音机、洗衣机和微波炉这样的设备都已经完全被(ROM形式的)软件控制,在这些情况下,软件都采用访问绝对内存地址的寻址方式。在这些设备中这样能够正常工作是因为,所有运行的程序都是可以事先确定的,用户不可能在烤面包机上自由地运行他们自己的软件。
虽然高端的嵌入式系统(比如手机)有复杂的操作系统,但是一般的简单嵌入式系统并非如此。在某些情况下可以用一种简单的操作系统,它只是一个被链接到应用程序的库,该库为程序提供I/O和其他任务所需要的系统调用。操作系统作为库实现的常见例子如流行的e-cos操作系统。