3.5虚拟存储技术

《3.5虚拟存储技术》由会员分享，可在线阅读，更多相关《3.5虚拟存储技术（107页珍藏版）》请在金锄头文库上搜索。

1、3.5虚拟存储器管理 1为什么要引入虚拟存储器?实存管理：必须为进程分配足够的空间，实存管理：必须为进程分配足够的空间，装入全部信息，即使对换，也是针对整个装入全部信息，即使对换，也是针对整个进程（进程（一次性，驻留性一次性，驻留性）存在问题：进程运行时不用的，或暂时不存在问题：进程运行时不用的，或暂时不用的，或某种条件下才用的程序和数据，用的，或某种条件下才用的程序和数据，全部驻留于主存是对宝贵的存储资源的浪全部驻留于主存是对宝贵的存储资源的浪费；主存资源不够用怎么办？费；主存资源不够用怎么办？解决方法：部分装入，部分替换解决方法：部分装入，部分替换2部分装入：部分装入：不必装入进程的全部信

2、息，仅将当前不必装入进程的全部信息，仅将当前使用部分先装入主存，其余部分存放在磁盘中，使用部分先装入主存，其余部分存放在磁盘中，待使用时系统自动将其装进来。当进程所访问的待使用时系统自动将其装进来。当进程所访问的程序和数据在主存时，可顺利执行；如果不在主程序和数据在主存时，可顺利执行；如果不在主存，系统自动将这部分信息从外存装入内存（请存，系统自动将这部分信息从外存装入内存（请求调入功能）求调入功能）部分替换：部分替换：如果没有足够的空闲物理空间，便把如果没有足够的空闲物理空间，便把主存中暂时不用的信息移至磁盘（页面置换功能）主存中暂时不用的信息移至磁盘（页面置换功能）3通过部分装入和部分替换

3、：通过部分装入和部分替换：当主存空间小于进程的需要量时，进程也能运行；当主存空间小于进程的需要量时，进程也能运行；当多个进程的总长超出主存总容量时，也可将进当多个进程的总长超出主存总容量时，也可将进程全部装入主存，实现多道程序运行程全部装入主存，实现多道程序运行所有这些所有这些“部分换入换出部分换入换出”对用户完全是透明的，对用户完全是透明的，用户编程时不必考虑物理空间的实际容量，允许用户编程时不必考虑物理空间的实际容量，允许用户的逻辑地址空间大于主存物理地址空间，用用户的逻辑地址空间大于主存物理地址空间，用户感觉到的是比实际物理内存大的多的主存户感觉到的是比实际物理内存大的多的主存 虚拟存储

4、器虚拟存储器4虚拟存储技术的思想虚拟存储技术的思想总结：将外存作为内存的扩充，进程运行总结：将外存作为内存的扩充，进程运行不需要将进程的全部信息放入内存，将暂不需要将进程的全部信息放入内存，将暂时将不运行的进程信息放在外存，通过内时将不运行的进程信息放在外存，通过内存与外存之间的对换，使系统逐步将进程存与外存之间的对换，使系统逐步将进程信息放入内存，最终达到能够运行整个进信息放入内存，最终达到能够运行整个进程，从逻辑上扩充内存的目的。程，从逻辑上扩充内存的目的。5虚拟内存实现基础：虚拟内存实现基础： 局部性原理局部性原理早在早在1968年，年， Denning.P就曾指出：就曾指出： (1)

5、顺序性：顺序性：程序执行时，程序执行时， 除了少部分的转移和过程除了少部分的转移和过程调用指令外，调用指令外， 在大多数情况下仍是顺序执行的。在大多数情况下仍是顺序执行的。 (2) 局限性：局限性：过程调用将会使程序的执行轨迹由一部分过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，区域转至另一部分区域， 但经研究看出，过程调用的但经研究看出，过程调用的深度在大多数情况下都不超过深度在大多数情况下都不超过5。程序中还包括许多对。程序中还包括许多对数据结构的处理，数据结构的处理， 如对数组进行操作，如对数组进行操作， 它们往往都局它们往往都局限于很小的范围内。限于很小的范围内。 (3)

6、多次性：多次性：程序中存在许多循环结构，程序中存在许多循环结构， 这些虽然只由这些虽然只由少数指令构成，少数指令构成， 但是它们将多次执行。但是它们将多次执行。 (4) 独立性：独立性：程序中有些部分彼此互斥，不是每次运行程序中有些部分彼此互斥，不是每次运行都用到都用到6程序局部性原理：在一段时间内一个程序程序局部性原理：在一段时间内一个程序的执行往往呈现出高度的局部性（聚集成的执行往往呈现出高度的局部性（聚集成群），表现在时间与空间两方面群），表现在时间与空间两方面（一）时间局部性：（一）时间局部性： 一条指令被执行了，则在不久的将来它可一条指令被执行了，则在不久的将来它可能再被执行（指令在

7、一定时间执行）能再被执行（指令在一定时间执行）（二）空间局部性：（二）空间局部性： 若某一存储单元被使用，则在一定时间若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用内，与该存储单元相邻的单元可能被使用（程序使用一定的空间）（程序使用一定的空间）虚拟内存实现基础： 局部性原理7虚拟存储器的定义虚拟存储器的定义 在具有层次结构存储器的计算机系统中，在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换（单位是页自动实现部分装入和部分替换（单位是页或段）功能，或段）功能，能从逻辑上为用户提供一个能从逻辑上为用户提供一个比物理主存容量大的多的、可寻址的比物理主存容量大的

8、多的、可寻址的“主主存储器存储器”，对用户隐蔽了可用物理存储器，对用户隐蔽了可用物理存储器的容量和具体操作细节的容量和具体操作细节。8虚拟存储器的组织形式虚拟存储器的组织形式硬盘的这部分特殊区域称作对换区硬盘的这部分特殊区域称作对换区9虚拟存储器相关注意事项虚拟存储器相关注意事项支持虚存的物质基础：一定的主存，存放正在支持虚存的物质基础：一定的主存，存放正在运行的一部分信息；一部分外存，作为主存的运行的一部分信息；一部分外存，作为主存的补充；地址变换机构，以实现程序的虚地址向补充；地址变换机构，以实现程序的虚地址向实地址的转换实地址的转换虚拟存储器的容量（即给进程提供的逻辑地址虚拟存储器的容量

9、（即给进程提供的逻辑地址空间）由空间）由CPU的地址长度决定，与实际内存的的地址长度决定，与实际内存的大小没有关系大小没有关系例如：如果计算机系统的地址为例如：如果计算机系统的地址为3232位，则可寻位，则可寻址的范围为址的范围为0 04G4G；如果计算机系统的地址为；如果计算机系统的地址为2020位，则可寻址的范围为位，则可寻址的范围为0 01M1M。计算机系统。计算机系统的可寻址范围为虚拟存储器的最大范围。而物的可寻址范围为虚拟存储器的最大范围。而物理内存一般是小于虚拟存储大小的理内存一般是小于虚拟存储大小的103.6 请求分页虚拟存储管理请求分页虚拟存储管理11什么是请求分页存储管理？l

10、请求式分页也称虚拟页式存储管理：请求式分页也称虚拟页式存储管理： 与与纯分页存储管理不同，请求式分页管理系纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，统在进程开始运行之前，不是装入全部页不是装入全部页面，而是装入一个或零个页面面，而是装入一个或零个页面，之后根据，之后根据进程运行的需要，动态装入其它页面；当进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入则根据某种算法淘汰某个页面，以便装入新的页面新的页面12基本原理（和页式管理比较）1 1）首先，物理的内存空间被划分为等长的物理块

11、，）首先，物理的内存空间被划分为等长的物理块，并对块编号。同时，用户程序也进行分页，这些并对块编号。同时，用户程序也进行分页，这些与页式存储管理相同。与页式存储管理相同。2 2）在用户程序开始执行前，不将该程序的所有页）在用户程序开始执行前，不将该程序的所有页都一次性装入内存，而是先放在外存。当程序被都一次性装入内存，而是先放在外存。当程序被调度投入运行时，系统先将少数页装入内存，随调度投入运行时，系统先将少数页装入内存，随着程序运行，如果所访问的页在内存中，则对其着程序运行，如果所访问的页在内存中，则对其管理与分页存储管理情况相同管理与分页存储管理情况相同3 3）若发现所要访问的数据或指令不

12、在内存中，就）若发现所要访问的数据或指令不在内存中，就会产生缺页中断，到外存寻找包含所需数据或指会产生缺页中断，到外存寻找包含所需数据或指令的页，并将其装入到内存的空闲块中。令的页，并将其装入到内存的空闲块中。134 4）在装入一页的过程中，若发现内存无空闲）在装入一页的过程中，若发现内存无空闲块或分配给该进程的物理块已用完，则需块或分配给该进程的物理块已用完，则需要通过页面置换功能从已在内存的页中挑要通过页面置换功能从已在内存的页中挑选一个将其淘汰，释放所占用的物理块后选一个将其淘汰，释放所占用的物理块后将新的页面装入该块，进程继续运行。将新的页面装入该块，进程继续运行。5 5）被淘汰的页面

13、如果刚才被修改过，则还需）被淘汰的页面如果刚才被修改过，则还需要将其回写到外存，以保留其最新内容。要将其回写到外存，以保留其最新内容。因此：请求分页虚拟存储管理与页式存储管理因此：请求分页虚拟存储管理与页式存储管理在许多地方相似，区别是增加了请求调页（部在许多地方相似，区别是增加了请求调页（部分装入）和页面置换（部分替换）等功能分装入）和页面置换（部分替换）等功能14需要解决的问题系统需要解决下面五个问题：系统需要解决下面五个问题：1 1）需要提供一个全新的页表机制来记录任一页是在）需要提供一个全新的页表机制来记录任一页是在内存或在外存的位置、是否被修改过等信息。内存或在外存的位置、是否被修改

14、过等信息。2 2）在请求分页虚拟存储管理方式下，内存中允许装）在请求分页虚拟存储管理方式下，内存中允许装入多个进程，每个进程占用一部分物理块，问题在入多个进程，每个进程占用一部分物理块，问题在于：为每个进程分配多少个物理块才合适？采用何于：为每个进程分配多少个物理块才合适？采用何种分配方式才合理？种分配方式才合理？3 3）进程运行过程中发现所要访问的数据或指令不在）进程运行过程中发现所要访问的数据或指令不在内存时，便会产生缺页中断，到外存寻找该页，此内存时，便会产生缺页中断，到外存寻找该页，此时，缺页中断如何处理时，缺页中断如何处理15需要解决的问题4 4）一个页面或者是一开始就装入内存，或者

15、是在）一个页面或者是一开始就装入内存，或者是在运行中被动态的装入内存，如何进行地址重定位运行中被动态的装入内存，如何进行地址重定位？5 5）在动态装入一个页面时，若发现内存当前无空）在动态装入一个页面时，若发现内存当前无空闲块或分配给该进程的物理块已经用完，则需要闲块或分配给该进程的物理块已经用完，则需要从已在内存的页面中选出一个将其淘汰。问题在从已在内存的页面中选出一个将其淘汰。问题在于：在什么范围内选择要淘汰的页面？淘汰哪个于：在什么范围内选择要淘汰的页面？淘汰哪个页面？这就需要合适的页面置换算法。页面？这就需要合适的页面置换算法。16请求分页虚拟存储管理的请求分页虚拟存储管理的 硬件支持

16、硬件支持1. 请求分页的页表机制请求分页的页表机制2. 缺页中断机构缺页中断机构3. 地址转换机构地址转换机构4.请求分页的请求分页的 硬件支撑（硬件支撑（MMU）171. 请求分页的页表机制请求分页的页表机制 在虚拟存储管理中，页表除了要完成从逻辑地址在虚拟存储管理中，页表除了要完成从逻辑地址到物理地址的转换外，还需要提供页面置换的相到物理地址的转换外，还需要提供页面置换的相关信息。因此，页表中除了有页号和物理块号等关信息。因此，页表中除了有页号和物理块号等信息外，还增加了页的状态位、外存地址、修改信息外，还增加了页的状态位、外存地址、修改位、访问字段等信息位、访问字段等信息图3.27 页式

17、虚拟存储管理的页表181. 请求分页的页表机制请求分页的页表机制u状态位：状态位：用于标志一页是否已装入内存。u外存地址：外存地址：页在外存中的地址。u修改位：修改位：页在内存中是否被修改过的标志，用来确定如果该页被换出内存时，是否需要再回写入外存。u访问字段：访问字段：标志页在内存时是否被访问过。用于进行页面置换时考虑是否将该页换出内存。如果该页被访问过，在进行页面置换时，系统会考虑该页可能以后会被再次访问而不将其换出。192 2缺页中断机构缺页中断机构在进程运行过程中，当发现所访问的页不在内存时，缺页中断机构便产生一个缺页（Page fault）中断信号，操作系统接到此信号后，就运行缺页中

18、断处理程序，将所需要的页调入内存。缺页中断与一般中断类似，都需要经历保护CPU环境、分析中断原因、转入中断程序处理、中断处理后恢复CPU环境等步骤。202 2缺页中断机构缺页中断机构但缺页中断与一般中断也有不同：1 1）CPU检测中断的时间不同。对一般的中断信号，CPU是在一条指令执行完后检测其是否存在，检测时间以一个指令周期为间隔。而对缺页中断信号，CPU在一条指令执行期间，只要有中断信息就可检测，不需要等待一个指令周期。因此，CPU检测缺页中断更及时。2 2）CPU可以多次处理。如果在一个指令周期中多次检测到缺页中断，CPU都会及时处理。21223. 3. 地址转换机构地址转换机构请求分页

19、虚拟存储技术是在程序执行过程中逐步将程序页面调入内存的，所以从逻辑地址到物理地址的转换是在程序运行过程中完成的，是动态重定位装入23244. 请求分页的硬件支撑（请求分页的硬件支撑（MMU）请求分页存储管理需要底层硬件的支撑来请求分页存储管理需要底层硬件的支撑来完成，即完成，即MMU(主存管理部件主存管理部件)，负责地址，负责地址转换和存储保护转换和存储保护MMU由一组集成电路芯片组成，逻辑地址由一组集成电路芯片组成，逻辑地址作为输入，物理地址作为输出，直接送达作为输入，物理地址作为输出，直接送达总线总线254. 请求分页的硬件支撑（请求分页的硬件支撑（MMU）MMU的主要功能的主要功能（1）

20、管理硬件页表基址寄存器）管理硬件页表基址寄存器（2）分解逻辑地址）分解逻辑地址（3）管理快表）管理快表（4）访问页表）访问页表（5）发出相应中断）发出相应中断（6）管理特征位）管理特征位26请求分页存储管理地址变换流程l当当进程程调度度到到CPUCPU上上运运行行时，操操作作系系统自自动把把此此进程程PCBPCB中中的的页表表起起始始地地址址装装入入硬硬件件页表基址寄存器表基址寄存器l进程程开开始始运运行行，访问某某个个虚虚地地址址，MMUMMU工工作：作：（1 1）MMUMMU接接收收CPUCPU传送送过来来的的逻辑地地址址并并自自动按按页面大小把它从某位起分解成面大小把它从某位起分解成页号

21、和号和页内位移内位移（2 2）以）以页号号为索引索引查找找TLBTLB27请求分页存储管理地址变换流程（3 3）快表不命中，就搜索）快表不命中，就搜索页表表（4 4）如如果果在在页表表中中找找到到此此页面面（相相应驻留留位位为1 1），送送出出页框框号号，与与页内内位位移移拼拼接接成成物物理理地地址址，并并进行行访问权限限检查，通通过即即可可访问，并并把把页面面信信息息装入快表装入快表（5 5）如如果果发现页表表中中的的对应页面面失失效效即即发生生缺缺页中中断断，MMUMMU发出出缺缺页中中断断后后就就停停止止工工作作，由由内内核核存存储管管理理（操操作作系系统，软件件）接接收收控控制制，处理

22、理缺缺页中中断断28请求分页存储管理地址变换流程内核存内核存储管理管理处理缺理缺页中断的中断的过程：程：1 1）根据）根据页号搜索外号搜索外页表，找到存放此表，找到存放此页的磁的磁盘物理地址；物理地址；2 2）查看看主主存存是是否否有有空空闲页框框，如如果果有有则找找出出，修修改改主主存存管管理理表和相表和相应页表，表，转5 5；3 3）如如果果主主存存无无空空闲页框框，按按照照替替换算算法法选择淘淘汰汰页面面，检查其是否被写其是否被写过或修改或修改过，若否，若否转5 5，若是，若是则转4 44 4）淘汰）淘汰页面被写面被写过或修改或修改过，将其内容写回磁，将其内容写回磁盘的原先位置的原先位置

23、5 5）进行行调页，把把页面面装装入入主主存存所所分分配配的的页框框中中，同同时修修改改进程程页表表项6 6）返回）返回进程断点，重新启程断点，重新启动被中断的指令被中断的指令29查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无30请求页式虚拟存储系统优缺点l优点：作业的程序和数据可按页分散存放在主存中，减少移动开销，有效解决了碎片问题;既有利于改进主存利用率，又有利于多道程序运行。l缺点：要有硬件支持，

24、要进行缺页中断处理，机器成本增加，系统开销加大。这些开销主要包括：用于地址变换和各种数据结构的存储开销、执行地址变换指令的时间开销、内存与外存之间对换页面的I/O开销等。313.6.3 页面分配策略与页面调度算法323.6.3 页面分配策略与页面调度算法 请求分页虚拟存储管理支持多个进程同时装入内存，操作请求分页虚拟存储管理支持多个进程同时装入内存，操作系统为各个进程分别分配部分物理块，并将各自的部分页系统为各个进程分别分配部分物理块，并将各自的部分页调入内存，在实施中涉及到以下三个策略：调入内存，在实施中涉及到以下三个策略： 1、页面分配策略：、页面分配策略：分配策略决定系统应该给一个进程分

25、配多少物理块，进程才能运行。 2、页面调入策略：、页面调入策略：页面调入策略决定如何将进程所需要的页面调入到内存。 3、页面置换策略：、页面置换策略：页面置换策略决定内存中的哪些页面被换出内存。331、页面分配策略、页面分配策略系统为进程分配主存,需考虑因素: 分给进程的空间越小,同一时间处于主存的进程就越多，至少有一个进程处于就绪态的可能性就越大如果进程只有小部分在主存里,即使局部性很好,缺页中断率还会相当高因程序的局部性原理，分给进程的主存超过一定限度后，再增加主存空间,不会明显降低进程的缺页中断率。34页面分配策略：固定分配页面分配策略：固定分配 为每个进程分配固定数量的物理块，其数量在

26、进程创建时，由进程的类型（交互性、批处理或应用性）或根据用户的要求确定，在进程的整个运行期间都不再改变。具体的分配方式包括：按进程平均分配法、进程按比例分配法和进程优先权分配法等。35页面分配策略：可变分配页面分配策略：可变分配n可变分配方式是指分配给进程的物理块数，在该进程的运行期间可以动态变化。它用来解决由于事先分配给进程的物理块太少而导致的频繁缺页问题。n具体实现时，先为每一进程分配必要数量的物理块，使之可以开始运行，系统中余下的空闲物理块组成一个空闲物理块队列，当某一进程在运行过程中发生缺页时，系统从空闲物理块队列中取出一个空闲块分配给该进程。只要该空闲队列中还有物理块，凡发生缺页的进

27、程都可以才该队列中申请并获得物理块。36页面分配策略：可变分配页面分配策略：可变分配进程执行的某阶段缺页率较高,说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前的局部性较好,可减少分给进程的物理块数372、页面调入策略、页面调入策略页面装入主存页面装入主存, ,有两种策略：有两种策略： （1 1）请求页调入）请求页调入 （2 2）预先页调入）预先页调入38（1）请求页调入策略）请求页调入策略n请求页调入简称请调，是指在CPU需要访问进程某页面时，发现所访问的页面不在内存，CPU发出缺页中断信号，请求将该页调入内存。操作系统接收到缺页中断请求后，为之分配物理块并从外存将该页调入

28、内存。n每个进程在刚开始执行时，所需的页面很多，会产生多次缺页中断，页面被逐一调入内存。根据程序的局部性原理，当进程运行一段时间后，所需要的页面会逐步减少，缺页中断次数会逐渐下降，最后趋向于很低的水平，进程运行进入相对平稳阶段。39（1）请求页调入策略）请求页调入策略n优点：只有在需要时才将页面调入内存，节省了内存空间。n缺点： 1）在进程初次执行时，开始阶段会有大量的页调入内存，这时的进程切换开销很大。 2）发生缺页中断时操作系统会调入页面，而每次又仅调入一个页面，启动磁盘作I/O的频率很高。由于每次启动磁盘时会产生一个时间延迟，因此，会造成系统用于I/O的时间增长，系统效率降低。 3）对于

29、执行顺序跳跃性大的程序，缺页情况变化大，难以趋向稳定的水平，从而引起系统不稳定。40（2）预先页调入策略）预先页调入策略n预先页调入简称预调，是指由操作系统根据某种算法，预先估计进程可能要访问的页面，并在处理器需要访问页面之前先将页面预先调入内存。n优点：一次可将多个页面调入内存，减少了缺页中断的次数和I/O操作次数，系统付出的开销减少。如果预先动态估计准确率高，该调入策略会大大提高系统效率。41（2）预先页调入策略）预先页调入策略缺点：1）如果预先动态估计准确率较低，调入的页面不被使用的可能性大，系统效率较低。 2）如果程序员不能预先提供所需程序部分的信息，则该调度策略难以实施。总结：在实际

30、应用中，页面调入会将请求页调入和预先页调入结合起来。在进程刚开始执行时或每次缺页中断时，采用预先页调入。在进程运行稳定后，如果发现缺页，系统可采用请求页调入。423、页面置换策略、页面置换策略如果页面替换算法的作用范围是整个系统，称全局页面置换算法,它可以在运行进程间动态地分配物理块数。如果页面替换算法的作用范围局限于本进程，称为局部页面置换算法,它实际上需要为每个进程分配固定的物理块。43页面分配和置换策略组合页面分配和置换策略组合可组合出以下三种适用的策略。可组合出以下三种适用的策略。 1) 固定分配局部置换固定分配局部置换(Fixed Allocation, Local Replacem

31、ent) 2) 可变分配全局置换可变分配全局置换(Variable Allocation, Global Replacement) 3) 可变分配局部置换可变分配局部置换(Variable Allocation, Local Replacemen 441）固定分配局部置换）固定分配局部置换n为每个进程分配固定数量的物理块，在进程的整为每个进程分配固定数量的物理块，在进程的整个运行期间都不再改变。当一个进程运行中发生个运行期间都不再改变。当一个进程运行中发生缺页中断时，操作系统只从该进程在内存中的页缺页中断时，操作系统只从该进程在内存中的页面中选择一页淘汰。面中选择一页淘汰。n该策略不足在于：应

32、为每个进程分配多少物理块该策略不足在于：应为每个进程分配多少物理块数难以确定。如果分配给进程的物理块太少，缺数难以确定。如果分配给进程的物理块太少，缺页中断率高，进而导致整个多道程序系统运行缓页中断率高，进而导致整个多道程序系统运行缓慢；给多了，会使内存中能同时执行的进程数减慢；给多了，会使内存中能同时执行的进程数减少，进而造成处理器空闲和其他设备空闲，浪费少，进而造成处理器空闲和其他设备空闲，浪费资源。资源。451）固定分配局部置换）固定分配局部置换 采用固定分配算法，系统把物理块分配给进程，采用：平均分配；按比例分配；优先权分配462）可变分配全局置换）可变分配全局置换u先先为为每每一一进

33、进程程分分配配必必要要数数量量的的物物理理块块，使使之之可可以以开开始始运运行行，系系统统中中余余下下的的空空闲闲物物理理块块组组成成一一个个空空闲闲物物理理块块队队列列，当当某某一一进进程程在在运运行行中中发发生生缺缺页页时时，系系统统从从空空闲闲物物理理块块队队列列中中取取出出一一个个空空闲闲块块分分配配给给该该进进程程。直直到到系系统统拥拥有有的的空空闲闲物物理理块块耗耗尽尽，才才会会从从内内存存中中选选择择一一页页淘淘汰汰，该该页页可可以以是是内内存存中中任任一一进程的页面。进程的页面。u该该策策略略易易于于实实现现，且且可可以以有有效效地地减减少少缺缺页页中中断断率率，是采用得较多的

34、一种分配和置换策略。是采用得较多的一种分配和置换策略。473）可变分配局部置换）可变分配局部置换 其实现要点如下其实现要点如下: :(1)(1)新新进进程程装装入入主主存存时时，根根据据应应用用类类型型、程程序序要要求求，分分配配给给一一定定数数目目物物理理块块数数, ,可可用用请请页页式或预调式完成这个分配。式或预调式完成这个分配。(2)(2)产产生生缺缺页页中中断断时时, ,从从该该进进程程驻驻留留集集中中选选一一个页面替换。个页面替换。(3)(3)不不时时重重新新评评价价进进程程的的分分配配，增增加加或或减减少少分分配给进程的页框以改善系统性能配给进程的页框以改善系统性能483.6.4页

35、面置换算法49n请求分页虚拟存储管理规定，当需要从外存调入一个新的页面时，如果此时物理内存无空闲块，系统必须按照一定的算法选择内存中的一些页面调出，并将所需的页面调入内存，这个过程叫页面置换。页面置换算法决定从内存中置换出哪一个页面。n衡量页面置换算法的重要的指标是缺页率。50 一个进程或一个作业在运行中成功的页面访问次数为S，即所访问的页面在内存中；不成功的页面访问次数为F，即访问的页面不在内存，需要缺页中断并调入内存；需要访问的页面的总次数为A=S+F。则缺页率f为：f=F/A51影响缺页率的因素如下影响缺页率的因素如下： 1）进程分得的内存物理块数越多，缺页率越低。 2）划分的页面越大，

36、缺页率越低。 3）如果程序局部性好，则缺页率低。 4）如果选取的置换算法优，则缺页率低。 在进程的内存物理块数和页面大小不能改变的情况下，要减少缺页率，就要考虑选择合适的页面置换算法。52当要放一页面到全满的主存块时，系统需淘汰当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫替换算一页。用来选取淘汰哪一页的规则，叫替换算法。法。全局：全局： 1 1 先进先出页面替换算法先进先出页面替换算法FIFOFIFO 2 2 最佳页面替换算法最佳页面替换算法OPT OPT 3 3 最近最少使用页面替换算法最近最少使用页面替换算法LRULRU 4 4 第二次机会页面替换算法第二次机

37、会页面替换算法SCR SCR 5 5 时钟页面替换算法时钟页面替换算法Clock Clock 53 1 先进先出先进先出(FIFO)页面置换算法页面置换算法基于程序总是按线性顺序来访问物理空间这一假设。基于程序总是按线性顺序来访问物理空间这一假设。算法总是淘汰最先调入主存的那一页，或者说在主存算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。中驻留时间最长的那一页（常驻的除外）。注意：不考虑刚被访问，只要是队列中最先进入注意：不考虑刚被访问，只要是队列中最先进入的就被淘汰，做题时可按先进先出排好队的就被淘汰，做题时可按先进先出排好队54777001701201

38、201320230430432303042423230212011701301012127701缺页次数：缺页次数：15270FFFF(7)SF(0) F(1) F(2) F(3)F(0)F(4)SSF(2)F(3)SSSF(0) F(1) F(2)55先进先出页面置换算法开销低、容易编程实现，适合于线性顺序特性好的程序。但是该算法没有考虑到页面的访问频率，很可能刚被换出的页面马上又要被访问，使得缺页率偏高。为了改善FIFO算法，减少缺页率，科学家尝试在进程发生缺页时给进程增加物理块。在实验中，Belady发现了一个奇怪的现象，该现象也被称为Belady异常现象。即：当页数在一定范围内时，缺页

39、率反而随分配给进程的物理块数的增加而增加56如图所示：当内存物理块数从4增加到6时，缺页率增加了，该现象说明，如果要改善系统性能，不能只靠给进程增加内存物理块。57 2 2 最佳页面替换算法最佳页面替换算法OPT OPT 调调入入一一页页而而必必须须淘淘汰汰一一个个旧旧页页时时，所所淘淘汰汰的的页页应应该该是是以以后后不不再再访访问问的的页页或或距距现现在在最最长时间后再访问长时间后再访问的页。的页。理理论论算算法法, ,可可用用来来作作为为衡衡量量各各种种具具体体算算法法的的标准。标准。方方法法：淘淘汰汰可可选选页页面面中中离离当当前前页页面面向向后后最最远远的的一一页页，表表示示以以后后不

40、不再再访访问问或或距距现现在在最最长时间后再访问长时间后再访问的页的页58 假假定定系系统统为为某某进进程程分分配配了了三三个个物物理理块块， 并并考考虑虑有有以以下下的页面号引用串：的页面号引用串：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予以淘汰。予以淘汰。 缺页次数：缺页次数：959 3 最近最少使用最近最少使用(L

41、RU)置换算法置换算法 l 算法淘汰的页面是在最近一段时间里较久未被访问的那页。l 根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。60 3 最近最少使用最近最少使用(LRU)置换算法置换算法举例举例： （淘汰可选页面中离当前页面（淘汰可选页面中离当前页面向前向前最远的一页，表示最近最少使用）最远的一页，表示最近最少使用）缺页次数：缺页次数：1261LRU算法的实现（算法的实现（1）队队列列中中存存放放当当前前在在主主存存中中的的页页号号，每每当当访访问问一一页页时时就就调调整整一一次次，使使队队列列尾尾总总指指向向最最近近访访问

42、问的的页页，队队列列头头就就是是最最近近最最少少用的页。用的页。发发生生缺缺页页中中断断时时总总淘淘汰汰队队列列头头所所指指示示的的页页；执执行行一一次次页页面面访访问问后后，需需要要从从队队列列中把该页调整到队列尾中把该页调整到队列尾第一：维护一个特殊的队列 页面淘汰队列62LRU算法的实现（算法的实现（1）例子：给某作业分配了三块主存，该作业依次访问的页号为：4，3，0，4，1，1，2，3，2。当访问这些页时，页面淘汰序列变化情况如下63访问页号 页面淘汰序列 被淘汰页面 4 4 3 4 3 0 4 3 0 4 3 0 4 1 0 4 1 3 1 0 4 1 2 4 1 2 0 3 1 2

43、 3 4 2 1 3 2队头队头 队尾队尾64LRU算法的实现（算法的实现（2）标志位法标志位法多位计数器法多位计数器法多位计时器法多位计时器法第二：需要硬件支持，确定页面最后访问以来所经历的时间65标志位法标志位法每页设置一个引用标志位每页设置一个引用标志位R R，访问某页时，访问某页时，由硬件将页标志位由硬件将页标志位R R置置1 1，隔一定时间，隔一定时间t t将所将所有页的标志有页的标志R R均清均清0 0。发生缺页中断时，从标志位发生缺页中断时，从标志位R R为为0 0的页中挑的页中挑选一页淘汰。挑选到要淘汰的页后，也将选一页淘汰。挑选到要淘汰的页后，也将所有页的标志位所有页的标志位

44、R R清清0 0。 66多位计数器法多位计数器法每个页面设置一个多位计数器，又叫最不每个页面设置一个多位计数器，又叫最不常用页面替换算法常用页面替换算法LFULFU。每当访问一页时，。每当访问一页时，就使它对应的计数器加。就使它对应的计数器加。当发生缺页中断时，可选择计数值最小的当发生缺页中断时，可选择计数值最小的对应页面淘汰，并将所有计数器全部清。对应页面淘汰，并将所有计数器全部清。67多位计时器法多位计时器法为每个页面设置一个多位计时器，每当页为每个页面设置一个多位计时器，每当页面被访问时，系统的绝对时间记入计时器。面被访问时，系统的绝对时间记入计时器。比较各页面的计时器的值，选最小值的未

45、比较各页面的计时器的值，选最小值的未使用的页面淘汰，因为，它是最使用的页面淘汰，因为，它是最“老老”的的未使用的页面。未使用的页面。684 第二次机会页面替换算法（第二次机会页面替换算法（SCR） 改改进进FIFOFIFO算算法法, ,把把FIFOFIFO与与页页表表中中的的”引引用位用位”结合起来使用结合起来使用 算算法法含含义义：最最先先进进入入主主存存的的页页面面，如如果果最最近近还还在在被被使使用用的的话话, ,仍仍然然有有机机会会作作为为像一个新调入页面一样留在主存中。像一个新调入页面一样留在主存中。694 第二次机会页面替换算法（第二次机会页面替换算法（SCR） 实现过程：实现过程

46、： 检检查查FIFOFIFO中中的的队队首首页页面面( (最最早早进进入入主主存存的的页页面面),),如如果果它它的的”引引用用位位”是是0,0,这这个个页页面面既既老老又又没有用，选择该页面淘汰没有用，选择该页面淘汰; ; 如如果果“引引用用位位”是是1,1,说说明明它它进进入入主主存存较较早早，但但最最近近仍仍在在使使用用。把把它它的的”引引用用位位”清清0,0,并并把把这这个个页页面面移移到到队队尾尾，把把它它看看作作是是一一个个新新调调入的页。入的页。705 时钟页面替换算法（时钟页面替换算法（Clock）SCR算法采用算法采用FIFO队列可能产生频繁的出队列可能产生频繁的出队和入队，

47、实现代价高队和入队，实现代价高改进：可采用类似钟表面的环形表，队列改进：可采用类似钟表面的环形表，队列指针相当于钟表面上的表针，指向可能要指针相当于钟表面上的表针，指向可能要淘汰的页面淘汰的页面 时钟页面替换算法时钟页面替换算法注意：和注意：和SCR算法并没有本质区别，算法并没有本质区别，仍需使用引用位（访问位）仍需使用引用位（访问位）715 时钟页面替换算法（时钟页面替换算法（Clock）实现要点：实现要点：(1)(1)一个页面首次装入主存，其一个页面首次装入主存，其“引用位引用位”置置0 0 。(2)(2)主存中的任何页面被访问时主存中的任何页面被访问时, “, “引用位引用位”置置1 1

48、。(3)(3)淘淘汰汰页页面面时时, ,从从指指针针当当前前指指向向的的页页面面开开始始扫扫描描循循环环队队列列，把把遇遇到到的的“引引用用位位”是是1 1的的页页面面的的“引引用用位位”清清0,0,跳跳过过这这个个页页面面; ; 把把所所遇遇到到的的”引引用用位位”是是0 0的的页页面面淘淘汰汰掉掉, ,指指针针推进一步。推进一步。(4)(4)扫扫描描循循环环队队列列时时，如如果果碰碰到到的的所所有有页页面面的的”引引用用位位”为为1 1，指指针针就就会会绕绕整整个个循循环环队队列列一一圈圈，把把碰碰到到的的所所有有页页面面的的”引引用用位位”清清0;0;指指针针停停在在起起始始位位置置，并

49、并淘淘汰汰掉掉这这一一页页, ,然然后，指针推进一步。后，指针推进一步。72Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0指针指针n n0 01 12 23 34 45 56 67 78 8一个页替换前的缓冲区状态一个页替换前的缓冲区状态Page9 use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page727Use=1Page13Use=0Page67Use=1Pag

50、e33Use=1Page222Use=0n n0 01 12 23 34 45 56 67 78 8下一页替换后的缓冲区状态下一页替换后的缓冲区状态第1页框73时钟页面替换改进算法把把”引引用用位位”和和”修修改改位位”结结合合起起来来使使用，共组合成四种情况：用，共组合成四种情况：(1)(1)最近没有被引用最近没有被引用, ,没有被修改没有被修改(r=0,m=0)(r=0,m=0)(2)(2)最近被引用最近被引用, ,没有被修改没有被修改(r=1,m=0)(r=1,m=0)(3)(3)最近没有被引用最近没有被引用, ,但被修改但被修改(r=0,m=1)(r=0,m=1)(4)(4)最近被引用

51、过最近被引用过, ,也被修改过也被修改过(r=1,m=1)(r=1,m=1)74时钟页面替换改进算法步步1 1：选选择择最最佳佳淘淘汰汰页页面面，从从指指针针当当前前位位置置开开始始, ,扫扫描描循循环环队队列列。扫扫描描过过程程中中不不改改变变“引引用用位位”，把碰到的第一个把碰到的第一个r=0,m=0r=0,m=0的页面作为淘汰页面。的页面作为淘汰页面。步步2 2：如如果果步步1 1失失败败，再再次次从从原原位位置置开开始始，查查找找r=0r=0且且m=1m=1的的页页面面，把把碰碰到到的的第第一一个个这这样样的的页页面面作作为为淘淘汰汰页页面面，而而在在扫扫描描过过程程中中把把指指针针所

52、所扫扫过过的的页页面面的的”引用位引用位”r”r置置0 0。步步3 3：如如果果步步2 2失失败败，指指针针再再次次回回到到了了起起始始位位置置，由由于于此此时时所所有有页页面面的的”引引用用位位”r”r均均己己为为0 0，再再转转向向步步1 1操操作作，必必要要时时再再做做步步2 2操操作作，这这次次一一定定可可以以挑出一个可淘汰的页面。挑出一个可淘汰的页面。75举例举例假设采用固定分配策略，进程分得三假设采用固定分配策略，进程分得三个页框个页框, ,执行中按下列次序引用执行中按下列次序引用5 5个独个独立的页面立的页面: 2 3 2 1 5 2 4 5 : 2 3 2 1 5 2 4 5

53、3 2 5 23 2 5 2，分别用计算，分别用计算OPT OPT 、LRULRU、FIFOFIFO和和CLOCKCLOCK算法中缺页中断的次数算法中缺页中断的次数762 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 5 3 2 5 21队首：要淘汰的页面队首：要淘汰的页面队尾：最近的页面队尾：最近的页面772 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 5 3 2 5 2最先进入队列的页面最先进入队列的页面78性能比较性能比较OPT F(1) F(2) F(4) +3次LRU F(3) F(1) F(2) F(4) +3次CLOCK F(2)

54、 F(3) F(1) F(5) F(4) +3次FIFO F(1) F(3) F(1) F(5) F(2) F(4) +3次可以看出：可以看出：FIFO算法的性能最差，算法的性能最差，OPT算法的性能最好，而算法的性能最好，而Clock算法算法与与LRU算法的性能十分接近算法的性能十分接近793.6.5影响请求页式存储管理性能的因素80虚拟存储技术以增加进程运行的时间为代价虚拟存储技术以增加进程运行的时间为代价换来系统更多的虚拟内存，影响其性能（即换来系统更多的虚拟内存，影响其性能（即缺页中断率）的因素有：缺页中断率）的因素有： 主存物理块数：分得物理块数越多主存物理块数：分得物理块数越多f

55、f越低越低 页面大小：页面越大页面大小：页面越大f f越低越低 页面置换算法页面置换算法 程序特性：局部性好，中断率低程序特性：局部性好，中断率低3.6.5影响请求页式存储管理性能的因素811.分配给进程的内存块数与缺页率的关系n分给进程的物理块数越多，缺页率越小。分给进程的物理块数越多，缺页率越小。n例如，若某进程逻辑地址共需例如，若某进程逻辑地址共需3030个页面，取极端个页面，取极端情况，为其分配情况，为其分配3030个物理块。则所有页面全部进个物理块。则所有页面全部进入内存，缺页率自然为入内存，缺页率自然为0 0。不过此时请求页式管。不过此时请求页式管理已变成了页式管理。理已变成了页式

56、管理。n如果取另一个极端，即只分给进程一个物理块，如果取另一个极端，即只分给进程一个物理块，只能容纳下一页，这种情况下毫无疑问会频繁地只能容纳下一页，这种情况下毫无疑问会频繁地发生缺页中断，缺页率最大。发生缺页中断，缺页率最大。n试验结果表明，对每个进程来说，为其分配进程试验结果表明，对每个进程来说，为其分配进程空间页面数约一半的物理块时，请求页式的效果空间页面数约一半的物理块时，请求页式的效果最好。最好。822.页面大小对系统性能的影响1）从页表大小考虑：）从页表大小考虑：如果页面较小，页数就要如果页面较小，页数就要增加，页表也随之扩大，为了控制页表所占的内增加，页表也随之扩大，为了控制页表

57、所占的内存空间，存空间，应选择较大的页面尺寸。应选择较大的页面尺寸。2 2）从内存利用率考虑：内存以块为单位，一般）从内存利用率考虑：内存以块为单位，一般情况下进程的最后一个页面总是装不满一个物理情况下进程的最后一个页面总是装不满一个物理块，会产生内部碎片，为了减少内部碎片，块，会产生内部碎片，为了减少内部碎片，应选应选择小的页面尺寸。择小的页面尺寸。832.页面大小对系统性能的影响n3 3）从读写一个页面所需的时间考虑：页面需要）从读写一个页面所需的时间考虑：页面需要从外存对换区读到内存，作业存放在辅助存储器从外存对换区读到内存，作业存放在辅助存储器上，从磁盘读入一个页面的时间包括等待时间上

58、，从磁盘读入一个页面的时间包括等待时间（移臂时间（移臂时间+ +旋转时间）和传输时间，通常等待旋转时间）和传输时间，通常等待时间远大于传输时间。显然，时间远大于传输时间。显然，加大页面的尺寸，加大页面的尺寸，有利于提高有利于提高 I/O I/O 的效率。的效率。总结：现代操作系统中，页面大小大多选择在512B到4KB之间。页面长度是由CPU中的MMU规定的，操作系统通过特定寄存器的指示位来指定当前选用的页面长度。843.缺页率对系统性能的影响页面替换中的页面替换中的“抖动现象抖动现象”： 刚被淘汰的页面立即又要调用，而调入不久随即刚被淘汰的页面立即又要调用，而调入不久随即被淘汰，淘汰不久又再被

59、调用，如此反复，使得被淘汰，淘汰不久又再被调用，如此反复，使得整个系统的页面调度非常频繁，以致大部分时间整个系统的页面调度非常频繁，以致大部分时间都花费在来回调度页面上，而不是执行计算任务，都花费在来回调度页面上，而不是执行计算任务，这样的现象称作这样的现象称作“抖动现象抖动现象”l原因：页面淘汰算法不合理原因：页面淘汰算法不合理; ;分配给进程的物理分配给进程的物理块数太少块数太少注意：采取好的调度算法可以避免抖动现象注意：采取好的调度算法可以避免抖动现象853.7请求分段虚拟存储管理86请求分段的概念请求分段的概念请求分段虚拟存储系统把作业的所有请求分段虚拟存储系统把作业的所有分段的副本都

60、存放在辅助存储器中，分段的副本都存放在辅助存储器中，当作业被调度投入运行时，首先把当当作业被调度投入运行时，首先把当前需要的一段或几段装入主存，在执前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把行过程中访问到不在主存的段时再把它们装入。它们装入。 87需要对段表进行扩充需要对段表进行扩充段号，段号，特征位，存储权限，扩充位，标志位，特征位，存储权限，扩充位，标志位，主主存始址，段长，存始址，段长，辅存始址辅存始址特征位特征位: 0 (: 0 (不在主存不在主存) )；1(1(在主存在主存) )；存存取取权权限限: : 00(00(可可执执行行) )；01(01(可可读读) )

61、；11(11(可可写写) )；扩充位扩充位: 0(: 0(固定长固定长) )；1(1(可扩充可扩充) )；标标志志位位: : 00(00(未未修修改改) )；01(01(已已修修改改) )；11(11(不不可移动可移动) )；88地址转换流程地址转换流程1. 访问某段，由硬件的地址转换机制查段表，若所访问某段，由硬件的地址转换机制查段表，若所需的段在主存，则按分段存储管理方法进行地址需的段在主存，则按分段存储管理方法进行地址转换得物理地址转换得物理地址2. 若不在主存，触发缺段中断，由操作系统处理此若不在主存，触发缺段中断，由操作系统处理此中断：查主存分配表，找出一个足够大的连续区中断：查主存

62、分配表，找出一个足够大的连续区域容纳此分段，找不到查看空闲区总和能否满足域容纳此分段，找不到查看空闲区总和能否满足此段要求，满足进行适当移动；若不满足，需要此段要求，满足进行适当移动；若不满足，需要调出一个或多个分段到磁盘上调出一个或多个分段到磁盘上89S S段在主存段在主存否否是是BSBS段长度段长度发越界中断发越界中断是是否否形成绝对地址形成绝对地址继续执行指令继续执行指令操作系统操作系统硬件硬件符合存取权限符合存取权限发保护中断发保护中断是是否否发缺段中断发缺段中断移动或调移动或调出分段出分段S S段末端相邻空段末端相邻空闲区长度满足闲区长度满足要求要求地址错地址错S S段可扩充段可扩充

63、是是装入装入S S段段重新启动指令重新启动指令调整调整S S段段表及段段表及主存分配表主存分配表否否非法存取非法存取否否主存中有满足主存中有满足S S段段长度的连续空闲区长度的连续空闲区是是否否是是移动或调移动或调出分段出分段90回顾回顾段式存储是基于用户程序结构的存储管理技术，段式存储是基于用户程序结构的存储管理技术，有利于模块化程序设计，便于段的扩充、动态有利于模块化程序设计，便于段的扩充、动态链接、共享和保护链接、共享和保护, ,但会生成段内碎片浪费存但会生成段内碎片浪费存储空间储空间页式存储是基于系统存储器结构的存储管理技页式存储是基于系统存储器结构的存储管理技术术, , 存储利用率高

64、存储利用率高, ,便于系统管理，但不易实便于系统管理，但不易实现存储共享、保护和动态扩充现存储共享、保护和动态扩充把两者结合起来就是段页式存储管理把两者结合起来就是段页式存储管理 91请求段页式的基本原理请求段页式的基本原理1 1、虚虚地地址址以以程程序序的的逻逻辑辑结结构构划划分分成成段段( (段页式存储管理的段式特征段页式存储管理的段式特征) )2 2、实实地地址址划划分分成成位位置置固固定定、大大小小相相等等的的页框页框( (段页式存储管理的页式特征段页式存储管理的页式特征) )3 3、将将每每一一段段的的线线性性地地址址空空间间划划分分成成与与页页框框大大小小相相等等的的页页面面，于于

65、是是形形成成了了段段页页式存储管理的特征。式存储管理的特征。4 4、逻辑地址形式为：、逻辑地址形式为：段号(s) 段内页号 (p) 页内位移(d)92请求段页式管理的数据结构请求段页式管理的数据结构作业表：登记进入系统中的所有作业及该作业段表的起始地址，段表：至少包含这个段是否在主存，以及该段页表的起始地址,页表：包含该页是否在主存(中断位)、对应主存块号。93地址转换地址转换1. 1. 从逻辑地址出发，先以段号从逻辑地址出发，先以段号s s和页号和页号p p作索作索引去查快表引去查快表, ,如果找到如果找到, ,那么立即获得页那么立即获得页p p的的页框号页框号p,p,并与位移并与位移d d

66、一起拼装得到访问主一起拼装得到访问主存的实地址存的实地址, ,从而完成了地址转换。从而完成了地址转换。94地址转换地址转换2. . 若查快表失败若查快表失败, ,就要通过段表和页表作地就要通过段表和页表作地址转换了，用段号址转换了，用段号s s作索引作索引, ,找到相应表目找到相应表目, ,由此得到由此得到s s段的页表起址段的页表起址s,s,再以再以p p作索引作索引得到得到s s段段p p页对应的表目页对应的表目, ,得到页框号得到页框号p;p;这这时一方面把时一方面把s s段段p p页和页框号页和页框号pp置换进快表，置换进快表，另一方面用另一方面用pp和和d d生成主存实地址生成主存实

67、地址, ,从而完从而完成地址转换。成地址转换。95地址转换地址转换3.3.如查段表时，发现如查段表时，发现s s段不在主存，产生段不在主存，产生“缺缺段中断段中断”，引起系统查找，引起系统查找s s段在辅存的位置，段在辅存的位置，将该段页表调入主存；将该段页表调入主存；4.4.如查页表时，发现如查页表时，发现s s段的段的p p页不在主存，产页不在主存，产生生“缺页中断缺页中断”，引起系统查找，引起系统查找s s段段p p页在页在辅存的位置，并将该页调入主存，当主存辅存的位置，并将该页调入主存，当主存已无空闲页框时，就会导致淘汰页面。已无空闲页框时，就会导致淘汰页面。9697例例1：某请求页式

68、管理系统，用户编程空：某请求页式管理系统，用户编程空间有间有40个页面，每个页面为个页面，每个页面为200H字节，字节，假定某时刻用户页表中虚页号和物理块假定某时刻用户页表中虚页号和物理块号对照表如下：号对照表如下： 虚页号：虚页号： 0 2 5 17 20 物理块号：物理块号： 5 20 8 14 36 求：虚地址求：虚地址0A3CH、223CH分别对应的分别对应的物理地址。物理地址。98解：可以转换成十进制做也可以转换成解：可以转换成十进制做也可以转换成二进制做。下面转换成十进制二进制做。下面转换成十进制 页的大小页的大小200H，即，即512字节字节 （1）虚地址）虚地址0A3CH转换成

69、十进制为转换成十进制为2620,2620/512得到页号为得到页号为5，页内地址，页内地址为为60，查页面得对应块号为，查页面得对应块号为8.因此该地因此该地址对应的物理地址为：址对应的物理地址为： 8*512+60=4156 (2)虚地址虚地址223CH转换成十进制为转换成十进制为8762,8762/512得到页号为得到页号为17，页内地址，页内地址为为58，查页面得对应块号为，查页面得对应块号为14.因此该地因此该地址对应的物理地址为：址对应的物理地址为： 14*512+58=722699例例2：某系统采用页式存储管理策略，拥某系统采用页式存储管理策略，拥有的逻辑空间为有的逻辑空间为32页

70、，每页页，每页2KB；拥有；拥有物理空间为物理空间为1MB。（1）写出逻辑地址的格式）写出逻辑地址的格式（2）若不考虑访问权限位，进程的页表有）若不考虑访问权限位，进程的页表有多少项？每项至少多少位？多少项？每项至少多少位？（3）如果物理空间减少一半，页表结构应）如果物理空间减少一半，页表结构应做怎样的改变？做怎样的改变？100解：解：（1）描述逻辑空间需要）描述逻辑空间需要16位地址，前位地址，前5位位是页号，后是页号，后11位为页内地址位为页内地址（2）进程的页表共有）进程的页表共有32项，每项至少要有项，每项至少要有9个二进制位表示个二进制位表示（3）可以不变）可以不变101例例3：一台

71、计算机含有：一台计算机含有65536字节的存储字节的存储空间，这一空间被分成许多长度为空间，这一空间被分成许多长度为4096B的页。有一个程序，其代码段为的页。有一个程序，其代码段为32768B，数据段为，数据段为16386B，栈段为，栈段为15870B。试问该及其的主存空间适合这。试问该及其的主存空间适合这个进程吗？如果将每页改成个进程吗？如果将每页改成512B，适合，适合吗？吗？102解解： （1）当存储空间为）当存储空间为4096B时，整个物时，整个物理空间可分成理空间可分成16块：块： 其中代码段占：其中代码段占：32768/4096=8块块 数据段占：数据段占：16386/4096=

72、5块块 栈段栈段: 15870/4096=4块块 合计合计17块块 因此该机器主存空间不适合这个作业因此该机器主存空间不适合这个作业（2）当每块为）当每块为512字节时，字节时，整个物理空间可整个物理空间可分成分成128块，所有段共需要块，所有段共需要127块，所以主块，所以主存空间适合这个作业存空间适合这个作业103例例4：某分页系统中，页的大小为某分页系统中，页的大小为100字。字。一个程序大小为一个程序大小为1200字，可能的访问序字，可能的访问序列如下：列如下： 10，205，110，735，603，50，815，314，432，320，225，80，130，270 系统采用系统采用L

73、RU算法。当为其分配算法。当为其分配4个主存个主存块时，给出该作业驻留的各个页的变化块时，给出该作业驻留的各个页的变化情况及页故障数情况及页故障数104解：首先将逻辑地址变换为页号，分别解：首先将逻辑地址变换为页号，分别为为0,2,1,7,6,0,8,3,4,3,2,0,1,2. 根据根据LRU算法，被淘汰的页依次为算法，被淘汰的页依次为0，2，1，7，6，0，8，4.缺页次数为缺页次数为12次次（过程略）（过程略）105例5填空题1.在采用请求分页式存储管理的系统中，在采用请求分页式存储管理的系统中，地址变换过程可能会因为（访问越界地址变换过程可能会因为（访问越界 ）、（）、（ 缺页缺页 ）

74、和（）和（ 访问权限错误访问权限错误 ）等原因而产生中断。）等原因而产生中断。2.分区存储管理方案不能实现虚存的原因分区存储管理方案不能实现虚存的原因是（是（ 连续内存分配连续内存分配 ）。）。3.采用交换技术来获得好处是以牺牲（时采用交换技术来获得好处是以牺牲（时间间 ）为代价的）为代价的1064.设有设有8页的逻辑空间，每页有页的逻辑空间，每页有1024字，字，它们被映射到它们被映射到32块的物理主存区中。那块的物理主存区中。那么逻辑地址的有效位是（么逻辑地址的有效位是（13 ）位，物）位，物理地址至少为（理地址至少为（ 15 )位。位。5.计算机计算机CPU为为32b，主存为，主存为32MB，该机，该机物理空间为（物理空间为（ 32MB ），逻辑空间为（），逻辑空间为（ 4G ）。）。6.动态页式系统中的页表比静态页式中的动态页式系统中的页表比静态页式中的页表项增加了（页表项增加了（ 驻留位驻留位 ）、（）、（ 修修改位改位 )和外存地址，决定淘汰页是否和外存地址，决定淘汰页是否写回外存的页表项中的依据是（写回外存的页表项中的依据是（修改位修改位 ）。）。107