存储管理17667

1、存储管理存储管理n存储体系存储体系n存储管理的任务存储管理的任务n分区存储管理分区存储管理n页式存储管理页式存储管理n交换技术与覆盖技术交换技术与覆盖技术n虚拟存储虚拟存储一、存储体系一、存储体系存储系统设计三个问题：存储系统设计三个问题： 容量、速度和成本容量、速度和成本n容量：需求无止境容量：需求无止境n速度：能匹配处理器的速度速度：能匹配处理器的速度n成本问题：成本和其它部件相比应在合成本问题：成本和其它部件相比应在合适范围之内适范围之内层次化的存储体系结构层次化的存储体系结构存储体系存储体系操作系统协调各存储器的使用操作系统协调各存储器的使用 重要性：直接存取要求内存速度尽量快到重要性

2、：直接存取要求内存速度尽量快到与与CPU取指速度相匹配，大到能装下当取指速度相匹配，大到能装下当前运行的程序与数据，否则前运行的程序与数据，否则CPU执行速执行速度就会受到内存速度和容量的影响而得度就会受到内存速度和容量的影响而得不到充分发挥不到充分发挥内存内存 由存储单元（字节或字）组成的一维连续由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指令本身地址所指的、亦即程序计数器所指的存储器指的存储器分为：分为：n系统区：用于存

3、放操作系统系统区：用于存放操作系统n用户区：用于装入并存放用户程序和数据用户区：用于装入并存放用户程序和数据 二、存储管理的任务二、存储管理的任务（1）内存空间的管理、分配与回收）内存空间的管理、分配与回收n记录内存的使用情况记录内存的使用情况 设置相应的内存分配表设置相应的内存分配表 （内存分配回收的依据）（内存分配回收的依据）n 内存空间划分问题？内存空间划分问题？ 静态或动态，等长或不等长静态或动态，等长或不等长存储管理的任务（续存储管理的任务（续1）n内存分配表内存分配表n位示图：位示图：用一位（用一位（bitbit）表示一个空闲页面（）表示一个空闲页面（0 0：空闲，空闲，1 1：占

4、用）：占用）n空闲页面表：包括首页面号和页面个数，连续空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中若干的页面作为一组登记在表中n空闲块表：空闲块首址和空闲块长度，没有记空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用录的区域即为进程所占用n空闲块链表：将所有的空闲块链成一个链表空闲块链表：将所有的空闲块链成一个链表0.110.第第0页第页第1页页 第第i页页 第第n-1页页存储管理的任务（续存储管理的任务（续2）n确定分配算法确定分配算法 连续性连续性 离散性离散性 驻留性驻留性 交换性交换性 一次性一次性 多次性多次性n实施内存分配实施内存分配n内存回收

5、内存回收n内存分配：静态方式内存分配：静态方式 与与 动态方式动态方式存储管理的任务（续存储管理的任务（续3）（2）存储共享）存储共享 两个或多个进程两个或多个进程共用内存中相同区域共用内存中相同区域 目的：目的： 节省内存空间，提高内存利用率节省内存空间，提高内存利用率 实现进程通信（数据共享）实现进程通信（数据共享） 共享内容：共享内容： 代码共享，要求代码为纯代码代码共享，要求代码为纯代码 数据共享数据共享存储管理的任务（续存储管理的任务（续4）（3）存储保护）存储保护 为多个程序共享内存提供保障，使在内存中为多个程序共享内存提供保障，使在内存中的各道程序，的各道程序，只能访问它自己的区

6、域只能访问它自己的区域，避免，避免各道程序间相互干扰，特别是当一道程序发各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行生错误时，不致于影响其他程序的运行 通常由硬件完成保护功能，由软件辅助实现通常由硬件完成保护功能，由软件辅助实现存储管理的任务（续存储管理的任务（续5）保护过程保护过程-防止地址越界防止地址越界 每个进程都有自己独立的进程空间，如果一个进程每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬地址越界。即当程序要访问某个内存单元时，

7、由硬件检查是否允许，如果允许则执行，否则产生地址件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理越界中断，由操作系统进行相应处理一般由硬件提供一对寄存器：一般由硬件提供一对寄存器： 基址寄存器：存放起始地址基址寄存器：存放起始地址 限长寄存器：存放长度限长寄存器：存放长度 （或（或 上界寄存器上界寄存器/下界寄存器）下界寄存器）存储管理的任务（续存储管理的任务（续6）保护过程保护过程-防止操作越权防止操作越权 对于允许多个进程共享的存储区域，每个进程都有对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问自己的访问权限。如果一个进

8、程对共享区域的访问违反了权限规定，则发生操作越权违反了权限规定，则发生操作越权 即读写保护即读写保护 存储管理的任务（续存储管理的任务（续7）（4）内存扩充）内存扩充 通过通过虚拟存储技术虚拟存储技术实现实现 用户在编制程序时，不应该受内存容量限用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来制，所以要采用一定技术来“扩充扩充”内存的内存的容量，使用户得到比实际内存容量大的多的容量，使用户得到比实际内存容量大的多的内存空间内存空间 具体实现是在硬件支持下，软硬件相互协具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用作，将内存和外存结合起来统一使用存储管理的任务（

9、续存储管理的任务（续8）（5）地址转换）地址转换 又称地址重定位、地址映射又称地址重定位、地址映射 n逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址）n物理地址（绝对地址，实地址）物理地址（绝对地址，实地址）n地址映射地址映射存储管理的任务（续存储管理的任务（续9）n逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址） 用户的程序经过汇编或编译后形成目标代码，用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地目标代码通常采用相对地址的形式，其首地址为址为0，其余指令中的地址都相对于首地址，其余指令中的地址都相对于首地址而编址而编址 不能用逻辑地址在内存中

10、读取信息不能用逻辑地址在内存中读取信息n物理地址（绝对地址，实地址）物理地址（绝对地址，实地址） 内存中存储单元的地址，可直接寻址内存中存储单元的地址，可直接寻址存储管理的任务（续存储管理的任务（续10）n地址转换地址转换 为了保证为了保证CPU执行指令时可正确访问存储单执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称时由机器直接寻址的物理地址，这一过程称为地址映射为地址映射原因原因: 当程序装入内存时当程序装入内存时, 操作系统要为该程序分配操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址

11、与分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致到内存物理地址不一致, 而而CPU执行指令时，是按执行指令时，是按物理地址进行的，所以要进行地址转换物理地址进行的，所以要进行地址转换03456.LOAD A 200.0100200300.LOAD A 2003456逻辑地址空间逻辑地址空间110012001300物理地址空间物理地址空间200VR+1000BR存储管理的任务（续存储管理的任务（续11）存储管理的任务（续存储管理的任务（续12）n静态地址转换静态地址转换 当用户程序被装入内存时，一次性实现逻辑地址到当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，

12、以后不再转换物理地址的转换，以后不再转换 一般在装入内存时由软件完成一般在装入内存时由软件完成n动态地址转换动态地址转换 在程序运行过程中要访问数据时再进行地址变换在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）支持，软硬件结合完成） 硬件上需要一对寄存器的支持硬件上需要一对寄存器的支持三、分区存储管理方案三、分区存储管理方案 系统把内存用户区划分为若干分区，分系统把内存用户区划分为若干分区，分区大小可以

13、相等，也可以不等。一个进区大小可以相等，也可以不等。一个进程占据一个分区程占据一个分区n固定分区固定分区n可变分区可变分区1. 固定分区固定分区 预先把可分配的内存空间分割成若干个连预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区续区域，每一区域称为分区 每个分区的大小可以相同也可以不同，分每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装一个且只区大小固定不变，每个分区装一个且只能装一个作业能装一个作业 存储分配：如果有一个空闲区，则分配给存储分配：如果有一个空闲区，则分配给进程进程分区分区4分区分区3分区分区2分区分区1操作系统操作系统多个等待队列多个等待队列单个等

14、待队列单个等待队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统固定分区（续）固定分区（续）内存管理：设置内存分配表内存管理：设置内存分配表内存分配：内存分配：内存回收：内存回收：缺点：内存利用率不高缺点：内存利用率不高分区号分区号 起始地址起始地址长度长度状态状态进程名进程名2. 可变分区存储管理方案可变分区存储管理方案n基本思想基本思想内存不是预先划分好的内存不是预先划分好的作业装入时，根据作业的需求和内存空间的作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配使用情况来决定是否分配若有足够的空间，则按需要分割一部分分区若有足够的空间，则按需要分割一部分分区给该进程；否

15、则令其等待内存空间给该进程；否则令其等待内存空间可变分区存储管理方案（续可变分区存储管理方案（续1）n内存管理内存管理空闲块表空闲块表记录了空闲区起始地址和记录了空闲区起始地址和长度长度已分配区表已分配区表n内存分配内存分配 动态分配动态分配 三种分配算法：三种分配算法：首先适配、最佳适配、首先适配、最佳适配、最差适配最差适配0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址始址长度长度标志标志15K23K未分配未分配48K20K未分配未分配80K30K未分配未分配空空空空始址始址长度长度标志标志0K15KJ138K10KJ268K12KJ3110K10

16、KJ4空空空空0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址始址长度长度标志标志15K23K未分配未分配48K20K未分配未分配98K12K未分配未分配空空空空始址始址长度长度标志标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K可变分区存储管理方案（续可变分区存储管理方案（续2）n内存回收内存回收 当某一块归还后，前后空间合并，修改当某一块归还后，前后空间合并，修改内存空闲块表内存空闲块表 考虑：上邻、下邻、上下相邻、上下不相邻考虑：上邻、下邻、上下相邻、上下不相邻n“碎片碎片”问题问题

17、经过一段时间的分配回收后，内存中存经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片足分配要求。这些空闲块被称为碎片 造成存储资源的浪费造成存储资源的浪费可变分区存储管理方案（续可变分区存储管理方案（续3）n“碎片碎片”问题解决问题解决 紧凑技术：通过在内存移动程序，将所紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域有小的空闲区域合并为大的空闲区域 （又称：紧缩技术，紧致技术，浮动技（又称：紧缩技术，紧致技术，浮动技术，搬家

18、技术）术，搬家技术） 问题：开销问题：开销 大大 移动时机移动时机 ？可变分区存储管理方案（续可变分区存储管理方案（续4）n分区的保护：设置界地址寄存器分区的保护：设置界地址寄存器 保护键保护键n优点：便于动态申请内存优点：便于动态申请内存 便于共享内存便于共享内存 便于动态链接便于动态链接n缺点：缺点：碎片问题碎片问题(外碎片外碎片)，内存利用率不高，内存利用率不高 受实际内存容量限制受实际内存容量限制四、页式存储管理方案四、页式存储管理方案1. 基本思想（工作原理）基本思想（工作原理）n用户程序划分用户程序划分 把用户程序按逻辑页划分成大小相等的把用户程序按逻辑页划分成大小相等的部分，称为

19、页。从部分，称为页。从0开始编制页号，页内开始编制页号，页内地址是相对于地址是相对于0编址编址n逻辑地址逻辑地址页号页号 页内地址页内地址基本思想（续基本思想（续1）n逻辑地址逻辑地址 用户程序的划分是由系统自动完成的，对用户用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为是透明的。一般，一页的大小为2的整数次幂，的整数次幂，因此，地址的高位部分为页号，低位部分为页因此，地址的高位部分为页号，低位部分为页内地址内地址0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095基本思想（续基本思想（续2）n内存空间内存空间 按页的大小划分为

20、大小相等的区域，称按页的大小划分为大小相等的区域，称为内存块（物理页面，页框）为内存块（物理页面，页框）n内存分配内存分配 以页为单位进行分配，并按作业的页数以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上多少来分配。逻辑上相邻的页，物理上不一定相邻不一定相邻.01234560123456作业的作业的地址空间地址空间页框页框（物理块）（物理块）页页号号页页表表主存中页框主存中页框（物理块）（物理块）.2. 管理管理n页表：系统为每个进程建立一个页表，页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应页表给出逻辑页号和具体内存块号相应的关系的关系 页表放在内

21、存，属于进程的现场信息页表放在内存，属于进程的现场信息n空块管理空块管理位示图位示图0310/10/10/10/10/1017空闲块数空闲块数空块管理空块管理位示图位示图管理（续管理（续1）管理（续管理（续2）n内存的分配与回收内存的分配与回收计算一个作业所需要的总块数计算一个作业所需要的总块数N查位示图，看看是否还有查位示图，看看是否还有N个空闲块个空闲块如果有足够的空闲块，则页表长度设为如果有足够的空闲块，则页表长度设为N，可填入可填入PCB中；申请页表区，把页表始中；申请页表区，把页表始址填入址填入PCB依次分配依次分配N个空闲块，将块号和页号填入个空闲块，将块号和页号填入页表页表修改位

22、示图修改位示图3. 硬件支持硬件支持n系统设置一对寄存器：系统设置一对寄存器： 页表始址寄存器页表始址寄存器 页表长度寄存器页表长度寄存器n相联存储器相联存储器快表快表 快表表项：快表表项： 页号；内存块号；标识位；淘汰位页号；内存块号；标识位；淘汰位硬件支持（续硬件支持（续1）相联（联想）存储器（相联（联想）存储器（associative memory） TLB（Translation lookaside buffers） 介于内存与寄存器之间的存储机制，它又介于内存与寄存器之间的存储机制，它又叫快表叫快表用途：保存正在运行进程的页表的子集（部用途：保存正在运行进程的页表的子集（部分表项）分

23、表项）特点：按内容并行查找特点：按内容并行查找硬件支持（续硬件支持（续2）引入快表的目的：引入快表的目的： 为了提高地址映射速度为了提高地址映射速度快表淘汰问题？快表淘汰问题？p页表页表地址越界地址越界 l比较比较P=1pp. . .快表快表 b+页号页号p p 页内地址页内地址dPd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址地址映射机制地址映射机制五、覆盖技术与交换技术五、覆盖技术与交换技术1、为什么引入？、为什么引入？ 在多道环境下扩充内存的方法，用以解在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时决在较小的存储空间中运行

24、较大程序时遇到的矛盾遇到的矛盾n覆盖技术主要用在早期的操作系统中覆盖技术主要用在早期的操作系统中n交换技术被广泛用于小型分时系统中，交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现交换技术的发展导致了虚存技术的出现为什么引入？（续）为什么引入？（续）n交换技术与覆盖技术共同点：交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间需要执行的部分放在内存，内外存之间进行信息交换进行信息交换n不同点：如何控制交换？不同点：如何控制交换？2、覆盖技术、覆盖技术n把程序划分为若干个功能上相对独立的程序段，把

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

26、，程序员要向系统指明覆盖结构，然后由由操作程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖系统完成自动覆盖A8KE4KF10KC10KB8KD12K作业作业X的调用结构的调用结构作业作业X X的常驻区的常驻区 A A（8K8K）覆盖区覆盖区0（10K）覆盖区覆盖区1（12K） BC C D E F覆盖技术（续覆盖技术（续1）缺点：缺点： 对用户不透明，增加了用户负担对用户不透明，增加了用户负担 例子：目前这一技术用于小型系统中的例子：目前这一技术用于小型系统中的系统程序的内存管理上，系统程序的内存管理上，MS-DOS的启的启动过程中，多次使用覆盖技术；启动之动过程中，多次使用覆盖技术；

27、启动之后，用户程序区后，用户程序区TPA的高端部分与的高端部分与COMMAND.COM暂驻模块也是一种覆暂驻模块也是一种覆盖结构盖结构覆盖技术（续覆盖技术（续2）3、交换技术、交换技术n为什么引入？为什么引入？ 当内存空间紧张时，系统将内存中某些当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态种技术是进程在内存与外存之间的动态调度调度 多用于分时系统中多用于分时系统中交换技术（续交换技术（续1）n交换技术实现中的几个问题交换技术实现中的几个

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

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

30、？来位置上吗？ 受地址受地址“绑定绑定”技术的影响，即绝对地址产生技术的影响，即绝对地址产生时机的限制时机的限制 与覆盖技术相比，交换技术不要求用户给出程与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段的程序段六、虚拟存储六、虚拟存储连续性连续性 ； 离散性离散性驻留性驻留性 ； 交换性交换性一次性；一次性； 多次性多次性 以以CPU时间和外存空间换取昂贵内

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

32、程序设计系统CPUMMU内存内存磁盘磁盘控制器控制器总线总线虚拟地址虚拟地址物理地址物理地址MMU：内存管理单元：内存管理单元XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页页框页框151413121110 9 8 7 6 5 4 3

33、 2 10000000000000000111100001011000000000000011110010001110100110101 00010000000000100110000000000100110在在/不在内存不在内存页表页表虚地址虚地址8196物理地址物理地址24580概述（续概述（续1）n程序局部性原理程序局部性原理 在一段时间内一个程序的执行往往呈现出高度在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面的局部性，表现在时间与空间两方面时间局部性时间局部性 一条指令被执行了，则在不久的将来它可能再一条指令被执行了，则在不久的将来它可能再被执行被执行空间局

34、部性空间局部性 若某一存储单元被使用，则在一定时间内，与若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用该存储单元相邻的单元可能被使用n虚拟存储技术虚拟存储技术虚存：虚存：把内存与外存有机的结合起来使用，从而把内存与外存有机的结合起来使用，从而得到一个容量很大的得到一个容量很大的“内存内存”，这就是虚存，这就是虚存实现思想：实现思想：当进程运行时，先将一部分程序装入当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存令不在内存时，由系统自动完成将它们从外存调入内存工作调入内

35、存工作目的：目的： 提高内存利用率提高内存利用率概述（续概述（续2）2、虚拟页式存储管理、虚拟页式存储管理（1）基本思想）基本思想 在进程开始运行之前，不是装入全部页在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，面时，则根据某种算法淘汰某个页面，以便装入新的页面以便装入新的页面（2）页表表项设计）页表表项设计n页号、驻留位、内存块号、保护位、访问页号、驻留位、内存块号

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

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

38、块，则要淘汰某页，若该页在内存期间被修改过，则要将其写若该页在内存期间被修改过，则要将其写回外存回外存（4）页面淘汰算法）页面淘汰算法n理想淘汰算法理想淘汰算法最佳页面算法（最佳页面算法（OPT） 淘汰以后不再需要的或最远的将来才会淘汰以后不再需要的或最远的将来才会用到的页面用到的页面实现？实现？作用？作用？页面淘汰算法（续页面淘汰算法（续1）n最近未使用页面淘汰算法最近未使用页面淘汰算法（NRUNot Recently Used） 选择在最近一段时间内未使用过的一页并淘汰选择在最近一段时间内未使用过的一页并淘汰之之实现：设置两位实现：设置两位 访问位（访问位（R），）， 修改位（修改位（M）

39、 启动一个进程时，启动一个进程时，R、M置置0 R被定期清零被定期清零发生缺页中断时，操作系统检查发生缺页中断时，操作系统检查R R，M M： 第第0 0类：无访问，无修改类：无访问，无修改 第第1 1类：无访问，有修改类：无访问，有修改 第第2 2类：有访问，无修改类：有访问，无修改 第第3 3类：有访问，有修改类：有访问，有修改 操作系统随机从编号最小的非空类中选择一页操作系统随机从编号最小的非空类中选择一页淘汰淘汰页面淘汰算法（续页面淘汰算法（续2）页面淘汰算法（续页面淘汰算法（续3）n先进先出页面淘汰算法（先进先出页面淘汰算法（FIFO） 选择在内存中驻留时间最长的页并淘汰之选择在内存

40、中驻留时间最长的页并淘汰之 对照：超市撤换商品对照：超市撤换商品n第二次机会淘汰算法第二次机会淘汰算法 (SCR-Second Chance ) 按照先进先出算法选择某一页面，检查其按照先进先出算法选择某一页面，检查其访问位，如果为访问位，如果为0，则淘汰该页，如果为，则淘汰该页，如果为1，则给第二次机会，并将访问位置则给第二次机会，并将访问位置0 实现：时钟（实现：时钟（Clock）算法）算法页面淘汰算法（续页面淘汰算法（续4）n最近最久未使用页面淘汰算法最近最久未使用页面淘汰算法（LRULeast Recently Used） 选择最后一次访问时间距离当前时间最选择最后一次访问时间距离当前

41、时间最长的一页并淘汰之长的一页并淘汰之 即淘汰没有使用的时间最长的页即淘汰没有使用的时间最长的页 实现代价很高实现代价很高 时间戳或硬件方法时间戳或硬件方法页面淘汰算法（续页面淘汰算法（续5）LRU的软件解决方案：的软件解决方案：n最不经常使用（最不经常使用（NFU-Not Frequently Used） 选择访问次数最少的页面淘汰之选择访问次数最少的页面淘汰之 实现：软件计数器，一页一个，初值为实现：软件计数器，一页一个，初值为0。每。每次时钟中断时，计数器加次时钟中断时，计数器加R。发生缺页中断时，。发生缺页中断时，选择计数器值最小的一页淘汰选择计数器值最小的一页淘汰改进（模拟改进（模拟

42、LRU）：计数器在加）：计数器在加R前先右移一位前先右移一位 R位加到计数器的最左端位加到计数器的最左端称为称为老化算法老化算法 某程序在内存中分配三个页面，初始为某程序在内存中分配三个页面，初始为空，页面走向为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5，计算缺页次数，计算缺页次数页面淘汰算法（续页面淘汰算法（续6）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 共缺页中断共缺页中断

43、9次次页面淘汰算法（续页面淘汰算法（续7） 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次次页面淘汰算法（续页面淘汰算法（续8） 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 共缺页中断共

44、缺页中断7次次页面淘汰算法（续页面淘汰算法（续9） 例例2：某程序在内存中分配：某程序在内存中分配m页初始为空，页初始为空，页面走向为页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当。当m=3，m=4时缺页中断分别时缺页中断分别为多少？用为多少？用FIFO算法计算缺页次数算法计算缺页次数页面淘汰算法（续页面淘汰算法（续10）m=3时，缺页中断时，缺页中断9次次m=4时，缺页中断时，缺页中断10次次注：注：FIFO页面淘汰算法会产生异常现页面淘汰算法会产生异常现象（象（Belady现象），即：当分配给现象），即：当分配给进程的物理页面数增加时，缺页次进程的物理页面数增加时，缺页次数反

45、而增加数反而增加页面淘汰算法（续页面淘汰算法（续11）(1) 分配给进程的物理页面数分配给进程的物理页面数(2) 页面本身的大小页面本身的大小(3) 程序的编制方法程序的编制方法(4) 页面淘汰算法页面淘汰算法（5）影响缺页次数的因素）影响缺页次数的因素例子例子3：内存分配一页，初始时第一页在内存；页：内存分配一页，初始时第一页在内存；页面大小为面大小为128个整数；矩阵个整数；矩阵A128X128按行存放按行存放程序编制方法程序编制方法1： For j:=1 to 128 For i:=1 to 128 Ai,j:=0;程序编制方法程序编制方法2： For i:=1 to 128 For j

46、:=1 to 128 Ai,j:=0;影响缺页次数的因素（续影响缺页次数的因素（续1）（1）颠簸（抖动）颠簸（抖动） 在虚存中，页面在内存与外存之间频繁调度，在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖至导致系统崩溃。这种现象称为颠簸或抖动动原因：原因：页面淘汰算法不合理页面淘汰算法不合理分配给进程的物理页面数太少分配给进程的物理页面数太少3、性能问题、性能问题 基本思想：根据程序的局部性原理，一基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁装入内存，则进程在运行过程中将频繁发生中断发生中断