第三章存储器管理操作系统课件

1、第第3 3章章 存储器管理存储器管理CPU内存I/O系统设备内存是现代计算机系统的中心，内存是现代计算机系统的中心，是是CPU能直接存取指令能直接存取指令和数据的存储器，如上图所示，和数据的存储器，如上图所示，CPU和和I/O 都需要和内都需要和内存打交道。存打交道。CPU根据程序计数器根据程序计数器PC的值从内存中提取指令，这些的值从内存中提取指令，这些指令可能会引起进一步的对特定内存地址的读取和写入。指令可能会引起进一步的对特定内存地址的读取和写入。例如，例如，一个典型的指令执行周期是：一个典型的指令执行周期是：首先从内存中读取首先从内存中读取指令，接着该指令被解码，且可能需要从内存中读取

2、操指令，接着该指令被解码，且可能需要从内存中读取操作数，在指令对操作数执行后，其执行结果又被写回到作数，在指令对操作数执行后，其执行结果又被写回到内存中。内存中。内存在计算机系统中的地位内存在计算机系统中的地位：（补充）（补充）第第3 3章章 存储器管理存储器管理n程序和数据可以长期保存在容量最大的外存程序和数据可以长期保存在容量最大的外存中，但是，他们只有中，但是，他们只有。为了改善。为了改善 CPU的利用率和提供程序的利用率和提供程序的响应速度，计算机必须在内存中保留多个进的响应速度，计算机必须在内存中保留多个进程，程，也也是本章介绍的主要内容。是本章介绍的主要内容。第第3 3章章 存储器

3、管理存储器管理n3.1 存储存储管理概述管理概述（次重点）（次重点）n3.2 分区存储管理分区存储管理（次重点）（次重点）n3.3 页式存储管理页式存储管理（重点）（重点）n3.4 段式存储管理段式存储管理（非重点）（非重点）n3.5 段页式存储管理段页式存储管理（自学）（自学）3.1 3.1 存储管理概念存储管理概念1. 存储体系存储体系（补充）（补充）三级存储器三级存储器内存内存( (主存主存) )：RAM、ROM外存外存( (辅存辅存) )：磁盘磁盘、磁带、光盘等、磁带、光盘等高速缓冲存储器高速缓冲存储器(cache) OS负责协调各存储器的使用，负责协调各存储器的使用，OS本身的程序和

4、数据与其他本身的程序和数据与其他程序一起共享主存，为安全起见，多道程序系统常由程序一起共享主存，为安全起见，多道程序系统常由OS把内存把内存初始化为系统区和用户区两大部分：初始化为系统区和用户区两大部分： 内存内存 系统区系统区用户区用户区，为多道程序并发执行提供存储基础，为多道程序并发执行提供存储基础 n能够解决能够解决的问题的问题n保证保证n实现存储保护与安全实现存储保护与安全n实现共享与通信实现共享与通信n了解有关资源的使用状况了解有关资源的使用状况3.1 3.1 存储管理概念存储管理概念实际存储单元在内存实际存储单元在内存中的物理位置中的物理位置 内存中实际的物理地址的集合内存中实际的

5、物理地址的集合（范围）。（范围）。用户程序中使用的地用户程序中使用的地址（一般从址（一般从“0”开始的）开始的）用户程序中所使用的逻辑地址用户程序中所使用的逻辑地址的集合（范围）。的集合（范围）。 3.1 存储管理的概念存储管理的概念3.1 存储管理的概念存储管理的概念n动态重定位：动态重定位： OS将程序装入内存以后，将程序装入内存以后，把目标程序中的逻辑地址转换为物理地址，把目标程序中的逻辑地址转换为物理地址，n优点：优点： 可以将程序分配到不连续的存储区域中可以将程序分配到不连续的存储区域中 有利于实现程序段的共享有利于实现程序段的共享缺点：缺点： 需要附加的硬件支持需要附加的硬件支持（

6、重定位寄存器存放（重定位寄存器存放程序程序/数据数据在内在内存中起始地址）存中起始地址） 相应的软件算法也比较复杂相应的软件算法也比较复杂操作数和指令地址并操作数和指令地址并不在程序装入时确定不在程序装入时确定多用户程序只需知道被共享程序的逻辑地址多用户程序只需知道被共享程序的逻辑地址3.1 存储管理的概念存储管理的概念 区号区号起始地址起始地址长度长度(KB)状态状态1aS1空闲空闲2bS2已分配已分配3cS3空闲空闲固定分区内存分配表固定分区内存分配表指为了保证指为了保证CPU执行指令时可正确访问存执行指令时可正确访问存储单元，需将用户程序中的储单元，需将用户程序中的逻辑地址逻辑地址（相对

7、地（相对地址，虚地址）转换为运行时由机器直接寻址的址，虚地址）转换为运行时由机器直接寻址的物理地址物理地址（绝对地址，实地址）的过程（绝对地址，实地址）的过程。 内存保护限定程序只能访问自己所在的内存区，内存保护限定程序只能访问自己所在的内存区，保保护了护了OS和其他程序。一般来说，对内存区域的保护和其他程序。一般来说，对内存区域的保护可采取如下措施：可采取如下措施：n定义：定义：当用户运行比内存大的程序时采取软件的当用户运行比内存大的程序时采取软件的方法来对内存进行逻辑扩充，达到方法来对内存进行逻辑扩充，达到常用常用覆盖覆盖、交换交换和和虚拟存储虚拟存储技术。技术。在硬件的配合下，将部分外存

8、空间虚在硬件的配合下，将部分外存空间虚拟为内存空间，并将内存和外存有机结合起来，拟为内存空间，并将内存和外存有机结合起来，得到一个得到一个、价、价格十分便宜的虚拟存储系统。格十分便宜的虚拟存储系统。n贡献：贡献：内存扩充技术打破了进程必须内存扩充技术打破了进程必须内内存才能运行的惯例。存才能运行的惯例。（从逻辑上扩充内存容量）（从逻辑上扩充内存容量）具有具有功能，能功能，能的一种存储器系统。其逻辑容量由的一种存储器系统。其逻辑容量由所决定，运行速度接近内存，每位成本接近外存。所决定，运行速度接近内存，每位成本接近外存。进程开始运行时只需要进程开始运行时只需要装入内存即可，当要访问装入内存即可，

9、当要访问自己地址空间中的内容不在内存时，将产生自己地址空间中的内容不在内存时，将产生，由服务程，由服务程序把所缺的内容序把所缺的内容，若此时内存没有空间，则用，若此时内存没有空间，则用，如果这部分信息，如果这部分信息来自该进程所在的内存区，则换入时相当于使用了自动覆盖来自该进程所在的内存区，则换入时相当于使用了自动覆盖技术。技术。虚拟存储虚拟存储存储管理策略分类存储管理策略分类n存储管理策略存储管理策略：n实存模式实存模式要求进程运行时要求进程运行时全部在全部在内存内存n虚存模式虚存模式只要求进程运行时只要求进程运行时部分在部分在内存即可内存即可存储管理分类存储管理分类按照对内存的划分使用策略

10、不同来分类，按照对内存的划分使用策略不同来分类，可分为：可分为：3.2 3.2 分区式存储管理分区式存储管理 实存实存管理技术（管理技术（进程运行全部装入内存进程运行全部装入内存） 系统给每个作业或进程分配一个系统给每个作业或进程分配一个。n单一连续区分配（静态分区技术）单一连续区分配（静态分区技术）n可变分区分配（动态分区技术）可变分区分配（动态分区技术）1. 单一连续区存储管理单一连续区存储管理 系统静态地将系统静态地将，一个供操作系统使用，一个供操作系统使用，一个供用户使用，且每次只能装入一个作业或进程，主要一个供用户使用，且每次只能装入一个作业或进程，主要用于早期单道程序系统和后来的用

11、于早期单道程序系统和后来的PC操作系统。操作系统。操作系统操作系统用户程序用户程序0 xFFF.0系统预先把可分配的内存空间分割成若干个连续区系统预先把可分配的内存空间分割成若干个连续区域，域，每一区域称为分区，每个分区的大小可以相同也每一区域称为分区，每个分区的大小可以相同也可以不同，可以不同，一旦划分好分区之后一旦划分好分区之后，这种分区法属于一种这种分区法属于一种静态分区静态分区。 或进程。等待进入或进程。等待进入内存的作业排成一个作业队列，当内存中有空闲的分内存的作业排成一个作业队列，当内存中有空闲的分区时，依次从作业队列中选择一个能装入该分区的作区时，依次从作业队列中选择一个能装入该

12、分区的作业。当所有的分区都已装有作业，则其他的作业暂时业。当所有的分区都已装有作业，则其他的作业暂时不能再装入。不能再装入。已经装入内存的作业在获得处理机运行时，已经装入内存的作业在获得处理机运行时，要要3.2.1 3.2.1 固定分区存储管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用区号区号起始地址起始地址长度长度(KB)状态状态1aS102bS2job23cS30设置一张设置一张“内存分配表内存分配表”来管理内存空间的使用。来管理内存空间的使用。OS0abcd空空 job2空空 内存分配表内存分配表内存内存3.2.1 3.2.1 固定分区存储

13、管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用：3.2.1 3.2.1 固定分区存储管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用重新置成重新置成0。3.2.1 3.2.1 固定分区存储管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用固定分区管理，分区固定且只能装入一个作业固定分区管理，分区固定且只能装入一个作业，作业在执行过程中不会改变存放区域。，作业在执行过程中不会改变存放区域。u存储保护采用存储保护采用“”方法方法当某作业占用处理机时，进程调度程序

14、必须把当某作业占用处理机时，进程调度程序必须把该作业所在分区下限地址该作业所在分区下限地址（最小地址）（最小地址）和上限和上限地址地址（最大地址）（最大地址）存入处理机的下限寄存器和存入处理机的下限寄存器和上限寄存器，当上限寄存器，当下限地址下限地址物理地址物理地址上限地址上限地址时访问物理主存，时访问物理主存，否则形成否则形成3.2.1 3.2.1 固定分区存储管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用3.2.1 3.2.1 固定分区存储管理固定分区存储管理 单一连续区在多道程序系统中的直接应用单一连续区在多道程序系统中的直接应用v内存空间

15、的利用率：内存空间的利用率：“内碎内碎片片”。特点：实现简单，可用于多道程序系统，但内特点：实现简单，可用于多道程序系统，但内存利用率低，作业大小受限。存利用率低，作业大小受限。v基本思想基本思想3.2.2 可变分区存储管理可变分区存储管理n当某作业执行结束后，它所占的分区必须被当某作业执行结束后，它所占的分区必须被3.2.2 可变分区存储管理可变分区存储管理3.2.2 可变分区存储管理可变分区存储管理v内存空间的分配内存空间的分配内存分配表用内存分配表用组成，组成，“”和和“”。查空闲分区表，按照查空闲分区表，按照进行分配后，对空闲分区表进行修改。空闲分区表仅当被进行分配后，对空闲分区表进行

16、修改。空闲分区表仅当被选中分区的尺寸与作业需求相等时才将相应表目状态置成选中分区的尺寸与作业需求相等时才将相应表目状态置成“空空”，根据空闲分区表把已分配分区表根据空闲分区表把已分配分区表中的一个空表目改为一个标志为某作业名的相应表目，并中的一个空表目改为一个标志为某作业名的相应表目，并调整起始地址和长度。（调整起始地址和长度。（3.2.2 可变分区存储管理可变分区存储管理区号区号起始地址起始地址长度长度(KB)标志位标志位1aS1空空2bS2job23cS3空空OS0abcd空空 job2空空 已分配分区表已分配分区表内存内存区号区号起始地址起始地址长度长度(KB)标志位标志位1aS1未分配

17、未分配2bS2空空3cS3未分配未分配空闲分区表空闲分区表3.2.2 可变分区存储管理可变分区存储管理3.2.2 可变分区存储管理可变分区存储管理 空闲分区表的表目按相应分区的空闲分区表的表目按相应分区的以以，分配时，顺序查找空闲分区表，找到第一个能满足作，分配时，顺序查找空闲分区表，找到第一个能满足作业要求的空闲分区，若该空闲分区比作业长度大，则分割业要求的空闲分区，若该空闲分区比作业长度大，则分割这个空闲分区，一部分分配给作业，另一部分仍为空闲分这个空闲分区，一部分分配给作业，另一部分仍为空闲分区；若该空闲分区长度与作业大小相等，则直接把它分给区；若该空闲分区长度与作业大小相等，则直接把它

18、分给作业。作业。（因为每一次都从低地址搜索）（因为每一次都从低地址搜索）3.2.2 可变分区存储管理可变分区存储管理空闲分区表的表目按相应空闲分区表的表目按相应分区的大小分区的大小。找到的第一个能满足作业要求的空闲分区一定是个最找到的第一个能满足作业要求的空闲分区一定是个最小的空闲分区，即其长度最接近或最适合作业要求的小的空闲分区，即其长度最接近或最适合作业要求的空闲分区，这样可保证不去分割一个更大的区域，以空闲分区，这样可保证不去分割一个更大的区域，以利于以后到来的大作业。利于以后到来的大作业。3.2.2 可变分区存储管理可变分区存储管理空闲分区表的表目按相应分区的空闲分区表的表目按相应分区

19、的。找到的第一个能满足作业要求的空闲分区一定是。找到的第一个能满足作业要求的空闲分区一定是个个，即其长度与作业要求，即其长度与作业要求，这样可保证每次分割后的剩余部分不至于太小，仍可这样可保证每次分割后的剩余部分不至于太小，仍可被分配使用，被分配使用，例例3.1 分区存储管理算法题分区存储管理算法题n采用可变分区方式管理内存时，若内存中按采用可变分区方式管理内存时，若内存中按依次有五个大小依次为依次有五个大小依次为15k、37k、14k、220k和和103k的的。现有五个作业。现有五个作业Ja、Jb、Jc、Jd和和Je，它它们各需要内存们各需要内存12k、14k、103k、36k和和190k。

20、问：。问：如果采用最先适应分配算法，能将这五个作业按如果采用最先适应分配算法，能将这五个作业按Ja Je的次序全部装入内存吗？用什么分配算法装入的次序全部装入内存吗？用什么分配算法装入这这5个作业可使内存的利用率最高？个作业可使内存的利用率最高？解答：解答： 按最先适应分配算法，不能将这五个作业按按最先适应分配算法，不能将这五个作业按Ja Je的次序全部装入内存。因为内存中前两个原先的空闲分区能的次序全部装入内存。因为内存中前两个原先的空闲分区能依次装入依次装入Ja(15k)和和Jb(37k)，Jc(220K)之后，第四个分区还剩之后，第四个分区还剩117K , Jd (117K)之后，第四个

21、分区还剩之后，第四个分区还剩81K, Je190K的任务的任务已经没有分区能够满足了。已经没有分区能够满足了。 用最佳适应分配算法装入这用最佳适应分配算法装入这5个作业，可使内存的利个作业，可使内存的利用率最高。此时，原先的用率最高。此时，原先的5个空闲区依次装入了个空闲区依次装入了5个作业，它个作业，它们是：们是：Jb(15k)，Jd(37k)，Ja(14k)，Je(220k)和和Jc(103k)。15k37k14k220k103k3.2.2 可变分区存储管理可变分区存储管理v内存空间的释放内存空间的释放释放后释放后将相应表目的状态置成将相应表目的状态置成“空空”；3.2.2 可变分区存储管

22、理可变分区存储管理n特点特点克服了固定分区管理的克服了固定分区管理的“内碎片内碎片”问题，但问题，但产生了产生了“外碎片外碎片”。怎样解决怎样解决碎片问题碎片问题呢？呢？改进内存释放算法改进内存释放算法在内存中移动程序在内存中移动程序3.2.2 可变分区存储管理可变分区存储管理移动技术和内存紧缩移动技术和内存紧缩移动技术和内存紧缩移动技术和内存紧缩采用采用装入程序装入程序基址基址-限长寄存器限长寄存器地址转换与存储保护地址转换与存储保护作业执行过程中，处理机每执行一条指令都要取出该指作业执行过程中，处理机每执行一条指令都要取出该指令的逻辑地址；当令的逻辑地址；当小于小于限长寄存器的值时，则把限

23、长寄存器的值时，则把逻辑地址与逻辑地址与的值相加得到的值相加得到。当当限长寄存器的值时，表示欲访问限长寄存器的值时，表示欲访问的主存地址超出了所分配的分区范围，形成的主存地址超出了所分配的分区范围，形成“地址越界地址越界”地址转换与存储保护地址转换与存储保护3.2 分区存储管理分区存储管理限长基址寄存器保护法限长基址寄存器保护法3.2 分区存储管理分区存储管理n主要在于连续分配的限制，即它要求每主要在于连续分配的限制，即它要求每个作业在内存必须占用一个连续的区域。个作业在内存必须占用一个连续的区域。3.3 3.3 页式存储管理页式存储管理 不用不用“紧凑紧凑”也能消除碎片的一种也能消除碎片的一

24、种技术技术由于要求每个作业在内存必须占用由于要求每个作业在内存必须占用一个连续的区域，因此最大缺点是一个连续的区域，因此最大缺点是结合固定分区和离散存储的思想产生的结合固定分区和离散存储的思想产生的允许一个进程在内存中占有允许一个进程在内存中占有因此因此基本解决了碎片问题基本解决了碎片问题，是目前内存，是目前内存利用率最高的一种存储管理方式。分为：利用率最高的一种存储管理方式。分为：3.3 页式存储管理页式存储管理n基本原理基本原理将将分成大小相分成大小相同的若干个存储块，从同的若干个存储块，从“0”开始编号开始编号将一个进程的将一个进程的分分成与物理块成与物理块的片，从的片，从“0”开始编号

25、开始编号n以页为单位分配内存，一页分配一个块，每以页为单位分配内存，一页分配一个块，每页可以不连续页可以不连续地址结构地址结构 页号（页号（P）：）：指明该地址在指明该地址在的哪的哪一页一页 页内偏移量（页内偏移量（D）：）：表明该地址在该页内的相对表明该地址在该页内的相对地址。地址。 页号和页内偏移量的计算页号和页内偏移量的计算 页号：页号：P=INTA/L 页内偏移量：页内偏移量：D=A MOD L A：逻辑地址：逻辑地址 L：页面大小：页面大小3.3.1 实页式存储管理实页式存储管理n举例举例n设页面大小为设页面大小为L=1 kB，逻辑地址，逻辑地址A=2170B，计，计算逻辑地址对应的

26、页号和页内偏移量算逻辑地址对应的页号和页内偏移量 n页表页表n系统为每一个进程建立一张系统为每一个进程建立一张 页表，存放在内存。页表，存放在内存。n每一个页表项记录了相应页每一个页表项记录了相应页 在内存中对应的物理块号在内存中对应的物理块号3.3.1 实页式存储管理实页式存储管理3.3.1 实页式存储管理实页式存储管理n举例：举例：n一逻辑地址为一逻辑地址为3120，页面大小，页面大小L1kB，页，页表如右图所示，求其对应的表如右图所示，求其对应的 物理地址物理地址=7*1024+48 =7216 逻辑地址逻辑地址1000对应的物理地址对应的物理地址 逻辑地址逻辑地址5670对应的物理地址

27、对应的物理地址页号块号011425374103.3.1 实页式存储管理实页式存储管理地址转换地址转换3.3.1 实页式存储管理实页式存储管理n具有快表的具有快表的地址变换地址变换n联想寄存器（快表）的引入联想寄存器（快表）的引入n地址变换过程地址变换过程 地址变换机构同时查找快表和页表，如果在快表地址变换机构同时查找快表和页表，如果在快表中有与之相匹配的页号，可中有与之相匹配的页号，可 如果在快表中没有找到与之对应的页表项，继续如果在快表中没有找到与之对应的页表项，继续访问主存中的页表，从页表中读出与页号对应的访问主存中的页表，从页表中读出与页号对应的物理块号，同时将此页表项存入快表中的寄存器

28、物理块号，同时将此页表项存入快表中的寄存器单元中单元中 如果快表已满，则操作系统必须找到一个认为不如果快表已满，则操作系统必须找到一个认为不再需要的页表项将之移出再需要的页表项将之移出 3.3.1 实页式存储管理实页式存储管理3.3.1 实页式存储管理实页式存储管理n页的分配与回收页的分配与回收3.3.1 实页式存储管理实页式存储管理0310/10/10/10/10/1017空闲块数空闲块数位示图位示图主存储器可分配区域被分成主存储器可分配区域被分成256块，则需要一个块，则需要一个33个字节的位示图来作为个字节的位示图来作为主存分配表。其中主存分配表。其中8个字长为个字长为32位的字来描述全

29、部位的字来描述全部256个块的分配使用情况，个块的分配使用情况，另有一个字节记录当前剩余的空闲块数。如下图：另有一个字节记录当前剩余的空闲块数。如下图：3.3.1 实页式存储管理实页式存储管理0310/10/10/10/10/1017空闲块数空闲块数需进行需进行的转换：的转换：=字号字号*字长字长+位号位号(255=732+31)3.3.1 实页式存储管理实页式存储管理1 初始化时把操作系统已经占用块对应的位置成初始化时把操作系统已经占用块对应的位置成1，其余位均置成其余位均置成0，剩余空闲块为可分配空闲块总数。，剩余空闲块为可分配空闲块总数。2 使用时，先查看空闲块数是否满足作业要求，若不使

30、用时，先查看空闲块数是否满足作业要求，若不满足不进行分配，否则找出一些值为满足不进行分配，否则找出一些值为0的位将其置的位将其置1，从空闲块中减去本次占用块数，按公式转换：从空闲块中减去本次占用块数，按公式转换：3 执行结束后，应执行结束后，应，根据归还的块号，按公式：，根据归还的块号，按公式：字号字号=块号块号div字长字长（7=255/32）位号位号=块号块号mod字长字长(31=255%32)3.3.1 实页式存储管理实页式存储管理ed1ed2ed40data1data22122606162进程进程1页表页表ed1ed2ed40data1data2进程进程23132707172页表页表.

31、OSed1ed2ed40data1data2data1data2011125051525354主存主存3.3.1 实页式存储管理实页式存储管理n只有纯的页面只有纯的页面才能共享才能共享n一般分页常采用一般分页常采用技术（要求有目标技术（要求有目标模块拷贝）因此无法实现共享模块拷贝）因此无法实现共享n页块按地址空间划分，页内信息不完整，页块按地址空间划分，页内信息不完整，3.3.1 实页式存储管理实页式存储管理n越界检查越界检查3.3.1 实页式存储管理实页式存储管理01111141102910036101页号页号块号块号可读可读可写可写可执行可执行图图3.1 3.1 带有存取控制字段的页表带有

32、存取控制字段的页表存取控制字段存取控制字段3.3.1 实页式存储管理实页式存储管理3.3.2 3.3.2 虚拟页式存储管理虚拟页式存储管理n虚拟页式存储管理的引入：虚拟页式存储管理的引入： 当一个进程的地址空间大于整个内存空当一个进程的地址空间大于整个内存空间时，若采用实分页式存储管理，那么间时，若采用实分页式存储管理，那么1. 虚拟存储器的概念虚拟存储器的概念n虚拟存储器是虚拟存储器是为了为了逻辑扩充内存，以解决逻辑扩充内存，以解决而而引入引入的，是一种以的，是一种以（是（是OS中的资源转换技术），也是迄今为止逻辑中的资源转换技术），也是迄今为止逻辑扩充内存程度最彻底的技术。扩充内存程度最彻

33、底的技术。n虚拟存储器是在虚拟存储器是在1961年由英国曼彻斯特大学的年由英国曼彻斯特大学的Fotheringham提出，并在该校的提出，并在该校的atlas机器上实现的一种存储技术。从机器上实现的一种存储技术。从1970年后被广泛应用，今天的年后被广泛应用，今天的OS普遍采用这一技术管理内存。普遍采用这一技术管理内存。n虚拟存储器的基本思想虚拟存储器的基本思想是：是：OS把程序当前使用的部分保留在内存，而把把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间其它部分保存在磁盘上，并在需要时在内存和磁盘之间1. 虚拟存储器的概念（续虚拟存储器的概念（续1）196

34、8年美国年美国MIT的的Denning提出程序局部性原理是对提出程序局部性原理是对虚拟存储器有力的理论支持。虚拟存储器有力的理论支持。 程序在执行时呈现出高度的局部性特征，即在一较短程序在执行时呈现出高度的局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。程序执行的它所访问的存储空间也局限于某个区域。程序执行的局部性表现在时间与空间两个方面：局部性表现在时间与空间两个方面： 如果某个参数被引用，那它不久将再次被引用。程序如果某个参数被引用，那它不久将再次被引用。程序往往在短时间内多次引用同一个参

35、数。往往在短时间内多次引用同一个参数。 若某一存储单元被访问，则在不久之后，与该存储单若某一存储单元被访问，则在不久之后，与该存储单元相邻的单元也可能被访问。元相邻的单元也可能被访问。1. 虚拟存储器的概念（续虚拟存储器的概念（续1） 按照局部性原理，一个进程运行时，可不必将其按照局部性原理，一个进程运行时，可不必将其全部装载到内存中，只需把全部装载到内存中，只需把随着进程运行的不断随着进程运行的不断推进，其中部分程序和数据可随时装入，这样做可实推进，其中部分程序和数据可随时装入，这样做可实现现的设想。的设想。 1. 虚拟存储器的概念（续虚拟存储器的概念（续2）n虚拟存储器定义虚拟存储器定义（

36、至今没有统一定义，我认为以下前（至今没有统一定义，我认为以下前3种比较重要）种比较重要）n虚假的存储器；虚假的存储器；n进程能够访问的虚拟地址空间；进程能够访问的虚拟地址空间；n虚拟存储器是把虚拟存储器是把内存与外存这两级存储器并用做一级存储器内存与外存这两级存储器并用做一级存储器的结果，是逻辑扩充内存的最佳手段的结果，是逻辑扩充内存的最佳手段n虚拟存储器的容量虚拟存储器的容量取决于取决于，但实际最，但实际最大尺寸取决于系统的地址结构（大尺寸取决于系统的地址结构（）基本思想基本思想2. 两个问题两个问题 1）进程运行时，）进程运行时，那那么在内存容量和进程数量确定的前提下，么在内存容量和进程数

37、量确定的前提下，应当如何把内存分配给诸进程呢？应当如何把内存分配给诸进程呢？ 2）当进程访问的页不在内存时将产生）当进程访问的页不在内存时将产生缺页缺页中断中断，由服务程序把所缺页装入内存。如，由服务程序把所缺页装入内存。如何为所缺页面分配内存？何为所缺页面分配内存？2. 主存页面分配策略主存页面分配策略问题问题1：既然进程开始运行时只需要一部分内存，：既然进程开始运行时只需要一部分内存，那么在内存容量和进程数量确定的前提下，应当那么在内存容量和进程数量确定的前提下，应当如何把内存物理块分配给诸进程？如何把内存物理块分配给诸进程？将内存所有块等分给进入系统中将内存所有块等分给进入系统中的进程。

38、的进程。2）按进程）按进程比例分配。比例分配。3）按进程）按进程分配。分配。4）按进程）按进程分配。分配。2. 主存页面分配策略主存页面分配策略问题问题2：进程运行过程中访问不在内存的页面发生：进程运行过程中访问不在内存的页面发生缺页中断时，如何为所缺页面分配内存？缺页中断时，如何为所缺页面分配内存？进程在内存占据进程在内存占据，置换时总是从这一部，置换时总是从这一部分区域中找淘汰对象。分区域中找淘汰对象。开始时为进程分配一定数目的内存块，此后当进程访问开始时为进程分配一定数目的内存块，此后当进程访问所缺页面时，若该进程所占内存已经装满页面，则只能从中所缺页面时，若该进程所占内存已经装满页面，

39、则只能从中选择一页换出，然后再调入所缺的页面，以保证分配给该进选择一页换出，然后再调入所缺的页面，以保证分配给该进程的程的只能从当前进程所占的内存空间中找淘汰对象只能从当前进程所占的内存空间中找淘汰对象 ，因，因此一个进程缺页此一个进程缺页不会影响其他进程。不会影响其他进程。2. 主存页面分配策略主存页面分配策略 进程在内存占据的空间进程在内存占据的空间，一般是由系统定时，一般是由系统定时地根据进程访问的缺页率的高低而动态调整，置换时从地根据进程访问的缺页率的高低而动态调整，置换时从用户进程所占的内存空间中找淘汰对象用户进程所占的内存空间中找淘汰对象。一个进程缺页会影响其他进程。一个进程缺页会

40、影响其他进程。2. 主存页面分配策略主存页面分配策略3. 页面调入时机页面调入时机n请求调页策略请求调页策略（demand paging）n进程运行过程中，进程访问不在内存的页面，引进程运行过程中，进程访问不在内存的页面，引发发，靠缺页中断程序装入所需访问的不，靠缺页中断程序装入所需访问的不在内存的页面。在内存的页面。n实现简单，用得广，但费时。实现简单，用得广，但费时。n预调页策略预调页策略（prepaging）n一个页面被访问前已预先装入内存，以减少今后一个页面被访问前已预先装入内存，以减少今后的缺页率。主要用于的缺页率。主要用于n有的系统结合请求调入使用，即每次缺页时装入有的系统结合请求

41、调入使用，即每次缺页时装入多个页面。多个页面。虚分页所需的硬件支持（补充）虚分页所需的硬件支持（补充）n页表机制页表机制n页表基本作用是将用户地址空间中的页表基本作用是将用户地址空间中的转换为内存转换为内存空间中的空间中的由于引入虚拟存储技术的分页存储管由于引入虚拟存储技术的分页存储管理模式只需将应用程序的理模式只需将应用程序的，另一部分仍在，另一部分仍在磁盘上，需在页表中增加若干项，供程序换进（出）做参磁盘上，需在页表中增加若干项，供程序换进（出）做参考。考。n标志位（状态位）标志位（状态位）P:指示该页是否调入内存指示该页是否调入内存n访问字段访问字段A：记录本页在一段时间内被访问的次数记

42、录本页在一段时间内被访问的次数n修改位修改位M：该页在调入内存后是否被修改过，若修改还需该页在调入内存后是否被修改过，若修改还需写回外存。写回外存。n外存地址：外存地址：指出该页在外存上的地址指出该页在外存上的地址页号页号物理块号物理块号虚分页所需的硬件支持虚分页所需的硬件支持n缺页中断（缺页中断（Page Fault）机构）机构n在地址映射过程中，所访问的页不在内存时，便产在地址映射过程中，所访问的页不在内存时，便产生一缺页中断；生一缺页中断；OS接到此中断信号后，就调出缺页接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的中断处理程序，根据页表中给出的外存地址外存地址，将该，将该页

43、页调入内存调入内存，更新页表更新页表，完成重定位，使进程继续，完成重定位，使进程继续运行下去。运行下去。3.3 虚分页式存储管理虚分页式存储管理n硬件地址转换机构根据页表（控制）寄存器找到页硬件地址转换机构根据页表（控制）寄存器找到页表首地址表首地址n再由页表首址找到页表中要访问的页面号再由页表首址找到页表中要访问的页面号Xn查找页表对应页号查找页表对应页号X的标志位的标志位n当当X页标志为页标志为0时，产生一缺页中断时，产生一缺页中断n操作系统中断处理程序在主存中找空闲页（操作系统中断处理程序在主存中找空闲页（需置换需置换的页的页）n将辅存地址将辅存地址Y指向的页面指向的页面XX插入主存插入

44、主存n修改标志位为修改标志位为1和填写物理块号，并修改访问位为和填写物理块号，并修改访问位为1，若是写指令，还要置修改位为若是写指令，还要置修改位为1 （需写会到内存）（需写会到内存）3.3 页式存储管理页式存储管理页表地址页表地址访问访问X页面页面页表长度页表长度页号页号 标志标志页框页框访问访问修改修改辅存地址辅存地址.XY.0缺页中断处理程序缺页中断处理程序Y0页面页面控制寄存器控制寄存器辅存作业地址空间辅存作业地址空间辅存（磁盘）辅存（磁盘）存储器示意图存储器示意图页表页表页面调入过程页面调入过程1XX缺页中断XX虚分页所需的硬件支持（续虚分页所需的硬件支持（续1）n借助快表借助快表地

45、址变换过程与实分页类似，但地址变换过程与实分页类似，但n首先根据页号检索首先根据页号检索，若找到，修改页表项中，若找到，修改页表项中的的标志标志（表示该页已调入内存），（表示该页已调入内存），然后利用页然后利用页表项中给出的表项中给出的物理块号物理块号以及逻辑地址中的以及逻辑地址中的页内地页内地址址，形成物理地址。，形成物理地址。n如果在快表中未找到相应的页表项，则检索如果在快表中未找到相应的页表项，则检索，察看页表项中的状态位，若该页已经，察看页表项中的状态位，若该页已经调入内存，则形成物理地址，并调入内存，则形成物理地址，并更新快表更新快表，当快，当快表满时，应淘汰一个页表项；若该页尚未调

46、入内表满时，应淘汰一个页表项；若该页尚未调入内存，则存，则产生缺页中断产生缺页中断，请求，请求OSOS把该页调入内存，把该页调入内存，然后再完成重定位。然后再完成重定位。3.3 3.3 页式存储管理页式存储管理n抖动（抖动（thrashingthrashing）：）：又称为颠簸，指由又称为颠簸，指由于缺页中断频繁，于缺页中断频繁，CPUCPU忙于在内外存之间忙于在内外存之间调页，很少执行有效的任务调页，很少执行有效的任务n缺页率缺页率n定义定义 假定作业共有假定作业共有n n页，而系统分配的主存物理块数目为页，而系统分配的主存物理块数目为m m，且且1mn1mn。如果作业在运行过程中成功访问主

47、存的次数为。如果作业在运行过程中成功访问主存的次数为S S（所访问页在主存中），（所访问页在主存中），不成功不成功的访问次数为的访问次数为F F，总访总访问次数问次数为为A A，那么缺页率为，那么缺页率为f=F/A f=F/A 4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法 Page Replacement Algorithms （淘汰（淘汰 / 置换）置换）n最佳页面置换算法（最佳页面置换算法（OPTOPT） 由由Belady于于1966年提出的一种理论上的算法年提出的一种理论上的算法 淘汰淘汰，或是在，或是在最长时间内不被访问的页最长时间内不被访问的页面面 是一种理想化的算法

48、，具有最好的性能，但是在实是一种理想化的算法，具有最好的性能，但是在实际上难于实现际上难于实现4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法最佳置换算法页面淘汰序列最佳置换算法页面淘汰序列次数次数 t访问页面访问页面P=物理块物理块M=3失败失败F=012345678910 11 1244444443444111111222223333343333355555555F=7缺页率缺页率f=7/12=58%21434. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法 先进先出页面替换算法（先进先出页面替换算法（FIFOFIFO） 最早的一种页面置换算法，实现起来比较容易最早的

49、一种页面置换算法，实现起来比较容易 淘汰在内存中驻留时间最久的页面淘汰在内存中驻留时间最久的页面 在在分页分页式式虚拟存储器虚拟存储器管理中，发生缺页时的置换算法管理中，发生缺页时的置换算法采用采用FIFO算法时，如果对一个进程未分配它所要求的算法时，如果对一个进程未分配它所要求的有时就会出现分配的有时就会出现分配的4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法页块数为页块数为3的先进先出置换算法页面淘汰序列的先进先出置换算法页面淘汰序列次数次数 t页面踪迹页面踪迹P=页框页框M=3失败失败F=012345678910 11 124441122333554412335551214

50、41233335225521344434 F=9f=9/12=75% 4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法页块数为页块数为4的先进先出置换算法页面淘汰序列的先进先出置换算法页面淘汰序列次数次数t页面踪页面踪迹迹P=页框页框M=4失败失败F=012345678910111244411223335541234123551142322412351433324235121344445F=10f=10/12=83%4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法3 最近最少使用算法最近最少使用算法(LRU)(LRU) 用进程过去对页面的使用情况来预测其将来的行为用进程

51、过去对页面的使用情况来预测其将来的行为 需要一定的硬件成本以记录各页面所经历的访问时间需要一定的硬件成本以记录各页面所经历的访问时间 LRU LRU与与OPTOPT区别：区别：OPTOPT使用页面将要访问的时间，使用页面将要访问的时间，进程向后进程向后看，看，LRULRU使用页面最后一次被访问的时间，使用页面最后一次被访问的时间，进程向前看进程向前看。 实现算法：实现算法：4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法物理块数为物理块数为3的的LRU堆栈置换算法页面淘汰序列堆栈置换算法页面淘汰序列次数次数 t页面踪页面踪迹迹P=页框页框M=3失败失败F=0123456789101

52、112444112233355444112233355444112233352134433452 F=10f=10/12=83% 4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法次数次数 t0123456789101112页面踪页面踪迹迹P=432143543215页框页框M=4432143543215F=8f=8/12=67%43214354321432143543243 11 3失败失败F= 页块数为页块数为4的的LRU置换算法页面淘汰序列置换算法页面淘汰序列4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法最近最少使用最近最少使用置换算法理论上性能好，置换算法理论上

53、性能好，但实现代价高但实现代价高（需硬件支持需硬件支持，如：为进程每个内存页面设一，如：为进程每个内存页面设一计时器计时器或或寄存器寄存器，或为进程所有内存页面设一，或为进程所有内存页面设一栈栈/链表）。链表）。LRU的软件解决方案的软件解决方案（LRU的近似算法）的近似算法）：二次机会二次机会(SC, Second Chance）置换算法置换算法时钟时钟(Clock)置换算法置换算法最近未使用最近未使用（NRU, Not Recently Used ）置换算法置换算法4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法 实现实现：页表目中增设访问位页表目中增设访问位R，初值为，初值为

54、1。当页面访问时。当页面访问时置置1。发生缺页中断需置换时，发生缺页中断需置换时，OS按照按照先进先出先进先出FIFO置换算法选择某一页面，检查其置换算法选择某一页面，检查其访问位访问位，如果为，如果为0，则，则淘汰该页，如果为淘汰该页，如果为1，则将该位置，则将该位置0，把该页放到内存，把该页放到内存页面链表的尾端，页面链表的尾端，给它第二次驻留机会给它第二次驻留机会，再检查内存，再检查内存页面链上的下一个页面。如果查到链尾还未找到置换页面链上的下一个页面。如果查到链尾还未找到置换对象，则再从链首开始，进行第对象，则再从链首开始，进行第2趟扫描检查。趟扫描检查。优点优点：实现简单，且性能比实

55、现简单，且性能比FIFO好很多；好很多；缺点：缺点：运行效率低，时间开销大。运行效率低，时间开销大。4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法现有一进程访问的页面号序列为：现有一进程访问的页面号序列为：4,7,0,6,7,1,0,64. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法41474117741110007100660710176761011161101006111160n时钟时钟(Clock)置换算法置换算法 SC的一种改进实现的一种改进实现SC算法因为常需把给予二次驻留机算法因为常需把给予二次驻留机会的页面移到链尾而降低效率，若把会的页面移到链尾而降低效

56、率，若把其所用的内存页面单向链表改为循环其所用的内存页面单向链表改为循环链表，则就不必在链中移动页面了。链表，则就不必在链中移动页面了。这种改进的这种改进的SC法就是法就是Clock法。法。该算法首先检测指针所指的页面，若该算法首先检测指针所指的页面，若访问位为访问位为0，则，则淘汰该页，淘汰该页，新装入的页插入到此位置新装入的页插入到此位置，然后指针前进一个位置；，然后指针前进一个位置；如果它的如果它的访问位为访问位为1，则清除为，则清除为0，并将并将指针前进一个位置指针前进一个位置，继续，继续检查访问位。重复此过程，直到找到访问位为检查访问位。重复此过程，直到找到访问位为0的页面为止。将的

57、页面为止。将该页替换为新页面并置访问位为该页替换为新页面并置访问位为1。 4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法n最近未使用最近未使用（NRU, Not Recently Used ）置换算法置换算法页表目中增设页表目中增设启动进程时，启动进程时，R、M置置0；当对页面执行写操作时，其当对页面执行写操作时，其和和均由硬件置成均由硬件置成1；当对某页面执行读操作时，只有访问位被置成当对某页面执行读操作时，只有访问位被置成1，系统每隔固定时间将所有系统每隔固定时间将所有访问位访问位R都清都清0。当要淘汰某页面时，按照当要淘汰某页面时，按照选择被淘汰的页面，若状选择被淘汰的页面

58、，若状态位相同，淘汰先进入的页面。态位相同，淘汰先进入的页面。4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法n最近未使用最近未使用（NRU, Not Recently Used ）置换算法置换算法 访问位访问位=0=0，修改位，修改位=0=0；直接淘汰；直接淘汰 访问位访问位=0=0，修改位，修改位=1=1；写回外存后淘汰（；写回外存后淘汰（0 0为访问位刷新后为访问位刷新后经过）经过） 访问位访问位=1=1，修改位，修改位=0=0；直接淘汰；直接淘汰 访问位访问位=1=1，修改位，修改位=1=1；写回外存后淘汰；写回外存后淘汰特点特点：易实现，性能上也够用。：易实现，性能上也够

59、用。4. 页面调度页面调度（淘汰（淘汰 / 置换）置换）算法算法例例3.2 设某请求分页系统采用固定分配局部置换策略，一进程的页面走向设某请求分页系统采用固定分配局部置换策略，一进程的页面走向为为4、3、2、1、4、3、5、4、3、2、1、5，该进程分得，该进程分得3个页块，初始个页块，初始为空，试计算分别采用为空，试计算分别采用FIFO、LRU置换算法时该进程访问过程中所发置换算法时该进程访问过程中所发生的缺页次数和依次被换出的页面。生的缺页次数和依次被换出的页面。解解： FIFO 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 5 5 2 1 1 4 3 2 1

60、 4 3 3 3 5 2 2 4 3 2 1 4 4 4 3 5 5 是否命中是否命中 x x x x x x x x x 所以该进程运行时共发生缺页中断所以该进程运行时共发生缺页中断9次，被换出次，被换出的页面依次是的页面依次是4、3、2、1、4、3。5. 页面置换算法举例页面置换算法举例页块页块1页块页块2页块页块3 LRU 4 3 2 1 4 3 5 4 3 2 1 5栈：栈： 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 4 3 2 1 4 3 5 4 3 2 是否命中是否命中 x x x x x x x x x x 所以该进程运行时共发生