第12章文件系統(tǒng)的實(shí)現(xiàn)教師：計(jì)算機(jī)操作系統(tǒng)課程組E-mail:zhao.yanhong@163.com（趙艷紅）

wxzx@（沈峰）

安徽科技學(xué)院設(shè)計(jì)人:趙艷紅0Contents文件存儲(chǔ)設(shè)備磁盤(pán)空間管理文件分配方法目錄的實(shí)現(xiàn)GeekOS的文件系統(tǒng)1112.1文件存儲(chǔ)設(shè)備順序存取設(shè)備---磁帶只有當(dāng)?shù)趇塊物理塊被訪問(wèn)之后，才能對(duì)第i+1塊訪問(wèn)對(duì)某個(gè)特定物理塊的訪問(wèn)與該物理塊到磁頭當(dāng)前位置的距離有很大關(guān)系，遠(yuǎn)則移動(dòng)磁頭需要花費(fèi)很長(zhǎng)時(shí)間。優(yōu)點(diǎn)：容量大2212.1文件存儲(chǔ)設(shè)備直接存取設(shè)備----磁盤(pán)由多個(gè)磁盤(pán)片(platter)組成磁盤(pán)片的表面被邏輯地劃分為圓形磁道(track)磁道被劃分為固定長(zhǎng)度的單元，稱為扇區(qū)(sector)位于同一磁臂位置的磁道集合形成柱面(cylinder)性能：容量、傳輸速率、定位時(shí)間（＝尋道時(shí)間＋旋轉(zhuǎn)等待時(shí)間）3312.1文件存儲(chǔ)設(shè)備磁盤(pán)44磁盤(pán)相關(guān)的操作定位(seek)移動(dòng)磁臂到適當(dāng)?shù)闹?，所用時(shí)間稱為尋道時(shí)間。Read/Write一次只能讀/寫(xiě)一個(gè)扇區(qū)磁頭移到指定的扇區(qū)地址之前系統(tǒng)必須等待，所用時(shí)間稱為旋轉(zhuǎn)等待時(shí)間。操作系統(tǒng)必須跟蹤硬盤(pán)的物理地址用以實(shí)現(xiàn)文件系統(tǒng)。55磁盤(pán)相關(guān)的操作一塊硬盤(pán)由多個(gè)盤(pán)片組成。一個(gè)盤(pán)片對(duì)應(yīng)一個(gè)磁頭臂：兩個(gè)讀寫(xiě)磁頭對(duì)盤(pán)片上下頁(yè)進(jìn)行讀寫(xiě)。盤(pán)面上的同心圓稱為磁道。一個(gè)磁道被分割成大小相同的多個(gè)扇區(qū)。所有盤(pán)片中相同的磁道稱為柱面。IDE硬盤(pán)：扇區(qū)大小：512bit。通常情況：一個(gè)物理塊=？個(gè)扇區(qū)6612.2磁盤(pán)空間管理?一個(gè)長(zhǎng)度為n個(gè)字節(jié)的文件存儲(chǔ)在硬盤(pán)上時(shí)，如何分配存儲(chǔ)空間？方案1：把文件分配到n個(gè)字節(jié)的連續(xù)空閑磁盤(pán)空間。當(dāng)文件擴(kuò)大時(shí)，空閑空間不夠，就需要移到磁盤(pán)的另一個(gè)位置。方案2：把文件分割成多個(gè)塊，然后把它們存放在不同的磁盤(pán)塊中(各塊之間不必相鄰)。7712.2磁盤(pán)空間管理?塊的大小為多少呢？過(guò)大？如整個(gè)柱面為單位。過(guò)小？則一個(gè)文件將包含多個(gè)塊，每訪問(wèn)一個(gè)塊磁頭都要定位和旋轉(zhuǎn)延遲，文件的訪問(wèn)速度將很慢。實(shí)驗(yàn)表明：塊大小為4KB較好。Linux2.6:4KBGeekOS:4KB8812.2磁盤(pán)空間管理?如何管理空閑塊？方法1：空閑鏈表：使用一個(gè)鏈表，每個(gè)結(jié)點(diǎn)是一個(gè)磁盤(pán)塊，里面盡可能存放多的空閑磁盤(pán)塊號(hào)，另外每個(gè)結(jié)點(diǎn)還有指向下一個(gè)結(jié)點(diǎn)的指針。方法2：位示圖如果一個(gè)磁盤(pán)有N個(gè)塊，那么就需要N個(gè)位來(lái)描述。1：表示空閑，0：表示已分配(或相反)。Linux、GeekOS采用9912.2磁盤(pán)空間管理空閑鏈表法占用存儲(chǔ)空間比位示圖法多。101012.2磁盤(pán)空間管理采用空閑鏈表法，在內(nèi)存中只要保存一個(gè)結(jié)點(diǎn)。當(dāng)創(chuàng)建一個(gè)新文件時(shí)，所需要的磁盤(pán)塊就從這個(gè)結(jié)點(diǎn)中取。如果該結(jié)點(diǎn)中的空閑塊都已經(jīng)用完，就從鏈表中讀入一個(gè)新的結(jié)點(diǎn)。類(lèi)似地，當(dāng)一個(gè)文件被刪除后，它的磁盤(pán)塊就被釋放并添加到內(nèi)存中的鏈表結(jié)點(diǎn)中，如果該結(jié)點(diǎn)裝滿，就把它寫(xiě)回磁盤(pán)。111112.3文件分配方法?如何為文件分配存儲(chǔ)空間，以便有效使用磁盤(pán)空間和快速訪問(wèn)文件？方法：連續(xù)分配、鏈表分配、帶有文件分配表的鏈表結(jié)構(gòu)、索引節(jié)點(diǎn)121212.3.1連續(xù)分配(ContiguousAllocation)把每個(gè)文件存放在連續(xù)的磁盤(pán)數(shù)據(jù)塊中。例如，如果磁盤(pán)數(shù)據(jù)塊大小為4KB，則一個(gè)40KB的文件就需要10個(gè)連續(xù)的磁盤(pán)塊。131312.3.1連續(xù)分配(ContiguousAllocation)當(dāng)前應(yīng)用：CD-ROM、DVD等一次性寫(xiě)入的光學(xué)存儲(chǔ)介質(zhì)領(lǐng)域。優(yōu)點(diǎn)：簡(jiǎn)單、易實(shí)現(xiàn)缺點(diǎn)：外碎片(指比較小、沒(méi)有辦法再利用的多個(gè)連續(xù)空閑塊)141412.3.2鏈接分配(LinkedAllocation)為每個(gè)文件構(gòu)造一條磁盤(pán)塊鏈表。每個(gè)塊的每個(gè)字作為指向下一塊的指針，塊的其余部分則用來(lái)存放數(shù)據(jù)。151512.3.2鏈接分配(LinkedAllocation)161612.3.2鏈接分配(LinkedAllocation)優(yōu)點(diǎn)：每一個(gè)磁盤(pán)塊都被利用(不會(huì)有外碎片，但可能有內(nèi)碎片)、目錄項(xiàng)中只需存放第一個(gè)塊的磁盤(pán)地址。缺點(diǎn)：不利用隨機(jī)訪問(wèn)、指針要占用字節(jié)。171712.3.2帶有文件分配表的鏈表結(jié)構(gòu)帶有文件分配表的鏈表結(jié)構(gòu)(LinkedListwithFileAllocationTable)在鏈表的基礎(chǔ)上進(jìn)行改進(jìn)，把每一個(gè)磁盤(pán)塊中的鏈表指針單獨(dú)抽取出來(lái)，單獨(dú)組成一個(gè)表格，放在內(nèi)存中，這個(gè)表格稱為文件分配表。標(biāo)志0表示結(jié)束。如DOS、Windows98181812.3.2帶有文件分配表的鏈表結(jié)構(gòu)優(yōu)點(diǎn)：容易隨機(jī)訪問(wèn)、整個(gè)鏈表都在內(nèi)存中遍歷速度較塊、目錄項(xiàng)中只需存放第一個(gè)塊的磁盤(pán)地址缺點(diǎn)：整個(gè)表都必須位于內(nèi)存中。如果一個(gè)20GB的磁盤(pán)，塊大小為1KB，則FAT表項(xiàng)就需要2000萬(wàn)個(gè)，若每個(gè)表項(xiàng)占4字節(jié)，則整個(gè)表占內(nèi)存80MB。191912.3.3索引分配索引節(jié)點(diǎn)(index-node)給每個(gè)文件賦予一個(gè)數(shù)據(jù)結(jié)構(gòu)，稱為索引節(jié)點(diǎn)或i節(jié)點(diǎn)，里面列出文件的屬性和各個(gè)數(shù)據(jù)塊的磁盤(pán)地址。當(dāng)一個(gè)文件被打開(kāi)時(shí)，才把它的i節(jié)點(diǎn)讀入內(nèi)存，如果一個(gè)節(jié)點(diǎn)占用n個(gè)字節(jié)，且最多只能同時(shí)打開(kāi)k個(gè)文件，則存放節(jié)點(diǎn)的空間是nk個(gè)字節(jié)，與磁盤(pán)的容量無(wú)關(guān)。而FAT不同，它與磁盤(pán)容量成正比。如Linux、GeekOS202012.3.3索引分配?如果每個(gè)i節(jié)點(diǎn)能夠存放的磁盤(pán)地址個(gè)數(shù)是有限的，那么如果文件太大，超出這個(gè)限制怎么辦？

……屬性i節(jié)點(diǎn)磁盤(pán)地址磁盤(pán)塊2121最后一些磁盤(pán)地址不是指向數(shù)據(jù)塊，而是指向一個(gè)間接塊，此間接塊存放更多的磁盤(pán)塊地址。下圖是一個(gè)具有三級(jí)間接塊的i節(jié)點(diǎn)。222212.4目錄的實(shí)現(xiàn)打開(kāi)一個(gè)文件：需要根據(jù)路徑名找目錄項(xiàng)需要定位根目錄：位于磁盤(pán)分區(qū)中的某個(gè)固定位置，Unix中此位置是超級(jí)塊。目錄項(xiàng)提供了查找磁盤(pán)塊所需要的信息整個(gè)文件的磁盤(pán)地址(連續(xù)分配)第一個(gè)磁盤(pán)塊的地址(鏈表分配)i節(jié)點(diǎn)(索引節(jié)點(diǎn)方式分配)232312.4目錄的實(shí)現(xiàn)哪兒存放文件的屬性信息？把文件屬性直接放在目錄項(xiàng)中一個(gè)目錄由一組固定長(zhǎng)度的目錄項(xiàng)組成，一個(gè)存放一個(gè)文件，在每個(gè)目錄項(xiàng)中包含文件名、屬性及此文件對(duì)應(yīng)的磁盤(pán)塊地址。如圖a。針對(duì)使用i節(jié)點(diǎn)的系統(tǒng)，把文件屬性存放在i節(jié)點(diǎn)中,如圖b。圖a圖b2424Linux中的目錄Unix中的目錄項(xiàng)如圖所示。當(dāng)一個(gè)文件被打開(kāi)時(shí)，文件系統(tǒng)根據(jù)用戶給定的文件名，找到相應(yīng)的磁盤(pán)塊。示例：如何找/usr/ast/mbox的？首先找根目錄，此目錄通過(guò)超級(jí)塊可以找到。然后，找usr。2525262612.5GeekOS的文件系統(tǒng)保存測(cè)試用的用戶可執(zhí)行程序我們需要實(shí)現(xiàn)的文件系統(tǒng)272712.5.1VFS(虛擬文件系統(tǒng))將各種具體文件系統(tǒng)的基本操作抽象出來(lái)、組織在一起，從而形成系統(tǒng)調(diào)用與實(shí)際文件系統(tǒng)之間的中間層。使一個(gè)操作系統(tǒng)可以使用多種文件系統(tǒng)成為可能。282812.5.2高速緩沖區(qū)用于保存磁盤(pán)塊數(shù)據(jù)的內(nèi)存區(qū)，是一個(gè)虛擬磁盤(pán)。緩沖塊大小與磁盤(pán)塊大小一樣：4KB文件系統(tǒng)進(jìn)行磁盤(pán)操作時(shí)，首先檢查所需磁盤(pán)塊是否已經(jīng)在高速緩沖區(qū)中，如果在，就直接在內(nèi)存上進(jìn)行塊操作，如果不在，則向塊設(shè)備提出磁盤(pán)訪問(wèn)請(qǐng)求，讀入所需磁盤(pán)塊。文件系統(tǒng)高速緩沖區(qū)塊設(shè)備請(qǐng)求處理機(jī)制磁盤(pán)292912.5.3GOSFS文件系統(tǒng)結(jié)構(gòu)支持多級(jí)目錄、長(zhǎng)文件名。提供文件與目錄的創(chuàng)建、刪除等基本操作。文件系統(tǒng)駐留在Ide1硬盤(pán)上，大小：10MB。磁盤(pán)塊：4KB3030(1)GOSFS的布局3131(1)GOSFS的布局第0塊(超級(jí)塊)Magic:4Byte,是具體的文件系統(tǒng)標(biāo)識(shí)

RootDirPointer:根目錄的磁盤(pán)塊號(hào)，Size:磁盤(pán)大小FreeBlocksBitmap:1024*8位，每一位對(duì)應(yīng)一個(gè)4KB的磁盤(pán)塊。1024*8*4KB=32MB.磁盤(pán)格式化：系統(tǒng)根據(jù)磁盤(pán)容量計(jì)算出磁盤(pán)塊數(shù)，然后計(jì)算位圖大小并將位圖中對(duì)應(yīng)的位設(shè)置為空，然后創(chuàng)建根目錄，并使RootDirPointer指向它，將相關(guān)數(shù)據(jù)填入超級(jí)塊，并將根目錄使用的磁盤(pán)塊在位圖對(duì)應(yīng)位置標(biāo)記為使用，最后填寫(xiě)magic。除第0塊之外，其它磁盤(pán)塊用于存放文件和目錄。3232(2)文件與目錄將目錄作為特殊的文件進(jìn)行管理，目錄項(xiàng)（即文件控制塊）定義如下：

struct

GOSFS_Dir_Entry{

ulong_tsize;

ulong_tflags; charfilename[128];

ulong_tblockList[10];

struct

VFS_ACL_Entryacl10};3333(2)文件與目錄GOSFS_Dir_Entryfilename[128]flagssizeacl[10]blockList[10]目錄項(xiàng)GOSFS_Dir_EntryGOSFS_Dir_EntryGOSFS_Dir_EntryGOSFS_Dir_EntryGOSFS_Dir_EntryGOSFS_Dir_EntryGOSFS_Dir_Entry目錄

數(shù)據(jù)塊數(shù)據(jù)塊3434Datastorage–DirectMapping01234567894KBdatablockGOSFS_Dir_Entry.blockList[10]4KBdatablock4KBdatablockDISK=used長(zhǎng)度12KB的文件3535Datastorage–SingleIndirect4KBdatablock4KBdatablock4KBdatablockDISK0123456789001234...1022102304KBdatablock4KBdatablock長(zhǎng)度40KB

的文件singleindirectblock….GOSFS_Dir_Entry.blockList[10]3636Datastorage–DoubleIndirect4KBdatablock4KBdatablock4KBdatablockDISK012345678904KBdatab