標題是真事，感覺涼了，難受，爬起來整理了一波操作系統(tǒng)面試題，下次一定……

引論

什么是操作系統(tǒng)？

可以這么說，操作系統(tǒng)是一種運行在內核態(tài)的軟件。

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

操作系統(tǒng)主要有哪些功能？

操作系統(tǒng)最主要的功能：

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

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

操作系統(tǒng)結構

什么是內核？

可以這么說，內核是一個計算機程序，它是操作系統(tǒng)的核心，提供了操作系統(tǒng)最核心的能力，可以控制操作系統(tǒng)中所有的內容。

什么是用戶態(tài)和內核態(tài)？

內核具有很?的權限，可以控制 cpu、內存、硬盤等硬件，出于權限控制的考慮，因此?多數操作系統(tǒng)，把內存分成了兩個區(qū)域：

• 內核空間，這個內存空間只有內核程序可以訪問；
• ?戶空間，這個內存空間專?給應?程序使?，權限比較?。?/section>

?戶空間的代碼只能訪問?個局部的內存空間，?內核空間的代碼可以訪問所有內存空間。因此，當程序使??戶空間時，我們常說該程序在?戶態(tài)執(zhí)?，?當程序使內核空間時，程序則在內核態(tài)執(zhí)?。

用戶態(tài)和內核態(tài)是如何切換的？

應?程序如果需要進?內核空間，就需要通過系統(tǒng)調?，來進入內核態(tài)：

內核程序執(zhí)?在內核態(tài)，?戶程序執(zhí)?在?戶態(tài)。當應?程序使?系統(tǒng)調?時，會產??個中斷。發(fā)?中斷后， CPU 會中斷當前在執(zhí)?的?戶程序，轉?跳轉到中斷處理程序，也就是開始執(zhí)?內核程序。內核處理完后，主動觸發(fā)中斷，把 CPU 執(zhí)?權限交回給?戶程序，回到?戶態(tài)繼續(xù)?作。

進程和線程

并行和并發(fā)有什么區(qū)別？

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

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

什么是進程上下文切換？

對于單核單線程 CPU 而言，在某一時刻只能執(zhí)行一條 CPU 指令。上下文切換 (Context Switch) 是一種將 CPU 資源從一個進程分配給另一個進程的機制。從用戶角度看，計算機能夠并行運行多個進程，這恰恰是操作系統(tǒng)通過快速上下文切換造成的結果。在切換的過程中，操作系統(tǒng)需要先存儲當前進程的狀態(tài) (包括內存空間的指針，當前執(zhí)行完的指令等等)，再讀入下一個進程的狀態(tài)，然后執(zhí)行此進程。

進程有哪些狀態(tài)？

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

上圖中各個狀態(tài)的意義：

• 運?狀態(tài)（Runing）：該時刻進程占? CPU；
• 就緒狀態(tài)（Ready）：可運?，由于其他進程處于運?狀態(tài)?暫時停?運?；
• 阻塞狀態(tài)（Blocked）：該進程正在等待某?事件發(fā)?（如等待輸?/輸出操作的完成）?暫時停?運?，這時，即使給它CPU控制權，它也?法運?；

當然，進程還有另外兩個基本狀態(tài)：

• 創(chuàng)建狀態(tài)（new）：進程正在被創(chuàng)建時的狀態(tài)；
• 結束狀態(tài)（Exit）：進程正在從系統(tǒng)中消失時的狀態(tài)；

什么是僵尸進程？

僵尸進程是已完成且處于終止狀態(tài)，但在進程表中卻仍然存在的進程。

僵尸進程一般發(fā)生有父子關系的進程中，一個子進程的進程描述符在子進程退出時不會釋放，只有當父進程通過 wait() 或 waitpid() 獲取了子進程信息后才會釋放。如果子進程退出，而父進程并沒有調用 wait() 或 waitpid()，那么子進程的進程描述符仍然保存在系統(tǒng)中。

什么是孤兒進程？

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

進程有哪些調度算法？

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

• 先來先服務

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

• 短作業(yè)優(yōu)先

非搶占式的調度算法，按估計運行時間最短的順序進行調度。長作業(yè)有可能會餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因為如果一直有短作業(yè)到來，那么長作業(yè)永遠得不到調度。

• 優(yōu)先級調度

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

• 時間片輪轉

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

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

• 最短剩余時間優(yōu)先

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

進程間通信有哪些方式？

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

  管道可以分為兩類：匿名管道和命名管道。匿名管道是單向的，只能在有親緣關系的進程間通信；命名管道是雙向的，可以實現(xiàn)本機任意兩個進程通信。

  

• 信號 ：信號可以理解成一種電報，發(fā)送方發(fā)送內容，指定接收進程，然后發(fā)出特定的軟件中斷，操作系統(tǒng)接到中斷請求后，找到接收進程，通知接收進程處理信號。

  比如kill -9 1050就表示給PID為1050的進程發(fā)送SIGKIL信號。Linux系統(tǒng)中常用信號：

  （1）SIGHUP：用戶從終端注銷，所有已啟動進程都將收到該進程。系統(tǒng)缺省狀態(tài)下對該信號的處理是終止進程。（2）SIGINT：程序終止信號。程序運行過程中，按Ctrl+C鍵將產生該信號。（3）SIGQUIT：程序退出信號。程序運行過程中，按Ctrl+\鍵將產生該信號。（4）SIGBUS和SIGSEGV：進程訪問非法地址。（5）SIGFPE：運算中出現(xiàn)致命錯誤，如除零操作、數據溢出等。（6）SIGKILL：用戶終止進程執(zhí)行信號。shell下執(zhí)行kill -9發(fā)送該信號。（7）SIGTERM：結束進程信號。shell下執(zhí)行kill 進程pid發(fā)送該信號。（8）SIGALRM：定時器信號。（9）SIGCLD：子進程退出信號。如果其父進程沒有忽略該信號也沒有處理該信號，則子進程退出后將形成僵尸進程。

• 消息隊列：消息隊列就是保存在內核中的消息鏈表，包括Posix消息隊列和System V消息隊列。有足夠權限的進程可以向隊列中添加消息，被賦予讀權限的進程則可以讀走隊列中的消息。消息隊列克服了信號承載信息量少，管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。

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

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

  信號量表示資源的數量，控制信號量的?式有兩種原?操作：

  P 操作是?在進?共享資源之前，V 操作是?在離開共享資源之后，這兩個操作是必須成對出現(xiàn)的。

  

• ?個是 P 操作，這個操作會把信號量減去 1，相減后如果信號量 < 0，則表明資源已被占?，進程需阻塞等待；相減后如果信號量 >= 0，則表明還有資源可使?，進程可正常繼續(xù)執(zhí)?。
• 另?個是 V 操作，這個操作會把信號量加上 1，相加后如果信號量 <= 0，則表明當前有阻塞中的進程，于是會將該進程喚醒運?；相加后如果信號量 > 0，則表明當前沒有阻塞中的進程；

• Socket：與其他通信機制不同的是，它可用于不同機器間的進程通信。

優(yōu)缺點：

• 管道：簡單；效率低，容量有限；
• 消息隊列：不及時，寫入和讀取需要用戶態(tài)、內核態(tài)拷貝。
• 共享內存區(qū)：能夠很容易控制容量，速度快，但需要注意不同進程的同步問題。
• 信號量：不能傳遞復雜消息，一般用來實現(xiàn)進程間的同步；
• 信號：它是進程間通信的唯一異步機制。
• Socket：用于不同主機進程間的通信。

進程和線程的聯(lián)系和區(qū)別？

線程和進程的聯(lián)系：

線程是進程當中的?條執(zhí)?流程。

同?個進程內多個線程之間可以共享代碼段、數據段、打開的?件等資源，但每個線程各?都有?套獨?的寄存器和棧，這樣可以確保線程的控制流是相對獨?的。

線程與進程的?較如下：

• 調度：進程是資源（包括內存、打開的?件等）分配的單位，線程是 CPU 調度的單位；
• 資源：進程擁有?個完整的資源平臺，?線程只獨享必不可少的資源，如寄存器和棧；
• 擁有資源：線程同樣具有就緒、阻塞、執(zhí)?三種基本狀態(tài)，同樣具有狀態(tài)之間的轉換關系；
• 系統(tǒng)開銷：線程能減少并發(fā)執(zhí)?的時間和空間開銷——創(chuàng)建或撤銷進程時，系統(tǒng)都要為之分配或回收系統(tǒng)資源，如內存空間，I/O設備等，OS所付出的開銷顯著大于在創(chuàng)建或撤銷線程時的開銷，進程切換的開銷也遠大于線程切換的開銷。

線程上下文切換了解嗎？

這還得看線程是不是屬于同?個進程：

• 當兩個線程不是屬于同?個進程，則切換的過程就跟進程上下?切換?樣；

• 當兩個線程是屬于同?個進程，因為虛擬內存是共享的，所以在切換時，虛擬內存這些資源就保持不動，只需要切換線程的私有數據、寄存器等不共享的數據；

所以，線程的上下?切換相?進程，開銷要?很多。

線程有哪些實現(xiàn)方式？

主要有三種線程的實現(xiàn)?式：

• 內核態(tài)線程實現(xiàn)：在內核空間實現(xiàn)的線程，由內核直接管理直接管理線程。

• ?戶態(tài)線程實現(xiàn)：在?戶空間實現(xiàn)線程，不需要內核的參與，內核對線程無感知。

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

線程間如何同步？

同步解決的多線程操作共享資源的問題，目的是不管線程之間的執(zhí)行如何穿插，最后的結果都是正確的。

我們前面知道線程和進程的關系：線程是進程當中的?條執(zhí)?流程。所以說下面的一些同步機制不止針對線程，同樣也可以針對進程。

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

臨界區(qū)不僅針對線程，同樣針對進程。

臨界區(qū)同步的一些實現(xiàn)方式：

1、鎖

使?加鎖操作和解鎖操作可以解決并發(fā)線程/進程的互斥問題。

任何想進?臨界區(qū)的線程，必須先執(zhí)?加鎖操作。若加鎖操作順利通過，則線程可進?臨界區(qū)；在完成對臨界資源的訪問后再執(zhí)?解鎖操作，以釋放該臨界資源。

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

根據鎖的實現(xiàn)不同，可以分為忙等待鎖和和?忙等待鎖。

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

?忙等待鎖就是加鎖失敗的線程，會進入阻塞狀態(tài)，放棄CPU，等待被調度。

2、信號量

信號量是操作系統(tǒng)提供的?種協(xié)調共享資源訪問的?法。

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

另外，還有兩個原?操作的系統(tǒng)調?函數來控制信號量的，分別是：

• P 操作：將 sem 減 1 ，相減后，如果 sem < 0 ，則進程/線程進?阻塞等待，否則繼續(xù)，表明 P操作可能會阻塞；

• V 操作：將 sem 加 1 ，相加后，如果 sem <= 0 ，喚醒?個等待中的進程/線程，表明 V 操作不會阻塞；

P 操作是?在進?臨界區(qū)之前，V 操作是?在離開臨界區(qū)之后，這兩個操作是必須成對出現(xiàn)的。

什么是死鎖？

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

死鎖產生有哪些條件？

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

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

如何避免死鎖呢？

產?死鎖的有四個必要條件：互斥條件、持有并等待條件、不可剝奪條件、環(huán)路等待條件。

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

消除互斥條件

這個是沒法實現(xiàn)，因為很多資源就是只能被一個線程占用，例如鎖。

消除請求并持有條件

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

消除不可剝奪條件

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

消除環(huán)路等待條件

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

活鎖和饑餓鎖了解嗎？

饑餓鎖：

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

活鎖：

在活鎖狀態(tài)下，處于活鎖線程組里的線程狀態(tài)可以改變，但是整個活鎖組的線程無法推進。

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

內存管理

什么是虛擬內存？

我們實際的物理內存主要是主存，但是物理主存空間有限，所以一般現(xiàn)代操作系統(tǒng)都會想辦法把一部分內存塊放到磁盤中，用到的時候再裝入主存，但是對用戶程序而言，是不需要注意實際的物理內存的，為什么呢？因為有虛擬內存的機制。

簡單說，虛擬內存是操作系統(tǒng)提供的?種機制，將不同進程的虛擬地址和不同內存的物理地址映射起來。

每個進程都有自己獨立的地址空間，再由操作系統(tǒng)映射到到實際的物理內存。

于是，這?就引出了兩種地址的概念：

程序所使?的內存地址叫做虛擬內存地址（Virtual Memory Address）

實際存在硬件??的空間地址叫物理內存地址（Physical Memory Address）。

什么是內存分段？

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

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

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

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

什么是內存分頁？

分?是把整個虛擬和物理內存空間切成?段段固定尺?的??。這樣?個連續(xù)并且尺?固定的內存空間，我們叫?（Page）。在 Linux 下，每??的??為 4KB 。

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

多級頁表知道嗎？

操作系統(tǒng)可能會有非常多進程，如果只是使用簡單分頁，可能導致的后果就是頁表變得非常龐大。

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

所謂的多級頁表，就是把我們原來的單級頁表再次分頁，這里利用了局部性原理，除了頂級頁表，其它級別的頁表一來可以在需要的時候才被創(chuàng)建，二來內存緊張的時候還可以被置換到磁盤中。

什么是塊表？

同樣利用了局部性原理，即在?段時間內，整個程序的執(zhí)?僅限于程序中的某?部分。相應地，執(zhí)?所訪問的存儲空間也局限于某個內存區(qū)域。

利?這?特性，把最常訪問的?個?表項存儲到訪問速度更快的硬件，于是計算機科學家們，就在 CPU 芯?中，加?了?個專?存放程序最常訪問的?表項的 Cache，這個 Cache 就是 TLB（Translation Lookaside Buffer） ，通常稱為?表緩存、轉址旁路緩存、快表等。

分頁和分段有什么區(qū)別？

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

什么是交換空間？

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

用途：

• 物理內存不足時一些不常用的頁可以被交換出去，騰給系統(tǒng)。
• 程序啟動時很多內存頁被用來初始化，之后便不再需要，可以交換出去。

頁面置換算法有哪些？

在分頁系統(tǒng)里，一個虛擬的頁面可能在主存里，也可能在磁盤中，如果CPU發(fā)現(xiàn)虛擬地址對應的物理頁不在主存里，就會產生一個缺頁中斷，然后從磁盤中把該頁調入主存中。

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

常見的頁面置換算法：

• 最佳??置換算法（OPT）

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

所以，該算法實現(xiàn)需要計算內存中每個邏輯??的下?次訪問時間，然后?較，選擇未來最?時間不訪問的??。

但這個算法是無法實現(xiàn)的，因為當缺頁中斷發(fā)生時，操作系統(tǒng)無法知道各個頁面下一次將在什么時候被訪問。

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

既然我們?法預知??在下?次訪問前所需的等待時間，那可以選擇在內存駐留時間很?的??進?中置換，這個就是「先進先出置換」算法的思想。

FIFO的實現(xiàn)機制是使用鏈表將所有在內存的頁面按照進入時間的早晚鏈接起來，然后每次置換鏈表頭上的頁面就行了，新加進來的頁面則掛在鏈表的末端。

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

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

這種算法近似最優(yōu)置換算法，最優(yōu)置換算法是通過「未來」的使?情況來推測要淘汰的??，? LRU 則是通過歷史的使?情況來推測要淘汰的??。

LRU 在理論上是可以實現(xiàn)的，但代價很?。為了完全實現(xiàn) LRU，需要在內存中維護?個所有??的鏈表，最近最多使?的??在表頭，最近最少使?的??在表尾。

困難的是，在每次訪問內存時都必須要更新整個鏈表。在鏈表中找到?個??，刪除它，然后把它移動到表頭是?個?常費時的操作。

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

• 時鐘頁面置換算法

這個算法的思路是，把所有的??都保存在?個類似鐘?的環(huán)形鏈表中，?個表針指向最?的??。

當發(fā)?缺?中斷時，算法?先檢查表針指向的??：

如果它的訪問位位是 0 就淘汰該??，并把新的??插?這個位置，然后把表針前移?個位置；

如果訪問位是 1 就清除訪問位，并把表針前移?個位置，重復這個過程直到找到了?個訪問位為 0 的??為?；

• 最不常?置換算法

最不常用算法（LFU），當發(fā)?缺?中斷時，選擇訪問次數最少的那個??，將其置換。

它的實現(xiàn)?式是，對每個??設置?個「訪問計數器」，每當?個??被訪問時，該??的訪問計數器就累加 1。在發(fā)?缺?中斷時，淘汰計數器值最?的那個??。

文件

硬鏈接和軟鏈接有什么區(qū)別？

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

• 軟鏈接相當于重新創(chuàng)建?個?件，這個?件有獨?的 inode，但是這個?件的內容是另外?個?件的路徑，所以訪問軟鏈接的時候，實際上相當于訪問到了另外?個?件，所以軟鏈接是可以跨?件系統(tǒng)的，甚??標?件被刪除了，鏈接?件還是在的，只不過打不開指向的文件了而已。

  

IO

零拷貝了解嗎？

假如需要文件傳輸，使用傳統(tǒng)I/O，數據讀取和寫入是用戶空間到內核空間來回賦值，而內核空間的數據是通過操作系統(tǒng)的I/O接口從磁盤讀取或者寫入，這期間發(fā)生了多次用戶態(tài)和內核態(tài)的上下文切換，以及多次數據拷貝。

為了提升I/O性能，就需要減少用戶態(tài)與內核態(tài)的上下文切換和內存拷貝的次數。

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

• mmap + write

mmap() 系統(tǒng)調?函數會直接把內核緩沖區(qū)?的數據「映射」到?戶空間，這樣，操作系統(tǒng)內核與?戶空間就不需要再進?任何的數據拷?操作。

• sendfile

在 Linux 內核版本 2.1 中，提供了?個專?發(fā)送?件的系統(tǒng)調?函數 sendfile() 。

?先，它可以替代前?的 read() 和 write() 這兩個系統(tǒng)調?，這樣就可以減少?次系統(tǒng)調?，也就減少了 2 次上下?切換的開銷。

其次，該系統(tǒng)調?，可以直接把內核緩沖區(qū)?的數據拷?到 socket 緩沖區(qū)?，不再拷?到?戶態(tài)，這樣就只有 2 次上下?切換，和 3 次數據拷?。

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

聊聊阻塞與?阻塞 **I/O **、 同步與異步 I/O？

• 阻塞I/O

先來看看阻塞 I/O，當?戶程序執(zhí)? read ，線程會被阻塞，?直等到內核數據準備好，并把數據從內核緩沖區(qū)拷?到應?程序的緩沖區(qū)中，當拷?過程完成， read 才會返回。

注意，阻塞等待的是內核數據準備好和數據從內核態(tài)拷?到?戶態(tài)這兩個過程。

• 非阻塞I/O

?阻塞的 read 請求在數據未準備好的情況下?即返回，可以繼續(xù)往下執(zhí)?，此時應?程序不斷輪詢內核，直到數據準備好，內核將數據拷?到應?程序緩沖區(qū)， read 調?才可以獲取到結果。

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

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

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

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

• 異步I/O

真正的異步 I/O 是內核數據準備好和數據從內核態(tài)拷?到?戶態(tài)這兩個過程都不?等待。

發(fā)起 aio_read 之后，就?即返回，內核?動將數據從內核空間拷?到應?程序空間，這個拷?過程同樣是異步的，內核?動完成的，和前?的同步操作不?樣，應?程序并不需要主動發(fā)起拷?動作。

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

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

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

非阻塞I/O就是，老三發(fā)現(xiàn)UP沒更，就去喝個茶什么的，過一會兒來盯一次，一直等到UP更新。

基于?阻塞的 I/O 多路復?好?，老三發(fā)現(xiàn)UP沒更，就去干別的，過了一會兒B站推送消息了，老三一看，有很多條，就去翻動態(tài)，看看等的UP是不是更新了。

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

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

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

我們在傳統(tǒng)的I/O模型中，如果服務端需要支持多個客戶端，我們可能要為每個客戶端分配一個進程/線程。

不管是基于重一點的進程模型，還是輕一點的線程模型，假如連接多了，操作系統(tǒng)是扛不住的。

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

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

我們來看看I/O多路復用三種實現(xiàn)機制：

• select

select 實現(xiàn)多路復?的?式是：

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

select 使?固定?度的 BitsMap，表示?件描述符集合，?且所?持的?件描述符的個數是有限制的，在Linux 系統(tǒng)中，由內核中的 FD_SETSIZE 限制， 默認最?值為 1024 ，只能監(jiān)聽 0~1023 的?件描述符。

select機制的缺點：

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

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

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

（4）每次調用select之前都需要遍歷設置監(jiān)聽集合，重復工作。

• poll

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

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

• epoll

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

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

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

epoll 的?式即使監(jiān)聽的 Socket 數量越多的時候，效率不會?幅度降低，能夠同時監(jiān)聽的 Socket 的數?也?常的多了，上限就為系統(tǒng)定義的進程打開的最??件描述符個數。因?，epoll 被稱為解決 C10K 問題的利器。

參考：

[1].這可能最全的操作系統(tǒng)面試題https://blog.csdn.net/qq_36894974/article/details/115654242

[2]. 操作系統(tǒng)常見面試題（2021最新版）https://blog.csdn.net/weixin_45545542/article/details/117929487

[3]. 小林coding《圖解系統(tǒng)》

[4].《現(xiàn)代操作系統(tǒng)》

[5]. 《深入理解計算機系統(tǒng)》

[6]. 《操作系統(tǒng)之哲學原理》