操作系统第6章 课件

第六章文件管理6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制第六章文件管理6.1文件和文件系统16.1文件和文件系统6.1.1文件、记录和数据项1.数据项(1)基本数据项。是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。例如，用于描述一个学生的基本数据项有：学号、姓名、年龄、所在班级等。基于文件系统的概念把数据的组成分为数据项、记录和文件三级。6.1文件和文件系统6.1.1文件、记录和数据项12(2)组合数据项。是由若干个基本数据项组成的，简称组项。如，作为组项的工资可由基本工资、工龄工资和奖励工资等基本项所组成。基本数据项除了数据名外，还应有数据类型。因为基本项仅是描述某个对象的属性，根据属性的不同，需要用不同的数据类型来描述。如，描述学生的学号，应使用整数；描述学生的姓名则应使用字符串(含汉字)；描述性别，用逻辑变量或汉字。可见，由数据项的名字和类型两者共同定义了一个数据项的“型”。而表征一个实体在数据项上的数据则称为“值”。例如，学号/30211、姓名/王有年、性别/男等。(2)组合数据项。是由若干个基本数据项组成32.记录记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于它所处的环境不同可把它作为不同的对象。如，一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。在诸多记录中，为了能惟一标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字。2.记录43.文件文件是具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。如，可以将一个班的学生记录作为一个文件。一个文件必须有一个文件名，它通常是由一串ASCII码或(和)汉字构成，名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中又规定可用14个字符。3.文件文件是具有文件名的一组相关元素的集5文件属性可以包括：文件类型(2)文件长度(3)文件的物理位置(4)文件的建立时间图6-1文件、记录和数据项之间的层次关系文件记录1记录2…记录n数据项1数据项2…数据项n文件属性可以包括：图6-1文件、记录和数据项之间的层次66.1.2文件类型和文件系统模型按用途分类系统文件(2)用户文件(3)库文件2)按文件中数据的形式分类源文件(2)目标文件(3)可执行文件6.1.2文件类型和文件系统模型按用途分类2)按文件中73)按存取控制属性分类只执行文件(2)只读文件(3)读写文件4)按组织形式和处理方式分类普通文件(2)目录文件(3)特殊文件3)按存取控制属性分类只执行文件4)按组织形式和处理方8图6-2文件系统模型2.文件系统模型图6-2文件系统模型2.文件系统模型91)对象及其属性文件管理系统管理的对象有：①文件。它是文件管理的直接对象。②目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。③磁盘(磁带)存储空间。文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。1)对象及其属性102)对对象操纵和管理的软件集合这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，包括：对文件存储空间的管理；对文件目录的管理；用于将文件的逻辑地址转换为物理地址的机制；对文件读和写的管理；以及对文件的共享与保护等功能。2)对对象操纵和管理的软件集合113)文件系统的接口为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口：(1)命令接口。指作为用户与文件系统交互的接口。用户可通过键盘终端键入命令，取得文件系统的服务。(2)程序接口。指用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。3)文件系统的接口126.1.3文件操作1.最基本的文件操作(1)创建文件(2)删除文件(3)读文件(4)写文件(5)截断文件：是将原有文件的长度设置为0，即放弃原有文件的内容。(6)设置文件的读/写位置6.1.3文件操作1.最基本的文件操作132.文件的“打开”和“关闭”操作“打开”，指系统将指定文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件在打开文件表中的表目删除掉。2.文件的“打开”和“关闭”操作“打开”143.其它文件操作一类是：有关对文件属性进行操作的。即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权，以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另一类是：有关目录的。如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。3.其它文件操作156.2文件的逻辑结构对于任何一个文件，都存在着以下两种形式的结构：（1）文件的逻辑结构(FileLogicalStructure)(2)文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。6.2文件的逻辑结构对于任何一个166.2.1文件逻辑结构的类型有结构文件记录长度分为：定长记录(2)变长记录可用多种方式组织这些记录：顺序文件：将定长记录按某种顺序排列所形成的文件。(2)索引文件：建立一张索引表，为每条变长记录设置一个表项。(3)索引顺序文件：为文件建立一张索引表，为每组记录中的第一个记录设置一个表项。6.2.1文件逻辑结构的类型有结构文件172.无结构文件如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。2.无结构文件186.2.2顺序文件1.逻辑记录的排序(1)串结构各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录，……依此类推。(2)顺序结构指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。6.2.2顺序文件1.逻辑记录的排序192.对顺序文件(SequentialFile)的读/写操作R0R1R2R3…Ri…LLLLLL2L3L4LL(i＋1)LRptr(a)定长记录文件L0R0L1R1…Ri…Rptr(b)变长记录文件Li00L0L0＋1L1L0＋L1＋2Li∑(Lk＋1)i－1k＝0∑(Lk＋1)ik＝0图6-3定长和变长记录文件2.对顺序文件(SequentialFile)的读/写操20读定长记录的顺序文件，可设置一个读指针Rptr，令它指向下一个记录的首地址，每当读完一个记录时，便执行：Rptr:=Rptr+L同样写操作也可设置一个写指针Wptr，使之指向要写的记录的首地址，每当写完一个记录时，便执行：Wptr:=Wptr+L但变长记录的顺序文件，每次执行读（或写）时，指针增加的值会因记录变长而不同，即：Rptr:=Rptr+Li或：Wptr:=Wptr+Li读定长记录的顺序文件，可设置一个读指针Rpt213.顺序文件的优缺点顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。如，一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5×103个记录；如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。3.顺序文件的优缺点顺序文件的最佳应用场合22顺序文件的另一个缺点是，如果想增加或删除一个记录，都比较困难。为了解决这一问题，可以为顺序文件配置一个运行记录文件(LogFile)或称为事务文件(TransactionFile)，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如4小时，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。顺序文件的另一个缺点是，如果想增加或删除一个236.2.3索引文件对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i×L然而，对于变长记录文件，要查找第i个记录时，须先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则6.2.3索引文件对于定长记录文件，如果24为方便检索，对变长记录采用索引表。1、索引表主文件中的一个记录，在索引表中有一个表项，记录该记录的长度和指向的指针（即该记录逻辑地址空间的首地址）。索引表是定长记录的顺序文件。2、检索方法检索文件时，根据用户提供的关键字，在索引表中，找相应的表项；用表项中的指针，到主文件中访问记录。为方便检索，对变长记录采用索引表。25图6-4索引文件的组织图6-4索引文件的组织263、增加一条记录时，需对索引表进行修改。4、优缺点索引表有较快的检索速度，从而提高了索引文件的检索速度。但比顺序文件，增加了一个索引表（提高了存储费用）。3、增加一条记录时，需对索引表进行修改。276.2.4索引顺序文件1、索引表将顺序文件中的所有记录分为若干组，为每组中的第一个记录，建立一个索引项，其中含该记录的关键字和指向该记录的指针。这样索引表小多了。2、检索方法检索文件时，根据用户提供的关键字，在索引表中，找该记录组中第一个记录的表项；用表项中的指针，得到主文件中的位置；利用顺序查找在主文件中找要求的记录。6.2.4索引顺序文件1、索引表28图6-5索引顺序文件图6-5索引顺序文件293、多级索引对于非常大的文件，可采用多级索引顺序文件，即可为索引表再建立一个索引表，形成两级或多级索引表。3、多级索引304、比较检索效率：例如：一个1000,000个记录的文件，采用顺序文件形式，平均查找记录为500,000；N/2。如果采用一级索引顺序文件形式（1000记录为一组），平均查找记录为500+500=1000；如果采用两级索引顺序文件形式（100为一组），平均查找记录为50+50+50=150。采用两级索引顺序文件形式，每级索引表都是100个表项，且100记录为一组。4、比较检索效率：如果采用一级索引顺序文件形316.2.5直接文件和哈希文件1.直接文件直接文件可以根据给定的记录键值，直接获得指定记录的物理地址。2.哈希文件Hash文件利用Hash函数，将记录键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。6.2.5直接文件和哈希文件1.直接文件32图6-6Hash文件的逻辑结构fHash函数目录表键值图6-6Hash文件的逻辑结构fHash函数目录表键值336.3外存分配方式为文件分配外存空间时，要考虑：有效利用外存空间；提高文件访问速度。6.3外存分配方式为文件分配外存空间时，要考虑：346.3.1连续分配连续分配是，逻辑文件中的记录，顺序地存储到邻接的各物理盘块中。这样形成的物理文件是顺序文件；这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用的盘块的顺序的一致性。在目录文件中的目录项应包含该文件第一个记录所在的盘块号和文件长度（也是以盘块计量）。1.连续分配方式6.3.1连续分配连续分配是，逻辑文件中351230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目录trf图6-7磁盘空间的连续分配123056749101181314151217181916362.连续分配的主要优缺点连续分配的主要优点如下：顺序访问容易。(2)顺序访问速度快。磁头移动距离少。2.连续分配的主要优缺点连续分配的主要优点如下：37连续分配的主要缺点如下：要求有连续的存储空间。并会形成严重的外存外部碎片（切割剩下的部分）。一定时间，需要“紧凑”剩余残片。(2)必须事先知道文件的长度。这有时很难做到，尤其是动态增长的文件。连续分配的主要缺点如下：386.3.2链接分配1.隐式链接将文件装在多个离散的盘块中，通过链接指针将这些盘块链接成一个链表。链接方式可采用两种方法：在文件目录中，每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针；而每个盘块中又含有一个指向下一个盘块的指针。缺点是，只适合于顺序访问，随机访问效率低。可靠性差，一个指针出现问题，整个链都失效。6.3.2链接分配1.隐式链接将文件39图6-8磁盘空间的链接式分配25123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116图6-8磁盘空间的链接式分配2512305674910402.显式链接将链接文件的各物理块的指针统一放在一个内存中的链表中，分给该文件的所有盘块号都放在其中，称该表为文件分配表FAT（FileAllocationTables）。每个表项中，存放链接指针，指向下一个盘块。文件的第一盘块号需填到该文件的FCB的“物理地址”中。2.显式链接将链接文件的各物理块的指针统41图6-9显式链接结构012345物理块号2FCBFAT0451图6-9显式链接结构012345物理块号2FCBFAT426.3.3FAT和NTFS技术磁盘→分区（卷）→簇→盘块（扇区）1．FAT12（1）以盘块为基本分配单位MS-DOS的FAT文件系统中，引入了“卷”的概念，最多可将硬盘分为四个卷（逻辑磁盘），每个卷都是一个能够被单独格式化和使用的逻辑单元。一个卷中包含了文件系统信息、一组文件以及空闲空间；并有单独区域存放自己的目录和FAT表。6.3.3FAT和NTFS技术磁盘→分区（卷）→簇→盘块43MS-DOS的FAT12文件系统中，每个分区都有两张文件分配表FAT1和FAT2，FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接指针，通过它将一个文件的所有的盘块链接起来，而将文件的第一盘块号放在自己的FCB中。MS-DOS的FAT12文件系统中，每个分区44（2）簇的基本概念簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2的整数倍个盘块，如一个扇区，两个扇区，四个扇区，八个扇区。簇的好处是能适应磁盘容量不断增大的情况，并减少FAT表的表项数，减少存取开销，提高文件系统的效率。但造成更大的簇内碎片。（3）FAT12存在问题：对所允许的磁盘容量存在着严重的限制，最多数十兆；簇内碎片增加；只支持8+3文件名。（2）簇的基本概念45FAT表项占位FAT表中最多允许表项磁盘每分区的容量四个逻辑分区最大容量支持的系统支持的文件名FAT12（以盘块为基本分配单位）12位40962MB8MBMS-DOS8字符文件名+3字符扩展名FAT12（以簇为基本分配单位，一簇包含两扇区）4MB16MBFAT12（以簇为基本分配单位，一簇包含八扇区）16MB64MB以盘块和簇为基本分配单位的比较FAT表项占位FAT表中最多允许表项磁盘每分区的容量四个逻辑466EOF11105EOF0123456789FATFCBA4FCBB9图6-10MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCBA472．FAT16比FAT12的宽度（位数）增加，最大表项增加，最大分区空间增加。但，对FAT12的局限性改善有限；随着磁盘容量增加，簇内碎片越大。不支持长文件名。扩展的FAT12—VFAT（Virtual）文件名可长达255个字符。2．FAT1648FAT表项占位FAT表中最多允许表项最大分区空间的容量支持的系统支持的文件名FAT16（以簇为基本分配单位，一簇包含64扇区）（簇的盘块数可为4、8、16、32、64）16位655362048MB2GBMS-DOSWindows958字符文件名+3字符扩展名FAT表项占位FAT表中最多允许表项最大分区空间的容量支持的493．FAT32为了减少簇内碎片，就应选择较小的簇。FAT32的每个簇固定为4KB。单个最大磁盘空间达到：（P219最上面有错）3．FAT32（P219最上面有错）50FAT表项占位FAT表中最多允许表项最大磁盘空间的容量应用的系统支持的文件名FAT32（以簇为基本分配单位，一簇固定为4KB，8扇区）32位4294967296（4G）16TBWindows98/ME/NT/2000/XP255字符FAT表项占位FAT表中最多允许表项最大磁盘空间的容量应用的51簇包含块数簇大小/KBFAT12/MBFAT16/MBFAT32/TB10.522144281288416256161685122321610242643220482簇包含块数簇大小/KBFAT12/MBFAT16/MBFAT52FAT32的优缺点：比FAT16支持更小的簇和更大的磁盘容量，这就减少了磁盘碎片，减少了磁盘空间的浪费。但，明显不足是：由于文件分配表的扩大，运行速度比FAT16慢；FAT32有最小管理空间的限制；不能保持向下兼容。FAT32的优缺点：534．NTFS（NewTechnologyFileSystem）为WindowsNT专门开发的。新特征：(1)使用了64位磁盘地址，理论上可支持字节的磁盘分区；(2)支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符；(3)具有容错功能，即系统出错，可保证系统正常运行；(4)提供了数据的一致性；(5)提供了文件加密、文件压缩功能。4．NTFS（NewTechnologyFileSy542）磁盘组织：以簇为磁盘空间的分配和回收的基本单位。通过簇来间接管理磁盘，可不需知道盘块的大小，即与扇区大小无关的独立性，很容易支持扇区大小非标准的磁盘。磁盘的卷的簇的大小称为“卷因子”，在磁盘格式化时确定。对于小磁盘（≤512MB），默认簇大小为512字节；对于1GB磁盘，默认簇大小为1KB；对于2GB磁盘，默认簇大小为4KB。2）磁盘组织：55簇的定位，采用逻辑簇号LCN（LogicalClusterNumber）和虚拟簇号VCN（VirtualClusterNumber）。LCN以卷为单位，将整个卷中所有的簇按顺序进行简单编号，NTFS在进行地址映射时，可通过卷因子与LCN的乘积，便可算出卷上的物理字节偏移量，从而得到文件数据所在的物理磁盘地址。为了方便文件中的数据的引用，可使用VCN，以文件为单位，将属于某文件的簇按顺序进行编号。只要知道文件的开始簇的地址，便可将VCN映射到LCN。簇的定位，采用逻辑簇号LCN（Logical563)文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT（MasterFileTable）中。MFT表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1KB，每行称为该行所对应文件的元数据（metadata），也称为文件控制字。3)文件的组织57MFT表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织在所对应文件的一组属性中。由于文件大小相差悬殊，其属性所需空间大小也相差很大，因此，在MFT表中，对于元数据的1KB空间，可能记录不下文件的全部信息。所以当文件较小时，其属性值所占空间也较小，可以将文件的所有属性直接记录在元数据中。而当文件较大时，元数据仅记录该文件的一部分属性，其余属性，如文件的内容等，可以记录到卷中的其他可用簇中，并将这些簇按其所记录文件的属性进行分类，分别链接成多个队列，将指向这些队列的指针保存在元数据中。MFT表中，每个元数据将其所对应文件的所有信58例如：对于一个文件的真正数据，即文件DATA属性，如果很小，就直接存储在MFT表中对应的元数据中，这样对文件数据的访问，仅需要对MFT表进行即可，减少了磁盘访问次数，较大地提高了对小文件存取的效率。如果文件较大，则文件的真正数据往往保存在其他簇中。此时通过元数据中指向文件DATA属性的队列指针，可以方便地查找到这些簇，完成对文件数据的访问。例如：对于一个文件的真正数据，即文件DAT59文件在存储过程中，数据往往连续存放在若干个相邻的簇中，仅用一个指针记录这几个相邻的簇即可，而不是每个簇需要一个指针，从而可以节省指针所耗费的空间。一般地，采用上述的方式，只需十几个字节就可以含有FAT32所需几百个KB才能拥有的信息量。不足：它只能被WindowsNT所识别。NTFS文件系统可以存取FAT等文件系统的文件，但NTFS文件却不能被FAT等文件系统所存取，缺乏兼容性。Windows95/98/98SE/Me都不能识别NTFS文件系统。文件在存储过程中，数据往往连续存放在若干个相606.3.4索引分配1.单级索引分配链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。只有将整个FAT调入内存才能保证在FAT中找到一个文件的所有盘块号。6.3.4索引分配1.单级索引分配61解决办法是：只将该文件所占用的盘块号调入内存，即将该文件占用的盘块编号集中地存放在一个索引块中。就是索引分配方式。为每个文件分配一个索引块，把分配给它的所有盘块号，都放在其中，即该索引块就是一个盘块号的数组。在建立文件时，为它建立一个目录项（其中填上索引块的盘块号），索引块中放的是该文件的所有盘块号。解决办法是：62图6-12索引分配方式123056749101181314151217181916212223202526272429303128countfile块序号jeep19目录91611025－1－1－119图6-12索引分配方式123056749101181363优点是，支持直接访问，可直接从索引块中找到某盘块号；不会产生外部碎片；对于单个较大文件，比链接方式占用的空间小。缺点是，索引块的数量随文件数量增多，占外存空间。相对来说，大文件效果好。但索引块中的盘块号的数组会越大。优点是，支持直接访问，可直接从索引块中找到某642.多级索引分配当文件很大时，所需盘块增加，索引块中的盘块号也会增加。可以分级索引，来减少每个索引块中的盘块号的数量，并将它们用链接指针链接起来。2.多级索引分配当文件很大时，所需盘块增加65012……………105106254356357985105106254740356357…1125985360740…1125…主索引360第二级索引磁盘空间图6-13两级索引分配012……………1051062543563579851051663.混合索引分配方式在UNIX系统中采用了这种混合分配方式，较充分地利用了各种分配方式的优点。在UNIXSystemV的索引结点中，共设置了13个地址项。3.混合索引分配方式在UNIX系统中采用了67图6-14混合索引方式modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)directblockssingleindirectdoubleindirecttripleindirectdatadatadatadata……datadata………datadatadatadata图6-14混合索引方式modeowners(2)ti68(1)直接地址。为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)~iaddr(9)来存放直接地址。在这里的每项中所存放的是该文件数据盘块的盘块号。假如每个盘块的大小为4KB，当文件不大于40KB时，便可直接从索引结点中读出该文件的全部盘块号。(1)直接地址。69(2)一次间接地址。对于大、中型文件，除采用直接地址外，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1K个盘块号，因而允许文件长达4MB。(2)一次间接地址。70(3)多次间接地址。当文件长度大于4MB+40KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TB。(3)多次间接地址。71第六章文件管理6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制第六章文件管理6.1文件和文件系统726.1文件和文件系统6.1.1文件、记录和数据项1.数据项(1)基本数据项。是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。例如，用于描述一个学生的基本数据项有：学号、姓名、年龄、所在班级等。基于文件系统的概念把数据的组成分为数据项、记录和文件三级。6.1文件和文件系统6.1.1文件、记录和数据项173(2)组合数据项。是由若干个基本数据项组成的，简称组项。如，作为组项的工资可由基本工资、工龄工资和奖励工资等基本项所组成。基本数据项除了数据名外，还应有数据类型。因为基本项仅是描述某个对象的属性，根据属性的不同，需要用不同的数据类型来描述。如，描述学生的学号，应使用整数；描述学生的姓名则应使用字符串(含汉字)；描述性别，用逻辑变量或汉字。可见，由数据项的名字和类型两者共同定义了一个数据项的“型”。而表征一个实体在数据项上的数据则称为“值”。例如，学号/30211、姓名/王有年、性别/男等。(2)组合数据项。是由若干个基本数据项组成742.记录记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于它所处的环境不同可把它作为不同的对象。如，一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。在诸多记录中，为了能惟一标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字。2.记录753.文件文件是具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。如，可以将一个班的学生记录作为一个文件。一个文件必须有一个文件名，它通常是由一串ASCII码或(和)汉字构成，名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中又规定可用14个字符。3.文件文件是具有文件名的一组相关元素的集76文件属性可以包括：文件类型(2)文件长度(3)文件的物理位置(4)文件的建立时间图6-1文件、记录和数据项之间的层次关系文件记录1记录2…记录n数据项1数据项2…数据项n文件属性可以包括：图6-1文件、记录和数据项之间的层次776.1.2文件类型和文件系统模型按用途分类系统文件(2)用户文件(3)库文件2)按文件中数据的形式分类源文件(2)目标文件(3)可执行文件6.1.2文件类型和文件系统模型按用途分类2)按文件中783)按存取控制属性分类只执行文件(2)只读文件(3)读写文件4)按组织形式和处理方式分类普通文件(2)目录文件(3)特殊文件3)按存取控制属性分类只执行文件4)按组织形式和处理方79图6-2文件系统模型2.文件系统模型图6-2文件系统模型2.文件系统模型801)对象及其属性文件管理系统管理的对象有：①文件。它是文件管理的直接对象。②目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。③磁盘(磁带)存储空间。文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。1)对象及其属性812)对对象操纵和管理的软件集合这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，包括：对文件存储空间的管理；对文件目录的管理；用于将文件的逻辑地址转换为物理地址的机制；对文件读和写的管理；以及对文件的共享与保护等功能。2)对对象操纵和管理的软件集合823)文件系统的接口为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口：(1)命令接口。指作为用户与文件系统交互的接口。用户可通过键盘终端键入命令，取得文件系统的服务。(2)程序接口。指用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。3)文件系统的接口836.1.3文件操作1.最基本的文件操作(1)创建文件(2)删除文件(3)读文件(4)写文件(5)截断文件：是将原有文件的长度设置为0，即放弃原有文件的内容。(6)设置文件的读/写位置6.1.3文件操作1.最基本的文件操作842.文件的“打开”和“关闭”操作“打开”，指系统将指定文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件在打开文件表中的表目删除掉。2.文件的“打开”和“关闭”操作“打开”853.其它文件操作一类是：有关对文件属性进行操作的。即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权，以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另一类是：有关目录的。如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。3.其它文件操作866.2文件的逻辑结构对于任何一个文件，都存在着以下两种形式的结构：（1）文件的逻辑结构(FileLogicalStructure)(2)文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。6.2文件的逻辑结构对于任何一个876.2.1文件逻辑结构的类型有结构文件记录长度分为：定长记录(2)变长记录可用多种方式组织这些记录：顺序文件：将定长记录按某种顺序排列所形成的文件。(2)索引文件：建立一张索引表，为每条变长记录设置一个表项。(3)索引顺序文件：为文件建立一张索引表，为每组记录中的第一个记录设置一个表项。6.2.1文件逻辑结构的类型有结构文件882.无结构文件如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。2.无结构文件896.2.2顺序文件1.逻辑记录的排序(1)串结构各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录，……依此类推。(2)顺序结构指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。6.2.2顺序文件1.逻辑记录的排序902.对顺序文件(SequentialFile)的读/写操作R0R1R2R3…Ri…LLLLLL2L3L4LL(i＋1)LRptr(a)定长记录文件L0R0L1R1…Ri…Rptr(b)变长记录文件Li00L0L0＋1L1L0＋L1＋2Li∑(Lk＋1)i－1k＝0∑(Lk＋1)ik＝0图6-3定长和变长记录文件2.对顺序文件(SequentialFile)的读/写操91读定长记录的顺序文件，可设置一个读指针Rptr，令它指向下一个记录的首地址，每当读完一个记录时，便执行：Rptr:=Rptr+L同样写操作也可设置一个写指针Wptr，使之指向要写的记录的首地址，每当写完一个记录时，便执行：Wptr:=Wptr+L但变长记录的顺序文件，每次执行读（或写）时，指针增加的值会因记录变长而不同，即：Rptr:=Rptr+Li或：Wptr:=Wptr+Li读定长记录的顺序文件，可设置一个读指针Rpt923.顺序文件的优缺点顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。如，一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5×103个记录；如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。3.顺序文件的优缺点顺序文件的最佳应用场合93顺序文件的另一个缺点是，如果想增加或删除一个记录，都比较困难。为了解决这一问题，可以为顺序文件配置一个运行记录文件(LogFile)或称为事务文件(TransactionFile)，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如4小时，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。顺序文件的另一个缺点是，如果想增加或删除一个946.2.3索引文件对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i×L然而，对于变长记录文件，要查找第i个记录时，须先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则6.2.3索引文件对于定长记录文件，如果95为方便检索，对变长记录采用索引表。1、索引表主文件中的一个记录，在索引表中有一个表项，记录该记录的长度和指向的指针（即该记录逻辑地址空间的首地址）。索引表是定长记录的顺序文件。2、检索方法检索文件时，根据用户提供的关键字，在索引表中，找相应的表项；用表项中的指针，到主文件中访问记录。为方便检索，对变长记录采用索引表。96图6-4索引文件的组织图6-4索引文件的组织973、增加一条记录时，需对索引表进行修改。4、优缺点索引表有较快的检索速度，从而提高了索引文件的检索速度。但比顺序文件，增加了一个索引表（提高了存储费用）。3、增加一条记录时，需对索引表进行修改。986.2.4索引顺序文件1、索引表将顺序文件中的所有记录分为若干组，为每组中的第一个记录，建立一个索引项，其中含该记录的关键字和指向该记录的指针。这样索引表小多了。2、检索方法检索文件时，根据用户提供的关键字，在索引表中，找该记录组中第一个记录的表项；用表项中的指针，得到主文件中的位置；利用顺序查找在主文件中找要求的记录。6.2.4索引顺序文件1、索引表99图6-5索引顺序文件图6-5索引顺序文件1003、多级索引对于非常大的文件，可采用多级索引顺序文件，即可为索引表再建立一个索引表，形成两级或多级索引表。3、多级索引1014、比较检索效率：例如：一个1000,000个记录的文件，采用顺序文件形式，平均查找记录为500,000；N/2。如果采用一级索引顺序文件形式（1000记录为一组），平均查找记录为500+500=1000；如果采用两级索引顺序文件形式（100为一组），平均查找记录为50+50+50=150。采用两级索引顺序文件形式，每级索引表都是100个表项，且100记录为一组。4、比较检索效率：如果采用一级索引顺序文件形1026.2.5直接文件和哈希文件1.直接文件直接文件可以根据给定的记录键值，直接获得指定记录的物理地址。2.哈希文件Hash文件利用Hash函数，将记录键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。6.2.5直接文件和哈希文件1.直接文件103图6-6Hash文件的逻辑结构fHash函数目录表键值图6-6Hash文件的逻辑结构fHash函数目录表键值1046.3外存分配方式为文件分配外存空间时，要考虑：有效利用外存空间；提高文件访问速度。6.3外存分配方式为文件分配外存空间时，要考虑：1056.3.1连续分配连续分配是，逻辑文件中的记录，顺序地存储到邻接的各物理盘块中。这样形成的物理文件是顺序文件；这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用的盘块的顺序的一致性。在目录文件中的目录项应包含该文件第一个记录所在的盘块号和文件长度（也是以盘块计量）。1.连续分配方式6.3.1连续分配连续分配是，逻辑文件中1061230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目录trf图6-7磁盘空间的连续分配1230567491011813141512171819161072.连续分配的主要优缺点连续分配的主要优点如下：顺序访问容易。(2)顺序访问速度快。磁头移动距离少。2.连续分配的主要优缺点连续分配的主要优点如下：108连续分配的主要缺点如下：要求有连续的存储空间。并会形成严重的外存外部碎片（切割剩下的部分）。一定时间，需要“紧凑”剩余残片。(2)必须事先知道文件的长度。这有时很难做到，尤其是动态增长的文件。连续分配的主要缺点如下：1096.3.2链接分配1.隐式链接将文件装在多个离散的盘块中，通过链接指针将这些盘块链接成一个链表。链接方式可采用两种方法：在文件目录中，每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针；而每个盘块中又含有一个指向下一个盘块的指针。缺点是，只适合于顺序访问，随机访问效率低。可靠性差，一个指针出现问题，整个链都失效。6.3.2链接分配1.隐式链接将文件110图6-8磁盘空间的链接式分配25123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116图6-8磁盘空间的链接式分配25123056749101112.显式链接将链接文件的各物理块的指针统一放在一个内存中的链表中，分给该文件的所有盘块号都放在其中，称该表为文件分配表FAT（FileAllocationTables）。每个表项中，存放链接指针，指向下一个盘块。文件的第一盘块号需填到该文件的FCB的“物理地址”中。2.显式链接将链接文件的各物理块的指针统112图6-9显式链接结构012345物理块号2FCBFAT0451图6-9显式链接结构012345物理块号2FCBFAT1136.3.3FAT和NTFS技术磁盘→分区（卷）→簇→盘块（扇区）1．FAT12（1）以盘块为基本分配单位MS-DOS的FAT文件系统中，引入了“卷”的概念，最多可将硬盘分为四个卷（逻辑磁盘），每个卷都是一个能够被单独格式化和使用的逻辑单元。一个卷中包含了文件系统信息、一组文件以及空闲空间；并有单独区域存放自己的目录和FAT表。6.3.3FAT和NTFS技术磁盘→分区（卷）→簇→盘块114MS-DOS的FAT12文件系统中，每个分区都有两张文件分配表FAT1和FAT2，FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接指针，通过它将一个文件的所有的盘块链接起来，而将文件的第一盘块号放在自己的FCB中。MS-DOS的FAT12文件系统中，每个分区115（2）簇的基本概念簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2的整数倍个盘块，如一个扇区，两个扇区，四个扇区，八个扇区。簇的好处是能适应磁盘容量不断增大的情况，并减少FAT表的表项数，减少存取开销，提高文件系统的效率。但造成更大的簇内碎片。（3）FAT12存在问题：对所允许的磁盘容量存在着严重的限制，最多数十兆；簇内碎片增加；只支持8+3文件名。（2）簇的基本概念116FAT表项占位FAT表中最多允许表项磁盘每分区的容量四个逻辑分区最大容量支持的系统支持的文件名FAT12（以盘块为基本分配单位）12位40962MB8MBMS-DOS8字符文件名+3字符扩展名FAT12（以簇为基本分配单位，一簇包含两扇区）4MB16MBFAT12（以簇为基本分配单位，一簇包含八扇区）16MB64MB以盘块和簇为基本分配单位的比较FAT表项占位FAT表中最多允许表项磁盘每分区的容量四个逻辑1176EOF11105EOF0123456789FATFCBA4FCBB9图6-10MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCBA1182．FAT16比FAT12的宽度（位数）增加，最大表项增加，最大分区空间增加。但，对FAT12的局限性改善有限；随着磁盘容量增加，簇内碎片越大。不支持长文件名。扩展的FAT12—VFAT（Virtual）文件名可长达255个字符。2．FAT16119FAT表项占位FAT表中最多允许表项最大分区空间的容量支持的系统支持的文件名FAT16（以簇为基本分配单位，一簇包含64扇区）（簇的盘块数可为4、8、16、32、64）16位655362048MB2GBMS-DOSWindows958字符文件名+3字符扩展名FAT表项占位FAT表中最多允许表项最大分区空间的容量支持的1203．FAT32为了减少簇内碎片，就应选择较小的簇。FAT32的每个簇固定为4KB。单个最大磁盘空间达到：（P219最上面有错）3．FAT32（P219最上面有错）121FAT表项占位FAT表中最多允许表项最大磁盘空间的容量应用的系统支持的文件名FAT32（以簇为基本分配单位，一簇固定为4KB，8扇区）32位4294967296（4G）16TBWindows98/ME/NT/2000/XP255字符FAT表项占位FAT表中最多允许表项最大磁盘空间的容量应用的122簇包含块数簇大小/KBFAT12/MBFAT16/MBFAT32/TB10.522144281288416256161685122321610242643220482簇包含块数簇大小/KBFAT12/MBFAT16/MBFAT123FAT32的优缺点：比FAT16支持更小的簇和更大的磁盘容量，这就减少了磁盘碎片，减少了磁盘空间的浪费。但，明显不足是：由于文件分配表的扩大，运行速度比FAT16慢；FAT32有最小管理空间的限制；不能保持向下兼容。FAT32的优缺点：1244．NTFS（NewTechnologyFileSystem）为WindowsNT专门开发的。新特征：(1)使用了64位磁盘地址，理论上可支持字节的磁盘分区；(2)支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符；(3)具有容错功能，即系统出错，可保证系统正常运行；(4)提供了数据的一致性；(5)提供了文件加密、文件压缩功能。4．NTFS（NewTechnologyFileSy1252）磁盘组织：以簇为磁盘空间的分配和回收的基本单位。通过簇来间接管理磁盘，可不需知道盘块的大小，即与扇区大小无关的独立性，很容易支持扇区大小非标准的磁盘。磁盘的卷的簇的大小称为“卷因子”，在磁盘格式化时确定。对于小磁盘（≤512MB），默认簇大小为512字节；对于1GB磁盘，默认簇大小为1KB；对于2GB磁盘，默认簇大小为4KB。2）磁盘组织：126簇的定位，采用逻辑簇号LCN（LogicalClusterNumber）和虚拟簇号VCN（VirtualClusterNumber）。LCN以卷为单位，将整个卷中所有的簇按顺序进行简单编号，NTFS在进行地址映射时，可通过卷因子与LCN的乘积，便可算出卷上的物理字节偏移量，从而得到文件数据所在的物理磁盘地址。为了方便文件中的数据的引用，可使用VCN，以文件为单位，将属于某文件的簇按顺序进行编号。只要知道文件的开始簇的地址，便可将VCN映射到LCN。簇的定位，采用逻辑簇号LCN（Logical1273)文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT（MasterFileTable）中。MFT表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1KB，每行称为该行所对应文件的元数据（metadata），也称为文件控制字。3)文件的组织128MFT表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织在所对应文件的一组属性中。由于文件大小相差悬殊，其属性所需空间大小也相差很大，因此，在MFT表中，对于元数据的1KB空间，可能记录不下文件的全部信息。所以当文件较小时，其属性值所占空间也较小，可以将文件