计算机操作系统

1、4.6 请求分页存储管理方式请求分页存储管理方式4.6.1 请求分页中的硬件支持请求分页中的硬件支持 为了实现请求分页，系统必须提供一定的硬件为了实现请求分页，系统必须提供一定的硬件支持。它除了需要一台具有一定容量的内存及外存支持。它除了需要一台具有一定容量的内存及外存的计算机系统外，还需要有的计算机系统外，还需要有页表机制、缺页中断机页表机制、缺页中断机构以及地址变换机构构以及地址变换机构。1. 页表机制页表机制(Page Table Mechanism)u基本作用仍是将基本作用仍是将LA变换为变换为PA。页号页号修改位修改位M状态位状态位p物理块号物理块号访问字段访问字段A外存地址外存地址

2、 （1）状态位状态位：表示该页是否在主存。中断位为：表示该页是否在主存。中断位为0表示该页表示该页在主存；为在主存；为1表示不在主存。表示不在主存。（2）修改位修改位：该位为：该位为0时，表示该页面中的数据未被修改时，表示该页面中的数据未被修改过。该位为过。该位为1时，表示该页面中的信息已被修改过。时，表示该页面中的信息已被修改过。（3）访问字段访问字段：用于记录本页在一段时间内被访问的次数，：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时或记录本页最近已有多长时间未被访问，供选择换出页面时参考。参考。（4）外存地址外存地址：指出该页面在外存上的存放

3、地址。：指出该页面在外存上的存放地址。2.缺页中断机构缺页中断机构 在请求分页系统中，每当所要访问的页面不在内在请求分页系统中，每当所要访问的页面不在内存时，便要产生一个缺页中断，请求存时，便要产生一个缺页中断，请求OS将所缺之将所缺之页调入内存。页调入内存。 缺页中断和一般中断的区别：缺页中断和一般中断的区别： （1）在指令执行期间产生和处理中断信号。）在指令执行期间产生和处理中断信号。 （2）一条指令在执行期间，可能产生多次中断。）一条指令在执行期间，可能产生多次中断。修改访问位和修改位修改访问位和修改位访问页表访问页表Os命令命令CPU从外存读缺页从外存读缺页修改快表修改快表形成物理地址

4、形成物理地址CPU检索快表检索快表修改页表修改页表将一页从外存读到内存将一页从外存读到内存将该页写回外存将该页写回外存启动启动I/O硬件硬件选择一页换出选择一页换出从外存中找到缺页从外存中找到缺页保留保留CPU现场现场该页被修改否？该页被修改否？内存满否？内存满否？开始开始地址变换结束地址变换结束页表项在快表中吗？页表项在快表中吗？页号页号页表长度页表长度越界中断越界中断页在内存？页在内存？缺页中断处理缺页中断处理程序请求访问一页程序请求访问一页产生缺页中断产生缺页中断请求调页请求调页YNYNYYYNN3. 地址变换机构地址变换机构4.7 页面置换算法页面置换算法 一个一个好的页面调度算法，应

5、具有较低的页面更换频好的页面调度算法，应具有较低的页面更换频率率。从理论上讲，应将那些以后不再访问的页面换。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不会再访问的页面调出。出，或把那些在较长时间内不会再访问的页面调出。4.7.1 最佳置换算法和先进先出算法最佳置换算法和先进先出算法 OPT and FIFO Algorithm1. 最佳最佳(Optimal)置换算法置换算法 OPT算法所选择的被淘汰页面，将是永久不算法所选择的被淘汰页面，将是永久不使用的，或者是在最长时间内不再被访问的页面。使用的，或者是在最长时间内不再被访问的页面。对于固定分配页面方式对于固定分配页面方

6、式 ，采用，采用OPT算法可保证获算法可保证获得最低的缺页率。可利用该算法去评价其它算法。得最低的缺页率。可利用该算法去评价其它算法。2. 先进先出页面置换算法（先进先出页面置换算法（FIFO） 该该算法总是淘汰最先进入内存的页面，即选算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。择在内存中驻留时间最久的页面予以淘汰。但但该算法与进程实际运行的规律不相适应，它不该算法与进程实际运行的规律不相适应，它不能保证那些经常被访问的页面不被淘汰。能保证那些经常被访问的页面不被淘汰。4.7.2 最近最久未使用最近最久未使用LRU置换算法置换算法Least Recently Us

7、ed Replacement Algorithm1. LRU置换算法的描述置换算法的描述 LRU算法则是根据页面调入内存后的使用算法则是根据页面调入内存后的使用情况。选择最近最久未使用的页面予以淘汰情况。选择最近最久未使用的页面予以淘汰。1) 寄存器寄存器 用于记录某进程在内存中各页的使用情况。所以，需为每用于记录某进程在内存中各页的使用情况。所以，需为每个内存中的页面配置一个移位寄存器，可表示为：个内存中的页面配置一个移位寄存器，可表示为： R= R n-1 R n-2 R n-3. R 2 R 1 R 0 当进程访问某物理块时，要将相应的寄存器的当进程访问某物理块时，要将相应的寄存器的R

8、n-1置成置成1。此时，定时信号将每隔一定时间（例如此时，定时信号将每隔一定时间（例如100ms)将寄存器右将寄存器右移一位。移一位。如果我们把如果我们把n位寄存器的数看作是一个页符号的位寄存器的数看作是一个页符号的整数，那么具有最小数值的寄存器所对应的页面，就是最整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。近最久未使用的页面。2) 栈栈 可利用一个特殊的栈来保存当前使用的各个可利用一个特殊的栈来保存当前使用的各个页面的页面号。页面的页面号。每当进程访问某页时，便将每当进程访问某页时，便将该页面的页面号从栈中移出，将它压入栈顶该页面的页面号从栈中移出，将它压入栈顶。因

9、此，栈顶始终是最新访问页面的编号，而因此，栈顶始终是最新访问页面的编号，而栈底则是最近最久未使用页面的页面号。栈底则是最近最久未使用页面的页面号。4.7.3 Clock置换算法置换算法 虽然虽然LRU算法是一种比较好的置换算法，但由于它要求有算法是一种比较好的置换算法，但由于它要求有较多的硬件支持，使实现起来成本较高。因此，在实际应较多的硬件支持，使实现起来成本较高。因此，在实际应用中，大多采用用中，大多采用LRU的近似算法。的近似算法。Clock算法就是用得较算法就是用得较多的一种多的一种LRU近似算法。近似算法。1. 简单的简单的Clock置换算法置换算法 利用利用Clock算法时，只须为

10、每页设置一位访问位，再将内存算法时，只须为每页设置一位访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。中的所有页面都通过链接指针链成一个循环队列。当某页当某页被访问时，其访问位置被置被访问时，其访问位置被置1。置换算法在选择一页淘汰。置换算法在选择一页淘汰时，只须检查其访问位。如果是时，只须检查其访问位。如果是0，就选择换出；，就选择换出；若为若为1，则重新将它复则重新将它复0，暂不换出而给该页第二次驻留内存的机暂不换出而给该页第二次驻留内存的机会，在会，在按照按照FIFO算法检查下一个页面算法检查下一个页面。当检查到队列中的。当检查到队列中的最后一个页面时，若其访问位仍为最后一个

11、页面时，若其访问位仍为1，则再返回队首再去，则再返回队首再去检查第一个页面。检查第一个页面。2. 改进型改进型Clock置换算法置换算法 在改进型在改进型Clock算法中，除了考虑到页面的使用情况外，还算法中，除了考虑到页面的使用情况外，还须再增设一个须再增设一个置换代价置换代价这一因素。这样，选择换出页面时，这一因素。这样，选择换出页面时，既要是未使用过的页面，又要是未被修改过的页面既要是未使用过的页面，又要是未被修改过的页面。把同。把同时满足两条件的页面作为首选淘汰的页。时满足两条件的页面作为首选淘汰的页。 由访问位由访问位A和修改位和修改位M可以组合为四种类型的页面：可以组合为四种类型的

12、页面：1 类类(A=0, M=0)。该页最近既未被访问、又未被修改，最佳淘汰页。该页最近既未被访问、又未被修改，最佳淘汰页。2 类类(A=0, M=1)。该页最近既未被访问，但被修改，不是很好的淘汰页。该页最近既未被访问，但被修改，不是很好的淘汰页。3 类类(A=1, M=0)。最近已被访问，但未被修改，该页有可能再被访问。最近已被访问，但未被修改，该页有可能再被访问。4 类类(A=1, M=1)。最近已被访问且被修改，该页可能再被访问。最近已被访问且被修改，该页可能再被访问。 改进型改进型Clock算法的执行过程算法的执行过程可分成以下三步：可分成以下三步： (1) 从指针所指示的当前位置开

13、始，扫描循环队列，寻从指针所指示的当前位置开始，扫描循环队列，寻找找A=0且且M=0的第一类页面，将所遇到的第一个页面作为所的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在选中的淘汰页。在第一次扫描期间不改变访问位第一次扫描期间不改变访问位A。 (2)如果第一步失败，即查找一周后未遇到第一类页面，如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找则开始第二轮扫描，寻找A=0且且M=1的第二类页面，将所遇的第二类页面，将所遇到的第一个这类页面作为淘汰页。到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所在第二轮扫描期间，将所经过的页面的访问位置经过的页面的访问位置0。

14、 (3)如果第二步也失败，即未找到第二类页面，则将指针如果第二步也失败，即未找到第二类页面，则将指针返回开始的位置，并返回开始的位置，并所有的访问位置所有的访问位置0。然后，重复第一轮，。然后，重复第一轮，如果仍失败，再重复第二步，此时就一定能找到被淘汰的页。如果仍失败，再重复第二步，此时就一定能找到被淘汰的页。 该算法与简单该算法与简单Clock算法比较，可以减少磁盘的算法比较，可以减少磁盘的I/O操作次数。操作次数。4.8 请求分段存储管理方式请求分段存储管理方式4.8.1请求分段中的硬件支持请求分段中的硬件支持1. 段表机制段表机制段名段名段长段长访问访问字段字段A增补增补位位存在存在位

15、位P修改修改字段字段M 存取存取方式方式外存外存始址始址段的段的基址基址(1) 存取方式：本段的存取属性存取方式：本段的存取属性;(2) 访问字段访问字段A：该段被访问的频繁程度；：该段被访问的频繁程度；(3) 修改位修改位M：该页进入内存后，是否已被修改过；：该页进入内存后，是否已被修改过；(4) 存在位存在位P：本段是否已调入内存；：本段是否已调入内存；(5) 增补位：该段是否允许动态增长；增补位：该段是否允许动态增长；(6) 外存始址：本段在外存中的起始地址，即起始盘块号。外存始址：本段在外存中的起始地址，即起始盘块号。从外存读入段从外存读入段S修改段表及内存区空链修改段表及内存区空链唤

16、醒请求进程唤醒请求进程阻塞请求进程阻塞请求进程淘汰一个或几个实段淘汰一个或几个实段以形成一个合适空区以形成一个合适空区空区拼接，以形成空区拼接，以形成一个合适的空区一个合适的空区空区容量总和空区容量总和能否满足？能否满足？内存中有合适内存中有合适的空闲区吗？的空闲区吗？返回返回虚段虚段S不在内存不在内存是是是是否否否否图图4-31 请求分段系统中的中断处理过程请求分段系统中的中断处理过程2. 缺段中断机构缺段中断机构修改访问字段，如修改访问字段，如写访问，置修改位写访问，置修改位=1形成访问主存地址形成访问主存地址(A)=(主存地址主存地址)+（位移（位移W）分段保护分段保护中断处理中断处理缺

17、段中断处理缺段中断处理分段越界分段越界中断处理中断处理返回返回访问访问sw w段长？段长？符合存取方式符合存取方式段段s在主存在主存?否否否否否否是是是是是是图图4-32 请求分段系统的地址变换过程请求分段系统的地址变换过程3. 地址变换机构地址变换机构4.8.2分段共享与保护分段共享与保护Segment Sharing and Protection1. 共享段表共享段表 (1) 共享进程计数共享进程计数count：记录有多少个进程共享该分段；：记录有多少个进程共享该分段； (2) 存取控制字段：每个进程关于该段的存取权限；存取控制字段：每个进程关于该段的存取权限； (3) 段号：不同的进程可

18、以使用不用的段号去共享该段。段号：不同的进程可以使用不用的段号去共享该段。段名段名段长段长内存始址内存始址状态状态外存始址外存始址共享进程计数共享进程计数count状态状态进程名进程名进程号进程号段号段号存取控制存取控制 共享段表共享段表图图4-33 共享段表项共享段表项2. 共享段的分配与回收共享段的分配与回收Allocation and Return of Shared Segment1) 共享段的分配共享段的分配 对于第一个请求使用该共享段的进程，由系统为对于第一个请求使用该共享段的进程，由系统为它分配一物理区，再把共享段调入该区，同时将它分配一物理区，再把共享段调入该区，同时将该区的始

19、址填入该进程的段表的相应项中，还须该区的始址填入该进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把在共享段表中增加一表项，填写有关数据，把count置置1； 之后，当又有其它进程要调用该共享段时，只需之后，当又有其它进程要调用该共享段时，只需在调用进程的段表中，增加一表项，填入该共享在调用进程的段表中，增加一表项，填入该共享段的物理地址；同时在共享段的段表中，填上进段的物理地址；同时在共享段的段表中，填上进程名、存取控制等，执行程名、存取控制等，执行count:=count+1操作。操作。2. 共享段的分配与回收共享段的分配与回收Allocation and Return o

20、f Shared Segment2) 共享段的回收共享段的回收 当共享此段的某进程不再需要该段时，应当共享此段的某进程不再需要该段时，应将该段释放，包括撤销该进程段表中共享段所将该段释放，包括撤销该进程段表中共享段所对应的表项，以及执行对应的表项，以及执行count:=count - 1操作。操作。若结果为若结果为0，则需由系统回收该共享段的物理，则需由系统回收该共享段的物理内存，取消段表中的对应表项；否则，则只是内存，取消段表中的对应表项；否则，则只是取消调用者进程在共享段表中的有关记录。取消调用者进程在共享段表中的有关记录。3. 分段保护分段保护Segment Protection 在分段

21、系统中，由于每个分段在逻辑上是独立的，在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。目前，常采用以下几因而比较容易实现信息保护。目前，常采用以下几种措施，来确保信息的安全。种措施，来确保信息的安全。 1）越界检查）越界检查 在段表中设置一个段长值，以指明该段的长度。在段表中设置一个段长值，以指明该段的长度。当存储访问时，段地址的位移量与段长相比较，如当存储访问时，段地址的位移量与段长相比较，如超过段长，便发出越界中断信号。超过段长，便发出越界中断信号。 2）存取控制检查）存取控制检查 (1)只读只读 (2)只执行只执行 (3)读读/写写 3）环保护机构）环保护机构 是一

22、种功能较完善的保护机构是一种功能较完善的保护机构.在该机制中规定在该机制中规定:低编号的环具有高优先权低编号的环具有高优先权,OS核心处于核心处于0环内环内;某些重某些重要的实用程序和操作系统服务要的实用程序和操作系统服务,占居中间环占居中间环;而一般的而一般的应用程序应用程序,则被安排在外环上则被安排在外环上.在环系统中在环系统中,程序的访问和调用应遵循以下规则程序的访问和调用应遵循以下规则:一个程序可以访问驻留在相同环或较低特权环中的数据一个程序可以访问驻留在相同环或较低特权环中的数据;一个程序可以调用驻留在相同环或较高特权环中的服务一个程序可以调用驻留在相同环或较高特权环中的服务.第四章

23、第四章 复习复习1. 程序的装入和链接及其重要概念程序的装入和链接及其重要概念 (1)编译编译(Compiling ) (2)链接链接(Linking) (3)装入装入(Loading) 绝对地址（物理地址）绝对地址（物理地址） 相对地址相对地址(逻辑地址逻辑地址) 符号地址符号地址 重定位重定位 静态重定位静态重定位 动态重定位动态重定位2. 动态分区分配算法：动态分区分配算法：FF,CFF,BF,WF 各种算法是如何来进行内存的分配和回收的？各种算法是如何来进行内存的分配和回收的？3. 造成动态分区分配方式浪费内存空间的主要原造成动态分区分配方式浪费内存空间的主要原因是什么？它可以通过什么

24、办法加以解决。因是什么？它可以通过什么办法加以解决。紧凑或拼接紧凑或拼接4. 什么是对换？对换的分类：什么是对换？对换的分类： 整体对换或进程对换；整体对换或进程对换； 部分对换或页面对换（分段对换）部分对换或页面对换（分段对换）5. 分页系统是如何将地址空间中的作业划分成若分页系统是如何将地址空间中的作业划分成若干个页，它又是如何进行内存分配的？干个页，它又是如何进行内存分配的？6. 分页系统的地址转换。掌握分页系统逻辑地址分页系统的地址转换。掌握分页系统逻辑地址的结构，为了进行逻辑地址到物理地址的转换，的结构，为了进行逻辑地址到物理地址的转换，分页系统必须为每个作业配置什么样的数据结分页系

25、统必须为每个作业配置什么样的数据结构并提供哪些硬件支持，为什么引进快表可以构并提供哪些硬件支持，为什么引进快表可以加快分页系统存取指令和数据的速度。加快分页系统存取指令和数据的速度。7. 分段存储管理方式。了解由分页发展为分段，分段存储管理方式。了解由分页发展为分段，并进一步发展为段页式存储管理方式的主要推并进一步发展为段页式存储管理方式的主要推动力是什么，分段和段页式系统是如何管理作动力是什么，分段和段页式系统是如何管理作业的地址空间和内存空间的，它们的地址变换业的地址空间和内存空间的，它们的地址变换是如何完成的，并应注意对分段系统和分页系是如何完成的，并应注意对分段系统和分页系统的比较。统

26、的比较。8. 信息的共享和保护。为什么分段比分页更容易？信息的共享和保护。为什么分段比分页更容易？9. 为什么要引入虚拟存储器？为什么要引入虚拟存储器？ 常规存储管理方式的特征（一次性和驻留性）常规存储管理方式的特征（一次性和驻留性） 局部性原理局部性原理10. 虚拟存储器的特征：多次性、对换性和虚拟性。虚拟存储器的特征：多次性、对换性和虚拟性。了解每种特征的具体含义，以及它们相互之间了解每种特征的具体含义，以及它们相互之间存在着什么样的关系？存在着什么样的关系？11. 实现虚拟存储器的关键技术是什么。关键是请实现虚拟存储器的关键技术是什么。关键是请求调页（段）技术和页（段）置换技术，这些求调

27、页（段）技术和页（段）置换技术，这些技术的实现需要得到哪些硬件和软件支持。技术的实现需要得到哪些硬件和软件支持。 （一定容量的内存和较大容量的外存，还需要（一定容量的内存和较大容量的外存，还需要缺页（段）中断结构和地址变换结构的支持）缺页（段）中断结构和地址变换结构的支持）12. 请求分页系统的基本原理请求分页系统的基本原理（1）页表机制）页表机制（2）地址变换机构和过程）地址变换机构和过程（3）页面置换算法）页面置换算法 OPT置换算法置换算法 FIFO置换算法置换算法 LRU置换算法及其近似算法置换算法及其近似算法13. 请求分段系统的基本原理。请求分段系统的基本原理。典型问题分析和解答典

28、型问题分析和解答u 什么情况下需要进行重定位？为什么要引入动什么情况下需要进行重定位？为什么要引入动态重定位？态重定位？u 在以进程为单位进行对换时，每次是否将整个在以进程为单位进行对换时，每次是否将整个进程换出进程换出?为什么？为什么？u 对一个将页表存放在内存中的分页系统：对一个将页表存放在内存中的分页系统：1）如果内存需要）如果内存需要0.2us，有效访问时间为多少？，有效访问时间为多少？u 2）如果加一快表，且假定在快表中找到）如果加一快表，且假定在快表中找到页表项的几率高达页表项的几率高达90，则有效访问时间又是，则有效访问时间又是多少（假定查快表需花的时间为多少（假定查快表需花的时间为0）？）？每次访问数据时，若不使用快表，则需要两次访问内每次访问数据时，若不使用快表，则需要两次访问内存，即先从内存的页表中读出页对应的