文件系统的实现.pptx

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