第五章 文件系统

第五章文件系统在现代计算机系统用，要用到大量的程序和数据，因内存容量有限，且不能长期保存，故而平时总是把它们以文件的形式存放在外存中，需要时再随时将它们调入内存。如果由用户直接管理外存上的文件，需要用户熟悉外存特性，了解各文件的属性，它们在外存上的位置，显然用户无法承担，因此，在操作系统上增加了文件管理功能，即文件系统。第五章文件系统对大多数用户来说，文件系统是操作系统中最直接可见的部分。计算机的重要作用之一就是能快速处理大量信息,从而信息的组织、存取和保管就成为一个极为重要的内容。文件系统是计算机组织、存取和保存信息数据的重要手段。本章主要讨论文件的组织结构、存取结构、保护以及文件系统空间管理等问题。第五章文件系统文件结构文件目录管理文件存储空间管理文件共享与保护目的与要求：了解文件结构，访问方式，存储结构。掌握文件管理用的文件控制块和文件目录结构。了解文件空间管理方法。重点与难点：文件存放与访问方式，文件目录结构。第五章文件系统•为了方便使用、管理系统公共程序和数据以及用户自己的程序和数据而引入文件。•为了对外存空间管理和对其上文件的按名访问而引入文件系统。第五章文件系统为什么引入文件和文件系统•文件系统的功能(1)为了合理的存放文件，必需对磁盘等辅助存储器空间(或称文件空间)进行统一管理。在用户创建新文件时为其分配空闲区，而在用户删除或修改某个文件时,回收和调整存储区。(2)实现按名存取。(3)为了便于存放，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。(4)完成对存放在存储设备上的文件信息的查找。(5)完成文件的共享和提供保护功能。5.1文件组织结构5.1.1文件概念•文件是由创建者所定义、具有文件名的一组相关的信息集合。•文件的主要属性：•文件名，文件类型，文件长度，创建者，创建时间，修改时间，文件定位信息，文件所包含的信息。5.1.2文件的逻辑结构操作系统感知文件信息的组织形式叫文件的逻辑结构。它包括流式文件（无结构文件）和记录式文件（有结构文件）两种，每种文件信息的逻辑单位分别是字节和记录。•流式文件（无结构文件）：•是指对文件内信息不再划分单位，它是依次的一串字节流构成的文件。•记录式文件（有结构文件）：•是用户把文件内的信息按逻辑上独立的含义划分信息单位，每个单位称为一个记录。所有记录通常都是描述一个实体集的，有着相同或不同数目的数据项，记录的长度可分为定长和不定长记录两类。记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。但若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血显然，对于流式的无结构文件来说，查找文件中的基本信息单位，例如某个单词，是比较困难的。但反过来，流式的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用流式的无结构方式，例如，源程序文件、目标代码文件等。记录式的有结构文件可把文件中的记录按各种不同的方式排列，以便用户对文件中的记录进行修改、追加、查找和管理等操作，主要用于信息管理，如数据库系统中。5.1.3文件的物理结构为了便于存放于磁盘，文件可被等分成块（类比页式存储系统的页）将文件系统类比页式存储管理–页式存储管理将一个进程分页存放于主存，页表是逻辑页到物理页的定位信息–文件系统将一个文件分块存放于外存，文件控制块将包含文件的定位信息5.1.3文件的物理结构•逻辑文件在辅存的组织结构称为文件的物理结构。如何组织它们主要依赖于文件存储器的物理特性，以及用户对其文件的访问方式。•文件的访问方式•顺序访问指用户从文件初始数据开始依次访问文件中的信息。经常被顺序访问的文件应该连续存储在文件存储器上。操作系统自动记录文件访问的当前位置。•直接（随机）访问指用户随机访问文件中的某段信息。读/写时直接给出要访问数据的逻辑位置（如第几个字节或第几个记录）及长度，由OS将逻辑位置转换成物理位置并访问之。•磁带顺序访问设备→要求文件顺序存放于带上。•磁盘直接（随机）访问设备→文件可顺序、链接式或随机（通过类似页表的结构访问）存放于设备上。在使用文件存储器前，要选择好物理块的划分长度，并对其进行物理块划分。同样文件的逻辑空间也相应的划分为逻辑块。•文件的物理结构：逻辑文件在辅存的组织机构称为文件的物理结构，也叫文件的存储结构。它包括顺序结构（连续结构）、链接结构、索引结构三种。•顺序结构（连续结构）文件顺序连续存放于文件存储器上（如磁带文件，光盘文件）。特点:实现简单顺序访问容易且速度快要求有连续的存储空间，外部碎片多必须事先知道文件的长度（一）顺序结构012345678910111213141516171819202122232425262728293031文件名始址块数count02tr143mail196list284f62文件目录countftrmaillist磁盘空间（二）链接结构•链接结构文件不连续地存放于文件存储器上，但使用指针按文件数据顺序将其链接起来。特点：提高了磁盘空间利用率,不存在外部碎片问题；文件操作灵活（添加、删除等），有利于文件长度动态变化。（二）链接结构1、隐式链接文件名始址末址jeep925文件目录01234567891011121314151617181920212223242526272829303111016-125磁盘空间隐式链接问题：–只适合顺序访问，对随机访问是低效的。–可靠性差，因为只要其中任何一个指针出现问题，都会导致整个链断开。–指针占用空间。2.显式链接把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表对应整个磁盘，表的序号是物理盘块号。在每个表项中存放链接指针，即下一个盘块号。我们将该表称为文件分配表FAT。大大减少了访问磁盘的次数，提高了检索速度。2.显式链接012345物理块号2FCBFAT04516EOF11105EOF0123456789FATFCBA4FCBB9MS-DOS的文件物理结构（三）索引结构链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT(2)FAT需占用较大的内存空间。（三）索引结构索引结构文件不连续存放于文件存储器上，使用一张索引表来定位文件中的数据（类比页表）特点：既能顺序存取，又能随机存取，支持文件长度动态变化，外存利用率高，但索引表需占额外空间。单级索引结构：–为每个文件分配一个索引表，一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块多级索引结构：混合索引结构：1、单级索引结构012345678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep199171102519文件jeep的单级索引表问题：每建立一个文件，分配一个索引表，占用较多的外存空间。对于中小文件，一个索引表需要占用一个盘块，空间浪费。2.多级索引结构012¡¡¡¡¡105106254356357985105106254740356357¡1125985360740¡1125¡主索引（第一级索引）360第二级索引磁盘空间3.混合索引结构•将多种索引方式相结合而形成的一种分配方式。•例如，系统中即采用了直接地址，有采用了一级索引方式，或两级索引方式，甚至还采用了三级索引。•这种方式在UNIX系统中采用。•在UnixSystemV的索引点中，共设置了13个地址项，即iaddr(0)~iaddr(12)。它们把所有的地址项分成两类，即直接地址和间接地址。modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)directblockssingleindirectdoubleindirecttripleindirectdatadatadatadata……datadata………datadatadatadata(1)直接地址为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)~iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据的块号。假如每个块的大小为4KB，当文件不大于40KB时，便可直接从索引结点中读出该文件的全部块号。(2)一次间接地址对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个块号记入其中。在一次间址块中可存放1K个块号，因而允许文件长达4MB。(3)多次间接地址。当文件长度大于4MB+40KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的块号。在采用二次间址方式时，文件最大长度可达4GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TB。习题一设文件索引节点有8个索引项，其中4个地址项是直接地址索引，3个地址项是一级间接地址索引，1个地址项是二级间接地址索引。每个地址项大小为4个字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件的最大长度为多少KB?习题二普通文件采用UNIX三级索引结构，即文件控制块中给出13个磁盘地址，前10个磁盘地址指出文件前10块的物理地址，第11个磁盘地址指向一级索引表，一级索引表给出256个磁盘地址，即指出该文件第11块至第266块的物理地址；第12个磁盘地址指向二级索引表，二级索引表中指出256个一级索引表的地址；第13个磁盘地址指向三级索引表，三级索引表中指出256个二级索引表的地址。文件K的第7266块需要启动几级索引？习题三普通文件采用UNIX三级索引结构，即文件控制块中给出13个磁盘地址，前10个磁盘地址指出文件前10块的物理地址，第11个磁盘地址指向一级索引表，一级索引表给出256个磁盘地址，即指出该文件第11块至第266块的物理地址；第12个磁盘地址指向二级索引表，二级索引表中指出256个一级索引表的地址；第13个磁盘地址指向三级索引表，三级索引表中指出256个二级索引表的地址。访问文件K的第7266块需要启动几次磁盘？（假设已经找到了K文件的地址）5.2文件目录管理建立文件系统的作用在于对文件信息的“按名存取”，力求查找简便，减少查找时间。为了能对这些文件实施有效的管理，必须对它们加以妥善组织，这主要是通过文件目录实现的。文件目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。实现“按名存取”。提高对目录的检索速度。文件共享。允许文件重名。1、文件控制块•为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，即文件控制块。•文件控制块（FCB）的主要内容•文件名•创建者•存放方式：说明该文件在辅存的结构，如顺序结构、索引结构。•文件物理位置信息：具体说明文件在辅存的物理位置和范围，对于不同的物理结构，应做不同的说明，如索引表。•创建、修改时间、保存时间•口令：用于对文件访问进行验证•操作限制：如读、写、执行权限说明文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合目录项：构成文件目录的项目，即FCB目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件目录主要是为了系统快速实现“按名存取”而引入的，查目录是文件系统最频繁的操作，因此目录的合理组织很重要.