操作系統(tǒng),原理,徐宗元OS-第五章課件

第五章()文件系統(tǒng)引言操作系統(tǒng)對系統(tǒng)的軟件資源（不論是應(yīng)用軟件和系統(tǒng)軟件）的管理都以文件方式進(jìn)行，承擔(dān)這部分功能的操作系統(tǒng)稱為文件系統(tǒng)。本章介紹文件的邏輯組織和在文件存儲器上的物理組織；實現(xiàn)“按名存取”和文件共享、保護的文件系統(tǒng)目錄的結(jié)構(gòu)和管理；文件存儲空間分配和回收算法和文件系統(tǒng)的磁盤格式；文件系統(tǒng)的安全性。教學(xué)要求掌握文件和文件系統(tǒng)的定義，了解文件系統(tǒng)的類型、文件系統(tǒng)模型。掌握文件的邏輯結(jié)構(gòu)，熟悉五種記錄文件。掌握文件的物理結(jié)構(gòu)及連續(xù)分配、鏈接分配、索引分配和UNIX直接間接混合尋址方式等外存分配方法。掌握文件控制塊和多級目錄結(jié)構(gòu)，掌握UNIX樹型帶勾連的目錄結(jié)構(gòu)和可裝卸文件系統(tǒng)，熟悉現(xiàn)代操作系統(tǒng)對多種文件系統(tǒng)的支持，了解FAT、VFAT目錄結(jié)構(gòu)。掌握基于索引節(jié)點的共享方式和利用符號連接的文件共享。熟悉目錄查詢技術(shù)，掌握內(nèi)存的目錄管理表，掌握文件操作與目錄管理關(guān)系。文件系統(tǒng)目錄5.1概述5.1.1文件5.1.2文件系統(tǒng)5.2文件的組織5.2.1文件的邏輯結(jié)構(gòu)和存取方法5.2.2文件的物理結(jié)構(gòu)5.2.3UNIX/Linux直接間接混合尋址方式5.2.4VFAT表結(jié)構(gòu)5.2.5范例文件系統(tǒng)目錄-15.3文件的目錄和管理5.3.1文件控制塊FCB5.3.2目錄結(jié)構(gòu)－－多級目錄5.3.3UNIX/Linux樹型目錄結(jié)構(gòu)5.3.4文件別名（文件共享）---樹型帶勾連的目錄結(jié)構(gòu)5.3.5子文件系統(tǒng)連結(jié)––UNIX/Linux可裝卸子文件系統(tǒng)5.3.6虛擬文件系統(tǒng)VFS――Linux操作系統(tǒng)對多種文件系統(tǒng)的支持5.3.7內(nèi)存目錄管理5.3.8win32文件和目錄操作的API函數(shù)5.3.9FAT、VFAT文件系統(tǒng)目錄結(jié)構(gòu)文件系統(tǒng)目錄-25.4文件存儲空間的管理5.4.1磁盤組織5.4.2磁盤空閑塊管理和磁盤碎片整理5.4.3Linuxext2文件系統(tǒng)磁盤的結(jié)構(gòu)5.4.4FAT文件系統(tǒng)磁盤的結(jié)構(gòu)[14]5.5NTFS文件系統(tǒng)5.5.1NTFS的卷、蔟和卷布局5.5.2NTFS的引導(dǎo)扇區(qū)5.5.3NTFS系統(tǒng)文件和主文件表5.5.4NTFS文件屬性5.5.5NTFS文件名5.5.6索引5.1文件系統(tǒng)概述5.1.1文件1.文件的定義和命名

計算機系統(tǒng)對系統(tǒng)中軟件資源：無論是程序或數(shù)據(jù)、系統(tǒng)軟件或應(yīng)用軟件都以文件方式來管理。文件是存貯在某種介質(zhì)上的（如磁盤、磁帶等）并具有文件名的一組有序信息的集合。

文件的定義和命名-1

文件名是由字符和數(shù)字組成的，例如MS-DOS中文件名由三部分組成，格式如下：[<盤符>]<文件名>[.擴展名]。格式[]中是可以省略，盤符為存放文件的磁盤驅(qū)動器號，如用A:和C:分別表示軟盤和硬盤驅(qū)動器；文件名由1∽8個字符組成。擴展名為由“.”開始的1-3個字符組成，如.EXE表示可執(zhí)行的浮動代碼文件，.TXT表示ASCⅡ碼文本文件，.LIB表示庫文件，.BAT表示批處理文件等。2.文件類型

UNIX文件系統(tǒng)將文件分成普通文件、目錄文件、設(shè)備文件（特殊文件）和符號連接文件(Symboliclink)等幾類，UNIX把所有I/O設(shè)備作為特殊文件，對I/O設(shè)備操作模仿為對普通文件的存取，這樣將文件與設(shè)備的I/O盡可能統(tǒng)一起來。目錄文件在5.3.3介紹，符號連接文件在5.3.4介紹。

UNIX用$ls–l長列表顯示時第一個字符表示文件類型：“-”表示普通文件，“d”表示目錄文件，“l(fā)”表示符號連接文件，c、b、p分別表示字符設(shè)備、塊設(shè)備和FIFO管道的特殊文件。

5.1.2文件系統(tǒng)1.

文件系統(tǒng)定義和命名

文件系統(tǒng)是操作系統(tǒng)中以文件方式管理計算機軟件資源的軟件和被管理的文件和數(shù)據(jù)結(jié)構(gòu)（如目錄和索引表等）的集合。

從系統(tǒng)角度來看，文件系統(tǒng)是對文件存儲器的存儲空間進(jìn)行組織、分配和回收，負(fù)責(zé)文件的存儲、檢索、共享和保護。從用戶角度來看，文件系統(tǒng)主要是實現(xiàn)“按名存取”，文件系統(tǒng)的用戶只要知道所需文件的文件名，就可存取文件中的信息，而無需知道這些文件究竟存放在什么地方。

2。文件系統(tǒng)的類型(1)FAT文件系統(tǒng)（MS-DOS文件系統(tǒng)、msdos）它是MS-DOS操作系統(tǒng)使用的文件系統(tǒng)，它也能由Windows98/NT、linux、SCOUNIX等操作系統(tǒng)訪問。文件地址以FAT表結(jié)構(gòu)存放，文件目錄32B，文件名為8個基本名加上一個“.”和3個字符擴展名。(2)擴展文件表系統(tǒng)（vfat）它是Windows98使用的擴展的DOS文件系統(tǒng)，它在MS-DOS文件系統(tǒng)基礎(chǔ)上增加了對長文件名（最多到256B）支持。文件系統(tǒng)的類型-1(3)NTFS（NT文件系統(tǒng)）它是WindowsNT操作系統(tǒng)使用的文件系統(tǒng)，它具有很強的安全特性和文件系統(tǒng)恢復(fù)功能，可以處理巨大的存儲媒體，支持多種文件系統(tǒng)。(4)ext2（二級擴展文件系統(tǒng)）它是Linux操作系統(tǒng)使用的高性能磁盤文件系統(tǒng)，它是對Minux操作系統(tǒng)中使用的文件系統(tǒng)擴展（ext）的擴展。它支持256字符的文件名，最大可支持到4TB的文件系統(tǒng)大小。文件系統(tǒng)的類型-3(8)UDF通用磁盤格式文件系統(tǒng)UDF(UniversalDiskFormat)文件系統(tǒng)是依據(jù)光學(xué)儲存技術(shù)協(xié)會（OpticalStorageTechnologyAssociation,OSTA）的通用磁盤格式文件系統(tǒng)規(guī)格1.02版所制定的。它提供了對UDF格式媒體的只讀訪問（例如DVD光盤）。Windows98提供對UDF文件系統(tǒng)支持。3.現(xiàn)代操作系統(tǒng)支持多種文件系統(tǒng)

現(xiàn)代操作系統(tǒng)（如Windows2000/XP、Linux、UNIX等）提供了對多種文件系統(tǒng)的支持。(1)Windows2000/XPWindows2000/XP支持FAT文件系統(tǒng)、NTFS、HPFS、CD-ROM文件系統(tǒng)等多種文件系統(tǒng)。Windows2000執(zhí)行體內(nèi)I/O系統(tǒng)分成I/O管理程序、文件系統(tǒng)驅(qū)動程序和盤驅(qū)動程序三層，不同的文件系統(tǒng)采用不同的文件系統(tǒng)驅(qū)動程序，系統(tǒng)用動態(tài)連接庫對這些文件系統(tǒng)進(jìn)行裝入和卸出并適宜于將來的擴展?，F(xiàn)代操作系統(tǒng)支持多種文件系統(tǒng)-1(2)LinuxLinux支持ext、ext2、msdos、vfat、iso9660、hpfs等多種文件系統(tǒng)。Linux采用虛擬文件系統(tǒng)VFS支持許多不同類型的文件系統(tǒng)，VFS是物理系統(tǒng)與服務(wù)之間的一個接口層，它屏蔽各類文件系統(tǒng)的差異，給用戶和程序提供一個統(tǒng)一的接口。使用命令mkfs創(chuàng)建各類文件系統(tǒng)。5.文件管理的目的方便的文件訪問和控制：以符號名稱作為文件標(biāo)識，便于用戶使用；并發(fā)文件訪問和控制：在多道程系統(tǒng)中支持對文件的并發(fā)訪問和控制；統(tǒng)一的用戶接口：在不同設(shè)備上提供同樣的接口，方便用戶操作和編程；多種文件訪問權(quán)限：在多用戶系統(tǒng)中的不同用戶對同一文件會有不同的訪問權(quán)限；優(yōu)化性能：存儲效率、檢索性能、讀寫性能；差錯恢復(fù)：能夠驗證文件的正確性，并具有一定的差錯恢復(fù)能力；5.2文件的組織

文件的組織是指文件的構(gòu)造方式從用戶觀點出發(fā)觀察到的文件組織結(jié)構(gòu)稱為文件的邏輯結(jié)構(gòu)而文件在外存上的存儲組織形式稱為文件的物理結(jié)構(gòu)，又稱文件的存儲結(jié)構(gòu)。

5.2.1文件的邏輯結(jié)構(gòu)和存取方法1.文件的邏輯結(jié)構(gòu)

從用戶觀點出發(fā)觀察到的文件組織結(jié)構(gòu)---文件的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)的文件稱邏輯文件邏輯文件---無結(jié)構(gòu)的流式文件---有結(jié)構(gòu)的記錄式文件

文件的邏輯結(jié)構(gòu)和存取方法-1

記錄文件有順序、索引、索引順序、直接、分區(qū)和堆文件幾種。(1)堆(ThePile)文件(累積文件)堆文件是最簡單的記錄文件，它是串結(jié)構(gòu)的順序文件。數(shù)據(jù)按先來后到的次序組織，每個記錄所包含的數(shù)據(jù)項是自我標(biāo)識的，數(shù)據(jù)項的長度可以明確指定或使用界定符區(qū)分。在堆文件中訪問所需要的記錄需窮盡搜索，這種文件組織不適合大多數(shù)應(yīng)用。(4)索引順序文件

(IndexedSequentialFile)

索引順序文件是基于鍵的約定次序組織的，為之建立一張索引表，為每個不同鍵值的記錄組的第一個記錄設(shè)置一個表項，為該組的其它記錄設(shè)置了溢出區(qū)域，在溢出區(qū)域內(nèi)記錄按順序文件方式組織。它是順序文件和索引文件的結(jié)合。索引順序文件既適用于交互方式應(yīng)用，也適用于批處理方式應(yīng)用。索引順序文件圖示(5)直接文件/哈希文件

(TheDirect/HashedFile)檢索時給出記錄編號，通過哈希函數(shù)計算出該記錄在文件中的相對位置。它可以對記錄在直接訪問存儲設(shè)備上的物理地址直接（隨機）訪問。直接文件常用于需要高速訪問文件而且每次訪問一條記錄的應(yīng)用中。2.存取方法

用戶通過對文件的存取來完成對文件的修改、追加和搜索等操作。常用的存取方法有順序存取法、隨機存取法（直接存取法）和按鍵存取法三種。

順序存取法是按照文件的邏輯地址順序存取，在記錄式文件中，這反映為按記錄的排列順序來存取，在無結(jié)構(gòu)的字符流文件中，順序存取反映當(dāng)前讀寫指針的變化。存取方法-1

隨機存取法允許用戶根據(jù)記錄的編號來存取文件的任一記錄，或者是根據(jù)存取命令把讀寫指針移到欲讀寫處來讀寫。

按鍵存取法是一種用在復(fù)雜文件系統(tǒng)，特別是數(shù)據(jù)庫管理系統(tǒng)中的存取方法，文件的存取是根據(jù)給定的鍵或記錄名進(jìn)行的。

UNIX、Linux和Windows等操作系統(tǒng)都采用順序存取和隨機存取兩種方法。

5.2.2文件的物理結(jié)構(gòu)

文件在存儲介質(zhì)上的組織方式稱為文件的存儲結(jié)構(gòu)或稱文件的物理結(jié)構(gòu)、物理文件。

外存分配方法有連續(xù)分配、鏈接分配、索引分配，相應(yīng)物理文件有：順序文件、鏈接文件、索引文件。1。連續(xù)分配—順序文件

把邏輯文件中連續(xù)的信息存儲到磁盤連續(xù)的物理盤塊中所形成的文件稱為順序文件。這種文件保證了邏輯文件中邏輯記錄（流式文件為邏輯塊、頁）順序和存儲器中文件占用盤塊順序的一致性。為使系統(tǒng)能查找文件中任一記錄，在文件控制塊FCB（或在目錄）中存放文件第一個記錄所存放的盤塊號ADRR和文件總的盤塊數(shù)N，如下圖所示。連續(xù)分配—順序文件-1如假設(shè)邏輯塊和盤塊大小相等，則要讀取文件第Ⅰ頁（頁從0開始計數(shù)）所在盤區(qū)塊號J可通過下式計算得到：J＝ADRR＋I(xiàn)。邏輯地址LA對應(yīng)邏輯塊號為I=LA/塊大小塊內(nèi)位移為d=LAmod塊大小優(yōu)點是管理簡單，順序存取速度快。缺點是增刪記錄相當(dāng)困難，磁盤存儲空間的利用率不高，有外零頭。所以順序文件只適用于長度不變的只讀文件。

P203圖5-1順序文件結(jié)構(gòu)ContiguousAllocationofDiskSpace2。鏈接分配—鏈接文件在將邏輯文件存儲到外存上時，不要求為整個文件分配連續(xù)的空間,而是可以裝入到離散的多個盤塊中，只在每個盤塊最后一個單元設(shè)置鏈接指針(這稱為隱式鏈接)，然后用鏈接指針將這些離散的盤塊鏈接成一個隊列，這樣形成的物理文件稱為鏈接文件。管理鏈接文件只需在文件控制塊FCB中設(shè)二項，一是存儲文件頭塊信息的盤塊號，另一是存儲文件尾塊信息的盤塊號。鏈接文件結(jié)構(gòu)如下圖所示。

P203圖5-2鏈接文件結(jié)構(gòu)LinkedAllocationofdiskspace鏈接分配—鏈接文件-1鏈接文件的優(yōu)點是盤存儲空間利用率高，文件增刪改記錄方便，缺點是在隨機存取某一個記錄前需要化多次盤Ｉ/Ｏ操作讀該記錄前的文件信息以取得該記錄的盤塊號，才能存取該記錄。如要讀取邏輯塊號第3塊的信息，就要先進(jìn)行3次盤I/O操作以讀取存放第3塊邏輯塊信息的盤塊號，所以鏈接文件只適用于順序存取文件。

3。索引分配—索引文件

索引文件是實現(xiàn)非連續(xù)存儲的另一種方法，系統(tǒng)為加快記錄的檢索過程，為每個文件建立了一張索引表，每個邏輯塊在索引表中占有一個表項，登記存放該邏輯塊的盤塊號。在FCB中放置了索引表指針，它指向索引表始址，索引表存放在盤塊中。

ExampleofIndexedAllocation索引分配—索引文件-1

當(dāng)索引表很大時，需要用多個盤塊。管理有多個盤塊的索引表有二種方法：一種方法是將存放索引表的盤塊用鏈接指針鏈接起來稱為鏈接索引。鏈接索引可以順序地讀取索引表各索引表項，但讀取后面的索引表項類同鏈接文件需要化費多次盤I/O操作。另一種方法是采用多級索引，即為索引表本身建立索引表，從而形成了兩級索引，如所形成的兩級索引表還不能存放在一個盤塊中，則需要為二級索引表建索引表，而形成三級索引。下圖所示為兩級索引。

鏈接索引分配圖示80501012::2580#010#112::#102225120::176.::

:#1023120::

::索引表塊號50總的盤塊數(shù)NFCBP204圖5-3二級索引文件結(jié)構(gòu)

012物理塊號８

101120索引表塊號10820

...........

邏輯塊號0邏輯塊號1第二級索引

主索引表物理塊號101文件控制表FCB物理塊號120物理塊號20物理塊號10索引分配文件系統(tǒng)管理的最大的文件系統(tǒng)采用多級索引的級別由系統(tǒng)管理的最大文件所決定。如果每個盤塊的大小為4KB，每個盤塊號大小占4B一個盤塊可以管理的最大盤塊數(shù)(它有索引表項數(shù))n=盤塊的大小/盤塊號大小=4KB/4B=1K個。一級索引可以管理的最大文件=盤塊的大小×一級索引可以管理的最大盤塊數(shù)=盤塊的大小×n=4KB×1K＝4MB,

二級索引可以管理的最大文件=盤塊的大小×二級索引可以管理的最大盤塊數(shù)=盤塊的大小×(n×n)=4KB×(1K×1K)=4GB，三級索引可以管理的最大文件=盤塊的大小×三級索引可以管理的最大盤塊數(shù)=盤塊的大小×(n×n×n)=4KB×1K×1K×1K=4TB。索引分配—索引文件-2

采用鏈接索引讀取大文件的最前和最后索引表項時需要盤I/O操作次數(shù)相差很大，如文件大小為450MB，則索引表需要113塊盤塊存放，讀取第一邏輯塊只需一次盤I/O操作即取得所在盤塊號，而讀取最后邏輯塊需要113次才能取得所在盤塊號。而對于多級索引，不論對大文件還是小文件，不論是大文件開始或結(jié)尾處，讀取文件某個邏輯塊的盤I/O操作次數(shù)是固定的，例如對二級索引要讀取文件第8500號邏輯塊信息，必須根據(jù)邏輯塊號分別進(jìn)行三次盤I/O操作，第一次先讀取主索引表第8項索引表項（8500／1000＝8取整）取得二級索引表項所在盤塊號。第二次讀二級索引的盤塊，讀得第8500號邏輯塊所在盤塊號，第三次才能進(jìn)行存取第8500號邏輯塊。索引分配——索引文件-2

索引文件由于它既適合順序存取記錄又適合按任意次序隨意存取記錄，也便于增刪文件的記錄，所以索引結(jié)構(gòu)文件應(yīng)用范圍較廣。索引文件的缺點是當(dāng)文件很大時索引表很龐大，占用了許多盤空間，而在文件很小時，多級索引級別又不變，帶來索引塊的另頭和存取速度減慢。

5.2.3UNIX/Linux直接間接混合尋址方式

由于80％以上文件是小文件，為了解決能高速存取小文件和管理大文件的矛盾，UNIX將直接尋址、一級索引、二級索引和三級索引結(jié)合起來，形成了混合尋址方式，如下圖所示。在UNIXSV的索引結(jié)點中設(shè)有13個地址項di_addr[13]（Linux的ext2設(shè)有15個地址項）它們把所存的地址項分成兩類，其中最后三個地址項分別是一級索引、二級索引和三級索引的指針，而前面10個（ext2為12個）為直接尋址的地址項.假如每個盤塊大小為4KB，每個地址用4B表示，一個盤塊可存n=4KB/4B=1K個索引表目。UNIX/Linux直接間接混合尋址方式-1前面10個地址項存放文件邏輯塊號第0－9塊號的盤塊號。如文件大于4KB*10=40KB時，系統(tǒng)增加一級索引，文件邏輯塊號第10－1033塊號的盤塊號存放在一級索引塊中。如文件大于4KB*(10+1K),系統(tǒng)再逐步增加二級索引和三級索引，這樣最大管理的文件為40KB＋4MB＋4GB＋4TB，達(dá)到管理大文件的目標(biāo)。當(dāng)文件不大于40KB時，便可直接從索引結(jié)點的di_addr[0]--di_addr[9]中讀出該文件全部盤塊號，這樣讀小文件時速度快；由于它采用直接尋址，也不需專用物理塊來用作索引塊，節(jié)省了用作管理的空間。P205圖5-4UNIX/Linux直接間接混合尋址方式

二次間接塊一次間接塊

三次間接塊....。。

..

..

....di_addr[0]

di_addr[1]

di_addr[2]

...

di_addr[9]

di_addr[10]一次間接di_addr[11]二次間接di_addr[12]三次間接1034#數(shù)據(jù)塊0#1#2#9#10#5.2.4VFAT表結(jié)構(gòu)

MS-DOS文件系統(tǒng)的文件物理結(jié)構(gòu)采用FAT表結(jié)構(gòu)。該結(jié)構(gòu)為了克服鏈接文件隨機讀取任一邏輯塊需要化費多次盤I/O操作的不足，將各盤塊中的鏈接指針集中存放在盤的開始部分，構(gòu)成一張表，稱為FAT表。(這稱為顯式鏈接)FAT表每一項存放鏈接指針（下一個簇號），每個FAT表項占12位或16位，稱為FAT12或FAT16。對于軟盤因為容量小，簇數(shù)也少，采用12位FAT表，對于硬盤則采用16位FAT表。VFAT表結(jié)構(gòu)-1

FAT表文件系統(tǒng)原為小硬盤的目錄結(jié)構(gòu)而設(shè)計，由于簇的數(shù)目最多只能用16位表示，即最多只能有64K個簇，要用FAT表管理大的磁盤分區(qū)，只能采取增大每簇所包含的扇區(qū)數(shù)，一般根據(jù)磁盤的類型和容量大小來決定簇的大小，如表5-1左邊所示。當(dāng)然每簇包含扇區(qū)數(shù)增加，帶來內(nèi)另頭的浪費，這對小文件特別嚴(yán)重。Windows98為了減少內(nèi)另頭的浪費，可采取每簇的數(shù)目用32位表示，減少每簇包含扇區(qū)數(shù)，這稱為FAT32。FAT16、FAT32文件系統(tǒng)簇和扇區(qū)關(guān)系見表5-1右邊所示。FAT文件系統(tǒng)卷結(jié)構(gòu)圖示返回表5-1FAT文件系統(tǒng)簇和扇區(qū)關(guān)系

VFAT表結(jié)構(gòu)-1VFAT表結(jié)構(gòu)圖示VFAT表結(jié)構(gòu)－2對于16位FAT表，每個表項占據(jù)2字節(jié)，前一字節(jié)作為低2位，后一個字節(jié)作為高2位，即得到表項內(nèi)容。FAT32第一行前8個字符為F8FFFFOFFFFFFFOF。其中第8個字符默認(rèn)為OFh。虛擬文件分配表(VFAT)和Windows98關(guān)閉處理把這個字節(jié)的第4位變成1或0。其中0-VFAF已經(jīng)寫到磁盤；1-Windows已經(jīng)正確地關(guān)閉。當(dāng)把一個文件寫到磁盤上時，VFAT處理這個寫操作。在寫操作期間，VFAT把第4位清為0（即把OFh改為07h）。當(dāng)Windows98正常退出時，這個位重新設(shè)置為1。在重新引導(dǎo)時，W讀這個數(shù)據(jù)位。如果它被設(shè)置為0，磁盤掃描工具將檢查驅(qū)動器錯誤。W就是這樣確定不正確關(guān)機。FAT文件系統(tǒng)瀏覽見實驗5.7.2。

5.2.5范例

一個文件系統(tǒng)中有一個20MB大文件和一個20KB小文件,當(dāng)分別采用連續(xù)、鏈接、二級索引和UNIXSV分配方案時(每塊大小為4096B,每塊地址用4B表示)，問:1.各文件系統(tǒng)管理的最大的文件是多少?2.每種方案對大、小二文件各需要多少專用塊來記錄文件的物理地址(說明各塊的用途)?范例-13．如需要讀大文件前面第5.5KB和后面（16M＋5.5KB）信息，則每個方案各需要多少次盤I/O操作?這個范例是幫助讀者深入比較文件物理組織的各種方案：順序文件的連續(xù)分配、鏈接文件的鏈接分配、二級索引分配、鏈接索引分配和UNIX的直接間接混合分配，明確各種分配方案的優(yōu)缺點和UNIX分配方案的設(shè)計特點。范例-21。各種分配方案的文件系統(tǒng)可管理的最大文件連續(xù)分配：不受限制，可大到整個磁盤文件區(qū)。鏈接分配：同上。鏈接索引：同上。二級索引：由于盤塊大小為4KB，每個地址用4B表示，一個盤塊可存1K個索引表目，二級索引可管理的最大文件容量為4KB×1K×1K＝4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件。UNIX混合分配：可管理的最大文件為40KB＋4MB+4GB＋4TB。范例-32。每種分配方案對20MB大文件和20KB小文件各需要多少專用塊來記錄文件的物理地址?連續(xù)分配：對大小二個文件都只需在文件控制塊FCB中設(shè)二項，一是首塊物理塊塊號，另一是文件總塊數(shù)，不需專用塊來記錄文件的物理地址。鏈接分配：對大小二個文件都只需在文件控制塊FCB中設(shè)二項，一是首塊物理塊塊號，另一是文件總塊數(shù)；同時在每塊存文件的物理塊中設(shè)置存貯下一塊塊號的指針。范例-4

二級索引：對大小文件都固定要用二級索引，對20KB小文件，用一塊作第一級索引，用另一塊作二級索引，共用二塊專用物理塊作索引塊，對于20MB大文件，用一塊作第一級索引，用5塊作第二級索引，共用六塊專用物理塊作索引塊。UNIX的混合分配：對20KB小文件只需在文件控制塊FCB的i_addr[13]中使用前5個表目存放文件的物理塊號，不需專用物理塊。對20MB大文件，F(xiàn)CB的i_addr[13]中使用前10個表目存放大文件前10塊物理塊塊號，用一級索引塊一塊保存大文件接著的1K塊塊號，還要用二級索引存大文件以后的塊號，二級索引使用第一級索引1塊，第二級索引4塊。總共也需要6塊專用物理塊來存放文件物理地址。范例-53.為讀大文件前面第5.5KB和后面（16M＋5.5KB）信息需要多少次盤I/O操作?連續(xù)分配：為讀大文件前面和后面信息都需先計算信息在文件中相對塊數(shù)，前面信息相對邏輯塊號為5.5K／4K=1，后面信息相對邏輯塊號為（16M＋5.5K）/4K=4097。再計算物理塊號＝文件首塊號＋相對邏輯塊號，最后化一次盤I/O操作讀出該塊信息。范例-6鏈接分配：為讀大文件前面5.5.KB的信息，只需先讀一次文件頭塊得到信息所在塊的塊號，再讀一次第1號邏輯塊得到所需信息。而讀大文件后面16MB＋5.5KB的信息，要先把該信息所在塊前面塊順序讀出，共化費4097次盤I／O操作，才能得到信息所在塊的塊號，最后化一次I/O操作讀出該塊信息。所以總共需要4098次盤I／O才能讀取（16MB+5.5KB）字節(jié)信息。范例-7二級索引：為讀大文件前面和后面信息的操作相同，首先進(jìn)行一次盤I／O讀第一級索引塊，然后根據(jù)它的相對邏輯塊號計算應(yīng)該讀第二級索引的那塊，第一級索引塊表目號=相對邏輯塊號／1K，對文件前面信息1／1K＝0，對文件后面信息4097／1K＝4，第二次根據(jù)第一級索引塊的相應(yīng)表目內(nèi)容又化一次盤I／O讀第二級索引塊，得到信息所在塊塊號，再化一次盤I／O讀出信息所在盤塊，這樣讀取大文件前面或后面信息都只需要3次盤I／O操作。范例-8UNIX混合分配：為讀大文件前面5.5KB信息，先根據(jù)它的相對邏輯塊號，在內(nèi)存文件控制塊FCB的i_addr[13]第二個表目中讀取信息所在塊塊號，而只化費一次盤I／O操作即可讀出該塊信息。為讀大文件后在（16MB＋5。5KB）信息，先根據(jù)它的相對邏輯塊號判斷它是在UNIX二級索引管理范圍，先根據(jù)i_addr[11]內(nèi)容化一次盤I／O操作讀出第一級索引塊，再計算信息所在塊的索引塊號在第一級索引塊的表目號為（4097-9-1024）／1024＝3，根據(jù)第一級索引塊第3個表目內(nèi)容再化費一次盤I／O操作，讀出第二級索引塊，就可以得到信息所在塊塊號，最后化一次盤I／O讀出信息所在盤塊，這樣總共需要3次盤I／O操作才能讀出文件后面的信息。

范例-95.3文件的目錄和管理

5.3.1文件控制塊FCB

為了實現(xiàn)“按名存取”，系統(tǒng)必須為每個文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，它至少要包括文件名和存放文件的盤物理地址，這個數(shù)據(jù)結(jié)構(gòu)稱為文件控制塊FCB，文件控制塊的有序集合稱為文件目錄，即一個文件控制塊FCB就是一個文件目錄項。文件控制塊FCB中包含的信息有以下三類：文件控制塊FCB-11?；拘畔㈩愇募簶?biāo)識一個文件的符號名，在每個系統(tǒng)中文件必須具有唯一的名字。.文件的物理地址：這由于文件的物理結(jié)構(gòu)不同而不同。對于連續(xù)文件就是文件的起始塊號和文件總塊數(shù)；對于MS－DOS是文件的起始簇號和文件總字節(jié)數(shù)；對于UNIXSV是文件所在設(shè)備的設(shè)備號、13個地址項、文件長度和文件塊數(shù)等。2．存取控制信息類文件的存取權(quán)限，象UNIX用戶分成文件主、同組用戶和一般用戶三類，這三類用戶的讀寫執(zhí)行（RWX）的權(quán)限。文件控制塊FCB-23．使用信息類文件建立日期、最后一次修改日期、最后一次訪問的日期；當(dāng)前使用的信息：打開文件的進(jìn)程數(shù)，在文件上的等待隊列等。文件控制塊的信息因OS而不同，SCOUNIX文件系統(tǒng)ls文件長列表顯示$ls–l的FCB信息如下：-r-xr-xr-t1binbin43296May131997/opt/K/SCO/Unix/5.0.4Eb/bin/ls顯示的各項信息為文件類型和存取權(quán)限、連接數(shù)、文件主、組名、文件長度、最后一次修改日期、文件名。5.3.2目錄結(jié)構(gòu)－－多級目錄

目錄結(jié)構(gòu)的組織關(guān)系到文件系統(tǒng)的存取速度，關(guān)系到文件共享性和安全性，因此組織好文件的目錄是設(shè)計文件系統(tǒng)的重要環(huán)節(jié)。1。單級目錄結(jié)構(gòu)最簡單的目錄結(jié)構(gòu)是在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個表目，這稱為單級目錄。單級目錄結(jié)構(gòu)簡單，能實現(xiàn)目錄管理的基本功能--按名存取，但存在查找速度慢，不允許重名和不便于實現(xiàn)文件共享等缺點，因此它只適用于單用戶環(huán)境。目錄結(jié)構(gòu)－－多級目錄-12。多級目錄結(jié)構(gòu)為了解決以上問題，在多道程序設(shè)計系統(tǒng)中常采用多級目錄結(jié)構(gòu)，MS－DOS和UNIX等操作系統(tǒng)都采用多級目錄結(jié)構(gòu)。這種目錄結(jié)構(gòu)象一棵倒置的有根樹，該樹根向下，每一個節(jié)點是一個目錄，最末一個結(jié)點是文件，下圖為UNIX樹形多級目錄結(jié)構(gòu)。在多級目錄中要訪問一個文件時，必須指出文件所在的路徑名，路徑名從根目錄開始到該文件的通路上所有各級目錄名拼起來得到，各目錄名之間與文件名之間可用分隔符隔開。在MS-DOS中分隔符為“\”，在UNIX中分隔符為“/”。例如下圖中訪問命令文件man的路徑名為/usr/lib/man，這也稱為文件全名。Tree-StructuredDirectoriesP209圖5-5UNIX樹形目錄結(jié)構(gòu)binusrmntetctmpdevbootunixlswhohdlmountTmp00ltty0lspoolincludesysbinlibdchioconfdir.hlibio.hTab.cmana.out.h目錄結(jié)構(gòu)－－多級目錄-2重名問題：在多級目錄中存取一個文件需要用文件全名，這就允許用戶在自己的目錄中使用與其它用戶文件相同的文件名，由于各用戶使用不同的目錄，雖二者使用了相同的文件名，但它們的文件全名仍不相同，這就解決了重名問題。采用多級目錄結(jié)構(gòu)也提高了檢索目錄的速度：如采用單級目錄則查找一個文件最多需查遍系統(tǒng)所有文件名，平均也要查一半文件名。而多級目錄查找一個文件最多只要查遍文件路徑上各目錄的子目錄和文件，例如上圖中要查找文件man，只要查遍root目錄、usr目錄和lib目錄所在子目錄和文件就可以。目錄結(jié)構(gòu)－－多級目錄-3相對路徑：每訪問一個文件都要使用從根目錄開始搜索直到樹葉的數(shù)據(jù)文件為止，包含各中間子目錄的全路徑名是相當(dāng)麻煩的，同時由于一個進(jìn)程運行時訪問的文件大多局限在某個范圍，基于這一點，可為每個用戶（或每個進(jìn)程）設(shè)置一個“當(dāng)前目錄”，又稱“工作目錄”。進(jìn)程對各文件的訪問都相對于“工作目錄”而設(shè)置路徑，這稱為相對路徑名。目錄結(jié)構(gòu)－－多級目錄-4相應(yīng)地，從根目錄開始的路徑名稱為絕對路徑名(absolutepathname)。用相對路徑可縮短搜索路徑，提高搜索速度。例：文件mbox的絕對路徑名為/usr/ast/mbox，如設(shè)置一個“當(dāng)前目錄”為/usr，則文件mbox的相對路徑名為ast/mbox。

5.3.3UNIX/Linux樹型目錄結(jié)構(gòu)

UNIX為了加快目錄的尋找速度，UNIX將文件控制塊FCB中文件名和文件說明分開。文件說明為索引節(jié)點，各文件索引節(jié)點集中存放在索引節(jié)點區(qū)，索引節(jié)點按索引節(jié)點號排序。而文件名與索引節(jié)點號構(gòu)成目錄項，UNIXSV操作系統(tǒng)的文件名14個字節(jié)，索引節(jié)點2個字節(jié)，共16個字節(jié)構(gòu)成目錄項。同一級目錄項構(gòu)成目錄文件，在文件區(qū)存放。

UNIX/Linux樹型目錄結(jié)構(gòu)-1

Linux目錄文件中的目錄項會變長，以保證系統(tǒng)支持文件名長度可變，最長達(dá)255個字符。目錄項的前三項是定長的，包含以下信息：(1)索引節(jié)點號(4B)；(2)目錄項長度(2B)；(3)文件名長度(2B)。目錄項最后是文件名，目錄項不能跨越二個塊。UNIX樹型的目錄結(jié)構(gòu)-1

每個文件有一個存放在磁盤索引節(jié)點區(qū)的索引節(jié)點，稱為磁盤索引節(jié)點,它包括以下內(nèi)容：(1)文件主標(biāo)識符和同組用戶標(biāo)識符；(2)文件類型:是普通文件、目錄文件、符號連接文件或特別文件（又分塊設(shè)備文件或字符設(shè)備文件）；(3)文件主，同組用戶和其它人對文件存取權(quán)限（讀R、寫W、執(zhí)行X）；（４）文件的物理地址，用于5.2.4UNIX直接、間接混合尋址的13個地址項di_addr[13];（5）文件長度（字節(jié)數(shù)）di_size；（6）文件鏈接數(shù)di_nlink；（7）文件最近存取和修改時間等。UNIX采用文件名和文件說明分離的目錄結(jié)構(gòu)如下圖所示：

UNIX磁盤文件卷結(jié)構(gòu)圖示P211圖5-6UNIX樹型帶勾連的目錄結(jié)構(gòu)lsI=2bindevunixusrmntetctmpdey476987I=4I=6

ls10

dirdiskasterikjimbal101926305145

I=10I=26Booksmbox……9260…..I=60mbox5.3.4文件別名（文件共享）---樹型帶勾連的目錄結(jié)構(gòu)1.一般共享目錄結(jié)構(gòu)的缺點文件共享是指不同的用戶使用不同的文件名來使用同一文件。在用一般共享目錄結(jié)構(gòu)時，一用戶增加文件的內(nèi)容，只改變自己的文件目錄，其它用戶不知改變。一般共享目錄結(jié)構(gòu)的缺點-12.基于索引節(jié)點(indexnode)的共享方式實現(xiàn)文件共享的一種有效方法是基本文件目錄法。該方法把所有目錄的內(nèi)容分為文件名和文件說明兩部分。一部分稱為符號文件目錄（SDF），它包含文件符號名和由系統(tǒng)賦予唯一的內(nèi)部標(biāo)識符ID組成。另一部分稱為基本文件目錄（BDF），它包含目錄項中除文件符號名外的所有其它信息，并加上與符號目錄相一致的內(nèi)部標(biāo)識符ID。標(biāo)識符ID是各文件在基本文件目錄中表目的排序號。UNIX/Linux采用了基本文件目錄法目錄結(jié)構(gòu)。

基于索引節(jié)點的共享方式-1

采用文件名和文件說明分離的目錄結(jié)構(gòu)有利于實現(xiàn)文件共享，這里的文件共享是指不同的用戶對同一文件可取不同的文件名，即給文件取別名。文件共享是通過在二個不同子目錄下取了不同的文件名，但它們具有相同的索引節(jié)點號的方法來實現(xiàn)，UNIX/Linux這種目錄結(jié)構(gòu)稱為樹形帶勾連的目錄結(jié)構(gòu)。

基于索引節(jié)點的共享方式-2

列出當(dāng)前目錄的子目錄和文件命令ls是放在/bin子目錄下，而/usr/bin子目錄下可設(shè)置一個DOS兼容的命令dir，這增加的命令實為執(zhí)行l(wèi)s命令。為了共享文件，只是在二個不同子目錄下取了不同的文件名ls和dir，但它們具有相同的索引節(jié)點。在文件的索引節(jié)點中有一個量di_nlink表示連接到該索引節(jié)點上的連接數(shù)；在用命令“l(fā)s-l”長列表顯示時，文件的第2項數(shù)據(jù)項表示鏈接數(shù)?；谒饕?jié)點的共享方式-3

使用命令“l(fā)n”可給一已存在文件增加一個新文件名，即給文件取別名。

命令“$lnoldnew”執(zhí)行后，文件的索引節(jié)點中鏈接數(shù)增加1。采用二個文件目錄表目指向同一個索引節(jié)點的連接稱為文件硬連接，此種鏈接不能跨越文件系統(tǒng)。用硬連接格式如下：$ln/opt/k/sco/unix/5.0.4Eb/bin/ls/usr/lx20/dir$ls

–ldir-r-xr-xr-t2binbin43296May131997dir3.利用符號連接(symboliclink,shortcut)文件硬連接不利于文件主刪除它擁有的文件，因為文件主要刪除它擁有的共享文件，必須首先刪除（關(guān)閉）所有的硬連接，否則就會造成共享該文件的用戶的目錄表目指針懸空。為此又提出另一種連接方法－－符號連接。系統(tǒng)為共享的用戶創(chuàng)建一個link類型的新文件，將這新文件登錄在該用戶共享目錄項中，這個link型文件包含連接文件的路徑名。該類文件在用ls命令長列表顯示時，文件類型為l。利用符號連接－1當(dāng)用戶要訪問共享文件且正要讀link型新文件時，操作系統(tǒng)根據(jù)link文件類型性質(zhì)將文件讀出的內(nèi)容作為路徑名去訪問真正的共享文件。在UNIX中也是使用ln來建立符號連接的共享文件，這時命令為“$ln-soldnew”。如用符號連接格式如下：$ln-s/opt/k/sco/unix/5.0.4Eb/bin/ls/usr/lx20/dir$ls

–ldirlrwxrwxrwx1lx20group30Dec2713:34dir->/opt/K/SCO/Unix/5/0/4Eb/bin/ls利用符號連接-2采用符號連接可以跨越文件系統(tǒng)，甚至可以通過計算機網(wǎng)絡(luò)連接到世界上任何地方的機器中的文件，此時只需提供該文件所在的地址，以及在該機器中的文件路徑。符號連接的缺點：其它用戶讀取符號連接的共享文件比讀取硬連接的共享文件需要增多讀盤操作。因為其它用戶去讀符號連接的共享文件時，系統(tǒng)中根據(jù)給定的文件路徑名，逐個分量地去查找目錄，通過多次讀盤操作才能找到該文件的索引節(jié)點，而用硬連接的共享文件的目錄文件表目中已包括了共享文件的索引節(jié)點號。Windows2000的NTFS，支持文件別名的符號鏈接方式。

利用符號連接-3

SCOUNIX例：在SCOUNIX中l(wèi)s文件實際存放的目錄為/opt/k/sco/unix/5.0.4Eb/bin列表顯示如下：$ls-l/opt/k/sco/unix/5.0.4Eb/bin/ls-r-xr-xr-t1binbin43296May131997/opt/K/SCO/Unix/5.0.4Eb/bin/ls在標(biāo)準(zhǔn)UNIX中l(wèi)s命令在/bin子目錄下，SCOUNIX采用符號連接在/bin子目錄下建立ls文件，該ls是個link類型的文件，它不能用編輯文件顯示，但用ls長列表顯示時可看出它的符號連接的路徑名，可從下列表顯示可見$ls

–l/bin/lslrwxrwxrwx1rootroot30Nov241998/bin/ls->/opt/K/SCO/Unix/5.0.4Eb/bin/ls長列表顯示最后一列數(shù)據(jù)是文件名和它連接文件的路徑名。4.文件別名（文件共享）的演示實驗在Linux/UNIX建立一個與DOS一樣的列表顯示命令dir。①用硬連接格式如下：$ln/bin/ls/usr/lx20/dir執(zhí)行后ls與dir長列表顯示如下：$ls-l/bin/ls-r-xr-xr-t2binbin43296May131997/bin/ls$ls

–ldir-r-xr-xr-t2binbin43296May131997dir可看出硬連接時ls和dir文件的連接數(shù)為２，二文件大小相等為43296B。

文件別名（文件共享）的演示實驗-1②如用符號連接格式如下：$ln-s/bin/ls/usr/lx20/dir命令執(zhí)行后ls與dir文件長列表顯示如下：$ls

–ldirlrwxrwxrwx1lx20group30Dec2713:34dir->/bin/ls$ls-l/bin/ls-r-xr-xr-t1binbin43296May131997/bin/ls5.3.5子文件系統(tǒng)連結(jié)––

UNIX/Linux可裝卸子文件系統(tǒng)文件存儲器硬盤各盤區(qū)和軟盤都有一個象倒置的樹一樣的多級目錄的文件系統(tǒng)，MS-DOS系統(tǒng)用“盤符”來識別它們，而UNIX系統(tǒng)，只有一個安裝UNIX操作系統(tǒng)的根設(shè)備的文件系統(tǒng)常駐系統(tǒng)，而硬盤其它盤區(qū)和軟盤上的子文件系統(tǒng)直至被安裝前，UNIX系統(tǒng)不知道它存在。系統(tǒng)要使用其它的子文件系統(tǒng)，必須先用mount安裝命令將其安裝到系統(tǒng)。子文件系統(tǒng)連結(jié)–1被安裝子文件系統(tǒng)的倒樹形目錄結(jié)構(gòu)的根被安裝到根設(shè)備文件系統(tǒng)樹形目錄的某一節(jié)點上，與根設(shè)備的文件系統(tǒng)的樹形目錄結(jié)構(gòu)融為一體，構(gòu)成一個倒置樹的多級目錄結(jié)構(gòu)。通常這個安裝節(jié)點所對應(yīng)的文件是專為安裝新文件系統(tǒng)而創(chuàng)建的空子目錄，如UNIX根目錄下的mnt子目錄。新文件系統(tǒng)通過在內(nèi)存的數(shù)據(jù)結(jié)構(gòu)（安裝表等）與根設(shè)備文件系統(tǒng)某節(jié)點聯(lián)系起來，在安裝時也將新子文件系統(tǒng)盤的管理塊（superblock）和有關(guān)目錄信息拷貝到內(nèi)存的系統(tǒng)緩沖區(qū)和活動索引節(jié)點表。子文件系統(tǒng)連結(jié)--2新文件系統(tǒng)必須在安裝后才能進(jìn)行讀寫，文件創(chuàng)建和刪除等操作，其變化要記錄在內(nèi)存系統(tǒng)緩沖區(qū)中管理塊和活動索引節(jié)點表中。而使用完畢后必須使用umount拆卸命令拆卸安裝上去的子文件系統(tǒng)，在拆卸時系統(tǒng)將內(nèi)存系統(tǒng)緩沖中的管理塊和活動索引節(jié)點表信息拷貝到將拆卸子文件系統(tǒng)的盤中，以保證盤中信息的完整性。子文件系統(tǒng)連結(jié)圖示SeparateAftermounting(a)(b)(a)Beforemounting.(b)Aftermounting安裝表結(jié)構(gòu)和作用圖示structmount{intm_flags;dev_tm_dev;structinode*m_inodp;structbuf*m_bufp;structinode*m_mount;}安裝表作用圖示見下：0#

1#superblcckI=1i-inadeFilsys子文件卷inadeI=123456m-indpm-bufpm-mount根設(shè)備內(nèi)存軟盤安裝表緩沖池的緩沖區(qū)子文件系統(tǒng)連結(jié)--3在UNIX系統(tǒng)中一般將硬盤劃分為幾個區(qū)，即為幾個文件系統(tǒng)，把系統(tǒng)文件和用戶程序分開，以保護數(shù)據(jù)正確和便于維護。系統(tǒng)啟動時，在安裝根文件系統(tǒng)后，會根據(jù)/etc/fstab逐個安裝各區(qū)文件系統(tǒng)，在關(guān)機前，會逐個拆卸各區(qū)文件系統(tǒng)，最常用的其它文件系統(tǒng)為/u，用于存儲用戶程序。

子文件系統(tǒng)連結(jié)演示實驗：

在Linux/UNIX系統(tǒng)上讀寫軟盤上信息操作如下：①插入軟盤。②使用安裝命令安裝軟盤文件系統(tǒng):格式：#mount–ttypedevicemount-point例：#mount–tvfat/dev/fd0/mnt③在/mnt目錄下讀寫Windows格式化的軟盤上*.txt文件。④使用拆卸的命令卸下軟盤文件系統(tǒng):格式：#umountdevice例：#umount/dev/fd0or#umount/mnt⑤取出軟盤。5.3.6虛擬文件系統(tǒng)VFS――

Linux操作系統(tǒng)對多種文件系統(tǒng)的支持Linux采用虛擬文件系統(tǒng)VFS支持許多不同類型的文件系統(tǒng)，VFS是物理系統(tǒng)與服務(wù)之間的一個接口層，它屏蔽各類文件系統(tǒng)的差異，給用戶和程序提供一個統(tǒng)一的接口。Linux支持ext、ext2、msdos、vfat、iso9660、hpfs等多種文件系統(tǒng)。使用命令mkfs創(chuàng)建各類文件系統(tǒng)。VSF使Linux同時安裝支持不同類型的文件系統(tǒng)成為可能。虛擬文件系統(tǒng)VFS―1VFS是物理文件系統(tǒng)與服務(wù)之間的一個接口，它對Linux的每一個文件系統(tǒng)的所有細(xì)節(jié)進(jìn)行抽象，使得不同的文件系統(tǒng)在Linux內(nèi)核以及系統(tǒng)中運行的其它進(jìn)程看來都是相同的，嚴(yán)格說來VFS并不上一種實際的文件系統(tǒng)，它只存在于內(nèi)存中，不存在于任何外存空間，VFS在系統(tǒng)啟動時建立，在系統(tǒng)關(guān)閉時消亡。VFS擁有關(guān)于各種特殊文件系統(tǒng)的公共接口，如超級塊incde，文件操作函數(shù)入口等。特殊文件系統(tǒng)的細(xì)節(jié)問題統(tǒng)一由VFS的公共接口來翻譯，它們對系統(tǒng)內(nèi)核和用戶進(jìn)程是透明的。P213圖5-7VFS與實際文件系統(tǒng)的封裝關(guān)系

ext2FSMINIXFSextFSMSDOSFS

BufferCache

I/O設(shè)備驅(qū)動

VFS5.3.7內(nèi)存目錄管理

1．目錄查詢技術(shù)

為了實現(xiàn)用戶對文件的按名存取，系統(tǒng)必須首先利用用戶提供的文件名，對文件目錄進(jìn)行查詢，找出該文件的文件控制塊FCB，對UNIX系統(tǒng)即要找出該文件的索引節(jié)點。然后根據(jù)找到的FCB中所記錄的文件物理地址，（對UNIX系統(tǒng)即是索引節(jié)點中的用于UNIX直接、間接混合尋址的13個地址項di-addr[13]），并根據(jù)文件物理組織方式找出文件的盤塊號，進(jìn)而換算出文件在磁盤上的物理位置（柱面號、磁頭號、扇區(qū)號），最后啟動磁盤驅(qū)動程序，將所需文件讀入內(nèi)存。目錄查詢技術(shù)-1對目錄查詢的技術(shù)有兩種：線性檢索法和Hash法。這里介紹UNIX中使用的線性檢索法，又稱為順序檢索法。下面以在上圖所示UNIX樹型目錄中查找文件/bin/ls為例介紹線性檢索法。首先系統(tǒng)讀入根索引節(jié)點（其索引節(jié)點號為1），從文件地址項查找根目錄文件所在物理塊號讀入內(nèi)存。同時從用戶提供的文件名中讀入根目錄下第一個文件分量bin,用它與根目錄文件中各個目錄項的文件名順序地進(jìn)行比較，從中找到匹配號，得到匹配項的索引節(jié)點號為2。目錄查詢技術(shù)-2

然后將磁盤第2個索引節(jié)點讀入內(nèi)存，從中找出bin目錄文件所在物理塊號，并將它讀入內(nèi)存。同時從用戶提供的文件名中讀入第二個文件分量ls，用它與bin目錄文件中目錄項的文件名順序地進(jìn)行比較，從中找出匹配號，得到匹配項的索引號為10。爾后，將磁盤第10號節(jié)點讀入內(nèi)存，從中判斷l(xiāng)s文件所在的物理塊號。目錄查詢操作到此結(jié)束，如果順序查找過程中發(fā)現(xiàn)一個文件分量名未能找到，則仃止查找并送回“文件未找到”信息。

2。內(nèi)存的目錄管理表目錄查詢必須通過在磁盤上反復(fù)搜索來完成，這要化費不少次的盤塊I/O，這樣大大浪費了CPU處理時間，降低了處理速度。為了減輕盤I/O負(fù)擔(dān)，采用把當(dāng)前使用的文件目錄表目復(fù)制到內(nèi)存，建立內(nèi)存的目錄管理表。這樣只要第一次使用某個目錄表目時需要盤I/O來完成讀入內(nèi)存，以后使用該目錄表目只要在內(nèi)存目錄管理表中進(jìn)行，不需再進(jìn)行盤塊I/O，提高了處理速度，由于只把正在使用的目錄復(fù)制到內(nèi)存而不是全部目錄讀入內(nèi)存，所以內(nèi)存目錄所占容量也不大。內(nèi)存的目錄管理表-1UNIX磁盤上的目錄分成索引節(jié)點和目錄文件，在內(nèi)存中建立活動索引節(jié)點表（或稱內(nèi)存索引節(jié)點表）和系統(tǒng)打開文件表，分別保存已打開文件的索引節(jié)點和文件名內(nèi)容，同時在每個進(jìn)程控制塊的User區(qū)中設(shè)置一張用戶文件描述表（又稱用戶/進(jìn)程打開文件表），每個打開文件在相應(yīng)的用戶文件描述表目中存儲一個指向在系統(tǒng)打開文件表中相應(yīng)表目位置偏移的指針fp。系統(tǒng)打開文件表用來存放已打開文件信息，包括指向內(nèi)存索引節(jié)點表相應(yīng)表目的指針f_inode，文件讀寫標(biāo)志f_flag，文件讀寫指針＊f_offset[2]和訪問計數(shù)f_count等。內(nèi)存的目錄管理表-2內(nèi)存索引節(jié)點表表目稱為內(nèi)存索引節(jié)點,它是相應(yīng)磁盤索引節(jié)點在內(nèi)存駐留,同時增加了些信息：索引節(jié)點號i_number，當(dāng)前正在訪問該索引節(jié)點的引用計數(shù)i_count，文件所屬文件系統(tǒng)邏輯設(shè)備號i_dev，鏈接的前向指針i_forw和后向指針i_back等。用戶打開文件表、系統(tǒng)打開文件表和活動索引節(jié)點表之間關(guān)系如下圖所示。i_nlink系統(tǒng)目錄中一個文件取了幾個不同的文件名f_count幾個用戶用相同文件名同時來存取同一文件i_count用戶用幾個不同的文件名（或不同的存取方式）同時來存取同一文件P215圖5-8內(nèi)存的目錄管理關(guān)系..

.用戶文件描述表

fP..............f_inodef_countf_offsetf_flag.............i-counti_addr[o]i_addr[1]...i_addr[12]............進(jìn)程控制塊PCB系統(tǒng)打開文件表內(nèi)存索引節(jié)點表磁盤文件區(qū)USER內(nèi)存的目錄管理表圖示-1

Therelationbetweenthetable,theopen內(nèi)存的目錄管理表圖示-2i-count=2f-count=1內(nèi)存的目錄管理表圖示-3i-count=1f-count=23。文件操作與目錄管理關(guān)系

為了讓用戶靈活方便和有效地使用文件，文件系統(tǒng)提供許多有關(guān)文件的系統(tǒng)調(diào)用，即文件操作供用戶使用。文件系統(tǒng)提供的常用系統(tǒng)調(diào)用有“建立”（create）文件、“打開”（open）文件、“寫”（write）文件、“讀”（read）文件、“關(guān)閉”（close）文件、“刪除”（delete）文件等。這些操作與目錄管理的數(shù)據(jù)結(jié)構(gòu)關(guān)系密切，下面以UNIX為例說明。文件操作與目錄管理關(guān)系-1

(1)建立文件當(dāng)用戶提出在某個路徑或目錄下建立文件時，系統(tǒng)首先檢查在該目錄下有否相同名的文件，如沒有的話則在磁盤目錄中登記此文件，對UNIX系統(tǒng)則需給它分配索引節(jié)點，以保存文件存放的盤塊號，同時在該目錄文件中增加一個表目，記錄文件名和相應(yīng)的索引節(jié)點號。文件操作與目錄管理關(guān)系-2

(2)打開文件用戶使用文件前必須使用“打開”命令打開文件，“打開”命令的任務(wù)是磁盤目錄中找到該文件的FCB，拷貝到內(nèi)存，建立內(nèi)存的目錄管理表。對UNIX系統(tǒng)是找到此文件所在的目錄文件的表目和磁盤索引節(jié)點，然后將它們拷貝到內(nèi)存，建立系統(tǒng)打開文件表和活動索引節(jié)點表有關(guān)表目，同時在PCB的用戶打開文件表中增加表目，并建立如前圖一樣的三個表間的聯(lián)系。文件操作與目錄管理關(guān)系-3(3)讀／寫文件用戶（或進(jìn)程）要讀寫文件時，利用PCB中用戶打開文件表的fP指針可以從三表關(guān)系中找到所需讀／寫的文件所的盤塊，在系統(tǒng)打開文件表的表目中設(shè)置讀寫指針f_offset[2]分別記錄了進(jìn)程讀／寫文件的位置。如在寫文件時增加或減少文件所用的磁盤塊數(shù)，則要修改活動索引節(jié)點表的表目中的13個地址項i_addr[13].文件操作與目錄管理關(guān)系-4(4)關(guān)閉文件當(dāng)對文件操作完成后，或暫時不用，均需及時使用“關(guān)閉”命令關(guān)閉文件，將已修改的內(nèi)存文件目錄信息及時寫回到磁盤目錄中，并釋放文件的內(nèi)存目錄表目空間供其它進(jìn)程使用。對UNIX子系統(tǒng)，關(guān)閉文件，將文件在系統(tǒng)打開文件表和活動索引表的表目內(nèi)容分別寫回到磁盤的相應(yīng)目錄文件和索引節(jié)點表區(qū)，并刪除相應(yīng)表目供它用，同時進(jìn)程打開文件表中相應(yīng)表目也刪除，以免進(jìn)程打開文件數(shù)超過定值。如用戶打開文件并進(jìn)行讀寫后未關(guān)閉文件就退出，或者發(fā)生斷電情況，這樣都可能會造成這次讀寫修改信息的丟失。文件操作與目錄管理關(guān)系-5(5)刪除文件如文件不需要則要用“刪除”命令刪除文件，根據(jù)用戶提出的在某目錄下的文件名，命令將該文件在目錄文件中的表項和相應(yīng)的索引節(jié)點內(nèi)容刪除，釋放供它用。P216圖5-9文件操作命令和目錄管理數(shù)據(jù)結(jié)構(gòu)關(guān)系

“建立”“打開”“刪除”“關(guān)閉”

磁盤目錄內(nèi)存目錄(練習(xí)6)目錄文件磁盤索引節(jié)點PCB中用戶文件描述表系統(tǒng)打開文件表

內(nèi)存索引節(jié)點表讀寫5.3.9FAT、VFAT文件系統(tǒng)目錄結(jié)構(gòu)

1.FAT文件系統(tǒng)目錄結(jié)構(gòu)MS-DOS的FAT文件系統(tǒng)文件控制塊FCB的長度為32個字節(jié)，它的內(nèi)容及其含義如下：

FCB第0－7位為文件名，其中第一個字節(jié)表示目錄項的狀態(tài)，00H從未用過的目錄項，E5H已刪除文件的目錄項，2EH子目錄標(biāo)記項，2EH20H為子目錄本身，2EH2EH為其父目錄，其它為文件名的首字符。

078ABCF文件名擴展名屬性未用未用時間日期起始簇號文件長度（B）

1015161718191A1B1C1FFAT、VFAT文件系統(tǒng)目錄結(jié)構(gòu)-1第16H-17H為最后修改時間，第18H-19H為最后修改日期，第1AH-1BH字節(jié)為文件第一簇簇號，起始簇號為002H。FCB第0BH字節(jié)為屬性，共有六種文件屬性，其中有些可組合使用，含義如下：例如MS-DOS6.21操作系統(tǒng)文件MS-DOS.SYS的屬性為07H。根目錄包含的子目錄和文件在盤區(qū)的根目錄區(qū)，而子目錄所包含的目錄和文件以目錄文件形式存放。VFAT文件系統(tǒng)目錄在FAT文件系統(tǒng)的FCB32個字節(jié)的未用位中增加使用：0DH-0FH為創(chuàng)建時間，10H-11H為創(chuàng)建日期，12H-13H為最后存取日期。

B7B6B5B4B3B2B1B0

××更改位子目錄卷標(biāo)位系統(tǒng)隱含只讀2.VFAT文件系統(tǒng)目錄結(jié)構(gòu)(1)長文件名

Windows98長文件名的目錄項由幾個MS－DOS的32B目錄組成。它用一個表項存放短文件名和這個文件或子目錄的其它信息（包括MS－DOSFCB原有的簇號、文件大小，最后修改時間和最后修改日期，還有Windows98增加的創(chuàng)建時間、創(chuàng)建日期和最后存取日期），短文件名的屬性是0×20。另外用連續(xù)若干個表項存放長文件名，每個表項存放13個字符（使用Unicode編碼，不論西文和漢字，每個字符一律占用2個字節(jié)。對西文第一個字節(jié)存ASCII碼，第二個字節(jié)存0×00。）VFAT文件系統(tǒng)目錄結(jié)構(gòu)－長文件名的表項首字節(jié)的二進(jìn)制數(shù)低5位值，分別為00001B、00010B、00011B、……，表示它們的次序，左起第2位為1（也就是在低5位基礎(chǔ)上加40H）表示該表項是最后一項。最后項存放13個字符位置多余時，先用2個字節(jié)0表示結(jié)束，再用FFH填充。長文件名的屬性是OFH。長文件名項的第13、27、28字節(jié)為0×00，第14字節(jié)為短文件名檢驗和。長文件名Thequickbrown.fox（短文件名為THEQUI~1.FOX）目錄項格式如下：VFAT文件系統(tǒng)目錄結(jié)構(gòu)-1Windows98VFAT目錄結(jié)構(gòu)-2用Debug工具查根目錄區(qū)找出其目錄項顯示如下：2171:29A04277006E002E0066-006F000F00077800Bw.n...f.o....x.2171:29B00000FFFFFFFFFFFF-FFFF0000FFFFFFFF................2171:29C00154006800650020-0071000F00077500.T.h.e..q....u.2171:29D0690063006B002000-6200000072006F00i.c.k..b...r.o.2171:29E05448455155497E31-464F5820003CC17BTHEQUI~1FOX.<.{2171:29F06E267B2700002351-6326F409006A0200n&{'..#Qc&...j..Windows98VFAT目錄結(jié)構(gòu)-2用Debug工具查根目錄區(qū)找出其目錄項顯示如下：2171:29A04277006E002E0066-006F000F00077800Bw.n...f.o....x.2171:29B00000FFFFFFFFFFFF-FFFF0000FFFFFFFF................2171:29C00154006800650020-0071000F00077500.T.h.e..q....u.2171:29D0690063006B002000-6200000072006F00i.c.k..b...r.o.2171:29E05448455155497E31-464F5820003CC17BTHEQUI~1FOX.<.{2171:29F06E267B2700002351-6326F409006A0200n&{'..#Qc&...j..5.4文件存儲空間的管理5.4.1磁盤組織磁盤是常用的存儲設(shè)備，它具有容量大，存取速度快，可以實現(xiàn)隨機存取等優(yōu)點，是現(xiàn)代操作系統(tǒng)的必需存儲設(shè)備，也是實現(xiàn)虛擬存儲器所必需的硬件。1.磁盤物理組織每個磁盤都是由盤片，磁道和扇區(qū)組成。磁道是盤片每個表面上的環(huán)形區(qū)域，柱面是有多個盤片的磁盤上處于同一磁頭位置的一組磁道組成。盤片的每一個面有一個磁頭，磁頭一般都連在一個公用的磁頭移動機構(gòu)--磁臂上，這樣所有的磁頭都一起移動，每盤片的每個面上的磁頭都永遠(yuǎn)定位在同一邏輯道上。每個磁道被分為扇區(qū)的部分，一個扇區(qū)是磁盤上最小的物理存儲單元，扇區(qū)的數(shù)據(jù)大小永遠(yuǎn)都是2的冪，并且?guī)缀跤肋h(yuǎn)是512B。MS-DOS、Windows98/2000都以簇為單位來開辟存儲區(qū)，而簇是一個或2的冪次個(2、4、8..)連續(xù)的扇區(qū)。

柱面扇區(qū)磁臂磁頭DisksparametersDiskparametersfortheoriginalIBMPCfloppydiskandaWesternDigitalWD18300harddisk磁盤性能概述-22.磁盤的邏輯組織一個物理磁盤在邏輯上可分為幾個區(qū)域，分區(qū)信息存放在主引導(dǎo)塊分區(qū)表中。分區(qū)表中保存磁盤各種分區(qū)起始和終止的磁頭、柱面、扇區(qū)、總的扇區(qū)數(shù)等信息。在主引導(dǎo)塊中有三種類型分區(qū)：主分區(qū)、擴展區(qū)和邏輯分區(qū)。主分區(qū)是常用的，加載一個操作系統(tǒng)所需文件安裝其上，操作系統(tǒng)必須從主分區(qū)上引導(dǎo)，一個硬盤上只能有四個主分區(qū)。為了突破四個分區(qū)的限制，就要在四個分區(qū)中創(chuàng)建立一個擴展分區(qū)。擴展分區(qū)其實是一個邏輯盤，它不能格式化，也不能分配盤符。但可在擴展分區(qū)中創(chuàng)建一個或多個邏輯分區(qū)，（或稱邏輯驅(qū)動器），每個邏輯分區(qū)分配一個盤符，可以格式化成一個特定的文件系統(tǒng)，MS-DOS、Windows98和WindowsNT可用fdisk命令將硬盤分區(qū)。5.4.2磁盤空閑塊管理和磁盤碎片整理

為了實現(xiàn)存儲空間的分配和回收，系統(tǒng)應(yīng)為存儲空間設(shè)置相應(yīng)的結(jié)構(gòu)以記住存儲空間的使用情況，并配以相應(yīng)算法方便地對存儲空間進(jìn)行分配和回收，下面介紹幾種常用的文件存儲空間管理方法。1.空閑表法空閑表法屬于連讀分配方法，它為外存上所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)一個空閑表項，其中包括序號、該空閑區(qū)的第一盤塊號，該區(qū)的空閑盤塊數(shù)等信息，再將所有空閑區(qū)按起始盤塊號遞增的次序排列。UNIXSV操作系統(tǒng)盤對換區(qū)空間管理采用空閑表法，它與內(nèi)存系統(tǒng)頁表管理采用同樣的數(shù)據(jù)結(jié)構(gòu)和分配回收算法。空閑表法的缺點是需要專用盤區(qū)來存放空閑表，在文件系統(tǒng)中較少采用連續(xù)分配。2。位示圖法

位示圖是利用二進(jìn)制的一位來表示磁盤中一個塊的作用情況，當(dāng)其值為0時表示對應(yīng)盤塊空閑；值為1時盤塊已分配。磁盤上所有盤塊都有一個二進(jìn)制位與之對應(yīng)，這樣，由所有盤塊所對應(yīng)的位形成了一個集合稱為位示圖，位示圖用磁盤塊存放，稱為位圖塊。例如：SCOUNIX操作系統(tǒng)盤塊大小為1KB，每個位圖塊有8192位，即每個位圖塊能管理8MB磁盤空間，要管理大的磁盤空間就需要多個位圖塊，這就需增設(shè)位圖索引塊，每個位圖塊塊號用4B記錄，這樣一個位圖索引塊可管理256個位圖塊，總共管理2GB大小磁盤空間。位示圖法-1位圖塊在管理的8192塊盤塊的最前面，位圖塊中第i個字節(jié)（i=0,1,……1023）的第j位(j=0,1……7)管理的塊在該圖塊后塊數(shù)為N＝i*8＋j。Windows2000、Linux等操作系統(tǒng)的盤塊管理都采用位示圖法。位示圖的主要優(yōu)點是位示圖描述能力強，位示圖較小，可以復(fù)制到內(nèi)存，使查找既方便又快速。很多計算機提供了位操作指令，使位示圖查找能夠高效進(jìn)行，能夠簡單有效地在盤上找到n個連續(xù)空閑塊。例如Intelx86微處理器系列就有這樣的指令：返回指定寄存器的所有位中值為1的第一位。SCOUNIX文件系統(tǒng)磁盤的結(jié)構(gòu)3?？臻e塊鏈接法

空閑塊鏈接法是將磁盤上所有空閑盤區(qū)鏈接在一個隊列中，稱為空閑塊鏈。請求分配時從鏈頭依次摘下適當(dāng)數(shù)目的空閑盤塊來分配，回收時將回收空閑盤塊鏈入空閑塊鏈尾部?？臻e塊鏈接法的優(yōu)點是不需專用塊存放管理信息，它的缺點是連續(xù)分配回收多塊空閑塊時需增加盤I/O操作?？臻e塊鏈接法結(jié)構(gòu)

空閑鏈表

空閑鏈頭塊塊號3

空閑鏈尾塊塊號20

8

16

10

20

／

物理塊號38161020

4。成組鏈接法

UNIXSV操作系統(tǒng)采用成組鏈接法管理磁盤空閑塊，該方法是空閑表法和空閑塊鏈接法的結(jié)合，具備分配回收方便，不需專用塊來存放分配表等優(yōu)點。成組鏈接法將磁盤空閑塊分成若干組，如將每100個盤塊作為一組，該組空閑塊總數(shù)和各空閑塊塊號存入下一組的第一個空閑塊中。最后不滿100塊的那組空閑塊總數(shù)和各空閑塊塊號記入磁盤區(qū)專用管理塊的空閑塊管理的數(shù)據(jù)結(jié)構(gòu)：s_nfree和s_free[100]中，如下圖所示。

P222圖5-11成組鏈接法