連續分配需要多少次磁碟io刪除一個物理塊

1. 編程實現連續分配,鏈接分配和索引分配等三種外存分配方式

一. 連續分配

原理：創建文件時，分配一組連續的塊；FAT（文檔分配表）中每個文件只要一項，說明起始塊和文件長度。對於順序文件有利。

優點：1.簡便。適用於一次性寫入操作。2.支持順序存取和隨機存取，順序存取速度快。3.所需的磁碟尋道次數和尋道時間最少。（因為空間的連續性，當訪問下一個磁碟塊時，一般無需移動磁頭，當需要移動磁頭時，只需要移動一個磁軌。）

缺點：1.文件不能動態增長。（可能文件末尾處的空塊已經分配給了別的文件。）2.不利於文件的插入和刪除。3.外部碎片問題。（反復增刪文件後，很難找到空間大小足夠的連續塊，需要進行緊縮。）4.在創建文件時需生命文件大小。

如圖：

2. 文件管理

文件名：同一目錄下不允許有同名文件 標識符：一個系統內的各文件標識符唯一，對用戶來說毫無可讀性，因此標識符只是操作系統用於區分各個文件的一種內部名稱
類型
位置：文件的存放路徑（讓用戶使用）、在外存中的地址（操作系統使用，對用戶不可見）
大小
創建時間
上次修改時間
創建者
保護信息：對文件進行保護的訪問控制信息

文件內部的數據組織方式

文件如何存放在外存
邏輯塊號+塊內地址

順序文件

鏈式存儲無法實現隨機存取，每次只能從第一個記錄開始往後查找
順序可變長記錄無法實現隨機存取，每次只能從第一個記錄開始往後查找
順序存儲定長記錄可實現隨機存取，若採用串結構，無法快速找到某關鍵字對應的記錄，若採用順序結構可以快速找到某關鍵字對應的記錄

串結構比順序結構的增刪更簡單，因為串結構不需要關鍵字按順序排列

索引文件

建立一張索引表以加快文件檢索速度，每條記錄對應一個索引項
索引項本身是定長記錄的順序文件，因此可以快速找到第i個記錄對應的索引項
將關鍵字作為索引號內容，若按關鍵字順序排列，還可以支持按照關鍵字對半查找
每當要增加/刪除一個記錄，需要對索引表進行修改
主要用於對信息處理的及時性要求比較高的場合
還可以用不同的數據項建立多個索引表

多級索引

目錄本身就是一種有結構文件，由一條條記錄組成，每條記錄對應一個該存放在該目錄下的文件

文件控制塊FCB：目錄文件中的一條記錄，實現了文件名和文件之間的映射，使用戶可以按名存取。包含文件名、物理地址、邏輯結構、物理結構、存儲控制信息、使用信息等，最基本的是文件名和文件存放的物理地址

單級目錄：不允許文件重名

兩級目錄：主文件目錄，用戶文件目錄
不同用戶的文件可以重名，也可以實現訪問限制，usr1不可以訪問usr2的文件

多級目錄結構
絕對路徑：從根目錄出發的路徑，/照片/2015/自拍.jpg，三次讀盤IO操作
相對路徑：從當前目錄出發，./2015/自拍.jpg，兩次讀盤IO操作

無環圖目錄結構
可以用不同的文件名指向同一個文件，甚至可以指向同一個目錄。可以為共享節點設置共享計數器，共享計數器為0時，真正刪除文件

磁碟塊：在很多操作系統中，磁碟塊的大小與內存塊、頁面的大小相同
磁碟IO、讀寫操作：內存和磁碟之間的數據交換，以塊為單位進行，每次讀入一塊，或者每次寫出一塊
文件的邏輯地址也可以表示為邏輯塊號和塊內地址的形式
用戶通過邏輯地址來操作自己的文件，操作系統要負責實現從邏輯地址到物理地址的映射

連續分配：每個文件在磁碟上佔有一組連續的塊
此時文件目錄項中需要記錄文件的起始塊號和長度（佔用了多少個塊）
用戶給出要訪問的邏輯塊號時，操作系統需要檢查用戶提供的邏輯塊號是否合法（邏輯塊號≥長度）
優點1：可以直接算出邏輯塊號對應的物理塊號，因此連續分配支持順序訪問和直接訪問（隨機訪問）
優點2：讀取磁碟塊時，需要移動磁頭，訪問的兩個磁碟塊相距越遠，移動磁頭所需時間越長。因此連續分配的文件在順序讀寫時速度最快
缺點：物理上採用連續分配的文件不方便拓展（需要移動）；會產生磁碟碎片，使得空間利用率降低（可以用緊湊技術，需要很大的時間代價）

鏈接分配：採取離散分配，通過指針鏈接將磁碟塊連接

默認是隱式鏈接

索引分配：系統為每個文件建立一張索引表，表中記錄文件的各個邏輯塊對應的物理塊（相當於頁表），索引表存放的磁碟塊稱為索引塊，文件數據存放的磁碟塊稱為數據塊
目錄中需要記錄文件的索引塊是幾號磁碟塊，索引表中邏輯塊號是隱藏的

與顯式鏈接的區別：FAT是整個磁碟對應一張FAT，索引表是一個文件對應一張索引表

支持隨機訪問，容易實現文件拓展
索引表需要佔用空間

如果索引表太大怎麼辦

3. 設一個文件由100個物理塊所組成

101

4. 程序員必備知識（操作系統5-文件系統）

本篇與之前的第三篇的內存管理知識點有相似的地方

對於運行的進程來說，內存就像一個紙箱子, 僅僅是一個暫存數據的地方， 而且空間有限。如果我們想要進程結束之後，數據依然能夠保存下來，就不能只保存在內存里，而是應該保存在 外部存儲 中。就像圖書館這種地方，不僅空間大,而且能夠永久保存。

我們最常用的外部存儲就是 硬碟 ，數據是以文件的形式保存在硬碟上的。為了管理這些文件，我們在規劃文件系統的時候，需要考慮到以下幾點。

第一點,文件系統要有嚴格的組織形式，使得文件能夠 以塊為單位進行存儲 。這就像圖書館里，我們會給設置一排排書架，然後再把書架分成一個個小格子，有的項目存放的資料非常多，一個格子放不下，就需要多個格子來進行存放。我們把這個區域稱為存放原始資料的 倉庫區 。

第二點,文件系統中也要有 索引區 ，用來方便查找一個文件分成的多個塊都存放在了什麼位置。這就好比，圖書館的書太多了,為了方便查找,我們需要專門設置一排書架,這裡面會寫清楚整個檔案庫有哪些資料,資料在哪個架子的哪個格子上。這樣找資料的時候就不用跑遍整個檔案庫,在這個書架上找到後，直奔目標書架就可以了。

第三點,如果文件系統中有的文件是熱點文件,近期經常被讀取和寫入，文件系統應該有 緩存層 。這就相當於圖書館裡面的熱門圖書區,這裡面的書都是暢銷書或者是常常被借還的圖書。因為借還的次數比較多,那就沒必要每次有人還了之後，還放回遙遠的貨架，我們可以專門開辟一個區域, 放置這些借還頻次高的圖書。這樣借還的效率就會提高。

第四點,文件應該用 文件夾 的形式組織起來，方便管理和查詢。這就像在圖書館裡面，你可以給這些資料分門別類,比如分成計算機類.文學類.歷史類等等。這樣你也容易管理，項目組借閱的時候只要在某個類別中去找就可以了。

在文件系統中，每個文件都有一個名字,這樣我們訪問一個文件，希望通過它的名字就可以找到。文件名就是一個普通的文本。 當然文件名會經常沖突,不同用戶取相同的名字的情況還是會經常出現的。

要想把很多的文件有序地組織起來,我們就需要把它們成為 目錄 或者文件夾。這樣,一個文件夾里可以包含文件夾,也可以包含文件,這樣就形成了一種 樹形結構 。而我們可以將不同的用戶放在不同的用戶目錄下，就可以一定程度上避免了命名的沖突問題。

第五點，Linux 內核要在自己的內存裡面維護一套數據結構，來保存哪些文件被哪些進程打開和使用 。這就好比，圖書館里會有個圖書管理系統，記錄哪些書被借閱了，被誰借閱了，借閱了多久,什麼時候歸還。

文件系統是操作系統中負責管理持久數據的子系統，說簡單點,就是負責把用戶的文件存到磁碟硬體中,因為即使計算機斷電了，磁碟里的數據並不會丟失,所以可以持久化的保存文件。

文件系統的基本數據單位是 文件 ，它的目的是對磁碟上的文件進行組織管理，那組織的方式不同,就會形成不同的文件系統。

Linux最經典的一句話是:「一切皆文件」,不僅普通的文件和目錄，就連塊設備、管道、socket 等，也都是統一交給文件系統管理的。

Linux文件系統會為每個文件分配兩個數據結構: 索引節點(index node) 和 目錄項(directory entry) ，它們主要用來記錄文件的元信息和目錄層次結構。

●索引節點，也就是inode, 用來記錄文件的元信息，比如inode編號、文件大小訪問許可權、創建時間、修改時間、 數據在磁碟的位置 等等。 索引節點是文件的唯一標識 ,它們之間一一對應, 也同樣都會被 存儲在硬碟 中,所以索引節點同樣佔用磁碟空間。

●目錄項，也就是dentry, 用來記錄文件的名字、索引節點指針以及與其他目錄項的層級關聯關系。多個目錄項關聯起來，就會形成 目錄結構 ，但它與索引節點不同的是,目錄項是由內核維護的一個數據結構,不存放於磁碟，而是 緩存在內存 。

由於索引節點唯一標識一個文件，而目錄項記錄著文件的名，所以目錄項和索引節點的關系是多對一,也就是說，一個文件可以有多個別字。比如，硬鏈接的實現就是多個目錄項中的索引節點指向同一個文件。

注意，目錄也是文件，也是用索引節點唯一標識，和普通文件不同的是，普通文件在磁碟裡面保存的是文件數據，而目錄文件在磁碟裡面保存子目錄或文件。

（PS：目錄項和目錄不是一個東西！你也不是一個東西（^_=）， 雖然名字很相近，但目錄是個文件。持久化存儲在磁碟,而目錄項是內核一個數據結構,緩存在內存。

如果查詢目錄頻繁從磁碟讀，效率會很低，所以內核會把已經讀過的目錄用目錄項這個數據結構緩存在內存，下次再次讀到相同的目錄時，只需從內存讀就可以,大大提高了 文件系統的效率。

目錄項這個數據結構不只是表示目錄，也是可以表示文件的。）

磁碟讀寫的最小單位是 扇區 ，扇區的大小隻有512B大小，很明顯，如果每次讀寫都以這么小為單位，那這讀寫的效率會非常低。

所以，文件系統把多個扇區組成了一個 邏輯塊 ，每次讀寫的最小單位就是邏輯塊(數據塊) , Linux中的邏輯塊大小為4KB,也就是一次性讀寫 8個扇區,這將大大提高了磁碟的讀寫的效率。

以上就是索引節點、目錄項以及文件數據的關系，下面這個圖就很好的展示了它們之間的關系:

索引節點是存儲在硬碟上的數據，那麼為了加速文件的訪問，通常會把索引節點載入到內存中。

另外，磁碟進行格式化的時候，會被分成三個存儲區域，分別是超級塊、索引節點區和數據塊區。

●超級塊,用來存儲文件系統的詳細信息，比如塊個數、塊大小、空閑塊等等。

●索引節點區,用來存儲索引節點;

●數據塊區，用來存儲文件或目錄數據;

我們不可能把超級塊和索引節點區全部載入到內存,這樣內存肯定撐不住，所以只有當需要使用的時候，才將其載入進內存，它們載入進內存的時機是不同的.

●超級塊:當文件系統掛載時進入內存;

●索引節點區:當文件被訪問時進入內存;

文件系統的種類眾多，而操作系統希望 對用戶提供一個統一的介面 ，於是在用戶層與文件系統層引入了中間層，這個中間層就稱為 虛擬文件系統(Virtual File System, VFS) 。

VFS定義了一組所有文件系統都支持的數據結構和標准介面,這樣程序員不需要了解文件系統的工作原理，只需要了解VFS提供的統一介面即可。

在Linux文件系統中，用戶空間、系統調用、虛擬機文件系統、緩存、文件系統以及存儲之間的關系如下圖:

Linux支持的文件系統也不少，根據存儲位置的不同，可以把文件系統分為三類:

●磁碟的文件系統，它是直接把數據存儲在磁碟中,比如Ext 2/3/4. XFS 等都是這類文件系統。

●內存的文件系統，這類文件系統的數據不是存儲在硬碟的,而是佔用內存空間，我們經常用到的/proc 和/sys文件系統都屬於這一類,讀寫這類文件,實際上是讀寫內核中相關的數據。

●網路的文件系統,用來訪問其他計算機主機數據的文件系統，比如NFS. SMB等等。

文件系統首先要先掛載到某個目錄才可以正常使用，比如Linux系統在啟動時,會把文件系統掛載到根目錄。

在操作系統的輔助之下，磁碟中的數據在計算機中都會呈現為易讀的形式，並且我們不需要關心數據到底是如何存放在磁碟中,存放在磁碟的哪個地方等等問題，這些全部都是由操作系統完成的。

那麼，文件數據在磁碟中究竟是怎麼樣的呢?我們來一探究竟!

磁碟中的存儲單元會被劃分為一個個的「 塊 」，也被稱為 扇區 ,扇區的大小一般都為512byte.這說明即使一塊數據不足512byte,那麼它也要佔用512byte的磁碟空間。

而幾乎所有的文件系統都會把文件分割成固定大小的塊來存儲，通常一個塊的大小為4K。如果磁碟中的扇區為512byte,而文件系統的塊大小為4K,那麼文件系統的存儲單元就為8個扇區。這也是前面提到的一個問題，文件大小和佔用空間之間有什麼區別?文件大小是文件實際的大小，而佔用空間則是因為即使它的實際大小沒有達到那麼大,但是這部分空間實際也被佔用，其他文件數據無法使用這部分的空間。所以我們 寫入1byte的數據到文本中,但是它佔用的空間也會是4K。

這里要注意在Windows下的NTFS文件系統中，如果一開始文件數據小於 1K,那麼則不會分配磁碟塊來存儲，而是存在一個文件表中。但是一旦文件數據大於1K,那麼不管以後文件的大小，都會分配以4K為單位的磁碟空間來存儲。

與內存管理一樣,為了方便對磁碟的管理,文件的邏輯地址也被分為一個個的文件塊。於是文件的邏輯地址就是(邏輯塊號，塊內地址)。用戶通過邏輯地址來操作文件,操作系統負責完成邏輯地址與物理地址的映射。

不同的文件系統為文件分配磁碟空間會有不同的方式，這些方式各自都有優缺點。

連續分配要求每個文件在磁碟上有一組連續的塊，該分配方式較為簡單。

通過上圖可以看到，文件的邏輯塊號的順序是與物理塊號相同的,這樣就可以實現隨機存取了，只要知道了第一個邏輯塊的物理地址, 那麼就可以快速訪問到其他邏輯塊的物理地址。那麼操作系統如何完成邏輯塊與物理塊之間的映射呢?實際上,文件都是存放在目錄下的，而目錄是一種有結構文件, 所以在文件目錄的記錄中會存放目錄下所有文件的信息，每一個文件或者目錄都是一個記錄。 而這些信息就包括文件的起始塊號和佔有塊號的數量。

那麼操作系統如何完成邏輯塊與物理塊之間的映射呢? (邏輯塊號, 塊內地址) -> (物理塊號, 塊內地址)，只需要知道邏輯塊號對應的物理塊號即可,塊內地址不變。

用戶訪問一個文件的內容,操作系統通過文件的標識符找到目錄項FCB, 物理塊號=起始塊號+邏輯塊號。 當然，還需要檢查邏輯塊號是否合法,是否超過長度等。因為可以根據邏輯塊號直接算出物理塊號，所以連續分配支持 順序訪問和隨機訪問 。

因為讀/寫文件是需要移動磁頭的，如果訪問兩個相隔很遠的磁碟塊,移動磁頭的時間就會變長。使用連續分配來作為文件的分配方式，會使文件的磁碟塊相鄰，所以文件的讀/寫速度最快。

連續空間存放的方式雖然讀寫效率高，但是有 磁碟空間碎片 和 文件長度不易擴展 的缺陷。

如下圖，如果文件B被刪除，磁碟上就留下一塊空缺，這時，如果新來的文件小於其中的一個空缺，我們就可以將其放在相應空缺里。但如果該文件的大小大於所

有的空缺，但卻小於空缺大小之和，則雖然磁碟上有足夠的空缺，但該文件還是不能存放。當然了，我們可以通過將現有文件進行挪動來騰出空間以容納新的文件,但是這個在磁碟挪動文件是非常耗時，所以這種方式不太現實。

另外一個缺陷是文件長度擴展不方便，例如上圖中的文件A要想擴大一下，需要更多的磁碟空間,唯一的辦法就只能是挪動的方式，前面也說了，這種方式效率是非常低的。

那麼有沒有更好的方式來解決上面的問題呢?答案當然有，既然連續空間存放的方式不太行，那麼我們就改變存放的方式，使用非連續空間存放方式來解決這些缺陷。

非連續空間存放方式分為 鏈表方式 和 索引方式 。

鏈式分配採取離散分配的方式，可以為文件分配離散的磁碟塊。它有兩種分配方式:顯示鏈接和隱式鏈接。

隱式鏈接是只目錄項中只會記錄文件所佔磁碟塊中的第一塊的地址和最後一塊磁碟塊的地址, 然後通過在每一個磁碟塊中存放一個指向下一 磁碟塊的指針， 從而可以根據指針找到下一塊磁碟塊。如果需要分配新的磁碟塊,則使用最後一塊磁碟塊中的指針指向新的磁碟塊,然後修改新的磁碟塊為最後的磁碟塊。

我們來思考一個問題, 採用隱式鏈接如何將實現邏輯塊號轉換為物理塊號呢?

用戶給出需要訪問的邏輯塊號i,操作系統需要找到所需訪問文件的目錄項FCB.從目錄項中可以知道文件的起始塊號，然後將邏輯塊號0的數據讀入內存,由此知道1號邏輯塊的物理塊號，然後再讀入1號邏輯塊的數據進內存，此次類推，最終可以找到用戶所需訪問的邏輯塊號i。訪問邏輯塊號i,總共需要i+ 1次磁碟1/0操作。

得出結論: 隱式鏈接分配只能順序訪問，不支持隨機訪問，查找效率低 。

我們來思考另外一個問題，採用隱式鏈接是否方便文件拓展?

我們知道目錄項中存有結束塊號的物理地址，所以我們如果要拓展文件，只需要將新分配的磁碟塊掛載到結束塊號的後面即可，修改結束塊號的指針指向新分配的磁碟塊，然後修改目錄項。

得出結論: 隱式鏈接分配很方便文件拓展。所有空閑磁碟塊都可以被利用到，無碎片問題，存儲利用率高。

顯示鏈接是把用於鏈接各個物理塊的指針顯式地存放在一張表中，該表稱為文件分配表(FAT, File Allocation Table)。

由於查找記錄的過程是在內存中進行的,因而不僅顯著地 提高了檢索速度 ，而且 大大減少了訪問磁碟的次數 。但也正是整個表都存放在內存中的關系，它的主要的缺點是 不適 用於大磁碟 。

比如，對於200GB的磁碟和1KB大小的塊，這張表需要有2億項，每一項對應於這2億個磁碟塊中的一個塊,每項如果需要4個位元組，那這張表要佔用800MB內存,很顯然FAT方案對於大磁碟而言不太合適。

一直都在，加油！（*゜Д゜）σ凸←自爆按鈕

鏈表的方式解決了連續分配的磁碟碎片和文件動態打展的問題，但是不能有效支持直接訪問(FAT除外) ,索引的方式可以解決這個問題。

索引的實現是為每個文件創建一個 索引數據塊 ，裡面存放的 是指向文件數據塊的指針列表 ,說白了就像書的目錄一樣,要找哪個章節的內容,看目錄查就可以。

另外， 文件頭需要包含指向索引數據塊的指針 ,這樣就可以通過文件頭知道索引數據塊的位置，再通過索弓|數據塊里的索引信息找到對應的數據塊。

創建文件時，索引塊的所有指針都設為空。當首次寫入第i塊時，先從空閑空間中取得一個塊， 再將其地址寫到索引塊的第i個條目。

索引的方式優點在於:

●文件的創建、增大、縮小很方便;

●不會有碎片的問題;

●支持順序讀寫和隨機讀寫;

由於索引數據也是存放在磁碟塊的，如果文件很小，明明只需一塊就可以存放的下，但還是需要額外分配一塊來存放索引數據，所以缺陷之一就是存儲索引帶來的開銷。

如果文件很大，大到一個索引數據塊放不下索引信息，這時又要如何處理大文件的存放呢?我們可以通過組合的方式，來處理大文件的存儲。

先來看看 鏈表+索引 的組合，這種組合稱為 鏈式索引塊 ，它的實現方式是在 索引數據塊留出一個存放下一個索引數據塊的指針 ，於是當一個索引數據塊的索引信息用完了，就可以通過指針的方式，找到下一個索引數據塊的信息。那這種方式也會出現前面提到的鏈表方式的問題，萬一某個指針損壞了，後面的數據也就會無法讀取了。

還有另外一種組合方式是 索引+索引 的方式，這種組合稱為多級索引塊，實現方式是通過一個索引塊來存放多個索引數據塊,一層套一層索引， 像極了俄羅斯套娃是吧๑乛◡乛๑ 

前面說到的文件的存儲是針對已經被佔用的數據塊組織和管理，接下來的問題是，如果我要保存一個數據塊, 我應該放在硬碟上的哪個位置呢?難道需要將所有的塊掃描一遍，找個空的地方隨便放嗎?

那這種方式效率就太低了，所以針對磁碟的空閑空間也是要引入管理的機制，接下來介紹幾種常見的方法:

●空閑表法

●空閑鏈表法

●點陣圖法

空閑表法

空閑表法就是為所有空閑空間建立一張表，表內容包括空閑區的第一個塊號和該空閑區的塊個數，注意，這個方式是連續分配的。如下圖:

當請求分配磁碟空間時，系統依次掃描空閑表裡的內容，直到找到一個合適的空閑區域為止。當用戶撤銷一個文件時，系統回收文件空間。這時，也需順序掃描空閑表,尋找一個空閑表條目並將釋放空間的第一個物理塊號及它佔用的塊數填到這個條目中。

這種方法僅當有少量的空閑區時才有較好的效果。因為，如果存儲空間中有著大量的小的空閑區,則空閑表變得很大,這樣查詢效率會很低。另外，這種分配技術適用於建立連續文件。

空閑鏈表法

我們也可以使用鏈表的方式來管理空閑空間，每一個空閑塊里有一個指針指向下一個空閑塊，這樣也能很方便的找到空閑塊並管理起來。如下圖：

當創建文件需要一塊或幾塊時，就從鏈頭上依次取下一塊或幾塊。反之，當回收空間時，把這些空閑塊依次接到鏈頭上。

這種技術只要在主存中保存一個指針, 令它指向第一個空閑塊。其特點是簡單,但不能隨機訪問，工作效率低，因為每當在鏈上增加或移動空閑塊時需要做很多1/0操作,同時數據塊的指針消耗了一定的存儲空間。

空閑表法和空閑鏈表法都不適合用於大型文件系統，因為這會使空閑表或空閑鏈表太大。

點陣圖法

點陣圖是利用二進制的一位來表示磁碟中一個盤塊的使用情況，磁碟上所有的盤塊都有一個二進制位與之對應。

當值為0時，表示對應的盤塊空閑，值為1時，表示對應的盤塊已分配。它形式如下:

在Linux文件系統就採用了點陣圖的方式來管理空閑空間,不僅用於數據空閑塊的管理,還用於inode空閑塊的管理，因為inode也是存儲在磁碟的，自然也要有對其管理。

前面提到Linux是用點陣圖的方式管理空閑空間，用戶在創建一個新文件時， Linux 內核會通過inode的點陣圖找到空閑可用的inode,並進行分配。要存儲數據時，會通過塊的點陣圖找到空閑的塊，並分配，但仔細計算一下還是有問題的。

數據塊的點陣圖是放在磁碟塊里的，假設是放在一個塊里,一個塊4K,每位表示一個數據塊,共可以表示4 * 1024 * 8 = 2^15個空閑塊,由於1個數據塊是4K大小，那麼最大可以表示的空間為2^15 * 4 * 1024 = 2^27個byte,也就是128M。

也就是說按照上面的結構，如果採用（一個塊的點陣圖+ 一系列的塊），外加一（個塊的inode的點陣圖+一系列的inode）的結構能表示的最大空間也就128M,

這太少了，現在很多文件都比這個大。

在Linux文件系統，把這個結構稱為一個 塊組 ，那麼有N多的塊組,就能夠表示N大的文件。

最終,整個文件系統格式就是下面這個樣子。

最前面的第一個塊是引導塊,在系統啟動時用於啟用引導，接著後面就是一個一個連續的塊組了,塊組的內容如下:

● 超級塊 ,包含的是文件系統的重要信息，比如inode總個數、塊總個數、每個塊組的inode個數、每個塊組的塊個數等等。

● 塊組描述符 ,包含文件系統中各個塊組的狀態,比如塊組中空閑塊和inode的數目等，每個塊組都包含了文件系統中「所有塊組的組描述符信息」。

● 數據點陣圖和inode點陣圖 ，用於表示對應的數據塊或inode是空閑的，還是被使用中。

● inode 列表 ，包含了塊組中所有的inode, inode 用於保存文件系統中與各個文件和目錄相關的所有元數據。

● 數據塊 ，包含文件的有用數據。

你可以會發現每個塊組里有很多重復的信息，比如 超級塊和塊組描述符表，這兩個都是全局信息，而且非常的重要 ，這么做是有兩個原因:

●如果系統崩潰破壞了超級塊或塊組描述符,有關文件系統結構和內容的所有信息都會丟失。如果有冗餘的副本,該信息是可能恢復的。

●通過使文件和管理數據盡可能接近，減少了磁頭尋道和旋轉,這可以提高文件系統的性能。

不過，Ext2 的後續版本採用了稀疏技術。該做法是，超級塊和塊組描述符表不再存儲到文件系統的每個塊組中,而是只寫入到塊組0、塊組1和其他ID可以表示為3、5、7的冪的塊組中。

在前面，我們知道了一個普通文件是如何存儲的，但還有一個特殊的文件,經常用到的目錄，它是如何保存的呢?

基於Linux 一切切皆文件的設計思想，目錄其實也是個文件,你甚至可以通過vim打開它，它也有inode, inode 裡面也是指向一些塊。

和普通文件不同的是， 普通文件的塊裡面保存的是文件數據，而目錄文件的塊裡面保存的是目錄裡面一項一項的文件信息 。

在目錄文件的塊中，最簡單的保存格式就是 列表 ，就是一項一項地將目錄下的文件信息(如文件名、文件inode.文件類型等)列在表裡。

列表中每一項就代表該目錄下的文件的文件名和對應的inode,通過這個inode,就可以找到真正的文件。

通常，第一項是「則」，表示當前目錄,第二項是.，表示上一級目錄, 接下來就是一項一項的文件名和inode。

如果一個目錄有超級多的文件,我們要想在這個目錄下找文件,按照列表一項一項的找,效率就不高了。

於是，保存目錄的格式改成 哈希表 ，對文件名進行哈希計算,把哈希值保存起來,如果我們要查找一個目錄下面的文件名，可以通過名稱取哈希。如果哈希能夠匹配上,就說明這個文件的信息在相應的塊裡面。

Linux系統的ext文件系統就是採用了哈希表，來保存目錄的內容,這種方法的優點是查找非常迅速，插入和刪除也較簡單,不過需要一些預備措施來避免哈希沖突。

目錄查詢是通過在磁碟上反復搜索完成，需要不斷地進行/0操作,開銷較大。所以,為了減少/0操作,把當前使用的文件目錄緩存在內存，以後要使用該文件時只要在內存中操作，從而降低了磁碟操作次數,提高了文件系統的訪問速度。

感謝您的閱讀，希望您能攝取到知識！加油！沖沖沖！（發現光，追隨光，成為光，散發光！）我是程序員耶耶！有緣再見。<－biubiu－⊂(`ω´∩)

5. 單極索引分配 在文件結尾添加一個磁碟塊 需要幾次磁碟操作

因為一個目錄文件最多可以由4個磁碟塊組成，讀目錄和下級目錄的時候，在最好的情況下，總能在第一個磁碟塊上就能找到所需的下級目錄信息，所以ADKQ四個目錄讀四次就可以了，此後是讀文件，理想情況下所需頁面可以通過前10個索引直接找到，此時只需再讀一次就能讀到所需頁了，結果最少共用5次

最壞情況下，每個目錄都存放在4個磁碟塊的最後一個上，因此每個目錄都得讀四次，一共4*4=16次，而找到文件後，所需頁面又得通過2級索引去找，這樣一來2級索引表讀一次，1級索引表又讀一次，頁面本身內容再讀一次，又需2+1=3次，所以最壞情況就是16+3=19次

6. 一個文件有100個磁碟塊，fcb在內存，採用鏈接分配在文件結尾處添加一個磁碟塊需要多少次磁碟操作

首先如果弄不明白，也不要苦惱，你可以找一下自己的朋友，或者是專業人士來為您回答這技術性問題，如果自己鑽牛角尖，那就是給自己找麻煩了

7. 操作系統(四)文件管理

文件—就是一組有意義的信息/數據集合

文件屬於抽象數據類型。為了恰當地定義文件，需要考慮有關文件的操作。操作系統提供系統調用，它對文件進行創建、寫、讀、重定位、搠除和截斷等操作。

所謂的「邏輯結構」，就是指在用戶看來，文件內部的數據應該是如何組織起來的。而「物理結構」指的是在操作系統看來，文件的數據是如何存放在外存中的。

無結構文件：文件內部的數據就是一系列二進制流或字元流組成。又稱「流式文件」

文件內部的數據其實就是一系列字元流，沒有明顯的結構特性。因此也不用探討無結構文件的「邏輯結構」問題。

有結構文件：由一組相似的記錄組成，又稱「記錄式文件」。每條記錄又若干個數據項組成。 [1] 一般來說，每條記錄有一個數據項可作為關鍵字。根據各條記錄的長度（佔用的存儲空間）是否相等，又可分為定長記錄和可變長記錄兩種。有結構文件按記錄的組織形式可以分為：

對於含有N條記錄的順序文件，查找某關鍵字值的記錄時，平均需要查找N/2次。在索引順序文件中，假設N條記錄分為√N組，索引表中有√N個表項，每組有√N條記錄，在查找某關鍵字值的記錄時，先順序查找索引表，需要查找√N /2次，然後在主文件中對應的組中順序查找，也需要查找√N/2次，因此共需查找√N/2+√N/2=√N次。顯然，索引順序文件提高了查找效率，若記錄數很多，則可採用兩級或多級索引

FCB的有序集合稱為「文件目錄」，一個FCB就是一個文件目錄項。FCB中包含了文件的基本信息（文件名、物理地址、邏輯結構、物理結構等），存取控制信息（是否可讀/可寫、禁止訪問的用戶名單等），使用信息（如文件的建立時間、修改時間等）。最重要，最基本的還是文件名、文件存放的物理地址。

對目錄的操作如下：

操作的時候，可以有以下幾種目錄結構：

早期操作系統並不支持多級目錄，整個系統中只建立一張目錄表，每個文件佔一個目錄項。

單級目錄實現了「按名存取」，但是不允許文件重名。在創建一個文件時，需要先檢查目錄表中有沒有重名文件，確定不重名後才能允許建立文件，並將新文件對應的目錄項插入目錄表中。顯然， 單級目錄結構不適用於多用戶操作系統。

早期的多用戶操作系統，採用兩級目錄結構。分為主文件目錄（MFD，Master File Directory）和用戶文件目錄（UFD，User Flie Directory）。

允許不同用戶的文件重名。文件名雖然相同，但是對應的其實是不同的文件。兩級目錄結構允許不同用戶的文件重名，也可以在目錄上實現實現訪問限制（檢查此時登錄的用戶名是否匹配）。但是兩級目錄結構依然缺乏靈活性，用戶不能對自己的文件進行分類

用戶（或用戶進程）要訪問某個文件時要用文件路徑名標識文件，文件路徑名是個字元串。各級目錄之間用「/」隔開。從根目錄出發的路徑稱為絕對路徑。

系統根據絕對路徑一層一層地找到下一級目錄。剛開始從外存讀入根目錄的目錄表；找到目錄的存放位置後，從外存讀入對應的目錄表；再找到目錄的存放位置，再從外存讀入對應目錄表；最後才找到文件的存放位置。整個過程需要3次讀磁碟I/O操作。

很多時候，用戶會連續訪問同一目錄內的多個文件，顯然，每次都從根目錄開始查找，是很低效的。因此可以設置一個「當前目錄」。此時已經打開了的目錄文件，也就是說，這張目錄表已調入內存，那麼可以把它設置為「當前目錄」。當用戶想要訪問某個文件時，可以使用從當前目錄出發的「相對路徑」

可見，引入「當前目錄」和「相對路徑」後，磁碟I/O的次數減少了。這就提升了訪問文件的效率。

樹形目錄結構可以很方便地對文件進行分類，層次結構清晰，也能夠更有效地進行文件的管理和保護。但是，樹形結構不便於實現文件的共享。為此，提出了「無環圖目錄結構」。

可以用不同的文件名指向同一個文件，甚至可以指向同一個目錄（共享同一目錄下的所有內容）。需要為每個共享結點設置一個共享計數器，用於記錄此時有多少個地方在共享該結點。用戶提出刪除結點的請求時，只是刪除該用戶的FCB、並使共享計數器減1，並不會直接刪除共享結點。只有共享計數器減為0時，才刪除結點。

其實在查找各級目錄的過程中只需要用到「文件名」這個信息，只有文件名匹配時，才需要讀出文件的其他信息。因此可以考慮讓目錄表「瘦身」來提升效率。

當找到文件名對應的目錄項時，才需要將索引結點調入內存，索引結點中記錄了文件的各種信息，包括文件在外存中的存放位置，根據「存放位置」即可找到文件。存放在外存中的索引結點稱為「磁碟索引結點」，當索引結點放入內存後稱為「內存索引結點」。相比之下內存索引結點中需要增加一些信息，比如：文件是否被修改、此時有幾個進程正在訪問該文件等。

為文件設置一個「口令」（如：abc112233），用戶請求訪問該文件時必須提供「口令」。

優點：保存口令的空間開銷不多，驗證口令的時間開銷也很小。

缺點：正確的「口令」存放在系統內部，不夠安全。

使用某個「密碼」對文件進行加密，在訪問文件時需要提供正確的「密碼」才能對文件進行正確的解密。 [3]

優點：保密性強，不需要在系統中存儲「密碼」

缺點：編碼/解碼，或者說加密/解密要花費一定時間。

在每個文件的FCB（或索引結點）中增加一個訪問控制列表（Access-Control List, ACL），該表中記錄了各個用戶可以對該文件執行哪些操作。

有的計算機可能會有很多個用戶，因此訪問控制列表可能會很大，可以用精簡的訪問列表解決這個問題

精簡的訪問列表：以「組」為單位，標記各「組」用戶可以對文件執行哪些操作。當某用戶想要訪問文件時，系統會檢查該用戶所屬的分組是否有相應的訪問許可權。

索引結點，是一種文件目錄瘦身策略。由於檢索文件時只需用到文件名，因此可以將除了文件名之外的其他信息放到索引結點中。這樣目錄項就只需要包含文件名、索引結點指針。

索引結點中設置一個鏈接計數變數count，用於表示鏈接到本索引結點上的用戶目錄項數。

當User3訪問「ccc」時，操作系統判斷文件「ccc」屬於Link類型文件，於是會根據其中記錄的路徑層層查找目錄，最終找到User1的目錄表中的「aaa」表項，於是就找到了文件1的索引結點。

類似於內存分頁，磁碟中的存儲單元也會被分為一個個「塊/磁碟塊/物理塊」。很多操作系統中，磁碟塊的大小與內存塊、頁面的大小相同

內存與磁碟之間的數據交換（即讀/寫操作、磁碟I/O）都是以「塊」為單位進行的。即每次讀入一塊，或每次寫出一塊

在內存管理中，進程的邏輯地址空間被分為一個一個頁面同樣的，在外存管理中，為了方便對文件數據的管理，文件的邏輯地址空間也被分為了一個一個的文件「塊」。於是文件的邏輯地址也可以表示為（邏輯塊號，塊內地址）的形式。用戶通過邏輯地址來操作自己的文件，操作系統要負責實現從邏輯地址到物理地址的映射

連續分配方式要求每個文件在磁碟上佔有一組連續的塊。用戶給出要訪問的邏輯塊號，操作系統找到該文件對應的目錄項（FCB）——可以直接算出邏輯塊號對應的物理塊號，物理塊號=起始塊號+邏輯塊號。還需要檢查用戶提供的邏輯塊號是否合法（邏輯塊號≥ 長度就不合法）因此 連續分配支持順序訪問和直接訪問 （即隨機訪問）

讀取某個磁碟塊時，需要移動磁頭。訪問的兩個磁碟塊相隔越遠，移動磁頭所需時間就越長。 連續分配的文件在順序讀/寫時速度最快，物理上採用連續分配的文件不方便拓展，且存儲空間利用率低，會產生難以利用的磁碟碎片可以用緊湊來處理碎片，但是需要耗費很大的時間代價。。

鏈接分配採取離散分配的方式，可以為文件分配離散的磁碟塊。分為隱式鏈接和顯式鏈接兩種。

用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）…從目錄項中找到起始塊號（即0號塊），將0號邏輯塊讀入內存，由此知道1號邏輯塊存放的物理塊號，於是讀入1號邏輯塊，再找到2號邏輯塊的存放位置……以此類推。因此，讀入i號邏輯塊，總共需要i+1次磁碟I/O。

採用鏈式分配（隱式鏈接）方式的文件，只支持順序訪問，不支持隨機訪問，查找效率低。另外，指向下一個盤塊的指針也需要耗費少量的存儲空間。但是，採用隱式鏈接的鏈接分配方式，很方便文件拓展。另外，所有的空閑磁碟塊都可以被利用，不會有碎片問題，外存利用率高。

把用於鏈接文件各物理塊的指針顯式地存放在一張表中。即文件分配表（FAT，File Allocation Table）

一個磁碟僅設置一張FAT 。開機時，將FAT讀入內存，並常駐內存。FAT的各個表項在物理上連續存儲，且每一個表項長度相同，因此「物理塊號」欄位可以是隱含的。

從目錄項中找到起始塊號，若i>0，則查詢內存中的文件分配表FAT，往後找到i號邏輯塊對應的物理塊號。 邏輯塊號轉換成物理塊號的過程不需要讀磁碟操作。

採用鏈式分配（顯式鏈接）方式的文件，支持順序訪問，也支持隨機訪問 （想訪問i號邏輯塊時，並不需要依次訪問之前的0 ~ i-1號邏輯塊）， 由於塊號轉換的過程不需要訪問磁碟，因此相比於隱式鏈接來說，訪問速度快很多。顯然，顯式鏈接也不會產生外部碎片，也可以很方便地對文件進行拓展。

索引分配允許文件離散地分配在各個磁碟塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊（索引表的功能類似於內存管理中的頁表——建立邏輯頁面到物理頁之間的映射關系）。索引表存放的磁碟塊稱為索引塊。文件數據存放的磁碟塊稱為數據塊。

在顯式鏈接的鏈式分配方式中，文件分配表FAT是一個磁碟對應一張。而索引分配方式中，索引表是一個文件對應一張。可以用固定的長度表示物理塊號 [4] ，因此，索引表中的「邏輯塊號」可以是隱含的。

用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）…從目錄項中可知索引表存放位置，將索引表從外存讀入內存，並查找索引表即可只i號邏輯塊在外存中的存放位置。

可見， 索引分配方式可以支持隨機訪問。文件拓展也很容易實現 （只需要給文件分配一個空閑塊，並增加一個索引表項即可）但是 索引表需要佔用一定的存儲空間

索引塊的大小是一個重要的問題，每個文件必須有一個索引塊，因此索引塊應盡可能小，但索引塊太小就無法支持大文件，可以採用以下機制：

空閑表法適用於「連續分配方式」。分配磁碟塊：與內存管理中的動態分區分配很類似，為一個文件分配連續的存儲空間。同樣可採用首次適應、最佳適應、最壞適應等演算法來決定要為文件分配哪個區間。回收磁碟塊：與內存管理中的動態分區分配很類似，當回收某個存儲區時需要有四種情況——①回收區的前後都沒有相鄰空閑區；②回收區的前後都是空閑區；③回收區前面是空閑區；④回收區後面是空閑區。總之，回收時需要注意表項的合並問題。

操作系統保存著鏈頭、鏈尾指針。如何分配：若某文件申請K個盤塊，則從鏈頭開始依次摘下K個盤塊分配，並修改空閑鏈的鏈頭指針。如何回收：回收的盤塊依次掛到鏈尾，並修改空閑鏈的鏈尾指針。適用於離散分配的物理結構。為文件分配多個盤塊時可能要重復多次操作

操作系統保存著鏈頭、鏈尾指針。如何分配：若某文件申請K個盤塊，則可以採用首次適應、最佳適應等演算法，從鏈頭開始檢索，按照演算法規則找到一個大小符合要求的空閑盤區，分配給文件。若沒有合適的連續空閑塊，也可以將不同盤區的盤塊同時分配給一個文件，注意分配後可能要修改相應的鏈指針、盤區大小等數據。如何回收：若回收區和某個空閑盤區相鄰，則需要將回收區合並到空閑盤區中。若回收區沒有和任何空閑區相鄰，將回收區作為單獨的一個空閑盤區掛到鏈尾。 離散分配、連續分配都適用。為一個文件分配多個盤塊時效率更高

位示圖：每個二進制位對應一個盤塊。在本例中，「0」代表盤塊空閑，「1」代表盤塊已分配。位示圖一般用連續的「字」來表示，如本例中一個字的字長是16位，字中的每一位對應一個盤塊。因此可以用（字型大小，位號）對應一個盤塊號。當然有的題目中也描述為（行號，列號）

盤塊號、字型大小、位號從0開始，若n表示字長，則

如何分配：若文件需要K個塊，①順序掃描位示圖，找到K個相鄰或不相鄰的「0」；②根據字型大小、位號算出對應的盤塊號，將相應盤塊分配給文件；③將相應位設置為「1」。如何回收：①根據回收的盤塊號計算出對應的字型大小、位號；②將相應二進制位設為「0」

空閑表法、空閑鏈表法不適用於大型文件系統，因為空閑表或空閑鏈表可能過大。UNIX系統中採用了成組鏈接法對磁碟空閑塊進行管理。文件卷的目錄區中專門用一個磁碟塊作為「超級塊」，當系統啟動時需要將超級塊讀入內存。並且要保證內存與外存中的「超級塊」數據一致。

進行Create系統調用時，需要提供的幾個主要參數：

操作系統在處理Create系統調用時，主要做了兩件事：

進行Delete系統調用時，需要提供的幾個主要參數：

操作系統在處理Delete系統調用時，主要做了幾件
事：

在很多操作系統中，在對文件進行操作之前，要求用戶先使用open系統調用「打開文件」，需要提供的幾個主要參數：

操作系統在處理open系統調用時，主要做了幾件事：

進程使用完文件後，要「關閉文件」

操作系統在處理Close系統調用時，主要做了幾件事：

進程使用read系統調用完成寫操作。需要指明是哪個文件（在支持「打開文件」操作的系統中，只需要提供文件在打開文件表中的索引號即可），還需要指明要讀入多少數據（如：讀入1KB）、指明讀入的數據要放在內存中的什麼位置。操作系統在處理read系統調用時，會從讀指針指向的外存中，將用戶指定大小的數據讀入用戶指定的內存區域中。

進程使用write系統調用完成寫操作，需要指明是哪個文件（在支持「打開文件」操作的系統中，只需要提供文件在打開文件表中的索引號即可），還需要指明要寫出多少數據（如：寫出1KB）、寫回外存的數據放在內存中的什麼位置操作系統在處理write系統調用時，會從用戶指定的內存區域中，將指定大小的數據寫回寫指針指向的外存。

尋找時間（尋道時間）T S ：在讀/寫數據前，將磁頭移動到指定磁軌所花的時間。

延遲時間T R ：通過旋轉磁碟，使磁頭定位到目標扇區所需要的時間。設磁碟轉速為r（單位：轉/秒，或轉/分），則平均所需的延遲時間

傳輸時間T t ：從磁碟讀出或向磁碟寫入數據所經歷的時間，假設磁碟轉速為r，此次讀/寫的位元組數為b，每個磁軌上的位元組數為N。則

總的平均存取時間Ta

延遲時間和傳輸時間都與磁碟轉速相關，且為線性相關。而轉速是硬體的固有屬性，因此操作系統也無法優化延遲時間和傳輸時間，但是操作系統的磁碟調度演算法會直接影響尋道時間

根據進程請求訪問磁碟的先後順序進行調度。

優點：公平；如果請求訪問的磁軌比較集中的話，演算法性能還算過的去
缺點：如果有大量進程競爭使用磁碟，請求訪問的磁軌很分散，則FCFS在性能上很差，尋道時間長。

SSTF演算法會優先處理的磁軌是與當前磁頭最近的磁軌。可以保證每次的尋道時間最短，但是並不能保證總的尋道時間最短。（其實就是貪心演算法的思想，只是選擇眼前最優，但是總體未必最優）

優點：性能較好，平均尋道時間短
缺點：可能產生「飢餓」現象

SSTF演算法會產生飢餓的原因在於：磁頭有可能在一個小區域內來回來去地移動。為了防止這個問題，可以規定，只有磁頭移動到最外側磁軌的時候才能往內移動，移動到最內側磁軌的時候才能往外移動。這就是掃描演算法（SCAN）的思想。由於磁頭移動的方式很像電梯，因此也叫電梯演算法。

優點：性能較好，平均尋道時間較短，不會產生飢餓現象
缺點：①只有到達最邊上的磁軌時才能改變磁頭移動方向②SCAN演算法對於各個位置磁軌的響應頻率不平均

掃描演算法（SCAN）中，只有到達最邊上的磁軌時才能改變磁頭移動方向，事實上，處理了184號磁軌的訪問請求之後就不需要再往右移動磁頭了。LOOK調度演算法就是為了解決這個問題，如果在磁頭移動方向上已經沒有別的請求，就可以立即改變磁頭移動方向。（邊移動邊觀察，因此叫LOOK）

優點：比起SCAN演算法來，不需要每次都移動到最外側或最內側才改變磁頭方向，使尋道時間進一步縮短

SCAN演算法對於各個位置磁軌的響應頻率不平均，而C-SCAN演算法就是為了解決這個問題。規定只有磁頭朝某個特定方向移動時才處理磁軌訪問請求，而返回時直接快速移動至起始端而不處理任何請求。

優點：比起SCAN來，對於各個位置磁軌的響應頻率很平均。
缺點：只有到達最邊上的磁軌時才能改變磁頭移動方向，另外，比起SCAN演算法來，平均尋道時間更長。

C-SCAN演算法的主要缺點是只有到達最邊上的磁軌時才能改變磁頭移動方向，並且磁頭返回時不一定需要返回到最邊緣的磁軌上。C-LOOK演算法就是為了解決這個問題。如果磁頭移動的方向上已經沒有磁軌訪問請求了，就可以立即讓磁頭返回，並且磁頭只需要返回到有磁軌訪問請求的位置即可。

優點：比起C-SCAN演算法來，不需要每次都移動到最外側或最內側才改變磁頭方向，使尋道時間進一步縮短

磁碟地址結構的設計：

Q：磁碟的物理地址是（柱面號，盤面號，扇區號）而不是（盤面號，柱面號，扇區號）

A：讀取地址連續的磁碟塊時，採用（柱面號，盤面號，扇區號）的地址結構可以減少磁頭移動消耗的時間

減少延遲時間的方法：

Step 1：進行低級格式化（物理格式化），將磁碟的各個磁軌劃分為扇區。一個扇區通常可分為頭、數據區域（如512B大小）、尾三個部分組成。管理扇區所需要的各種數據結構一般存放在頭、尾兩個部分，包括扇區校驗碼（如奇偶校驗、CRC循環冗餘校驗碼等，校驗碼用於校驗扇區中的數據是否發生錯誤）

Step 2：將磁碟分區，每個分區由若干柱面組成（即分為我們熟悉的C盤、D盤、E盤）

Step 3：進行邏輯格式化，創建文件系統。包括創建文件系統的根目錄、初始化存儲空間管理所用的數據結構（如位示圖、空閑分區表）

計算機開機時需要進行一系列初始化的工作，這些初始化工作是通過執行初始化程序（自舉程序）完成的

初始化程序可以放在ROM（只讀存儲器）中。ROM中的數據在出廠時就寫入了，並且以後不能再修改。ROM中只存放很小的「自舉裝入程序」，完整的自舉程序放在磁碟的啟動塊（即引導塊/啟動分區）上，啟動塊位於磁碟的固定位置，開機時計算機先運行「自舉裝入程序」，通過執行該程序就可找到引導塊，並將完整的「自舉程序」讀入內存，完成初始化。擁有啟動分區的磁碟稱為啟動磁碟或系統磁碟（C:盤）

對於簡單的磁碟，可以在邏輯格式化時（建立文件系統時）對整個磁碟進行壞塊檢查，標明哪些扇區是壞扇區，比如：在FAT表上標明。（在這種方式中，壞塊對操作系統不透明）。

對於復雜的磁碟，磁碟控制器（磁碟設備內部的一個硬體部件）會維護一個壞塊鏈表。在磁碟出廠前進行低級格式化（物理格式化）時就將壞塊鏈進行初始化。會保留一些「備用扇區」，用於替換壞塊。這種方案稱為扇區備用。且這種處理方式中，壞塊對操作系統透明

8. 考慮一個由4個物理塊組成的文件，假定採用索引結構，且 文件控制塊已經在主存。對於採用連續結構、鏈接

連續：201，101，1，0，98，0 鏈接：1，52，102，1，52，100 索引：1，1，1，0，0，0

9. 26 文件外存分配方式

目前，常用的外存分配方法有 連續分配 、 鏈接分配 和 索引分配 三種。採用不同的分配方式時，將形成不同的文件物理結構。

連續分配方式對應順序式文件結構，鏈接分配方式形成鏈接式文件結構，索引分配方式將形成索引式文件結構。有的系統（如DOS操作系統）對三種方法都支持，但是更普遍的是 一個系統只提供一種方法的支持 。

連續分配方法要求每個文件在磁碟上佔有一組連續的塊，如圖所示。這樣所形成的文件結構稱為 順序文件結構 ，此時的物理文件稱為 順序文件 。這種分配方式保證了邏輯文件中的的記錄順序與存儲器中的文件佔用盤塊的順序是 一致的 。

優點是 實現簡單、存取速度快 ，支持順序訪問和直接訪問，作業訪問磁碟時需要的尋道數和尋道時間最短。

缺點在於，文件長度 不宜動態增加 ，因為一個文件末尾後的盤塊可能已經分配給其他文件，一旦需要增加， 就需要大量移動盤塊。在外存上使用緊湊技術所花費的時間遠比內存緊湊一次所花費的時間多得多。

此外，反復增刪文件後會產生 外部碎片 （與內存管理分配方式中的碎 片相似)，並且很難確定一個文件需要的空間大小，因而只適用於長度固定的文件。

鏈接分配是釆取 離散分配 的方式，消除了外部碎片，故而顯著地 提高了磁碟空間的利用率 ；又因為是根據文件的當前需求，為它分配必需的盤塊，當文件動態增長時，可以動態地再為它分配盤塊，故而 無需事先知道文件的大小 。此外，對文件的 增、刪、改也非常方便 。

鏈接分配又可以分為隱式鏈接和顯式鏈接兩種形式。

文件，目錄中每個目錄項都包括 指向鏈接文件第一盤塊和最後一個盤塊的指針 。磁碟塊分布在磁碟的任何地方，除最後一個盤塊外，每一個盤塊都有指向下一個盤塊的指針，這些指針對用戶是透明的。

為了提高檢索速度和減小指針所佔存儲空間，可以將幾個盤塊組成一個簇（cluster），雖然成倍 減少了訪問時間，以及指針存儲空間，但卻增大了內部碎片，改進很有限 。

顯示鏈接把用於鏈接文件各物理塊的指針，顯示地存放在內存的一張鏈接表中。該表在整個磁碟僅設置一張。

表的序號從0開始，直至N-1，N為盤塊總數，在每個表項中存放鏈接指針，即下一個盤塊號。

在該表中，凡是屬於某一文件的第一個盤塊號（鏈首指針所對應的盤塊號）均作為文件地址被填入相應的文件的FCB的物理地址欄位中。

由於查找記錄的過程是 在內存中進行的，因而提高了檢索速度，減少了訪問磁碟的次數 。由於分配給文件的所有盤塊號都在該表中，故把該表稱為文件分配表FAT（File Allocation Table）。

在打開某個文件時，只需把該文件佔用的盤塊號的編號調入內存即可， 無需把整個FAT調入內存 。為此，將每個文件所對應的盤塊號集中地放在一起，索引分配方式就是基於此想法所形成的一種分配方式。

其為每個文件分配一個索引表，再把分配給該文件的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個含有許多磁碟塊號的數組。在建立一個文件時，只需要在為之建立的目錄項中填上指向該索引塊的指針。

當文件太大時，索引塊太多，單級索引是低效的 。此時，為這些索引塊再建立一級索引，稱為第一級索引，還可再建立索引，稱為第二級索引等等。稱為多級索引分配。

在二級索引分配方式下，若每個盤塊的大小為1KB，每個盤塊號佔4個位元組，在一個索引塊可以存放256個盤塊號。則，在兩級索引時，最多可以包括存放文件的盤塊號總數為64K(256 * 256)個盤塊號，所允許文件最大長度為64MB。

若盤塊號為4KB，則一級索引的最大文件大小為4MB，二級索引的最大文件大小為4GB。

將 多種索引分配方式相結合 而形成的一種分配方式，如直接地址，一次間接地址，多次間接地址。

Unix SystemV的分配採用了三級索引分配方式。共設置了13個索引地址項。前10個：iaddr(0)~iaddr(9)為直接地址項，iaddr(10)為一次間接地址項，iaddr(11)為二次間接地址項，iaddr(12)為三次間接地址項。

10. 某系統磁碟塊大小為512b，1560位元組處的信息要進行多少次的i/o

2.什麼是批處理、分時操作系統、實時操作系統?各有什麼特徵? 3.多道程序設計與多重處理有何區別? 4.討論操作系統可以從哪些角度出發，如何把它們統一起來? 5.現代操作系統對運行環境有何要求? 3 2 1.有人說，一個進程是由偽處理機執行的一個程序，這話對嗎?為什麼? 2.比較進程與程序的聯系和區別。 3.我們說程序的並發執行將導致最終結果失去封閉性。這話對所有的程序都成立嗎?試舉例說明。 4.什麼是臨界區?舉一臨界區的例子。 5.什麼是線程?線程和進程有何區別? 6.某高校計算機系開設網路課並安排上機實習，假設機房共有2m台機器，有2n 名學生選該課，規定: ① 每2 個學生組成一組，各佔一台機器，協同完成上機實習; ② 只有一組2 個學生到齊，並且此時機房有空閑機器時，該組學生才能進入機房; ③ 上機實習由一名教師檢查，檢查完畢，一組學生同時離開機房。 試用P、V操作模擬上機實習過程。 7.今有三個並發進程R，M，P，它們共享了一個可循環使用的緩沖區B，緩沖區B 共有N個單元。進程R 負責從輸入設備讀信息，每讀一個字元後，把它存放在緩沖區B 的一個單元中;進程M負責處理讀入的字元，若發現讀入的字元中有空格符，則把它改成「，」;進程P負責把處理後的字元取出並列印輸出。當緩沖區單元中的字元被進程P 取出後，則又可用來存放下一次讀入的字元。請用PV操作為同步機制寫出它們能正確並發執行的程序。 8.寫出Reader-Writer 問題的演算法，避免由於不斷有Reader 出現，而使得Writer 無限期等待。 9. 設計C 程序(可以嵌入匯編語言)，以忙等待方式實現信號量的P、V操作。 10. 設計C 程序，實現生產者-消費者問題。 說明:8-10 為課外實踐練習。 4 3 1.進程調度的功能有哪些? 2.進程調度的時機有哪幾種? 3.為什麼說在進程上下文切換的過程中，上下文切換程序不能破壞「老」進程的上下文結構? 4.比較常用的幾種調度演算法。 5.假設有四道作業，它們的進入時刻與執行時間如下所示: 作業號 進入時刻(時) 執行時間(小時) 1 10.00 0.4 2 10.10 1.0 3 10.20 0.6 4 10.30 0.2 在單道程序環境下，分別採用先來先服務和最短作業優先調度演算法，試說明它們的調度順序及平均周轉時間。 5 4 1.什麼是虛擬存儲器?其特點是什麼? 2.動態分區管理的常用內存分配演算法有哪幾種?比較它們各自的優缺點。 3.什麼是頁式管理?靜態頁式管理可以實現虛存嗎? 4.請求頁式管理有哪幾種常用的頁置換演算法?比較它們的優缺點。 5.什麼是段式管理?它與頁式管理有何區別? 6.在一個請求分頁系統中，採用LRU 頁面置換演算法時，假如一個進程的頁面訪問順序為4， 3，2，1，4，3，5，4，3，2，1，5，當分配給該進程的物理塊數M 分別為3 和4 時，請計算訪問過程中發生的缺頁次數和缺頁率，比較所得結果。 7.設一個計算機有4 個頁框，裝入時間、最近訪問時間和每頁的訪問位、修改位如下所示(時間以時鍾周期為單位): 頁 裝入時間 最近訪問時間 訪問位A 修改位M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1 1)NRU 將置換哪一頁? 2)LRU 將置換哪一頁? 3)FIFO 將置換哪一頁? 8.已知如下段表: 段號 基址 長度 合法(0)/非法(1) 0 219 600 0 1 2300 14 0 2 90 100 1 3 1327 580 0 4 1952 96 0 在分段存儲管理下系統運行時，下列邏輯地址的物理地址是什麼? (1)0，430 (2)1，10 (3)1，11 (4)2，500 (5)3，400 (6)4，112 6 5 1.什麼是系統調用?系統調用與一般的過程調用有何區別? 2.在Linux 操作系統中，引起進程調度的時機有哪些? 3.簡述 shell 命令在Linux 中的實現過程。 4.在Linux 系統中，進程在什麼時候處理它們接收到的軟中斷信號?進程接收到軟中斷信號後放在什麼地方? 5.Windows 2000/xp 在哪些情況下進行線程優先順序提升? 6.試描述使用Win32 API 實現線程同步的一般方法。 7 6 1.什麼是文件、文件系統?文件系統有哪些功能? 2.文件的物理結構有哪幾種?為什麼說串聯文件結構不適合隨機存取? 3.什麼是文件目錄?文件目錄中包含哪些信息? 4.在實現文件系時，為加快文件目錄的檢索速度，可利用「文件控制塊分解法」。假設目錄文件存放在磁碟上，每個盤塊512 位元組。文件控制塊佔64 位元組。其中文件名佔8 位元組。通常將文件控制塊分解成兩部分，第一部分佔10 位元組(包括文件名和文件內部號)，第二部分佔 56 位元組(包括文件內部號和文件其他描述信息)。 ① 假設某一目錄文件共有254 個文件控制塊，試分別給出採用分解法前和分解法後，查找該目錄文件的某一個文件控制塊的平均訪問磁碟次數。 ② 一般地，若目錄文件分解前佔用 n 個盤塊，分解後改用 m 個盤塊存放文件名和文件內部號部分，請組出訪問磁碟次數減少的條件。 5.在創建一個文件時，可能發生哪幾種情況?應如何處理? 6.文件存取控制方式有哪幾種?比較它們的優缺點。 7.文件系統採用多級索引結構搜索文件內容。設塊長為512 位元組，每個塊號長3 位元組，如果不考慮邏輯塊號在物理塊中所佔的位置，分別求二級索引和三級索引時可定址的文件最大長度。 8 7 1.設備管理的目標和功能是什麼? 2.什麼是I/O 緩沖?為什麼要引入I/O 緩沖? 3.設備驅動程序是什麼?為什麼要有設備驅動程序?用戶進程怎樣使用設備驅動程序? 4.為什麼在單緩沖與雙緩沖情況下，系統對一塊數據的處理時間分別為 max(C,T)+M 和 max(C,T)?其中，C:CPU 的計算時間，T:數據從I/O 控制器到緩沖區的傳輸時間，M:數據從緩沖區到用戶工作區的傳輸時間。 5.為什麼要引入設備獨立性?如何實現設備獨立性? 6.某移動臂磁碟的柱面由外向里順序編號，假定當前磁頭停在100 號柱面且移動臂方向是向里的，現有如下表1 所示的請求序列在等待訪問磁碟: 表1 訪問磁碟請求序列 請求次序 1 2 3 4 5 6 7 8 9 10 柱面號 190 10 160 80 90 125 30 20 140 25 回答下面的問題: ① 寫出分別採用「最短查找時間優先演算法」和「電梯調度演算法」時，實際處理上述請求的次序。 ② 針對本題比較上述兩種演算法，就移動臂所花的時間(忽略移動臂改向時間)而言，哪種演算法更合適?簡要說明之。 9 8 1.ext2 文件系統為什麼有磁碟I 節點和內存I 節點? 2.在Linux 系統中，用於打開文件的系統調用open 的格式為 fd = open( pathname, flags) 其中，pathname 為欲打開的文件路徑名，flags 指示打開方式(讀、寫)，open 的返回值為文件描述符。 1)給出open 的實現演算法。 2)說明用戶文件描述符表、系統打開文件表與I 節點表的作用及三者之間的關系。 3.在Linux 系統中，文件共享有哪兩種方式? 4.說明Linux 虛擬文件系統VFS 的工作原理。 5.說明Linux 虛擬文件系統VFS 中查找文件的過程。 6.什麼是塊設備驅動程序? 7.分別給出文件的磁碟索引節點與內存索引節點的引用數可能大於1的情況。 10 9 1.什麼是死鎖?給出產生死鎖的個必要條件。 2.有三個進程P1、P2 和P3 並發工作。進程P1 需用資源S3 和S1;進程P2 需用資源S1 和 S2;進程P3 需用資源S2 和S3。回答: (1) 若對資源分配不加限制，會發生什麼情況?為什麼? (2) 為保證進程正確工作，應採用怎樣的資源分配策略?為什麼? 3.某系統有R1，R2，R3 三種資源，在T0 時刻P1，P2，P3，P4 四個進程對資源的佔用和需求情況如表1 所示，此刻系統的可用資源向量為(2, 1, 2)，問題: ① 將系統中各種資源總數和此刻各進程對各資源的需求數目用向量或矩陣表示出來; ② 如果此時P1 和P2 均發出資源請求向量Request(1, 0, 1)，為了保持系統安全性，應該如何分配資源給這兩個進程?說明你所採用策略的原因; ③ 如果②中兩個請求立刻得到滿足後，系統此刻是否處於死鎖狀態? 表1 T0 時刻P1，P2，P3，P4 四個進程對資源的佔用和需求情況表 Maximum demand Current allocation R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 4.在解決死鎖問題的幾種方法中，哪一種方法最容易實現?哪一種方法使資源利用率最高?