操作系统03：文件系统

本文转载于操作系统笔记 - 知乎 (zhihu.com)，本人在原作者的基础上进行了格式上的整理和部分内容的补充，仅供个人学习所用，如果涉及到任何版权行为，请联系我予以删除。3.1 文件系统概述3.1.1 文件概念

（1） 什么是文件

文件是在逻辑上具有完整意义的信息集合，它有一个名字以供标识，文件名是以字母开头的字母数字串。

（2）构成文件的基本单位

记录

（3）文件分类

（1）按用途分类：系统文件； 库文件； 用户文件

（2）按保护方式分类：只执行文件；只读文件；读写文件

（3）按文件存放的内容：unix

3.1.2 文件系统

（1）文件系统概念：

是指文件和对文件进行操纵和管理的软件集合及相关数据结构，它是由管理文件所需的数据结构和相应的管理软件以及访问文件的一组操作组成。

（2）文件系统功能：

（1）从用户的角度看：文件系统实现了“按名存取”的功能

（2）从系统的角度看：

（3）文件系统模型：层次模型

（1）对象及其属性

文件系统管理的对象有：

文件。它作为文件管理的直接对象。目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。文件存储空间。如磁盘、光盘等。文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。

（2）对对象操纵和管理的软件集合

这是文件管理系统的核心部分。功能包括：

（3）文件系统的接口

为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口：

① 命令接口：这是用户与文件系统交互的接口。 用户可通过键盘终端键入命令，取得文件系统的服务。

② 程序接口：这是用户程序与文件系统的接口。 用户程序可通过系统调用来取得文件系统的服务。

3.2 文件的物理结构3.2.1 连续文件

将逻辑文件中的信息顺序存储到连续的物理盘块中。

如下是外存中的物理盘块的分布图：

这是我们文件的目录：

在文件目录中，有两个属性的信息：文件名和物理地址（在外存中存放的位置）。

主要优点：

主要缺点：

3.2.2 串联文件

利用指针将文件所占的盘块连接起来。

（1）串联文件结构（隐式链接）

串联文件的缺点：

（2）文件映照结构（显式链接）

所有链接指针统一存放在一张显示的链接表(fat表：文件分配表)中。一个逻辑磁盘设置一张表，以物理盘块号为序，表项内容为指向某文件的下一盘块的指针。

例：若文件f1占据了2，4，5，1四个盘块：

FAT文件系统磁盘组织结构：

FAT1 和 FAT2 是互为备份的连个相同的文件。

FAT32引导区主要内容有：

串联文件性能评价

1.存储空间利用率高；没有文件存储空间碎片的问题了。

2.文件创建时用户不必指出文件的大小；采用指针的形式。

3.文件动态扩充和修改容易。采用指针的形式。

4.顺序存取效率高，随机存取效率较低。

FAT 表大小的计算方法

例：一个磁盘分区大小为20GB，若盘块大小为1KB，计算该磁盘分区的FAT表大小？

盘块数=20GB/1KB =20MB≈2^25B，所有至少需要25个二进制位。由于每个FAT的表项可以是半个整数倍，所以25位最少取3.5个字节。所以FAT表大小=20MB×3.5B=70MB

3.2.3 索引文件

（1）什么是索引文件

索引表：系统为每个文件建立的逻辑块号与物理块号的对照表。

如对应的文件 file1 分配到4个磁盘块：

其所构建的索引表对应的结构就是：

索引块：存放文件的索引表的物理块，其块号保存在文件目录项的物理地址中；

文件由数据文件和索引表构成。这种文件称为索引文件。

单级索引分配

就如上例所示的样子

多级索引分配

文件file2分配到1000个磁盘块：2，3，5，20，22，25，…1200，1511，若每个盘块号占4B，每个盘块1KB：

由于每个盘块只有1KB，所以最多存放的盘块号是 1KB/4B = 256个。不能存放1000个盘块号，所以需要分组，分为四个部分。为了找到刚才建立的索引块，所以我们需要建立一个二级索引来记录以及索引所占的盘块号。最好，我们需要在文件目录中记录二级索引表所占的盘块号。

混合索引分配

Unix：i 节点中的物理地址字段 iaddr(13)

iaddr(0) ～iaddr(9): 直接地址；

Iaddr(10)：一级索引；

iaddr(11): 二级索引；

iaddr(12): 三级索引。

例：设某文件长度为xB，若盘块大小为4KB，每个盘块号4B，则:

（1）文件盘块数量为： n=[x/4k] + 1

（2）每个索引块能存放的盘块号数量：=4K/4 =1K(个)

对 n 进行分类：

(1)n≤10：

所有数据块号全部存放在iaddr(0) ～iaddr(9)中：

(2)10＜n≤1034：

前面10个数据块号全部存放在iaddr(0) ～iaddr(9)中；

剩下的不超过1024个数据块号放在一个一级索引块中；

并将该一级索引块号存入iaddr(10)中：

(3)1034＜n≤1034+1M：

前面10个数据块号全部存放在iaddr(0) ～iaddr(9)中；

剩下的不超过1024+1M个数据块号放在不超过1025个一级索引块

将第一个一级索引块号存入iaddr(10)中；

将剩下的不超过1024个一级索引块号存入一个二级索引块中；

最后将该二级索引块号存入iaddr(11)中：

（4)1034+1M＜n≤1034+1M+1G：

前面10个数据块号全部存放在iaddr(0) ～iaddr(9)中；

剩下的不超过1024+1M+1G个数据块号放在不超过1025+1M个一级索引块中；

将第一个一级索引块号存入iaddr(10)中；

剩下的不超过1024+1M个一级索引块号存入≤1025个二级索引块中；

再将第一个二级索引块存入iaddr(11)中；

剩下的不超过1024个二级索引块号存入一个三级索引块中；

最后将该三级索引块块号存入iaddr(12)中：

3.2.4 文件物理结构的比较3.3 文件存储空间的管理3.3.1 空闲文件目录

适合连续文件

3.3.2 空闲块链表法

3.3.3 位示图法：Linux

位示图概念：

二进制位位0表示该盘块空闲，为1表示已经分配出去了。

盘块的分配 ：i，j，b从1开始计数

(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。

(2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示图的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j

式中， n代表每行的位数，i，j，b从1开始计数。

(3) 修改位示图， 令 map［i,j］=1。

盘块的回收 ： i，j，b从1开始计数

(1) 将回收盘块的盘块号b转换成位示图中的行号i和列号j。 转换公式为：

i=(b-1) DIV n + 1 // 取商

j=(b-1) MOD n + 1 // 取余

(2) 修改位示图。 令map ［i,j］=0。

3.3.4 成组链接法：Unix

空闲盘块的组织

（1）对所有空闲盘块分组：

若8# ～ 499#空闲unix文件系统，每组100块，从后往前分组，则分组情况是：

最末组为99块：499～401；

其余每组100块，分别为： 400～301； 300～201； 200～101； 100～8.

（2）空闲盘块的链接：

①将每组（第1组除外）的总块数及相应的块号记录在前一组的最末块中：

② 对第1组，其总块数和各块块号记录在空闲盘块栈中，放在超级块里。

系统启动后，将超级块复制到主存中，并建立空闲盘块号栈，栈顶指针S_Free=第1组总块数。

空闲盘块的分配 : 针对空闲盘块栈进行。

count=当前组空闲盘块总数；
S_free--；
b=*S_free;
if (count＞1）then
{  
    count--;
    return b;
}
else if (count==1)then
{  
    if (b==0)then   // 是最后一个分组了，没有空前盘块了
	拒绝分配，返回0；  
    else
    { 
        将b中内容读入空闲盘块栈；  //读入下一个分组
        count=当前组空闲盘块总数；
	S_free=count；
	return b;
    }
}

空闲盘块的回收: 针对空闲盘块栈进行。

count=当前组空闲盘块总数；
b:回收块号；（如回收50、60号块）
if（count＜100) then
{   
    *S_Free=b;
    count++;
    S_Free++;
    return;   
}
else if( count==100) then
{   
    将空闲盘块栈内容写入b中；
    count=1；
    S_free=0；
    *S_Free=b;
    S_Free++;
    return;   
}

3.4 文件目录管理3.4.1 文件目录相关概念

对目录管理的要求

(1) 实现“按名存取”。

(2) 提高对目录的检索速度。

(3) 文件共享。

(4) 允许文件重名。

什么是文件目录

文件目录是由一组文件目录项组成的。每个目录项是记录某个文件的名字、存放地址及其他有关文件的说明信息和控制信息的数据结构。

文件控制块FCB（或文件目录项）的内容

文件与FCB一一对应，是 文件存在的唯一标志。

（1）基本信息类 ：

① 文件名 ；

② 文件物理地址 ：

连续文件： 起始块号、块数

串联文件： 起始块号

索引文件： 索引表首址

③ 文件逻辑结构 ；

④ 用户名：

文件主、同组用户、用户组等

⑤ 文件长度；

⑥ 文件类型；

(2) 存取控制信息类

文件主的权限；核准用户的权限；一般用户的权限。

(3) 使用信息类 ：

① 文件建立日期及时间；

② 文件最近访问日期及时间；

③ 文件最近修改日期及时间；

④ 文件链接计数。

举例： MS-DOS的文件控制块：FAT16

其具体的位的含义如下：

属性

时间：最近修改时间

日期：最近修改日期

索引结点（i节点）

引入 i 节点的目的是为了提高目录检索的效率。

（1） 索引结点的引入

FCB：文件名 、物理地址、用户名、长度、类型、存取控制权限、时间、共享信息

符号目录项：

基本目录项：

传统unix目录项：

Unix S5fs目录项：

（2）Unix S5FS 文件系统的磁盘布局：

超级块：

3.4.2 目录结构

单级目录结构 ： 整个文件系统只建立一张目录表。

优点：

缺点：

树型文件目录

(1) 什么是树型文件目录

在多级目录系统中 (除最末一级外)，任何一级目录的目录项可以描述一个目录文件，也可以描述一个非目录文件 (数据文件)，而数据文件一定在树叶上。这样，就构成了一个树形层次结构。

(2)树型文件目录结构

(3)文件路径名

绝对路径： 根目录/子目录名…/文件名

相对路径： 当前目录/子目录名…/文件名

(4) 树形文件目录的优点：

(5)目录查询技术：线性检索

例：/usr/ast/mbox

首先在根目录中对 usr 进行文件名的匹配。其对应的是6号i节点（索引节点）。根据6号i节点，我们知道这个子目录存在在132块，也就是文件的物理地址。

然后进入132块，进入 usr 的子目录中查找 ast 这个文件名。同理进入 ast 目录 查找 mbox 文件。通过60号索引节点查找到其对应的物理磁盘块号。

3.5 文件的共享和保护3.5.1 文件共享

是指某一个或某一部分文件可以让事先规定的某些用户共同使用。

文件索引节点法

假设B用户想使用“/B/B1/B12”文件名访问共享文件C21。

但是这种的链接方式会造成当一个目录删除文件C21的时候，导致另一个目录也不能检索到给文件，因为C21在之前的目录索引删除过程中已经被删除了，15号索引节点已经为空。如下图：

所以，为了解决这个问题，我们引入了一个链接计数器 count 。表示有 count 个用户正在访问该共享文件。当一个用户想要删除该文件时不能直接将C21文件删除。

在Linux中共享索引节点法又称为硬链接。

ln 共享文件名  新文件名
ln /C/C2/C21  /B/B1/B12

符号链接法：

为共享文件创建一个link类型的新文件：如/B/B1/B12

（1）分配并填写一个空闲i节点；

（2）建立目录项；

（3）分配磁盘空间；

（4）写入文件内容：共享文件的路径名:/C/C2/C21

Linux：

ln –s 共享文件名  新文件名
ln –s /C/C2/C21  /B/B1/B12

硬链接与符号链接的区别：

$ ls –il   // i 表示显示索引节点， l 表示显示长格式显示
13058  -rwxrwx - - -   1     zwh  zwh  48  9月 5 16:38    file1
13059  -rwx rwx- - -   1     zwh  zwh  57  9月 5 16:40    file2

文件属性：

文件类型：

（1）- ：普通文件；

（2）d ：目录文件；

（3）l ：符号链接文件；

（4）c ：字符设备文件；

（5）b ：块设备文件；

（6）s ：socket文件；

（7）p ：管道文件；

$ ls –il
 13058  -rwxrwx - - -   1     zwh  zwh  48  9月 5 16:38    file1
 13059  -rwx rwx- - -   1     zwh  zwh  57  9月 5 16:40    file2
 $ ln file2 file2hard    // 文件索引节点法
 $ ls –il 
 13058  -rwxrwx - - -   1   zwh  zwh  48  9月 5 16:38    file1
 13059  -rwxrwx - - -   2   zwh  zwh  57  9月 5 16:40    file2
 13059  -rwxrwx - - -   2   zwh  zwh  57 9月 5 16:40  file2hard

应为是使用的硬节点方式，所以他们指向的共同的一个索引节点，于是他们的索引节点编号是一样的。

$ ln –s file1 file1soft   // 符号链接法
$ ls –il
13058  -rwxrwx - - -   1   zwh  zwh  48  9月 5 16:38    file1
13059  -rwxrwx - - -   2   zwh  zwh  57  9月 5 16:40    file2
13059  -rwxrwx - - -   2   zwh  zwh  57  9月 5 16:40    file2hard
13061  lrwxrwxrwx      1   zwh  zwh   5  9月 5 16:58    file1soft->file1
// 符号链接文件， 链接计数仍为1 ，文件也明显比原来的文件小。

用符号链接法创建的只是一个能够找到目标文件的一个路径，所以明显比目标文件大小要小。

$ rm file2hard   // 删除刚才创建的硬链接文件
$ ls –il
13058  -rwxrwx - - -   1   zwh  zwh  48  9月 5 16:38    file1
13059  -rwxrwx - - -   1   zwh  zwh  57  9月 5 16:40    file2  // 链接数又变为1
13061  lrwxrwxrwx      1   zwh  zwh   5  9月 5 16:58    file1soft->file1

硬链接和符号链接总结：

（1）索引节点：

（2）在文件属性上：

（3）链接计数不一样：

（4）文件大小不一样：

（5）硬链接不能跨越文件卷建立链接，不能给目录创建硬链接；而符号链接可以。

（6）符号链接要建立新的符号链接文件，共享开销大。

3.5.2 文件保护

造成文件被破坏的原因：

提高系统可靠性

（1）备份技术：

① 周期性转储

按固定的时间周期把存储器中所有文件的内容转存到某种介质上，通常是磁带或磁盘。在系统失效时，使用这些转存磁盘或磁带，将所有文件重新建立并恢复到最后一次转存时的状态。

② 增量性转储

这种技术转储的只是从上次转储以后已经改变过的信息；增量转储的信息量较小，故转储可在更短的时间周期内进行。

（2）磁盘容错技术

① 第一级容错技术SFT-Ⅰ ：主要用于防止因磁盘部分缺陷所造成的数据丢失。

② 第二级容错技术SFT-Ⅱ ：主要用于防止因磁盘驱动器和磁盘控制器故障所造成的文件破坏。

提高系统安全性

是指文件本身不得被未经文件主授权的任何用户存取，而对于授权用户也只能在允许的存取权限内使用文件。

手段：权限验证

（1）访问矩阵： 描述系统存取控制权限的矩阵

行：代表用户（组）；

列：代表对象：软硬件资源；

值：权限

（2）访问控制表：为文件设置存取控制属性

对访问矩阵按列（对象）进行划分，每一列建立一张访问控制表。

比如对于刚才建立的F1这一列，可以建立访问控制表如下：

对于F2列可以建立：

（3）访问权限表 ：为用户设置权限

对访问矩阵按行进行划分，每一行建立一张访问权限表。

对于D1用户，可以列出其可操作性的对象，建立其访问权限表如下：

对于D2用户：

3.6 文件操作3.6.1 常用的文件操作命令

create	 //创建一个新文件
delete	 //从系统目录中撤消一个文件
rename	 //在系统目录中改变文件的名字
open	 //打开文件
         //在用户和文件(或设备)之间建立一个逻辑通路
close	 //关闭文件
         //在用户和文件(或设备)之间撤消一个逻辑通路
write	 //写到一个文件(或设备)上
read	 //从一个文件(或设备)读入数据信息

在创建文件时需要为新文件创建一个必要的内存空间，并在文件目录中建立一个文件目录项，在目录项中记录新文件的文件名和其在外存中的地址等属性。

对于删除文件，需要在在目录中找到删除文件的目录项，使其成为空项，然后回收改文件所占的存储空间。

读文件时需要根据给出的文件名查找目录，从中得到被读文件在外存中的位置。

写文件时需要根据指针去查找目录，找到对应的目录项，再根据目录项中的写指针进行操作。

3.6.2 “打开文件”和“关闭文件”操作操作

① 打开文件操作

所谓打开文件就是把该文件的有关目录表目复制到主存中约定的区域，建立文件控制块，建立用户和这个文件的联系。

② 关闭文件操作

所谓关闭文件就是用户宣布这个文件当前不再使用，系统将其在主存中的文件控制块删去，因而也就切断了用户同这个文件的联系。

3.7 磁盘管理3.7.1 数据的组织和格式

基本概念

存储容量

= 磁头数×磁道（柱面）数×每道扇区数 ×每扇区字节数

扇区编址方式

LBA（相对扇区号）方式：

LBA扇区号与（柱面号、磁头号、扇区号）间的转换

3.7.2 磁盘的类型

按照磁头是否需要移动进行分类：

固定头磁盘移动头磁盘

固定头磁盘

对于同一盘面上的不同磁道我们都有相应位置固定的磁头进行读写，如上图中的黑色磁头和蓝色磁头分别读取一个磁道，对多条磁道进行读写的时候，磁头不需要移动位置。所以对于一个盘面上的多条磁道可以并行进行读取，访问速度较快。同样价格也较高。

移动头磁盘

对于移动头磁盘，它的磁头是可以沿着径向臂进行径向移动，所以只需要使用一个磁头就可以访问所有的磁道。但是同一时间只能访问一个磁道，只能实现顺序读写，读写速度较慢，但是造价较低。计算机中使用的磁盘大多数都是移动头磁盘。

3.7.3 磁盘访问时间

以移动头磁盘为例

寻道时间Ts ：把磁头移动到指定磁道上所经历的时间。

T_s=m×n +s

m：一般磁盘：0.2～0.3；高速磁盘：m≤0.1

s：磁臂启动时间，约为2ms～ 3ms

磁盘读写操作中绝大部分时间都是寻道时间，所以对寻道时间进行优化可以有效的大幅减少访问时间。

旋转延迟时间Tr ：指定扇区移动到磁头下面所经历的时间。

也就是要读取的蓝色扇区移动到我们的黑色磁头下面所要经历的时间。所以旋转延迟时间最长为 \frac{1}{r} ，最短为 0。平均旋转延迟时间为 T_r = \frac{1}{2r} 。（r 表示转速）

传输时间Tt

把数据从磁盘读出或向磁盘写入数据所经历的时间。

T_t = \frac{b}{rN} （b 表示要读写的字节数，N 表示一条磁道上总的字节数 ）

因此， 可将磁盘访问时间 Ta 表示为：

T_a = T_s + \frac{1}{2r} + \frac{b}{rN}

3.7.4 磁盘调度

当有大量磁盘I/O请求时，恰当选择调度顺序，以降低完成这些I/O服务的总时间。

磁盘调度方式主要有以下两种：

由于旋转调度算法较为简单，只是按照扇区距离磁头的位置的偏差来进行调度。所以下面将以移臂调度为讲解。

3.7.5 移臂调度算法

先来先服务FCFS(First-Come, First Served)

假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：23，376， 205，132， 61， 190， 29， 4， 40。

则磁盘调度顺序和寻道距离为：

23，376， 205，132， 61， 190， 29， 4， 40

Ts = (100-23) + (376-23) + (376-205) + (205-132) + ... + (40-4)

平均寻道距离 = Ts / 9 。

由于先来新服务算法并没有对磁盘访问进行优化，所以它可能会得到比较长的寻道距离。

最短寻道时间优先算法SSTF

在选择下一条磁道的时候总是访问与当前磁盘距离最近的磁盘进行访问。

对于上例，其磁盘调度顺序和寻道距离为：

132 , 190, 205, 61, 40, 29, 23, 4, 376

Ts = (132-100) + (190-132) + (205-190) + ... + (23-4) + (376-4)

最短寻道距离优先可以保障每一次的寻道距离最短，但是不能够保障最后系统得到的平均寻道距离最短。如最后 4 到 376 的磁盘寻道跨度就非常大。

它也存在着一下几个问题：

扫描(SCAN)算法（又称为电梯算法）

它是目前操作系统中用的比较广泛的一种磁盘移臂调度算法。

（编辑：源码门户网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!