第12章 文件系统的实现

第12章文件系统的实现教师：计算机操作系统课程组E-mail:zhao.yanhong@163.com（赵艳红）

wxzx@（沈峰）

安徽科技学院设计人:赵艳红0Contents文件存储设备磁盘空间管理文件分配方法目录的实现GeekOS的文件系统1112.1文件存储设备顺序存取设备---磁带只有当第i块物理块被访问之后，才能对第i+1块访问对某个特定物理块的访问与该物理块到磁头当前位置的距离有很大关系，远则移动磁头需要花费很长时间。优点：容量大2212.1文件存储设备直接存取设备----磁盘由多个磁盘片(platter)组成磁盘片的表面被逻辑地划分为圆形磁道(track)磁道被划分为固定长度的单元，称为扇区(sector)位于同一磁臂位置的磁道集合形成柱面(cylinder)性能：容量、传输速率、定位时间（＝寻道时间＋旋转等待时间）3312.1文件存储设备磁盘44磁盘相关的操作定位(seek)移动磁臂到适当的柱面，所用时间称为寻道时间。Read/Write一次只能读/写一个扇区磁头移到指定的扇区地址之前系统必须等待，所用时间称为旋转等待时间。操作系统必须跟踪硬盘的物理地址用以实现文件系统。55磁盘相关的操作一块硬盘由多个盘片组成。一个盘片对应一个磁头臂：两个读写磁头对盘片上下页进行读写。盘面上的同心圆称为磁道。一个磁道被分割成大小相同的多个扇区。所有盘片中相同的磁道称为柱面。IDE硬盘：扇区大小：512bit。通常情况：一个物理块=？个扇区6612.2磁盘空间管理?一个长度为n个字节的文件存储在硬盘上时，如何分配存储空间？方案1：把文件分配到n个字节的连续空闲磁盘空间。当文件扩大时，空闲空间不够，就需要移到磁盘的另一个位置。方案2：把文件分割成多个块，然后把它们存放在不同的磁盘块中(各块之间不必相邻)。7712.2磁盘空间管理?块的大小为多少呢？过大？如整个柱面为单位。过小？则一个文件将包含多个块，每访问一个块磁头都要定位和旋转延迟，文件的访问速度将很慢。实验表明：块大小为4KB较好。Linux2.6:4KBGeekOS:4KB8812.2磁盘空间管理?如何管理空闲块？方法1：空闲链表：使用一个链表，每个结点是一个磁盘块，里面尽可能存放多的空闲磁盘块号，另外每个结点还有指向下一个结点的指针。方法2：位示图如果一个磁盘有N个块，那么就需要N个位来描述。1：表示空闲，0：表示已分配(或相反)。Linux、GeekOS采用9912.2磁盘空间管理空闲链表法占用存储空间比位示图法多。101012.2磁盘空间管理采用空闲链表法，在内存中只要保存一个结点。当创建一个新文件时，所需要的磁盘块就从这个结点中取。如果该结点中的空闲块都已经用完，就从链表中读入一个新的结点。类似地，当一个文件被删除后，它的磁盘块就被释放并添加到内存中的链表结点中，如果该结点装满，就把它写回磁盘。111112.3文件分配方法?如何为文件分配存储空间，以便有效使用磁盘空间和快速访问文件？方法：连续分配、链表分配、带有文件分配表的链表结构、索引节点121212.3.1连续分配(ContiguousAllocation)把每个文件存放在连续的磁盘数据块中。例如，如果磁盘数据块大小为4KB，则一个40KB的文件就需要10个连续的磁盘块。131312.3.1连续分配(ContiguousAllocation)当前应用：CD-ROM、DVD等一次性写入的光学存储介质领域。优点：简单、易实现缺点：外碎片(指比较小、没有办法再利用的多个连续空闲块)141412.3.2链接分配(LinkedAllocation)为每个文件构造一条磁盘块链表。每个块的每个字作为指向下一块的指针，块的其余部分则用来存放数据。151512.3.2链接分配(LinkedAllocation)161612.3.2链接分配(LinkedAllocation)优点：每一个磁盘块都被利用(不会有外碎片，但可能有内碎片)、目录项中只需存放第一个块的磁盘地址。缺点：不利用随机访问、指针要占用字节。171712.3.2带有文件分配表的链表结构带有文件分配表的链表结构(LinkedListwithFileAllocationTable)在链表的基础上进行改进，把每一个磁盘块中的链表指针单独抽取出来，单独组成一个表格，放在内存中，这个表格称为文件分配表。标志0表示结束。如DOS、Windows98181812.3.2带有文件分配表的链表结构优点：容易随机访问、整个链表都在内存中遍历速度较块、目录项中只需存放第一个块的磁盘地址缺点：整个表都必须位于内存中。如果一个20GB的磁盘，块大小为1KB，则FAT表项就需要2000万个，若每个表项占4字节，则整个表占内存80MB。191912.3.3索引分配索引节点(index-node)给每个文件赋予一个数据结构，称为索引节点或i节点，里面列出文件的属性和各个数据块的磁盘地址。当一个文件被打开时，才把它的i节点读入内存，如果一个节点占用n个字节，且最多只能同时打开k个文件，则存放节点的空间是nk个字节，与磁盘的容量无关。而FAT不同，它与磁盘容量成正比。如Linux、GeekOS202012.3.3索引分配?如果每个i节点能够存放的磁盘地址个数是有限的，那么如果文件太大，超出这个限制怎么办？

……属性i节点磁盘地址磁盘块2121最后一些磁盘地址不是指向数据块，而是指向一个间接块，此间接块存放更多的磁盘块地址。下图是一个具有三级间接块的i节点。222212.4目录的实现打开一个文件：需要根据路径名找目录项需要定位根目录：位于磁盘分区中的某个固定位置，Unix中此位置是超级块。目录项提供了查找磁盘块所需要的信息整个文件的磁盘地址(连续分配)第一个磁盘块的地址(链表分配)i节点(索引节点方式分配)232312.4目录的实现哪儿存放文件的属性信息？把文件属性直接放在目录项中一个目录由一组固定长度的目录项组成，一个存放一个文件，在每个目录项中包含文件名、属性及此文件对应的磁盘块地址。如图a。针对使用i节点的系统，把文件属性存放在i节点中,如图b。图a图b2424Linux中的目录Unix中的目录项如图所示。当一个文件被打开时，文件系统根据用户给定的文件名，找到相应的磁盘块。示例：如何找/usr/ast/mbox的？首先找根目录，此目录通过超级块可以找到。然后，找usr。2525262612.5GeekOS的文件系统保存测试用的用户可执行程序我们需要实现的文件系统272712.5.1VFS(虚拟文件系统)将各种具体文件系统的基本操作抽象出来、组织在一起，从而形成系统调用与实际文件系统之间的中间层。使一个操作系统可以使用多种文件系统成为可能。282812.5.2高速缓冲区用于保存磁盘块数据的内存区，是一个虚拟磁盘。缓冲块大小与磁盘块大小一样：4KB文件系统进行磁盘操作时，首先检查所需磁盘块是否已经在高速缓冲区中，如果在，就直接在内存上进行块操作，如果不在，则向块设备提出磁盘访问请求，读入所需磁盘块。文件系统高速缓冲区块设备请求处理机制磁盘292912.5.3GOSFS文件系统结构支持多级目录、长文件名。提供文件与目录的创建、删除等基本操作。文件系统驻留在Ide1硬盘上，大小：10MB。磁盘块：4KB3030(1)GOSFS的布局3131(1)GOSFS的布局第0块(超级块)Magic:4Byte,是具体的文件系统标识

RootDirPointer:根目录的磁盘块号，Size:磁盘大小FreeBlocksBitmap:1024*8位，每一位对应一个4KB的磁盘块。1024*8*4KB=32MB.磁盘格式化：系统根据磁盘容量计算出磁盘块数，然后计算位图大小并将位图中对应的位设置为空，然后创建根目录，并使RootDirPointer指向它，将相关数据填入超级块，并将根目录使用的磁盘块在位图对应位置标记为使用，最后填写magic。除第0块之外，其它磁盘块用于存放文件和目录。3232(2)文件与目录将目录作为特殊的文件进行管理，目录项（即文件控制块）定义如下：

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目录

数据块数据块3434Datastorage–DirectMapping01234567894KBdatablockGOSFS_Dir_Entry.blockList[10]4KBdatablock4KBdatablockDISK=used长度12KB的文件3535Datastorage–SingleIndirect4KBdatablock4KBdatablock4KBdatablockDISK0123456789001234...1022102304KBdatablock4KBdatablock长度40KB

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