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

《第四章存储器管理ppt课件.ppt》由会员分享，可在线阅读，更多相关《第四章存储器管理ppt课件.ppt（133页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图 4-1 对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存图 4-2 作业装入内存时的情况 LO A D 1,2500365LO A D 1,2500365100001100012500150005000250010000作 业 地 址 空 间内 存 空 间模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块在将这几个目标模块装配成一个装入模

2、块时，须解决以下两个问题： 对相对地址进行修改 变换外部调用符号n特点： 便于修改和更新 各个模块是分开存放的。 便于实现对目标模块的共享 很容易将一个模块连接到多个模块。n这种链接方式是将对某些模块的链接推迟到执行时才执行。n在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存， 把它链接到调用者模块上。n凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。连续分配方式连续分配方式单一连续分配单一连续分配n这是最简单的一种存储管理方式。n只能用于单用户、单任务的操作系统中。n采用这种

3、存储管理方式时，可把内存分为系统区和用户区两部分：n系统区仅提供给OS使用，通常是放在内存的低地址部分；n用户区是指除系统区以外的全部内存空间， 提供给用户使用。单一连续分配单一连续分配固定分区分配固定分区分配固定分区分配固定分区分配n划分分区的方法划分分区的方法 分区大小相等， 即使所有的内存分区大小相等。 缺点：缺乏灵活性。 优点： 用于利用一台计算机去控制多个相同对象的场合。 分区大小不等。 固定分区分配固定分区分配n内存分配内存分配n 为了便于内存分配，通常将分区按大小进行排为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项队，并为之建立一张分区使用表，其

4、中各表项包括每个分区的起始地址、大小及状态（已分包括每个分区的起始地址、大小及状态（已分配）。配）。固定分区分配固定分区分配图 4-4 固定分区使用表 固定分区分配固定分区分配动态分区分配动态分区分配分区分配中的数据结构分区分配中的数据结构 空闲分区表 空闲分区链分区分配中的数据结构分区分配中的数据结构空闲分区表分区分配中的数据结构分区分配中的数据结构n空闲分区链前向指针N20N 个字节可用后向指针N20分区分配算法分区分配算法 首次适应算法FF 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应算法分区分配操作n分配内存分配内存n u.size : 请求的分区大小请求的分区大小 n m.

5、size : 每个空闲分区大小每个空闲分区大小n size : 事先规定的不再切割的剩余分区的大小事先规定的不再切割的剩余分区的大小n回收内存回收内存分配内存从头开始查表检索完否？m.size u.size?m.size u.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN图 4-6 内存分配流程回收内存可重定位分区分配可重定位分区分配n动态重定位的引入动态重定位的引入n在连续分配方式中，必须把一个系统或用户程在连续分配方式中，必须把一个系统或用户程序装入一个连续的内存空间。序装入一个连续的内存空

6、间。n如果出现以下情况，该怎么办？如果出现以下情况，该怎么办？可重定位分区分配可重定位分区分配操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a) 紧凑前(b) 紧凑后可重定位分区分配可重定位分区分配n动态重定位的实现动态重定位的实现LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存图 4-9 动态重定位示意图可重定位分区分配可重定位分区分配n动态重定位分区分配

7、算法动态重定位分区分配算法n算法与动态分区分配算法基本上相同。算法与动态分区分配算法基本上相同。n差别：在这种分配算法中，增加了紧凑的功能，差别：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空间分区来满足需求通常，在找不到足够大的空间分区来满足需求时进行紧凑。时进行紧凑。n具体操作如下：具体操作如下：请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否动态重定位分区分配算法图 4-10 动态分区分配算法流程图 0407

8、0180512OS区域对换对换(Swapping) 对换的引入对换的引入 对换空间的管理对换空间的管理 进程的换出与换入进程的换出与换入对换对换(Swapping)n对换的引入对换的引入n所谓“对换”， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。对换对换(Swapping)n对换空间的管理对换空间的管理n为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用

9、空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。对换对换(Swapping)n进程的换出进程的换出n每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。 其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。对换对换(Swapping)n进程的换入进程的换入n系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程

10、，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。n页面与页表页面与页表n地址变化机构地址变化机构n* 两级或多级页表两级或多级页表页面与页表n页面页面 页面和物理块页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0块、1块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页

11、经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。页面与页表n页面 页面大小 在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B8 KB。页面与页表n地址结构地址结构分页地址中的地址结构如下： 3112110 对某特定机器，其地址结构是一

12、定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： MODLAdLAINTP页面与页表页面与页表n页表页表用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910地址变换机构n为了能将用户地址空间中的逻辑地址变换为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须为内存空间中的物理地址，在系统中必须设置地址变换机构。设置地址变换机构。n页内地址和物理地址是一一对应的。页内地址和物理地址是一一对应的。n通常页表存放在内存中，而页表在内存中通常页表存放在内存中，而页表在内存中始地址

13、和长度存放在始地址和长度存放在PCB中。中。n当调度程序调度到某进程时，才将以上两当调度程序调度到某进程时，才将以上两个数据调入到页表寄存器中。个数据调入到页表寄存器中。地址变换机构n基本的地址变换机构基本的地址变换机构页表寄存器页表始址页表长度页号(3)页内 地 址逻辑地址L越界中断1块号b页表页号012物理地址3图 4-12 分页系统的地址变换机构 地址变换机构地址变换机构n具有快表的地址变换具有快表的地址变换机构机构页表寄存器页表始址页表长度页号页内 地 址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址图 4-13 具有快表的地址变换机构 大小通常只存放16512个

14、页表项。*两级和多级页表两级和多级页表n现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用一个字节， 故每个进程仅仅其页表就要占用4 KB的内存空间，而且还要求是连续的。 n可以采用这样两个方法来解决这一问题：n采用离散分配方式来解决难以找到一块连续的大内存空间的问题：n 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。两级页表(Two-Leve

15、l Page Table)n逻辑地址结构可描述如下：101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页表14680121023内存空间外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址图 4-15 具有两级页表的地址变换机构 *多级页表多级页表 对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4 KB即212 B，那么还剩下52位， 假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能

16、有4096 G个页表项， 要占用16384 GB的连续内存空间。 必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。 对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。n引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 方便编程 信息共享 信息保护 动态增长 动态链接 分段系统的基本原理分段系统的基本原理n 在分段存储管理系统中，作业的地址空间在分段存储管理系统中，作业的地址空间被划分为若干个

17、段，每个段定义了一组逻被划分为若干个段，每个段定义了一组逻辑信息。辑信息。n每个段都从每个段都从0开始编址。开始编址。n段的长度由相应的逻辑信息组的长度决定。段的长度由相应的逻辑信息组的长度决定。n逻辑地址空间是二维的。逻辑地址空间是二维的。n段地址由段号和段内地址所组成。段地址由段号和段内地址所组成。分段系统的基本原理分段系统的基本原理n分段分段分段地址中的地址具有如下结构： 31 16 15 0分段系统的基本原理分段系统的基本原理n逻辑地址空间到物理地址空间的映射需要逻辑地址空间到物理地址空间的映射需要一张表格来实现即段表。一张表格来实现即段表。n系统中为每个进程创建系统中为每个进程创建-

18、“段表段表”。n段表存储在内存中。段表存储在内存中。n段表的始地址和段长度存放在段表的始地址和段长度存放在PCB中中 。分段系统的基本原理分段系统的基本原理n段表段表作业空间(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段长 基址段号(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表内存空间0123分段系统的基本原理分段系统的基本原理n地址变换机构控制寄存器段表始址段表长度2100段号 S越界1 K段长600段号01236 K4 K5002008 K9200

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

20、突出有点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。n在分页系统中 ，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。信息共享：示例信息共享：示例ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进 程 22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表分页管理方式分页管理方式editor进程1data 1进程2editordata 2段表段长 基址1608040240160

21、8040380editordata 1data 280240280380420图 4-19 分段系统中共享editor的示意图 段页式存储管理方式段页式存储管理方式04K8K12K15K16K子 程 序 段04K8K数 据 段04K8K10K12K(a)段 号 (S)段 内 页 号 (P)段 内 地 址 (W)(b)主 程 序 段段页式存储管理方式段页式存储管理方式图 4-21 利用段表和页表实现地址映射 段号 状态 页表大小 页表始址0111213041页号 状态存储块#0111213041操作系统主存页表段表段表大小 段表始址段表寄存器图 4-22 段页式系统中的地址变换机构 段表寄存器段

22、表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度Spdfd页表长度段表地址f越界越界段表段表页表页表虚拟存储器的基本概念虚拟存储器的基本概念n虚拟存储器的引入虚拟存储器的引入n虚拟存储器的实现方法虚拟存储器的实现方法n虚拟存储器的特征虚拟存储器的特征虚拟存储器的引入 常规存储器管理方式的特征常规存储器管理方式的特征: 一次性 驻留性虚拟存储器的引入n局部性原理局部性原理n早在1968年， Denning.P就曾指出：程序在执行时呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。虚拟存储

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

24、由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、 中、 小型机器和微型机中。虚拟存储器的实现方法虚拟存储器的实现方法分页请求系统分页请求系统 硬件支持硬件支持 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构； 缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存； 地址变换机构， 它同样是在纯分页地址变换机构的基础上发展形成的 实现请求分页的软件实现请求分页的软件虚拟存储器的实现方法虚拟存储器的

25、实现方法 虚拟存储器的特征：虚拟存储器的特征： 多次性多次性 对换性对换性 虚拟性虚拟性请求分页存储管理方式请求分页存储管理方式 请求分页中的硬件支持请求分页中的硬件支持 页表机制页表机制该页是否已调入内存请求分页存储管理方式请求分页存储管理方式请求分页中的硬件支持请求分页中的硬件支持 缺页中断机构缺页中断机构页面B：A：654321指令copy ATO B与一般中断相比，有着明显的区别： 在指令执行期间和处理中断信号。 一条指令在执行期间，可能产生多次缺页中断。请求分页存储管理方式请求分页存储管理方式缺页中断处理保留CPU 现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外

26、存OS 命令CPU 从外存读缺页启动I/O 硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU 检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是 地址表换机构地址表换机构内存分配策略和分配算法内存分配策略和分配算法 最小物理块数的确定最小物理块数的确定 物理块的分配策略物理块的分配策略 物理块分配算法物理块分配算法最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指

27、令的格式、 功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时， 也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。 固定分配局部置换(Fixed Allocation, Local Replacement) 可变分配全局置换(Variable Allocation, Global Replacement) 可变分配局部置换

28、(Variable Allocation, Local Replacemen物理块分配算法物理块分配算法 平均分配算法 按比例分配算法平均分配算法平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。 例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。 按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为S

29、i，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。 niiSS1mSSbii调页策略调页策略何时调入页面何时调入页面 预调页策略 请求调页策略调页策略调页策略 从何处调入页面从何处调入页面n在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。n每当发生缺页请求时，系统应从何处将缺页调入内存。从何处调入页面 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高

30、调页速度。为此，在进程运行前， 便须将与该进程有关的文件，从文件区拷贝到对换区。 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。 从何处调入页面 UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此， 某进程所请求的页面有可能已被其它进程

31、调入内存，此时也就无须再从对换区调入。页面置换算法页面置换算法n最佳置换算法最佳置换算法n先进先出置换算法先进先出置换算法n最近最久未使用最近最久未使用(LRU)置换算法置换算法nClock置换算法置换算法n其它置换算法其它置换算法 置换算法的好坏，将直接影响到系统的性能。 一个好的页面置换算法，应具有较低的页面更换频率。最佳置换算法n最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用

32、串：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予以淘汰。 引用率70770170122010320304243230321201201770101页框(物理块）203图 4-25 利用最佳页面置换算法时的置换图 先进先出置换算法引用率70770170122010323104430230321013201770201页框2304204230230127127011图 4-26 利用FIFO置换算法时的置换图 淘汰最先调入内

33、存的页面，即在内存中驻留时间最久的页面。淘汰最先调入内存的页面，即在内存中驻留时间最久的页面。缺点：缺点： 该算法与进程实际运行的规律不相适应，因为在进程中，该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问。有些页面经常被访问。 它所依据的条件是各个页面调入内存的它所依据的条件是各个页面调入内存的时间，而页面调入的先后不能反映页面的使用情况。时间，而页面调入的先后不能反映页面的使用情况。最近最久未使用(LRU)置换算法图 4-27 LRU页面置换算法 引用率70770170122010320304403230321132201710701页框402432032102最近最久

34、未使用(LRU)置换算法最近最久未使用(LRU)置换算法LRU置换算法的硬件支持置换算法的硬件支持 寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0 最近最久未使用(LRU)置换算法图 4-28 某进程具有8个页面时的LRU访问情况 栈栈 图 4-29 用栈保存当前使用页面时栈的变化情况 4474707407047170410174010741210742120741210742621076 每当进程访问页面时，便将该页面的页号从栈中移出，每当进程访问页面时，便将该页面的页号从栈中移出，将它压入栈

35、顶。将它压入栈顶。Clock置换算法Clock置换算法1. 简单的简单的Clock置换算法（最近未使用算法置换算法（最近未使用算法NRU） 图 4-30 简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针改进型改进型Clock置换算法置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。

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

37、找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。 其它置换算法其它置换算法 最少使用(LFU： Least Frequently Used)置换算法 页面缓冲算法(PBA： Page Buffering Algorithm) 在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。请求分段存储管理方式请求分段存储管理方式请求分段存储管理方式请求分段存储管理方式n请求分段中的硬件支持请求分段中的硬件支持n 段表机制段表机制n 缺页中断机构缺页中断机构n 地址变换机

38、构地址变换机构请求分段中的硬件支持1. 段表机制段表机制 在段表项中， 除了段名(号)、 段长、 段在内存中的起始地址外， 还增加了以下诸项： (1) 存取方式。 (2) 访问字段A。 (3) 修改位M。 (4) 存在位P。 (5) 增补位。 (6) 外存始址。 2. 缺段中断机构缺段中断机构 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是图图 4-31 请求分段系统中的中断处理过程请求分段系统中的中断处理过程3. 地址变换机构地址变换机构 访

39、问sww段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位1形成访问主存地址(A) (主存始址) (位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否图 4-32 请求分段系统的地址变换过程分段的共享与保护分段的共享与保护 1. 共享段表共享段表 图 4-33 共享段表项 段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制共享段表2. 共享段的分配与回收共享段的分配与回收 1) 共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相

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