模擬Linux文件系統(tǒng)

1、設計五：設計任務：模擬linux文件系統(tǒng)。在任一os下，建立一個大文件，把它假象成一張盤，在其中實現(xiàn)一個簡單的 模擬linux文件系統(tǒng) 。1. 在現(xiàn)有機器硬盤上開辟20m的硬盤空間，作為設定的硬盤空間。2. 編寫一管理程序?qū)Υ丝臻g進行管理，以模擬linux文件系統(tǒng)，具體要求如下：（1） 要求盤塊大小1k 正規(guī)文件 (2) i 結(jié)點文件類型 目錄文件 (共1byte) 塊設備 管道文件 。物理地址（索引表） 共有13個表項，每表項2byte 。文件長度 4byte 。聯(lián)結(jié)計數(shù) 1byte （3）0號塊 超級塊 棧長度50 空閑盤塊的管理：成組鏈接 ( unix) 位示圖法 (linux) （4）

2、每建一個目錄，分配4個物理塊 文件名 14byte （5）目錄項信息 i 結(jié)點號 2byte(6)結(jié)構： 0#： 超級塊 1#20#號為 i 結(jié)點區(qū) 20#30#號為根目錄區(qū)3. 該管理程序的功能要求如下：(1) 能夠顯示整個系統(tǒng)信息，源文件可以進行讀寫保護。目錄名和文件名支持全路徑名和相對路徑名，路徑名各分量間用“/”隔開。(2) 改變目錄：改變當前工作目錄，目錄不存在時給出出錯信息。(3) 顯示目錄：顯示指定目錄下或當前目錄下的信息，包括文件名、物理地址、保護碼、文件長度、子目錄等（帶/s參數(shù)的dir命令，顯示所有子目錄）。(4) 創(chuàng)建目錄：在指定路徑或當前路徑下創(chuàng)建指定目錄。重名時給出錯

3、信息。(5) 刪除目錄：刪除指定目錄下所有文件和子目錄。要刪目錄不空時，要給出提示是否要刪除。(6) 建立文件（需給出文件名，文件長度）。(7) 打開文件（顯示文件所占的盤塊）。(8) 刪除文件：刪除指定文件，不存在時給出出錯信息。4. 程序的總體流程為：(1) 初始化文件目錄；(2) 輸出提示符，等待接受命令，分析鍵入的命令；(3) 對合法的命令，執(zhí)行相應的處理程序，否則輸出錯誤信息，繼續(xù)等待新命令，直到鍵入exit退出為止。一 程序清單頭文件block.h, command.h, disk.h, fd.h, inode.h, shell.hc文件block.c, command.c, di

4、sk.c, fd.c, inode.c, shell.c具體程序清單見源代碼，在此不一一列出。二 概要設計 2.1 文件系統(tǒng)組織結(jié)構super inodesdata blocks 1024b30*1024b磁盤塊以組的形式鏈接起來(1)第一個磁盤塊：寫入超級塊(2)從第二個磁盤塊開始：用30個磁盤塊記inodes(3)剩下的磁盤塊作為數(shù)據(jù)塊data blocksdata blocks是由多個磁盤塊組構成，每個棧的開始磁盤塊用于記錄空閑塊棧，因為本實驗是采用unix的空閑盤塊管理方法，即成組鏈接法。每一組用一個棧表示，里面存放空閑塊的磁盤塊號。剩下的磁盤塊都作為文件的數(shù)據(jù)塊，記錄文件或目錄的內(nèi)容

5、。2.2 系統(tǒng)流程圖2.2.1 系統(tǒng)框架-main()創(chuàng)建大小20m的文件作盤并格式化文件系統(tǒng)創(chuàng)建根目錄，初始化文件系統(tǒng)運行shell，接受命令并執(zhí)行相關動作2.2.2 格式化文件系統(tǒng)流程-int fs_format(file *fp)鏈接空閑磁盤塊，生成空閑磁盤塊棧初始化超級塊的數(shù)據(jù)，包括空閑inode棧開辟inodes空間開辟data blocks空間2.2.3 shell運行流程-void shell( file *fp, int *pd_ind_no)找印幫助信息轉(zhuǎn)到當前目錄用戶輸入命令解析命令，并轉(zhuǎn)去執(zhí)行相應函數(shù)是否退出退出程序是否echo回應功能help幫助功能mkfile創(chuàng)建文件

6、mkdir創(chuàng)建目錄ls顯示目錄內(nèi)容date顯示日期cd改變目錄status顯示狀態(tài) rm刪除文件/目錄 rn文件重命名psw顯示當前路徑open打開文件2.2.4 相關功能實現(xiàn)流程（1）創(chuàng)建目錄int create_fd( file *fp, int dir_ind_no, const char *file, const char given_type, const char *f_size)這里given_type =”d”表示目錄，f_size默認為0.分配inode號找到當前目錄所在的inode結(jié)點，把（文件名，inode號）表項加入該目錄記錄的inode索引表，并修改目錄大小更新ino

7、de內(nèi)容。在新建的目錄下建”.”和”.”目錄，初始化新目錄下的inode索引表（2）創(chuàng)建文件int create_fd( file *fp, int dir_ind_no, const char *file, const char given_type, const char *f_size)這里given_type =”f”表示目錄，f_size默認為0，也可以是用戶輸入的創(chuàng)建文件大小分配inode號找到當前目錄所在的inode結(jié)點，把（文件名，inode號）表項加入該目錄記錄的inode索引表，并修改目錄大小更新inode內(nèi)容。按照文件大小分配磁盤塊，在inode里的磁盤地址記錄磁盤塊號（

8、3）顯示目錄內(nèi)容- void list_dir( file *fp, int dir_ind_no)找到當前目錄的inode，讀取該目錄下的inode索引表根據(jù)索引表的表項找到相應inode，讀取inode內(nèi)容，并顯示。列出文件/目錄所占的磁盤塊表結(jié)束？否是退出（4） 改變目錄-int cd_path( file *fp, int *pd_ind_no, char *given_path)以/分隔路徑每次打開一級目錄，如果不是目錄則出錯路徑結(jié)束？否是退出（5）顯示狀態(tài)-void status( file *fp)讀取超級塊信息羅列超級塊信息讀取當前空閑塊棧里未分配的空閑塊號，并逐個輸出（6）刪

9、除文件/目錄-int remove_fd( file *fp, int dir_ind_no, const char *file)在當前目錄的inode索引表中找到文件/目錄名相同的項，刪去更新當前目錄的inode信息釋放文件/目錄占用的磁盤塊有子目錄/文件？如果是目錄退出否是對該目錄下的所有子目錄和文件（7）文件重命名-void re_name( file *fp, int dir_ind_no, char *f1, char *f2)在當前目錄的inode索引表中找到文件/目錄名相同的項修改該表項中的文件/目錄名字寫回該inode索引表項（8）顯示當前路徑-void pwd( file *

10、fp, int *pd_ind_no, char *path)找到上一級目錄記錄已擴展的路徑名否是退出是根目錄？（9）打開文件-void open_file(file*fp,int dir_ind_no,char* file)找到文件所在inode讀取inode記錄的文件大小列出文件所占的磁盤塊三 詳細設計3.1 系統(tǒng)定義#define disk_size 1024*1024*20/磁盤大小為20m#define block_size 1024/每個磁盤塊1024b#define inode_table_blocks 30/用30個磁盤塊來存儲inodes#define stack_max 5

11、0/inode空閑棧和空閑磁盤塊棧的大小均為50/尋找磁盤塊號對應的磁盤塊在文件系統(tǒng)中的地址#define seek_blk(blk_no) block_size*(inode_table_blocks + 1 + blk_no)/尋找inode號為x的inode在文件系統(tǒng)中的地址#define inode_offset(x) (block_size + (x)*sizeof(struct fs_inode)#define name_len 14 /文件名最大長度#define path_len 100 /路徑名最大長度3.2 主要數(shù)據(jù)結(jié)構/超級塊結(jié)構struct fs_super int t

12、otal_block_count;/* total block count */ int free_block_stackstack_max+1; /* free block stack */ int free_block_count;/* current free block quantity */ int free_inode_stackstack_max+1; /* free inode stack */ int free_inode_count;/* current free inode quantity */ int remembered_inode;/* the last unre

13、gister inode pos */;/inode結(jié)構struct fs_inode char user15;/用戶名 char type;/文件類型，分為一般文件和目錄文件 unsigned links;/文件聯(lián)結(jié)數(shù) int size;/文件大小 int addr13;/磁盤塊索引;/表示i-node表中的一項struct fd_entry char namename_len;/ 文件或目錄名 int inode_no;/ inode號 ;3.3 系統(tǒng)結(jié)構和管理3.3.1空閑磁盤塊管理采用成組鏈接法管理空閑塊每一組存入50個磁盤塊號，并用一個當前索引記錄當前分配塊號所在組中的位置，以便下次

14、分配時只要移動一個位置就可以獲得新分配的塊號。 。 。（1）分配一個空閑磁盤塊號，返回一個磁盤塊號int get_blk(file *fp) 獲取當前空閑塊組的索引值，即指向空閑塊組的第幾個索引讀取當前索引值存放的磁盤塊號空閑塊數(shù)目少1如果棧滿并且還有空閑塊，重新載入新的空閑塊組到超級塊中空閑棧作為當前空閑組返回當前磁盤塊號作為分配的磁盤塊號（2）釋放一個磁盤塊，使該磁盤塊號恢復自由分配權int free_blk(file *fp, int blk_no)把剛釋放的磁盤塊號加到當前空閑棧頂，并修改當前空閑棧的索引指針即stack0的值 如果當前空閑棧滿，重新從前面開始生成一個空閑組覆蓋原來已經(jīng)

15、完全使用的舊的空閑棧并存入釋放的磁盤塊號空閑塊加1更新超級塊的當前空閑棧3.3.2 空閑inode管理空閑inode是通過超級塊中的int free_inode_stackstack_max+1和int remembered_inode來管理的。將部分空閑的inode構成部分空閑inode表，放入超級塊中，每交該部分的空閑塊用完后重新載入另一部分空閑塊。正常情況下，remembered_inode每次記住該組inode號用完后，下次可以分配的最小inode號，可以是下一組inode的最小inode號，也可以是釋放的inode中最小的。（1）分配inode每次分配inode時，如果超級塊中的空閑

16、索引節(jié)點表不空，就從該空閑索引節(jié)點表中從棧頂取一個分配并將當前索引即棧頂指針向下移，讀出該磁盤索引節(jié)點。如果超級塊中的空閑索引節(jié)點表為空，則從銘記節(jié)點開始向后（從低序號向高序號）查找空閑索引節(jié)點，并把它們登記到超級塊的空閑索引節(jié)點表中，直到超級塊的空閑節(jié)點表滿為止，并設置銘記節(jié)點為搜索到的最后一個空閑節(jié)點號。銘記節(jié)點是用來紀錄下一次搜索空閑索引節(jié)點的起始位置，銘記節(jié)點前的索引節(jié)點都是已經(jīng)分配了的，所以每 次搜索只要從銘記節(jié)點開始?？臻einode表50inode號49inode號48inode號47inode號。3inode號2inode號1inode號0當前索引（2）釋放inode在釋放索引節(jié)

17、點時，如果當前空閑inode表已分配過inodes，那么把釋放的節(jié)點號加進空閑節(jié)點表的棧頂。如果當前空閑inode表已滿，則不能加入棧頂。這時要看該索引節(jié)點號是否大于銘記節(jié)點號，大于則直接釋放該索引節(jié)點，小于則在釋放后要將銘記節(jié)點號改成剛釋放的索引節(jié)點號。3.3.3 文件的結(jié)構（文件所占磁盤塊號的組織）一個文件/目錄對應一個inode，在inode中以int addr13記錄文件磁盤塊索引由于考慮到存放足夠大的文件，我采用了多級間接地址，分為索引節(jié)點inode包含文件數(shù)據(jù)的磁盤地址明細表，它指出文件數(shù)據(jù)在磁盤上的存儲位置。系統(tǒng)在磁盤上給文件分配空間時，并不一定需 要連續(xù)的空間來存放文件。核心有

18、較大的靈活性，一次分配一塊文件空間，并且允許文件數(shù)據(jù)分布在整個文件系統(tǒng)中，這樣沒有了造成碎片的風險，每個文件浪費的 空間最多不到一個數(shù)據(jù)塊。但是這樣導致了文件數(shù)據(jù)讀取時，數(shù)據(jù)定位的復雜程度。另外，一個索引節(jié)點的大小時固定的，也就是說，索引節(jié)點包含文件數(shù)據(jù)的磁盤 地址明細表的大小時固定的，當一個文件較大時，索引節(jié)點中的磁盤地址明細表就不夠放。這樣就有幾種解決辦法，一種是加大inode的大小，但這樣浪費磁盤 空間。二種是限制文件大小，這是一種不可取的方法。我采用的是unix的解決辦法在inode的磁盤地址明細表中前若干項是直接指向磁盤數(shù)據(jù)所在塊的塊號，前10項為直接塊號。隨后的三項分別是一次間接、

19、二次間接和三次間接。一次間接是指該項存放的磁盤塊號所指向的 磁盤數(shù)據(jù)塊的內(nèi)容是若干數(shù)據(jù)塊的磁盤塊號，即從該項得到數(shù)據(jù)塊號，由此可得數(shù)據(jù)塊的內(nèi)容，而數(shù)據(jù)塊的內(nèi)容是一張磁盤塊號表，每一項地址指向一個數(shù)據(jù)塊。二 次間接是指該項存放的磁盤塊號所指向的數(shù)據(jù)塊的內(nèi)容是一張磁盤塊號表，而由該磁盤塊號表得到的數(shù)據(jù)塊的內(nèi)容仍然是一張磁盤塊號表，再由該表得到的數(shù)據(jù)塊才 是文件的數(shù)據(jù)。三次間接以此類推。該結(jié)構可由圖1-1說明。雖然從邏輯上還可以做四次間接，但實際上不需要這樣，現(xiàn)在的結(jié)構已經(jīng)足夠， 它可以使文件的最大長度達到(10+1*256+1*256*256+1*256*256*256)*1k=16843018k

20、（當一個塊的大小是 1024bytes，磁盤塊號為32bits時），而在索引節(jié)點中文件長度是由一個32bits的字段存放的，所以文件最大長度不能超過4g。假設文件系統(tǒng)中一個塊（block）的大小為1024bytes，那么對一個大小不超過10k的文件的存放是由直接塊號表得到數(shù)據(jù)塊的塊號，數(shù)據(jù)定位不復 雜。而對一個大小超過10k的文件來說，前10k可以從直接塊號表得到磁盤塊號，但后面的數(shù)據(jù)就要先讀入一個一次間接塊的內(nèi)容，再去讀數(shù)據(jù)，對磁盤操作稍 有影響。3.3.4 目錄目錄是一種文件，起到文件名到索引節(jié)點號之間轉(zhuǎn)換的橋梁作用，也是使得文件系統(tǒng)成為樹狀結(jié)構的關鍵。目錄文件的內(nèi)容是由一系列的目錄登記項

21、構成，每項由該目錄包含的一個文件名及該文件的索引節(jié)點號兩部分組成。目錄登記項一般含有以下幾個字段：文件名：文件名的長度為14個字符索引節(jié)點號：該字段指出本目錄中該文件名所對應的索引節(jié)點號。每個目錄文件的前兩項是兩個特殊文件“”和“”，其中“”表示當前目錄自身，對應“”文件的索引節(jié)點號就是該 目錄文件的索引節(jié)點號。文件“”表示上級目錄，即對應“”的索引節(jié)點號是當前目錄的父目錄的索引節(jié)點號。“”是一個比較特殊的目錄，稱為根目 錄。該目錄是在mkfs程序生成文件系統(tǒng)時產(chǎn)生的目錄，該目錄文件的“”和“”對應的索引節(jié)點號是“”目錄自身的索引節(jié)點號。在一個文件操作中我們常用路徑名來指出文件所在的位置，路徑

22、名第一個字符為“”時，我們稱這個路徑是絕對路徑，即該路 徑從根目錄開始指出文件的位置。路徑名以“”為分隔符，區(qū)分各目錄層次。最后一個分量可以是目錄，也可以是文件名。當路徑名不是以“”為第一個字符 時，我們稱這個路徑是相對路徑，即該路徑從當前目錄指出文件所在的位置。系統(tǒng)對目錄文件數(shù)據(jù)存儲的操作與普通文件一樣，也使用inode來保存目錄文件的信息及存儲的磁盤塊號。目錄文件的讀權 限表示進程可以讀取這個目錄，寫權限表示進程可以創(chuàng)建或撤銷目錄登記項（通過creat、mknod等），執(zhí)行權限表示進程可以搜索這個目錄。核心在目錄 樹中找一個文件的索引節(jié)點的過程，是一個轉(zhuǎn)換過程。核心內(nèi)部對文件都是用索引節(jié)點

23、來操作的，這就是說必須有一個路徑名到索引節(jié)點的轉(zhuǎn)換過程。對于一個絕對 路徑來說，就是從根目錄起，在根目錄文件中尋找路徑名的下一個分量所對應的索引節(jié)點，再從索引節(jié)點找到磁盤數(shù)據(jù)塊，如此循環(huán)直到搜索完畢為止。對于一個相 對路徑，就是在當前目錄文件中尋找下一個分量所對應的索引節(jié)點。對于路徑名中跨越安裝點的問題將在1.3.11節(jié)中討論。舉例來說，要打開/etc/passwd文件，系統(tǒng)先讀取根目錄文件在該文件中找到目錄登記項中文件名是etc的項，并 由此得到etc的索引節(jié)點號，由索引節(jié)點找到etc目錄文件。在讀入etc目錄文件后，查找文件名為passwd的目錄登記項，并得到索引節(jié)點，這時可以 打開該文件

24、了。對于一個相對路徑來說，要打開././etc/passwd文件，首先根據(jù)當前工作目錄，得到該目錄文件，并可以查找其父目錄的索引節(jié) 點號，重復查找過程，即可得到該文件的索引節(jié)點。最后要注意的是，一個目錄文件的目錄登記項中，如果文件名存在，而索引節(jié)點號為0，表示該文件在這個目錄 存在過，現(xiàn)在不存在（已經(jīng)被刪除了）。文件名inode號.num1.num2file1num3filennumn3.4 相關算法實現(xiàn)（1）創(chuàng)建文件時為文件分配磁盤塊創(chuàng)建文件時，為文件分配磁盤塊，每次分配一個磁盤塊，直到滿足用戶要求的文件大小為止。每一次為文件分配一個磁盤塊都要記錄進inode的磁盤地址明細表。具體算法如下：

25、int alc_blk( file *fp, int ind_no)分配一個空閑磁盤塊，返回磁盤塊號讀出inode中記錄的文件已分配大小if（已分配大小= direct）直接把新塊號寫進下一直接地址addri中else if（已分配大小= single）如果是第一次超過直接地址，則分配一磁盤塊作為間接地址表把新塊號寫進間接地址表的下一表項else if（已分配大小= double）如果是第一次超過間接地址，則分配一磁盤塊作為二級間接地址表檢查是否需要新的二級地址表，如果是則分配一磁盤塊作為新的二級地址表，把二級地址表的塊號記錄進一級地址表把新塊號寫進當前二級地址表的下一表項else /* triple */如果是第一次超過二級間接地址，則分配一磁盤塊作為三級間接地址表檢查是否需要新的二級地址表，如果是則分配一磁盤塊作為新的二級地址表把二級地址表的塊號記錄進一級地址表檢查是否需要新的三級地址表，如果是則分配一磁盤塊作為新的三級地址表把三級地址表的塊號記錄進二級地址表把新塊號寫進當前三級地址表的下一表項（2）刪除文件/目錄int remove_fd( file *fp, int dir_ind_no, const char *file)在當前目錄的inode索引表中找到文件/目錄名相同的項，刪去更新當前目錄的inode信息釋放