计算机操作系统考研辅导讲义(第4、5章)

1四、文件管理4.1考试大纲（一）文件系统基础1．文件概念2．文件结构顺序文件；索引文件；索引顺序文件3．目录结构文件控制块和索引结点；单级目录结构和两级目录结构；树形目录结构。4．文件共享共享动机；共享方式；共享语义。5．文件保护访问类型；访问控制。（二）文件系统实现1．文件系统层次结构2．目录实现3．文件实现（三）磁盘组织与管理1．磁盘的结构2．磁盘调度算法3．磁盘的管理4.2知识点归纳4.2.1文件系统基础文件系统的管理功能是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。而文件是指具有文件名的若干相关元素的集合。元素通常是记录，而记录又是一组有意义的数据项的集合。基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。一、文件概念1、数据项在文件系统中，数据项是最低级的数据组织形式，可把它分成以下两种类型：（1）基本数据项。用于描述一个对象的某种属性的字符集，是组织中可以命名的最小逻辑数据单位，即原子数据。（2）组合数据项。它是由若干基本数据项组成的。简称组项。基本数据项除了数据名外，还应有数据类型。2、记录记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而在诸多记录中，为了能唯一地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字。3、文件文件是由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构的文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位。此外，文件应具有自己的属性，属性可以包括：文件类型、文件长度、文件的物理位置、文件的建立时间等。二、文件结构文件是由一系列的记录组成的。文件系统设计的关键要素，是将这些记录构成一个文2件的方法，以及将一个文件存储到外存上的方法。因此，对于任何文件都存在着以下两种形式的结构：文件的逻辑结构。这是从用户的观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。文件的物理结构。又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。无论是文件的逻辑结构，还是文件的物理结构，都会影响对文件的检索速度。下面介绍一下文件的逻辑结构。对文件逻辑结构所提出的基本要求，首先是能提高检索速度，其次是便于修改，第三是降低文件的存储费用。A、文件逻辑结构的类型文件的逻辑结构可分为两大类，一类是有结构文件，是指由一个以上的记录构成的文件，故又把它称为记录式文件；其二是无结构文件，是由字符流构成的文件，故又称为流式文件。（1）有结构文件在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。定长记录是指文件中所有记录的长度都是相同的，所有记录中的各数据项，都处在记录中相同的位置，具有相同的顺序和长度；变长记录是指文件中各记录的长度不相同。产生变长记录的原因，可能是由于一个记录中所包含的数据项数目并不相同，也可能是数据项本身的长度不定，但不论哪一种，在处理前，每个记录的长度是可知的。根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件：顺序文件。是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录的检索速度。索引顺序文件。是上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。（2）无结构文件大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。2、顺序文件（1）逻辑记录的排序文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的顺序进行排列。可归纳为两种情况：第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列。第二种情况是顺序结构，指文件中的所有记录按关键字排列。可以按关键词的长短从小到大排序，也可以从大到小排序，或按其英文字母顺序排序。对顺序结构的文件可利用某种有效的查找算法，获得更高的检索效率。（2）顺序文件的优缺点顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。3在交互应用的场合，如果用户（程序）要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这是，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。顺序文件的另一个缺点是增加或删除记录比较困难。3、索引文件对于定长记录的文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i*L。然而，对于可变长度记录的文件，要查找其第i个记录时，需首先计算出该记录的首地址。为此，需顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则Ai=iLiii10，可见，对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。然而对于变长记录就较难实现直接存取。为了解决这一问题，可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设立一个相应的表项，用于记录该记录的长度L和指向该记录的指针（指向该记录在逻辑地址空间中的首址）。由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而可以方便地实现直接存取。如图4-1示出了索引文件的组织形式。索引号长度m指针ptrR00m0R11m1……Riimi……索引表逻辑文件图4-1索引文件的组织在对索引文件进行检索时，首先是根据用户提供的关键字，并利用折半查找法去检索索引表，从中找到相应的表项；再利用该表项中给出的指向记录的指针值，去访问所需的记录。而每当要向索引文件中增加一个新记录时，便需对索引表进行修改。由于索引文件可有较快的检索速度，故它主要用于对信息处理的及时性要求较高的场合。使用索引文件的主要问题是，它除了有主文件外，还需配置一张索引表，而且每个记录都要有一个索引项，因此提高了存储费用。4、索引顺序文件索引顺序文件可能是最常见的一种逻辑文件形式。它有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。它是顺序文件和索引文件想结合的产物。将顺序文件中的所有记录分为若干个组（例如50个记录为一组）；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。如图4-2所示：在对索引文件进行检索时，首先也是利用用户（程序）所提供的关键字以及某种查找算法，去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置；然后再利用顺序查找法去查找主文件，从中找到所要求的记录。4键逻辑地址姓名其它属性AnQiAnQiBaoRongAnKangChenLinBaoRong逻辑文件图4-2索引顺序文件如果在一个顺序文件中所含有的记录数为N，则为检索到具有指定关键字的记录，平均须查找2/N个记录；但对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只要查找N个记录数，因而检索效率比顺序文件约提高2/N倍。B、文件物理结构（外存分配方式）文件的物理结构（文件外存分配方式）主要考虑怎样才能有效地利用外存空间和如何提高对文件的访问速度。1、连续分配—顺序式的文件结构如同内存的动态分区分配，会产生外存碎片，可利用紧凑方法，将碎片拼接成一大片。优点：顺序访问容易，连续分配支持直接存取顺序访问速度快。缺点：要求有连续的存储空间必须事先知道文件的长度2、链接分配：隐式链接和显式链接优点：可离散分配，解决了碎片问题缺点：只适合于顺序访问，对随机访问极其低效，不支持直接访问，不可靠。显式链接：文件分配表FAT3、索引分配单级索引、多级索引、混合索引方式三、目录结构在现代计算机系统中，都要存储大量的文件。为了能对这些文件实施有效的管理，必须对它们加以妥善组织，这主要通过文件目录实现。文件目录也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下：（1）实现“按名存取”。即用户只需向系统提供所需访问文件的名字，便能快速准确地找到指定文件在外存上存储位置。这是目录管理中最基本的功能，也是文件系统向用户提供的最基本的服务。（2）提高对目录的检索速度。通过合理地组织目录结构的方法，可加快对目录的检索速度，从而提高对文件的存取速度。（3）文件共享。5在多用户系统中，应允许多个用户共享一个文件。这样就须在外存中只保留一份该文件的副本，供不同用户使用，以节省大量的存储空间，并方便用户和提高文件的利用率。（4）允许文件重名。系统应允许不同用户对不同文件采用相同的名字，以便于用户按照自己的习惯给文件命名和使用文件。1、文件控制块和索引结点为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块”。文件管理程序可借助于文件控制块中的信息，对文件施以各种操作。文件与文件控制块一一对应，而人们把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项。通常，一个文件目录也被看作是一个文件，称为目录文件。（1）文件控制块为了能对系统中的大量文件施以有效地管理，在文件控制块中，通常含有以下三类信息，即基本信息、存取控制信息及使用信息。基本信息类包括：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构。存取控制信息类包括：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。使用信息类包括文件建立的日期和时间、文件上一次修改的日期和时间及当前使用信息。（2）索引结点稍加分析发现，在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（即其中的文件名与指定要查找的文件名相匹配）时，才需从该目录项中读出该文件的物理地址。而其它一些对该文件进行描述的信息，在检索目录时一概不用，显然，这些信息在检索目录时，不需调入内存。为此，在有的系统中如UNIX系统，便采用了把文件名和文件描述信息分开的办法，使文件描述信息单独形成一个称为索引结点的数据结构。在文件目录中的每个目录项，仅由文件名和指向该文件所对应的索引结点指针所构成。磁盘索引结点是存放在磁盘上的索引结点。每个文件有唯一的一个磁盘索引结点，它主要包括文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件连接计数、文件存取时间。内存索引结点是存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，便于以后使用。在内存索引结点中又增加索引结点编号、状态、访问计数、文件所属文件系统的逻辑设备号、链接指针等。2、单级目录结构这是最简单的目录结构。在整个文件系统中只建立一张目录表，每个文件占一个目录项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件属性。此外，为表明每个目录项是否空闲，又设置了一个状态位。每当要建立一个新文件时，必须先检索所有的目录项，以保证新文件名在目录中是唯一的。然后再从目录表中找出一个空白目录项，填入新文件的文件名及其它说明信息，并置状态位为1，删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空间，然后在清除该目录项。单级目录的优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一些缺点：查找速度慢；不允许重名；不便于实现文件共享。3、两级目录为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目录UFD。这些文件目录具有相