操作系统
Operating System
第6章 文件系统
本章主要内容：
§ 文件和文件系统
§ 文件的逻辑结构
§ 外存分配方式
§ 目录管理
§ 文件存储空间的管理
§ 文件共享与文件保护
§ 数据一致性控制
本章学习目标
文件、文件系统、文件目录、目录项、文件共享等基本概念及文件的分类
文件的两种逻辑结构及两种存取方法
文件的三种物理结构：连续结构、链接结构及索引结构
UNIX系统的文件索引结构
三种目录结构：单级、两级、多级目录结构
文件的共享及保护
外存空间的管理方法
本章重点：
文件的逻辑结构和物理结构
文件外存空间的管理
文件目录结构的管理
文件的保护与共享
本章难点：
目录的搜索
文件外存空间的管理
§ 文件和文件系统
主要内容：
§ 文件
§ 文件类型和文件系统
§ 文件操作
§ 文件
1.文件的定义
文件是具有标识符（文件名）的一组相关信息的集合。标识符是用来标识文件的。不同的系统对标识符的规定有所不同。文件的确切定义有两种说法：
（1）文件是具有标识符的相关字符流的集合。
（2）文件是具有标识符的相关记录的集合。
2.文件属性
文件应具有自己的属性，属性包括：
文件类型
文件长度
文件的物理位置
文件的建立时间
文件的逻辑结构
§ 文件类型和文件系统
1.文件的类型
按文件的用途可分为：
（1）用户文件：由用户建立，并由文件拥有者进行读/写和执行。这类文件只能由文件所有者或所有者授权用户使用。
（2）库文件：由系统为用户提供的实用程序、标准子程序、动态链接库等。
（3）系统文件：由系统建立的文件，如操作系统、编辑系统、编译系统等。这类文件只允许通过系统调用来执行，不允许读/写与修改。
按文件中的数据形式分为：
（1）源文件：由源代码和数据构成的文件。通常是由ASCII码或汉字所组成。
（2）目标文件：是指源程序经过编译程序编译后，但尚未链接成可执行文件的目标代码文件。属于二进制文件。
（3）可执行文件：是指目标代码经过链接程序链接后所形成的可以执行的文件。
按文件的访问控制属性分为：
（1）只读文件：允许所有者或授权用户对文件进行读，但不允许写。
（2）读写文件：允许所有者或授权用户对文件进行读写。
（3）执行文件：允许授权用户调用执行，但不允许对它进行读写。
（4）不保护文件：不加任何访问限制的文件。
按信息流向分类
（1）输入文件：如读卡机上的文件只能读入，所以它们是输入文件。
（2）输出文件：如打印机上的文件只能写出，所以它们是输出文件。
（3）输入/输出文件：如磁盘、磁带上的文件，既可读又可写，所以它们是输入/输出文件。
按文件的组织方式分类
（1）一般文件：也叫普通文件，它按一般的文件格式进行组织，如字符流文件。
（2）特殊文件：如目录文件（由目录信息构成的文件）。在某些操作系统中，把I/O设备也定义为特殊文件。
UNIX文件类型
（1）正规文件：是指系统所规定的普通格式的文件，包括系统文件、库文件以及各种用户文件等。
（2）目录文件：是由文件目录构成的一类文件。是用来维护文件系统结构和管理普通文件和目录的文件。
（3）符号链接：又称为软链接。它是一个短文件，其中包含了另一个文件的任意一个路径名。这个路径名可以指向位于任意一个文件系统的任意文件，甚至可以指向一个不存在的文件。硬链接是指目录表中的目录项所确定的文件名和索引节点之间的对应关系。硬链接的次数就是同一索引节点被目录项引用的次数。
（4）设备文件：包括块设备文件和字符设备文件。在UNIX系统中，所有的输入输出设备都被看成是文件，甚至在使用形式上也和普通文件相同。
（5）管道（pipe）文件：系统使用管道文件的目的是希望将一个进程的输出作为另一个进程的输入。管道文件使用一块专用的内存区域来保存中间信息。
（6）套接字（socket）：又称插口。通过在发送方和接收方分别创建一个称为套接字的通信端点可以获得TCP服务。每个套接字有一个套接字序号（地址），包含主机的IP地址和一个端口。每条连接由两端的套接字标识符来识别，即（socket1, socket2）。
2.文件系统
定义:
文件系统是操作系统中负责存取和管理文件信息的机构。它由管理文件所需的数据结构（如文件控制块，存储分配表等）和相应的管理软件以及访问文件的一组操作组成。
文件系统是指操作系统中用来管理文件以及对文件进行操作的机制及其实现。
文件系统由三个基本部分组成：存储数据的文件的集合，组织文件的目录结构，管理文件的软件机构。
§ 文件操作
文件系统向用户提供的对文件的操作可以分为两大类：一类是对文件自身的操作，例如，创建新文件、打开文件、删除文件、读写文件等；另一类是对记录的操作，例如，检索文件中的记录、插入记录、删除记录等。常用的文件操作如下：
1.创建文件
当用户需要把一批信息作为文件保存时，要通过系统调用命令向系统提出请求。系统首先要为新文件分配必要的外存空间，并且在文件系统的相应的目录中，为之建立一个目录项，其中记录了该文件的文件名及其在外存中的地址等文件属性信息。
2.打开文件
当用户要访问外存文件时，应先打开文件，在用户和文件之间建立起联系。将文件属性信息装入内存，在内存建立起相应的文件对象。一旦文件被打开就可以多次使用，直到文件被关闭为止。
3.读文件
读文件就是把文件中的数据从外存读入内存的用户区。在读文件的系统调用中要给出文件路径名和存放读出内容的内存地址。系统首先根据用户提供的文件路径名查找目录，找到指定文件的目录项，从中得到该文件在外存的地址。在目录项中，还有一个指针用于对文件的读写。通过读指针，将位于外存上的数据读入指定的内存区域。
4.写文件
当用户需要在文件中添加信息或修改文件时，可通过写文件系统调用向系统提出请求。
5.关闭文件
关闭文件是指撤销该文件在主存中的目录项（属性）信息，切断用户与该文件的联系；若在文件打开期间，该文件做过某些修改，则应将其写回辅存。 关闭文件不但为了释放内存空间，而且也因为许多系统常常限制可以同时打开的文件数。
6.删除文件
当用户提出删除文件的请求后，系统先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件占用的存储空间。
§ 文件的逻辑结构
§ 文件逻辑结构类型
文件的逻辑结构是指从用户的观点出发，用户所观察到的文件组织形式。
文件的逻辑结构可分为两种：一类是有结构文件或称记录式文件;一类是无结构文件或称流式文件。
文件的逻辑结构（常分为2种）
(1)有结构的文件
有结构的文件是指由若干个相关的记录构成的文件，又称记录式文件。用户存取文件是以记录为单位进行的。记录又分为定长的和变长的记录。
根据用户和系统管理的需要，可采用多种方式组织这些记录：
1、顺序文件
2、索引文件
3、索引顺序文件
１、 顺序文件
…
Ri
…
R3
R2
R1
R0
…
Ri
Li
…
R1
L1
R0
L0
L0
L1
L0+1
0
L0+L1+…Li-1+i
0
L
L
2L
i L
定长记录文件
变长记录文件
２、索引文件
…
…
Li
i
…
…
L1
１
L0
０
指针
长度
索引号
…
Ri
…
R1
R0
索引表
逻辑文件
３、索引顺序文件
它将顺序文件中的所有记录分成若干组，为顺序文件建立一张索引表，为每组中的第一个记录建立一个索引项。
Ch
Ba
Ａn
逻辑地址
键
…
Ba B
…
An c
An a
属性
姓名
4、哈希文件
把记录的键值通过哈希函数转换为相对地址，可提高查找速度。
键值
哈希函数f
得到记录的相对地址
(2)无结构文件
无结构文件又称流式文件，组成流式文件的基本信息单位是字节或字，其长度是文件中所含字节的数目，如大量的源程序，库函数等采用的就是流式结构。
记录式文件和流式文件的关系：
流式文件没有结构，但用户在使用流式文件时可以自己定义文件的结构。如可将３０个字节作为一个记录。
若每个记录只包含一个域，而且该域的类型为字符型时，记录式文件便退化为流式文件，因而可以说流式文件是记录式文件的特例。
§6.３ 文件的物理结构
为了有效地管理文件存储器，通常把文件存储空间划分成若干个大小相等的物理块，物理块是分配及传输信息的基本单位。块的大小通常是扇区的倍数，如512B、1KB、2KB或者4KB。
一个物理块中可以存放若干个逻辑记录，一个逻辑记录也可以存放在若干个物理块中。
为了有效地利用外存和便于系统管理，一般也把文件信息划分为与物理存储块大小相等的逻辑块。
常见的文件物理结构有三种：连续结构、链接结构和索引结构。
1.连续结构
图 文件的连续结构
连续结构，又称顺序结构，是一种最常用和最简单的物理文件结构，它把逻辑上连续的文件信息存储在物理位置连续的物理块中。
4
15
File C
5
8
File B
3
2
File A
长度
起始块号
文件名
14
29
0
磁盘空间
图 连续结构的文件组织
文件目录表
连续结构的主要优点是实现简单和存取速度快，只要记住文件的第一块号和块数就能确定该文件在外存上的位置。当文件是定长记录文件时，还可根据文件起始地址及记录长度进行随机访问。
缺点：不利于文件的动态增长，因为文件末尾处可能已经没有空闲块了，一旦增长，就需要进行大量的改动；反复增删文件以后，存储设备中便会产生类似于内存分配中出现的磁盘空间碎片。因此，连续结构只适用于长度固定的文件。
2.链接结构
图 文件的链接结构（隐式链接结构）
链接结构是指可以将文件存储在外部存储介质上的若干个不必连续的物理块中，其中的每个物理块都设有一个指针字段，指向下一个物理块的位置，从而使得存放同一个文件的物理块链接起来。以链接结构存放的文件称为链接文件。
22
15
File C
14
10
File B
7
2
File A
结束块号
起始块号
文件名
文件目录表
19
13
7
4
14
29
0
磁盘空间
图 链接结构的文件组织
4
7
13
14
-1
-1
12
-1
19
22
链接结构的优点是可以解决文件存储空间的碎片问题，提高了文件存储空间的利用率，同时允许文件动态增长。
缺点：但链接文件只能按照文件的链接指针顺序访问，为了访问文件的第i块，必须从第一块开始访问，然后一块接着一块，直到找到第i块。另一个缺点是必须为指针字段分配空间。
为了克服链接结构文件的缺点，可以把所有链接文件里的指针从物理块中取出，存放在一张链接表中，表的长度就是文件存储器能划分的物理块数，表的序号就是物理块号。
在每个表项中，存放链接指针，即下一个物理块号。该链接表存放在内存里。
由于分配给文件的所有物理块的块号都在该链接表中，故把该链接表称为文件分配表FAT（File Allocation Table），MS-DOS及OS/2等操作系统都采用FAT。
显式链接
图 显式链接结构
图 MS-DOS的文件物理结构
3.索引结构
图 文件的索引结构
索引结构就是把每个文件占用磁盘的物理块号集中存放在一张表中，即每一个文件都有一张索引表。每一个索引表项存放文件数据所占用的一个磁盘块的地址。以索引结构存放的文件称为索引文件。
10
File B
20
File A
索引块号
文件名
19
13
7
4
14
29
0
磁盘空间
图 索引结构的文件组织
4，6，9，11，14，16
文件目录表
图 文件的多重索引结构
模式
拥有者
时间戳
文件大小
块的数量
直
接
块
一级间接块
二级间接块
三级间接块
…
数据块
数据块
数据块
数据块
数据块
数据块
数据块
数据块
数据块
…
…
数据块
…
…
图 UNIX文件的索引结构(混合索引结构)
假如:每个盘块的大小为4k, 一个盘块号占4B,则直接地址项登记文件10个盘块,一级索引可登记1k的盘块,二级索引可登记1k*1k=1M 个盘块,三级索引可登记1G个盘块.
这样,当文件不大于40k时,可用直接地址,
当文件大于40k但不大于1k*4k+40k可用一级索引,当文件大于1k*4k+40k但不大于1M*4K+1K*4K+40K可用二级索引…….
§ 文件的存取方法
文件存取方法是指用户在使用文件时按怎样的次序存取文件。文件的存取方法是由文件的性质和用户使用文件的情况决定的。根据对文件信息的存取次序不同，把文件存取方法分为顺序存取、随机存取、索引存取等。
1.顺序存取
顺序存取是最简单的方法。它严格按照文件信息单位排列的顺序依次存取，后一次存取总是在前一次存取的基础上进行，所以不必给出具体的存取位置。在文件读写过程中总有两个位置指针指向其中要读写的字节位置或要读写的记录位置。
读写指针R
R+l
R+l
：
：
：
2.随机存取
随机存取又称直接存取，在存取时必须先确定进行存取时的起始位置（如记录号、字符序号等）。直接存取通常是对记录式文件而言的。
对于定长记录式文件来说，直接存取方便、高效。
对于变长记录文件，采用顺序存取方法会更高效。磁盘是支持随机存取的典型设备。
定长记录随机存取
变长记录随机存取
起始R
R+4*l
起始R
R+l0
l0
l1
l2
l3
l4
l5
R+l0+l1+l2+l3+l4
文件索引存取又称为按键存取，即对文件中的记录按某个数据项的值进行排序，从而可以根据键值来快速存取。
3.按键存取
l0
l1
l2
l3
l4
l5
按键值排列的
索引表
起始R
R+4*l
§ 文件存储空间的管理
文件存储空间主要是指磁盘空间。文件系统应为分配存储空间而设置相应的数据结构，还应提供对存储空间进行分配和回收的功能。下面介绍几种常用的空闲存储空间管理方法。
1.空白文件目录
系统将文件存储设备上的每个连续空闲区都看作一个空白文件，并为所有空白文件单独建立一个目录，每个空白文件在这个目录中占一个目录项，目录项的内容包括第一个空白块的地址（物理块号）和空白块的数目。
表6-1 空白文件目录
这是一种最简单的空闲区管理技术。适合于文件的静态分配（即连续结构的文件分配）。分配存储空间时，分割某个空白文件；系统回收该文件所占空间，要考虑相邻接空白文件合并问题。
显然，当文件存储空间中只有少量空白区时，这种方法才有较好的效果。如果存储空间中有大量小的空白区，那么空白文件目录会变得很大，因而效率大为降低。
序号 第一个空白块号 空白块的数目 物理磁盘块号
1 14 6 （14，15，16，17，18，19）
2 23 2 （23，24）
3 51 4 （51，52，53，54）
… … … …
2.位映像表
系统需要将位映像表中的二进制位所在位置与盘块号之间进行转换：
分配时，已知位坐标i、j，盘块号k=16*i+j；
回收时，已知K，则i=k/16，j=K%16。
一个1G的磁盘，每个盘块为1KB时，它要求一个1M位的映像表这个表占128个磁盘块(1M/8k)。位映像表需要调入内存。
1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0
……………………
15 14 …… 9 8 7 6 5 4 3 2 1 0
适合文件静态分配和动态分配的最简单管理方法是采用位映像表（或位示图）
0 1 2 3 ：：
3.空闲块链表
该方法的优点是实现简单，但工作效率低，因为每当在链上增加或移去空闲块时，都需要对空闲块链做较大的调整，因而会有较大的系统开销。
对空闲块链管理技术的改进方法是采用成组空闲块链表，即利用盘空闲块管理盘上的空闲块，每个磁盘块记录尽可能多的空闲块。
空闲块链表是通过链表来实现的。
∧
first
例如：
…
31
…
48
49
50
空闲块数20
…
149
150
空闲块数100
50
…
0
空闲块数100
专用块
0
1
19
150
4、成组块链
UNIX系统采用了这种成组空闲块链表管理方法。
显然这种管理方法既适合连续结构，也适合链接和索引结构。
图 成组空闲块链示意图
§ 文件的共享与保护
文件共享是指不同的用户可以通过共享使用同一文件。文件的共享可以节省大量的辅存空间和主存空间，减少输入/输出操作，为用户间的合作提供便利条件。文件的共享应该是有条件的，是要加以控制的。因此，文件的共享要解决两个问题，一个是如何实现文件共享，二是对各类需共享文件的用户进行存取控制。
实现文件共享有两种方法。一种方法是由系统实现对文件的共享，即当用户知道要共享文件的路径时，可以通过提供从根目录出发的路径名来共享访问这些文件。另一种方法是对需要共享的文件进行链接，即一个目录中的目录项直接指向另一个目录的目录项。
文件别名的实现
提供文件共享的方法有两种：各用户通过唯一的共享文件的路径名访问共享文件（该方法的访问速度慢，适用于不经常访问的文件共享），或利用多个目录中的不同文件名来描述同一共享文件（即文件别名，该方法的访问速度快，但会影响文件系统的树状结构，适用于经常访问的文件共享，同时存在一定的限制）。文件别名的实现方法有以下两种：
基于索引结点
基于符号链接
1. 基于索引结点(index node)的文件别名
也称为硬链接（hard link）；基于改进的多级目录结构，将目录内容分为两部分：文件名和索引结点。前者包括文件名和索引结点编号，后者包括文件的其他内容（包括属主和访问权限）。通过多个文件名链接(link)到同一个索引结点，可建立同一个文件的多个彼此平等的别名。别名的数目记录在索引结点的链接计数中，若其减至0，则文件被删除。
2. 基于符号链接(symbolic link, shortcut)的文件别名
它是一种特殊类型的文件，其内容是到另一个目录或文件路径的链接。建立符号链接文件，并不影响原文件，实际上它们各是一个文件。可以建立任意的别名关系，甚至原文件是在其他计算机上。
文件保护是指避免文件拥有者或其他用户因有意或无意的错误操作而使文件遭到破坏。。存取控制矩阵如下所示：
用户
文件
Joan
Alice
Tom
FILE1
RW
RWX
R
FILE2
R
X
R
FILE3
W
X
RW
文件的保护
用户
权限
文件主
RWE
A
R
B
WE
文件
权限
FILE1
RW
FILE2
R
FILE3
W
访问权限表
访问控制表
UNIX系统为每个文件的三类用户：拥有者、拥有者的小组成员及其它用户都规定了访问权限。
每类用户有一个由三个二进制位组成的存取控制表。这三位用来指示该类用户对文件是否有读、写、执行的存取权。若相应位被设置，则允许执行相应操作，否则拒绝执行。
例如，当一个文件的访问权限为111 101 001时，表示该文件允许文件主读、写、执行，小组成员读和执行，其它用户则只能执行。此外，允许文件主通过chmod命令修改文件的存取权限。
E
W
R
E
W
R
E
W
R
文件主
同组用户
其他用户
特权用户（系统操作员）
文件的保密
文件保密是指文件本身不得被未授权的用户访问。
1、口令
用户在创建文件时为其规定一个口令，文件系统将此口令记录在该文件的控制块FCB中。
2、加密
对文件的内容加密，加密的文件可能被其他用户窃取，但得到的是一组杂乱无章的数据。
文件的安全
文件安全性是指抵抗和预防各种物理性破坏及人为性破坏的能力。
1、海量转储
定期地将所有文件全部拷贝到后援存储器中。
2、增量转储
增量转储并不复制所有文件，而是仅复制两次转储期间被修改过的内容。
§ 文件的存储设备
1.文件存储设备
保存文件的设备主要有磁盘、磁带、光盘等等。通常，存储在不同设备上的文件，其存取方法也不同。这里以磁盘和磁带为例介绍一下文件存储设备。
磁带是一种典型的顺序存取设备。为了存取方便，磁带被划分成若干物理块，由于磁带机的启动和停止都要花费一定的时间，因此在磁带相邻物理块之间设计有一段间隙将它们隔开。
磁带的存取速度与其上的信息密度、磁带带速以及块间间隙有关。若磁带带速较高，信息密度较大并且所需的块间间隙较小，则磁带的存取速度就高。反之，磁带的存取速度就低。在读写磁带时，如果要访问的数据所在的物理块离磁头当前位置较近，则读写数据较快。反之，则较慢。
磁盘是一种典型的随机存取（直接存取）设备，即磁盘允许文件系统直接存取磁盘上的任意物理块。磁盘上的物理块可以用柱面号、磁道号和扇区号表示。
磁盘组结构：
访问磁盘时，首先需要寻道，将磁头从当前位置移动到指定磁道上，称之为寻道时间；接着将指定扇区移动到磁头下面叫旋转延迟时间；然后将扇区上的数据读出或向该扇区写入数据，称为传输时间。
读写臂
0号磁头
5号磁头
转速为r=7200/分，转一圈1/r
柱面号 扇区
因此访问磁盘的时间由寻道时间、旋转延迟时间和传输时间组成。即
访问磁盘的时间=寻道时间+旋转延迟时间+传输时间
各磁盘块的编号按柱面顺序,每个柱面按磁道顺序,每个磁道按扇区顺序进行排序.
0柱面0磁道0扇区为0块
0柱面0磁道1扇区为1块
………..
0柱面1磁道0扇区为7块
0柱面1磁道1扇区为8块
………..
1柱面0磁道0扇区….
0号块
1号块
2号块
假定每个柱面有t个磁道,每个盘面上有s个扇区,则:
第i柱面,j磁头,k扇区对应的块号b是:
b=i*t*s+j*s+k
同样,根据块号可确定该块在磁盘上的位置.
每个柱面上有s*t个磁盘块.第b块的位置是:
柱面号=b/(s*t)
磁头号=(b%(s*t))/s
扇区号=(b%(s*t))%s
2.磁盘调度算法
磁盘属于共享设备，可以被多个进程共享。当多个进程都提出访问磁盘的请求时，系统应采用相应的磁盘调度算法，在满足各个进程请求的同时，尽力缩短访问磁盘的时间。常用的磁盘调度算法有先来先服务（FCFS）、最短寻道时间优先（SSTF）、扫描（SCAN）算法、循环扫描（Circular SCAN）算法。
(1) 先来先服务FCFS (First-Come, First Served)
图 FCFS调度算法
磁道请求：
55，
58，
39，
18，
90，
160，
150，
38，
184
(2) 最短寻道时间优先SSTF (Shortest Seek Time First)
图 SSTF调度算法
磁道请求：
55，
58，
39，
18，
90，
160，
150，
38，
184
(3) 扫描(SCAN)算法（电梯调度算法）
1) 进程“饥饿”现象
SSTF算法虽然能获得较好的寻道性能， 但却可能导致某个进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达， 且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须优先满足。对SSTF算法略加修改后所形成的SCAN算法， 即可防止老进程出现“饥饿”现象。
2) SCAN算法
图 SCAN调度算法示例
磁道请求：
55，
58，
39，
18，
90，
160，
150，
38，
184
(4)循环扫描(CSCAN)算法
扫描算法具有较好的寻道功能，又避免了饥饿现象；但不利于远离磁头一端的访问请求。循环扫描算法是对扫描算法的改良，它规定磁头单向移动。
平均移动道数
50
10
24
166
20
1
16
3
32
150
160
184
18
38
39
55
58
90
移动的磁道数
被访问的下一个磁道号
从100号磁道开始，向磁道号增加的方向移动
磁道请求：
55，58，39，18，90，160，150，38，184
图 CSCAN算法示例
§6.４ 目录管理
§ 文件控制块和索引节点
§ 目录结构
通过文件目录来对外存上所存储的文件进行管理的，功能有：
(1)按名存取。这是文件系统向用户提供的最基本功能。
(2)提高检索速度。合理地组织目录结构，可以加快对目录的检索速度，从而提高对文件的存取速度。
(3)文件共享。允许多个用户共享同一文件，以节省存储空间，同时也方便用户。
(4)允许文件重名。以方便用户按照自己的习惯来命名和使用文件。
§ 文件控制块和索引节点
用于描述和控制文件的数据结构被称为文件控制块（FCB，File Control Block）。文件控制块的有序集合称为文件目录，即一个文件控制块占用一个文件目录项。通常，把文件目录也看作一个文件，称为目录文件。
1.文件控制块
在文件控制块中常用的属性如下：
(1)文件名。用户利用文件名来存取文件。
(2)文件的物理地址。包括：文件所在的设备名、盘块号、占用的盘块数。
(3)文件的逻辑结构。文件是流式文件还是记录式文件。
(4)文件的物理结构。指示文件是顺序结构，还是链接结构或索引结构。
(5)存取权限。文件主、核准用户、一般用户的存取权限。
(6)日期和时间。文件建立、修改的日期和时间。
(7)当前使用信息。当前已打开该文件的进程数，文件在内存中是否被修改过但尚未写回磁盘上。
第一个磁盘块号
修改时间
修改日期
文件长度
建立时间
建立日期
文件属性
扩展名
文件名
目录文件
2.索引节点
(1)索引节点的引入
文件目录存放在磁盘上，当文件很多时，文件目录要占用大量的磁盘块。
设盘块大小为1K，目录项占64字节，则一个盘块可存放1024/64=16，查找时只须比对文件名，因而读进来的目录项内容大部分没有用处。
假设目录文件所占用的盘块数为N，按此方法查找，则为了找到一个目录项，平均需要调入盘块数为 (N+1) /2个。可见查找效率很低。
(2)索引节点
通过分析可发现，在检索目录文件的过程中，只用到了文件名。属性信息在检索目录时无需调入内存。因此可把文件名和文件属性信息分开，即把文件属性信息用一个称为索引节点的数据结构来描述，而在文件目录的每个目录项中，仅存有文件名和该文件的索引节点编号。
文件名 索引节点号
0
1
2
…
目录文件
索引节点表
索引
节点号
0
1
2
…
磁盘块号
……
修改日期
文件长度
建立时间
建立日期
文件属性
§ 目录结构
目录的逻辑结构分为：单级目录结构、两级目录结构、树型目录结构。
1.单级目录结构
单级目录结构是指在整个文件系统中只建立一张目录表，其中每个目录项对应一个文件。
创建及删除文件涉及到目录项申请与回收。
单级目录结构的主要优点是实现简单。
其缺点：不允许文件重名；文件查找速度慢。
第一个磁盘块号
修改时间
修改日期
文件长度
建立时间
建立日期
文件属性
扩展名
文件名
2.两级目录结构
两级目录结构是指把系统中的目录分为一个主目录表和多个次目录表。在多用户系统中，可以为每个用户建立一个次目录表，而主目录表则存储着各个次目录表的信息。
两级目录结构的优点：提高了文件检索速度；在不同的用户目录中，可以使用相同的文件名。其缺点：不便于用户之间共享文件；同一用户内不允许文件重名。
3.树型目录结构
树型目录结构是两级目录结构的推广。为了克服两级目录结构不够灵活的缺点，方便文件查找，提高系统效率，在现代操作系统中采用了树型目录结构，如图4-6所示。
根目录
root
usr
home
bash
sbin
local
Zhang
Liu
Abc
squid
poly
httpd
图 树型目录结构
从树的根目录到任何数据文件，都只有一条唯一的路径，在该路径上从根目录开始，把全部目录文件名和数据文件名，依次用“/”连接起来，就构成了该数据文件的绝对路径名。如文件的路径名为“/home/Liu/”。
通常，一个进程在运行时所要访问的文件只局限于某个范围之内，因此可为每个进程设置一个“当前工作目录”。因此路径名又分为相对路径名和绝对路径名。
树型目录结构的优点：可以把不同类型和不同用途的文件分类，查找速度快；允许文件重名，不同的文件有不同的路径名；利用多级层次关系，能更方便地制定文件的存取权限，有利于保护文件；有利于文件共享。
图 多级目录结构
(1)在根目录下，查找B子目录文件；
(2)在B目录下，再查找B子目录文件；
目录查询技术
文件控制块检索
查找/B/B/AA/B的步骤
文件名 类型 其他属性
A D ……
B D ……
C D ……
…… … ………
…… … ………
根目录表
文件名 类型 其他属性
B D ……
E F ……
F D ……
…… … ………
…… … ………
B目录文件
B
B
目录查询技术
文件控制块检索
查找/B/B/AA/B的步骤
文件名 类型 其他属性
AA D ……
B F ……
C F ……
…… … ………
…… … ………
B目录文件
文件名 类型 其他属性
B F ……
C F ……
…… … ………
…… … ………
AA目录文件
(3)在B目录下，再查找AA子目录文件；
(4)在AA目录下，再查找B文件；
AA
B
目录查询技术
索引节点检索
图 查找/usr/ast/mbox的步骤
9
etc
6
usr
8
tmp
14
lib
7
dev
4
bin
1
..
1
.
索引
节点
文件
名
根目录表
(1) 在根目录表中查找usr目录
…
60
…
26
…
6
…
1
索引节点
…
…
…
…
…
…
属性
…
200
…
496
…
132
物理地址
…
f
…
d
…
d
…
d
文件
类型
索引节点表
(2) 读入6号索引节点到内存
目录查询技术
索引节点检索
图 查找/usr/ast/mbox的步骤
26
ast
45
lkm
51
hui
30
jkl
19
are
1
..
6
.
索引
节点
文件
名
usr目录文件
…
60
…
26
…
6
…
1
索引节点
…
…
…
…
…
…
…
属性
…
200
…
496
…
132
物理地址
…
f
…
d
…
d
…
d
文件
类型
索引节点表
(3)
从
132
号
盘块
读入
usr
目录
文件
，
查找
ast
(4)
读入
26
号
索引
节点
到
内存
目录查询技术
索引节点检索
图 查找/usr/ast/mbox的步骤
81
mini
17
scr
60
mbox
92
book
64
gran
6
..
26
.
索引
节点
文件
名
ast目录文件
…
60
…
26
…
6
…
1
索引节点
…
…
…
…
…
…
…
…
属性
…
200
…
496
…
132
…
…
物理地址
…
f
…
d
…
d
…
d
文件
类型
索引节点表
(5)
从
496
号
盘块
读入
ast
目录
文件
，
查找
mbox
(6)
读入
60
号
索引
节点
到
内存
(7)
从
200
号
盘块
读入
mbox
文件
，
查找
结束
§ 文件系统模型
1 、文件系统模型
该模型分为三个
层次：
对象及其属性
对对象操纵和管理的软件集合
文件系统接口
用户
文件，目录，磁盘存储空间
对文件存储空间的管理，对文件目录的管理，将文件的逻辑地址转换为物理地址的机制，对文件读写的管理，对文件的共享和保护功能
命令接口，程序接口
2.层次模型
传统的文件系统模型是层次模型。每一层都在下一层的基础上创建新的功能来为上一层服务，由下至上逐层扩展，从而形成一个层次清晰和功能完备的文件系统。
通常，文件系统的层次模型采用四层结构，如图4-7所示。其中包括逻辑文件系统层、文件组织模块层、基本文件系统层、I/O控制层。
应用程序
逻辑文件系统层
文件组织模块层
基本文件系统层
I/O控制层
物理磁盘
图 文件系统层次模型
1)I/O控制层由设备驱动程序和中断处理程序组成，在内存和磁盘之间传输信息。
2)基本文件系统层主要向相应的设备驱动程序发出读写磁盘物理块的命令。
3)文件组织模块层负责对具体文件的逻辑块和物理块进行操作。文件组织模块层能够把文件的逻辑块号对应到物理块号，供基本文件系统层使用。另外，文件组织模块层还负责磁盘空闲空间的管理。
4)逻辑文件系统层管理元数据信息。元数据包括除了文件内容之外的所有文件结构数据。根据给定的文件名，通过文件目录结构，能找到文件控制块（FCB）信息。逻辑文件系统层还负责文件的保护和安全。
3、文件系统的基本模型
文件系统的基本模型划分为6个软件级，使人们对文件系统的设计和构造更加容易理解。
用户接口
文件目录系统
存取控制模块
逻辑文件系统
物理文件系统
存储设备分配策略模块
设备管理模块
用户存取要求
回答
设备
用户接口级
1、对用户级发出的系统调用参数进行语法检查及合法性检验
2、把系统调用码及参数转换成内部调用格式
3、补充用户默认提供的参数，并完成相应的初始化
4、调用下一级程序，并负责与用户的文件数据转换
文件目录系统
1、管理活跃目录表
2、管理用户进程的打开文件表
3、管理与组织在存储设备上的文件目录结构，支持有关操作。
4、调用下一级软件。
存取控制模块
把用户的访问要求与文件控制块的访问权限进行比较
逻辑文件系统
根据文件的逻辑结构将用户欲访问的逻辑记录/字节转换为文件逻辑结构内的相应块号。若文件允许有不同的逻辑结构及不同的存取方法，则在该级分别设置若干个相应的程序模块。
物理文件系统
1、把逻辑记录所在的相对块号转换成实际的物理地址。
2、负责与下层次进行通信。若本次写操作，且尚未给写入的记录分配辅存空间，则调用辅存分配模块，然后再调用设备管理模块。若本次读操作，直接调设备管理模块。
分配模块：
管理辅存空间
设备管理模块：
分配设备、分配设备缓冲区、磁盘调度、启动设备、处理设备中断、释放设备等等。
图 文件系统层次模型
4.虚拟文件系统模型
有些操作系统，如Linux和UNIX系统，具有兼容其它操作系统的能力。人们能够透明地安装磁盘或分区，在这些磁盘或分区上可以驻留其它操作系统所用的文件系统。
要实现操作系统对其它各种不同文件系统的支持，就要将对各种不同文件系统的操作和管理纳入到一个统一的框架中。对用户程序隐去各种不同文件系统的实现细节，为用户程序提供一个统一的、抽象的、虚拟的文件系统界面，这就是所谓的虚拟文件系统（Virtual File System Switch，VFS）。例如，在Linux操作系统中，可以将DOS格式的磁盘或分区，即文件系统，“安装”到系统中，然后用户程序就可以按完全相同的方式访问这些文件，就好像它们也是Ext2格式的文件一样。
通常，虚拟文件系统分为三个层次，如图4-8所示。
第一层为文件系统接口层，如open、write、close等系统调用接口。
第二层为VFS (Virtual File System)接口层。该层有两个接口：一个是与用户的接口；一个是与特定文件系统的接口。VFS与用户的接口主要是V节点（Vnode，虚拟节点）。V节点是内核中的一个活动文件基类抽象。它定义了文件的访问接口，并且将所有对文件的操作定向到相应的特定文件系统函数上。VFS与特定文件系统的接口主要是通过vfs-operations来实现的。VFS通过网络文件系统协议处理远程文件访问。
第三层是具体文件系统层，提供具体文件系统的结构和实现，包括网络文件系统，如NFS (network file system)。
采用虚拟文件系统结构，用户不仅能够访问包含在本地磁盘上的多种文件系统中的文件，甚至能够通过网络访问远程文件系统中的文件。
网络
文件系统接口
VFS接口
图 虚拟文件系统模型
本地文件系统类型2
本地文件系统类型1
远程文件系统类型1
磁盘
磁盘
§ 文件系统的结构
通常，一套系统存储装置可以由若干个物理磁盘组成，而每个物理磁盘又可以进行分区。分区（逻辑盘）包括基本分区（primary partition）和扩展分区（extended partition）。扩展分区可以由逻辑分区（logical partition）组成。
分区是磁盘的基本组成部分，是一个能够被格式化和单独使用的逻辑单元。
分区的目的有三个：一是使磁盘初始化，以便可以格式化和存储数据；二是用来分割不同的操作系统；三是便于管理，可以有针对性地对数据进行分类存储，另外也可以更好地利用磁盘空间。分区格式化之后，操作系统就可把初始的文件系统数据结构存储于该分区，此时的分区又称为文件系统或文件卷。一个磁盘可以有多个文件卷，一个文件卷也可以由多个磁盘组成，如RAID磁盘阵列。
通常，磁盘分区由若干个物理磁盘块组成。当用户在使用Format命令或其他的格式化程序格式化磁盘分区时，物理磁盘块的大小就确定了。物理磁盘块的大小是物理扇区的整数倍，通常为2的整次幂。
文件系统的结构包括在磁盘上的结构和在内存中的结构。这些结构随操作系统和文件系统的不同而不同，但又有一些共同的规律。如，在磁盘上，文件系统有多少个磁盘块、空闲磁盘块数、目录结构、文件数据区等。
通常，逻辑盘的结构包括：
引导控制块：操作系统的初始引导块，用以读入并启动操作系统。一个文件系统，只有根文件系统才含有引导控制块。典型地，逻辑盘的第一块或作为引导控制块或空闲不用。在UFS中，被称为引导块；在NTFS中，被称为引导扇区。
盘控制块：包含整个逻辑盘的资源管理信息，如逻辑盘中的块数、块大小、空闲块数、空闲块地址、空闲FCB数以及FCB地址。在UFS中，被称为超级块；在NTFS中，它是主控文件表MFT。
目录结构：被用来组织文件的。
FCB：包含文件的属性信息，如文件访问权限、大小、存储地址。在UFS中，被称为i节点(inode)；在NTFS中，文件属性信息实际上被存储在MFT里。
目录块
数据块
数据块
目录块
数据块
数据块
…
…
2#
1#
0#
图 磁盘文件卷
引导块
超级块
磁盘inode区
磁盘信息区
…
inode
…
inode
inode 文件名
在内存中的数据结构包括：
已安装文件卷表：包含每一个被安装文件卷的信息。
内存目录结构：维持最近访问过的目录信息。已安装文件卷的目录包含一个指向该文件卷的指针。
系统打开文件表：包含每个已打开文件的FCB的副本，以及其他信息。
进程打开文件表：包含一个指向系统打开文件表相应项的指针，以及其他信息。
当创建一个新文件时，应用程序调用逻辑文件系统，由逻辑文件系统分配一个新的FCB（文件控制块）。同时把相应的目录读入内存，用新的文件名和FCB来更新该目录，接着把该目录写回磁盘。
逻辑文件系统能通过调用文件组织模块，实现目录I/O到磁盘块号的映射，该磁盘块号会被送到基本文件系统层和I/O控制层。文件组织模块层能为文件数据的存储分配磁盘块。文件被创建后，就可以读写文件了。
读写文件之前必须先打开文件。在文件被打开的过程中，要根据给定的文件路径名搜索目录结构。在内存，常常缓存部分目录结构以便加速目录操作。一旦文件被找到，文件的FCB被复制到内存里的系统打开文件表里。该表不仅存储FCB，还记录打开该文件的进程数。接着，在进程打开文件表里创建一个指针字段，指向系统打开文件表里相应的表项。
打开文件系统调用返回指向进程打开文件表相应项的指针，以后文件的操作都通过这个指针进行。在UNIX系统，打开文件系统调用返回的是文件描述符；在Windows 2000中，返回的是文件句柄。
fd
文件描述符
…
fp
…
…
f_inode
f_offset（0）
f_count（1）
f_flag（）
…
…
i_addr
i_nlink
i_mode
…
用户打开文件表
系统打开文件表
活动inode表
物理块
f_count反映不同进程通过同一个系统打开文件表项共享一个文件的情况(父子进程)；i_nlink(或i_count)反映不同进程通过不同系统打开文件表项共享一个文件的情况.
图 打开文件功能数据结构示意图
fd
用户打开文件表
fp
用户空间
f_inode
…
f_count
f_flag
…
…
i_addr
i_nlink
i_mode
…
系统打开文件表
一个打开文件
主存活动inode表
一个活动inode
内核空间
…
…
…
…
2#
1#
0#
磁盘
图 两个进程打开文件后的数据结构
打开操作实现过程
1、检索目录
在检索到指定文件之后，将其磁盘inode复制到活动inode表中。
2、把参数mode所给出的打开方式与活动inode中所记录的文件访问权限相比较，如果非法，则此次打开操作失败。
3、当“打开”合法时，为文件分配用户打开文件表项和系统打开文件表项，并为系统打开文件表项置初值，通过指针建立表项与活动inode 之间的联系，然后把文件描述符fd返回给调用者。
关闭操作的实现过程
1、根据fd找到用户打开文件表项，在找到系统打开文件表项；释放用户打开文件表项。
2、把对应的系统打开文件表项中的f_count减1，如果其值不为0，说明进程族中还有进程正在共享它，不用释放此表项直接返回；否则释放此表项，并找到与之连接的活动inode。
3、把活动inode中的i_count减1，若其值不为0，表明有其他进程正在使用此文件，直接返回；否则把活动inode的内容复制回相应磁盘inode中，释放此活动inode。
当进程关闭文件时，相应的进程打开文件表项被删除，相应的系统打开文件表项里的文件打开次数减一。当所有打开该文件的进程都关闭该文件时，已修改的文件信息被写回磁盘，相应的系统打开文件表项被删除。
实际上，open系统调用首先搜索系统打开文件表，看该文件是否已被其它进程打开了。如果已经打开了，在进程打开文件表里增加一个指针，指向该文件在系统打开文件表里所占用的表项即可。
在UFS中，系统打开文件表维持者i节点和其它文件信息，为网络连接和设备也维持着同样的信息。
§ 常用文件系统
S5FS：Unix系统V的文件系统
FAT（File Allocation Table）：FAT文件系统于1982年开始应用于MS-DOS中。经过不断改进，它已经发展成为包含FAT12，FAT16和FAT32的庞大家族。
NTFS（New Technology File System）：NTFS是微软为了配合Windows NT的推出而设计的文件系统，为系统提供了极大的安全性和可靠性。
Ext2：是Linux系统常用的文件系统，向后兼容性好。
Minix：最早的Unix文件系统之一，但缺少特色，能力也有限。
HPFS（High Performance File System）：用于OS/2操作系统的高性能文件系统。
NFS：网络文件系统，允许多台计算机之间共享文件系统。
