第5章 存 储 管 理,5.1 存储管理概述 5.2 存储管理方案 5.3 虚拟存储管理 5.4 Linux的存储管理 习题,5.1 存储管理概述 操作系统中用于管理内存空间的模块称为内存管理模块，它负责内存的全部管理工作，具体地说就是要完成4个功能，即存储空间的分配、存储地址的变换、存储空间的保护以及存储空间的扩充。,5.1.1 内存的分配与回收 内存分配是为进入系统准备运行的程序分配内存空间，内存回收是当程序运行结束后回收其所占用的内存空间。为实现此功能，系统须跟踪并记录所有内存空间的使用情况，按照一定的算法为进程分配和回收内存空间。 存储分配方案主要包括以下要素： (1) 描述存储分配的数据结构：系统需采用某种数据结构(表格、链表或队列等)来登记当前内存使用情况以及空闲区的分布情况，供存储分配程序使用。在每次分配或回收操作后，系统都要相应地修改这些数据结构以反映这次分配或回收的结果。,(2) 实施分配的策略：确定内存分配和回收的算法。好的算法应既能满足进程的运行要求，又能充分利用内存空间。 分配策略及相关数据结构的设计直接决定存储空间的利用率以及存储分配的效率，因而对系统的整体性能有很大的影响。,5.1.2 地址变换 由于用户在编写程序时无法预先确定程序在内存中的具体位置，所以只能采用逻辑地址进行编程。而当程序进入内存后，必须把程序中的逻辑地址转换为程序所在的实际内存地址。这一转换过程称为存储空间的地址变换，或称为地址映射。地址变换是由内存管理模块与硬件的地址变换机构共同完成的。,1. 地址的概念 1) 符号地址 在用高级语言编写的源程序中，我们使用符号名(变量名、函数名、语句标号等)来表示操作对象或控制的转移地址。比如用变量名代表一个存储单元、用函数名代表函数的入口地址、用语句标号代表跳转地址等。这些符号名的集合称为符号名空间。因此，高级语言程序使用的地址空间是符号名空间，编程者不需考虑程序代码和数据的具体存放地址。 例如，以下所示的是一个C源程序的片段：,main() int i=1; i+; 此源程序中没有具体地址，只有符号名。这里main代表的是程序的入口地址，i代表的是一个数据的存放地址。,2) 逻辑地址 编译程序将源代码中的语句逐条翻译为机器指令，为每个变量分配存储单元，并用存储单元的地址替换变量名。这些指令和数据顺序存放在一起，从0开始编排地址，形成目标代码。目标代码所占有的地址范围称为逻辑地址空间，范围是0n-1，n为目标代码的长度。逻辑地址空间中的地址称为逻辑地址，或称为相对地址。在访问内存的指令中用逻辑地址来指定一个操作数的地址，在跳转指令中用逻辑地址来表示要跳转到的那条指令的地址。 例如，对上例所示的源程序进行编译，生成的目标代码的反汇编结果如下：,00000000: 0000004B: LDS R24,0x0060 ;从0060地址取数据，加载到R24 寄存器 0000004D: ADIW R24,0x01 ;R24寄存器内容加1 0000004E: STS 0x0060,R24 ;将R24寄存器内容写回0060地址 00000060: 0x0001 ;i变量的存储单元 ,左侧列出的是指令和数据的逻辑地址，从0地址开始顺序排列。i变量被分配到逻辑地址0060处，i+语句被译为LDS、ADIW和STS 3条指令，它们排在逻辑地址004B、004D和004E处。在目标代码的指令中已看不到符号名了，而代之以具体的地址值。如LDS和STS指令的操作数地址是0060，表示要到这个地址(也就是i变量)读/写数据。,3) 物理地址 物理内存由一系列的内存单元组成，这些存储单元从0开始按字节编址，称为内存地址。当目标程序加载到内存中时，它所占据的实际内存空间就是它的物理存储空间，物理空间中的地址称为物理地址，或称为绝对地址。 每次程序加载时所获得的实际地址空间取决于系统当时的运行状态，因而是不确定的。但物理地址空间不会是从0开始的，因为系统内存的低端地址通常被操作系统占用。由此可看出，程序的逻辑地址空间与物理地址空间是不同的。由于编译程序无法预知程序执行时的实际内存地址，所以目标程序中的地址都是从0开始的逻辑地址，而实际地址只有在程序加载时才能得知。,假设上面例子的程序加载到内存，它分配到的内存地址空间是从1024(即十六进制的0x0400)开始的，则程序中各条指令和变量的地址是原来的相对地址加上1024这个基址。因此程序在内存的起始地址为0x0400，LDS、ADIW和STS 3条指令的绝对地址分别为0x044B、0x044D和0x044E，i变量的绝对地址为0x0460。 图5-1所示是关于内存地址的示意图。仍以前面的程序为例，源程序中的i变量是用符号名i标识的一个存储单元，它没有具体的地址值。i+语句的操作就是对这个存储单元进行的操作。编译时，编译程序为i分配了具体的存储单元，并用该单元的编号地址96(0x0060)替换掉所有i符号名。程序在加载时获得实际的内存空间。如果得到的内存空间的起始地址是1024，则程序中的相对地址96单元就是实际内存的1120(0x0460)单元。,图5-1 内存地址的概5FF5,2. 地址变换 用户编程时只能使用逻辑地址，而CPU执行指令时必须指定物理地址，因此必须在指令执行前进行地址变换，将指令中的逻辑地址转换为CPU可直接寻址的物理地址，这样才能保证CPU访问到正确的存储单元。 假设上面的例子程序加载到内存，它分配到的内存地址空间是从1024开始的，则程序中各条指令和变量的地址都是原来的相对地址加上1024。为了适应这个变化，指令中引用的操作数地址也应进行相应的调整。下面所示是经过地址变换后的目标代码，粗体部分为变换后的操作数的绝对地址。,00000400: 0000044B: LDS R24,0x0460 ;从0460地址取数据，加载到R24 寄存器 0000044D: ADIW R24,0x01 ;R24寄存器内容加1 0000044E: STS 0x0460,R24 ;将R24寄存器内容写回0460地址 00000460: 0x0001 ;i变量的存储单元 ,地址变换的方式有两种： (1) 静态地址变换：程序在装入内存前一次性完成地址转换。程序装入内存后即可直接执行。DOS系统中的程序就是采用这种方式加载的。采用静态地址变换的程序在内存中始终处于最初加载的位置，不可移动。,(2) 动态地址变换：程序在装入内存时不进行地址变换，而是保持指令中的逻辑地址不变。在程序执行过程中，每执行一条指令时，如果指令中用到了逻辑地址，地址变换机构就会自动进行地址转换，将逻辑地址变换为实际地址。例如，当CPU取到LDS R24, 0x0060指令时，先将0060这个逻辑地址变换为绝对地址0460，然后再执行LDS R24, 0x0460指令。 动态地址变换的特点是程序在内存中可移动、可共享。但是动态地址变换需要有硬件的支持，不过目前PC机以上档次的计算机都具有动态地址变换的硬件机构。,5.1.3 内存的保护 内存保护的含义是要确保每个进程都在自己的地址空间中运行，互不干扰，尤其是不允许用户进程访问操作系统的存储区域。对于允许多个进程共享的内存区域，每个进程也只能按自己的权限(只读或读/写)进行访问，不允许超越权限进行访问。 许多程序错误都会导致地址越界，比如使用了未赋值的“野”指针或空指针等。还有一些程序代码则属于恶意的破坏。存储保护的目的是为了防止因为各种原因导致的程序越界和越权行为。为此，系统必须设置内存保护机制，对每条指令所访问的地址进行检查。一旦发现非法的内存访问就会中断程序的运行，由操作系统进行干预。现代操作系统都具有良好的存储保护功能，因此程序错误通常只会导致程序的异常结束，而不会造成系统的崩溃。,常用的存储保护措施有： (1) 界限保护：在CPU中设置界限寄存器，限制进程的活动空间。 (2) 保护键：为共享内存区设置一个读/写保护键，在CPU中设置保护键开关，它表示进程的读/写权限。只有进程的开关代码和内存区的保护键匹配时方可进行访问。 (3) 保护模式：将CPU的工作模式分为用户态与核心态。核心态下的进程可以访问整个内存地址空间，而用户态下的进程只能访问在界限寄存器所规定范围内的空间。,5.1.4 内存的扩充 尽管内存容量不断提高，但相比应用规模的增长来说，内存总是不够的。因此，内存扩充始终是存储管理的一个重要功能。 “扩充”存储器空间的基本思想是借用外存空间来扩展内存空间，方法是让程序的部分代码进入内存，其余驻留在外存，在需要时再调入内存。主要的实现方法有以下3种：,1. 覆盖技术 覆盖(overlay)技术的原理是将一个程序划分为几个模块。程序的必要模块(主控或常用功能)常驻内存，其余模块共享一个或几个存储空间。它们平时驻留在外存中，在需要时才装入内存，覆盖掉某个暂时不用的模块。 覆盖技术的缺点是必须在编程时对程序进行模块划分，并确定程序模块之间的覆盖关系。这无疑增加了编程的复杂度。,2. 交换技术 在多个程序并发执行时，往往有一些程序因等待某事件而暂时不能运行。如果将暂时不能执行的程序换到外存中，就可以获得空闲内存空间来运行别的程序。这就是交换(swapping)技术的思想。与覆盖技术不同的是，交换是以进程为单位进行的。 交换技术的优点是增加了可并发运行的程序数目，且对用户的程序结构没有要求。其缺点是对整个进程进行的换入、换出操作往往需要花费大量的CPU时间。,3. 虚拟存储器 以上两种存储扩充技术都不能称为虚拟存储技术，因为在用户(编程者)眼里看到的还是实际大小的内存。虚拟存储(virtual memory)的原理是只将程序的部分代码调入内存，其余驻留在外存空间中，在需要时调入内存。程序代码的换入和换出完全由系统动态地完成，用户察觉不到。因此，用户看到的是一个比实际内存大得多的“虚拟内存”。 虚拟存储技术的特点是方便用户编程，存储扩充的性能也是最好的。关于虚拟存储器的介绍见5.3节。,5.2 存储管理方案 随着操作系统的发展，内存管理技术也在不断地发展着。本节将简要介绍各种存储管理方案的技术和特点。,5.2.1 单一连续存储管理 最简单的存储器管理方案是在内存中只存放一个应用程序，这个应用程序和操作系统共享存储器。这是最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中。DOS系统采用的就是这种方式。 单一连续存储管理方式的分配策略是将内存分成两个分区，称为系统区和用户区，如图5-2所示。系统区仅供操作系统和硬件使用，用户区供给用户程序使用，它只能容纳一个程序。地址变换方式是静态地址变换，即程序加载前一次性完成全部地址变换。存储保护措施采用界限保护，即不允许用户程序访问操作系统区域，否则就发生地址越界中断。存储扩充的手段只能采用覆盖技术。,图5-2 单一连续存储分配示意图,单一连续存储管理的特点是简单，它只适用于单道程序系统。,5.2.2 分区存储管理 多道程序系统的出现要求内存中能同时容纳多个程序，分区管理方案因而诞生。分区分配是多道程序系统最早使用的一种管理方式，其思想是将内存划分为若干个分区，操作系统占用其中一个分区，其他分区由用户程序使用，每个分区容纳一个用户程序。,1. 简单分区管理 1) 分区分配策略 最初的分区划分方法是固定分区，即系统把内存静态地划分为若干个固定大小的分区。当一个进程被建立时，系统按其程序的大小为其分配一个足够大的分区。由于分区大小是预先划分好的，通常会大于程序的实际尺寸，因此分区内余下的空闲空间就被浪费掉了。图5-3(a)所示为固定分区的内存分配方式。 对固定分区分配策略进行改进就产生了可变分区分配。它的思想是：在程序调入内