前言

最近，我偷偷潛伏在各大技術(shù)群，因?yàn)榍镎性诩?，看到不少小伙伴分享的大廠面經(jīng)。

然后發(fā)現(xiàn)，操作系統(tǒng)的知識(shí)點(diǎn)考察還是比較多的，大廠就是大廠就愛(ài)問(wèn)基礎(chǔ)知識(shí)。其中，關(guān)于操作系統(tǒng)的「調(diào)度算法」考察也算比較頻繁。

所以，我這邊總結(jié)了操作系統(tǒng)的三大調(diào)度機(jī)制，分別是「進(jìn)程調(diào)度/頁(yè)面置換/磁盤調(diào)度算法」，供大家復(fù)習(xí)，希望大家在秋招能斬獲自己心意的 offer。

正文

進(jìn)程調(diào)度算法

進(jìn)程調(diào)度算法也稱 CPU 調(diào)度算法，畢竟進(jìn)程是由 CPU 調(diào)度的。

當(dāng) CPU 空閑時(shí)，操作系統(tǒng)就選擇內(nèi)存中的某個(gè)「就緒狀態(tài)」的進(jìn)程，并給其分配 CPU。

什么時(shí)候會(huì)發(fā)生 CPU 調(diào)度呢？通常有以下情況：

1. 當(dāng)進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)到等待狀態(tài)；

2. 當(dāng)進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)到就緒狀態(tài)；

3. 當(dāng)進(jìn)程從等待狀態(tài)轉(zhuǎn)到就緒狀態(tài)；

4. 當(dāng)進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)到終止?fàn)顟B(tài)；

其中發(fā)生在 1 和 4 兩種情況下的調(diào)度稱為「非搶占式調(diào)度」，2 和 3 兩種情況下發(fā)生的調(diào)度稱為「搶占式調(diào)度」。

非搶占式的意思就是，當(dāng)進(jìn)程正在運(yùn)行時(shí)，它就會(huì)一直運(yùn)行，直到該進(jìn)程完成或發(fā)生某個(gè)事件而被阻塞時(shí)，才會(huì)把 CPU 讓給其他進(jìn)程。

而搶占式調(diào)度，顧名思義就是進(jìn)程正在運(yùn)行的時(shí)，可以被打斷，使其把 CPU 讓給其他進(jìn)程。那搶占的原則一般有三種，分別是時(shí)間片原則、優(yōu)先權(quán)原則、短作業(yè)優(yōu)先原則。

你可能會(huì)好奇為什么第 3 種情況也會(huì)發(fā)生 CPU 調(diào)度呢？假設(shè)有一個(gè)進(jìn)程是處于等待狀態(tài)的，但是它的優(yōu)先級(jí)比較高，如果該進(jìn)程等待的事件發(fā)生了，它就會(huì)轉(zhuǎn)到就緒狀態(tài)，一旦它轉(zhuǎn)到就緒狀態(tài)，如果我們的調(diào)度算法是以優(yōu)先級(jí)來(lái)進(jìn)行調(diào)度的，那么它就會(huì)立馬搶占正在運(yùn)行的進(jìn)程，所以這個(gè)時(shí)候就會(huì)發(fā)生 CPU 調(diào)度。

那第 2 種狀態(tài)通常是時(shí)間片到的情況，因?yàn)闀r(shí)間片到了就會(huì)發(fā)生中斷，于是就會(huì)搶占正在運(yùn)行的進(jìn)程，從而占用 CPU。

調(diào)度算法影響的是等待時(shí)間（進(jìn)程在就緒隊(duì)列中等待調(diào)度的時(shí)間總和），而不能影響進(jìn)程真在使用 CPU 的時(shí)間和 I/O 時(shí)間。

接下來(lái)，說(shuō)說(shuō)常見(jiàn)的調(diào)度算法：

• 先來(lái)先服務(wù)調(diào)度算法

• 最短作業(yè)優(yōu)先調(diào)度算法

• 高響應(yīng)比優(yōu)先調(diào)度算法

• 時(shí)間片輪轉(zhuǎn)調(diào)度算法

• 最高優(yōu)先級(jí)調(diào)度算法

• 多級(jí)反饋隊(duì)列調(diào)度算法

先來(lái)先服務(wù)調(diào)度算法

最簡(jiǎn)單的一個(gè)調(diào)度算法，就是非搶占式的先來(lái)先服務(wù)（First Come First Severd, FCFS）算法了。

顧名思義，先來(lái)后到，每次從就緒隊(duì)列選擇最先進(jìn)入隊(duì)列的進(jìn)程，然后一直運(yùn)行，直到進(jìn)程退出或被阻塞，才會(huì)繼續(xù)從隊(duì)列中選擇第一個(gè)進(jìn)程接著運(yùn)行。

這似乎很公平，但是當(dāng)一個(gè)長(zhǎng)作業(yè)先運(yùn)行了，那么后面的短作業(yè)等待的時(shí)間就會(huì)很長(zhǎng)，不利于短作業(yè)。

FCFS 對(duì)長(zhǎng)作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

最短作業(yè)優(yōu)先調(diào)度算法

最短作業(yè)優(yōu)先（Shortest Job First, SJF）調(diào)度算法同樣也是顧名思義，它會(huì)優(yōu)先選擇運(yùn)行時(shí)間最短的進(jìn)程來(lái)運(yùn)行，這有助于提高系統(tǒng)的吞吐量。

這顯然對(duì)長(zhǎng)作業(yè)不利，很容易造成一種極端現(xiàn)象。

比如，一個(gè)長(zhǎng)作業(yè)在就緒隊(duì)列等待運(yùn)行，而這個(gè)就緒隊(duì)列有非常多的短作業(yè)，那么就會(huì)使得長(zhǎng)作業(yè)不斷的往后推，周轉(zhuǎn)時(shí)間變長(zhǎng)，致使長(zhǎng)作業(yè)長(zhǎng)期不會(huì)被運(yùn)行。

高響應(yīng)比優(yōu)先調(diào)度算法

前面的「先來(lái)先服務(wù)調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒(méi)有很好的權(quán)衡短作業(yè)和長(zhǎng)作業(yè)。

那么，高響應(yīng)比優(yōu)先 （Highest Response Ratio Next, HRRN）調(diào)度算法主要是權(quán)衡了短作業(yè)和長(zhǎng)作業(yè)。

每次進(jìn)行進(jìn)程調(diào)度時(shí)，先計(jì)算「響應(yīng)比優(yōu)先級(jí)」，然后把「響應(yīng)比優(yōu)先級(jí)」最高的進(jìn)程投入運(yùn)行，「響應(yīng)比優(yōu)先級(jí)」的計(jì)算公式：

從上面的公式，可以發(fā)現(xiàn)：

• 如果兩個(gè)進(jìn)程的「等待時(shí)間」相同時(shí)，「要求的服務(wù)時(shí)間」越短，「響應(yīng)比」就越高，這樣短作業(yè)的進(jìn)程容易被選中運(yùn)行；

• 如果兩個(gè)進(jìn)程「要求的服務(wù)時(shí)間」相同時(shí)，「等待時(shí)間」越長(zhǎng)，「響應(yīng)比」就越高，這就兼顧到了長(zhǎng)作業(yè)進(jìn)程，因?yàn)檫M(jìn)程的響應(yīng)比可以隨時(shí)間等待的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其響應(yīng)比便可以升到很高，從而獲得運(yùn)行的機(jī)會(huì)；

時(shí)間片輪轉(zhuǎn)調(diào)度算法

最古老、最簡(jiǎn)單、最公平且使用最廣的算法就是時(shí)間片輪轉(zhuǎn)（Round Robin, RR）調(diào)度算法。

每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱為時(shí)間片（Quantum），即允許該進(jìn)程在該時(shí)間段中運(yùn)行。

• 如果時(shí)間片用完，進(jìn)程還在運(yùn)行，那么將會(huì)把此進(jìn)程從 CPU 釋放出來(lái)，并把 CPU 分配另外一個(gè)進(jìn)程；

• 如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換；

另外，時(shí)間片的長(zhǎng)度就是一個(gè)很關(guān)鍵的點(diǎn)：

• 如果時(shí)間片設(shè)得太短會(huì)導(dǎo)致過(guò)多的進(jìn)程上下文切換，降低了 CPU 效率；

• 如果設(shè)得太長(zhǎng)又可能引起對(duì)短作業(yè)進(jìn)程的響應(yīng)時(shí)間變長(zhǎng)；

通常時(shí)間片設(shè)為 20ms~50ms 通常是一個(gè)比較合理的折中值。

最高優(yōu)先級(jí)調(diào)度算法

前面的「時(shí)間片輪轉(zhuǎn)算法」做了個(gè)假設(shè)，即讓所有的進(jìn)程同等重要，也不偏袒誰(shuí)，大家的運(yùn)行時(shí)間都一樣。

但是，對(duì)于多用戶計(jì)算機(jī)系統(tǒng)就有不同的看法了，它們希望調(diào)度是有優(yōu)先級(jí)的，即希望調(diào)度程序能從就緒隊(duì)列中選擇最高優(yōu)先級(jí)的進(jìn)程進(jìn)行運(yùn)行，這稱為最高優(yōu)先級(jí)（Highest Priority First，HPF）調(diào)度算法。

進(jìn)程的優(yōu)先級(jí)可以分為，靜態(tài)優(yōu)先級(jí)或動(dòng)態(tài)優(yōu)先級(jí)：

• 靜態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)候，就已經(jīng)確定了優(yōu)先級(jí)了，然后整個(gè)運(yùn)行時(shí)間優(yōu)先級(jí)都不會(huì)變化；

• 動(dòng)態(tài)優(yōu)先級(jí)：根據(jù)進(jìn)程的動(dòng)態(tài)變化調(diào)整優(yōu)先級(jí)，比如如果進(jìn)程運(yùn)行時(shí)間增加，則降低其優(yōu)先級(jí)，如果進(jìn)程等待時(shí)間（就緒隊(duì)列的等待時(shí)間）增加，則升高其優(yōu)先級(jí)，也就是隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。

該算法也有兩種處理優(yōu)先級(jí)高的方法，非搶占式和搶占式：

• 非搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，運(yùn)行完當(dāng)前進(jìn)程，再選擇優(yōu)先級(jí)高的進(jìn)程。

• 搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，當(dāng)前進(jìn)程掛起，調(diào)度優(yōu)先級(jí)高的進(jìn)程運(yùn)行。

但是依然有缺點(diǎn)，可能會(huì)導(dǎo)致低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)不會(huì)運(yùn)行。

多級(jí)反饋隊(duì)列調(diào)度算法

多級(jí)反饋隊(duì)列（Multilevel Feedback Queue）調(diào)度算法是「時(shí)間片輪轉(zhuǎn)算法」和「最高優(yōu)先級(jí)算法」的綜合和發(fā)展。

顧名思義：

• 「多級(jí)」表示有多個(gè)隊(duì)列，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短。

• 「反饋」表示如果有新的進(jìn)程加入優(yōu)先級(jí)高的隊(duì)列時(shí)，立刻停止當(dāng)前正在運(yùn)行的進(jìn)程，轉(zhuǎn)而去運(yùn)行優(yōu)先級(jí)高的隊(duì)列；

來(lái)看看，它是如何工作的：

• 設(shè)置了多個(gè)隊(duì)列，賦予每個(gè)隊(duì)列不同的優(yōu)先級(jí)，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短；

• 新的進(jìn)程會(huì)被放入到第一級(jí)隊(duì)列的末尾，按先來(lái)先服務(wù)的原則排隊(duì)等待被調(diào)度，如果在第一級(jí)隊(duì)列規(guī)定的時(shí)間片沒(méi)運(yùn)行完成，則將其轉(zhuǎn)入到第二級(jí)隊(duì)列的末尾，以此類推，直至完成；

• 當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程運(yùn)行。如果進(jìn)程運(yùn)行時(shí)，有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則停止當(dāng)前運(yùn)行的進(jìn)程并將其移入到原隊(duì)列末尾，接著讓較高優(yōu)先級(jí)的進(jìn)程運(yùn)行；

可以發(fā)現(xiàn)，對(duì)于短作業(yè)可能可以在第一級(jí)隊(duì)列很快被處理完。對(duì)于長(zhǎng)作業(yè)，如果在第一級(jí)隊(duì)列處理不完，可以移入下次隊(duì)列等待被執(zhí)行，雖然等待的時(shí)間變長(zhǎng)了，但是運(yùn)行時(shí)間也會(huì)更長(zhǎng)了，所以該算法很好的兼顧了長(zhǎng)短作業(yè)，同時(shí)有較好的響應(yīng)時(shí)間。

內(nèi)存頁(yè)面置換算法

在了解內(nèi)存頁(yè)面置換算法前，我們得先談一下缺頁(yè)異常（缺頁(yè)中斷）。

當(dāng) CPU 訪問(wèn)的頁(yè)面不在物理內(nèi)存時(shí)，便會(huì)產(chǎn)生一個(gè)缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)將所缺頁(yè)調(diào)入到物理內(nèi)存。那它與一般中斷的主要區(qū)別在于：

• 缺頁(yè)中斷在指令執(zhí)行「期間」產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行「完成」后檢查和處理中斷信號(hào)。

• 缺頁(yè)中斷返回到該指令的開(kāi)始重新執(zhí)行「該指令」，而一般中斷返回回到該指令的「下一個(gè)指令」執(zhí)行。

我們來(lái)看一下缺頁(yè)中斷的處理流程，如下圖：

1. 在 CPU 里訪問(wèn)一條 Load M 指令，然后 CPU 會(huì)去找 M 所對(duì)應(yīng)的頁(yè)表項(xiàng)。

2. 如果該頁(yè)表項(xiàng)的狀態(tài)位是「有效的」，那 CPU 就可以直接去訪問(wèn)物理內(nèi)存了，如果狀態(tài)位是「無(wú)效的」，則 CPU 則會(huì)發(fā)送缺頁(yè)中斷請(qǐng)求。

3. 操作系統(tǒng)收到了缺頁(yè)中斷，則會(huì)執(zhí)行缺頁(yè)中斷處理函數(shù)，先會(huì)查找該頁(yè)面在磁盤中的頁(yè)面的位置。

4. 找到磁盤中對(duì)應(yīng)的頁(yè)面后，需要把該頁(yè)面換入到物理內(nèi)存中，但是在換入前，需要在物理內(nèi)存中找空閑頁(yè)，如果找到空閑頁(yè)，就把頁(yè)面換入到物理內(nèi)存中。

5. 頁(yè)面從磁盤換入到物理內(nèi)存完成后，則把頁(yè)表項(xiàng)中的狀態(tài)位修改為「有效的」。

6. 最后，CPU 重新執(zhí)行導(dǎo)致缺頁(yè)異常的指令。

上面所說(shuō)的過(guò)程，第 4 步是能在物理內(nèi)存找到空閑頁(yè)的情況，那如果找不到呢？

找不到空閑頁(yè)的話，就說(shuō)明此時(shí)內(nèi)存已滿了，這時(shí)候，就需要「頁(yè)面置換算法」選擇一個(gè)物理頁(yè)，如果該物理頁(yè)有被修改過(guò)（臟頁(yè)），則把它換出到磁盤，然后把該被置換出去的頁(yè)表項(xiàng)的狀態(tài)改成「無(wú)效的」，最后把正在訪問(wèn)的頁(yè)面裝入到這個(gè)物理頁(yè)中。

這里提一下，頁(yè)表項(xiàng)通常有如下圖的字段：

那其中：

• 狀態(tài)位：用于表示該頁(yè)是否有效，也就是說(shuō)是否在物理內(nèi)存中，供程序訪問(wèn)時(shí)參考。

• 訪問(wèn)字段：用于記錄該頁(yè)在一段時(shí)間被訪問(wèn)的次數(shù)，供頁(yè)面置換算法選擇出頁(yè)面時(shí)參考。

• 修改位：表示該頁(yè)在調(diào)入內(nèi)存后是否有被修改過(guò)，由于內(nèi)存中的每一頁(yè)都在磁盤上保留一份副本，因此，如果沒(méi)有修改，在置換該頁(yè)時(shí)就不需要將該頁(yè)寫回到磁盤上，以減少系統(tǒng)的開(kāi)銷；如果已經(jīng)被修改，則將該頁(yè)重寫到磁盤上，以保證磁盤中所保留的始終是最新的副本。

• 硬盤地址：用于指出該頁(yè)在硬盤上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。

這里我整理了虛擬內(nèi)存的管理整個(gè)流程，你可以從下面這張圖看到：

所以，頁(yè)面置換算法的功能是，當(dāng)出現(xiàn)缺頁(yè)異常，需調(diào)入新頁(yè)面而內(nèi)存已滿時(shí)，選擇被置換的物理頁(yè)面，也就是說(shuō)選擇一個(gè)物理頁(yè)面換出到磁盤，然后把需要訪問(wèn)的頁(yè)面換入到物理頁(yè)。

那其算法目標(biāo)則是，盡可能減少頁(yè)面的換入換出的次數(shù)，常見(jiàn)的頁(yè)面置換算法有如下幾種：

• 最佳頁(yè)面置換算法（OPT）

• 先進(jìn)先出置換算法（FIFO）

• 最近最久未使用的置換算法（LRU）

• 時(shí)鐘頁(yè)面置換算法（Lock）

• 最不常用置換算法（LFU）

最佳頁(yè)面置換算法

最佳頁(yè)面置換算法基本思路是，置換在「未來(lái)」最長(zhǎng)時(shí)間不訪問(wèn)的頁(yè)面。

所以，該算法實(shí)現(xiàn)需要計(jì)算內(nèi)存中每個(gè)邏輯頁(yè)面的「下一次」訪問(wèn)時(shí)間，然后比較，選擇未來(lái)最長(zhǎng)時(shí)間不訪問(wèn)的頁(yè)面。

我們舉個(gè)例子，假設(shè)一開(kāi)始有 3 個(gè)空閑的物理頁(yè)，然后有請(qǐng)求的頁(yè)面序列，那它的置換過(guò)程如下圖：

在這個(gè)請(qǐng)求的頁(yè)面序列中，缺頁(yè)共發(fā)生了 7 次（空閑頁(yè)換入 3 次 + 最優(yōu)頁(yè)面置換 4 次），頁(yè)面置換共發(fā)生了 4 次。

這很理想，但是實(shí)際系統(tǒng)中無(wú)法實(shí)現(xiàn)，因?yàn)槌绦蛟L問(wèn)頁(yè)面時(shí)是動(dòng)態(tài)的，我們是無(wú)法預(yù)知每個(gè)頁(yè)面在「下一次」訪問(wèn)前的等待時(shí)間。

所以，最佳頁(yè)面置換算法作用是為了衡量你的算法的效率，你的算法效率越接近該算法的效率，那么說(shuō)明你的算法是高效的。

先進(jìn)先出置換算法

既然我們無(wú)法預(yù)知頁(yè)面在下一次訪問(wèn)前所需的等待時(shí)間，那我們可以選擇在內(nèi)存駐留時(shí)間很長(zhǎng)的頁(yè)面進(jìn)行中置換，這個(gè)就是「先進(jìn)先出置換」算法的思想。

還是以前面的請(qǐng)求的頁(yè)面序列作為例子，假設(shè)使用先進(jìn)先出置換算法，則過(guò)程如下圖：

在這個(gè)請(qǐng)求的頁(yè)面序列中，缺頁(yè)共發(fā)生了 10 次，頁(yè)面置換共發(fā)生了 7 次，跟最佳頁(yè)面置換算法比較起來(lái)，性能明顯差了很多。

最近最久未使用的置換算法

最近最久未使用（LRU）的置換算法的基本思路是，發(fā)生缺頁(yè)時(shí)，選擇最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)的頁(yè)面進(jìn)行置換，也就是說(shuō)，該算法假設(shè)已經(jīng)很久沒(méi)有使用的頁(yè)面很有可能在未來(lái)較長(zhǎng)的一段時(shí)間內(nèi)仍然不會(huì)被使用。

這種算法近似最優(yōu)置換算法，最優(yōu)置換算法是通過(guò)「未來(lái)」的使用情況來(lái)推測(cè)要淘汰的頁(yè)面，而 LRU 則是通過(guò)「歷史」的使用情況來(lái)推測(cè)要淘汰的頁(yè)面。

還是以前面的請(qǐng)求的頁(yè)面序列作為例子，假設(shè)使用最近最久未使用的置換算法，則過(guò)程如下圖：

在這個(gè)請(qǐng)求的頁(yè)面序列中，缺頁(yè)共發(fā)生了 9 次，頁(yè)面置換共發(fā)生了 6 次，跟先進(jìn)先出置換算法比較起來(lái)，性能提高了一些。

雖然 LRU 在理論上是可以實(shí)現(xiàn)的，但代價(jià)很高。為了完全實(shí)現(xiàn) LRU，需要在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表，最近最多使用的頁(yè)面在表頭，最近最少使用的頁(yè)面在表尾。

困難的是，在每次訪問(wèn)內(nèi)存時(shí)都必須要更新「整個(gè)鏈表」。在鏈表中找到一個(gè)頁(yè)面，刪除它，然后把它移動(dòng)到表頭是一個(gè)非常費(fèi)時(shí)的操作。

所以，LRU 雖然看上去不錯(cuò)，但是由于開(kāi)銷比較大，實(shí)際應(yīng)用中比較少使用。

時(shí)鐘頁(yè)面置換算法

那有沒(méi)有一種即能優(yōu)化置換的次數(shù)，也能方便實(shí)現(xiàn)的算法呢？

時(shí)鐘頁(yè)面置換算法就可以兩者兼得，它跟 LRU 近似，又是對(duì) FIFO 的一種改進(jìn)。

該算法的思路是，把所有的頁(yè)面都保存在一個(gè)類似鐘面的「環(huán)形鏈表」中，一個(gè)表針指向最老的頁(yè)面。

當(dāng)發(fā)生缺頁(yè)中斷時(shí)，算法首先檢查表針指向的頁(yè)面：

• 如果它的訪問(wèn)位位是 0 就淘汰該頁(yè)面，并把新的頁(yè)面插入這個(gè)位置，然后把表針前移一個(gè)位置；

• 如果訪問(wèn)位是 1 就清除訪問(wèn)位，并把表針前移一個(gè)位置，重復(fù)這個(gè)過(guò)程直到找到了一個(gè)訪問(wèn)位為 0 的頁(yè)面為止；

我畫了一副時(shí)鐘頁(yè)面置換算法的工作流程圖，你可以在下方看到：

了解了這個(gè)算法的工作方式，就明白為什么它被稱為時(shí)鐘（Clock）算法了。

最不常用算法

最不常用（LFU）算法，這名字聽(tīng)起來(lái)很調(diào)皮，但是它的意思不是指這個(gè)算法不常用，而是當(dāng)發(fā)生缺頁(yè)中斷時(shí)，選擇「訪問(wèn)次數(shù)」最少的那個(gè)頁(yè)面，并將其淘汰。

它的實(shí)現(xiàn)方式是，對(duì)每個(gè)頁(yè)面設(shè)置一個(gè)「訪問(wèn)計(jì)數(shù)器」，每當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)，該頁(yè)面的訪問(wèn)計(jì)數(shù)器就累加 1。在發(fā)生缺頁(yè)中斷時(shí)，淘汰計(jì)數(shù)器值最小的那個(gè)頁(yè)面。

看起來(lái)很簡(jiǎn)單，每個(gè)頁(yè)面加一個(gè)計(jì)數(shù)器就可以實(shí)現(xiàn)了，但是在操作系統(tǒng)中實(shí)現(xiàn)的時(shí)候，我們需要考慮效率和硬件成本的。

要增加一個(gè)計(jì)數(shù)器來(lái)實(shí)現(xiàn)，這個(gè)硬件成本是比較高的，另外如果要對(duì)這個(gè)計(jì)數(shù)器查找哪個(gè)頁(yè)面訪問(wèn)次數(shù)最小，查找鏈表本身，如果鏈表長(zhǎng)度很大，是非常耗時(shí)的，效率不高。

但還有個(gè)問(wèn)題，LFU 算法只考慮了頻率問(wèn)題，沒(méi)考慮時(shí)間的問(wèn)題，比如有些頁(yè)面在過(guò)去時(shí)間里訪問(wèn)的頻率很高，但是現(xiàn)在已經(jīng)沒(méi)有訪問(wèn)了，而當(dāng)前頻繁訪問(wèn)的頁(yè)面由于沒(méi)有這些頁(yè)面訪問(wèn)的次數(shù)高，在發(fā)生缺頁(yè)中斷時(shí)，就會(huì)可能會(huì)誤傷當(dāng)前剛開(kāi)始頻繁訪問(wèn)，但訪問(wèn)次數(shù)還不高的頁(yè)面。

那這個(gè)問(wèn)題的解決的辦法還是有的，可以定期減少訪問(wèn)的次數(shù)，比如當(dāng)發(fā)生時(shí)間中斷時(shí)，把過(guò)去時(shí)間訪問(wèn)的頁(yè)面的訪問(wèn)次數(shù)除以 2，也就說(shuō)，隨著時(shí)間的流失，以前的高訪問(wèn)次數(shù)的頁(yè)面會(huì)慢慢減少，相當(dāng)于加大了被置換的概率。

磁盤調(diào)度算法

我們來(lái)看看磁盤的結(jié)構(gòu)，如下圖：

常見(jiàn)的機(jī)械磁盤是上圖左邊的樣子，中間圓的部分是磁盤的盤片，一般會(huì)有多個(gè)盤片，每個(gè)盤面都有自己的磁頭。右邊的圖就是一個(gè)盤片的結(jié)構(gòu)，盤片中的每一層分為多個(gè)磁道，每個(gè)磁道分多個(gè)扇區(qū)，每個(gè)扇區(qū)是 512 字節(jié)。那么，多個(gè)具有相同編號(hào)的磁道形成一個(gè)圓柱，稱之為磁盤的柱面，如上圖里中間的樣子。

磁盤調(diào)度算法的目的很簡(jiǎn)單，就是為了提高磁盤的訪問(wèn)性能，一般是通過(guò)優(yōu)化磁盤的訪問(wèn)請(qǐng)求順序來(lái)做到的。

尋道的時(shí)間是磁盤訪問(wèn)最耗時(shí)的部分，如果請(qǐng)求順序優(yōu)化的得當(dāng)，必然可以節(jié)省一些不必要的尋道時(shí)間，從而提高磁盤的訪問(wèn)性能。

假設(shè)有下面一個(gè)請(qǐng)求序列，每個(gè)數(shù)字代表磁道的位置：

98，183，37，122，14，124，65，67

初始磁頭當(dāng)前的位置是在第 53 磁道。

接下來(lái)，分別對(duì)以上的序列，作為每個(gè)調(diào)度算法的例子，那常見(jiàn)的磁盤調(diào)度算法有：

• 先來(lái)先服務(wù)算法

• 最短尋道時(shí)間優(yōu)先算法

• 掃描算法算法

• 循環(huán)掃描算法

• LOOK 與 C-LOOK 算法

先來(lái)先服務(wù)

先來(lái)先服務(wù)（First-Come，F(xiàn)irst-Served，F(xiàn)CFS），顧名思義，先到來(lái)的請(qǐng)求，先被服務(wù)。

那按照這個(gè)序列的話：

98，183，37，122，14，124，65，67

那么，磁盤的寫入順序是從左到右，如下圖：

先來(lái)先服務(wù)算法總共移動(dòng)了 640 個(gè)磁道的距離，這么一看這種算法，比較簡(jiǎn)單粗暴，但是如果大量進(jìn)程競(jìng)爭(zhēng)使用磁盤，請(qǐng)求訪問(wèn)的磁道可能會(huì)很分散，那先來(lái)先服務(wù)算法在性能上就會(huì)顯得很差，因?yàn)閷さ罆r(shí)間過(guò)長(zhǎng)。

最短尋道時(shí)間優(yōu)先

最短尋道時(shí)間優(yōu)先（Shortest Seek First，SSF）算法的工作方式是，優(yōu)先選擇從當(dāng)前磁頭位置所需尋道時(shí)間最短的請(qǐng)求，還是以這個(gè)序列為例子：

98，183，37，122，14，124，65，67

那么，那么根據(jù)距離磁頭（ 53 位置）最近的請(qǐng)求的算法，具體的請(qǐng)求則會(huì)是下列從左到右的順序：

65，67，37，14，98，122，124，183

磁頭移動(dòng)的總距離是 236 磁道，相比先來(lái)先服務(wù)性能提高了不少。

但這個(gè)算法可能存在某些請(qǐng)求的饑餓，因?yàn)楸敬卫游覀兪庆o態(tài)的序列，看不出問(wèn)題，假設(shè)是一個(gè)動(dòng)態(tài)的請(qǐng)求，如果后續(xù)來(lái)的請(qǐng)求都是小于 183 磁道的，那么 183 磁道可能永遠(yuǎn)不會(huì)被響應(yīng)，于是就產(chǎn)生了饑餓現(xiàn)象，這里產(chǎn)生饑餓的原因是磁頭在一小塊區(qū)域來(lái)回移動(dòng)。

掃描算法

最短尋道時(shí)間優(yōu)先算法會(huì)產(chǎn)生饑餓的原因在于：磁頭有可能再一個(gè)小區(qū)域內(nèi)來(lái)回得移動(dòng)。

為了防止這個(gè)問(wèn)題，可以規(guī)定：磁頭在一個(gè)方向上移動(dòng)，訪問(wèn)所有未完成的請(qǐng)求，直到磁頭到達(dá)該方向上的最后的磁道，才調(diào)換方向，這就是掃描（Scan）算法。

這種算法也叫做電梯算法，比如電梯保持按一個(gè)方向移動(dòng)，直到在那個(gè)方向上沒(méi)有請(qǐng)求為止，然后改變方向。

還是以這個(gè)序列為例子，磁頭的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假設(shè)掃描調(diào)度算先朝磁道號(hào)減少的方向移動(dòng)，具體請(qǐng)求則會(huì)是下列從左到右的順序：

37，14，0，65，67，98，122，124，183

磁頭先響應(yīng)左邊的請(qǐng)求，直到到達(dá)最左端（ 0 磁道）后，才開(kāi)始反向移動(dòng)，響應(yīng)右邊的請(qǐng)求。

掃描調(diào)度算法性能較好，不會(huì)產(chǎn)生饑餓現(xiàn)象，但是存在這樣的問(wèn)題，中間部分的磁道會(huì)比較占便宜，中間部分相比其他部分響應(yīng)的頻率會(huì)比較多，也就是說(shuō)每個(gè)磁道的響應(yīng)頻率存在差異。

循環(huán)掃描算法

掃描算法使得每個(gè)磁道響應(yīng)的頻率存在差異，那么要優(yōu)化這個(gè)問(wèn)題的話，可以總是按相同的方向進(jìn)行掃描，使得每個(gè)磁道的響應(yīng)頻率基本一致。

循環(huán)掃描（Circular Scan, CSCAN ）規(guī)定：只有磁頭朝某個(gè)特定方向移動(dòng)時(shí)，才處理磁道訪問(wèn)請(qǐng)求，而返回時(shí)直接快速移動(dòng)至最靠邊緣的磁道，也就是復(fù)位磁頭，這個(gè)過(guò)程是很快的，并且返回中途不處理任何請(qǐng)求，該算法的特點(diǎn)，就是磁道只響應(yīng)一個(gè)方向上的請(qǐng)求。

還是以這個(gè)序列為例子，磁頭的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假設(shè)循環(huán)掃描調(diào)度算先朝磁道增加的方向移動(dòng)，具體請(qǐng)求會(huì)是下列從左到右的順序：

65，67，98，122，124，183，199，0，14，37

磁頭先響應(yīng)了右邊的請(qǐng)求，直到碰到了最右端的磁道 199，就立即回到磁盤的開(kāi)始處（磁道 0），但這個(gè)返回的途中是不響應(yīng)任何請(qǐng)求的，直到到達(dá)最開(kāi)始的磁道后，才繼續(xù)順序響應(yīng)右邊的請(qǐng)求。

循環(huán)掃描算法相比于掃描算法，對(duì)于各個(gè)位置磁道響應(yīng)頻率相對(duì)比較平均。

LOOK 與 C-LOOK算法

我們前面說(shuō)到的掃描算法和循環(huán)掃描算法，都是磁頭移動(dòng)到磁盤「最始端或最末端」才開(kāi)始調(diào)換方向。

那這其實(shí)是可以優(yōu)化的，優(yōu)化的思路就是磁頭在移動(dòng)到「最遠(yuǎn)的請(qǐng)求」位置，然后立即反向移動(dòng)。

那針對(duì) SCAN 算法的優(yōu)化則叫 LOOK 算法，它的工作方式，磁頭在每個(gè)方向上僅僅移動(dòng)到最遠(yuǎn)的請(qǐng)求位置，然后立即反向移動(dòng)，而不需要移動(dòng)到磁盤的最始端或最末端，反向移動(dòng)的途中會(huì)響應(yīng)請(qǐng)求。

而針 C-SCAN 算法的優(yōu)化則叫 C-LOOK，它的工作方式，磁頭在每個(gè)方向上僅僅移動(dòng)到最遠(yuǎn)的請(qǐng)求位置，然后立即反向移動(dòng)，而不需要移動(dòng)到磁盤的最始端或最末端，反向移動(dòng)的途中不會(huì)響應(yīng)請(qǐng)求。

絮叨

上周，奔波了不少城市，先后見(jiàn)到了帥地、敖丙、三歪和 JavaGuide，大家都是年輕的帥小伙。

接著，一同去蘇州參加了技術(shù)類的公眾號(hào)交流會(huì)，一下見(jiàn)到了好多個(gè)百萬(wàn)/千萬(wàn)的大佬，明天給大家分享下此次的行程和感悟。

大家好，我是小林，一個(gè)專為大家圖解的工具人，我們下次見(jiàn)！