lru置换算法

❶ LRU替换算法怎么理解，过程好难，这个题麻烦大神帮我看看

• LRU是LeastRecently Used 近期最少使用算法，也就是说，近期最少使用的那个页面，将被置换出去（可以理解为这个页面将被废弃）

• 对于本题。内存容量为4个页面，这是要清楚的。具体看下面的表格：

• 缺页率 = 6 / 20 =3/ 10 = 30%

• 我具体解释下上面的表格吧。

  从上到下是4个页面。

• 最开始，1需要被调用，将1放入内存中，由于1一开始没有，所以一次缺页

• 然后，8要被调用，，将1放入内存中，由于8一开始没有，所以又产生一次缺页

• 以此往后，直到4块内存都满了，最新使用过的放在最下面（页4），则置换出最上面（页1）。

• 通俗地说，就是总共空间只有4块。只能放4个页面。那么当页面满的时候，就把你很久很久没有使用过的那个页面（也就是近期最少使用的页面）置换出去，然后补充新的页面进来。

• 这个算是页面置换里面比较经典的一个算法了，希望能帮到你！
  

❷ 操作系统 页面置换算法LRU

这两种方法都正确，LRU算法有几种实现，前一种是基于计数器的，需要统计之前的引用页，后一种是基于队列的调度，只调整队列就能找到最近未使用的页。
如果是考试的话可以说明一下用了哪种方法，个人感觉第二种方法比较合适
《操作系统概念》第七版·高等教育出版社P286

❸ 什么是lru置换算法

LRU是Least
Recently
Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。
LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。
这是一个相当好的算法，它是理想算法很好的近似。

❹ 一个程序的页面走向，FIFO和LRU页面置换算法

FIFO(先进先出页面置换算法)：
1 2 3 4 1 2 5 1 2 3 4 5
————————————
1 1 1 1 1 1 2 3 4 5 1 2
2 2 2 2 2 3 4 5 1 2 3
3 3 3 3 4 5 1 2 3 4
4 4 4 5 1 2 3 4 5
X X X X X X X X X X
共10次缺页中断

LRU（最近最少使用页面置换算法）：
1 2 3 4 1 2 5 1 2 3 4 5
————————————
1 1 1 1 2 3 4 4 4 5 1 2
2 2 2 3 4 1 2 5 1 2 3
3 3 4 1 2 5 1 2 3 4
4 1 2 5 1 2 3 4 5
X X X X X X X X

共八次缺页中断

❺ LRU置换算法的疑问

sd

❻ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

❼ LRU页面置换算法的实现

我会。就是最近未使用的算法吧。例如一个三道程序，等待进入的是1，2，3，4，4，2，5，6，3，4，2，1。先分别把1，2，3导入，然后导入4，置换的是1，因为他离导入时间最远。然后又是4，不需要置换，然后是2，也不需要，因为内存中有，到5的时候，因为3最远，所以置换3，依次类推，还有不懂联系我吧。QQ：243926566

❽ FIFO和LRU置换算法的问题

FIFO 先进先出
-------------
刚开始内存为空 null, null, null
使用2，缺页读入 2, null, null
使用3，缺页读入 2, 3, null
使用2，直接使用 2, 3, null
使用1，缺页读入 2, 3, 1
使用5，缺页读入 3, 1, 5 因为2是最先读入的，所以就把它删掉
使用2，缺页读入 1, 5, 2
使用4，缺页读入 5, 2, 4
使用5，直接使用 5, 2, 4
使用3，缺页读入 2, 4, 3
使用2，直接使用 2, 4, 3
使用5，缺页读入 4, 3, 5
使用2，缺页读入 3, 5, 2

共9次缺页
========================

LRU 会删除最不常访问的
----------------------
刚开始内存为空 null, null, null
使用2，缺页读入 2, null, null
使用3，缺页读入 3, 2, null
使用2，直接使用 2, 3, null
使用1，缺页读入 1, 2, 3
使用5，缺页读入 5, 1, 2 因为最近1和2都访问过而3是很早之前用过的，所以就把它删掉
使用2，直接使用 2, 5, 1
使用4，缺页读入 4, 2, 5
使用5，直接使用 5, 4, 2
使用3，缺页读入 3, 5, 4
使用2，缺页读入 2, 3, 5
使用5，直接使用 5, 2, 3
使用2，直接使用 2, 5, 3

共7次缺页

❾ LRU 页面置换算法

问题是很简单的，只是代码写起来比较费劲。比较的结果就是Belady现象，也就是随着增加分配给作业的内存块数，反而增加了缺页次数，提高了缺页率。

❿ 页面置换算法的常见的置换算法

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