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