操作系统学习笔记（五）文件管理系统基础
阅读的时候带着两个问题
- 什么是文件？什么是文件系统？
- 文件系统要完成哪些功能？
要注意区分文件的逻辑结构和物理结构，不要把二者混为一谈.
文件的概念
文件的定义
文件是操作系统中的一个重要概念，文件是以计算机硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档，图片，程序等。
在系统运行时，计算机以进程为基本单位进行资源的调度和分配；而在用户进行的输入，输出中，则以文件为基本单位
大多数应用程序的输入都是通过文件来实现的，其输出也都保存在文件中，以便信息的长期存储及将来的访问。当用户将文件用于应用程序的输入，输出时，还希望可以访问文件，修改文件和保存文件等，实现对文件的维护管理，这就需要系统提供一个文件管理系统，操作系统中的文件系统（File System），就是用于实现用户的这些管理要求的。
要清晰地理解文件概念，就要了解文件究竟由哪些东西组成：
- 首先，要有一块存储空间，更准确地说，是存储空间中的数据。
- 其次，由于操作系统要管理成千上万的数据，因此必定需要对这些数据进行划分，以便于分类和索引，所以文件必定包含分类和索引的信息。
- 最后，不同的用户拥有对数据的不同访问权限，因此文件中一定包含一些关于访问权限的信息。
用户通过文件系统建立文件，提供应用程序的输入，输出，对资源进行管理。首先了解文件的结构，我们通过自底向上的方式来定义：
- 数据项。数据项是文件系统中最低级的数据组织形式，可以分为两种类型：
- 基本数据项。用于描述一个对象的某种属性的一个值，如姓名，日期或证件号等，是数据中可命名的最小逻辑数据单位，即原子数据。
- 组合数据项。由多个基本数据项组成。
- 记录。记录是一组相关的数据项的集合，用于描述一个对象在某方面的属性，如一名考生的报名记录包括考生姓名，出生日期，报考学校代号，身份证号等一系列域。
- 文件。文件是指由创建者所定义的一组相关信息的集合，逻辑上可分为有结构文件和无结构文件两种
文件的属性
文件具有一定的属性，系统不同，属性也会有所不同，但通常都包括如下属性：
- 名称。文件名称唯一，以容易读取的形式保存。
- 标识符。标识文件系统内文件的唯一标签，通常为数字，对人不可读的一种内部名称。
- 类型。被支持不同类型的文件系统所使用。
- 位置。指设备和设备上文件的指针。
- 大小。文件当前的大小（用字节，字或块表示），也可包含文件允许的最大值。
- 保护。对文件进行保护的访问控制信息。
- 时间，日期和用户标识。文件创建，上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。
所有文件信息都保存在目录结构中，而目录结构保存在外存上。
文件信息在需求时才调入内存。通常，目录条目包括文件名称及其唯一的标识符，而标识符定位其他属性的信息。
文件的基本操作
文件属于抽象数据类型，为了恰当定义文件，需要考虑有关文件的操作。操作系统提供系统调用，它对文件进行创建，写，读，重定位，删除和截断等操作。
- 创建文件。创建文件有两个必要步骤：一是在文件系统中为文件找到空间，二是在目录中为新文件创建条目，该条目记录文件名称，在文件系统中的位置及其他可能的信息。
- 写文件。为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。对于给定的文件名称，系统搜索目录一查找文件位置。系统必须为该文件维护一个写位置的指针（是为每个对该文件进行写操作的进程都保存？），以便每当发生写操作时，更新写指针。
- 读文件。为了读文件，执行一个系统调用，指明文件名称和要读入的文件块的内存位置。同样需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，因此当前操作位置可作为每个进程当前文件位置的指针，也就是对于同一个进程而言，读写指针可以是同一个。
- 文件重定位（文件寻址）。按某条件搜索目录，将当前文件位置设定为给定值，并且不会读写文件。
- 删除文件。先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
- 截断文件。允许文件所有属性不变，并删除文件内容，即将其长度设为0.
这六个基本操作可以组合起来执行其他文件操作，例如，一个文件的复制，可以创建新文件，然后从旧文件读出并写入新文件。
这里可以结合下面的目录结构的所需要操作，整体上认识文件系统的操作
文件的打开与关闭
因为许多文件操作都涉及为给定文件搜索相关目录条目，因此许多系统要求在首次使用文件的时候，使用系统调用open将指明文件的属性（包括该文件在外存上的物理位置）从外存复制到内存的一个打开文件表的表目中，并将该表目的编号（也叫索引）返回给用户。
操作系统维护一个所有打开文件信息的表（打开文件表，open-file table）。
当用户需要操作一个文件时，可以直接从打开文件表中找到该索引，从而节省搜索环节。
大部分操作系统要求在文件使用之前就被显式打开
操作open会根据文件名搜索目录，并将目录条目复制到打开文件表。
若open请求被允许，则进程就可以打开文件，而open通常返回一个指向打开文件表的一个条目的指针。
通过使用该指针而非文件名进行I/O操作。
open指令通过文件名，查找目录，找到对应目录项后，返回索引给进程，并存储到打开文件表，open之后，操作系统不再使用文件名进行操作。
整个系统表包含进程相关信息，如文件在磁盘的位置，访问日期和大小。
一个文件第一次被某个进程打开，系统打开表就会增加一个条目，当另一个进程执行open时，是在其自己的进程打开表中增加一个条目，然后指向系统打开表的对应条目，同时系统打开表的相应条目中的计数器加一，用于表明有多少个进程打开了该文件。
每个关闭操作都会将计数器减一，当计数器为0时，表示该文件不再被使用，系统将回收分配给该文件的内存资源，若文件被修改过，还会将文件写回外存（这一步有点类似缺页置换时，如果修改位为1，需要将该页内容写回硬盘），并将系统打开表中的相应条目删除，最后释放文件控制块（File Control Block， FCB）
FCB，目录项，系统打开表项的异同？
每个打开文件都有如下关联信息：
- **文件指针。**系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，也就是说是进程级别的，因此必须与磁盘文件本身的属性分开存放。
- 文件打开计数。文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间会逐渐缩小。而又因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。通过计数器来实现，计数为0时，关闭文件，删除条目。这个是文件级别的。
- 文件磁盘位置。绝大多数文件操作都要求系统修改文件数据。该信息保存在内存中。
这东西应该在系统打开表中，但是又个问题，如果是连续存放的文件，在写入过程中，文件大小超了，会发生什么？
是重新申请磁盘空间，然后复制过去，修改位置？还是不允许写入超过文件大小的内容。
- 访问权限。每个进程都需要一个访问模式（创建/只读/读写/添加 等）。该信息是进程级别的，所以应该存储在进程打开表中。
文件的逻辑结构（文件的内部逻辑结构）
文件的逻辑结构，是从用户观点出发看到的文件的组织形式。
文件的物理结构，是从实现观点出发看到的文件存储在外存上的存储组织形式。
文件的逻辑结构与存储介质的性质无关，但是文件的物理结构与存储介质的特性又很大关系。
这一点就像是，数据结构中的链表，既可以是顺序存储，也可以是链式存储
Unable to paste block outside Docs
无结构文件
最简单的文件组织形式，将数据按顺序组织城际路并积累，它是有序相关信息项的集合，以字节为单位。因为没有结构，所有访问只能通过穷举搜索的形式，因此这种形式对大多数文件不适用，而对于那些基本信息单位操作不多的文件较为适合
有结构文件
按照记录的组织形式，可以分为：
顺序文件（按顺序组织）
文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储，在访问是需要顺序搜索文件。
顺序文件有以下两张结构：
- 第一种是串结构，记录之间的顺序与关键字顺序无关，通常方法是由时间决定，即按存入时间的先后进行排序。
- 第二种是顺序结构，指文件中所有的记录按关键字顺序排列。
对记录进行批量操作时，，即每次要读取一大批记录时，顺序文件的效率是所有逻辑文件中最高的；也只有顺序文件可以存储在磁带上。
顺序文件的优势在于批量操作，无论是采用顺序存储还是链式存储。单条记录的增删查改则比较困难，那是索引文件比较擅长的事情。
索引文件（按索引组织）
对于定长记录文件，要找到第i条记录，可以直接根据下面的公式计算得到第i条记录相对于第一条记录的地址：Ai = i * L;
定长记录文件，需要是顺序存储才可以这样计算，但是需要注意，顺序存储不代表是顺序文件，顺序文件的定义是按顺序组织记录，索引文件的定义是按索引组织，组织形式的不同才是二者的差别。
但是对于可变长记录文件来说，要找到第i条记录，必须顺序查找前i-1条数据，从而获得对应数据的长度L，然后不断相加得到第i条记录的首地址。
变长记录文件只能按顺序查找，系统开销较大，所以可以建立一张索引表加快检索速度，索引表本身是定长记录的顺序文件。
索引顺序文件（按顺序组织索引）
索引顺序文件是顺序和索引两种组织形式的结合。
索引顺序文件将文件中所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项，其中含有该记录的关键字和指向该记录的指针。
主文件中的记录分组排列，同一个组中的关键字可以无序，但是组与组之间的关键字必须有序。
直接文件或散列文件（没有任何顺序特性）
给定记录的键值或通过散列函数转换的键值直接决定记录的物理位置。这种映射结构不同于顺序文件或者索引文件，没有顺序的特性。
散列文件与数据结构中的散列表相同，也会产生哈希冲突，需要处理。
这里对这几种有结构文件进行一个汇总比较。
首先明白第一点，顺序存储还是链式存储，定长记录还是可变长记录，与它属于有结构文件中的哪一类没有什么关系。
顺序文件指的就是是文件中的记录是有顺序的。查找的时候是按顺序查找的。
索引文件指的是文件有个索引，这个索引可以是因为顺序存储而隐含的（类似数组索引），也可以是一个单独的索引表。查找的时候是按索引查找的。
索引顺序文件则是，索引是有顺序的。先按顺序找到索引，再用索引去找。
哈希文件则是通过散列函数直接计算记录的物理位置，没有什么顺序在里面。
目录结构（文件的外部逻辑结构）
与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的信息，如属性，位置和所有权等，这些信息主要由操作系统进行管理。
目录管理的基本要求：
- 从用户角度看，目录在用户所需要的文件名和文件之间需要提供一种映射，所以目录管理需要实现“按名存取”。
- 目录的存取效率直接影响到系统的性能，所以要提高对目录的检索速度。
- 共享系统中，目录还需要提供用于控制访问文件的信息。
- 文件允许重名也是用户的合理和必然要求，目录管理通过树形结构来解决和实现。
文件控制块和索引节点
文件控制块（FCB）
文件控制块，是用来存放控制文件所需的各种信息的数据结构，以实现“按名存取”，FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
为了创建一个新的文件，系统将分配一个FCB并存放在文件目录项中，成为目录项。
FCB主要包含以下信息：
- 基本信息：如文件名，文件的物理位置，文件的逻辑结构，文件的物理结构等。
- 存取控制信息：如文件存取权限等。
- 使用信息：如文件建立时间，修改时间等。
索引节点
在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中读出该文件的物理地址。
也就是说，在检索目录时，文件中的其他描述信息都不会用到，也不需要调入内存中。
因此有的系统，如UNIX，采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引节点的数据结构，称为i节点（应该是index节点的缩写）。目录项中仅保存文件名和i节点的指针。
一个FCB大小事64B，盘块大小事1KB，那么每个盘块中可以存放16个FCB（注意，FCB必须连续存储）。而在UNIX中，一个目录项仅占16B，文件名14B，2B是i节点的指针。
存放在磁盘上的索引节点称为磁盘索引节点，该节点内容包括：
- 文件主标识符：也就是拥有该文件的个人或小组的标识符。
- 文件类型：包括普通文件，目录文件或特别文件。
- 文件存取权限：各类用户对文件的存取权限。
- 文件物理地址：每个索引节点中包含13个地址项，即iaddr(0)~iaddr(12)，他们可以直接或间接方式给出数据文件所在盘块的编号。
- 文件长度。以字节为单位。
- 文件链接计数，在文件系统中所有指向该文件的文件名计数指针。
- 文件存取时间。本文件最近被进程存取的时间，最近被修改时间，及索引节点被修改时间。
文件打开时，磁盘索引节点复制到内存的索引节点中，以便使用，同时内存索引节点中增加了以下内容：
- 索引节点编号：用于标识内存索引节点。
- 状态：指示i节点是否上锁或被修改。
- 访问计数：每当有一进程要访问此i节点，计数加1，访问结束减1。
- 逻辑设备号：文件所属文件系统的逻辑设备号。
- 链接指针：设置分别指向空闲链表和散列队列的指针。
目录结构
在理解一个文件系统的需求前，我们首先考虑在目录这个层次上所需要执行的操作：
- 搜索。当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
- 创建文件。当创建一个新文件时，需要在目录中增加一个目录项。
- 删除文件。当删除一个文件时，需要在目录中删除相应的目录项。
- 显示目录。用户可以请求显示目录的内容，如显示该用户目录中所有文件及属性。
- 修改目录。某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。
操作时，考虑以下几种目录结构：
单级目录结构
整个系统中只建立一张目录表，每个文件占一个目录项，如图所示：
当访问一个文件时，首先按文件名在目录结构中找到相应的FCB，经过合法性检验后执行相应的操作。当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项目。删除文件时，首先找到FCB，回收文件占用空间，然后清理该目录项。
单级目录结构实现了“按名存取”，但是存在查找速度慢，文件不允许重名，不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。
两级目录结构
文件目录分为主文件目录（Master File Directory，MFD）和用户文件目录（User File Directory，UFD）两级。
主文件目录项记录用户名及相应的用户文件目录所在位置。
用户文件目录项记录该用户文件的FCB信息。
当某个用户想要访问文件时，只搜索该用户对应的UFD。
这既解决了不同用户文件的重名问题，又在一定程度上保证了文件的安全。
多级目录结构（树形目录结构）
这个就是我们最熟悉的目录结构了，有绝对路径，相对路径，工作目录（当前目录），所有的目录名和文件名之间用“/”分割。
书上说，树形目录查找一个文件时，需要按照路径名逐级访问中间节点，增加了磁盘访问次数，影响查询速度，但是个人感觉还是比上面两种快的。
无环目录结构
树形结构便于实现文件分类，但是不利于实现文件共享。
为此在树形目录结构的基础上增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图。
这里可以回头看一下数据结构与算法，如何判断一个图是否是有向无环图，无向无环图。
二者的算法是不完全同的，比如并查集算法可以用来识别无向图是否有环，但是不可以识别有向图是否有环。
无向无环图方便地实现了文件的共享，但是系统管理更加复杂。
文件共享
文件共享使多个用户（进程）共享同一个文件，系统只保留该文件的一个副本。
现代常用的文件共享方式有两种：
基于索引节点的共享方式（硬链接）
在树形目录的结构中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便找到。
这里有个问题，索引节点直接指向了文件，那这种方式可以共享目录吗？
这个问题的本质是，索引节点可以指向一个目录吗？进一步说FCB可以指向一个目录吗？
在这种共享方式中，诸如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而是放在索引节点中。在文件目录中只设置文件名及指向相应索引节点的指针。
在索引节点中还应该有个计数器，用于表示链接到本索引节点（即文件）上的用户目录项的数目。
某个用户删除文件时，并不能直接删除，而是要看一下计数器，如果计数器为0，由系统负责删除该文件。
利用符号链实现文件共享（软链接）
为了使用户B可以共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件，也取名F，然后将这个文件F保存到用户B的目录中，以实现用户B的目录与文件F相连。
新文件中只包含原文件F的路径名。这样的链接方法被称为符号链接。
新文件中的路径名只被视为符号链，当用户B要访问被链接的文件F且正要读LINK类新文件时，操作系统根据新文件的路径名去读该文件，从而实现用户B对文件F的共享。
只有文件的拥有者才拥有指向其索引节点的指针，而共享该文件的其他用户只有该文件的路径名，这样也就不会发生删除一个共享文件后留下一个悬空指针的问题（这个问题是硬链接的问题）。
当文件的拥有者删除一个共享文件时，其他用户通过符号链去访问文件时，会出现访问失败，这个时候就去把这个符号链删除，此时不会产生任何影响。
但是使用这种方式还是有问题，一个文件通过符号链接方式共享，文件的拥有者将其删除后，共享的其他用户在使用改符号链访问该文件之前，又有人在同一路径下创建了一个同名的文件，则该符号链还是有效的，但是指向的已经不是原本的文件了。
软链的方式，缺点是需要根据文件路径名逐个查找目录，直到找到该文件的索引节点。每次访问都可能要多次地读盘，使访问文件的开销增大，增加了启动磁盘的频率。
优点是，网络共享只需要提供该文件所在机器的网络地址和文件路径。
共同的问题
这两种链接方式都存在一个共同的问题，即每个共享文件都有几个文件名。
也就是说，每增加一条链接，就增加一个文件名。实质上是每个用户都使用自己的路径名去访问共享文件，那么当我们试图遍历整个文件系统时，就会多次找到该共享文件。
两种链接都是静态共享方法，在文件系统中还存在另外的共享需求，即两个进程同时对一个文件进行操作，这样的共享称为动态共享。
也就是说，这种静态共享的方式，只是解决了不同用户如何访问到同一个文件，但是，还是不能做到同时访问，同时访问属于动态共享。
文件保护
访问类型
对文件的保护，就是对文件的访问权限进行控制，访问类型主要分为：
- 读。从文件中读取。
- 写。向文件中写入。
- 执行。将文件从硬盘加载到内存中。
- 添加。将新信息添加到文件结尾部分。
- 删除。删除文件，释放空间。
- 列表清单。列出文件名和属性。
此外还可以对文件进行重命名，复制，编辑等加以控制。这些高层功能都可以由上面几种底层组合，所以保护只需要在低层进行就可以了。
这里有个问题，为什么要区分写操作和添加操作？
访问控制
ACL 访问控制表
解决访问控制最常用的方式是根据用户身份进行控制，从而实现基于身份访问的最为普通的方法是，为每一个文件和目录增加一个访问控制表（Access-Control List，ACL），规定的是每个用户名以及所允许的访问权限。
这种方法的优点是可以使用复杂的访问方法，缺点是长度无法预计且可能导致复杂的空间管理。
精简的访问列表采用拥有者，组和其他三类用户类型。
- 拥有者。创建文件的用户。
- 组。一组需要共享文件，且具有类似访问的用户
- 其他。系统内所有其他用户
这样只需要是哪个域即可列出访问表中这三类用户的访问权限。
文件拥有者在创建文件时，说明创建用户名及所在的组名，系统在创建文件时也将文件主的名字，所属组名都列在该文件的FCB中。
用户访问文件时，按照拥有者所拥有的权限访问文件，若用户和拥有者在同一个用户组，则按照同组权限访问，否则只能按照其他用户权限访问，UNIX就是采用这种。
这种权限控制方法经过拓展，其实就很像RBAC，基于角色的访问控制(Role-Based Access Control)。
口令
用户在建立一个文件时提供一个口令，系统为其建立的FCB附上相应口令，同时把这个口令告诉允许共享该文件的其他用户，用户请求访问该文件时必须提供相应口令。
这种时间和空间开销不大，但是口令是直接存在FCB中的，也就是直接就在系统中，不安全。
密码
这种是对文件进行加密，通过一串密码将原本的明文转成无法理解的密文存储，每次打开的时候都需要用户提供密码进行解码。
这种方式没有空间消耗，密码不需要存储，但是每次使用时都需要编码和解码。
口令和密码都是防止用户文件被其他人存取或窃取，并没有控制对文件的访问类型。
现代操作系统常用的文件保护方法是，将ACL和用户，组和其他成员访问控制方案一起使用。
对于多级目录而言，不仅需要保护单个文件，而且需要保护目录，而目录与文件不仅操作不同，而且目录项并没有FCB，所以目录保护的机制和文件保护机制并不相同。
回答开始的两个问题
什么是文件？什么是文件系统？
文件是以计算机硬盘为载体存储在计算机上的信息集合，它的形式多样，可以是文本文档，图片，程序等。操作系统中负责管理和存储文件信息的软件机构被称为文件管理系统，简称文件系统，文件系统由三部分组成：
- 与文件管理有关的软件
- 被管理文件
- 实施文件管理所需的数据结构
文件系统需要完成哪些功能？
对用户而言，文件系统最主要的功能是实现对文件的基本操作，让用户按名存取和查找文件，组织成合适的结构，并应当具有基本的文件共享和文件保护功能。
对操作系统本身而言，文件系统需要管理与磁盘的信息交换，完成文件逻辑结构和物理结构上的交换，组织文件在磁盘上的存放，采取好的文件存放顺序和磁盘调度方法以提高整个系统的性能。