内存管理与虚拟内存管理知识点总结.pdf

《内存管理与虚拟内存管理知识点总结.pdf》由会员分享，可在线阅读，更多相关《内存管理与虚拟内存管理知识点总结.pdf（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 内存管理与虚拟内存管理知识点总结 内存管理概念 内存管理的基本原理和要求 内存管理的主要功能 内存空间的分配与回收。由操作系统完成主存储器空间的分配与管理。地址转换。把逻辑地址转换成为物理地址。内存空间的扩充。内存共享。存储保护。保证各道作业在各自的存储空间内运行，互不干扰。1.程序的链接与装入 从写程序到程序运行 编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块 装入（装载）：由装入程序将装入模块装入内存运行 链接的三种方式（将各个目标模块（都是从0 开始）形成

2、一个装入模块，装入模块的地址为逻辑地址，从0 开始形成逻辑地址）1.静态链接 在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。需要解决两个问题：1，修改相对位置（每个目标模块都是从0开始的相对地址，现在要要统一为一个地址），2，变换外部调用符号，（将每个模块中所用的外部调用符号也都变换为相对地址）。2.装入时动态链接 将各目标模块装入内存时，边装入边链接的链接方式。优点是:便于修改和更新，便于实现对目标模块的共享。3.运行时动态链接 在程序执行中需要该目标模块时，才对它进行链接。优点是:能加快程序装入的过程，还可以节省大量时间。装入的三种方

3、式（将装入逻辑地址与物理地址的相转换）形成物理地址 绝对装入（装入前转换从物理地址）在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。2 静态重定位（边装入，边转换为物理地址，一次性装入）又称可重定位装入。编译、链接后的装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的，通过修改装配模块中的有关使用地址的指令）。静态重定位的特点是

4、在一个作业装入内存时，必须分配其要求的全部内存空间（必须连续，不适合离散分配），如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。动态重定位（运行后需要哪一部分才装入哪一部分，并且转换物理地址）又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行（在作业运行过程中执行到一条访存指令时，在转换地址）。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器 的支持。并且可将程序分配到不连续的存储区 中；在程序运行

5、前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。2.逻辑地址与物理地址 逻辑地址：程序经过编译、链接后生成的指令中指明的是逻辑地址（相对地址），即：相对于进程的起始地址而言的地址 物理地址：内存中物理单元的集合，它是地址转换的最终地址。3.进程的内存映像 代码段：程序的二进制代码段 数据段：包括全局变量和静态变量 代码段和数据段在调入内存时就指定了大小。进程控制块（PCB）:存放在系统区（常驻内存，即使挂起也在内存）堆：存放动态分配的变量。通过 malloc函数动态的向高地址分配空间。栈：用来实现

6、函数调用。从用户空间的最大地址向低地址方向增长。4.内存保护 方法一：在 CPU 中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU 检查是否越界。方法二：采用重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定寄存器中存放的是进程的起始物理地址。界3 地址寄存器中存放的是进程的最大逻辑地址。（先界址寄存器按逻辑地址检查是否越界，再用基址寄存器得到物理地址）重定位寄存器是用来加的，界地址寄存器是用来比的，先比后加 加载重定位寄存器和界地址寄存器必须使用特权指令，只有操作系统内核才可以加载或修改这两个寄存器。5.内存共享 只有那些可

7、读区域才可以共享。可重入代码又称纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码 在实际执行时，也可以为每个进程配以局部数据区，把在执行中可能发生改变的部分复制到该数据区。6.内存分配与回收 由单一连续配发展到固定分区分配（操作系统单道到多道）由固定分区分配发展到动态分区分配（适应不同大小的程序要求）由连续分配方式发展到离散分配方式页式存储管理（提高内存利用率）分段式存储管理（便于用户，便于共享）连续分配管理方式 连续分配：指为用户进程分配的必须是一个连续的内存空间。内部碎片：分配给某进程的内存区域中，如果有些部分没有用上，就称为内部碎片。外部碎片：是指内存中的某些空闲分区由于太

8、小而难以利用。单一连续分配 原理：在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分（供操作系统使用），用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不需要采取内存保护（eg：早期的 PC 操作系统 MS-DOS）。缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。4 固定分区分配 原理：是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业 划分分区时有两种不同的方法 分区大小相等：程序太小会造成浪费，程序太

9、大无法装入，分区大小不等：划分为多个较小分区，适量的中等分区，少量大分区 操作系统需要建立一个数据结构分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。优点：实现简单，无外部碎片。（可用于多道程序设计）缺点：a.当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b.会产生内部碎片，内存利用率低。动态分区分配（可变分区分配）原理：这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的

10、大小和数目是可变的。（eg：假设某计算机内存大小为 64MB，系统区 8MB，用户区共 56 MB）动态分区分配没有内部碎片，但是有外部碎片。如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。（需要动态重定位寄存器的支持）回收空闲分区的四种情况 情况一：回收区的后面有一个相邻的空闲分区，两个相邻的空闲分区合并为一个，并修改后一分区表项的始址和大小 情况二：回收区的前面有一个相邻的空闲分区，两个相邻的空闲分区合并为一个，并修改前一分区表项的大小为两者之和 情况

11、三：回收区的前、后各有一个相邻的空闲分区，三个相邻的空闲分区合并为一个，修改前一分区表项的大小为三者之和，取消后一分区表项 情况四：回收区的前、后都没有相邻的空闲分区，新增一个表项注：各表项的顺序不一定按照地址递增顺序排列，具体的排列方式需要依据动态分区分配算法来确定。动态分区分配算法 首次适应算法（通常为最好和最快）算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。5 如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。最佳适应算法（有外部碎片）算法思想：由于动态分区分配是一种 连续分配方式，为各进程分

12、配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区 缺点：每次都选最小的分区进行分配，会留下越来越多的、很小 的、难以利用的内存块。因此这种方法会产生很多的外部碎片。最坏适应算法（不利于大进程）算法思想：为了解决最佳适应算法的问题即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。如何实现：空闲分区按容量递减次序链接。每次

13、分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的 空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。邻近适应算法（不利于大进程）算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。如何实现：空闲分区以 地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始 查找空

14、闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把 高地址部分的大分区保留下来（最佳适应算法的优点）邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）综合来看，四种算法中，首次适应算法的效果反而更好 6 非连续分配管理方式 基本分页存储管理 基本概念 页面和页面大小 进程中的块为页面或页

15、内存中的块为为页框或页帧（内存块，物理块，物理页面）外存中也以同样的单位进行划分，称为块或盘块。页号和页框号从0开始。操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。页面大小一般为2的整数幂，同时页面的大小应该适中，太大是内部碎片增多，大小页表过长。逻辑地址结构：页号P|页内偏移量W；地址结构决定虚拟内存的寻址空间。页表 1.一个进程对应一张页表 2.进程的每个页面对应一个页表项 3.每个页表项由“页号”和“块号”组成（页表中的页号可以是隐含的，即页号不占用存储空间

16、）注意：页表记录的只是内存块号，而不是内存块的起始地址！J 号内存块的起始地址=J*内存块大小 4.页表记录进程页面和实际存放的内存块之间的映射关系 5.每个页表项的长度是相同的 页表项中的块号*页面大小+逻辑地址中的偏移量=物理地址 页面大小一般为 2的幂次的好处 7 逻辑地址的拆分更加迅速如果每个页面大小为 2KB，用二进制数表示逻辑地址，则末尾 K 位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为 2 的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。物理地址的计算更加迅速根据逻辑地址得到页号，根据页号查询页

17、表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。页表项大小一般选择为，让一个页面能恰好容下整数个页表项，进而方便存储。基本地址变换机构（逻辑地址到物理地址）页表寄存器（PTR）：存放页表在内存中的起始地址 F和页表长度 M。在进程未被执行时，页表始址和页表长度存放在本进程的 PCB中，当进程被调度执行时，才将其装入页表寄存器。变换过程 1，确定逻辑地址 A 对应的“页号”P（页号=逻辑地址/页面长度（取除法的整数部分）2，通过页号和页表查找页面在内存中的起始地址（需要查页表），需要检查是否页号是否大于等于页表寄存器中的页表长度 M。3，确定逻

18、辑地址 A 的“页内偏移量”W（页内偏移量=逻辑地址%页面长度（取除法的余数部分）4，逻辑地址 A 对应的物理地址=P 号页面在内存中的起始地址+页内偏移量 W 具有快表的地址变换机构 快表：又称联想寄存器（TLB，translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。CPU 给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，

19、再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）8 基于局部性原理 时间局部性 如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该

20、数据很可能再次被访问。（因为程序中存在大量的循环）空间局部性 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）两种变换机构的对比 两级页表 问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存 若想访问的页面不在内存中，则产生缺页中断（内中断/异常），然后将目标页面从外存调入内存 把页表再分页并离散存储，然后再建立

21、一张页表记录页表各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表 如何实现地址变换 9 注意事项 1.若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面 2.两级页表的访存次数分析（假设没有快表机构）N级页表访问一个逻辑地址需要 N+1 次访存。基本分段存储管理 分段 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0开始编址 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。段号的位数决定了每个进程最多可以分几个段 段内地址位数决定了

22、每个段的最大长度是多少 段表 1.每个段对应一个段表项，其中记录了该段在内存中的起始位置（与内存的最大容量有关）（又称“基址”）和段的长度。2.各个段表项的长度是相同的。例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号 16位,段内地址 16位），因此用 16位即可表示最大段长。物理内存大小为 4GB（可用 32位表示整个物理内存地址空间）。因此，可以让每个段表项占 16（段长）+32（段的起始地址）=48 位（段表项长度），即 6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为 M，则 K号段对应的段表项存放的地址为 M+K*6 地址变换 10

23、 分段、分页管理的对比 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或

24、可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的 分页（单级页表）：第一次访存查内存中的页表，第二次访存访问目标内存单元。总共两次访存 分段：第一次访存查内存中的段表，第二次访存访问目标内存单元。总共两次访存与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。段页式存储管理 分页、分段的优缺点分析 11 段页式存储管理：将进程按逻辑模块分段（由用户完成），再将各段分页（系统自动完成）（如每个页面 4KB）再将内存空间分为大小相同的内存块/页框/页帧/物理块进程前将各页面分别装入各内存块中 段页式的逻辑

25、地址结构 段号的位数决定了每个进程最多可以分几个段 页号位数决定了每个段最大有多少页 页内偏移量决定了页面大小、内存块大小是多少 “分段”对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。因此段页式管理的地址结构是二维的 段表，页表 每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。每个段表项长度相等，段号是隐含的。每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的 变换机构 虚拟内存管理 虚拟内存的基本概念 传统存储管理方式的

26、特征、缺点（一次性，驻留性）一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：作业很大时，不能全部装入内存，导致大作业无法运行；当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。12 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。局部性原理 时间局部性（使用过的数据或者指令保存一段时间）：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不

27、久之后该数据很可能再次被访问。（因为程序中存在大量的循环）空间局部性（预存取到缓存中）：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的）高速缓冲技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。页表，页高速缓存，及虚拟内存技术都属于高速缓存技术，依赖于局部性原理 虚拟内存的定义和特征 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作

28、系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的存储器，这就是虚拟存储器（两个任务）易混知识点：虚拟内存的实际容量=min（内存和外存容量之和，CPU寻址范围）虚拟内存的最大容量是由计算机的地址结构（CPU 寻址范围）确定的 三个主要特征（多次性，对换性，虚拟性最重要特征）多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。虚拟性：从逻辑上扩充了内存的容量，使 用户看

29、到的内存容量，远大于实际的容量。虚拟内存的技术的实现 虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。三种方式 请求分页存储管理 请求分段存储管理 13 请求段页式存储管理 硬件支持 一定的容量和外存 页表机制（或段表机制），作为主要的数据结构 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。地址变换机构，逻辑地址到物理地址的变换 请求分页管理方式（请求调页，页面置换）请求分页存储管理与基本分页存储管理的主要区别：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内

30、存（操作系统要提供请求调页功能，将缺失页面从外存调入内存），然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。（操作系统要提供页面置换的功能，将暂时用不到的页面换出外存）。页表机制（页号，内存块号，状态位，访问字段，修改位，外存地址）当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。缺页中断机构 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断

31、处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项（还有快表）。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存 缺页中断作为中断，同样要经历诸如保护 CPU环境，分析中断原因，转入缺页中断处理程序，恢复 CPU环境等几个步骤，但与一般的中断相比，它有以下两个明显的区别。在指令执行期间而非一条指令执行完后产生和中断处理信号，属于内部异常。一条指令在执行期间，可能产生多次缺页中断。地址变换机构

32、 14 页面置换算法 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。（需要置换算法），好的页面置换算法应该追求更少的缺页率。最佳置换算法（OPT）每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。先进先出置换算法（FIFO）每次选择淘汰的页面是最早进入内存的页面

33、实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。Belady 异常当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。只有 FIFO 算法会产生 Belady 异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差 15 最近最久未使用置换算法（LRU）最近最久未使用置换算法（LRU，least recently used）：每次淘汰的页面是最近最久未使用的页面 实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面

34、自上次被访问以来所经历的时间 t。当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面。LRU算法性能较好，但需要寄存器和栈的硬件支持。时钟置换算法（CLOCK）最佳置换算法性能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近 OPT 算法性能的，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一种性能和开销较均衡的算法，又称 CLOCK算法，或最近未用算法（NRU，NotRecently Used）简单的 CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页

35、被首次装入或者被访问时，其访问位置为 1。当需要淘汰一个页面时，只需检查页的访问位。如果是 0，就选择该页换出；如果是1，则将它置为 0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是 1，则将这些页面的访问位依次置为 0 后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0 的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）（当某页被替换时，该指针被设置指向被替换页面的下一页）改进型的时钟置换算法 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存。只有被淘汰的页面被修改过时，才需要写回外

36、存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O 操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。16 页框策略 驻留集 指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，但驻留在主存中的进程就越多从而可以提高 CPU 的利用

37、率，实际用于进程推进的时间很少；驻留集太大，又会导致多道程序并发度下降，资源利用率降低，对缺页率没有太明显的影响。所以应该合理分配。内存分配策略 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变 局部置换：发生缺页时只能选进程自己的物理块进行置换。全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。固定分配局部置换 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若

38、进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）可变分配全局置换（只要缺页就给分配新物理块）刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系

39、统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。17 可变分配局部置换（要根据发生缺页的频率来动态地增加或减少进程的物理块）刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。没有固定分配全局置换。物理块调入算法 采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述算法 1）平均分配算

40、法 2）按比例分配算法，按进程大小的比例 3）优先权分配算法。按重要和紧迫程度 通常采取的方法是把所有可分配的物理块分成两部分：一部分按比例分配分配给各个进程，一部分则根据优先权分配。调入页面的时机 1.预调页策略：根据局部性原理（空间局部性原理），一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有 50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。2.请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页

41、面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘 I/O 操作，因此 I/O开销较大。从何处调入页面 1.系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。2.系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。18 抖动（颠簸）现象 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页

42、面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率 工作集（在某段时间间隔（窗口）里，进程实际访问页面的集合。）工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如：窗口尺寸为 5，经过一段时间的监测发现某进程的工作集最大为 3，那么说明该进程有很好的局部性，可以给这个进程分配 3 个以上的内存块即可满足进程的运行需要。一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。拓展：基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法选择一个不在工作集中的页面进行淘汰。内存映射文件（还没看）虚拟存储器性能影响因素（还没看）地址翻译（还没看）