文件管理

文件逻辑结构

逻辑结构：在用户看来，文件内部数据是如何组织起来的，并且用户使用逻辑结构操纵文件数据

物理结构：在操作系统看来，文件的数据是如何存放到外存中的，操作系统负责组织文件数据真实结构

无结构文件

文件内部的数据就是一系列的二进制或字符流组成，又称流式文件

顺序文件

文件中的记录从逻辑上看，顺序排列，记录可以是定长也可以不定长，各个记录在物理上可以顺序存储或者链式存储

链式存储

无论是定长还是可变长都不能实现随机存取，只能从第一个记录开始依次向后寻找

顺序存储

对于可变长记录：

无法实现随机存取，只能从第一个记录开始向后查找
需要显式给出记录长度

对于定长记录：

可实现随机存取
若采用串结构，无法快速找到某关键字对应的记录
若采用顺序结构，可以快速找到某关键字对应的记录(比如二分查找)

串结构：记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序，增加、删除记录相对顺序结构简单一点

索引结构

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

索引表的本质是定长记录的顺序文件，因此可以快速定位
文件的记录本身在物理上可以是离散存储的

主要用于对信息处理的及时性要求比较高的场合

每个记录对应一个索引表项，因此索引表可能会很大，降低存储空间利用率

索引顺序文件

同样为文件建立一张索引表，但不同的是，为一组记录建立一个索引表项

一个索引表内含多个分组的索引，可以让索引文件大小大大降低。

该索引表的记录不需要再进行顺序排列，极大方便了新表项的插入，

其本质是定长记录串结构的顺序文件

文件目录

文件控制块

文件控制块FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。

FCB中包含文件的基本信息：文件名、物理地址、逻辑结构、物理结构等，存取控制信息(可读/可写，访问权限)，使用信息

FCB实现了文件名和文件之间的映射

单级目录结构

实现按名存取，但不允许文件重名。

不适用于多用户操作系统

两级目录结构

分为主文件目录MFD，和用户文件目录UFD

主文件目录记录用户名和用户文件目录存放地址

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

允许不同用户的文件重名
可以在目录设置访问限制
用户无法对自己的文件进行分类

多级目录结构

又称树形目录结构，用户要访问某个文件时要用文件路径名表示文件，文件路径名是个字符串，各级目录之间用“/”隔开，从根目录出发的路径称为绝对路径

系统访问一个文件，将首先从外存读入根目录的目录表，将顺着文件路径字符串逐个寻找目标目录

显然，如果有文件被用户连续访问，可以设置一个**“当前目录”，当已经打开一个目录时，就将它作为当前目录，当用户访问某个文件时可以使用从当前目录出发的相对路径**
树形结构不便于实现文件共享

无环图目录结构

在树形目录结构的基础上，增加一些指向同一结点的有向边，使整个目录成为一个有向无环图

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(共享该目录所有数据)

需要为每个共享节点设置一个共享计数器，记录此时有多少个地方在共享节点，用户提出删除节的请求时，知识删除该用户的FCB、并使共享计数器减1，并不会直接删除共享节点。

只有共享计数器减为0时，删除节点
只要有一个用户修改了共享文件，别的用户都将看到文件数据的变化

索引结点

对传统FCB的改进，在查找各级目录的过程中，只需要用到文件名这个信息，故可将除文件名之外的所有信息存放到索引结点中，目录表项新增索引结点指针指向它。

可以加快文件检索速度

文件的物理结构

连续分配

磁盘块的大小通常设置与内存块、页面的大小相同

内存和磁盘之间的数据交换(磁盘I/O，读写操作)都是以块为单位进行的，即每次读入一块或每次写出一块。

文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式。

逻辑地址到物理地址的改变仅需转换块号，块内地址保持不变

连续分配方式要求每个文件在磁盘上占有一组连续的块，文件目录中额外记录文件存放的起始块号和长度。

物理块号=起始块号+逻辑块号，将进行越界检查
支持顺序访问与随机访问
连续分配的文件在顺序读写的时候速度最快
存储空间利用率低，会产生磁盘碎片

隐式链接

目录中新增文件起始块号和结束块号，每个磁盘块将保存指向下一个盘块的指针，指针对用户透明

访问一个逻辑块号i，将需要i+1次磁盘I/O，因为起始块号实际上是逻辑上的块号0！
只支持顺序访问，不支持随机访问
文件拓展很方便，文件利用率高，不会产生磁盘碎片

显式链接

把用于连接文件各物理块的指针显式地存放在一张表中，即文件分配表FAT

文件目录项只新增起始块号用于指出文件查询起点

一个磁盘仅有一张FAT，且在开机的时候将FAT读入内存，常驻内存

FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此物理块号字段可以隐藏
逻辑块号到物理块号的转换不需要读磁盘操作
支持顺序访问，也支持随机访问。
不会产生磁盘碎片，文件分配表将占用一定存储空间

考题中的未指明隐式/显式的链接分配方式默认为隐式链接分配

索引分配

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

根据逻辑块号i，操作系统将找到该文件对应的目录项FCB
从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知晓i逻辑块在外存中的存放位置
支持随机访问和顺序，易于文件拓展
索引表需要占用一定存储空间

若索引表大小超出磁盘块大小：

链接索引：则可将索引表切割，除最后一个索引部分，其余部分末尾用一个指针指向下一个索引部分，在FCB中，对应文件的索引块只需记录第一个索引块块号即可，这将一定程度上牺牲其随机访问的特性

多层索引：原理类似多级页表，使第一层索引块指向第二层的索引块，根据文件大小可以建立更多层的索引块，FCB中只需记录顶级索引块的块号。

采用K层索引，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

混合索引：多种索引分配方式的结合，例如一个文件的顶级索引表中，既包含直接地址索引，又包含K级间接索引(指向K层索引表)

文件存储空间管理

用什么方式记录、组织空闲块？
如何分配磁盘块
如何回收磁盘块

空闲表法

记录第一个空闲盘块号以及空闲盘块数两个表项，适用于连续分配方式，不适用大型文件系统

磁盘块的分配和内存管理的动态分区分配类似，分配连续的存储空间，同样拥有相同的算法(首次适应、最佳适应…….)

磁盘块回收：同样与内存块回收类似，注意表项的合并问题

空闲链表法

两种链法：

以盘块为单位组织成一条空闲链，空闲盘块存储着下一个空闲盘块的指针
以盘区为单位组成一条空闲链，空闲盘区的第一个盘块内记录盘区长度、下一个盘区的指针
- 连续的空闲盘块组成一个空闲盘区

操作系统保存链头、链尾指针，对于空闲盘块链：

分配：从链头开始摘取K个盘块进行分配，修改空闲链的链头指针
回收：回收的盘块依次挂到链尾，修改空闲链的链尾指针

适用于离散分配的物理结构，不适用大型文件系统

空闲盘区链：

分配：采用首次适应、最佳适应等算法，从链头开始检索，分配空间；若没有，就将不同盘区的盘块同时分配给一个文件，分配后需要修改相应的链指针、盘区大小
回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中，若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾

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

位图法

每个二进制位对应一个盘块，0代表盘块空闲，1代表盘块已分配，位图一般用连续的字表示，字中的每一位对应一个盘块，因此可以用字号，位号对应一个盘块号

字号位号(i，j)则盘块号b=ni+j

成组链接法

在文件卷的目录区，专门用一个磁盘块作为超级块，系统启动时需要将超级块读入内存，并且要保证内存与外存中的超级块数据一致

超级块中记录下一组空闲盘块数目，以及下一组空闲块的首个块号
一组空闲盘块中，首个空闲块同样记录下一组空闲盘块数目，其余记录下一组空闲块的首个块号
若已经没有下一组空闲块，此处设为某特殊值(-1等)

分配：

当分配数目小于分组中空闲盘块数，则分配掉，修改相应数据(空闲块数)
当分配数目等于分组中空闲盘块数，则将分配出去的空闲区分组数据复制到超级块中
当分配数目大于分组中空闲盘块数，则将

回收：

分组未满，插入到分组中，修改数目信息
分组已满，将超级块中的数据复制到新回收的块中，并修改超级块的内容，指向多余回收快

文件基本操作

create系统调用

delete系统调用

open系统调用

提供三个参数：

文件存放路径
文件名
对文件操作类型

操作系统做了：

根据存放路径找到文件名对应的目录项，并检查该用户是否有对应的操作权限
将目录项复制到内存中的打开文件表中，并将表目的编号返给用户，之后用户使用打开文件表的编号来指明要操作的文件
- 这样，用户之后再操作文件就不需要重新查目录，加快访问速度

整个系统也维护一张打开文件表，其记录所有被其他进程访问的文件信息，编号将用于其他进程的文件表的文件索引，并记录打开计数器，记录该文件被多少进程访问

进程的打开文件表仅记录自己访问的文件，且记录文件对应系统表的索引号

close系统调用

系统做的事：

进程的打开文件表相应表项删除
回收分配给该文件的内存空间等资源
系统打开文件表的打开计数器-1，若count=0，则删除对应表项

read系统调用

使用read系统调用完成读操作，提供参数：

open函数调用返回的文件描述符fd
读入多少数据
读入的数据放在内存中的什么位置

write系统调用

使用write系统调用完成写操作，提供参数：

open函数调用返回的文件描述符fd
写出多少数据
写回外存的数据放在内存中的什么位置

文件共享

硬链接

全称：基于索引结点的共享方式

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

若某用户要删除文件，则系统将该用户目录中与该文件对应的目录项删除，且索引结点值-1，当count=0，该文件真正意义上被删除。

软连接

全称：基于符号链的共享方式

系统将为用户创建一个Link类型的文件，记录共享文件的存放路径，类似快捷方式

若被指向的共享文件被删除，则该软连接将失效（Link文件本身不会被删除）

由于该方式访问共享文件要查询多级目录，产生多次磁盘I/O，因此访问速度较慢

文件保护

口令保护

访问文件时，必须提供口令，该口令预设在文件的FCB或索引节点中

口令空间开销少，验证时间开销也少
正确口令存放在系统内部，不够安全

加密保护

使用密码对文件加密，用户需要提供密钥对文件解密访问

保密性强，不需要在系统存储密钥
加密/解密需要较大时间开销

访问控制

FCB或索引节点增加一个访问控制列表ACL，该表中记录各个用户可以对文件执行哪些操作

访问控制列表可以进一步精简，以组为单位，标记各组用户可以对文件执行哪些操作

如：系统管理员、文件主、文件主合作伙伴、其他用户
实现灵活、可以实现复杂的文件保护功能
如果对目录进行访问权限控制，则需要对目录下的是所有文件进行相同的访问权限控制

文件系统的全局结构

文件系统在外存中的结构

物理格式化

也称低级格式化：划分扇区，检测坏扇区，并用备用扇区替换坏扇区

逻辑格式化

逻辑格式化后，将磁盘分为一个个分区Volume，从初始地址写入主引导记录MBR用于记录此案引导程序和分区表，完成各分区的文件系统初始化

每个分区都可以建立自己的文件系统，例：

文件系统在内存中的结构

开辟用户区与内核区

用户区记录文件描述符/文件句柄

内核区记录系统打开文件表和进程打开文件表，以及目录缓存(记录近期访问过的目录文件)

虚拟文件系统VFS

位于系统内核中，向下对接不同的文件系统，向上对接用户进程

向上层用户进程提供统一标准的系统调用接口(比如POSIX)，屏蔽底层具体文件系统的实现差异(比如UFS\NTFS\FAT)
要求下层的文件系统必须实现某些规定的函数功能比如：open/write/read

当打开一个文件时，VFS将在内存中新建一个V结点，包含文件名、文件大小、创建者、文件格式以及函数功能指针等信息，将文件数据复制到V结点中，实现数据结构的统一

函数功能指针指向实际文件系统向上提供的函数调用

文件系统挂载

在VFS中注册新挂载的文件系统，内存中的挂载表包含每个文件系统的相关信息，包括系统类型、容量大小
新挂载的文件系统，向VFS提供一个函数地址列表
将新文件系统加到挂载点，也就是挂载到某个父目录下

磁盘结构

盘面被等分为若干个同心圆圈，即磁道，磁道又被划分为若干个扇区，即磁盘块，存放的数据量相同

最内侧磁道扇区面积最小，数据密度最大

一个盘片可能有两个盘面，每个盘面对应一个磁头，磁头共进退，所有盘面中相对位置相同的磁道组成柱面

可用(柱面号、盘面号、扇区号)来定位任意一个磁盘块

根据柱面号移动磁臂，让磁头指向指定柱面
激活指定盘面对应的磁头
磁盘旋转的过程中，指定扇区从磁头下面划过，完成读/写

磁盘调度算法

寻道时间T_s：在读/写数据前，将磁头移动到指定磁道所花的时间

启动磁头臂时间s
假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道，则：

延迟时间T_R：通过旋转磁盘，使磁头定位到目标扇区所需要的时间，设磁盘转速为r，则平均所需

传输时间T_t：从磁盘读出/写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则：

操作系统无法影响延迟时间与传输时间，仅可优化寻道时间，引出下文调度算法

先来先服务算法

根据进程请求访问磁盘的先后顺序进行调度

公平，当请求访问的磁道相对集中时，性能还可以
如果大量的进程争用磁盘，访问的磁道分散，性能很差

最短寻找时间SSTF

寻找与当前磁头最近的磁道，保证每次的寻道时间最短(贪心算法)

性能较好，可能会产生饥饿现象，因为磁头可能会在一个小区域内来回地移动

扫面算法SCAN

只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动，又称电梯算法

性能较好，不会产生饥饿现象
只有到达边界才会改变磁头移动方向，可能会导致访问到不需要的磁道，浪费时间
算法对于各个位置磁道的响应频率不平均(边界响应频率要更快一点)

LOOK调度算法

当磁头移动方向没有别的磁道访问请求，直接改变磁头移动方向

解决了SCAN可能导致的访问多余磁道的问题

循环扫描算法C-SCAN

只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动到起始端而不处理任何请求，解决SCAN对各个磁道响应频率不一致的问题

注意，这个起始端指的是整个磁道的起始端，而非访问队列的起始端

比起SCAN算法，其平均寻道时间更长了
在返回时可能导致大量的时间浪费(一个请求都没处理)

C-LOOK算法

如果磁头移动的方向上已经没有磁道访问请求，就立即让磁头返回，且磁头只需要返回到访问队列起始端即可

减少磁盘延迟时间的方法

磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的延迟时间

硬盘地址结构设计

围绕着尽量让磁头臂不移动设计，所以，当读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间

交替编号

让逻辑上相邻的扇区在物理上有一定的间隔，可以使连续的逻辑扇区需要的延迟时间更小

错位命名

针对不同的盘面，同一相对位置的扇区命名错位

磁盘管理

磁盘初始化

低级格式化，将各个磁道划分为扇区，扇区可分为头、数据区域、尾三个部分
- 头尾存储扇区校验码(奇偶校验、CRC校验码)用于检验扇区数据是否发生错误
将磁盘分区，每个分区由若干个柱面组成
进行逻辑格式化，创建文件系统，包括创建文件系统根目录、初始化存储空间管理所用的数据结构（位示图、空闲分区表）

引导块

开机时进行的一系列初始化程序(自举程序)，将很小的自举装入程序放于ROM中，集成在主板上

将完整的自举程序放在磁盘的启动块(即引导块/启动分区)上，启动块位于磁盘的固定位置，开机时先从ROM中运行自举装入，找到引导块，执行完整的自举程序，完成初始化

拥有启动分区的磁盘称为启动磁盘或系统磁盘

坏块管理

数据硬件故障，无法修复

可以在逻辑格式化时(建立文件系统)对整个磁盘进行坏块检查，标明哪些扇区是坏扇区

比如在在FAT表标明，该方式坏块对操作系统不透明

对于复杂的硬盘，磁盘控制器会维护一个坏块链表，在低格时就将坏块链进行初始化

保留一些备用扇区，用于替换，坏块对操作系统透明

固态硬盘SSD

本质上属于电可擦除ROM，即EEPROM

组成

闪存翻译层：负责将逻辑地址映射到物理地址

闪存芯片组：对节山村翻译层，有若干个闪存芯片，每个芯片包含多个块，每个块包含多个页

注：图中系统要读写的逻辑“块”，对应到SSD中，指的是页

读写性能

以页为单位读/写—-对应到磁盘的“扇区”

以块为单位擦除，擦干净的块，每个页都可以写一次，读无限次

支持随机访问，闪存翻译层通过电路将逻辑地址映射到物理地址

读块，写慢，要写的页如果有数据，则不能写入，需要将块内其他页全部复制到新的块中，再写入新的页

对比机械硬盘

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

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

SSD的块被擦除过多的话可能导致损坏，而机械硬盘的扇区不会

磨损均衡技术

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

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

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