前言
上個(gè)星期跟幾位朋友一起開了個(gè)公眾號(hào) “ 于你供讀 ”虑绵，每日推送Android，iOS闽烙，UI翅睛，前端，產(chǎn)品和生活情感的文章黑竞。好了捕发，入正題，這個(gè)星期的面試題是 今日頭條的面試題很魂。
題目
操作系統(tǒng)中可以使用 LRU（Least Recently Used）內(nèi)存淘汰舊數(shù)據(jù)的策略扎酷，如果內(nèi)存需要加載新數(shù)據(jù)但空間不足，則會(huì)按照最近訪問時(shí)間進(jìn)行排序遏匆，并將最老的數(shù)據(jù)淘汰法挨。假設(shè)現(xiàn)在內(nèi)存空間大小為 5，原本內(nèi)存中沒有數(shù)據(jù)幅聘，對(duì)內(nèi)存中數(shù)據(jù)的訪問順序如下：
1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9
問訪問過程中發(fā)生缺頁的次數(shù)是多少次凡纳？A. 缺頁次數(shù)：4
B. 缺頁次數(shù)：10
C. 缺頁次數(shù)：5
D. 缺頁次數(shù)：9
知識(shí)點(diǎn)
要解決上面的題目，首先我們先要了解什么是缺頁
缺頁中斷
在請(qǐng)求分頁系統(tǒng)中帝蒿，可以通過查詢頁表中的狀態(tài)位來確定所要訪問的頁面是否存在于內(nèi)存中荐糜。每當(dāng)所要訪問的頁面不在內(nèi)存時(shí)，會(huì)產(chǎn)生一次缺頁中斷，此時(shí)操作系統(tǒng)會(huì)根據(jù)頁表中的外存地址在外存中找到所缺的一頁暴氏，將其調(diào)入內(nèi)存丛版。
缺頁本身是一種中斷，與一般的中斷一樣偏序，需要經(jīng)過4個(gè)處理步驟：
- 保護(hù)CPU現(xiàn)場(chǎng)
- 分析中斷原因
- 轉(zhuǎn)入缺頁中斷處理程序進(jìn)行處理
- 恢復(fù)CPU現(xiàn)場(chǎng)页畦，繼續(xù)執(zhí)行
但是缺頁中斷時(shí)由于所要訪問的頁面不存在與內(nèi)存時(shí)，有硬件所產(chǎn)生的一種特殊的中斷研儒，因此豫缨，與一般的中斷存在區(qū)別：
- 在指令執(zhí)行期間產(chǎn)生和處理缺頁中斷信號(hào)
- 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷
- 缺頁中斷返回時(shí)端朵，執(zhí)行產(chǎn)生中斷的那一條指令好芭，而一般的中斷返回時(shí)，執(zhí)行下一條指令
還有一點(diǎn)就是我們必需了解 LRU 算法冲呢，這個(gè)算法使用頻率還是相當(dāng)?shù)母叩纳岚埽虼宋覀円膊荒吧?/p>
LRU
LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)敬拓，其核心思想是“如果數(shù)據(jù)最近被訪問過邻薯，那么將來被訪問的幾率也更高”。
LRU 最常見的實(shí)現(xiàn)是使用一個(gè)鏈表保存緩存數(shù)據(jù)乘凸，詳細(xì)算法實(shí)現(xiàn)如下：
- 新數(shù)據(jù)插入到鏈表頭部厕诡；
- 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部营勤；
- 當(dāng)鏈表滿的時(shí)候灵嫌，將鏈表尾部的數(shù)據(jù)丟棄。
解題
這道題目答案選擇 B 葛作，缺頁數(shù)為 10寿羞，我把解題思路弄了一個(gè)流程圖出來，可以看下赂蠢。
最后用 JAVA 來模擬一下：
Github：LRU.java
