2.5w字 + 36 張圖爆肝操作系統(tǒng)面試題

大家好，我是 cxuan，我之前匯總了一下關(guān)于操作系統(tǒng)的面試題，最近又重新翻閱了一下發(fā)現(xiàn)不是很全，現(xiàn)在也到了面試季了，所以我又花了一周的時間修訂整理了一下這份面試題，這份面試題可以吊打市面上所有的操作系統(tǒng)面試題了，不是我說，是因為我系統(tǒng)查過，如果有不相信的大佬，歡迎狠狠的打我臉。

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

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

操作系統(tǒng)簡介篇

解釋一下什么是操作系統(tǒng)

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

通常情況下，計算機上會運行著許多應(yīng)用程序，它們都需要對內(nèi)存和 CPU 進行交互，操作系統(tǒng)的目的就是為了保證這些訪問和交互能夠準(zhǔn)確無誤的進行。

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

一般來說，現(xiàn)代操作系統(tǒng)主要提供下面幾種功能

進程管理: 進程管理的主要作用就是任務(wù)調(diào)度，在單核處理器下，操作系統(tǒng)會為每個進程分配一個任務(wù)，進程管理的工作十分簡單；而在多核處理器下，操作系統(tǒng)除了要為進程分配任務(wù)外，還要解決處理器的調(diào)度、分配和回收等問題

內(nèi)存管理：內(nèi)存管理主要是操作系統(tǒng)負責(zé)管理內(nèi)存的分配、回收，在進程需要時分配內(nèi)存以及在進程完成時回收內(nèi)存，協(xié)調(diào)內(nèi)存資源，通過合理的頁面置換算法進行頁面的換入換出

設(shè)備管理：根據(jù)確定的設(shè)備分配原則對設(shè)備進行分配，使設(shè)備與主機能夠并行工作，為用戶提供良好的設(shè)備使用界面。

文件管理：有效地管理文件的存儲空間，合理地組織和管理文件系統(tǒng)，為文件訪問和文件保護提供更有效的方法及手段。

提供用戶接口：操作系統(tǒng)提供了訪問應(yīng)用程序和硬件的接口，使用戶能夠通過應(yīng)用程序發(fā)起系統(tǒng)調(diào)用從而操縱硬件，實現(xiàn)想要的功能。

軟件訪問硬件的幾種方式

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

硬件在 I/O 上大致分為并行和串行，同時也對應(yīng)串行接口和并行接口。

隨著計算機技術(shù)的發(fā)展，I/O 控制方式也在不斷發(fā)展。選擇和衡量 I/O 控制方式有如下三條原則

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

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

（3） 能充分發(fā)揮硬件資源的能力，使 I/O 設(shè)備盡可能忙，而 CPU 等待時間盡可能少。

根據(jù)以上控制原則，I/O 操作可以分為四類

直接訪問：直接訪問由用戶進程直接控制主存或 CPU 和外圍設(shè)備之間的信息傳送。直接程序控制方式又稱為忙/等待方式。

中斷驅(qū)動：為了減少程序直接控制方式下 CPU 的等待時間以及提高系統(tǒng)的并行程度，系統(tǒng)引入了中斷機制。中斷機制引入后，外圍設(shè)備僅當(dāng)操作正常結(jié)束或異常結(jié)束時才向 CPU 發(fā)出中斷請求。在 I/O 設(shè)備輸入每個數(shù)據(jù)的過程中，由于無需 CPU 的干預(yù)，一定程度上實現(xiàn)了 CPU 與 I/O 設(shè)備的并行工作。

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

DMA 直接內(nèi)存訪問：為了進一步減少 CPU 對 I/O 操作的干預(yù)，防止因并行操作設(shè)備過多使 CPU 來不及處理或因速度不匹配而造成的數(shù)據(jù)丟失現(xiàn)象，引入了 DMA 控制方式。

通道控制方式：通道，獨立于 CPU 的專門負責(zé)輸入輸出控制的處理機，它控制設(shè)備與內(nèi)存直接進行數(shù)據(jù)交換。有自己的通道指令，這些指令由 CPU 啟動，并在操作結(jié)束時向 CPU 發(fā)出中斷信號。

解釋一下操作系統(tǒng)的主要目的是什么

操作系統(tǒng)是一種軟件，它的主要目的有三種

管理計算機資源，這些資源包括 CPU、內(nèi)存、磁盤驅(qū)動器、打印機等。

提供一種圖形界面，就像我們前面描述的那樣，它提供了用戶和計算機之間的橋梁。

為其他軟件提供服務(wù)，操作系統(tǒng)與軟件進行交互，以便為其分配運行所需的任何必要資源。

操作系統(tǒng)的種類有哪些

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

為什么 Linux 系統(tǒng)下的應(yīng)用程序不能直接在 Windows 下運行

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

其中一點是因為 Linux 系統(tǒng)和 Windows 系統(tǒng)的格式不同，格式就是協(xié)議，就是在固定位置有意義的數(shù)據(jù)。Linux 下的可執(zhí)行程序文件格式是 elf，可以使用 readelf 命令查看 elf 文件頭。

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

還有一點是因為 Linux 系統(tǒng)和 Windows 系統(tǒng)的 API 不同，這個 API 指的就是操作系統(tǒng)的 API，Linux 中的 API 被稱為系統(tǒng)調(diào)用，是通過 int 0x80 這個軟中斷實現(xiàn)的。而 Windows 中的 API 是放在動態(tài)鏈接庫文件中的，也就是 Windows 開發(fā)人員所說的 DLL ，這是一個庫，里面包含代碼和數(shù)據(jù)。Linux 中的可執(zhí)行程序獲得系統(tǒng)資源的方法和 Windows 不一樣，所以顯然是不能在 Windows 中運行的。

 

操作系統(tǒng)結(jié)構(gòu)

單體系統(tǒng)

在大多數(shù)系統(tǒng)中，整個系統(tǒng)在內(nèi)核態(tài)以單一程序的方式運行。整個操作系統(tǒng)是以程序集合來編寫的，鏈接在一塊形成一個大的二進制可執(zhí)行程序，這種系統(tǒng)稱為單體系統(tǒng)。

在單體系統(tǒng)中構(gòu)造實際目標(biāo)程序時，會首先編譯所有單個過程（或包含這些過程的文件），然后使用系統(tǒng)鏈接器將它們?nèi)拷壎ǖ揭粋€可執(zhí)行文件中

在單體系統(tǒng)中，對于每個系統(tǒng)調(diào)用都會有一個服務(wù)程序來保障和運行。需要一組實用程序來彌補服務(wù)程序需要的功能，例如從用戶程序中獲取數(shù)據(jù)。可將各種過程劃分為一個三層模型

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

 

分層系統(tǒng)

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

 

微內(nèi)核

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

MINIX 3 是微內(nèi)核的代表作，它的具體結(jié)構(gòu)如下

在內(nèi)核的外部，系統(tǒng)的構(gòu)造有三層，它們都在用戶態(tài)下運行，最底層是設(shè)備驅(qū)動器。由于它們都在用戶態(tài)下運行，所以不能物理的訪問 I/O 端口空間，也不能直接發(fā)出 I/O 命令。

相反，為了能夠?qū)?I/O 設(shè)備編程，驅(qū)動器構(gòu)建一個結(jié)構(gòu)，指明哪個參數(shù)值寫到哪個 I/O 端口，并聲稱一個內(nèi)核調(diào)用，這樣就完成了一次調(diào)用過程。

客戶-服務(wù)器模式

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

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

客戶通過發(fā)送消息與服務(wù)器通信，客戶端并不需要知道這些消息是在本地機器上處理，還是通過網(wǎng)絡(luò)被送到遠程機器上處理。對于客戶端而言，這兩種情形是一樣的：都是發(fā)送請求并得到回應(yīng)。

為什么稱為陷入內(nèi)核

如果把軟件結(jié)構(gòu)進行分層說明的話，應(yīng)該是這個樣子的，最外層是應(yīng)用程序，里面是操作系統(tǒng)內(nèi)核。

 

應(yīng)用程序處于特權(quán)級 3，操作系統(tǒng)內(nèi)核處于特權(quán)級 0 。如果用戶程序想要訪問操作系統(tǒng)資源時，會發(fā)起系統(tǒng)調(diào)用，陷入內(nèi)核，這樣 CPU 就進入了內(nèi)核態(tài)，執(zhí)行內(nèi)核代碼。至于為什么是陷入，我們看圖，內(nèi)核是一個凹陷的構(gòu)造，有陷下去的感覺，所以稱為陷入。

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

用戶態(tài)和內(nèi)核態(tài)是操作系統(tǒng)的兩種運行狀態(tài)。

內(nèi)核態(tài)：處于內(nèi)核態(tài)的 CPU 可以訪問任意的數(shù)據(jù)，包括外圍設(shè)備，比如網(wǎng)卡、硬盤等，處于內(nèi)核態(tài)的 CPU 可以從一個程序切換到另外一個程序，并且占用 CPU 不會發(fā)生搶占情況，一般處于特權(quán)級 0 的狀態(tài)我們稱之為內(nèi)核態(tài)。

用戶態(tài)：處于用戶態(tài)的 CPU 只能受限的訪問內(nèi)存，并且不允許訪問外圍設(shè)備，用戶態(tài)下的 CPU 不允許獨占，也就是說 CPU 能夠被其他程序獲取。

那么為什么要有用戶態(tài)和內(nèi)核態(tài)呢？

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

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

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

一般用戶態(tài) -> 內(nèi)核態(tài)的轉(zhuǎn)換我們都稱之為 trap 進內(nèi)核，也被稱之為 陷阱指令(trap instruction)。

他們的工作流程如下：

首先用戶程序會調(diào)用 glibc 庫，glibc 是一個標(biāo)準(zhǔn)庫，同時也是一套核心庫，庫中定義了很多關(guān)鍵 API。

glibc 庫知道針對不同體系結(jié)構(gòu)調(diào)用系統(tǒng)調(diào)用的正確方法，它會根據(jù)體系結(jié)構(gòu)應(yīng)用程序的二進制接口設(shè)置用戶進程傳遞的參數(shù)，來準(zhǔn)備系統(tǒng)調(diào)用。

然后，glibc 庫調(diào)用軟件中斷指令(SWI) ，這個指令通過更新 CPSR 寄存器將模式改為超級用戶模式，然后跳轉(zhuǎn)到地址 0x08 處。

到目前為止，整個過程仍處于用戶態(tài)下，在執(zhí)行 SWI 指令后，允許進程執(zhí)行內(nèi)核代碼，MMU 現(xiàn)在允許內(nèi)核虛擬內(nèi)存訪問

從地址 0x08 開始，進程執(zhí)行加載并跳轉(zhuǎn)到中斷處理程序，這個程序就是 ARM 中的 vector_swi()。

在 vector_swi() 處，從 SWI 指令中提取系統(tǒng)調(diào)用號 SCNO，然后使用 SCNO 作為系統(tǒng)調(diào)用表 sys_call_table 的索引，調(diào)轉(zhuǎn)到系統(tǒng)調(diào)用函數(shù)。

執(zhí)行系統(tǒng)調(diào)用完成后，將還原用戶模式寄存器，然后再以用戶模式執(zhí)行。

什么是內(nèi)核

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

這里還需要了解一下什么是 boot loader。

boot loader 又被稱為引導(dǎo)加載程序，能夠?qū)⒂嬎銠C的操作系統(tǒng)放入內(nèi)存中。在電源通電或者計算機重啟時，BIOS 會執(zhí)行一些初始測試，然后將控制權(quán)轉(zhuǎn)移到引導(dǎo)加載程序所在的主引導(dǎo)記錄(MBR) 。

 

什么是實時系統(tǒng)

實時操作系統(tǒng)對時間做出了嚴(yán)格的要求，實時操作系統(tǒng)分為兩種：硬實時和軟實時

硬實時操作系統(tǒng)規(guī)定某個動作必須在規(guī)定的時刻內(nèi)完成或發(fā)生，比如汽車生產(chǎn)車間，焊接機器必須在某一時刻內(nèi)完成焊接，焊接的太早或者太晚都會對汽車造成永久性傷害。

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

你可以簡單理解硬實時和軟實時的兩個指標(biāo)：是否在時刻內(nèi)必須完成以及是否造成嚴(yán)重損害。

Linux 操作系統(tǒng)的啟動過程

當(dāng)計算機電源通電后，BIOS會進行開機自檢(Power-On-Self-Test, POST)，對硬件進行檢測和初始化。因為操作系統(tǒng)的啟動會使用到磁盤、屏幕、鍵盤、鼠標(biāo)等設(shè)備。下一步，磁盤中的第一個分區(qū)，也被稱為 MBR(Master Boot Record) 主引導(dǎo)記錄，被讀入到一個固定的內(nèi)存區(qū)域并執(zhí)行。這個分區(qū)中有一個非常小的，只有 512 字節(jié)的程序。程序從磁盤中調(diào)入 boot 獨立程序，boot 程序?qū)⒆陨韽?fù)制到高位地址的內(nèi)存從而為操作系統(tǒng)釋放低位地址的內(nèi)存。

復(fù)制完成后，boot 程序讀取啟動設(shè)備的根目錄。boot 程序要理解文件系統(tǒng)和目錄格式。

然后 boot 程序被調(diào)入內(nèi)核，把控制權(quán)移交給內(nèi)核。直到這里，boot 完成了它的工作。系統(tǒng)內(nèi)核開始運行。

內(nèi)核啟動代碼是使用匯編語言完成的，主要包括創(chuàng)建內(nèi)核堆棧、識別 CPU 類型、計算內(nèi)存、禁用中斷、啟動內(nèi)存管理單元等，然后調(diào)用 C 語言的 main 函數(shù)執(zhí)行操作系統(tǒng)部分。

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

然后操作系統(tǒng)會進行自動配置，檢測設(shè)備，加載配置文件，被檢測設(shè)備如果做出響應(yīng)，就會被添加到已鏈接的設(shè)備表中，如果沒有相應(yīng)，就歸為未連接直接忽略。

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

init 進程會檢測它的標(biāo)志以確定它是否為單用戶還是多用戶服務(wù)。在前一種情況中，它會調(diào)用 fork 函數(shù)創(chuàng)建一個 shell 進程，并且等待這個進程結(jié)束。后一種情況調(diào)用 fork 函數(shù)創(chuàng)建一個運行系統(tǒng)初始化的 shell 腳本（即 /etc/rc）的進程，這個進程可以進行文件系統(tǒng)一致性檢測、掛載文件系統(tǒng)、開啟守護進程等。

然后 /etc/rc 這個進程會從 /etc/ttys 中讀取數(shù)據(jù)，/etc/ttys 列出了所有的終端和屬性。對于每一個啟用的終端，這個進程調(diào)用 fork 函數(shù)創(chuàng)建一個自身的副本，進行內(nèi)部處理并運行一個名為 getty 的程序。

getty 程序會在終端上輸入

login:

等待用戶輸入用戶名，在輸入用戶名后，getty 程序結(jié)束，登陸程序 /bin/login 開始運行。

login 程序需要輸入密碼，并與保存在 /etc/passwd 中的密碼進行對比，如果輸入正確，login 程序以用戶 shell 程序替換自身，等待第一個命令。如果不正確，login 程序要求輸入另一個用戶名。

整個系統(tǒng)啟動過程如下

 

進程和線程篇

多處理系統(tǒng)的優(yōu)勢

隨著處理器的不斷增加，我們的計算機系統(tǒng)由單機系統(tǒng)變?yōu)榱硕嗵幚硐到y(tǒng)，多處理系統(tǒng)的吞吐量比較高，多處理系統(tǒng)擁有多個并行的處理器，這些處理器共享時鐘、內(nèi)存、總線、外圍設(shè)備等。

多處理系統(tǒng)由于可以共享資源，因此可以開源節(jié)流，省錢。整個系統(tǒng)的可靠性也隨之提高。

什么是進程和進程表

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

操作系統(tǒng)負責(zé)管理所有正在運行的進程，操作系統(tǒng)會為每個進程分配特定的時間來占用 CPU，操作系統(tǒng)還會為每個進程分配特定的資源。

操作系統(tǒng)為了跟蹤每個進程的活動狀態(tài)，維護了一個進程表。在進程表的內(nèi)部，列出了每個進程的狀態(tài)以及每個進程使用的資源等。

什么是線程，線程和進程的區(qū)別

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

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

下面是線程和進程持有資源的區(qū)別

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

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

什么是上下文切換

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

使用多線程的好處是什么

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

能夠提高對用戶的響應(yīng)順序

在流程中的資源共享

比較經(jīng)濟適用

能夠?qū)Χ嗑€程架構(gòu)有深入的理解

進程終止的方式

進程的終止

進程在創(chuàng)建之后，它就開始運行并做完成任務(wù)。然而，沒有什么事兒是永不停歇的，包括進程也一樣。進程早晚會發(fā)生終止，但是通常是由于以下情況觸發(fā)的

正常退出(自愿的)

錯誤退出(自愿的)

嚴(yán)重錯誤(非自愿的)

被其他進程殺死(非自愿的)

 

正常退出

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

 

錯誤退出

進程發(fā)生終止的第二個原因是發(fā)現(xiàn)嚴(yán)重錯誤，例如，如果用戶執(zhí)行如下命令

cc foo.c    

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

嚴(yán)重錯誤

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

被其他進程殺死

第四個終止進程的原因是，某個進程執(zhí)行系統(tǒng)調(diào)用告訴操作系統(tǒng)殺死某個進程。在 UNIX 中，這個系統(tǒng)調(diào)用是 kill。在 Win32 中對應(yīng)的函數(shù)是 TerminateProcess（注意不是系統(tǒng)調(diào)用）。

進程間的通信方式

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

競態(tài)條件：即兩個或多個線程同時對一共享數(shù)據(jù)進行修改，從而影響程序運行的正確性時，這種就被稱為競態(tài)條件(race condition)。

臨界區(qū)：不僅共享資源會造成競態(tài)條件，事實上共享文件、共享內(nèi)存也會造成競態(tài)條件、那么該如何避免呢？或許一句話可以概括說明：禁止一個或多個進程在同一時刻對共享資源（包括共享內(nèi)存、共享文件等）進行讀寫。換句話說，我們需要一種 互斥(mutual exclusion) 條件，這也就是說，如果一個進程在某種方式下使用共享變量和文件的話，除該進程之外的其他進程就禁止做這種事（訪問統(tǒng)一資源）。

一個好的解決方案，應(yīng)該包含下面四種條件

任何時候兩個進程不能同時處于臨界區(qū)

不應(yīng)對 CPU 的速度和數(shù)量做任何假設(shè)

位于臨界區(qū)外的進程不得阻塞其他進程

不能使任何進程無限等待進入臨界區(qū)

忙等互斥：當(dāng)一個進程在對資源進行修改時，其他進程必須進行等待，進程之間要具有互斥性，我們討論的解決方案其實都是基于忙等互斥提出的。

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

消息傳遞：消息傳遞是進程間實現(xiàn)通信和同步等待的機制，使用消息傳遞，進程間的交流不需要共享變量，直接就可以進行通信；消息傳遞分為發(fā)送方和接收方

先進先出隊列：先進先出隊列指的是兩個不相關(guān)聯(lián)進程間的通信，兩個進程之間可以彼此相互進程通信，這是一種全雙工通信方式

管道：管道用于兩個相關(guān)進程之間的通信，這是一種半雙工的通信方式，如果需要全雙工，需要另外一個管道。

直接通信：在這種進程通信的方式中，進程與進程之間只存在一條鏈接，進程間要明確通信雙方的命名。

間接通信：間接通信是通信雙方不會直接建立連接，而是找到一個中介者，這個中介者可能是個對象等等，進程可以在其中放置消息，并且可以從中刪除消息，以此達到進程間通信的目的。

消息隊列：消息隊列是內(nèi)核中存儲消息的鏈表，它由消息隊列標(biāo)識符進行標(biāo)識，這種方式能夠在不同的進程之間提供全雙工的通信連接。

共享內(nèi)存：共享內(nèi)存是使用所有進程之間的內(nèi)存來建立連接，這種類型需要同步進程訪問來相互保護。

進程間狀態(tài)模型

進程的三態(tài)模型

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

 

圖中會涉及三種狀態(tài)

運行態(tài)：運行態(tài)指的就是進程實際占用 CPU 時間片運行時

就緒態(tài)：就緒態(tài)指的是可運行，但因為其他進程正在運行而處于就緒狀態(tài)

阻塞態(tài)：阻塞態(tài)又被稱為睡眠態(tài)，它指的是進程不具備運行條件，正在等待被 CPU 調(diào)度。

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

三種狀態(tài)會涉及四種狀態(tài)間的切換，在操作系統(tǒng)發(fā)現(xiàn)進程不能繼續(xù)執(zhí)行時會發(fā)生狀態(tài)1的輪轉(zhuǎn)，在某些系統(tǒng)中進程執(zhí)行系統(tǒng)調(diào)用，例如 pause，來獲取一個阻塞的狀態(tài)。在其他系統(tǒng)中包括 UNIX，當(dāng)進程從管道或特殊文件（例如終端）中讀取沒有可用的輸入時，該進程會被自動終止。

轉(zhuǎn)換 2 和轉(zhuǎn)換 3 都是由進程調(diào)度程序（操作系統(tǒng)的一部分）引起的，進程本身不知道調(diào)度程序的存在。轉(zhuǎn)換 2 的出現(xiàn)說明進程調(diào)度器認定當(dāng)前進程已經(jīng)運行了足夠長的時間，是時候讓其他進程運行 CPU 時間片了。當(dāng)所有其他進程都運行過后，這時候該是讓第一個進程重新獲得 CPU 時間片的時候了，就會發(fā)生轉(zhuǎn)換 3。

程序調(diào)度指的是，決定哪個進程優(yōu)先被運行和運行多久，這是很重要的一點。已經(jīng)設(shè)計出許多算法來嘗試平衡系統(tǒng)整體效率與各個流程之間的競爭需求。

當(dāng)進程等待的一個外部事件發(fā)生時（如從外部輸入一些數(shù)據(jù)后），則發(fā)生轉(zhuǎn)換 4。如果此時沒有其他進程在運行，則立刻觸發(fā)轉(zhuǎn)換 3，該進程便開始運行，否則該進程會處于就緒階段，等待 CPU 空閑后再輪到它運行。

進程的五態(tài)模型

在三態(tài)模型的基礎(chǔ)上，增加了兩個狀態(tài)，即 新建 和 終止 狀態(tài)。

新建態(tài)：進程的新建態(tài)就是進程剛創(chuàng)建出來的時候

創(chuàng)建進程需要兩個步驟：即為新進程分配所需要的資源和空間，設(shè)置進程為就緒態(tài)，并等待調(diào)度執(zhí)行。

終止態(tài)：進程的終止態(tài)就是指進程執(zhí)行完畢，到達結(jié)束點，或者因為錯誤而不得不中止進程。

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

先等待操作系統(tǒng)或相關(guān)的進程進行善后處理。

然后回收占用的資源并被系統(tǒng)刪除。

調(diào)度算法都有哪些

調(diào)度算法分為三大類：批處理中的調(diào)度、交互系統(tǒng)中的調(diào)度、實時系統(tǒng)中的調(diào)度

批處理中的調(diào)度

先來先服務(wù)

很像是先到先得。。?？赡茏詈唵蔚姆菗屨际秸{(diào)度算法的設(shè)計就是 先來先服務(wù)(first-come,first-serverd)。使用此算法，將按照請求順序為進程分配 CPU。最基本的，會有一個就緒進程的等待隊列。當(dāng)?shù)谝粋€任務(wù)從外部進入系統(tǒng)時，將會立即啟動并允許運行任意長的時間。它不會因為運行時間太長而中斷。當(dāng)其他作業(yè)進入時，它們排到就緒隊列尾部。

當(dāng)正在運行的進程阻塞，處于等待隊列的第一個進程就開始運行。當(dāng)一個阻塞的進程重新處于就緒態(tài)時，它會像一個新到達的任務(wù)，會排在隊列的末尾，即排在所有進程最后。

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

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

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

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

如上圖 a 所示，這里有 4 個作業(yè) A、B、C、D ，運行時間分別為 8、4、4、4 分鐘。若按圖中的次序運行，則 A 的周轉(zhuǎn)時間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時間內(nèi)為 14 分鐘。

現(xiàn)在考慮使用最短作業(yè)優(yōu)先算法運行 4 個作業(yè)，如上圖 b 所示，目前的周轉(zhuǎn)時間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業(yè)優(yōu)先是最優(yōu)的?？紤]有 4 個作業(yè)的情況，其運行時間分別為 a、b、c、d。第一個作業(yè)在時間 a 結(jié)束，第二個在時間 a + b 結(jié)束，以此類推。平均周轉(zhuǎn)時間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，所以 a 應(yīng)該是最短優(yōu)先作業(yè)，其次是 b，然后是 c ，最后是 d 它就只能影響自己的周轉(zhuǎn)時間了。

需要注意的是，在所有的進程都可以運行的情況下，最短作業(yè)優(yōu)先的算法才是最優(yōu)的。

 

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

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

交互式系統(tǒng)中的調(diào)度

交互式系統(tǒng)中在個人計算機、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來探討一下交互式調(diào)度

 

輪詢調(diào)度

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

 

優(yōu)先級調(diào)度

事實情況是不是所有的進程都是優(yōu)先級相等的。例如，在一所大學(xué)中的等級制度，首先是院長，然后是教授、秘書、后勤人員，最后是學(xué)生。這種將外部情況考慮在內(nèi)就實現(xiàn)了優(yōu)先級調(diào)度(priority scheduling)

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

但是也不意味著高優(yōu)先級的進程能夠永遠一直運行下去，調(diào)度程序會在每個時鐘中斷期間降低當(dāng)前運行進程的優(yōu)先級。如果此操作導(dǎo)致其優(yōu)先級降低到下一個最高進程的優(yōu)先級以下，則會發(fā)生進程切換?；蛘?，可以為每個進程分配允許運行的最大時間間隔。當(dāng)時間間隔用完后，下一個高優(yōu)先級的進程會得到運行的機會。

 

最短進程優(yōu)先

對于批處理系統(tǒng)而言，由于最短作業(yè)優(yōu)先常常伴隨著最短響應(yīng)時間，一種方式是根據(jù)進程過去的行為進行推測，并執(zhí)行估計運行時間最短的那一個。假設(shè)每個終端上每條命令的預(yù)估運行時間為 T0，現(xiàn)在假設(shè)測量到其下一次運行時間為 T1，可以用兩個值的加權(quán)來改進估計時間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是盡快忘掉老的運行時間，還是在一段長時間內(nèi)始終記住它們。當(dāng) a = 1/2 時，可以得到下面這個序列

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

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

彩票調(diào)度

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

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

公平分享調(diào)度

如果用戶 1 啟動了 9 個進程，而用戶 2 啟動了一個進程，使用輪轉(zhuǎn)或相同優(yōu)先級調(diào)度算法，那么用戶 1 將得到 90 % 的 CPU 時間，而用戶 2 將之得到 10 % 的 CPU 時間。

為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會把進程的擁有者考慮在內(nèi)。在這種模型下，每個用戶都會分配一些CPU 時間，而調(diào)度程序會選擇進程并強制執(zhí)行。因此如果兩個用戶每個都會有 50% 的 CPU 時間片保證，那么無論一個用戶有多少個進程，都將獲得相同的 CPU 份額。

影響調(diào)度程序的指標(biāo)是什么

會有下面幾個因素決定調(diào)度程序的好壞

CPU 使用率：

CPU 正在執(zhí)行任務(wù)（即不處于空閑狀態(tài)）的時間百分比。

等待時間

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

吞吐量

單位時間內(nèi)完成進程的數(shù)量

響應(yīng)時間

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

周轉(zhuǎn)時間

從提交流程到完成流程所經(jīng)過的時間。

什么是 RR 調(diào)度算法

RR(round-robin) 調(diào)度算法主要針對分時系統(tǒng)，RR 的調(diào)度算法會把時間片以相同的部分并循環(huán)的分配給每個進程，RR 調(diào)度算法沒有優(yōu)先級的概念。這種算法的實現(xiàn)比較簡單，而且每個線程都會占有時間片，并不存在線程饑餓的問題。

內(nèi)存管理篇

什么是按需分頁

在操作系統(tǒng)中，進程是以頁為單位加載到內(nèi)存中的，按需分頁是一種虛擬內(nèi)存的管理方式。在使用請求分頁的系統(tǒng)中，只有在嘗試訪問頁面所在的磁盤并且該頁面尚未在內(nèi)存中時，也就發(fā)生了缺頁異常，操作系統(tǒng)才會將磁盤頁面復(fù)制到內(nèi)存中。

什么是虛擬內(nèi)存

虛擬內(nèi)存是一種內(nèi)存分配方案，是一項可以用來輔助內(nèi)存分配的機制。我們知道，應(yīng)用程序是按頁裝載進內(nèi)存中的。但并不是所有的頁都會裝載到內(nèi)存中，計算機中的硬件和軟件會將數(shù)據(jù)從 RAM 臨時傳輸?shù)酱疟P中來彌補內(nèi)存的不足。如果沒有虛擬內(nèi)存的話，一旦你將計算機內(nèi)存填滿后，計算機會對你說

呃，不，對不起，您無法再加載任何應(yīng)用程序，請關(guān)閉另一個應(yīng)用程序以加載新的應(yīng)用程序。對于虛擬內(nèi)存，計算機可以執(zhí)行操作是查看內(nèi)存中最近未使用過的區(qū)域，然后將其復(fù)制到硬盤上。虛擬內(nèi)存通過復(fù)制技術(shù)實現(xiàn)了 妹子，你快來看哥哥能裝這么多程序 的資本。

復(fù)制是自動進行的，你無法感知到它的存在。

虛擬內(nèi)存的實現(xiàn)方式

虛擬內(nèi)存中，允許將一個作業(yè)分多次調(diào)入內(nèi)存。釆用連續(xù)分配方式時，會使相當(dāng)一部分內(nèi)存空間都處于暫時或永久的空閑狀態(tài)，造成內(nèi)存資源的嚴(yán)重浪費，而且也無法從邏輯上擴大內(nèi)存容量。因此，虛擬內(nèi)存的實需要建立在離散分配的內(nèi)存管理方式的基礎(chǔ)上。虛擬內(nèi)存的實現(xiàn)有以下三種方式：

請求分頁存儲管理。

請求分段存儲管理。

請求段頁式存儲管理。

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

一定容量的內(nèi)存和外存。

頁表機制（或段表機制），作為主要的數(shù)據(jù)結(jié)構(gòu)。

中斷機構(gòu)，當(dāng)用戶程序要訪問的部分尚未調(diào)入內(nèi)存，則產(chǎn)生中斷。

地址變換機構(gòu)，邏輯地址到物理地址的變換。

內(nèi)存為什么要分段

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

那么什么是重定位呢？

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

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

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

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

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

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

物理地址就是內(nèi)存中真正的地址，它就相當(dāng)于是你家的門牌號，你家就肯定有這個門牌號，具有唯一性。不管哪種地址，最終都會映射為物理地址。

在實模式下，段基址 + 段內(nèi)偏移經(jīng)過地址加法器的處理，經(jīng)過地址總線傳輸，最終也會轉(zhuǎn)換為物理地址。

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

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

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

 

空閑內(nèi)存管理的方式

操作系統(tǒng)在動態(tài)分配內(nèi)存時（malloc，new），需要對空間內(nèi)存進行管理。一般采用了兩種方式：位圖和空閑鏈表。

使用位圖進行管理

使用位圖方法時，內(nèi)存可能被劃分為小到幾個字或大到幾千字節(jié)的分配單元。每個分配單元對應(yīng)于位圖中的一位，0 表示空閑， 1 表示占用（或者相反）。一塊內(nèi)存區(qū)域和其對應(yīng)的位圖如下

å圖 a 表示一段有 5 個進程和 3 個空閑區(qū)的內(nèi)存，刻度為內(nèi)存分配單元，陰影區(qū)表示空閑（在位圖中用 0 表示）；圖 b 表示對應(yīng)的位圖；圖 c 表示用鏈表表示同樣的信息

分配單元的大小是一個重要的設(shè)計因素，分配單位越小，位圖越大。然而，即使只有 4 字節(jié)的分配單元，32 位的內(nèi)存也僅僅只需要位圖中的 1 位。32n 位的內(nèi)存需要 n 位的位圖，所以1 個位圖只占用了 1/32 的內(nèi)存。如果選擇更大的內(nèi)存單元，位圖應(yīng)該要更小。如果進程的大小不是分配單元的整數(shù)倍，那么在最后一個分配單元中會有大量的內(nèi)存被浪費。

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

使用空閑鏈表

另一種記錄內(nèi)存使用情況的方法是，維護一個記錄已分配內(nèi)存段和空閑內(nèi)存段的鏈表，段會包含進程或者是兩個進程的空閑區(qū)域?？捎蒙厦娴膱D c 來表示內(nèi)存的使用情況。鏈表中的每一項都可以代表一個 空閑區(qū)(H) 或者是進程(P)的起始標(biāo)志，長度和下一個鏈表項的位置。

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

當(dāng)按照地址順序在鏈表中存放進程和空閑區(qū)時，有幾種算法可以為創(chuàng)建的進程（或者從磁盤中換入的進程）分配內(nèi)存。

首次適配算法：在鏈表中進行搜索，直到找到最初的一個足夠大的空閑區(qū)，將其分配。除非進程大小和空間區(qū)大小恰好相同，否則會將空閑區(qū)分為兩部分，一部分為進程使用，一部分成為新的空閑區(qū)。該方法是速度很快的算法，因為索引鏈表結(jié)點的個數(shù)較少。

下次適配算法：工作方式與首次適配算法相同，但每次找到新的空閑區(qū)位置后都記錄當(dāng)前位置，下次尋找空閑區(qū)從上次結(jié)束的地方開始搜索，而不是與首次適配一樣從頭開始；

最佳適配算法：搜索整個鏈表，找出能夠容納進程分配的最小的空閑區(qū)。這樣存在的問題是，盡管可以保證為進程找到一個最為合適的空閑區(qū)進行分配，但大多數(shù)情況下，這樣的空閑區(qū)被分為兩部分，一部分用于進程分配，一部分會生成很小的空閑區(qū)，而這樣的空閑區(qū)很難再被進行利用。

最差適配算法：與最佳適配算法相反，每次分配搜索最大的空閑區(qū)進行分配，從而可以使得空閑區(qū)拆分得到的新的空閑區(qū)可以更好的被進行利用。

頁面置換算法都有哪些

在地址映射過程中，如果在頁面中發(fā)現(xiàn)所要訪問的頁面不在內(nèi)存中，那么就會產(chǎn)生一條缺頁中斷。當(dāng)發(fā)生缺頁中斷時，如果操作系統(tǒng)內(nèi)存中沒有空閑頁面，那么操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。

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

最優(yōu)算法在當(dāng)前頁面中置換最后要訪問的頁面。不幸的是，沒有辦法來判定哪個頁面是最后一個要訪問的，因此實際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。

NRU 算法根據(jù) R 位和 M 位的狀態(tài)將頁面氛圍四類。從編號最小的類別中隨機選擇一個頁面。NRU 算法易于實現(xiàn)，但是性能不是很好。存在更好的算法。

FIFO 會跟蹤頁面加載進入內(nèi)存中的順序，并把頁面放入一個鏈表中。有可能刪除存在時間最長但是還在使用的頁面，因此這個算法也不是一個很好的選擇。

第二次機會算法是對 FIFO 的一個修改，它會在刪除頁面之前檢查這個頁面是否仍在使用。如果頁面正在使用，就會進行保留。這個改進大大提高了性能。

時鐘 算法是第二次機會算法的另外一種實現(xiàn)形式，時鐘算法和第二次算法的性能差不多，但是會花費更少的時間來執(zhí)行算法。

LRU 算法是一個非常優(yōu)秀的算法，但是沒有特殊的硬件(TLB)很難實現(xiàn)。如果沒有硬件，就不能使用 LRU 算法。

NFU 算法是一種近似于 LRU 的算法，它的性能不是非常好。

老化 算法是一種更接近 LRU 算法的實現(xiàn)，并且可以更好的實現(xiàn)，因此是一個很好的選擇

最后兩種算法都使用了工作集算法。工作集算法提供了合理的性能開銷，但是它的實現(xiàn)比較復(fù)雜。WSClock 是另外一種變體，它不僅能夠提供良好的性能，而且可以高效地實現(xiàn)。

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

文件系統(tǒng)篇

提高文件系統(tǒng)性能的方式

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

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

高速緩存

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

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

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

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

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

塊提前讀

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

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

減少磁盤臂運動

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

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

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

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

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

當(dāng)然，只有在磁盤中裝有磁盤臂的情況下，討論尋道時間和旋轉(zhuǎn)時間才是有意義的?，F(xiàn)在越來越多的電腦使用 固態(tài)硬盤(SSD)，對于這些硬盤，由于采用了和閃存同樣的制造技術(shù)，使得隨機訪問和順序訪問在傳輸速度上已經(jīng)較為相近，傳統(tǒng)硬盤的許多問題就消失了。但是也引發(fā)了新的問題。

磁盤碎片整理

在初始安裝操作系統(tǒng)后，文件就會被不斷的創(chuàng)建和清除，于是磁盤會產(chǎn)生很多的碎片，在創(chuàng)建一個文件時，它使用的塊會散布在整個磁盤上，降低性能。刪除文件后，回收磁盤塊，可能會造成空穴。

磁盤性能可以通過如下方式恢復(fù)：移動文件使它們相互挨著，并把所有的至少是大部分的空閑空間放在一個或多個大的連續(xù)區(qū)域內(nèi)。Windows 有一個程序 defrag 就是做這個事兒的。Windows 用戶會經(jīng)常使用它，SSD 除外。

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

磁盤臂調(diào)度算法

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

尋道時間 - 尋道時間指的就是將磁盤臂移動到需要讀取磁盤塊上的時間

旋轉(zhuǎn)延遲 - 等待合適的扇區(qū)旋轉(zhuǎn)到磁頭下所需的時間

實際數(shù)據(jù)的讀取或者寫入時間

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

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

通常情況下，磁盤在進行尋道時，其他進程會產(chǎn)生其他的磁盤請求。磁盤驅(qū)動程序會維護一張表，表中會記錄著柱面號當(dāng)作索引，每個柱面未完成的請求會形成鏈表，鏈表頭存放在表的相應(yīng)表項中。

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

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

我們可以計算一下磁盤臂所跨越的磁盤數(shù)量為 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51，相當(dāng)于是跨越了 51 次盤面，如果使用最短路徑優(yōu)先，我們來計算一下跨越的盤面

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

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

這里有一個原型可以參考就是我們?nèi)粘Ｉ钪械碾娞?，電梯使用一種電梯算法(elevator algorithm) 來進行調(diào)度，從而滿足協(xié)調(diào)效率和公平性這兩個相互沖突的目標(biāo)。電梯一般會保持向一個方向移動，直到在那個方向上沒有請求為止，然后改變方向。

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

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

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

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

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

這里需要注意一點，當(dāng)一個柱面有多條磁道時，相繼的請求可能針對不同的磁道，這種選擇沒有代價，因為選擇磁頭不需要移動磁盤臂也沒有旋轉(zhuǎn)延遲。

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

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

當(dāng)同一個控制器上有多個驅(qū)動器時，操作系統(tǒng)應(yīng)該為每個驅(qū)動器都單獨的維護一個未完成的請求表。一旦有某個驅(qū)動器閑置時，就應(yīng)該發(fā)出一個尋道請求來將磁盤臂移到下一個被請求的柱面。如果下一個尋道請求到來時恰好沒有磁盤臂處于正確的位置，那么驅(qū)動程序會在剛剛完成傳輸?shù)尿?qū)動器上發(fā)出一個新的尋道命令并等待，等待下一次中斷到來時檢查哪個驅(qū)動器處于閑置狀態(tài)。

RAID 的不同級別

RAID 稱為 磁盤冗余陣列，簡稱 磁盤陣列。利用虛擬化技術(shù)把多個硬盤結(jié)合在一起，成為一個或多個磁盤陣列組，目的是提升性能或數(shù)據(jù)冗余。

RAID 有不同的級別

RAID 0 - 無容錯的條帶化磁盤陣列

RAID 1 - 鏡像和雙工

RAID 2 - 內(nèi)存式糾錯碼

RAID 3 - 比特交錯奇偶校驗

RAID 4 - 塊交錯奇偶校驗

RAID 5 - 塊交錯分布式奇偶校驗

RAID 6 - P + Q冗余

 

IO 篇

操作系統(tǒng)中的時鐘是什么

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

時鐘硬件

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

比較簡單的一種時鐘被連接到 110 V 或 220 V 的電源線上，這樣每個電壓周期會產(chǎn)生一個中斷，大概是 50 - 60 HZ。這些時鐘過去一直占據(jù)支配地位。

另外的一種時鐘由晶體振蕩器、計數(shù)器和寄存器組成，示意圖如下所示

這種時鐘稱為可編程時鐘 ，可編程時鐘有兩種模式，一種是 一鍵式(one-shot mode)，當(dāng)時鐘啟動時，會把存儲器中的值復(fù)制到計數(shù)器中，然后，每次晶體的振蕩器的脈沖都會使計數(shù)器 -1。當(dāng)計數(shù)器變?yōu)?0 時，會產(chǎn)生一個中斷，并停止工作，直到軟件再一次顯示啟動。還有一種模式是 方波(square-wave mode) 模式，在這種模式下，當(dāng)計數(shù)器變?yōu)?0 并產(chǎn)生中斷后，存儲寄存器的值會自動復(fù)制到計數(shù)器中，這種周期性的中斷稱為一個時鐘周期。

設(shè)備控制器的主要功能

設(shè)備控制器是一個可編址的設(shè)備，當(dāng)它僅控制一個設(shè)備時，它只有一個唯一的設(shè)備地址；如果設(shè)備控制器控制多個可連接設(shè)備時，則應(yīng)含有多個設(shè)備地址，并使每一個設(shè)備地址對應(yīng)一個設(shè)備。

設(shè)備控制器主要分為兩種：字符設(shè)備和塊設(shè)備

設(shè)備控制器的主要功能有下面這些

接收和識別命令：設(shè)備控制器可以接受來自 CPU 的指令，并進行識別。設(shè)備控制器內(nèi)部也會有寄存器，用來存放指令和參數(shù)

進行數(shù)據(jù)交換：CPU、控制器和設(shè)備之間會進行數(shù)據(jù)的交換，CPU 通過總線把指令發(fā)送給控制器，或從控制器中并行地讀出數(shù)據(jù)；控制器將數(shù)據(jù)寫入指定設(shè)備。

地址識別：每個硬件設(shè)備都有自己的地址，設(shè)備控制器能夠識別這些不同的地址，來達到控制硬件的目的，此外，為使 CPU 能向寄存器中寫入或者讀取數(shù)據(jù)，這些寄存器都應(yīng)具有唯一的地址。

差錯檢測：設(shè)備控制器還具有對設(shè)備傳遞過來的數(shù)據(jù)進行檢測的功能。

中斷處理過程

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

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

非嵌套的中斷處理程序按照順序處理各個中斷，非嵌套的中斷處理程序也是最簡單的中斷處理

嵌套的中斷處理程序會處理多個中斷而無需分配優(yōu)先級

可重入的中斷處理程序可使用優(yōu)先級處理多個中斷

簡單優(yōu)先級中斷處理程序可處理簡單的中斷

標(biāo)準(zhǔn)優(yōu)先級中斷處理程序比低優(yōu)先級的中斷處理程序在更短的時間能夠處理優(yōu)先級更高的中斷

高優(yōu)先級 中斷處理程序在短時間能夠處理優(yōu)先級更高的任務(wù)，并直接進入特定的服務(wù)例程。

優(yōu)先級分組中斷處理程序能夠處理不同優(yōu)先級的中斷任務(wù)

下面是一些通用的中斷處理程序的步驟，不同的操作系統(tǒng)實現(xiàn)細節(jié)不一樣

保存所有沒有被中斷硬件保存的寄存器

為中斷服務(wù)程序設(shè)置上下文環(huán)境，可能包括設(shè)置 TLB、MMU 和頁表，如果不太了解這三個概念，請參考另外一篇文章

為中斷服務(wù)程序設(shè)置棧

對中斷控制器作出響應(yīng)，如果不存在集中的中斷控制器，則繼續(xù)響應(yīng)中斷

把寄存器從保存它的地方拷貝到進程表中

運行中斷服務(wù)程序，它會從發(fā)出中斷的設(shè)備控制器的寄存器中提取信息

操作系統(tǒng)會選擇一個合適的進程來運行。如果中斷造成了一些優(yōu)先級更高的進程變?yōu)榫途w態(tài)，則選擇運行這些優(yōu)先級高的進程

為進程設(shè)置 MMU 上下文，可能也會需要 TLB，根據(jù)實際情況決定

加載進程的寄存器，包括 PSW 寄存器

開始運行新的進程

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

 

什么是設(shè)備驅(qū)動程序

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

什么是 DMA

DMA 的中文名稱是直接內(nèi)存訪問，它意味著 CPU 授予 I/O 模塊權(quán)限在不涉及 CPU 的情況下讀取或?qū)懭雰?nèi)存。也就是 DMA 可以不需要 CPU 的參與。這個過程由稱為 DMA 控制器（DMAC）的芯片管理。由于 DMA 設(shè)備可以直接在內(nèi)存之間傳輸數(shù)據(jù)，而不是使用 CPU 作為中介，因此可以緩解總線上的擁塞。DMA 通過允許 CPU 執(zhí)行任務(wù)，同時 DMA 系統(tǒng)通過系統(tǒng)和內(nèi)存總線傳輸數(shù)據(jù)來提高系統(tǒng)并發(fā)性。

直接內(nèi)存訪問的特點

DMA 方式有如下特點：

數(shù)據(jù)傳送以數(shù)據(jù)塊為基本單位

所傳送的數(shù)據(jù)從設(shè)備直接送入主存，或者從主存直接輸出到設(shè)備上

僅在傳送一個或多個數(shù)據(jù)塊的開始和結(jié)束時才需 CPU 的干預(yù)，而整塊數(shù)據(jù)的傳送則是在控制器的控制下完成。

DMA 方式和中斷驅(qū)動控制方式相比，減少了 CPU 對 I/O 操作的干預(yù)，進一步提高了 CPU 與 I/O 設(shè)備的并行操作程度。

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

死鎖篇

什么是僵尸進程

僵尸進程是已完成且處于終止?fàn)顟B(tài)，但在進程表中卻仍然存在的進程。僵尸進程通常發(fā)生在父子關(guān)系的進程中，由于父進程仍需要讀取其子進程的退出狀態(tài)所造成的。

死鎖產(chǎn)生的原因

死鎖產(chǎn)生的原因大致有兩個：資源競爭和程序執(zhí)行順序不當(dāng)

死鎖產(chǎn)生的必要條件

資源死鎖可能出現(xiàn)的情況主要有

互斥條件：每個資源都被分配給了一個進程或者資源是可用的

保持和等待條件：已經(jīng)獲取資源的進程被認為能夠獲取新的資源

不可搶占條件：分配給一個進程的資源不能強制的從其他進程搶占資源，它只能由占有它的進程顯示釋放

循環(huán)等待：死鎖發(fā)生時，系統(tǒng)中一定有兩個或者兩個以上的進程組成一個循環(huán)，循環(huán)中的每個進程都在等待下一個進程釋放的資源。

死鎖的恢復(fù)方式

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

通過搶占進行恢復(fù)

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

通過回滾進行恢復(fù)

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

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

殺死進程恢復(fù)

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

另外一種方式是選擇一個環(huán)外的進程作為犧牲品來釋放進程資源。

如何破壞死鎖

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

破壞互斥條件

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

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

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

破壞保持等待的條件

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

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

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

破壞不可搶占條件

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

破壞循環(huán)等待條件

現(xiàn)在就剩最后一個條件了，循環(huán)等待條件可以通過多種方法來破壞。一種方式是制定一個標(biāo)準(zhǔn)，一個進程在任何時候只能使用一種資源。如果需要另外一種資源，必須釋放當(dāng)前資源。

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

進程可以在任何時間提出請求，但是所有的請求都必須按照資源的順序提出。如果按照此分配規(guī)則的話，那么資源分配之間不會出現(xiàn)環(huán)。

 

死鎖類型

兩階段加鎖

雖然很多情況下死鎖的避免和預(yù)防都能處理，但是效果并不好。隨著時間的推移，提出了很多優(yōu)秀的算法用來處理死鎖。例如在數(shù)據(jù)庫系統(tǒng)中，一個經(jīng)常發(fā)生的操作是請求鎖住一些記錄，然后更新所有鎖定的記錄。當(dāng)同時有多個進程運行時，就會有死鎖的風(fēng)險。

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

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

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

通信死鎖

我們上面一直討論的是資源死鎖，資源死鎖是一種死鎖類型，但并不是唯一類型，還有通信死鎖，也就是兩個或多個進程在發(fā)送消息時出現(xiàn)的死鎖。進程 A 給進程 B 發(fā)了一條消息，然后進程 A 阻塞直到進程 B 返回響應(yīng)。假設(shè)請求消息丟失了，那么進程 A 在一直等著回復(fù)，進程 B 也會阻塞等待請求消息到來，這時候就產(chǎn)生死鎖。

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

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

但是并非所有網(wǎng)絡(luò)通信發(fā)生的死鎖都是通信死鎖，也存在資源死鎖，下面就是一個典型的資源死鎖。

當(dāng)一個數(shù)據(jù)包從主機進入路由器時，會被放入一個緩沖區(qū)，然后再傳輸?shù)搅硗庖粋€路由器，再到另一個，以此類推直到目的地。緩沖區(qū)都是資源并且數(shù)量有限。如下圖所示，每個路由器都有 10 個緩沖區(qū)（實際上有很多）。

假如路由器 A 的所有數(shù)據(jù)需要發(fā)送到 B ，B 的所有數(shù)據(jù)包需要發(fā)送到 D，然后 D 的所有數(shù)據(jù)包需要發(fā)送到 A 。沒有數(shù)據(jù)包可以移動，因為在另一端沒有緩沖區(qū)可用，這就是一個典型的資源死鎖。

活鎖

某些情況下，當(dāng)進程意識到它不能獲取所需要的下一個鎖時，就會嘗試禮貌的釋放已經(jīng)獲得的鎖，然后等待非常短的時間再次嘗試獲取?？梢韵胂褚幌逻@個場景：當(dāng)兩個人在狹路相逢的時候，都想給對方讓路，相同的步調(diào)會導(dǎo)致雙方都無法前進。

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

饑餓

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

我們假設(shè)打印機的分配方案是每次都會分配給最小文件的進程，那么要打印大文件的進程會永遠得不到服務(wù)，導(dǎo)致進程饑餓，進程會無限制的推后，雖然它沒有阻塞。

后記

這篇文章到這里就結(jié)束了，后面我會繼續(xù)寫關(guān)于計算機網(wǎng)絡(luò)、計算機基礎(chǔ)、Java 相關(guān)、Java 架構(gòu)相關(guān)的面試題。

如果這篇文章你覺得還不錯的話，還希望可以點贊、在看、轉(zhuǎn)發(fā)、留言，歡迎關(guān)注一下我的公眾號【程序員cxuan】，這個號的干貨簡直太多了。

最后，你的支持是我繼續(xù)肝文的動力。希望你能順利進入大廠，加油！