作業系統常見面試題

2021 年 10 月 2 日
筆記
面試

引論

什麼是作業系統？

可以這麼說，作業系統是一種運行在內核態的軟體。

它是應用程式和硬體之間的媒介，嚮應用程式提供硬體的抽象，以及管理硬體資源。

作業系統主要有哪些功能？

作業系統最主要的功能：

處理器（CPU）管理：CPU的管理和分配，主要指的是進程管理。
記憶體管理：記憶體的分配和管理，主要利用了虛擬記憶體的方式。
外存管理：外存（磁碟等）的分配和管理，將外存以文件的形式提供出去。
I/O管理：對輸入/輸出設備的統一管理。

除此之外，還有保證自身正常運行的健壯性管理，防止非法操作和入侵的安全性管理。

作業系統結構

什麼是內核？

可以這麼說，內核是一個電腦程式，它是作業系統的核心，提供了作業系統最核心的能力，可以控制作業系統中所有的內容。

什麼是用戶態和內核態？

內核具有很⾼的許可權，可以控制 cpu、記憶體、硬碟等硬體，出於許可權控制的考慮，因此⼤多數作業系統，把記憶體分成了兩個區域：

內核空間，這個記憶體空間只有內核程式可以訪問；
⽤戶空間，這個記憶體空間專⻔給應⽤程式使⽤，許可權比較小；

⽤戶空間的程式碼只能訪問⼀個局部的記憶體空間，⽽內核空間的程式碼可以訪問所有記憶體空間。因此，當程式使⽤⽤戶空間時，我們常說該程式在⽤戶態執⾏，⽽當程式使內核空間時，程式則在內核態執⾏。

用戶態和內核態是如何切換的？

應⽤程式如果需要進⼊內核空間，就需要通過系統調⽤，來進入內核態：

內核程式執⾏在內核態，⽤戶程式執⾏在⽤戶態。當應⽤程式使⽤系統調⽤時，會產⽣⼀個中斷。發⽣中斷後， CPU 會中斷當前在執⾏的⽤戶程式，轉⽽跳轉到中斷處理程式，也就是開始執⾏內核程式。內核處理完後，主動觸發中斷，把 CPU 執⾏許可權交回給⽤戶程式，回到⽤戶態繼續⼯作。

進程和執行緒

並行和並發有什麼區別？

並發就是在一段時間內，多個任務都會被處理；但在某一時刻，只有一個任務在執行。單核處理器做到的並發，其實是利用時間片的輪轉，例如有兩個進程A和B，A運行一個時間片之後，切換到B，B運行一個時間片之後又切換到A。因為切換速度足夠快，所以宏觀上表現為在一段時間內能同時運行多個程式。

並行就是在同一時刻，有多個任務在執行。這個需要多核處理器才能完成，在微觀上就能同時執行多條指令，不同的程式被放到不同的處理器上運行，這個是物理上的多個進程同時進行。

什麼是進程上下文切換？

對於單核單執行緒 CPU 而言，在某一時刻只能執行一條 CPU 指令。上下文切換 (Context Switch) 是一種將 CPU 資源從一個進程分配給另一個進程的機制。從用戶角度看，電腦能夠並行運行多個進程，這恰恰是作業系統通過快速上下文切換造成的結果。在切換的過程中，作業系統需要先存儲當前進程的狀態 (包括記憶體空間的指針，當前執行完的指令等等)，再讀入下一個進程的狀態，然後執行此進程。

進程有哪些狀態？

當一個進程開始運行時，它可能會經歷下面這幾種狀態：

上圖中各個狀態的意義：

運⾏狀態（Runing）：該時刻進程占⽤ CPU；
就緒狀態（Ready）：可運⾏，由於其他進程處於運⾏狀態⽽暫時停⽌運⾏；
阻塞狀態（Blocked）：該進程正在等待某⼀事件發⽣（如等待輸⼊/輸出操作的完成）⽽暫時停⽌運⾏，這時，即使給它CPU控制權，它也⽆法運⾏；

當然，進程還有另外兩個基本狀態：

創建狀態（new）：進程正在被創建時的狀態；
結束狀態（Exit）：進程正在從系統中消失時的狀態；

什麼是殭屍進程？

殭屍進程是已完成且處於終止狀態，但在進程表中卻仍然存在的進程。

殭屍進程一般發生有父子關係的進程中，一個子進程的進程描述符在子進程退出時不會釋放，只有當父進程通過 wait() 或 waitpid() 獲取了子進程資訊後才會釋放。如果子進程退出，而父進程並沒有調用 wait() 或 waitpid()，那麼子進程的進程描述符仍然保存在系統中。

什麼是孤兒進程？

一個父進程退出，而它的一個或多個子進程還在運行，那麼這些子進程將成為孤兒進程。孤兒進程將被 init 進程 (進程 ID 為 1 的進程) 所收養，並由 init 進程對它們完成狀態收集工作。因為孤兒進程會被 init 進程收養，所以孤兒進程不會對系統造成危害。

進程有哪些調度演算法？

進程調度就是確定某一個時刻CPU運行哪個進程，常見的進程調度演算法有：

先來先服務

非搶佔式的調度演算法，按照請求的順序進行調度。有利於長作業，但不利於短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。另外，對I/O密集型進程也不利，因為這種進程每次進行I/O操作之後又得重新排隊。

短作業優先

非搶佔式的調度演算法，按估計運行時間最短的順序進行調度。長作業有可能會餓死，處於一直等待短作業執行完畢的狀態。因為如果一直有短作業到來，那麼長作業永遠得不到調度。

優先順序調度

為每個進程分配一個優先順序，按優先順序進行調度。為了防止低優先順序的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優先順序。

時間片輪轉

將所有就緒進程按先來先服務的原則排成一個隊列，每次調度時，把 CPU 時間分配給隊首進程，該進程可以執行一個時間片。當時間片用完時，由計時器發出時鐘中斷，調度程式便停止該進程的執行，並將它送往就緒隊列的末尾，同時繼續把 CPU 時間分配給隊首的進程。

時間片輪轉演算法的效率和時間片的大小有很大關係：因為進程切換都要保存進程的資訊並且載入新進程的資訊，如果時間片太小，會導致進程切換得太頻繁，在進程切換上就會花過多時間。而如果時間片過長，那麼實時性就不能得到保證。

最短剩餘時間優先

最短作業優先的搶佔式版本，按剩餘運行時間的順序進行調度。當一個新的作業到達時，其整個運行時間與當前進程的剩餘時間作比較。如果新的進程需要的時間更少，則掛起當前進程，運行新的進程。否則新的進程等待。

進程間通訊有哪些方式？

管道：管道可以理解成不同進程之間的對白，一方發聲，一方接收，聲音的介質可是是空氣或者電纜，進程之間就可以通過管道，所謂的管道就是內核中的一串快取，從管道的一端寫入數據，就是快取在了內核里，另一端讀取，也是從內核中讀取這段數據。

管道可以分為兩類：匿名管道和命名管道。匿名管道是單向的，只能在有親緣關係的進程間通訊；命名管道是雙向的，可以實現本機任意兩個進程通訊。
訊號：訊號可以理解成一種電報，發送方發送內容，指定接收進程，然後發出特定的軟體中斷，作業系統接到中斷請求後，找到接收進程，通知接收進程處理訊號。

比如kill -9 1050就表示給PID為1050的進程發送SIGKIL訊號。Linux系統中常用訊號：

（1）SIGHUP：用戶從終端註銷，所有已啟動進程都將收到該進程。系統預設狀態下對該訊號的處理是終止進程。
（2）SIGINT：程式終止訊號。程式運行過程中，按Ctrl+C鍵將產生該訊號。
（3）SIGQUIT：程式退出訊號。程式運行過程中，按Ctrl+\鍵將產生該訊號。
（4）SIGBUS和SIGSEGV：進程訪問非法地址。
（5）SIGFPE：運算中出現致命錯誤，如除零操作、數據溢出等。
（6）SIGKILL：用戶終止進程執行訊號。shell下執行kill -9發送該訊號。
（7）SIGTERM：結束進程訊號。shell下執行kill 進程pid發送該訊號。
（8）SIGALRM：定時器訊號。
（9）SIGCLD：子進程退出訊號。如果其父進程沒有忽略該訊號也沒有處理該訊號，則子進程退出後將形成殭屍進程。
消息隊列：消息隊列就是保存在內核中的消息鏈表，包括Posix消息隊列和System V消息隊列。有足夠許可權的進程可以向隊列中添加消息，被賦予讀許可權的進程則可以讀走隊列中的消息。消息隊列克服了訊號承載資訊量少，管道只能承載無格式位元組流以及緩衝區大小受限等缺點。

共享記憶體：共享記憶體的機制，就是拿出⼀塊虛擬地址空間來，映射到相同的物理記憶體中。這樣這個進程寫⼊的東西，另外的進程⻢上就能看到。共享記憶體是最快的 IPC 方式，它是針對其他進程間通訊方式運行效率低而專門設計的。它往往與其他通訊機制，如訊號量，配合使用，來實現進程間的同步和通訊。

訊號量：訊號量我們可以理解成紅綠燈，紅燈行，綠燈停。它本質上是一個整數計數器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，防止某進程正在訪問共享資源時，其他進程也訪問該資源。因此，主要作為進程間以及同一進程內不同執行緒之間的同步手段。

訊號量表示資源的數量，控制訊號量的⽅式有兩種原⼦操作：
- ⼀個是 P 操作，這個操作會把訊號量減去 1，相減後如果訊號量 < 0，則表明資源已被占⽤，進程需阻塞等待；相減後如果訊號量 >= 0，則表明還有資源可使⽤，進程可正常繼續執⾏。
- 另⼀個是 V 操作，這個操作會把訊號量加上 1，相加後如果訊號量 <= 0，則表明當前有阻塞中的進程，於是會將該進程喚醒運⾏；相加後如果訊號量 > 0，則表明當前沒有阻塞中的進程；
P 操作是⽤在進⼊共享資源之前，V 操作是⽤在離開共享資源之後，這兩個操作是必須成對出現的。
Socket：與其他通訊機制不同的是，它可用於不同機器間的進程通訊。

優缺點：

管道：簡單；效率低，容量有限；
消息隊列：不及時，寫入和讀取需要用戶態、內核態拷貝。
共享記憶體區：能夠很容易控制容量，速度快，但需要注意不同進程的同步問題。
訊號量：不能傳遞複雜消息，一般用來實現進程間的同步；
訊號：它是進程間通訊的唯一非同步機制。
Socket：用於不同主機進程間的通訊。

進程和執行緒的聯繫和區別？

執行緒和進程的聯繫：

執行緒是進程當中的⼀條執⾏流程。

同⼀個進程內多個執行緒之間可以共享程式碼段、數據段、打開的⽂件等資源，但每個執行緒各⾃都有⼀套獨⽴的暫存器和棧，這樣可以確保執行緒的控制流是相對獨⽴的。

執行緒與進程的⽐較如下：

調度：進程是資源（包括記憶體、打開的⽂件等）分配的單位，執行緒是 CPU 調度的單位；
資源：進程擁有⼀個完整的資源平台，⽽執行緒只獨享必不可少的資源，如暫存器和棧；
擁有資源：執行緒同樣具有就緒、阻塞、執⾏三種基本狀態，同樣具有狀態之間的轉換關係；
系統開銷：執行緒能減少並發執⾏的時間和空間開銷——創建或撤銷進程時，系統都要為之分配或回收系統資源，如記憶體空間，I/O設備等，OS所付出的開銷顯著大於在創建或撤銷執行緒時的開銷，進程切換的開銷也遠大於執行緒切換的開銷。

執行緒上下文切換了解嗎？

這還得看執行緒是不是屬於同⼀個進程：

當兩個執行緒不是屬於同⼀個進程，則切換的過程就跟進程上下⽂切換⼀樣；
當兩個執行緒是屬於同⼀個進程，因為虛擬記憶體是共享的，所以在切換時，虛擬記憶體這些資源就保持不動，只需要切換執行緒的私有數據、暫存器等不共享的數據；

所以，執行緒的上下⽂切換相⽐進程，開銷要⼩很多。

執行緒有哪些實現方式？

主要有三種執行緒的實現⽅式：

內核態執行緒實現：在內核空間實現的執行緒，由內核直接管理直接管理執行緒。

⽤戶態執行緒實現：在⽤戶空間實現執行緒，不需要內核的參與，內核對執行緒無感知。

混合執行緒實現：現代作業系統基本都是將兩種方式結合起來使用。用戶態的執行系統負責進程內部執行緒在非阻塞時的切換；內核態的作業系統負責阻塞執行緒的切換。即我們同時實現內核態和用戶態執行緒管理。其中內核態執行緒數量較少，而用戶態執行緒數量較多。每個內核態執行緒可以服務一個或多個用戶態執行緒。

執行緒間如何同步？

同步解決的多執行緒操作共享資源的問題，目的是不管執行緒之間的執行如何穿插，最後的結果都是正確的。

我們前面知道執行緒和進程的關係：執行緒是進程當中的⼀條執⾏流程。所以說下面的一些同步機制不止針對執行緒，同樣也可以針對進程。

臨界區：我們把對共享資源訪問的程式片段稱為臨界區，我們希望這段程式碼是互斥的，保證在某時刻只能被一個執行緒執行，也就是說一個執行緒在臨界區執行時，其它執行緒應該被阻止進入臨界區。

臨界區不僅針對執行緒，同樣針對進程。

臨界區同步的一些實現方式：

1、鎖

使⽤加鎖操作和解鎖操作可以解決並發執行緒/進程的互斥問題。

任何想進⼊臨界區的執行緒，必須先執⾏加鎖操作。若加鎖操作順利通過，則執行緒可進⼊臨界區；在完成對臨界資源的訪問後再執⾏解鎖操作，以釋放該臨界資源。

加鎖和解鎖鎖住的是什麼呢？可以是臨界區對象，也可以只是一個簡單的互斥量，例如互斥量是0無鎖，1表示加鎖。

根據鎖的實現不同，可以分為忙等待鎖和和⽆忙等待鎖。

忙等待鎖和就是加鎖失敗的執行緒，會不斷嘗試獲取鎖，也被稱為自旋鎖，它會一直佔用CPU。

⽆忙等待鎖就是加鎖失敗的執行緒，會進入阻塞狀態，放棄CPU，等待被調度。

2、訊號量

訊號量是作業系統提供的⼀種協調共享資源訪問的⽅法。

通常訊號量表示資源的數量，對應的變數是⼀個整型（ sem ）變數。

另外，還有兩個原⼦操作的系統調⽤函數來控制訊號量的，分別是：

P 操作：將 sem 減 1 ，相減後，如果 sem < 0 ，則進程/執行緒進⼊阻塞等待，否則繼續，表明 P操作可能會阻塞；
V 操作：將 sem 加 1 ，相加後，如果 sem <= 0 ，喚醒⼀個等待中的進程/執行緒，表明 V 操作不會阻塞；

P 操作是⽤在進⼊臨界區之前，V 操作是⽤在離開臨界區之後，這兩個操作是必須成對出現的。

什麼是死鎖？

在兩個或者多個並發執行緒中，如果每個執行緒持有某種資源，而又等待其它執行緒釋放它或它們現在保持著的資源，在未改變這種狀態之前都不能向前推進，稱這一組執行緒產生了死鎖。通俗的講就是兩個或多個執行緒無限期的阻塞、相互等待的一種狀態。

死鎖產生有哪些條件？

死鎖產生需要同時滿足四個條件：

互斥條件：指執行緒對己經獲取到的資源進行它性使用，即該資源同時只由一個執行緒佔用。如果此時還有其它執行緒請求獲取獲取該資源，則請求者只能等待，直至佔有資源的執行緒釋放該資源。
請求並持有條件：指一個執行緒己經持有了至少一個資源，但又提出了新的資源請求，而新資源己被其它執行緒佔有，所以當前執行緒會被阻塞，但阻塞的同時並不釋放自己已經獲取的資源。
不可剝奪條件：指執行緒獲取到的資源在自己使用完之前不能被其它執行緒搶佔，只有在自己使用完畢後才由自己釋放該資源。
環路等待條件：指在發生死鎖時，必然存在一個執行緒——資源的環形鏈，即執行緒集合 {T0，T1，T2,…… ，Tn} 中 T0 正在等待一 T1 佔用的資源，Tl1正在等待 T2用的資源，…… Tn 在等待己被 T0佔用的資源。

如何避免死鎖呢？

產⽣死鎖的有四個必要條件：互斥條件、持有並等待條件、不可剝奪條件、環路等待條件。

避免死鎖，破壞其中的一個就可以。

消除互斥條件

這個是沒法實現，因為很多資源就是只能被一個執行緒佔用，例如鎖。

消除請求並持有條件

消除這個條件的辦法很簡單，就是一個執行緒一次請求其所需要的所有資源。

消除不可剝奪條件

佔用部分資源的執行緒進一步申請其他資源時，如果申請不到，可以主動釋放它佔有的資源，這樣不可剝奪這個條件就破壞掉了。

消除環路等待條件

可以靠按序申請資源來預防。所謂按序申請，是指資源是有線性順序的，申請的時候可以先申請資源序號小的，再申請資源序號大的，這樣線性化後就不存在環路了。

活鎖和飢餓鎖了解嗎？

飢餓鎖：

飢餓鎖，這個飢餓指的是資源飢餓，某個執行緒一直等不到它所需要的資源，從而無法向前推進，就像一個人因為飢餓無法成長。

活鎖：

在活鎖狀態下，處於活鎖執行緒組裡的執行緒狀態可以改變，但是整個活鎖組的執行緒無法推進。

活鎖可以用兩個人過一條很窄的小橋來比喻：為了讓對方先過，兩個人都往旁邊讓，但兩個人總是讓到同一邊。這樣，雖然兩個人的狀態一直在變化，但卻都無法往前推進。

記憶體管理

什麼是虛擬記憶體？

我們實際的物理記憶體主要是主存，但是物理主存空間有限，所以一般現代作業系統都會想辦法把一部分記憶體塊放到磁碟中，用到的時候再裝入主存，但是對用戶程式而言，是不需要注意實際的物理記憶體的，為什麼呢？因為有虛擬記憶體的機制。

簡單說，虛擬記憶體是作業系統提供的⼀種機制，將不同進程的虛擬地址和不同記憶體的物理地址映射起來。

每個進程都有自己獨立的地址空間，再由作業系統映射到到實際的物理記憶體。

於是，這⾥就引出了兩種地址的概念：

程式所使⽤的記憶體地址叫做虛擬記憶體地址（Virtual Memory Address）

實際存在硬體⾥⾯的空間地址叫物理記憶體地址（Physical Memory Address）。

什麼是記憶體分段？

程式是由若⼲個邏輯分段組成的，如可由程式碼分段、數據分段、棧段、堆段組成。不同的段是有不同的屬性的，所以就⽤分段（Segmentation）的形式把這些段分離出來。

分段機制下的虛擬地址由兩部分組成，段號和段內偏移量。

虛擬地址和物理地址通過段表映射，段表主要包括段號、段的界限。

我們來看一個映射，虛擬地址：段3、段偏移量500 —-> 段基地址7000+段偏移量500 —-> 物理地址：7500。

什麼是記憶體分頁？

分⻚是把整個虛擬和物理記憶體空間切成⼀段段固定尺⼨的⼤⼩。這樣⼀個連續並且尺⼨固定的記憶體空間，我們叫⻚（Page）。在 Linux 下，每⼀⻚的⼤⼩為 4KB 。

訪問分頁系統中記憶體數據需要兩次的記憶體訪問：一次是從記憶體中訪問頁表，從中找到指定的物理頁號，加上頁內偏移得到實際物理地址，第二次就是根據第一次得到的物理地址訪問記憶體取出數據。

多級頁表知道嗎？

作業系統可能會有非常多進程，如果只是使用簡單分頁，可能導致的後果就是頁表變得非常龐大。

所以，引入了多級頁表的解決方案。

所謂的多級頁表，就是把我們原來的單級頁表再次分頁，這裡利用了局部性原理，除了頂級頁表，其它級別的頁表一來可以在需要的時候才被創建，二來記憶體緊張的時候還可以被置換到磁碟中。

什麼是塊表？

同樣利用了局部性原理，即在⼀段時間內，整個程式的執⾏僅限於程式中的某⼀部分。相應地，執⾏所訪問的存儲空間也局限於某個記憶體區域。

利⽤這⼀特性，把最常訪問的⼏個⻚表項存儲到訪問速度更快的硬體，於是電腦科學家們，就在 CPU 芯⽚中，加⼊了⼀個專⻔存放程式最常訪問的⻚表項的 Cache，這個 Cache 就是 TLB（Translation Lookaside Buffer），通常稱為⻚錶快取、轉址旁路快取、快表等。

分頁和分段有什麼區別？

段是資訊的邏輯單位，它是根據用戶的需要劃分的，因此段對用戶是可見的；頁是資訊的物理單位，是為了管理主存的方便而劃分的，對用戶是透明的。
段的大小不固定，有它所完成的功能決定；頁的大小固定，由系統決定
段向用戶提供二維地址空間；頁向用戶提供的是一維地址空間
段是資訊的邏輯單位，便於存儲保護和資訊的共享，頁的保護和共享受到限制。

什麼是交換空間？

作業系統把物理記憶體(Physical RAM)分成一塊一塊的小記憶體，每一塊記憶體被稱為頁(page)。當記憶體資源不足時，Linux把某些頁的內容轉移至磁碟上的一塊空間上，以釋放記憶體空間。磁碟上的那塊空間叫做交換空間(swap space),而這一過程被稱為交換(swapping)。物理記憶體和交換空間的總容量就是虛擬記憶體的可用容量。

用途：

物理記憶體不足時一些不常用的頁可以被交換出去，騰給系統。
程式啟動時很多記憶體頁被用來初始化，之後便不再需要，可以交換出去。

頁面置換演算法有哪些？

在分頁系統里，一個虛擬的頁面可能在主存里，也可能在磁碟中，如果CPU發現虛擬地址對應的物理頁不在主存里，就會產生一個缺頁中斷，然後從磁碟中把該頁調入主存中。

如果記憶體里沒有空間，就需要從主存里選擇一個頁面來置換。

常見的頁面置換演算法：

最佳⻚⾯置換演算法（OPT）

最佳⻚⾯置換演算法是一個理想的演算法，基本思路是，置換在未來最⻓時間不訪問的⻚⾯。

所以，該演算法實現需要計算記憶體中每個邏輯⻚⾯的下⼀次訪問時間，然後⽐較，選擇未來最⻓時間不訪問的⻚⾯。

但這個演算法是無法實現的，因為當缺頁中斷髮生時，作業系統無法知道各個頁面下一次將在什麼時候被訪問。

先進先出置換演算法（FIFO）

既然我們⽆法預知⻚⾯在下⼀次訪問前所需的等待時間，那可以選擇在記憶體駐留時間很⻓的⻚⾯進⾏中置換，這個就是「先進先出置換」演算法的思想。

FIFO的實現機制是使用鏈表將所有在記憶體的頁面按照進入時間的早晚鏈接起來，然後每次置換鏈表頭上的頁面就行了，新加進來的頁面則掛在鏈表的末端。

最近最久未使⽤的置換演算法（LRU）

最近最久未使⽤（LRU）的置換演算法的基本思路是，發⽣缺⻚時，選擇最⻓時間沒有被訪問的⻚⾯進⾏置換，也就是說，該演算法假設已經很久沒有使⽤的⻚⾯很有可能在未來較⻓的⼀段時間內仍然不會被使⽤。

這種演算法近似最優置換演算法，最優置換演算法是通過「未來」的使⽤情況來推測要淘汰的⻚⾯，⽽ LRU 則是通過歷史的使⽤情況來推測要淘汰的⻚⾯。

LRU 在理論上是可以實現的，但代價很⾼。為了完全實現 LRU，需要在記憶體中維護⼀個所有⻚⾯的鏈表，最近最多使⽤的⻚⾯在表頭，最近最少使⽤的⻚⾯在表尾。

困難的是，在每次訪問記憶體時都必須要更新整個鏈表。在鏈表中找到⼀個⻚⾯，刪除它，然後把它移動到表頭是⼀個⾮常費時的操作。

所以，LRU 雖然看上去不錯，但是由於開銷⽐較⼤，實際應⽤中⽐較少使⽤。

時鐘頁面置換演算法

這個演算法的思路是，把所有的⻚⾯都保存在⼀個類似鍾⾯的環形鏈表中，⼀個錶針指向最⽼的⻚⾯。

當發⽣缺⻚中斷時，演算法⾸先檢查錶針指向的⻚⾯：

如果它的訪問位位是 0 就淘汰該⻚⾯，並把新的⻚⾯插⼊這個位置，然後把錶針前移⼀個位置；

如果訪問位是 1 就清除訪問位，並把錶針前移⼀個位置，重複這個過程直到找到了⼀個訪問位為 0 的⻚⾯為⽌；

最不常⽤置換演算法

最不常用演算法（LFU），當發⽣缺⻚中斷時，選擇訪問次數最少的那個⻚⾯，將其置換。

它的實現⽅式是，對每個⻚⾯設置⼀個「訪問計數器」，每當⼀個⻚⾯被訪問時，該⻚⾯的訪問計數器就累加 1。在發⽣缺⻚中斷時，淘汰計數器值最⼩的那個⻚⾯。

文件

硬鏈接和軟鏈接有什麼區別？

硬鏈接就是在目錄下創建一個條目，記錄著文件名與 inode 編號，這個 inode 就是源文件的 inode。刪除任意一個條目，文件還是存在，只要引用數量不為 0。但是硬鏈接有限制，它不能跨越文件系統，也不能對目錄進行鏈接。

軟鏈接相當於重新創建⼀個⽂件，這個⽂件有獨⽴的 inode，但是這個⽂件的內容是另外⼀個⽂件的路徑，所以訪問軟鏈接的時候，實際上相當於訪問到了另外⼀個⽂件，所以軟鏈接是可以跨⽂件系統的，甚⾄⽬標⽂件被刪除了，鏈接⽂件還是在的，只不過打不開指向的文件了而已。

IO

零拷貝了解嗎？

假如需要文件傳輸，使用傳統I/O，數據讀取和寫入是用戶空間到內核空間來回賦值，而內核空間的數據是通過作業系統的I/O介面從磁碟讀取或者寫入，這期間發生了多次用戶態和內核態的上下文切換，以及多次數據拷貝。

為了提升I/O性能，就需要減少用戶態與內核態的上下文切換和記憶體拷貝的次數。

這就用到了我們零拷貝的技術，零拷貝技術實現主要有兩種：

mmap + write

mmap() 系統調⽤函數會直接把內核緩衝區⾥的數據「映射」到⽤戶空間，這樣，作業系統內核與⽤戶空間就不需要再進⾏任何的數據拷⻉操作。

sendfile

在 Linux 內核版本 2.1 中，提供了⼀個專⻔發送⽂件的系統調⽤函數 sendfile() 。

⾸先，它可以替代前⾯的 read() 和 write() 這兩個系統調⽤，這樣就可以減少⼀次系統調⽤，也就減少了 2 次上下⽂切換的開銷。

其次，該系統調⽤，可以直接把內核緩衝區⾥的數據拷⻉到 socket 緩衝區⾥，不再拷⻉到⽤戶態，這樣就只有 2 次上下⽂切換，和 3 次數據拷⻉。

很多開源項目如Kafka、RocketMQ都採用了零拷貝技術來提升IO效率。

聊聊阻塞與⾮阻塞 I/O 、同步與非同步 I/O？

阻塞I/O

先來看看阻塞 I/O，當⽤戶程式執⾏ read ，執行緒會被阻塞，⼀直等到內核數據準備好，並把數據從內核緩衝區拷⻉到應⽤程式的緩衝區中，當拷⻉過程完成， read 才會返回。

注意，阻塞等待的是內核數據準備好和數據從內核態拷⻉到⽤戶態這兩個過程。

非阻塞I/O

⾮阻塞的 read 請求在數據未準備好的情況下⽴即返回，可以繼續往下執⾏，此時應⽤程式不斷輪詢內核，直到數據準備好，內核將數據拷⻉到應⽤程式緩衝區， read 調⽤才可以獲取到結果。

基於非阻塞的I/O多路復用

我們上面的非阻塞I/O有一個問題，什麼問題呢？應用程式要一直輪詢，這個過程沒法干其它事情，所以引入了I/O 多路復⽤技術。

當內核數據準備好時，以事件通知應⽤程式進⾏操作。

注意：⽆論是阻塞 I/O、還是⾮阻塞 I/O、非阻塞I/O多路復用，都是同步調⽤。因為它們在read調⽤時，內核將數據從內核空間拷⻉到應⽤程式空間，過程都是需要等待的，也就是說這個過程是同步的，如果內核實現的拷⻉效率不⾼，read調⽤就會在這個同步過程中等待⽐較⻓的時間。

非同步I/O

真正的非同步 I/O 是內核數據準備好和數據從內核態拷⻉到⽤戶態這兩個過程都不⽤等待。

發起 aio_read 之後，就⽴即返回，內核⾃動將數據從內核空間拷⻉到應⽤程式空間，這個拷⻉過程同樣是非同步的，內核⾃動完成的，和前⾯的同步操作不⼀樣，應⽤程式並不需要主動發起拷⻉動作。

拿例子理解幾種I/O模型

老三關注了很多UP主，有些UP主是老鴿子，到了更新的時間：

阻塞I/O就是，老三不幹別的，就乾等著，盯著UP的更新。

非阻塞I/O就是，老三發現UP沒更，就去喝個茶什麼的，過一會兒來盯一次，一直等到UP更新。

基於⾮阻塞的 I/O 多路復⽤好⽐，老三發現UP沒更，就去干別的，過了一會兒B站推送消息了，老三一看，有很多條，就去翻動態，看看等的UP是不是更新了。

非同步I/O就是，老三說UP你該更了，UP趕緊爆肝把影片做出來，然後把影片親自呈到老三面前，這個過程不用等待。

詳細講一講I/O多路復用？

我們先了解什麼是I/O多路復用？

我們在傳統的I/O模型中，如果服務端需要支援多個客戶端，我們可能要為每個客戶端分配一個進程/執行緒。

不管是基於重一點的進程模型，還是輕一點的執行緒模型，假如連接多了，作業系統是扛不住的。

所以就引入了I/O多路復用 技術。

簡單說，就是一個進程/執行緒維護多個Socket，這個多路復用就是多個連接復用一個進程/執行緒。

我們來看看I/O多路復用三種實現機制：

select

select 實現多路復⽤的⽅式是：

將已連接的 Socket 都放到⼀個⽂件描述符集合fd_set，然後調⽤ select 函數將fd_set集合拷⻉到內核⾥，讓內核來檢查是否有⽹絡事件產⽣，檢查的⽅式很粗暴，就是通過遍歷fd_set的⽅式，當檢查到有事件產⽣後，將此 Socket 標記為可讀或可寫，接著再把整個fd_set拷⻉回⽤戶態⾥，然後⽤戶態還需要再通過遍歷的⽅法找到可讀或可寫的 Socket，再對其處理。

select 使⽤固定⻓度的 BitsMap，表示⽂件描述符集合，⽽且所⽀持的⽂件描述符的個數是有限制的，在Linux 系統中，由內核中的 FD_SETSIZE 限制，默認最⼤值為 1024 ，只能監聽 0~1023 的⽂件描述符。

select機制的缺點：

（1）每次調用select，都需要把fd_set集合從用戶態拷貝到內核態，如果fd_set集合很大時，那這個開銷也很大，比如百萬連接卻只有少數活躍連接時這樣做就太沒有效率。

（2）每次調用select都需要在內核遍歷傳遞進來的所有fd_set，如果fd_set集合很大時，那這個開銷也很大。

（3）為了減少數據拷貝帶來的性能損壞，內核對被監控的fd_set集合大小做了限制，一般為1024，如果想要修改會比較麻煩，可能還需要編譯內核。

（4）每次調用select之前都需要遍歷設置監聽集合，重複工作。

poll

poll 不再⽤ BitsMap 來存儲所關注的⽂件描述符，取⽽代之⽤動態數組，以鏈表形式來組織，突破了select 的⽂件描述符個數限制，當然還會受到系統⽂件描述符限制。

但是 poll 和 select 並沒有太⼤的本質區別，都是使⽤線性結構存儲進程關注的Socket集合，因此都需要遍歷⽂件描述符集合來找到可讀或可寫的Socke，時間複雜度為O(n)，⽽且也需要在⽤戶態與內核態之間拷⻉⽂件描述符集合，這種⽅式隨著並發數上來，性能的損耗會呈指數級增⻓。

epoll

epoll 通過兩個⽅⾯，很好解決了 select/poll 的問題。

第⼀點，epoll 在內核⾥使⽤紅⿊樹來跟蹤進程所有待檢測的⽂件描述字，把需要監控的 socket 通過epoll_ctl() 函數加⼊內核中的紅⿊樹⾥，紅⿊樹是個⾼效的數據結構，增刪查⼀般時間複雜度是O(logn) ，通過對這棵⿊紅樹進⾏操作，這樣就不需要像 select/poll 每次操作時都傳⼊整個 socket 集合，只需要傳⼊⼀個待檢測的 socket，減少了內核和⽤戶空間⼤量的數據拷⻉和記憶體分配。

第⼆點， epoll 使⽤事件驅動的機制，內核⾥維護了⼀個鏈表來記錄就緒事件，當某個 socket 有事件發⽣時，通過回調函數，內核會將其加⼊到這個就緒事件列表中，當⽤戶調⽤ epoll_wait() 函數時，只會返回有事件發⽣的⽂件描述符的個數，不需要像 select/poll 那樣輪詢掃描整個 socket 集合，⼤⼤提⾼了檢測的效率。

epoll 的⽅式即使監聽的 Socket 數量越多的時候，效率不會⼤幅度降低，能夠同時監聽的 Socket 的數⽬也⾮常的多了，上限就為系統定義的進程打開的最⼤⽂件描述符個數。因⽽，epoll 被稱為解決 C10K 問題的利器。

部落客水平有限，參閱的資料在某些問題上也有一些出入，如有錯漏，歡迎指出！

參考：

[1].這可能最全的作業系統面試題

[2]. 作業系統常見面試題（2021最新版）

[3]. 小林coding《圖解系統》

[4].《現代作業系統》

[5]. 《深入理解電腦系統》

[6]. 《作業系統之哲學原理》

[7]. IO多路復用與epoll原理探究

Tags: 面試