多操作系統(tǒng)支持兩部分的文件名，它們之間用 . 分隔開，比如文件名 prog.c。原點后面的文件稱為 文件擴展名(file extension) ，文件擴展名通常表示文件的一些信息。一些常用的文件擴展名以及含義如下圖所示

擴展名含義bak備份文件cc 源程序文件gif符合圖形交換格式的圖像文件hlp幫助文件htmlWWW 超文本標記語言文檔jpg符合 JPEG 編碼標準的靜態(tài)圖片mp3符合 MP3 音頻編碼格式的音樂文件mpg符合 MPEG 編碼標準的電影o目標文件（編譯器輸出格式，尚未鏈接）pdfpdf 格式的文件psPostScript 文件tex為 TEX 格式化程序準備的輸入文件txt文本文件zip壓縮文件

在 UNIX 系統(tǒng)中，文件擴展名只是一種約定，操作系統(tǒng)并不強制采用。

文件結構

文件的構造有多種方式。下圖列出了常用的三種構造方式

三種不同的文件。 a) 字節(jié)序列 。b) 記錄序列。c) 樹

上圖中的 a 是一種無結構的字節(jié)序列，操作系統(tǒng)不關心序列的內(nèi)容是什么，操作系統(tǒng)能看到的就是字節(jié)(bytes)。其文件內(nèi)容的任何含義只在用戶程序中進行解釋。UNIX 和 Windows 都采用這種辦法。

圖 b 表示在文件結構上的第一部改進。在這個模型中，文件是具有固定長度記錄的序列，每個記錄都有其內(nèi)部結構。 把文件作為記錄序列的核心思想是：讀操作返回一個記錄，而寫操作重寫或者追加一個記錄。第三種文件結構如上圖 c 所示。在這種組織結構中，文件由一顆記錄樹構成，記錄樹的長度不一定相同，每個記錄樹都在記錄中的固定位置包含一個key 字段。這棵樹按 key 進行排序，從而可以對特定的 key 進行快速查找。

文件類型

很多操作系統(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ù)寫入時，內(nèi)核會根據(jù)文件系統(tǒng)的規(guī)則執(zhí)行操作，是寫入可能被延遲，記錄日志或者接受其他操作。

文件訪問

早期的操作系統(tǒng)只有一種訪問方式：序列訪問(sequential access)。在這些系統(tǒng)中，進程可以按照順序讀取所有的字節(jié)或文件中的記錄，但是不能跳過并亂序執(zhí)行它們。順序訪問文件是可以返回到起點的，需要時可以多次讀取該文件。當存儲介質(zhì)是磁帶而不是磁盤時，順序訪問文件很方便。

在使用磁盤來存儲文件時，可以不按照順序讀取文件中的字節(jié)或者記錄，或者按照關鍵字而不是位置來訪問記錄。這種能夠以任意次序進行讀取的稱為隨機訪問文件(random access file)。許多應用程序都需要這種方式。

隨機訪問文件對許多應用程序來說都必不可少，例如，數(shù)據(jù)庫系統(tǒng)。如果乘客打電話預定某航班機票，訂票程序必須能夠直接訪問航班記錄，而不必先讀取其他航班的成千上萬條記錄。

有兩種方法可以指示從何處開始讀取文件。第一種方法是直接使用 read 從頭開始讀取。另一種是用一個特殊的 seek 操作設置當前位置，在 seek 操作后，從這個當前位置順序地開始讀文件。UNIX 和 Windows 使用的是后面一種方式。

文件屬性

文件包括文件名和數(shù)據(jù)。除此之外，所有的操作系統(tǒng)還會保存其他與文件相關的信息，如文件創(chuàng)建的日期和時間、文件大小。我們可以稱這些為文件的屬性(attributes)。有些人也喜歡把它們稱作 元數(shù)據(jù)(metadata)。文件的屬性在不同的系統(tǒng)中差別很大。文件的屬性只有兩種狀態(tài)：設置(set) 和 清除(clear)。

文件操作

使用文件的目的是用來存儲信息并方便以后的檢索。對于存儲和檢索，不同的系統(tǒng)提供了不同的操作。以下是與文件有關的最常用的一些系統(tǒng)調(diào)用：

1. Create，創(chuàng)建不包含任何數(shù)據(jù)的文件。調(diào)用的目的是表示文件即將建立，并對文件設置一些屬性。
2. Delete，當文件不再需要，必須刪除它以釋放內(nèi)存空間。為此總會有一個系統(tǒng)調(diào)用來刪除文件。
3. Open，在使用文件之前，必須先打開文件。這個調(diào)用的目的是允許系統(tǒng)將屬性和磁盤地址列表保存到主存中，用來以后的快速訪問。
4. Close，當所有進程完成時，屬性和磁盤地址不再需要，因此應關閉文件以釋放表空間。很多系統(tǒng)限制進程打開文件的個數(shù)，以此達到鼓勵用戶關閉不再使用的文件。磁盤以塊為單位寫入，關閉文件時會強制寫入最后一塊，即使這個塊空間內(nèi)部還不滿。
5. Read，數(shù)據(jù)從文件中讀取。通常情況下，讀取的數(shù)據(jù)來自文件的當前位置。調(diào)用者必須指定需要讀取多少數(shù)據(jù)，并且提供存放這些數(shù)據(jù)的緩沖區(qū)。
6. Write，向文件寫數(shù)據(jù)，寫操作一般也是從文件的當前位置開始進行。如果當前位置是文件的末尾，則會直接追加進行寫入。如果當前位置在文件中，則現(xiàn)有數(shù)據(jù)被覆蓋，并且永遠消失。
7. append，使用 append 只能向文件末尾添加數(shù)據(jù)。
8. seek，對于隨機訪問的文件，要指定從何處開始獲取數(shù)據(jù)。通常的方法是用 seek 系統(tǒng)調(diào)用把當前位置指針指向文件中的特定位置。seek 調(diào)用結束后，就可以從指定位置開始讀寫數(shù)據(jù)了。
9. get attributes，進程運行時通常需要讀取文件屬性。
10. set attributes，用戶可以自己設置一些文件屬性，甚至是在文件創(chuàng)建之后，實現(xiàn)該功能的是 set attributes 系統(tǒng)調(diào)用。
11. rename，用戶可以自己更改已有文件的名字，rename 系統(tǒng)調(diào)用用于這一目的。

目錄

文件系統(tǒng)通常提供目錄(directories) 或者 文件夾(folders) 用于記錄文件的位置，在很多系統(tǒng)中目錄本身也是文件，下面我們會討論關于文件，他們的組織形式、屬性和可以對文件進行的操作。

一級目錄系統(tǒng)

目錄系統(tǒng)最簡單的形式是有一個能夠包含所有文件的目錄。這種目錄被稱為根目錄(root directory)，由于根目錄的唯一性，所以其名稱并不重要。在最早期的個人計算機中，這種系統(tǒng)很常見，部分原因是因為只有一個用戶。下面是一個單層目錄系統(tǒng)的例子

含有四個文件的單層目錄系統(tǒng)

該目錄中有四個文件。這種設計的優(yōu)點在于簡單，并且能夠快速定位文件，畢竟只有一個地方可以檢索。這種目錄組織形式現(xiàn)在一般用于簡單的嵌入式設備（如數(shù)碼相機和某些便攜式音樂播放器）上使用。

層次目錄系統(tǒng)

對于簡單的應用而言，一般都用單層目錄方式，但是這種組織形式并不適合于現(xiàn)代計算機，因為現(xiàn)代計算機含有成千上萬個文件和文件夾。如果都放在根目錄下，查找起來會非常困難。為了解決這一問題，出現(xiàn)了層次目錄系統(tǒng)(Hierarchical Directory Systems)，也稱為目錄樹。通過這種方式，可以用很多目錄把文件進行分組。進而，如果多個用戶共享同一個文件服務器，比如公司的網(wǎng)絡系統(tǒng)，每個用戶可以為自己的目錄樹擁有自己的私人根目錄。這種方式的組織結構如下

根目錄含有目錄 A、B 和 C ，分別屬于不同的用戶，其中兩個用戶個字創(chuàng)建了子目錄。用戶可以創(chuàng)建任意數(shù)量的子目錄，現(xiàn)代文件系統(tǒng)都是按照這種方式組織的。

路徑名

當目錄樹組織文件系統(tǒng)時，需要有某種方法指明文件名。常用的方法有兩種，第一種方式是每個文件都會用一個絕對路徑名(absolute path name)，它由根目錄到文件的路徑組成。

另外一種指定文件名的方法是 相對路徑名(relative path name)。它常常和 工作目錄(working directory) （也稱作 當前目錄(current directory)）一起使用。用戶可以指定一個目錄作為當前工作目錄。例如，如果當前目錄是 /usr/ast，那么絕對路徑 /usr/ast/mailbox可以直接使用 mailbox 來引用。

目錄操作

不同文件中管理目錄的系統(tǒng)調(diào)用的差別比管理文件的系統(tǒng)調(diào)用差別大。為了了解這些系統(tǒng)調(diào)用有哪些以及它們怎樣工作，下面給出一個例子（取自 UNIX）。

1. Create，創(chuàng)建目錄，除了目錄項 . 和 .. 外，目錄內(nèi)容為空。
2. Delete，刪除目錄，只有空目錄可以刪除。只包含 . 和 .. 的目錄被認為是空目錄，這兩個目錄項通常不能刪除
3. opendir，目錄內(nèi)容可被讀取。例如，未列出目錄中的全部文件，程序必須先打開該目錄，然后讀其中全部文件的文件名。與打開和讀文件相同，在讀目錄前，必須先打開文件。
4. closedir，讀目錄結束后，應該關閉目錄用于釋放內(nèi)部表空間。
5. readdir，系統(tǒng)調(diào)用 readdir 返回打開目錄的下一個目錄項。以前也采用 read 系統(tǒng)調(diào)用來讀取目錄，但是這種方法有一個缺點：程序員必須了解和處理目錄的內(nèi)部結構。相反，不論采用哪一種目錄結構，readdir 總是以標準格式返回一個目錄項。
6. rename，在很多方面目錄和文件都相似。文件可以更換名稱，目錄也可以。
7. link，鏈接技術允許在多個目錄中出現(xiàn)同一個文件。這個系統(tǒng)調(diào)用指定一個存在的文件和一個路徑名，并建立從該文件到路徑所指名字的鏈接。這樣，可以在多個目錄中出現(xiàn)同一個文件。有時也被稱為硬鏈接(hard link)。
8. unlink，刪除目錄項。如果被解除鏈接的文件只出現(xiàn)在一個目錄中，則將它從文件中刪除。如果它出現(xiàn)在多個目錄中，則只刪除指定路徑名的鏈接，依然保留其他路徑名的鏈接。在 UNIX 中，用于刪除文件的系統(tǒng)調(diào)用就是 unlink。

文件系統(tǒng)的實現(xiàn)

文件系統(tǒng)布局

文件系統(tǒng)存儲在磁盤中。大部分的磁盤能夠劃分出一到多個分區(qū)，叫做磁盤分區(qū)(disk partitioning) 或者是磁盤分片(disk slicing)。每個分區(qū)都有獨立的文件系統(tǒng)，每塊分區(qū)的文件系統(tǒng)可以不同。磁盤的 0 號分區(qū)稱為 主引導記錄(Master Boot Record, MBR)，用來引導(boot) 計算機。在 MBR 的結尾是分區(qū)表(partition table)。每個分區(qū)表給出每個分區(qū)由開始到結束的地址。

當計算機開始引 boot 時，BIOS 讀入并執(zhí)行 MBR。

引導塊

MBR 做的第一件事就是確定活動分區(qū)，讀入它的第一個塊，稱為引導塊(boot block) 并執(zhí)行。引導塊中的程序?qū)⒓虞d分區(qū)中的操作系統(tǒng)。為了一致性，每個分區(qū)都會從引導塊開始，即使引導塊不包含操作系統(tǒng)。引導塊占據(jù)文件系統(tǒng)的前 4096 個字節(jié)，從磁盤上的字節(jié)偏移量 0 開始。引導塊可用于啟動操作系統(tǒng)。

除了從引導塊開始之外，磁盤分區(qū)的布局是隨著文件系統(tǒng)的不同而變化的。通常文件系統(tǒng)會包含一些屬性，如下

文件系統(tǒng)布局

超級塊

緊跟在引導塊后面的是 超級塊(Superblock)，超級塊 的大小為 4096 字節(jié)，從磁盤上的字節(jié)偏移 4096 開始。超級塊包含文件系統(tǒng)的所有關鍵參數(shù)

• 文件系統(tǒng)的大小
• 文件系統(tǒng)中的數(shù)據(jù)塊數(shù)
• 指示文件系統(tǒng)狀態(tài)的標志
• 分配組大小

在計算機啟動或者文件系統(tǒng)首次使用時，超級塊會被讀入內(nèi)存。

空閑空間塊

接著是文件系統(tǒng)中空閑塊的信息，例如，可以用位圖或者指針列表的形式給出。

BitMap 位圖或者 Bit vector 位向量

位圖或位向量是一系列位或位的集合，其中每個位對應一個磁盤塊，該位可以采用兩個值：0和1，0表示已分配該塊，而1表示一個空閑塊。下圖中的磁盤上給定的磁盤塊實例（分配了綠色塊）可以用16位的位圖表示為：0000111000000110。

使用鏈表進行管理

在這種方法中，空閑磁盤塊鏈接在一起，即一個空閑塊包含指向下一個空閑塊的指針。第一個磁盤塊的塊號存儲在磁盤上的單獨位置，也緩存在內(nèi)存中。

碎片

這里不得不提一個叫做碎片(fragment)的概念，也稱為片段。一般零散的單個數(shù)據(jù)通常稱為片段。 磁盤塊可以進一步分為固定大小的分配單元，片段只是在驅(qū)動器上彼此不相鄰的文件片段。

inode

然后在后面是一個 inode(index node)，也稱作索引節(jié)點。它是一個數(shù)組的結構，每個文件有一個 inode，inode 非常重要，它說明了文件的方方面面。每個索引節(jié)點都存儲對象數(shù)據(jù)的屬性和磁盤塊位置

有一種簡單的方法可以找到它們 ls -lai 命令。讓我們看一下根文件系統(tǒng)：

inode 節(jié)點主要包括了以下信息

• 模式/權限（保護）
• 所有者 ID
• 組 ID
• 文件大小
• 文件的硬鏈接數(shù)
• 上次訪問時間
• 最后修改時間
• inode 上次修改時間

文件分為兩部分，索引節(jié)點和塊。一旦創(chuàng)建后，每種類型的塊數(shù)是固定的。你不能增加分區(qū)上 inode 的數(shù)量，也不能增加磁盤塊的數(shù)量。

緊跟在 inode 后面的是根目錄，它存放的是文件系統(tǒng)目錄樹的根部。最后，磁盤的其他部分存放了其他所有的目錄和文件。

文件的實現(xiàn)

最重要的問題是記錄各個文件分別用到了哪些磁盤塊。不同的系統(tǒng)采用了不同的方法。下面我們會探討一下這些方式。分配背后的主要思想是有效利用文件空間和快速訪問文件 ，主要有三種分配方案

• 連續(xù)分配
• 鏈表分配
• 索引分配

連續(xù)分配

最簡單的分配方案是把每個文件作為一連串連續(xù)數(shù)據(jù)塊存儲在磁盤上。因此，在具有 1KB 塊的磁盤上，將為 50 KB 文件分配 50 個連續(xù)塊。

使用連續(xù)空間存儲文件

上面展示了 40 個連續(xù)的內(nèi)存塊。從最左側(cè)的 0 塊開始。初始狀態(tài)下，還沒有裝載文件，因此磁盤是空的。接著，從磁盤開始處（塊 0 ）處開始寫入占用 4 塊長度的內(nèi)存 A 。然后是一個占用 6 塊長度的內(nèi)存 B，會直接在 A 的末尾開始寫。

注意每個文件都會在新的文件塊開始寫，所以如果文件 A 只占用了 3 又 1/2 個塊，那么最后一個塊的部分內(nèi)存會被浪費。在上面這幅圖中，總共展示了 7 個文件，每個文件都會從上個文件的末尾塊開始寫新的文件塊。

連續(xù)的磁盤空間分配有兩個優(yōu)點。

• 第一，連續(xù)文件存儲實現(xiàn)起來比較簡單，只需要記住兩個數(shù)字就可以：一個是第一個塊的文件地址和文件的塊數(shù)量。給定第一個塊的編號，可以通過簡單的加法找到任何其他塊的編號。

• 第二點是讀取性能比較強，可以通過一次操作從文件中讀取整個文件。只需要一次尋找第一個塊。后面就不再需要尋道時間和旋轉(zhuǎn)延遲，所以數(shù)據(jù)會以全帶寬進入磁盤。

因此，連續(xù)的空間分配具有實現(xiàn)簡單、高性能的特點。

不幸的是，連續(xù)空間分配也有很明顯的不足。隨著時間的推移，磁盤會變得很零碎。下圖解釋了這種現(xiàn)象

這里有兩個文件 D 和 F 被刪除了。當刪除一個文件時，此文件所占用的塊也隨之釋放，就會在磁盤空間中留下一些空閑塊。磁盤并不會在這個位置擠壓掉空閑塊，因為這會復制空閑塊之后的所有文件，可能會有上百萬的塊，這個量級就太大了。

鏈表分配

第二種存儲文件的方式是為每個文件構造磁盤塊鏈表，每個文件都是磁盤塊的鏈接列表，就像下面所示

以磁盤塊的鏈表形式存儲文件

每個塊的第一個字作為指向下一塊的指針，塊的其他部分存放數(shù)據(jù)。如果上面這張圖你看的不是很清楚的話，可以看看整個的鏈表分配方案

與連續(xù)分配方案不同，這一方法可以充分利用每個磁盤塊。除了最后一個磁盤塊外，不會因為磁盤碎片而浪費存儲空間。同樣，在目錄項中，只要存儲了第一個文件塊，那么其他文件塊也能夠被找到。

另一方面，在鏈表的分配方案中，盡管順序讀取非常方便，但是隨機訪問卻很困難（這也是數(shù)組和鏈表數(shù)據(jù)結構的一大區(qū)別）。

還有一個問題是，由于指針會占用一些字節(jié)，每個磁盤塊實際存儲數(shù)據(jù)的字節(jié)數(shù)并不再是 2 的整數(shù)次冪。雖然這個問題并不會很嚴重，但是這種方式降低了程序運行效率。許多程序都是以長度為 2 的整數(shù)次冪來讀寫磁盤，由于每個塊的前幾個字節(jié)被指針所使用，所以要讀出一個完成的塊大小信息，就需要當前塊的信息和下一塊的信息拼湊而成，因此就引發(fā)了查找和拼接的開銷。

使用內(nèi)存表進行鏈表分配

由于連續(xù)分配和鏈表分配都有其不可忽視的缺點。所以提出了使用內(nèi)存中的表來解決分配問題。取出每個磁盤塊的指針字，把它們放在內(nèi)存的一個表中，就可以解決上述鏈表的兩個不足之處。下面是一個例子

上圖表示了鏈表形成的磁盤塊的內(nèi)容。這兩個圖中都有兩個文件，文件 A 依次使用了磁盤塊地址 4、7、 2、 10、 12，文件 B 使用了6、3、11 和 14。也就是說，文件 A 從地址 4 處開始，順著鏈表走就能找到文件 A 的全部磁盤塊。同樣，從第 6 塊開始，順著鏈走到最后，也能夠找到文件 B 的全部磁盤塊。你會發(fā)現(xiàn)，這兩個鏈表都以不屬于有效磁盤編號的特殊標記（-1）結束。內(nèi)存中的這種表格稱為 文件分配表(File Application Table,FAT)。

目錄的實現(xiàn)

文件只有打開后才能夠被讀取。在文件打開后，操作系統(tǒng)會使用用戶提供的路徑名來定位磁盤中的目錄。目錄項提供了查找文件磁盤塊所需要的信息。根據(jù)系統(tǒng)的不同，提供的信息也不同，可能提供的信息是整個文件的磁盤地址，或者是第一個塊的數(shù)量（兩個鏈表方案）或 inode的數(shù)量。不過不管用那種情況，目錄系統(tǒng)的主要功能就是 將文件的 ASCII 碼的名稱映射到定位數(shù)據(jù)所需的信息上。

共享文件

當多個用戶在同一個項目中工作時，他們通常需要共享文件。如果這個共享文件同時出現(xiàn)在多個用戶目錄下，那么他們協(xié)同工作起來就很方便。下面的這張圖我們在上面提到過，但是有一個更改的地方，就是 C 的一個文件也出現(xiàn)在了 B 的目錄下。

如果按照如上圖的這種組織方式而言，那么 B 的目錄與該共享文件的聯(lián)系稱為 鏈接(link)。那么文件系統(tǒng)現(xiàn)在就是一個 有向無環(huán)圖(Directed Acyclic Graph, 簡稱 DAG)，而不是一棵樹了。

日志結構文件系統(tǒng)

技術的改變會給當前的文件系統(tǒng)帶來壓力。這種情況下，CPU 會變得越來越快，磁盤會變得越來越大并且越來越便宜（但不會越來越快）。內(nèi)存容量也是以指數(shù)級增長。但是磁盤的尋道時間（除了固態(tài)盤，因為固態(tài)盤沒有尋道時間）并沒有獲得提高。

為此，Berkeley 設計了一種全新的文件系統(tǒng)，試圖緩解這個問題，這個文件系統(tǒng)就是 日志結構文件系統(tǒng)(Log-structured File System, LFS)。旨在解決以下問題。

• 不斷增長的系統(tǒng)內(nèi)存

• 順序 I/O 性能勝過隨機 I/O 性能

• 現(xiàn)有低效率的文件系統(tǒng)

• 文件系統(tǒng)不支持 RAID（虛擬化）

另一方面，當時的文件系統(tǒng)不論是 UNIX 還是 FFS，都有大量的隨機讀寫（在 FFS 中創(chuàng)建一個新文件至少需要5次隨機寫），因此成為整個系統(tǒng)的性能瓶頸。同時因為 Page cache的存在，作者認為隨機讀不是主要問題：隨著越來越大的內(nèi)存，大部分的讀操作都能被 cache，因此 LFS 主要要解決的是減少對硬盤的隨機寫操作。

在這種設計中，inode 甚至具有與 UNIX 中相同的結構，但是現(xiàn)在它們分散在整個日志中，而不是位于磁盤上的固定位置。所以，inode 很定位。為了能夠找到 inode ，維護了一個由 inode 索引的 inode map(inode 映射)。表項 i 指向磁盤中的第 i 個 inode 。這個映射保存在磁盤中，但是也保存在緩存中，因此，使用最頻繁的部分大部分時間都在內(nèi)存中。

到目前為止，所有寫入最初都緩存在內(nèi)存中，并且追加在日志末尾，所有緩存的寫入都定期在單個段中寫入磁盤。所以，現(xiàn)在打開文件也就意味著用映射定位文件的索引節(jié)點。一旦 inode 被定位后，磁盤塊的地址就能夠被找到。所有這些塊本身都將位于日志中某處的分段中。

真實情況下的磁盤容量是有限的，所以最終日志會占滿整個磁盤空間，這種情況下就會出現(xiàn)沒有新的磁盤塊被寫入到日志中。幸運的是，許多現(xiàn)有段可能具有不再需要的塊。例如，如果一個文件被覆蓋了，那么它的 inode 將被指向新的塊，但是舊的磁盤塊仍在先前寫入的段中占據(jù)著空間。

為了處理這個問題，LFS 有一個清理(clean)線程，它會循環(huán)掃描日志并對日志進行壓縮。首先，通過查看日志中第一部分的信息來查看其中存在哪些索引節(jié)點和文件。它會檢查當前 inode 的映射來查看 inode 否在在當前塊中，是否仍在被使用。如果不是，該信息將被丟棄。如果仍然在使用，那么 inode 和塊就會進入內(nèi)存等待寫回到下一個段中。然后原來的段被標記為空閑，以便日志可以用來存放新的數(shù)據(jù)。用這種方法，清理線程遍歷日志，從后面移走舊的段，然后將有效的數(shù)據(jù)放入內(nèi)存等待寫到下一個段中。由此一來整個磁盤會形成一個大的環(huán)形緩沖區(qū)，寫線程將新的段寫在前面，而清理線程則清理后面的段。

日志文件系統(tǒng)

雖然日志結構系統(tǒng)的設計很優(yōu)雅，但是由于它們和現(xiàn)有的文件系統(tǒng)不相匹配，因此還沒有廣泛使用。不過，從日志文件結構系統(tǒng)衍生出來一種新的日志系統(tǒng)，叫做日志文件系統(tǒng)，它會記錄系統(tǒng)下一步將要做什么的日志。微軟的 NTFS 文件系統(tǒng)、Linux 的 ext3 就使用了此日志。 OS X 將日志系統(tǒng)作為可供選項。為了看清它是如何工作的，我們下面討論一個例子，比如 移除文件 ，這個操作在 UNIX 中需要三個步驟完成：

• 在目錄中刪除文件
• 釋放 inode 到空閑 inode 池
• 將所有磁盤塊歸還給空閑磁盤池。

虛擬文件系統(tǒng)

UNIX 操作系統(tǒng)使用一種 虛擬文件系統(tǒng)(Virtual File System, VFS) 來嘗試將多種文件系統(tǒng)構成一個有序的結構。關鍵的思想是抽象出所有文件系統(tǒng)都共有的部分，并將這部分代碼放在一層，這一層再調(diào)用具體文件系統(tǒng)來管理數(shù)據(jù)。下面是一個 VFS 的系統(tǒng)結構

還是那句經(jīng)典的話，在計算機世界中，任何解決不了的問題都可以加個代理來解決。所有和文件相關的系統(tǒng)調(diào)用在最初的處理上都指向虛擬文件系統(tǒng)。這些來自用戶進程的調(diào)用，都是標準的 POSIX 系統(tǒng)調(diào)用，比如 open、read、write 和 seek 等。VFS 對用戶進程有一個 上層 接口，這個接口就是著名的 POSIX 接口。

文件系統(tǒng)的管理和優(yōu)化

能夠使文件系統(tǒng)工作是一回事，能夠使文件系統(tǒng)高效、穩(wěn)定的工作是另一回事，下面我們就來探討一下文件系統(tǒng)的管理和優(yōu)化。

磁盤空間管理

文件通常存在磁盤中，所以如何管理磁盤空間是一個操作系統(tǒng)的設計者需要考慮的問題。在文件上進行存有兩種策略：分配 n 個字節(jié)的連續(xù)磁盤空間；或者把文件拆分成多個并不一定連續(xù)的塊。在存儲管理系統(tǒng)中，主要有分段管理和 分頁管理 兩種方式。

正如我們所看到的，按連續(xù)字節(jié)序列存儲文件有一個明顯的問題，當文件擴大時，有可能需要在磁盤上移動文件。內(nèi)存中分段也有同樣的問題。不同的是，相對于把文件從磁盤的一個位置移動到另一個位置，內(nèi)存中段的移動操作要快很多。因此，幾乎所有的文件系統(tǒng)都把文件分割成固定大小的塊來存儲。

塊大小

一旦把文件分為固定大小的塊來存儲，就會出現(xiàn)問題，塊的大小是多少？按照磁盤組織方式，扇區(qū)、磁道和柱面顯然都可以作為分配單位。在分頁系統(tǒng)中，分頁大小也是主要因素。

擁有大的塊尺寸意味著每個文件，甚至 1 字節(jié)文件，都要占用一個柱面空間，也就是說小文件浪費了大量的磁盤空間。另一方面，小塊意味著大部分文件將會跨越多個塊，因此需要多次搜索和旋轉(zhuǎn)延遲才能讀取它們，從而降低了性能。因此，如果分配的塊太大會浪費空間；分配的塊太小會浪費時間。

記錄空閑塊

一旦指定了塊大小，下一個問題就是怎樣跟蹤空閑塊。有兩種方法被廣泛采用，如下圖所示

第一種方法是采用磁盤塊鏈表，鏈表的每個塊中包含極可能多的空閑磁盤塊號。對于 1 KB 的塊和 32 位的磁盤塊號，空閑表中每個塊包含有 255 個空閑的塊號。考慮 1 TB 的硬盤，擁有大概十億個磁盤塊。為了存儲全部地址塊號，如果每塊可以保存 255 個塊號，則需要將近 400 萬個塊。通常，空閑塊用于保存空閑列表，因此存儲基本上是空閑的。

另一種空閑空間管理的技術是位圖(bitmap)，n 個塊的磁盤需要 n 位位圖。在位圖中，空閑塊用 1 表示，已分配的塊用 0 表示。對于 1 TB 硬盤的例子，需要 10 億位表示，即需要大約 130 000 個 1 KB 塊存儲。很明顯，和 32 位鏈表模型相比，位圖需要的空間更少，因為每個塊使用 1 位。只有當磁盤快滿的時候，鏈表需要的塊才會比位圖少。

磁盤配額

為了防止一些用戶占用太多的磁盤空間，多用戶操作通常提供一種磁盤配額(enforcing disk quotas)的機制。系統(tǒng)管理員為每個用戶分配最大的文件和塊分配，并且操作系統(tǒng)確保用戶不會超過其配額。我們下面會談到這一機制。

在用戶打開一個文件時，操作系統(tǒng)會找到文件屬性和磁盤地址，并把它們送入內(nèi)存中的打開文件表。其中一個屬性告訴文件所有者是誰。任何有關文件的增加都會記到所有者的配額中。

配額表中記錄了每個用戶的配額

第二張表包含了每個用戶當前打開文件的配額記錄，即使是其他人打開該文件也一樣。如上圖所示，該表的內(nèi)容是從被打開文件的所有者的磁盤配額文件中提取出來的。當所有文件關閉時，該記錄被寫回配額文件。

當在打開文件表中建立一新表項時，會產(chǎn)生一個指向所有者配額記錄的指針。每次向文件中添加一個塊時，文件所有者所用數(shù)據(jù)塊的總數(shù)也隨之增加，并會同時增加硬限制和軟限制的檢查。可以超出軟限制，但硬限制不可以超出。當已達到硬限制時，再往文件中添加內(nèi)容將引發(fā)錯誤。同樣，對文件數(shù)目也存在類似的檢查。

文件系統(tǒng)備份

做文件備份很耗費時間而且也很浪費空間，這會引起下面幾個問題。首先，是要備份整個文件還是僅備份一部分呢？一般來說，只是備份特定目錄及其下的全部文件，而不是備份整個文件系統(tǒng)。

其次，對上次未修改過的文件再進行備份是一種浪費，因而產(chǎn)生了一種增量轉(zhuǎn)儲(incremental dumps) 的思想。最簡單的增量轉(zhuǎn)儲的形式就是周期性的做全面的備份，而每天只對增量轉(zhuǎn)儲完成后發(fā)生變化的文件做單個備份。

稍微好一點的方式是只備份最近一次轉(zhuǎn)儲以來更改過的文件。當然，這種做法極大的縮減了轉(zhuǎn)儲時間，但恢復起來卻更復雜，因為最近的全面轉(zhuǎn)儲先要全部恢復，隨后按逆序進行增量轉(zhuǎn)儲。為了方便恢復，人們往往使用更復雜的轉(zhuǎn)儲模式。

第三，既然待轉(zhuǎn)儲的往往是海量數(shù)據(jù)，那么在將其寫入磁帶之前對文件進行壓縮就很有必要。但是，如果在備份過程中出現(xiàn)了文件損壞的情況，就會導致破壞壓縮算法，從而使整個磁帶無法讀取。所以在備份前是否進行文件壓縮需慎重考慮。

第四，對正在使用的文件系統(tǒng)做備份是很難的。如果在轉(zhuǎn)儲過程中要添加，刪除和修改文件和目錄，則轉(zhuǎn)儲結果可能不一致。因此，因為轉(zhuǎn)儲過程中需要花費數(shù)個小時的時間，所以有必要在晚上將系統(tǒng)脫機進行備份，然而這種方式的接受程度并不高。所以，人們修改了轉(zhuǎn)儲算法，記下文件系統(tǒng)的瞬時快照，即復制關鍵的數(shù)據(jù)結構，然后需要把將來對文件和目錄所做的修改復制到塊中，而不是到處更新他們。

磁盤轉(zhuǎn)儲到備份磁盤上有兩種方案：物理轉(zhuǎn)儲和邏輯轉(zhuǎn)儲。物理轉(zhuǎn)儲(physical dump) 是從磁盤的 0 塊開始，依次將所有磁盤塊按照順序?qū)懭氲捷敵龃疟P，并在復制最后一個磁盤時停止。這種程序的萬無一失性是其他程序所不具備的。

第二個需要考慮的是壞塊的轉(zhuǎn)儲。制造大型磁盤而沒有瑕疵是不可能的，所以也會存在一些壞塊(bad blocks)。有時進行低級格式化后，壞塊會被檢測出來并進行標記，這種情況的解決辦法是用磁盤末尾的一些空閑塊所替換。

然而，一些塊在格式化后會變壞，在這種情況下操作系統(tǒng)可以檢測到它們。通常情況下，它可以通過創(chuàng)建一個由所有壞塊組成的文件來解決問題，確保它們不會出現(xiàn)在空閑池中并且永遠不會被分配。那么此文件是完全不可讀的。如果磁盤控制器將所有的壞塊重新映射，物理轉(zhuǎn)儲還是能夠正常工作的。

Windows 系統(tǒng)有分頁文件(paging files) 和 休眠文件(hibernation files) 。它們在文件還原時不發(fā)揮作用，同時也不應該在第一時間進行備份。

文件系統(tǒng)的一致性

影響可靠性的一個因素是文件系統(tǒng)的一致性。許多文件系統(tǒng)讀取磁盤塊、修改磁盤塊、再把它們寫回磁盤。如果系統(tǒng)在所有塊寫入之前崩潰，文件系統(tǒng)就會處于一種不一致(inconsistent)的狀態(tài)。如果某些尚未寫回的塊是索引節(jié)點塊，目錄塊或包含空閑列表的塊，則此問題是很嚴重的。

為了處理文件系統(tǒng)一致性問題，大部分計算機都會有應用程序來檢查文件系統(tǒng)的一致性。例如，UNIX 有 fsck；Windows 有 sfc，每當引導系統(tǒng)時（尤其是在崩潰后），都可以運行該程序。

可以進行兩種一致性檢查：塊的一致性檢查和文件的一致性檢查。為了檢查塊的一致性，應用程序會建立兩張表，每個包含一個計數(shù)器的塊，最初設置為 0 。第一個表中的計數(shù)器跟蹤該塊在文件中出現(xiàn)的次數(shù)，第二張表中的計數(shù)器記錄每個塊在空閑列表、空閑位圖中出現(xiàn)的頻率。

文件系統(tǒng)性能

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

從內(nèi)存讀一個 32 位字大概是 10ns，從硬盤上讀的速率大概是 100MB/S，對每個 32 位字來說，效率會慢了四倍，另外，還要加上 5 - 10 ms 的尋道時間等其他損耗，如果只訪問一個字，內(nèi)存要比磁盤快百萬數(shù)量級。所以磁盤優(yōu)化是很有必要的，下面我們會討論幾種優(yōu)化方式

高速緩存

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

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

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

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

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

塊提前讀

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

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

減少磁盤臂運動

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

磁盤碎片整理

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

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

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

下面我們來探討一下 I/O 流程問題。

I/O 設備

什么是 I/O 設備？I/O 設備又叫做輸入/輸出設備，它是人類用來和計算機進行通信的外部硬件。輸入/輸出設備能夠向計算機發(fā)送數(shù)據(jù)（輸出）并從計算機接收數(shù)據(jù)（輸入）。

I/O 設備(I/O devices)可以分成兩種：塊設備(block devices) 和 字符設備(character devices)。

塊設備

塊設備是一個能存儲固定大小塊信息的設備，它支持以固定大小的塊，扇區(qū)或群集讀取和（可選）寫入數(shù)據(jù)。每個塊都有自己的物理地址。通常塊的大小在 512 - 65536 之間。所有傳輸?shù)男畔⒍紩赃B續(xù)的塊為單位。塊設備的基本特征是每個塊都較為對立，能夠獨立的進行讀寫。常見的塊設備有 硬盤、藍光光盤、USB 盤

與字符設備相比，塊設備通常需要較少的引腳。

塊設備的缺點

基于給定固態(tài)存儲器的塊設備比基于相同類型的存儲器的字節(jié)尋址要慢一些，因為必須在塊的開頭開始讀取或?qū)懭搿Ｋ裕x取該塊的任何部分，必須尋找到該塊的開始，讀取整個塊，如果不使用該塊，則將其丟棄。要寫入塊的一部分，必須尋找到塊的開始，將整個塊讀入內(nèi)存，修改數(shù)據(jù)，再次尋找到塊的開頭處，然后將整個塊寫回設備。

字符設備

另一類 I/O 設備是字符設備。字符設備以字符為單位發(fā)送或接收一個字符流，而不考慮任何塊結構。字符設備是不可尋址的，也沒有任何尋道操作。常見的字符設備有 打印機、網(wǎng)絡設備、鼠標、以及大多數(shù)與磁盤不同的設備。

設備控制器

設備控制器是處理 CPU 傳入和傳出信號的系統(tǒng)。設備通過插頭和插座連接到計算機，并且插座連接到設備控制器。設備控制器從連接的設備處接收數(shù)據(jù)，并將其存儲在控制器內(nèi)部的一些特殊目的寄存器(special purpose registers) 也就是本地緩沖區(qū)中。

每個設備控制器都會有一個應用程序與之對應，設備控制器通過應用程序的接口通過中斷與操作系統(tǒng)進行通信。設備控制器是硬件，而設備驅(qū)動程序是軟件。

內(nèi)存映射 I/O

每個控制器都會有幾個寄存器用來和 CPU 進行通信。通過寫入這些寄存器，操作系統(tǒng)可以命令設備發(fā)送數(shù)據(jù)，接收數(shù)據(jù)、開啟或者關閉設備等。通過從這些寄存器中讀取信息，操作系統(tǒng)能夠知道設備的狀態(tài)，是否準備接受一個新命令等。

為了控制寄存器，許多設備都會有數(shù)據(jù)緩沖區(qū)(data buffer)，來供系統(tǒng)進行讀寫。

那么問題來了，CPU 如何與設備寄存器和設備數(shù)據(jù)緩沖區(qū)進行通信呢？存在兩個可選的方式。第一種方法是，每個控制寄存器都被分配一個 I/O 端口(I/O port)號，這是一個 8 位或 16 位的整數(shù)。所有 I/O 端口的集合形成了受保護的 I/O 端口空間，以便普通用戶程序無法訪問它（只有操作系統(tǒng)可以訪問）。使用特殊的 I/O 指令像是

IN REG,PORT

CPU 可以讀取控制寄存器 PORT 的內(nèi)容并將結果放在 CPU 寄存器 REG 中。類似的，使用

OUT PORT,REG

CPU 可以將 REG 的內(nèi)容寫到控制寄存器中。大多數(shù)早期計算機，包括幾乎所有大型主機，如 IBM 360 及其所有后續(xù)機型，都是以這種方式工作的。

第二個方法是 PDP-11 引入的，它將所有控制寄存器映射到內(nèi)存空間中。

直接內(nèi)存訪問

無論一個 CPU 是否具有內(nèi)存映射 I/O，它都需要尋址設備控制器以便與它們交換數(shù)據(jù)。CPU 可以從 I/O 控制器每次請求一個字節(jié)的數(shù)據(jù)，但是這么做會浪費 CPU 時間，所以經(jīng)常會用到一種稱為直接內(nèi)存訪問(Direct Memory Access) 的方案。為了簡化，我們假設 CPU 通過單一的系統(tǒng)總線訪問所有的設備和內(nèi)存，該總線連接 CPU 、內(nèi)存和 I/O 設備，如下圖所示

DMA 傳送操作

現(xiàn)代操作系統(tǒng)實際更為復雜，但是原理是相同的。如果硬件有DMA 控制器，那么操作系統(tǒng)只能使用 DMA。有時這個控制器會集成到磁盤控制器和其他控制器中，但這種設計需要在每個設備上都裝有一個分離的 DMA 控制器。單個的 DMA 控制器可用于向多個設備傳輸，這種傳輸往往同時進行。

DMA 工作原理

首先 CPU 通過設置 DMA 控制器的寄存器對它進行編程，所以 DMA 控制器知道將什么數(shù)據(jù)傳送到什么地方。DMA 控制器還要向磁盤控制器發(fā)出一個命令，通知它從磁盤讀數(shù)據(jù)到其內(nèi)部的緩沖區(qū)并檢驗校驗和。當有效數(shù)據(jù)位于磁盤控制器的緩沖區(qū)中時，DMA 就可以開始了。

DMA 控制器通過在總線上發(fā)出一個讀請求到磁盤控制器而發(fā)起 DMA 傳送，這是第二步。這個讀請求就像其他讀請求一樣，磁盤控制器并不知道或者并不關心它是來自 CPU 還是來自 DMA 控制器。通常情況下，要寫的內(nèi)存地址在總線的地址線上，所以當磁盤控制器去匹配下一個字時，它知道將該字寫到什么地方。寫到內(nèi)存就是另外一個總線循環(huán)了，這是第三步。當寫操作完成時，磁盤控制器在總線上發(fā)出一個應答信號到 DMA 控制器，這是第四步。

然后，DMA 控制器會增加內(nèi)存地址并減少字節(jié)數(shù)量。如果字節(jié)數(shù)量仍然大于 0 ，就會循環(huán)步驟 2 - 步驟 4 ，直到字節(jié)計數(shù)變?yōu)?0 。此時，DMA 控制器會打斷 CPU 并告訴它傳輸已經(jīng)完成了。

重溫中斷

在一臺個人計算機體系結構中，中斷結構會如下所示

中斷是怎樣發(fā)生的

當一個 I/O 設備完成它的工作后，它就會產(chǎn)生一個中斷（默認操作系統(tǒng)已經(jīng)開啟中斷），它通過在總線上聲明已分配的信號來實現(xiàn)此目的。主板上的中斷控制器芯片會檢測到這個信號，然后執(zhí)行中斷操作。

精確中斷和不精確中斷

使機器處于良好狀態(tài)的中斷稱為精確中斷(precise interrupt)。這樣的中斷具有四個屬性：

• PC （程序計數(shù)器）保存在一個已知的地方
• PC 所指向的指令之前所有的指令已經(jīng)完全執(zhí)行
• PC 所指向的指令之后所有的指令都沒有執(zhí)行
• PC 所指向的指令的執(zhí)行狀態(tài)是已知的

不滿足以上要求的中斷稱為 不精確中斷(imprecise interrupt)，不精確中斷讓人很頭疼。上圖描述了不精確中斷的現(xiàn)象。指令的執(zhí)行時序和完成度具有不確定性，而且恢復起來也非常麻煩。

IO 軟件原理

I/O 軟件目標

設備獨立性

I/O 軟件設計一個很重要的目標就是設備獨立性(device independence)。這意味著我們能夠編寫訪問任何設備的應用程序，而不用事先指定特定的設備。

錯誤處理

除了設備獨立性外，I/O 軟件實現(xiàn)的第二個重要的目標就是錯誤處理(error handling)。通常情況下來說，錯誤應該交給硬件層面去處理。如果設備控制器發(fā)現(xiàn)了讀錯誤的話，它會盡可能的去修復這個錯誤。如果設備控制器處理不了這個問題，那么設備驅(qū)動程序應該進行處理，設備驅(qū)動程序會再次嘗試讀取操作，很多錯誤都是偶然性的，如果設備驅(qū)動程序無法處理這個錯誤，才會把錯誤向上拋到硬件層面（上層）進行處理，很多時候，上層并不需要知道下層是如何解決錯誤的。

同步和異步傳輸

I/O 軟件實現(xiàn)的第三個目標就是 同步(synchronous) 和 異步(asynchronous，即中斷驅(qū)動)傳輸。這里先說一下同步和異步是怎么回事吧。

同步傳輸中數(shù)據(jù)通常以塊或幀的形式發(fā)送。發(fā)送方和接收方在數(shù)據(jù)傳輸之前應該具有同步時鐘。而在異步傳輸中，數(shù)據(jù)通常以字節(jié)或者字符的形式發(fā)送，異步傳輸則不需要同步時鐘，但是會在傳輸之前向數(shù)據(jù)添加奇偶校驗位。大部分物理IO(physical I/O) 是異步的。物理 I/O 中的 CPU 是很聰明的，CPU 傳輸完成后會轉(zhuǎn)而做其他事情，它和中斷心靈相通，等到中斷發(fā)生后，CPU 才會回到傳輸這件事情上來。

緩沖

I/O 軟件的最后一個問題是緩沖(buffering)。通常情況下，從一個設備發(fā)出的數(shù)據(jù)不會直接到達最后的設備。其間會經(jīng)過一系列的校驗、檢查、緩沖等操作才能到達。

共享和獨占

I/O 軟件引起的最后一個問題就是共享設備和獨占設備的問題。有些 I/O 設備能夠被許多用戶共同使用。一些設備比如磁盤，讓多個用戶使用一般不會產(chǎn)生什么問題，但是某些設備必須具有獨占性，即只允許單個用戶使用完成后才能讓其他用戶使用。

一共有三種控制 I/O 設備的方法

• 使用程序控制 I/O
• 使用中斷驅(qū)動 I/O
• 使用 DMA 驅(qū)動 I/O

I/O 層次結構

I/O 軟件通常組織成四個層次，它們的大致結構如下圖所示

下面我們具體的來探討一下上面的層次結構

中斷處理程序

在計算機系統(tǒng)中，中斷就像女人的脾氣一樣無時無刻都在產(chǎn)生，中斷的出現(xiàn)往往是讓人很不爽的。中斷處理程序又被稱為中斷服務程序 或者是 ISR(Interrupt Service Routines)，它是最靠近硬件的一層。中斷處理程序由硬件中斷、軟件中斷或者是軟件異常啟動產(chǎn)生的中斷，用于實現(xiàn)設備驅(qū)動程序或受保護的操作模式（例如系統(tǒng)調(diào)用）之間的轉(zhuǎn)換。

中斷處理程序負責處理中斷發(fā)生時的所有操作，操作完成后阻塞，然后啟動中斷驅(qū)動程序來解決阻塞。通常會有三種通知方式，依賴于不同的具體實現(xiàn)

• 信號量實現(xiàn)中：在信號量上使用 up 進行通知；
• 管程實現(xiàn)：對管程中的條件變量執(zhí)行 signal 操作
• 還有一些情況是發(fā)送一些消息

設備驅(qū)動程序

每個連接到計算機的 I/O 設備都需要有某些特定設備的代碼對其進行控制。這些提供 I/O 設備到設備控制器轉(zhuǎn)換的過程的代碼稱為 設備驅(qū)動程序(Device driver)。

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

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

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

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

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

在這種情況下，設備控制器會阻塞，直到中斷來解除阻塞狀態(tài)。還有一種情況是操作是可以無延遲的完成，所以驅(qū)動程序不需要阻塞。在第一種情況下，操作系統(tǒng)可能被中斷喚醒；第二種情況下操作系統(tǒng)不會被休眠。

設備驅(qū)動程序必須是可重入的，因為設備驅(qū)動程序會阻塞和喚醒然后再次阻塞。驅(qū)動程序不允許進行系統(tǒng)調(diào)用，但是它們通常需要與內(nèi)核的其余部分進行交互。

與設備無關的 I/O 軟件

I/O 軟件有兩種，一種是我們上面介紹過的基于特定設備的，還有一種是設備無關性的，設備無關性也就是不需要特定的設備。設備驅(qū)動程序與設備無關的軟件之間的界限取決于具體的系統(tǒng)。下面顯示的功能由設備無關的軟件實現(xiàn)

與設備無關的軟件的基本功能是對所有設備執(zhí)行公共的 I/O 功能，并且向用戶層軟件提供一個統(tǒng)一的接口。

緩沖

無論是對于塊設備還是字符設備來說，緩沖都是一個非常重要的考量標準。緩沖技術應用廣泛，但它也有缺點。如果數(shù)據(jù)被緩沖次數(shù)太多，會影響性能。

錯誤處理

在 I/O 中，出錯是一種再正常不過的情況了。當出錯發(fā)生時，操作系統(tǒng)必須盡可能處理這些錯誤。有一些錯誤是只有特定的設備才能處理，有一些是由框架進行處理，這些錯誤和特定的設備無關。

I/O 錯誤的一類是程序員編程錯誤，比如還沒有打開文件前就讀流，或者不關閉流導致內(nèi)存溢出等等。這類問題由程序員處理；另外一類是實際的 I/O 錯誤，例如向一個磁盤壞塊寫入數(shù)據(jù)，無論怎么寫都寫入不了。這類問題由驅(qū)動程序處理，驅(qū)動程序處理不了交給硬件處理，這個我們上面也說過。

設備驅(qū)動程序統(tǒng)一接口

我們在操作系統(tǒng)概述中說到，操作系統(tǒng)一個非常重要的功能就是屏蔽了硬件和軟件的差異性，為硬件和軟件提供了統(tǒng)一的標準，這個標準還體現(xiàn)在為設備驅(qū)動程序提供統(tǒng)一的接口，因為不同的硬件和廠商編寫的設備驅(qū)動程序不同，所以如果為每個驅(qū)動程序都單獨提供接口的話，這樣沒法搞，所以必須統(tǒng)一。

分配和釋放

一些設備例如打印機，它只能由一個進程來使用，這就需要操作系統(tǒng)根據(jù)實際情況判斷是否能夠?qū)υO備的請求進行檢查，判斷是否能夠接受其他請求，一種比較簡單直接的方式是在特殊文件上執(zhí)行 open操作。如果設備不可用，那么直接 open 會導致失敗。還有一種方式是不直接導致失敗，而是讓其阻塞，等到另外一個進程釋放資源后，在進行 open 打開操作。這種方式就把選擇權交給了用戶，由用戶判斷是否應該等待。

設備無關的塊

不同的磁盤會具有不同的扇區(qū)大小，但是軟件不會關心扇區(qū)大小，只管存儲就是了。一些字符設備可以一次一個字節(jié)的交付數(shù)據(jù)，而其他的設備則以較大的單位交付數(shù)據(jù)，這些差異也可以隱藏起來。

用戶空間的 I/O 軟件

雖然大部分 I/O 軟件都在內(nèi)核結構中，但是還有一些在用戶空間實現(xiàn)的 I/O 軟件，凡事沒有絕對。一些 I/O 軟件和庫過程在用戶空間存在，然后以提供系統(tǒng)調(diào)用的方式實現(xiàn)。

盤

盤可以說是硬件里面比較簡單的構造了，同時也是最重要的。下面我們從盤談起，聊聊它的物理構造

盤硬件

盤會有很多種類型。其中最簡單的構造就是磁盤(magnetic hard disks)， 也被稱為 hard disk,HDD等。磁盤通常與安裝在磁臂上的磁頭配對，磁頭可將數(shù)據(jù)讀取或者將數(shù)據(jù)寫入磁盤，因此磁盤的讀寫速度都同樣快。在磁盤中，數(shù)據(jù)是隨機訪問的，這也就說明可以通過任意的順序來存儲和檢索單個數(shù)據(jù)塊，所以你可以在任意位置放置磁盤來讓磁頭讀取，磁盤是一種非易失性的設備，即使斷電也能永久保留。

磁盤

為了組織和檢索數(shù)據(jù)，會將磁盤組織成特定的結構，這些特定的結構就是磁道、扇區(qū)和柱面

磁盤被組織成柱面形式，每個盤用軸相連，每一個柱面包含若干磁道，每個磁道由若干扇區(qū)組成。軟盤上大約每個磁道有 8 - 32 個扇區(qū)，硬盤上每條磁道上扇區(qū)的數(shù)量可達幾百個，磁頭大約是 1 - 16 個。

對于磁盤驅(qū)動程序來說，一個非常重要的特性就是控制器是否能夠同時控制兩個或者多個驅(qū)動器進行磁道尋址，這就是重疊尋道(overlapped seek)。對于控制器來說，它能夠控制一個磁盤驅(qū)動程序完成尋道操作，同時讓其他驅(qū)動程序等待尋道結束。控制器也可以在一個驅(qū)動程序上進行讀寫草哦做，與此同時讓另外的驅(qū)動器進行尋道操作，但是軟盤控制器不能在兩個驅(qū)動器上進行讀寫操作。

RAID

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

RAID 有不同的級別

• RAID 0 - 無容錯的條帶化磁盤陣列
• RAID 1 - 鏡像和雙工
• RAID 2 - 內(nèi)存式糾錯碼
• RAID 3 - 比特交錯奇偶校驗
• RAID 4 - 塊交錯奇偶校驗
• RAID 5 - 塊交錯分布式奇偶校驗
• RAID 6 - P + Q冗余

磁盤格式化

磁盤由一堆鋁的、合金或玻璃的盤片組成，磁盤剛被創(chuàng)建出來后，沒有任何信息。磁盤在使用前必須經(jīng)過低級格式化(low-levvel format)，下面是一個扇區(qū)的格式

前導碼相當于是標示扇區(qū)的開始位置，通常以位模式開始，前導碼還包括柱面號、扇區(qū)號等一些其他信息。緊隨前導碼后面的是數(shù)據(jù)區(qū)，數(shù)據(jù)部分的大小由低級格式化程序來確定。大部分磁盤使用 512 字節(jié)的扇區(qū)。數(shù)據(jù)區(qū)后面是 ECC，ECC 的全稱是 error correction code ，數(shù)據(jù)糾錯碼，它與普通的錯誤檢測不同，ECC 還可以用于恢復讀錯誤。ECC 階段的大小由不同的磁盤制造商實現(xiàn)。ECC 大小的設計標準取決于設計者愿意犧牲多少磁盤空間來提高可靠性，以及程序可以處理的 ECC 的復雜程度。通常情況下 ECC 是 16 位，除此之外，硬盤一般具有一定數(shù)量的備用扇區(qū)，用于替換制造缺陷的扇區(qū)。

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

下面我們來探討一下關于影響磁盤讀寫的算法，一般情況下，影響磁盤快讀寫的時間由下面幾個因素決定

• 尋道時間 - 尋道時間指的就是將磁盤臂移動到需要讀取磁盤塊上的時間
• 旋轉(zhuǎn)延遲 - 等待合適的扇區(qū)旋轉(zhuǎn)到磁頭下所需的時間
• 實際數(shù)據(jù)的讀取或者寫入時間

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

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

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

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

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

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

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

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

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

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

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

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

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

錯誤處理

一般壞塊有兩種處理辦法，一種是在控制器中進行處理；一種是在操作系統(tǒng)層面進行處理。

這兩種方法經(jīng)常替換使用，比如一個具有 30 個數(shù)據(jù)扇區(qū)和兩個備用扇區(qū)的磁盤，其中扇區(qū) 4 是有瑕疵的。

控制器能做的事情就是將備用扇區(qū)之一重新映射。

還有一種處理方式是將所有的扇區(qū)都向上移動一個扇區(qū)

上面這這兩種情況下控制器都必須知道哪個扇區(qū)，可以通過內(nèi)部的表來跟蹤這一信息，或者通過重寫前導碼來給出重新映射的扇區(qū)號。如果是重寫前導碼，那么涉及移動的方式必須重寫后面所有的前導碼，但是最終會提供良好的性能。

穩(wěn)定存儲器

磁盤經(jīng)常會出現(xiàn)錯誤，導致好的扇區(qū)會變成壞扇區(qū)，驅(qū)動程序也有可能掛掉。RAID 可以對扇區(qū)出錯或者是驅(qū)動器崩潰提出保護，然而 RAID 卻不能對壞數(shù)據(jù)中的寫錯誤提供保護，也不能對寫操作期間的崩潰提供保護，這樣就會破壞原始數(shù)據(jù)。

我們期望磁盤能夠準確無誤的工作，但是事實情況是不可能的，但是我們能夠知道的是，一個磁盤子系統(tǒng)具有如下特性：當一個寫命令發(fā)給它時，磁盤要么正確地寫數(shù)據(jù)，要么什么也不做，讓現(xiàn)有的數(shù)據(jù)完整無誤的保留。這樣的系統(tǒng)稱為 穩(wěn)定存儲器(stable storage)。 穩(wěn)定存儲器的目標就是不惜一切代價保證磁盤的一致性。

穩(wěn)定存儲器使用兩個一對相同的磁盤，對應的塊一同工作形成一個無差別的塊。穩(wěn)定存儲器為了實現(xiàn)這個目的，定義了下面三種操作：

• 穩(wěn)定寫(stable write)
• 穩(wěn)定讀(stable read)
• 崩潰恢復(crash recovery)

時鐘

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

時鐘硬件

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

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

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

時鐘軟件

時鐘硬件所做的工作只是根據(jù)已知的時間間隔產(chǎn)生中斷，而其他的工作都是由時鐘軟件來完成，一般操作系統(tǒng)的不同，時鐘軟件的具體實現(xiàn)也不同，但是一般都會包括以下這幾點

• 維護一天的時間
• 阻止進程運行的時間超過其指定時間
• 統(tǒng)計 CPU 的使用情況
• 處理用戶進程的警告系統(tǒng)調(diào)用
• 為系統(tǒng)各個部分提供看門狗定時器
• 完成概要剖析，監(jiān)視和信息收集

軟定時器

時鐘軟件也被稱為可編程時鐘，可以設置它以程序需要的任何速率引發(fā)中斷。時鐘軟件觸發(fā)的中斷是一種硬中斷，但是某些應用程序?qū)τ谟仓袛鄟碚f是不可接受的。

這時候就需要一種軟定時器(soft timer) 避免了中斷，無論何時當內(nèi)核因為某種原因呢在運行時，它返回用戶態(tài)之前都會檢查時鐘來了解軟定時器是否到期。如果軟定時器到期，則執(zhí)行被調(diào)度的事件也無需切換到內(nèi)核態(tài)，因為本身已經(jīng)處于內(nèi)核態(tài)中。這種方式避免了頻繁的內(nèi)核態(tài)和用戶態(tài)之前的切換，提高了程序運行效率。

軟定時器因為不同的原因切換進入內(nèi)核態(tài)的速率不同，原因主要有

• 系統(tǒng)調(diào)用
• TLB 未命中
• 缺頁異常
• I/O 中斷
• CPU 變得空閑

死鎖問題也是操作系統(tǒng)非常重要的一類問題

資源

大部分的死鎖都和資源有關，在進程對設備、文件具有獨占性（排他性）時會產(chǎn)生死鎖。我們把這類需要排他性使用的對象稱為資源(resource)。資源主要分為 可搶占資源和不可搶占資源

可搶占資源和不可搶占資源

資源主要有可搶占資源和不可搶占資源。可搶占資源(preemptable resource) 可以從擁有它的進程中搶占而不會造成其他影響，內(nèi)存就是一種可搶占性資源，任何進程都能夠搶先獲得內(nèi)存的使用權。

不可搶占資源(nonpreemtable resource) 指的是除非引起錯誤或者異常，否則進程無法搶占指定資源，這種不可搶占的資源比如有光盤，在進程執(zhí)行調(diào)度的過程中，其他進程是不能得到該資源的。

死鎖

如果要對死鎖進行一個定義的話，下面的定義比較貼切

如果一組進程中的每個進程都在等待一個事件，而這個事件只能由該組中的另一個進程觸發(fā)，這種情況會導致死鎖。

資源死鎖的條件

針對我們上面的描述，資源死鎖可能出現(xiàn)的情況主要有

• 互斥條件：每個資源都被分配給了一個進程或者資源是可用的
• 保持和等待條件：已經(jīng)獲取資源的進程被認為能夠獲取新的資源
• 不可搶占條件：分配給一個進程的資源不能強制的從其他進程搶占資源，它只能由占有它的進程顯示釋放
• 循環(huán)等待：死鎖發(fā)生時，系統(tǒng)中一定有兩個或者兩個以上的進程組成一個循環(huán)，循環(huán)中的每個進程都在等待下一個進程釋放的資源。

發(fā)生死鎖時，上面的情況必須同時會發(fā)生。如果其中任意一個條件不會成立，死鎖就不會發(fā)生。可以通過破壞其中任意一個條件來破壞死鎖，下面這些破壞條件就是我們探討的重點

死鎖模型

Holt 在 1972 年提出對死鎖進行建模，建模的標準如下：

• 圓形表示進程
• 方形表示資源

從資源節(jié)點到進程節(jié)點表示資源已經(jīng)被進程占用，如下圖所示

在上圖中表示當前資源 R 正在被 A 進程所占用

由進程節(jié)點到資源節(jié)點的有向圖表示當前進程正在請求資源，并且該進程已經(jīng)被阻塞，處于等待這個資源的狀態(tài)

在上圖中，表示的含義是進程 B 正在請求資源 S 。Holt 認為，死鎖的描述應該如下

這是一個死鎖的過程，進程 C 等待資源 T 的釋放，資源 T 卻已經(jīng)被進程 D 占用，進程 D 等待請求占用資源 U ，資源 U 卻已經(jīng)被線程 C 占用，從而形成環(huán)。

有四種處理死鎖的策略：

• 忽略死鎖帶來的影響（驚呆了）
• 檢測死鎖并回復死鎖，死鎖發(fā)生時對其進行檢測，一旦發(fā)生死鎖后，采取行動解決問題
• 通過仔細分配資源來避免死鎖
• 通過破壞死鎖產(chǎn)生的四個條件之一來避免死鎖

下面我們分別介紹一下這四種方法

鴕鳥算法

最簡單的解決辦法就是使用鴕鳥算法(ostrich algorithm)，把頭埋在沙子里，假裝問題根本沒有發(fā)生。每個人看待這個問題的反應都不同。數(shù)學家認為死鎖是不可接受的，必須通過有效的策略來防止死鎖的產(chǎn)生。工程師想要知道問題發(fā)生的頻次，系統(tǒng)因為其他原因崩潰的次數(shù)和死鎖帶來的嚴重后果。如果死鎖發(fā)生的頻次很低，而經(jīng)常會由于硬件故障、編譯器錯誤等其他操作系統(tǒng)問題導致系統(tǒng)崩潰，那么大多數(shù)工程師不會修復死鎖。

死鎖檢測和恢復

第二種技術是死鎖的檢測和恢復。這種解決方式不會嘗試去阻止死鎖的出現(xiàn)。相反，這種解決方案會希望死鎖盡可能的出現(xiàn)，在監(jiān)測到死鎖出現(xiàn)后，對其進行恢復。下面我們就來探討一下死鎖的檢測和恢復的幾種方式

每種類型一個資源的死鎖檢測方式

每種資源類型都有一個資源是什么意思？我們經(jīng)常提到的打印機就是這樣的，資源只有打印機，但是設備都不會超過一個。

可以通過構造一張資源分配表來檢測這種錯誤，比如我們上面提到的

如果這張圖包含了一個或一個以上的環(huán)，那么死鎖就存在，處于這個環(huán)中任意一個進程都是死鎖的進程。

每種類型多個資源的死鎖檢測方式

如果有多種相同的資源存在，就需要采用另一種方法來檢測死鎖。可以通過構造一個矩陣來檢測從 P1 -> Pn 這 n 個進程中的死鎖。

現(xiàn)在我們提供一種基于矩陣的算法來檢測從 P1 到 Pn 這 n 個進程中的死鎖。假設資源類型為 m，E1 代表資源類型1，E2 表示資源類型 2 ，Ei 代表資源類型 i (1 <=i <=m)。E 表示的是 現(xiàn)有資源向量(existing resource vector)，代表每種已存在的資源總數(shù)。

現(xiàn)在我們就需要構造兩個數(shù)組：C 表示的是當前分配矩陣(current allocation matrix) ，R 表示的是 請求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數(shù)。所以，Cij 表示 Pi 持有資源 j 的數(shù)量。Rij 表示 Pi 所需要獲得的資源 j 的數(shù)量

一般來說，已分配資源 j 的數(shù)量加起來再和所有可供使用的資源數(shù)相加=該類資源的總數(shù)。

死鎖的檢測就是基于向量的比較。每個進程起初都是沒有被標記過的，算法會開始對進程做標記，進程被標記后說明進程被執(zhí)行了，不會進入死鎖，當算法結束時，任何沒有被標記過的進程都會被判定為死鎖進程。

上面我們探討了兩種檢測死鎖的方式，那么現(xiàn)在你知道怎么檢測后，你何時去做死鎖檢測呢？一般來說，有兩個考量標準：

• 每當有資源請求時就去檢測，這種方式會占用昂貴的 CPU 時間。
• 每隔 k 分鐘檢測一次，或者當 CPU 使用率降低到某個標準下去檢測。考慮到 CPU 效率的原因，如果死鎖進程達到一定數(shù)量，就沒有多少進程可以運行，所以 CPU 會經(jīng)常空閑。

從死鎖中恢復

上面我們探討了如何檢測進程死鎖，我們最終的目的肯定是想讓程序能夠正常的運行下去，所以針對檢測出來的死鎖，我們要對其進行恢復，下面我們會探討幾種死鎖的恢復方式

通過搶占進行恢復

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

通過回滾進行恢復

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

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

殺死進程恢復

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

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

死鎖避免

我們上面討論的是如何檢測出現(xiàn)死鎖和如何恢復死鎖，下面我們探討幾種規(guī)避死鎖的方式

單個資源的銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調(diào)度算法，它本身是一種死鎖的調(diào)度算法。它的模型是基于一個城鎮(zhèn)中的銀行家，銀行家向城鎮(zhèn)中的客戶承諾了一定數(shù)量的貸款額度。算法要做的就是判斷請求是否會進入一種不安全的狀態(tài)。如果是，就拒絕請求，如果請求后系統(tǒng)是安全的，就接受該請求。

類似的，還有多個資源的銀行家算法，讀者可以自行了解。

破壞死鎖

死鎖本質(zhì)上是無法避免的，因為它需要獲得未知的資源和請求，但是死鎖是滿足四個條件后才出現(xiàn)的，它們分別是

• 互斥
• 保持和等待
• 不可搶占
• 循環(huán)等待

我們分別對這四個條件進行討論，按理說破壞其中的任意一個條件就能夠破壞死鎖

破壞互斥條件

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

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

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

破壞保持等待的條件

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

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

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

破壞不可搶占條件

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

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

現(xiàn)在就剩最后一個條件了，循環(huán)等待條件可以通過多種方法來破壞。一種方式是制定一個標準，一個進程在任何時候只能使用一種資源。如果需要另外一種資源，必須釋放當前資源。對于需要將大文件從磁帶復制到打印機的過程，此限制是不可接受的。

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

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

盡管通過這種方式來消除死鎖，但是編號的順序不可能讓每個進程都會接受。

其他問題

下面我們來探討一下其他問題，包括 通信死鎖、活鎖是什么、饑餓問題和兩階段加鎖

兩階段加鎖

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

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

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

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

通信死鎖

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

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

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

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

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

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

活鎖

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

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

饑餓

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

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