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

计算机操作系统考研辅导讲义

（第4.5章）

四、文件管理

4.1考试大纲

（一）文件系统基础

1.文件概念

2.文件结构

顺序文件；索引文件；索引顺序文件

3.录结构

文件控制块和索引结点；单级目录结构和两级

录结构；树形目录结构。

4.文件共享

共享动机；共享方式；共享语义。

5.文件保护

访问类型；访问控制。

（二）文件系统实现

1.文件系统层次结构

2.录实现

3.文件实现

（三）磁盘组织与管理

1.磁盘的结构

2.磁盘调度算法

3.磁盘的管理

4.2知识点归纳

2

4.2.1文件系统基础

文件系统的管理功能是通过把它所管理的

程序和数据组织成一系列文件的方法来实现的。

而文件是指具有文件名的若干相关元素的集合。

元素通常是记录，而记录又是一组有意义的数据

项的集合。基于文件系统的概念，可以把数据组

成分为数据项.记录和文件三级。

一、文件概念

1.数据项

在文件系统中，黝居项是最低级的黝居组织形

式，可把它分成以下两种类型：

(1)基本数据项。用于描述一介对象的某种

属性的字符集，是组织中可以命名的最小逻辑数

据单位，即原子数据。

(2)组合数据项。它是由若干基本数据项组

成的。简称组项。

基本数据项除了数据名外，还应有数据类型。

2、记录

记录是一组相关数据项的集合，用于描述一个

对象在某方面的属性。一个记录应包含哪些数据

项，取决于需要描述对象的哪个方面。而在诸多

记录中，为了能唯一地标识一个记录，必须在一

3

个记录的各个黝居项中，确定出一个或几个数据

项，把它们的集合称为关键字。

3、文件

文件是由创建者所定义的、具有文件名的一组

相关元素的集合，可分为有结构文件和无结构文件

两种。在有结构的文件中，文件由若干个相关记录

组成；而幅构的文件则被看成是一个字符流。

文件在文件系统中是一个最大的数据单位。此外，

文件应具有自己的属性，属性可以包括：

文件类型、文件长度.文件的物理位置、文件的

建立时间等。

二、文件结构

文件是由一系列的记录组成的。文件系统设计的

关键要素，是将这些记录构成一个文件的方法，以

及将一个文件存储囹I夕第上的方法。因此，对于任

何文件都存在着以下两种形式的结构：

文件的逻辑结构。这是从用户的观点出发所观

察到的文件组织形式，是用户可以直接处理的数

据及其结构，它独立于文件的物理特性，又称为

文件组织。

文件“Hi结构。又称为文件的存储结构，是

指文件在夕第上的存储组织形式。这不仅与存储

4

介质的存储性能有关，而且与所采用的夕晤分配

方式有关。

无论是文件的逻辑结构，还是文件的物理结构，

都会影响对文件的检索速度。下面介绍一下文件的

逻辑结构。

对文件逻辑结构所提出的基本要求，首先是能

提高检索速度，其次是便于修改，第三是降低文

件的存储费用。

A、文件逻辑结构的类型

文件的逻辑结构可分为两大类，一类是有结构

文件，是指由一个以上的记录构成的文件，故又

把它称为记录式文件；其二是无结构文件，是由

字符流构成的文件，故又称为流式文件。

(1)有结构文件

在记录式文件中，每个记录都用于描述实体集

中的一个实体，各记录有着相同或不同数目的数

据项。记录的长度可分为定长和不定长两类。

定长记录是指文件中所有记录的长度都是相

同的，所有记录中的各数据项，都处在记录中相

同的位置，具有相同的顺序和长度；变长记录是

指文件中各记录的长度不相同。产生变长记录的

原因，可能是由于一个记录中所包含的黝居I谶

5

并不相同，也可能是数据项本身的长度不定,

但不论哪一种，在处理前，每个i己录的长度是可

知的。

根据用户和系统管理上的需要，可采用多种方

式来组织这些记录，形成下述的几种文件：

顺序文件。是由一系列记录按某种顺序排列所

形成的文件。其中的记录通常是定长记录，因而

能用较快的速度查找文件中的记录。

索引文件。当记录为可变长度时，通常为之建

立一张索引表，并为每个记录设置一个表项，以

加快对记录的检索速度。

索引顺序文件。是上述两种文件构成方式的结

合。它为文件建立一张索引表，为每一组记录中

的第一个记录设置一个表项。

(2)无结构文件

大量的源程序、可执行文件、库函数等，所采

用的就是无结构的文件形式，即流式文件。其长

度以字节为单位。对流式文件的访问，则是采用

读写指针来指出下一个要访问的字符。

2.顺序文件

(1)逻辑记录的排序

文件是记录的集合。文件中的记录可以是任意

6

顺序的，因此，它可以按照各种不同的顺序进行

排列。可归纳为两种情况：第一种是串结构，各

记录之间的顺序与关键字无关。通常的办法是由

时间来决定，即按存入时间的先后排列。第二种

情况是顺序结构，指文件中的所有记录按关键字

排列。可以按关键词的长短从小到大排序，也可

以从大到小排序，或按其英文字母顺序排序。对

顺序结构的文件可利用某种有效的查找算法，获

得更高的检索效率。

(2)顺序文件的优缺点

顺序文件的最佳应用场合是在对诸记录进行

睡时，即每次要画泻一斑匕iB藐此时，

对顺序文件的存取效率是所有逻辑文件中最高

的；此外，也只有顺序文件才能存储在磁带上，

并能有效地工作。

在交互应用的场合，如果用户(程序)要求查

找或修改单个记录，为此系统便要去逐个地查找

诸记录。这是，顺序文件所表现出来的性能就可

能很差，尤其是当文件较大时，情况更为严重。

顺序文件的另一个缺点是增加或删除记录比较

困难。

3.索引文件

7

对于定长记录的文件，如果要查找第i个记录,

可直接根据下式计算来获得第i个记录相对于第

一个记录首址的地址：A尸i*L。然而，对于可变

长度记录的文件，要查找其第i个记录时，需首

先计算出该记录的首地址。为此，需顺序地查找

每个记录，从中获得相应记录的长度Li,然后才

能按下式计算出第i个记录的首址。假定在每个

记录前用一个字节指明该记录的长度，则

人=巧,+,,可见，对于定长记录，除了可以方

i=0

便地实现瞋序存取外，还可较方便地实现直除

取。然而对于变长记录就较唯实现直接存取。为

了解决这一问题，可为变长记录文件建立一张索引

表，对主文件中的每个i己录，在索引表中设立一

相应的表项，用于记录该记录的长度L和指向该

记录的指■（指向该记录在逻辑地址空间中的首

址X由于索引表蔑记录键排序的，因此，索引

表本身是一个定长记录的顺序文件，从而可以方

便地实现直接存取。

如图4-1示出了索引文件的组织形式。

8

・・・.・・

索引表逻辑文件

图4-1索引文件的组织

在对索引文件进行检索时，首先是根据用户提

供的关键字，并利用折半查找法去检索索引表，

从中找到相应的表项；再利用该表项中给出的指

向记录的指针值，去访问所需的记录。而每当要

向索引文件中增加一个新记录时，便需对索引表

进行修改。由于索引文件可有较快的检索速度，

故它主要用于对信息处理的及时性要求较高的

场合。使用索引文件的主要问题是，它除了有主

文件外，还需配置一张索引表，而且每个记录都

要有一个索引项，因此提高了存储费用。

4.索引顺序文件

索引顺序文件可能是最常见的一种逻辑文件

形式。它有效地克服了变长记录文件不便于直接

存取的缺点，而且所付出的代价也不算太大。它

是顺序文件和索引文件想结合的产物。将顺序文

件中的所有记录分为若干个组（例如50个记录

为一组）；为顺序文件建立一张索引表，在索引

表中为每组中的第一个记录建立一个索引项，其

中含有该记录的键值和指向该记录的指针。如图

4-2所示：

9

在对索引文件进行检索时，首先也是利用用户

（程序）所提供的关键字以及某种查找算法，去

检索索引表，找到该记录所在记录组中第一个记

录的表项，从中得到该记录组第一个记录在主文

件中的位置；然后再利用顺序查找法去查找主文

件，从中找到所要求的记录。

键逻辑姓名其它

地址属性

AnAnQi

Qi

BaoAn

RongKang

Chen

Lin

Bao

Rong

10

逻辑文件

图4-2索引顺序文件

如果在一个顺序文件中所含有的记录数为N,

则为检索到具有指定关键字的记录，平均须查找

N/2个记录；但对于索引顺序文件，则为能检索

到具有!旨定关键字的记录，平均只要查找1个记

录数，因而检索效率比顺序文件约提高42倍。

B、文件物理结构（外存分配方式）

文件的物理结构（文件外存分配方式）主要考

虑怎样才能有效地利用外存空间和如何提高对

文件的访问速度。

1.连续分配一顺序式的文件结构

如同内存的动态分区分配，会产生外存碎片，

可利用紧凑方法，将碎片拼接成一大片。

优点：I顺序访问容易，连续分配支持直接存取

顺序访问速度快。

缺点：要求有连续的存储空间

必须事先知道文件的长度

2、链接分配：隐式链接和显式链接

优点：可离散分配，解决了碎片问题

缺点：只适合于顺序访问，对随机访问极其低

效，不支持直接访问，不可靠。

显式链接：文件分配表FAT

3.索引分配

单级索引.多级索引•混合索引方式

录结构

在现代计算机系统中，都要存储大量的文件。

为了能对这些文件实施有效的管理，必须对它们

加以妥善组织，这主要通过文件目录实现。文件

录也是一种数据结构，用于标识系统中的文件

及其物理地址，供检索时使用。对目录管理的要

求如下：

(1)或见“按名存取〃。即用户只需向例是

供所需访问文件的名字，便能快速准确地找到指

定文件在外存上存储位置。这是目录管理中最基

本的功能，也是文件系统向用户提供的最基本的

服务。

(2)提局对录的检索速度。通过合理地组

织录结构的方法，可加快对录的检索速度,

从而提高对文件的存取速度。

(3)文件共享。

12

在多用户系统中，应允许多个用户共享一个文

件。这样就须在外存中只保留T分该文件的副本，

供不同用户使用，以节省大量的存储空间，并方便

用户和提高文件的利用率。

(4)允许文件重名。系统应允许不同用户对

不同文件采用相同的名字，以便于用户按照自己

的习惯给文件命名和使用文件。

1、文件控制块和索引结点

为了能对一个文件进行正确的存取，必须为文

件设置用于描述和控制文件的数据结构，称之为

“文件控制块〃。文件管理程序可借助于文件控

制块中的信息，对文件施以各种操作。文件与文

件控制块一对应，而人们把文件控制块的有序

集合称为文件目录，即一个文件控制块就是一个

文件目录项。通常，一个文件目录也被看作是一

个文件，称为目录文件。

(1)文件控制块

为了能对系统中的大量文件施以有效地管理,

在文件控制块中，通常含有以下三类信息，即基

本信息.存取控制信息及使用信息。

基本信息类包括：文件名、文件的物理位置.

文件的逻辑结构、文件的物理结构。

13

存取控制信息类包括：文件主的存取权限、核

准用户的存取权限以及一般用户的存取权限。

使用信息类包括文件建立的日期和时间、文件

上一次修改的日期和时间及当前使用信息。

(2)索引结点

稍加分析发现，在检索目录文件的过程中，只

用到了文件名，仅当找到一个目录项(即其中的

文件名与指定要查找的文件名相匹配)时，才需

从该目录项中读出该文件的物理地址。而其它一

些对该文件进行描述的信息，在检索目录时一概

不用，显然，这些信息在检索目录时，不需调入

内存。为此，在有的系统中如UNIX系统，便采

用了把文件名和文件描述信息分开的办法，使文

件描述信息单独形成一个称为索引结点的数据

结构。在文件目录中的每个目录项，仅由文件名

和指向该文件所对应的索引结点指针所构成。

磁盘索引结点是存放在磁盘上的索引结点。每

个文件有唯一的一个磁盘索引结点，它主要包括

文件主标识符、文件类型.文件存取权限.文件

物理地址.文件长度、文件连接计数.文件存取

时间。

内存索引结点是存放在内存中的索引结点。当

14

文件被打开时，要将磁盘索引结点拷贝到内存的

索引结点中，便于以后使用。在内存索引结点中

又增加索引结点编号.状态、访问计数、文件所

属文件系统的逻辑设备号、链接指针等。

2.单级目录结构

这是最简单的目录结构。在整个文件系统中只

建立一张目录表，每个文件占一个目录项,录

项中含文件名、文件扩展名、文件长度、文件类

型、文件物理地址以及其它文件属性。此外，为

表明每个录项是否空闲，又设置了一个状态位。

每当要建立T新文件时，必须先检索所有的

录项，以保证新文件名在目录中是唯一的。然

后再从目录表中找出一个空白目录项，填入新文

件的文件名及其它说明信息，并置状态位为1,

删除文件时，先从目录中找到该文件的目录项，

回收该文件所占用的存储空间，然后在清除该

录项。

单级目录的优点是简单且能实现目录管理的

基本功能一按名存取，但却存在下述：

雌速度慢；不允许重名;不便于实现文件共享。

3、两级目录

为了克服单级目录所存在的缺点，可以为每一

15

个用户建立一个单独的用户文件目录UFDe这

些文件目录具有相似的结构，它由用户所有文件

的文件控制块组成。此外，在系统再建立一个主

文件目录MFD；在主文件目录中，每个用户

录文件都占有一个目录项，其目录项中包括用户

在两级目面构中，如果用户希望有自己的用

户文件目录，可以请求系统为自己建立一个用户

秦繁星融贺髓翩噩舒快D蝌解

可以根据自己的需要创建新文件。每当此时，OS

只需检查该用户的UFD，判断在该UFD中是否

16

已有同名的另一个文件。若有，用户必须为新文

件重新命名；若无，便在UFD中建立一个新目

录项，将新文件名及其有关属性填入目录项中,

并置其状态位为T'。当用户要删^个文件时，

OS也只需查找该用户的UFD,从中找出指定文

件的目录项，在回收该文件所占用的存储空间后,

将该目录项删除。如图4・3所示

两级目录结构基本上克服了单级目录的缺点,

并具有以下优点：提高了检索目录的速度；在不

同的用户目录中，可以使用相同的文件名；不同

用户还可使用不同的文件名来访问系统中同一

个共享文件。

4、树形目录结构

对于大型文件系统，通常采用三级或以上的

录结构，以提高对目录的检索速度和文件系统的

性能。多级目录结构又称为树型目录结构，主

录在这里被称为根目录，把数据文件称为树叶,

其它的目录均作为树的结点。图示出了树型目录

结构。图中用方框代表目录文件,因圈代表的居

文件。在该树型目舞构中，根目录中有三个用

户的总目录项A、B和Co在B项所指出的B用

户的总目录B中，又包括三个分目录F.E和

17

D,其中每个分目录中又包含多个文件。如B目

录中的F分目录中，包含J和N两个文件。为

了提高文件系统的灵活性，应允许在一个目录文

件中的目录项既是作为目录文件的FCB,又是

作为数据文件的FCB,这一信息可用目录项中

的一位来指示。例如，在图中，用户A的总目

录中，目录项A是目录文件的FCB,而目录项B

和D则是数据文件的FCBe如图4-4所示：

工图形目录结构

图形目录结构是在树形目录结构的基础上形

成的一种目录，树形目录结构要保证目录结构中

没有环，如果有环就会形成图状结构。在图状结

构目录中通过link文件实现文件共享；在It弹构

18

中，实现目录的遍历和文件的删除等操作时，可

能会存在问题，相对于数形目录，图形目录结构

需要一些额外的措施来解决上述问题，如采用

〃垃圾收集〃机制来解决文件的删除问题等。

四、文件共享

1.共享动机

在现代计算机系统中，必礴供文件共享手段,

即指系统应允许多个用户（进程）共享同一份文

件。这样，在系统中只需保留该共享文件的一份

副本。如果系统不能是供文件共享功能，就意味

着凡是需要该文件的用户，都需各自备有此文件

的副本，显然这会造成对存储空间的极大浪费。

随着计算机技术的发展，文件共享的范围也在不

断扩大，从单机系统中的共享，扩展为多机系统

的共享，进而又扩展为计算机网络范围的共享,

甚至实现全世界的文件共享。

2、共享方式

（1）基于索引结点的共享方式

在树型结构的目录中，当有两个（或多个）用

户要共享一个子目录或文件时，必须将共享文件

或子目录链接到两个（或多个）用户的目录中，

才能方便地找到该文件，如图所示。此时该文件

19

系统的目录结构已不再是树型结构，而是一个有

向非循环图。如图4-5所示:

图4-5包含有共享文件的文件系统

如何建立B目录与共享文件之间的链接呢？

如果在文件目录中包含了文件的物理地址，即文

件所在盘块的盘块号，则在链接时，必须将文件

的物理地址拷贝到B录中去。但如果以后B

或C还要继续向该文件中填加新内容，也必然

要相应地增加新的盘块，而这些新增加的盘块，

也只会出现在执行了操作的目录中。可见，这种

变化对其他用户而言，是不可见的，因而新增加

的这部分内容已不能被共享。

为了解决这个问题，可以引用索引结点，即诸

如文件的物理地址及其它的文件属性等信息，不

20

再是放在目录项中，而是放在索引结点中。在文

件目录中只设置文件名及指向相应索引结点的

指针，如图4-6所示。此时，由任何用户对文件

进行的追加或修改操作，所引起的相应结点内容

的改变（例如，增加了新的盘块和文件长度等）,

都是其他用户可见的，从而也就解是健合其他用

户来共享。

在索引结点中还应有一个链接计数count,用

于表示链接到本索引结点上的用户目录项的数

目。当count=3时，表示有三个用户目录项连接

到本文件中，或者说是有三个用户共享此文件。

当用户C创建一个新文件时，他便是该文件

的所有者，此时将count置1。当有用户B要共

享此文件时，在用户B的目录中增加一目录项,

并设置一指针指向该文件的索引结点，此时文件

主仍然是C,count=20如果用户C不再需要此

文件，也不能将此文件删除。因为若删除了该文

件，必然删除了该文件的索引结点，这样便会使

B的｝器堪空，而B可能正在此文件上执行写操

作，此时也因此半途而废。

21

Wang用户文件目录

但如果C不删除此文件而等待B继续使用，

这样，由于文件主是C,如果系统要记帐收费,

则C必须为B使用此共享文件而付帐，直至B

不在需要。如图4・7所示。

C的目录C的目录C的目录C的目录

图4-7进程BfiSS前后的情况

22

(2)利用符号链实现文件共享

为使能共享的一个文件夹，可由系统创建一个

类型的新文件，也取名为，并将写入的目录中，

以实现的目录与文件的链接。在新文件中只包含

被链接文件的路径名。这样的链接方法被称为符号

雌。新文件中的路径名，只被看作是符号链，当

要访问被链接的文件且正要读类新文件时，此要

求将被蹒，根据新文件中的路径名去读该文

件，于是就实现了用户对文件的共享。

在利用符号链方式实现文件共享时，只是文件

主才拥有指向其索引结点的指针；而共享该文件

的其它用户，则只有该文件的路径名，并不拥有

指向其索引结点的指针。这样，这样也就不会发

生在文件主删除一共享文件后留下一悬空指针

的情况。当文件的拥有者把一个共享文件删除后

其他用户试图通过符号链去访问一个已被删除

的共享文件时，会因系统找不到该文件而使访问

失败，于是再将符号链删除，此时不会产生任何

影响。

符号链的共享方式也存在自己的问题：当其它

用户去读共享文件时，系统是根据给定的文件路

径名，逐个分量地去查找目录，直到找到该文件

23

的索引结点。因此，在每次访问共享文件时，都

可能要多次读盘，这使得每次访问文件的开销很

大，且增加了启动磁盘的频率。此外，要为每个

共享用户建立一条符号链，由于该链实际上是一

个文件，尽管该文件非常简单，却要为它配置一

个索引结点，要耗费一定的磁盘空间。

符号链方式有一个很大的优点，是它能够用于

链接世界上任何地方机器中的文件。

五、文件保护

在现代计算机系统中，存放了愈来愈多的宝贵

信息供用户使用，给人们带来了极大的好处和方

便；但同时也潜在有不安全性。影响文件安全性的

主要因素有：人为因素、系统因素、自然因素。存

取控制机制是确保文件安全性的重要措施。

1、访问类型。

我们可利用一个矩阵来描述系统的存取控

制，并把该矩阵称为访问矩阵。访问矩阵的行代

表域，列代表对象，矩阵中的每一项是由一组访

问权组成。因为对象已由列显式地定义，故可以

只写出访问权而不必写出是对哪个对象的访问

权，每一项的访问权access(i,j)定义了在域D

中执行的进程能对对象Qj施加的操作集。

24

访问矩阵中的访问权，通常是由资源的拥有者

或者管理者所决定的。当用户创建一新文件时，

创建者便是拥有者，系统在访问矩阵中为新文件增

加一列，由用户决定在该列的某个项中应具有哪些

访问权，而在另一项中又应具有阴阚防问权。当用

户删除此文件时，也要相应地将该文件在访问矩阵

的列中取消。

访问矩阵如图5-8所示，它是由3个域和8个

海野整写要押僵手馨普螂那执官解噂

能读文件F3.F4.F5及写文件F4.F5和执行文

件F4,此外还可打印。只有当进程在域D3中运

行时，才可使用绘图机。

对象文件1文件2文件3文件4文件5文件6打印机1绘图仪2

气

RR,W

D2RR,W,ER.WW

D3R,W,EWW

1＜：读；\¥：马；至：执行

图4・8一个保护矩阵

上面的访问矩阵，在概念上是简单的，极易理

解。但在具体实现上，却有一定的困难。这是因

为，在稍具规模的系统中，域的数量和对象的数

量都可能很大。保存访问矩阵需要比较大的存储

空间，同时进行访问时也十分费时。

25

事实上，每个用户(进程)所需访问的对象，

通常都是非常有限的，因此访问矩阵是非常稀疏

的矩阵，目前实现的方法，是将访问矩阵按列划

分，或者按行划分，分别形成访问控制表或访问

权利表。

(1)访问控制表

指对访问矩阵按列的捌分，为每TU建立

一张访问控制表。在该表中，已把矩阵中属于该

列的所有空项删除，此时的访问控制表是由一有

酶T(域，权集)所组成。由于在大多数情况下，

空项远多于非空项，因而使用访问控制表可以显著

地减少所占用的存储空间，并箭是高查找速度。域

是一个抽象的概念，它能以各种方式实现：

每个用户可以是一个域，这是最常见的一种情况，

一个用户是一个域，而对象则是文件，此时，用

户能够访问的文件集和访问权限取决于用户的

身份；每个进程是一个域，此时，能够访问的对

象集中的各访问权，取决于进程身份。

(2)访问权限表

如栗巴访问矩阵按行进行划分，便可由每一行

构成一张访问权限表，换言之，是由一个域对每

一个对象可以执行的一组操作所构成的表。表中

26

的每一项即为该域对某一对象的访问权限，当域

为用户（进程），对象为文件时，访问权限表便

可用来描述一个用户（进程）对每一文件所能执

行的一组操作。

如图对应于图中域D2的访问权限表。在表中

共有三个字段，其中，类型字段用于说明对象的

类型；权利字段是指域D2对该对象所拥有的访

问权限；对象字段是一个指向相应对象的指针。

由该表可以看出，域D2可以访问的对象有4个，

即文件3、4、5和打印机，对文件3的访问权限

是只读，对文件4的访问权限是可读.可写或可

类型权利

0文件R—指向文件3的指针

1文件RWE指向文件4的指针

2文件RVV-指向文件5的指针

3打印机-W-指向打印机1的指针

图4-9访问权限表

访问权限表是安全的，那么由它所保护的对象

才可能是安全的。因此，访问权限表不允许被用

户（进程）直接访问。通常，可采用三种方式对

为每个对象建立f标识位，用于标明该对象是

否要访问权限表，该标识位不允许被用户程序访

27

问；可以将访问权限表放在用户空间，但须将表

中的每一个访问权限都译成密码。目前大多数系

统都同时采用访问控制表和访问权限表。

2、访问控制

在计算机应用范围迅速扩大的同时，如何保证

系统安全性的问题，变的更为重要了。在稍具规

模的系统中，都加强了对系统安全性的管理，不

少系统已经从多个级别上来保证系统的安全性。

下面介绍在四个级别上对文件进行安全性管理

的措施:

(1)系统级安全管理

系统级安全管理的主要任务，是不允许未经核

准的用户进入系统，从而也就防止了他人非法地

使用系统中的各类资源(包括文件1系统级的

安全管理有以下几种主要方法：

a.注册。注册的主要目的是使系统管理员能

够掌握要使用系统的诸用户的情况，并保证用户

名在系统中的唯一性。为此，在系统中保存了一

张用户表，每个注册用户在其中占有一个表项。

表项中包括用户名和指定的口令。

b,登录。用户注册后，若要使用本系统，还

需曲覆录。登录的主要目的，是通过核实该用

28

户的注册名及口令来检查该用户使用系统的合

法性。

C,若干措施。系统管理员可采取以下措施，

来进一步保证文件的系统级安全性：规定用户定

期地修改口令，以防口令被窃；限定用户在指定

的终端上机，不能任意更换终端；限定用户在规

定的时间上机，其它时间不得上机。

(2)用户级安全管理

是为了给用户分配〃文件访问权〃而设计的。

用户对文件访问权限的大小，是根据用户性质、

需求及文件属性而分配的。用户级安全包括两方

面的内容：

a.用户分类

不同系统对用户进行分类的方法各不相同，在

一些系统中把用户分为四类：超级用户。这是具

有最高文件访问权的用户，通常是系统管理员；

系统操作员。系统赋予其较高的文件访问权；用

户。在登录时，系统根据其需求，为他指定对一

系列文件的访问权。顾客。系统限定他只能访问

某些特定文件。

b.文件访问权

已经在系统中登录过的用户都具有指定的访

29

问权。访问权决定了用户对哪些文件能执行哪些

操作。当对某用户赋予其访问指定目录的权限时,

他便具有了对该目录下的所有子目录和文件的

访问权。某种访问权也可被赋予一个用户组，这时,

该组中的每个成员便都具有这种访问权。

可以定义八种访问权限：建立.删除、打开.

读.写.查询.修改、父权等。

(3)目录级安全管理

是为保护系统中的各种目录而设计的，它与用

户权限无关。为保证目录的安全，规定只有系统

核心才具有写目录的权利。

通常，系统是分别为用户和目录独立地指定权

限的。当用户试图访问一目录时，核心将通过对

用户访问权和目录中的访问权的比较后，用户才

能获得有效的访问权。即在用户和目录中都有的

访问权；或者说，有效访问权是上述两个权限的

交集。

(4)文件级安全管理

是通过系统管理员或文件主对文件属性的设

置，来控制用户对文件的访问。通常可设置以下

几种属性：只执行.隐含.索引■修改.只读、

读/写.共享、系统，用户对文件的访问，将由

30

用户访问权、目录访问权限及文件属性三者的权

限所确定。或者说，是有效权限和文件属性的交

集。

4.2.2文件系统实现

一.文件系统层次结构

如图示出了文件系统的模型。可将该模型分

为三个层次，其最低层是对象及其属性；中间层

是对对象进行操纵和理的软件集合；最高层是

文件系统提供给用户的接口。

用户（程序）

对酶操纵和管理

的软件的集合

血及其属性

图4-10文件系统模型

1、对象及其属性。

文件管理系统管理的对象有：（1）文件。

它作为文件管理的直檄嫁。（2）目录。为了方

'口;

高对文件存取速度的关键。（3）磁盘存储空间。

文件和目录必定占用存储空间，对这部分空间的

31

有效管理，不仅雌高夕帝的利用率，而且解是

高对文件的存取速度。

2、对对象操纵和管理的软件集合

这是文件管理系统的核心部分。文件系统的

功能大多是在这一层实现的，其中包括：对文件

存储空间的管理、对文件目录的管理、用于将文

件的逻辑地址转换为物理地址的机制.对文件读

和写的管理，以及对文件的共享和保护等功能。

3、文件系统的接口

为方便用户使用文件系统，文件系统通常向

用户提供两种类型的接口：

(1)命令接口。这是指作为用户与文件系

统交互的接口。用户可通过键盘终端键入命令，

取得文件系统的服务。

(2)程序接口。这是指作为用户程序与文

件系统的接口。用户程序可通过系统调用来取得

文件系统的服务。

二、文件的实现

在实现文件的存储时，最重要的问题是如何来

记录一个文件被存放在哪一些磁盘块中。由于磁

盘具有可直接访问的斗寺性，故当利用磁盘来存放

文件时，具有很±的灵活性。在为文件分配夕第

32

空间时所要考虑的主要问题是：怎样才能有效地

利用外存空间和如何提高对文件的访问速度。

前常用的夕府分配方法有：连续分配、链接分配

和索引分配三种。通常，在一个系统中，仅采用

其中的一种方法来为文件分配外存空间。

1.连续分配方式

连续分配要求为每一个文件分配一组相邻接

的盘块，在采用连续分配方式时，可把逻辑文件

中的记录顺序地存放到邻接的各物理盘块中，这

样形成的文件结构称为顺序文件结构，此时的物

理文件称为顺序文件。

这种分配方式保证了逻辑文件中的记录顺序

与存储器中文件占用盘块的顺序的一致性。为使

系统能找到文件存放的地址，应在目录项的〃文

件物理地址〃字段中，记录该文件第一个记录所

在的盘块号和文件长度。

连续分配的主要优点：顺序访问容易。访问一

个占有连续空间的文件，非常容易；顺序访问速

度快。因为由连续分配襁入的文件，所占用的

盘块可能是位于一条或几条相邻的磁道上，这时

磁头的移动距离最少，因此访问速度快。

连续分配的主要缺点：要有连续的存储空间;

33

必须事先知道文件的长度。

2、链接分配方式

如同内存管理一样，连续分配所存在的问题

就在于：必须为一个文件分配连续的磁盘空间。

如果将一个逻辑文件存储到外存上时，并不要求

为整个文件分配一块连续的空间，而是可以将文

件装到装到多个离散的盘块中，就可消除上述缺

点。在采用链接分配方式时，可通过在每个盘块

上的镯爵旨针，将同属于一个文件的多个离散的

盘块链接成一个链表，把这样形成的物理文件称

为链接文件。

由于链接分配是采取离散分配方式，消除了

外部碎片，故而显著地提高了外存空间的利用率；

又因为是根据文件的当前需要，为它分配必需的

盘块，当文件动态增长时，可动态地再为它分配盘

块，无须事先知道文件的大小。此外，对文件的

增.删.改也十分方便。

链接方式又可分为隐式链接和显式链接两

种形式。

(1)隐式链接

在采用隐式链接分配方式时，在文件目录的

每个目录项中，都须含有指向链接文件第一盘块

34

和最后一个盘块的指针。而在每个盘块中都含有

一个指向下一个盘块的指针。

隐式链接分配方式的主要问题在于：它只适

合顺序访问，对随机访问是极其低效的；只通过

链接指针来将一大批离散的盘块链接起来，任何

一个指针出问题，都会导致整个链的断开。

(2)显式链接

把用理接文件驰理块的指针，皿地存

放在内存的一张链接表中，该表在整个磁盘仅设

置一张，如图所示。表的序号是物理盘块号，

从0开始，直至N-l；N为盘块总数。在每个表

项中存放镯凿第十，即下f盘块号。在瞬中，

凡是属于某个文件的第一个盘块号，或者是每一

条链的链首指针所对应的盘块号，均作为文件地

址被填入相应文件的FCB的〃物理地址〃字段

中。由于查找记录的过程是在内存中进行的，因

而不仅显著地提高了检索速度，而且大大减少了

访问磁盘的次数。由于分配给文件的所有盘块号

都放在该表中，故把该表成为文件分配表。

MS-DOS.Windows及OS/2等操作系统都采用

了FAT。

物理块号FAT

0

35

10

24

3

45

51

图4-11显式链接结构

3、索引分配

(1)单级索引分配

链接分配方式虽然解决了连续分配方式所

存在的问题，但又出现了两个问题：其一不能支

持高效的直接存取，要对一个较大的文件直接存

取，须首先在FAT中顺序地查找许多盘块号；

FAT需占用较大的内存空间，由于一个文件所

占用的盘块号，是随机地分布在FAT中的，因

而只有将整个FAT调入内存，才能保证在FAT

中找到一个文件的盘块号，当磁盘容量较大时，

FAT可能要占用数MB以上的内存空间，这是

令人难以接受的。

事实上，金了开某个文件时，只需｝巴文件占

用的盘块的编号调入内存即可，完全没有必要将

整个FAT调入内存。为此，应将每个文件所对

应的盘块号集中地放在一起。索引分配方法就是

基于这种想法所形成的一种分配方法。它为每个

文件分配一个索引块(表)，在把分配给该文件

的所有盘块号，都记录在该索引块中，因而该索

36

引块就是一个含有许多盘块号的数组。在建立一

个文件时，便须在为之建立的目录项中，填上指

向该索引块的指针。

索引分配方式支持直接访问，当要读文件的

第i个盘块时，可以方便地直接从索引块中找到

第i个盘块的盘块号；另外索引分配方式也不会

产生外部碎片，当文件较大时，索引分配方式无

疑要优于链接分配方式。

索引分配方式的主要问题是：可能要花费较

多的夕帝空间。对于小文件采用索引分配方式时，

其索引块的利用率是极低的。

(2)多级索引分配

当操作系统为一个大文件分配磁盘空间时，

如果所分配出去的盘块的盘块号已经装满一个

索引块时，操作系统便为该文件分配另一个索引

块，用于将以后继续为之分配的盘块号记录于其

中。依次类推，再通过链指针将各索引块按序链

接起来。当文件太大时，索引块太多，这种方法

是低效的。此时，应为这些索引块再建立一级索

引，称为第一索引。即系统再分配一个索引块，

作为第一级索引的索引块，将第一块、第二块等

索引块的盘块号，填入到此索引表中，这样便形

37

成了两级索引分配方式。如果文件非常大时，还

可用三级、犯级索引分配方式。

（3）混合索引方式

录的实现

当用户要访问一个已存文件时，系统首先利

用用户提供的文件名对目录进行查询，找出该文

件的文件控制块或对应索引结点；然后根据FCB

或索引结点中所记录的文件物理地址（盘块号），

换算出文件在磁盘上的物理位置；最后，再通过

磁盘驱动程序，将所需文件读入内存。目前对

录进行查询最常用的方式是线性检索法。

线性检索法又称为顺序检索法。在单级目录

中，利用用户提供的文件名，用顺序查找法直接

从文件目录中找到指名文件的目录项。在树型

录中，用户提供的文件名是由多个文件分量名组

成的路径名，此时须对多级目录进行查找。假定

用户给定的文件路径名是/usr/ast/mbox,则查找

/usr/ast/mbox的文件的过程如图所示。其查找

过程说明如下：

首先，系统应先读入第一个文件分量名usr,

用它与根目录文件（或当前目录文件）中各目录

项中的文件名顺序地进行比较，从中找出匹配者,

38

并得到匹配项的索引结点号6,再从6号索引结

点中得知usr录文件放在132号盘块中，将该

盘块内容读入内存。

接着，系统再将路径名中的第二个分量名

ast读入，用它与放在132号盘块中的第二级

录文件中各目录项的文件名顺序进行比较，又找

到匹配项，从中得到ast的录文件放在26号

索引结点中，再从26号索引结点中得知/usr/ast

是存放在496号盘块中，再读入496号盘块。

然后，系统又将该文件的第三分量名mbox

读入，用它与第三级目录文件/usr/ast中各目录

项中的文件名的比较，最后得到/usr/ast/mbox的

索引结点号为60,即在60号索引结点中存放了

指定文件的物理地址。目录查询操作到此结束。

如果在II牖查找过程中，发现有一个文件分量名未

育俄到，则应停止查找，并返回“文件未找到〃的

信息。

根目录结点6是的132盘块是/usr结点26是496号盘块是

/usr目录的目录/usr/ast的目录/usr/ast的目录

1•626•

116•

4bin19dick64grants

_______________

7dev30erik49692books

14lib51jim60mbox

9etc二26ast一81minik

6usr45bal17src

8tmp

39

图4-12查找/usr/ast/mbox的步骤

4.2.3磁盘组织与管理

一、磁盘的结构

磁盘设备是一种相当复杂的机电设备，这里仅

对磁盘的某些性能，如数据的组织、磁盘的类型

和访问时间等方面做扼要介绍。

1、数据的组织与格式

磁盘设备可包括一或多个盘块，每片分两面，

每面可分够干条磁道，各磁道之间留有必要的间

隙。在每条蹴上可存储相同数目的二进制位。这

样，磁盘密度即每英寸中所存储的位数，显然内层

磁道的密度较外层磁道的密度高。每条磁道又分成

若干个扇区，具典型值为10〜100个扇区。每个扇

区的大“环目当于一个盘块，各扇区之间保留一定

的间隙。

为了在磁盘上存保据，必须先将磁盘格式化。

一种中一条磁道格式化后，每条磁道含有30

个固定大小的扇区，每个扇区为600个字节，其

中512字节存1辘据，其余的用于存雌制信息。

每个扇区包括两个字段：

(1)标识符字段。其中一个字节的SYNCH

具有特定的位图像，作为该字段的定界符。利用

40

磁道号、磁头号及扇区号三者来标识一个扇区；

CRC字段用于段校验。

(2)数据字段。存放512字节的数据。

2、磁盘的类型

对磁盘，可以从不同的角度进行分类。最常见

的有：软盘和硬盘.单片盘和多片盘、固定头磁

盘和移动头磁盘等。

(1)固定头磁盘

这种磁盘在每条磁道上都有读/写磁头，所有

的磁头都被装在一刚性磁臂中。通过这些磁头可

访问所有各磁道，并进行并行读写，有效地提高

了磁盘的I/O速度。这种结构主要用于大容量的

磁盘上。

(2)移动头磁盘

每一个盘面仅配有一个磁头，也被装入磁臂中。

为能访问该盘面上的所有磁道，该磁头必须能移动

以进行寻道，可见，移动磁头仅能以串行方式读/

写，致使其I/O速度较慢；但由于其结构简单，

故广泛应用于中小型磁盘设备中。

3、磁盘的访问时间

磁盘设备在工作时，以恒定速率旋卷为了读

或写，磁头必须能移动到所要求的磁道上，并等

41

待所要求的扇区的开始位置旋转到磁头下，然后

在开始读或写数据。故可把对磁盘的访问时间分

成以下三部分。

(1)寻道时间Ts

是指B磁臂(磁头)移动到指定磁道上所经历

的时间。该时间是启动磁臂的时间§与磁头移动n

条磁道所花费的时间之和，即Ts=mxn+so加

m是一常数，与磁盘驱动器的速度有关。

(2)旋转延迟时间TT

是指指定扇区移动到磁头下面所经历的时间。

对于硬盘，典型的旋转速度大多为5400r/min,

每转需时U.lms,平均旋转延迟时间为5.55mse

(3)传输时间Tt

是指把数据从磁盘读出或向磁盘写入数据所

经历的时旬。Tt的大小与每次所读写的字节数b

和旋转速度有关。Y其中，,为磁盘每秒钟的

转数，N为一条磁道上的字节数。

二、磁盘调度算法

磁盘是可供多个进程共享的设备，当有多个进程

都要求访问磁盘时，应采用一种最佳调度算法，以

使各进程对磁盘的平均访问时间最小。由于在

42

访问磁盘的时间中，主要是寻道时间，因此，磁

盘的调度目标，是使磁盘的平均寻道时间最少。

前常用的磁盘调度算法有如下几种：

1.先来先服务

是一种最简单的磁盘调度算法，它根触程请

求访问磁盘的先后次序进行调度，此算法的优点

是公平、简单，且每个进程的请求都能依次得到

处理，不会出现某一进程的请求长期得不到的情

况。但此算法由于未对寻道进行优化，致使平均

寻道时间可能较长。

2、最短寻道时间优先

该算法选择这样的进程，其要求访问的磁道，

与当前磁头所在的磁道距离最近，以使每次的寻

道时间最短，但这种算法不能保证平均寻道时间

3、扫描算法

(1)进程"饥饿〃现象

最短寻道时间优先算法虽然能获得较好的寻

道性能，但却可能导致某个进程发生〃饥饿〃现

象。因为只要不断有新进程的请求到达，且其所

要访问的磁道与磁头当前所在磁道的距离较近，

这种新进程的请求必然优先满足。会导致老进程

43

出现〃饥饿〃现象。

(2)SCAN算法

该算法不仅考虑到欲访问的磁道与当前磁道

间的距离，更优先考虑的是磁头当前的移动方向,

当磁头正在自里向外移动时，扫描算法所考虑的下

一个访问对象，应是其欲访问的磁道既在当前磁道

之外，又是距离最近的。这样自里向外地访问，直

至再无更外的磁道需要访问时，才将磁臂

换向自外向里移动。同理，要访问在这个方向距

离最近的，直至在无更里面的磁道要访问。从而

避免出现“饥饿〃现象。由于这种算法中磁头移

动的规律颇似电梯的运行，因而又常称之为电梯

调度算法。

4、循环扫描算法

扫描算法既能获做好的寻道性能，又能防止

〃饥饿〃现象，故被广泛用于大、中、小型机器

和网络中的磁盘调度，但也存在这样的问题：当

磁头刚从里向外移动而越过了某一磁道时，恰好

又有一进程请求访问此磁道，这时该进程必须等

待，待磁头继续从里向外，然后再从外向里扫描

完所有要访问的磁道后，才处理该进程的请求,

致使该进程的请求被大大地推迟。为了减少这种

44

延迟，循环扫描算法规定磁头单向移动，例如，

只是自里向外移动，当磁头移到最外的磁道并访

问后，磁头立即返回到最里的欲访问磁道，亦即

将最小磁道号紧接着最大磁道号构成循环，进行

循环扫描。采用循环扫描方式后，上述请求进程

的请求延迟将从原来的2T减为T+Smax,加T

为由里向外或由外向里单向扫描完要访问的磁

道所需的寻道时间，Smax是将磁头从最外面被访

间的磁道直接移到最里面欲访问的磁道的寻道

时间（或相反X

三、磁盘的管理

为了实现磁盘空间的管理，首先必须记住空闲

存储空间的情况。为此，首先，系统应为分配磁

盘空间而设置相应的数据结构；其次，系统应提

供对存储空间进行分配和回收的功能。

I空闲表法

城闲表法属于连续分配方式，它为每个文件分

配一个连续的存储空间。系统为外存上的所有空

闲区建立一张空闲表，每个空闲区对应于一个空

闲表项，空闲表中包括：序号、该空闲区的第一

个盘块号、该区的空闲盘块数等信息，应将所W

空闲区按起始盘块号递增的次序排列，形成空闲

45

盘块表。

空闲盘区的分配和内存的动态分配类似，同样

可采取首次适应算法、循环首次适应算法.最佳

适应算法等。在内存分配上，虽然很少采用连续

分配方式；然而在外存管理上，由于它具有较高

的分配速度，可减少访问磁盘的频率，故它在诸

多分配方式中仍占有一席之地。

2.空闲链表法

是将所有的空闲盘区拉成一条空闲链，根据构

成链的基本元素不同，可有两种链表形式：空闲

盘块链和空闲盘区链。

(1)空闲盘块链

是将磁盘上的所有空闲存储空间，以盘块为基

本元素拉成一条链。当用户因创建文件而请求分

配存储空间时，系统从链首开始，依次摘下适当

数目的空闲盘块分配给用户，当用户因删除文件

而释放存储空间时，系统将回收的盘块，依次链

入空闲盘块链的尾部。这种方法的优点是用于分

配和回收一个盘块的过程非常简单；缺点是空闲

盘块链可能很长。

(2)空闲盘区链

将磁盘上的所有空闲盘区拉成一条链(每个盘

46

区可包含若干个盘块I在每个盘区上除含有用

于指示下一个空闲盘区的指针外，还应标有指明

本盘区大小(盘块数)的信息。盘区的分配方法

与内存的动态分区分配类似。这种方法的优缺点

刚好和第一种方法的优缺点相反，即分配与回收

过程较复杂，但空闲盘区链较短。

3、位示图法

(1)位示图

是利用二进制的一位来表示磁盘中一个盘块

的使用情况。当其值为时，表示对应的盘

块空闲；为时表示已分配。磁盘上的所有

盘块都有一个二进制位与之对应，这样由所有盘

块所对应的位构成一个集合，称为位示图。通常

可用mxn个位数来构成位示图，并使mxn等

于磁盘的总块数。

(2)盘块的分配

根据位示图进行盘块分配时，可分三步进行：

12345678910111213141516

11001000111100011

20011001100000111

30100001111000011

4

16

图4-13位示图

47

(2)盘块的分配

根据位示图进行盘块分配时，可分三步进行：

a.顺序扫描位示图，从中找出一个或一组其

值均为“0〃的二进制位(”0〃表示空闲时X

b,将所找到的一个或一组二进制位，转换成

与之相应的盘块号。假定，找到的其值为“0〃

的二进制位，位于位示图的第i行，第j列，则

其相应的盘块号应按下式计算：b=n(i-1)+j式

中，n代表每行的位数。

c.修改位示图，令map[i,j]=l.

(3)盘块的回收

盘块的回收分两步：

a.将回收盘块的盘块号转换成位示图中的行

号和列号，转换公式为：

i=(b-1)DIVn+1

j=(b-1)MODn+1

b.修改位示图。令map[i,j]=0o

这种方法的主要优点，是从位示图中很容易

找到一个或一组相邻接的空闲盘块。此外由于位

示图很小，占用空间少，因而可将它保存在内存

中，在每次进行盘区分配时，无需首先出巴磁盘分

配表读入内存，从而省掉许多磁盘的启动操作。

48

4.3经典例题解析

1.试述文件管理系统设置打开文件、关闭文件

命令的原因。

分析：该题目深入地考察了文件系统的功能。

操作系统要处理大量用户文件，而访问一个文件要

查询目录，有时甚至要多次查询目录。由于文件目

录和文件一起存放在辅存上，当存取文件时，必须

先到辅存中读取文件目录信息，从中获得文件的

存放地址，然后再去存取文件。这样一来，

文件信息的存取将花费很多时间。如果将整个文

件目录放入主存，虽然可以提高存取速度，但这需

要占据大量的主存空间，显然这也是不可取的。

实际上，在一段时间内使用的文件数总是有

限的，因此只要将目录中当前使用的那些文件的

录表目复制到内存中就可以了。这样，既不占

用太多的主存空间，又可显著提高查询文件目录

的速度。为此，大多数操作系统中设置了两个文

件操作：打开文件和关闭文件。打开文件操作完

成的功能是将文件的有关目录信息复制到主存

活动文件表中，以建立用户和这个文件的联系,

并将该表目的编号（或称为索引）返回给用户，

以后，当用户要求对该文件操作时，系统便可直

49

接利用该索引号到活动文件表中去查找，避免了

对该文件的再次检索，提高检索速度。关闭文件

操作的功能是用户宣布这个文件当前不再使用，

系统将其在主存中的相应目录信息删去，因而也

就切断了用户与这个文件的联系。

2、有一磁盘组共有10