模拟Linux文件系统

1、设计五：设计任务：模拟linux文件系统。在任一os下，建立一个大文件，把它假象成一张盘，在其中实现一个简单的 模拟linux文件系统 。1. 在现有机器硬盘上开辟20m的硬盘空间，作为设定的硬盘空间。2. 编写一管理程序对此空间进行管理，以模拟linux文件系统，具体要求如下：（1） 要求盘块大小1k 正规文件 (2) i 结点文件类型 目录文件 (共1byte) 块设备 管道文件 。物理地址（索引表） 共有13个表项，每表项2byte 。文件长度 4byte 。联结计数 1byte （3）0号块 超级块 栈长度50 空闲盘块的管理：成组链接 ( unix) 位示图法 (linux) （4）

2、每建一个目录，分配4个物理块 文件名 14byte （5）目录项信息 i 结点号 2byte(6)结构： 0#： 超级块 1#20#号为 i 结点区 20#30#号为根目录区3. 该管理程序的功能要求如下：(1) 能够显示整个系统信息，源文件可以进行读写保护。目录名和文件名支持全路径名和相对路径名，路径名各分量间用“/”隔开。(2) 改变目录：改变当前工作目录，目录不存在时给出出错信息。(3) 显示目录：显示指定目录下或当前目录下的信息，包括文件名、物理地址、保护码、文件长度、子目录等（带/s参数的dir命令，显示所有子目录）。(4) 创建目录：在指定路径或当前路径下创建指定目录。重名时给出错

3、信息。(5) 删除目录：删除指定目录下所有文件和子目录。要删目录不空时，要给出提示是否要删除。(6) 建立文件（需给出文件名，文件长度）。(7) 打开文件（显示文件所占的盘块）。(8) 删除文件：删除指定文件，不存在时给出出错信息。4. 程序的总体流程为：(1) 初始化文件目录；(2) 输出提示符，等待接受命令，分析键入的命令；(3) 对合法的命令，执行相应的处理程序，否则输出错误信息，继续等待新命令，直到键入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 文件系统组织结构super inodesdata blocks 1024b30*1024b磁盘块以组的形式链接起来(1)第一个磁盘块：写入超级块(2)从第二个磁盘块开始：用30个磁盘块记inodes(3)剩下的磁盘块作为数据块data blocksdata blocks是由多个磁盘块组构成，每个栈的开始磁盘块用于记录空闲块栈，因为本实验是采用unix的空闲盘块管理方法，即成组链接法。每一组用一个栈表示，里面存放空闲块的磁盘块号。剩下的磁盘块都作为文件的数据块，记录文件或目录的内容

5、。2.2 系统流程图2.2.1 系统框架-main()创建大小20m的文件作盘并格式化文件系统创建根目录，初始化文件系统运行shell，接受命令并执行相关动作2.2.2 格式化文件系统流程-int fs_format(file *fp)链接空闲磁盘块，生成空闲磁盘块栈初始化超级块的数据，包括空闲inode栈开辟inodes空间开辟data blocks空间2.2.3 shell运行流程-void shell( file *fp, int *pd_ind_no)找印帮助信息转到当前目录用户输入命令解析命令，并转去执行相应函数是否退出退出程序是否echo回应功能help帮助功能mkfile创建文件

6、mkdir创建目录ls显示目录内容date显示日期cd改变目录status显示状态 rm删除文件/目录 rn文件重命名psw显示当前路径open打开文件2.2.4 相关功能实现流程（1）创建目录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结点，把（文件名，inode号）表项加入该目录记录的inode索引表，并修改目录大小更新ino

7、de内容。在新建的目录下建”.”和”.”目录，初始化新目录下的inode索引表（2）创建文件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，也可以是用户输入的创建文件大小分配inode号找到当前目录所在的inode结点，把（文件名，inode号）表项加入该目录记录的inode索引表，并修改目录大小更新inode内容。按照文件大小分配磁盘块，在inode里的磁盘地址记录磁盘块号（

8、3）显示目录内容- void list_dir( file *fp, int dir_ind_no)找到当前目录的inode，读取该目录下的inode索引表根据索引表的表项找到相应inode，读取inode内容，并显示。列出文件/目录所占的磁盘块表结束？否是退出（4） 改变目录-int cd_path( file *fp, int *pd_ind_no, char *given_path)以/分隔路径每次打开一级目录，如果不是目录则出错路径结束？否是退出（5）显示状态-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 系统定义#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/寻找磁盘块号对应的磁盘块在文件系统中的地址#define seek_blk(blk_no) block_size*(inode_table_blocks + 1 + blk_no)/寻找inode号为x的inode在文件系统中的地址#define inode_offset(x) (block_size + (x)*sizeof(struct fs_inode)#define name_len 14 /文件名最大长度#define path_len 100 /路径名最大长度3.2 主要数据结构/超级块结构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结构struct fs_inode char user15;/用户名 char type;/文件类型，分为一般文件和目录文件 unsigned links;/文件联结数 int size;/文件大小 int addr13;/磁盘块索引;/表示i-node表中的一项struct fd_entry char namename_len;/ 文件或目录名 int inode_no;/ inode号 ;3.3 系统结构和管理3.3.1空闲磁盘块管理采用成组链接法管理空闲块每一组存入50个磁盘块号，并用一个当前索引记录当前分配块号所在组中的位置，以便下次

14、分配时只要移动一个位置就可以获得新分配的块号。 。 。（1）分配一个空闲磁盘块号，返回一个磁盘块号int get_blk(file *fp) 获取当前空闲块组的索引值，即指向空闲块组的第几个索引读取当前索引值存放的磁盘块号空闲块数目少1如果栈滿并且还有空闲块，重新载入新的空闲块组到超级块中空闲栈作为当前空闲组返回当前磁盘块号作为分配的磁盘块号（2）释放一个磁盘块，使该磁盘块号恢复自由分配权int free_blk(file *fp, int blk_no)把刚释放的磁盘块号加到当前空闲栈顶，并修改当前空闲栈的索引指针即stack0的值 如果当前空闲栈满，重新从前面开始生成一个空闲组覆盖原来已经

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、索引节点表不空，就从该空闲索引节点表中从栈顶取一个分配并将当前索引即栈顶指针向下移，读出该磁盘索引节点。如果超级块中的空闲索引节点表为空，则从铭记节点开始向后（从低序号向高序号）查找空闲索引节点，并把它们登记到超级块的空闲索引节点表中，直到超级块的空闲节点表满为止，并设置铭记节点为搜索到的最后一个空闲节点号。铭记节点是用来纪录下一次搜索空闲索引节点的起始位置，铭记节点前的索引节点都是已经分配了的，所以每 次搜索只要从铭记节点开始。空闲inode表50inode号49inode号48inode号47inode号。3inode号2inode号1inode号0当前索引（2）释放inode在释放索引节

17、点时，如果当前空闲inode表已分配过inodes，那么把释放的节点号加进空闲节点表的栈顶。如果当前空闲inode表已满，则不能加入栈顶。这时要看该索引节点号是否大于铭记节点号，大于则直接释放该索引节点，小于则在释放后要将铭记节点号改成刚释放的索引节点号。3.3.3 文件的结构（文件所占磁盘块号的组织）一个文件/目录对应一个inode，在inode中以int addr13记录文件磁盘块索引由于考虑到存放足够大的文件，我采用了多级间接地址，分为索引节点inode包含文件数据的磁盘地址明细表，它指出文件数据在磁盘上的存储位置。系统在磁盘上给文件分配空间时，并不一定需 要连续的空间来存放文件。核心有

18、较大的灵活性，一次分配一块文件空间，并且允许文件数据分布在整个文件系统中，这样没有了造成碎片的风险，每个文件浪费的 空间最多不到一个数据块。但是这样导致了文件数据读取时，数据定位的复杂程度。另外，一个索引节点的大小时固定的，也就是说，索引节点包含文件数据的磁盘 地址明细表的大小时固定的，当一个文件较大时，索引节点中的磁盘地址明细表就不够放。这样就有几种解决办法，一种是加大inode的大小，但这样浪费磁盘 空间。二种是限制文件大小，这是一种不可取的方法。我采用的是unix的解决办法在inode的磁盘地址明细表中前若干项是直接指向磁盘数据所在块的块号，前10项为直接块号。随后的三项分别是一次间接、

19、二次间接和三次间接。一次间接是指该项存放的磁盘块号所指向的 磁盘数据块的内容是若干数据块的磁盘块号，即从该项得到数据块号，由此可得数据块的内容，而数据块的内容是一张磁盘块号表，每一项地址指向一个数据块。二 次间接是指该项存放的磁盘块号所指向的数据块的内容是一张磁盘块号表，而由该磁盘块号表得到的数据块的内容仍然是一张磁盘块号表，再由该表得到的数据块才 是文件的数据。三次间接以此类推。该结构可由图1-1说明。虽然从逻辑上还可以做四次间接，但实际上不需要这样，现在的结构已经足够， 它可以使文件的最大长度达到(10+1*256+1*256*256+1*256*256*256)*1k=16843018k

20、（当一个块的大小是 1024bytes，磁盘块号为32bits时），而在索引节点中文件长度是由一个32bits的字段存放的，所以文件最大长度不能超过4g。假设文件系统中一个块（block）的大小为1024bytes，那么对一个大小不超过10k的文件的存放是由直接块号表得到数据块的块号，数据定位不复 杂。而对一个大小超过10k的文件来说，前10k可以从直接块号表得到磁盘块号，但后面的数据就要先读入一个一次间接块的内容，再去读数据，对磁盘操作稍 有影响。3.3.4 目录目录是一种文件，起到文件名到索引节点号之间转换的桥梁作用，也是使得文件系统成为树状结构的关键。目录文件的内容是由一系列的目录登记项

21、构成，每项由该目录包含的一个文件名及该文件的索引节点号两部分组成。目录登记项一般含有以下几个字段：文件名：文件名的长度为14个字符索引节点号：该字段指出本目录中该文件名所对应的索引节点号。每个目录文件的前两项是两个特殊文件“”和“”，其中“”表示当前目录自身，对应“”文件的索引节点号就是该 目录文件的索引节点号。文件“”表示上级目录，即对应“”的索引节点号是当前目录的父目录的索引节点号。“”是一个比较特殊的目录，称为根目 录。该目录是在mkfs程序生成文件系统时产生的目录，该目录文件的“”和“”对应的索引节点号是“”目录自身的索引节点号。在一个文件操作中我们常用路径名来指出文件所在的位置，路径

22、名第一个字符为“”时，我们称这个路径是绝对路径，即该路 径从根目录开始指出文件的位置。路径名以“”为分隔符，区分各目录层次。最后一个分量可以是目录，也可以是文件名。当路径名不是以“”为第一个字符 时，我们称这个路径是相对路径，即该路径从当前目录指出文件所在的位置。系统对目录文件数据存储的操作与普通文件一样，也使用inode来保存目录文件的信息及存储的磁盘块号。目录文件的读权 限表示进程可以读取这个目录，写权限表示进程可以创建或撤销目录登记项（通过creat、mknod等），执行权限表示进程可以搜索这个目录。核心在目录 树中找一个文件的索引节点的过程，是一个转换过程。核心内部对文件都是用索引节点

23、来操作的，这就是说必须有一个路径名到索引节点的转换过程。对于一个绝对 路径来说，就是从根目录起，在根目录文件中寻找路径名的下一个分量所对应的索引节点，再从索引节点找到磁盘数据块，如此循环直到搜索完毕为止。对于一个相 对路径，就是在当前目录文件中寻找下一个分量所对应的索引节点。对于路径名中跨越安装点的问题将在1.3.11节中讨论。举例来说，要打开/etc/passwd文件，系统先读取根目录文件在该文件中找到目录登记项中文件名是etc的项，并 由此得到etc的索引节点号，由索引节点找到etc目录文件。在读入etc目录文件后，查找文件名为passwd的目录登记项，并得到索引节点，这时可以 打开该文件

24、了。对于一个相对路径来说，要打开././etc/passwd文件，首先根据当前工作目录，得到该目录文件，并可以查找其父目录的索引节 点号，重复查找过程，即可得到该文件的索引节点。最后要注意的是，一个目录文件的目录登记项中，如果文件名存在，而索引节点号为0，表示该文件在这个目录 存在过，现在不存在（已经被删除了）。文件名inode号.num1.num2file1num3filennumn3.4 相关算法实现（1）创建文件时为文件分配磁盘块创建文件时，为文件分配磁盘块，每次分配一个磁盘块，直到满足用户要求的文件大小为止。每一次为文件分配一个磁盘块都要记录进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信息释放