4.1、文件系统基础
1、文件的概念
文件是操作系统中一个重要的概念。在系统运行时，计算机以进程为基本单位进行资源的调度和分配；而在用户进行的输入、输出中，则以文件为基本单位。大多数应用程序的输入都是通过文件来实现的，其输出也都保存在文件中，以便信息的长期存储及将来的访问。当用户将文件用于应用程序的输入、输出时，还希望可以访问文件、修改文件和保存文件等，实现对文件的维护管理，这就需要系统提供一个文件管理系统，操作系统的问价那系统就是实现用户的这些管理要求。
从用户的角度看，文件系统时操作系统的重要部分之一。用户关心的是如何命名、分类和查找文件，如何保证文件数据的安全性以及对文件可以进行哪些操作等。而对其中的细节，如文件如何存储在辅存上、如何管理晚间辅存区域等关心甚少。
文件系统提供了与二级存储相关的资源的映像，让用户能在不了解文件的各种属性、、文件存储介质的特性以及文件在存储介质上的具体位置等情况下，方便快捷的使用文件。
用户通过文件系统建立文件，提供应用程序的输入输出，对资源进行管理。首先了解文件的结构，我们通过自底向上的方式来定义。
1）数据项。
数据项是文件系统中最低级的数据组织形式，可分为以下两种类型：
基本数据项：用于描述一个对象的某种属性的一个值，如姓名、日期或证件号码等，是数据中可命名的最小逻辑数据单位，即原子数据。
组合数据项：有多个基本数据项组成。
2）记录。
记录是一组相关的数据项集合，用于描述一个对象在某方面的属性，如一个考生报名记录包括考生姓名、出生日期、报考学校代号、身份证号等一系列域。
3）文件。
文件是指由穿件这所定义的一组相关信息的集合，可分为有结构文件和无结构文件两种。在有结构文件中，文件由一组相似记录组成，如报考某学校的所有考生的报考信息记录；而无结构文件则被看成是一个字符流，比如一个二进制文件或字符文件。
虽然上面给出了结构化的表述，但实际上关于文件并无严格定义。通常在操作系统中将程序和数据组成文件。文件可以是数字、字母或二进制代码，基本访问单元可以是字节、行货记录。文件可以长期存储于硬盘或其他二级存储器，运行可控制的进程间共享访问，能够被组织成复杂的结构。
文件有一定的属性，这根据系统的不同而有所不同，但是通常都包括如下属性：
名称：文件名唯一，以容易读取的形势保存。
标示符：表示文件系统内文件的唯一标签，通常为数字，它是对人不可读的一种内部名称。
类型：被支持不同类型的文件系统所使用。
位置：指向设备和设备上文件的指针。
大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值。
保护：对文件进行保护的访问控制信息。
时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护、安全和跟踪文件的使用。
所有文件的信息都保存在目录结构中，而目录结构也保存在外存上。文件信息当需要时再调入内存。通常，目录条目包括文件名称及其唯一标示符，而标示符定位其他属性的信息。
文件属于抽象数据类型。为了恰当的定义文件，就需要考虑有关文件的操作。操作系统提供系统调用，他对文件进行创建、写、读、定位和截断。
创建文件：创建文件有两个必要步骤。仪式在文件系统中为文件找到空间；而是在目录中为新文件创建条目。此目录条目记录文件名称、在文件系统中的位置以及其他可能的信息。
写文件：为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。对于给定文件名称，系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作，便更新写指针。
读文件：为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样，需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，所以当前操作位置可作为每个进程当前文件位置指针。由于读和写操作都是用同一指针，节省了空间也降低了系统复杂度。
文件重定位：（文件寻址）按某条件搜索目录，将当前文件位置设为给定值，并且不会读写文件。
删除文件：搜索到给定名称的文件并释放空间，找到相关目录并予以删除。
阶段文件：允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。
这六个基本操作可以组成执行其他文件操作。例如，一个文件的复制，可以创建新文件；从旧文件读出并写入到新文件。
因为许多文件操作都涉及为给定文件搜索相关目录条目，许多系统要求在首次使用文件时，有系统调用open。操作系统维护一个包含所有打开文件信息的表（打开文件表，open-file table）。当需要一个文件操作时，可通过该表的一个索引指定文件，就省略了搜索环节。当文件不再使用时，进程可以关闭它，操作系统从打开文件表中删除这一个条目。
大部分操作系统要求在文件使用之前就被显式的打开。操作open会根据文件名搜索目录，并将目录条目复制到打开文件表。如果调用open请求（创建、只读、读写、添加等）得到允许你，进程就可以打开文件，而open通常返回一个指向打开文件表中的一个条目的指针。通过使用该指针（而非文件名）进行所有IO操作，以简化步骤并节省资源。
整个系统表包含进程相关信息，如文件在磁盘的位置、访问日期和大小。一个进程打开一个文件，系统打开文件表就会为打开的文件增加一个条目，并指向整个系统表的相应条目。通常，系统打开文件表的每个文件时，还用一个文件打开计数器（open count），记录多少进程打开了该文件。每个关闭操作close则使count递减，当打开计数器为0时，便是该文件不再被使用。系统将收回分配给该文件的内存空间等资源，若文件被修改过，则将文件写会外存，并肩系统打开文件表中的相应条目删除，最后释放文件的文件控制块（file control block，FCB）。
每个打开文件都有如下关联信息：
l 文件指针：系统跟踪上次读写位置作为当前文件位置指针。，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
l 文件打开计数：文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间会不够用。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。该计数器跟踪打开或关闭的数量，当计数为0时，系统关闭文件，删除该条目。
l 文件磁盘位置：绝大多数文件操作都要求系统修改文件数据，该信息在内存中以免为每个操作都从磁盘中读取。
l 访问权限：每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等）。该信息保存在进程的打开文件表中一边操作系统能允许或拒绝之后的IO请求。
2、文件的逻辑结构
文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构是从省市县观点出发，又称为文件的存储结构，是指文件在外存上的存储组织形式。文件的逻辑结构与存储介质特征无关，但文件的物理结构与存储介质的特性有很大关系。
按逻辑结构，文件有无结构文件和有结构文件两种类型：
无机构稳健是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累保存，它是有序相关信息项的集合，以字节（byte）为单位。由于无结构文件没有机构，因为对记录的访问只能通过穷举搜索的方式，股这种文件形势对大多数应用不适用，但字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件比较适于采用字符流的无结构方式，如源程序文件、目标代码文件等。
有结构文件按记录的组织形式可以分为：
1）顺序文件。
记录是定长的且按关键字顺序排列。可以顺序存储或以链表形势存储，在访问时需要顺序搜索文件。顺序文件有以下两种结构：
第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录，以此类推。
第二种是顺序结构，指文件中所有记录按关键字顺序排列。
在对记录进行批量操作时，即每次要读或写一大批记录，对顺序文件的效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效的工作。但顺序文件对查找、修改、增加或删除单个记录的操作比较困难。
2）索引文件
对于可变长记录的文件只能顺序查找，系统开销较大，为此可以建立一张索引表以加快检索速度，索引表本身是顺序文件。在记录很多或是访问要求高的文件中，需要引入索引以提供有效的访问，实际中，通过索引可以成百上千倍的提高访问速度。
3）索引顺序表
索引顺序表是顺序和索引两种组织形势的结合。索引顺序文件将顺序文件中所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。
4）直接文件或散列文件（哈希文件，Hash File）
给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址。这种映射接哦股不同于顺序文件或索引文件，没有顺序的特性。散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。
3、目录结构
与文件管理系统和文件集合相关联的是文件目录，它包含有文件的信息，包括属性、位置和所有权等，这些信息都由操作系统进行管理。首先我们来看目录管理的基本要求 ：从用户的角度看，目录在用户所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”；目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度；在共享系统中，目录还需要提供用于控制访问文件的信息。此外，文件允许重名也是用户的合理和必然要求，目录管理通过树形结构来解决和实现。
同进程管理一样，为实现目录管理，操作系统中引入了文件控制块的数据结构。
1）文件控制块。
文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，称为目录项。
FCB主要包含以下信息：
l 基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
l 存取控制信息，如文件的存取权限等。
l 使用信息，如文件建立时间、修改时间等。
2）索引节点
在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中独处该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不许调入内存，因此，有的系统（如UNIX）采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引节点的数据结构，简称为i节点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i节点的指针构成。
一个FCB的大小时64B，盘块大小是1KB，则在每个盘块中可以存放16个FCB。而在UNIX系统中一个目录仅占16B，其中14B是文件名，2B是i节点指针。在1KB的盘块中可存放64个目录项。这样可是查找文件时平均启动磁盘次数减少到原来的1/4，大大节省了系统开销。
存放在磁盘上的索引节点成为磁盘索引节点，UNIX中每个文件都有一个唯一的磁盘索引节点，主要包括以下几个方面：
文件主标示符，拥有该文件的个人或小组的标示符。
文件类型，包括普通文件、目录文件或特别文件。
文件存取权限，各类用户对该文件的存取权限。
文件物理地址，每个索引节点中含有13个地址项，即iaddr（0）~iaddr（12），他们以直接或间接方式给出数据文件所在盘块的编号。
文件长度，以字节为单位。
文件链接计数，文本文件系统中所有指向该文件的文件名的指针计数。
文件存取时间，本文件最近被进程存取的时间、最近被修改的时间以索引节点最近被修改的时间。
文件被打开时，磁盘索引节点复制到内存的索引节点中，以便于使用。在内存索引节点中有增加了以下内容：
索引节点编号，用于标示内存索引节点。
状态，指示i节点是否上锁或被修改。
访问计数，每当有一进程要访问此i节点时，计数加1，访问结束减1.
逻辑设备号，文件所属文件系统的逻辑设备号。
连接指针，设置分别指向空闲链表和散列队列的指针。
在理解一个文件系统的需求前，我们首先来了考虑在目录这个层次上所需要执行的操作，这有助于后面文件系统的整体理解。
搜索：当用户使用一个文件时，需要搜索目录，已找到该文件的对应目录项。
创建文件：当创建一个新文件时，需要在目录中增加一个目录项。
删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
显示目录：用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。
修改目录：某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。
操作时，考虑一下集中目录结构：
1）单级目录结构。
整个文件系统只建立一张目录表，每个文件占一个目录项。
当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的现象，然后在该目录中增设一项，把FCB的全部信息保存在该项中。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。
单级目录结构实现了按名存取，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。
2）二级目录结构
单机目录很容易造成文件名称的混淆，可以考虑采用二级方案，将文件目录分成主文件目录MFD和用户文件目录UFD两级。
主文件目录项纪录用户名及相应用户文件所在的存储位置。用户文件目录项记录该用户文件的FCB信息。当某用户与对其文件进行访问时，只需要搜索该用户对应的UFD，这即解决了不同用户文件的重名问题，也在一定程度上保证了文件的安全。
两级目录结构可以解决多用户之间的文件重名问题，文件系统可以在目录上实现访问限制，但是两级结构对于用户结构内部结构没有任何帮助。用户如果需要在某个任务上进行合作和访问那其他文件时便会产生很多问题。
3）多级目录结构
也成为树形目录结构。将两级目录结构的层析加以推广，就形成了多级目录结构，及树形目录结构。
用户要访问某个文件时用文件的路径名标识文件，文件路径名是一个字符串，由从根目录出发到所找文件的通路商的所有目录名与数据文件名用分隔符/连接起来而成。从根目录出发的路径称为绝对路径。当层次较多时，每次从根目录查询浪费时间，于是加入了当前目录，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件，相对路径由从当前目录出发到所找文件通路商所有目录名与数据文件名用分隔符/链接而成。
通常，每个用户都有自己的当前目录，登陆后自动进入该用户的当前目录。操作系统提供一条专门的系统调用，供用户随时改变当前目录。
树形目录结构可以很方便的对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，在属性目录中查找一个文件，需要按路径名主机访问中间节点，这就增加了磁盘访问次数，无疑将影响查询速度。
4）五环图目录结构
树形目录结构可便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图。
引入五环图目录结构是为了实现文件共享。
当某用户要求删除一个共享节点时，若系统只是简单地将它删除，当另一共享用户需要访问时，却无法找到这个文件而发生错误。。为此可以为每个共享节点设置一个共享计数器，每当途中增加对该节点的共享链时，计数器加1；每当某用户提出删除该节点时，计数器减1。仅当共享计数器为0时，才真正删除该节点，否则仅删除请求用户的共享链。
共享文件或目录不同于文件复制。如果有两个复制文件，每个程序员看到的是复制文件而不是原件；但如果一个文件被修改，那么另一个程序员的复制不会有改变。对于共享文件，只存在一个真正文件，任何改变都会为其他用户所见。
无环图目录结构方便实现了文件的共享，但是的系统的管理变得更加复杂。
4、文件共享
文件共享十多个用户进程共享同一份文件，系统中只需保留该文件的一份副本。如果系统不能提供共享功能，那么每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。
随着计算机技术的发展，文件共享的范围已由单机系统发展到多机系统，进而通过网络扩展到全球。这些文件的分享是通过分布式文件系统、远程文件系统、分布式信息系统实现的。这些系统允许多个客户通过c/s模型共享网络中的服务器文件。
现代常用的两种文件共享方法有：
在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录连接到两个或多个用户的目录中，才能方便的找到该文件。
在这种哦你共享方式中引用索引节点，即诸如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而是放在索引节点中。在文件目录中只设置文件名及指向相应索引节点的指针。在索引节点中还应有一个连接技术count，用于表示连接到本索引节点上的用户目录项的数目。当count=2时，表示有两个用户目录项连接到本文件上，或者说是有两个用户共享此文件。
当用户A创建一个新文件时，他便是该文件的所有者，此时将count置1.当有用户B要共享此文件时，在用户B的目录中增加一个目录项，并设置一个指针指向该文件的索引节点，此时文件主仍然是用户A，count=2.如果用户A不再需要此文件，不能讲问价那直接删除。因为，若删除了该文件，也必然删除了该文件的索引节点，这样便会使用户B的指针悬空，而用户B则可能正在此文件上执行写操作，此时将因此半途而废。因而用户A不能拿删除此文件，只是将该文件count减1，然后删除自己目录中的相应目录项。用户B仍可以使用该文件。当count=0时，表示没有用户使用该文件，系统将负责删除该文件。
为使用户B能共享用户A的一个文件F，可以有系统创建一个link类型的新文件，也取名为F，并将文件F写入B的目录中，以实现用户B的目录与文件F的连接。在新文件中只包含被连接文件F的路径名。这样的连接方法被称为符号链接。
新文件中的路径名则被看作是符号链。当用户B要访问被链接的文件F且正要读LINK类新文件时，操作系统根据新文件中的路径名去读该文件，从而实现了用户B对文件F的共享。
在利用符号链方式实现文件共享时，只有文件的拥有者才拥有指向其索引节点的指针。而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引节点的指针。这样，也就不会发生在文件主删除一个共享文件后留下一个悬空指针的情况。当文件的拥有者把一个共享文件删除后，其他用户通过符号链去访问它时，会出现访问失败，于是再将符号链删除，此时不会产生任何影响。此处我们要注意一个问题：当一个文件删除，而在使用其符号链接之前，另一个具有同样名称的文件被创建了。
在符号链的共享方式中，当其他用户读共享文件时，需要根据文件路径名逐个得查找目录，直至找到该文件的索引节点。因此，每次访问时，都可能要多次的读盘，使得访问文件的开销变大并增加了启动磁盘的频率。此外，符号链的索引结点也要耗费一定的磁盘空间。符号链方式有一个很大的优点，即网络共享只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。
上述两种连接方式都存在一个共同的问题，即每个共享文件都有几个文件名。换言之，每增加一条链接，就增加一个文件名。这实质上就是每个用户都是用自己的路径名去访问共享文件。当我们试图去遍历整个文件系统时，将会多次遍历到该共享文件。
硬链接和软链接都是文件系统中的静态共享方法，在文件系统中还存在着另外的共享需求，及两个进程同时对同一个文件进行操作。这样的共享可以称为动态共享。
5、文件保护
为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。
文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了方式用户文件被他人存取或盗取，而访问控制则用于控制用户对文件的访问方式。
对文件的保护可以从限制对文件的访问类型中出发。可加以控制的访问类型主要有以下几种：
读：从文件中读。
写：向文件中写。
执行：将文件装入内存并执行。
添加：将信息添加到文件结尾部分。
删除：删除文件，释放空间。
列表清单：列出文件名和文件属性。
西外还可以对文件的重命名、复制、编辑等加以控制。这些该层的功能可以通过系统程序调用低层系统调用来实现。保护壳一直在底层提供。例如，复制文件可利用一系列的请求来完成。这样，具有读访问用户同时也具有复制和打印的权限了。
解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是为每个文件和目录增加一个访问控制列表（Access-Control List，ACL），以规定每个用户名及其所允许访问的类型。
这种方法的优点是可以使用复杂的访问方法。其缺点是长度无法预期并且可能导致复杂的空间管理，使用精简的访问列表可以解决这个问题。
精简的访问列表采用拥有者、组合其他三种用户类型。
1）拥有者：创建文件的用户。
2）组：一组需要共享文件且具有类似访问的用户。
3）其他：系统内的所有其他用户。
这样只需用三个域列出访问表中这三类用户的访问权相即可。文件拥有者在创建文件时，说明创建者用户名及所在的组名，系统在创建文件时也将文件主的名字、所属组名列在该文件的FCB中。用户访问该文件时，按照拥有着所拥有的权限访问。UNIX操作系统即采用此种方法。
口令和密码是另外两种访问控制方法。
口令指用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应的口令，同时告诉允许共享该文件的其他用户。用户请求访问时必须提供相应的口令。这种方法时间和空间的开销不多，缺点是口令直接存在系统内部，不够安全。
密码纸用户对文件进行加密，文件被访问时需要使用密钥。这种方法保密性强，节省了存储空间，不过编码和译码要花费一定时间。
口令和密码都是仿制用户文件被他人存取或盗取，并没有控制用户对文件的访问类型。
注意两个问题：
1）现代操作系统常用的文件保护方法，是将访问控制列表与用户、组和其他成员访问控制方案一起组合使用。
2）对于多级目录结构而言，不仅需要保护单个文件，而且还需要保护子目录内的文件，即需要提供目录保护机制。目录操作与文件操作并不相同，因此需要不同的保护机制。