操作系統(tǒng)的四十多道題面試題

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

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

話不多說，下面我們直接進(jìn)入面試題。

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

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

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

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

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

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

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

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

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

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

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

軟件訪問硬件的幾種方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

單體系統(tǒng)

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

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

在單體系統(tǒng)中，對于每個(gè)系統(tǒng)調(diào)用都會有一個(gè)服務(wù)程序來保障和運(yùn)行。需要一組實(shí)用程序來彌補(bǔ)服務(wù)程序需要的功能，例如從用戶程序中獲取數(shù)據(jù)?？蓪⒏鞣N過程劃分為一個(gè)三層模型

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

分層系統(tǒng)

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

微內(nèi)核

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

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

在內(nèi)核的外部，系統(tǒng)的構(gòu)造有三層，它們都在用戶態(tài)下運(yùn)行，最底層是設(shè)備驅(qū)動(dòng)器。由于它們都在用戶態(tài)下運(yùn)行，所以不能物理的訪問 I/O 端口空間，也不能直接發(fā)出 I/O 命令。相反，為了能夠?qū)?I/O 設(shè)備編程，驅(qū)動(dòng)器構(gòu)建一個(gè)結(jié)構(gòu)，指明哪個(gè)參數(shù)值寫到哪個(gè) I/O 端口，并聲稱一個(gè)內(nèi)核調(diào)用，這樣就完成了一次調(diào)用過程。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所有的用戶進(jìn)程都是運(yùn)行在用戶態(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 進(jìn)內(nèi)核，也被稱之為陷阱指令(trap instruction)。

他們的工作流程如下：

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

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

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

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

從地址 0x08 開始，進(jìn)程執(zhí)行加載并跳轉(zhuǎn)到中斷處理程序，這個(gè)程序就是 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)核

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

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

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

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

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

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

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

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

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

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

復(fù)制完成后，boot 程序讀取啟動(dòng)設(shè)備的根目錄。boot 程序要理解文件系統(tǒng)和目錄格式。然后 boot 程序被調(diào)入內(nèi)核，把控制權(quán)移交給內(nèi)核。直到這里，boot 完成了它的工作。系統(tǒng)內(nèi)核開始運(yùn)行。

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

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

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

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

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

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

getty 程序會在終端上輸入

login:

等待用戶輸入用戶名，在輸入用戶名后，getty 程序結(jié)束，登陸程序/bin/login開始運(yùn)行。login 程序需要輸入密碼，并與保存在/etc/passwd中的密碼進(jìn)行對比，如果輸入正確，login 程序以用戶 shell 程序替換自身，等待第一個(gè)命令。如果不正確，login 程序要求輸入另一個(gè)用戶名。

整個(gè)系統(tǒng)啟動(dòng)過程如下

進(jìn)程和線程篇

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

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

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

什么是進(jìn)程和進(jìn)程表

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

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

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

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

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

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

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

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

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

什么是上下文切換

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

使用多線程的好處是什么

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

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

在流程中的資源共享

比較經(jīng)濟(jì)適用

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

進(jìn)程終止的方式

進(jìn)程的終止

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

正常退出(自愿的)

錯(cuò)誤退出(自愿的)

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

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

正常退出

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

錯(cuò)誤退出

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

ccfoo.c

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

嚴(yán)重錯(cuò)誤

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

被其他進(jìn)程殺死

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

進(jìn)程間的通信方式

進(jìn)程間的通信方式比較多，首先你需要理解下面這幾個(gè)概念

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

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

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

任何時(shí)候兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運(yùn)行態(tài)：運(yùn)行態(tài)指的就是進(jìn)程實(shí)際占用 CPU 時(shí)間片運(yùn)行時(shí)

就緒態(tài)：就緒態(tài)指的是可運(yùn)行，但因?yàn)槠渌M(jìn)程正在運(yùn)行而處于就緒狀態(tài)

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

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

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

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

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

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

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

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

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

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

終止態(tài)：進(jìn)程的終止態(tài)就是指進(jìn)程執(zhí)行完畢，到達(dá)結(jié)束點(diǎn)，或者因?yàn)殄e(cuò)誤而不得不中止進(jìn)程。

終止一個(gè)進(jìn)程需要兩個(gè)步驟：

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

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

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

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

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

先來先服務(wù)

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

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

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

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

批處理中，第二種調(diào)度算法是最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時(shí)間已知。例如，一家保險(xiǎn)公司，因?yàn)槊刻煲鲱愃频墓ぷ?，所以人們可以相?dāng)精確地預(yù)測處理 1000 個(gè)索賠的一批作業(yè)需要多長時(shí)間。當(dāng)輸入隊(duì)列中有若干個(gè)同等重要的作業(yè)被啟動(dòng)時(shí)，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法

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

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

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

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

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

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

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

輪詢調(diào)度

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

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

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

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

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

最短進(jìn)程優(yōu)先

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

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

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

彩票調(diào)度

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

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

公平分享調(diào)度

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

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

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

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

CPU 使用率：

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

等待時(shí)間

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

吞吐量

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

響應(yīng)時(shí)間

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

周轉(zhuǎn)時(shí)間

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

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

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

內(nèi)存管理篇

什么是按需分頁

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

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

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

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

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

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

請求分頁存儲管理。

請求分段存儲管理。

請求段頁式存儲管理。

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

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

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

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

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

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

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

那么什么是重定位呢？

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

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

愛了愛了，這篇寄存器講的有點(diǎn)意思

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

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

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

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

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

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

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

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

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

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

使用位圖進(jìn)行管理

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

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

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

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

使用空閑鏈表

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

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

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

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

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

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

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

頁面置換算法都有哪些

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

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

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

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

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

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

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

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

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

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

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

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

文件系統(tǒng)篇

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

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

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

高速緩存

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

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

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

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

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

塊提前讀

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

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

減少磁盤臂運(yùn)動(dòng)

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

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

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

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

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

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

磁盤碎片整理

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

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

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

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

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

尋道時(shí)間 - 尋道時(shí)間指的就是將磁盤臂移動(dòng)到需要讀取磁盤塊上的時(shí)間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RAID 的不同級別

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

RAID 有不同的級別

RAID 0 - 無容錯(cuò)的條帶化磁盤陣列

RAID 1 - 鏡像和雙工

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

RAID 3 - 比特交錯(cuò)奇偶校驗(yàn)

RAID 4 - 塊交錯(cuò)奇偶校驗(yàn)

RAID 5 - 塊交錯(cuò)分布式奇偶校驗(yàn)

RAID 6 - P + Q冗余

IO 篇

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

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

時(shí)鐘硬件

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

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

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

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

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

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

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

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

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

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

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

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

中斷處理過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

把寄存器從保存它的地方拷貝到進(jìn)程表中

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

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

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

加載進(jìn)程的寄存器，包括 PSW 寄存器

開始運(yùn)行新的進(jìn)程

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

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

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

什么是 DMA

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

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

DMA 方式有如下特點(diǎn)：

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

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

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

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

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

死鎖篇

什么是僵尸進(jìn)程

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

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

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

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

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

互斥條件：每個(gè)資源都被分配給了一個(gè)進(jìn)程或者資源是可用的

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

不可搶占條件：分配給一個(gè)進(jìn)程的資源不能強(qiáng)制的從其他進(jìn)程搶占資源，它只能由占有它的進(jìn)程顯示釋放

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

死鎖的恢復(fù)方式

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

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

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

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

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

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

殺死進(jìn)程恢復(fù)

最簡單有效的解決方案是直接殺死一個(gè)死鎖進(jìn)程。但是殺死一個(gè)進(jìn)程可能照樣行不通，這時(shí)候就需要?dú)⑺绖e的資源進(jìn)行恢復(fù)。

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

如何破壞死鎖

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

破壞互斥條件

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

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

因此，盡量做到盡可能少的進(jìn)程可以請求資源。

破壞保持等待的條件

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

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

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

破壞不可搶占條件

破壞不可搶占條件也是可以的?？梢酝ㄟ^虛擬化的方式來避免這種情況。

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

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

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

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

死鎖類型

兩階段加鎖

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

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

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

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

通信死鎖

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

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

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

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

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

假如路由器 A 的所有數(shù)據(jù)需要發(fā)送到 B ，B 的所有數(shù)據(jù)包需要發(fā)送到 D，然后 D 的所有數(shù)據(jù)包需要發(fā)送到 A 。沒有數(shù)據(jù)包可以移動(dòng)，因?yàn)樵诹硪欢藳]有緩沖區(qū)可用，這就是一個(gè)典型的資源死鎖。

活鎖

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

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

饑餓

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

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

原文標(biāo)題：2.5w字 + 36 張圖爆肝操作系統(tǒng)面試題

文章出處：【微信公眾號：Linux愛好者】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq