计算机操作系统.ppt

《计算机操作系统.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统.ppt（32页珍藏版）》请在优知文库上搜索。

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）分段保护分段保护中断处理中断处理缺段中断处理缺段中断处理分段越界分段越界中断处理中断处理返回返回访问访问sw w段长？段长？符合存取方式符合存取方式段段s在主存在主存?否否否否否否是是是是是是图图4-32 请求分段系统的地址变换过程请求分段系统的地址变换过程3. 地址变换机构地址变换机构4.8.2分段共享与保护分段共享与保护Segment Sharing and Protection1. 共享段表共享段表 (1) 共享进程计数共享