文件管理

概念

文件是指创建者所定义的，具有文件名的一组数据的集合，可分为有结构文件和无结构文件两种

在有结构的文件中，文件由若干个相关记录组成，而无结构文件则被看成一个字符流

文件属性包括：

• 文件类型，可以从不同的角度来对规定文件的类型
• 文件长度，文件长度指文件的当前长度
• 文件的物理位置，通常用于指示文件所在的设备以及设备中地址的指针
• 文件的建立时间，指最后一次修改时间等

文件的逻辑结构

流式文件：无结构的文件，数据不再组成记录，只是一串顺序的信息集合

有结构文件：由一组相似的记录组成，又称记录式文件，每条记录由若干个数据项组成，一般来说，每条记录有一个数据项作为关键字，根据各条记录的长度是否相等，又可分为定长记录和可变长记录

顺序文件

文件的记录按一个接一个顺序排列，记录可以是定长的或可变长的，各个记录在物理上可以顺序存储或链式存储

顺序存储：逻辑上相邻的记录物理上也相邻

链式存储：逻辑上相邻的记录物理上不一定相邻

定长记录可以随机存取，可变长记录不可以随机存取

索引文件

对于可变长记录文件，要找到第i个记录，必须先顺序查找到前i-1个记录，很不方便

如果建立一张索引表加快文件的检索速度，每条记录对应一个索引项

索引表本身就是定长记录的顺序文件，因此可以迅速找到第i个记录对应的索引项

由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场所

缺点：每个记录对应一个索引表项，因此索引表可能会很大

索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合，在索引顺序文件中，同样会为文件建立一张索引表，但是，并不是每个记录都对应一个索引表项，而是一组记录对应一个索引表项

为了进一步提高检索效率，可以为顺序文件建立多级索引表

文件目录

文件控制块

目录本身就是一种有结构文件，由一条条记录组成，每条记录对应一个放在该目录下的文件

为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为文件控制块(FCB)

FCB中包含了文件的基本信息(文件名，文件大小，物理地址，逻辑结构等)，存储控制信息，使用信息

每当创建一个文件时，先建立一个FCB，用来记录文件属性，每当存取文件时，先找到FCB，再找到文件信息盘块号或索引表就能存取文件

为了加快文件查找速度，将FCB汇集和组织在一起形成文件目录

目录结构

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项

优点：

• 单级目录实现了按名存取

缺点：

• 但是不允许文件重名，显然单级目录结构不适用于多用户操作系统

两级目录结构

早起的多用户操作系统，采用两级目录机构，分为主文件目录和用户文件目录

主文件目录记录用户名及相应的用户文件目录的存放位置

用户文件目录由该用户的文件FCB组成

优点：

• 两级目录结构允许不同用户的文件重名，也可以在目录上实现访问限制

缺点：

• 但是两级目录结构依然缺乏灵活性，也不能对自己的文件进行分类

多级目录结构

用户要访问某个文件时要用文件路径名标识文件，文件路径是个字符串，各级目录之间用 / 隔开，从根目录出发的路径称为绝对路径

系统根据绝对路径一层一层地找到下一级目录。从外存读入根目录的目录表

每次从根目录找很低效，可以设置相对目录，减少磁盘I/O次数

优点：

• 树形目录可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。

缺点

• 树形结构不便于实现文件的共享。为此，提出了无环图目录结构

无环图目录结构

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，可以更方便地实现多个用户间的文件共享

需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享这个结点，用户提出删除结点的请求时，只是删除该用户的FCB，并将共享计数器减1，并不会删除共享结点，只有共享计数器为0时才被删除

索引结点

索引结点是对FCB的优化，在查找各级目录的过程只需要文件名这个信息，只有文件名匹配的时候，才需要读出文件的其他信息

可以将除了文件之外的描述信息都放到索引结点，减少了IO次数

文件的物理结构

类似内存分页，磁盘中的储存单元也会被分为一个个块，很多操作系统中，磁盘块的大小与内存块，页面的大小相同

在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件块，于是文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式

用户通过逻辑地址操作自己的文件，操作系统负责实现从逻辑地址到物理地址的映射

连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块

文件目录中记录存放的起始块号和长度

用户给出了要访问的逻辑块号，操作系统找到该文件对应的目录项(FCB)

物理块号=起始块号+逻辑块号

优点：

• 连续分配支持顺序访问和随机访问

• 在读取某个磁盘块时，需要移动磁头，访问的两个磁盘块相隔越远，移动磁头所需时间就越长，所以，连续分配的文件在顺序读写时速度最快

缺点：

• 连续分配方式的文件不方便扩展
• 物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片

链接分配

隐式链接

除了文件的最后一个磁盘块，每个磁盘块都会保存指向下一个盘块的指针，这些指针对用户是透明的

在目录中记录了文件的起始块号和结束块号

从目录项中找到起始块号，将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，再找到2号逻辑块存放位置，以此类推

因此，读入i号逻辑块，总共需要i+1次磁盘I/O

优点：很方便文件拓展，不会有碎片问题，外存利用率高

缺点：采用链式分配方式的文件，只支持顺序访问，不支持随机访问，查找效率低

显式链接(FAT)

把用于链接文件各物理块的指针显示地存放在一张表中，即文件分配表(FAT，File Allocation Table)

在目录中只需记录文件的起始块号

在FAT中，记录每个物理块号对应的下一块，如果物理块号是文件的末尾，可以记为-1

一个磁盘仅设置一张FAT，开机时，将FAT读入内存，并常驻内存，FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此，物理块号字段可以是隐含的

逻辑块号转换成物理块号的过程不需要读磁盘操作

优点：采用显式链式分配的文件，支持顺序访问，也支持随机访问，由于块号转换不需要访问磁盘，因此相比于隐式链接来说，访问速度要快，也不会产生外部碎片，方便扩展

缺点：文件分配表需要占据一定空间

索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块，索引块存放的磁盘块称为索引块，文件数据存放的磁盘块称为物理块

在索引块中存放的是索引表

在显式链接中，文件分配表FAT是一张磁盘对应一张，而索引分配方式中，索引表是一个文件对应一张

可以用固定长度表示物理块号，因此，索引表中的逻辑块号可以是隐含的

将索引表从外存读入内存，并查找索引表即可知道i号逻辑块在外存中的存放位置，可见，索引分配方式支持随机访问，也支持文件拓展

如果整张索引表的大小超过了一个磁盘块，该如何解决？

链接方案

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放

但是，如果索引表过大，那么所要链接的索引块也就很多，如果要找最后一个索引块，那么必须先顺序地读入前面所有索引块，很低效

多层索引

建立多层索引，事第一层索引块指向第二层索引块，还可根据文件的大小要求再建立第三层，第四层索引块

如果使用两层索引，则文件的最大长度可以达到256*256=64MB

缺点是，即使是小文件，访问一个数据块依然需要k+1次读磁盘

混合索引

多种索引分配方式的结合，例如，一个文件的顶级索引表中，既包含直接地址索引，又包含一级间接索引，还包含两级间接索引

总结

文件存储空间管理

存储空间的划分：将物理磁盘划分为一个个文件卷

存储空间的初始化：将各个文件卷划分为目录区，文件区

目录区主要存放文件目录信息，用于磁盘存储空间管理的信息

文件区用于存放文件数据

空闲表法

用一张表来记录空闲盘块和空闲盘块数，适用于连续分配方式

分配磁盘：与内存管理中的动态分区分配类似，为一个分配连续的存储空间，同样可采用首次适应，最佳适应，最坏适应等算法决定为文件分配哪个区间

回收磁盘：和动态分区分配一样，需要考虑到不同情况

空闲链表法

空闲盘块链

空闲盘块中存储着下一个空闲盘块的指针

操作系统保存着链头和链尾指针

分配：若某文件申请K个盘块，则从链头开始一次摘下K个盘块分配，并修改空闲链的链头指针

回收：回收的盘快挂到链尾，并修改空闲链的链尾指针

适用于离散分配的物理结构

空闲盘区链

连续的空闲盘块组成一个空闲盘区

空闲盘区中第一个盘块记录了盘区的长度，下一个盘块的指针

分配：若某个文件申请K个盘块，则可以开始采用适应算法，从链头开始检索，找到一个大小符合要求的空闲盘区，如果没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件

回收：如果回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾

离散分配，连续分配都适用，为一个文件分配多个磁盘块时效率高

位示图法

每个二进制对应一个盘块，比如0代表盘块空闲，1代表盘块已分配，位移图一般用连续的字来表示

分配：若文件需要K个块，先顺序扫描位示图，找到K个相邻或不相邻的0，根据字号，位号算出对应的盘块号，将相应盘块分配给文件，将相应位设置为1

回收：根据回收的盘块号计算出相应的字号，位号，将相应二进制设为0

要根据矩阵推算出位示图和盘块号的转化关系

此外，在文件的显式分配中所使用的FAT表，由于标记了磁盘中各块的被使用情况，一样可以用在空闲空间的管理中

文件的基本操作

创建文件

创建文件需要进行Create系统调用，需要提供的几个主要参数

1. 所需的外存大小
2. 文件存放路径
3. 文件名

在处理系统调用时，主要有两步

1. 在外存中找到文件所需的空间
2. 根据文件存放路径的信息找到该目录对应的目录文件，在目录文件创建该文件对应的目录项

删除文件

通过Delete系统调用

处理系统调用时，主要有三步

1. 根据文件存放路径，找到文件名对应的目录项
2. 根据目录项记录的文件位置，回收文件占用的磁盘块
3. 从目录项中删除文件对应的目录项

打开文件

通过open系统调用

需要提供的主要参数

1. 文件存放路径
2. 文件名
3. 要对文件的操作类型

操作系统在处理open系统调用时，主要做了：

1. 根据文件存放路径找到文件名对应的目录项，并检查该文件是否有指定的操作权限
2. 将目录项复制到内存中的打开文件表，并将对应的目的编号返回给用户，之后用户使用打开文件表的编号来指明要操作的文件

之后用户进程A再操作文件就不需要每次都重新检查目录了，这样可以加快文件访问速度

进程的打开文件表中，读写指针记录了该进程对文件读写所进行到的位置

访问权限标明了进程能对文件所进行的操作

系统表索引号指向了系统的打开文件表

打开文件时并不会把文件数据直接读入内存，索引号也称文件描述符

关闭文件

系统在处理close系统调用时

1. 将进程的打开文件表相应表项删除
2. 回收分配给该文件的内存空间等资源
3. 系统打开文件表的打开计数器count减1

读文件与写文件

进程在使用read系统调用时，需要的主要参数是

1. 指明是哪个文件(编号)
2. 还需要指明要读入多少数据
3. 读入的数据要放在内存中的什么位置

在写文件时，需要的主要参数是

1. 指明是哪个文件(编号)
2. 还需要指明要写出多少数据
3. 写出的数据要放在内存中的什么位置

文件共享

基于索引结点的共享方式(硬链接)

在索引结点中设置一个链接计数变量count，用于表示链接本索引结点上的用户目录项数

特性：

• 不能交叉文件系统进行硬链接的创建
• 不能对目录进行创建，只能对文件创建
• 删除一个硬链接文件不影响其他有相同inode号的文件，才有单级目录结构

基于符号链的共享方式(软链接)

概念：符号链接又叫软链接，和原文件不是一个文件，例如Windows的快捷方式，如果原始文件被删除，所有指向它的符号链接也就都被破坏了。

软链接有自己的inode，是Linux特殊文件的一种，作为一个文件，它的数据是它所连接的文件的路径。符号链接可以跨越文件系统，也可以为目录建立

操作系统根据路径一层层打开查找目录，最终找到共享文件，即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败

文件保护

口令保护

口令一般存放在文件对应的FCB或索引结点中，用户访问文件需要先输入口令，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确就允许访问

优点：保存口令的空间开销不多，验证口令的时间开销也很小

缺点：存放在系统内部不安全

加密保护

使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密

优点：保密性强，不需要在系统中存储密码

缺点：加密和解密要花费一定时间

访问控制表

在每个文件的FCB中增加一个访问控制列表，该表中记录了各个用户可以对该文件执行哪些操作

文件系统的全局结构

外存结构

磁盘初始化

1. 进行物理格式化，将磁盘的各个磁道划分为扇区

   

2. 将磁盘分区，每个分区由若干个柱面组成

3. 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录，初始化存储空间管理所用的数据结构

   

引导块是负责初始化操作系统(PBR→MBR)

超级块可以迅速找到磁盘中的空间块

结点区是集中存放索引结点的区

内存结构

近期访问过的目录文件会缓存在内存中，不用每次都从磁盘读入，这样可以加快目录检索速度

打开文件的步骤：

1. 根据路径读入目录
2. 找到文件的FCB，复制到系统打开文件表
3. 在进程打开文件表中新建一个条目，并返回文件描述符

虚拟文件系统

概念

操作系统中可以有多个不同的文件系统，所以需要一个虚拟的文件系统来协调各个不同的文件系统

特点

1. 向上层用户进程提供同一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
2. VFS要求下层的文件系统必须实现某些规定的函数，一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求
3. 每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统

不同的文件系统目录项都不一样，在虚拟文件系统中，统一用vnode表示，vnode只存在于主存中，而inode既会被调入主存，也会在外存中存储

文件系统的挂载

即将一个文件系统挂载到操作系统的虚拟操作系统上

1. 在VFS中注册新挂载的文件系统。内存中的挂载表包含每个文件系统的相关信息，包括文件系统类型，容量大小等
2. 新挂载的文件系统，要向VFS提供一个函数地址列表(即文件系统的基本函数(如open)的地址)
3. 将新文件系统加到挂载点，也就是将新文件系统挂载到某个父目录下

固态硬盘(SSD)

SSD基于闪存技术，属于电可擦除ROM，即EEPROM

结构

闪存翻译层：负责翻译逻辑块号，找到对应页

存储介质：多个闪存芯片，每个芯片代表多个块，每个块代表多个页

读写性能

• 以页为单位读写
• 以块为单位擦除，其中每页都可以写一次，读无限次，在擦除的时候会将块内除要擦除数据之外的数据，移动到空闲块中，然后将原来的块进行擦除，同时闪存翻译层修改逻辑块号的映射
• 支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址

特点

• 读写速度快，随机访问性能高，用电路控制访问位置

• 安静无噪音，耐摔抗震，能耗低，造价贵

• SSD的一个块被擦除次数过多可能会坏掉，而机械硬板的扇区不会因为写的次数太多而坏掉

磨损均衡技术

将擦除平均到各个块上，以提升使用寿命

动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块

静态磨损均衡：SSD监测并自动进行数据分配，迁移，让老旧的闪存块承担以读为主的存储任务，让新闪存块承担更多的写任务