2010年自学考试操作系统名词解释总结.ppt

第四章 存储器管理,4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式,在学习这章之前，我们先来考虑这样一个问题：为什么要进行存储器的管理？,要回答这个问题，我们先回忆一下我们计算机使用的过程。,计算机启动到桌面用户启动自己想要运行的程序开始使用,此时我们来假想一下计算机内存中的情况： 内存中此时至少有两部分程序，一部分是操作系统的程序，一部分是用户运行的程序。,而且为了提高计算机的使用效率，现在的计算机系统多采用多道程序的思想，也就是说计算机中一次装入内存的程序应该有多道，再加上操作系统本身的程序，那么在计算机内存中存在的程序应该是多个。,因此就出现了几个问题值得我们思考： 第一个问题：这么多程序在一块内存中，他们之间不相互影响吗？万一串了怎么办？用户程序互相影响也就罢了，但万一影响到操作系统，那系统可就崩溃了！,第二个问题：这些程序装入内存是怎样装入的？只是简单的将要运行的程序的源代码复制到内存就可以了吗？ 第三个问题：多个程序在内存中是怎样存放的，是简单的一个接一个吗？ 第四个问题：万一操作系统的程序和用户要运行的程序都比内存空间大，那怎么办，这些程序还能运行吗？ 我们会考虑这些问题，作为方便用户管理计算机的操作系统更会考虑这些问题，因此操作系统必须具有很好的解决上述几个问题的功能，即存储器管理功能，这也正是要进行存储器管理的主要原因。,下面我们来考虑一下前面几个问题的解决方法： 第一个问题：多个程序相互影响吗？ 肯定影响，解决方法：存储地址保护，即就是给每个程序划分不同的内存区域，如下图所示,以内存地址为界，将内存划分为系统区和用户区，用户程序调入内存时，操作系统肯定在用户区中划分空间，这样首先保证用户程序不会破坏系统程序而是系统崩溃； 在用户区中为不同的用户程序分配空间时，进行内存地址的保护，以保证用户程序之间不会相互干扰和破坏。 这种保护包括： 1、防止地址越界 2、防止越权(对共享区有访问权),存储保护的实现方法 在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址 也可将一个寄存器作为基址寄存器，另一寄存器作为限长寄存器（指示存储区长度） 每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界 如果未越界，则按此地址访问主存，否则将产生程序中断越界中断（存储保护中断）,上下界寄存器保护,基址、限长寄存器保护,说明：并不一定为每个进程设置单独的硬件设备，多个进程公用一组设备即可。,第二个问题：程序装入内存是简单的源代码复制吗？ 肯定不是，将用户源程序变为可在内存中执行的程序的步骤如下： 编译：由编译程序将用户源代码编译成若干个目标模块 链接：由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块 装入：由装入程序将装入模块装入内存 如下图所示,提问：为什么不能将源程序直接复制到内存呢？编译、链接到底提供了什么？,在计算机中执行程序时，CPU是根据内存的地址来寻找指令的，而我们编写程序时，根本不会考虑地址的问题，因此编译、链接的工作是为我们源程序的每条指令设置相应的能在内存中使用的地址，这种问题称为地址的映射。 为了更好的理解地址映射，我们引入几个概念： 物理地址：内存的每个存储单元都有一个编号，这种编号称为内存地址或称为物理地址，绝对地址。 要求用户用内存地址编程是非常困难的，尤其是在多道程序设计的环境中。因此用户编程时一般将开始位置认为0地址，其余指令的地址都是相对于首地址而言的。,逻辑地址：用户编程所用的地址称为逻辑地址（或程序地址，或虚地址），由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）。,我们把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。 地址映射的方式有两种： 1、静态地址映射 2、动态地址映射,1、静态地址映射 程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换，程序分配到那一块内存，根据这块内存的地址对程序中的所有地址进行修改。 假定程序装入内存的首地址为BR，装入前程序的逻辑地址为VR，装入后内存地址为MR，则地址映射按下式进行：MR=BR+VR 。 例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Load A，200就变为Load A，1200,静态地址映射的优缺点 优点：容易实现，不需要硬件的支持。 缺点：程序必须占用连续的内存空间；地址变换在装入时一次完成，以后不再改变，一旦程序装入后不能移动；程序装入时必须一次全部装入内存。,2、动态地址映射 动态地址映射是指把装入模块装入内存时，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。装入内存后的所有地址都仍是相对地址。程序真正要执行时，利用专门的硬件机构来完成地址的映射。,最简单的动态地址映射硬件机构是重定位寄存器。在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。,动态地址映射的具体过程 程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。 在程序执行的过程中，若要访问内存，将访问的逻辑地址送入VR中。 地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的地址。,动态地址映射的地址转换工作是在作业执行的过程中完成的，而静态地址映射的地址转换工作是在作业执行之前集中一次完成的。,动态地址映射的优点 1、程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。 2、一个程序不一定要求占用一个连续的内存空间。 3、可以部分地装入程序运行。 4、便于多个进程共享同一个程序的代码。 动态地址映射的缺点 1、需要硬件的支持。 2、实现存储管理的软件算法较为复杂,第三个问题：多个程序在内存中是怎样存放的，是简单的一个接一个吗？ 这种内存的分配方案不是不行，只是，这种分配方案效率太低，因此，内存的分配方案有很多种，常见的有： 1、连续分配方案 2、基本分页存储管理 3、基本分段存储管理 4、段页式存储管理,第四个问题：万一操作系统的程序和用户要运行的程序都比内存空间大，那怎么办，这些程序还能运行吗？ 程序肯定能够运行，现实中，由于程序员编程时不会受到限制，想写多长就可以写多长，但内存空间是由硬件来决定的，计算机一旦装好，内存的空间不会再变，因此执行的程序空间比内存空间大的情况很多。为了解决这一问题，人们利用了虚拟存储器的思想，利用覆盖和交换技术在逻辑上对内存进行了扩充。,总结 存储器管理的主要功能有: 1、存储保护 2、地址重定位(地址映射) 3、主存分配与回收 4、主存扩充(虚拟内存) 存储器管理的主要目的是：合理安全的使用内存，同时提高内存空间的利用率,4.2 连续分配方式,连续分配方式，是指为一个用户程序分配一个连续的内存空间。 分类： 单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配,4.2.1 单一连续分配 最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。 采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常放在内存低址部分，用户区是指除系统区以外的全部内存空间，提供给用户使用。 而用户区每次只装入一个作业程序，直到该作业程序完成，才会调其它的作业程序进入内存。,4.2.2 固定分区分配 将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样把用户空间划分为几个分区，便允许有几道作业并发执行。当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。 说明：这种分配方法注意两个问题： 1. 划分分区的方法 (1) 分区大小相等：缺乏灵活性，用于一台计算机控制多个相同对象的场合 (2) 分区大小不等：把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区，可根据程序的大小为之分配适当的分区。,2. 内存分配的方法 为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。,4.2.3 动态分区分配 动态分区分配是根据进程的实际需要，动态地为之分配内存空间,使分区的大小刚好与作业的大小相等。这种存储管理的方法解决了固定分区严重浪费内存的问题。是一种较为实用的存储管理方法。 为实现动态分区过程，一般系统中需要建立两个表： 1、分区表 2、可用空间表,固定分区分配很容易产生作业与作业之间的零头问题，引入动态分区思想。,1、分区表 用来记录已经分配了的分区情况,2、空闲分区表：记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。,随着时间的推移，也会出现不连续的可用空间，而且时间变，可用空间也会发生变化，所以也要对可用空间情况做一个记录,为了更好的管理空闲分区，将它们串接为一个空闲分区链 空闲分区链：在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，在分区末尾重复设置状态位和分区大小表目。如下图所示：,引出一个问题：当一个新作业申请装入内存时，需要从空闲分区表或空闲分区链中选出一分区分配给该作业，若有若干个空闲分区都满足条件，那应该选择那一个空闲分区呢？因此出现了几种选择算法： (1) 首次适应算法FF (2) 循环首次适应算法 (3) 最佳适应算法 (4) 最坏适应算法,(1) 首次适应算法FF FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从头到尾不存在满足要求的分区，则分配失败。 优点：优先利用内存低址部分的内存空间 缺点：低址部分不断划分，产生小碎片；每次查找从低址部分开始，增加了查找的开销 要求:空闲区表或空闲区链按地址从低到高排列.,(2) 循环首次适应算法 在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。 为实现算法，需要： 设置一起始查寻指针 采用循环查找方式 优点：使内存空闲分区分布均匀，减少查找的开销 缺点：缺乏大的空闲分区 要求:空闲区表或空闲区链按地址从低到高排列.,(3) 最佳适应算法 所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。 缺点：产生许多难以利用的小空闲区 要求:空闲分区表或空闲分区链按其容量从小到大排列。,(4) 最坏(差)适应算法 所谓“最坏”是指每次为作业分配内存时，总是把能满足要求、又是最大的空闲分区分配给作业。 缺点：大的空闲区不容易保留。 要求:空闲分区表或空闲分区链按其容量从大到小排列。,例：分区存储管理算法 采用可变分区方式管理内存时，若内存中按地址顺序依次有五个大小依次为15k、28k、10k、226k和110k的空闲区。现有五个作业Ja、Jb、Jc、Jd和Je，它们各需要内存10k、15k、102k、26k和180k。 问： 如果采用最先适应分配算法，能将这五个作业按Ja Je的次序全部装入内存吗？ 用什么分配算法装入这5个作业可使内存的利用率最高？,解：(1)按最先适应分配算法，不能将这五个作业按Ja-Je的次序全部装入内存。因为内存中前两个原先的空闲分区能依次装入Ja(10k)和Jb(15k)，第3个10KB的空闲区和刚刚划分出来的两个大小分别为5KB和13KB的空闲区均无法分配，第4个空闲区可以分2次装入作业Jc(102k)和Jd(26k)，则作业Je(180k)无法装入内存。 (2)用最佳适应分配算法装入这5个作业，可使内存的利用率最高。此时，原先的5个空闲区依次装入了5个作业，它们是：Jb(15k)，Jd(26k)，Ja(10k)，Je(180k)和Jc(102k)。,三种分配算法的比较,1、从搜索速度上看：最先适应算法具有最佳性能。尽管最佳适应算法或最坏适应算法看上去能很快地找到一个最适合的或最大的空闲区，但后两种算法都要求首先把不同大小的空闲区按其大小进行排队，这实际上是对所有空闲区进行一次搜索。 2、从释放速度来看：最先适应算法也是最佳的。因为使用最先适应算法回收某一空闲区时，无论被释放区是否与空闲区相邻，都不用改变该区在可用表或自由链中的位置，只需修改其大小或起始地址。 3、上述三种放置策略各有利弊，到底哪种最好 不能一概而论，而应针对具体作业序列来分析。,动态分区刚开始时，没有存储零头，但随着时间的推移，也会出现零头的问题。 例如：有三个存储零头是5k、8k、12k，有一个20k的作业，每个存储零头都不能满足作业要求，但总的存储空间是满足的。 因此要提高存储空间的使用效率，主要是解决存储零头的问题，那如何解决存储零头问题呢？ 两种方法： 1、程序的浮动：将几个空闲空间合并。 2、多重分区：将一个作业撕开，分散的装入到几个分区中。,动态分区总结,4.2.4 可重定位分区分配 1. 动态重定位的引入 在连续分配方式中，必须把系统或用户程序装入一连续的内存空间。 如果在系统中只有若干个小分区，即使它们的容量总和大于要装入的程序，但由于这些分区不相邻，所以无法将程序装入内存。 解决方法：将内存中的所有作业进行移动，使它们全部邻接，这样可把原来分散的小分区拼接成大分区，这种方法称为“拼接”或“紧凑”。 缺点：用户程序在内存中的地址发生变化，必须重定位，开销大，移动时机不好定。,2. 动态重定位的实现 在动态运行时装入的方式时，将相对地址转换为物理地址的工作在程序指令真正要执行时才进行。地址转换需要重定位寄存器的支持。程序执行时访问的内存地址是相对地址与重定位寄存器中的地址相加而成。 地址变换过程是在程序执行过程期间，随着对每条指令的访问自动进行的，称为动态重定位。,扩充内存的两种方法 -交换与覆盖,覆盖技术：把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域 覆盖举例：,程序总共需要108k内存空间，但在执行的过程中A、B；X、M、N进程不会同时执行，因此它们有65k的内存空间就够用了。,覆盖技术的实现：把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域，即就是一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。,交换技术：是指当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度，多用于分时系统中。,交换技术实现的基本依据：程序的局部性原理。,局部性原理：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：,时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内（一条指令被执行了，则在不久的将来它可能再被执行） 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。（若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用),局部性原理的具体体现 1、程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。 2、过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。 3、程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。 4、程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。,交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换 交换技术与覆盖技术不同点： 与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。,4.3 页式存储管理方式,连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销大。根据多重分区的思想，如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式。 分页技术是由曼彻斯特大学提出，并于1960年前后在Atlas计算机上实现。这种技术对操作系统的发展产生了深远影响。,4.3.1 页面与页表 1. 几个基本概念 页面：将一个进程的逻辑地址空间分成若干个大小相等的片称为页或页面，并为各页加以编号，从0开始。 物理块:把内存空间分成与页面相同大小的若干个存储块，称为块或页架。 页式管理的基本思想：在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。 页内碎片：进程的最后一页经常装不满而形成“页内碎片”。,1、页面大小的确定 页面大小应适中，必须是2的幂，通常是512B8KB。,2、页号、页内地址的计算 若给定一个逻辑地址空间中的地址为A，页面大小为L，则 页号P=INTA/L 页内地址d=A MOD L 例1：系统页面大小为1KB，设A=2170B，计算页号P和页内地址。 解：P=INT (2170/1024)=2 d=2170 mod 1024 =122,页式管理中的几个注意问题：,3. 页式存储下内存地址结构,假设：内存地址长度为32，且系统为每个页面划分大小为4K，则内存地址的含义如下：,地址长度共32位: 011位为位移量(页内地址)，即每页的大小为4KB 12 31位为页号，地址空间最多允许有1M页,例如：设内存地址线共14位，后10位表征页的大小,前4位为页号,则内存的分页情况如图所示,每页大小为1K,16K的内存分了16个页架,4. 页表的含义和地址映射中的计算 在分页系统中，允许进程的每一页离散地存储在内存的任一存储块中，为方便查找，系统为每一进程建立一张页面映像表，简称页表。 页表记录了一个进程的各个页对应的页架号，有了页表就可以实现从页号到物理块号的地址映射。 在页表表项中常设置一存取控制字段，对存储块内容加以保护。,页表常包含的几个表项： 页号：登记程序地址空间的页号。 块号：登记相应的页所对应的内存块号 其它：登记与存储信息保护有关的信息 如下表就是一个页表,例2：一个进程具有有0、1、2三个页面，对应的页架号为4、5、9。若系统页面大小为1KB，指令load 2 2480 的逻辑地址为1200，则该指令和指令中操作数的物理地址是多少？ 解： 1200/1024=商1余176 说明该指令在第1页中且页内地址为176 因此，指令的物理地址=1024*5+176=5296 2480/1024=商2余432 说明该操作数在第2页中且页内地址为432 因此，操作数的物理地址=1024*9+432=9648,总结页式存储管理的过程，可得到如下结论： 1、CPU每存取一个数据时，都需要进行两次访问内存。 2、第一次访问内存：找到页表，查找相应指定页的物理块号，将块号与页内偏移量拼接形成物理地址。 3、第二次访问内存：从第一次所得地址中获得所需数据，或向此地址中写入数据。 其过程如下图所示：,在上述过程中，还有两个问题需要我们考虑： 1、存储器利用率提高了，但处理器处理速度降低了。 2、现代的大多数计算机系统，都支持非常大的逻辑地址空间(232-264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB，则页表中页表项就有1兆（220）个之多。假设每个页表项占用4个字节， 仅仅其页表就要占用4MB的内存空间，而且还要求是连续的。,第一个问题的解决方法：具有快表的地址变换机构，即就是在系统中增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想寄存器”或“快表”。 因为快表的速度是内存速度的数倍或数十倍，那么相对于内存速度，访问页表的时间可以忽略不计。也就是说页地址变换不会造成进程运行速度下降多少。 其示意图如下：,第二个问题的解决方法： 采用离散分配方式来解决难以找到一块连续的大内存空间的问题： 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。,也就是说，页表在内存中也使用离散分装和换进换出的思想，以减小页表所占内存空间和小空间、大页表的问题。,页表能够分散装入和换进换出，一个整的页表是很难做到的，因此引入两级页表和多级页表的思想。 两级页表 ：将页表也进行分页，离散地将各个页面分别存放在不同的物理块中，同时为离散分装的页表再建立一张额外的页表，称为外层页表，其每个页表项记录了页表页面的物理块号。 其示意图如下：,例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB，则页表中页表项就有1兆（220）个之多。假设每个页表项占用4个字节， 仅仅其页表就要占用4MB的内存空间，但若采用二级页表，页表所占空间总数没有变化，不过这些空间可以分为若干个小的空间，放在不连续的内存块中。而且当时不用的一些小空间可暂时不调入内存，从而使页表所占内存大大减小。,为实现实现上述所说，在地址变换机构中需设一外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用p2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址，其示意图如下：,通过前面的学习，我们了解到两级页表的确可以解决页表占连续内存的问题，但同时也引入了一个新的问题，那就是两级页表系统中，CPU每存取一个数据时，都需要进行三次访问内存，使得处理机的效率下降，因此前面我们所说的两个问题都要解决，就要处理好这两个问题之间的取舍关系。,多级页表 对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4 KB即212 B，那么还剩下52位， 假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项， 要占用16384 GB的连续内存空间。 必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。 对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。,页式存储管理分为两种方式： 基本分页存储管理：也叫实分页式存储管理或静态页式存储管理，它是指只有作业或进程将涉及到的所有页面全部装入内存后，才会执行。 请求分页存储管理：也叫虚拟页式存储管理或动态页式存储管理，它是指作业或进程执行之前不是将作业或进程涉及到的所有页面全部装入内存，而是只装入一部分，其它部分在执行的过程中需要了再动态装入。,基本分页存储管理方式，它要求作业执行前，必须将作业或进程涉及到的所有页面全部装入内存。这样就有了一些限制。例如，当内存能提供的所有页架的个数小于作业的页面数时，则这个作业将永远不能执行。而请求分页存储管理方式可以动态的装入作业，不会产生这样的问题。因此在现在的计算机系统中多采用请求分页存储管理方式来管理内存。 但请求分页存储管理方式同样存在问题： 1、把作业的那一部分装入内存比较合适？ 2、什么时候进行页面的换进换出？ 3、若内存中没有空闲空间时，换进换出应换掉那一个页面？,解决问题： 1、把作业的那一部分装入内存比较合适？ 当然应该将马上要运行的页面先装入内存，其它的可先放在外存中等待换进换出。 2、什么时候进行页面的换进换出？ 两种策略：请求调入策略：即执行时缺少页了，就中断调入。预调入策略：将外存中的页提前计算一个时间顺序，按此顺序进行调入。 3、若内存中没有空闲空间时，换进换出应换掉那一个页面？ 三种算法：先进先出页面置换算法（FIFO） 最近最久未使用置换算法（LRU） 理想淘汰置换算法（OPTIMAL） 为了说明这三种算法，我们先来看一个例题：,例：设某作业占有7个页面，如果在主存中只允许装入4个工作页面，作业运行时，实际访问页面的顺序是1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用FIFO、 LRU 与OPTIMAL页面调度算法，列出各自的页面淘汰顺序和缺页中断次数,解：（1）fifo页面调度算法,如上表所示，缺页的顺序为：1 2 3 6 4 7 2 1 5 6 缺页的次数：10次,（2）lru页面调度算法,如上表所示，缺页的顺序为：1 2 3 6 4 7 2 1 4 7 5 6 2 1 缺页的次数：14次,（2） OPTIMAL页面调度算法,如上表所示，缺页的顺序为：1 2 3 6 4 7 4 5 6 缺页的次数：9次,总结请求分页存储管理方式： 1、基本思想：在基本分页（实分页）的基础上增加虚拟存储功能。 进程开始运行之前，不是装入全部页面，而是装入几个或零个页面，之后根据进程运行的需要，动态装入其它页面； 当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,2、页表结构：同基本分页管理方式一样， 为了将用户程序地址空间中的逻辑地址变换为内存空间中具体内存块的物理地址。 在请求分页系统中也需要页表。只不过页表的结构发生了变化，其具体结构如下：,状态位P ：用于指示该页是否已调入内存。 (2)访问字段A ：用于记录本页在一段时间内被访问的 次数，或记录本页最近已有多长时间未被访问。 (3)修改位M ：表示该页在调入内存后是否被修改过。 问题：考虑为什么要有这一项？ (4)外存地址：用于指出该页在外存上的地址。,其中：,3、系统中应该有缺页中断机构 在请求分页系统中，每当要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。 此时应将缺页的进程挂起（调页完成唤醒） 如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项目 若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）,问题：缺页中断同一般中断的区别？ 相同点：缺页中断作为中断，同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。 不同点：缺页中断是一种特殊的中断，与一般中断有明显区别： (1) 在指令执行期间产生和处理中断信号。 (2) 一条指令在执行期间，可能产生多次缺页中断。,4、系统中的地址变换机构有所改进 请求分页系统中的地址变换机构，是在基本分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的。 如：能够产生和处理缺页中断，以及具有从内存中换出一页的功能等等。 其过程如下图所示：,5、 系统为进程分配内存时， 内存的分配策略和分配算法，主要涉及三个问题： （1）最小物理块数的确定 （2）物理块的分配策略 （3）物理块的分配算法,（1）最小物理块数的确定 最小物理块数，是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。,进程应获得的最小物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。 对于某些简单机器，若是单地址指令且采用直接寻址方式，最小物理块数应为2，如果该机器允许间接寻址，则至少要求3个物理块。 对于某些功能较强的机器，指令长度可能是两个或两个以上字节，至少要为进程分配6个物理块。,（2） 物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。 在进行置换时，也可以采取两种策略，即全局置换和局部置换。于是可以组合出三种适合的策略。,、固定分配局部置换 基于进程的类型，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间不再改变。 采用该策略时，如果进程在运行中发现缺页，只能从该进程在内存中的n个页面中选出一页换出，然后再调入一页。,、可变分配全局置换 在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲的物理块队列。如果某进程发生缺页时，由系统从空闲的物理块队列中，取出一个物理块分配给该进程，并将欲调入的页装入其中。,、可变分配局部置换 基于进程的类型，或根据程序员的要求，为每个进程分配一定数目的物理块，如果某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，不会影响其他进程执行。如果进程在运行中频繁发生缺页中断，则系统再为进程分配若干物理块；如果进程在运行中缺页率特别低，则适当减少分配给该进程的物理块。,（3）物理块分配算法 在采用固定分配策略时，如何将系统中可供分配的物理块分配给各个进程，可采用以下几种算法： (1) 平均分配算法 将系统中所有可供分配的物理块，平均分配给各个进程。 缺点：未考虑各进程本身的大小。 (2) 按比例分配算法 根据进程的大小按比例分配物理块。 假设系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：,又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：,注意：b应该取整，而且必须大于最小物理块数。,(3) 考虑优先权的分配算法 以上两种算法可以完成物理块的分配，但没有考虑到各个作业的轻重缓急程度。在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间。 方法： 一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。,6、请求分页存储管理方式中页面大小的确定 页面太大：页的碎片多，缺页的机率提高 页面太小：页表占用的内存空间会增大 页面大小如何确定呢？我们来看一个例题。 例：设内存大小为M，作业的平均尺寸为J，一 个页表项占一个单位，问最佳的页面尺寸P应该为多少？ 解：最佳页面尺寸也就是空间浪费最小的尺寸。 在这我们认为所有作业的平均页内碎片的大小为P/2 则系统中浪费空间的函数为：,把它看作是P的函数，因此有,我们希望Y越小越好，则,计算得：,即：,7、调页策略 1. 何时调入页面 1）预调页策略 采用以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。 目前预调页的成功率仅为50%,主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 2）请求调页策略 当程序在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需要的页面调入内存。 优点：由请求调页策略所确定调入的页，一定会被访问；请求调页策略比较容易实现。 缺点：每次仅调入一页，需花费较大的系统开销，增加了磁盘I/O的启动频率,2. 从何处调入页面 在请求分页系统中的外存分为文件区和对换区。 每当发生缺页时，系统应从何处将缺页调入内存，可分成三种情况： 系统拥有足够的对换区空间：可以全部从对换区调入所需页面，以提高调页速度。 系统缺少足够的对换区空间：凡不会被修改的文件，直接从文件区调入；换出时不用换，再调入时仍从文件区调入。可能被修改的部分，换出时需调到对换区，换入时从对换区调入。,3. 页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。 主要过程如下： 1、缺页中断 2、查找页表，找到该页在外存的物理块 3、调入并修改页表 4、如果内存已满，按照某种置换算法从内存中选出一页准备换出 5、再把做缺的页面调入内存，修改页表中的相应表项,8、页面置换算法概念： 在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区。但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能。 一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。,常见的几种页面置换算法 最佳置换算法（Optimal) 先进先出页面置换算法（FIFO） 最近最久未使用置换算法（LRU） 简单Clock置换算法（最近未用算法NRU） 改进型Clock置换算法 最少使用置换算法（LFU) 页面缓冲算法,1. 最佳置换算法 其所选择的被淘汰页面，将是以后永不再用的，或者是在最长(未来)时间内不再被访问的页面。 优点：保证获得最低的缺页率 缺点：无法预知一个进程在内存的若干个页面，哪个在未来最长时间内不再被访问。 算法无法实现，但可评价其他算法,2. 先进先出置换算法 算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。 算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针(替换指针)，使它总是指向最老的页面。 算法与进程的实际运行规律不相适应，因为进程中的某些页面经常被访问，但先进先出置换算法不能保证这些页面不被淘汰。 先进先出置换算法最直观，但其性能较差，故应用极少。,3、 LRU置换算法的描述 算法根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。,LRU置换算法虽然较好，但如何能具体实现这个算法呢？ 最容易想到，也最简单的方法：计时法。给页表中的每一页增加一个域，专门用来存放计时标志，用来记录该页面自上次被访问以来所经历的时间。页面每被访问一次，计时清0。要装入新页时，从内存的页面中选出时间最长的一页，调出，同时把各页的计时标志全部清0，重新开始计时。 计时法可以稍作改变，成为计数法：页面被访问，计数标志清0，其余所有内存页面计数器加1；要装入新页时，选出计数最大的一页调出，同时所有计数器清0。 这两种方法确实很简单，但运行效率却不尽如人意。每个时刻，或是每调用一个页面，就需要对内存中所有页面的访问情况进行记录和更新，麻烦且开销相当大。,另一种实现的方法：链表法。 操作系统为每个进程维护一条链表，链表的每个结点记录一张页面的地址。调用一次页面，则把该页面的结点从链中取出，放到链尾；要装入新页，则把链头的页面调出，同时生成调入页面的结点，放到链尾。 链表法可看作简单计时/计数法的改良，维护一个链表，自然要比维护所有页面标志要简单和轻松。可是，这并没有在数量级上改变算法的时间复杂度，每调用一个页面，都要在链表中搜寻对应结点并放至链尾的工作量并不算小。,前面几种方法都是单纯使用软件实现的算法。我们知道，硬件的速度比软件的速度要快的多，因此如果能有特殊的硬件帮忙，我们可以得到更有效率的算法。 常用硬件的方法有两种： 1、寄存器 2、栈 1）寄存器 为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。 移位寄存器表示为R=RnRn-1Rn-2R2R1 则：在一个有n个页框的机器中，寄存器就构成了一个n*n的矩阵，开始时所有位的初始值都是0。访问到第k页时，硬件把k行的位全设为1，之后再把k列的位置设为0。不难证明，在任意时候，二进制值最小的行即为最久未使用的页面，当调换页面时，将其调出。,例：一个作业的共有5个页面，访问次序为2、1、4、3、5，用寄存器法来验证每次置换时内存中的最近最久未使用的页面。,初始情况,5,4,3,2,1,1,2,3,4,5,2）栈 利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。,4、clock置换算法 LRU算法是比较好的算法，但需要硬件的支持，因此实际中多采用LRU算法的近似算法。 算法步骤： 1、每页增设一个访问位,访问过的页面访问位置1 2、将内存中的页链成一个循环队列,查询指针循环移动 其过程图如下：,例题说明三种算法：,5、改进型Clock算法 Clock算法加上置换代价(尽量选择未修改过的页面淘汰) 每页有访问页u 和 修改位m u=0 m=0 未用过,未修改过,最佳淘汰页面 u=0 m=1 未用过,但改过,不是最佳淘汰页面 u=1 m=0 最近用过,但未被修改,可能被再次使用 u=1 m=1 最近用过,被修改过,可能被再次使用 算法需要重复多次Clock算法 从当前位置找u=0,m=0的页面,有则淘汰 否则第二遍找u=0,m=1的页面,同时将u置为0,有则淘汰 否则第三遍找u=0,m=0的页面,有则淘汰 否则第四遍找u=0,m=1的页面,(肯定会找到),6、其它置换算法 1、最少使用置换算法(LFU) 2、页面缓冲算法(PBA),最后，我们再来考虑一个问题，分配的页架数越多，作业执行的速度是不是越快呢？ 例：假设进程P共有5页，程序访问内存的顺序为1，2，3，4，1，2，5，1，2，3，4，5。当分配到的页架数是3和4时，利用FIFO算法求出其缺页次数？,解：页架数为三时，其缺页情况如下：,页面数3 缺页次数9 缺页率75,页架数为四时，其缺页情况如下：,页面数4 缺页次数10 缺页率=83.3,Belady现象 是指在使用FIFO算法进行内存页面置换时，在未给进程或作业分配足它所要求的全部页面的情况下，有时出现的分配的页面数增多，缺页次数反而增加的奇怪现象。,到此我们对分页存储管理方式有了一个全面的了解，分页管理方式的主要思路就是将一个作业分为大小相同的若干个页，然后将它们离散的分装在内存中的页架上。 页式管理方式很好的解决了碎片的问题，但同时也存在着一个这样的问题：那就是一个作业能不能随意的分开呢？如果要分的地方偏偏不能分怎么办？,因此我们提出了段式存储管理的思想。 我们知道，一个大的程序可以分解为若干个小的功能完整的子函数（程序）段，对于整个作业来说，一个子函数段在逻辑上是完整的，是可分的。因此我们采用动态分区的方式将一个作业的子函数段离散的分装在内存中，就不会出现刚在我们在分页管理中分页时考虑的能不能分的问题。 这种将大的作业按照子函数段离散分装在内存中的思想就是段式存储的思想。,一个程序由若干部分(段)组成，每个段有各自的特点、用途! 通常在操作系统中还用段号代替段名。,因此分段管理中每一条指令的地址其实都是一个二维地址，横向找到段，从向找到段内偏移地址。,分段管理方式中各段装入内存的情况如下：,总结段式存储管理的基本原理 1. 用户程序的划分 在分段存储管理方式中，作业地址空间被划分为若干个段，每个段定义了一组逻辑信息，都有自己的名字（称为段名）， 通常还用段号代替段名。 每段从0开始编址，并采用一段连续地址空间。段长由逻辑信息组的长度决定。一个段的逻辑地址由段号(段名)和段内地址所组成。 2.内存划分 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定 3.内存分配 分段式存储管理的实现是基于动态分区存储管理的原理。系统为每个分段分配一个连续的分区，而进程中的各个段可以离散地装入内存中不同的分区中。,段式存储管理中的数据结构-段表 在段式存储管理中，为使操作系统清楚了解内存分配情况，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(段基址)和段的长度。 有了段表就可以实现从逻辑地址到内存物理地址的映射。,一个进程需要记录多个基址,通过上图我们可以看出分段管理方式与分页管理方式有着同样的问题，那就是：段式存储管理中，因为存在段表，同时段表存放在内存中，所以分段管理方式中每访问一个数据，也需两次访问内存，降低了计算机的速率。 解决方法：设置联想寄存器（快表），用于保存最近常用的段表项。这样,比起没有地址变换的常规存储器的存取速度来仅慢约10%15%.,分页和分段的主要区别 相似点： 采用离散分配方式，通过地址映射机构实现地址变换 不同点： 页是信息的物理单位，分页是为了满足系统的需要,可以提高内存的利用率，但可能破坏程序的逻辑关系； 段是信息的逻辑单位，含有一组意义相对完整的信息，分段是为了满足用户的需要。 页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。 分页的作业地址空间是一维的；分段的作业地址空间是二维的。,段式存储管理的优缺点分析,