《文件管理》PPT课件.ppt

第六章 文 件 管 理,6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性控制,文件管理(File System Management),教学目的： 计算机系统中使用的大量程序和数据都以文件形式存放在外存。操作系统中增加了文件管理功能即构成文件系统，它负责管理在外存上的文件，并把对文件的存取共享和保护等手段提供给操作系统和用户，这不仅方便了用户，保证了文件的安全性，还有效地提高系统资源的利用率。,教学要求：,掌握文件和文件系统的定义，了解文件系统的类型、文件系统模型和操作系统(Windows98/NT 、Linux )对多种文件系统的支持。 掌握文件的逻辑结构，熟悉五种记录文件。 掌握文件控制块和多级目录结构，掌握UNIX树型带勾连的目录结构和可装卸文件系统，了解Windows98 VFAT目录结构。熟悉目录查询技术，掌握内存的目录管理表，掌握文件操作与目录管理关系。 掌握基于索引节点的共享方式和利用符号连接的文件共享。 掌握文件的存取控制，熟悉分级安全管理，了解文件的转储和恢复，了解WindowsNT安全性。,6.1 文件和文件系统,6.1.1 文件、记录和数据项 1数据项 在文件系统中，数据项是最低级的数据组织形式，可把它分成以下两种类型: (1) 基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。例如，用于描述一个学生的基本数据项有学号、姓名、年龄、所在班级等。,(2) 组合数据项。它是由若干个基本数据项组成的，简称组项。例如，经理便是个组项，它由正经理和副经理两个基本项组成。又如，工资也是个组项，它可由基本工资、工龄工资和奖励工资等基本项所组成。 基本数据项除了数据名外，还应有数据类型。因为基本项仅是描述某个对象的属性，根据属性的不同，需要用不同的数据类型来描述。例如，在描述学生的学号时，应使用整数；描述学生的姓名则应使用字符串(含汉字)；描述性别时，可用逻辑变量或汉字。可见，由数据项的名字和类型两者共同定义了一个数据项的“型”。而表征一个实体在数据项上的数据则称为“值”。例如，学号/30211、姓名/王有年、性别/男等。,2记录 记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把他作为不同的对象。例如，一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。但若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项。,在诸多记录中，为了能惟一地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字(key)。或者说，关键字是惟一能标识一个记录的数据项。通常，只需用一个数据项作为关键字。例如，前面的病历号或学号便可用来从诸多记录中标识出惟一的一个记录。然而有时找不到这样的数据项，只好把几个数据项定为能在诸多记录中惟一地标识出某个记录的关键字。,3文件 文件是指由创建者所定义的、存贮在某种介质上的（如磁盘、磁带等）并具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例如，可以将一个班的学生记录作为一个文件。一个文件必须要有一个文件名，它通常是由一串ASCII码或(和)汉字构成的，名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中又规定可用14个字符。用户利用文件名来访问文件。,此外，文件应具有自己的属性，属性可以包括： (1) 文件类型。可以从不同的角度来规定文件的类型，如源文件、目标文件及可执行文件等。 (2) 文件长度。文件长度指文件的当前长度，长度的单位可以是字节、字或块，也可能是最大允许的长度。 (3) 文件的物理位置。该项属性通常是用于指示文件在哪一个设备上及在该设备的哪个位置的指针。 (4) 文件的建立时间。这是指文件最后一次的修改时间等。,图6-1 文件、记录和数据项之间的层次关系,6.1.2 文件类型和文件系统模型 1文件类型 为了便于管理和控制文件而将文件分成若干种类型。由于不同系统对文件的管理方式不同，因而它们对文件的分类方法也有很大差异。为了方便系统和用户了解文件的类型，在许多OS中都把文件类型作为扩展名而缀在文件名的后面，在文件名和扩展名之间用“.”号隔开。下面是常用的几种文件分类方法。,1) 按用途分类 根据文件的性质和用途的不同，可将文件分为三类: (1) 系统文件。这是指由系统软件构成的文件。大多数的系统文件只允许用户调用，但不允许用户去读，更不允许修改；有的系统文件不直接对用户开放。 (2) 用户文件。指由用户的源代码、目标文件、可执行文件或数据等所构成的文件。用户将这些文件委托给系统保管。 (3) 库文件。这是由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用，但不允许修改。,2) 按文件中数据的形式分类 按这种方式分类，也可把文件分为三类： (1) 源文件。这是指由源程序和数据构成的文件。通常由终端或输入设备输入的源程序和数据所形成的文件都属于源文件。它通常是由ASCII码或汉字所组成的。 (2) 目标文件。这是指把源程序经过相应语言的编译程序编译过，但尚未经过链接程序链接的目标代码所构成的文件。它属于二进制文件。通常，目标文件所使用的后缀名是“.obj”。 (3) 可执行文件。这是指把编译后所产生的目标代码再经过链接程序链接后所形成的文件。,3) 按存取控制属性分类 根据系统管理员或用户所规定的存取控制属性，可将文件分为三类： (1) 只执行文件。该类文件只允许被核准的用户调用执行，既不允许读，更不允许写。 (2) 只读文件。该类文件只允许文件主及被核准的用户去读，但不允许写。 (3) 读写文件。这是指允许文件主和被核准的用户去读或写的文件。,4) 按组织形式和处理方式分类 根据文件的组织形式和系统对其的处理方式，可将文件分为三类： (1) 普通文件：由ASCII码或二进制码组成的字符文件。一般用户建立的源程序文件、数据文件、目标代码文件及操作系统自身代码文件、库文件、实用程序文件等都是普通文件，它们通常存储在外存储设备上。 (2) 目录文件：由文件目录组成的，用来管理和实现文件系统功能的系统文件，通过目录文件可以对其它文件的信息进行检索。由于目录文件也是由字符序列构成，因此对其可进行与普通文件一样的种种文件操作。,(3) 特殊文件：特指系统中的各类I/O设备。为了便于统一管理，系统将所有的输入/输出设备都视为文件，按文件方式提供给用户使用，如目录的检索、权限的验证等都与普通文件相似，只是对这些文件的操作是和设备驱动程序紧密相连的，系统将这些操作转为对具体设备的操作。根据设备数据交换单位的不同，又可将特殊文件分为块设备文件和字符设备文件。前者用于磁盘、光盘或磁带等块设备的I/O 操作，而后者用于终端、打印机等字符设备的I/O 操作。,2文件系统模型 图6-2示出了文件系统的模型。可将该模型分为三个层次，其最底层是对象及其属性；中间层是对对象进行操纵和管理的软件集合；最高层是文件系统提供给用户的接口。,图6-2 文件系统模型,File System Software Architecture,Logical I/O,Pile,Sequential,Indexed Sequential,Indexed,Hashed,Basic I/O Supervisor,Basic (Physical) File System,Disk Device Driver,Tape Device Driver,User Program,Logical I/O,File Organization File Logical Structure,1) 对象及其属性 文件管理系统管理的对象有： 文件。它作为文件管理的直接对象。 目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录，每个目录项中，必须含有文件名及该文件所在的物理地址(或指针)。对目录的组织和管理是方便用户和提高对文件存取速度的关键。 磁盘(磁带)存储空间。文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。,2) 对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括: 对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、对文件读和写的管理，以及对文件的共享与保护等功能。,3) 文件系统的接口 为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口: (1) 命令接口。 这是指作为用户与文件系统交互的接口。 用户可通过键盘终端键入命令，取得文件系统的服务。 (2) 程序接口。这是指作为用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。,文件系统的定义: 文件系统是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构（如目录和索引表等）的集合。从系统角度来看，文件系统是对文件存储器的存储空间进行组织、分配和回收，负责文件的存储、检索、共享和保护。从用户角度来看，文件系统主要是实现“按名取存”，文件系统的用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。,6.1.3 文件操作 1最基本的文件操作 (1) 创建文件。在创建一个新文件时，系统首先要为新文件分配必要的外存空间，并在文件系统的目录中，为之建立一个目录项。目录项中应记录新文件的文件名及其在外存的地址等属性。 (2) 删除文件。当已不再需要某文件时，可将它从文件系统中删除。在删除时，系统应先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。,(3) 读文件。在读一个文件时，须在相应系统调用中给出文件名和应读入的内存目标地址。此时，系统同样要查找目录，找到指定的目录项，从中得到被读文件在外存中的位置。在目录项中，还有一个指针用于对文件的读/写。 (4) 写文件。在写一个文件时，须在相应系统调用中给出该文件名及该文件在内存中的(源)地址。为此，也同样须先查找目录，找到指定文件的目录项，再利用目录中的写指针进行写操作。,(5) 截断文件。如果一个文件的内容已经陈旧而需要全部更新时，一种方法是将此文件删除，再重新创建一个新文件。但如果文件名及其属性均无改变时，则可采取另一种所谓的截断文件的方法，此即将原有文件的长度设置为0，或者说是放弃原有的文件内容。 (6) 设置文件的读/写位置。前述的文件读/写操作都只提供了对文件顺序存取的手段，即每次都是从文件的始端读或写。设置文件读/写位置的操作，用于设置文件读/写指针的位置，以便每次读/写文件时，不是从其始端而是从所设置的位置开始操作。也正因如此，才能改顺序存取为随机存取。,2文件的“打开”和“关闭”操作 当前OS所提供的大多数对文件的操作，其过程大致都是这样两步: 第一步是通过检索文件目录来找到指定文件的属性及其在外存上的位置；第二步是对文件实施相应的操作，如读文件或写文件等。当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在大多数OS中都引入了“打开”(open)这一文件系统调用，当用户第一次请求对某文件进行操作时，先利用open系统调用将该文件打开。,所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉。,3其它文件操作 为了方便用户使用文件，通常，OS都提供了数条有关文件操作的系统调用，可将这些调用分成若干类: 最常用的一类是有关对文件属性进行操作的，即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权，以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另一类是有关目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。,6.2 文件的逻辑结构,6.2.1 文件逻辑结构的类型 1有结构文件 在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。 (1) 定长记录。这是指文件中所有记录的长度都是相同的，所有记录中的各数据项都处在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录的处理方便、开销小，所以这是目前较常用的一种记录格式，被广泛用于数据处理中。,(2) 变长记录。这是指文件中各记录的长度不相同。产生变长记录的原因，可能是由于一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等；也可能是数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。不论是哪一种，在处理前，每个记录的长度是可知的。 根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件： (1) 顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。,(2) 索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。 (3) 索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。,2无结构文件 如果说大量的数据结构和数据库是采用有结构的文件形式的话，则大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读/写指针来指出下一个要访问的字符。可以把流式文件看做是记录式文件的一个特例。在UNIX系统中，所有的文件都被看做是流式文件，即使是有结构文件，也被视为流式文件，系统不对文件进行格式处理。,6.2.2 顺序文件 1逻辑记录的排序 文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的顺序进行排列。一般地，可归纳为以下两种情况： 第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录， 依此类推。,第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。 对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必须从头开始，逐个记录地查找，直至找到指定的记录，或查完所有的记录为止。而对顺序结构文件，则可利用某种有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法来提高检索效率。,2对顺序文件(Sequential File)的读/写操作 顺序文件中的记录可以是定长的，也可以是变长的。对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。在读一个文件时，可设置一个读指针Rptr，令它指向下一个记录的首地址，每当读完一个记录时，便执行 Rptr:=Rptr + L 操作，使之指向下一个记录的首地址，其中的L为记录长度。,类似地，在写一个文件时，也应设置一个写指针Wptr，使之指向要写的记录的首地址。同样，在每写完一个记录时，又须执行以下操作: Wptr:=Wptr + L 对于变长记录的顺序文件，在顺序读或写时的情况相似，但应分别为它们设置读或写指针，在每次读或写完一个记录后，须将读或写指针加上Li。Li是刚读或刚写完的记录的长度。图6-3所示为定长和变长记录文件。,图6-3 定长和变长记录文件,3顺序文件的优缺点 顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录时。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。,在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。例如，有一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5103个记录；如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。,顺序文件的另一个缺点是，如果想增加或删除一个记录都比较困难。为了解决这一问题， 可以为顺序文件配置一个运行记录文件(Log File)，或称为事务文件(Transaction File)，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如4小时，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。,6.2.3 索引文件 对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：,Ai = i L,然而，对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则,可见，对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。然而，对于变长记录就较难实现直接存取了，因为用直接存取方法来访问变长记录文件中的一个记录是十分低效的，其检索时间也很难令人接受。为了解决这一问题，可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于记录该记录的长度L及指向该记录的指针(指向该记录在逻辑地址空间的首址)。由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地实现直接存取。图6-4示出了索引文件(Index File)的组织形式。,图6-4 索引文件的组织,6.2.4 索引顺序文件 索引顺序文件(Index Sequential File)可能是最常见的一种逻辑文件形式。它有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。前已述及，它是顺序文件和索引文件相结合的产物。它将顺序文件中的所有记录分为若干个组(例如，50个记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。索引顺序文件如图6-5所示。,图6-5 索引顺序文件,6.2.5 直接文件和哈希文件 1直接文件 采用前述几种文件结构对记录进行存取时，都须利用给定的记录键值，先对线性表或链表进行检索，以找到指定记录的物理地址。然而对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直接文件的关键，在于用什么方法进行从记录值到物理地址的转换。,2哈希(Hash)文件 这是目前应用最为广泛的一种直接文件。它利用Hash函数(或称散列函数)，可将记录键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块，如图6-6所示。例如，若令K为记录键值，用A作为通过Hash函数H的转换所形成的该记录在目录表中对应表目的位置，则有关系A=H(K)。通常，把Hash函数作为标准函数存于系统中，供存取文件时调用。,图6-6 Hash文件的逻辑结构,6.3 外存分配方式,6.3.1 连续分配(连续文件、顺序文件) 1连续分配方式 连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。,在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图6-7 示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count文件的第一个盘块号是0，文件长度为2，因此是在盘块号为0和1的两盘块中存放文件1的数据。,图6-7 磁盘空间的连续分配,如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(repack routine)，由它将磁盘A上的大量文件拷贝到一张软盘B或几张软盘(C，D，)上，并释放原来的A盘，使之成为一个空闲盘。然后再将软盘B(C，D，)上的文件拷回A盘上。这种方法能将含有多个文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。,2连续分配的主要优缺点 连续分配的主要优点如下： (1) 顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的文件中的第i个盘块的内容，就可直接访问b+i号盘块。 (2) 顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。,连续分配的主要缺点如下： (1) 要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。,(2) 必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。在有些情况下，知道文件的大小是件非常容易的事，如可拷贝一个已存文件。但有时却很难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的拷贝，须再要求用户重新估算，然后再次执行。这样，显然既费时又麻烦。这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得多，显然，这会严重地浪费外存空间。,对于那些动态增长的文件，由于开始时文件很小，在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存储空间长期地空闲着。,6.3.2 链接分配(链接文件、串联文件) 1隐式链接 在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。图6-8 中示出了一个占用5个盘块的链接式文件。在相应的目录项中，指示了其第一个盘块号是9，最后一个盘块号是25。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块9中设置了第二个盘块的盘块号是16；在16号盘块中又设置了第三个盘块的盘块号1。如果指针占用4个字节，对于盘块大小为512字节的磁盘，则每个盘块中只有508个字节可供用户使用。,图6-8 磁盘空间的链接式分配,隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块，就这样顺序地查找直至第i块。当i=100时，须启动100次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。,2显式链接 这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，如图6-9所示。表的序号是物理盘块号，从0开始，直至N-1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT(File Allocation Table)。,图6-9 显式链接结构,6.3.3 FAT和NTFS技术 1FAT12 1) 以盘块为基本分配单位 早期MS-DOS操作系统所使用的是FAT12文件系统，在每个分区中都配有两张文件分配表FAT1和FAT2，在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。,图6-10示出了MS-DOS的文件物理结构，这里示出了两个文件，文件A占用三个盘块，其盘块号依次为4、6、11；文件B则依次占用9、10及5号三个盘块。每个文件的第一个盘块号放在自己的FCB中。整个系统有一张文件分配表FAT。在FAT的每个表项中存放下一个盘块号。对于1.2 MB的软盘，每个盘块的大小为512 B，在每个FAT中共含有2.4 K个表项，由于每个FAT表项占12位，故FAT表占用3.6 KB的存储空间。,图6-10 MS-DOS的文件物理结构,现在我们来计算以盘块为分配单位时，所允许的最大磁盘容量。由于每个FAT表项为12位，因此，在FAT表中最多允许有4096个表项，如果采用以盘块作为基本分配单位，每个盘块(也称扇区)的大小一般是512字节，那么，每个磁盘分区的容量为2 MB(4096512 B)。同时，一个物理磁盘支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8 MB。这对最早时期的硬盘还可应付，但很快磁盘的容量就超过了8 MB，FAT12是否还可继续用呢，回答虽是肯定的，但需要引入一个新的分配单位簇。,2) 簇的基本概念 为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n (n为整数)个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为8 MB；当一个簇包含两个扇区时，磁盘的最大容量可以达到16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到64 MB。,由上所述可以看出，以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位虽可减少FAT表中的项数(在相同的磁盘容量下，FAT表的项数是与簇的大小成反比的)。这一方面会使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。,3) FAT12存在的问题 尽管FAT12曾是一个不错的文件系统，但毕竟已老化，已不能满足操作系统发展的需要，其表现出来的主要问题是，对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只能支持8+3格式的文件名。,2FAT16 对FAT12所存在的问题进行简单的分析即可看出，其根本原因在于，FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。由此可以得出解决方法，那就是增加FAT表的表项数，亦即应增加FAT表的宽度，如果我们将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65 536(216)个簇。我们把具有16位表宽的FAT表称为FAT16。在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分区空间为216 64 512 = 2048 MB。,由上述分析不难看出，FAT16对FAT12的局限性有所改善，但改善很有限。当磁盘容量迅速增加时，如果再继续使用FAT16，由此所形成的簇内碎片所造成的浪费也越大。例如，当要求磁盘分区的大小为8 GB时，则每个簇的大小达到128 KB，这意味着内部零头最大可达到128 KB。一般而言，对于14 GB的硬盘来说，大约会浪费1020的空间。为了解决这一问题，微软推出了FAT32。,3FAT32 如同存储器管理中的分页管理，所选择的页面越大，可能造成的页内零头也会越大。为减少页内零头就应该选择适当大小的页面。在这里，为了减小磁盘的簇内零头，也就应当选择适当大小的簇。问题是FAT16表的长度只有65 535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加FAT表的长度。为此，需要再增加FAT表的宽度，这样也就由FAT16演变为FAT32。,FAT32是FAT系列文件系统的最后一个产品。每一簇在FAT表中的表项占据4字节(232)，FAT表可以表示4 294 967 296项，即FAT32允许管理比FAT16更多的簇。这样就允许在FAT32中采用较小的簇，FAT32的每个簇都固定为4 KB，即每簇用8个盘块代替FAT16的64个盘块，每个盘块仍为512字节，FAT32分区格式可以管理的单个最大磁盘空间大到4 KB232 = 2 TB。三种FAT类型的最大分区以及所对应的块的大小如图6-11所示。,图6-11 FAT中簇的大小与最大分区的对应关系,4NTFS 1) NTFS新特征 NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows 2000/XP/2003。NTFS具有许多新的特征：首先，它使用了64位磁盘地址，理论上可以支持2的64次方字节的磁盘分区；其次，在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32 767个字符；第三，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行，这一点我们将在6.6节中介绍；第四，提供了数据的一致性，这是一个非常有用的功能，我们将在本章的最后一节介绍；此外，NTFS还提供了文件加密、文件压缩等功能。,2) 磁盘组织 同FAT文件系统一样，NTFS也是以簇作为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个簇只属于一个文件。通过簇来间接管理磁盘，可以不需要知道盘块(扇区)的大小，使NTFS具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是512字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。,在NTFS文件系统中，把卷上簇的大小称为“卷因子”，卷因子是在磁盘格式化时确定的，其大小同FAT一样，也是物理磁盘扇区的整数倍，即一个簇包含2n(n为整数)个盘块，簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为512 B、1 KB、2 KB，最大可达64 KB。对于小磁盘(512 MB)，默认簇大小为512字节；对于1 GB磁盘，默认簇大小为1 KB；对于2 GB磁盘，则默认簇大小为4 KB。事实上，为了在传输效率和簇内碎片之间进行折中，NTFS在大多数情况下都是使用4 KB。,对于簇的定位，NTFS是采用逻辑簇号LCN(Logical Cluster Number)和虚拟簇号VCN(Virtual Cluster Number)进行的。LCN是以卷为单位，将整个卷中所有的簇按顺序进行简单的编号，NTFS在进行地址映射时，可以通过卷因子与LCN的乘积，便可算出卷上的物理字节偏移量，从而得到文件数据所在的物理磁盘地址。为了方便文件中数据的引用，NTFS还可以使用VCN，以文件为单位，将属于某个文件的簇按顺序进行编号。只要知道了文件开始的簇地址，便可将VCN映射到LCN。,3) 文件的组织 在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中。该表是NTFS 卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT 表中占有一行，其中还包括MFT 自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。,在MFT表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织在所对应文件的一组属性中。由于文件大小相差悬殊，其属性所需空间大小也相差很大，因此，在MFT表中，对于元数据的1 KB空间，可能记录不下文件的全部信息。所以当文件较小时，其属性值所占空间也较小，可以将文件的所有属性直接记录在元数据中。而当文件较大时，元数据仅记录该文件的一部分属性，其余属性，如文件的内容等，可以记录到卷中的其它可用簇中，并将这些簇按其所记录文件的属性进行分类，分别链接成多个队列，将指向这些队列的指针保存在元数据中。,6.3.4 索引分配(索引文件) 1单级索引分配 链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题： (1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。,(2) FAT需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。当磁盘容量较大时，FAT可能要占用数兆字节以上的内存空间，这是令人难以接受的。 事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图6-12 示出了磁盘空间的索引分配图。,图6-12 索引分配方式,索引表,2多级索引分配 当OS为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。,图6-13示出了两级索引分配方式下各索引块之间的链接情况。如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时， 最多可包含的存放文件的盘块的盘块号总数N = 256 256 = 64 K个盘块号。由此可得出结论: 采用两级索引时，所允许的文件最大长度为64 MB。倘若盘块的大小为4 KB，在采用单级索引时所允许的最大文件长度为4 MB；而在采用两级索引时所允许的最大文件长度可达4 GB。,图6-13 两级索引分配,3混合索引分配方式 所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIX System 的索引结点中，共设置了13个地址项，即iaddr(0)iaddr(12)，如图6-14所示。在BSD UNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。,图6-14 混合索引方式,1) 直接地址 为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据所在盘块的盘块号。假如每个盘块的大小为 4 KB，当文件不大于40 KB时，便可直接从索引结点中读出该文件的全部盘块号。,2) 一次间接地址 对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1 K个盘块号，因而允许文件长达4 MB。,3) 多次间接地址 当文件长度大于4 MB + 40 KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4 GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4 TB。,1.存取方式有以下两种： 顺序存取 随机(直接)存取,6.3.5 文件结构、文件存取方式与文件存储介质的关系,存储介质,物理结构,存取方式,磁带,连续结构,顺序存取,磁盘,连续,链接,索引,顺序,顺序,顺序,随机,随机,2.文件结构、文件存取方式与文件存储介质的关系,文件寻址与文件的物理结构和逻辑结构以及设备的物理特性密切相关。 文件信息是以块为单位存储、传输的。但存取文件时，对于记录式文件，是以逻辑记录为单位提出存取要求的，因此，存储介质上的物理块长度与逻辑记录的长度是否匹配直接影响到对文件的寻址。 （1）逻辑记录长度与物理块长相等 （2）逻辑记录长度为物理块长的整数因子 （3）逻辑记录长度不为物理块长的整数因子,3.文件寻址,记录的成组：把若干个逻辑记录合成一组存放一块的工作 进行成组操作时必须使用主存缓冲区，缓冲区的长度等于逻辑记录长度乘以成组的块因子 记录的成组：提高了存储空间的利用率；减少了启动外设的次数，提高系统的工作效率 记录的分解：从一组逻辑记录中把一个逻辑记录分离出来的操作,4.记录的成组与分解,a.根据记录号和记录长度，确定记录所在物理块的相对块号rb； b.由记录长确定记录所在的物理块块数n； c.计算记录在所占的首物理块内的位移量d1； d.计算记录所占的末物理块内的位移量d2，即记录在末块内占据的长度； e.根据物理块长bs及计算出来的d1和d2，判断记录是否跨块；若跨块则修改n值和d2值。 （允许跨块）,6.4 目 录 管 理,通常，在现代计算机系统中，都要存储大量的文件。为了能对这些文件实施有效的管理，必须对它们加以妥善组织，这主要是通过文件目录实现的。文件目录也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下： (1) 实现“按名存取”，即用户只须向系统提供所需访问文件的名字，便能快速准确地找到指定文件在外存上的存储位置。这是目录管理中最基本的功能，也是文件系统向用户提供的最基本的服务。,(2) 提高对目录的检索速度。通过合理地组织目录结构的方法，可加快对目录的检索速度，从而提高对文件的存取速度。这是在设计一个大、中型文件系统时所追求的主要目标。 (3) 文件共享。在多用户系统中，应允许多个用户共享一个文件。这样就须在外存中只保留一份该文件的副本，供不同用户使用，以节省大量的存储空间，并方便用户和提高文件利用率。 (4) 允许文件重名。系统应允许不同用户对不同文件采用相同的名字，以便于用户按照自己的习惯给文件命名和使用文件。,6.4.1 文件控制块和索引结点 1文件控制块 为了能对系统中的大量文件施以有效的管理，在文件控制块中，通常应含有三类信息，即基本信息、存取控制信息及使用信息。,1) 基本信息类 基本信息类包括: 文件名，指用于标识一个文件的符号名。在每个系统中，每一个文件都必须有惟一的名字，用户利用该名字进行存取。 文件物理位置，指文件在外存上的存储位置，它包括存放文件的设备名、文件在外存上的起始盘块号、指示文件所占用的盘块数或字节数的文件长度。 文件逻辑结构，指示文件是流式文件还是记录式文件、记录数；文件是定长记录还是变长记录等。 文件的物理结构，指示文件是顺序文件，还是链接式文件或索引文件。,2) 存取控制信息类 存取控制信息类包括：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。 3) 使用信息类 使用信息类包括: 文件的建立日期和时间、文件上一次修改的日期和时间及当前使用信息(这项信息包括当前已打开该文件的进程数、是否被其它进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上)。应该说明，对于不同OS的文件系统，由于功能不同，可能只含有上述信息中的某些部分。,图6-15 MS-DOS的文件控制块,图6-15示出了MS-DOS中的文件控制块，其中含有文件名、文件所在的第一个