LRU算法

$LeastRecentlyUsed$ 算法，意為“最近最少使用”，這是操作系統(tǒng)內(nèi)存管理部分重要的一個(gè)頁置換算法。

解釋：LRU chooses that page that has not been used for the longest period of time.

追溯Operating System

Operating System 中特別重要的三個(gè)頁置換算法：

• First-In-First-Out (FIFO) Algorithm
• Optimal Algorithm
• Least Recently Used (LRU) Algorithm

當(dāng)然還有很多其他算法，比如LRU Approximation Algorithms，不提……

Optimal Algorithm 與 LRU Algorithm

Optimal Algorithm 為什么是“最優(yōu)”呢？因?yàn)樗畚磥?#xff0c;但實(shí)際上，“未來并不可以準(zhǔn)確預(yù)測”，所以不能在計(jì)算機(jī)上真正實(shí)現(xiàn)，但LRU是可以的。

LRU的思想，恰如其名，著眼于過去，它根據(jù)過去的使用做出判斷。

簡而言之，就是“誰最近沒被用過，就把誰換出去”，棧和隊(duì)列這樣的數(shù)據(jù)結(jié)構(gòu)就可以幫助我們實(shí)現(xiàn)這一點(diǎn)。
當(dāng)然，也可以對頁面的引用時(shí)間進(jìn)行計(jì)時(shí)，通過計(jì)時(shí)進(jìn)行頁置換。

LRU算法實(shí)例

給出一個(gè) reference string ：“7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1”，置換順序如下：（注意下圖前三次也是換進(jìn)去的呀，每個(gè)頁都是經(jīng)歷Demand Paging才得以從外存換入內(nèi)存的）

棧實(shí)現(xiàn)的解讀

比如下圖，在 a → b 的時(shí)候，相當(dāng)于把7號頁從棧中抽出來放到棧底（注意棧底在頂部），從棧頂換出頁，新?lián)Q入的頁插入棧底。（實(shí)際上就相當(dāng)于隊(duì)列結(jié)構(gòu)啦）

洛谷P1540題

題目要求

P1540題目鏈接

分析

在有經(jīng)驗(yàn)的人看來，確實(shí)，普通的模擬+使用隊(duì)列作為輔助數(shù)據(jù)結(jié)構(gòu)，一個(gè)小題。

問題是，你還想到了什么？
沒錯(cuò)——LRU算法！

其實(shí)這題的背景本身就是OS的虛擬內(nèi)存頁置換算法啊！

AC代碼（Java語言描述）

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class Main {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();Scanner scanner = new Scanner(System.in);int limit = scanner.nextInt(), num = scanner.nextInt(), counter = 0, result = 0;while (queue.size() <= num && result < limit) {int temp = scanner.nextInt();if (!queue.contains(temp)) {queue.offer(temp);result++;}counter++;}for (int i = counter; i < num; i++) {int temp = scanner.nextInt();if (!queue.contains(temp)) {queue.poll();queue.offer(temp);result++;}}scanner.close();System.out.println(result);} }

總結(jié)

LRU算法是一種重要的算法。比起算法本身，更重要的是領(lǐng)會(huì)到LRU算法的思想，并能在處理實(shí)際問題的時(shí)候得以啟發(fā)，這樣就很好啦！

另外，OS的LRU頁置換算法也應(yīng)該深刻理解，這是涉及計(jì)算機(jī)原理的重要知識。

希望對不懂LRU算法的讀者一些啟示，也希望幫助對洛谷P1540題理解不深的讀者加深理解。
總之，希望對大家有所幫助！

總結(jié)

以上是生活随笔為你收集整理的深入理解 操作系统 LRU算法（以洛谷P1540题为例）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。