1. 文件系统基础

1.1 文件的概念

1.1.1 文件的定义

文件是以计算机硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。

文件在逻辑上分为有结构文件和无结构文件两种。在有结构文件中，文件由一组相似的记录组成，又称记录式文件；而无结构文件则被视为一个字符流，又称流式文件。

1.1.2 文件的属性

1. 文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
2. 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
3. 类型：指明文件的类型
4. 位置：文件存放的路径（让用户使用）、在外存中的地址(操作系统使用，对用户不可见)
5. 大小：指明文件大小创建时间、上次修改时间文件所有者信息
6. 保护信息：对文件进行保护的访问控制信息
7. 时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用

1.1.3 文件的基本操作

1. 创建文件。创建文件有两个必要的步骤：一是在文件系统中为文件找到空间；二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统的位置及其他可能的信息。
2. 写文件。为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。
3. 读文件。为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。
4. 文件重定位（文件寻址）。按某条件搜索目录，将当前文件位置设为给定值，并且不会读、写文件。
5. 删除文件。先从目录中找到要删除文件的目录项，使之称为空项，然后回收该文件所占用的空间。
6. 截断文件。允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。

1.1.4 文件的打开与关闭

打开文件不是一个文件系统必须有的操作。
引入打开和关闭文件的目的是为了实现文件共享以及提高文件的存取效率。

打开文件所需要的数据结构：

1. 打开文件表：跟踪打开文件
2. 文件指针：指向最后一次读写的位置，每个进程一个
3. 打开文件计数器：打开文件次数（调用open次数）
4. 访问权限：每个进程的访问权限
5. 文件存储位置：文件存放在存储设备上的位置信息

1.2 文件的逻辑结构

文件的逻辑结构是从用户观点出发看到的文件的组织形式，文件的存储结构是从实现观点出发看到的文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关，但文件的物理结构与存储介质的特性有很大的关系。

按逻辑结构，文件可划分为无结构文件和有结构文件两种。

1.2.1 无结构文件（流式文件）

无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累、保存，它是有序相关信息项的集合，以字节为单位。

字符流的无结构文件虽然对记录的访问只能通过穷举搜索的方式，但是管理简单，用户可以方便地对其进行操作。所以，对基本信息操作不多的文件比较适合采用字符流的无结构方式，如源程序文件、目标代码文件等。

1.2.2 有结构文件（记录式文件）

有结构文件按记录的组织形式可以分为以下几种：

1. 顺序文件。
   文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储，在访问时需要顺序搜索文件。顺序文件有串结构和顺序结构两种结构。
   
   
   在对记录进行批量操作，即每次要读或写一大批记录时，顺序文件的效率是所有逻辑结构中最高的，而且，也只有顺序文件才能存储在磁带上，并且有效工作。并且记录存储紧凑，没有浪费空间。但是顺序文件对查找、修改、增加或删除单条记录的操作比较困难。

2. 索引文件
   索引文件的示意图如下所示：
   

• 对于定长记录文件，要查找第i条记录，可直接根据Ai = i x L得到第i条记录相对于第一条记录的地址。
• 对于可变长记录文件，要查找第i条记录，必须顺序地查找前i - 1条记录，从而获得相应记录地长度L。

变长记录文件只能顺序查找，系统开销大，为此可以建立一张索引表以加快检索速度。

索引表本身是定长记录的顺序文件，因此可以快速找到第 i 个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。

由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。另外，可以用不同的数据项建立多个索引表。如:学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。

索引文件解决了顺序文件不方便增删记录地问题，同时让不定长记录文件实现了随机存取，但索引表可能占用很多空间。

3. 索引顺序文件
   索引顺序文件是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项，其中包含该记录的关键字值和指向该记录的指针。

索引顺序文件示意图如下所示：

查找一条记录时，首先通过索引表找到其所在的组，然后在改组中使用顺序查找。

索引顺序文件提高了查找效率，若记录数很多，则可采用两级或多级索引。

索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间。

4. 直接文件或散列文件
   给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同与顺序文件或索引文件，没有顺序的特性。
   散列文件有很高的存取速度，但是会引起冲突，即不同的关键字的散列函数值相同。

1.3 目录结构

目录管理的基本要求：从用户的角度看，目录在用户所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”；目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度；在共享系统中，目录还需要提供用于控制访问文件的信息。此外，文件允许重名也是用户的合理和必然要求，目录管理通过树形结构来解决和实现。

1.3.1 文件控制块和索引结点

• 文件控制块（FCB）：文件控制块是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
• 索引结点：在检索目录时，文件的其他描述信息不会用到，也不需要调入内存。因此，有的系统采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构。

1.3.2 目录结构

在目录结构上执行的操作有如下几种：

1. 搜索。当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
2. 创建文件。当创建一个新文件时，需要在目录中增加一个目录项。
3. 删除文件。当删除一个文件时，需要在目录中删除相应的目录项。
4. 显示目录。用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。
5. 修改目录。某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。

几种常用的目录结构如下：
单级目录结构
在整个文件系统中只建立一张目录表，每个文件占一个目录项。
优点：实现了按名存取
缺点：查找速度慢、文件不允许重名、不便于文件共享

两级目录结构
将文件目录分为主文件目录和用户文件目录两级，如下图所示。

优点：解决了不同用户文件重名的问题，在一定程度上保证了文件的安全
缺点：缺乏灵活性，不能对文件分类，且同一用户不能有相同的文件名

多级目录结构（树形目录结构）

用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
从根目录出发的路径称为绝对路径，从当前目录出发的路径称为相对路径。
优点：可以很方便的对文件进行分类，层次结构清晰，能够有效地进行文件地管理和保护
缺点：查找文件时，需要按照路径名逐级访问中间结点，增加了访盘次数，影响了查询速度；不方便对文件共享

无环图目录结构
在树形目录结构地基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享。
无环图目录结构需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点。
注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

1.4 文件共享

文件共享使多个用户共享同一个文件，系统中只需保留该文件的一个副本。若系统不能提供共享功能，则每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。

1.4.1 基于索引结点的共享方式（硬链接）

索引结点，是一种文件目录瘦身策略。由于检索文件时只需要用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。

索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。
若count=2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。
若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
当count =0时系统负责删除文件。

1.4.2 利用符号链实现文件共享（软链接）

为使用户B能共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F，并将文件F写入用户B的目录，以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这种链接方法被称为符号链接。

当User3访问“ccc”时，操作系统判断文件“ccc”属于Link类型文件，于是会根据其中记录的路径层层查找目录，最终找到User1的目录表中的“aaa”表项，于是就找到了文件1的索引结点。

在符号链的共享方式中，当其他用户读共享文件时，需要根据文件路径名逐个地查找目录，甚至找到该文件的索引结点。因此，每次访问时，都可能要多次地读盘，使得访问文件的开销变大并增加了启动磁盘的频率。所以，软连接比硬链接要慢。此外，符号链的索引结点也要耗费一定的磁盘空间。

1.5 文件保护

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。

文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了防止用户文件被他人存取或窃取，而访问控制则用于对文件的访问方式。

2. 文件系统实现

2.1 文件系统层次结构

现代操作系统有多种文件系统类型，如FAT32，NTFS等，因此文件系统的层次结构也不尽相同。

2.2 目录实现

在读文件前，必须先打开文件。打开文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有线性列表和哈希表两种。线性列表实现对应线性查找，哈希表的实现对应散列查找。

• 线性列表：采用链表结构可以减少删除文件的时间，其优点在于实现简单，不过由于线性表的特殊性，比较费事。
• 哈希表：哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也标胶简单，不过需要一些预备措施来避免冲突。最大的困难是哈希表长度固定以及哈希函数对表长的依赖性。

2.3 文件实现

文件的实现就是研究文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。
一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理。

2.3.1 文件分配方式

常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。
连续分配
连续分配方法要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。

一个文件的目录条目包括开始块的地址和该文件所分配区域的长度。
优点：连续分配的文件在顺序访问时速度最快；支持直接访问和顺序访问；实现简单、存取速度快；适合一次性写入操作。
缺点：文件长度不宜动态增加；会产生磁盘碎片，浪费空间

链接分配
链接分配采用离散分配的方式，消除了外部碎片，显著提高了磁盘空间利用率；又因为根据文件的当前需求为其分配必须的块，当文件增长时，可以动态地再为它分配盘块。
链接分配又分为隐式链接和显示链接两种形式。

隐式链接分配如下图所示。每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针，这些指针对用户是透明的。目录包括第一块的指针和最后一块的指针。

优点：很方便文件拓展，不会有碎片问题，外存利用率高
缺点：只支持顺序访问，不支持随机访问，查找效率高；指向下一个盘块的指针也会耗费少量的存储空间。

显示链接是指把用于链接文件各物理块的指针，从每个物理块的块末尾中提取出来，显示地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，称为文件分配表（FAT）。每个表项中存放对应块的下一块链接指针，即下一个盘块号。文件的第一个盘块号记录在目录中，后续的盘块可提高查FAT找到。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表会占用一定的存储空间。

索引分配
索引分配解决了链接分配不能有效支持直接访问的问题，它把每个文件的所有的盘块号都集中放在一起构成索引表。
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

优点：索引分配支持直接访问，且没有外部碎片的问题
缺点：由于索引块的分配，增加了系统存储的开销

索引块太小无法支持大文件时，可以采用以下机制来处理这个问题：

• 链接方案。如果索引表太大，一个索引块装不下，可以将多个索引块链接起来存放
• 多层索引。多层索引使第一层索引块指向第二层的索引块，第二层的索引块再指向文件快。
• 混合索引。将多种索引方式相结合的分配方式。

文件三种分配方式的比较如下：

2.3.2 文件存储空间管理

文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织、分配和回收等问题。

1. 空闲表法
   空闲表法适用于连续分配方式。
   

2. 空闲链表法
   将所有的空闲盘区拉成一条空闲链，根据构成链所用的基本元素不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。
   分配：系统从链首开始，依次摘下适当数目的空闲盘块分配给用户
   回收：系统将回收的盘块依次插入空闲盘块链的末尾
   优点：不需要专用块存放管理信息
   缺点：增加I/O操作，得到连续空间难

3. 位示图法
   位示图利用二进制的一位来表示磁盘中的一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。当其值为“0”时，表示对应的盘块空闲；当其值为“1”时，表示对应的盘块已分配。
   

4. 成组链接法
   空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。适用于大型文件系统。

3. 磁盘组织与管理

3.1 磁盘的结构

磁盘是由表面涂有磁性物质的金属或塑料构成的圆形盘片，通过一个称为磁头的导体线圈从磁盘存取数据。磁盘盘面上的数据存储在一组同心圆中，称为磁道。磁道又分为几百个扇区，每个扇区固定存储大小，一个扇区称为一个盘块。
磁盘地址用“柱面号，盘面号，扇区号”组成。

3.2 磁盘调度算法

引入磁盘调度的目的：降低磁盘访问时间，提高文件系统的效率

1. 寻找时间(寻道时间)Ts：在读/写数据前，将磁头移动到指定磁道所花的时间。
   ①启动磁头臂是需要时间的。假设耗时为s；
   ②移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则：
   寻道时间Ts =s + m*n
2. 延迟时间TR：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r(单位:转/秒，或转/分），则
   平均所需的延迟时间TR= (1/2)*(1/r) = 1/2r
3. 传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则:
   传输时间T=(1/r)*(b/N)= b/(rN)

每个磁道要可存N字节的数据，因此b字节的数据需要b/N个磁道才能存储。而读/写一个磁道所需的时间刚好又是转一圈所需要的时间1/r

调度算法直接决定寻找时间，从而决定总的存取时间。

1. 先来先服务算法
   FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法。
   
   优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
   缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

2. 最短寻道时间优先
   SSTF算法选择调度处理的磁道是与当前所在磁道距离最近的磁道，以便使每次的寻找时间最短。
   
   优点：算法性能好，平均寻道时间短
   缺点：会产生饥饿现象

3. 扫描算法
   SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，实际上就是在最短寻找时间优先算法的基础上规定了磁头运动的方向。又称电梯算法。
   
   优点：性能较好，寻道时间短，不会产生饥饿现象
   缺点：只有达到最边上的磁道时才能改变磁头移动方向；对于各个位置的磁道响应频率不平均

4. 循环扫描算法
   在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。
   优点：比起SCAN来，对于各个位置磁道的响应频率很平均。
   缺点：只有到达最边上的磁道时才能改变磁头移动方向；另外，比起SCAN算法来，平均寻道时间更长。

总结如下：

除减少寻找时间外，减少延迟时间也是提高磁盘传输效率的重要因素。可以对盘面扇区进行交替编号，对磁盘片组中的不同盘面错位命名。
磁盘的物理地址是（柱面号，盘面号，扇区号），而不是（盘面号，柱面号，扇区号），因为在读取地址连续的磁盘块时，前者更不需要移动磁头。

3.3 磁盘的管理

3.3.1 磁盘初始化

1. 进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。
2. 将磁盘分区，每个分区由若干柱面组成（即分为我们熟悉的C盘、D盘、E盘)
3. 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（(如位示图、空闲分区表)

3.3.2 引导块

计算机启动时需要运行一个初始化程序，完成初始化，它初始CPU、寄存器、设备控制器和内存等，接着启动操作系统。

3.3.3 坏块

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它。

简单的磁盘：逻辑格式化时将坏块标记出来
复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区