Question

操作系统请求分页存储方式的基本原理是什么？谢谢？

Answer 1

3．请求分页系统(1)请求分页对页表的扩充
在请求分页系统中所使用的主要数据结构仍然是页表。它对页式系统中的页表机制进行了扩充但其基本作用是实现由用户地址空间到物理内存空间的映射。由于只将应用程序的一部分装入内存，还有一部分仍在磁盘上，故需在页表中增加若干项，供操作系统实现虚拟存储器功能时参考。常见的系统中，一般对页表的表项进行如下扩充：除了页号对应的物理块号，还增加了状态位、修改位、外存地址和访问字段等。
·状态位，用于指示该页是否已经调入了内存。该位一般由操作系统软件来管理，每当操作系统把一页调人物理内存中时，置位。相反，当操作系统把该页从物理内存调出时，复位。CPU对内存进行引用时，根据该位判断要访问的页是否在内存中，若不在内存之中，则产生缺页中断。
·修改位，表示该页调入内存后是否被修改过。当CPU以写的方式访问页面时，对该页表项中的修改位置位。该位也可由操作系统软件来修改，例如，当操作系统将修改过页面保存在磁盘上后，可将该位复位。
·外存地址，用于指出该页在外存上的地址，供调人该页时使用。
·访问宇段，用于记录本页在一定时间内被访问的次数，或最近已经有多长时间未被访问。提供给相应的置换算法在选择换出页面时参考。
(2)对缺页中断的支持
在请求分页系统中，CPU硬件一定要提供对缺页中断的支持，根据页表项中的状态位判断是否产生缺页中断。缺页中断是一个比较特殊的中断，这主要体现在如下两点：
·在指令的执行期间产生和处理缺页信号。通常的CPU外部中断，是在每条指令执行完毕后检查是否有中断请求到达。而缺页中断，是在一条指令的执行期间，发现要访问的指令和数据不在内存时产生和处理的。
·一条指令可以产生多个缺页中断。例如，一条双操作数的指令，每个操作数都不在内存中，这条指令执行时，将产生两个中断。CPU提供的硬件支持，还要体现在当从中断处理程序返回时，能够正确执行产生缺页中断的指令。
(3)页面调度策略
虚拟存储器系统通常定义三种策略来规定如何(或何时)进行页面调度：调入策略、置页策略和置换策略。
(4)置换算法(replacementalgorithm)决定在需要调入页面时，选择内存中哪个物理页面被置换。置换算法的出发点应该是，把未来不再使用的或短期内较少使用的页面调出。而未来的实际情况是不确定的，通常只能在局部性原理指导下依据过去的统计数据进行预测。常用的算法有以下几种：
·最佳算法(optimal，OPT)。选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现，只能用作性能评价的依据。
·最近最久未使用算法(LeastRecentlyUsed，LRU)。选择内存中最久未使用的页面被置换，这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。LRU可用如下的硬件机构帮助实现：
一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。
·先进先出算法(FIFO)。选择装入最早的页面置换。可以通过链表来表示各页的装入时间先后。FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。Belady现象可形式化地描述为：一个进程户要访问M个页，OS分配舻个内存页面给进程P；对一个访问序列S，发生缺页次数为PE(占，N)。当N增大时，PE(S，N)时而增大时而减小。Belady现象的原因是FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。
·时钟(clock)算法。也称最近未使用算法(NotRecentlyUsed，NRU)，它是LRU和FIFO的折中。每页有一个使用标志位(usebit)，若该页被访问则置userbit=l，这是由CPU的硬件自动完成的。置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找usebit=0的面作为被置换页。指针经过的userbit=l的页都修改userbit=O，这个修改的过程是操作系统完成的，最后指针停留在被置换页的下一个页。
·最不常用算法(LeastFrequentlyUsed，LFU)。选择到当前时间为止被访问次数最少的页面被置换。每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1。发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零。
·页面缓冲算法(pagebuffering)。它是对FIFO算法的发展，通过建立置换页面的缓冲，这样就有机会找回刚被置换的页面，从而减少系统I／0的开销。页面缓冲算法用FIFO算法选择被置换页，把被置换的页面放人两个链表之一。即是如果页面未被修改，就将其归人到空闲页面链表的末尾，否则将其归人到已修改页面链表。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，被访问的页面就可以返还作为进程的内存页。需要调入新的物理页面时，将新页面内容读人到空闲页面链表的第一项所指的页面，然后将第一项删除。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归人空闲页面链表。这样能大大减少I／O操作的次数。