《操作系统课件chap5-2》由会员分享，可在线阅读，更多相关《操作系统课件chap5-2（25页珍藏版）》请在金锄头文库上搜索。
1、5.2 请求分页存储管理方式Demanding Paged-Memory Management请求页式管理在作业或进程开始执行之前，只把当前需要的一部分页面装入主存，其它部分在作业执行过程中需要时，再从辅存上调入主存。5.2.1请求分页中的硬件支持 为了实现请求分页，系统必须提供一定的硬件支持。它除了需要一台具有一定容量的内存及外存的计算机系统外，还需要有页表机制、缺页中断机构以及地址变换机构。1.页表机制(PageTableMechanism)u基本作用仍是将LA变换为PA。页号修改位M状态位p物理块号访问字段A外存地址（1）状态位：表示该页是否在主存。中断位为0表示该页在主存；为1表示不在
2、主存。（2）修改位：该位为0时，表示该页面中的数据未被修改过。该位为1时，表示该页面中的信息已被修改过。（3）访问字段：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。（4）外存地址：指出该页面在外存上的存放地址。2.缺页中断机构Page fault interrupt mechanismn在请求分页系统中，每当所要访问的页面不在内存时，便要产生一个缺页中断，请求OS将所缺之页调入内存。n缺页中断和一般中断的区别： （1）在指令执行期间产生和处理中断信号。 （2）一条指令在执行期间，可能产生多次中断，在图4-23中的例子中，执行一条 copy A
3、 to B的指令，可能要产生6次缺页中断。 B:A:Copy ATo B指令图4-23涉及6次缺页中断的指令3. 地址变换机构修改访问位和修改位访问页表Os命令CPU从外存读缺页修改快表形成物理地址CPU检索快表修改页表将一页从外存读到内存将该页写回外存启动I/O硬件选择一页换出从外存中找到缺页保留CPU现场该页被修改否？内存满否？开始地址变换结束页表项在快表中吗？页号页表长度越界中断页在内存？缺页中断处理程序请求访问一页产生缺页中断请求调页YNYNYYYNNn在为进程分配物理块时，又将涉及到这样三个问题：第一，进程能正常运行所需的最少物理块数的确定；第二，为每个进程分配的固定的还是可变的物理
4、块；第三，物理块的分配算法。1. 最小物理块数的确定(Determination of minimum blocks)n是指保证进程正常运行所需的最少物理块数。此值与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。n单地址指令直接寻址方式，所需的最少物理块数为2。n单地址指令间接寻址方式，所需的最少物理块数为3。n对于指令长度超过2个字节的机器，至少为每个进程分配6个物理块，以装入6个页面。5.2.2 页面分配策略和分配算法2. 物理块的分配策略 在请求分页系统中，可采取固定和可变两种分配策略，可采取全局置换和局部置换，可组合出三种适用的策略： 1) 固定分配局部置换 2) 可变分配全
5、局置换 3) 可变分配局部置换3. 分配方法 1) 平均分配算法：将系统中所有物理块平均分配给各个进程。 2) 按比例分配算法：根据进程的大小按比例分配物理块。 3) 考虑优先权的分配算法：为重要的、紧迫的作业分配较多的内存空间。1. 何时调入页面 1) 预调页策略 采取一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存，如果预测较准确，那么，这种策略显然是很有吸引力的。但遗憾的是，目前预调页的成功率仅约50%。 2) 请求调页策略 当进程在运行中需要访问某部分程序和数据时，发现其所在的页面不在内存，需立即提出请求，又系统将其所需页面调入内存。在目
6、前的虚拟存储器中，大多采用此策略。但它在调页时须花费较大的系统开销，增加了磁盘I/O的启动频率，因为每次请求只调入一页。5.2.3 调页策略 Page Put-in Strategy 在请求分页系统中，可把外存分为文件区和对换区两部分，每当发生缺页请求时，系统应从何处将缺页调入内存，对于不同的系统，所采用的方法不尽相同，可分成三种情况： （1）系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度； （2）系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时再从对换区调入； （3）UN
7、IX方式，由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾运行过而又被换出的页面，下次从对换区调入。对于共享页面，采取特殊的方法。2. 从何处调入页面3. 页面调入过程 缺页中断程序通过查找页表，得到该页在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。 如果内存已满，则须先按某种置换算法，从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写入磁盘；但如果此页已被修改，则必须将它重新写入磁盘，然后再将缺页调入内存，并修改页表中的相应页表项，将其存在位置设为1，再将此页表项写入快表中。 在将缺页调入内存后，
8、利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。4. 缺页率5.3 页面置换算法n把选择换出页面的算法称为页面置换算法。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生“抖动”（Thrashing）。即刚被换出的页很快又被访问，需重新调入，为此，又需在选一页调出；而此刚被换出的页，很快又要被访问，因而又需将它调入，如此频繁地更换页面，以至一个进程在运行中，将大部分时间花费在完成页面调度的工作上，我们称该进程发生了“抖动”。n一个好的页面调度算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在
9、较长时间内不会再访问的页面调出。5.3.1 最佳置换算法和先进先出算法 OPT and FIFO Algorithm1. 最佳(Optimal)置换算法 OPT算法所选择的被淘汰页面，将是永久不使用的，或者是在最长时间内不再被访问的页面。对于固定分配页面方式 ，采用OPT算法可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。例子：701203042303212017017707012012032432032017016次置换2. 先进先出页面置换算法（FIFO） 这是最早出
10、现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老页面。但该算法与进程实际运行的规律不相适应，它不能保证那些经常被访问的页面不被淘汰。例子：7012030423032120170177070120123123043042042302301301271270270112次置换5.3.2 最近最久未使用LRU置换算法Least Recently Used Replacement Algorithm1. LRU置换算法的描述 FIFO的性能之
11、所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。LRU算法则是根据页面调入内存后的使用情况。选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。例子：701203042303212017017707012012034034024320321321021079次置换2. LRU 算法的硬件支持 Hardware Support of LRU Algorithm 把LRU算法作为页面置换算法是比较好的，它对于
12、各种类型的程序都能适用，但实现起来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有：（1）一个进程在内存中的各个页面有多久未被进程访问；（2）如何快速地知道哪一页是最近最久未使用的页面。为此，须利用以下两类支持硬件： 1.寄存器(register) 2.栈(stack)1) 寄存器n用于记录某进程在内存中各页的使用情况。所以，需为每个内存中的页面配置一个移位寄存器，可表示为： R= R n-1 R n-2 R n-3. R 2 R 1 R 0 当进程访问某物理块时，要将相应的寄存器的R n-1置成1。此时，定时信号将每隔一定时间（例如100ms)将寄存器右移一位。如果我们把n
13、位寄存器的数看作是一个页符号的整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。2) 栈n可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新访问页面的编号，而栈底则是最近最久未使用页面的页面号。n例子：47071012126474074704170401741074210741207421074621075.3.3 Clock置换算法n虽然LRU算法是一种比较好的置换算法，但由于它要求有较多的硬件支持，使实现起来成本较高。因此，在实际应用中，大多采用LRU的近似算法。Clock算法就是用得
14、较多的一种LRU近似算法。1. 简单的Clock置换算法 利用Clock算法时，只须为每页设置一位访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置被置1。置换算法在选择一页淘汰时，只须检查其访问位。如果是0，就选择换出；若为1，则重新将它复0，暂不换出而给该页第二次驻留内存的机会，在按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回队首再去检查第一个页面。块号页号 访问位0124034215650711指针替换指针图4-30简单Clock置换算法的流程与示例入口返回查询指针前进一步，指向下一个表目页面访问位=0？选择
15、该页面淘汰置页面访问位=“0”N2. 改进型Clock置换算法n在改进型Clock算法中，除了考虑到页面的使用情况外，还须再增设一个置换代价这一因素。这样，选择换出页面时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足两条件的页面作为首选淘汰的页。n由访问位A和修改位M可以组合为四种类型的页面：1 类(A=0, M=0)。该页最近既未被访问、又未被修改，最佳淘汰页。2 类(A=0, M=1)。该页最近既未被访问，但被修改，不是很好的淘汰页。3 类(A=1, M=0)。最近已被访问，但未被修改，该页有可能再被访问。4 类(A=1, M=1)。最近已被访问且被修改，该页可能再被访问。n改
16、进型Clock算法的执行过程可分成以下三步： (1) 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。 (2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所经过的页面的访问位置0。 (3)如果第二步也失败，即未找到第二类页面，则将指针返回开始的位置，并所有的访问位置0。然后，重复第一轮，如果仍失败，再重复第二步，此时就一定能找到被淘汰的页。n该算法与简单Clock算法比较，可以减少磁盘的I/O操作次数。5.3.4 其它置换算法1. 最少使用(Least Frequently Used)置换算法 在采用该算法时，应为在内存中的每个页面设置一移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面（即Ri的值最小的页）作为淘汰页。2. 页面缓冲算法(Page Buffering Algorithm) 该算法采用了前述的可变分配和局部置换方式。置换算法采用的是FIFO
