lru算法及例题讲解 lru算法？
lru算法？
LRU算法的设计原则是：如果一个数据最近一段时间没有被访问过，那么它在将来就不太可能被访问。换言之，当有限的空间充满数据时，应该消除最长时间未被访问的数据。
执行LRU
1。使用数组存储数据，用访问时间戳标记每个数据项。插入新数据项时，首先增加数组中现有数据项的时间戳，将新数据项的时间戳设置为0，然后将其插入数组中。每次访问数组中的数据项时，所访问数据项的时间戳都设置为0。当数组空间已满时，时间戳最大的数据项将被删除。
2. 使用链表实现，每次插入新数据时，将新数据插入链表的头部；每次缓存命中时，将数据移动到链表的头部（即访问数据）；然后在链表已满时丢弃链表末尾的数据。
3. 使用链表和HashMap。当需要插入新数据项时，如果新数据项存在于链表中（通常称为hit），请将节点移动到链表的头部。如果不存在，则创建一个新节点并将其放在链表的头部。如果缓存已满，请删除链表的最后一个节点。在访问数据时，如果链表中存在该数据项，则节点会移到链表的头，否则返回-1。这样，链表末尾的节点就是最近不可访问的数据项。
对于第一种方法，需要连续维护数据项的访问时间戳。另外，在插入数据、删除数据和访问数据时，时间复杂度为O（n）。对于第二种方法，链表的时间复杂度为O（n）。所以一般来说，第三种方法是实现LRU算法。
LFU算法LFU算法过程是什么，呵LRU算？
LRU是最近最少使用的页面替换算法（最近最少使用），即首先消除最长未使用的页面！LFU是最近使用最少的页面替换算法（最少频繁使用），即在一定时间内消除最少访问的页面！例如，第二方法的周期T是10分钟。如果每分钟分页一次，则内存块为3，如果所需的页方向为2121234，请注意，调用第4页时会出现缺页。根据LRU算法，第1页应该被替换（第1页的使用时间最长），但是第3页应该根据LFU算法被替换（第3页每十分钟才使用一次）。可以看出，LRU的关键是看页面从上次使用到调度的时间，而LFU的关键是看页面在一定时间段内的使用频率
LRU算法，缺页是什么概念？怎么计算缺页次数？
根据LRU算法，需要替换上次使用最远的页面。首先，2页、3页和2页进入内存（进程只分配到3页，顺序是从内到外。当第二个2进入时，没有缺页，因此缺2页）。当1进入时，内存未满，内存中没有1页，即第一页进入内存，所以顺序是2、3、1（缺页1次）。下一页是5。替换3（缺页1次），下一页为2、1、5、2。内存中没有第2页。继续下一页。下一页输入4，4替换1得到2，5，4（缺页一次）。下一页进入第5页。内存中没有第5页。继续下一页。下一页输入3，3替换2得到3，5，4（缺页一次）。下一页输入2，2替换4得到3，5，2（缺页一次）。如果2和5内存都有，则无需更换。所以有七个分页符。你的分析有问题。你不妨画一幅画
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
