文件系统的实现

安徽科技学院设计人 赵艳红 第12章文件系统的实现 教师 计算机操作系统课程组E mail zhao yanhong 赵艳红 wxzx 沈峰 1 1 Contents 文件存储设备 磁盘空间管理 文件分配方法 目录的实现 GeekOS的文件系统 2 2 12 1文件存储设备 顺序存取设备 磁带只有当第i块物理块被访问之后 才能对第i 1块访问对某个特定物理块的访问与该物理块到磁头当前位置的距离有很大关系 远则移动磁头需要花费很长时间 优点 容量大 3 3 12 1文件存储设备 直接存取设备 磁盘 由多个磁盘片 platter 组成磁盘片的表面被逻辑地划分为圆形磁道 track 磁道被划分为固定长度的单元 称为扇区 sector 位于同一磁臂位置的磁道集合形成柱面 cylinder 性能 容量 传输速率 定位时间 寻道时间 旋转等待时间 4 4 12 1文件存储设备 磁盘 5 5 磁盘相关的操作 定位 seek 移动磁臂到适当的柱面 所用时间称为寻道时间 Read Write一次只能读 写一个扇区磁头移到指定的扇区地址之前系统必须等待 所用时间称为旋转等待时间 操作系统必须跟踪硬盘的物理地址用以实现文件系统 6 6 磁盘相关的操作 一块硬盘由多个盘片组成 一个盘片对应一个磁头臂 两个读写磁头对盘片上下页进行读写 盘面上的同心圆称为磁道 一个磁道被分割成大小相同的多个扇区 所有盘片中相同的磁道称为柱面 IDE硬盘 扇区大小 512bit 通常情况 一个物理块 个扇区 7 7 12 2磁盘空间管理 一个长度为n个字节的文件存储在硬盘上时 如何分配存储空间 方案1 把文件分配到n个字节的连续空闲磁盘空间 当文件扩大时 空闲空间不够 就需要移到磁盘的另一个位置 方案2 把文件分割成多个块 然后把它们存放在不同的磁盘块中 各块之间不必相邻 8 8 12 2磁盘空间管理 块的大小为多少呢 过大 如整个柱面为单位 过小 则一个文件将包含多个块 每访问一个块磁头都要定位和旋转延迟 文件的访问速度将很慢 实验表明 块大小为4KB较好 Linux2 6 4KBGeekOS 4KB 9 9 12 2磁盘空间管理 如何管理空闲块 方法1 空闲链表 使用一个链表 每个结点是一个磁盘块 里面尽可能存放多的空闲磁盘块号 另外每个结点还有指向下一个结点的指针 方法2 位示图如果一个磁盘有N个块 那么就需要N个位来描述 1 表示空闲 0 表示已分配 或相反 Linux GeekOS采用 10 10 12 2磁盘空间管理 空闲链表法占用存储空间比位示图法多 11 11 12 2磁盘空间管理 采用空闲链表法 在内存中只要保存一个结点 当创建一个新文件时 所需要的磁盘块就从这个结点中取 如果该结点中的空闲块都已经用完 就从链表中读入一个新的结点 类似地 当一个文件被删除后 它的磁盘块就被释放并添加到内存中的链表结点中 如果该结点装满 就把它写回磁盘 12 12 12 3文件分配方法 如何为文件分配存储空间 以便有效使用磁盘空间和快速访问文件 方法 连续分配 链表分配 带有文件分配表的链表结构 索引节点 13 13 12 3 1连续分配 ContiguousAllocation 把每个文件存放在连续的磁盘数据块中 例如 如果磁盘数据块大小为4KB 则一个40KB的文件就需要10个连续的磁盘块 14 14 12 3 1连续分配 ContiguousAllocation 当前应用 CD ROM DVD等一次性写入的光学存储介质领域 优点 简单 易实现缺点 外碎片 指比较小 没有办法再利用的多个连续空闲块 15 15 12 3 2链接分配 LinkedAllocation 为每个文件构造一条磁盘块链表 每个块的每个字作为指向下一块的指针 块的其余部分则用来存放数据 16 16 12 3 2链接分配 LinkedAllocation 17 17 12 3 2链接分配 LinkedAllocation 优点 每一个磁盘块都被利用 不会有外碎片 但可能有内碎片 目录项中只需存放第一个块的磁盘地址 缺点 不利用随机访问 指针要占用字节 18 18 12 3 2带有文件分配表的链表结构 带有文件分配表的链表结构 LinkedListwithFileAllocationTable 在链表的基础上进行改进 把每一个磁盘块中的链表指针单独抽取出来 单独组成一个表格 放在内存中 这个表格称为文件分配表 标志0表示结束 如DOS Windows98 19 19 12 3 2带有文件分配表的链表结构 优点 容易随机访问 整个链表都在内存中遍历速度较块 目录项中只需存放第一个块的磁盘地址缺点 整个表都必须位于内存中 如果一个20GB的磁盘 块大小为1KB 则FAT表项就需要2000万个 若每个表项占4字节 则整个表占内存80MB 20 20 12 3 3索引分配 索引节点 index node 给每个文件赋予一个数据结构 称为索引节点或i节点 里面列出文件的属性和各个数据块的磁盘地址 当一个文件被打开时 才把它的i节点读入内存 如果一个节点占用n个字节 且最多只能同时打开k个文件 则存放节点的空间是nk个字节 与磁盘的容量无关 而FAT不同 它与磁盘容量成正比 如Linux GeekOS 21 21 12 3 3索引分配 如果每个i节点能够存放的磁盘地址个数是有限的 那么如果文件太大 超出这个限制怎么办 最后一些磁盘地址不是指向数据块 而是指向一个间接块 此间接块存放更多的磁盘块地址 下图是一个具有三级间接块的i节点 23 23 12 4目录的实现 打开一个文件 需要根据路径名找目录项 需要定位根目录 位于磁盘分区中的某个固定位置 Unix中此位置是超级块 目录项提供了查找磁盘块所需要的信息整个文件的磁盘地址 连续分配 第一个磁盘块的地址 链表分配 i节点 索引节点方式分配 24 24 12 4目录的实现 哪儿存放文件的属性信息 把文件属性直接放在目录项中一个目录由一组固定长度的目录项组成 一个存放一个文件 在每个目录项中包含文件名 属性及此文件对应的磁盘块地址 如图a 针对使用i节点的系统 把文件属性存放在i节点中 如图b 图a 图b 25 25 Linux中的目录 Unix中的目录项如图所示 当一个文件被打开时 文件系统根据用户给定的文件名 找到相应的磁盘块 示例 如何找 usr ast mbox的 首先找根目录 此目录通过超级块可以找到 然后 找usr 26 26 27 27 12 5GeekOS的文件系统 保存测试用的用户可执行程序 我们需要实现的文件系统 28 28 12 5 1VFS 虚拟文件系统 将各种具体文件系统的基本操作抽象出来 组织在一起 从而形成系统调用与实际文件系统之间的中间层 使一个操作系统可以使用多种文件系统成为可能 29 29 12 5 2高速缓冲区 用于保存磁盘块数据的内存区 是一个虚拟磁盘 缓冲块大小与磁盘块大小一样 4KB文件系统进行磁盘操作时 首先检查所需磁盘块是否已经在高速缓冲区中 如果在 就直接在内存上进行块操作 如果不在 则向块设备提出磁盘访问请求 读入所需磁盘块 文件系统 高速缓冲区 块设备请求处理机制 磁盘 30 30 12 5 3GOSFS文件系统结构 支持多级目录 长文件名 提供文件与目录的创建 删除等基本操作 文件系统驻留在Ide1硬盘上 大小 10MB 磁盘块 4KB 31 31 1 GOSFS的布局 32 32 1 GOSFS的布局 第0块 超级块 Magic 4Byte 是具体的文件系统标识RootDirPointer 根目录的磁盘块号 Size 磁盘大小FreeBlocksBitmap 1024 8位 每一位对应一个4KB的磁盘块 1024 8 4KB 32MB 磁盘格式化 系统根据磁盘容量计算出磁盘块数 然后计算位图大小并将位图中对应的位设置为空 然后创建根目录 并使RootDirPointer指向它 将相关数据填入超级块 并将根目录使用的磁盘块在位图对应位置标记为使用 最后填写magic 除第0块之外 其它磁盘块用于存放文件和目录 33 33 2 文件与目录 将目录作为特殊的文件进行管理 目录项 即文件控制块 定义如下 structGOSFS Dir Entry ulong tsize ulong tflags charfilename 128 ulong t