英文原文

4. Memory Management

Memory is an important resource that must be carefully managed. While the average home

computer nowadays has two thousand times as much memory as the IBM 7094 (the largest

computer in the world in the early 1960s), programs and the data they are expected to handle

have also grown tremendously. To paraphrase Parkinsons law, 'Programs and their data expandto fill the memory available to hold them.' In this chapter we will study how operating systems

manage memory.Ideally, what every programmer would like is an infinitely large, infinitely fast memory that is also nonvolatile, that is, does not lose its contents when the electric power fails. While we are at it,why not also ask for it to be inexpensive, too? Unfortunately technology cannot turn such dreams into memories. Consequently, most computers have a memory hierarchy, with a small amount of very fast, expensive, volatile cache memory, hundreds of megabytes of medium-speed,medium-price, volatile main memory (RAM), and tens or hundreds of gigabytes of slow, cheap,nonvolatile disk storage. It is the job of the operating system to coordinate how these memoriesare used.

The part of the operating system that manages the memory hierarchy is usually called the

memory manager. Its job is to keep track of which parts of memory are in use and which parts

are not in use, to allocate memory to processes when they need it and deallocate it when they aredone, and to manage swapping between main memory and disk when main memory is too small to hold all the processes. In most systems (but not MINIX 3), it is in the kernel.

In this chapter we will investigate a number of different memory management schemes, ranging from very simple to highly sophisticated. We will start at the beginning and look first at the simplest possible memory management system and then gradually progress to more and more elaborate ones.

As we pointed out in Chap. 1, history tends to repeat itself in the computer world: minicomputer software was initially like mainframe software and personal computer software was initially like minicomputer software. The cycle is now repeating itself with palmtops, PDAs, and embedded systems. In these systems, simple memory management schemes are still in use. For this reason,they are still worth studying.

4.1. Basic Memory Management

Memory management systems can be divided into two basic classes: those that move processes back and forth between main memory and disk during execution (swapping and paging), and

those that do not. The latter are simpler, so we will study them first. Later in the chapter we will examine swapping and paging. Throughout this chapter the reader should keep in mind that swapping and paging are largely artifacts caused by the lack of sufficient main memory to hold all programs and data at once. If main memory ever gets so large that there is truly enough of it, the arguments in favor of one kind of memory management scheme or another may become obsolete.

On the other hand, as mentioned above, software seems to grow as fast as memory, so efficient memory management may always be needed. In the 1980s, there were many universities that ran a timesharing system with dozens of (more-or-less satisfied) users on a 4 MB VAX. Now Microsoft recommends having at least 128 MB for a single-user Windows XP system. The trend

toward multimedia puts even more demands on memory, so good memory management is

probably going to be needed for the next decade at least.

4.1.1. Monoprogramming without Swapping or Paging

The simplest possible memory management scheme is to run just one program at a time, sharing the memory between that program and the operating system. Three variations on this theme are shown in Fig. 4-1. The operating system may be at the bottom of memory in RAM (Random Access Memory), as shown in Fig. 4-1(a), or it may be in ROM (Read-Only Memory) at the top of memory, as shown in Fig. 4-1(b), or the device drivers may be at the top of memory in a ROM and the rest of the system in RAM down below, as shown in Fig. 4-1(c). The first model was formerly used on mainframes and minicomputers but is rarely used any more. The second model is used on some palmtop computers and embedded systems. The third model was used by early personal computers (e.g., running MS-DOS), where the portion of the system in the ROM is called the BIOS (Basic Input Output System).

When the system is organized in this way, only one process at a time can be running. As soon as the user types a command, the operating system copies the requested program from disk to memory and executes it. When the process finishes, the operating system displays a prompt character and waits for a new command. When it receives the command, it loads a new program into memory, overwriting the first one.

4.1.2. Multiprogramming with Fixed Partitions

Except on very simple embedded systems, monoprogramming is hardly used any more. Most

modern systems allow multiple processes to run at the same time. Having multiple processes

running at once means that when one process is blocked waiting for I/O to finish, another one can use the CPU. Thus multiprogramming increases the CPU utilization. Network servers always have the ability to run multiple processes (for different clients) at the same time, but most client (i.e., desktop) machines also have this ability nowadays.

The easiest way to achieve multiprogramming is simply to divide memory up into n (possibly

unequal) partitions. This partitioning can, for example, be done manually when the system is

started up.

When a job arrives, it can be put into the input queue for the smallest partition large enough to hold it. Since the partitions are fixed in this scheme, any space in a partition not used by a job is wasted while that job

剩余内容已隐藏，支付完成后下载完整资料

---

存储器是一种很重要的资源， 必须仔细管理随着科技的发展， 存

储器容量也越来越大。例如， 与20 世纪60 年代初世界最大的计算机IBM

7094 相比， 现在一台普通家用计算机的存储器容量已是它的2 倍。但

与此相对应， 应用程序的规模也越来越大。用Parkmson 定律来说， 就是

“ 存储器有多大， 程序就会有多长' 。在这一章中， 我们将讨论操作系统

是如何来管理存储器的。

从一个程序员的角度来说， 他梦想拥有的存储器应该是容量无限大

的， 速度无限快的， 而且是非易失型的（ nonvolaule ） ， 即掉电后数据不

会丢失。嗯， 既然话已至此， 干脆再加上一条： 价格还要尽量便宜。遗

憾的是， 在目前这个阶段， 同时满足这么多条件的存储器还仅仅是一个梦想， 仅凭现有的科技手段还无法让我们梦想成真。因此， 绝大多数的计算机采用了一种折中的方

法， 也就是说， 建立了一个存储器层次结构。在这个层次结构的最顶层， 是CPU 内部的一些寄存

器， 它们的访问速度是最快的， 但容量不是很大， 价格也比较昂贵。第二层是高速缓存（ cache ） 。

第三层是主存储器（ 内存） ， 它的访问速度适中， 价格也适中， 容量一般在几百兆字节。以上这三

种存储器都是易失型的， 即在断电后， 其内容全部会丢失。第四层是磁盘， 它的访问速度较慢、价

格较便宜， 存储容量一般在几十或几百GB ， 而且是非易失型的。操作系统作为一个系统软件， 其

任务就是协调好这些不同类型的存储器的使用

在操作系统中， 负责管理这个存储器层次结构的那一部分程序， 称为存储管理器（ memory

manager ） 。它的主要任务是： 第一， 记录存储器的使用情况， 即哪些部分正被使用， 哪些部分还空

闲着第二， 当进程需要存储空间时， 就分配给它； 然后当它运行结束后， 再把存储空间回收回来

第三， 如果内存太小， 容不下所有的进程， 那么就需要把内存中暂时不能运行的进程送到磁盘上，

然后再把磁盘上的另一个进程装人内存， 这个交换的过程也要由存储管理器来管理在大多数的操

作系统中， 存储管理器都位于内核之中（ 但MINIX 3 除外） 。

本章我们将讨论一些不同类型的存储管理方案， 在这些方案中， 既有非常简单的， 也有非常复

杂的。我们将按照从简单到复杂的顺序， 循序渐进地来进行介绍。

就像我们在第1 章中指出的那样，再计算机领域，历史总是在重演。

早期的小型机软件有点像

大型机软件， 而早期的个人计算机软件又有点像小型机软件。时至今日， 在掌上型电脑、个人数字

助理（ PDA ） 和嵌人式系统中， 历史又在重演。在这些系统中， 简单的存储管理方案仍然得到了广

泛应用， 因此， 我们在这里讨论这些存储管理方案是有意义的

4 .1 基本的存储管理

存储管理系统可以分为两类， 一类是需要在内存和磁盘之间， 把进程换进换出的； 另一类是不需要这种换进换出的。后者比较简单， 因此我们将首先介绍。在本章稍后， 我们将讨论进程的换进换出和页面置换这里先请大家记住一点， 进程的换进换出和页面置换都是由于内存不足造成的，由于在内存中无法同时容纳所有的程序和数据， 因此只能设计出各种策略来解决这个问题如果内存的容量足够大、足够用， 那么各种存储管理方案之间的差别也就无足轻重了。

另一方面， 如上所述， 软件规模的增长速度与存储容量的增长速度是差不多的， 因此， 有效的存储管理还是有用的。在20 世纪80 年代， 许多大学的分时系统运行在4 MB 的VAX 机上， 还带着许多的用户， 而且这些用户对于能够使用这样的系统， 或多或少还是满意的。而现在微软的单用户Windows xp 系统， 推荐的内存容量为128MB 。此外， 目前的发展趋势是多媒体， 这就需要更多的内存。因此， 即便是在下一个十年， 一个好的存储管理器还是很有必要的。

4 .1.1单道程序存储管理

单道程序存储管理是最简单的一种存储管理方法。它的基本思路是， 把整个内存划分为两个区域， 即系统区和用户区。然后每一次把一个应用程序装人到用户区去运行， 由它和操作系统来共享整个内存。而且从装人开始一直到它运行结束， 在这段时期内， 该程序始终独占着整个用户区。在具体实现单道程序存储管理方案时， 主要有3种实现方式， 如图所示。在图 所示的方式

中， 操作系统被放在了随机存取存储器（ Random Access Memory ， RAM ） 的最低端； 在图4 所示的方式中， 操作系统被放在了内存地址的最高端， 而且是放在了只读存储器（ Read-On1y Memory,ROM ） 里面。在图4 所示的方式中， 操作系统被分成两部分， 一部分是设备驱动程序， 被放在内存高端的ROM 中； 另一部分则放在了内存地址的最低端。对于这三种实现方式， 第一种主要用在早期的大型机和小型机中， 现在已经很少使用了； 第二种主要用在一些掌上型电脑和嵌人式系统中； 第三种主要用在早期的个人计算机系统中， 如MS-DOS 。其中， 存放在内存高端的ROM 中的系统内容， 称为基本输入输出系统（ Basic lnput Output system, BIOS ） 。

在单道程序存储管理方式下， 每一次只能运行一个程序。当用户输人一条命令后， 操作系统就会把相应的程序从磁盘装人内存并运行之。当该进程运行结束后， 操作系统就会显示一个提示符，等待用户输人新的命令。当操作系统收到新的命令后， 就会把一个新的程序装人内存， 从而把旧的那个程序覆盖掉。

4 .1.2 固定分区的多道程序系统

在单道程序存储管理中每次只能运行一个进程， 所以除了一些简单的嵌人式系统以外， 已经没什么人再用它了。大多数现代系统都能够同时运行多个进程。所谓多个进程同时运行， 就是说， 当一个进程由于等待I/O 操作被阻塞时， 另一个进程可以去使用CPU 。所以多道程序增加了CPU 的利用率。对于网络服务器来说， 它总是能够同时运行多个进程（ 每个进程服务于不同的客户） ， 但现在大多数的客户（ 如桌面） 计算机都具备了这种能力。

为了实现多道程序技术， 最简单的办法就是把内存划分为n个分区， 每个分区的大小可以相等，也可以不等。例如， 在系统启动的时候， 由管理员来手工地划分出若干个分区。

当一个新进程到来时， 需要根据它的大小， 把它放置到相应的输人队列中去， 然后等待合适的空闲分区。一方面， 这个分区必须比进程要大， 这样才能装得下它； 另一方面， 这个分区又必须尽可能地小， 这样的话， 在装人了该进程后， 所浪费的内存资源就会尽可能地少（ 在本方案中， 分区设置是固定的， 在一个分区内未被进程使用的空间即被浪费掉了） 。图4 .2(a) 显示了固定分区和多个输人队列的示意图

多个输人队列方式存在一个很明显的缺点， 也就是说， 它可能会出现如下情形： 小分区的输人队列是满的， 而大分区的输人队列却是空的例如， 在图4 .2（a） 中， 在分区1 的输人队列中， 有3 个进程在等待， 而分区3 的输人队列却是空的。也就是说， 一方面， 有很多个小的进程在等着进人内存， 而另一方面， 在内存中却存在着大量的空闲空间。在本例中有300 KB 的空闲空间， 如果能把它平均分给这三个进程， 那么它们就都能进人内存了。为了改变这种不合理的状态， 人们提出了单个输人队列的方法， 如图4 .2（ b ） 所示。也就是说， 对于所有的用户分区， 只设置一个统一的输人队列。当一个新的进程到来时， 就把它加人到这个输人队列中。然后， 当某个分区变得空闲时， 可以采用两种办法来选择合适的进程一种办法是选择离队首最近的、能够装人该分区的进程但是这样的话， 如果选中的进程是一个比较小的进程， 那么就会浪费大量的内存空间。所以另外一种方法是先搜索整个队列， 从中选择能够装人该分区的最大进程， 从而尽可能地减少所浪费的空间。显然，这种算法不利于那些比较小的进程， 因为这种算法会认为它们不值得拥有整个分区。但实际上， 对于这些比较小的进程（ 通常是一些交互式进程） ， 更应该给它们提供良好的服务， 而不是反过来去歧视它们。一种解决办法是始终保留至少一个小分区。这样， 一些小的进程就可以直接运行， 而无须去和其他进程竞争大块的内存分区。

另一种方法是制定一条规则， 规定一个进程被忽略的次数不能超过k 次。每当跳过一个进程时，该进程就得到1 分。当它得到k 分后， 就不能再跳过它。这种固定分区的方法， 在IBM 大型机的OS / 360 上使用了许多年， 操作员早晨开机的时候， 手

工地划分出若干个分区， 并确定每个分区的起始位置和大小等参数。然后， 在系统的整个运行期间，这些参数就固定下来， 不再改变。这套系统称为固定数量任务的多道程序（ Multiprogramnung witha number of Tasks ， MFT ） 。它的优点是易于理解， 也易于实现。当一个新进程到来时， 把它放到输人队列中， 然后等待合适的空闲分区。此时将进程装人该分区运行， 直到其运行结束。不过，时至今日， 很少有操作系统支持这种模型， 即便是在大型机的批处理系统中

4.1.3 重定位和存储保护

多道程序技术引发了两个很重要的问题： 地址重定位和存储保护如图生2 所示， 不同的作业将在不同的地址区间运行。当一个程序被链接时（ 即把主程序、用户编写的函数和库函数组合到同一个地址空间中) ，链接器必须知道程序将在内存的什么地址开始运行。

例如， 假设一个程序的第一条指令是去调用一个起始地址为100 的函数， 这个地址是链接器在生成二进制文件时分配的。如果程序被装人分区1 （ 起始地址为1 佣） ， 那么该指令在执行时， 将跳转到绝对地址为的地方， 而这个地址存放的是操作系统的代码或数据， 并不是它想要访问的那个函数。实际上， 本次调用的目标地址应该是 I(K) 换句话说， 如果程序被装人分区2（ 起始地址为200 KB ） ， 那么函数调用的目标地址应该是200 KB 100， 等等。像这样的问题， 就是内存地址的重定位问题为了解决这个问题， 一种方案是当一个程序被装入内存时， 直接对指令代码进行修改， 一次性地实现从文件内的相对地址到内存中的绝对地址的转换。例如， 如果程序被装人分区1 ， 那么就把它的每个地址加上100KB ； 如果程序被装人分区2 ， 那么就把每个地址加上2 00kb， 等等。为了在装人程序的时候执行这种操作， 链接器必须在可执行文件中包含一个链表或位图， 列出各个需要重定位的地址单元的位置， 也就是说， 需要告诉装载程序， 哪些地方是需要修改的地址， 哪些地方是不能修改的操作码、常量数据等。OS/MFT 采用的就是这种方法。

在装入程序时进行地址重定位， 这种方法并没有解决存储保护问题。由于系统中的程序使用的是绝对地址而不是相对于某个寄存器的相对地址， 因此对于一个恶意的程序来说， 它总是能生成一条指令， 去访问内存中任何它想访问的地址。在多用户系统中， 我们不希望一个进程去写其他进程的内存空间。IBM 采用的保护360 机器的办法是将内存划分为2 的块， 并为每个块分配一个4 位的保护码。另外， 在CPU 的程序状态字（ Program word ， psw ） 中包含一个4 位的密钥。当一个进程在运行时， 如果它访问的内存单元的保护码与PSW 中的密钥不符， 那么360 的硬件就会引起一个陷入。由于只有操作系统才能修改保护码和密钥， 因此这种办法能有效地阻止一个用户进程去破坏其他进程或操作系统的运行。

地址重定位和存储保护的另一种解决方案， 就是在机器中增加两个特殊的硬件寄存器， 即基地址（ base ） 寄存器和边界(limlt ） 寄存器当一个进程被调度执行时， 就把该进程所在的分区的起始地址， 放在基地址寄存器中， 并且把这个分区的长度， 放在边界寄存器中。然后， 在这个进程的运行过程中， 当它需要访问内存单元的时候， 硬件就会自动地把相应的内存地址加上基地址寄存器的值， 从而得到真正的目标地址。因此， 如果基地址寄存器的值为IOOKB ， 那么指令CALL 1 的执行结果就是CALL 100 KB 100 。这样， 对于指令本身来说， 就不用做任何修改。在存储保护方面， 对于每一次的内存访问， 都要把该地址与边界寄存器的值进行比较， 以防止它去访问分区以外的内存区域。当然， 在这种方案中， 一个前提条件就是必须用硬件把基地址寄存器和边界寄存器保护起来， 不能让用户程序随便去修改它们， 否则， 这种方法就失去了意义。

这种方法的一个缺点是， 在每一次内存访问中， 都必须增加一次加法和比较操作。比较操作的速度比较快， 但加法操作的速度比较慢（ 需要进位传播） 一一除非使用特殊的加法电路

CDC 66 （ 世界上第一台巨型机） 使用了这种方案。早期的IBM PC 中的lntel 8088 CPU 使用了这种方案的一个较弱版本· 一一有基地址寄存器， 但没有边界寄存器。时至今日，已经没有计算机再采用这种方案了。

4.2 交换技术

在批处理系统中， 采用固定分区的存储管理方案是简单而高效的。当一个作业需要运行时， 先是在输人队列中等待， 等到有了一个足够大的空闲分区后， 就把它装人该分区去运行。在作业运行期间， 它始终位于内存中， 直到运行结束。只要在内存中能够有足够多的作业， 使CPU 始终保持繁忙的状态， 那么就没有理由去使用某种更为复杂的存储管理方案。

但在分时系统或面向图形的个人计算机中情形就不同了， 有时会出现内存不够用的情形， 无法同时容纳所有当前活动的进程。此时， 就必须把多出来的进程暂时保

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[238721]，资料为PDF文档或Word文档，PDF文档可免费转换为Word