引言
由于内存是易失的，断电就会丢失，所以需要文件来保存数据。而文件系统就是用于管理操作系统中的文件。
这篇文章是写得最懵的...知识点都比较杂乱，可能逻辑性没有组织的特别好。
见谅呀(>﹏<)
文章导读
- 文件和文件系统相关概念
- 文件别名与文件系统类别
- 文件分配（连续分配，链式分配，索引分配）
- 提高I/O速度的方法（高速缓存，提前读，延迟写，优化物理块分布，虚拟盘，RAID）
- 磁盘调度算法（FCFS，SSTF，SCAN系列）
一、文件和文件系统相关概念
文件系统：一种用于持久性存储的系统抽象。
文件：系统中一个单元的相关数据在操作系统中的抽象。
文件系统的功能
1.分配文件磁盘空间
管理文件块；管理空闲空间；分配算法。
2.管理文件集合
定位文件及其内容；命名（通过名字找到文件的接口）；最常见的是分层文件系统。
3.提供便利及特征
保护数据安全 ；保持文件的持久即使发生崩溃，媒体错误攻击，也要减少数据的丢失等。
文件头
文件头存储文件的元数据信息，属性以及跟踪哪一块存储块属于逻辑上文件结构的哪个偏移。
文件描述符
文件描述符用于内核跟踪每个进程打开的文件，操作系统为每个进程维护一个打开文件表，一个打开文件描述符就是这个表中的索引。C语言中的open()函数返回的就是一个文件描述符。
对于一个文件，需要许多的元数据来对其进行管理。其中包括：
- 文件指针：指向最近一次读写位置，每个打开了这个文件的进程都是这个指针。
- 文件打开计数：记录文件打开的次数，当最后一个进程关闭了文件时，允许将其从打开文件表中移除。
- 文件磁盘位置：缓存访问信息。
- 访问权限：每个程序访问模式信息。
如果将所有文件进行线性的显示，则显得杂乱无章，所以需要目录来组织文件。下面看看目录相关的概念。
目录
文件是以目录的方式组织起来，目录也是一类特殊的文件。值得注意的是，操作系统只允许内核状态下修改目录，以确保映射的完整性。
根据目录找到对应文件的过程叫做名字解析。是将逻辑名字转换成物理资源的过程，遍历文件目录直到找到目标文件。
二、文件别名与文件系统类别
2.1 文件别名
文件别名可分为软链接和硬链接。软链接是以“快捷方式”指向其他文件，通过存储文件的逻辑名称来实现；而硬链接是多个文件项指向一个文件。后续会讲，多个硬链接文件对应一个inode，当这个inode改变时，硬链接文件中的内容也会同步。
2.2 文件系统的类别
文件系统主要分为磁盘文件系统（文件存储在数据存储设备上），数据库文件系统（文件根据其特征是可被寻址的），日志文件系统（记录文件系统的修改/事件），网络/分布式文件系统，特殊/虚拟文件系统。下面主要说虚拟文件系统。
2.2.1 虚拟文件系统
虚拟文件系统是对所有不同文件系统的一层抽象，通过虚拟文件系统来屏蔽底层文件系统的差异。
图片来源于网络
从图中可以看出，虚拟文件系统屏蔽了底层的磁盘文件系统和网络文件系统。操作系统又在此基础之上给应用程序提供相关的API。
功能
1.提供相同的文件和文件系统接口。
2.管理所有文件和文件系统关联的数据结构。
3.高效查询便利文件系统。
4.与特定文件系统模块的交互。
2.2.2 虚拟文件系统的组成
除去各个文件系统之间差异性的东西，一般的文件系统由什么组成呢？
主要是卷控制块，目录节点和文件控制块及数据。
卷控制块（superblock）
每个文件系统有一个卷控制块，记录着文件系统详细信息以及块，块大小，空余块，计数/指针。
目录节点（dentry）
每个目录项一个，将目录项数据结构及树型布局编码成树型数据结构。指向文件控制块，父节点，项目列表等。
文件控制块（vnode或inode）
每个文件一个，记录文件详细信息，比如许可，拥有着，大小，数据库位置等。
如上图所示，一个虚拟文件系统有一个卷控制块，对应一个根目录，每个目录节点都可以与其他目录或文件建立联系，然后文件指向自己的数据块（存放在磁盘中）。
不管是哪个控制块还是文件，都会对应到磁盘里的某个扇区。操作系统还需要考虑什么时候将什么数据块拿到内存中来。当需要时加载进内存，下面是各个块加载进内存的时机：
- 卷控制模块：当文件系统挂载时进入内存。
- 文件控制块：当文件被访问时进入。
- 目录节点：在遍历一个文件路径时进入内存。
三、文件分配
大多数文件都很小，需要对文件提供强力的支持，块空间不能太大。一些文件非常大，必须支持大文件，大文件访问需要高效。那么，如何为文件分配数据块？分配方式有连续分配，链式分配，索引分配。
文件分配的指标有存储利用和访问速度。
3.1 文件分配方式（外存的组织方式）
3.1.1 连续分配
连续分配主要是由文件头指定起始块和长度。
注：本次分配的空间为蓝色，紫色为已分配的空间，浅蓝色为空闲空间。
优点
1.文件读取表现好。
2.高效的顺序和随机访问。
3.对于只读的文件来说是最佳选择。
缺点
会产生碎片问题；
面临文件增长问题，可能需要预分配。
3.1.2 链式分配
文件以数据块链表方式存储，文件头包含了到第一块和最后一块的指针。
优点
文件创建，增大，缩小很容易；
没有碎片。
缺点
不可能进行真正的随机访问；
可靠性问题，断电后某个节点信息丢失会导致后序的都丢失。
3.1.3 索引分配
为每个文件创建一个名为索引数据块的非数据数据块（就是到文件数据块的指针列表，文件头包含了索引数据块）。
优点
创建，增大，缩小很容易；
没有碎片；
直接访问。
缺点
当文件很小时，存储索引的开销；
如何处理大文件，一个索引块描述的数据快的数量是有限制的。如何对索引块扩容，以及多级索引块问题。（链式索引块，多级索引块都是对大索引块的解决方案）
3.2 文件存储空间的管理
在进行文件分配之前需要组织空闲空间，便于后续内存分配。主要讲述空闲列表法和位示图法。
3.2.1 空闲列表法
为每个文件分配一块连续的存储空间。每个空闲区对应一个空闲表项，包括序号，第一块空闲盘号，该区的空闲盘块数等。如下图所示。
分配时和之前的内存分配策略差不多，可以是首次适配法，最佳适配法等等。空闲盘块表作为分配的依据，系统会先顺序检索，然后找到打一个大小能满足要求的空闲区，分配内存，修改空闲表。
在回收时考虑，空闲区是否可以合并等。这种分配方式能够减少磁头的寻道时间和访问IO的频率。
3.2.2 位示图法
利用二进制的一位来表示磁盘中一个盘块的使用情况，可以规定0为空闲，1为使用。一般用 
个位数来构成一个二位的位示图map[m,n]。其中=磁盘块的总块数。
一般来说，空闲快越多，扫描的时间越短。如果空闲空间在磁盘均匀分布，那么在找到“0”之前需要扫描n/r。
注：n=磁盘上数据块的总数；r=空闲块的总数。
磁盘与内存数据一致性问题
由于位图存储在硬盘上，为了提高效率，会将其读到内存中来。如何确保硬盘和内存中的位图的一致性？
前提条件
位图必须保存在磁盘上；
在内存和磁盘拷贝有所不同；
不允许block[i]（某一块）在内存中的状态为bit[i]=1而在磁盘中bit[i]=0。
解决办法分为三步：
1）在磁盘设置bit[i]=1
2）分配block[i]
3）内存中设置bit[i]=1
只要修改磁盘中的值，此时断电重启后，就不会出现已分配的资源未置1啦~
四、提高I/O速度的方法
对于文件系统性能的优化，大致有三个方向：
（1）改进文件的目录结构以及检索目录的方法，减少目录的查找时间。
（2）选取好的文件存储结构，以提高对文件的访问速度。
（3）提高磁盘的I/O速度，能讲文件的数据快速地从磁盘传送到内存。
前两点在之前都有所涉及，现在来看看提高磁盘IO的方法有哪些。
4.1 利用高速缓存
让一些经常访问的数据从缓存中获取，可以直接存数据，也可以指针。尽可能快低让数据从缓存到进程的内存工作区。光有高速缓存还不够，要搭配着合适的页面置换算法来使用才能奏效。
相关的置换算法已经在内存管理中都讲解过，主要应该参考访问频率，可预见性，数据的一致性等因素，还应具备周期性的回写（Unix增设update程序，周期性地调用SYNC，强制性地将所有在高速缓存中已修改的盘块数据写回磁盘，保证数据一致性）。
4.2 其他方法
其他方法有提前读，延迟写，优化物理块分布，虚拟盘等。
提前读
很好理解，如果是顺序访问的，就采取预先读取的方式，在读当前块时，将下一个盘块也读到缓冲区，从而减少了下一次的查找和读取时间。
延迟写
操作系统认为被修改过的数据可能在后续被访问或修改的概率会很大，才产生了这种策略。当缓冲区的数据本应立即被写回磁盘时，将它挂在空闲缓冲区的尾部，随着缓冲区内存的分配，直到其移到空闲缓冲区队首时，将其写回到磁盘。在此期间，可以任意地访问和修改，减少对磁盘的访问时间。
优化物理块的分布
尽可能地将一个文件对应的盘块分布在同一个磁道上，消除寻道时间。
虚拟盘（RAM）
用内存区仿真磁盘，在虚拟盘上的设备可以接收所有标准的磁盘操作，这些操作对用户透明。由于断电后RAM的数据会丢失，所以一般用于存储临时文件。
4.3 RAID（磁盘冗余阵列）
RAID的思想是使用多个相同的组件来获得性能最大复度的提高。一个大容量的磁盘冗余阵列就是由多个小磁盘组成的。
RAID分为7个级别，下面对重要的级别进行简单的介绍。
RAID0
提供了并行交叉存取的功能。
RAID0原理图
将数据块拆分为几个子块，均匀的存储在独立的磁盘中，访问时可以并行来提高效率。通过更大的有效块大小来提供更大的磁盘带宽。
缺点是没有错误校验机制，如果某个磁盘孙环，就会造成数据丢失。
RAID1
相对RAID0而言，RAID1提供了可靠性。增加了磁盘镜像，向两个磁盘写入，从任何一个读取。故障恢复简单。
RAID4
希望既能提高IO性能，又能提供可靠性。于是增加了一个Parity Disk用于做奇偶校验。
RAID4原理
数据块级磁带配有专门的奇偶校验磁盘，允许从任意一个故障磁盘中恢复。
注：关于奇偶校验不懂的可以戳这里~
RAID5
没有专门的奇偶校验盘。让块均匀分布在每一个disk中，让开销也均匀，既保证了校验变得均匀，又让访问是并行的。一般是按照块来奇偶校验的。
RAID5实现原理
从上图中可以看除每隔4个块来进行一次校验~
RAID6
使用两个冗余块，用一种特殊的编码方式，允许磁盘错误。
五、磁盘调度算法
选择好的磁盘调度算法，可以有效地减少磁盘的寻道时间，从而提高IO速度。在外设层面，通过重新组织IO的顺序来有效的减少访问的开销。读或写入时，磁头必须被定位在所期望的磁道，并从所期望的扇区开始。
几个概念
寻道时间：定位到期望的磁道所花费的时间。
旋转延迟：从扇区的开始处到到达目的处花费的时间。
平均旋转延迟时间=磁盘旋转一周时间/2。
5.1 FCFS（先来先服务）
寻道时间是性能上区别的原因，对于单个磁盘，会有一个I/O请求数目，如果请求是随机的，那么表现会很差。
按顺序处理请求，公平对代所有进程，在很多进程的情况下，接近随机调度的性能。
5.2 SSTF（短查找时间优先）
选择从磁臂当前位置需要移动最少的I/O请求，总是选择最短寻道时间。该算法的目标是使每次磁头移动时间最少。它不一定是最短平均柱面定位时间，但比FIFO算法有更好的性能。可能会有进程处于饥饿状态。
5.3 SCAN，C-SCAN，NStepSCAN，FSCAN
SCAN
磁臂在一个方向上移动，满足所有未完成的请求，直到磁臂到达该方向上最后的磁道，再调换方向，有时被称为elevator algorithm。
C-SCAN
是对SSTF算法的改进，磁盘I/O较好，且没有进程会饿死。限制仅在一个方向上扫描，当最后一个磁道也被访问过了后，磁臂返回到磁盘的另一端再次进行扫描。
NStepSCAN
为了解决磁臂粘着现象。如果某个进程反复请求对某一磁道的IO操作，从而垄断了整个磁盘设备，这一现象就是磁臂粘着。N步SCAN算法是讲磁盘请求队列分成若干个长度为N的队列，用FCFS处理队列。对于具体的每一个队列的处理又是按照SCAN算法来实现的。当处理某个队列时，此时新请求同一磁道，将会被放到队列中，等前面的队列都处理完了再处理这个队列。从而避免的磁臂粘着的出现。
FSCAN
FSCAN算法实际上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个队列。
一个是由当前所有请求磁盘的进程形成的队列，采用SCAN处理。在处理当前队列的期间，将新出现的所有请求磁盘的IO进程放入另一个等待处理的请求队列。所有的请求都将被推迟到下一次扫描时处理。
参考文章：操作系统第七篇【设备管理】，《计算机操作系统 第四版》
顺便分享一下我看操作系统的链接