六、文件管理

1、文件

?????? 文件系統(tǒng)的管理功能是將其管理的程序和數(shù)據(jù)通過組織為一系列文件的方式實現(xiàn)的。而文件是指具有文件名的，在邏輯上具有完整意義的一組相關(guān)元素的集合。

■? 數(shù)據(jù)項、記錄和文件

????? 在文件系統(tǒng)中，數(shù)據(jù)項是最低級的數(shù)據(jù)組織形式，可把它分成以下兩種類型：基本數(shù)據(jù)項、組合數(shù)據(jù)項。記錄是一組相關(guān)數(shù)據(jù)項的集合，用于描述一個對象在某方面的屬性。一個記錄應(yīng)包含哪些數(shù)據(jù)項，取決于需要描述對象的哪個方面。由于對象所處的環(huán)境不同可把他作為不同的對象。 文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

■??文件命名：由文件名和擴展名構(gòu)成

文件名MS-DOS由1-8個字符組成；WINDOWS由1-255個字符組成（支持長文件名），擴展名一般由1-3個字符組成。

■??文件類型

1) 按用途分類：系統(tǒng)文件、用戶文件、庫文件

2) 按文件中數(shù)據(jù)的形式分類：源文件、目標(biāo)文件、可執(zhí)行文件

3) 按存取控制屬性分類：只執(zhí)行文件、只讀文件、讀寫文件

4) 按組織形式和處理方式分類：普通文件、目錄文件、特殊文件

■??文件屬性

除了文件內(nèi)容外還包含文件屬性信息：名稱、類型、位置、大小、保護、時間日期等

2、文件操作：

■?? 存取方法：順序存取方法、直接存取方法（又稱隨機存取方法）、索引存取方法

■?? 基本操作：創(chuàng)建文件、刪除文件、讀文件、寫文件。

■?? 打開和關(guān)閉操作

■?? 其它文件操作

3、文件結(jié)構(gòu)

■??文件的邏輯結(jié)構(gòu)：無結(jié)構(gòu)的流式文件、有結(jié)構(gòu)的記錄式文件

■??? 選取文件邏輯結(jié)構(gòu)遵循的基本要求：

（1）有助于提高對文件的檢索速度

（2）方便對文件進行修改

（3）盡量減少文件占用的存儲空間，不要求大片的連續(xù)存儲空間

■?? 根據(jù)文件的組織方式，可把有結(jié)構(gòu)文件分為三類：順序文件、索引文件、索引順序文件。

■??順序文件

????? 順序文件的最佳應(yīng)用場合是在對文件中的記錄進行批量存取時(即每次要讀或?qū)懸淮笈涗?。所有邏輯文件中順序文件的存取效率是最高的。此外，對于順序存儲設(shè)備(如磁帶)，也只有順序文件才能被存儲并能有效地工作。

■??? 索引文件

（1）按關(guān)鍵字建立索引

（2）具有多個索引表的索引文件：為每種可能成為檢索條件的域(屬性或關(guān)鍵字)都配置一張索引表。

■?? 索引順序文件

????? 索引順序文件是對順序文件的一種改進，它基本上克服了變長記錄的順序文件不能隨機訪問，以及不便于記錄的刪除和插入的缺點。但它仍保留了順序文件的關(guān)鍵特征，即記錄是按關(guān)鍵字的順序組織起來的。它又增加了兩個新特征：一個是引入了文件索引表，通過該表可以實現(xiàn)對索引順序文件的隨機訪問；另一個是增加了溢出(overflow)文件，用它來記錄新增加的、刪除的和修改的記錄。

（1）一級索引順序文件
　　最簡單的索引順序文件只使用了一級索引。

檢索時間：

????? 對于一個含有N個記錄的順序文件，查找某個關(guān)鍵字值的記錄時平均需要查找N/2次。對于具有一級索引順序文件，為能查找某個關(guān)鍵字值的記錄時平均需要查找次。

（2）兩級索引順序文件：對于一個非常大的文件，為找到一個記錄而須查找的記錄數(shù)目仍然很多，為了進一步提高檢索效率，可以為順序文件建立多級索引，即為索引文件再建立一張索引表，從而形成兩級索引表。

■??直接文件：關(guān)鍵字決定了記錄的物理地址。哈希(Hash)文件是目前應(yīng)用最為廣泛的一種直接文件。

4、文件目錄

■?? 功能：實現(xiàn)按名存取、提高檢索速度、文件共享、允許文件重名。

■?? 操作：創(chuàng)建目錄、刪除目錄、改變目錄、移動目錄、鏈接(Link)操作、查找

■??文件目錄內(nèi)容：

（1）文件控制塊FCB(File Control Block)

????? 文件目錄在文件名與文件自身之間一種映射。為了能對文件進行正確的存取，必須提供用于描述和控制文件信息的數(shù)據(jù)結(jié)構(gòu)。

MS-DOS的文件控制塊

　（2）索引結(jié)點：查找目錄的過程中，須將存放目錄文件的第一個盤塊中的目錄調(diào)入內(nèi)存，然后將用戶所給定的文件名，與目錄項中的文件名逐一比較。因此，有的系統(tǒng)（UNIX，Linux）采用將文件名和文件描述信息分開，將文件描述信息單獨形成一個稱為索引節(jié)點的數(shù)據(jù)結(jié)構(gòu)。

UNIX的文件目錄

■??文件目錄結(jié)構(gòu)

（1）單級文件目錄
　　這是最簡單的文件目錄。在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項，目錄項中含文件名、文件擴展名、文件長度、文件類型、文件物理地址以及其它文件屬性。此外，為表明每個目錄項是否空閑，又設(shè)置了一個狀態(tài)位。

單級文件目錄

單級目錄結(jié)構(gòu)的特點：

優(yōu)點：結(jié)構(gòu)簡單，使用方便，易于實現(xiàn)。

缺點：查找速度慢、不允許重名、不便共享、不適合多用戶操作系統(tǒng)

（2）兩級文件目錄

?????? 克服單級文件目錄所存在的缺點，可以為每一個用戶再建立一個單獨的用戶文件目錄UFD(User File Directory)。這些文件目錄具有相似的結(jié)構(gòu)，它由用戶所有文件的文件控制塊組成。此外，在系統(tǒng)中再建立一個主文件目錄MFD(Master File Directory)；在主文件目錄中，每個用戶目錄文件都占有一個目錄項，其目錄項中包括用戶名和指向該用戶目錄文件的指針。

（3）樹形多級結(jié)構(gòu)目錄(Tree-Structured Directory)

?????? 在現(xiàn)代OS中，最通用且實用的文件目錄無疑是樹形結(jié)構(gòu)目錄。它可以明顯地提高對目錄的檢索速度和文件系統(tǒng)的性能。主目錄在這里被稱為根目錄，在每個文件目錄中，只能有一個根目錄，每個文件和每個目錄都只能有一個父目錄。把數(shù)據(jù)文件稱為樹葉，其它的目錄均作為樹的結(jié)點，或稱為子目錄。

（4）無環(huán)圖目錄結(jié)構(gòu)

?????? 嚴格的樹形結(jié)構(gòu)目錄中，每個文件只允許有一個父目錄，父目錄可以有效地擁有該文件，其它用戶要想訪問它，必須經(jīng)過其屬主目錄來訪問該文件。這就是說，對文件的共享是不對稱的，或者說，樹形結(jié)構(gòu)目錄是不適合文件共享的。

■??文件路徑

（1）絕對路徑

?????? 在樹形結(jié)構(gòu)目錄中，從根目錄到任何數(shù)據(jù)文件都只有一條唯一的通路。在該路徑上，從樹的根(即主目錄)開始，把全部目錄文件名與數(shù)據(jù)文件名依次地用“/”連接起來，即構(gòu)成該數(shù)據(jù)文件唯一的路徑名。

（2）相對路徑

?????? 當(dāng)進程訪問局限于某個子目錄時，可以設(shè)置一個“當(dāng)前目錄”，又稱為“工作目錄”。從當(dāng)前目錄開始，到達要訪問的最終文件所進過的路徑稱為相對路徑。

5、文件共享與保護

■??利用符號鏈接(Symbolic Linking)實現(xiàn)共享

優(yōu)點：在利用符號鏈方式實現(xiàn)文件共享時，只是文件主才擁有指向其索引結(jié)點的指針；而共享該文件的其他用戶則只有該文件的路徑名，并不擁有指向其索引結(jié)點的指針。這樣就不會發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。當(dāng)文件的擁有者把一個共享文件刪除后，如果其他用戶又試圖通過符號鏈去訪問一個已被刪除的共享文件，則會因系統(tǒng)找不到該文件而使訪問失敗，于是再將符號鏈刪除，此時不會產(chǎn)生任何影響。

缺點：每次訪問共享文件時，都可能要多次地讀盤。這使每次訪問文件的開銷甚大，且增加了啟動磁盤的頻率。此外，要為每個共享用戶建立一條符號鏈，而由于鏈本身實際上是一個文件，盡管該文件非常簡單，卻仍要為它配置一個索引結(jié)點，這也要耗費一定的磁盤空間。

■??利用索引結(jié)點的共享方式

■??文件保護：口令保護、加密保護、訪問控制

（1）訪問類型：讀、寫、執(zhí)行、添加、刪除、列表、重命名、復(fù)制

（2）訪問控制：用戶身份認證，如WINDOWS，數(shù)據(jù)庫等身份認證。

（3）口令：用戶在建立一個文件時提供一個口令，系統(tǒng)為其建立FCB時附上相應(yīng)的口令，同時告訴共享該文件的其他用戶。

（4）密碼：用戶對文件內(nèi)容進行加密，文件被訪問時需要使用密鑰

6、文件存儲空間管理

■?? 空閑表法

????? 空閑表法屬于連續(xù)分配方式，它與內(nèi)存的動態(tài)分配方式雷同，它為每個文件分配一塊連續(xù)的存儲空間。即系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個空閑表項，其中包括表項序號、該空閑區(qū)的第一個盤塊號、該區(qū)的空閑盤塊數(shù)等信息。再將所有空閑區(qū)按其起始盤塊號遞增的次序排列，形成空閑盤塊表。

存儲空間的分配與回收：

????? 空閑盤區(qū)的分配與內(nèi)存的分區(qū)(動態(tài))分配類似，同樣是采用首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法等，它們對存儲空間的利用率大體相當(dāng)。

■??空閑鏈表法

1) 空閑盤塊鏈：磁盤上的所有空閑空間以盤塊為單位拉成一條鏈，其中的每一個盤塊都有指向后繼盤塊的指針。缺點：空閑盤塊鏈可能很長，影響效率。

2) 空閑盤區(qū)鏈：將磁盤上的所有空閑盤區(qū)(每個盤區(qū)可包含若干個盤塊)拉成一條鏈。在每個盤區(qū)上除含有用于指示下一個空閑盤區(qū)的指針外，還應(yīng)有能指明本盤區(qū)大小(盤塊數(shù))的信息。缺點：分配與回收的過程較復(fù)雜。

■?? 位示圖法

????? 利用二進制的一位來表示磁盤中一個盤塊的使用情況。當(dāng)其值為“0”時，表示對應(yīng)的盤塊空閑；為“1”時，表示已分配。有的系統(tǒng)把“0”作為盤塊已分配的標(biāo)志，把“1”作為空閑標(biāo)志。(它們在本質(zhì)上是相同的，都是用一位的兩種狀態(tài)來標(biāo)志空閑和已分配兩種情況。)磁盤上的所有盤塊都有一個二進制位與之對應(yīng)，這樣，由所有盤塊所對應(yīng)的位構(gòu)成一個集合，稱為位示圖。

????? 盤塊分配時可分三步進行：

(1) 順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑時)。

(2) 將所找到的一個或一組二進制位轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進制位位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算：

b?=?n(i?-?1)?+?j

式中，n代表每行的位數(shù)。

(3) 修改位示圖，令map[i, j]?=?1。

　盤塊的回收分兩步：

(1) 將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為：

i?=?(b?-?1)DIV? n?+?1

j?=?(b?-?1)MOD ?n?+?1

(2) 修改位示圖。令map[i, j] =?0。

■??鏈接索引表法

又稱成組鏈接法。使用若干個空閑盤塊作為索引表塊，來指出存儲空間中所有的空閑塊。

7、文件分配

文件分配是指如何分配空白塊來存放文件中的內(nèi)容，也稱為文件的物理結(jié)構(gòu)。文件的物理結(jié)構(gòu)直接與外存的組織方式有關(guān)。對于不同的外存組織方式，將形成不同的文件物理結(jié)構(gòu)。目前常用的外存組織方式有： (1) 連續(xù)組織方式。 (2) 鏈接組織方式。 (3) 索引組織方式。

■??連續(xù)分配：又稱連續(xù)組織方式，要求為每一個文件分配一組相鄰接的盤塊。采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時的物理文件稱為順序文件。

優(yōu)點：順序訪問容易、順序訪問速度快

缺點：要為文件分配連續(xù)存儲空間、必須事先知道文件長度

不能靈活刪除和插入記錄、容易形成磁盤碎片

■??鏈接分配：采用鏈接分配方式時，可為文件分配多個不連續(xù)的盤塊，再通過每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，由此所形成的物理文件稱為鏈接文件。

(1) 消除了磁盤的外部碎片，提高了外存的利用率。

(2) 對插入、刪除和修改記錄都非常容易。

(3) 能適應(yīng)文件的動態(tài)增長，無需事先知道文件的大小。

1. 隱式鏈接：在采用隱式鏈接組織方式時，在文件目錄的每個目錄項中，都須含有指向鏈接文件第一個盤塊的指針和文件的長度。

2. 顯式鏈接

?????? 把鏈接文件各物理塊的指針顯式地存放在內(nèi)存的一張鏈接表中。該表在整個磁盤中僅設(shè)置一張（FAT表）。

隱式鏈接和顯式鏈接的比較：

隱式鏈接指針在磁盤上，每次都要讀取磁盤。

顯式鏈接將磁盤上文件的鏈式結(jié)構(gòu)用內(nèi)存的一張FAT表去描述，查找時可以在內(nèi)存中進行，定位后再讀磁盤。速度比隱式快很多。

■??索引鏈接分配

（1）一級索引鏈接分配
　　鏈接組織方式雖然解決了連續(xù)組織方式所存在的問題(即不便于隨機訪問)，但又出現(xiàn)了另外兩個問題，即：① 不能支持高效的直接存取，要對一個較大的文件進行存取，須在FAT中順序地查找許多盤塊號；② FAT需占用較大的內(nèi)存空間，由于一個文件所占用盤塊的盤塊號是隨機地分布在FAT中的，因而只有將整個FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個文件的所有盤塊號。

（2）多級索引鏈接分配

????? 在為一個大文件分配磁盤空間時，如果所分配出去的盤塊的盤塊號已經(jīng)裝滿一個索引塊時，OS須再為該文件分配另一個索引塊，用于將以后繼續(xù)為之分配的盤塊號記錄于其中。依此類推，再通過鏈指針將各索引塊按序鏈接起來。

8、Windows文件管理

■??FAT12

1) 早期的FAT12文件系統(tǒng)

????? FAT12是以盤塊為基本分配單位的。由于FAT是文件系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)，為了安全起見，在每個分區(qū)中都配有兩張相同的文件分配表FAT1和FAT2。在FAT的每個表項中存放下一個盤塊號，它實際上是用于盤塊之間的鏈接的指針，通過它可以將一個文件的所有的盤塊鏈接起來，而將文件的第一個盤塊號放在自己的FCB中。

MS-DOS的文件物理結(jié)構(gòu)

2) 以簇為單位的FAT12文件系統(tǒng)

?????? 如果把每個盤塊(扇區(qū))的容量增大n倍，則磁盤的最大容量便可增加n倍。但要增加盤塊的容量是不方便和不靈活的。為此，引入了簇(cluster)的概念。

■??FAT16??

????? FAT12對磁盤容量限制的原因在于， FAT12表中的表項有限制，亦即最多只允許4096個。這樣，隨著磁盤容量的增加，必定會引起簇的大小和簇內(nèi)碎片也隨之增加。

■?? FAT32

????? 由于FAT16表長只有65?535項，隨著磁盤容量的增加，簇的大小也必然會隨之增加，為了減少簇內(nèi)零，也就應(yīng)當(dāng)增加FAT表的長度，為此需要再增加FAT表的寬度，這樣也就由FAT16演變?yōu)镕AT32。

FAT中簇的大小與最大分區(qū)的對應(yīng)關(guān)系

■??NTFS

????? NTFS(New Technology File System)是一個專門為Windows NT開發(fā)的、全新的文件系統(tǒng)，并適用于Windows 2000/XP及后續(xù)的Windows OS。

（1）磁盤組織：

????? NTFS是以簇作為磁盤空間分配和回收的基本單位的。一個文件占用若干個簇，一個簇只屬于一個文件。這樣，在為文件分配磁盤空間時，就無須知道盤塊的大小，只要根據(jù)不同的磁盤容量，選擇相應(yīng)大小的簇，即使NTFS具有了與磁盤物理塊大小無關(guān)的獨立性。

（2）文件的組織：

????? 在NTFS中，以卷為單位，將一個卷中的所有文件信息、目錄信息以及可用的未分配空間信息，都以文件記錄的方式記錄在一張主控文件表MFT(Master File Table)中，該表是NTFS卷結(jié)構(gòu)的中心，從邏輯上講，卷中的每個文件作為一條記錄，在MFT表中占有一行，其中還包括MFT自己的這一行。每行大小固定為1?KB，每行稱為該行所對應(yīng)文件的元數(shù)據(jù)(metadata)，也稱為文件控制字。