一.文件系统基础

问题线索：
①什么是文件？什么是文件系统？
②文件系统要完成哪些功能？

1.1文件的概念

1. 文件的定义
   ①概念：以计算机硬盘为载体存储在计算机上的信息集合，文件可以是文档、图片、程序等等。
   ②文件的地位：
   系统运行时，计算机以进程为基本单位进行资源的调度和分配
   用户输入输出时，以文件作为基本单位。
   ③文件系统：实现用户对文件的操作和管理要求，如——访问、修改、保存文件，实现对文件的维护管理。
   ④文件的结构：

2. 文件的属性
   

1.2 文件的逻辑结构

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

1. 无结构文件（流式文件）

无结构文件是最简单的文件组织形式。无结构文件按顺序组织成记录并积累保存，它是有序相关信息项的集合，以字节为单位。
对无结构文件的记录的访问只能采用字符流的无结构方式。

2. 有结构文件（记录式文件）

①顺序文件：文件中的记录式一个接一个地按照顺序排列的，记录通常都是定长的，访问的时候需要顺序搜索。
a.串结构：记录之间的顺序和关键字无关。通常按照存取时间确定记录之间的顺序。
b.顺序结构：文件中的所有记录按关键字顺序排列。
评价：顺序文件的读写效率是最高的，也只能顺序文件可以存储在磁带上；但是顺序文件的增删改等操作比较困难。

②索引文件：是为了提高对于变长记录文件的访问速度而引入索引表，索引表自身是定长记录的顺序文件

③索引顺序文件
将顺序文件中的所有记录分成若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的关键字值和指向这个记录的指针。
将记录划分为组的时候，组与组之间关键字是有序的，组内可以无序。最后查找的时候通过索引表查找到该记录所在的组，然后再在组中使用顺序查找。

④直接文件或散列文件：通过记录的键值经过Hash函数的转换得到的键值作为给定记录的物理地址。这种映射结构没有顺序的特性，有很高的存取速度，但是会引起冲突。

综上：有结构的文件逻辑结构实质上是为了在文件中查找数据来服务的，因为上述四种结构分别对应四种查找结构：顺序查找、索引查找、索引顺序查找、哈希查找。

1.3 目录结构

目录结构解决的问题是多个文件之间在逻辑上是如何组织的，实际上，是文件“外部”的逻辑结构的问题。

1. 文件控制块和索引节点

①文件控制块（可以类比进程控制块出现的原因）
是用来存放控制文件所需要的各种信息的一种数据结构，FCB的有序集合就称为文件目录。
FCB含有的信息：
【基本信息】文件名、物理位置、逻辑结构、物理结构
【存取控制信息】文件存取权限
【使用信息】文件建立时间、修改时间

②索引节点
有的时候，检索文件目录只需要用到文件名，所以在检索目录的时候除了文件名的其他信息不会用到，也不会被调入内存。像UNIX这样的系统采用了文件名的文件描述信息分开的方法，文件描述信息单独形成一个称为索引节点的数据结构，而文件目录中的每个目录项仅由文件名和指向该文件所对应的i节点的指针构成。

2. 目录结构

①文件目录层次所需要处理的操作

②单级目录结构：在整个文件系统中只建立一张目录表，每个文件占一个目录项

查找文件：按照文件名在目录中查找相应的FCB
创建新文件：检索所有的目录项以确保没有重名，再在目录中增设一项
删除一个文件：在目录中找到该文件对应的目录项，回收文件所占用的存储空间，再清除该目录项。
评价：查找速度慢，文件不允许重名，不便于文件共享，多用户操作系统不适用。

③两级目录结构：将文件分成主文件目录和用户文件目录，主文件目录记录用户名及相应用户文件目录所在的存储位置；用户文件目录项记录该用户文件的FCB信息。

④多级目录结构

⑤无环图目录结构
在树形目录结构的基础上增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图。
若用户要对共享节点执行删除的时候，需要对共享节点维护的共享计数器减一，只有当计数器为0的时候，才能真正删除该节点，否则仅仅删除请求用户的共享链。

1.4文件共享

1. 硬链接——基于索引节点的共享方式

①当有多个用户共享一个子目录或者文件的时候，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件。

2. 软链接——利用符号链实现文件共享

当用户A共享另一用户B的某个文件，需要有系统创建一个LINK类型的文件，并把这个文件写入A的目录，在这个文件中只包含链接文件的路径名。

1.5文件保护

1. 相关基础概念

①内容：控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。
②原因：文件的共享可能会导致文件被破坏或未经核准的用户修改文件。
③实现手段：通过口令保护、加密保护和访问控制等方式实现。

• 口令保护和加密保护是为了防止用户文件被他人存取或窃取。
• 访问控制则用于控制用户对文件的访问方式。

2. 访问类型

在对文件进行保护的时候可以从多个角度切入，其中，限制对文件的访问类型就是一个角度。

读：从文件中读
写：向文件中写
执行：将文件装入内存并执行
添加：将新信息添加到文件结尾部分
删除：删除文件，释放空间
列表清单：列出文件名和文件属性
或者对文件的重命名、复制、编辑等加以控制。这些复杂的高层功能通过系统程序调用低层系统调用来实现。保护可以在低层提供。

3. 保护方法

①口令

用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应口令，同时告诉允许共享该文件的其他用户。用户请求访问时需要提供相应的口令。
时空开销不大，但口令存储在系统内部，不太安全。

②密码
用户对文件进行加密，文件访问时需要使用密钥。这种方法保密性强，节省存储空间，但是编码和译码需要花费一定时间。

口令和密码都只是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型。

③访问控制——根据用户身份进行控制，为每个文件和目录增加一个访问控制列表
虽然可以使用比较复杂的访问方法，但是长度无法预计并且可能导致复杂的空间管理。
plus:精简的访问列表
拥有者：创建文件的用户
组：一组需要共享文件且具有类似访问的用户
其他：系统内的所有其他用户
只需要用三个域列出访问表中这三类用户的访问权限即可。

二.文件系统实现

2.1 文件系统层次结构

2.2 目录实现

在读文件前，需要打开文件，打开文件的过程，操作系统需要利用路径名找到相应目录项，目录项中提供了查找文件磁盘块需要的信息。
目录实现的方法有线性列表和哈希表，因为目录的实现是为了查找，线性列表实现对应线性查找，哈希表的实现对应散列查找。

1. 线性列表

2. 哈希表
   优：查找，插入和删除等操作十分迅速
   缺：需要预备的冲突避免策略，哈希表长度固定且对长度具有依赖性。

目录查询是在磁盘上反复搜索操作完成的，需要不断进行I/O操作，开销较大。
可以把当前使用的文件目录复制到内存，以后使用的时候只在内存中操作，从而降低了磁盘的操作次数，提高系统速度。

2.3 文件实现

把文件看成是一种抽象结构，那么我们对文件需要关注的内容就是——逻辑结构、物理结构和一系列操作。
文件实现——研究文件的物理结构，数据在物理存储设备上是如何分布以及组织起来的。
①文件的分配方式——对磁盘非空闲块的管理
②文件存储空间管理——对磁盘空闲块的管理

1. 文件分配方式

所谓文件分配，对应于文件的物理结构，是指如何为文件分配磁盘块。
常见的磁盘空间分配方法有：连续分配、链接分配和索引分配。

（1）连续分配
要求每个文件在磁盘上占有一组连续的块，磁盘的物理地址就定义了磁盘上的一个线性排序。

• 模式：如果文件有n块长并从位置b开始，那么该文件将占有块b，b+1,…b+n-1。一个文件的目录条目包括开始块地址和该文件所分配区域的长度。
• 磁盘上原始定义的线性排列，使得作业访问磁盘时需要的寻道数和寻道时间最小。

（2）链接分配
采用离散分配的方式，消除了外部碎片，显著提高了磁盘空间的利用率；按需进行盘块的分配，文件动态增长的时候可以动态进行分配。
①隐式链接：每个文件对应为一个磁盘块的链表，每一个盘块都有指向下一个盘块的指针（除了最后一个盘块）。


②显式链接：
把用于链接各个文件物理块的指针，从每个物理块的末尾中取出来，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，每个表项中存放对应块的下一链接地址，也就是下一个盘块号。

（3）索引分配

索引分配继续解决链接分配不能直接访问的问题，把每个文件的所有盘块号集中放在一起构成索引表。

• 每个文件都有对应的索引块，是一个磁盘块地址的数组。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第i块，通过索引块的第i个条目的指针来查找和读入所需要的块。

2. 文件存储空间管理

文件存储空间管理的具体任务

①文件存储器空间的划分与初始化：
一个文件一般来说存储在一个文件卷中。一个文件卷可以是一个物理块的一部分，也可以是一整个物理块。
因为文件数据信息的空间和存放文件控制信息FCB的空间是分离的。因为文件的种类和存放的格式是多样的，所以现代操作系统中会有很多不同的文件管理模块。因此逻辑卷在提供文件服务之前，需要先划分好目录取和文件区。


②对空闲块的组织和管理。
因为文件存储设备分成了许多大小相同的物理块，所需要做的任务就是空闲块的组织、分配与回收等问题。

（1）空闲表法对空闲块进行分配

• 特点：连续分配方式，机制类似于内存的动态分配方式
• 机制：系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项，其中总包括表项序号、空闲区第一个盘块号、该区的空闲盘块数等信息。
  
• 系统在对用户所释放的存储空间进行回收的时候，也采取类似于内存回收的方法，考虑回收区是否与空闲表中插入点的前区和后区相邻接，对邻接者应予以合并。

（2）空闲链表法

• 本质：将所有的空闲盘区拉成一条空闲链。
• 类别：空闲盘块链，空闲盘区链
  ①空闲盘块链是将磁盘上的所有空闲空间，以盘块为单位拉成一条链，在分配的时候和内存动态分配方式一样，采用首次适应算法。
  ②空闲盘区链是将磁盘上的所有空闲盘区拉成一个链，在每个盘区上除了含有用于指示下一个空闲盘区的指针外，还应有指明本盘区大小（盘块数）的信息。

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

（4）成组链接法
对于大型文件系统，空闲表和空闲链表其实都是不适用的，因为光空闲表本身就会很大。在UNIX中采用的是成组链接法。

• 基本思想：把顺序的n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，如此继续，直到所有的空闲扇区都相互链接。对于系统而言，只需要保存指向第一个空闲扇区的指针即可。
  

三.磁盘组织与管理

3.1 磁盘的结构

磁盘：表面涂有磁性物质的金属或者塑料构成的圆形盘片，通过一个称为磁头的导体线圈从磁盘中存取数据。

磁道：磁盘的盘面上的数据存储在一组同心圆中，称为磁道。

扇区：一个盘面有上千个磁道，磁道又划分为几百个扇区，每个扇区都是固定的存储大小。一个扇区又称为一个盘块。
p.s. 相邻的磁道和扇区之间通过一定的间隙进行分隔，以避免精度错误。

3.2 磁盘调度算法

1. 一次磁盘的读写操作时间

读写操作时间=寻道时间+延迟时间+传输时间

（1）寻找时间Ts：活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。，包括跨越n条磁道的时间，启动磁臂的时间s。
T_s = m x n+s
p.s. m是和磁盘驱动器速度有关的常数，约为0.2ms。

（2）延迟时间：磁头定位到某一磁道的扇区（块号）所需要的时间

（3）传输时间：从磁盘读出或向磁盘写入数据所经历的时间，取决于每次读写的字节数和磁盘的旋转速度。

2. 常见的磁盘调度算法
   （1）FCFS
   
   （2）SSTF
   
   
   （3）SCAN算法
   
   （4）CSCAN算法
   

磁盘调度算法的比较

3.3 磁盘的管理

1. 磁盘的初始化

• 一个新的磁盘时一个空白盘，本身只含有磁性记录材料。
• 低级格式化（物理分区）：在磁盘可以存储数据之前，必须分成扇区以便磁盘控制器可以进行读写操作。每个扇区的数据结构通常由头数据区域（512B大小）和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息。
  
• 逻辑格式化：操作系统将自己的数据结构记录在磁盘上——第一步，将磁盘分成由一个或多个柱面组成的分区（C、D盘等分区形式）；第二步，对物理分区创建文件系统，将初始的文件系统数据结构存储到磁盘上，数据结构包含空闲和已分配的空间以及一个初始为空的目录。

2. 引导块
   
3. 坏块

坏块属于硬件故障，操作系统是不能修复坏块的，只能采用某种机制，使系统不去使用坏块。
简单磁盘而言，坏扇区可以手工处理，在执行逻辑格式化时扫描磁盘检查坏扇区，在FAT表上进行标明，程序不会使用。
复杂磁盘而言，控制器维护一个坏块链表。

后记

本文系在复习操作系统时阅读《王道2019年操作系统考研复习指导》记笔记所作