阿竺 ·1. 前言
操作系統(tǒng)的核心管理邏輯可以簡(jiǎn)化為進(jìn)程管理、內(nèi)存管理、文件管理。之前的小節(jié)已經(jīng)介紹了進(jìn)程的基本概念，每個(gè)進(jìn)程都有獨(dú)立的地址空間，這些地址空間被分為大小相同的塊，定義為頁(yè)（Page）。然而物理機(jī)的內(nèi)存硬件空間是有限的，舉例來(lái)說(shuō)，我們裝配最常見的 4G 內(nèi)存條，但是很多進(jìn)程例如單機(jī)游戲，運(yùn)行時(shí)都需要占用幾個(gè) G 的內(nèi)存空間，所以就需要用到虛擬內(nèi)存。
2. 頁(yè)面置換算法
面試官提問(wèn)： 操作系統(tǒng)的頁(yè)面置換算法是什么？常用算法有哪些？
題目解析：
首先要明確頁(yè)面置換算法是針對(duì)內(nèi)存管理的算法。
頁(yè)面置換算法是虛擬內(nèi)存的運(yùn)行機(jī)制核心，內(nèi)存被分頁(yè)之后，每個(gè)頁(yè)都是一段連續(xù)的地址，每個(gè)進(jìn)程擁有的都是一段虛擬地址，需要經(jīng)過(guò)內(nèi)存管理單元（Memory Management Unit，也就是 MMU）將虛擬地址轉(zhuǎn)換為物理地址。
操作系統(tǒng)的 CPU 和內(nèi)存都是稀缺資源，所以資源比較緊張，內(nèi)存具有非常高的 I/O 速度，但是空間很小。硬盤具有很大的存儲(chǔ)空間，但是 I/O 能力一般。所以操作系統(tǒng)綜合了兩者的特性，將硬盤作為內(nèi)存的緩存，虛擬內(nèi)存就是硬盤空間的一部分。進(jìn)程運(yùn)行時(shí)，操作系統(tǒng)訪問(wèn)內(nèi)存空間，如果訪問(wèn)的頁(yè)面在內(nèi)存中不存在則從硬盤中將其調(diào)入，如果內(nèi)存沒(méi)有空閑空間，則將內(nèi)存中的一段數(shù)據(jù)調(diào)出到硬盤空間。
我們介紹三種最常見的內(nèi)存管理算法：LRU、FIFO、OPT 算法。
2.1 LRU 算法
LRU（Least Recently Used）即最近最少使用算法，算法的核心思想是如果在過(guò)去一段時(shí)間沒(méi)有訪問(wèn)過(guò)的頁(yè)面，在未來(lái)最近一段時(shí)間也不會(huì)訪問(wèn)。
算法的實(shí)現(xiàn)是給每個(gè)頁(yè)面設(shè)置一個(gè)時(shí)間戳，記錄最近一次訪問(wèn)的時(shí)間，如果發(fā)生缺頁(yè)錯(cuò)誤，則從所有頁(yè)面中淘汰時(shí)間戳最久遠(yuǎn)的一個(gè)。
LRU 算法案例示例：
| 訪問(wèn)頁(yè)面序號(hào) | 5 | 0 | 2 | 8 | 0 | 4 | 8 |
|---|---|---|---|---|---|---|---|
| 物理塊 1 | 5 | 5 | 5 | 8 | 8 | 8 | 8 |
| 物理塊 2 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 物理塊 3 | 2 | 2 | 2 | 4 | 4 | ||
| 是否發(fā)生缺頁(yè) | 是 | 是 | 是 | 是 | 否 | 是 | 否 |
對(duì)于第 4 次訪問(wèn)頁(yè)面時(shí)，因?yàn)樗形锢韷K都有頁(yè)面，所以發(fā)生缺頁(yè)錯(cuò)誤，需要替換出最近最少訪問(wèn)的頁(yè)面，也就是序號(hào)為 5 的頁(yè)面，即物理塊 1 的內(nèi)容被置換。
2.2 FIFO 算法
FIFO（First In First Out）即先進(jìn)先出算法，也就是常見數(shù)據(jù)結(jié)構(gòu)的隊(duì)列模型。當(dāng)物理塊存儲(chǔ)空間不夠時(shí)，優(yōu)先淘汰在最先進(jìn)入物理塊的頁(yè)面，也就是駐留時(shí)間最久的頁(yè)面。
FIFO 算法雖然相對(duì)簡(jiǎn)單，但是不符合操作系統(tǒng)的實(shí)際運(yùn)行情況，因?yàn)轳v留時(shí)間最久的頁(yè)面，大多數(shù)情況是經(jīng)常訪問(wèn)的頁(yè)面，F(xiàn)IFO 算法會(huì)增加缺頁(yè)錯(cuò)誤的概率。
FIFO 算法案例示例：
| 訪問(wèn)頁(yè)面序號(hào) | 5 | 0 | 2 | 8 | 0 | 4 | 8 |
|---|---|---|---|---|---|---|---|
| 物理塊 1 | 5 | 5 | 5 | 8 | 8 | 8 | 8 |
| 物理塊 2 | 0 | 0 | 0 | 0 | 4 | 0 | |
| 物理塊 3 | 2 | 2 | 2 | 2 | 4 | ||
| 是否發(fā)生缺頁(yè) | 是 | 是 | 是 | 是 | 否 | 是 | 否 |
FIFO 算法相對(duì)于 LRU 的區(qū)別在于，只考慮頁(yè)面的駐留時(shí)間，在第 6 次訪問(wèn)頁(yè)面時(shí)，不會(huì)因?yàn)樯洗问切蛱?hào) 0 的頁(yè)面剛進(jìn)行了訪問(wèn)就不進(jìn)行替換，因?yàn)樾蛱?hào) 0 的頁(yè)面是最早進(jìn)入物理塊的，所以替換為了序號(hào)為 4 的頁(yè)面。
2.3 OPT 算法
OPT（Optiomal）最優(yōu)頁(yè)面置換算法，算法的核心思想是置換最長(zhǎng)時(shí)間不會(huì)使用的頁(yè)面，這需要預(yù)判未來(lái)的頁(yè)面置換順序，目前的操作系統(tǒng)無(wú)法做到對(duì)于進(jìn)程未來(lái)需要使用的頁(yè)面進(jìn)行預(yù)測(cè)，所以算法也沒(méi)有實(shí)際落地的實(shí)現(xiàn)。主要作用是對(duì)于已經(jīng)給定的頁(yè)面順序，作為最優(yōu)置換算法的比較標(biāo)桿，比如對(duì)于給定的頁(yè)面順序 5 0 2 8 0 4 8 可以對(duì)比 FIFO 算法以及 OPT 算法的頁(yè)面置換效率，判斷 FIFO 算法是否足夠高效。
| 訪問(wèn)頁(yè)面序號(hào) | 5 | 0 | 2 | 8 | 0 | 4 | 8 | 0 |
|---|---|---|---|---|---|---|---|---|
| 物理塊 1 | 5 | 5 | 5 | 8 | 8 | 8 | 8 | 8 |
| 物理塊 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 物理塊 3 | 2 | 2 | 2 | 4 | 4 | 4 | ||
| 是否發(fā)生缺頁(yè) | 是 | 是 | 是 | 是 | 否 | 是 | 否 | 否 |
對(duì)于訪問(wèn)頁(yè)面序號(hào)是 4 時(shí)，因?yàn)榭梢钥吹轿磥?lái)會(huì)有頁(yè)面序號(hào) 8 和 0 的訪問(wèn)，不會(huì)有序號(hào) 2 的訪問(wèn)，所以置換物理塊 3 中的頁(yè)面序號(hào) 2。
3. 小結(jié)
頁(yè)面調(diào)度的目的是盡可能少的發(fā)生缺頁(yè)錯(cuò)誤，因?yàn)榘l(fā)生缺頁(yè)錯(cuò)誤時(shí)需要從硬盤置換空間，所以會(huì)降低進(jìn)程的執(zhí)行效率。常見的頁(yè)面置換算法除了本文介紹的 FIFO、LRU、OPT，還有時(shí)鐘置換算法，候選人可以自行了解。
2025 imooc.com All Rights Reserved |