操作系统2002--存储管理(2)

1、五、分段存储管理 1、基本原理 引入分段存储管理方式，主要是为了满足用户的下引入分段存储管理方式，主要是为了满足用户的下述要求：述要求：q 方便编程方便编程q 分段共享分段共享q 分段保护分段保护q 动态链接动态链接q 动态增长动态增长A A、分段、分段 在分段存储管理方式中，作业的地址空间被划在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个分为若干个段，每个段定义了一组逻辑信息。每个段的逻辑地址都是从段的逻辑地址都是从0 0开始。段内地址是连续的，开始。段内地址是连续的，但段与段之间不一定是连续的。但段与段之间不一定是连续的。 分段的基本原理分段的基本原理

2、 子程子程段序段序数据栈数据栈符号表符号表主程主程序段序段系统系统函数函数作业的逻辑地址由段号与段内地址所组成，结构如下：作业的逻辑地址由段号与段内地址所组成，结构如下： 段号段号段内地址段内地址3116 150如果机器的地址有如果机器的地址有m m位，其中段内地址占位，其中段内地址占n n位，则每位，则每个作业最多可分为个作业最多可分为2 2(m-n) (m-n) 个段。个段。 B B、段表、段表 为使程序能够正常运行，亦即能从物理内存中为使程序能够正常运行，亦即能从物理内存中找出每个逻辑段所对应的位置，应象分页系统那样，找出每个逻辑段所对应的位置，应象分页系统那样，在系统中为每个作业建立一

3、张段的映射表，简称段在系统中为每个作业建立一张段的映射表，简称段表。在配置了段表后，程序在执行过程中可通过查表。在配置了段表后，程序在执行过程中可通过查找段表，找到每个段所对应的内存区找段表，找到每个段所对应的内存区。 子程子程段序段序数据栈数据栈符号表符号表主程主程序段序段系统系统函数函数段表段表段长段长基址基址段号段号012342 2、主存空间的分配与去配、主存空间的分配与去配 段式存储管理分配主存空间的方法及回收存储段式存储管理分配主存空间的方法及回收存储空间的方法与可变分区管理方式所采用的方法相同空间的方法与可变分区管理方式所采用的方法相同。 3 3、地址转换与存储保护、地址转换与存储

4、保护 地址变换机构和变换过程地址变换机构和变换过程 段表始址段表始址段表长度段表长度1K6K6004K5008K2009200位移量位移量段号段号段号段号01232100+控制寄存器控制寄存器8292基址基址段长段长越界越界逻辑地址逻辑地址物理地址物理地址主存主存例题例题: :某分段管理中采用下表所示的段表：某分段管理中采用下表所示的段表： 段号段号段的长度段的长度段的起段的起始地址始地址01234660141005809621933309012371954 给定段号和段内地址，说明分段管理中的地址变给定段号和段内地址，说明分段管理中的地址变 换过程；换过程； 计算计算00，430430，11

5、，1010，22，500500，33，400400， 44，2020，55，100 100 的内存地址，其中方括号内的内存地址，其中方括号内 的第一个元素是段号，第二个元素是段内地址；的第一个元素是段号，第二个元素是段内地址； 说明存取主存的一条指令或数据至少要访问几次说明存取主存的一条指令或数据至少要访问几次 内存。内存。解答：解答：00，430 430 的物理地址是：的物理地址是：219+430=649219+430=64911，10 10 的物理地址是：的物理地址是：3300+10=33103300+10=331022，500 500 的物理地址是：的物理地址是：500100500100

6、，越界，越界33，400 400 的物理地址是：的物理地址是：1237+400=16371237+400=163744，20 20 的物理地址是：的物理地址是：1952+20=19721952+20=197255，100 100 的物理地址是：的物理地址是：5454，段号越界，段号越界存取主存的一条指令或数据至少要访问存取主存的一条指令或数据至少要访问2 2次内存次内存段号段号段的长度段的长度段的起始段的起始地址地址01234660141005809621933309012371954分段的共享分段的共享 与分页系统相比较，分段系统对段的保护更加简单易行。与分页系统相比较，分段系统对段的保护更

7、加简单易行。 假定有一文本编辑程序，程序区假定有一文本编辑程序，程序区500K500K，数据区，数据区100K100K，两个，两个用户作业同时进行文本编辑，对于分页系统，假定每个页面大用户作业同时进行文本编辑，对于分页系统，假定每个页面大小为小为1K1K。对于分页系统，每个用户作业需建立一个页表，其中，。对于分页系统，每个用户作业需建立一个页表，其中，500500个页表项对应程序区，个页表项对应程序区，100100个页表项对应数据区。而如果采个页表项对应数据区。而如果采用分段系统，则每个段表只需两个段表项，系统的开销要小的用分段系统，则每个段表只需两个段表项，系统的开销要小的多，而且管理也会更

8、加简单。多，而且管理也会更加简单。 程序段程序段数据段数据段程序程序数据数据页表页表段表段表分页和分段的主要区别分页和分段的主要区别 1 1、页是信息的物理单位，而段是信息的逻辑单位；、页是信息的物理单位，而段是信息的逻辑单位；2 2、页的大小固定且由系统决定，而段的长度不固定，、页的大小固定且由系统决定，而段的长度不固定， 决定于用户编写的程序；决定于用户编写的程序；3 3、分页的作业地址空间是一维的，而分段的地址空间、分页的作业地址空间是一维的，而分段的地址空间 是二维的。是二维的。4 4、分段系统便于动态链接，存储保护，便于增长、修、分段系统便于动态链接，存储保护，便于增长、修 改和信息

9、共享。改和信息共享。4 4、可分页的段式存储管理、可分页的段式存储管理 A A、基本原理、基本原理 先将作业分为若干个段，再把每个段划分为若干页。先将作业分为若干个段，再把每个段划分为若干页。 段号段号页内地址页内地址段内页号段内页号地址结构地址结构段号段号状态状态页表页表大小大小页表页表始址始址段表控制寄存器段表控制寄存器0 0号段页表号段页表1 1号段页表号段页表主存主存B B、地址变换过程、地址变换过程 再获得逻辑地址后，根据段表的控制寄存器，得到段表的首再获得逻辑地址后，根据段表的控制寄存器，得到段表的首 地址；地址； 首先利用段号，将它与段表长度进行比较，如段号大于段表首先利用段号，

10、将它与段表长度进行比较，如段号大于段表 长度，表示段号越界；长度，表示段号越界； 根据段号求得对应该段的页表的首地址；根据段号求得对应该段的页表的首地址； 再根据段内页号得到该页对应的物理块的地址；再根据段内页号得到该页对应的物理块的地址； 最后将物理块的首地址和页内地址相加构成最后的物理地址。最后将物理块的首地址和页内地址相加构成最后的物理地址。 1 1、基本概念、基本概念 虚拟存储器虚拟存储器 为用户提供一种不受物理存储器结构和容量限为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储制的存储器的技术称为虚拟存储器，或称虚拟存储技术。技术。 它是用户编程时所

11、使用的一种用户思维中的存它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空储器，它可以是任何结构（一维线性空间、二维空间、乃至间、乃至n n维空间），并没有容量的限制。维空间），并没有容量的限制。 现代计算机操作系统都采用了这种技术，使得现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。极大地方便了用户。 虚拟存储器需要大容量的外存储器的支持，或虚拟存储器需要大容量的外存储器的支持，或称物资基础。称物资基础。五、虚拟存储器五、虚拟存储器 2 2、虚拟存储器的工作原理

12、、虚拟存储器的工作原理 1 1、局部性原理、局部性原理 程序执行时的局部性规律：程序执行时的局部性规律： 程序在执行时，除了少部分的转移和过程调用指程序在执行时，除了少部分的转移和过程调用指 令外，在大多数情况下，仍然是顺序执行的。令外，在大多数情况下，仍然是顺序执行的。 过程调用将会使程序的执行轨迹从一部分内存区过程调用将会使程序的执行轨迹从一部分内存区 域转到另一部分区域，但在大多数情况下，过程域转到另一部分区域，但在大多数情况下，过程 调用的深度都不超过调用的深度都不超过5 5。 程序中存在许多循环结构，它们虽由少数指令构程序中存在许多循环结构，它们虽由少数指令构 成，但可以多次执行成，

13、但可以多次执行 程序中的许多数据结构，如数组，在被操作时，程序中的许多数据结构，如数组，在被操作时， 往往局限于一个很小的范围内。往往局限于一个很小的范围内。 局部性原理表现在：局部性原理表现在： 时间局限性时间局限性 是指某个位置最近被访问了，那么往往很快又要是指某个位置最近被访问了，那么往往很快又要被再次访问。被再次访问。 空间局限性空间局限性 是指一旦某个位置最近被访问了，那么它附近的是指一旦某个位置最近被访问了，那么它附近的位置也要被访问。位置也要被访问。 3 3、虚拟存储器的定义、虚拟存储器的定义 所谓虚拟存储器，是指仅把作业的一部分装入内所谓虚拟存储器，是指仅把作业的一部分装入内存

14、便可运行作业的存储器系统。存便可运行作业的存储器系统。 4 4、虚拟存储器的实现方式：、虚拟存储器的实现方式：q 页式虚拟存贮页式虚拟存贮q 段式虚拟存储段式虚拟存储 页式虚拟存储页式虚拟存储 它是在分页系统的基础上，增加了请求调页功它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储系统。能、页面置换功能所形成的虚拟存储系统。 系统必须提供的硬件支持：系统必须提供的硬件支持： 请求分页的页表机构请求分页的页表机构 缺页中断机构缺页中断机构 地址变换机构地址变换机构 段式虚拟存储段式虚拟存储 这是在分段系统的基础上，增加了请求调段功这是在分段系统的基础上，增加了请求调段功能

15、及分段置换功能后，所形成的段式虚拟存储系统。能及分段置换功能后，所形成的段式虚拟存储系统。 系统必须提供的硬件支持：系统必须提供的硬件支持： 请求分段的段表机构请求分段的段表机构 缺段中断机构缺段中断机构 地址变换机构地址变换机构虚拟存储器的特征：虚拟存储器的特征： v离散性离散性 指内存分配时采用离散分配方式指内存分配时采用离散分配方式v多次性多次性 指一个作业被分成多次的调入内存运行指一个作业被分成多次的调入内存运行v对换性对换性 指允许在作业运行过程中在内存和磁盘指允许在作业运行过程中在内存和磁盘 间换进、换出间换进、换出v虚拟性虚拟性 指能够从逻辑上扩充内存容量。指能够从逻辑上扩充内存

16、容量。 1 1、问题的提出、问题的提出 在页式存储管理提高了内存的利用效率，在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术人们提出请求分页存储管理技术页式虚拟存储管理页式虚拟存储管理 需要解决的问题需要解决的问题 如何发现执行的程序或访问的数据不在内存；如何发现

17、执行的程序或访问的数据不在内存； 程序或数据什么时候调入内存，调入策略；程序或数据什么时候调入内存，调入策略； 当一些页调入内存时，内存没有空闲内存时，当一些页调入内存时，内存没有空闲内存时， 将淘汰哪些页，采用什么淘汰策略。将淘汰哪些页，采用什么淘汰策略。2 2、基本原理、基本原理 页式虚拟存储中的页表项组成页式虚拟存储中的页表项组成： 页号页号物理块号物理块号状态位状态位访问字段访问字段修改位修改位外存地址外存地址状态位状态位：用于指示该页是否已调入内存；：用于指示该页是否已调入内存；访问字段访问字段：用于记录该页在一段时间内被访问的：用于记录该页在一段时间内被访问的 次数；次数；修改位修

18、改位：表示该页在调入内存后是否被修改过；：表示该页在调入内存后是否被修改过；外存地址外存地址：用于指出该页在外存上的地址。：用于指出该页在外存上的地址。3 3、页式虚拟存储中的缺页中断机构、页式虚拟存储中的缺页中断机构缺页中断与一般中断的区别：缺页中断与一般中断的区别：v在指令执行期间产生和处理中断信号在指令执行期间产生和处理中断信号v在一条指令执行期间，可能产生多次中断。在一条指令执行期间，可能产生多次中断。 COPY ATO BAB4 4、页式虚拟存储中的地址变换机构、页式虚拟存储中的地址变换机构 在分页系统地址变化机构的基础上，再增加在分页系统地址变化机构的基础上，再增加某些虚拟存储器的

19、功能而形成的。某些虚拟存储器的功能而形成的。 地址变换过程地址变换过程 页号页号页表长度页表长度越界中断越界中断开开 始始CPU检索快表检索快表页表项在快表中页表项在快表中访问页表访问页表页在内存页在内存修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址地址变换结束地址变换结束内存满否内存满否该页被修改过该页被修改过将一页从外存换入内存将一页从外存换入内存启动启动I/O硬件硬件CPU从外存读缺页从外存读缺页将该页写回外存将该页写回外存修改页表修改页表选择一页换出选择一页换出从外存中找到缺页从外存中找到缺页保留保留CPU现场现场缺页中断处理缺页中断处理程序请求访问一页程

20、序请求访问一页是是否否是是否否否否是是否否是是否否是是产生缺页中产生缺页中断，请求调页断，请求调页5 5、页面调度、页面调度 主存的分配与置换策略主存的分配与置换策略固定分配局部置换：基于进程的类型（交互型或批固定分配局部置换：基于进程的类型（交互型或批处理型），或根据程序员、系统管理员的建议，为处理型），或根据程序员、系统管理员的建议，为进程分配一固定页数的内存空间。进程分配一固定页数的内存空间。可变分配全局置换：先为系统中的每一个进程分配可变分配全局置换：先为系统中的每一个进程分配一定数目的物理块，一定数目的物理块，OSOS本身保留一个空闲物理块队本身保留一个空闲物理块队列。当某进程发现缺

21、页时，由系统从空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个进行分配。列中取出一个进行分配。可变分配局部置换：同样基于进程的类型或根据程可变分配局部置换：同样基于进程的类型或根据程序员的要求，为每个进程分配一定数量的内存空间。序员的要求，为每个进程分配一定数量的内存空间。当某进程发生缺页时，只允许从该进程在内存的页当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运面中选出一页换出，这样就不会影响其它进程的运行。行。 6 6、分配算法、分配算法 在采用固定分配算法时，如何将系统中可供分配在采用固定分配算法时，如何将系统中可供分配的所有物

22、理块分配给各个进程，可采取下述方法：的所有物理块分配给各个进程，可采取下述方法：平均分配算法平均分配算法：将系统中所有可供分配的物理块，平：将系统中所有可供分配的物理块，平均分配各个进程。均分配各个进程。按比例分配算法按比例分配算法：根据进程的大小按比例分配物理块。：根据进程的大小按比例分配物理块。例如：如果各进程页面数的总和是：例如：如果各进程页面数的总和是： niiSS1同时，假定系统中可用物理块总数为同时，假定系统中可用物理块总数为m m， 则每个进则每个进程所能分到的物理块程所能分到的物理块b bi i为：为： mSSbii考虑优先权的分配算法考虑优先权的分配算法：把内存中可供分配的物

23、理块分：把内存中可供分配的物理块分成两个部分：一部分按比例分配给各个进程；另一部分成两个部分：一部分按比例分配给各个进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。配给各进程。 7 7、页面调入策略、页面调入策略 何时调入页面：何时调入页面：预调页策略：将那些预计在不久之后便会被访问的程序预调页策略：将那些预计在不久之后便会被访问的程序和数据所在的页面，预先调入内存。和数据所在的页面，预先调入内存。请求调页策略：当发现所需要的页面不再内存时，立即请求调页策略：当发现所需要的页面不再内存时，立即提出请求，由系统将所需页面调

24、入内存。提出请求，由系统将所需页面调入内存。 从何处调入页面从何处调入页面对于不同的系统，所采用的方法也不相同，可分成三种对于不同的系统，所采用的方法也不相同，可分成三种情况：情况： 如果系统拥有足够的内存空间，可以全部从对换区调入页面，如果系统拥有足够的内存空间，可以全部从对换区调入页面，以提高调页速度。以提高调页速度。 如果系统缺少足够的内存空间，则可以对不被修改的部分，如果系统缺少足够的内存空间，则可以对不被修改的部分，直接从文件区调入；对于那些可能被修改的部分，将它们换出直接从文件区调入；对于那些可能被修改的部分，将它们换出时，便需调到对换区，以后需要时再从对换区调入。时，便需调到对换

25、区，以后需要时再从对换区调入。 UNIXUNIX方式：凡是未运行过的页面，都从文件区调入，对于方式：凡是未运行过的页面，都从文件区调入，对于曾经运行过而又被换出的页面，由于是放在对换区的，因此在曾经运行过而又被换出的页面，由于是放在对换区的，因此在下次调入时，应从对换区调入。下次调入时，应从对换区调入。 常用到的几个术语：常用到的几个术语：抖动：刚刚被淘汰出去的页面，不久又被调入主存，这种现象，抖动：刚刚被淘汰出去的页面，不久又被调入主存，这种现象， 称为抖动（也称为颠簸）。称为抖动（也称为颠簸）。页面走向：用引用串来表示。页面走向：用引用串来表示。页面失效率：缺页中断次数占全部访问页面数的百

26、分比，即：页面失效率：缺页中断次数占全部访问页面数的百分比，即： 失效率失效率 = = （失效次数（失效次数 / / 访问页面总数）访问页面总数） 100% 100%在讨论页面淘汰算法前假设：在讨论页面淘汰算法前假设：引用串：对进程逻辑地址空间的访问所涉及到的页引用串：对进程逻辑地址空间的访问所涉及到的页 面号序列。面号序列。仅考虑页面号，不需考虑其页内位移。仅考虑页面号，不需考虑其页内位移。如连续两次对页面如连续两次对页面P P进行访问，则至少第二次访问不进行访问，则至少第二次访问不 会产生缺页中断。会产生缺页中断。随着可用块数量的增加，产生缺页中断的次数将会随着可用块数量的增加，产生缺页中

27、断的次数将会 减少。减少。 8 8、页面置换算法、页面置换算法v先进先出页面置换算法先进先出页面置换算法 该算法总是在淘汰最先进入内存的页面，即选该算法总是在淘汰最先进入内存的页面，即选择在内存中驻留最久的页面予以淘汰，即先进入主择在内存中驻留最久的页面予以淘汰，即先进入主存的页，先退出储存。存的页，先退出储存。FIFOFIFO（3 3块）块） 引用串引用串7 0 1 2 0 3 0 4 2 3 0 32 1 2 01 7 0 1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7 0 0 0 3 3 3 2 2 2 1 1 1 0 0 1 1 1 0 0 0 3 3 3 2 2 2

28、1发生置换发生置换 共进行了共进行了1212次页面置换次页面置换 假定系统分配给某进程假定系统分配给某进程3 3个存储块，并考虑如下引用个存储块，并考虑如下引用串：串： 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 FIFOFIFO（4 4块）块） 共进行了共进行了6 6次页面置换次页面置换 引用串引用串70120304230321201701 7012 3 4 0 12 7 701 2 3 4 01 2 70 1 2 3 40 1 7 0 1 2 34 0 发生置换发生置换 例题

29、：在请求分页存储管理中，若采用先进先出页面淘汰算法，例题：在请求分页存储管理中，若采用先进先出页面淘汰算法，会产生一种奇怪的现象：分配给作业的物理块越多，作业执行会产生一种奇怪的现象：分配给作业的物理块越多，作业执行时的缺页率反而升高。试举一例说明这种现象。时的缺页率反而升高。试举一例说明这种现象。 解答：若在作业运行过程中地址访问的引用串为：解答：若在作业运行过程中地址访问的引用串为：4 4，3 3，2 2，1 1，4 4，3 3，5 5，4 4，3 3，2 2，1 1，5 5。下面是为作业分配。下面是为作业分配3 3个和个和4 4个物理块个物理块时的页面访问过程：时的页面访问过程： 引用串

30、引用串432143543215 4443214-3 5- 332143-52- 21435-21-缺页缺页 FIFOFIFO（3 3块）块） FIFOFIFO（4 4块）块） 引用串引用串432143543215 4444-3215 43 333-215432 22-154321 1 - -5 43 2 15缺页缺页 可见，可见，3 3块时缺页中断次数为块时缺页中断次数为9 9，而，而4 4块时为块时为1010v最佳页面置换算法最佳页面置换算法 所选择的被淘汰的页面，将是以后永不被使用的，或者所选择的被淘汰的页面，将是以后永不被使用的，或者是在最长时间内不再被访问的页面。是在最长时间内不再被访

31、问的页面。 OPTOPT（3 3块）块） 引用串引用串70120304230321201701 7772 2 2 2 2 7 700 0 4 0 0 0 11 3 3 3 1 1 发生置换发生置换 共进行了共进行了6 6次页面置换。次页面置换。 v最近最久未使用置换算法最近最久未使用置换算法 选择最近最久未使用过的页面进行淘汰，是用作业执选择最近最久未使用过的页面进行淘汰，是用作业执行过程中过去的页面踪迹来推测未来的行为。行过程中过去的页面踪迹来推测未来的行为。 LRULRU（3 3块）块） 引用串引用串70120304230321201701 7772 2 4440 1 1 1 000 0

32、0033 3 0 0 11 3 3222 2 2 7 发生置换发生置换 共发生共发生9 9次置换次置换 例题：近代计算机系统常采用请求页式存储管理方案来管理例题：近代计算机系统常采用请求页式存储管理方案来管理自己的主存。自己的主存。 用简图说明它的地址变换方法；用简图说明它的地址变换方法； 假定某假定某作业作业J J所涉及的页面依次为：所涉及的页面依次为：0 0，1 1，0 0，2 2，0 0，1 1，0 0，1 1，3 3，0 0，并已知主存中有并已知主存中有3 3个可供作业个可供作业J J使用的空闲存储块。试说明采使用的空闲存储块。试说明采用用FIFOFIFO和和LRULRU两种不同淘汰算

33、法时，缺页中断率各是多少？两种不同淘汰算法时，缺页中断率各是多少？ FIFOFIFO（3 3块）块） 引用串引用串01020101030 00-0-1 2 1-1-23 2-30缺页缺页 缺页中断次数为缺页中断次数为5 5次次 LRULRU（3 3块）块） 引用串引用串01020101030 00-0-0 - 1-1-1- -2-3-缺页缺页 缺页中断次数为缺页中断次数为4 4次次 注意，计算缺页次数和缺页率时，要注意初始时刻所注意，计算缺页次数和缺页率时，要注意初始时刻所有物理块为空。此时，虽然不发生页面的淘汰，但却需要有物理块为空。此时，虽然不发生页面的淘汰，但却需要引起缺页中断。引起缺页

34、中断。 vCLOCKCLOCK置换算法置换算法 简单的简单的CLOCKCLOCK置换算法置换算法 为每页设置一个访问位，将内存中所有被使用为每页设置一个访问位，将内存中所有被使用的页面通过链接指针链成一个循环队列。当某页被的页面通过链接指针链成一个循环队列。当某页被访问时，其访问位被置访问时，其访问位被置1 1。置换算法再选择一页被淘。置换算法再选择一页被淘汰时，只需按链查找，如果检查到链中的某页访问汰时，只需按链查找，如果检查到链中的某页访问位是位是0 0，则选择该页换出，若为，则选择该页换出，若为1 1，则重新将它置为，则重新将它置为0 0，然后检查下一页然后检查下一页。块号块号页号页号访

35、问位访问位指针指针0 1 240 3 421 5 650 711 队首指针队首指针页面访问页面访问位为位为0置页面访置页面访问位为问位为0入口入口选择该页面淘汰选择该页面淘汰是是否否查询指针前进一查询指针前进一步，指向下一表目步，指向下一表目返回返回 改进的改进的CLOCKCLOCK置换算法置换算法 除了考虑页面的使用情况外，还考虑置换代价，除了考虑页面的使用情况外，还考虑置换代价，即同时检查访问位即同时检查访问位A A和修改位和修改位M M。1 1类类 A=0A=0，M=0M=0，表示该页最近既未被访问，也未，表示该页最近既未被访问，也未 被修改，是最佳淘汰页；被修改，是最佳淘汰页；2 2类

36、类 A=0A=0，M=1M=1，表示该页最近既未被访问，但已，表示该页最近既未被访问，但已 被修改，并不是很好的淘汰页；被修改，并不是很好的淘汰页；3 3类类 A=1A=1，M=0M=0，最近已被访问，但未被修改，该，最近已被访问，但未被修改，该 页有可能再被访问；页有可能再被访问；4 4类类 A=1A=1，M=1M=1，最近已被访问，也被修改，该页，最近已被访问，也被修改，该页 有可能再被访问；有可能再被访问；改进型改进型CLOCKCLOCK算法的执行过程：算法的执行过程：第一步，从指针所指示的当前位置开始，扫描循第一步，从指针所指示的当前位置开始，扫描循环队列，寻找环队列，寻找A=0A=0

37、且且M=0M=0的页面，如找到，则淘汰的页面，如找到，则淘汰之。在这遍扫描中不改变访问位之。在这遍扫描中不改变访问位A A。第二步，如果第一步失败，则开始第二遍扫描，第二步，如果第一步失败，则开始第二遍扫描，寻找寻找A=0A=0且且M=1M=1的页面，将所遇到的第一个这样的的页面，将所遇到的第一个这样的页面作为淘汰页，在此遍扫描中将所有经过的页页面作为淘汰页，在此遍扫描中将所有经过的页面的访问位置为面的访问位置为0 0。第三步，如果第二步也没有找到所要淘汰的页面，第三步，如果第二步也没有找到所要淘汰的页面，则将指针返回到开始的位置，并将所有页面的访则将指针返回到开始的位置，并将所有页面的访问位

38、置为问位置为0 0。然后重复第一步。然后重复第一步。9 9、缺页中断率、缺页中断率 假定，出现缺页的概率为假定，出现缺页的概率为p p，主存的有效访问时间为，主存的有效访问时间为MAMA，则，则页式虚拟存储管理的有效访问时间：页式虚拟存储管理的有效访问时间： 有效访问时间有效访问时间 = = （1 1p p）MAMAp p缺页中断时间缺页中断时间其中，缺页中断时间主要由三部分组成：其中，缺页中断时间主要由三部分组成：q缺页中断服务时间缺页中断服务时间q将缺页读入的时间将缺页读入的时间q作业重新执行时间作业重新执行时间 可见，有效访问时间正比于缺页率。可见，有效访问时间正比于缺页率。 影响缺页中

39、断率的因素：影响缺页中断率的因素： 分配给作业的的物理块数：一般地说，分配给作业的物理块数越分配给作业的的物理块数：一般地说，分配给作业的物理块数越多，则缺页中断率越低；多，则缺页中断率越低；页面的大小：页面越大，装入页面的信息量就越多，越可能降低页面的大小：页面越大，装入页面的信息量就越多，越可能降低缺页中断率；缺页中断率；程序的编制方法：程序编制的方法不同，对缺页中断的次数有很程序的编制方法：程序编制的方法不同，对缺页中断的次数有很大的影响；大的影响；页面的调度算法：页面的调度算法对缺页中断率的影响也很大。页面的调度算法：页面的调度算法对缺页中断率的影响也很大。 例子：例子： 设有二维数组设有二维数组 Var A: array1128 of array1128 of integer;在一个页式虚拟存储系统中，采用在一个页式虚拟存储系统中，采用LRULRU页面淘汰算法，页面淘汰算法，一个进程有一个进程有2 2页内存空间，每页可以存放页内存空间，每页可以存放128128个整数。个整数。其中第一页存放程序，且假定程序已经在内存。请分其中第一页存放程序，且假定程序已经在内存。请分别就下面程序别就下面程序A A和和B B的执行过程计算缺页次数。的执行过程计算缺页次数。 程序程序Afor i:=1 to 128 do for j:=1 to 128 do