存储器管理95191

1、第四章 存储器管理第一节 基本概念1 程序的装入和链接在多道程序环境下，要使程序运行，必须创建进程，而创建进程第一件事就是将程序和数据装入内存。一个用户源程序要变为在内存中可执行的程序，通常要进行以下处理：（1）编译：由编译程序将用户源程序编译成若干个目标模块（2）链接：由链接程序将目标模块和相应的库函数链接成装入模块（3）装入：由装入程序将装入模块装入内存1.1 一些概念u 逻辑地址-用户程序经编译后，每个目标模块以0为基地址进行的顺序编址。也就是相对与初始地址的，逻辑地址又称相对地址，相对基地址而言。u 物理地址-内存中各物理存储单元的地址从统一的基地址进行的顺序编址。物理地址又称绝对地址

2、，它是数据在内存中的实际存储地址。u 地址空间（名空间）：指用户程序使用的全部地址。地址空间中的每个地址单元编号称为逻辑地址（logical address），由于通常逻辑地址都是相对于程序的起始地址的，故又称为相对地址（relative address）。u 存储空间：指内存中存储数据的物理单元的集合。这些物理单元的集合称为物理地址（physical address）或绝对地址（absolute address）。u 重定位：当作业的地址空间与存储空间不一致时，所进行的地址调整以便使作业能够执行的过程称为重定位。重定位实质是地址变换，即作业地址空间中的逻辑地址变换为主存空间的物理地址。根据地

3、址变换进行的时间及采用技术手段不同，可分为静态重定位和动态重定位两类。1.2 程序的装入将装入模块装入内存时。可以有以下装入方式。1.2.1 绝对装入方式思想:编译时，若知道程序将驻留内存的什么位置，则编译程序将产生绝对地址的目标代码，链接得到装入模块。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，因此不用对程序和数据进行修改。适用：单道程序环境1.2.2重定位装入方式基本思想：在多道环境下，不可能预知程序应该放在内存的哪个位置，装入程序在装入时根据内存的实际情况把相对地址（逻辑地址）转换为绝对地址，装入到适当的位置。

4、（在装入时进行地址转换）静态重定位。适用：用于多道程序环境。课本例子见下图P1041.2.3动态运行时装入方式（动态重定位的装入方式）思想：在把装入模块装入内存后，并不立即进行地址转换，而是把相对地址到绝对地址的的地址转换推迟到程序真正开始运行的时候再进行。需要一个重定位寄存器支持。其本质就是在程序运行的过程中进行地址转换。适用：多道环境中程序在内存中改变位置。1.2.4 三种装入方式的对比绝对装入方式只能将装入模块装入到内存中事先指定的位置，在多道程序环境下是不可能事先知道每一道程序在内存中的位置的，因此这种装入方式只能用于单道程序环境。地址转换时机：程序中所使用的绝对地址，既可在编译或汇编

5、时给出，也可由程序员直接赋予。适用于单道 环境。可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境；然而它不允许程序在运行中移动位置。地址转换时机发生于程序装入内存时发生。适用于动态运行时装入方式允许程序在运行中移动位置，需要特殊硬件的支持。地址转换时机发生于程序运行时。适用于1.2 程序的链接由链接程序将目标模块和相应的库函数链接成装入模块。按照链接时间不同分为三种：1.2.1 静态链接方式思想：我们常说静态链接实在生成可执行文件时进行的。是一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块(执行文件)，以后不再拆开。实现

6、静态链接应解决的问题：（1）相对地址的修改。每个模块中所有相对地址的修改。比如，原起始地址为0，现在为L。则模块中所有相对地址都要加L。（2）变换外部调用符号。每个模块中所用的外部调用符号也都要变换。存在问题：（1）不便于对目标模块的修改和更新（2）无法实现对目标模块的共享如图 动态链接在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。优点 共享：多个进程可以共用一个DLL，节省内存，减少文件交换。 部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存

7、。 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。 便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。.1 装入时动态链接思想：指将一组目标模块在装入内存时，边装入边链接的方式。具有便于修改和更新、便于实现对目标模块的共享。存在问题：由于程序运行所有可能用的目标模块在装入时均全部链接在一起，所以将会把一些不会运行的目标模块也链接进去。如程序中的错误处理模块1.2.2.2 运行时动态链接思想：在程序运行中需要某些

8、目标模块时，才对它们进行链接的方式。具有高效且节省内存空间的优点。第二节 连续分配方式1 单一连续分配（单独分区分配）最简单的一种存储管理方式，但只能用于单用户、单任务的OS中。概念：单一连续分配就是整个主存区域的用户空间均归一个用户作业使用。存储管理方法：将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）。其中用户区是指除了系统区外的内存空间，提供给用户程序使用。采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存。主要特点：管理简单，只需小量的软件和硬件支持，便于用户了解和使用。但因内存中只装入一道作业运行，内存空间浪费大，各类资源的利用率也不高

9、。例子：一个容量为256KB的内存，操作系统占用32KB，剩下224KB全部分配给用户作业，如果一个作业仅需64KB，那么就有160KB的存储空间被浪费。2 固定分区分配分区分配方式是满足多道程序设计需要的一种最简单的存储管理方法。2.1 思想：将内存分成若干个分区（大小相等/不相等），除OS占一区外，其余的每一个分区容纳一个用户程序。这样来实现多道并发。2.2 分区划分方法：分区大小相等，分区大小不等。但事先必须确定，在运行时不能改变。即分区大小及边界在运行时不能改变。2.3 内存分配：首先：要先建立一张分区说明表或使用表，以记录分区号、分区大小、分区的起始地址及状态（已分配或未分配）。其次

10、：当某个用户程序要装入内存时，由内存分配程序检索分区说明表，从表中找出一个满足要求的尚未分配的分区分配该程序，同时修改说明表中相应分区的状态；若找不到大小足够的分区，则拒绝为该程序分配内存。第三：当程序执行完毕，释放占用的分区，管理程序将修改说明表中相应分区的状态为未分配，实现内存资源的回收。2.4 特点主要特点：管理简单，但因作业的大小并不一定与某个分区大小相等，从而使一部分存储空间被浪费。所以主存的利用率不高3 动态分区分配3.1 基本思想：根据进程的实际需要，动态的为其分配内存空间。因此分区大小是动态可变的，分区的个数也是可变的。3.2 主要特点管理简单，只需小量的软件和硬件支持，便于用

11、户了解和使用。进程的大小与某个分区大小相等，从而主存的利用率有所提高。3.3 分区分配的数据结构为描述空闲分区合已分配的分区，引入如下数据结构。3.3.1 空闲分区表用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目重含有分区序号，分区起始地址，分区大小等数据项。如下图3.3.2 空闲分区链用链头指针将系统中的空闲分区链接起来，构成空闲分区链。每个空闲分区的起始部分存放相应的控制信息(如大小,指向下一空闲分区的指针等).就是在分区头设置一个前向指针，分区尾部设置一个后向指针，这样把所有空闲分区连起来。3.4 分区分配算法把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链

12、中选择一合适分区分配给该作业。有下面三种分配算法：3.4.1 首次适应算法算法过程：算法要求空闲分区（链）按地址递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。算法的特点优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。3.4.2 循环首次适应算法算法过程：由首次

13、适应算法发展而来，每次为进程分配内存空间时，不是从链首开始，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个满足要求的空闲分区。该算法要设置一个起始查寻指针。用于标识下一次起始查寻的空闲分区。算法特点使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。3.4.3 最佳适应算法算法过程：算法要求空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则

14、与首次适应算法相同，将剩余空闲分区仍留在空闲分区表/链中。算法特点若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，,从而保留了大的空闲分区,但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。3.5 分区分配操作这里所谓的操作是：分配内存和回收内存。3.5.1 分配内存操作实际上是分区的分割。具体过程如下：设请求的分区大小为u.size，空闲分区的大小为m.size,若£size(size是事先规定的不再切割的剩余分区

15、的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则,即多余部分超过size，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中，然后，将分配区的首址返回给调用者。分配流程图：3.5.2 回收内存操作基本过程：当作业执行结束时，应回收已使用完毕的分区。系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。回收分区与已有空闲分区的相邻情况有以下四种： 1）回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首地址,大小为二者之和。 2）回收分区下邻接一个空闲分区,合并后首

16、地址为回收分区的首地址,大小为二者之和。 3）回收分区上下邻接空闲分区,合并后首地址为上空闲分区的首地址,大小为三者之和。4）回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息，并根据其首地址插入到空闲链的适当位置。如下图：4可重定位分区分配4.1 动态重定位的引入在连续分配方式中，我们必须把一个系统或用户程序装入一个连续的内存空间。但是，如果在系统中只有一些小分区并且这些分区不相邻链接，即使它们的相加之后的空间大于要装入的程序，也不可能把程序装入这些内存中。这些小分区就叫做“零头”或“碎片”。处理思路“紧凑”：将内存中的所有作业移动到内存的另一端，使它们全部相邻。这样

17、，就可以把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入了。称为“紧凑”或“拼接”。出现问题：紧凑后，明显可以看出内存中的数据和程度的存放位置发生了变化，如果不对程序和数据的地址加以更改，则程序不能运行，因此我们需要重定位。也就是说在每次紧凑之后需要重定位。4.2 动态重定位的实现引入重定位寄存器，程序在执行时，真正访问的内存地址是相对地址和重定位寄存器中的地址相加后的地址。见课本图p111动态重定位：地址变换过程是在程序执行期间，随着对每条指令或数据的访问时才进行的。因此称为动态重定位。4.3动态重定位分区分配算法和动态分区分配算法基本相同，只是增加了紧凑功能。算法流程如下：5 对

18、换 了解多道程序环境下，会出现某些进程未执行而占据内存空间，而大量的作业在外存而不能进入内存执行。为了充分的利用内存空间，我们引入了覆盖和对换。覆盖是早期的操作系统中运用，有兴趣的同学了解一下对换：将暂时不用的某个进程及数据（首先是处于阻塞状态优先级最低的，根据系统的采用算法决定）部分（或全部）从内存移到到外存（备份区或对换区，采用连续分配的动态存储管理方式）中去，让出内存空间，同时将某个需要的进程调入到内存中，让其运行。交换到外存的进程需要时可以被再次交换回（选择换出时间最久的，也是根据系统采用的算法决定）内存中继续执行。这种内存扩充技术就是交换技术。6 覆盖6.1 引入：覆盖实现了在较小的

19、可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。6.2 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)覆盖示例如下：第三节 基本分页存储管理方式1 基本概念概念：在分页式存储管理方式中，如果不具备页面对换功能，不支持虚拟存储器功能，在调度作业运行时，必须将它的所有页面一次调入内存，若内存没有足够的块，则作

20、业等待，则称为纯分页或基本的分页存储管理方式。1.1 基本思想就是先划分在装块。n 空间划分：（1）地址空间的划分：将一个用户进程的逻辑地址空间划分成若干个大小相等的区域，称为页或页面,并将各页从0开始编号。（2）物理空间的划分：内存空间也分成若干个与页大小相等的区域，称为（存储、物理）块或页框（frame），同样从0开始编号。n 内存分配：在为进程分配内存时,以块为单位,将进程中若干页装入到多个不相邻的块中,最后一页常装不满一块而出现页内碎片。注：需要CPU的硬件支持（地址变换机构）。1.2 页面页面的概念前面提到了。若页面较小：§ 减少页内碎片和内存碎片的总空间，有利于提高内存利

21、用率。§ 每个进程页面数增多，从而使页表长增加，占用内存就较大。§ 页面换进换出速度将降低。 若页面较大：§ 每个进程页面数减少，页表长度减少，占用内存就较小。§ 页面换进换出速度将提高。§ 会增加页内碎片不利于提高内存利用率。页面大小-选择适中，通常为2的幂，一般在512B-8KB之间。分页地址的地址结构-如下图：页面的大小其实由位移量来确定。课本P131有计算公式，可以看一下。1.3 页表1.3.1 什么是页表记录页号到物理块号之间的对应关系，映射的映射表就是页表，1.3.2 页表的作用就是实现从进程的页号到内存物理块号的地址映射。如图示1

22、.3.3 页表的性质n 记录了页面在内存中对应的块号。n 页表一般存放在内存中。n 访问一个字节的数据/指令需访问内存2次(页表一次,内存一次),所以出现内存访问速度降低的问题。n 一般分页系统中，常在页表中设置一个存取控制字段，用于标识对该存储块的内容保护也就是存取权限。表示允许读/写，只读等等。2 地址变换机构引入：由于由页号到物理块号，页内地址到块内地址都是将逻辑地址，变换为内存空间的物理地址，因此在系统中必须设置地址变换机构。2.1 地址变换机构的基本任务实现逻辑地址向物理地址的转换（由页号->块号）。由于，页表就是实现从页号到物理块号的变换，因此地址变换借助页表来完成。2.2

23、基本地址变换机构过程描述：页表驻留在内存。系统中设置一个页表寄存器PTR，在其中存放页表在内存的起始地址和页表的长度。进程未执行时，页表的起始地址和页表长度存放再本进程的PCB中，当该进程被调度时，这两个数据装入页表寄存器。当进程执行时要访问某个逻辑地址中的数据时，地址变换机构会自动把逻辑地址分为页号和页内地址两部分。用页号为索引来检索页表。先将页号和页表长度比较，若页号大于等于页表长度，则表示本次所访问的地址超过进程的地址空间，越界错误中断。若无，则将页表起始地址与页号和页表项长度的乘积相加，便得到该表项再页表中的位置，由此可找到该页的物理块号。同时页内地址送入物理地址寄存器的块内地址字段中

24、。这样便完成了逻辑地址到物理地址的转换。如下图例1： 若在一分页存储管理系统中，某作业的页表如表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。页号块号02132136解：分析：页面大小是1024B,即1M，可知页面是10bit.由题知逻辑地址为： 物理地址为：（1）逻辑地址1011（十进制）的二进制表示为 00 1111110011 由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中，其物理地址的二进制表示为 010 1111110011 所以逻辑地址1011对应的物理地址为0BF3H.其地址转换图如后所示。 （2）

25、略 （3）逻辑地址5012（十进制）的二进制表示为：100 1110010100 可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。2.3 具有快表的地址变换机构 引入基本的地址变换机构存在的问题是CPU每次存取一个数据时，需要访问内存两次，一次是访问内存中的页表，最终得到物理地址，第二次才是真正的访问数据。因此降低了速度。因此为了提高地址变换速度，我们引入了“快表”。 基本原理快表就是一个高速缓冲存储器，存放当前访问的那些页表项，也就是快表中存放的是部分页表。CPU产生的逻辑地址的页首先在快表中寻找，若找到（命中），就找出其对应的物理块；若未找到（未命中），再到内存的页表中找

26、其对应的物理块，之后还要修改当前快表，把这个页表项添加到快表中。图见课本p133若快表中内容满，则按某种算法淘汰某些页。2.4 两级和多级页表2.4.1 引言当一个计算机系统的逻辑地址空间非常大。则页表就会很大，要占用大的内存空间，而且要采用连续存储方式。这实际上是没法满足的。因此我们提出两个解决方法：1、 采用离散分配方式取代找一个大的内存空间来存放页表的问题。2、 只将当前需要的部分页表放在内存，其他页表驻留在磁盘，需要时调入。2.4.2 两级页表采用的是第一种方法，用离散分配方式解决。基本原理：把页表也进行分页，并离散地将各个页面分别存放在不同的物理块中。这样也就需要为离散分配的页表再建

27、一个页表，称之为外层页表，其用于记录页表页面所对应的物理块号。如图示 过程是：利用外层页号（页面页表号），作为外层页表的索引，从中找到指定页表分页的起始地址，再利用内层页号找到指定的页表项，其中含有该页所在的块号，在和页内地址构成实际的内存物理地址。详见P134。2.4.3 多级页表将外层页表再进行分页，也将各外层页表页面离散地存放在不同的物理块中，再利用第2级的外层页表来记录它们之间的对应的关系。逻辑地址：如图第四节 基本分段存储管理方式1 分段存储管理方式的引入为什么要引入分段？分段有哪些优点？我们现在了解一下。1 方便编程： 因为实际编程中，用户作业通常按照逻辑关系分为几个段，每个段都是

28、从0开始编址，并有名字和长度，访问的逻辑地址由段名和段内偏移量决定。此存储管理方式就按逻辑上有联系的段来进行管理，方便编程。2 信息共享： 从上面可以得知，段是信息的逻辑单位，也就是段具有实际的逻辑意义。这和前一讲的“页”完全不同。因此要实现段的共享，就要求存储管理能与用户程序的分段组织方式相适应。3 信息保护： 信息保护同样是对信息的逻辑单位进行保护，因此分段管理方式能有效的实现信息保护。4 动态增长： 实际应用中，某些段（数据段）会不断增长，前面的存储管理方法均难以实现。而分段却可以解决这个问题。5 动态链接： 要求以段为单位。 由此我们理解为什么要引入分段存储管理。2 分段系统的基本原理

29、2.1 空间划分（分段）将用户作业的地址空间依照相应的逻辑信息组的长度来划分若干个段，各段的长度不等。各段有段名（常用段号代替），段内首地址为0。段地址结构如下图：一般我们常见的有代码段、数据段、共享段等等。允许一个作业最长又64个段，每个段最大长度是64kB。2.2 内存分配在为作业分配内存时，也以段为单位，分配一段连续的物理地址空间；段间不必连续。如下图注意：整个作业的逻辑地址空间是二维的，其逻辑地址由段号和段内地址组成。1、 需要CPU的硬件支持（地址变换机构）2.3 段表u 概念：系统中为每个进程建立一张段映射表，就是段表。u 段表内容：每个段在表中占有一个表项，其中记录了该段在内存中

30、的起始地址（又叫“基址”）和段的长度。段表如下图u 存储位置：可以存储于寄存器。但一般存放在内存。u 作用：记录了段与内存位置的对应关系u 注意：访问一个字节的数据/指令需访问内存2次(段表一次,内存一次),所以也出现内存访问速度降低的问题。利用段表实现地址映射如下图2.4 地址变换机构地址变换过程：系统中设置段表寄存器，用于存放段表起始地址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，则访问越界。否则，根据段表的起始地址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址。再检查段内地址D是否超过该段的段长SL。若超过则

31、越界，否则将该段的基址和段内地址相加，即可得到要访问的内存物理地址。如下图例1：在一个段式存储管理系统中，其段表为： 段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 9504302120试求表中逻辑地址对应的物理地址是什么？解：逻辑地址为：段号段内地址逻辑地址 0430对应的物理地址为：210+430=640逻辑地址 2120因为段内地址120>段长90，所为该段为非法段。2.5 分页和分段的主要区别3 信息共享与保存3.1共享：分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。分段系统的一个突出优点是易

32、于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。分段系统中，实现共享只需要在每个进程的段表中为共享段设置一个段表项。如图其中，p1,p2是进程3.2 保护保护方式：地址越界保护；存取控制保护段表的改进，实际就是增加了存取控制字段如图4 段页式存储管理方式引言：段式优于页式，便于共享和保护，没有内碎片，外碎片可以通过内存“紧凑”来消除。页式优于段式，消除“外碎片”问题，没有外碎片，每个内碎片不超过页大小。段页式：结合二者优点。每个进程包含若干段，每个段包含若干页1 基本原理基本原理：是先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。再把每个

33、段分成若干个页（页式）。其地址结构由段号、段内页号、及页内位移三部分所组成。下图是作业地址空间和地址结构。该图显示一个作业有三个段。页面大小是4kB.分别是主程序段、子程序段、数据段。04K8K12K15K16K主程序段04K8K子程序段04K8K12K10K数据段作业地址空间：地址结构：页内地址(W)段内页号(P)段号(S)2 地址变换过程2.1 地址变换过程在段页式系统中，为了实现地址变换，增加一个段表寄存器，用来存放段表始址和段长。进行地址变换时，首先利用段号S和段长TL比较。若S<TL，表示没越界。于是利用段表起始地址和段号求出该段所对应的段表项在段表的位置，从中得到该段的页表地

34、址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。如下图所示。注意：在段页式系统中，为了获得一条指令或数据，需要访问三次内存：第一次：访问内存中的段表，取得页表始址第二次：访问内存中的页表，取得该页所在的物理块号，将块号与页内地址形成物理地址第三次：访问第二次所得的地址，取出指令或数据解决方法：增设高速缓冲寄存器-快表第五节 虚拟存储器虚拟存储器，对换，覆盖都是从逻辑上扩充内存容量1 引入1.1 常规内存管理方式的特征常规存储管理的特征：§ 一次性（指全部装入）。也就是要求作业在运行前一次性的全部装入内存。但

35、是许多作业在运行时，并不是全部程序和数据都要用到，如果一次性全部装入，其实就是对内存空间的浪费。§ 驻留性（指驻留在内存不换出）。是指作业装入内存后，一直驻留在内存，直到作业运行结束。一直占用内存资源。1.2 局部性原理概念：指程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。§ 时间局部性：如循环执行。§ 空间局部性：如顺序执行。1.3 虚拟存储器的概念u 基于局部性原理，程序在运行之前，没有必要全部装入内存，仅须将当前要运行的页（段）装入内存即可。u 运行时，如访问的页（段）在内存中，则继续执

36、行，如访问的页未在内存中（缺页或缺段），则利用OS的请求调页（段）功能，将该页（段）调入内存。 u 如内存已满，则利用OS的页（段）置换功能，按某种置换算法将内存中的某页（段）调至外存，从而调入需访问的页。 虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求页调入功能和页置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存。2 虚拟存储器的实现方法虚拟存储器的实现，都建立在离散分配的存储管理方式基础上。2,1 分页请求系统 在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。

37、它允许只装入若干页的用户程序和数据，便可启动运行，以后再硬件支持下通过调页功能和置换页功能，陆续将要运行的页面调入内存，同时把暂不运行的页面换到外存上，置换时以页面为单位。 系统须设置相应的硬件支持和软件：（1）硬件支持：请求分页的页表机制、缺页中断机构和地址变换机构。（2）软件：请求调页功能和页置换功能的软件。2.2 分段请求系统 在分段系统的基础上，增加了请求调段功能及分段置换功能，所形成的段式虚拟存储器系统。 它允许只装入若干段的用户程序和数据，便可启动运行，以后再硬件支持下通过请求调段功能和分段置换功能，陆续将要运行的段调入内存，同时把暂不运行的段换到外存上，置换时以段为单位。系统须设

38、置相应的硬件支持和软件：（1）硬件支持：请求分段的段表机制、缺段中断机构和地址变换机构（2）软件：请求调段功能和段置换功能的软件3 虚拟存储器特征u 离散性：在分配内存时采用离散分配方式u 多次性：一个作业被分成多次调入内存运行u 对换性：允许在作业的运行过程中进行换进、换出。u 虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。注意：虚拟性以多次性和对换性为基础；多次性和对换性又必须建立在离散分配的基础上。第六节 请求分页存储管理方式1 基本概述请求分页管理是建立在基本分页基础上的，为了能支持虚拟存储器而增加了请求调页功能和页面置换功能。基本原理：地址空间的划分同页

39、式；装入页时，可装入作业的一部分(运行所需)页即可运行。2 请求分页的硬件支持为实现请求分页，需要一定的硬件支持，包括：页表机制、缺页中断机构、地址变换机构。2.1 页表机制作用：将用户地址空间的逻辑地址转换为内存空间的物理地址。因为请求分页的特殊性，即程序的一部分调入内存，一部分仍在外存，因此页表结构有所不同。如图：页号块号状态位访问字段修改位外存地址说明：（1）状态位P：指示该页是否已调入内存。（2）访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间。（3）修改位M：表示该页在调入内存后是否被修改过。若修改过，则换出时需重写至外存。（4）外存地址：指出该页在外存上的地址。2.

40、2 缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便产生缺页中断，请求OS将所缺的页调入内存。缺页中断与一般中断的区别：（1）在指令执行期间产生和处理中断信号（2）一条指令在执行期间，可能产生多次缺页中断2.3 地址变换机构请求分页系统的地址变换机构。是在分页系统地址变换机构的基础上，又增加了一些功能。例：某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。解：虚拟地址为：页号（25=32）5位 页内位移（1K =210=1024）10位 物理地

41、址为 物理块号（24=16）4位 因为页内是10 位， 块内位移（1K =210=1024）10位虚拟地址OA5C对应的二进制为： 00010 1001011100 即虚拟地址OA5C的页号为2，页内位移为1001011100，由题意知对应的物理地址为：0100 1001011100即125C同理求093C。略3 内存分配策略和分配算法在请求分页系统中，为进程分配内存时，将涉及以下三个问题：最小物理块数的确定；物理块的分配策略；物理块的分配算法。3.1 最小物理块数的确定概念：最小物理块数：是指能保证进程正常运行所需的最小物理块数。确定方法：与计算机的硬件结构有关，取决于指令的格式、功能和寻址

42、方式。3.2 物理块的分配策略内存分配策略：固定和可变分配策略置换策略：全局置换和局部置换三种合适的策略如下：（1）固定分配局部置换（Fixecd Allocation,Local replacement）：为每个进程分配固定数目n的物理块，在整个运行中都不改变。如出现缺页，则从中置换一页。（2）可变分配全局置换(VariableAllocatio,Global Repalcement)：分配固定数目的物理块，但OS自留一空闲块队列，若发现缺页，则从空闲块队列中分配一空闲块与该进程，并调入缺面于其中。当空闲块队列用完时，OS才从内存中任选择一页置换。（3）可变分配局部置换(VariableAl

43、locatio,Local Repalcement)：分配一定数目的物理块，若发现缺页，则从该进程的页面中置换一页，根据该进程缺页率高低，则可增加或减少物理块。3.3 物理块的分配算法在采用固定分配策略时，将系统中可供分配的所有物理块分配给各个进程，可采用以下几种算法：（1）平均分配算法：将系统中所有可供分配的物理块，平均分配给每个进程。缺点：未考虑各进程本身的大小。（2）按比例分配算法：这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，

44、它必须大于最小物理块数。 （3）考虑优先权的分配算法：将系统提供的物理块一部分根据进程大小先按比例分配给各个进程，另一部分再根据各进程的优先权适当增加物理块数。4 调页策略什么时候将一个页面由外存调入内存？从何处将页面调入内存？这就是调页策略所要解决的问题。4.1 何时调入页面？v 预调页策略：将那些预计在不久便被访问的页预先调入内存。这种调入策略提高了调页的效率，减少了I/O次数。但由于这是一种基于局部性原理的预测，若预调入的页面在以后很少被访问，则造成浪费，故这种方式常用于程序的首次调入。v 请求调页策略：当进程运行中访问的页出现缺页时，则发出缺页中断，提出请求调页，由OS将所需页调入内存

45、。这种策略实现简单，应用于目前的虚拟存储器中，但易产生较多的缺页中断，且每次调一页，系统开销较大，容易产生抖动现象。注意：首次：预调页；运行时：请求调页。4.2从何处调入页面？ 在请求分页系统中，通常将外存分成了文件区和对换区，文件区按离散分配方式存放文件，对换区按连续分配方式存放对换页。 v 系统有足够的对换区空间情况：运行前可将与进程相关的文件从文件区复制至对换区，以后缺页时，全部从对换区调页。只从对换区调页。v 系统没有足够的对换区空间情况：页面不会被修改：凡是不会被修改的文件，每次都直接从文件区调页，换出时不必换出。只从文件区调页。页面可能被修改：若对可能会修改的文件第一次调页直接从文

46、件区，换出时换至对换区，以后从对换区调页。第一次从文件区调入以后从对换区。从文件区/对换区调页v UNIX方式：凡未运行过的页面均从文件区调页，运行过的页面和换出的页面均从对换区调页。5 页面调入过程 了解过程如下：每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存上的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则需按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必写回磁盘；但如果此页已被修改，则必须将它写回磁

47、盘，然后把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表。在缺页调入内存后，利用修改后的页表，形成所要访问的物理地址，再去访问内存数据。流程如下：第七节 页面置换算法1 引言在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区。但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能。刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不入又再次被淘汰出内存，然后又要访问它，如此反复，这种现象称为抖动（又称颠簸）。

48、一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。2 常用的页面置换算法2.1 最佳置换算法（The best optimal） 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。 由于人们无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再被访问的页面，因此该算法无法实现。但该算法可以用来评价其他算法。例：就是课本上的例子假定系统为某进程分配了三个物

49、理块， 并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 2.2 先进先出页面置换算法(FIFO)该算法淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面淘汰。Belady现象：使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面增多，缺页次数反而增加的奇怪现象，就是Belady现象。例：和上例一样例子：1，2，3，4，1，2，5，1，2，3，4，5内存3个物理页面：缺页9次内存4个物理页面：缺页10次 异常！ Belady现象2.3最近最久未使用置换算法(Least Recently Used,LR

50、U) 算法描述算法思想：利用“最近的过去”作为“最近的将来”。选择最近最久未使用的页面淘汰。该算法对每个页面设置一个访问字段，用于记录一个页面自上次被访问以来所经历的时间t,每次淘汰t值最大的页面，也就是最近最久未使用的页面。例：缺页12次，总访问次数20次，缺页率12/2060 硬件支持两类硬件支持：寄存器、栈。为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。移位寄存器表示为 R=当进程访问某物理块时，要将相应寄存器的位置成1。此时，定时信号将每隔一定时间将寄存器右移一位。如果把n位寄存器的数看作一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用

51、的页面。例：某进程在内存中具有8个页面，为每个页面配置一个8位寄存器。如下图：2.3.3 栈利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。如下图：R0R1R2R3R4R5R6R7 R 实页 000101111001111001101011010101011000100001010101100110010100100012345678某进程具有8个页面时的LRU访问情况444774700407740711471004701147012247021147

52、0122701266设一进程访问页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，6随着进程的访问，栈中页面号的变化情况：2.4 CLOCK置换算法是一种最近最久未使用算法的近似算法。 简单的CLOCK置换算法算法描述：v 每页设置一位访问位，某页被访问时，其访问位被置1。内存中的所有页链接成一个循环队列；v 循环检查各页面的使用情况，访问位为“0”，选择该页淘汰；访问位为“1”，复位访问位为“0”，查询指针前进一步。v 因为该算法只有一位访问位，只能用它表示该页是否使用过，置换时只能将未使用过的页面置换出去，因此称为“最近未使用”置换算法（NRU）例子：2.4.2 改进型的CLOC

53、K置换算法1 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问，又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问，但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改，该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改，该页可能再被访问。 2 执行过程访问位A，修改位M共同表示一个页面的状态：四种状态：00 01 10 11。三轮扫描：第一轮：查找00页面，若找到，则淘汰所找到的第一页，结束；若未找到，下一步；第二轮：查找01页面，若找到，则淘汰所找到的第一页，结束；，若未找到，下一步；（第二轮中，所有扫描过的页面，A位复位为“0”）第三轮：所有页面A位复位为“0”，重复第一步。2.5 其他置换算法最少使用(LFU： Least Frequently Used)置换算法Ø 选择到当前时间为止被访问次数最少的页面被置换；Ø 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；Ø 发生