操作系统设计与实现(第四章).ppt

操作系统设计与实现操作系统设计与实现 第四章第四章 存储器管理存储器管理 一、存储器在操作系统中的地位一、存储器在操作系统中的地位 是计算机不可缺少的部分，存在的方式也是计算机不可缺少的部分，存在的方式也 多种多样。多种多样。 对于操作者、程序设计者、系统开发者对于操作者、程序设计者、系统开发者 都希望能拥有无穷大的、高速的、内容不发生都希望能拥有无穷大的、高速的、内容不发生 变化的存储器（不易丢失），最根本的还是能变化的存储器（不易丢失），最根本的还是能 以很低的成本来使用。以很低的成本来使用。 由于技术的原因，我们无法满足我们的由于技术的原因，我们无法满足我们的 需求，因此，大部分的计算机都以一种层次结需求，因此，大部分的计算机都以一种层次结 构来进行存储器的管理。构来进行存储器的管理。 高速、价格昂贵、易失信息的高速、价格昂贵、易失信息的CacheCache一般单位几百一般单位几百KBKB； 中速、中等价格、易变化的中速、中等价格、易变化的RAMRAM，一般单位为几百，一般单位为几百MM； 低速、低廉价格、不易丢失信息的磁盘，一般单位为低速、低廉价格、不易丢失信息的磁盘，一般单位为GG； 存储存储 器层器层 次结次结 构构 对于操作系统，它本身提供一个存储管理模块对于操作系统，它本身提供一个存储管理模块 来管理它本身的这个层次性的存储器系统。来管理它本身的这个层次性的存储器系统。 Memory managerMemory manager 由操作系统协调这些存储器的使用 重要性：直接存取要求内存速度尽量快到与 CPU取指速度相匹配，大到能装下当前运行 的程序与数据，否则CPU执行速度就会受到 内存速度和容量的影响而得不到充分发挥。 内存： 是由存储单元（字节或字）组成的一维连续的地址 空间，简称内存空间。用来存放当前正在运行程序的代 码及数据，是程序中指令本身地址所指的、亦即程序计 数器所指的存储器。 可以分为： 系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据。 操作系统存储管理目的- 用户对内存的使用要求 1、充分利用内存，为多道程序并发执行提供存储基础； 2、尽可能方便用户使用： 自动装入用户程序； 用户程序中不必考虑硬件细节； 3、系统能够解决程序空间比实际内存空间大的问题； 4、程序在执行时可以动态伸缩； 5、内存存取速度快； 6、存储保护与安全； 7、共享与通信； 8、了解有关资源的使用状况； 9、实现的性能和代价。 操作系统存储管理的任务 前提: 引入多道程序设计技术，满足用户要求 1. 内存空间的管理、分配与回收 记录内存的使用情况 设置相应的内存分配表（见下页） （内存分配回收的依据） 内存空间划分问题？ 静态或动态，等长或不等长 内存分配表 位示图表示法：用一位（bit）表示一个空闲页 面（0：空闲，1：占用）； 0 0 . 1 1 1 1 0 0 . 第第0 0页第页第1 1页页 第第i i页页 第第n-1n-1页页 空闲页面表：包括首页面号和页面个数，连续若 干的页面作为一组登记在表中 空闲块表：空闲块首址和空闲块长度，没有记录 的区域即为进程所占用； 空闲块链表：将所有的空闲块链成一个链表。 确定分配算法 实施内存分配 回收内存 分配回收方式: 静态分配与动态分配 连续性 ； 离散性 驻留性 ； 交换性 一次性； 多次性 2. 存储共享 内存共享：两个或多个进程共用内存中相同区域 目的： 节省内存空间，提高内存利用率 实现进程通信（数据共享） 共享内容： 代码共享，要求代码为纯代码 数据共享 3. 存储保护与安全 保护目的： 为多个程序共享内存提供保障,使在内存中的各道 程序, 只能访问它自己的区域，避免各道程序间 相互干拢，特别是当一道程序发生错误时, 不致 于影响其他程序的运行。通常由硬件完成保护功 能，由软件辅助实现。（特权指令不能完成存储 保护。） 存储保护 保护系统程序区不被用户侵犯; （有意或无意的） 不允许用户程序读写不属于自己地址空间的数据; （系统区地址空间，其他用户程序的地址空间） 保护过程-防止地址越界 每个进程都有自己独立的进程空间，如果一个 进程在运行时所产生的地址在其地址空间之外，则 发生地址越界。即当程序要访问某个内存单元时， 由硬件检查是否允许，如果允许则执行，否则产生 地址越界中断，由操作系统进行相应处理。 一般由硬件提供一对寄存器： 基址寄存器：存放起始地址 限长寄存器：存放长度 （上界寄存器/下界寄存器） 保护过程-防止操作越权 对于允许多个进程共享的存储区域，每个进程 都有自己的访问权限。如果一个进程对共享区域的 访问违反了权限规定，则发生操作越权。 即读写保护。 4 .内存“扩充” 通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所 以要采用一定技术来“扩充“内存的容量，使用户得到 比实际内存容量大的多的内存空间。 内存“扩充” 具体实现是在硬件支持下，软硬件相互协作，将 内存和外存结合起来统一使用。通过这种方法把内 存扩充，使用户在编制程序时不受内存限制。 5 . 地址映射（地址重定位，地址变换） 逻辑地址（相对地址，虚地址） 物理地址（绝对地址，实地址） 地址映射 (1)逻辑地址（相对地址，虚地址） 用户的程序经过汇编或编译后形成目标代码 ，目标代码通常采用相对地址的形式，其首地址为 0，其余指令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。 (2)物理地址（绝对地址，实地址） 内存中存储单元的地址，可直接寻址。 (3)地址映射 为了保证CPU执行指令时可正确访问存储单元 ，需将用户程序中的逻辑地址转换为运行时由机器 直接寻址的物理地址，这一过程称为地址映射。 地址映射地址映射 BA=1000BA=1000 Load A 200Load A 200 3456 3456 。 。 。 12001200 物理地址空间物理地址空间 Load A data1Load A data1 data1 3456data1 3456 源程序源程序 Load A 200Load A 200 3456 3456 0 0 100100 200200 编译连接编译连接 逻辑地址空间逻辑地址空间 0 100 200 300 . . . . . . . . . LOAD A 200 3456 逻辑地址空间 1100 1200 1300 物理地址空间 200 VR + + 1000 BR *重定位和保护重定位和保护 多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了 新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。 如果多个作业都是为某如果多个作业都是为某一一个程序服务，当主程序个程序服务，当主程序 调用这些作业的时候，就需要定位到这些作业，保调用这些作业的时候，就需要定位到这些作业，保 证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。 这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来 定位程序。定位程序。 定位和保护的常见方法：定位和保护的常见方法： 原因: 当程序装入内存时, 操作系统要为该程序分 配一个合适的内存空间，由于程序的逻辑地址与 分配到内存物理地址不一致, 而CPU执行指令时， 是按物理地址进行的，所以要进行地址转换。 静态重定位 当用户程序被装入内存时，一次性实现逻辑 地址到物理地址的转换，以后不再转换（一般在 装入内存时由软件完成）。 动态重定位 在程序运行过程中要访问数据时再进行地址变 换（即在逐条指令执行时完成地址映射。一般为了 提高效率，此工作由硬件地址映射机制来完成。硬 件支持，软硬件结合完成）。 硬件上需要一对寄存器的支持。 4.1 4.1 基本的内存管理基本的内存管理 在运行时进程可以在内存和磁盘之间进行移在运行时进程可以在内存和磁盘之间进行移 动（交换和分页技术）的系统；动（交换和分页技术）的系统； 运行时进程不能够移动的系统，较为简单。运行时进程不能够移动的系统，较为简单。 交换和分页技术的目的是由于没有足交换和分页技术的目的是由于没有足 够的主存来同时容纳所有的进程而被引入。够的主存来同时容纳所有的进程而被引入。 随着硬件的发展，现有的良好的管理方案也随着硬件的发展，现有的良好的管理方案也 会可能变成过时的技术而被淘汰。会可能变成过时的技术而被淘汰。 .1无交换和分页的单道程序无交换和分页的单道程序 此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。 用户程序用户程序 位于位于RAMRAM中的中的 操作系统操作系统 0xFFF.0xFFF. 0 0 位于位于RAMRAM中的中的 操作系统操作系统 用户程序用户程序 0 0 ROMROM中的中的 设备驱动程序设备驱动程序 用户程序用户程序 位于位于RAMRAM中的中的 操作系统操作系统 0 0 A A B B C C 对于对于A A图，操作系统位于主存最底部的图，操作系统位于主存最底部的RAMRAM， 即随机存取存储器中，用户程序位于主存的上部。即随机存取存储器中，用户程序位于主存的上部。 对于对于B B图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存 储器里（储器里（ROMROM）, ,（其实本身属于一种映像区域，（其实本身属于一种映像区域， 映像了主板上的基本的输入输出系统）。映像了主板上的基本的输入输出系统）。 对于对于C C图，设备的驱动程序位于内存最高端的图，设备的驱动程序位于内存最高端的 ROMROM中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的RAMRAM中中 ，中间是用户的应用程序。如，中间是用户的应用程序。如MS-DOSMS-DOS系统。系统。 对于对于IBMIBM操作系统，系统位于操作系统，系统位于ROMROM中的部分即中的部分即 为为BIOSBIOS。 对于这种方式，不管是哪一个图，操作对于这种方式，不管是哪一个图，操作 系统每次把需要的程序从磁盘复制到存储系统每次把需要的程序从磁盘复制到存储 器里并执行，当程序结束时，系统提示结器里并执行，当程序结束时，系统提示结 束，当有新的命令时，系统加载新的程序束，当有新的命令时，系统加载新的程序 到存储器中，覆盖原来的程序，继续新的到存储器中，覆盖原来的程序，继续新的 执行。执行。 可以满足早期一般的小型的操作系统的可以满足早期一般的小型的操作系统的 需求，但随着硬件性能的提高，这种方式需求，但随着硬件性能的提高，这种方式 逐渐被淘汰。逐渐被淘汰。 4.1.2 4.1.2 固定分区的多道程序固定分区的多道程序 对于常见的系统，我们希望能够支持更多的对于常见的系统，我们希望能够支持更多的 程序，当某个程序处于等待程序，当某个程序处于等待I/OI/O的时候，可以让的时候，可以让 CPUCPU为别的程序服务，来提高系统整体的性能。为别的程序服务，来提高系统整体的性能。 因此可以用划分分区的方法来同时加载多个因此可以用划分分区的方法来同时加载多个 程序，可以把主存分为几个大小不同的分区，根程序，可以把主存分为几个大小不同的分区，根 据程序的不同，来把他们加载到不同的分区中。据程序的不同，来把他们加载到不同的分区中。 而同时，程序也可按照单个输入队列的方式进行而同时，程序也可按照单个输入队列的方式进行 输入，也可以按照多个输入队列的方式进行输入输入，也可以按照多个输入队列的方式进行输入 。 分区分区4 4 分区分区3 3 分区分区2 2 分区分区1 1 操作系统操作系统 多个输入队列多个输入队列 单个输入队列单个输入队列 分区分区4 4 分区分区3 3 分区分区2 2 分区分区1 1 操作系统操作系统 700K700K 400K400K 100K100K 0 0 对于左图，由于作业的大小类似的时候，而且对于左图，由于作业的大小类似的时候，而且 众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定， 我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样 的话，类似的作业就被分到了一起，而那些与作业的话，类似的作业就被分到了一起，而那些与作业 的大小不一致的分区，就必然会出现空闲状态，那的大小不一致的分区，就必然会出现空闲状态，那 些分到一起的进程却不得不等待，等待要分到内存些分到一起的进程却不得不等待，等待要分到内存 空间。忙得忙，闲的闲。空间。忙得忙，闲的闲。 如分区一和分区三。如分区一和分区三。 对于右图，所有的作业都被放入一个队列，每对于右图，所有的作业都被放入一个队列，每 次当有分区被释放的时候，就从等待队列中寻找，次当有分区被释放的时候，就从等待队列中寻找， 最适合这个分区大小的进程，这样做是为了避免把最适合这个分区大小的进程，这样做是为了避免把 大的分区分给那小的作业，免得资源被浪费，但这大的分区分给那小的作业，免得资源被浪费，但这 样却常常把小的作业推到了后面；但对于操作系统样却常常把小的作业推到了后面；但对于操作系统 ，我们做普通的要求就是简单的操作能被最快的反，我们做普通的要求就是简单的操作能被最快的反 馈给我们，即小的作业能够被最快的处理，因此，馈给我们，即小的作业能够被最快的处理，因此， 为了总能够满足用户的这个要求，一般要专门保证为了总能够满足用户的这个要求，一般要专门保证 总有一个小的分区，专门来处理那些小的事件、作总有一个小的分区，专门来处理那些小的事件、作 业，免得被大的作业抢去分区。业，免得被大的作业抢去分区。 或者通过加权来判断作业被推后的次数，到了或者通过加权来判断作业被推后的次数，到了 一定的程度，就不再跳过而是立即执行。一定的程度，就不再跳过而是立即执行。 4.2 4.2 交换交换 固定分区的方案在批处理系统中是种简单高效固定分区的方案在批处理系统中是种简单高效 的方案，每一个作业都在队列中一直到被分配到某的方案，每一个作业都在队列中一直到被分配到某 个分区，然后被执行完毕。只要能够放入内存，能个分区，然后被执行完毕。只要能够放入内存，能 够使够使CPU CPU 繁忙，就能满足要求。繁忙，就能满足要求。 但在分时系统中，或者个人的但在分时系统中，或者个人的PCPC中，这种方案就中，这种方案就 不太实际，会常常由于主存不够，需要把进程保存不太实际，会常常由于主存不够，需要把进程保存 到磁盘，同样的，也需要常常动态地把进程从磁盘到磁盘，同样的，也需要常常动态地把进程从磁盘 调入内存。调入内存。 这时就需要有新的技术，即交换技术这时就需要有新的技术，即交换技术(swapping)(swapping) 和虚拟内存技术的引入。和虚拟内存技术的引入。 OSOSOSOSOSOS AAA BBBB CCCC DD ab c d e f OS C D E 进程依次进入，并获得到自己所进程依次进入，并获得到自己所 需要的内存空间，当某个进程执行完需要的内存空间，当某个进程执行完 毕后便离开，它原来的占用的内存资毕后便离开，它原来的占用的内存资 源便得到释放，当新的进程到来的时源便得到释放，当新的进程到来的时 候，又可以从这个被释放的空间中划候，又可以从这个被释放的空间中划 分新的空间，因此主存的利用变得很分新的空间，因此主存的利用变得很 高效。（理想上的）高效。（理想上的） g 上图中的内存分配与固定分区的不同，上图中的内存分配与固定分区的不同， 它是一种可变分区的内存分配，这时内存中它是一种可变分区的内存分配，这时内存中 的分区的数目和大小都是在随时随着进程的的分区的数目和大小都是在随时随着进程的 变化而变化的。变化而变化的。 实际上，内存空间在不断划分的时候，本身实际上，内存空间在不断划分的时候，本身 的分布也在变化的越来越复杂，越来越不便的分布也在变化的越来越复杂，越来越不便 于管理。于管理。 迫切需要一个机制去整理这个零碎的空迫切需要一个机制去整理这个零碎的空 间。即空闲区域的合并间。即空闲区域的合并-内存紧缩。内存紧缩。( (低效的低效的 操作，耗时操作，耗时) ) *新的问题新的问题 如果根据进程需要给它分配内存，而且如果根据进程需要给它分配内存，而且 ，进程运行的时候大小不再变化，那么分配，进程运行的时候大小不再变化，那么分配 就简单，根据需要的大小分配即可；就简单，根据需要的大小分配即可； 如果进程运行时，该进程的数据段增如果进程运行时，该进程的数据段增 长，就需要分配新的内存，那进程所需的空长，就需要分配新的内存，那进程所需的空 间就开始变大，上图中，如果相邻区域是空间就开始变大，上图中，如果相邻区域是空 洞，则直接分配给它，但如果是进程时？交洞，则直接分配给它，但如果是进程时？交 换，将某一进程移出，但此时内存满了，磁换，将某一进程移出，但此时内存满了，磁 盘交换分区也满了，某进程则必须等待或杀盘交换分区也满了，某进程则必须等待或杀 死。死。 *新问题的解决带来的矛盾：新问题的解决带来的矛盾： 多数的进程都需要动态的空间，且申请新的内存多数的进程都需要动态的空间，且申请新的内存 空间，频繁的交换导致大量的进程等待和时间开销。空间，频繁的交换导致大量的进程等待和时间开销。 *矛盾的解决矛盾的解决 在每个进程申请空间的时候分配一些多余的内在每个进程申请空间的时候分配一些多余的内 存空间；（存空间；（A A） 或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采 用在进程的分区内分开放置的方式管理。（用在进程的分区内分开放置的方式管理。（B B） OSOS A A B B A A 为增长内存为增长内存 准备的内存准备的内存 实际使用的实际使用的 内存内存 为增长内存为增长内存 准备的内存准备的内存 实际使用的实际使用的 内存内存 OSOS A-PROGA-PROG A-DATAA-DATA A-STACKA-STACK B-DATAB-DATA B-STACKB-STACK B-PROGB-PROG B B 为增长内存为增长内存 准备的内存准备的内存 为增长内存为增长内存 准备的内存准备的内存 4.2 .1 4.2 .1 使用位图的内存管理使用位图的内存管理 由于操作系统需要对内存进行分配管理和回由于操作系统需要对内存进行分配管理和回 收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用 的是位图法和自由链表：的是位图法和自由链表： A A B B C C D D E E (a ) 对于位图方法，位图的大小与内存的大小和分配对于位图方法，位图的大小与内存的大小和分配 的单位的大小相关，内存不变时，被分配的单个单的单位的大小相关，内存不变时，被分配的单个单 元越小，则位图就越大。元越小，则位图就越大。 位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内 存很小但也有缺陷：定位的速度受限，由于每个位存很小但也有缺陷：定位的速度受限，由于每个位 图单元代表一个被分配的单元，所以连续性不强，图单元代表一个被分配的单元，所以连续性不强， 对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速 在位图中找到这样连续的空间。故实际不很常用。在位图中找到这样连续的空间。故实际不很常用。 4.2 .2 4.2 .2 使用链表的内存管理使用链表的内存管理 这种方法是通过一个链表来管理已经分配的和这种方法是通过一个链表来管理已经分配的和 尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存 的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可以使被某个进程所占用， 也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。 表的内容包括段的性质、开始地址、长度、长表的内容包括段的性质、开始地址、长度、长 度和指向下一个表项的指针。这是一般，链表的组度和指向下一个表项的指针。这是一般，链表的组 织都按照地址来排列，这样的进程切换会很直观，织都按照地址来排列，这样的进程切换会很直观， 更有效的方法是采用双向链表来记录。更有效的方法是采用双向链表来记录。 但这时就需要对空洞进行处理。但这时就需要对空洞进行处理。 A A B B X X A A X X A A B B B B X X X X A A B B 变为变为 变为变为 变为变为 变为变为 （a a） （b b） （c c） （d d） 对于某进程对于某进程X X结束的时候同邻居合并的四种方式结束的时候同邻居合并的四种方式 对于这种内存的组织和管理方法，我们需要讨对于这种内存的组织和管理方法，我们需要讨 论如何用合理的方法来为新创建的进程和新换进来论如何用合理的方法来为新创建的进程和新换进来 的进程分配大小：的进程分配大小： *最简单的分配算法最简单的分配算法最先匹配算法（最先匹配算法（first fitfirst fit） 存储管理器沿内存段链表从头开始寻找足够存储管理器沿内存段链表从头开始寻找足够 的空间来装载进程，除非找到的这个区域的大小刚的空间来装载进程，除非找到的这个区域的大小刚 好和进程相同，否则就要把这个空间拆为两部分，好和进程相同，否则就要把这个空间拆为两部分， 一部分来装进程，另一部分依然为空。一部分来装进程，另一部分依然为空。 属于快速算法，搜索的开销很小。属于快速算法，搜索的开销很小。 *最先匹配的变形最先匹配的变形下次匹配法（下次匹配法（next fitnext fit） 工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索 完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜 索。索。( (缺点：较大的空闲分区不易保留）缺点：较大的空闲分区不易保留） *最佳匹配算法（最佳匹配算法（best fitbest fit） 每次搜索整个链表中最适合该进程大小的内每次搜索整个链表中最适合该进程大小的内 存空间，没有完全相同就寻找次之的；每次都要搜存空间，没有完全相同就寻找次之的；每次都要搜 索整个链表故速度很慢，而且每次都可能拆分内存索整个链表故速度很慢，而且每次都可能拆分内存 ，而且生成的新的内存空间会很小。，而且生成的新的内存空间会很小。 *放弃最佳匹配算法放弃最佳匹配算法采用最差匹配算法采用最差匹配算法 采用最差，即每次找最大的内存空间分给进采用最差，即每次找最大的内存空间分给进 程，这样就不会产生大量的极小的内存空洞，即被程，这样就不会产生大量的极小的内存空洞，即被 分开后剩余的那部分仍然足够大，可以继续被使用分开后剩余的那部分仍然足够大，可以继续被使用 。 对于这四种算法，都不是很有效的方法对于这四种算法，都不是很有效的方法 ，如果把表示进程占用的内存段和表示空闲，如果把表示进程占用的内存段和表示空闲 的内存段分开放到两个链表中，这样检索效的内存段分开放到两个链表中，这样检索效 率会提高很多，但这样带来的新麻烦就是控率会提高很多，但这样带来的新麻烦就是控 制过程的复杂化和内存释放过程的延长，不制过程的复杂化和内存释放过程的延长，不 得不把释放的内存从一个链表中清除再放到得不把释放的内存从一个链表中清除再放到 另一个中去。另一个中去。 *一些改进思路一些改进思路 * * 进程和空洞（空闲区）存放在两个链表中，进程和空洞（空闲区）存放在两个链表中， 针对最佳匹配算法的缺陷，将空洞的组织不按地址针对最佳匹配算法的缺陷，将空洞的组织不按地址 ，而是按照大小来组织，这样就减小了搜索时的开，而是按照大小来组织，这样就减小了搜索时的开 销。销。 *进程和空洞存放在两个链表中，用空洞本身进程和空洞存放在两个链表中，用空洞本身 来存放这个链表，第一个字存放空洞的大小，第二来存放这个链表，第一个字存放空洞的大小，第二 个字存放下一个空洞的地址。个字存放下一个空洞的地址。 *快速匹配法，按照常见进程需要的空间大小快速匹配法，按照常见进程需要的空间大小 设置单独的链表，这种算法就根据进程所需空间的设置单独的链表，这种算法就根据进程所需空间的 大小快速在这些特殊的空洞链表中查找空内存。它大小快速在这些特殊的空洞链表中查找空内存。它 需要将所有的空洞进行排序，即进程换出时的空洞需要将所有的空洞进行排序，即进程换出时的空洞 合并判断。合并判断。 4.3 4.3 虚拟存储器虚拟存储器 交换技术与覆盖技术是交换技术与覆盖技术是在多道环境下扩充内存的在多道环境下扩充内存的 方法，用以解决在较小的存储空间中运行较大程序时方法，用以解决在较小的存储空间中运行较大程序时 遇到的矛盾。遇到的矛盾。 覆盖技术主要用在早期的操作系统中；覆盖技术主要用在早期的操作系统中； 交换技术被广泛用于小型分时系统中，交换技术交换技术被广泛用于小型分时系统中，交换技术 的发展导致了虚存技术的出现。的发展导致了虚存技术的出现。 交换技术与覆盖技术共同点：交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行进程的程序和数据主要放在外存，当前需要执行 的部分放在内存，内外存之间进行信息交换。的部分放在内存，内外存之间进行信息交换。 覆盖：一个作业的若干程序段，或几个作业的某些覆盖：一个作业的若干程序段，或几个作业的某些 部分共享某一个存储空间。部分共享某一个存储空间。 把程序划分为若干个功能上相对独立的程序段，把程序划分为若干个功能上相对独立的程序段， 按照其自身的逻辑结构将那些不会同时执行的程序段按照其自身的逻辑结构将那些不会同时执行的程序段 共享同一块内存区域。共享同一块内存区域。 程序段先保存在磁盘上，当有关程序段的前一部程序段先保存在磁盘上，当有关程序段的前一部 分执行结束，把后续程序段调入内存，覆盖前面的程分执行结束，把后续程序段调入内存，覆盖前面的程 序段（内存序段（内存“ “扩大扩大” ”了）。了）。 一般要求作业各模块之间有明确的调用结构，程一般要求作业各模块之间有明确的调用结构，程 序员要向系统指明覆盖结构，然后又由操作系统完成序员要向系统指明覆盖结构，然后又由操作系统完成 自动覆盖。自动覆盖。 A A 8K8K E E 4K4K F F 10K10K C C 10K10K B B 8K8K D D 12K12K 作业作业X X的调用结构的调用结构 作业作业X X的常驻区的常驻区 A A（8K8K） 覆盖区覆盖区0 0 （10K10K） 覆盖区覆盖区1 1 （12K12K） B BC C D D E E F F 缺点：对用户不透明，增加了用户负担。缺点：对用户不透明，增加了用户负担。 例子：目前这一技术用于小型系统中的系统程例子：目前这一技术用于小型系统中的系统程 序的内存管理上，序的内存管理上，MS-DOSMS-DOS的启动过程中，多次的启动过程中，多次 使用覆盖技术；启动之后，用户程序区使用覆盖技术；启动之后，用户程序区TPATPA的高的高 端部分与端部分与COMMAND.COMCOMMAND.COM暂驻模块也是一种覆暂驻模块也是一种覆 盖结构。盖结构。 虚拟存储器的基本思想是：虚拟存储器的基本思想是： 程序、数据、堆栈的大小可以超过内存的大小程序、数据、堆栈的大小可以超过内存的大小 ，操作系统把程序当前使用的部分保留在内存，而，操作系统把程序当前使用的部分保留在内存，而 把其它部分保存在磁盘上，并在需要时在内存和磁把其它部分保存在磁盘上，并在需要时在内存和磁 盘之间动态交换。盘之间动态交换。 虚拟存储器支持多道程序设计技术。虚拟存储器支持多道程序设计技术。 虚存： 把内存与外存有机的结合起来使用， 从而得到一个容量很大的“内存”，这就是 虚存。 实现思想： 当进程运行时，先将一部分程序装入 内存，另一部分暂时留在外存，当要执行 的指令不在内存时，由系统自动完成将它 们从外存调入内存工作。 4.3.1 4.3.1 分页（虚拟页式存储管理）分页（虚拟页式存储管理） 在虚拟存储器系统中，内存管理单元负责地址的在虚拟存储器系统中，内存管理单元负责地址的 计算和重新定位。它是一组或一个芯片，完成地计算和重新定位。它是一组或一个芯片，完成地 址映射的功能。址映射的功能。 CPUCPU MMUMMU 内存内存 磁盘磁盘 控制器控制器 总线总线 MMUMMU把物理地址送给存储器把物理地址送给存储器 CPUCPU把虚拟地址送给把虚拟地址送给MMUMMU 内存管内存管 理单元理单元 一方面，把物理内存划分为许多个固定大小的一方面，把物理内存划分为许多个固定大小的 内存块，称为物理页面，或者是页框（内存块，称为物理页面，或者是页框（page page frameframe） 另一方面，把虚拟地址空间也划分为大小相同另一方面，把虚拟地址空间也划分为大小相同 的块，称为虚拟页面，或者简称为页面（的块，称为虚拟页面，或者简称为页面（pagepage） ，页面的大小要求是，页面的大小要求是2 2的整数次幂。的整数次幂。 X X 60K-64K60K-64K X X 56K-60K56K-60K X X 52K-56K52K-56K X X 48K-52K48K-52K 7 7 44K-48K44K-48K X X 40K-44K40K-44K 5 5 36K-40K36K-40K X X 32K-36K32K-36K X X 28K-32K28K-32K X X 24K-28K24K-28K 3 3 20K-24K20K-24K 4 4 16K-20K16K-20K 0 0 12K-16K12K-16K 6 6 8K-12K 8K-12K 1 1 4K-8K 4K-8K 2 2 0K-4K 0K-4K X X X X 3 3 4 4 0 0 6 6 1 1 2 2 28K-32K28K-32K 24K-28K24K-28K 20K-24K20K-24K 16K-20K16K-20K 12K-16K12K-16K 8K-12K 8K-12K 4K-8K 4K-8K 0K-4K 0K-4K 虚地址空间虚地址空间 物理地址空间物理地址空间 虚页虚页 页框页框 虚地址中虚地址中 称作页称作页 物理地址中物理地址中 称作页框称作页框 程序程序 MOV REG , 0MOV REG , 0 MMUMMU MOV REG,8192MOV REG,8192 MMUMMU MOV REG,24576MOV REG,24576 MOV REG,8192MOV REG,8192 *隐含的问题：隐含的问题： 程序不知道实际的存储器的大小，由于页和页框程序不知道实际的存储器的大小，由于页和页框 的大小一样，则必然有些程序中的地址是没有经过的大小一样，则必然有些程序中的地址是没有经过 映射的，即虚拟存储器中有空页，他没有和实际的映射的，即虚拟存储器中有空页，他没有和实际的 物理内存对应起来。虚页是否被对应了都专门有一物理内存对应起来。虚页是否被对应了都专门有一 位来存储这个信息。位来存储这个信息。 如：如：MOV REG,32780MOV REG,32780 这时会发现在虚页这时会发现在虚页8 8里没有对应的物理地址，这时里没有对应的物理地址，这时 MMUMMU就无法处理此时的问题。这时的故障就叫做缺就无法处理此时的问题。这时的故障就叫做缺 页故障。操作系统需要找到一个页框将其内容移到页故障。操作系统需要找到一个页框将其内容移到 磁盘，把刚才需要引用的页取到这个页框中，并修磁盘，把刚才需要引用的页取到这个页框中，并修 改映射，然后重新启动刚才的指令。改映射，然后重新启动刚才的指令。 MMUMMU的内部结构及工作方法的内部结构及工作方法 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 110110 在在/ /不在内存不在内存 页表页表 虚地址虚地址 81968196 物理地址物理地址 2458024580 000000 0 0 1515 000000 0 0 1414 000000 0 0 1313 000000 0 0 1212 111111 1 1 1111 000000 0 0 1010 101101 1 1 9 9 000000 0 0 8 8 000000 0 0 7 7 000000 0 0 6 6 011011 1 1 5 5 100100 1 1 4 4 000000 1 1 3 3 110110 1 1 2 2 001001 1 1 1 1 010010 1 1 0 0 2 2 = = 1616 4 4 2 2 = = 40964096 1212 4.3.2 4.3.2 页表页表 （page tablepage table） 页表是用来索引页面的，通过判断页表的存页表是用来索引页面的，通过判断页表的存 在位，判断这个虚页在物理内存中是否有对应的页在位，判断这个虚页在物理内存中是否有对应的页 框，如果有，就直接通过页表函数获得实际的物理框，如果有，就直接通过页表函数获得实际的物理 地址定位物理内存，如果没有，就通知操作系统，地址定位物理内存，如果没有，就通知操作系统， 引发中断，寻找空页框来装入这个虚页。引发中断，寻找空页框来装入这个虚页。 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 2 2 = = 1616 4 4 2 2 = = 40964096 1212 定位页面定位页面根据页面，加上偏移地址完成实际的地址定位根据页面，加上偏移地址完成实际的地址定位 对于对于1616位指令系统的一种方案位指令系统的一种方案 地址映射在实际应用中的问题：地址映射在实际应用中的问题： 现代计算机的虚地址一般最少都现代计算机的虚地址一般最少都3232位，如果按位，如果按 照页面照页面4K4K来处理，则对此系统来说，就是有来处理，则对此系统来说，就是有 的页面大小，同时又有的页面大小，同时又有 个页表记录。而个页表记录。而 6464位系统的更为庞大位系统的更为庞大. 即问题主要是页表的庞大导致了索引不再高效即问题主要是页表的庞大导致了索引不再高效 ； 另外，从虚地址到物理地址的映射的频繁执行另外，从虚地址到物理地址的映射的频繁执行 ，现有的庞大页表无法完成快速的查找定位，现有的庞大页表无法完成快速的查找定位 地址映射相应变慢。地址映射相应变慢。 2 =40962 =4096 1212 2 =1048562 =104856 2020 问题的解决：问题的解决： 一、利用硬件配合解决一、利用硬件配合解决 -CPU-CPU端端 将页表装入寄存器中，避免进程运行时访问内存，将页表装入寄存器中，避免进程运行时访问内存， 对页表的检查也直观。但这样当页表大的时候，就要对页表的检查也直观。但这样当页表大的时候，就要 很多硬件寄存器来存放，代价昂贵。每次进程切换时很多硬件寄存器来存放，代价昂贵。每次进程切换时 候都要装入内存中的页表，开销也会很大。候都要装入内存中的页表，开销也会很大。 二、另一种极端，全放入内存二、另一种极端，全放入内存 这时的硬件开销就很小，只需要指向页表起始地址这时的硬件开销就很小，只需要指向页表起始地址 的寄存器即可。环境切换时，改变这个寄存器里的东的寄存器即可。环境切换时，改变这个寄存器里的东 西即可。但缺点是执行每条指令时都要一次或多次访西即可。但缺点是执行每条指令时都要一次或多次访 问内存。故很少单纯使用。问内存。故很少单纯使用。 *多级页表多级页表 为了不将庞大的页表全放内存，引入了多级页表为了不将庞大的页表全放内存，引入了多级页表 技术：技术： 对于此例：对于此例：3232位虚地址分为了位虚地址分为了1010位的位的PT1PT1域，域，1010位位 的的PT2PT2域，每个页的大小是域，每个页的大小是1212位。位。 每一个进程都拥有自己的页表，即每个进程都可以拥每一个进程都拥有自己的页表，即每个进程都可以拥 有有4G4G的虚存空间。的虚存空间。 当一个虚地址定位的时候，具体过程如下：当一个虚地址定位的时候，具体过程如下： 1010位位1010位位1212位位 虚地址虚地址 根页表指针根页表指针 帧号帧号偏移量偏移量 页页 帧帧 根页表根页表 10241024个个PTEPTE 页表页表 10241024个个PTEPTE 物理内存物理内存 当用户的页不在主存中，当用户的页不在主存中， 就会发生缺页故障，由操就会发生缺页故障，由操 作系统完成换页的工作。作系统完成换页的工作。 *页表分析页表分析 禁用缓存禁用缓存 访问访问( (引用引用 ) ) 修改修改 保护保护 在在/ /不在不在 页框号页框号 页框号（物理页面号）：具体对应的物理内存的位置页框号（物理页面号）：具体对应的物理内存的位置 在在/ /不在位（有效位）：表示是否会发生缺页不在位（有效位）：表示是否会发生缺页 保护位：表示此页所允许的操作（是只读、可读写、可执行）保护位：表示此页所允许的操作（是只读、可读写、可执行） 修改位：表示此页被修改的情况（上一次的操作）修改位：表示此页被修改的情况（上一次的操作）-dirty bit-dirty bit 引用位：此页被访问的情况，页面替换算法的重要依据引用位：此页被访问的情况，页面替换算法的重要依据 禁用缓存：特殊使用，保证数据的及时更新禁用缓存：特殊使用，保证数据的及时更新 4.3.3 TLB-4.3.3 TLB-关联存储器（转换后援存储器）关联存储器（转换后援存储器） 用硬件手段来解决庞大页表的问题。由于页表使用硬件手段来解决庞大页表的问题。由于页表使 用的不均匀性，小部分页表被大量频繁的使用，另一用的不均匀性，小部分页表被大量频繁的使用，另一 些则很少被使用，故专门用硬件些则很少被使用，故专门用硬件TLB(TranslationTLB(Translation LookasideLookaside Buffer) Buffer)来存放常用的页号，并不停的保来存放常用的页号，并不停的保 持持TLBTLB中页号的更新。中页号的更新。 工作时，当有虚地址需要转换时，先到工作时，当有虚地址需要转换时，先到TLBTLB中中 去作判断，如果不在去作判断，如果不在TLBTLB中，就去页表中查询，并在中，就去页表中查询，并在 获得后更新获得后更新TLBTLB中的页号数据，淘汰一个条目，将其中的页号数据，淘汰一个条目，将其 信息写回内存中的页表项，把新的条目加入；如果虚信息写回内存中的页表项，把新的条目加入；如果虚 页号在页号在TLBTLB中，则判断保护情况，合法就直接取出使中，则判断保护情况，合法就直接取出使 用，不用查询页表，不合法时，就出现保护故障。用，不用查询页表，不合法时，就出现保护故障。 用于加快页表查找的TLB *软件软件TLBTLB管理管理 现代很多大型操作系统的缺页故障不再由现代很多大型操作系统的缺页故障不再由MMUMMU 处理，而是交给处理，而是交给TLBTLB，而，而TLBTLB也是由操作系统装入的也是由操作系统装入的 ，因此，因此，TLBTLB的缺页故障比的缺页故障比MMUMMU的高得多，但通过的高得多，但通过 设置设置TLBTLB的大小，可以很有效提高页面的命中率，而的大小，可以很有效提高页面的命中率，而 此时此时MMUMMU的设计就可以简化很多，从而使的设计就可以简化很多，从而使CPUCPU可以可以 更好地设计自己所需的其他部件。更好地设计自己所需的其他部件。 并且操作系统可以根据进程的性质，自动预装进并且操作系统可以根据进程的性质，自动预装进 程可能需要的页面，这样，就使进程的缺页率大大程可能需要的页面，这样，就使进程的缺页率大大 减少。减少。 4.3.4 4.3.4 反置页表（逆向页表）反置页表（逆向页表） 对于对于6464位计算机，如果页面大小仍然位计算机，如果页面大小仍然4K4K，此时，此时 页表项就变得更加庞大，不可能去管理好，故用了页表项就变得更加庞大，不可能去管理好，故用了 逆向的思路来处理：根据内存中的物理页面号来组逆向的思路来处理：根据内存中的物理页面号来组 织页表，用物理页面号来作为访问页表的索引，有织页表，用物理页面号来作为访问页表的索引，有 多少个物理页面，就在页表中设置多少个页表项。多少个物理页面，就在页表中设置多少个页表项。 这样，可节省大量的物理空间。这样，可节省大量的物理空间。 弱点是虚地址到实际物理地址转换很困难，不弱点是虚地址到实际物理地址转换很困难，不 能根据虚地址查物理地址，必须搜索整个页表，才能根据虚地址查物理地址，必须搜索整个页表，才 能找到它所对应的物理页面号。能找到它所对应的物理页面号。 ( (散列散列) ) 页号页号偏移量偏移量 虚地址虚地址 散列表散列表 页号页号表项表项链链 反向页表反向页表 帧号帧号 帧号帧号偏移量偏移量 实地址实地址 4.4 4.4 页面替换算法页面替换算法 页的置换算法：当发生缺页，而主存中已无空闲页架 时，需选一页淘汰。选取淘汰页的方法叫页的置换算 法。 抖动：刚被淘汰出去的页，不久又被访问，又需把它 调入而将另一页淘汰出去，很可能又把刚调入的或很 快要用的页淘汰出去了。如此反复更换页面，以至系 统大部分机时花在页面的调度和传输上，系统的实际 效率很低。这种现象称为“抖动”。 缺页率：f = (缺页次数/访问页面总数)% 常见的页面置换算法： 最佳置换算法 OPT；先进先出置换算法FIFO；最近最 少使用置换算法LRU；最近未使用置换算法NUR；工 作集. 4.4.1 最佳置换算法 OPT（Optimum Strategy） 基本原则： 淘汰在将来再也不被访问，或者是在最远的 将来才能被访问的页。 特点： 无法预测作业将用到哪些页！所以此算法是 无法实现的理论上的算法。 例：某进程分配物理页面数为3，其运行期间 页面访问序列：A,B,C,D,A,B,E,A,B,C,D,E， 分析其按照OPT算法进行页面置换时的缺页 情况。（堆栈式算法） 最佳置换算法OPT 页面访问序列页面访问序列 A BC D A BEA BCD E A A A A BA A BEEEE BB BA BB EBCD D C D