第四章存储器管理ppt课件.ppt

《第四章存储器管理ppt课件.ppt》由会员分享，可在线阅读，更多相关《第四章存储器管理ppt课件.ppt（133页珍藏版）》请在三一办公上搜索。

1、第四章 存储器管理,2012年4月23日,存储器管理,存储器的层次结构程序的装入和链接 连续分配方式 基本分页存储管理方式 基本分段存储管理方式 虚拟存储器的基本概念 请求分页存储管理方式 页面置换算法 请求分段存储管理方式,存储器的层次结构,多级存储结构主存储器与寄存器高速缓存和磁盘缓存,图 4-1 对用户程序的处理步骤,程序的装入和链接,程序的装入,绝对装入方式(Absolute Loading Mode)可重定位装入方式(Relocation Loading Mode)动态运行时装入方式(Denamle Run-time Loading),绝对装入方式,程序中所使用的绝对地址，既可在编译

2、或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。,绝对装入方式,特点 只能将目标装入到内存中事先指定的地方。装入模块装入内存后，由于程序中的逻辑地址与实际地址完全相同，故不须对程序和数据的地址进行修改。多道程序环境下，编译程序不可能预知所编译的目标模块在内存的何处。因此，只适用于单道系统。问题：如果想把装入模块装入到内存的任何一个位置，应该怎么做？,图 4-2 作业装入内存时的情况,可重定位装入方

3、式,可重定位装入方式,特点：在装入时对目标程序中指令和数据的修改过程通常进行重定位。将装入模块装入到内存中任何允许的位置。不允许程序运行时在内存中移动位置。问题：但是，程序在内存中的位置可能经常改变，此时应采取什么措施？,动态运行时装入方式,动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。,程序的链接,静态链接方式(Static Linking)装入时动态链接(Loadtime Dynamic Linking)运行时动态链接(Run-time Dynamic L

4、inking),静态链接方式,静态链接方式,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：对相对地址进行修改 变换外部调用符号,静态链接方式,特点：事先进行连接，以后不再拆开目标模块。无法修改和更新目标模块。如果要修改或更新其中的某个目标模块，则要求重新打开装入模块。无法实现对目标模块的共享。,装入时动态链接,用户源程序经编译后所得的目标模块，是在装入时边装入边连接的。装入目标模块时，修改目标模块的相对地址。,装入时动态链接,特点：便于修改和更新 各个模块是分开存放的。便于实现对目标模块的共享 很容易将一个模块连接到多个模块。,运行时动态链接,这种链接方式是将对某些模块的链接推迟

5、到执行时才执行。在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,运行时动态链接,特点：容易实现程序局部性操作。提高内存的利用率。提高程序的执行效率。,连续分配方式,连续分配方式，是指为一个用户分配一个连续的内存空间。分类：单一连续分配 固定分区分配 动态分区分配 可重定位分区分配 对换(Swapping),单一连续分配,这是最简单的一种存储管理方式。只能用于单用户、单任务的操作系统中。采用这种存储管理方

6、式时，可把内存分为系统区和用户区两部分：系统区仅提供给OS使用，通常是放在内存的低地址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。,单一连续分配,特点：仅适用于单用户、单任务操作系统；内存空间连续分配 机器由一个用户独占，不可能存在其他用户的干扰。,固定分区分配,固定分区分配是最简单的一种可运行多道程序的存储管理方式；将内存用户空间划分为若干个固定大小的区域，在每个区域中只装入一道作业，便允许有几道作业并发执行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区。,固定分区分配,划分分区的方法 分区大小相等，即使所有的内存分区大小相等。缺点：缺乏灵

7、活性。优点：用于利用一台计算机去控制多个相同对象的场合。分区大小不等。,固定分区分配,内存分配 为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（已分配）。,固定分区分配,图 4-4 固定分区使用表,固定分区分配,特点：内存管理比较简单。满足少量的进程的需要。内存的利用率低。,动态分区分配,是根据进程的实际需要，动态地分配内存空间。分区分配时，应考虑：所采用的数据结构分区分配算法分区的分配与回收,分区分配中的数据结构,空闲分区表 空闲分区链,分区分配中的数据结构,空闲分区表,分区分配中的数据结构,空闲分区链,分区分配算法,首次适

8、应算法FF 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应算法,分区分配操作,分配内存 u.size:请求的分区大小 m.size:每个空闲分区大小 size:事先规定的不再切割的剩余分区的大小回收内存,分配内存,图 4-6 内存分配流程,回收内存,可重定位分区分配,动态重定位的引入在连续分配方式中，必须把一个系统或用户程序装入一个连续的内存空间。如果出现以下情况，该怎么办？,可重定位分区分配,可重定位分区分配,动态重定位的实现,图 4-9 动态重定位示意图,可重定位分区分配,动态重定位分区分配算法算法与动态分区分配算法基本上相同。差别：在这种分配算法中，增加了紧凑的功能，通常，在找不

9、到足够大的空间分区来满足需求时进行紧凑。具体操作如下：,动态重定位分区分配算法,图 4-10 动态分区分配算法流程图,例题：,某一存储器系统采用动态分区方案，设当前的空白区如下表所示：,例题：,现有5个作业J1，J2，J3，J4，J5，他们分别需要20,42,120,130,18 KB，若采用最先适应算法，以怎样的次序可以将这五个作业都装入主存，并给出空白区表。,例题2：,在某系统中，采用固定分区存储管理方式，内存分区的情况如图所示。现有大小为15KB、53KB、110KB的多个作业要求进入内存。试画出它们进入内存后的空间分配情况，并说明主存浪费有多大？,对换(Swapping),对换的引入

10、对换空间的管理 进程的换出与换入,对换(Swapping),对换的引入所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。,对换(Swapping),对换空间的管理为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，它们的单位是盘块号和盘块数。,对换(Swapping

11、),进程的换出每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。,对换(Swapping),进程的换入系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,连续分配方式,特点:将把内存连续地分配，会形成许多“碎片”。

12、虽然使用“紧凑”技术，对形成的“碎片”进行拼接，但须为之付出很大的开销。适用于比较简单的内存管理场合。问题：如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无须再进行”紧凑”，那应该如何实现？,离散分配方式,分页存储管理方式分配的基本单位是页分段存储管理方式分配的基本单位是段段页式存储管理方式分配的基本单位是”段页“,基本分页存储管理方式,页面与页表地址变化机构*两级或多级页表,页面与页表,页面 页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块

13、，称为(物理)块或页框(frame)，也同样为它们加以编号，如0块、1块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。,页面与页表,页面 页面大小 在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大

14、。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B8 KB。,页面与页表,地址结构,分页地址中的地址结构如下：,31,12,11,0,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,页面与页表,地址计算公式：逻辑地址=p(页号).d(页内位移)物理地址=f(页帧号).d(页内位移)p=逻辑地址/页面大小 d=逻辑地址-p*页面大小,页面与页表,页表,地址变换机构,为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。页内地址和物理地址是一一对应的。通常页表存放在内存

15、中，而页表在内存中始地址和长度存放在PCB中。当调度程序调度到某进程时，才将以上两个数据调入到页表寄存器中。,地址变换机构,基本的地址变换机构,图 4-12 分页系统的地址变换机构,地址变换机构,注意页表长度的表达方式：十进制表达方式采用公式计算二进制表达方式直接计算即给定的二进制位数来确定页面或页号大小。,例子1,在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（页表）见如下：,试借助地址变换图求现有效逻辑地址4865所对应的物理地址。,地址变换机构,具有快表的地址变换机构,图 4-13 具有快表的地址变换机构,大小通常只存放16512个页

16、表项。,例子2,假定某操作系统存储器采用页式存储管理，页的大小为64字节，假定一进程的代码段的长度为702个字节，页表如左表所示。该进程在联想存储器中的页表如右表所示,例子2,现进程有如下访问序列，其逻辑地址为八进制的105、217、567、1120、2500.试问给定的这些地址能否进行转化？若能，请说明地址转换过程及相应的物理地址。若不能，则说明理由。,*两级和多级页表,现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页

17、表中的页表项可达1兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用4 KB的内存空间，而且还要求是连续的。可以采用这样两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连续的大内存空间的问题：只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。,两级页表(Two-Level Page Table),逻辑地址结构可描述如下：,图 4-15 具有两级页表的地址变换机构,*多级页表,对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4 KB即212 B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则

18、将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16384 GB的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。,页式存储管理的特点,对内存的利用率比较高管理比较方便程序在内存中的表达方式和程序本身的逻辑划分之间存在差异完全没有考虑用户的需要，即对用户而言不自然不利于进行共享,基本分段存储管理方式,分段存储管理方式的

19、引入分段系统的基本原理信息共享段页式存储管理方式,分段存储管理方式的引入,引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：方便编程 信息共享 信息保护 动态增长 动态链接,分段系统的基本原理,在分段存储管理系统中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都从0开始编址。段的长度由相应的逻辑信息组的长度决定。逻辑地址空间是二维的。段地址由段号和段内地址所组成。,分段系统的基本原理,分段,分段地址中的地址具有如下结构：,31 16 15 0,分段系统的基本原理,逻辑地址空间到物理地址空间的映射需要一张表格来实现即段表。系统中为每个进程创建-“段表”。段表存

20、储在内存中。段表的始地址和段长度存放在PCB中。,分段系统的基本原理,段表,分段系统的基本原理,地址变换机构,为了加快内存的访问速度，在系统中增设联想存储器。,分页和分段的主要区别,页是信息的物理单位，以消减内存的外零头，提高内存的利用率。分页仅仅是由于系统管理的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。,分页和分段的主要区别,页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息

21、的性质来划分。,信息共享,分段系统的一个突出有点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。,信息共享：示例,有一个多用户系，可同时接纳40个用户，他们执行一个文本编辑程序。文本编辑程序有160KB的代码和另外40KB的数据区，则总共需有8MB的内存空间来支持40个用户。假定每个页面大小为4KB,分页管理方式,图 4-19 分段系统中共享editor的示意图,段页式存储管理方式,基本原理先将用户程序分成若干个段，再把每个段分成若干个页。在段页式系统中，其他地址结构由段号、段页号及页内

22、地址三部分组成。,段页式存储管理方式,图 4-21 利用段表和页表实现地址映射,地址转换过程,图 4-22 段页式系统中的地址变换机构,为了提高访问速度，在地址变换中增设了一个高速缓冲寄存器。,越界,段表,页表,虚拟存储器的基本概念,虚拟存储器的引入虚拟存储器的实现方法虚拟存储器的特征,虚拟存储器的引入,常规存储器管理方式的特征:一次性 驻留性,虚拟存储器的引入,局部性原理早在1968年，Denning.P就曾指出：程序在执行时呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。,虚拟存储器的引入,程序执行时，除了少部分的转移和过程调用

23、指令外，在大多数情况下仍是顺序执行的。过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。,虚拟存储器的引入,局限性又表现在下述两个方面：时间局限性 空间局限性,虚拟存储器的引入,虚拟存储器定义：所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可

24、见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。,虚拟存储器的实现方法,分页请求系统 硬件支持 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的 实现请求分页的软件,虚拟存储器的实现方法,虚拟存储器的特征：多次性 对换性 虚拟性,请求分页存储管理方式,请求分页中的硬件支持 页表机制,该页是否已调入内存,请求分页存储管理方式,请求分页中的硬件支持

25、缺页中断机构,与一般中断相比，有着明显的区别：在指令执行期间和处理中断信号。一条指令在执行期间，可能产生多次缺页中断。,请求分页存储管理方式,地址表换机构,内存分配策略和分配算法,最小物理块数的确定 物理块的分配策略 物理块分配算法,最小物理块数的确定,是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，

26、则至少要求有三个物理块。,物理块的分配策略,在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。固定分配局部置换(Fixed Allocation,Local Replacement)可变分配全局置换(Variable Allocation,Global Replacement)可变分配局部置换(Variable Allocation,Local Replacemen,物理块分配算法,平均分配算法 按比例分配算法,平均分配算法,这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有

27、100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。,按比例分配算法,这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。,调页策略,何时调入页面 预调页策略 请求调页策略,调页策略,从何处调入页面在请求分页

28、系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。每当发生缺页请求时，系统应从何处将缺页调入内存。,从何处调入页面,系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换

29、区，以后需要时，再从对换区调入。,从何处调入页面,UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。,页面置换算法,最佳置换算法先进先出置换算法最近最久未使用(LRU)置换算法Clock置换算法其它置换算法,置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的页面更换频率。,最佳置换算法,最佳置换算法是由Belady于1966年提出的一种理

30、论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。,图 4-25 利用最佳页面置换算法时的置换图,先进先出置换算法,图 4-26 利用FIFO置换算法时的置换图,淘汰最先调入内存的页面，即在内存中驻留时间最久的页面。,缺点：

31、该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问。它所依据的条件是各个页面调入内存的时间，而页面调入的先后不能反映页面的使用情况。,最近最久未使用(LRU)置换算法,页面调入内存后的使用情况进行决策的。由于无法预测各个页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似。LRU算法是选择最近最久未使用的页面予以淘汰。LRU算法予以每个页面一个访问字段，用来记录一个页面上次被访问以来所经历的时间t，当淘汰一个页面时，选择现有页面中其t值最大的页面予以淘汰。,图 4-27 LRU页面置换算法,最近最久未使用(LRU)置换算法,最近最久未使用(LRU)置换算法,LR

32、U置换算法的硬件支持,寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为,R=Rn-1Rn-2Rn-3 R2R1R0,最近最久未使用(LRU)置换算法,图 4-28 某进程具有8个页面时的LRU访问情况,栈,图 4-29 用栈保存当前使用页面时栈的变化情况,每当进程访问页面时，便将该页面的页号从栈中移出，将它压入栈顶。,Clock置换算法,Clock算法是用得较多的一种LRU近似算法。算法描述：当采用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一

33、页淘汰时，只需检查访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若访问位仍为1，则在返回到队首去检查第一个页面。,Clock置换算法,1.简单的Clock置换算法（最近未使用算法NRU）,图 4-30 简单Clock置换算法的流程和示例,改进型Clock置换算法,由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,

34、M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。,其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，

35、如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。,其它置换算法,最少使用(LFU：Least Frequently Used)置换算法 页面缓冲算法(PBA：Page Buffering Algorithm),在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。,例题：,在一个请求分页系统中，假如系统分配给一个作业的物理块数是3，并且此作业的页面走向为2,3,2,1,5,2,4,5,3,2,5,2，试用FIFO、LRU、Clock和最佳算法分别请求其程序访问过程中发生的缺页中断的次数。,请求分段存储管理方式,在请求分段系统中，程序运行之前

36、，只需先调入若干个分段（不必调入所有的分段），便可启动运行，当访问的段不在内存时，请求OS将所缺的段调入内存。,请求分段存储管理方式,请求分段中的硬件支持 段表机制 缺页中断机构 地址变换机构,请求分段中的硬件支持,1.段表机制,在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项：(1)存取方式。(2)访问字段A。(3)修改位M。(4)存在位P。(5)增补位。(6)外存始址。,2.缺段中断机构,图 4-31 请求分段系统中的中断处理过程,3.地址变换机构,图 4-32 请求分段系统的地址变换过程,分段的共享与保护,1.共享段表,图 4-33 共享段表项,2.共享段的分配

37、与回收,1)共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作，以表明有两个进程共享该段。,2)共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。,3.分段保护,越界检查 2)存取控制检查 只读(2)只执行(3)读/写 3)环保护机构 一个程序可以访问驻留在相同环或较低特权环中的数据。一个程序可以调用驻留在相同环或较高特权环中的服务。,图 4-34 环保护机构,