這可能最全的作業系統面試題

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

歡迎各位大佬訪問我的 github ，跪求 star
成為最好的 Java 程式員

這份面試題有 43 道題，囊括了校招面試和社招面試，看完這一篇文章，保準你能和面試官侃侃而談，增加進入大廠的幾率！

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

作業系統簡介篇

解釋一下什么是作業系統

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

通常情況下，計算機上會運行著許多應用程式，它們都需要對記憶體和 CPU 進行互動，作業系統的目的就是為了保證這些訪問和互動能夠準確無誤的進行，

作業系統的主要功能

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

• 行程管理: 行程管理的主要作用就是任務調度，在單核處理器下，作業系統會為每個行程分配一個任務，行程管理的作業十分簡單；而在多核處理器下，作業系統除了要為行程分配任務外，還要解決處理器的調度、分配和回收等問題
• 記憶體管理：記憶體管理主要是作業系統負責管理記憶體的分配、回收，在行程需要時分配記憶體以及在行程完成時回收記憶體，協調記憶體資源，通過合理的頁面置換演算法進行頁面的換入換出
• 設備管理：根據確定的設備分配原則對設備進行分配，使設備與主機能夠并行作業，為用戶提供良好的設備使用界面，
• 檔案管理：有效地管理檔案的存盤空間，合理地組織和管理檔案系統，為檔案訪問和檔案保護提供更有效的方法及手段，
• 提供用戶介面：作業系統提供了訪問應用程式和硬體的介面，使用戶能夠通過應用程式發起系統呼叫從而操縱硬體，實作想要的功能，

軟體訪問硬體的幾種方式

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

硬體在 I/O 上大致分為并行和串行，同時也對應串行介面和并行介面，

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

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

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

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

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

• 直接訪問：直接訪問由用戶行程直接控制主存或 CPU 和外圍設備之間的資訊傳送，直接程式控制方式又稱為忙/等待方式，
• 中斷驅動：為了減少程式直接控制方式下 CPU 的等待時間以及提高系統的并行程度，系統引入了中斷機制，中斷機制引入后，外圍設備僅當操作正常結束或例外結束時才向 CPU 發出中斷請求，在 I/O 設備輸入每個資料的程序中，由于無需 CPU 的干預，一定程度上實作了 CPU 與 I/O 設備的并行作業，

上述兩種方法的特點都是以 CPU 為中心，資料傳送通過一段程式來實作，軟體的傳送手段限制了資料傳送的速度，接下來介紹的這兩種 I/O 控制方式采用硬體的方法來顯示 I/O 的控制

• DMA 直接記憶體訪問：為了進一步減少 CPU 對 I/O 操作的干預，防止因并行操作設備過多使 CPU 來不及處理或因速度不匹配而造成的資料丟失現象，引入了 DMA 控制方式，
• 通道控制方式：通道，獨立于 CPU 的專門負責輸入輸出控制的處理機，它控制設備與記憶體直接進行資料交換，有自己的通道指令，這些指令由 CPU 啟動，并在操作結束時向 CPU 發出中斷信號，

解釋一下作業系統的主要目的是什么

作業系統是一種軟體，它的主要目的有三種

• 管理計算機資源，這些資源包括 CPU、記憶體、磁盤驅動器、列印機等，
• 提供一種圖形界面，就像我們前面描述的那樣，它提供了用戶和計算機之間的橋梁，
• 為其他軟體提供服務，作業系統與軟體進行互動，以便為其分配運行所需的任何必要資源，

作業系統的種類有哪些

作業系統通常預裝在你購買計算機之前，大部分用戶都會使用默認的作業系統，但是你也可以升級甚至更改作業系統，但是一般常見的作業系統只有三種：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 就進入了內核態，執行內核代碼，至于為什么是陷入，我們看圖，內核是一個凹陷的構造，有陷下去的感覺，所以稱為陷入，

什么是用戶態和內核態

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

• 內核態：處于內核態的 CPU 可以訪問任意的資料，包括外圍設備，比如網卡、硬碟等，處于內核態的 CPU 可以從一個程式切換到另外一個程式，并且占用 CPU 不會發生搶占情況，一般處于特權級 0 的狀態我們稱之為內核態，

• 用戶態：處于用戶態的 CPU 只能受限的訪問記憶體，并且不允許訪問外圍設備，用戶態下的 CPU 不允許獨占，也就是說 CPU 能夠被其他程式獲取，

那么為什么要有用戶態和內核態呢？

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

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

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

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

他們的作業流程如下：

• 首先用戶程式會呼叫 glibc 庫，glibc 是一個標準庫，同時也是一套核心庫，庫中定義了很多關鍵 API，
• glibc 庫知道針對不同體系結構呼叫系統呼叫的正確方法，它會根據體系結構應用程式的二進制介面設定用戶行程傳遞的引數，來準備系統呼叫，
• 然后，glibc 庫呼叫軟體中斷指令(SWI) ，這個指令通過更新 CPSR 暫存器將模式改為超級用戶模式，然后跳轉到地址 0x08 處，
• 到目前為止，整個程序仍處于用戶態下，在執行 SWI 指令后，允許行程執行內核代碼，MMU 現在允許內核虛擬記憶體訪問
• 從地址 0x08 開始，行程執行加載并跳轉到中斷處理程式，這個程式就是 ARM 中的 vector_swi()，
• 在 vector_swi() 處，從 SWI 指令中提取系統呼叫號 SCNO，然后使用 SCNO 作為系統呼叫表 sys_call_table 的索引，調轉到系統呼叫函式，
• 執行系統呼叫完成后，將還原用戶模式暫存器，然后再以用戶模式執行，

什么是內核

在計算機中，內核是一個計算機程式，它是作業系統的核心，可以控制作業系統中所有的內容，內核通常是在 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（注意不是系統呼叫），

行程間的通信方式

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

• 競態條件：即兩個或多個執行緒同時對一共享資料進行修改，從而影響程式運行的正確性時，這種就被稱為競態條件(race condition)，

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

  一個好的解決方案，應該包含下面四種條件

  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 使用率：

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)是按照地址排序的，這種方式的優點是，當行程終止或被交換時，更新串列很簡單，一個終止行程通常有兩個鄰居（除了記憶體的頂部和底部外），相鄰的可能是行程也可能是空閑區，它們有四種組合方式，

當按照地址順序在鏈表中存放行程和空閑區時，有幾種演算法可以為創建的行程（或者從磁盤中換入的行程）分配記憶體，

• 首次適配演算法：在鏈表中進行搜索，直到找到最初的一個足夠大的空閑區，將其分配，除非行程大小和空間區大小恰好相同，否則會將空閑區分為兩部分，一部分為行程使用，一部分成為新的空閑區，該方法是速度很快的演算法，因為索引鏈表結點的個數較少，
• 下次適配演算法：作業方式與首次適配演算法相同，但每次找到新的空閑區位置后都記錄當前位置，下次尋找空閑區從上次結束的地方開始搜索，而不是與首次適配放一樣從頭開始；
• 最佳適配演算法：搜索整個鏈表，找出能夠容納行程分配的最小的空閑區，這樣存在的問題是，盡管可以保證為行程找到一個最為合適的空閑區進行分配，但大多數情況下，這樣的空閑區被分為兩部分，一部分用于行程分配，一部分會生成很小的空閑區，而這樣的空閑區很難再被進行利用，
• 最差適配演算法：與最佳適配演算法相反，每次分配搜索最大的空閑區進行分配，從而可以使得空閑區拆分得到的新的空閑區可以更好的被進行利用，

頁面置換演算法都有哪些

在地址映射程序中，如果在頁面中發現所要訪問的頁面不在記憶體中，那么就會產生一條缺頁中斷，當發生缺頁中斷時，如果作業系統記憶體中沒有空閑頁面，那么作業系統必須在記憶體選擇一個頁面將其移出記憶體，以便為即將調入的頁面讓出空間，而用來選擇淘汰哪一頁的規則叫做頁面置換演算法，

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

• 最優演算法在當前頁面中置換最后要訪問的頁面，不幸的是，沒有辦法來判定哪個頁面是最后一個要訪問的，因此實際上該演算法不能使用，然而，它可以作為衡量其他演算法的標準，
• NRU 演算法根據 R 位和 M 位的狀態將頁面氛圍四類，從編號最小的類別中隨機選擇一個頁面，NRU 演算法易于實作，但是性能不是很好，存在更好的演算法，
• FIFO 會跟蹤頁面加載進入記憶體中的順序，并把頁面放入一個鏈表中，有可能洗掉存在時間最長但是還在使用的頁面，因此這個演算法也不是一個很好的選擇，
• 第二次機會演算法是對 FIFO 的一個修改，它會在洗掉頁面之前檢查這個頁面是否仍在使用，如果頁面正在使用，就會進行保留，這個改進大大提高了性能，
• 時鐘 演算法是第二次機會演算法的另外一種實作形式，時鐘演算法和第二次演算法的性能差不多，但是會花費更少的時間來執行演算法，
• LRU 演算法是一個非常優秀的演算法，但是沒有特殊的硬體(TLB)很難實作，如果沒有硬體，就不能使用 LRU 演算法，
• NFU 演算法是一種近似于 LRU 的演算法，它的性能不是非常好，
• 老化 演算法是一種更接近 LRU 演算法的實作，并且可以更好的實作，因此是一個很好的選擇
• 最后兩種演算法都使用了作業集演算法，作業集演算法提供了合理的性能開銷，但是它的實作比較復雜，WSClock 是另外一種變體，它不僅能夠提供良好的性能，而且可以高效地實作，

最好的演算法是老化演算法和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 有不同的級別

• RAID 0 - 無容錯的條帶化磁盤陣列
• RAID 1 - 鏡像和雙工
• RAID 2 - 記憶體式糾錯碼
• RAID 3 - 位元交錯奇偶校驗
• RAID 4 - 塊交錯奇偶校驗
• RAID 5 - 塊交錯分布式奇偶校驗
• RAID 6 - P + Q冗余

IO 篇

作業系統中的時鐘是什么

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

時鐘硬體

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

• 比較簡單的一種時鐘被連接到 110 V 或 220 V 的電源線上，這樣每個電壓周期會產生一個中斷，大概是 50 - 60 HZ，這些時鐘過去一直占據支配地位，
• 另外的一種時鐘由晶體振蕩器、計數器和暫存器組成，示意圖如下所示

這種時鐘稱為可編程時鐘 ，可編程時鐘有兩種模式，一種是 一鍵式(one-shot mode)，當時鐘啟動時，會把存盤器中的值復制到計數器中，然后，每次晶體的振蕩器的脈沖都會使計數器 -1，當計數器變為 0 時，會產生一個中斷，并停止作業，直到軟體再一次顯示啟動，還有一種模式時 方波(square-wave mode) 模式，在這種模式下，當計數器變為 0 并產生中斷后，存盤暫存器的值會自動復制到計數器中，這種周期性的中斷稱為一個時鐘周期，

設備控制器的主要功能

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

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

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

• 接收和識別命令：設備控制器可以接受來自 CPU 的指令，并進行識別，設備控制器內部也會有暫存器，用來存放指令和引數
• 進行資料交換：CPU、控制器和設備之間會進行資料的交換，CPU 通過總線把指令發送給控制器，或從控制器中并行地讀出資料；控制器將資料寫入指定設備，
• 地址識別：每個硬體設備都有自己的地址，設備控制器能夠識別這些不同的地址，來達到控制硬體的目的，此外，為使 CPU 能向暫存器中寫入或者讀取資料，這些暫存器都應具有唯一的地址，
• 差錯檢測：設備控制器還具有對設備傳遞過來的資料進行檢測的功能，

中斷處理程序

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

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

• 非嵌套的中斷處理程式按照順序處理各個中斷，非嵌套的中斷處理程式也是最簡單的中斷處理
• 嵌套的中斷處理程式會處理多個中斷而無需分配優先級
• 可重入的中斷處理程式可使用優先級處理多個中斷
• 簡單優先級中斷處理程式可處理簡單的中斷
• 標準優先級中斷處理程式比低優先級的中斷處理程式在更短的時間能夠處理優先級更高的中斷
• 高優先級 中斷處理程式在短時間能夠處理優先級更高的任務，并直接進入特定的服務例程，
• 優先級分組中斷處理程式能夠處理不同優先級的中斷任務

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

• 保存所有沒有被中斷硬體保存的暫存器
• 為中斷服務程式設定背景關系環境，可能包括設定 TLB、MMU 和頁表，如果不太了解這三個概念，請參考另外一篇文章
• 為中斷服務程式設定堆疊
• 對中斷控制器作出回應，如果不存在集中的中斷控制器，則繼續回應中斷
• 把暫存器從保存它的地方拷貝到行程表中
• 運行中斷服務程式，它會從發出中斷的設備控制器的暫存器中提取資訊
• 作業系統會選擇一個合適的行程來運行，如果中斷造成了一些優先級更高的行程變為就緒態，則選擇運行這些優先級高的行程
• 為行程設定 MMU 背景關系，可能也會需要 TLB，根據實際情況決定
• 加載行程的暫存器，包括 PSW 暫存器
• 開始運行新的行程

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

什么是設備驅動程式

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

什么是 DMA

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

直接記憶體訪問的特點

DMA 方式有如下特點：

• 資料傳送以資料塊為基本單位

• 所傳送的資料從設備直接送入主存，或者從主存直接輸出到設備上

• 僅在傳送一個或多個資料塊的開始和結束時才需 CPU 的干預，而整塊資料的傳送則是在控制器的控制下完成，

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)，想象一下你什么時候會餓？一段時間不吃東西是不是會餓？對于行程來講，最重要的就是資源，如果一段時間沒有獲得資源，那么行程會產生饑餓，這些行程會永遠得不到服務，

我們假設列印機的分配方案是每次都會分配給最小檔案的行程，那么要列印大檔案的行程會永遠得不到服務，導致行程饑餓，行程會無限制的推后，雖然它沒有阻塞，

后記

這篇文章到這里就結束了，后面我會繼續寫關于計算機網路、計算機基礎、Java 相關、Java 架構相關的面試題，

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

如果這篇文章對你有用，歡迎給我的 CSDN 賬號點贊 + 關注哦！！！

我自己肝了六本 PDF，全網傳播超過10w+ ，你需要關注一下我的 CSDN 賬號，私信回復 cxuan ，領取全部 PDF，這些 PDF 如下