重磅干貨，第一時(shí)間送達(dá)
這不是一篇教你如何創(chuàng)建一個(gè)操作系統(tǒng)的文章，相反，這是一篇指導(dǎo)性文章，教你從幾個(gè)方面來理解操作系統(tǒng)。首先你需要知道你為什么要看這篇文章以及為什么要學(xué)習(xí)操作系統(tǒng)。
高清大圖見文末
首先你要搞明白你學(xué)習(xí)操作系統(tǒng)的目的是什么？操作系統(tǒng)的重要性如何？學(xué)習(xí)操作系統(tǒng)會(huì)給我?guī)硎裁?？下面我?huì)從這幾個(gè)方面為你回答下。
操作系統(tǒng)也是一種軟件，但是操作系統(tǒng)是一種非常復(fù)雜的軟件。操作系統(tǒng)提供了幾種抽象模型
這些抽象和我們的日常開發(fā)息息相關(guān)。搞清楚了操作系統(tǒng)是如何抽象的，才能培養(yǎng)我們的抽象性思維和開發(fā)思路。
很多問題都和操作系統(tǒng)相關(guān)，操作系統(tǒng)是解決這些問題的基礎(chǔ)。如果你不學(xué)習(xí)操作系統(tǒng)，可能會(huì)想著從框架層面來解決，那是你了解的還不夠深入，當(dāng)你學(xué)習(xí)了操作系統(tǒng)后，能夠培養(yǎng)你的全局性思維。
學(xué)習(xí)操作系統(tǒng)我們能夠有效的解決并發(fā)問題，并發(fā)幾乎是互聯(lián)網(wǎng)的重中之重了，這也從側(cè)面說明了學(xué)習(xí)操作系統(tǒng)的重要性。
學(xué)習(xí)操作系統(tǒng)的重點(diǎn)不是讓你從頭制造一個(gè)操作系統(tǒng)，而是告訴你「操作系統(tǒng)是如何工作的」，能夠讓你對(duì)計(jì)算機(jī)底層有所了解，打?qū)嵞愕幕A(chǔ)。
相信你一定清楚什么是編程
「Data structures + Algorithms = Programming」
操作系統(tǒng)內(nèi)部會(huì)涉及到眾多的數(shù)據(jù)結(jié)構(gòu)和算法描述，能夠讓你了解算法的基礎(chǔ)上，讓你編寫更優(yōu)秀的程序。
我認(rèn)為可以把計(jì)算機(jī)比作一棟樓
計(jì)算機(jī)的底層相當(dāng)于就是樓的根基，計(jì)算機(jī)應(yīng)用相當(dāng)于就是樓的外形，而操作系統(tǒng)就相當(dāng)于是告訴你大樓的構(gòu)造原理，編寫高質(zhì)量的軟件就相當(dāng)于是告訴你構(gòu)建一個(gè)穩(wěn)定的房子。
在了解操作系統(tǒng)前，你需要先知道一下什么是計(jì)算機(jī)系統(tǒng)：現(xiàn)代計(jì)算機(jī)系統(tǒng)由「一個(gè)或多個(gè)處理器、主存、打印機(jī)、鍵盤、鼠標(biāo)、顯示器、網(wǎng)絡(luò)接口以及各種輸入/輸出設(shè)備構(gòu)成的系統(tǒng)」。這些都屬于硬件的范疇。我們程序員不會(huì)直接和這些硬件打交道，并且每位程序員不可能會(huì)掌握所有計(jì)算機(jī)系統(tǒng)的細(xì)節(jié)。
所以計(jì)算機(jī)科學(xué)家在硬件的基礎(chǔ)之上，安裝了一層軟件，這層軟件能夠根據(jù)用戶輸入的指令達(dá)到控制硬件的效果，從而滿足用戶的需求，這樣的軟件稱為 操作系統(tǒng)，它的任務(wù)就是為用戶程序提供一個(gè)更好、更簡單、更清晰的計(jì)算機(jī)模型。也就是說，操作系統(tǒng)相當(dāng)于是一個(gè)中間層，為用戶層和硬件提供各自的借口，屏蔽了不同應(yīng)用和硬件之間的差異，達(dá)到統(tǒng)一標(biāo)準(zhǔn)的作用。
上面一個(gè)操作系統(tǒng)的簡化圖，最底層是硬件，硬件包括「芯片、電路板、磁盤、鍵盤、顯示器」等我們上面提到的設(shè)備，在硬件之上是軟件。大部分計(jì)算機(jī)有兩種運(yùn)行模式：內(nèi)核態(tài) 和 用戶態(tài)，軟件中最基礎(chǔ)的部分是操作系統(tǒng)，它運(yùn)行在 內(nèi)核態(tài) 中。操作系統(tǒng)具有硬件的訪問權(quán)，可以執(zhí)行機(jī)器能夠運(yùn)行的任何指令。軟件的其余部分運(yùn)行在 用戶態(tài) 下。
在大概了解到操作系統(tǒng)之后，我們先來認(rèn)識(shí)一下硬件都有哪些
計(jì)算機(jī)硬件是計(jì)算機(jī)的重要組成部分，其中包含了 5 個(gè)重要的組成部分：「運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備、輸出設(shè)備」。
運(yùn)算器：運(yùn)算器最主要的功能是對(duì)數(shù)據(jù)和信息進(jìn)行加工和運(yùn)算。它是計(jì)算機(jī)中執(zhí)行算數(shù)和各種邏輯運(yùn)算的部件。運(yùn)算器的基本運(yùn)算包括加、減、乘、除、移位等操作，這些是由 算術(shù)邏輯單元(Arithmetic&logical Unit) 實(shí)現(xiàn)的。而運(yùn)算器主要由算數(shù)邏輯單元和寄存器構(gòu)成。控制器：指按照指定順序改變主電路或控制電路的部件，它主要起到了控制命令執(zhí)行的作用，完成協(xié)調(diào)和指揮整個(gè)計(jì)算機(jī)系統(tǒng)的操作?？刂破魇怯沙绦蛴?jì)數(shù)器、指令寄存器、解碼譯碼器等構(gòu)成。?運(yùn)算器和控制器共同組成了 CPU
?
存儲(chǔ)器：存儲(chǔ)器就是計(jì)算機(jī)的記憶設(shè)備，顧名思義，存儲(chǔ)器可以保存信息。存儲(chǔ)器分為兩種，一種是主存，也就是內(nèi)存，它是 CPU 主要交互對(duì)象，還有一種是外存，比如硬盤軟盤等。下面是現(xiàn)代計(jì)算機(jī)系統(tǒng)的存儲(chǔ)架構(gòu)
輸入設(shè)備：輸入設(shè)備是給計(jì)算機(jī)獲取外部信息的設(shè)備，它主要包括鍵盤和鼠標(biāo)。
輸出設(shè)備：輸出設(shè)備是給用戶呈現(xiàn)根據(jù)輸入設(shè)備獲取的信息經(jīng)過一系列的計(jì)算后得到顯示的設(shè)備，它主要包括顯示器、打印機(jī)等。
這五部分也是馮諾伊曼的體系結(jié)構(gòu)，它認(rèn)為計(jì)算機(jī)必須具有如下功能：
把需要的程序和數(shù)據(jù)送至計(jì)算機(jī)中。必須具有長期記憶程序、數(shù)據(jù)、中間結(jié)果及最終運(yùn)算結(jié)果的能力。能夠完成各種算術(shù)、邏輯運(yùn)算和數(shù)據(jù)傳送等數(shù)據(jù)加工處理的能力。能夠根據(jù)需要控制程序走向，并能根據(jù)指令控制機(jī)器的各部件協(xié)調(diào)操作。能夠按照要求將處理結(jié)果輸出給用戶。
下面是一張 intel 家族產(chǎn)品圖，是一個(gè)詳細(xì)的計(jì)算機(jī)硬件分類，我們?cè)诟鶕?jù)圖中涉及到硬件進(jìn)行介紹
總線(Buses)：在整個(gè)系統(tǒng)中運(yùn)行的是稱為總線的電氣管道的集合，這些總線在組件之間來回傳輸字節(jié)信息。通?？偩€被設(shè)計(jì)成傳送定長的字節(jié)塊，也就是 字(word)。字中的字節(jié)數(shù)（字長）是一個(gè)基本的系統(tǒng)參數(shù)，各個(gè)系統(tǒng)中都不盡相同?，F(xiàn)在大部分的字都是 4 個(gè)字節(jié)（32 位）或者 8 個(gè)字節(jié)（64 位）。I/O 設(shè)備(I/O Devices)：Input/Output 設(shè)備是系統(tǒng)和外部世界的連接。上圖中有四類 I/O 設(shè)備：用于用戶輸入的鍵盤和鼠標(biāo)，用于用戶輸出的顯示器，一個(gè)磁盤驅(qū)動(dòng)用來長時(shí)間的保存數(shù)據(jù)和程序。剛開始的時(shí)候，可執(zhí)行程序就保存在磁盤上。
每個(gè)I/O 設(shè)備連接 I/O 總線都被稱為控制器(controller) 或者是 適配器(Adapter)。控制器和適配器之間的主要區(qū)別在于封裝方式?？刂破魇?I/O 設(shè)備本身或者系統(tǒng)的主印制板電路（通常稱作主板）上的芯片組。而適配器則是一塊插在主板插槽上的卡。無論組織形式如何，它們的最終目的都是彼此交換信息。
主存(Main Memory)，主存是一個(gè)臨時(shí)存儲(chǔ)設(shè)備，而不是永久性存儲(chǔ)，磁盤是 永久性存儲(chǔ) 的設(shè)備。主存既保存程序，又保存處理器執(zhí)行流程所處理的數(shù)據(jù)。從物理組成上說，主存是由一系列 DRAM(dynamic random access memory) 動(dòng)態(tài)隨機(jī)存儲(chǔ)構(gòu)成的集合。邏輯上說，內(nèi)存就是一個(gè)線性的字節(jié)數(shù)組，有它唯一的地址編號(hào)，從 0 開始。一般來說，組成程序的每條機(jī)器指令都由不同數(shù)量的字節(jié)構(gòu)成，C 程序變量相對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的大小根據(jù)類型進(jìn)行變化。比如，在 Linux 的 x86-64 機(jī)器上，short 類型的數(shù)據(jù)需要 2 個(gè)字節(jié)，int 和 float 需要 4 個(gè)字節(jié)，而 long 和 double 需要 8 個(gè)字節(jié)。
處理器(Processor)，CPU(central processing unit) 或者簡單的處理器，是解釋（并執(zhí)行）存儲(chǔ)在主存儲(chǔ)器中的指令的引擎。處理器的核心大小為一個(gè)字的存儲(chǔ)設(shè)備（或寄存器），稱為程序計(jì)數(shù)器(PC)。在任何時(shí)刻，PC 都指向主存中的某條機(jī)器語言指令（即含有該條指令的地址）。
從系統(tǒng)通電開始，直到系統(tǒng)斷電，處理器一直在不斷地執(zhí)行程序計(jì)數(shù)器指向的指令，再更新程序計(jì)數(shù)器，使其指向下一條指令。處理器根據(jù)其指令集體系結(jié)構(gòu)定義的指令模型進(jìn)行操作。在這個(gè)模型中，指令按照嚴(yán)格的順序執(zhí)行，執(zhí)行一條指令涉及執(zhí)行一系列的步驟。處理器從程序計(jì)數(shù)器指向的內(nèi)存中讀取指令，解釋指令中的位，執(zhí)行該指令指示的一些簡單操作，然后更新程序計(jì)數(shù)器以指向下一條指令。指令與指令之間可能連續(xù)，可能不連續(xù)（比如 jmp 指令就不會(huì)順序讀?。?/span>
下面是 CPU 可能執(zhí)行簡單操作的幾個(gè)步驟
加載(Load)：從主存中拷貝一個(gè)字節(jié)或者一個(gè)字到內(nèi)存中，覆蓋寄存器先前的內(nèi)容存儲(chǔ)(Store)：將寄存器中的字節(jié)或字復(fù)制到主存儲(chǔ)器中的某個(gè)位置，從而覆蓋該位置的先前內(nèi)容操作(Operate)：把兩個(gè)寄存器的內(nèi)容復(fù)制到 ALU(Arithmetic logic unit)。把兩個(gè)字進(jìn)行算術(shù)運(yùn)算，并把結(jié)果存儲(chǔ)在寄存器中，重寫寄存器先前的內(nèi)容。?算術(shù)邏輯單元（ALU）是對(duì)數(shù)字二進(jìn)制數(shù)執(zhí)行算術(shù)和按位運(yùn)算的組合數(shù)字電子電路。
?
跳轉(zhuǎn)(jump)：從指令中抽取一個(gè)字，把這個(gè)字復(fù)制到程序計(jì)數(shù)器(PC) 中，覆蓋原來的值關(guān)于進(jìn)程和線程，你需要理解下面這張腦圖中的重點(diǎn)
操作系統(tǒng)中最核心的概念就是 進(jìn)程，進(jìn)程是對(duì)正在運(yùn)行中的程序的一個(gè)抽象。操作系統(tǒng)的其他所有內(nèi)容都是圍繞著進(jìn)程展開的。
在多道程序處理的系統(tǒng)中，CPU 會(huì)在進(jìn)程間快速切換，使每個(gè)程序運(yùn)行幾十或者幾百毫秒。然而，嚴(yán)格意義來說，在某一個(gè)瞬間，CPU 只能運(yùn)行一個(gè)進(jìn)程，然而我們?nèi)绻褧r(shí)間定位為 1 秒內(nèi)的話，它可能運(yùn)行多個(gè)進(jìn)程。這樣就會(huì)讓我們產(chǎn)生并行的錯(cuò)覺。因?yàn)?CPU 執(zhí)行速度很快，進(jìn)程間的換進(jìn)換出也非常迅速，因此我們很難對(duì)多個(gè)并行進(jìn)程進(jìn)行跟蹤。所以，操作系統(tǒng)的設(shè)計(jì)者開發(fā)了用于描述并行的一種概念模型（順序進(jìn)程），使得并行更加容易理解和分析。
一個(gè)進(jìn)程就是一個(gè)正在執(zhí)行的程序的實(shí)例，進(jìn)程也包括程序計(jì)數(shù)器、寄存器和變量的當(dāng)前值。從概念上來說，每個(gè)進(jìn)程都有各自的虛擬 CPU，但是實(shí)際情況是 CPU 會(huì)在各個(gè)進(jìn)程之間進(jìn)行來回切換。
如上圖所示，這是一個(gè)具有 4 個(gè)程序的多道處理程序，在進(jìn)程不斷切換的過程中，程序計(jì)數(shù)器也在不同的變化。
在上圖中，這 4 道程序被抽象為 4 個(gè)擁有各自控制流程（即每個(gè)自己的程序計(jì)數(shù)器）的進(jìn)程，并且每個(gè)程序都獨(dú)立的運(yùn)行。當(dāng)然，實(shí)際上只有一個(gè)物理程序計(jì)數(shù)器，每個(gè)程序要運(yùn)行時(shí)，其邏輯程序計(jì)數(shù)器會(huì)裝載到物理程序計(jì)數(shù)器中。當(dāng)程序運(yùn)行結(jié)束后，其物理程序計(jì)數(shù)器就會(huì)是真正的程序計(jì)數(shù)器，然后再把它放回進(jìn)程的邏輯計(jì)數(shù)器中。
從下圖我們可以看到，在觀察足夠長的一段時(shí)間后，所有的進(jìn)程都運(yùn)行了，「但在任何一個(gè)給定的瞬間僅有一個(gè)進(jìn)程真正運(yùn)行」。
因此，當(dāng)我們說一個(gè) CPU 只能真正一次運(yùn)行一個(gè)進(jìn)程的時(shí)候，即使有 2 個(gè)核（或 CPU），「每一個(gè)核也只能一次運(yùn)行一個(gè)線程」。
由于 CPU 會(huì)在各個(gè)進(jìn)程之間來回快速切換，所以每個(gè)進(jìn)程在 CPU 中的運(yùn)行時(shí)間是無法確定的。并且當(dāng)同一個(gè)進(jìn)程再次在 CPU 中運(yùn)行時(shí)，其在 CPU 內(nèi)部的運(yùn)行時(shí)間往往也是不固定的。
這里的關(guān)鍵思想是認(rèn)識(shí)到一個(gè)進(jìn)程所需的條件，進(jìn)程是某一類特定活動(dòng)的總和，它有程序、輸入輸出以及狀態(tài)。
操作系統(tǒng)需要一些方式來創(chuàng)建進(jìn)程。下面是一些創(chuàng)建進(jìn)程的方式
從技術(shù)上講，在所有這些情況下，讓現(xiàn)有流程執(zhí)行流程是通過創(chuàng)建系統(tǒng)調(diào)用來創(chuàng)建新流程的。該進(jìn)程可能是正在運(yùn)行的用戶進(jìn)程，是從鍵盤或鼠標(biāo)調(diào)用的系統(tǒng)進(jìn)程或批處理程序。這些就是系統(tǒng)調(diào)用創(chuàng)建新進(jìn)程的過程。該系統(tǒng)調(diào)用告訴操作系統(tǒng)創(chuàng)建一個(gè)新進(jìn)程，并直接或間接指示在其中運(yùn)行哪個(gè)程序。
在 UNIX 中，僅有一個(gè)系統(tǒng)調(diào)用來創(chuàng)建一個(gè)新的進(jìn)程，這個(gè)系統(tǒng)調(diào)用就是 fork。這個(gè)調(diào)用會(huì)創(chuàng)建一個(gè)與調(diào)用進(jìn)程相關(guān)的副本。在 fork 后，一個(gè)父進(jìn)程和子進(jìn)程會(huì)有相同的內(nèi)存映像，相同的環(huán)境字符串和相同的打開文件。
在 Windows 中，情況正相反，一個(gè)簡單的 Win32 功能調(diào)用 CreateProcess，會(huì)處理流程創(chuàng)建并將正確的程序加載到新的進(jìn)程中。這個(gè)調(diào)用會(huì)有 10 個(gè)參數(shù)，包括了需要執(zhí)行的程序、輸入給程序的命令行參數(shù)、各種安全屬性、有關(guān)打開的文件是否繼承控制位、優(yōu)先級(jí)信息、進(jìn)程所需要?jiǎng)?chuàng)建的窗口規(guī)格以及指向一個(gè)結(jié)構(gòu)的指針，在該結(jié)構(gòu)中新創(chuàng)建進(jìn)程的信息被返回給調(diào)用者。「在 Windows 中，從一開始父進(jìn)程的地址空間和子進(jìn)程的地址空間就是不同的」。
進(jìn)程在創(chuàng)建之后，它就開始運(yùn)行并做完成任務(wù)。然而，沒有什么事兒是永不停歇的，包括進(jìn)程也一樣。進(jìn)程早晚會(huì)發(fā)生終止，但是通常是由于以下情況觸發(fā)的
正常退出(自愿的) ：多數(shù)進(jìn)程是由于完成了工作而終止。當(dāng)編譯器完成了所給定程序的編譯之后，編譯器會(huì)執(zhí)行一個(gè)系統(tǒng)調(diào)用告訴操作系統(tǒng)它完成了工作。這個(gè)調(diào)用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。錯(cuò)誤退出(自愿的)：比如執(zhí)行一條不存在的命令，于是編譯器就會(huì)提醒并退出。嚴(yán)重錯(cuò)誤(非自愿的)被其他進(jìn)程殺死(非自愿的) ：某個(gè)進(jìn)程執(zhí)行系統(tǒng)調(diào)用告訴操作系統(tǒng)殺死某個(gè)進(jìn)程。在 UNIX 中，這個(gè)系統(tǒng)調(diào)用是 kill。在 Win32 中對(duì)應(yīng)的函數(shù)是 TerminateProcess（注意不是系統(tǒng)調(diào)用）。在一些系統(tǒng)中，當(dāng)一個(gè)進(jìn)程創(chuàng)建了其他進(jìn)程后，父進(jìn)程和子進(jìn)程就會(huì)以某種方式進(jìn)行關(guān)聯(lián)。子進(jìn)程它自己就會(huì)創(chuàng)建更多進(jìn)程，從而形成一個(gè)進(jìn)程層次結(jié)構(gòu)。
在 UNIX 中，進(jìn)程和它的所有子進(jìn)程以及子進(jìn)程的子進(jìn)程共同組成一個(gè)進(jìn)程組。當(dāng)用戶從鍵盤中發(fā)出一個(gè)信號(hào)后，該信號(hào)被發(fā)送給當(dāng)前與鍵盤相關(guān)的進(jìn)程組中的所有成員（它們通常是在當(dāng)前窗口創(chuàng)建的所有活動(dòng)進(jìn)程）。每個(gè)進(jìn)程可以分別捕獲該信號(hào)、忽略該信號(hào)或采取默認(rèn)的動(dòng)作，即被信號(hào) kill 掉。整個(gè)操作系統(tǒng)中所有的進(jìn)程都隸屬于一個(gè)單個(gè)以 init 為根的進(jìn)程樹。
相反，Windows 中沒有進(jìn)程層次的概念，Windows 中所有進(jìn)程都是平等的，唯一類似于層次結(jié)構(gòu)的是在創(chuàng)建進(jìn)程的時(shí)候，父進(jìn)程得到一個(gè)特別的令牌（稱為句柄），該句柄可以用來控制子進(jìn)程。然而，這個(gè)令牌可能也會(huì)移交給別的操作系統(tǒng)，這樣就不存在層次結(jié)構(gòu)了。而在 UNIX 中，進(jìn)程不能剝奪其子進(jìn)程的 進(jìn)程權(quán)。（這樣看來，還是 Windows 比較渣）。
盡管每個(gè)進(jìn)程是一個(gè)獨(dú)立的實(shí)體，有其自己的程序計(jì)數(shù)器和內(nèi)部狀態(tài)，但是，進(jìn)程之間仍然需要相互幫助。當(dāng)一個(gè)進(jìn)程開始運(yùn)行時(shí)，它可能會(huì)經(jīng)歷下面這幾種狀態(tài)
圖中會(huì)涉及三種狀態(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)，除非某種外部事件發(fā)生，否則進(jìn)程不能運(yùn)行操作系統(tǒng)為了執(zhí)行進(jìn)程間的切換，會(huì)維護(hù)著一張表，這張表就是 進(jìn)程表(process table)。每個(gè)進(jìn)程占用一個(gè)進(jìn)程表項(xiàng)。該表項(xiàng)包含了進(jìn)程狀態(tài)的重要信息，包括程序計(jì)數(shù)器、堆棧指針、內(nèi)存分配狀況、所打開文件的狀態(tài)、賬號(hào)和調(diào)度信息，以及其他在進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)換到就緒態(tài)或阻塞態(tài)時(shí)所必須保存的信息。
下面展示了一個(gè)典型系統(tǒng)中的關(guān)鍵字段
典型的進(jìn)程表表項(xiàng)中的一些字段
第一列內(nèi)容與進(jìn)程管理有關(guān)，第二列內(nèi)容與 存儲(chǔ)管理有關(guān)，第三列內(nèi)容與文件管理有關(guān)。
現(xiàn)在我們應(yīng)該對(duì)進(jìn)程表有個(gè)大致的了解了，就可以在對(duì)單個(gè) CPU 上如何運(yùn)行多個(gè)順序進(jìn)程的錯(cuò)覺做更多的解釋。與每一 I/O 類相關(guān)聯(lián)的是一個(gè)稱作 中斷向量(interrupt vector) 的位置（靠近內(nèi)存底部的固定區(qū)域）。它包含中斷服務(wù)程序的入口地址。假設(shè)當(dāng)一個(gè)磁盤中斷發(fā)生時(shí)，用戶進(jìn)程 3 正在運(yùn)行，則中斷硬件將程序計(jì)數(shù)器、程序狀態(tài)字、有時(shí)還有一個(gè)或多個(gè)寄存器壓入堆棧，計(jì)算機(jī)隨即跳轉(zhuǎn)到中斷向量所指示的地址。這就是硬件所做的事情。然后軟件就隨即接管一切剩余的工作。
當(dāng)中斷結(jié)束后，操作系統(tǒng)會(huì)調(diào)用一個(gè) C 程序來處理中斷剩下的工作。在完成剩下的工作后，會(huì)使某些進(jìn)程就緒，接著調(diào)用調(diào)度程序，決定隨后運(yùn)行哪個(gè)進(jìn)程。然后將控制權(quán)轉(zhuǎn)移給一段匯編語言代碼，為當(dāng)前的進(jìn)程裝入寄存器值以及內(nèi)存映射并啟動(dòng)該進(jìn)程運(yùn)行，下面顯示了中斷處理和調(diào)度的過程。
硬件壓入堆棧程序計(jì)數(shù)器等
硬件從中斷向量裝入新的程序計(jì)數(shù)器
匯編語言過程保存寄存器的值
匯編語言過程設(shè)置新的堆棧
C 中斷服務(wù)器運(yùn)行（典型的讀和緩存寫入）
調(diào)度器決定下面哪個(gè)程序先運(yùn)行
C 過程返回至匯編代碼
匯編語言過程開始運(yùn)行新的當(dāng)前進(jìn)程
一個(gè)進(jìn)程在執(zhí)行過程中可能被中斷數(shù)千次，但關(guān)鍵每次中斷后，被中斷的進(jìn)程都返回到與中斷發(fā)生前完全相同的狀態(tài)。
在傳統(tǒng)的操作系統(tǒng)中，每個(gè)進(jìn)程都有一個(gè)地址空間和一個(gè)控制線程。事實(shí)上，這是大部分進(jìn)程的定義。不過，在許多情況下，經(jīng)常存在同一地址空間中運(yùn)行多個(gè)控制線程的情形，這些線程就像是分離的進(jìn)程。下面我們就著重探討一下什么是線程
或許這個(gè)疑問也是你的疑問，為什么要在進(jìn)程的基礎(chǔ)上再創(chuàng)建一個(gè)線程的概念，準(zhǔn)確的說，這其實(shí)是進(jìn)程模型和線程模型的討論，回答這個(gè)問題，可能需要分三步來回答
更輕量級(jí)，由于線程更輕，所以它比進(jìn)程更容易創(chuàng)建，也更容易撤銷。在許多系統(tǒng)中，創(chuàng)建一個(gè)線程要比創(chuàng)建一個(gè)進(jìn)程快 10 - 100 倍。進(jìn)程中擁有一個(gè)執(zhí)行的線程，通常簡寫為 線程(thread)。線程會(huì)有程序計(jì)數(shù)器，用來記錄接著要執(zhí)行哪一條指令；線程實(shí)際上 CPU 上調(diào)度執(zhí)行的實(shí)體。
下圖我們可以看到三個(gè)傳統(tǒng)的進(jìn)程，每個(gè)進(jìn)程有自己的地址空間和單個(gè)控制線程。每個(gè)線程都在不同的地址空間中運(yùn)行
下圖中，我們可以看到有一個(gè)進(jìn)程三個(gè)線程的情況。每個(gè)線程都在相同的地址空間中運(yùn)行。
線程不像是進(jìn)程那樣具備較強(qiáng)的獨(dú)立性。同一個(gè)進(jìn)程中的所有線程都會(huì)有完全一樣的地址空間，這意味著它們也共享同樣的全局變量。由于每個(gè)線程都可以訪問進(jìn)程地址空間內(nèi)每個(gè)內(nèi)存地址，「因此一個(gè)線程可以讀取、寫入甚至擦除另一個(gè)線程的堆?！?/strong>。線程之間除了共享同一內(nèi)存空間外，還具有如下不同的內(nèi)容
上圖左邊的是同一個(gè)進(jìn)程中每個(gè)線程共享的內(nèi)容，上圖右邊是每個(gè)線程中的內(nèi)容。也就是說左邊的列表是進(jìn)程的屬性，右邊的列表是線程的屬性。
「線程之間的狀態(tài)轉(zhuǎn)換和進(jìn)程之間的狀態(tài)轉(zhuǎn)換是一樣的」。
每個(gè)線程都會(huì)有自己的堆棧，如下圖所示
進(jìn)程通常會(huì)從當(dāng)前的某個(gè)單線程開始，然后這個(gè)線程通過調(diào)用一個(gè)庫函數(shù)（比如 thread_create）創(chuàng)建新的線程。線程創(chuàng)建的函數(shù)會(huì)要求指定新創(chuàng)建線程的名稱。創(chuàng)建的線程通常都返回一個(gè)線程標(biāo)識(shí)符，該標(biāo)識(shí)符就是新線程的名字。
當(dāng)一個(gè)線程完成工作后，可以通過調(diào)用一個(gè)函數(shù)（比如 thread_exit）來退出。緊接著線程消失，狀態(tài)變?yōu)榻K止，不能再進(jìn)行調(diào)度。在某些線程的運(yùn)行過程中，可以通過調(diào)用函數(shù)例如 thread_join ，表示一個(gè)線程可以等待另一個(gè)線程退出。這個(gè)過程阻塞調(diào)用線程直到等待特定的線程退出。在這種情況下，線程的創(chuàng)建和終止非常類似于進(jìn)程的創(chuàng)建和終止。
另一個(gè)常見的線程是調(diào)用 thread_yield，它允許線程自動(dòng)放棄 CPU 從而讓另一個(gè)線程運(yùn)行。這樣一個(gè)調(diào)用還是很重要的，因?yàn)椴煌谶M(jìn)程，線程是無法利用時(shí)鐘中斷強(qiáng)制讓線程讓出 CPU 的。
POSIX 線程 通常稱為 pthreads是一種獨(dú)立于語言而存在的執(zhí)行模型，以及并行執(zhí)行模型。
它允許程序控制時(shí)間上重疊的多個(gè)不同的工作流程。每個(gè)工作流程都稱為一個(gè)線程，可以通過調(diào)用 POSIX Threads API 來實(shí)現(xiàn)對(duì)這些流程的創(chuàng)建和控制?？梢园阉斫鉃榫€程的標(biāo)準(zhǔn)。
?POSIX Threads 的實(shí)現(xiàn)在許多類似且符合POSIX的操作系統(tǒng)上可用，例如 「FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris」，它在現(xiàn)有 Windows API 之上實(shí)現(xiàn)了「pthread」。
IEEE 是世界上最大的技術(shù)專業(yè)組織，致力于為人類的利益而發(fā)展技術(shù)。
?
| 線程調(diào)用 | 描述 |
|---|---|
| pthread_create | 創(chuàng)建一個(gè)新線程 |
| pthread_exit | 結(jié)束調(diào)用的線程 |
| pthread_join | 等待一個(gè)特定的線程退出 |
| pthread_yield | 釋放 CPU 來運(yùn)行另外一個(gè)線程 |
| pthread_attr_init | 創(chuàng)建并初始化一個(gè)線程的屬性結(jié)構(gòu) |
| pthread_attr_destory | 刪除一個(gè)線程的屬性結(jié)構(gòu) |
所有的 Pthreads 都有特定的屬性，每一個(gè)都含有標(biāo)識(shí)符、一組寄存器（包括程序計(jì)數(shù)器）和一組存儲(chǔ)在結(jié)構(gòu)中的屬性。這個(gè)屬性包括堆棧大小、調(diào)度參數(shù)以及其他線程需要的項(xiàng)目。
主要有三種實(shí)現(xiàn)方式
下面我們分開討論一下
第一種方法是把整個(gè)線程包放在用戶空間中，內(nèi)核對(duì)線程一無所知，它不知道線程的存在。所有的這類實(shí)現(xiàn)都有同樣的通用結(jié)構(gòu)
在用戶空間中實(shí)現(xiàn)多線程
線程在運(yùn)行時(shí)系統(tǒng)之上運(yùn)行，運(yùn)行時(shí)系統(tǒng)是管理線程過程的集合，包括前面提到的四個(gè)過程：pthread_create, pthread_exit, pthread_join 和 pthread_yield。
當(dāng)某個(gè)線程希望創(chuàng)建一個(gè)新線程或撤銷一個(gè)已有線程時(shí)，它會(huì)進(jìn)行一個(gè)系統(tǒng)調(diào)用，這個(gè)系統(tǒng)調(diào)用通過對(duì)線程表的更新來完成線程創(chuàng)建或銷毀工作。
在內(nèi)核中實(shí)現(xiàn)多線程
內(nèi)核中的線程表持有每個(gè)線程的寄存器、狀態(tài)和其他信息。這些信息和用戶空間中的線程信息相同，但是位置卻被放在了內(nèi)核中而不是用戶空間中。另外，內(nèi)核還維護(hù)了一張進(jìn)程表用來跟蹤系統(tǒng)狀態(tài)。
所有能夠阻塞的調(diào)用都會(huì)通過系統(tǒng)調(diào)用的方式來實(shí)現(xiàn)，當(dāng)一個(gè)線程阻塞時(shí)，內(nèi)核可以進(jìn)行選擇，是運(yùn)行在同一個(gè)進(jìn)程中的另一個(gè)線程（如果有就緒線程的話）還是運(yùn)行一個(gè)另一個(gè)進(jìn)程中的線程。但是在用戶實(shí)現(xiàn)中，運(yùn)行時(shí)系統(tǒng)始終運(yùn)行自己的線程，直到內(nèi)核剝奪它的 CPU 時(shí)間片（或者沒有可運(yùn)行的線程存在了）為止。
結(jié)合用戶空間和內(nèi)核空間的優(yōu)點(diǎn)，設(shè)計(jì)人員采用了一種內(nèi)核級(jí)線程的方式，然后將用戶級(jí)線程與某些或者全部內(nèi)核線程多路復(fù)用起來
用戶線程與內(nèi)核線程的多路復(fù)用
在這種模型中，編程人員可以自由控制用戶線程和內(nèi)核線程的數(shù)量，具有很大的靈活度。采用這種方法，內(nèi)核只識(shí)別內(nèi)核級(jí)線程，并對(duì)其進(jìn)行調(diào)度。其中一些內(nèi)核級(jí)線程會(huì)被多個(gè)用戶級(jí)線程多路復(fù)用。
進(jìn)程是需要頻繁的和其他進(jìn)程進(jìn)行交流的。下面我們會(huì)一起討論有關(guān) 進(jìn)程間通信(Inter Process Communication, IPC) 的問題。大致來說，進(jìn)程間的通信機(jī)制可以分為 6 種
下面我們分別對(duì)其進(jìn)行概述
信號(hào)是 UNIX 系統(tǒng)最先開始使用的進(jìn)程間通信機(jī)制，因?yàn)?Linux 是繼承于 UNIX 的，所以 Linux 也支持信號(hào)機(jī)制，通過向一個(gè)或多個(gè)進(jìn)程發(fā)送異步事件信號(hào)來實(shí)現(xiàn)，信號(hào)可以從鍵盤或者訪問不存在的位置等地方產(chǎn)生；信號(hào)通過 shell 將任務(wù)發(fā)送給子進(jìn)程。
你可以在 Linux 系統(tǒng)上輸入 kill -l 來列出系統(tǒng)使用的信號(hào)，下面是我提供的一些信號(hào)
進(jìn)程可以選擇忽略發(fā)送過來的信號(hào)，但是有兩個(gè)是不能忽略的：SIGSTOP 和 SIGKILL 信號(hào)。SIGSTOP 信號(hào)會(huì)通知當(dāng)前正在運(yùn)行的進(jìn)程執(zhí)行關(guān)閉操作，SIGKILL 信號(hào)會(huì)通知當(dāng)前進(jìn)程應(yīng)該被殺死。除此之外，進(jìn)程可以選擇它想要處理的信號(hào)，進(jìn)程也可以選擇阻止信號(hào)，如果不阻止，可以選擇自行處理，也可以選擇進(jìn)行內(nèi)核處理。如果選擇交給內(nèi)核進(jìn)行處理，那么就執(zhí)行默認(rèn)處理。
操作系統(tǒng)會(huì)中斷目標(biāo)程序的進(jìn)程來向其發(fā)送信號(hào)、在任何非原子指令中，執(zhí)行都可以中斷，如果進(jìn)程已經(jīng)注冊(cè)了新號(hào)處理程序，那么就執(zhí)行進(jìn)程，如果沒有注冊(cè)，將采用默認(rèn)處理的方式。
Linux 系統(tǒng)中的進(jìn)程可以通過建立管道 pipe 進(jìn)行通信
在兩個(gè)進(jìn)程之間，可以建立一個(gè)通道，一個(gè)進(jìn)程向這個(gè)通道里寫入字節(jié)流，另一個(gè)進(jìn)程從這個(gè)管道中讀取字節(jié)流。管道是同步的，當(dāng)進(jìn)程嘗試從空管道讀取數(shù)據(jù)時(shí)，該進(jìn)程會(huì)被阻塞，直到有可用數(shù)據(jù)為止。shell 中的管線 pipelines 就是用管道實(shí)現(xiàn)的，當(dāng) shell 發(fā)現(xiàn)輸出
sort <f | head它會(huì)創(chuàng)建兩個(gè)進(jìn)程，一個(gè)是 sort，一個(gè)是 head，sort，會(huì)在這兩個(gè)應(yīng)用程序之間建立一個(gè)管道使得 sort 進(jìn)程的標(biāo)準(zhǔn)輸出作為 head 程序的標(biāo)準(zhǔn)輸入。sort 進(jìn)程產(chǎn)生的輸出就不用寫到文件中了，如果管道滿了系統(tǒng)會(huì)停止 sort 以等待 head 讀出數(shù)據(jù)
管道實(shí)際上就是 |，兩個(gè)應(yīng)用程序不知道有管道的存在，一切都是由 shell 管理和控制的。
兩個(gè)進(jìn)程之間還可以通過共享內(nèi)存進(jìn)行進(jìn)程間通信，其中兩個(gè)或者多個(gè)進(jìn)程可以訪問公共內(nèi)存空間。兩個(gè)進(jìn)程的共享工作是通過共享內(nèi)存完成的，一個(gè)進(jìn)程所作的修改可以對(duì)另一個(gè)進(jìn)程可見(很像線程間的通信)。
在使用共享內(nèi)存前，需要經(jīng)過一系列的調(diào)用流程，流程如下
(shmget())(shmat())(shmdt())(shmctl())先入先出隊(duì)列 FIFO 通常被稱為 命名管道(Named Pipes)，命名管道的工作方式與常規(guī)管道非常相似，但是確實(shí)有一些明顯的區(qū)別。未命名的管道沒有備份文件：操作系統(tǒng)負(fù)責(zé)維護(hù)內(nèi)存中的緩沖區(qū)，用來將字節(jié)從寫入器傳輸?shù)阶x取器。一旦寫入或者輸出終止的話，緩沖區(qū)將被回收，傳輸?shù)臄?shù)據(jù)會(huì)丟失。相比之下，命名管道具有支持文件和獨(dú)特 API ，命名管道在文件系統(tǒng)中作為設(shè)備的專用文件存在。當(dāng)所有的進(jìn)程通信完成后，命名管道將保留在文件系統(tǒng)中以備后用。命名管道具有嚴(yán)格的 FIFO 行為
寫入的第一個(gè)字節(jié)是讀取的第一個(gè)字節(jié)，寫入的第二個(gè)字節(jié)是讀取的第二個(gè)字節(jié)，依此類推。
一聽到消息隊(duì)列這個(gè)名詞你可能不知道是什么意思，消息隊(duì)列是用來描述內(nèi)核尋址空間內(nèi)的內(nèi)部鏈接列表?？梢园磶追N不同的方式將消息按順序發(fā)送到隊(duì)列并從隊(duì)列中檢索消息。每個(gè)消息隊(duì)列由 IPC 標(biāo)識(shí)符唯一標(biāo)識(shí)。消息隊(duì)列有兩種模式，一種是嚴(yán)格模式， 嚴(yán)格模式就像是 FIFO 先入先出隊(duì)列似的，消息順序發(fā)送，順序讀取。還有一種模式是 非嚴(yán)格模式，消息的順序性不是非常重要。
還有一種管理兩個(gè)進(jìn)程間通信的是使用 socket，socket 提供端到端的雙相通信。一個(gè)套接字可以與一個(gè)或多個(gè)進(jìn)程關(guān)聯(lián)。就像管道有命令管道和未命名管道一樣，套接字也有兩種模式，套接字一般用于兩個(gè)進(jìn)程之間的網(wǎng)絡(luò)通信，網(wǎng)絡(luò)套接字需要來自諸如TCP（傳輸控制協(xié)議）或較低級(jí)別UDP（用戶數(shù)據(jù)報(bào)協(xié)議）等基礎(chǔ)協(xié)議的支持。
套接字有以下幾種分類
順序包套接字(Sequential Packet Socket)：此類套接字為最大長度固定的數(shù)據(jù)報(bào)提供可靠的連接。此連接是雙向的并且是順序的。數(shù)據(jù)報(bào)套接字(Datagram Socket)：數(shù)據(jù)包套接字支持雙向數(shù)據(jù)流。數(shù)據(jù)包套接字接受消息的順序與發(fā)送者可能不同。流式套接字(Stream Socket)：流套接字的工作方式類似于電話對(duì)話，提供雙向可靠的數(shù)據(jù)流。原始套接字(Raw Socket)：可以使用原始套接字訪問基礎(chǔ)通信協(xié)議。當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)，會(huì)頻繁的有很多進(jìn)程或者線程來同時(shí)競爭 CPU 時(shí)間片。當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程/線程處于就緒狀態(tài)時(shí)，就會(huì)發(fā)生這種情況。如果只有一個(gè) CPU 可用，那么必須選擇接下來哪個(gè)進(jìn)程/線程可以運(yùn)行。操作系統(tǒng)中有一個(gè)叫做 調(diào)度程序(scheduler) 的角色存在，它就是做這件事兒的，該程序使用的算法叫做 調(diào)度算法(scheduling algorithm) 。
毫無疑問，不同的環(huán)境下需要不同的調(diào)度算法。之所以出現(xiàn)這種情況，是因?yàn)椴煌膽?yīng)用程序和不同的操作系統(tǒng)有不同的目標(biāo)。也就是說，在不同的系統(tǒng)中，調(diào)度程序的優(yōu)化也是不同的。這里有必要?jiǎng)澐殖鋈N環(huán)境
批處理(Batch) : 商業(yè)領(lǐng)域交互式(Interactive)：交互式用戶環(huán)境實(shí)時(shí)(Real time)現(xiàn)在讓我們把目光從一般性的調(diào)度轉(zhuǎn)換為特定的調(diào)度算法。下面我們會(huì)探討在批處理中的調(diào)度。
最簡單的非搶占式調(diào)度算法的設(shè)計(jì)就是 先來先服務(wù)(first-come,first-serverd)。當(dāng)?shù)谝粋€(gè)任務(wù)從外部進(jìn)入系統(tǒng)時(shí)，將會(huì)立即啟動(dòng)并允許運(yùn)行任意長的時(shí)間。它不會(huì)因?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í)，它會(huì)像一個(gè)新到達(dá)的任務(wù)，會(huì)排在隊(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)。
批處理中，第二種調(diào)度算法是 最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時(shí)間已知。例如，一家保險(xiǎn)公司，因?yàn)槊刻煲鲱愃频墓ぷ?，所以人們可以相?dāng)精確地預(yù)測(cè)處理 1000 個(gè)索賠的一批作業(yè)需要多長時(shí)間。當(dāng)輸入隊(duì)列中有若干個(gè)同等重要的作業(yè)被啟動(dòng)時(shí)，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法
?需要注意的是，在所有的進(jìn)程都可以運(yùn)行的情況下，最短作業(yè)優(yōu)先的算法才是最優(yōu)的。
?
最短作業(yè)優(yōu)先的搶占式版本被稱作為 最短剩余時(shí)間優(yōu)先(Shortest Remaining Time Next) 算法。使用這個(gè)算法，調(diào)度程序總是選擇剩余運(yùn)行時(shí)間最短的那個(gè)進(jìn)程運(yùn)行。
交互式系統(tǒng)中在個(gè)人計(jì)算機(jī)、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來探討一下交互式調(diào)度
一種最古老、最簡單、最公平并且最廣泛使用的算法就是 輪詢算法(round-robin)。每個(gè)進(jìn)程都會(huì)被分配一個(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。
輪詢調(diào)度假設(shè)了所有的進(jìn)程是同等重要的。但事實(shí)情況可能不是這樣。例如，在一所大學(xué)中的等級(jí)制度，首先是院長，然后是教授、秘書、后勤人員，最后是學(xué)生。這種將外部情況考慮在內(nèi)就實(shí)現(xiàn)了優(yōu)先級(jí)調(diào)度(priority scheduling)
它的基本思想很明確，每個(gè)進(jìn)程都被賦予一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)高的進(jìn)程優(yōu)先運(yùn)行。
最早使用優(yōu)先級(jí)調(diào)度的系統(tǒng)是 CTSS(Compatible TimeSharing System)。CTSS 在每次切換前都需要將當(dāng)前進(jìn)程換出到磁盤，并從磁盤上讀入一個(gè)新進(jìn)程。為 CPU 密集型進(jìn)程設(shè)置較長的時(shí)間片比頻繁地分給他們很短的時(shí)間要更有效（減少交換次數(shù)）。另一方面，如前所述，長時(shí)間片的進(jìn)程又會(huì)影響到響應(yīng)時(shí)間，解決辦法是設(shè)置優(yōu)先級(jí)類。屬于最高優(yōu)先級(jí)的進(jìn)程運(yùn)行一個(gè)時(shí)間片，次高優(yōu)先級(jí)進(jìn)程運(yùn)行 2 個(gè)時(shí)間片，再下面一級(jí)運(yùn)行 4 個(gè)時(shí)間片，以此類推。當(dāng)一個(gè)進(jìn)程用完分配的時(shí)間片后，它被移到下一類。
最短進(jìn)程優(yōu)先是根據(jù)進(jìn)程過去的行為進(jìn)行推測(cè)，并執(zhí)行估計(jì)運(yùn)行時(shí)間最短的那一個(gè)。假設(shè)每個(gè)終端上每條命令的預(yù)估運(yùn)行時(shí)間為 T0，現(xiàn)在假設(shè)測(cè)量到其下一次運(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。
一種完全不同的調(diào)度方法是對(duì)用戶做出明確的性能保證。一種實(shí)際而且容易實(shí)現(xiàn)的保證是：若用戶工作時(shí)有 n 個(gè)用戶登錄，則每個(gè)用戶將獲得 CPU 處理能力的 1/n。類似地，在一個(gè)有 n 個(gè)進(jìn)程運(yùn)行的單用戶系統(tǒng)中，若所有的進(jìn)程都等價(jià)，則每個(gè)進(jìn)程將獲得 1/n 的 CPU 時(shí)間。
對(duì)用戶進(jìn)行承諾并在隨后兌現(xiàn)承諾是一件好事，不過很難實(shí)現(xiàn)。但是存在著一種簡單的方式，有一種既可以給出預(yù)測(cè)結(jié)果而又有一種比較簡單的實(shí)現(xiàn)方式的算法，就是 彩票調(diào)度(lottery scheduling)算法。
其基本思想是為進(jìn)程提供各種系統(tǒng)資源（例如 CPU 時(shí)間）的彩票。當(dāng)做出一個(gè)調(diào)度決策的時(shí)候，就隨機(jī)抽出一張彩票，擁有彩票的進(jìn)程將獲得該資源。在應(yīng)用到 CPU 調(diào)度時(shí)，系統(tǒng)可以每秒持有 50 次抽獎(jiǎng)，每個(gè)中獎(jiǎng)?wù)邔@得比如 20 毫秒的 CPU 時(shí)間作為獎(jiǎng)勵(lì)。
到目前為止，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身，而不用考慮該進(jìn)程的擁有者是誰。結(jié)果是，如果用戶 1 啟動(dòng)了 9 個(gè)進(jìn)程，而用戶 2 啟動(dòng)了一個(gè)進(jìn)程，使用輪轉(zhuǎn)或相同優(yōu)先級(jí)調(diào)度算法，那么用戶 1 將得到 90 % 的 CPU 時(shí)間，而用戶 2 將之得到 10 % 的 CPU 時(shí)間。
為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會(huì)把進(jìn)程的擁有者考慮在內(nèi)。在這種模型下，每個(gè)用戶都會(huì)分配一些CPU 時(shí)間，而調(diào)度程序會(huì)選擇進(jìn)程并強(qiáng)制執(zhí)行。因此如果兩個(gè)用戶每個(gè)都會(huì)有 50% 的 CPU 時(shí)間片保證，那么無論一個(gè)用戶有多少個(gè)進(jìn)程，都將獲得相同的 CPU 份額。
實(shí)時(shí)系統(tǒng)(real-time) 是一個(gè)時(shí)間扮演了重要作用的系統(tǒng)。實(shí)時(shí)系統(tǒng)可以分為兩類，硬實(shí)時(shí)(hard real time) 和 軟實(shí)時(shí)(soft real time) 系統(tǒng)，前者意味著必須要滿足絕對(duì)的截止時(shí)間；后者的含義是雖然不希望偶爾錯(cuò)失截止時(shí)間，但是可以容忍。
實(shí)時(shí)系統(tǒng)中的事件可以按照響應(yīng)方式進(jìn)一步分類為周期性(以規(guī)則的時(shí)間間隔發(fā)生)事件或 非周期性(發(fā)生時(shí)間不可預(yù)知)事件。一個(gè)系統(tǒng)可能要響應(yīng)多個(gè)周期性事件流，根據(jù)每個(gè)事件處理所需的時(shí)間，可能甚至無法處理所有事件。例如，如果有 m 個(gè)周期事件，事件 i 以周期 Pi 發(fā)生，并需要 Ci 秒 CPU 時(shí)間處理一個(gè)事件，那么可以處理負(fù)載的條件是
只有滿足這個(gè)條件的實(shí)時(shí)系統(tǒng)稱為可調(diào)度的，這意味著它實(shí)際上能夠被實(shí)現(xiàn)。一個(gè)不滿足此檢驗(yàn)標(biāo)準(zhǔn)的進(jìn)程不能被調(diào)度，因?yàn)檫@些進(jìn)程共同需要的 CPU 時(shí)間總和大于 CPU 能提供的時(shí)間。
下面我們來了解一下內(nèi)存管理，你需要知道的知識(shí)點(diǎn)如下
如果要使多個(gè)應(yīng)用程序同時(shí)運(yùn)行在內(nèi)存中，必須要解決兩個(gè)問題：保護(hù)和 重定位。第一種解決方式是用保護(hù)密鑰標(biāo)記內(nèi)存塊，并將執(zhí)行過程的密鑰與提取的每個(gè)存儲(chǔ)字的密鑰進(jìn)行比較。這種方式只能解決第一種問題（破壞操作系統(tǒng)），但是不能解決多進(jìn)程在內(nèi)存中同時(shí)運(yùn)行的問題。
還有一種更好的方式是創(chuàng)造一個(gè)存儲(chǔ)器抽象：地址空間(the address space)。就像進(jìn)程的概念創(chuàng)建了一種抽象的 CPU 來運(yùn)行程序，地址空間也創(chuàng)建了一種抽象內(nèi)存供程序使用。
最簡單的辦法是使用動(dòng)態(tài)重定位(dynamic relocation)技術(shù)，它就是通過一種簡單的方式將每個(gè)進(jìn)程的地址空間映射到物理內(nèi)存的不同區(qū)域。還有一種方式是使用基址寄存器和變址寄存器。
每當(dāng)進(jìn)程引用內(nèi)存以獲取指令或讀取、寫入數(shù)據(jù)時(shí)，CPU 都會(huì)自動(dòng)將基址值添加到進(jìn)程生成的地址中，然后再將其發(fā)送到內(nèi)存總線上。同時(shí)，它檢查程序提供的地址是否大于或等于變址寄存器 中的值。如果程序提供的地址要超過變址寄存器的范圍，那么會(huì)產(chǎn)生錯(cuò)誤并中止訪問。
在程序運(yùn)行過程中，經(jīng)常會(huì)出現(xiàn)內(nèi)存不足的問題。
針對(duì)上面內(nèi)存不足的問題，提出了兩種處理方式：最簡單的一種方式就是交換(swapping)技術(shù)，即把一個(gè)進(jìn)程完整的調(diào)入內(nèi)存，然后再內(nèi)存中運(yùn)行一段時(shí)間，再把它放回磁盤?？臻e進(jìn)程會(huì)存儲(chǔ)在磁盤中，所以這些進(jìn)程在沒有運(yùn)行時(shí)不會(huì)占用太多內(nèi)存。另外一種策略叫做虛擬內(nèi)存(virtual memory)，虛擬內(nèi)存技術(shù)能夠允許應(yīng)用程序部分的運(yùn)行在內(nèi)存中。下面我們首先先探討一下交換
下面是一個(gè)交換過程
剛開始的時(shí)候，只有進(jìn)程 A 在內(nèi)存中，然后從創(chuàng)建進(jìn)程 B 和進(jìn)程 C 或者從磁盤中把它們換入內(nèi)存，然后在圖 d 中，A 被換出內(nèi)存到磁盤中，最后 A 重新進(jìn)來。因?yàn)閳D g 中的進(jìn)程 A 現(xiàn)在到了不同的位置，所以在裝載過程中需要被重新定位，或者在交換程序時(shí)通過軟件來執(zhí)行；或者在程序執(zhí)行期間通過硬件來重定位?；芳拇嫫骱妥冎芳拇嫫骶瓦m用于這種情況。
交換在內(nèi)存創(chuàng)建了多個(gè) 空閑區(qū)(hole)，內(nèi)存會(huì)把所有的空閑區(qū)盡可能向下移動(dòng)合并成為一個(gè)大的空閑區(qū)。這項(xiàng)技術(shù)稱為內(nèi)存緊縮(memory compaction)。但是這項(xiàng)技術(shù)通常不會(huì)使用，因?yàn)檫@項(xiàng)技術(shù)會(huì)消耗很多 CPU 時(shí)間。
在進(jìn)行內(nèi)存動(dòng)態(tài)分配時(shí)，操作系統(tǒng)必須對(duì)其進(jìn)行管理。大致上說，有兩種監(jiān)控內(nèi)存使用的方式
位圖(bitmap)空閑列表(free lists)使用位圖方法時(shí)，內(nèi)存可能被劃分為小到幾個(gè)字或大到幾千字節(jié)的分配單元。每個(gè)分配單元對(duì)應(yīng)于位圖中的一位，0 表示空閑， 1 表示占用（或者相反）。一塊內(nèi)存區(qū)域和其對(duì)應(yīng)的位圖如下
位圖提供了一種簡單的方法在固定大小的內(nèi)存中跟蹤內(nèi)存的使用情況，因?yàn)?strong>「位圖的大小取決于內(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)存段的鏈表，段會(huì)包含進(jìn)程或者是兩個(gè)進(jìn)程的空閑區(qū)域。可用上面的圖 c 「來表示內(nèi)存的使用情況」。鏈表中的每一項(xiàng)都可以代表一個(gè) 空閑區(qū)(H) 或者是進(jìn)程(P)的起始標(biāo)志，長度和下一個(gè)鏈表項(xiàng)的位置。
當(dāng)按照地址順序在鏈表中存放進(jìn)程和空閑區(qū)時(shí)，有幾種算法可以為創(chuàng)建的進(jìn)程（或者從磁盤中換入的進(jìn)程）分配內(nèi)存。我們先假設(shè)內(nèi)存管理器知道應(yīng)該分配多少內(nèi)存，最簡單的算法是使用 首次適配(first fit)。內(nèi)存管理器會(huì)沿著段列表進(jìn)行掃描，直到找個(gè)一個(gè)足夠大的空閑區(qū)為止。 除非空閑區(qū)大小和要分配的空間大小一樣，否則將空閑區(qū)分為兩部分，一部分供進(jìn)程使用；一部分生成新的空閑區(qū)。首次適配算法是一種速度很快的算法，因?yàn)樗鼤?huì)盡可能的搜索鏈表。
首次適配的一個(gè)小的變體是 下次適配(next fit)。它和首次匹配的工作方式相同，只有一個(gè)不同之處那就是下次適配在每次找到合適的空閑區(qū)時(shí)就會(huì)記錄當(dāng)時(shí)的位置，以便下次尋找空閑區(qū)時(shí)從上次結(jié)束的地方開始搜索，而不是像首次匹配算法那樣每次都會(huì)從頭開始搜索。
另外一個(gè)著名的并且廣泛使用的算法是 最佳適配(best fit)。最佳適配會(huì)從頭到尾尋找整個(gè)鏈表，找出能夠容納進(jìn)程的最小空閑區(qū)。
盡管基址寄存器和變址寄存器用來創(chuàng)建地址空間的抽象，但是這有一個(gè)其他的問題需要解決：管理軟件的不斷增大(managing bloatware)。虛擬內(nèi)存的基本思想是，每個(gè)程序都有自己的地址空間，這個(gè)地址空間被劃分為多個(gè)稱為頁面(page)的塊。每一頁都是連續(xù)的地址范圍。這些頁被映射到物理內(nèi)存，但并不是所有的頁都必須在內(nèi)存中才能運(yùn)行程序。當(dāng)程序引用到一部分在物理內(nèi)存中的地址空間時(shí)，硬件會(huì)立刻執(zhí)行必要的映射。當(dāng)程序引用到一部分不在物理內(nèi)存中的地址空間時(shí)，由操作系統(tǒng)負(fù)責(zé)將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。
大部分使用虛擬內(nèi)存的系統(tǒng)中都會(huì)使用一種 分頁(paging) 技術(shù)。在任何一臺(tái)計(jì)算機(jī)上，程序會(huì)引用使用一組內(nèi)存地址。當(dāng)程序執(zhí)行
MOV REG,1000這條指令時(shí)，它會(huì)把內(nèi)存地址為 1000 的內(nèi)存單元的內(nèi)容復(fù)制到 REG 中（或者相反，這取決于計(jì)算機(jī)）。地址可以通過索引、基址寄存器、段寄存器或其他方式產(chǎn)生。
這些程序生成的地址被稱為 虛擬地址(virtual addresses) 并形成虛擬地址空間(virtual address space)，在沒有虛擬內(nèi)存的計(jì)算機(jī)上，系統(tǒng)直接將虛擬地址送到內(nèi)存中線上，讀寫操作都使用同樣地址的物理內(nèi)存。「在使用虛擬內(nèi)存時(shí)，虛擬地址不會(huì)直接發(fā)送到內(nèi)存總線上」。相反，會(huì)使用 MMU(Memory Management Unit) 內(nèi)存管理單元把「虛擬地址映射為物理內(nèi)存地址」，像下圖這樣
下面這幅圖展示了這種映射是如何工作的
頁表給出虛擬地址與物理內(nèi)存地址之間的映射關(guān)系。每一頁起始于 4096 的倍數(shù)位置，結(jié)束于 4095 的位置，所以 4K 到 8K 實(shí)際為 4096 - 8191 ，8K - 12K 就是 8192 - 12287
在這個(gè)例子中，我們可能有一個(gè) 16 位地址的計(jì)算機(jī)，地址從 0 - 64 K - 1，這些是虛擬地址。然而只有 32 KB 的物理地址。所以雖然可以編寫 64 KB 的程序，但是程序無法全部調(diào)入內(nèi)存運(yùn)行，在磁盤上必須有一個(gè)最多 64 KB 的程序核心映像的完整副本，以保證程序片段在需要時(shí)被調(diào)入內(nèi)存。
虛擬頁號(hào)可作為頁表的索引用來找到虛擬頁中的內(nèi)容。由頁表項(xiàng)可以找到頁框號(hào)（如果有的話）。然后把頁框號(hào)拼接到偏移量的高位端，以替換掉虛擬頁號(hào)，形成物理地址。
因此，頁表的目的是把虛擬頁映射到頁框中。從數(shù)學(xué)上說，頁表是一個(gè)函數(shù)，它的參數(shù)是虛擬頁號(hào)，結(jié)果是物理頁框號(hào)。
通過這個(gè)函數(shù)可以把虛擬地址中的虛擬頁轉(zhuǎn)換為頁框，從而形成物理地址。
下面我們探討一下頁表項(xiàng)的具體結(jié)構(gòu)，上面你知道了頁表項(xiàng)的大致構(gòu)成，是由頁框號(hào)和在/不在位構(gòu)成的，現(xiàn)在我們來具體探討一下頁表項(xiàng)的構(gòu)成
頁表項(xiàng)的結(jié)構(gòu)是與機(jī)器相關(guān)的，但是不同機(jī)器上的頁表項(xiàng)大致相同。上面是一個(gè)頁表項(xiàng)的構(gòu)成，不同計(jì)算機(jī)的頁表項(xiàng)可能不同，但是一般來說都是 32 位的。頁表項(xiàng)中最重要的字段就是頁框號(hào)(Page frame number)。畢竟，頁表到頁框最重要的一步操作就是要把此值映射過去。下一個(gè)比較重要的就是在/不在位，如果此位上的值是 1，那么頁表項(xiàng)是有效的并且能夠被使用。如果此值是 0 的話，則表示該頁表項(xiàng)對(duì)應(yīng)的虛擬頁面不在內(nèi)存中，訪問該頁面會(huì)引起一個(gè)缺頁異常(page fault)。
保護(hù)位(Protection) 告訴我們哪一種訪問是允許的，啥意思呢？最簡單的表示形式是這個(gè)域只有一位，「0 表示可讀可寫，1 表示的是只讀」。
修改位(Modified) 和 訪問位(Referenced) 會(huì)跟蹤頁面的使用情況。當(dāng)一個(gè)頁面被寫入時(shí)，硬件會(huì)自動(dòng)的設(shè)置修改位。修改位在頁面重新分配頁框時(shí)很有用。如果一個(gè)頁面已經(jīng)被修改過（即它是 臟 的），則必須把它寫回磁盤。如果一個(gè)頁面沒有被修改過（即它是 干凈的），那么重新分配時(shí)這個(gè)頁框會(huì)被直接丟棄，因?yàn)榇疟P上的副本仍然是有效的。這個(gè)位有時(shí)也叫做 臟位(dirty bit)，因?yàn)樗从沉隧撁娴臓顟B(tài)。
訪問位(Referenced) 在頁面被訪問時(shí)被設(shè)置，不管是讀還是寫。這個(gè)值能夠幫助操作系統(tǒng)在發(fā)生缺頁中斷時(shí)選擇要淘汰的頁。不再使用的頁要比正在使用的頁更適合被淘汰。這個(gè)位在后面要討論的頁面置換算法中作用很大。
最后一位用于禁止該頁面被高速緩存，這個(gè)功能對(duì)于映射到設(shè)備寄存器還是內(nèi)存中起到了關(guān)鍵作用。通過這一位可以禁用高速緩存。具有獨(dú)立的 I/O 空間而不是用內(nèi)存映射 I/O 的機(jī)器來說，并不需要這一位。
下面我們就來探討一下有哪些頁面置換算法。
最優(yōu)的頁面置換算法的工作流程如下：在缺頁中斷發(fā)生時(shí)，這些頁面之一將在下一條指令（包含該指令的頁面）上被引用。其他頁面則可能要到 10、100 或者 1000 條指令后才會(huì)被訪問。每個(gè)頁面都可以用在該頁首次被訪問前所要執(zhí)行的指令數(shù)作為標(biāo)記。
最優(yōu)化的頁面算法表明應(yīng)該標(biāo)記最大的頁面。如果一個(gè)頁面在 800 萬條指令內(nèi)不會(huì)被使用，另外一個(gè)頁面在 600 萬條指令內(nèi)不會(huì)被使用，則置換前一個(gè)頁面，從而把需要調(diào)入這個(gè)頁面而發(fā)生的缺頁中斷推遲。計(jì)算機(jī)也像人類一樣，會(huì)把不愿意做的事情盡可能的往后拖。
這個(gè)算法最大的問題時(shí)無法實(shí)現(xiàn)。當(dāng)缺頁中斷發(fā)生時(shí)，操作系統(tǒng)無法知道各個(gè)頁面的下一次將在什么時(shí)候被訪問。這種算法在實(shí)際過程中根本不會(huì)使用。
為了能夠讓操作系統(tǒng)收集頁面使用信息，大部分使用虛擬地址的計(jì)算機(jī)都有兩個(gè)狀態(tài)位，R 和 M，來和每個(gè)頁面進(jìn)行關(guān)聯(lián)。「每當(dāng)引用頁面（讀入或?qū)懭耄r(shí)都設(shè)置 R，寫入（即修改）頁面時(shí)設(shè)置 M」，這些位包含在每個(gè)頁表項(xiàng)中，就像下面所示
因?yàn)槊看卧L問時(shí)都會(huì)更新這些位，因此由硬件來設(shè)置它們非常重要。一旦某個(gè)位被設(shè)置為 1，就會(huì)一直保持 1 直到操作系統(tǒng)下次來修改此位。
如果硬件沒有這些位，那么可以使用操作系統(tǒng)的缺頁中斷和時(shí)鐘中斷機(jī)制來進(jìn)行模擬。當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，將其所有的頁面都標(biāo)記為不在內(nèi)存；一旦訪問任何一個(gè)頁面就會(huì)引發(fā)一次缺頁中斷，此時(shí)操作系統(tǒng)就可以設(shè)置 R 位(在它的內(nèi)部表中)，修改頁表項(xiàng)使其指向正確的頁面，并設(shè)置為 READ ONLY 模式，然后重新啟動(dòng)引起缺頁中斷的指令。如果頁面隨后被修改，就會(huì)發(fā)生另一個(gè)缺頁異常。從而允許操作系統(tǒng)設(shè)置 M 位并把頁面的模式設(shè)置為 READ/WRITE。
可以用 R 位和 M 位來構(gòu)造一個(gè)簡單的頁面置換算法：當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，操作系統(tǒng)將其所有頁面的兩個(gè)位都設(shè)置為 0。R 位定期的被清零（在每個(gè)時(shí)鐘中斷）。用來將最近未引用的頁面和已引用的頁面分開。
當(dāng)出現(xiàn)缺頁中斷后，操作系統(tǒng)會(huì)檢查所有的頁面，并根據(jù)它們的 R 位和 M 位將當(dāng)前值分為四類：
盡管看起來好像無法實(shí)現(xiàn)第一類頁面，但是當(dāng)?shù)谌愴撁娴?R 位被時(shí)鐘中斷清除時(shí)，它們就會(huì)發(fā)生。時(shí)鐘中斷不會(huì)清除 M 位，因?yàn)樾枰@個(gè)信息才能知道是否寫回磁盤中。清除 R 但不清除 M 會(huì)導(dǎo)致出現(xiàn)一類頁面。
NRU(Not Recently Used) 算法從編號(hào)最小的非空類中隨機(jī)刪除一個(gè)頁面。此算法隱含的思想是，在一個(gè)時(shí)鐘內(nèi)（約 20 ms）淘汰一個(gè)已修改但是沒有被訪問的頁面要比一個(gè)大量引用的未修改頁面好，NRU 的主要優(yōu)點(diǎn)是「易于理解并且能夠有效的實(shí)現(xiàn)」。
另一種開銷較小的方式是使用 FIFO(First-In,First-Out) 算法，這種類型的數(shù)據(jù)結(jié)構(gòu)也適用在頁面置換算法中。由操作系統(tǒng)維護(hù)一個(gè)所有在當(dāng)前內(nèi)存中的頁面的鏈表，最早進(jìn)入的放在表頭，最新進(jìn)入的頁面放在表尾。在發(fā)生缺頁異常時(shí)，會(huì)把頭部的頁移除并且把新的頁添加到表尾。
我們上面學(xué)到的 FIFO 鏈表頁面有個(gè)缺陷，那就是出鏈和入鏈并不會(huì)進(jìn)行 check 檢查，這樣就會(huì)容易把經(jīng)常使用的頁面置換出去，為了避免這一問題，我們對(duì)該算法做一個(gè)簡單的修改：我們檢查最老頁面的 R 位，如果是 0 ，那么這個(gè)頁面就是最老的而且沒有被使用，那么這個(gè)頁面就會(huì)被立刻換出。如果 R 位是 1，那么就清除此位，此頁面會(huì)被放在鏈表的尾部，修改它的裝入時(shí)間就像剛放進(jìn)來的一樣。然后繼續(xù)搜索。
這種算法叫做 第二次機(jī)會(huì)(second chance)算法，就像下面這樣，我們看到頁面 A 到 H 保留在鏈表中，并按到達(dá)內(nèi)存的時(shí)間排序。
a）按照先進(jìn)先出的方法排列的頁面；b）在時(shí)刻 20 處發(fā)生缺頁異常中斷并且 A 的 R 位已經(jīng)設(shè)置時(shí)的頁面鏈表。
假設(shè)缺頁異常發(fā)生在時(shí)刻 20 處，這時(shí)最老的頁面是 A ，它是在 0 時(shí)刻到達(dá)的。如果 A 的 R 位是 0，那么它將被淘汰出內(nèi)存，或者把它寫回磁盤（如果它已經(jīng)被修改過），或者只是簡單的放棄（如果它是未被修改過）。另一方面，如果它的 R 位已經(jīng)設(shè)置了，則將 A 放到鏈表的尾部并且重新設(shè)置裝入時(shí)間為當(dāng)前時(shí)刻（20 處），然后清除 R 位。然后從 B 頁面開始繼續(xù)搜索合適的頁面。
尋找第二次機(jī)會(huì)的是在最近的時(shí)鐘間隔中未被訪問過的頁面。如果所有的頁面都被訪問過，該算法就會(huì)被簡化為單純的 FIFO 算法。具體來說，假設(shè)圖 a 中所有頁面都設(shè)置了 R 位。操作系統(tǒng)將頁面依次移到鏈表末尾，每次都在添加到末尾時(shí)清除 R 位。最后，算法又會(huì)回到頁面 A，此時(shí)的 R 位已經(jīng)被清除，那么頁面 A 就會(huì)被執(zhí)行出鏈處理，因此算法能夠正常結(jié)束。
一種比較好的方式是把所有的頁面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，一個(gè)表針指向最老的頁面。如下圖所示
當(dāng)缺頁錯(cuò)誤出現(xiàn)時(shí)，算法首先檢查表針指向的頁面，如果它的 R 位是 0 就淘汰該頁面，并把新的頁面插入到這個(gè)位置，然后把表針向前移動(dòng)一位；如果 R 位是 1 就清除 R 位并把表針前移一個(gè)位置。重復(fù)這個(gè)過程直到找到了一個(gè) R 位為 0 的頁面位置。了解這個(gè)算法的工作方式，就明白為什么它被稱為 時(shí)鐘(clokc)算法了。
在前面幾條指令中頻繁使用的頁面和可能在后面的幾條指令中被使用。反過來說，已經(jīng)很久沒有使用的頁面有可能在未來一段時(shí)間內(nèi)仍不會(huì)被使用。這個(gè)思想揭示了一個(gè)可以實(shí)現(xiàn)的算法：在缺頁中斷時(shí)，置換未使用時(shí)間最長的頁面。這個(gè)策略稱為 LRU(Least Recently Used) ，最近最少使用頁面置換算法。
雖然 LRU 在理論上是可以實(shí)現(xiàn)的，但是從長遠(yuǎn)看來代價(jià)比較高。為了完全實(shí)現(xiàn) LRU，會(huì)在內(nèi)存中維護(hù)一個(gè)所有頁面的鏈表，最頻繁使用的頁位于表頭，最近最少使用的頁位于表尾。困難的是在每次內(nèi)存引用時(shí)更新整個(gè)鏈表。在鏈表中找到一個(gè)頁面，刪除它，然后把它移動(dòng)到表頭是一個(gè)非常耗時(shí)的操作，即使使用硬件來實(shí)現(xiàn)也是一樣的費(fèi)時(shí)。
盡管上面的 LRU 算法在原則上是可以實(shí)現(xiàn)的，「但是很少有機(jī)器能夠擁有那些特殊的硬件」。上面是硬件的實(shí)現(xiàn)方式，那么現(xiàn)在考慮要用軟件來實(shí)現(xiàn) LRU 。一種可以實(shí)現(xiàn)的方案是 NFU(Not Frequently Used，最不常用)算法。它需要一個(gè)軟件計(jì)數(shù)器來和每個(gè)頁面關(guān)聯(lián)，初始化的時(shí)候是 0 。在每個(gè)時(shí)鐘中斷時(shí)，操作系統(tǒng)會(huì)瀏覽內(nèi)存中的所有頁，會(huì)將每個(gè)頁面的 R 位（0 或 1）加到它的計(jì)數(shù)器上。這個(gè)計(jì)數(shù)器大體上跟蹤了各個(gè)頁面訪問的頻繁程度。當(dāng)缺頁異常出現(xiàn)時(shí)，則置換計(jì)數(shù)器值最小的頁面。
只需要對(duì) NFU 做一個(gè)簡單的修改就可以讓它模擬 LRU，這個(gè)修改有兩個(gè)步驟
修改以后的算法稱為 老化(aging) 算法，下圖解釋了老化算法是如何工作的。
我們假設(shè)在第一個(gè)時(shí)鐘周期內(nèi)頁面 0 - 5 的 R 位依次是 1，0，1，0，1，1，（也就是頁面 0 是 1，頁面 1 是 0，頁面 2 是 1 這樣類推）。也就是說，「在 0 個(gè)時(shí)鐘周期到 1 個(gè)時(shí)鐘周期之間，0，2，4，5 都被引用了」，從而把它們的 R 位設(shè)置為 1，剩下的設(shè)置為 0 。在相關(guān)的六個(gè)計(jì)數(shù)器被右移之后 R 位被添加到 左側(cè) ，就像上圖中的 a。剩下的四列顯示了接下來的四個(gè)時(shí)鐘周期內(nèi)的六個(gè)計(jì)數(shù)器變化。
?CPU正在以某個(gè)頻率前進(jìn)，該頻率的周期稱為
?時(shí)鐘滴答或時(shí)鐘周期。一個(gè) 100Mhz 的處理器每秒將接收100,000,000個(gè)時(shí)鐘滴答。
當(dāng)缺頁異常出現(xiàn)時(shí)，將置換（就是移除）計(jì)數(shù)器值最小的頁面。如果一個(gè)頁面在前面 4 個(gè)時(shí)鐘周期內(nèi)都沒有被訪問過，那么它的計(jì)數(shù)器應(yīng)該會(huì)有四個(gè)連續(xù)的 0 ，因此它的值肯定要比前面 3 個(gè)時(shí)鐘周期內(nèi)都沒有被訪問過的頁面的計(jì)數(shù)器小。
這個(gè)算法與 LRU 算法有兩個(gè)重要的區(qū)別：看一下上圖中的 e，第三列和第五列
當(dāng)缺頁異常發(fā)生后，需要掃描整個(gè)頁表才能確定被淘汰的頁面，因此基本工作集算法還是比較浪費(fèi)時(shí)間的。一個(gè)對(duì)基本工作集算法的提升是基于時(shí)鐘算法但是卻使用工作集的信息，這種算法稱為WSClock(工作集時(shí)鐘)。由于它的實(shí)現(xiàn)簡單并且具有高性能，因此在實(shí)踐中被廣泛應(yīng)用。
與時(shí)鐘算法一樣，所需的數(shù)據(jù)結(jié)構(gòu)是一個(gè)以頁框?yàn)樵氐难h(huán)列表，就像下面這樣
工作集時(shí)鐘頁面置換算法的操作：a) 和 b) 給出 R = 1 時(shí)所發(fā)生的情形；c) 和 d) 給出 R = 0 的例子
最初的時(shí)候，該表是空的。當(dāng)裝入第一個(gè)頁面后，把它加載到該表中。隨著更多的頁面的加入，它們形成一個(gè)環(huán)形結(jié)構(gòu)。每個(gè)表項(xiàng)包含來自基本工作集算法的上次使用時(shí)間，以及 R 位（已標(biāo)明）和 M 位（未標(biāo)明）。
與時(shí)鐘算法一樣，在每個(gè)缺頁異常時(shí)，首先檢查指針指向的頁面。如果 R 位被是設(shè)置為 1，該頁面在當(dāng)前時(shí)鐘周期內(nèi)就被使用過，那么該頁面就不適合被淘汰。然后把該頁面的 R 位置為 0，指針指向下一個(gè)頁面，并重復(fù)該算法。該事件序列化后的狀態(tài)參見圖 b。
現(xiàn)在考慮指針指向的頁面 R = 0 時(shí)會(huì)發(fā)生什么，參見圖 c，如果頁面的使用期限大于 t 并且頁面為被訪問過，那么這個(gè)頁面就不會(huì)在工作集中，并且在磁盤上會(huì)有一個(gè)此頁面的副本。申請(qǐng)重新調(diào)入一個(gè)新的頁面，并把新的頁面放在其中，如圖 d 所示。另一方面，如果頁面被修改過，就不能重新申請(qǐng)頁面，因?yàn)檫@個(gè)頁面在磁盤上沒有有效的副本。為了避免由于調(diào)度寫磁盤操作引起的進(jìn)程切換，指針繼續(xù)向前走，算法繼續(xù)對(duì)下一個(gè)頁面進(jìn)行操作。畢竟，有可能存在一個(gè)老的，沒有被修改過的頁面可以立即使用。
原則上來說，所有的頁面都有可能因?yàn)?/span>磁盤I/O 在某個(gè)時(shí)鐘周期內(nèi)被調(diào)度。為了降低磁盤阻塞，需要設(shè)置一個(gè)限制，即最大只允許寫回 n 個(gè)頁面。一旦達(dá)到該限制，就不允許調(diào)度新的寫操作。
那么就有個(gè)問題，指針會(huì)繞一圈回到原點(diǎn)的，如果回到原點(diǎn)，它的起始點(diǎn)會(huì)發(fā)生什么？這里有兩種情況：
在第一種情況中，指針僅僅是不停的移動(dòng)，尋找一個(gè)未被修改過的頁面。由于已經(jīng)調(diào)度了一個(gè)或者多個(gè)寫操作，最終會(huì)有某個(gè)寫操作完成，它的頁面會(huì)被標(biāo)記為未修改。置換遇到的第一個(gè)未被修改過的頁面，這個(gè)頁面不一定是第一個(gè)被調(diào)度寫操作的頁面，因?yàn)橛脖P驅(qū)動(dòng)程序?yàn)榱藘?yōu)化性能可能會(huì)把寫操作重排序。
對(duì)于第二種情況，所有的頁面都在工作集中，否則將至少調(diào)度了一個(gè)寫操作。由于缺乏額外的信息，最簡單的方法就是置換一個(gè)未被修改的頁面來使用，掃描中需要記錄未被修改的頁面的位置，如果不存在未被修改的頁面，就選定當(dāng)前頁面并把它寫回磁盤。
我們到現(xiàn)在已經(jīng)研究了各種頁面置換算法，現(xiàn)在我們來一個(gè)簡單的總結(jié)，算法的總結(jié)歸納如下
| 算法 | 注釋 |
|---|---|
| 最優(yōu)算法 | 不可實(shí)現(xiàn)，但可以用作基準(zhǔn) |
| NRU(最近未使用) 算法 | 和 LRU 算法很相似 |
| FIFO(先進(jìn)先出) 算法 | 有可能會(huì)拋棄重要的頁面 |
| 第二次機(jī)會(huì)算法 | 比 FIFO 有較大的改善 |
| 時(shí)鐘算法 | 實(shí)際使用 |
| LRU(最近最少)算法 | 比較優(yōu)秀，但是很難實(shí)現(xiàn) |
| NFU(最不經(jīng)常食用)算法 | 和 LRU 很類似 |
| 老化算法 | 近似 LRU 的高效算法 |
| 工作集算法 | 實(shí)施起來開銷很大 |
| 工作集時(shí)鐘算法 | 比較有效的算法 |
最優(yōu)算法在當(dāng)前頁面中置換最后要訪問的頁面。不幸的是，沒有辦法來判定哪個(gè)頁面是最后一個(gè)要訪問的，因此實(shí)際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。
NRU 算法根據(jù) R 位和 M 位的狀態(tài)將頁面氛圍四類。從編號(hào)最小的類別中隨機(jī)選擇一個(gè)頁面。NRU 算法易于實(shí)現(xiàn)，但是性能不是很好。存在更好的算法。
FIFO 會(huì)跟蹤頁面加載進(jìn)入內(nèi)存中的順序，并把頁面放入一個(gè)鏈表中。有可能刪除存在時(shí)間最長但是還在使用的頁面，因此這個(gè)算法也不是一個(gè)很好的選擇。
第二次機(jī)會(huì)算法是對(duì) FIFO 的一個(gè)修改，它會(huì)在刪除頁面之前檢查這個(gè)頁面是否仍在使用。如果頁面正在使用，就會(huì)進(jìn)行保留。這個(gè)改進(jìn)大大提高了性能。
時(shí)鐘 算法是第二次機(jī)會(huì)算法的另外一種實(shí)現(xiàn)形式，時(shí)鐘算法和第二次算法的性能差不多，但是會(huì)花費(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)，你需要知道下面這些知識(shí)點(diǎn)
文件是一種抽象機(jī)制，它提供了一種方式用來存儲(chǔ)信息以及在后面進(jìn)行讀取?？赡苋魏我环N機(jī)制最重要的特性就是管理對(duì)象的命名方式。在創(chuàng)建一個(gè)文件后，它會(huì)給文件一個(gè)命名。當(dāng)進(jìn)程終止時(shí)，文件會(huì)繼續(xù)存在，并且其他進(jìn)程可以使用名稱訪問該文件。
文件命名規(guī)則對(duì)于不同的操作系統(tǒng)來說是不一樣的，但是所有現(xiàn)代操作系統(tǒng)都允許使用 1 - 8 個(gè)字母的字符串作為合法文件名。
某些文件區(qū)分大小寫字母，而大多數(shù)則不區(qū)分。UNIX 屬于第一類；歷史悠久的 MS-DOS 屬于第二類（順便說一句，盡管 MS-DOS 歷史悠久，但 MS-DOS 仍在嵌入式系統(tǒng)中非常廣泛地使用，因此它絕不是過時(shí)的）；因此，UNIX 系統(tǒng)會(huì)有三種不同的命名文件：maria、Maria、MARIA 。在 MS-DOS ，所有這些命名都屬于相同的文件。
許多操作系統(tǒng)支持兩部分的文件名，它們之間用 . 分隔開，比如文件名 prog.c。原點(diǎn)后面的文件稱為 文件擴(kuò)展名(file extension) ，文件擴(kuò)展名通常表示文件的一些信息。一些常用的文件擴(kuò)展名以及含義如下圖所示
| 擴(kuò)展名 | 含義 |
|---|---|
| bak | 備份文件 |
| c | c 源程序文件 |
| gif | 符合圖形交換格式的圖像文件 |
| hlp | 幫助文件 |
| html | WWW 超文本標(biāo)記語言文檔 |
| jpg | 符合 JPEG 編碼標(biāo)準(zhǔn)的靜態(tài)圖片 |
| mp3 | 符合 MP3 音頻編碼格式的音樂文件 |
| mpg | 符合 MPEG 編碼標(biāo)準(zhǔn)的電影 |
| o | 目標(biāo)文件（編譯器輸出格式，尚未鏈接） |
| pdf 格式的文件 | |
| ps | PostScript 文件 |
| tex | 為 TEX 格式化程序準(zhǔn)備的輸入文件 |
| txt | 文本文件 |
| zip | 壓縮文件 |
在 UNIX 系統(tǒng)中，文件擴(kuò)展名只是一種約定，操作系統(tǒng)并不強(qiáng)制采用。
文件的構(gòu)造有多種方式。下圖列出了常用的三種構(gòu)造方式
三種不同的文件。a) 字節(jié)序列 。b) 記錄序列。c) 樹
上圖中的 a 是一種無結(jié)構(gòu)的字節(jié)序列，操作系統(tǒng)不關(guān)心序列的內(nèi)容是什么，操作系統(tǒng)能看到的就是字節(jié)(bytes)。其文件內(nèi)容的任何含義只在用戶程序中進(jìn)行解釋。UNIX 和 Windows 都采用這種辦法。
圖 b 表示在文件結(jié)構(gòu)上的第一部改進(jìn)。在這個(gè)模型中，文件是具有固定長度記錄的序列，每個(gè)記錄都有其內(nèi)部結(jié)構(gòu)。把文件作為記錄序列的核心思想是：「讀操作返回一個(gè)記錄，而寫操作重寫或者追加一個(gè)記錄」。第三種文件結(jié)構(gòu)如上圖 c 所示。在這種組織結(jié)構(gòu)中，文件由一顆記錄樹構(gòu)成，記錄樹的長度不一定相同，每個(gè)記錄樹都在記錄中的固定位置包含一個(gè)key 字段。這棵樹按 key 進(jìn)行排序，從而可以對(duì)特定的 key 進(jìn)行快速查找。
很多操作系統(tǒng)支持多種文件類型。例如，UNIX（同樣包括 OS X）和 Windows 都具有常規(guī)的文件和目錄。除此之外，UNIX 還具有字符特殊文件(character special file) 和 塊特殊文件(block special file)。常規(guī)文件(Regular files) 是包含有用戶信息的文件。用戶一般使用的文件大都是常規(guī)文件，常規(guī)文件一般包括 「可執(zhí)行文件、文本文件、圖像文件」，從常規(guī)文件讀取數(shù)據(jù)或?qū)?shù)據(jù)寫入時(shí)，內(nèi)核會(huì)根據(jù)文件系統(tǒng)的規(guī)則執(zhí)行操作，是寫入可能被延遲，記錄日志或者接受其他操作。
早期的操作系統(tǒng)只有一種訪問方式：序列訪問(sequential access)。在這些系統(tǒng)中，進(jìn)程可以按照順序讀取所有的字節(jié)或文件中的記錄，但是不能跳過并亂序執(zhí)行它們。順序訪問文件是可以返回到起點(diǎn)的，需要時(shí)可以多次讀取該文件。當(dāng)存儲(chǔ)介質(zhì)是磁帶而不是磁盤時(shí)，順序訪問文件很方便。
在使用磁盤來存儲(chǔ)文件時(shí)，可以不按照順序讀取文件中的字節(jié)或者記錄，或者按照關(guān)鍵字而不是位置來訪問記錄。這種能夠以任意次序進(jìn)行讀取的稱為隨機(jī)訪問文件(random access file)。許多應(yīng)用程序都需要這種方式。
隨機(jī)訪問文件對(duì)許多應(yīng)用程序來說都必不可少，例如，數(shù)據(jù)庫系統(tǒng)。如果乘客打電話預(yù)定某航班機(jī)票，訂票程序必須能夠直接訪問航班記錄，而不必先讀取其他航班的成千上萬條記錄。
有兩種方法可以指示從何處開始讀取文件。第一種方法是直接使用 read 從頭開始讀取。另一種是用一個(gè)特殊的 seek 操作設(shè)置當(dāng)前位置，在 seek 操作后，從這個(gè)當(dāng)前位置順序地開始讀文件。UNIX 和 Windows 使用的是后面一種方式。
文件包括文件名和數(shù)據(jù)。除此之外，所有的操作系統(tǒng)還會(huì)保存其他與文件相關(guān)的信息，如文件創(chuàng)建的日期和時(shí)間、文件大小。我們可以稱這些為文件的屬性(attributes)。有些人也喜歡把它們稱作 元數(shù)據(jù)(metadata)。文件的屬性在不同的系統(tǒng)中差別很大。文件的屬性只有兩種狀態(tài)：設(shè)置(set) 和 清除(clear)。
使用文件的目的是用來存儲(chǔ)信息并方便以后的檢索。對(duì)于存儲(chǔ)和檢索，不同的系統(tǒng)提供了不同的操作。以下是與文件有關(guān)的最常用的一些系統(tǒng)調(diào)用：
Create，創(chuàng)建不包含任何數(shù)據(jù)的文件。調(diào)用的目的是表示文件即將建立，并對(duì)文件設(shè)置一些屬性。Delete，當(dāng)文件不再需要，必須刪除它以釋放內(nèi)存空間。為此總會(huì)有一個(gè)系統(tǒng)調(diào)用來刪除文件。Open，在使用文件之前，必須先打開文件。這個(gè)調(diào)用的目的是允許系統(tǒng)將屬性和磁盤地址列表保存到主存中，用來以后的快速訪問。Close，當(dāng)所有進(jìn)程完成時(shí)，屬性和磁盤地址不再需要，因此應(yīng)關(guān)閉文件以釋放表空間。很多系統(tǒng)限制進(jìn)程打開文件的個(gè)數(shù)，以此達(dá)到鼓勵(lì)用戶關(guān)閉不再使用的文件。磁盤以塊為單位寫入，關(guān)閉文件時(shí)會(huì)強(qiáng)制寫入最后一塊，即使這個(gè)塊空間內(nèi)部還不滿。Read，數(shù)據(jù)從文件中讀取。通常情況下，讀取的數(shù)據(jù)來自文件的當(dāng)前位置。調(diào)用者必須指定需要讀取多少數(shù)據(jù)，并且提供存放這些數(shù)據(jù)的緩沖區(qū)。Write，向文件寫數(shù)據(jù)，寫操作一般也是從文件的當(dāng)前位置開始進(jìn)行。如果當(dāng)前位置是文件的末尾，則會(huì)直接追加進(jìn)行寫入。如果當(dāng)前位置在文件中，則現(xiàn)有數(shù)據(jù)被覆蓋，并且永遠(yuǎn)消失。append，使用 append 只能向文件末尾添加數(shù)據(jù)。seek，對(duì)于隨機(jī)訪問的文件，要指定從何處開始獲取數(shù)據(jù)。通常的方法是用 seek 系統(tǒng)調(diào)用把當(dāng)前位置指針指向文件中的特定位置。seek 調(diào)用結(jié)束后，就可以從指定位置開始讀寫數(shù)據(jù)了。get attributes，進(jìn)程運(yùn)行時(shí)通常需要讀取文件屬性。set attributes，用戶可以自己設(shè)置一些文件屬性，甚至是在文件創(chuàng)建之后，實(shí)現(xiàn)該功能的是 set attributes 系統(tǒng)調(diào)用。rename，用戶可以自己更改已有文件的名字，rename 系統(tǒng)調(diào)用用于這一目的。文件系統(tǒng)通常提供目錄(directories) 或者 文件夾(folders) 用于記錄文件的位置，在很多系統(tǒng)中目錄本身也是文件，下面我們會(huì)討論關(guān)于文件，他們的組織形式、屬性和可以對(duì)文件進(jìn)行的操作。
目錄系統(tǒng)最簡單的形式是有一個(gè)能夠包含所有文件的目錄。這種目錄被稱為根目錄(root directory)，由于根目錄的唯一性，所以其名稱并不重要。在最早期的個(gè)人計(jì)算機(jī)中，這種系統(tǒng)很常見，部分原因是因?yàn)橹挥幸粋€(gè)用戶。下面是一個(gè)單層目錄系統(tǒng)的例子
該目錄中有四個(gè)文件。這種設(shè)計(jì)的優(yōu)點(diǎn)在于簡單，并且能夠快速定位文件，畢竟只有一個(gè)地方可以檢索。這種目錄組織形式現(xiàn)在一般用于簡單的嵌入式設(shè)備（如數(shù)碼相機(jī)和某些便攜式音樂播放器）上使用。
對(duì)于簡單的應(yīng)用而言，一般都用單層目錄方式，但是這種組織形式并不適合于現(xiàn)代計(jì)算機(jī)，因?yàn)楝F(xiàn)代計(jì)算機(jī)含有成千上萬個(gè)文件和文件夾。如果都放在根目錄下，查找起來會(huì)非常困難。為了解決這一問題，出現(xiàn)了層次目錄系統(tǒng)(Hierarchical Directory Systems)，也稱為目錄樹。通過這種方式，可以用很多目錄把文件進(jìn)行分組。進(jìn)而，如果多個(gè)用戶共享同一個(gè)文件服務(wù)器，比如公司的網(wǎng)絡(luò)系統(tǒng)，每個(gè)用戶可以為自己的目錄樹擁有自己的私人根目錄。這種方式的組織結(jié)構(gòu)如下
根目錄含有目錄 A、B 和 C ，分別屬于不同的用戶，其中兩個(gè)用戶個(gè)字創(chuàng)建了子目錄。用戶可以創(chuàng)建任意數(shù)量的子目錄，現(xiàn)代文件系統(tǒng)都是按照這種方式組織的。
當(dāng)目錄樹組織文件系統(tǒng)時(shí)，需要有某種方法指明文件名。常用的方法有兩種，第一種方式是每個(gè)文件都會(huì)用一個(gè)絕對(duì)路徑名(absolute path name)，它由根目錄到文件的路徑組成。
另外一種指定文件名的方法是 相對(duì)路徑名(relative path name)。它常常和 工作目錄(working directory) （也稱作 當(dāng)前目錄(current directory)）一起使用。用戶可以指定一個(gè)目錄作為當(dāng)前工作目錄。例如，如果當(dāng)前目錄是 /usr/ast，那么絕對(duì)路徑 /usr/ast/mailbox可以直接使用 mailbox 來引用。
不同文件中管理目錄的系統(tǒng)調(diào)用的差別比管理文件的系統(tǒng)調(diào)用差別大。為了了解這些系統(tǒng)調(diào)用有哪些以及它們?cè)鯓庸ぷ?，下面給出一個(gè)例子（取自 UNIX）。
Create，創(chuàng)建目錄，除了目錄項(xiàng) . 和 .. 外，目錄內(nèi)容為空。Delete，刪除目錄，只有空目錄可以刪除。只包含 . 和 .. 的目錄被認(rèn)為是空目錄，這兩個(gè)目錄項(xiàng)通常不能刪除opendir，目錄內(nèi)容可被讀取。例如，未列出目錄中的全部文件，程序必須先打開該目錄，然后讀其中全部文件的文件名。與打開和讀文件相同，在讀目錄前，必須先打開文件。closedir，讀目錄結(jié)束后，應(yīng)該關(guān)閉目錄用于釋放內(nèi)部表空間。readdir，系統(tǒng)調(diào)用 readdir 返回打開目錄的下一個(gè)目錄項(xiàng)。以前也采用 read 系統(tǒng)調(diào)用來讀取目錄，但是這種方法有一個(gè)缺點(diǎn)：程序員必須了解和處理目錄的內(nèi)部結(jié)構(gòu)。相反，不論采用哪一種目錄結(jié)構(gòu)，readdir 總是以標(biāo)準(zhǔn)格式返回一個(gè)目錄項(xiàng)。rename，在很多方面目錄和文件都相似。文件可以更換名稱，目錄也可以。link，鏈接技術(shù)允許在多個(gè)目錄中出現(xiàn)同一個(gè)文件。這個(gè)系統(tǒng)調(diào)用指定一個(gè)存在的文件和一個(gè)路徑名，并建立從該文件到路徑所指名字的鏈接。這樣，可以在多個(gè)目錄中出現(xiàn)同一個(gè)文件。有時(shí)也被稱為硬鏈接(hard link)。unlink，刪除目錄項(xiàng)。如果被解除鏈接的文件只出現(xiàn)在一個(gè)目錄中，則將它從文件中刪除。如果它出現(xiàn)在多個(gè)目錄中，則只刪除指定路徑名的鏈接，依然保留其他路徑名的鏈接。在 UNIX 中，用于刪除文件的系統(tǒng)調(diào)用就是 unlink。文件系統(tǒng)存儲(chǔ)在磁盤中。大部分的磁盤能夠劃分出一到多個(gè)分區(qū)，叫做磁盤分區(qū)(disk partitioning) 或者是磁盤分片(disk slicing)。每個(gè)分區(qū)都有獨(dú)立的文件系統(tǒng)，每塊分區(qū)的文件系統(tǒng)可以不同。磁盤的 0 號(hào)分區(qū)稱為 主引導(dǎo)記錄(Master Boot Record, MBR)，用來引導(dǎo)(boot) 計(jì)算機(jī)。在 MBR 的結(jié)尾是分區(qū)表(partition table)。每個(gè)分區(qū)表給出每個(gè)分區(qū)由開始到結(jié)束的地址。
當(dāng)計(jì)算機(jī)開始引 boot 時(shí)，BIOS 讀入并執(zhí)行 MBR。
MBR 做的第一件事就是確定活動(dòng)分區(qū)，讀入它的第一個(gè)塊，稱為引導(dǎo)塊(boot block) 并執(zhí)行。引導(dǎo)塊中的程序?qū)⒓虞d分區(qū)中的操作系統(tǒng)。為了一致性，每個(gè)分區(qū)都會(huì)從引導(dǎo)塊開始，即使引導(dǎo)塊不包含操作系統(tǒng)。引導(dǎo)塊占據(jù)文件系統(tǒng)的前 4096 個(gè)字節(jié)，從磁盤上的字節(jié)偏移量 0 開始。引導(dǎo)塊可用于啟動(dòng)操作系統(tǒng)。
除了從引導(dǎo)塊開始之外，磁盤分區(qū)的布局是隨著文件系統(tǒng)的不同而變化的。通常文件系統(tǒng)會(huì)包含一些屬性，如下
緊跟在引導(dǎo)塊后面的是 超級(jí)塊(Superblock)，超級(jí)塊的大小為 4096 字節(jié)，從磁盤上的字節(jié)偏移 4096 開始。超級(jí)塊包含文件系統(tǒng)的所有關(guān)鍵參數(shù)
在計(jì)算機(jī)啟動(dòng)或者文件系統(tǒng)首次使用時(shí)，超級(jí)塊會(huì)被讀入內(nèi)存。
接著是文件系統(tǒng)中空閑塊的信息，例如，可以用位圖或者指針列表的形式給出。
「BitMap 位圖或者 Bit vector 位向量」
位圖或位向量是一系列位或位的集合，其中每個(gè)位對(duì)應(yīng)一個(gè)磁盤塊，該位可以采用兩個(gè)值：0和1，0表示已分配該塊，而1表示一個(gè)空閑塊。下圖中的磁盤上給定的磁盤塊實(shí)例（分配了綠色塊）可以用16位的位圖表示為：0000111000000110。
「使用鏈表進(jìn)行管理」
在這種方法中，空閑磁盤塊鏈接在一起，即一個(gè)空閑塊包含指向下一個(gè)空閑塊的指針。第一個(gè)磁盤塊的塊號(hào)存儲(chǔ)在磁盤上的單獨(dú)位置，也緩存在內(nèi)存中。
這里不得不提一個(gè)叫做碎片(fragment)的概念，也稱為片段。一般零散的單個(gè)數(shù)據(jù)通常稱為片段。磁盤塊可以進(jìn)一步分為固定大小的分配單元，片段只是在驅(qū)動(dòng)器上彼此不相鄰的文件片段。
然后在后面是一個(gè) inode(index node)，也稱作索引節(jié)點(diǎn)。它是一個(gè)數(shù)組的結(jié)構(gòu)，每個(gè)文件有一個(gè) inode，inode 非常重要，它說明了文件的方方面面。每個(gè)索引節(jié)點(diǎn)都存儲(chǔ)對(duì)象數(shù)據(jù)的屬性和磁盤塊位置
有一種簡單的方法可以找到它們 ls -lai 命令。讓我們看一下根文件系統(tǒng)：
inode 節(jié)點(diǎn)主要包括了以下信息
文件分為兩部分，索引節(jié)點(diǎn)和塊。一旦創(chuàng)建后，每種類型的塊數(shù)是固定的。你不能增加分區(qū)上 inode 的數(shù)量，也不能增加磁盤塊的數(shù)量。
緊跟在 inode 后面的是根目錄，它存放的是文件系統(tǒng)目錄樹的根部。最后，磁盤的其他部分存放了其他所有的目錄和文件。
最重要的問題是記錄各個(gè)文件分別用到了哪些磁盤塊。不同的系統(tǒng)采用了不同的方法。下面我們會(huì)探討一下這些方式。分配背后的主要思想是有效利用文件空間和快速訪問文件 ，主要有三種分配方案
最簡單的分配方案是把每個(gè)文件作為一連串連續(xù)數(shù)據(jù)塊存儲(chǔ)在磁盤上。因此，在具有 1KB 塊的磁盤上，將為 50 KB 文件分配 50 個(gè)連續(xù)塊。
上面展示了 40 個(gè)連續(xù)的內(nèi)存塊。從最左側(cè)的 0 塊開始。初始狀態(tài)下，還沒有裝載文件，因此磁盤是空的。接著，從磁盤開始處（塊 0 ）處開始寫入占用 4 塊長度的內(nèi)存 A 。然后是一個(gè)占用 6 塊長度的內(nèi)存 B，會(huì)直接在 A 的末尾開始寫。
注意每個(gè)文件都會(huì)在新的文件塊開始寫，所以如果文件 A 只占用了 3 又 1/2 個(gè)塊，那么最后一個(gè)塊的部分內(nèi)存會(huì)被浪費(fèi)。在上面這幅圖中，總共展示了 7 個(gè)文件，每個(gè)文件都會(huì)從上個(gè)文件的末尾塊開始寫新的文件塊。
連續(xù)的磁盤空間分配有兩個(gè)優(yōu)點(diǎn)。
第一，連續(xù)文件存儲(chǔ)實(shí)現(xiàn)起來比較簡單，只需要記住兩個(gè)數(shù)字就可以：一個(gè)是第一個(gè)塊的文件地址和文件的塊數(shù)量。給定第一個(gè)塊的編號(hào)，可以通過簡單的加法找到任何其他塊的編號(hào)。
第二點(diǎn)是讀取性能比較強(qiáng)，可以通過一次操作從文件中讀取整個(gè)文件。只需要一次尋找第一個(gè)塊。后面就不再需要尋道時(shí)間和旋轉(zhuǎn)延遲，所以數(shù)據(jù)會(huì)以全帶寬進(jìn)入磁盤。
因此，連續(xù)的空間分配具有實(shí)現(xiàn)簡單、高性能的特點(diǎn)。
不幸的是，連續(xù)空間分配也有很明顯的不足。隨著時(shí)間的推移，磁盤會(huì)變得很零碎。下圖解釋了這種現(xiàn)象
這里有兩個(gè)文件 D 和 F 被刪除了。當(dāng)刪除一個(gè)文件時(shí)，此文件所占用的塊也隨之釋放，就會(huì)在磁盤空間中留下一些空閑塊。磁盤并不會(huì)在這個(gè)位置擠壓掉空閑塊，因?yàn)檫@會(huì)復(fù)制空閑塊之后的所有文件，可能會(huì)有上百萬的塊，這個(gè)量級(jí)就太大了。
第二種存儲(chǔ)文件的方式是為每個(gè)文件構(gòu)造磁盤塊鏈表，每個(gè)文件都是磁盤塊的鏈接列表，就像下面所示
每個(gè)塊的第一個(gè)字作為指向下一塊的指針，塊的其他部分存放數(shù)據(jù)。如果上面這張圖你看的不是很清楚的話，可以看看整個(gè)的鏈表分配方案
與連續(xù)分配方案不同，這一方法可以充分利用每個(gè)磁盤塊。除了最后一個(gè)磁盤塊外，不會(huì)因?yàn)榇疟P碎片而浪費(fèi)存儲(chǔ)空間。同樣，在目錄項(xiàng)中，只要存儲(chǔ)了第一個(gè)文件塊，那么其他文件塊也能夠被找到。
另一方面，在鏈表的分配方案中，盡管順序讀取非常方便，但是隨機(jī)訪問卻很困難（這也是數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)的一大區(qū)別）。
還有一個(gè)問題是，由于指針會(huì)占用一些字節(jié)，每個(gè)磁盤塊實(shí)際存儲(chǔ)數(shù)據(jù)的字節(jié)數(shù)并不再是 2 的整數(shù)次冪。雖然這個(gè)問題并不會(huì)很嚴(yán)重，但是這種方式降低了程序運(yùn)行效率。許多程序都是以長度為 2 的整數(shù)次冪來讀寫磁盤，由于每個(gè)塊的前幾個(gè)字節(jié)被指針?biāo)褂?，所以要讀出一個(gè)完成的塊大小信息，就需要當(dāng)前塊的信息和下一塊的信息拼湊而成，因此就引發(fā)了查找和拼接的開銷。
由于連續(xù)分配和鏈表分配都有其不可忽視的缺點(diǎn)。所以提出了使用內(nèi)存中的表來解決分配問題。取出每個(gè)磁盤塊的指針字，把它們放在內(nèi)存的一個(gè)表中，就可以解決上述鏈表的兩個(gè)不足之處。下面是一個(gè)例子
上圖表示了鏈表形成的磁盤塊的內(nèi)容。這兩個(gè)圖中都有兩個(gè)文件，文件 A 依次使用了磁盤塊地址 「4、7、 2、 10、 12」，文件 B 使用了「6、3、11 和 14」。也就是說，文件 A 從地址 4 處開始，順著鏈表走就能找到文件 A 的全部磁盤塊。同樣，從第 6 塊開始，順著鏈走到最后，也能夠找到文件 B 的全部磁盤塊。你會(huì)發(fā)現(xiàn)，這兩個(gè)鏈表都以不屬于有效磁盤編號(hào)的特殊標(biāo)記（-1）結(jié)束。內(nèi)存中的這種表格稱為 文件分配表(File Application Table,FAT)。
文件只有打開后才能夠被讀取。在文件打開后，操作系統(tǒng)會(huì)使用用戶提供的路徑名來定位磁盤中的目錄。目錄項(xiàng)提供了查找文件磁盤塊所需要的信息。根據(jù)系統(tǒng)的不同，提供的信息也不同，可能提供的信息是整個(gè)文件的磁盤地址，或者是第一個(gè)塊的數(shù)量（兩個(gè)鏈表方案）或 inode的數(shù)量。不過不管用那種情況，目錄系統(tǒng)的主要功能就是 「將文件的 ASCII 碼的名稱映射到定位數(shù)據(jù)所需的信息上」。
當(dāng)多個(gè)用戶在同一個(gè)項(xiàng)目中工作時(shí)，他們通常需要共享文件。如果這個(gè)共享文件同時(shí)出現(xiàn)在多個(gè)用戶目錄下，那么他們協(xié)同工作起來就很方便。下面的這張圖我們?cè)谏厦嫣岬竭^，但是有一個(gè)更改的地方，就是 「C 的一個(gè)文件也出現(xiàn)在了 B 的目錄下」。
如果按照如上圖的這種組織方式而言，那么 B 的目錄與該共享文件的聯(lián)系稱為 鏈接(link)。那么文件系統(tǒng)現(xiàn)在就是一個(gè) 有向無環(huán)圖(Directed Acyclic Graph, 簡稱 DAG)，而不是一棵樹了。
技術(shù)的改變會(huì)給當(dāng)前的文件系統(tǒng)帶來壓力。這種情況下，CPU 會(huì)變得越來越快，磁盤會(huì)變得越來越大并且越來越便宜（但不會(huì)越來越快）。內(nèi)存容量也是以指數(shù)級(jí)增長。但是磁盤的尋道時(shí)間（除了固態(tài)盤，因?yàn)楣虘B(tài)盤沒有尋道時(shí)間）并沒有獲得提高。
為此，Berkeley 設(shè)計(jì)了一種全新的文件系統(tǒng)，試圖緩解這個(gè)問題，這個(gè)文件系統(tǒng)就是 日志結(jié)構(gòu)文件系統(tǒng)(Log-structured File System, LFS)。旨在解決以下問題。
不斷增長的系統(tǒng)內(nèi)存
順序 I/O 性能勝過隨機(jī) I/O 性能
現(xiàn)有低效率的文件系統(tǒng)
文件系統(tǒng)不支持 RAID（虛擬化）
另一方面，當(dāng)時(shí)的文件系統(tǒng)不論是 UNIX 還是 FFS，都有大量的隨機(jī)讀寫（在 FFS 中創(chuàng)建一個(gè)新文件至少需要5次隨機(jī)寫），因此成為整個(gè)系統(tǒng)的性能瓶頸。同時(shí)因?yàn)?Page cache的存在，作者認(rèn)為隨機(jī)讀不是主要問題：隨著越來越大的內(nèi)存，大部分的讀操作都能被 cache，因此 LFS 主要要解決的是減少對(duì)硬盤的隨機(jī)寫操作。
在這種設(shè)計(jì)中，inode 甚至具有與 UNIX 中相同的結(jié)構(gòu)，但是現(xiàn)在它們分散在整個(gè)日志中，而不是位于磁盤上的固定位置。所以，inode 很定位。為了能夠找到 inode ，維護(hù)了一個(gè)由 inode 索引的 inode map(inode 映射)。表項(xiàng) i 指向磁盤中的第 i 個(gè) inode 。這個(gè)映射保存在磁盤中，但是也保存在緩存中，因此，使用最頻繁的部分大部分時(shí)間都在內(nèi)存中。
到目前為止，所有寫入最初都緩存在內(nèi)存中，并且追加在日志末尾，所有緩存的寫入都定期在單個(gè)段中寫入磁盤。所以，現(xiàn)在打開文件也就意味著用映射定位文件的索引節(jié)點(diǎn)。一旦 inode 被定位后，磁盤塊的地址就能夠被找到。所有這些塊本身都將位于日志中某處的分段中。
真實(shí)情況下的磁盤容量是有限的，所以最終日志會(huì)占滿整個(gè)磁盤空間，這種情況下就會(huì)出現(xiàn)沒有新的磁盤塊被寫入到日志中。幸運(yùn)的是，許多現(xiàn)有段可能具有不再需要的塊。例如，如果一個(gè)文件被覆蓋了，那么它的 inode 將被指向新的塊，但是舊的磁盤塊仍在先前寫入的段中占據(jù)著空間。
為了處理這個(gè)問題，LFS 有一個(gè)清理(clean)線程，它會(huì)循環(huán)掃描日志并對(duì)日志進(jìn)行壓縮。首先，通過查看日志中第一部分的信息來查看其中存在哪些索引節(jié)點(diǎn)和文件。它會(huì)檢查當(dāng)前 inode 的映射來查看 inode 否在在當(dāng)前塊中，是否仍在被使用。如果不是，該信息將被丟棄。如果仍然在使用，那么 inode 和塊就會(huì)進(jìn)入內(nèi)存等待寫回到下一個(gè)段中。然后原來的段被標(biāo)記為空閑，以便日志可以用來存放新的數(shù)據(jù)。用這種方法，清理線程遍歷日志，從后面移走舊的段，然后將有效的數(shù)據(jù)放入內(nèi)存等待寫到下一個(gè)段中。由此一來整個(gè)磁盤會(huì)形成一個(gè)大的環(huán)形緩沖區(qū)，寫線程將新的段寫在前面，而清理線程則清理后面的段。
雖然日志結(jié)構(gòu)系統(tǒng)的設(shè)計(jì)很優(yōu)雅，但是由于它們和現(xiàn)有的文件系統(tǒng)不相匹配，因此還沒有廣泛使用。不過，從日志文件結(jié)構(gòu)系統(tǒng)衍生出來一種新的日志系統(tǒng)，叫做日志文件系統(tǒng)，它會(huì)記錄系統(tǒng)下一步將要做什么的日志。微軟的 NTFS 文件系統(tǒng)、Linux 的 ext3 就使用了此日志。OS X 將日志系統(tǒng)作為可供選項(xiàng)。為了看清它是如何工作的，我們下面討論一個(gè)例子，比如 移除文件 ，這個(gè)操作在 UNIX 中需要三個(gè)步驟完成：
UNIX 操作系統(tǒng)使用一種 虛擬文件系統(tǒng)(Virtual File System, VFS) 來嘗試將多種文件系統(tǒng)構(gòu)成一個(gè)有序的結(jié)構(gòu)。關(guān)鍵的思想是抽象出所有文件系統(tǒng)都共有的部分，并將這部分代碼放在一層，這一層再調(diào)用具體文件系統(tǒng)來管理數(shù)據(jù)。下面是一個(gè) VFS 的系統(tǒng)結(jié)構(gòu)
還是那句經(jīng)典的話，在計(jì)算機(jī)世界中，任何解決不了的問題都可以加個(gè)代理來解決。所有和文件相關(guān)的系統(tǒng)調(diào)用在最初的處理上都指向虛擬文件系統(tǒng)。這些來自用戶進(jìn)程的調(diào)用，都是標(biāo)準(zhǔn)的 POSIX 系統(tǒng)調(diào)用，比如 open、read、write 和 seek 等。VFS 對(duì)用戶進(jìn)程有一個(gè) 上層 接口，這個(gè)接口就是著名的 POSIX 接口。
能夠使文件系統(tǒng)工作是一回事，能夠使文件系統(tǒng)高效、穩(wěn)定的工作是另一回事，下面我們就來探討一下文件系統(tǒng)的管理和優(yōu)化。
文件通常存在磁盤中，所以如何管理磁盤空間是一個(gè)操作系統(tǒng)的設(shè)計(jì)者需要考慮的問題。在文件上進(jìn)行存有兩種策略：「分配 n 個(gè)字節(jié)的連續(xù)磁盤空間；或者把文件拆分成多個(gè)并不一定連續(xù)的塊」。在存儲(chǔ)管理系統(tǒng)中，主要有分段管理和 分頁管理 兩種方式。
正如我們所看到的，按連續(xù)字節(jié)序列存儲(chǔ)文件有一個(gè)明顯的問題，當(dāng)文件擴(kuò)大時(shí)，有可能需要在磁盤上移動(dòng)文件。內(nèi)存中分段也有同樣的問題。不同的是，相對(duì)于把文件從磁盤的一個(gè)位置移動(dòng)到另一個(gè)位置，內(nèi)存中段的移動(dòng)操作要快很多。因此，幾乎所有的文件系統(tǒng)都把文件分割成固定大小的塊來存儲(chǔ)。
一旦把文件分為固定大小的塊來存儲(chǔ)，就會(huì)出現(xiàn)問題，塊的大小是多少？按照「磁盤組織方式，扇區(qū)、磁道和柱面顯然都可以作為分配單位」。在分頁系統(tǒng)中，分頁大小也是主要因素。
擁有大的塊尺寸意味著每個(gè)文件，甚至 1 字節(jié)文件，都要占用一個(gè)柱面空間，也就是說小文件浪費(fèi)了大量的磁盤空間。另一方面，小塊意味著大部分文件將會(huì)跨越多個(gè)塊，因此需要多次搜索和旋轉(zhuǎn)延遲才能讀取它們，從而降低了性能。因此，如果分配的塊太大會(huì)浪費(fèi)空間；分配的塊太小會(huì)浪費(fèi)時(shí)間。
一旦指定了塊大小，下一個(gè)問題就是怎樣跟蹤空閑塊。有兩種方法被廣泛采用，如下圖所示
第一種方法是采用磁盤塊鏈表，鏈表的每個(gè)塊中包含極可能多的空閑磁盤塊號(hào)。對(duì)于 1 KB 的塊和 32 位的磁盤塊號(hào)，空閑表中每個(gè)塊包含有 255 個(gè)空閑的塊號(hào)。考慮 1 TB 的硬盤，擁有大概十億個(gè)磁盤塊。為了存儲(chǔ)全部地址塊號(hào)，如果每塊可以保存 255 個(gè)塊號(hào)，則需要將近 400 萬個(gè)塊。通常，空閑塊用于保存空閑列表，因此存儲(chǔ)基本上是空閑的。
另一種空閑空間管理的技術(shù)是位圖(bitmap)，n 個(gè)塊的磁盤需要 n 位位圖。在位圖中，空閑塊用 1 表示，已分配的塊用 0 表示。對(duì)于 1 TB 硬盤的例子，需要 10 億位表示，即需要大約 130 000 個(gè) 1 KB 塊存儲(chǔ)。很明顯，和 32 位鏈表模型相比，位圖需要的空間更少，因?yàn)槊總€(gè)塊使用 1 位。只有當(dāng)磁盤快滿的時(shí)候，鏈表需要的塊才會(huì)比位圖少。
為了防止一些用戶占用太多的磁盤空間，多用戶操作通常提供一種磁盤配額(enforcing disk quotas)的機(jī)制。系統(tǒng)管理員為每個(gè)用戶分配「最大的文件和塊分配」，并且操作系統(tǒng)確保用戶不會(huì)超過其配額。我們下面會(huì)談到這一機(jī)制。
在用戶打開一個(gè)文件時(shí)，操作系統(tǒng)會(huì)找到文件屬性和磁盤地址，并把它們送入內(nèi)存中的打開文件表。其中一個(gè)屬性告訴文件所有者是誰。任何有關(guān)文件的增加都會(huì)記到所有者的配額中。
第二張表包含了每個(gè)用戶當(dāng)前打開文件的配額記錄，即使是其他人打開該文件也一樣。如上圖所示，該表的內(nèi)容是從被打開文件的所有者的磁盤配額文件中提取出來的。當(dāng)所有文件關(guān)閉時(shí)，該記錄被寫回配額文件。
當(dāng)在打開文件表中建立一新表項(xiàng)時(shí)，會(huì)產(chǎn)生一個(gè)指向所有者配額記錄的指針。每次向文件中添加一個(gè)塊時(shí)，文件所有者所用數(shù)據(jù)塊的總數(shù)也隨之增加，并會(huì)同時(shí)增加硬限制和軟限制的檢查?？梢猿鲕浵拗?，但硬限制不可以超出。當(dāng)已達(dá)到硬限制時(shí)，再往文件中添加內(nèi)容將引發(fā)錯(cuò)誤。同樣，對(duì)文件數(shù)目也存在類似的檢查。
做文件備份很耗費(fèi)時(shí)間而且也很浪費(fèi)空間，這會(huì)引起下面幾個(gè)問題。首先，是要「備份整個(gè)文件還是僅備份一部分呢」？一般來說，只是備份特定目錄及其下的全部文件，而不是備份整個(gè)文件系統(tǒng)。
其次，對(duì)上次未修改過的文件再進(jìn)行備份是一種浪費(fèi)，因而產(chǎn)生了一種增量轉(zhuǎn)儲(chǔ)(incremental dumps) 的思想。最簡單的增量轉(zhuǎn)儲(chǔ)的形式就是周期性的做全面的備份，而每天只對(duì)增量轉(zhuǎn)儲(chǔ)完成后發(fā)生變化的文件做單個(gè)備份。
稍微好一點(diǎn)的方式是只備份最近一次轉(zhuǎn)儲(chǔ)以來更改過的文件。當(dāng)然，這種做法極大的縮減了轉(zhuǎn)儲(chǔ)時(shí)間，但恢復(fù)起來卻更復(fù)雜，因?yàn)?strong>「最近的全面轉(zhuǎn)儲(chǔ)先要全部恢復(fù)，隨后按逆序進(jìn)行增量轉(zhuǎn)儲(chǔ)」。為了方便恢復(fù)，人們往往使用更復(fù)雜的轉(zhuǎn)儲(chǔ)模式。
第三，既然待轉(zhuǎn)儲(chǔ)的往往是海量數(shù)據(jù)，那么在將其寫入磁帶之前對(duì)文件進(jìn)行壓縮就很有必要。但是，如果在備份過程中出現(xiàn)了文件損壞的情況，就會(huì)導(dǎo)致破壞壓縮算法，從而使整個(gè)磁帶無法讀取。所以在備份前是否進(jìn)行文件壓縮需慎重考慮。
第四，對(duì)正在使用的文件系統(tǒng)做備份是很難的。如果在轉(zhuǎn)儲(chǔ)過程中要添加，刪除和修改文件和目錄，則轉(zhuǎn)儲(chǔ)結(jié)果可能不一致。因此，因?yàn)檗D(zhuǎn)儲(chǔ)過程中需要花費(fèi)數(shù)個(gè)小時(shí)的時(shí)間，所以有必要在晚上將系統(tǒng)脫機(jī)進(jìn)行備份，然而這種方式的接受程度并不高。所以，人們修改了轉(zhuǎn)儲(chǔ)算法，記下文件系統(tǒng)的瞬時(shí)快照，即復(fù)制關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，然后需要把將來對(duì)文件和目錄所做的修改復(fù)制到塊中，而不是到處更新他們。
磁盤轉(zhuǎn)儲(chǔ)到備份磁盤上有兩種方案：「物理轉(zhuǎn)儲(chǔ)和邏輯轉(zhuǎn)儲(chǔ)」。物理轉(zhuǎn)儲(chǔ)(physical dump) 是從磁盤的 0 塊開始，依次將所有磁盤塊按照順序?qū)懭氲捷敵龃疟P，并在復(fù)制最后一個(gè)磁盤時(shí)停止。這種程序的萬無一失性是其他程序所不具備的。
第二個(gè)需要考慮的是「壞塊的轉(zhuǎn)儲(chǔ)」。制造大型磁盤而沒有瑕疵是不可能的，所以也會(huì)存在一些壞塊(bad blocks)。有時(shí)進(jìn)行低級(jí)格式化后，壞塊會(huì)被檢測(cè)出來并進(jìn)行標(biāo)記，這種情況的解決辦法是用磁盤末尾的一些空閑塊所替換。
然而，一些塊在格式化后會(huì)變壞，在這種情況下操作系統(tǒng)可以檢測(cè)到它們。通常情況下，它可以通過創(chuàng)建一個(gè)由所有壞塊組成的文件來解決問題，確保它們不會(huì)出現(xiàn)在空閑池中并且永遠(yuǎn)不會(huì)被分配。「那么此文件是完全不可讀的」。如果磁盤控制器將所有的壞塊重新映射，物理轉(zhuǎn)儲(chǔ)還是能夠正常工作的。
Windows 系統(tǒng)有分頁文件(paging files) 和 休眠文件(hibernation files) 。它們?cè)谖募€原時(shí)不發(fā)揮作用，同時(shí)也不應(yīng)該在第一時(shí)間進(jìn)行備份。
影響可靠性的一個(gè)因素是文件系統(tǒng)的一致性。許多文件系統(tǒng)讀取磁盤塊、修改磁盤塊、再把它們寫回磁盤。如果系統(tǒng)在所有塊寫入之前崩潰，文件系統(tǒng)就會(huì)處于一種不一致(inconsistent)的狀態(tài)。如果某些尚未寫回的塊是索引節(jié)點(diǎn)塊，目錄塊或包含空閑列表的塊，則此問題是很嚴(yán)重的。
為了處理文件系統(tǒng)一致性問題，大部分計(jì)算機(jī)都會(huì)有應(yīng)用程序來檢查文件系統(tǒng)的一致性。例如，UNIX 有 fsck；Windows 有 sfc，每當(dāng)引導(dǎo)系統(tǒng)時(shí)（尤其是在崩潰后），都可以運(yùn)行該程序。
可以進(jìn)行兩種一致性檢查：「塊的一致性檢查和文件的一致性檢查」。為了檢查塊的一致性，應(yīng)用程序會(huì)建立兩張表，每個(gè)包含一個(gè)計(jì)數(shù)器的塊，最初設(shè)置為 0 。第一個(gè)表中的計(jì)數(shù)器跟蹤該塊在文件中出現(xiàn)的次數(shù)，第二張表中的計(jì)數(shù)器記錄每個(gè)塊在空閑列表、空閑位圖中出現(xiàn)的頻率。
訪問磁盤的效率要比內(nèi)存滿的多，是時(shí)候又祭出這張圖了
從內(nèi)存讀一個(gè) 32 位字大概是 10ns，從硬盤上讀的速率大概是 100MB/S，對(duì)每個(gè) 32 位字來說，效率會(huì)慢了四倍，另外，還要加上 5 - 10 ms 的尋道時(shí)間等其他損耗，如果只訪問一個(gè)字，內(nèi)存要比磁盤快百萬數(shù)量級(jí)。所以磁盤優(yōu)化是很有必要的，下面我們會(huì)討論幾種優(yōu)化方式
最常用的減少磁盤訪問次數(shù)的技術(shù)是使用 塊高速緩存(block cache) 或者 緩沖區(qū)高速緩存(buffer cache)。高速緩存指的是一系列的塊，它們?cè)谶壿嬌蠈儆诖疟P，但實(shí)際上基于性能的考慮被保存在內(nèi)存中。
管理高速緩存有不同的算法，常用的算法是：檢查全部的讀請(qǐng)求，查看在高速緩存中是否有所需要的塊。如果存在，可執(zhí)行讀操作而無須訪問磁盤。如果檢查塊不再高速緩存中，那么首先把它讀入高速緩存，再復(fù)制到所需的地方。之后，對(duì)同一個(gè)塊的請(qǐng)求都通過高速緩存來完成。
高速緩存的操作如下圖所示
由于在高速緩存中有許多塊，所以需要某種方法快速確定所需的塊是否存在。常用方法是將設(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)的性能是，在需要用到塊之前，試圖提前將其寫入高速緩存，從而提高命中率。許多文件都是順序讀取。如果請(qǐng)求文件系統(tǒng)在某個(gè)文件中生成塊 k，文件系統(tǒng)執(zhí)行相關(guān)操作并且在完成之后，會(huì)檢查高速緩存，以便確定塊 k + 1 是否已經(jīng)在高速緩存。如果不在，文件系統(tǒng)會(huì)為 k + 1 安排一個(gè)預(yù)讀取，因?yàn)槲募Ｍ谟玫皆搲K的時(shí)候能夠直接從高速緩存中讀取。
當(dāng)然，塊提前讀取策略只適用于實(shí)際順序讀取的文件。對(duì)隨機(jī)訪問的文件，提前讀絲毫不起作用。甚至還會(huì)造成阻礙。
高速緩存和塊提前讀并不是提高文件系統(tǒng)性能的唯一方法。另一種重要的技術(shù)是「把有可能順序訪問的塊放在一起，當(dāng)然最好是在同一個(gè)柱面上，從而減少磁盤臂的移動(dòng)次數(shù)」。當(dāng)寫一個(gè)輸出文件時(shí)，文件系統(tǒng)就必須按照要求一次一次地分配磁盤塊。如果用位圖來記錄空閑塊，并且整個(gè)位圖在內(nèi)存中，那么選擇與前一塊最近的空閑塊是很容易的。如果用空閑表，并且鏈表的一部分存在磁盤上，要分配緊鄰的空閑塊就會(huì)困難很多。
在初始安裝操作系統(tǒng)后，文件就會(huì)被不斷的創(chuàng)建和清除，于是磁盤會(huì)產(chǎn)生很多的碎片，在創(chuàng)建一個(gè)文件時(shí)，它使用的塊會(huì)散布在整個(gè)磁盤上，降低性能。刪除文件后，回收磁盤塊，可能會(huì)造成空穴。
磁盤性能可以通過如下方式恢復(fù)：移動(dòng)文件使它們相互挨著，并把所有的至少是大部分的空閑空間放在一個(gè)或多個(gè)大的連續(xù)區(qū)域內(nèi)。Windows 有一個(gè)程序 defrag 就是做這個(gè)事兒的。Windows 用戶會(huì)經(jīng)常使用它，SSD 除外。
磁盤碎片整理程序會(huì)在讓文件系統(tǒng)上很好地運(yùn)行。Linux 文件系統(tǒng)（特別是 ext2 和 ext3）由于其選擇磁盤塊的方式，在磁盤碎片整理上一般不會(huì)像 Windows 一樣困難，因此很少需要手動(dòng)的磁盤碎片整理。而且，固態(tài)硬盤并不受磁盤碎片的影響，事實(shí)上，在固態(tài)硬盤上做磁盤碎片整理反
下面我們來探討一下 I/O 流程問題。
什么是 I/O 設(shè)備？I/O 設(shè)備又叫做輸入/輸出設(shè)備，它是人類用來和計(jì)算機(jī)進(jìn)行通信的外部硬件。輸入/輸出設(shè)備能夠向計(jì)算機(jī)發(fā)送數(shù)據(jù)（輸出）并從計(jì)算機(jī)接收數(shù)據(jù)（輸入）。
I/O 設(shè)備(I/O devices)可以分成兩種：塊設(shè)備(block devices) 和 字符設(shè)備(character devices)。
塊設(shè)備是一個(gè)能存儲(chǔ)固定大小塊信息的設(shè)備，它支持「以固定大小的塊，扇區(qū)或群集讀取和（可選）寫入數(shù)據(jù)」。每個(gè)塊都有自己的物理地址。通常塊的大小在 512 - 65536 之間。所有傳輸?shù)男畔⒍紩?huì)以連續(xù)的塊為單位。塊設(shè)備的基本特征是每個(gè)塊都較為對(duì)立，能夠獨(dú)立的進(jìn)行讀寫。常見的塊設(shè)備有 「硬盤、藍(lán)光光盤、USB 盤」
與字符設(shè)備相比，塊設(shè)備通常需要較少的引腳。
基于給定固態(tài)存儲(chǔ)器的塊設(shè)備比基于相同類型的存儲(chǔ)器的字節(jié)尋址要慢一些，因?yàn)楸仨氃趬K的開頭開始讀取或?qū)懭?。所以，要讀取該塊的任何部分，必須尋找到該塊的開始，讀取整個(gè)塊，如果不使用該塊，則將其丟棄。要寫入塊的一部分，必須尋找到塊的開始，將整個(gè)塊讀入內(nèi)存，修改數(shù)據(jù)，再次尋找到塊的開頭處，然后將整個(gè)塊寫回設(shè)備。
另一類 I/O 設(shè)備是字符設(shè)備。字符設(shè)備以字符為單位發(fā)送或接收一個(gè)字符流，而不考慮任何塊結(jié)構(gòu)。字符設(shè)備是不可尋址的，也沒有任何尋道操作。常見的字符設(shè)備有 「打印機(jī)、網(wǎng)絡(luò)設(shè)備、鼠標(biāo)、以及大多數(shù)與磁盤不同的設(shè)備」。
設(shè)備控制器是處理 CPU 傳入和傳出信號(hào)的系統(tǒng)。設(shè)備通過插頭和插座連接到計(jì)算機(jī)，并且插座連接到設(shè)備控制器。設(shè)備控制器從連接的設(shè)備處接收數(shù)據(jù)，并將其存儲(chǔ)在控制器內(nèi)部的一些特殊目的寄存器(special purpose registers) 也就是本地緩沖區(qū)中。
每個(gè)設(shè)備控制器都會(huì)有一個(gè)應(yīng)用程序與之對(duì)應(yīng)，設(shè)備控制器通過應(yīng)用程序的接口通過中斷與操作系統(tǒng)進(jìn)行通信。設(shè)備控制器是硬件，而設(shè)備驅(qū)動(dòng)程序是軟件。
每個(gè)控制器都會(huì)有幾個(gè)寄存器用來和 CPU 進(jìn)行通信。通過寫入這些寄存器，操作系統(tǒng)可以命令設(shè)備發(fā)送數(shù)據(jù)，接收數(shù)據(jù)、開啟或者關(guān)閉設(shè)備等。通過從這些寄存器中讀取信息，操作系統(tǒng)能夠知道設(shè)備的狀態(tài)，是否準(zhǔn)備接受一個(gè)新命令等。
為了控制寄存器，許多設(shè)備都會(huì)有數(shù)據(jù)緩沖區(qū)(data buffer)，來供系統(tǒng)進(jìn)行讀寫。
那么問題來了，CPU 如何與設(shè)備寄存器和設(shè)備數(shù)據(jù)緩沖區(qū)進(jìn)行通信呢？存在兩個(gè)可選的方式。第一種方法是，每個(gè)控制寄存器都被分配一個(gè) I/O 端口(I/O port)號(hào)，這是一個(gè) 8 位或 16 位的整數(shù)。所有 I/O 端口的集合形成了受保護(hù)的 I/O 端口空間，以便普通用戶程序無法訪問它（只有操作系統(tǒng)可以訪問）。使用特殊的 I/O 指令像是
IN REG,PORTCPU 可以讀取控制寄存器 PORT 的內(nèi)容并將結(jié)果放在 CPU 寄存器 REG 中。類似的，使用
OUT PORT,REGCPU 可以將 REG 的內(nèi)容寫到控制寄存器中。大多數(shù)早期計(jì)算機(jī)，包括幾乎所有大型主機(jī)，如 IBM 360 及其所有后續(xù)機(jī)型，都是以這種方式工作的。
第二個(gè)方法是 PDP-11 引入的，它將「所有控制寄存器映射到內(nèi)存空間」中。
無論一個(gè) CPU 是否具有內(nèi)存映射 I/O，它都需要尋址設(shè)備控制器以便與它們交換數(shù)據(jù)。CPU 可以從 I/O 控制器每次請(qǐng)求一個(gè)字節(jié)的數(shù)據(jù)，但是這么做會(huì)浪費(fèi) CPU 時(shí)間，所以經(jīng)常會(huì)用到一種稱為直接內(nèi)存訪問(Direct Memory Access) 的方案。為了簡化，我們假設(shè) CPU 通過單一的系統(tǒng)總線訪問所有的設(shè)備和內(nèi)存，該總線連接 CPU 、內(nèi)存和 I/O 設(shè)備，如下圖所示
現(xiàn)代操作系統(tǒng)實(shí)際更為復(fù)雜，但是原理是相同的。如果硬件有DMA 控制器，那么操作系統(tǒng)只能使用 DMA有時(shí)這個(gè)控制器會(huì)集成到磁盤控制器和其他控制器中，但這種設(shè)計(jì)需要在每個(gè)設(shè)備上都裝有一個(gè)分離的 DMA 控制器。單個(gè)的 DMA 控制器可用于向多個(gè)設(shè)備傳輸，這種傳輸往往同時(shí)進(jìn)行。
首先 CPU 通過設(shè)置 DMA 控制器的寄存器對(duì)它進(jìn)行編程，所以 DMA 控制器知道將什么數(shù)據(jù)傳送到什么地方。DMA 控制器還要向磁盤控制器發(fā)出一個(gè)命令，通知它從磁盤讀數(shù)據(jù)到其內(nèi)部的緩沖區(qū)并檢驗(yàn)校驗(yàn)和。當(dāng)有效數(shù)據(jù)位于磁盤控制器的緩沖區(qū)中時(shí)，DMA 就可以開始了。
DMA 控制器通過在總線上發(fā)出一個(gè)讀請(qǐng)求到磁盤控制器而發(fā)起 DMA 傳送，這是第二步。這個(gè)讀請(qǐng)求就像其他讀請(qǐng)求一樣，磁盤控制器并不知道或者并不關(guān)心它是來自 CPU 還是來自 DMA 控制器。通常情況下，要寫的內(nèi)存地址在總線的地址線上，所以當(dāng)磁盤控制器去匹配下一個(gè)字時(shí)，它知道將該字寫到什么地方。寫到內(nèi)存就是另外一個(gè)總線循環(huán)了，這是第三步。當(dāng)寫操作完成時(shí)，磁盤控制器在總線上發(fā)出一個(gè)應(yīng)答信號(hào)到 DMA 控制器，這是第四步。
然后，DMA 控制器會(huì)增加內(nèi)存地址并減少字節(jié)數(shù)量。如果字節(jié)數(shù)量仍然大于 0 ，就會(huì)循環(huán)步驟 2 - 步驟 4 ，直到字節(jié)計(jì)數(shù)變?yōu)?0 。此時(shí)，DMA 控制器會(huì)打斷 CPU 并告訴它傳輸已經(jīng)完成了。
在一臺(tái)個(gè)人計(jì)算機(jī)體系結(jié)構(gòu)中，中斷結(jié)構(gòu)會(huì)如下所示
當(dāng)一個(gè) I/O 設(shè)備完成它的工作后，它就會(huì)產(chǎn)生一個(gè)中斷（默認(rèn)操作系統(tǒng)已經(jīng)開啟中斷），它通過在總線上聲明已分配的信號(hào)來實(shí)現(xiàn)此目的。主板上的中斷控制器芯片會(huì)檢測(cè)到這個(gè)信號(hào)，然后執(zhí)行中斷操作。
使機(jī)器處于良好狀態(tài)的中斷稱為精確中斷(precise interrupt)。這樣的中斷具有四個(gè)屬性：
不滿足以上要求的中斷稱為 不精確中斷(imprecise interrupt)，不精確中斷讓人很頭疼。上圖描述了不精確中斷的現(xiàn)象。指令的執(zhí)行時(shí)序和完成度具有不確定性，而且恢復(fù)起來也非常麻煩。
I/O 軟件設(shè)計(jì)一個(gè)很重要的目標(biāo)就是設(shè)備獨(dú)立性(device independence)。這意味著「我們能夠編寫訪問任何設(shè)備的應(yīng)用程序，而不用事先指定特定的設(shè)備」。
除了設(shè)備獨(dú)立性外，I/O 軟件實(shí)現(xiàn)的第二個(gè)重要的目標(biāo)就是錯(cuò)誤處理(error handling)。通常情況下來說，錯(cuò)誤應(yīng)該交給硬件層面去處理。如果設(shè)備控制器發(fā)現(xiàn)了讀錯(cuò)誤的話，它會(huì)盡可能的去修復(fù)這個(gè)錯(cuò)誤。如果設(shè)備控制器處理不了這個(gè)問題，那么設(shè)備驅(qū)動(dòng)程序應(yīng)該進(jìn)行處理，設(shè)備驅(qū)動(dòng)程序會(huì)再次嘗試讀取操作，很多錯(cuò)誤都是偶然性的，如果設(shè)備驅(qū)動(dòng)程序無法處理這個(gè)錯(cuò)誤，才會(huì)把錯(cuò)誤向上拋到硬件層面（上層）進(jìn)行處理，很多時(shí)候，上層并不需要知道下層是如何解決錯(cuò)誤的。
I/O 軟件實(shí)現(xiàn)的第三個(gè)目標(biāo)就是 同步(synchronous) 和 異步(asynchronous，即中斷驅(qū)動(dòng))傳輸。這里先說一下同步和異步是怎么回事吧。
同步傳輸中數(shù)據(jù)通常以塊或幀的形式發(fā)送。發(fā)送方和接收方在數(shù)據(jù)傳輸之前應(yīng)該具有同步時(shí)鐘。而在異步傳輸中，數(shù)據(jù)通常以字節(jié)或者字符的形式發(fā)送，異步傳輸則不需要同步時(shí)鐘，但是會(huì)在傳輸之前向數(shù)據(jù)添加奇偶校驗(yàn)位。大部分物理IO(physical I/O) 是異步的。物理 I/O 中的 CPU 是很聰明的，CPU 傳輸完成后會(huì)轉(zhuǎn)而做其他事情，它和中斷心靈相通，等到中斷發(fā)生后，CPU 才會(huì)回到傳輸這件事情上來。
I/O 軟件的最后一個(gè)問題是緩沖(buffering)。通常情況下，從一個(gè)設(shè)備發(fā)出的數(shù)據(jù)不會(huì)直接到達(dá)最后的設(shè)備。其間會(huì)經(jīng)過一系列的校驗(yàn)、檢查、緩沖等操作才能到達(dá)。
I/O 軟件引起的最后一個(gè)問題就是共享設(shè)備和獨(dú)占設(shè)備的問題。有些 I/O 設(shè)備能夠被許多用戶共同使用。一些設(shè)備比如磁盤，讓多個(gè)用戶使用一般不會(huì)產(chǎn)生什么問題，但是某些設(shè)備必須具有獨(dú)占性，即只允許單個(gè)用戶使用完成后才能讓其他用戶使用。
一共有三種控制 I/O 設(shè)備的方法
I/O 軟件通常組織成四個(gè)層次，它們的大致結(jié)構(gòu)如下圖所示
下面我們具體的來探討一下上面的層次結(jié)構(gòu)
在計(jì)算機(jī)系統(tǒng)中，中斷就像女人的脾氣一樣無時(shí)無刻都在產(chǎn)生，中斷的出現(xiàn)往往是讓人很不爽的。中斷處理程序又被稱為中斷服務(wù)程序 或者是 ISR(Interrupt Service Routines)，它是最靠近硬件的一層。中斷處理程序由硬件中斷、軟件中斷或者是軟件異常啟動(dòng)產(chǎn)生的中斷，用于實(shí)現(xiàn)設(shè)備驅(qū)動(dòng)程序或受保護(hù)的操作模式（例如系統(tǒng)調(diào)用）之間的轉(zhuǎn)換。
中斷處理程序負(fù)責(zé)處理中斷發(fā)生時(shí)的所有操作，操作完成后阻塞，然后啟動(dòng)中斷驅(qū)動(dòng)程序來解決阻塞。通常會(huì)有三種通知方式，依賴于不同的具體實(shí)現(xiàn)
up 進(jìn)行通知；signal 操作每個(gè)連接到計(jì)算機(jī)的 I/O 設(shè)備都需要有某些特定設(shè)備的代碼對(duì)其進(jìn)行控制。這些提供 I/O 設(shè)備到設(shè)備控制器轉(zhuǎn)換的過程的代碼稱為 設(shè)備驅(qū)動(dòng)程序(Device driver)。
設(shè)備控制器的主要功能有下面這些
接收和識(shí)別命令：設(shè)備控制器可以接受來自 CPU 的指令，并進(jìn)行識(shí)別。設(shè)備控制器內(nèi)部也會(huì)有寄存器，用來存放指令和參數(shù)
進(jìn)行數(shù)據(jù)交換：CPU、控制器和設(shè)備之間會(huì)進(jìn)行數(shù)據(jù)的交換，CPU 通過總線把指令發(fā)送給控制器，或從控制器中并行地讀出數(shù)據(jù)；控制器將數(shù)據(jù)寫入指定設(shè)備。
地址識(shí)別：每個(gè)硬件設(shè)備都有自己的地址，設(shè)備控制器能夠識(shí)別這些不同的地址，來達(dá)到控制硬件的目的，此外，為使 CPU 能向寄存器中寫入或者讀取數(shù)據(jù)，這些寄存器都應(yīng)具有唯一的地址。
差錯(cuò)檢測(cè)：設(shè)備控制器還具有對(duì)設(shè)備傳遞過來的數(shù)據(jù)進(jìn)行檢測(cè)的功能。
在這種情況下，設(shè)備控制器會(huì)阻塞，直到中斷來解除阻塞狀態(tài)。還有一種情況是操作是可以無延遲的完成，所以驅(qū)動(dòng)程序不需要阻塞。在第一種情況下，操作系統(tǒng)可能被中斷喚醒；第二種情況下操作系統(tǒng)不會(huì)被休眠。
設(shè)備驅(qū)動(dòng)程序必須是可重入的，因?yàn)樵O(shè)備驅(qū)動(dòng)程序會(huì)阻塞和喚醒然后再次阻塞。驅(qū)動(dòng)程序不允許進(jìn)行系統(tǒng)調(diào)用，但是它們通常需要與內(nèi)核的其余部分進(jìn)行交互。
I/O 軟件有兩種，一種是我們上面介紹過的基于特定設(shè)備的，還有一種是設(shè)備無關(guān)性的，設(shè)備無關(guān)性也就是不需要特定的設(shè)備。設(shè)備驅(qū)動(dòng)程序與設(shè)備無關(guān)的軟件之間的界限取決于具體的系統(tǒng)。下面顯示的功能由設(shè)備無關(guān)的軟件實(shí)現(xiàn)
與設(shè)備無關(guān)的軟件的基本功能是對(duì)所有設(shè)備執(zhí)行公共的 I/O 功能，并且向用戶層軟件提供一個(gè)統(tǒng)一的接口。
無論是對(duì)于塊設(shè)備還是字符設(shè)備來說，緩沖都是一個(gè)非常重要的考量標(biāo)準(zhǔn)。緩沖技術(shù)應(yīng)用廣泛，但它也有缺點(diǎn)。如果數(shù)據(jù)被緩沖次數(shù)太多，會(huì)影響性能。
在 I/O 中，出錯(cuò)是一種再正常不過的情況了。當(dāng)出錯(cuò)發(fā)生時(shí)，操作系統(tǒng)必須盡可能處理這些錯(cuò)誤。有一些錯(cuò)誤是只有特定的設(shè)備才能處理，有一些是由框架進(jìn)行處理，這些錯(cuò)誤和特定的設(shè)備無關(guān)。
I/O 錯(cuò)誤的一類是程序員編程錯(cuò)誤，比如還沒有打開文件前就讀流，或者不關(guān)閉流導(dǎo)致內(nèi)存溢出等等。這類問題由程序員處理；另外一類是實(shí)際的 I/O 錯(cuò)誤，例如向一個(gè)磁盤壞塊寫入數(shù)據(jù)，無論怎么寫都寫入不了。這類問題由驅(qū)動(dòng)程序處理，驅(qū)動(dòng)程序處理不了交給硬件處理，這個(gè)我們上面也說過。
我們?cè)诓僮飨到y(tǒng)概述中說到，操作系統(tǒng)一個(gè)非常重要的功能就是屏蔽了硬件和軟件的差異性，為硬件和軟件提供了統(tǒng)一的標(biāo)準(zhǔn)，這個(gè)標(biāo)準(zhǔn)還體現(xiàn)在為設(shè)備驅(qū)動(dòng)程序提供統(tǒng)一的接口，因?yàn)椴煌挠布蛷S商編寫的設(shè)備驅(qū)動(dòng)程序不同，所以如果為每個(gè)驅(qū)動(dòng)程序都單獨(dú)提供接口的話，這樣沒法搞，所以必須統(tǒng)一。
一些設(shè)備例如打印機(jī)，它只能由一個(gè)進(jìn)程來使用，這就需要操作系統(tǒng)根據(jù)實(shí)際情況判斷是否能夠?qū)υO(shè)備的請(qǐng)求進(jìn)行檢查，判斷是否能夠接受其他請(qǐng)求，一種比較簡單直接的方式是在特殊文件上執(zhí)行 open操作。如果設(shè)備不可用，那么直接 open 會(huì)導(dǎo)致失敗。還有一種方式是不直接導(dǎo)致失敗，而是讓其阻塞，等到另外一個(gè)進(jìn)程釋放資源后，在進(jìn)行 open 打開操作。這種方式就把選擇權(quán)交給了用戶，由用戶判斷是否應(yīng)該等待。
不同的磁盤會(huì)具有不同的扇區(qū)大小，但是軟件不會(huì)關(guān)心扇區(qū)大小，只管存儲(chǔ)就是了。一些字符設(shè)備可以一次一個(gè)字節(jié)的交付數(shù)據(jù)，而其他的設(shè)備則以較大的單位交付數(shù)據(jù)，這些差異也可以隱藏起來。
雖然大部分 I/O 軟件都在內(nèi)核結(jié)構(gòu)中，但是還有一些在用戶空間實(shí)現(xiàn)的 I/O 軟件，凡事沒有絕對(duì)。一些 I/O 軟件和庫過程在用戶空間存在，然后以提供系統(tǒng)調(diào)用的方式實(shí)現(xiàn)。
盤可以說是硬件里面比較簡單的構(gòu)造了，同時(shí)也是最重要的。下面我們從盤談起，聊聊它的物理構(gòu)造
盤會(huì)有很多種類型。其中最簡單的構(gòu)造就是磁盤(magnetic hard disks)， 也被稱為 hard disk,HDD等。磁盤通常與安裝在磁臂上的磁頭配對(duì)，磁頭可將數(shù)據(jù)讀取或者將數(shù)據(jù)寫入磁盤，因此磁盤的讀寫速度都同樣快。在磁盤中，數(shù)據(jù)是隨機(jī)訪問的，這也就說明可以通過任意的順序來存儲(chǔ)和檢索單個(gè)數(shù)據(jù)塊，所以你可以在任意位置放置磁盤來讓磁頭讀取，磁盤是一種非易失性的設(shè)備，即使斷電也能永久保留。
為了組織和檢索數(shù)據(jù)，會(huì)將磁盤組織成特定的結(jié)構(gòu)，這些特定的結(jié)構(gòu)就是「磁道、扇區(qū)和柱面」
磁盤被組織成柱面形式，每個(gè)盤用軸相連，每一個(gè)柱面包含若干磁道，每個(gè)磁道由若干扇區(qū)組成。軟盤上大約每個(gè)磁道有 8 - 32 個(gè)扇區(qū)，硬盤上每條磁道上扇區(qū)的數(shù)量可達(dá)幾百個(gè)，磁頭大約是 1 - 16 個(gè)。
對(duì)于磁盤驅(qū)動(dòng)程序來說，一個(gè)非常重要的特性就是控制器是否能夠同時(shí)控制兩個(gè)或者多個(gè)驅(qū)動(dòng)器進(jìn)行磁道尋址，這就是重疊尋道(overlapped seek)。對(duì)于控制器來說，它能夠控制一個(gè)磁盤驅(qū)動(dòng)程序完成尋道操作，同時(shí)讓其他驅(qū)動(dòng)程序等待尋道結(jié)束?？刂破饕部梢栽谝粋€(gè)驅(qū)動(dòng)程序上進(jìn)行讀寫草哦做，與此同時(shí)讓另外的驅(qū)動(dòng)器進(jìn)行尋道操作，但是軟盤控制器不能在兩個(gè)驅(qū)動(dòng)器上進(jìn)行讀寫操作。
RAID 稱為 磁盤冗余陣列，簡稱 磁盤陣列。利用虛擬化技術(shù)把多個(gè)硬盤結(jié)合在一起，成為一個(gè)或多個(gè)磁盤陣列組，目的是提升性能或數(shù)據(jù)冗余。
RAID 有不同的級(jí)別
磁盤由一堆鋁的、合金或玻璃的盤片組成，磁盤剛被創(chuàng)建出來后，沒有任何信息。磁盤在使用前必須經(jīng)過低級(jí)格式化(low-levvel format)，下面是一個(gè)扇區(qū)的格式
前導(dǎo)碼相當(dāng)于是標(biāo)示扇區(qū)的開始位置，通常以位模式開始，前導(dǎo)碼還包括柱面號(hào)、扇區(qū)號(hào)等一些其他信息。緊隨前導(dǎo)碼后面的是數(shù)據(jù)區(qū)，數(shù)據(jù)部分的大小由低級(jí)格式化程序來確定。大部分磁盤使用 512 字節(jié)的扇區(qū)。數(shù)據(jù)區(qū)后面是 ECC，ECC 的全稱是 「error correction code」 ，數(shù)據(jù)糾錯(cuò)碼，它與普通的錯(cuò)誤檢測(cè)不同，ECC 還可以用于恢復(fù)讀錯(cuò)誤。ECC 階段的大小由不同的磁盤制造商實(shí)現(xiàn)。ECC 大小的設(shè)計(jì)標(biāo)準(zhǔn)取決于「設(shè)計(jì)者愿意犧牲多少磁盤空間來提高可靠性」，以及程序可以處理的 ECC 的復(fù)雜程度。通常情況下 ECC 是 16 位，除此之外，硬盤一般具有一定數(shù)量的備用扇區(qū)，用于替換制造缺陷的扇區(qū)。
下面我們來探討一下關(guān)于影響磁盤讀寫的算法，一般情況下，影響磁盤快讀寫的時(shí)間由下面幾個(gè)因素決定
這三種時(shí)間參數(shù)也是磁盤尋道的過程。一般情況下，尋道時(shí)間對(duì)總時(shí)間的影響最大，所以，有效的降低尋道時(shí)間能夠提高磁盤的讀取速度。
如果磁盤驅(qū)動(dòng)程序每次接收一個(gè)請(qǐng)求并按照接收順序完成請(qǐng)求，這種處理方式也就是 先來先服務(wù)(First-Come, First-served, FCFS) ，這種方式很難優(yōu)化尋道時(shí)間。因?yàn)槊看味紩?huì)按照順序處理，不管順序如何，有可能這次讀完后需要等待一個(gè)磁盤旋轉(zhuǎn)一周才能繼續(xù)讀取，而其他柱面能夠馬上進(jìn)行讀取，這種情況下每次請(qǐng)求也會(huì)排隊(duì)。
通常情況下，磁盤在進(jìn)行尋道時(shí)，其他進(jìn)程會(huì)產(chǎn)生其他的磁盤請(qǐng)求。磁盤驅(qū)動(dòng)程序會(huì)維護(hù)一張表，表中會(huì)記錄著柱面號(hào)當(dāng)作索引，每個(gè)柱面未完成的請(qǐng)求會(huì)形成鏈表，鏈表頭存放在表的相應(yīng)表項(xiàng)中。
一種對(duì)先來先服務(wù)的算法改良的方案是使用 最短路徑優(yōu)先(SSF) 算法，下面描述了這個(gè)算法。
假如我們?cè)趯?duì)磁道 6 號(hào)進(jìn)行尋址時(shí)，同時(shí)發(fā)生了對(duì) 11 , 2 , 4, 14, 8, 15, 3 的請(qǐng)求，如果采用先來先服務(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)先級(jí) 問題，
這里有一個(gè)原型可以參考就是我們?nèi)粘Ｉ钪械碾娞?，電梯使用一種電梯算法(elevator algorithm) 來進(jìn)行調(diào)度，從而滿足協(xié)調(diào)效率和公平性這兩個(gè)相互沖突的目標(biāo)。電梯一般會(huì)保持向一個(gè)方向移動(dòng)，直到在那個(gè)方向上沒有請(qǐng)求為止，然后改變方向。
電梯算法需要維護(hù)一個(gè)二進(jìn)制位，也就是當(dāng)前的方向位：UP(向上)或者是 DOWN(向下)。當(dāng)一個(gè)請(qǐng)求處理完成后，磁盤或電梯的驅(qū)動(dòng)程序會(huì)檢查該位，如果此位是 UP 位，磁盤臂或者電梯倉移到下一個(gè)更高跌未完成的請(qǐng)求。如果高位沒有未完成的請(qǐng)求，則取相反方向。當(dāng)方向位是 DOWN時(shí)，同時(shí)存在一個(gè)低位的請(qǐng)求，磁盤臂會(huì)轉(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 算法。
一般壞塊有兩種處理辦法，一種是在控制器中進(jìn)行處理；一種是在操作系統(tǒng)層面進(jìn)行處理。
這兩種方法經(jīng)常替換使用，比如一個(gè)具有 30 個(gè)數(shù)據(jù)扇區(qū)和兩個(gè)備用扇區(qū)的磁盤，其中扇區(qū) 4 是有瑕疵的。
控制器能做的事情就是將備用扇區(qū)之一重新映射。
還有一種處理方式是將所有的扇區(qū)都向上移動(dòng)一個(gè)扇區(qū)
上面這這兩種情況下控制器都必須知道哪個(gè)扇區(qū)，可以通過內(nèi)部的表來跟蹤這一信息，或者通過重寫前導(dǎo)碼來給出重新映射的扇區(qū)號(hào)。如果是重寫前導(dǎo)碼，那么涉及移動(dòng)的方式必須重寫后面所有的前導(dǎo)碼，但是最終會(huì)提供良好的性能。
磁盤經(jīng)常會(huì)出現(xiàn)錯(cuò)誤，導(dǎo)致好的扇區(qū)會(huì)變成壞扇區(qū)，驅(qū)動(dòng)程序也有可能掛掉。RAID 可以對(duì)扇區(qū)出錯(cuò)或者是驅(qū)動(dòng)器崩潰提出保護(hù)，然而 RAID 卻不能對(duì)壞數(shù)據(jù)中的寫錯(cuò)誤提供保護(hù)，也不能對(duì)寫操作期間的崩潰提供保護(hù)，這樣就會(huì)破壞原始數(shù)據(jù)。
我們期望磁盤能夠準(zhǔn)確無誤的工作，但是事實(shí)情況是不可能的，但是我們能夠知道的是，一個(gè)磁盤子系統(tǒng)具有如下特性：當(dāng)一個(gè)寫命令發(fā)給它時(shí)，磁盤要么正確地寫數(shù)據(jù)，要么什么也不做，讓現(xiàn)有的數(shù)據(jù)完整無誤的保留。這樣的系統(tǒng)稱為 穩(wěn)定存儲(chǔ)器(stable storage)。穩(wěn)定存儲(chǔ)器的目標(biāo)就是不惜一切代價(jià)保證磁盤的一致性。
穩(wěn)定存儲(chǔ)器使用兩個(gè)一對(duì)相同的磁盤，對(duì)應(yīng)的塊一同工作形成一個(gè)無差別的塊。穩(wěn)定存儲(chǔ)器為了實(shí)現(xiàn)這個(gè)目的，定義了下面三種操作：
穩(wěn)定寫(stable write)穩(wěn)定讀(stable read)崩潰恢復(fù)(crash recovery)時(shí)鐘(Clocks) 也被稱為定時(shí)器(timers)，時(shí)鐘/定時(shí)器對(duì)任何程序系統(tǒng)來說都是必不可少的。時(shí)鐘負(fù)責(zé)維護(hù)時(shí)間、防止一個(gè)進(jìn)程長期占用 CPU 時(shí)間等其他功能。時(shí)鐘軟件(clock software) 也是一種設(shè)備驅(qū)動(dòng)的方式。下面我們就來對(duì)時(shí)鐘進(jìn)行介紹，一般都是先討論硬件再介紹軟件，采用由下到上的方式，也是告訴你，底層是最重要的。
在計(jì)算機(jī)中有兩種類型的時(shí)鐘，這些時(shí)鐘與現(xiàn)實(shí)生活中使用的時(shí)鐘完全不一樣。
電壓周期會(huì)產(chǎn)生一個(gè)中斷，大概是 50 - 60 HZ。這些時(shí)鐘過去一直占據(jù)支配地位。這種時(shí)鐘稱為可編程時(shí)鐘 ，可編程時(shí)鐘有兩種模式，一種是 一鍵式(one-shot mode)，當(dāng)時(shí)鐘啟動(dòng)時(shí)，會(huì)把存儲(chǔ)器中的值復(fù)制到計(jì)數(shù)器中，然后，每次晶體的振蕩器的脈沖都會(huì)使計(jì)數(shù)器 -1。當(dāng)計(jì)數(shù)器變?yōu)?0 時(shí)，會(huì)產(chǎn)生一個(gè)中斷，并停止工作，直到軟件再一次顯示啟動(dòng)。還有一種模式時(shí) 方波(square-wave mode) 模式，在這種模式下，當(dāng)計(jì)數(shù)器變?yōu)?0 并產(chǎn)生中斷后，存儲(chǔ)寄存器的值會(huì)自動(dòng)復(fù)制到計(jì)數(shù)器中，這種周期性的中斷稱為一個(gè)時(shí)鐘周期。
時(shí)鐘硬件所做的工作只是根據(jù)已知的時(shí)間間隔產(chǎn)生中斷，而其他的工作都是由時(shí)鐘軟件來完成，一般操作系統(tǒng)的不同，時(shí)鐘軟件的具體實(shí)現(xiàn)也不同，但是一般都會(huì)包括以下這幾點(diǎn)
時(shí)鐘軟件也被稱為可編程時(shí)鐘，可以設(shè)置它以程序需要的任何速率引發(fā)中斷。時(shí)鐘軟件觸發(fā)的中斷是一種硬中斷，但是某些應(yīng)用程序?qū)τ谟仓袛鄟碚f是不可接受的。
這時(shí)候就需要一種軟定時(shí)器(soft timer) 避免了中斷，無論何時(shí)當(dāng)內(nèi)核因?yàn)槟撤N原因呢在運(yùn)行時(shí)，它返回用戶態(tài)之前都會(huì)檢查時(shí)鐘來了解軟定時(shí)器是否到期。如果軟定時(shí)器到期，則執(zhí)行被調(diào)度的事件也無需切換到內(nèi)核態(tài)，因?yàn)楸旧硪呀?jīng)處于內(nèi)核態(tài)中。這種方式避免了頻繁的內(nèi)核態(tài)和用戶態(tài)之前的切換，提高了程序運(yùn)行效率。
軟定時(shí)器因?yàn)椴煌脑蚯袚Q進(jìn)入內(nèi)核態(tài)的速率不同，原因主要有
死鎖問題也是操作系統(tǒng)非常重要的一類問題
大部分的死鎖都和資源有關(guān)，在進(jìn)程對(duì)設(shè)備、文件具有獨(dú)占性（排他性）時(shí)會(huì)產(chǎn)生死鎖。我們把這類需要排他性使用的對(duì)象稱為資源(resource)。資源主要分為 「可搶占資源和不可搶占資源」
可搶占資源和不可搶占資源
資源主要有可搶占資源和不可搶占資源。可搶占資源(preemptable resource) 可以從擁有它的進(jìn)程中搶占而不會(huì)造成其他影響，內(nèi)存就是一種可搶占性資源，任何進(jìn)程都能夠搶先獲得內(nèi)存的使用權(quán)。
不可搶占資源(nonpreemtable resource) 指的是除非引起錯(cuò)誤或者異常，否則進(jìn)程無法搶占指定資源，這種不可搶占的資源比如有光盤，在進(jìn)程執(zhí)行調(diào)度的過程中，其他進(jìn)程是不能得到該資源的。
如果要對(duì)死鎖進(jìn)行一個(gè)定義的話，下面的定義比較貼切
「如果一組進(jìn)程中的每個(gè)進(jìn)程都在等待一個(gè)事件，而這個(gè)事件只能由該組中的另一個(gè)進(jìn)程觸發(fā)，這種情況會(huì)導(dǎo)致死鎖」。
針對(duì)我們上面的描述，資源死鎖可能出現(xiàn)的情況主要有
發(fā)生死鎖時(shí)，上面的情況必須同時(shí)會(huì)發(fā)生。如果其中任意一個(gè)條件不會(huì)成立，死鎖就不會(huì)發(fā)生?？梢酝ㄟ^破壞其中任意一個(gè)條件來破壞死鎖，下面這些破壞條件就是我們探討的重點(diǎn)
Holt 在 1972 年提出對(duì)死鎖進(jìn)行建模，建模的標(biāo)準(zhǔn)如下：
從資源節(jié)點(diǎn)到進(jìn)程節(jié)點(diǎn)表示資源已經(jīng)被進(jìn)程占用，如下圖所示
在上圖中表示當(dāng)前資源 R 正在被 A 進(jìn)程所占用
由進(jìn)程節(jié)點(diǎn)到資源節(jié)點(diǎn)的有向圖表示當(dāng)前進(jìn)程正在請(qǐng)求資源，并且該進(jìn)程已經(jīng)被阻塞，處于等待這個(gè)資源的狀態(tài)
在上圖中，表示的含義是進(jìn)程 B 正在請(qǐng)求資源 S 。Holt 認(rèn)為，死鎖的描述應(yīng)該如下
這是一個(gè)死鎖的過程，進(jìn)程 C 等待資源 T 的釋放，資源 T 卻已經(jīng)被進(jìn)程 D 占用，進(jìn)程 D 等待請(qǐng)求占用資源 U ，資源 U 卻已經(jīng)被線程 C 占用，從而形成環(huán)。
有四種處理死鎖的策略：
下面我們分別介紹一下這四種方法
最簡單的解決辦法就是使用鴕鳥算法(ostrich algorithm)，把頭埋在沙子里，假裝問題根本沒有發(fā)生。每個(gè)人看待這個(gè)問題的反應(yīng)都不同。數(shù)學(xué)家認(rèn)為死鎖是不可接受的，必須通過有效的策略來防止死鎖的產(chǎn)生。工程師想要知道問題發(fā)生的頻次，系統(tǒng)因?yàn)槠渌虮罎⒌拇螖?shù)和死鎖帶來的嚴(yán)重后果。如果死鎖發(fā)生的頻次很低，而經(jīng)常會(huì)由于硬件故障、編譯器錯(cuò)誤等其他操作系統(tǒng)問題導(dǎo)致系統(tǒng)崩潰，那么大多數(shù)工程師不會(huì)修復(fù)死鎖。
第二種技術(shù)是死鎖的檢測(cè)和恢復(fù)。這種解決方式不會(huì)嘗試去阻止死鎖的出現(xiàn)。相反，這種解決方案會(huì)希望死鎖盡可能的出現(xiàn)，在監(jiān)測(cè)到死鎖出現(xiàn)后，對(duì)其進(jìn)行恢復(fù)。下面我們就來探討一下死鎖的檢測(cè)和恢復(fù)的幾種方式
每種資源類型都有一個(gè)資源是什么意思？我們經(jīng)常提到的打印機(jī)就是這樣的，資源只有打印機(jī)，但是設(shè)備都不會(huì)超過一個(gè)。
可以通過構(gòu)造一張資源分配表來檢測(cè)這種錯(cuò)誤，比如我們上面提到的
如果這張圖包含了一個(gè)或一個(gè)以上的環(huán)，那么死鎖就存在，處于這個(gè)環(huán)中任意一個(gè)進(jìn)程都是死鎖的進(jìn)程。
如果有多種相同的資源存在，就需要采用另一種方法來檢測(cè)死鎖?？梢酝ㄟ^構(gòu)造一個(gè)矩陣來檢測(cè)從 P1 -> Pn 這 n 個(gè)進(jìn)程中的死鎖。
現(xiàn)在我們提供一種基于矩陣的算法來檢測(cè)從 P1 到 Pn 這 n 個(gè)進(jìn)程中的死鎖。假設(shè)資源類型為 m，E1 代表資源類型1，E2 表示資源類型 2 ，Ei 代表資源類型 i (1 <= i <= m)。E 表示的是 現(xiàn)有資源向量(existing resource vector)，代表每種已存在的資源總數(shù)。
現(xiàn)在我們就需要構(gòu)造兩個(gè)數(shù)組：C 表示的是當(dāng)前分配矩陣(current allocation matrix) ，R 表示的是 請(qǐng)求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數(shù)。所以，Cij 表示 Pi 持有資源 j 的數(shù)量。Rij 表示 Pi 所需要獲得的資源 j 的數(shù)量
一般來說，已分配資源 j 的數(shù)量加起來再和所有可供使用的資源數(shù)相加 = 該類資源的總數(shù)。
死鎖的檢測(cè)就是基于向量的比較。每個(gè)進(jìn)程起初都是沒有被標(biāo)記過的，算法會(huì)開始對(duì)進(jìn)程做標(biāo)記，進(jìn)程被標(biāo)記后說明進(jìn)程被執(zhí)行了，不會(huì)進(jìn)入死鎖，當(dāng)算法結(jié)束時(shí)，任何沒有被標(biāo)記過的進(jìn)程都會(huì)被判定為死鎖進(jìn)程。
上面我們探討了兩種檢測(cè)死鎖的方式，那么現(xiàn)在你知道怎么檢測(cè)后，你何時(shí)去做死鎖檢測(cè)呢？一般來說，有兩個(gè)考量標(biāo)準(zhǔn)：
上面我們探討了如何檢測(cè)進(jìn)程死鎖，我們最終的目的肯定是想讓程序能夠正常的運(yùn)行下去，所以針對(duì)檢測(cè)出來的死鎖，我們要對(duì)其進(jìn)行恢復(fù)，下面我們會(huì)探討幾種死鎖的恢復(fù)方式
在某些情況下，可能會(huì)臨時(shí)將某個(gè)資源從它的持有者轉(zhuǎn)移到另一個(gè)進(jìn)程。比如在不通知原進(jìn)程的情況下，將某個(gè)資源從進(jìn)程中強(qiáng)制取走給其他進(jìn)程使用，使用完后又送回。這種恢復(fù)方式一般比較困難而且有些簡單粗暴，并不可取。
如果系統(tǒng)設(shè)計(jì)者和機(jī)器操作員知道有可能發(fā)生死鎖，那么就可以定期檢查流程。進(jìn)程的檢測(cè)點(diǎn)意味著進(jìn)程的狀態(tài)可以被寫入到文件以便后面進(jìn)行恢復(fù)。檢測(cè)點(diǎn)不僅包含存儲(chǔ)映像(memory image)，還包含資源狀態(tài)(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測(cè)點(diǎn)，而是每出現(xiàn)一個(gè)檢測(cè)點(diǎn)都要把它寫入到文件中，這樣當(dāng)進(jìn)程執(zhí)行時(shí)，就會(huì)有一系列的檢查點(diǎn)文件被累積起來。
為了進(jìn)行恢復(fù)，要從上一個(gè)較早的檢查點(diǎn)上開始，這樣所需要資源的進(jìn)程會(huì)回滾到上一個(gè)時(shí)間點(diǎn)，在這個(gè)時(shí)間點(diǎn)上，死鎖進(jìn)程還沒有獲取所需要的資源，可以在此時(shí)對(duì)其進(jìn)行資源分配。
最簡單有效的解決方案是直接殺死一個(gè)死鎖進(jìn)程。但是殺死一個(gè)進(jìn)程可能照樣行不通，這時(shí)候就需要?dú)⑺绖e的資源進(jìn)行恢復(fù)。
另外一種方式是選擇一個(gè)環(huán)外的進(jìn)程作為犧牲品來釋放進(jìn)程資源。
我們上面討論的是如何檢測(cè)出現(xiàn)死鎖和如何恢復(fù)死鎖，下面我們探討幾種規(guī)避死鎖的方式
銀行家算法是 Dijkstra 在 1965 年提出的一種調(diào)度算法，它本身是一種死鎖的調(diào)度算法。它的模型是基于一個(gè)城鎮(zhèn)中的銀行家，銀行家向城鎮(zhèn)中的客戶承諾了一定數(shù)量的貸款額度。算法要做的就是判斷請(qǐng)求是否會(huì)進(jìn)入一種不安全的狀態(tài)。如果是，就拒絕請(qǐng)求，如果請(qǐng)求后系統(tǒng)是安全的，就接受該請(qǐng)求。
類似的，還有多個(gè)資源的銀行家算法，讀者可以自行了解。
死鎖本質(zhì)上是無法避免的，因?yàn)樗枰@得未知的資源和請(qǐng)求，但是死鎖是滿足四個(gè)條件后才出現(xiàn)的，它們分別是
我們分別對(duì)這四個(gè)條件進(jìn)行討論，按理說破壞其中的任意一個(gè)條件就能夠破壞死鎖
我們首先考慮的就是「破壞互斥使用條件」。如果資源不被一個(gè)進(jìn)程獨(dú)占，那么死鎖肯定不會(huì)產(chǎn)生。如果兩個(gè)打印機(jī)同時(shí)使用一個(gè)資源會(huì)造成混亂，打印機(jī)的解決方式是使用 假脫機(jī)打印機(jī)(spooling printer) ，這項(xiàng)技術(shù)可以允許多個(gè)進(jìn)程同時(shí)產(chǎn)生輸出，在這種模型中，實(shí)際請(qǐng)求打印機(jī)的唯一進(jìn)程是打印機(jī)守護(hù)進(jìn)程，也稱為后臺(tái)進(jìn)程。后臺(tái)進(jìn)程不會(huì)請(qǐng)求其他資源。我們可以消除打印機(jī)的死鎖。
后臺(tái)進(jìn)程通常被編寫為能夠輸出完整的文件后才能打印，假如兩個(gè)進(jìn)程都占用了假脫機(jī)空間的一半，而這兩個(gè)進(jìn)程都沒有完成全部的輸出，就會(huì)導(dǎo)致死鎖。
因此，盡量做到盡可能少的進(jìn)程可以請(qǐng)求資源。
第二種方式是如果我們能阻止持有資源的進(jìn)程請(qǐng)求其他資源，我們就能夠消除死鎖。一種實(shí)現(xiàn)方式是讓所有的進(jìn)程開始執(zhí)行前請(qǐng)求全部的資源。如果所需的資源可用，進(jìn)程會(huì)完成資源的分配并運(yùn)行到結(jié)束。如果有任何一個(gè)資源處于頻繁分配的情況，那么沒有分配到資源的進(jìn)程就會(huì)等待。
很多進(jìn)程「無法在執(zhí)行完成前就知道到底需要多少資源」，如果知道的話，就可以使用銀行家算法；還有一個(gè)問題是這樣「無法合理有效利用資源」。
還有一種方式是進(jìn)程在請(qǐng)求其他資源時(shí)，先釋放所占用的資源，然后再嘗試一次獲取全部的資源。
破壞不可搶占條件也是可以的。可以通過虛擬化的方式來避免這種情況。
現(xiàn)在就剩最后一個(gè)條件了，循環(huán)等待條件可以通過多種方法來破壞。一種方式是制定一個(gè)標(biāo)準(zhǔn)，一個(gè)進(jìn)程在任何時(shí)候只能使用一種資源。如果需要另外一種資源，必須釋放當(dāng)前資源。對(duì)于需要將大文件從磁帶復(fù)制到打印機(jī)的過程，此限制是不可接受的。
另一種方式是將所有的資源統(tǒng)一編號(hào)，如下圖所示
進(jìn)程可以在任何時(shí)間提出請(qǐng)求，但是所有的請(qǐng)求都必須按照資源的順序提出。如果按照此分配規(guī)則的話，那么資源分配之間不會(huì)出現(xiàn)環(huán)。
盡管通過這種方式來消除死鎖，但是編號(hào)的順序不可能讓每個(gè)進(jìn)程都會(huì)接受。
下面我們來探討一下其他問題，包括 「通信死鎖、活鎖是什么、饑餓問題和兩階段加鎖」
雖然很多情況下死鎖的避免和預(yù)防都能處理，但是效果并不好。隨著時(shí)間的推移，提出了很多優(yōu)秀的算法用來處理死鎖。例如在數(shù)據(jù)庫系統(tǒng)中，一個(gè)經(jīng)常發(fā)生的操作是請(qǐng)求鎖住一些記錄，然后更新所有鎖定的記錄。當(dāng)同時(shí)有多個(gè)進(jìn)程運(yùn)行時(shí)，就會(huì)有死鎖的風(fēng)險(xiǎn)。
一種解決方式是使用 兩階段提交(two-phase locking)。顧名思義分為兩個(gè)階段，一階段是進(jìn)程嘗試一次鎖定它需要的所有記錄。如果成功后，才會(huì)開始第二階段，第二階段是執(zhí)行更新并釋放鎖。第一階段并不做真正有意義的工作。
如果在第一階段某個(gè)進(jìn)程所需要的記錄已經(jīng)被加鎖，那么該進(jìn)程會(huì)釋放所有鎖定的記錄并重新開始第一階段。從某種意義上來說，這種方法類似于預(yù)先請(qǐng)求所有必需的資源或者是在進(jìn)行一些不可逆的操作之前請(qǐng)求所有的資源。
不過在一般的應(yīng)用場(chǎng)景中，兩階段加鎖的策略并不通用。如果一個(gè)進(jìn)程缺少資源就會(huì)半途中斷并重新開始的方式是不可接受的。
我們上面一直討論的是資源死鎖，資源死鎖是一種死鎖類型，但并不是唯一類型，還有通信死鎖，也就是兩個(gè)或多個(gè)進(jìn)程在發(fā)送消息時(shí)出現(xiàn)的死鎖。進(jìn)程 A 給進(jìn)程 B 發(fā)了一條消息，然后進(jìn)程 A 阻塞直到進(jìn)程 B 返回響應(yīng)。假設(shè)請(qǐng)求消息丟失了，那么進(jìn)程 A 在一直等著回復(fù)，進(jìn)程 B 也會(huì)阻塞等待請(qǐng)求消息到來，這時(shí)候就產(chǎn)生死鎖。
盡管會(huì)產(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ā)送者就會(huì)啟動(dòng)一個(gè)定時(shí)器，定時(shí)器會(huì)記錄消息的超時(shí)時(shí)間，如果超時(shí)時(shí)間到了但是消息還沒有返回，就會(huì)認(rèn)為消息已經(jīng)丟失并重新發(fā)送，通過這種方式，可以避免通信死鎖。
但是并非所有網(wǎng)絡(luò)通信發(fā)生的死鎖都是通信死鎖，也存在資源死鎖，下面就是一個(gè)典型的資源死鎖。
當(dāng)一個(gè)數(shù)據(jù)包從主機(jī)進(jìn)入路由器時(shí)，會(huì)被放入一個(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)程意識(shí)到它不能獲取所需要的下一個(gè)鎖時(shí)，就會(huì)嘗試禮貌的釋放已經(jīng)獲得的鎖，然后等待非常短的時(shí)間再次嘗試獲取。可以想像一下這個(gè)場(chǎng)景：當(dāng)兩個(gè)人在狹路相逢的時(shí)候，都想給對(duì)方讓路，相同的步調(diào)會(huì)導(dǎo)致雙方都無法前進(jìn)。
現(xiàn)在假想有一對(duì)并行的進(jìn)程用到了兩個(gè)資源。它們分別嘗試獲取另一個(gè)鎖失敗后，兩個(gè)進(jìn)程都會(huì)釋放自己持有的鎖，再次進(jìn)行嘗試，這個(gè)過程會(huì)一直進(jìn)行重復(fù)。很明顯，這個(gè)過程中沒有進(jìn)程阻塞，但是進(jìn)程仍然不會(huì)向下執(zhí)行，這種狀況我們稱之為 活鎖(livelock)。
與死鎖和活鎖的一個(gè)非常相似的問題是 饑餓(starvvation)。想象一下你什么時(shí)候會(huì)餓？一段時(shí)間不吃東西是不是會(huì)餓？對(duì)于進(jìn)程來講，最重要的就是資源，如果一段時(shí)間沒有獲得資源，那么進(jìn)程會(huì)產(chǎn)生饑餓，這些進(jìn)程會(huì)永遠(yuǎn)得不到服務(wù)。
我們假設(shè)打印機(jī)的分配方案是每次都會(huì)分配給最小文件的進(jìn)程，那么要打印大文件的進(jìn)程會(huì)永遠(yuǎn)得不到服務(wù)，導(dǎo)致進(jìn)程饑餓，進(jìn)程會(huì)無限制的推后，雖然它沒有阻塞。
倒是多此一舉，不僅沒有提高性能，反而磨損了固態(tài)硬盤。所以碎片整理只會(huì)縮短固態(tài)硬盤的壽命。
重磅！程序員大白交流群-學(xué)術(shù)微信交流群已成立
額外贈(zèng)送福利資源！邱錫鵬深度學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)，pytorch官方中文教程，利用Python進(jìn)行數(shù)據(jù)分析，機(jī)器學(xué)習(xí)學(xué)習(xí)筆記，pandas官方文檔中文版，effective java（中文版）等20項(xiàng)福利資源
獲取方式：進(jìn)入群后點(diǎn)開群公告即可領(lǐng)取下載鏈接
注意：請(qǐng)大家添加時(shí)修改備注為 [學(xué)校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對(duì)話系統(tǒng)。
號(hào)主，微商請(qǐng)自覺繞道。謝謝！
推薦閱讀
微軟太良心，這么強(qiáng)大的軟件竟然完全免費(fèi)！
關(guān)于程序員大白
程序員大白是一群哈工大，東北大學(xué)，西湖大學(xué)和上海交通大學(xué)的碩士博士運(yùn)營維護(hù)的號(hào)，大家樂于分享高質(zhì)量文章，喜歡總結(jié)知識(shí)，歡迎關(guān)注[程序員大白]，大家一起學(xué)習(xí)進(jìn)步！
聯(lián)系客服
