第12章 文件系统的实现

1、安徽科技学院 设计人:赵艳红第第12章章 文件系统的实现文件系统的实现教师：计算机操作系统课程组教师：计算机操作系统课程组E-mail: E-mail: （赵艳红）（赵艳红） （沈峰）（沈峰） 校重点建设课程校重点建设课程111Contents文件存储设备文件存储设备磁盘空间管理磁盘空间管理文件分配方法文件分配方法目录的实现目录的实现GeekOS的文件系统的文件系统校重点建设课程校重点建设课程22212.1 文件存储设备文件存储设备v 顺序存取设备顺序存取设备-磁带磁带只有当第只有当第i块物理块被访问之后，才能对第块物理块被访问之后，才能对第i+1块块访问访问对某个特定物理块的访问与该物理块到

2、磁头当前对某个特定物理块的访问与该物理块到磁头当前位置的距离有很大关系，远则移动磁头需要花费位置的距离有很大关系，远则移动磁头需要花费很长时间。很长时间。v 优点：容量大优点：容量大校重点建设课程校重点建设课程33312.1 文件存储设备文件存储设备v 直接存取设备直接存取设备-磁盘磁盘n由多个由多个磁盘片磁盘片(platter)(platter)组组成成n磁盘片的表面被逻辑地划分磁盘片的表面被逻辑地划分为圆形为圆形磁道磁道(track)(track)n磁道被划分为固定长度的单磁道被划分为固定长度的单元，称为元，称为扇区扇区(sector)(sector)n位于同一磁臂位置的磁道集位于同一磁臂

3、位置的磁道集合形成合形成柱面柱面(cylinder)(cylinder)n性能：性能： 容量、传输速率、定位容量、传输速率、定位时间（寻道时间旋时间（寻道时间旋转等待时间）转等待时间）校重点建设课程校重点建设课程44412.1 文件存储设备文件存储设备n磁盘磁盘校重点建设课程校重点建设课程555磁盘相关的操作磁盘相关的操作n 定位定位(seek)移动磁臂到适当的柱面，所用时间称为寻道时间。移动磁臂到适当的柱面，所用时间称为寻道时间。n Read/Write一次只能读一次只能读/写一个扇区写一个扇区磁头移到指定的扇区地址之前系统必须等待，所磁头移到指定的扇区地址之前系统必须等待，所用时间称为旋转

4、等待时间。用时间称为旋转等待时间。n 操作系统必须跟踪硬盘的物理地址用以实现操作系统必须跟踪硬盘的物理地址用以实现文件系统。文件系统。校重点建设课程校重点建设课程666磁盘相关的操作磁盘相关的操作 一块硬盘由多个盘片组成。一块硬盘由多个盘片组成。 一个盘片对应一个磁头臂：两个读写磁头对盘片上一个盘片对应一个磁头臂：两个读写磁头对盘片上下页进行读写。下页进行读写。 盘面上的同心圆称为磁道。一个磁道被分割成大小盘面上的同心圆称为磁道。一个磁道被分割成大小相同的多个扇区。相同的多个扇区。 所有盘片中相同的磁道称为柱所有盘片中相同的磁道称为柱面。面。 IDEIDE硬盘：扇区大小：硬盘：扇区大小：512

5、bit512bit。 通常情况：一个物理块通常情况：一个物理块= = ？个扇区？个扇区校重点建设课程校重点建设课程77712.2 磁盘空间管理磁盘空间管理? 一个长度为一个长度为n个字节的文件存储在硬盘上时，个字节的文件存储在硬盘上时，如何分配存储空间？如何分配存储空间？方案方案1 ：把文件分配到：把文件分配到n 个字节的连续空闲磁盘个字节的连续空闲磁盘空间。空间。当文件扩大时，空闲空间不够，就需要移到磁盘的另当文件扩大时，空闲空间不够，就需要移到磁盘的另一个位置。一个位置。方案方案2：把文件分割成多个块，然后把它们存放：把文件分割成多个块，然后把它们存放在不同的磁盘块中在不同的磁盘块中(各块

6、之间不必相邻各块之间不必相邻)。校重点建设课程校重点建设课程88812.2 磁盘空间管理磁盘空间管理? 块的大小为多少呢？块的大小为多少呢？过大？如整个柱面为单位。过大？如整个柱面为单位。 过小？则一个文件将包含多个块，每访问一个过小？则一个文件将包含多个块，每访问一个块磁头都要定位和旋转延迟，文件的访问速度将块磁头都要定位和旋转延迟，文件的访问速度将很慢。很慢。n 实验表明：块大小为实验表明：块大小为4KB较好。较好。Linux 2.6 :4KBGeekOS : 4KB校重点建设课程校重点建设课程99912.2 磁盘空间管理磁盘空间管理? 如何管理空闲块？如何管理空闲块？方法方法1：空闲链表

7、空闲链表：使用一个链表，每个结点是：使用一个链表，每个结点是一个磁盘块，里面尽可能存放多的空闲磁盘块号，一个磁盘块，里面尽可能存放多的空闲磁盘块号，另外每个结点还有指向下一个结点的指针。另外每个结点还有指向下一个结点的指针。方法方法2：位示图位示图如果一个磁盘有如果一个磁盘有N个块，那么就需要个块，那么就需要N个位来描述。个位来描述。1：表示空闲，表示空闲，0：表示已分配：表示已分配(或相反或相反)。Linux、GeekOS采用采用校重点建设课程校重点建设课程10101012.2 磁盘空间管理磁盘空间管理空闲链表法占用存储空间比位示图法多。空闲链表法占用存储空间比位示图法多。校重点建设课程校重

8、点建设课程11111112.2 磁盘空间管理磁盘空间管理采用采用空闲链表法空闲链表法，在，在内存内存中只要保存中只要保存一个结一个结点点。当创建一个新文件时，所需要的。当创建一个新文件时，所需要的磁盘块磁盘块就就从这个结点中取从这个结点中取。如果该结点中的空闲块。如果该结点中的空闲块都已经都已经用完用完，就从链表中，就从链表中读入读入一个一个新的结点新的结点。 类似地，当一个文件被删除后，它的磁盘块类似地，当一个文件被删除后，它的磁盘块就被释放并添加到内存中的链表结点中，如就被释放并添加到内存中的链表结点中，如果该结点装满，就把它写回磁盘。果该结点装满，就把它写回磁盘。校重点建设课程校重点建设

9、课程12121212.3 文件分配方法文件分配方法? 如何为文件分配存储空间，以便有效使用磁如何为文件分配存储空间，以便有效使用磁盘空间和快速访问文件？盘空间和快速访问文件？l方法：方法：连续分配连续分配、链表分配链表分配、带有文件分配表的链表结带有文件分配表的链表结构构、索引节点索引节点校重点建设课程校重点建设课程13131312.3.1 连续分配连续分配(Contiguous Allocation)v 把每个文件存放在把每个文件存放在连续的磁盘数据块连续的磁盘数据块中。中。例如，如果磁盘数据例如，如果磁盘数据块大小为块大小为4KB，则一，则一个个40KB的文件就需的文件就需要要10个连续的

10、磁盘块。个连续的磁盘块。校重点建设课程校重点建设课程14141412.3.1 连续分配连续分配(Contiguous Allocation)l当前应用：当前应用：CD-ROM、DVD等一次性写入的光学等一次性写入的光学存储介质领域。存储介质领域。l优点：简单、易实现优点：简单、易实现l缺点：外碎片缺点：外碎片(指比较小、没有办法再利用的多个指比较小、没有办法再利用的多个连续空闲块连续空闲块)校重点建设课程校重点建设课程15151512.3.2 链接分配链接分配(Linked Allocation)l 为每个文件构造为每个文件构造一条磁盘块链表。一条磁盘块链表。每个块的每个字每个块的每个字作为指

11、向下一块作为指向下一块的指针，块的其的指针，块的其余部分则用来存余部分则用来存放数据。放数据。校重点建设课程校重点建设课程16161612.3.2 链接分配链接分配(Linked Allocation)校重点建设课程校重点建设课程17171712.3.2 链接分配链接分配(Linked Allocation)n 优点：优点：每一个磁盘块都被利用每一个磁盘块都被利用(不会有外碎片，但可能不会有外碎片，但可能有内碎片有内碎片)、目录项中只需存放第一个块的磁盘、目录项中只需存放第一个块的磁盘地址。地址。n 缺点：缺点：不利用随机访问、指针要占用字节。不利用随机访问、指针要占用字节。校重点建设课程校重

12、点建设课程18181812.3.2 带有文件分配表的链表结构带有文件分配表的链表结构v 带有文件分配表的链表结带有文件分配表的链表结构构(Linked List with File Allocation Table)在链表的基础上进行改进，在链表的基础上进行改进，把每一个磁盘块中的把每一个磁盘块中的链表指链表指针针单独抽取出来，单独抽取出来，单独组成单独组成一个表格一个表格，放在，放在内存中内存中，这，这个表格称为文件分配表。个表格称为文件分配表。标志标志0表示结束。表示结束。如如DOS、Windows98校重点建设课程校重点建设课程19191912.3.2 带有文件分配表的链表结构带有文件分

13、配表的链表结构l 优点：优点：容易随机访问、整个链表都在内存中遍历速度较容易随机访问、整个链表都在内存中遍历速度较块、目录项中只需存放第一个块的磁盘地址块、目录项中只需存放第一个块的磁盘地址l 缺点：缺点：整个表整个表都必须位于都必须位于内存中内存中。如果一个如果一个20GB的磁盘，块大小为的磁盘，块大小为1KB，则，则FAT表项表项就需要就需要2000万个，若每个表项占万个，若每个表项占4字节，则整个表占字节，则整个表占内存内存80MB。校重点建设课程校重点建设课程20202012.3.3 索引分配索引分配v 索引节点索引节点(index-node)给每个文件赋予一个数据结构，称为索引节点或

14、给每个文件赋予一个数据结构，称为索引节点或i节点，里面列出文件的属性和各个数据块的磁节点，里面列出文件的属性和各个数据块的磁盘地址。盘地址。当一个文件被打开时，才把它的当一个文件被打开时，才把它的i节点读入内存，节点读入内存，如果一个节点占用如果一个节点占用n个字节，且最多只能同时打个字节，且最多只能同时打开开k个文件，则存放节点的空间是个文件，则存放节点的空间是nk个字节，与个字节，与磁盘的容量无关。而磁盘的容量无关。而FAT不同，它与磁盘容量成不同，它与磁盘容量成正比。正比。如如Linux、GeekOS校重点建设课程校重点建设课程21212112.3.3 索引分配索引分配? 如果每个如果每

15、个i节点能够存放的磁盘地址个数是有限的，节点能够存放的磁盘地址个数是有限的，那么如果那么如果文件太大文件太大，超出这个限制怎么办？，超出这个限制怎么办？ 属 性i节点节点磁盘地址磁盘地址磁盘块磁盘块最后一些磁盘地址不是指向数据块，而是最后一些磁盘地址不是指向数据块，而是指向一个指向一个间接块间接块，此间接块存放更多的磁盘块地址。下图是，此间接块存放更多的磁盘块地址。下图是一个具有三级间接块的一个具有三级间接块的i节点。节点。校重点建设课程校重点建设课程23232312.4 目录的实现目录的实现v 打开一个文件：打开一个文件：需要根据路径名找目录项需要根据路径名找目录项需要定位根目录：位需要定位

16、根目录：位于磁盘分区中的某个固定位置，于磁盘分区中的某个固定位置，Unix中此位置中此位置是超级块。是超级块。v 目录项提供了查找磁盘块所需要的信息目录项提供了查找磁盘块所需要的信息整个文件的磁盘地址整个文件的磁盘地址(连续分配连续分配)第一个磁盘块的地址第一个磁盘块的地址(链表分配链表分配) i节点节点(索引节点方式分配索引节点方式分配)校重点建设课程校重点建设课程24242412.4 目录的实现目录的实现v 哪儿存放文件的属性信息？哪儿存放文件的属性信息？把文件属性直接放在目录项中把文件属性直接放在目录项中一个目录由一组固定长度的目录项组成，一个存放一一个目录由一组固定长度的目录项组成，一

17、个存放一个文件，在每个目录项中包含文件名、属性及此文件个文件，在每个目录项中包含文件名、属性及此文件对应的磁盘块地址。如图对应的磁盘块地址。如图a。针对使用针对使用i节点的系统，把文件属性存放在节点的系统，把文件属性存放在i节点节点中中,如图如图b。图图a图图b校重点建设课程校重点建设课程252525Linux中的目录中的目录n Unix中的目录项如图所示。中的目录项如图所示。n 当一个文件被打开时，文件系统根据用户给定的文当一个文件被打开时，文件系统根据用户给定的文件名，找到相应的磁盘块。件名，找到相应的磁盘块。n 示例：如何找示例：如何找/usr/ast/mbox的？的？首先找根目录，此目

18、录通过超级块可以找到。然后，找首先找根目录，此目录通过超级块可以找到。然后，找usr。校重点建设课程校重点建设课程262626校重点建设课程校重点建设课程27272712.5 GeekOS的文件系统的文件系统保存测试用保存测试用的用户可执的用户可执行程序行程序我们需要我们需要实现的文实现的文件系统件系统校重点建设课程校重点建设课程28282812.5.1 VFS(虚拟文件系统虚拟文件系统)l将各种具体文件系统的基本操作抽象出来、将各种具体文件系统的基本操作抽象出来、组织在一起，从而形成系统调用与实际文件组织在一起，从而形成系统调用与实际文件系统之间的中间层。系统之间的中间层。l使一个操作系统可

19、以使用多种文件系统成为使一个操作系统可以使用多种文件系统成为可能。可能。校重点建设课程校重点建设课程29292912.5.2 高速缓冲区高速缓冲区l用于保存磁盘块数据的内存区，用于保存磁盘块数据的内存区，是一个虚拟磁盘。是一个虚拟磁盘。l缓冲块大小与磁盘块大小一样：缓冲块大小与磁盘块大小一样：4KB4KBl文件系统进行磁盘操作时，首文件系统进行磁盘操作时，首先检查所需磁盘块是否已经在先检查所需磁盘块是否已经在高速缓冲区中，如果在，就直高速缓冲区中，如果在，就直接在内存上进行块操作，如果接在内存上进行块操作，如果不在，则向块设备提出磁盘访不在，则向块设备提出磁盘访问请求，读入所需磁盘块。问请求，

20、读入所需磁盘块。文件系统文件系统高速缓冲区高速缓冲区块设备请求处理机制块设备请求处理机制磁盘磁盘校重点建设课程校重点建设课程30303012.5.3 GOSFS文件系统结构文件系统结构l支持多级目录、长文件名。支持多级目录、长文件名。l提供文件与目录的创建、删除等基本操作。提供文件与目录的创建、删除等基本操作。l文件系统驻留在文件系统驻留在Ide1Ide1硬盘上，大小：硬盘上，大小：10MB10MB。l磁盘块：磁盘块：4KB4KB校重点建设课程校重点建设课程313131(1) GOSFS的布局的布局校重点建设课程校重点建设课程323232(1) GOSFS的布局的布局l第第0块块(超级块超级块

21、)Magic:4Byte,是具体的文件系统标识是具体的文件系统标识 RootDirPointer:根目录的磁盘块号，根目录的磁盘块号，Size: 磁盘大小磁盘大小FreeBlocksBitmap:1024*8位，每一位对应一个位，每一位对应一个4KB的的磁盘块。磁盘块。1024*8*4KB=32MB.磁盘格式化磁盘格式化：系统根据磁盘容量计算出：系统根据磁盘容量计算出磁盘块数磁盘块数，然后，然后计算位图大小并将计算位图大小并将位图位图中对应的位设置为空，然后创建中对应的位设置为空，然后创建根目录根目录，并使，并使RootDirPointer指向它，将相关数据填入指向它，将相关数据填入超级块，并

22、将根目录使用的磁盘块在位图对应位置标记超级块，并将根目录使用的磁盘块在位图对应位置标记为使用，最后填写为使用，最后填写magic。l除第除第0块之外，其它磁盘块用于存放文件和目录。块之外，其它磁盘块用于存放文件和目录。校重点建设课程校重点建设课程333333(2) 文件与目录文件与目录l将目录作为特殊的文件进行管理，目录项（即文件将目录作为特殊的文件进行管理，目录项（即文件控制块）定义如下：控制块）定义如下： struct GOSFS_Dir_Entry ulong_t size; ulong_t flags; char filename128; ulong_t blockList10; struct VFS_ACL_Entry acl10 ;校重点建设课程校重点建设课程343434(2) 文件与目录文件与目录GOSFS_Dir_Entryfilename128flagssizeacl10blockList10目录项目录项GOSFS_Dir_EntryGOSFS_Dir_EntryGOSFS_D