2-5w 字 - 36 張圖爆肝操作系統面試題

大家好，我是 cxuan，我之前彙總了一下關於操作系統的面試題，最近又重新翻閱了一下發現不是很全，現在也到了面試季了，所以我又花了一週的時間修訂整理了一下這份面試題，這份面試題可以吊打市面上所有的操作系統面試題了，不是我說，是因爲我係統查過，如果有不相信的大佬，歡迎狠狠的打我臉。

這份面試題有四十多道題，涉及操作系統簡介篇、進程和線程篇、內存管理篇、文件系統篇、IO 篇、死鎖篇。囊括了校招面試和社招面試，看完這一篇文章，保準你能和麪試官侃侃而談，增加進入大廠的幾率！

話不多說，下面我們直接進入面試題。

操作系統簡介篇

解釋一下什麼是操作系統

操作系統是管理硬件和軟件的一種應用程序。操作系統是運行在計算機上最重要的一種軟件，它管理計算機的資源和進程以及所有的硬件和軟件。它爲計算機硬件和軟件提供了一種中間層，使應用軟件和硬件進行分離，讓我們無需關注硬件的實現，把關注點更多放在軟件應用上。

通常情況下，計算機上會運行着許多應用程序，它們都需要對內存和 CPU 進行交互，操作系統的目的就是爲了保證這些訪問和交互能夠準確無誤的進行。

操作系統的主要功能

一般來說，現代操作系統主要提供下面幾種功能

軟件訪問硬件的幾種方式

軟件訪問硬件其實就是一種 IO 操作，軟件訪問硬件的方式，也就是 I/O 操作的方式有哪些。

硬件在 I/O 上大致分爲並行和串行，同時也對應串行接口和並行接口。

隨着計算機技術的發展，I/O 控制方式也在不斷髮展。選擇和衡量 I/O 控制方式有如下三條原則

（1） 數據傳送速度足夠快，能滿足用戶的需求但又不丟失數據；

（2） 系統開銷小，所需的處理控制程序少；

（3） 能充分發揮硬件資源的能力，使 I/O 設備儘可能忙，而 CPU 等待時間儘可能少。

根據以上控制原則，I/O 操作可以分爲四類

上述兩種方法的特點都是以 CPU 爲中心，數據傳送通過一段程序來實現，軟件的傳送手段限制了數據傳送的速度。接下來介紹的這兩種 I/O 控制方式採用硬件的方法來顯示 I/O 的控制

解釋一下操作系統的主要目的是什麼

操作系統是一種軟件，它的主要目的有三種

操作系統的種類有哪些

操作系統通常預裝在你購買計算機之前。大部分用戶都會使用默認的操作系統，但是你也可以升級甚至更改操作系統。但是一般常見的操作系統只有三種：Windows、macOS 和 Linux。

爲什麼 Linux 系統下的應用程序不能直接在 Windows 下運行

這是一個老生常談的問題了，在這裏給出具體的回答。

其中一點是因爲 Linux 系統和 Windows 系統的格式不同，格式就是協議，就是在固定位置有意義的數據。Linux 下的可執行程序文件格式是 elf，可以使用 readelf 命令查看 elf 文件頭。

而 Windows 下的可執行程序是 PE 格式，它是一種可移植的可執行文件。

還有一點是因爲 Linux 系統和 Windows 系統的 API 不同，這個 API 指的就是操作系統的 API，Linux 中的 API 被稱爲系統調用，是通過 int 0x80 這個軟中斷實現的。而 Windows 中的 API 是放在動態鏈接庫文件中的，也就是 Windows 開發人員所說的 DLL ，這是一個庫，裏面包含代碼和數據。Linux 中的可執行程序獲得系統資源的方法和 Windows 不一樣，所以顯然是不能在 Windows 中運行的。

操作系統結構

單體系統

在大多數系統中，整個系統在內核態以單一程序的方式運行。整個操作系統是以程序集合來編寫的，鏈接在一塊形成一個大的二進制可執行程序，這種系統稱爲單體系統。

在單體系統中構造實際目標程序時，會首先編譯所有單個過程（或包含這些過程的文件），然後使用系統鏈接器將它們全部綁定到一個可執行文件中

在單體系統中，對於每個系統調用都會有一個服務程序來保障和運行。需要一組實用程序來彌補服務程序需要的功能，例如從用戶程序中獲取數據。可將各種過程劃分爲一個三層模型

除了在計算機初啓動時所裝載的核心操作系統外，許多操作系統還支持額外的擴展。比如 I/O 設備驅動和文件系統。這些部件可以按需裝載。在 UNIX 中把它們叫做 共享庫(shared library)，在 Windows 中則被稱爲 動態鏈接庫(Dynamic Link Library,DLL)。他們的擴展名爲 .dll，在 C:\Windows\system32 目錄下存在 1000 多個 DLL 文件，所以不要輕易刪除 C 盤文件，否則可能就炸了哦。

分層系統

分層系統使用層來分隔不同的功能單元。每一層只與該層的上層和下層通信。每一層都使用下面的層來執行其功能。層之間的通信通過預定義的固定接口通信。

微內核

爲了實現高可靠性，將操作系統劃分成小的、層級之間能夠更好定義的模塊是很有必要的，只有一個模塊 --- 微內核 --- 運行在內核態，其餘模塊可以作爲普通用戶進程運行。由於把每個設備驅動和文件系統分別作爲普通用戶進程，這些模塊中的錯誤雖然會使這些模塊崩潰，但是不會使整個系統死機。

MINIX 3 是微內核的代表作，它的具體結構如下

在內核的外部，系統的構造有三層，它們都在用戶態下運行，最底層是設備驅動器。由於它們都在用戶態下運行，所以不能物理的訪問 I/O 端口空間，也不能直接發出 I/O 命令。相反，爲了能夠對 I/O 設備編程，驅動器構建一個結構，指明哪個參數值寫到哪個 I/O 端口，並聲稱一個內核調用，這樣就完成了一次調用過程。

客戶 - 服務器模式

微內核思想的策略是把進程劃分爲兩類：服務器，每個服務器用來提供服務；客戶端，使用這些服務。這個模式就是所謂的 客戶-服務器模式。

客戶 - 服務器模式會有兩種載體，一種情況是一臺計算機既是客戶又是服務器，在這種方式下，操作系統會有某種優化；但是普遍情況下是客戶端和服務器在不同的機器上，它們通過局域網或廣域網連接。

客戶通過發送消息與服務器通信，客戶端並不需要知道這些消息是在本地機器上處理，還是通過網絡被送到遠程機器上處理。對於客戶端而言，這兩種情形是一樣的：都是發送請求並得到迴應。

爲什麼稱爲陷入內核

如果把軟件結構進行分層說明的話，應該是這個樣子的，最外層是應用程序，裏面是操作系統內核。

應用程序處於特權級 3，操作系統內核處於特權級 0 。如果用戶程序想要訪問操作系統資源時，會發起系統調用，陷入內核，這樣 CPU 就進入了內核態，執行內核代碼。至於爲什麼是陷入，我們看圖，內核是一個凹陷的構造，有陷下去的感覺，所以稱爲陷入。

什麼是用戶態和內核態

用戶態和內核態是操作系統的兩種運行狀態。

那麼爲什麼要有用戶態和內核態呢？

這個主要是訪問能力的限制的考量，計算機中有一些比較危險的操作，比如設置時鐘、內存清理，這些都需要在內核態下完成，如果隨意進行這些操作，那你的系統得崩潰多少次。

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

所有的用戶進程都是運行在用戶態的，但是我們上面也說了，用戶程序的訪問能力有限，一些比較重要的比如從硬盤讀取數據，從鍵盤獲取數據的操作則是內核態才能做的事情，而這些數據卻又對用戶程序來說非常重要。所以就涉及到兩種模式下的轉換，即用戶態 -> 內核態 -> 用戶態，而唯一能夠做這些操作的只有 系統調用，而能夠執行系統調用的就只有 操作系統。

一般用戶態 -> 內核態的轉換我們都稱之爲 trap 進內核，也被稱之爲 陷阱指令(trap instruction)。

他們的工作流程如下：

什麼是內核

在計算機中，內核是一個計算機程序，它是操作系統的核心，可以控制操作系統中所有的內容。內核通常是在 boot loader 裝載程序之前加載的第一個程序。

這裏還需要了解一下什麼是 boot loader。

boot loader 又被稱爲引導加載程序，能夠將計算機的操作系統放入內存中。在電源通電或者計算機重啓時，BIOS 會執行一些初始測試，然後將控制權轉移到引導加載程序所在的主引導記錄(MBR) 。

什麼是實時系統

實時操作系統對時間做出了嚴格的要求，實時操作系統分爲兩種：硬實時和軟實時

硬實時操作系統規定某個動作必須在規定的時刻內完成或發生，比如汽車生產車間，焊接機器必須在某一時刻內完成焊接，焊接的太早或者太晚都會對汽車造成永久性傷害。

軟實時操作系統雖然不希望偶爾違反最終的時限要求，但是仍然可以接受。並且不會引起任何永久性傷害。比如數字音頻、多媒體、手機都是屬於軟實時操作系統。

你可以簡單理解硬實時和軟實時的兩個指標：是否在時刻內必須完成以及是否造成嚴重損害。

Linux 操作系統的啓動過程

當計算機電源通電後，BIOS會進行開機自檢(Power-On-Self-Test, POST)，對硬件進行檢測和初始化。因爲操作系統的啓動會使用到磁盤、屏幕、鍵盤、鼠標等設備。下一步，磁盤中的第一個分區，也被稱爲 MBR(Master Boot Record) 主引導記錄，被讀入到一個固定的內存區域並執行。這個分區中有一個非常小的，只有 512 字節的程序。程序從磁盤中調入 boot 獨立程序，boot 程序將自身複製到高位地址的內存從而爲操作系統釋放低位地址的內存。

複製完成後，boot 程序讀取啓動設備的根目錄。boot 程序要理解文件系統和目錄格式。然後 boot 程序被調入內核，把控制權移交給內核。直到這裏，boot 完成了它的工作。系統內核開始運行。

內核啓動代碼是使用彙編語言完成的，主要包括創建內核堆棧、識別 CPU 類型、計算內存、禁用中斷、啓動內存管理單元等，然後調用 C 語言的 main 函數執行操作系統部分。

這部分也會做很多事情，首先會分配一個消息緩衝區來存放調試出現的問題，調試信息會寫入緩衝區。如果調試出現錯誤，這些信息可以通過診斷程序調出來。

然後操作系統會進行自動配置，檢測設備，加載配置文件，被檢測設備如果做出響應，就會被添加到已鏈接的設備表中，如果沒有相應，就歸爲未連接直接忽略。

配置完所有硬件後，接下來要做的就是仔細手工處理進程 0，設置其堆棧，然後運行它，執行初始化、配置時鐘、掛載文件系統。創建 init 進程(進程 1 ) 和 守護進程(進程 2)。

init 進程會檢測它的標誌以確定它是否爲單用戶還是多用戶服務。在前一種情況中，它會調用 fork 函數創建一個 shell 進程，並且等待這個進程結束。後一種情況調用 fork 函數創建一個運行系統初始化的 shell 腳本（即 /etc/rc）的進程，這個進程可以進行文件系統一致性檢測、掛載文件系統、開啓守護進程等。

然後 /etc/rc 這個進程會從 /etc/ttys 中讀取數據，/etc/ttys 列出了所有的終端和屬性。對於每一個啓用的終端，這個進程調用 fork 函數創建一個自身的副本，進行內部處理並運行一個名爲 getty 的程序。

getty 程序會在終端上輸入

login:

等待用戶輸入用戶名，在輸入用戶名後，getty 程序結束，登陸程序 /bin/login 開始運行。login 程序需要輸入密碼，並與保存在 /etc/passwd 中的密碼進行對比，如果輸入正確，login 程序以用戶 shell 程序替換自身，等待第一個命令。如果不正確，login 程序要求輸入另一個用戶名。

整個系統啓動過程如下

進程和線程篇

多處理系統的優勢

隨着處理器的不斷增加，我們的計算機系統由單機系統變爲了多處理系統，多處理系統的吞吐量比較高，多處理系統擁有多個並行的處理器，這些處理器共享時鐘、內存、總線、外圍設備等。

多處理系統由於可以共享資源，因此可以開源節流，省錢。整個系統的可靠性也隨之提高。

什麼是進程和進程表

進程就是正在執行程序的實例，比如說 Web 程序就是一個進程，shell 也是一個進程，文章編輯器 typora 也是一個進程。

操作系統負責管理所有正在運行的進程，操作系統會爲每個進程分配特定的時間來佔用 CPU，操作系統還會爲每個進程分配特定的資源。

操作系統爲了跟蹤每個進程的活動狀態，維護了一個進程表。在進程表的內部，列出了每個進程的狀態以及每個進程使用的資源等。

什麼是線程，線程和進程的區別

這又是一道老生常談的問題了，從操作系統的角度來回答一下吧。

我們上面說到進程是正在運行的程序的實例，而線程其實就是進程中的單條流向，因爲線程具有進程中的某些屬性，所以線程又被稱爲輕量級的進程。瀏覽器如果是一個進程的話，那麼瀏覽器下面的每個 tab 頁可以看作是一個個的線程。

下面是線程和進程持有資源的區別

線程不像進程那樣具有很強的獨立性，線程之間會共享數據

創建線程的開銷要比進程小很多，因爲創建線程僅僅需要堆棧指針和程序計數器就可以了，而創建進程需要操作系統分配新的地址空間，數據資源等，這個開銷比較大。

什麼是上下文切換

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

使用多線程的好處是什麼

多線程是程序員不得不知的基本素養之一，所以，下面我們給出一些多線程編程的好處

進程終止的方式

進程的終止

進程在創建之後，它就開始運行並做完成任務。然而，沒有什麼事兒是永不停歇的，包括進程也一樣。進程早晚會發生終止，但是通常是由於以下情況觸發的

正常退出

多數進程是由於完成了工作而終止。當編譯器完成了所給定程序的編譯之後，編譯器會執行一個系統調用告訴操作系統它完成了工作。這個調用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向屏幕中的軟件也支持自願終止操作。字處理軟件、Internet 瀏覽器和類似的程序中總有一個供用戶點擊的圖標或菜單項，用來通知進程刪除它所打開的任何臨時文件，然後終止。

錯誤退出

進程發生終止的第二個原因是發現嚴重錯誤，例如，如果用戶執行如下命令

cc foo.c

爲了能夠編譯 foo.c 但是該文件不存在，於是編譯器就會發出聲明並退出。在給出了錯誤參數時，面向屏幕的交互式進程通常並不會直接退出，因爲這從用戶的角度來說並不合理，用戶需要知道發生了什麼並想要進行重試，所以這時候應用程序通常會彈出一個對話框告知用戶發生了系統錯誤，是需要重試還是退出。

嚴重錯誤

進程終止的第三個原因是由進程引起的錯誤，通常是由於程序中的錯誤所導致的。例如，執行了一條非法指令，引用不存在的內存，或者除數是 0 等。在有些系統比如 UNIX 中，進程可以通知操作系統，它希望自行處理某種類型的錯誤，在這類錯誤中，進程會收到信號（中斷），而不是在這類錯誤出現時直接終止進程。

被其他進程殺死

第四個終止進程的原因是，某個進程執行系統調用告訴操作系統殺死某個進程。在 UNIX 中，這個系統調用是 kill。在 Win32 中對應的函數是 TerminateProcess（注意不是系統調用）。

進程間的通信方式

進程間的通信方式比較多，首先你需要理解下面這幾個概念

  1. 任何時候兩個進程不能同時處於臨界區

  2. 不應對 CPU 的速度和數量做任何假設

  3. 位於臨界區外的進程不得阻塞其他進程

  4. 不能使任何進程無限等待進入臨界區

進程間的通信用專業一點的術語來表示就是 Inter Process Communication，IPC，它主要有下面 7。種通信方式

進程間狀態模型

進程的三態模型

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

圖中會涉及三種狀態

  1. 運行態：運行態指的就是進程實際佔用 CPU 時間片運行時

  2. 就緒態：就緒態指的是可運行，但因爲其他進程正在運行而處於就緒狀態

  3. 阻塞態：阻塞態又被稱爲睡眠態，它指的是進程不具備運行條件，正在等待被 CPU 調度。

邏輯上來說，運行態和就緒態是很相似的。這兩種情況下都表示進程可運行，但是第二種情況沒有獲得 CPU 時間分片。第三種狀態與前兩種狀態不同的原因是這個進程不能運行，CPU 空閒時也不能運行。

三種狀態會涉及四種狀態間的切換，在操作系統發現進程不能繼續執行時會發生狀態1的輪轉，在某些系統中進程執行系統調用，例如 pause，來獲取一個阻塞的狀態。在其他系統中包括 UNIX，當進程從管道或特殊文件（例如終端）中讀取沒有可用的輸入時，該進程會被自動終止。

轉換 2 和轉換 3 都是由進程調度程序（操作系統的一部分）引起的，進程本身不知道調度程序的存在。轉換 2 的出現說明進程調度器認定當前進程已經運行了足夠長的時間，是時候讓其他進程運行 CPU 時間片了。當所有其他進程都運行過後，這時候該是讓第一個進程重新獲得 CPU 時間片的時候了，就會發生轉換 3。

程序調度指的是，決定哪個進程優先被運行和運行多久，這是很重要的一點。已經設計出許多算法來嘗試平衡系統整體效率與各個流程之間的競爭需求。

當進程等待的一個外部事件發生時（如從外部輸入一些數據後），則發生轉換 4。如果此時沒有其他進程在運行，則立刻觸發轉換 3，該進程便開始運行，否則該進程會處於就緒階段，等待 CPU 空閒後再輪到它運行。

進程的五態模型

在三態模型的基礎上，增加了兩個狀態，即 新建 和 終止 狀態。

創建進程需要兩個步驟：即爲新進程分配所需要的資源和空間，設置進程爲就緒態，並等待調度執行。

終止一個進程需要兩個步驟：

  1. 先等待操作系統或相關的進程進行善後處理。

  2. 然後回收佔用的資源並被系統刪除。

調度算法都有哪些

調度算法分爲三大類：批處理中的調度、交互系統中的調度、實時系統中的調度

批處理中的調度

先來先服務

很像是先到先得。。。可能最簡單的非搶佔式調度算法的設計就是 先來先服務(first-come,first-serverd)。使用此算法，將按照請求順序爲進程分配 CPU。最基本的，會有一個就緒進程的等待隊列。當第一個任務從外部進入系統時，將會立即啓動並允許運行任意長的時間。它不會因爲運行時間太長而中斷。當其他作業進入時，它們排到就緒隊列尾部。當正在運行的進程阻塞，處於等待隊列的第一個進程就開始運行。當一個阻塞的進程重新處於就緒態時，它會像一個新到達的任務，會排在隊列的末尾，即排在所有進程最後。

這個算法的強大之處在於易於理解和編程，在這個算法中，一個單鏈表記錄了所有就緒進程。要選取一個進程運行，只要從該隊列的頭部移走一個進程即可；要添加一個新的作業或者阻塞一個進程，只要把這個作業或進程附加在隊列的末尾即可。這是很簡單的一種實現。

不過，先來先服務也是有缺點的，那就是沒有優先級的關係，試想一下，如果有 100 個 I/O 進程正在排隊，第 101 個是一個 CPU 密集型進程，那豈不是需要等 100 個 I/O 進程運行完畢纔會等到一個 CPU 密集型進程運行，這在實際情況下根本不可能，所以需要優先級或者搶佔式進程的出現來優先選擇重要的進程運行。

最短作業優先

批處理中，第二種調度算法是 最短作業優先(Shortest Job First)，我們假設運行時間已知。例如，一家保險公司，因爲每天要做類似的工作，所以人們可以相當精確地預測處理 1000 個索賠的一批作業需要多長時間。當輸入隊列中有若干個同等重要的作業被啓動時，調度程序應使用最短優先作業算法

如上圖 a 所示，這裏有 4 個作業 A、B、C、D ，運行時間分別爲 8、4、4、4 分鐘。若按圖中的次序運行，則 A 的週轉時間爲 8 分鐘，B 爲 12 分鐘，C 爲 16 分鐘，D 爲 20 分鐘，平均時間內爲 14 分鐘。

現在考慮使用最短作業優先算法運行 4 個作業，如上圖 b 所示，目前的週轉時間分別爲 4、8、12、20，平均爲 11 分鐘，可以證明最短作業優先是最優的。考慮有 4 個作業的情況，其運行時間分別爲 a、b、c、d。第一個作業在時間 a 結束，第二個在時間 a + b 結束，以此類推。平均週轉時間爲 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，所以 a 應該是最短優先作業，其次是 b，然後是 c ，最後是 d 它就只能影響自己的週轉時間了。

需要注意的是，在所有的進程都可以運行的情況下，最短作業優先的算法纔是最優的。

最短剩餘時間優先

最短作業優先的搶佔式版本被稱作爲 最短剩餘時間優先(Shortest Remaining Time Next) 算法。使用這個算法，調度程序總是選擇剩餘運行時間最短的那個進程運行。當一個新作業到達時，其整個時間同當前進程的剩餘時間做比較。如果新的進程比當前運行進程需要更少的時間，當前進程就被掛起，而運行新的進程。這種方式能夠使短期作業獲得良好的服務。

交互式系統中的調度

交互式系統中在個人計算機、服務器和其他系統中都是很常用的，所以有必要來探討一下交互式調度

輪詢調度

一種最古老、最簡單、最公平並且最廣泛使用的算法就是 輪詢算法(round-robin)。每個進程都會被分配一個時間段，稱爲時間片(quantum)，在這個時間片內允許進程運行。如果時間片結束時進程還在運行的話，則搶佔一個 CPU 並將其分配給另一個進程。如果進程在時間片結束前阻塞或結束，則 CPU 立即進行切換。輪詢算法比較容易實現。調度程序所做的就是維護一個可運行進程的列表，就像下圖中的 a，當一個進程用完時間片後就被移到隊列的末尾，就像下圖的 b。

優先級調度

事實情況是不是所有的進程都是優先級相等的。例如，在一所大學中的等級制度，首先是院長，然後是教授、祕書、後勤人員，最後是學生。這種將外部情況考慮在內就實現了優先級調度(priority scheduling)

它的基本思想很明確，每個進程都被賦予一個優先級，優先級高的進程優先運行。

但是也不意味着高優先級的進程能夠永遠一直運行下去，調度程序會在每個時鐘中斷期間降低當前運行進程的優先級。如果此操作導致其優先級降低到下一個最高進程的優先級以下，則會發生進程切換。或者，可以爲每個進程分配允許運行的最大時間間隔。當時間間隔用完後，下一個高優先級的進程會得到運行的機會。

最短進程優先

對於批處理系統而言，由於最短作業優先常常伴隨着最短響應時間，一種方式是根據進程過去的行爲進行推測，並執行估計運行時間最短的那一個。假設每個終端上每條命令的預估運行時間爲 T0，現在假設測量到其下一次運行時間爲 T1，可以用兩個值的加權來改進估計時間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是儘快忘掉老的運行時間，還是在一段長時間內始終記住它們。當 a = 1/2 時，可以得到下面這個序列

可以看到，在三輪過後，T0 在新的估計值中所佔比重下降至 1/8。

有時把這種通過當前測量值和先前估計值進行加權平均從而得到下一個估計值的技術稱作 老化(aging)。這種方法會使用很多預測值基於當前值的情況。

彩票調度

有一種既可以給出預測結果而又有一種比較簡單的實現方式的算法，就是 彩票調度(lottery scheduling)算法。他的基本思想爲進程提供各種系統資源的彩票。當做出一個調度決策的時候，就隨機抽出一張彩票，擁有彩票的進程將獲得資源。比如在 CPU 進行調度時，系統可以每秒持有 50 次抽獎，每個中獎進程會獲得額外運行時間的獎勵。

可以把彩票理解爲 buff，這個 buff 有 15% 的幾率能讓你產生 速度之靴 的效果。

公平分享調度

如果用戶 1 啓動了 9 個進程，而用戶 2 啓動了一個進程，使用輪轉或相同優先級調度算法，那麼用戶 1 將得到 90 % 的 CPU 時間，而用戶 2 將之得到 10 % 的 CPU 時間。

爲了阻止這種情況的出現，一些系統在調度前會把進程的擁有者考慮在內。在這種模型下，每個用戶都會分配一些 CPU 時間，而調度程序會選擇進程並強制執行。因此如果兩個用戶每個都會有 50% 的 CPU 時間片保證，那麼無論一個用戶有多少個進程，都將獲得相同的 CPU 份額。

影響調度程序的指標是什麼

會有下面幾個因素決定調度程序的好壞

CPU 正在執行任務（即不處於空閒狀態）的時間百分比。

這是進程輪流執行的時間，也就是進程切換的時間

單位時間內完成進程的數量

這是從提交流程到獲得有用輸出所經過的時間。

從提交流程到完成流程所經過的時間。

什麼是 RR 調度算法

RR(round-robin) 調度算法主要針對分時系統，RR 的調度算法會把時間片以相同的部分並循環的分配給每個進程，RR 調度算法沒有優先級的概念。這種算法的實現比較簡單，而且每個線程都會佔有時間片，並不存在線程飢餓的問題。

內存管理篇

什麼是按需分頁

在操作系統中，進程是以頁爲單位加載到內存中的，按需分頁是一種虛擬內存的管理方式。在使用請求分頁的系統中，只有在嘗試訪問頁面所在的磁盤並且該頁面尚未在內存中時，也就發生了缺頁異常，操作系統纔會將磁盤頁面複製到內存中。

什麼是虛擬內存

虛擬內存是一種內存分配方案，是一項可以用來輔助內存分配的機制。我們知道，應用程序是按頁裝載進內存中的。但並不是所有的頁都會裝載到內存中，計算機中的硬件和軟件會將數據從 RAM 臨時傳輸到磁盤中來彌補內存的不足。如果沒有虛擬內存的話，一旦你將計算機內存填滿後，計算機會對你說

呃，不，對不起，您無法再加載任何應用程序，請關閉另一個應用程序以加載新的應用程序。對於虛擬內存，計算機可以執行操作是查看內存中最近未使用過的區域，然後將其複製到硬盤上。虛擬內存通過複製技術實現了 妹子，你快來看哥哥能裝這麼多程序 的資本。複製是自動進行的，你無法感知到它的存在。

虛擬內存的實現方式

虛擬內存中，允許將一個作業分多次調入內存。釆用連續分配方式時，會使相當一部分內存空間都處於暫時或永久的空閒狀態，造成內存資源的嚴重浪費，而且也無法從邏輯上擴大內存容量。因此，虛擬內存的實需要建立在離散分配的內存管理方式的基礎上。虛擬內存的實現有以下三種方式：

不管哪種方式，都需要有一定的硬件支持。一般需要的支持有以下幾個方面：

內存爲什麼要分段

內存是隨機訪問設備，對於內存來說，不需要從頭開始查找，只需要直接給出地址即可。內存的分段是從 8086 CPU 開始的，8086 的 CPU 還是 16 位的寄存器寬，16 位的寄存器可以存儲的數字範圍是 2 的 16 次方，即 64 KB，8086 的 CPU 還沒有 虛擬地址，只有物理地址，也就是說，如果兩個相同的程序編譯出來的地址相同，那麼這兩個程序是無法同時運行的。爲了解決這個問題，操作系統設計人員提出了讓 CPU 使用 段基址 + 段內偏移 的方式來訪問任意內存。這樣的好處是讓程序可以 重定位，這也是內存爲什麼要分段的第一個原因。

那麼什麼是重定位呢？

簡單來說就是將程序中的指令地址改爲另一個地址，地址處存儲的內容還是原來的。

CPU 採用段基址 + 段內偏移地址的形式訪問內存，就需要提供專門的寄存器，這些專門的寄存器就是 CS、DS、ES 等，如果你對寄存器不熟悉，可以看我的這一篇文章。

愛了愛了，這篇寄存器講的有點意思

也就是說，程序中需要用到哪塊內存，就需要先加載合適的段到段基址寄存器中，再給出相對於該段基址的段偏移地址即可。CPU 中的地址加法器會將這兩個地址進行合併，從地址總線送入內存。

8086 的 CPU 有 20 根地址總線，最大的尋址能力是 1MB，而段基址所在的寄存器寬度只有 16 位，最大爲你 64 KB 的尋址能力，64 KB 顯然不能滿足 1MB 的最大尋址範圍，所以就要把內存分段，每個段的最大尋址能力是 64KB，但是仍舊不能達到最大 1 MB 的尋址能力，所以這時候就需要 偏移地址的輔助，偏移地址也存入寄存器，同樣爲 64 KB 的尋址能力，這麼一看還是不能滿足 1MB 的尋址，所以 CPU 的設計者對地址單元動了手腳，將段基址左移 4 位，然後再和 16 位的段內偏移地址相加，就達到了 1MB 的尋址能力。所以內存分段的第二個目的就是能夠訪問到所有內存。

物理地址、邏輯地址、有效地址、線性地址、虛擬地址的區別

物理地址就是內存中真正的地址，它就相當於是你家的門牌號，你家就肯定有這個門牌號，具有唯一性。不管哪種地址，最終都會映射爲物理地址。

在實模式下，段基址 + 段內偏移經過地址加法器的處理，經過地址總線傳輸，最終也會轉換爲物理地址。

但是在保護模式下，段基址 + 段內偏移被稱爲線性地址，不過此時的段基址不能稱爲真正的地址，而是會被稱作爲一個選擇子的東西，選擇子就是個索引，相當於數組的下標，通過這個索引能夠在 GDT 中找到相應的段描述符，段描述符記錄了段的起始、段的大小等信息，這樣便得到了基地址。如果此時沒有開啓內存分頁功能，那麼這個線性地址可以直接當做物理地址來使用，直接訪問內存。如果開啓了分頁功能，那麼這個線性地址又多了一個名字，這個名字就是虛擬地址。

不論在實模式還是保護模式下，段內偏移地址都叫做有效地址。有效抵制也是邏輯地址。

線性地址可以看作是虛擬地址，虛擬地址不是真正的物理地址，但是虛擬地址會最終被映射爲物理地址。下面是虛擬地址 -> 物理地址的映射。

空閒內存管理的方式

操作系統在動態分配內存時（malloc，new），需要對空間內存進行管理。一般採用了兩種方式：位圖和空閒鏈表。

使用位圖進行管理

使用位圖方法時，內存可能被劃分爲小到幾個字或大到幾千字節的分配單元。每個分配單元對應於位圖中的一位，0 表示空閒， 1 表示佔用（或者相反）。一塊內存區域和其對應的位圖如下

å 圖 a 表示一段有 5 個進程和 3 個空閒區的內存，刻度爲內存分配單元，陰影區表示空閒（在位圖中用 0 表示）；圖 b 表示對應的位圖；圖 c 表示用鏈表表示同樣的信息

分配單元的大小是一個重要的設計因素，分配單位越小，位圖越大。然而，即使只有 4 字節的分配單元，32 位的內存也僅僅只需要位圖中的 1 位。32n 位的內存需要 n 位的位圖，所以 1 個位圖只佔用了 1/32 的內存。如果選擇更大的內存單元，位圖應該要更小。如果進程的大小不是分配單元的整數倍，那麼在最後一個分配單元中會有大量的內存被浪費。

位圖提供了一種簡單的方法在固定大小的內存中跟蹤內存的使用情況，因爲位圖的大小取決於內存和分配單元的大小。這種方法有一個問題，當決定爲把具有 k 個分配單元的進程放入內存時，內容管理器(memory manager) 必須搜索位圖，在位圖中找出能夠運行 k 個連續 0 位的串。在位圖中找出制定長度的連續 0 串是一個很耗時的操作，這是位圖的缺點。（可以簡單理解爲在雜亂無章的數組中，找出具有一大長串空閒的數組單元）

使用空閒鏈表

另一種記錄內存使用情況的方法是，維護一個記錄已分配內存段和空閒內存段的鏈表，段會包含進程或者是兩個進程的空閒區域。可用上面的圖 c 來表示內存的使用情況。鏈表中的每一項都可以代表一個 空閒區(H) 或者是進程(P)的起始標誌，長度和下一個鏈表項的位置。

在這個例子中，段鏈表(segment list)是按照地址排序的。這種方式的優點是，當進程終止或被交換時，更新列表很簡單。一個終止進程通常有兩個鄰居（除了內存的頂部和底部外）。相鄰的可能是進程也可能是空閒區，它們有四種組合方式。

當按照地址順序在鏈表中存放進程和空閒區時，有幾種算法可以爲創建的進程（或者從磁盤中換入的進程）分配內存。

頁面置換算法都有哪些

在地址映射過程中，如果在頁面中發現所要訪問的頁面不在內存中，那麼就會產生一條缺頁中斷。當發生缺頁中斷時，如果操作系統內存中沒有空閒頁面，那麼操作系統必須在內存選擇一個頁面將其移出內存，以便爲即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換算法。

下面我彙總的這些頁面置換算法比較齊全，只給出簡單介紹，算法具體的實現和原理讀者可以自行了解。

最好的算法是老化算法和 WSClock 算法。他們分別是基於 LRU 和工作集算法。他們都具有良好的性能並且能夠被有效的實現。還存在其他一些好的算法，但實際上這兩個可能是最重要的。

文件系統篇

提高文件系統性能的方式

訪問磁盤的效率要比內存慢很多，是時候又祭出這張圖了

所以磁盤優化是很有必要的，下面我們會討論幾種優化方式

高速緩存

最常用的減少磁盤訪問次數的技術是使用 塊高速緩存(block cache) 或者 緩衝區高速緩存(buffer cache)。高速緩存指的是一系列的塊，它們在邏輯上屬於磁盤，但實際上基於性能的考慮被保存在內存中。

管理高速緩存有不同的算法，常用的算法是：檢查全部的讀請求，查看在高速緩存中是否有所需要的塊。如果存在，可執行讀操作而無須訪問磁盤。如果檢查塊不再高速緩存中，那麼首先把它讀入高速緩存，再複製到所需的地方。之後，對同一個塊的請求都通過高速緩存來完成。

高速緩存的操作如下圖所示

由於在高速緩存中有許多塊，所以需要某種方法快速確定所需的塊是否存在。常用方法是將設備和磁盤地址進行散列操作。然後在散列表中查找結果。具有相同散列值的塊在一個鏈表中連接在一起（這個數據結構是不是很像 HashMap?），這樣就可以沿着衝突鏈查找其他塊。

如果高速緩存已滿，此時需要調入新的塊，則要把原來的某一塊調出高速緩存，如果要調出的塊在上次調入後已經被修改過，則需要把它寫回磁盤。這種情況與分頁非常相似。

塊提前讀

第二個明顯提高文件系統的性能是在需要用到塊之前試圖提前將其寫入高速緩存從而提高命中率。許多文件都是順序讀取。如果請求文件系統在某個文件中生成塊 k，文件系統執行相關操作並且在完成之後，會檢查高速緩存，以便確定塊 k + 1 是否已經在高速緩存。如果不在，文件系統會爲 k + 1 安排一個預讀取，因爲文件希望在用到該塊的時候能夠直接從高速緩存中讀取。

當然，塊提前讀取策略只適用於實際順序讀取的文件。對隨機訪問的文件，提前讀絲毫不起作用。甚至還會造成阻礙。

減少磁盤臂運動

高速緩存和塊提前讀並不是提高文件系統性能的唯一方法。另一種重要的技術是把有可能順序訪問的塊放在一起，當然最好是在同一個柱面上，從而減少磁盤臂的移動次數。當寫一個輸出文件時，文件系統就必須按照要求一次一次地分配磁盤塊。如果用位圖來記錄空閒塊，並且整個位圖在內存中，那麼選擇與前一塊最近的空閒塊是很容易的。如果用空閒表，並且鏈表的一部分存在磁盤上，要分配緊鄰的空閒塊就會困難很多。

不過，即使採用空閒表，也可以使用 塊簇 技術。即不用塊而用連續塊簇來跟蹤磁盤存儲區。如果一個扇區有 512 個字節，有可能系統採用 1 KB 的塊（2 個扇區），但卻按每 2 塊（4 個扇區）一個單位來分配磁盤存儲區。這和 2 KB 的磁盤塊並不相同，因爲在高速緩存中它仍然使用 1 KB 的塊，磁盤與內存數據之間傳送也是以 1 KB 進行，但在一個空閒的系統上順序讀取這些文件，尋道的次數可以減少一半，從而使文件系統的性能大大改善。若考慮旋轉定位則可以得到這類方法的變體。在分配塊時，系統儘量把一個文件中的連續塊存放在同一個柱面上。

在使用 inode 或任何類似 inode 的系統中，另一個性能瓶頸是，讀取一個很短的文件也需要兩次磁盤訪問：一次是訪問 inode，一次是訪問塊。通常情況下，inode 的放置如下圖所示

其中，全部 inode 放在靠近磁盤開始位置，所以 inode 和它所指向的塊之間的平均距離是柱面組的一半，這將會需要較長時間的尋道時間。

一個簡單的改進方法是，在磁盤中部而不是開始處存放 inode ，此時，在 inode 和第一個塊之間的尋道時間減爲原來的一半。另一種做法是：將磁盤分成多個柱面組，每個柱面組有自己的 inode，數據塊和空閒表，如上圖 b 所示。

當然，只有在磁盤中裝有磁盤臂的情況下，討論尋道時間和旋轉時間纔是有意義的。現在越來越多的電腦使用 固態硬盤(SSD)，對於這些硬盤，由於採用了和閃存同樣的製造技術，使得隨機訪問和順序訪問在傳輸速度上已經較爲相近，傳統硬盤的許多問題就消失了。但是也引發了新的問題。

磁盤碎片整理

在初始安裝操作系統後，文件就會被不斷的創建和清除，於是磁盤會產生很多的碎片，在創建一個文件時，它使用的塊會散佈在整個磁盤上，降低性能。刪除文件後，回收磁盤塊，可能會造成空穴。

磁盤性能可以通過如下方式恢復：移動文件使它們相互挨着，並把所有的至少是大部分的空閒空間放在一個或多個大的連續區域內。Windows 有一個程序 defrag 就是做這個事兒的。Windows 用戶會經常使用它，SSD 除外。

磁盤碎片整理程序會在讓文件系統上很好地運行。Linux 文件系統（特別是 ext2 和 ext3）由於其選擇磁盤塊的方式，在磁盤碎片整理上一般不會像 Windows 一樣困難，因此很少需要手動的磁盤碎片整理。而且，固態硬盤並不受磁盤碎片的影響，事實上，在固態硬盤上做磁盤碎片整理反倒是多此一舉，不僅沒有提高性能，反而磨損了固態硬盤。所以碎片整理只會縮短固態硬盤的壽命。

磁盤臂調度算法

一般情況下，影響磁盤快讀寫的時間由下面幾個因素決定

這三種時間參數也是磁盤尋道的過程。一般情況下，尋道時間對總時間的影響最大，所以，有效的降低尋道時間能夠提高磁盤的讀取速度。

如果磁盤驅動程序每次接收一個請求並按照接收順序完成請求，這種處理方式也就是 先來先服務(First-Come, First-served, FCFS) ，這種方式很難優化尋道時間。因爲每次都會按照順序處理，不管順序如何，有可能這次讀完後需要等待一個磁盤旋轉一週才能繼續讀取，而其他柱面能夠馬上進行讀取，這種情況下每次請求也會排隊。

通常情況下，磁盤在進行尋道時，其他進程會產生其他的磁盤請求。磁盤驅動程序會維護一張表，表中會記錄着柱面號當作索引，每個柱面未完成的請求會形成鏈表，鏈表頭存放在表的相應表項中。

一種對先來先服務的算法改良的方案是使用 最短路徑優先(SSF) 算法，下面描述了這個算法。

假如我們在對磁道 6 號進行尋址時，同時發生了對 11 , 2 , 4, 14, 8, 15, 3 的請求，如果採用先來先服務的原則，如下圖所示

我們可以計算一下磁盤臂所跨越的磁盤數量爲 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51，相當於是跨越了 51 次盤面，如果使用最短路徑優先，我們來計算一下跨越的盤面

跨越的磁盤數量爲 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ，相比 51 足足省了兩倍的時間。

但是，最短路徑優先的算法也不是完美無缺的，這種算法照樣存在問題，那就是優先級 問題，

這裏有一個原型可以參考就是我們日常生活中的電梯，電梯使用一種電梯算法(elevator algorithm) 來進行調度，從而滿足協調效率和公平性這兩個相互衝突的目標。電梯一般會保持向一個方向移動，直到在那個方向上沒有請求爲止，然後改變方向。

電梯算法需要維護一個二進制位，也就是當前的方向位：UP(向上)或者是 DOWN(向下)。當一個請求處理完成後，磁盤或電梯的驅動程序會檢查該位，如果此位是 UP 位，磁盤臂或者電梯倉移到下一個更高跌未完成的請求。如果高位沒有未完成的請求，則取相反方向。當方向位是 DOWN時，同時存在一個低位的請求，磁盤臂會轉向該點。如果不存在的話，那麼它只是停止並等待。

我們舉個例子來描述一下電梯算法，比如各個柱面得到服務的順序是 4，7，10，14，9，6，3，1 ，那麼它的流程圖如下

所以電梯算法需要跨越的盤面數量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22

電梯算法通常情況下不如 SSF 算法。

一些磁盤控制器爲軟件提供了一種檢查磁頭下方當前扇區號的方法，使用這樣的控制器，能夠進行另一種優化。如果對一個相同的柱面有兩個或者多個請求正等待處理，驅動程序可以發出請求讀寫下一次要通過磁頭的扇區。

這裏需要注意一點，當一個柱面有多條磁道時，相繼的請求可能針對不同的磁道，這種選擇沒有代價，因爲選擇磁頭不需要移動磁盤臂也沒有旋轉延遲。

對於磁盤來說，最影響性能的就是尋道時間和旋轉延遲，所以一次只讀取一個或兩個扇區的效率是非常低的。出於這個原因，許多磁盤控制器總是讀出多個扇區並進行高速緩存，即使只請求一個扇區時也是這樣。一般情況下讀取一個扇區的同時會讀取該扇區所在的磁道或者是所有剩餘的扇區被讀出，讀出扇區的數量取決於控制器的高速緩存中有多少可用的空間。

磁盤控制器的高速緩存和操作系統的高速緩存有一些不同，磁盤控制器的高速緩存用於緩存沒有實際被請求的塊，而操作系統維護的高速緩存由顯示地讀出的塊組成，並且操作系統會認爲這些塊在近期仍然會頻繁使用。

當同一個控制器上有多個驅動器時，操作系統應該爲每個驅動器都單獨的維護一個未完成的請求表。一旦有某個驅動器閒置時，就應該發出一個尋道請求來將磁盤臂移到下一個被請求的柱面。如果下一個尋道請求到來時恰好沒有磁盤臂處於正確的位置，那麼驅動程序會在剛剛完成傳輸的驅動器上發出一個新的尋道命令並等待，等待下一次中斷到來時檢查哪個驅動器處於閒置狀態。

RAID 的不同級別

RAID 稱爲 磁盤冗餘陣列，簡稱 磁盤陣列。利用虛擬化技術把多個硬盤結合在一起，成爲一個或多個磁盤陣列組，目的是提升性能或數據冗餘。

RAID 有不同的級別

IO 篇

操作系統中的時鐘是什麼

時鐘(Clocks) 也被稱爲定時器(timers)，時鐘 / 定時器對任何程序系統來說都是必不可少的。時鐘負責維護時間、防止一個進程長期佔用 CPU 時間等其他功能。時鐘軟件(clock software) 也是一種設備驅動的方式。下面我們就來對時鐘進行介紹，一般都是先討論硬件再介紹軟件，採用由下到上的方式，也是告訴你，底層是最重要的。

時鐘硬件

在計算機中有兩種類型的時鐘，這些時鐘與現實生活中使用的時鐘完全不一樣。

這種時鐘稱爲可編程時鐘 ，可編程時鐘有兩種模式，一種是 一鍵式(one-shot mode)，當時鍾啓動時，會把存儲器中的值複製到計數器中，然後，每次晶體的振盪器的脈衝都會使計數器 -1。當計數器變爲 0 時，會產生一箇中斷，並停止工作，直到軟件再一次顯示啓動。還有一種模式是 方波(square-wave mode) 模式，在這種模式下，當計數器變爲 0 併產生中斷後，存儲寄存器的值會自動複製到計數器中，這種週期性的中斷稱爲一個時鐘週期。

設備控制器的主要功能

設備控制器是一個可編址的設備，當它僅控制一個設備時，它只有一個唯一的設備地址；如果設備控制器控制多個可連接設備時，則應含有多個設備地址，並使每一個設備地址對應一個設備。

設備控制器主要分爲兩種：字符設備和塊設備

設備控制器的主要功能有下面這些

中斷處理過程

中斷處理方案有很多種，下面是 《ARM System Developer’s Guide

Designing and Optimizing System Software》列出來的一些方案

下面是一些通用的中斷處理程序的步驟，不同的操作系統實現細節不一樣

上面我們羅列了一些大致的中斷步驟，不同性質的操作系統和中斷處理程序能夠處理的中斷步驟和細節也不盡相同，下面是一個嵌套中斷的具體運行步驟

什麼是設備驅動程序

在計算機中，設備驅動程序是一種計算機程序，它能夠控制或者操作連接到計算機的特定設備。驅動程序提供了與硬件進行交互的軟件接口，使操作系統和其他計算機程序能夠訪問特定設備，不用需要了解其硬件的具體構造。

什麼是 DMA

DMA 的中文名稱是直接內存訪問，它意味着 CPU 授予 I/O 模塊權限在不涉及 CPU 的情況下讀取或寫入內存。也就是 DMA 可以不需要 CPU 的參與。這個過程由稱爲 DMA 控制器（DMAC）的芯片管理。由於 DMA 設備可以直接在內存之間傳輸數據，而不是使用 CPU 作爲中介，因此可以緩解總線上的擁塞。DMA 通過允許 CPU 執行任務，同時 DMA 系統通過系統和內存總線傳輸數據來提高系統併發性。

直接內存訪問的特點

DMA 方式有如下特點：

DMA 方式和中斷驅動控制方式相比，減少了 CPU 對 I/O 操作的干預，進一步提高了 CPU 與 I/O 設備的並行操作程度。

DMA 方式的線路簡單、價格低廉，適合高速設備與主存之間的成批數據傳送，小型、微型機中的快速設備均採用這種方式，但其功能較差，不能滿足複雜的 I/O 要求。

死鎖篇

什麼是殭屍進程

殭屍進程是已完成且處於終止狀態，但在進程表中卻仍然存在的進程。殭屍進程通常發生在父子關係的進程中，由於父進程仍需要讀取其子進程的退出狀態所造成的。

死鎖產生的原因

死鎖產生的原因大致有兩個：資源競爭和程序執行順序不當

死鎖產生的必要條件

資源死鎖可能出現的情況主要有

死鎖的恢復方式

所以針對檢測出來的死鎖，我們要對其進行恢復，下面我們會探討幾種死鎖的恢復方式

通過搶佔進行恢復

在某些情況下，可能會臨時將某個資源從它的持有者轉移到另一個進程。比如在不通知原進程的情況下，將某個資源從進程中強制取走給其他進程使用，使用完後又送回。這種恢復方式一般比較困難而且有些簡單粗暴，並不可取。

通過回滾進行恢復

如果系統設計者和機器操作員知道有可能發生死鎖，那麼就可以定期檢查流程。進程的檢測點意味着進程的狀態可以被寫入到文件以便後面進行恢復。檢測點不僅包含存儲映像(memory image)，還包含資源狀態(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測點，而是每出現一個檢測點都要把它寫入到文件中，這樣當進程執行時，就會有一系列的檢查點文件被累積起來。

爲了進行恢復，要從上一個較早的檢查點上開始，這樣所需要資源的進程會回滾到上一個時間點，在這個時間點上，死鎖進程還沒有獲取所需要的資源，可以在此時對其進行資源分配。

殺死進程恢復

最簡單有效的解決方案是直接殺死一個死鎖進程。但是殺死一個進程可能照樣行不通，這時候就需要殺死別的資源進行恢復。

另外一種方式是選擇一個環外的進程作爲犧牲品來釋放進程資源。

如何破壞死鎖

和死鎖產生的必要條件一樣，如果要破壞死鎖，也是從下面四種方式進行破壞。

破壞互斥條件

我們首先考慮的就是破壞互斥使用條件。如果資源不被一個進程獨佔，那麼死鎖肯定不會產生。如果兩個打印機同時使用一個資源會造成混亂，打印機的解決方式是使用 假脫機打印機(spooling printer) ，這項技術可以允許多個進程同時產生輸出，在這種模型中，實際請求打印機的唯一進程是打印機守護進程，也稱爲後臺進程。後臺進程不會請求其他資源。我們可以消除打印機的死鎖。

後臺進程通常被編寫爲能夠輸出完整的文件後才能打印，假如兩個進程都佔用了假脫機空間的一半，而這兩個進程都沒有完成全部的輸出，就會導致死鎖。

因此，儘量做到儘可能少的進程可以請求資源。

破壞保持等待的條件

第二種方式是如果我們能阻止持有資源的進程請求其他資源，我們就能夠消除死鎖。一種實現方式是讓所有的進程開始執行前請求全部的資源。如果所需的資源可用，進程會完成資源的分配並運行到結束。如果有任何一個資源處於頻繁分配的情況，那麼沒有分配到資源的進程就會等待。

很多進程無法在執行完成前就知道到底需要多少資源，如果知道的話，就可以使用銀行家算法；還有一個問題是這樣無法合理有效利用資源。

還有一種方式是進程在請求其他資源時，先釋放所佔用的資源，然後再嘗試一次獲取全部的資源。

破壞不可搶佔條件

破壞不可搶佔條件也是可以的。可以通過虛擬化的方式來避免這種情況。

破壞循環等待條件

現在就剩最後一個條件了，循環等待條件可以通過多種方法來破壞。一種方式是制定一個標準，一個進程在任何時候只能使用一種資源。如果需要另外一種資源，必須釋放當前資源。

另一種方式是將所有的資源統一編號，如下圖所示

進程可以在任何時間提出請求，但是所有的請求都必須按照資源的順序提出。如果按照此分配規則的話，那麼資源分配之間不會出現環。

死鎖類型

兩階段加鎖

雖然很多情況下死鎖的避免和預防都能處理，但是效果並不好。隨着時間的推移，提出了很多優秀的算法用來處理死鎖。例如在數據庫系統中，一個經常發生的操作是請求鎖住一些記錄，然後更新所有鎖定的記錄。當同時有多個進程運行時，就會有死鎖的風險。

一種解決方式是使用 兩階段提交(two-phase locking)。顧名思義分爲兩個階段，一階段是進程嘗試一次鎖定它需要的所有記錄。如果成功後，纔會開始第二階段，第二階段是執行更新並釋放鎖。第一階段並不做真正有意義的工作。

如果在第一階段某個進程所需要的記錄已經被加鎖，那麼該進程會釋放所有鎖定的記錄並重新開始第一階段。從某種意義上來說，這種方法類似於預先請求所有必需的資源或者是在進行一些不可逆的操作之前請求所有的資源。

不過在一般的應用場景中，兩階段加鎖的策略並不通用。如果一個進程缺少資源就會半途中斷並重新開始的方式是不可接受的。

通信死鎖

我們上面一直討論的是資源死鎖，資源死鎖是一種死鎖類型，但並不是唯一類型，還有通信死鎖，也就是兩個或多個進程在發送消息時出現的死鎖。進程 A 給進程 B 發了一條消息，然後進程 A 阻塞直到進程 B 返回響應。假設請求消息丟失了，那麼進程 A 在一直等着回覆，進程 B 也會阻塞等待請求消息到來，這時候就產生死鎖。

儘管會產生死鎖，但是這並不是一個資源死鎖，因爲 A 並沒有佔據 B 的資源。事實上，通信死鎖並沒有完全可見的資源。根據死鎖的定義來說：每個進程因爲等待其他進程引起的事件而產生阻塞，這就是一種死鎖。相較於最常見的通信死鎖，我們把上面這種情況稱爲通信死鎖(communication deadlock)。

通信死鎖不能通過調度的方式來避免，但是可以使用通信中一個非常重要的概念來避免：超時(timeout)。在通信過程中，只要一個信息被髮出後，發送者就會啓動一個定時器，定時器會記錄消息的超時時間，如果超時時間到了但是消息還沒有返回，就會認爲消息已經丟失並重新發送，通過這種方式，可以避免通信死鎖。

但是並非所有網絡通信發生的死鎖都是通信死鎖，也存在資源死鎖，下面就是一個典型的資源死鎖。

當一個數據包從主機進入路由器時，會被放入一個緩衝區，然後再傳輸到另外一個路由器，再到另一個，以此類推直到目的地。緩衝區都是資源並且數量有限。如下圖所示，每個路由器都有 10 個緩衝區（實際上有很多）。

假如路由器 A 的所有數據需要發送到 B ，B 的所有數據包需要發送到 D，然後 D 的所有數據包需要發送到 A 。沒有數據包可以移動，因爲在另一端沒有緩衝區可用，這就是一個典型的資源死鎖。

活鎖

某些情況下，當進程意識到它不能獲取所需要的下一個鎖時，就會嘗試禮貌的釋放已經獲得的鎖，然後等待非常短的時間再次嘗試獲取。可以想像一下這個場景：當兩個人在狹路相逢的時候，都想給對方讓路，相同的步調會導致雙方都無法前進。

現在假想有一對並行的進程用到了兩個資源。它們分別嘗試獲取另一個鎖失敗後，兩個進程都會釋放自己持有的鎖，再次進行嘗試，這個過程會一直進行重複。很明顯，這個過程中沒有進程阻塞，但是進程仍然不會向下執行，這種狀況我們稱之爲 活鎖(livelock)。

飢餓

與死鎖和活鎖的一個非常相似的問題是 飢餓(starvvation)。想象一下你什麼時候會餓？一段時間不喫東西是不是會餓？對於進程來講，最重要的就是資源，如果一段時間沒有獲得資源，那麼進程會產生飢餓，這些進程會永遠得不到服務。

我們假設打印機的分配方案是每次都會分配給最小文件的進程，那麼要打印大文件的進程會永遠得不到服務，導致進程飢餓，進程會無限制的推後，雖然它沒有阻塞。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/lKDwAY-Wfg0ozLS82Glrpg

猜你喜歡