计算机操作系统合编.ppt

4.7 页面置换算法 一个好的页面调度算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不会再访问的页面调出。 4.7.1 最佳置换算法和先进先出算法 OPT and FIFO Algorithm 1. 最佳(Optimal)置换算法 OPT算法所选择的被淘汰页面，将是永久不使用的，或者是在最长时间内不再被访问的页面。对于固定分配页面方式 ，采用OPT算法可保证获得最低的缺页率。可利用该算法去评价其它算法。 2. 先进先出页面置换算法（FIFO） 该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。但该算法与进程实际运行的规律不相适应，它不能保证那些经常被访问的页面不被淘汰。 4.7.2 最近最久未使用LRU置换算法Least Recently Used Replacement Algorithm 1. LRU置换算法的描述 LRU算法则是根据页面调入内存后的使用情况。选择最近最久未使用的页面予以淘汰。 1) 寄存器 用于记录某进程在内存中各页的使用情况。所以，需为每个内存中的页面配置一个移位寄存器，可表示为： R= R n-1 R n-2 R n-3... R 2 R 1 R 0 当进程访问某物理块时，要将相应的寄存器的R n-1置成1。此时，定时信号将每隔一定时间（例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个页符号的整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。 2) 栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是必威体育精装版访问页面的编号，而栈底则是最近最久未使用页面的页面号。 4.7.3 Clock置换算法 虽然LRU算法是一种比较好的置换算法，但由于它要求有较多的硬件支持，使实现起来成本较高。因此，在实际应用中，大多采用LRU的近似算法。Clock算法就是用得较多的一种LRU近似算法。 1. 简单的Clock置换算法 利用Clock算法时，只须为每页设置一位访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置被置1。置换算法在选择一页淘汰时，只须检查其访问位。如果是0，就选择换出；若为1，则重新将它复0，暂不换出而给该页第二次驻留内存的机会，在按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回队首再去检查第一个页面。 2. 改进型Clock置换算法 在改进型Clock算法中，除了考虑到页面的使用情况外，还须再增设一个置换代价这一因素。这样，选择换出页面时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足两条件的页面作为首选淘汰的页。 由访问位A和修改位M可以组合为四种类型的页面： 1 类(A=0, M=0)。该页最近既未被访问、又未被修改，最佳淘汰页。 2 类(A=0, M=1)。该页最近既未被访问，但被修改，不是很好的淘汰页。 3 类(A=1, M=0)。最近已被访问，但未被修改，该页有可能再被访问。 4 类(A=1, M=1)。最近已被访问且被修改，该页可能再被访问。 改进型Clock算法的执行过程可分成以下三步： (1) 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。 (2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所经过的页面的访问位置0。 (3)如果第二步也失败，即未找到第二类页面，则将指针返回开始的位置，并所有的访问位置0。然后，重复第一轮，如果仍失败，再重复第二步，此时就一定能找到被淘汰的页。 该算法与简单Clock算法比较，可以减少磁盘的I/O操作次数。 4.8 请求分段存储管理方式 4.8.1请求分段中的硬件支持 1. 段表机制 4.8.2分段共享与保护Segment Sharing and Protection 1. 共享段表 (1) 共享进程计数count：记录有多少个进程共享该分段； (2) 存取控制字段：每个进程关于该段的存取权限； (3) 段号：不同的进程可以使用不用的段号去共享该段。 2. 共享段的分配与回收Allocation and Return of Shared S