存储管理 存储体系 存储管理的任务 分区存储管理 页式存储管理 交换技术与覆盖技术 虚拟存储

一、存储体系 存储系统设计三个问题： 容量、速度和成本 容量：需求无止境 速度：能匹配处理器的速度 成本问题：成本和其它部件相比应在合适范围之内

层次化的存储体系结构

存储体系 操作系统协调各存储器的使用 重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥

内存 由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器 分为： 系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据

二、存储管理的任务 （1）内存空间的管理、分配与回收 记录内存的使用情况 ——设置相应的内存分配表 （内存分配回收的依据） 内存空间划分问题？ 静态或动态，等长或不等长

存储管理的任务（续1） 内存分配表 位示图：用一位（bit）表示一个空闲页面（0：空闲，1：占用） 空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中 空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用 空闲块链表：将所有的空闲块链成一个链表 1 …... 1 …... 第0页第1页 第i页 第n-1页

存储管理的任务（续2） 确定分配算法 连续性 离散性 驻留性 交换性 一次性 多次性 实施内存分配 内存回收 连续性 离散性 驻留性 交换性 一次性 多次性 实施内存分配 内存回收 内存分配：静态方式 与 动态方式

存储管理的任务（续3） （2）存储共享 两个或多个进程共用内存中相同区域 目的： 节省内存空间，提高内存利用率 实现进程通信（数据共享） 共享内容： 代码共享，要求代码为纯代码 数据共享

存储管理的任务（续4） （3）存储保护 为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行 通常由硬件完成保护功能，由软件辅助实现

存储管理的任务（续5） 保护过程----防止地址越界 每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理 一般由硬件提供一对寄存器： 基址寄存器：存放起始地址 限长寄存器：存放长度 （或 上界寄存器/下界寄存器）

存储管理的任务（续6） 保护过程----防止操作越权 对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权 即读写保护

存储管理的任务（续7） （4）内存扩充 通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间 具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用

存储管理的任务（续8） （5）地址转换 又称地址重定位、地址映射 逻辑地址（相对地址，虚地址） 物理地址（绝对地址，实地址） 地址映射

存储管理的任务（续9） 逻辑地址（相对地址，虚地址） 用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址 不能用逻辑地址在内存中读取信息 物理地址（绝对地址，实地址） 内存中存储单元的地址，可直接寻址

存储管理的任务（续10） 地址转换 为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射 原因: 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换

. . . . . . . . . . . . . . . . . . . . . 存储管理的任务（续11） 逻辑地址空间 物理地址空间 + BR . . . . 1000 . . VR 100 LOAD A 200 200 + LOAD A 200 1100 . . . . . . 200 . 3456 3456 1200 . . . . . . . . 1300 300

存储管理的任务（续12） 静态地址转换 当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换 一般在装入内存时由软件完成 动态地址转换 在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成） 硬件上需要一对寄存器的支持

三、分区存储管理方案 系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区 固定分区 可变分区

1. 固定分区 预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区 每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装一个且只能装一个作业 存储分配：如果有一个空闲区，则分配给进程

多个等待队列 分区4 分区3 分区2 分区1 操作系统 分区4 分区3 分区2 分区1 操作系统 单个等待队列

固定分区（续） 内存管理：设置内存分配表 内存分配： 内存回收： 缺点：内存利用率不高 分区号 起始地址 长度 状态 进程名

2. 可变分区存储管理方案 基本思想 内存不是预先划分好的 作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配 若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间

可变分区存储管理方案（续1） 内存管理 空闲块表——记录了空闲区起始地址和长度 已分配区表 内存分配 动态分配 三种分配算法：首先适配、最佳适配、最差适配

空闲区表 已分配区表 0K 15K 38K 48K 68K 80K 110K 120K 始址 长度 标志 15K 23K 未分配 48K J1 38K 10K J2 68K 12K J3 110K J4 空 68K 80K 110K 120K

空闲区表 已分配区表 0K 15K 38K 48K 68K 80K 85K 98K 110K 120K 始址 长度 标志 15K 23K 未分配 48K 20K 98K 12K 空 0K 15K 38K 48K 已分配区表 始址 长度 标志 0K 15K J1 38K 10K J2 68K 12K J3 110K J4 80K 5K J5 85K 13K J6 68K 80K 85K 98K 110K 120K

可变分区存储管理方案（续2） 内存回收 当某一块归还后，前后空间合并，修改内存空闲块表 考虑：上邻、下邻、上下相邻、上下不相邻 “碎片”问题 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片 造成存储资源的浪费

可变分区存储管理方案（续3） “碎片”问题解决 紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域 （又称：紧缩技术，紧致技术，浮动技术，搬家技术） 问题：开销 大 移动时机 ？

可变分区存储管理方案（续4） 分区的保护：设置界地址寄存器 保护键 优点：便于动态申请内存 便于共享内存 便于动态链接 缺点： 碎片问题(外碎片)，内存利用率不高 受实际内存容量限制

四、页式存储管理方案 1. 基本思想（工作原理） 用户程序划分 把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址 逻辑地址 页号 页内地址

基本思想（续1） 逻辑地址 用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址 页号P 页内位移量W 31 12 11 编号0~1048575 相对地址0~4095

基本思想（续2） 内存空间 按页的大小划分为大小相等的区域，称为内存块（物理页面，页框） 内存分配 以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻

. 1 2 3 4 5 6 作业的 地址空间 页框 （物理块） 页号 页表 主存中页框（物理块）

2. 管理 页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系 页表放在内存，属于进程的现场信息 空块管理——位示图

管理（续1） 31 0/1 0/1 0/1 0/1 0/1 1 …… …… 7 空闲块数 空块管理——位示图

管理（续2） 内存的分配与回收 计算一个作业所需要的总块数N 查位示图，看看是否还有N个空闲块 如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB 依次分配N个空闲块，将块号和页号填入页表 修改位示图

3. 硬件支持 系统设置一对寄存器： 页表始址寄存器 页表长度寄存器 相联存储器——快表 快表表项： 页号；内存块号；标识位；淘汰位

硬件支持（续1） 相联（联想）存储器（associative memory） TLB（Translation lookaside buffers） 介于内存与寄存器之间的存储机制，它又叫快表 用途：保存正在运行进程的页表的子集（部分表项） 特点：按内容并行查找

硬件支持（续2） 引入快表的目的： 为了提高地址映射速度 快表淘汰问题？

+ 地址映射机制 b l 页号p 页内地址d P>=1 快表 页表 p’ p p’ . . . P’ d 页表地址寄存器 页表长度寄存器 逻辑地址 b l 页号p 页内地址d + 比较 P>=1 快表 页表 p’ 地址越界 p p’ . . . P’ d 地址映射机制 物理地址

五、覆盖技术与交换技术 1、为什么引入？ 在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾 覆盖技术主要用在早期的操作系统中 交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现

为什么引入？（续） 交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换 不同点：如何控制交换？

2、覆盖技术 把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域 程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了） 覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间 一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖

覆盖技术（续1） 覆盖区0 C B （10K） D E 覆盖区1 F （12K） 作业X的常驻区 A（8K） 作业X的调用结构 A 8K B

覆盖技术（续2） 缺点： 对用户不透明，增加了用户负担 例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构

3、交换技术 为什么引入？ 当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度 多用于分时系统中

交换技术（续1） 交换技术实现中的几个问题 选择原则 即：将哪个进程换出/内存？ 例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的 需要特殊考虑的是：任何等待I/O的进程中存在的问题 解决： 从不换出处于等待I/O状态的进程 有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助

交换技术（续2） 交换时机的确定 何时需发生交换？ 例子： 只要不用就换出（很少再用） 只在内存空间不够或有不够的危险时换出 交换时需要做哪些工作？ 需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取

交换技术（续3） 换入回内存时位置的确定 换出后再换入的内存位置一定要在换出前的原来位置上吗？ 受地址“绑定”技术的影响，即绝对地址产生时机的限制 与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段

六、虚拟存储 连续性 ； 离散性 驻留性 ； 交换性 一次性； 多次性 以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术

1、概述 问题的提出 程序大于内存 程序暂时不执行或运行完是否还要占用内存 基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换 虚拟存储技术支持多道程序设计系统

虚拟地址 CPU 内存 磁盘 控制器 MMU 总线 物理地址 MMU：内存管理单元

} 虚页 虚地址空间 X 7 5 3 4 6 1 2 物理地址空间 页框 60K-64K 56K-60K 52K-56K 48K-52K 6 1 2 } 虚页 物理地址空间 页框 28K-32K 24K-28K 20K-24K 16K-20K 12K-16K 8K-12K 4K-8K 0K-4K

1 15 物理地址 24580 000 111 1 101 011 100 110 001 010 14 13 12 11 10 9 8 7 6 5 4 3 2 1 页表 110 虚地址 8196 在/不在内存 1

概述（续1） 程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面 时间局部性 一条指令被执行了，则在不久的将来它可能再被执行 空间局部性 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用

概述（续2） 虚拟存储技术 虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存 实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作 目的： 提高内存利用率

2、虚拟页式存储管理 （1）基本思想 在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面

（2）页表表项设计 页号、驻留位、内存块号、保护位、访问位、修改位 驻留位（中断位）：表示该页是在内存还是在外存 访问位：根据访问位来决定淘汰哪页（由不同的算法决定） 修改位：查看此页是否在内存中被修改过 保护位：读/写/执行 禁止缓存位：采用内存映射I/O的机器中需要 页号 中断位 内存块号 保护位 禁止缓存位 访问位 修改位

（3）缺页中断（Page Fault）处理 在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去 如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号 若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存

（4）页面淘汰算法 理想淘汰算法—最佳页面算法（OPT） 淘汰以后不再需要的或最远的将来才会用到的页面 实现？ 作用？

页面淘汰算法（续1） 最近未使用页面淘汰算法 （NRU——Not Recently Used） 选择在最近一段时间内未使用过的一页并淘汰之 实现：设置两位 访问位（R）， 修改位（M） 启动一个进程时，R、M置0 R被定期清零

页面淘汰算法（续2） 发生缺页中断时，操作系统检查R，M： 第0类：无访问，无修改 第1类：无访问，有修改 第2类：有访问，无修改 第3类：有访问，有修改 操作系统随机从编号最小的非空类中选择一页淘汰

页面淘汰算法（续3） 先进先出页面淘汰算法（FIFO） 选择在内存中驻留时间最长的页并淘汰之 对照：超市撤换商品 第二次机会淘汰算法 (SCR-Second Chance ) 按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0 实现：时钟（Clock）算法

页面淘汰算法（续4） 最近最久未使用页面淘汰算法 （LRU——Least Recently Used） 选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页 实现代价很高 时间戳或硬件方法

页面淘汰算法（续5） LRU的软件解决方案： 最不经常使用（NFU-Not Frequently Used） 选择访问次数最少的页面淘汰之 改进（模拟LRU）：计数器在加R前先右移一位 R位加到计数器的最左端 称为老化算法

页面淘汰算法（续6） 某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5，计算缺页次数

页面淘汰算法（续7） FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 5 5 2 1 1 页2 4 3 2 1 4 3 3 3 5 2 2 页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x   x x  共缺页中断9次

页面淘汰算法（续8） LRU 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 4 3 2 1 5 页2 4 3 2 1 4 3 5 4 3 2 1 页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x   x x x 共缺页中断10次

页面淘汰算法（续9） OPT 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 2 1 1 页2 4 3 3 3 3 3 3 3 5 5 5 页3 4 4 4 4 4 4 4 4 4 4 x x x x   x   x x  共缺页中断7次

页面淘汰算法（续10） 例2：某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？用FIFO算法计算缺页次数

页面淘汰算法（续11） m=3时，缺页中断9次 m=4时，缺页中断10次 注：FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加

（5）影响缺页次数的因素 (1) 分配给进程的物理页面数 (2) 页面本身的大小 (3) 程序的编制方法 (4) 页面淘汰算法

例子3：内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放 影响缺页次数的因素（续1） 例子3：内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放 程序编制方法1： For j:=1 to 128 For i:=1 to 128 A[i,j]:=0; 程序编制方法2： For i:=1 to 128 For j:=1 to 128 A[i,j]:=0;

3、性能问题 （1）颠簸（抖动） 在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动 原因： 页面淘汰算法不合理 分配给进程的物理页面数太少

（2）工作集（Working Set）模型 基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断 如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数

工作集（Working Set）模型（续1） 对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集 内容取决于页的三个因素： 访页序列特性 时刻Ti 窗口长度(△)

工作集（Working Set）模型（续2） 例： 26157775162341234443434441327 | |t1 | |t2 ws(t1)={1,2,5,6,7} ws(t2)={3,4}

4.其他有关设计问题 页面尺寸 TLB的大小、位置、访问方式 局部与全局分配策略 装入策略 与 清除策略 多级页表

其他有关设计问题（续1） 页面尺寸 确定页面大小对于分页的硬件设计非常重要 要考虑的因素： 内部碎片 页表长度 缺页次数（缺页率） Intel 80x86/Pentium：4096 或 4M 多页面大小的研究与使用

其他有关设计问题（续2） 快表TLB（Translation Lookaside Buffers） 为加快地址映射速度，改善系统性能 采用联想映射技术同时查找 置于MMU（Memory Management Unit）中 大小： Intel 80x86/Pentium：32项 SGI MIPS R4000：48项 命中率（在TLB中发现一个页面的百分比） TLB的两种访问方式： 软件访问 硬件访问

其他有关设计问题（续3） 局部与全局分配策略 分配给一个进程多少页面？ 固定数目分配 与 可变数目分配 置换范围 全局 与 局部 固定数目分配 与 可变数目分配 置换范围 全局 与 局部 三种组合：固定 + 局部 可变 + 全局 固定 + 全局

其他有关设计问题（续4） 页面装入策略与清除策略 装入方式 请求调页（demand paging） 预先调页（prefetch） 清除方式

其他有关设计问题（续5） 多级页表 32位 进程页表多大？ 结论：一个进程的页表的各页之间可以不连续存放 32位 进程页表多大？ 设：页面大小为4K 用户空间 2GB 则：一个进程 219页 设：每个内存块号 4字节 则：进程页表 512页 结论：一个进程的页表的各页之间可以不连续存放 解决：页表本身使用地址索引——页目录

二级页表结构及地址映射 + + 页目录地址 虚拟地址 目录位移 页表位移 页位移 页目录（每进程一个） 页表 内存块 块号 页表地址 31 21 11 页目录（每进程一个） 页表 内存块 块号 + 页表地址 + 代码或数据 . . . 二级页表结构及地址映射 页目录地址