网站怎么做百度的关键字,推广平台取名字,网络规划设计师报名费,wordpress设置显示为英文地址映射过程中#xff0c;若在页面中发现所要访问的页面不再内存中#xff0c;则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存#xff0c;以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。常见的置换算法有若在页面中发现所要访问的页面不再内存中则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。常见的置换算法有
1最佳置换算法OPT理想置换算法
这是一种理想情况下的页面置换算法但实际上是不可能实现的。该算法的基本思想是发生缺页时有些页面在内存中其中有一页将很快被访问也包含紧接着的下一条指令的那页而其他页面则可能要到10、100或者1000条指令后才会被访问每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。
2先进先出置换算法FIFO
最简单的页面置换算法是先入先出FIFO法。这种算法的实质是总是选择在主存中停留时间最长即最老的一页置换即先进入内存的页先退出内存。理由是最早调入内存的页其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时就把它插在队尾上。 这种算法只是在按线性顺序访问地址空间时才是理想的否则效率不高。因为那些常被访问的页往往在主存中也停留得最久结果它们因变“老”而不得不被置换出去。 FIFO的另一个缺点是它有一种异常现象即在增加存储块的情况下反而使缺页中断率增加了。当然导致这种异常现象的页面走向实际上是很少见的。
3最近最久未使用LRU算法
FIFO算法和OPT算法之间的主要差别是FIFO算法利用页面进入内存后的时间长短作为置换依据而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是当需要置换一页时选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法Least Recently UsedLRU。 LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时LRU算法选择过去一段时间里最久未被使用的页面。 LRU算法是经常采用的页面置换算法并被认为是相当好的但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序对此有两种可行的办法 1.计数器。最简单的情况是使每个页表项对应一个使用时间字段并给CPU增加一个逻辑时钟或计数器。每次存储访问该时钟都加1。每当访问一个页面时时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时选择该时间值最小的页面。这样做不仅要查页表而且当页表改变时因CPU调度要维护这个页表中的时间还要考虑到时钟值溢出的问题。 2.栈。用一个栈保留页号。每当访问一个页面时就把它从栈中取出放在栈顶上。这样一来栈顶总是放有目前使用最多的页而栈底放着目前最少使用的页。由于要从栈的中间移走一项所以要用具有头尾指针的双向链连起来。在最坏的情况下移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销但需要置换哪个页面却可直接得到用不着查找因为尾指针指向栈底其中有被置换页。 因实现LRU算法必须有大量硬件支持还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。 一种LRU近似算法是最近未使用算法Not Recently UsedNUR。它在存储分块表的每一表项中增加一个引用位操作系统定期地将它们置为0。当某一页被访问时由硬件将该位置1。过一段时间后通过检查这些位可以确定哪些页使用过哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去因为在最近一段时间里它未被访问过。
4Clock置换算法LRU算法的近似实现
5最少使用LFU置换算法
在采用最少使用置换算法时应为在内存中的每个页面设置一个移位寄存器用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度例如100 ns在1 ms时间内可能对某页面连续访问成千上万次因此通常不能直接利用计数器来记录某页被访问的次数而是采用移位寄存器方式。每次访问某页时便将该移位寄存器的最高位置1再每隔一定时间(例如100 ns)右移一次。这样在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同或者说利用这样一套硬件既可实现LRU算法又可实现LFU算法。应该指出LFU算法并不能真正反映出页面的使用情况因为在每一时间间隔内只是用寄存器的一位来记录页的使用情况因此访问一次和访问10 000次是等效的。
参考http://hary.wang.blog.163.com/blog/static/11695172820104945040438/
6工作集算法
参考http://hi.baidu.com/binbin_88115/blog/item/f2787a386d2eb7d8d5622595.html
7工作集时钟算法
8老化算法非常类似LRU的有效算法
9NRU(最近未使用算法
10第二次机会算法
第二次机会算法的基本思想是与FIFO相同的但是有所改进避免把经常使用的页面置换出去。当选择置换页面时检查它的访问位。如果是0就淘汰这页如果访问位是1就给它第二次机会并选择下一个FIFO页面。当一个页面得到第二次机会时它的访问位就清为0它的到达时间就置为当前时间。如果该页在此期间被访问过则访问位置1。这样给了第二次机会的页面将不被淘汰直至所有其他页面被淘汰过或者也给了第二次机会。因此如果一个页面经常使用它的访问位总保持为1它就从来不会被淘汰出去。 第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时指针就前进直至找到访问位是0的页。随着指针的前进把访问位就清为0。在最坏的情况下所有的访问位都是1指针要通过整个队列一周每个页都给第二次机会。这时就退化成FIFO算法了。
