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

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

wxzx@（沈峰）

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

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

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

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]目錄項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長度12KB的文件3535Datastorage–SingleIndirect4KBdatablock4KBdatablock4KBdatablockDISK0123456789001234...1022102304KBdatablock4KBdatablock長度40KB

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