7.1背景

内存时现代计算机运行的中心。内存有很大一组字或字节组成，每个字或字节 都有他们自己的内存地址。CPU根据程序计数器（PC）的值从内存中提取指令，这些指令可能会引起进一步对特定内存地址的读取和写入。
一个典型指令执行周期，首先从内存中读取指令。接着该指令被解码，且可能需要从内存中读取操作数。在指令对操作数执行后，其结果可能被存回到内存。内存单元只看到地址流，而并不知道这些地址流是如何产生的（由指令计数器、索引、简介寻址、实地址）或他们是什么地址（指令或数据）。

7.1.1 基本硬件

CPU所能直接访问的存储器只有内存和处理器内的寄存器。机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。如果数据不在内存中，那么CPU使用前必须先把数据移到内存中。

CPU内置寄存器通常可以在一个CPU时钟周期内完成访问。对于寄存器的内容，绝大多数CPU可以在一个时钟周期内解析并执行一个或多个指令，而对于内存就不行。完成内存访问需要多个CPU时钟周期，由于没有数据以便完成正在执行的指令，CPU通常需要暂停（stall）。由于内存访问频繁，这种情况是难以忍受的，解决方法是在CPU与内存之间增加高速内存。这种协调速度差异的内存缓冲区，称为高速缓存（cache）。（这一方面是计算机组成原理的内容）

除了保证访问物理内存的相对速度之外，还要确保操作系统不会被用户进程所访问，以及确保用户进程不会被其他用户进程访问。这种保护可通过硬件来实现，硬件实现由许多方法，将在之后讨论。

其中一种可能方案为：
首先确保每个进程都有独立的内存空间，为此，需要确定进程可访问的合法地址的范围，并确保进程只能访问其合法地址。通过基地址寄存器（base register）和界限地址寄存器（limit register）可以实现这种保护。

基地址寄存器（base register）含有最小的物理内存地址，界限地址寄存器（limit register）决定了范围的大小。例如：如果基地址寄存器为300040而界限寄存器为120900，那么程序可以访问从300040到420940的所有地址。
这里写图片描述
内存空间保护的实现，是通过CPU硬件对用户模式所产生的每个地址与寄存器的地址进程比较来完成的。如果访问了不该访问的地址，则会陷入到操作系统中，并作为致命错误处理。


只有操作系统可以通过特殊的特权指令来加载基地址寄存器和界限地址寄存器。由于特权指令只可在内核模式下执行，而只有操作系统在内核模式下执行，所以只有操作系统可以加载基地址寄存器和界限地址寄存器。这种方案允许操作系统修改两个寄存器的值，而不允许用户程序去修改他们。操作系统在内核模式下，可以无限制地访问操作系统和用户内存。因此操作系统可以将用户程序装入用户内存，在出错时输出这些程序，访问并修改系统调用的参数等。

7.1.2 地址绑定

通常，程序以二进制可执行文件的形式存储在磁盘上。为了执行，程序被调入内存并放入进程空间内。
根据所使用的内存管理方案，进程在执行时，可以在磁盘和内存之间移动。在磁盘上等待调入内存以便执行的进程形成输入队列（input queue）。

通常的步骤是从输入队列中选取一个进程并装入内存。进程在执行时，会访问内存中的指令和数据。最后，进程终止，其地址空间将被释放。
许多系统允许用户进程放在物理地址的任意位置。这种组合方式会影响用户程序能够使用的地址空间。在绝大多数情况下，用户程序在执行前，会经过好几个步骤，在这些步骤中，地址可能有不同的表示形式，源程序中的地址通常是用符号（如count）来表示，编译器通常将这些符号地址绑定（bind）在可重定位的地址（如：从本模块开始的第14字节）。链接程序或加载程序再将这些可重定位的地址绑定成绝对地址（如74014）。每次绑定都是从一个地址空间到另一地址空间的映射。
通常，将指令与数据绑定到内存地址有以下几种情况：
编译时（compile time）：如果编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码（absolute code）。如果将来开始地址发生变化，那么就必须重新编译代码。
加载时（load time）：当编译时不知道进程将驻留在内存的什么地方，那么编译器就必须生成可重定位代码（reloadable code）。绑定会延迟到加载时才进行。如果开始地址发生变化。只需要重新加载用户代码已引入改变值。
执行时（execution time）：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才发生。绝大多数通用计算机操作系统采用这种方法。

7.1.3逻辑地址空间和物理地址空间

生成的地址通常称为逻辑地址（logical address），而内存单元所看到的地址（即加载到内存地址寄存器（memory-address register）中的地址）通常称为物理地址（physical address）。
编译和加载时的地址绑定方法生成相同的逻辑地址和物理地址。但是，执行时的地址绑定方案导致不同的逻辑地址和物理地址。对于这种情况，通常称逻辑地址为虚拟地址（virtual address）。由程序所生成的所有逻辑地址称为逻辑地址空间（logical address space），与这些逻辑地址相对应的物理地址的集合称为物理地址空间（physical address space）。
运行时从虚拟地址到物理地址的映射由被称为内存管理单元（memory-management unit，MMU）的硬件设备来完成。有很多可选择的方法来完成这种映射，如使用一个简单的MMU方案来实现这种映射，这是一种基地址寄存器方案的推广，基地址寄存器在这里称为重定位寄存器（relocation register），用户进程所生成的地址在送交内存之前，都加上重定位寄存器的值。
假如，基地址为14000，那么用户对地址346的访问将映射为地址14346。

用户程序绝对不会看到真正的物理地址。如，程序可以创建一个指向位置346的指针，将他保存在内存中，使用它，与其他地址进行比较等等，所有这些操作都是基于346进行的。只有当它作为内存地址时（例如，在简介加载和存储时），它才进行相对于基地址寄存器的重定位。用户程序处理逻辑地址时，内存映射硬件将逻辑地址转变为物理地址。所引用的内存地址只有在引用时才最后定位。
逻辑地址空间绑定到单独的一套物理地址空间，这一概念对内存的管理至关重要。

7.1.4 动态加载

一个进程的整个程序和数据如果都处于物理内存中，则进程的大小受物理内存大小的限制。
为了获得更好的内存空间使用率，使用动态加载，即一个子程序只有在调用时才被加载。
所有的子程序都以可重定位的形式保存在磁盘中。主程序装入内存并执行。当一个子程序需要调用另外一个子程序的时候，调用子程序首先检查另一个子程序是否已经被加载。如果没有，可重定位的链接程序将用来加载所需要的子程序，并更新程序的地址表以反映这一变化。接着控制传递给新加载的子程序。
动态加载的优点是不用子程序绝对不会被加载，如果大多数代码需要处理异常情况，如错误处理，那么这种方法特别有用。对于这种情况，虽然总体上程序比较大，但是所使用的部分可能小很多。
动态家住在不需要操作系统提供特别的支持。利用这种方法设计程序主要是用户的责任。

7.1.5 动态链接与共享库

有的操作系统只支持静态链接，此时系统语言库的处理与其他目标模块一样，由加载程序合并到二进制程序镜像中。
动态链接的特点与动态加载类似。只是这里不是将加载延迟到运行时，而是将链接延迟到运行时。这一特点通常用于系统库，如语言子程序库。没有这一特点，系统上的所有程序都需要一份语言库的副本，这一需求浪费了磁盘空间和内存空间。
如果由动态链接，二进制镜像中每个程序的应用都有一个存根（stub）。存根是一小段代码，用以指出如何定位适当的内存驻留的库程序，或如果该程序不在内存中应如何安装入库。不管怎么样，存根会用子程序地址来代替自己，并开始执行子程序。因此下次再执行程序代码时，就可以直接进行，而不会因动态链接产生任何开销。采用该种方案，使用语言库的所有进程只需要一个库代码副本就可以了。
动态连接也可用于库更新。一个库可以被新的版本所替代，且使用该库的所有程序会自动使用新的版本。没有动态链接，所有这些程序必须重新链接以便访问。
为了不使程序错用新的、不兼容版本的库，程序和库将包括版本信息。多个版本的库都可以装入内存，程序通过版本信息来确定使用哪个库副本。
因此，只有用新库编译的程序才会收到新库的不兼容变化影响。在新程序装入之前所链接的其他程序可以继续使用老库。这种系统也称为共享库。
与动态加载不同，动态链接通常需要操作系统帮助。如果内存中的进程是彼此保护的，那么只有操作系统才可以检查所需子程序是否在其他进程内存空间内，或是允许多个进程访问同一内存地址。

7.2连续内存分配

内存必须容纳操作系统和各种用户进程，因此应该尽可能有效地分配内存的各个部分。
内存通常分为两个区域：一个用于驻留操作系统，一个用于用户进程。操作系统可以位于低内存或高内存，影响这一决定的主要因素是中断向量的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统放到低内存

通常需要将多个进程同时放入内存中，因此需要考虑如何为输入队列中需要调入内存的进程分配内存空间。
采用连续内存分配（contiguous memory allocation）时，每个进程位于一个连续的内存区域。

7.2.1 内存映射与保护

通过采用重定位寄存器和界限地址寄存器可以实现保护。
重定位寄存器含有最小的物理地址；界限地址寄存器含有逻辑地址的范围值。

这样每个逻辑地址必须小于界限地址寄存器。MMU动态的将逻辑地址加上重定位寄存器的值后映射称物理地址。映射后的物理地址再交送内存单元。

当CPU调度器选择一个进程来执行时，作为上下文切换工作的一个部分，调度程序会用正确的值来初始化重定位寄存器和界限地址寄存器，由于CPU所产生的每一个地址都需要与寄存器进程核对，所以保证操作系统和其他用户程序和数据不受该进程运行所影响。
重定位寄存器机制为允许操作系统动态改变提供了一个有效方法。如某驱动程序（或其他操作系统服务）不常使用便可以不必在内存中，这类代码有时称为暂时（transient）操作系统代码，它们根据需要调入或调出。因此，使用这种代码可以在程序执行时动态改变操作系统的大小。

7.2.2 内存分配

最简单的内存分配方法之一是将内存分为固定大小的分区。每个分区只能容纳，一个进程。那么多道程序的程度会受分区数限制。如果使用这种多分区方法，当一个分区空闲时，可以输入队列中选择一个进程，以调度入空闲分区。当进程终止时，其分区可以被其他进程所使用。这种方法现在已不再使用。对于固定分区方案的推广（称为MVT），它主要用于批处理环境。也可用于纯分段内存管理的分时操作系统。

在可变分区方案中，操作系统有一个表，用于记录那些内存可用和那些内存已被占用。一开始，所有内存都可用于用户进程，因此可以作为一大块可用内存，称为孔（hole），当新进程需要内存时，为该进程查找足够大的孔，如果找到，可以从该孔进程分配所需的内存，孔内存未分配的内存可用于下次再用。
随着进程进入系统，它们将被加入输入队列中。操作系统根据调度算法来对输入队列进行排序。内存不断分配给进程，知道下一个进程的内存需求不能满足为止，如果没有足够大的孔来装入进程，操作系统可以等到有足够大的空间，或者往下扫描输入队列以确定是否其他内存需求较小的进程可以被满足。
通常，一组不同大小的孔分散在内存中，当新进程需要内存时，系统为进程查找足够大的孔。如果孔太大，那么久分成两块：一块分配给新进程，另一块环回到孔集合，当进程终止时，它将释放其内存，该内存将还回给孔集合。如果孔与其他孔相邻，那么将这些孔合并为大孔。这时，系统可以检查是否有进程在等待内存空间，新合并的内存空间是否满足等待进程。

这种发放时通用动态存储分配问题的一种情况（根据一组空闲孔来分配大小为n的请求），这个问题有许多解决办法。从一组可用孔中选择一个空闲孔德最为常用德方法有首次适应（第一个足够大的孔）、最佳适应（最小的足够大的孔）、最差适应（分配最大的孔）。
首次适应：分配第一个足够大的孔，查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲孔，就可以停止；
最佳适应：分配最小的足够大的孔，必须查找整个列表，除非列表按照大小排序，这种方法可以产生最小剩余孔；
最大适应：分配最大的孔，同样必须查找整个列表，除非列表按照大小排序。这种方法可以产生最大剩余孔。该孔可能比最佳适应方法产生的最小剩余孔更有用。

7.2.1 碎片

首次适应和最佳适应算法都有外部碎片问题（external fragmentation）。随着进程装入和移出内存，空闲内存空间被分割为小分段，当所有总的空用内存之和可以满足请求，但并不连续时，这就出现了外部碎片问题。最坏的情况下，每两个进程之间就有空闲块（或浪费）。如果这些内存是一整块，那么就可以再运行多个进程。
在首次适应和最佳适应之间的选择可能会影响碎片的量。另一个影响因素是是从空闲块的哪端开始分配。不管使用那种算法外部碎片始终是个问题。
根据内存的总大小和平均进程大小的不同，外部碎片的重要程度也不同。例如，对采用首次适应方法的统计说明，对于首次适应方法不管怎么优化，假定N个可分配块，那么可能有0.5N个块为外部碎片。即1/3内存可能不能使用，这一特性称为50%规则。
内存碎片可以是内部的，也可以是外部的。如果内存以固定大小的块为单元来分配，进程所分配的内存可能比所要的要大。这两个数字之差称为内部碎片（internal fragmentation）这部分内存在分区内，但又不能使用。
一种解决外部碎片问题的方法是紧缩（compaction），紧缩的目的是移动内存内容，以便所有空闲空间合并成一整块。但是紧缩并非总是可能的。如果重定位是静态的，并且在汇编时或装入时进行的，那么就不能紧缩。
紧缩仅在重定位是动态的并在运行时可采用。如果地址被动态重定位，可以首先移动程序和数据，然后再跟据新基地址基地的值来改变址寄存器。如果采用紧缩，还要评估其开销，最简单的合并算法是简单地将所有进城移到内存的一端，而将所有的孔移到内存的另一端，以生成一个大的空闲块。这种方案开销较大。
另一种解决方法外部碎片问题的方法是允许物理地址为非连续的。这样只要有物理内存就可以为进程分配。这种方案有两种互补的实现技术：分页和分段。这两种技术也可以合并。
分页产生内部碎片，分段产生外部碎片

7.3 分页

分页内存管理方案允许进程的物理内存空间可以是非连续的。分页避免了将不同大小的内存块匹配到交换空间上，前面叙述的内存管理方案都有这个问题，当位于内存中的代码和数据需要换出时，必须现在欸分存储上找到空间，这时问题就产生了。备份存储也有前面所述的与内存相关的碎片问题，只不过访问更慢。
传统上，分页支持一直是有硬件来处理的。最近的设计是通过将硬件和操作系统相配合来实现分页。

7.3.1 基本方法