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

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

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

3、信息。(5) 刪除目錄：刪除指定目錄下所有文件和子目錄。要?jiǎng)h目錄不空時(shí)，要給出提示是否要?jiǎng)h除。(6) 建立文件（需給出文件名，文件長度）。(7) 打開文件（顯示文件所占的盤塊）。(8) 刪除文件：刪除指定文件，不存在時(shí)給出出錯(cuò)信息。4. 程序的總體流程為：(1) 初始化文件目錄；(2) 輸出提示符，等待接受命令，分析鍵入的命令；(3) 對合法的命令，執(zhí)行相應(yīng)的處理程序，否則輸出錯(cuò)誤信息，繼續(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具體程序清單見源代碼，在此不一一列出。二 概要設(shè)計(jì) 2.1 文件系統(tǒng)組織結(jié)構(gòu)super inodesdata blocks 1024b30*1024b磁盤塊以組的形式鏈接起來(1)第一個(gè)磁盤塊：寫入超級塊(2)從第二個(gè)磁盤塊開始：用30個(gè)磁盤塊記inodes(3)剩下的磁盤塊作為數(shù)據(jù)塊data blocksdata blocks是由多個(gè)磁盤塊組構(gòu)成，每個(gè)棧的開始磁盤塊用于記錄空閑塊棧，因?yàn)楸緦?shí)驗(yàn)是采用unix的空閑盤塊管理方法，即成組鏈接法。每一組用一個(gè)棧表示，里面存放空閑塊的磁盤塊號。剩下的磁盤塊都作為文件的數(shù)據(jù)塊，記錄文件或目錄的內(nèi)容

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

6、mkdir創(chuàng)建目錄ls顯示目錄內(nèi)容date顯示日期cd改變目錄status顯示狀態(tài) rm刪除文件/目錄 rn文件重命名psw顯示當(dāng)前路徑open打開文件2.2.4 相關(guān)功能實(shí)現(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默認(rèn)為0.分配inode號找到當(dāng)前目錄所在的inode結(jié)點(diǎn)，把（文件名，inode號）表項(xiàng)加入該目錄記錄的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默認(rèn)為0，也可以是用戶輸入的創(chuàng)建文件大小分配inode號找到當(dāng)前目錄所在的inode結(jié)點(diǎn)，把（文件名，inode號）表項(xiàng)加入該目錄記錄的inode索引表，并修改目錄大小更新inode內(nèi)容。按照文件大小分配磁盤塊，在inode里的磁盤地址記錄磁盤塊號（

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

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

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

11、0/inode空閑棧和空閑磁盤塊棧的大小均為50/尋找磁盤塊號對應(yīng)的磁盤塊在文件系統(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é)構(gòu)/超級塊結(jié)構(gòu)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é)構(gòu)struct fs_inode char user15;/用戶名 char type;/文件類型，分為一般文件和目錄文件 unsigned links;/文件聯(lián)結(jié)數(shù) int size;/文件大小 int addr13;/磁盤塊索引;/表示i-node表中的一項(xiàng)struct fd_entry char namename_len;/ 文件或目錄名 int inode_no;/ inode號 ;3.3 系統(tǒng)結(jié)構(gòu)和管理3.3.1空閑磁盤塊管理采用成組鏈接法管理空閑塊每一組存入50個(gè)磁盤塊號，并用一個(gè)當(dāng)前索引記錄當(dāng)前分配塊號所在組中的位置，以便下次

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

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

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

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

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

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

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

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

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

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

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

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