本文共 4967 字，大约阅读时间需要 16 分钟。
文章目录
文件的属性：文件名、标识符、类型、位置、大小、创建时间、修改时间…
文件系统的结构层次：
文件的逻辑结构
所谓“逻辑结构”，就是指在用户来看，文件内部的数据应该是如何组织起来的。
无结构文件
文件内部的数据就是一系列二进制流或字符流组成，又称"流式文件"，如.txt文件。
有结构文件
由一组相似的记录组成，又称记录式文件。每条记录又由若干个数据项组成，如数据库表文件，每条记录有一个数据项可以作为关键字。根据各条记录的长度，又可以分为定长记录和可变长记录两种。
根据有结构文件中的各条记录在逻辑上如何组织，可分为三类：
顺序文件
顺序文件：文件中的记录一个接一个地在逻辑上顺序排列，记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
-
顺序存储：逻辑上相邻的记录物理上也相邻（类似于顺序表）。
可变长记录：无法实现随机存取。每次只能从第一个记录开始依次往后查找。因为对于顺序存储下的可变长记录，除了记录内容还需要显式地给出记录长度。
定长记录：可实现随机存取。记录长度为L，则第i个记录存放的相对位置是i*L。若采用串结构，无法快速找到某关键字对应的记录。若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
-
链式存储：逻辑上相邻的记录物理上不一定相邻（类似于链表）。无论是定长还是可变长记录，链式存储都无法实现随机存取，每次只能从第一个记录开始依次往后查找。
索引文件
解决可变长记录查找速度慢的问题。
建立一张索引表以加快文件检索速度。每条记录对应一个索引项。索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。
每当要增加删除‘一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
索引顺序文件
针对索引文件本身占据空间较大的问题，引入了索引顺序文件。
索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
为了进一步提高检索效率，可以为顺序文件建立多级索引表。
文件目录
文件控制块
文件控制块是实现文件目录的关键数据结构。
FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、用户访问权限等），使用信息（如文件的建立时间、修改时间等）。FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”。
目录结构
单级目录结构
早期的操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。单级目录实现了按名存取，但是不允许文件重名，无法多用户操作。
两级目录结构
早期的多用户操作系统，采用两级目录。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User File Directory）。两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类。
多级目录结构
也称树形目录结构
用户或用户进程要访问某个文件时要用文件路径名标识符文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。系统会根据绝对路径一层层地找到下一级目录。
也可以通过当前目录，根据相对路径查找。
无环图目录结构
树形目录可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件地管理和保护。但是，树形结构不便于实现文件共享。为此，进一步提出了无环图目录结构。
在树形目录结构地基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。
可以用不同的文件名指向同一个文件，甚至指向同一个目录（共享同一目录下的所有内容）。需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享节点。
索引节点
为了FCB的大小，较少磁盘I/O次数，将除了文件名之外的所有信息都放到索引节点中，每个文件对应一个索引节点。目录项中只包含文件名、索引节点指针，因此每个目录项的长度大幅减小，每个磁盘块可以存放更多的目录项，因此检索文件时磁盘I/O次数会减少很多。
文件管理功能
文件共享
文件共享使多个用户（进程）共享同一份文件，系统中只需保留该文件的一份副本。否则，每个使用共享文件的用户都有各自的副本，会造成对存储空间的极大浪费。
1.基于索引结点的共享方式（硬链接）
在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件。
在索引结点中还应有一个链接计数count。当count=2时，表示有两个用户目录项链接到本文件上，共享此文件。添加和删除用户时count随之变化，count为0时，将删除此文件。
2.基于索引结点的共享方式（软链接）
为使用户B能共享用户A的一个文件F，可创建一LINK类型名为Flink的新文件，并将文件Flink写入用户B的目录中，以实现用户B的目录与文件F的链接。在Flink文件中只包含被链接文件F的路径名。此链接方法被称为符号链接。类似于windows系统中的快捷方式。
文件保护
口令保护
为文件设置一个“口令”，用户想要访问文件时需要提供口令，由系统验证口令是否正确。
系统开销少，但口令存放在FCB中或索引结点中，因此不安全。
加密保护
用一个密码对文件异或加密，用户想要访问文件时，需要提供相同的密码才能正确的解密。
安全性高，但解密/加密需要消耗一定的资源和时间
访问控制
用一个控制访问表（ACL）记录各个用户（或各组用户）对文件的访问权限。
对文件的访问类型可分为：读/写/执行/删除等
实现灵活，可以实现复制的文件保护功能。
文件磁盘块管理
文件的物理结构
文件的物理结构管理是对非空闲磁盘块的管理。
磁盘块的大小与内存块、页面大小相同。逻辑块号与磁盘块一一对应。
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。这种分配方式保证了逻辑文件中的的记录顺序与存储器中的文件占用盘块的顺序是一致的。
物理块号 = 起始块号 + 逻辑块号
优点在于连续分配的文件在顺序读/写时速度最快。
缺点在于，文件长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加， 就需要大量移动盘块。在外存上使用紧凑技术所花费的时间远比内存紧凑一次所花费的时间多得多。
链接分配
链接分配是釆取离散分配的方式，消除了外部碎片，故而显著地提高了磁盘空间的利用率；又因为是根据文件的当前需求，为它分配必需的盘块，当文件动态增长时，可以动态地再为它分配盘块，故而无需事先知道文件的大小。此外，对文件的增、删、改也非常方便。
链接分配又可以分为隐式链接和显式链接两种形式。
隐式链接：
文件，目录中每个目录项都包括指向链接文件第一盘块和最后一个盘块的指针。磁盘块分布在磁盘的任何地方，除最后一个盘块外，每一个盘块都有指向下一个盘块的指针，这些指针对用户是透明的。
优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：隐式链接只适用于顺序访问，对随机访问时极其低效的
显式链接：
显示链接把用于链接文件各物理块的指针，显示地存放在内存的一张链接表中。该表在整个磁盘仅设置一张。表的序号从0开始，直至N-1，N为盘块总数，在每个表项中存放链接指针，即下一个盘块号。由于查找记录的过程是在内存中进行的，因而提高了检索速度，减少了访问磁盘的次数。
但FAT需要占用较大的内存空间。
索引分配
在打开某个文件时，只需把该文件占用的盘块号的编号调入内存即可，无需把整个FAT调入内存。为此，将每个文件所对应的盘块号集中地放在一起，索引分配方式就是基于此想法所形成的一种分配方式。
1.单级索引
其为每个文件分配一个索引表，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多磁盘块号的数组。在建立一个文件时，只需要在为之建立的目录项中填上指向该索引块的指针。
2.多级索引
当文件太大时，索引块太多，单级索引是低效的。此时，为这些索引块再建立一级索引，称为第一级索引，还可再建立索引，称为第二级索引等等。称为多级索引分配。
3.混合索引
将多种索引分配方式相结合而形成的一种分配方式，如直接地址，一次间接地址，多次间接地址。
Unix SystemV的分配采用了三级索引分配方式。共设置了13个索引地址项。前10个：iaddr(0)~iaddr(9)为直接地址项，iaddr(10)为一次间接地址项，iaddr(11)为二次间接地址项，iaddr(12)为三次间接地址项。
文件的储存空间管理
磁盘的划分：分为文件卷和目录区。
目录区包含文件目录、空闲表、位式图、超级快等用于文件管理的数据。
空闲表法
空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块号等信息，再将所有空闲区按其起始盘块号递增排列。
空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法，循环首次适应算法等。
空闲链表法
空闲链表法是将所有空闲盘区拉成一条空闲链。把链表分成两种形式，空闲盘块链和空闲盘区链。
位式图法
利用二进制的一位表示磁盘中的一个盘块的使用情况，当其值为0时，表示对应的盘块空闲，为1时，表示已经分配，磁盘上的所有盘块都有一个二进制位与之对应。由所有盘块所对应的位构成一个集合，称为位示图，通常可用m×n个位数来构成位示图，并使m×n等于磁盘的总块数。
优点：由于位示图很小，占用空间少，因而可将其保存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，节省磁盘启动时间。
磁盘
磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。
磁盘结构
- 盘面（Platter）：一个磁盘有多个盘面；
- 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
- 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
- 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
- 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
- 主轴（Spindle）：使整个盘面转动。
磁盘调度算法
读写一个磁盘块的时间的影响因素有：
- 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
- 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
- 实际的数据传输时间
其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。
先来先服务
FCFS, First Come First Served
按照磁盘请求的顺序进行调度。
优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。
最短寻道时间优先
SSTF, Shortest Seek Time First
优先调度与当前磁头所在磁道距离最近的磁道。
虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。
电梯算法
SCAN
电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。
电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。
因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。
转载地址：http://txgmi.baihongyu.com/