第12章 文件系统的实现.ppt

第12章 文件系统的实现 教师：计算机操作系统课程组 E-mail: zhao.yanhong@163.com（赵艳红） wxzx@（沈峰） Contents 12.1 文件存储设备 顺序存取设备---磁带 只有当第i块物理块被访问之后，才能对第i+1块访问 对某个特定物理块的访问与该物理块到磁头当前位置的距离有很大关系，远则移动磁头需要花费很长时间。 优点：容量大 12.1 文件存储设备 直接存取设备----磁盘 12.1 文件存储设备 磁盘 磁盘相关的操作 定位(seek) 移动磁臂到适当的柱面，所用时间称为寻道时间。 Read/Write 一次只能读/写一个扇区 磁头移到指定的扇区地址之前系统必须等待，所用时间称为旋转等待时间。 操作系统必须跟踪硬盘的物理地址用以实现文件系统。 磁盘相关的操作 一块硬盘由多个盘片组成。 一个盘片对应一个磁头臂：两个读写磁头对盘片上下页进行读写。 盘面上的同心圆称为磁道。一个磁道被分割成大小相同的多个扇区。 所有盘片中相同的磁道称为柱面。 IDE硬盘：扇区大小：512bit。 通常情况：一个物理块= ？个扇区 12.2 磁盘空间管理 ? 一个长度为n个字节的文件存储在硬盘上时，如何分配存储空间？ 方案1 ：把文件分配到n 个字节的连续空闲磁盘空间。 当文件扩大时，空闲空间不够，就需要移到磁盘的另一个位置。 方案2：把文件分割成多个块，然后把它们存放在不同的磁盘块中(各块之间不必相邻)。 12.2 磁盘空间管理 ? 块的大小为多少呢？ 过大？如整个柱面为单位。 过小？则一个文件将包含多个块，每访问一个块磁头都要定位和旋转延迟，文件的访问速度将很慢。 实验表明：块大小为4KB较好。 Linux 2.6 :4KB GeekOS : 4KB 12.2 磁盘空间管理 ? 如何管理空闲块？ 方法1：空闲链表：使用一个链表，每个结点是一个磁盘块，里面尽可能存放多的空闲磁盘块号，另外每个结点还有指向下一个结点的指针。 方法2：位示图 如果一个磁盘有N个块，那么就需要N个位来描述。1：表示空闲，0：表示已分配(或相反)。 Linux、GeekOS采用 12.2 磁盘空间管理 空闲链表法占用存储空间比位示图法多。 12.2 磁盘空间管理 采用空闲链表法，在内存中只要保存一个结点。当创建一个新文件时，所需要的磁盘块就从这个结点中取。如果该结点中的空闲块都已经用完，就从链表中读入一个新的结点。 类似地，当一个文件被删除后，它的磁盘块就被释放并添加到内存中的链表结点中，如果该结点装满，就把它写回磁盘。 12.3 文件分配方法 ? 如何为文件分配存储空间，以便有效使用磁盘空间和快速访问文件？ 方法： 连续分配、链表分配、带有文件分配表的链表结构、索引节点 12.3.1 连续分配(Contiguous Allocation) 把每个文件存放在连续的磁盘数据块中。 例如，如果磁盘数据块大小为4KB，则一个40KB的文件就需要10个连续的磁盘块。 12.3.1 连续分配(Contiguous Allocation) 当前应用：CD-ROM、DVD等一次性写入的光学存储介质领域。 优点：简单、易实现 缺点：外碎片(指比较小、没有办法再利用的多个连续空闲块) 12.3.2 链接分配(Linked Allocation) 为每个文件构造一条磁盘块链表。每个块的每个字作为指向下一块的指针，块的其余部分则用来存放数据。 12.3.2 链接分配(Linked Allocation) 12.3.2 链接分配(Linked Allocation) 优点： 每一个磁盘块都被利用(不会有外碎片，但可能有内碎片)、目录项中只需存放第一个块的磁盘地址。 缺点： 不利用随机访问、指针要占用字节。 12.3.2 带有文件分配表的链表结构 带有文件分配表的链表结构(Linked List with File Allocation Table) 在链表的基础上进行改进，把每一个磁盘块中的链表指针单独抽取出来，单独组成一个表格，放在内存中，这个表格称为文件分配表。 标志0表示结束。 如DOS、Windows98 12.3.2 带有文件分配表的链表结构 优点： 容易随机访问、整个链表都在内存中遍历速度较块、目录项中只需存放第一个块的磁盘地址 缺点： 整个表都必须位于内存中。 如果一个20GB的磁盘，块大小为1KB，则FAT表项就需要2000万个，若每个表项占4字节，则整个表占内存80MB。 12.3.3 索引分配 索引节点(index-node) 给每个文件赋予一个数据结构，称为索引节点或i节点，里面列出文件的属性和各个数据块的磁盘地址。 当一个文件被打开时，才把它的i节点读入内