第四章-文件管理

4.1 文件系统基础

1.文件的概念和基本操作

文件是存储在硬盘上的信息集合，包含一块存储空间，分类和索引的信息，访问权限信息

文件最底层是数据项：某对象某属性的一个值

记录：一组相关的数据项的集合，一个对象的多个属性

文件的基本操作

文件的打开：

• 使用open系统调用，参数为[文件名，读写方式]，返回文件描述符，之后对文件的任何操作都不再需要文件名了

  int open(const char *pathname, int flags, mode_t mode);

• 操作系统根据文件名找到目录项，检查用户权限，把该目录项放入用户进程的打开文件表（不是把文件读入内存！）

每个进程的打开文件表中包含：【读写指针，访问控制权限，inode指针】

系统打开文件表中有所有文件的打开计数器count，表示多少进程打开该文件

关闭：删除用户进程的打开文件表项，释放空间

读：ssize_t read(int fd, void *buf, size_t count);

写：ssize_t write(int fd, void *buf, size_t count);

read和write系统调用的参数是文件描述符而不是文件名，通过open获得

2.文件的逻辑结构

（1）无结构文件：流式文件，以字节为单位，穷举搜索

（2）有结构文件：记录式文件，一组相似的记录

• 顺序文件：记录顺序排列的文件
• 索引文件：
  • 索引文件需要一个索引表来进行记录的查找。
  • 索引表项【索引号|记录长度|记录的逻辑地址】。
  • 对于定长记录，直接用iL得到第i条记录的地址；对于可变长记录，就要顺序查找
• 索引顺序文件：索引表项【键|逻辑地址】。
  • 将顺序文件分成若干组，索引表中的键是每组的第一条记录的关键字值。
  • 查找记录时，先用索引查到所在的组，每组内部顺序查找。
  • 如果n条记录分成$\sqrt{N}$组，平均共需查找$\sqrt{N}/2+\sqrt{N}/2=\sqrt{N}$次

（3）直接文件/散列文件：通过哈希函数映射到物理地址，可能冲突

3.目录结构

目录在文件名和文件之间提供映射

文件控制块FCB

包含文件的各种信息。每个文件都有一个FCB，FCB就是文件目录项

目录：一个文件夹下有哪些文件

索引节点inode

由于查找目录时，fcb太大不好放入内存，于是将文件名以外的信息放入索引节点，索引节点放在磁盘上

目录项只包含文件名-索引节点指针的映射，根据文件名可以找到对应的索引节点，就可以得到信息

文件目录项：【文件名|索引节点指针】

目录结构

• 单级目录结构：整个文件系统只有一个文件目录表，不允许文件重名
• 两级目录结构：不同用户的文件在不同的用户文件目录下
• 多级目录结构（树形目录结构）：
  • 不按用户划分，每层目录对应树的一层。
  • 从根目录出发得到绝对路径，从中间节点（当前目录）出发得到相对路径。
  • 缺点：不便于文件共享
• 无环图目录结构：
  • 实现文件共享
  • 在树形目录结构的基础上，可以不同文件名指向一个文件
  • 每个共享节点有一个共享计数器，值为0时删除共享文件

4.文件共享

硬链接（基于索引节点）

• 不同进程的打开文件表（目录）中该文件名对应的索引节点指针指向同一个inode

• inode内部有引用计数count，一个用户从目录中删除该目录项后，count--。

  count归0才能删除文件。

• 不同用户的硬链接文件的读写指针位置不同

• fd1是文件描述符，是文件f1在打开文件表中的位置（索引值）

软链接（基于符号链）

• 创建一个link文件（类似快捷方式），里面记录了原文件的路径，打开它本质上打开源文件
• 目录中link文件的inode的指针不指向源文件的inode
• link文件inode的引用计数count直接复制源文件的，之后就没有关系了
• 当源文件被删除，link文件也就失效了

硬链接速度比软链接快

5.文件保护

口令保护：打开文件需要密码

加密保护：把文件从明文加密成密文，需要密钥解密

访问控制：为每个文件和目录增加一个访问控制表，规定每个用户对文件的访问方式（m个用户，n种权限，则需要mn位）

4.2 文件系统实现

一、文件系统层次结构

用户调用接口

文件目录系统：查找文件索引信息

存取控制验证模块

逻辑文件系统和文件信息缓冲区：用户要读写的记录-》逻辑地址

物理文件系统：逻辑地址-》物理地址

辅助分配模块：释放空间

设备管理程序模块：空间用来输入输出

二、目录实现

线性列表：文件名直接映射地址

哈希表：根据hash(文件名)，返回一个地址

三、文件分配

如何为文件分配磁盘块

（1）连续分配

一个文件占用若干连续的磁盘块

逻辑地址：【逻辑块号|块内偏移】

文件目录项：【文件名|起始块号|长度】

访问磁盘块时，起始块号+逻辑块号=物理块号

优点：随机访问

缺点：文件增删改不方便，删除文件会产生外部碎片

（2）链接分配，FAT文件分配表

隐式链接：一个文件的每个磁盘块有指向下一块的指针。只能沿着链表顺序访问，访问磁盘次数太多。目录项为【文件名|起始块号|结束块号】。文件拓展方便，没有外部碎片

显式链接：整个磁盘在内存中有一个FAT（文件分配表），表项【块号|下一块的块号】。

• 这样访问磁盘块时，只需先在FAT中沿着链查找，所以对磁盘是随机访问。
• 下一块的块号：-1表示结束，-2表示空闲。文件拓展方便，没有外部碎片

优点：增删改方便

缺点：查不方便，只能顺序访问，需要额外存储空间存放链接指针

每个目录有一个目录文件，这个目录文件就位于该目录所在的簇中，里面存储该目录下每个文件的起始簇号。然后根据FAT，顺序找到每个文件的所有簇

（3）索引分配

每个文件把一个磁盘块作为索引块，里面是索引表【逻辑块号|物理块号】，目录中是【文件名|索引块号】

这样先找到索引块，然后里面按顺序记录了该文件所有块的物理块号。

优点：随机访问，增删改方便

缺点：索引表占空间

如果一个文件包含的块太多，一个索引表装不下，则有下面方法：

• 索引链接：将多个索引块用链表连接，查得慢
• 多层索引：类似多级页表，最后一级页表直接指向盘块。如果inode已经在内存中，m级页表则需要读磁盘m+1次才能找到盘块
• 混合索引：为了避免多层索引时要读的物理块很少却要读很多次索引表，对顶级索引表的不同项采取不同的索引方法（不同层的多层索引）

计算题：求单个文件的最大长度

多级索引就是索引数的n次方x块大小

总结

	访问方式	增删改	借助工具
连续分配	随机访问	不方便	/
链接分配	顺序访问	方便	FAT表
索引分配	随机访问	方便	索引表

四、磁盘空闲空间管理

文件卷：把磁盘分成若干逻辑盘，如C盘，D盘

空闲块的分配和回收

（1）空闲表法：连续分配

空闲盘块表：【序号|第一个空闲块号|空闲块数】

在为文件分配空闲块时，先顺序查找空闲盘块表，直到大小满足要求，分配，修改表。回收时，分为前后无空闲块、前后均空闲、前空闲、后空闲四种合并情况。

（2）空闲链表法

空闲盘块链：将空闲空间以盘块为单位连成链表，从链头分配，盘块回收后挂到链尾

空闲盘区链：以多个连续盘块（盘区）为单位连成链表

（3）位图法：bitmap

设字长为n，则位图的一行有n位，每位代表一个盘块的分配情况，0表示空闲，1表示已分配

位图的第i行第j列（字号为i，位号为j）表示盘块号b为ni+j的分配情况（默认i从0开始，若从1开始，盘块号为n(i-1)+j）

反过来，若盘块号为b，则字号为b/n，位号为b%n

（4）成组链接法

Unix操作系统，内存中有一个超级块，它的第一个单元记录了一组空闲盘块的数量，第二个单元指向下一组空闲盘块（又相当于一个超级块）的首地址，后面每个单元指向一个空闲盘块。这样把所有空闲盘块串起来，适合大型文件，一下子找到许多空闲块

4.3 磁盘组织与管理

磁盘结构

一个盘面有上千个同心圆，称为磁道，每个磁道划分为几百个扇区（也叫盘块），扇区是寻址的最小单位。

所有盘片上相同位置的磁道组成柱面，读写磁头同时读一个柱面上的不同盘面

磁盘地址：【柱面号|盘面号|扇区号】

柱面号确定哪一个磁道

盘面号确定哪张盘，即哪个磁头对应的位置，也称为磁头号

例：2019.44

磁盘读写时间

磁盘读写时间=寻道时间+延迟时间（旋转到某扇区）+传输时间

• 平均寻道时间=mn+s，m是常数，n是跨越磁道数，s是启动磁臂时间。一般题中直接给

• 平均旋转时间=一转的时间/2

• 传输时间=传输字节数/传输速率

  假设已知每个磁道的扇区数，则传输一个扇区的时间=一转的时间/扇区数

磁盘调度算法

多个进程请求读写磁盘，操作系统决定先为哪个请求服务

（1）先来先服务FCFS：按照请求的先后顺序服务

（2）最短寻找时间优先SSTF：总是先找离当前位置最近的磁道，会使远的饥饿

（3）扫描SCAN（电梯调度）：开始选定磁头移动方向，然后走到最靠边的有请求的磁道再反方向移动。不会饥饿，对内外磁道响应频率不平均【来回扫】

（4）循环扫描C-SCAN：磁头只能单向移动，一旦移动到最右侧的序号，就立刻回到最左侧序号，不处理中间的请求【单向扫】

• 例如序列30,50,90,120，当前磁头100向磁道号增大方向移动
• SCAN路径为：100->120->90->50->30
• C-SCAN路径为100->120->30->50->90，共移动了20+90+60=170个磁道
• 两种方法都不走到尽头，只走到有请求的

（5）LOOK调度：SCAN不走到头，只走到最边缘的请求

磁盘记录排列问题

读完一块信息后需要处理，而此时磁盘仍在旋转，所以希望旋转后正好到达下一个需要的块，这就涉及到如何更好地排列连续的记录问题。

王道8.4（21）

减少延迟时间的方法：同一盘面交替编号，不同盘面错位命名

磁盘的初始化

硬盘出厂时只有若干磁道，之后

• 物理格式化：
  • 各个磁道分成扇区，编物理地址。确定管理扇区的数据结构，包括扇区校验码，校验扇区内数据是否错误
  • 将磁盘分区，如CDE盘，每个分区由若干柱面组成
• 逻辑格式化：
  • 创建文件系统，包括文件系统根目录
  • 对空闲磁盘块管理的数据结构初始化（如位图，空闲分区表）

磁盘分成簇/块是操作系统层面的，创建文件时以簇为单位分配空间

引导块：计算机启动时需要自举程序初始化硬件，启动操作系统。自举程序一部分存在ROM中，完整功能的自举程序存在磁盘的启动块上（引导块）

坏块：硬件故障，FAT标明坏的扇区

操作系统以簇为单位分配磁盘空间

总结

注意如下概念：目录，索引节点，打开文件表，FAT表，索引表

目录的单位是FCB，用于从文件名找到文件地址

为了减小目录大小引出索引节点，目录项指向inode，inode里面保存信息和文件地址

进程的打开文件表就是个目录

为文件分配盘块有三种方式

1.连续分配时，目录包括文件名，起始块号，长度

2.链接分配时，目录包括文件名，起始块号，然后根据FAT表不断找下一块的块号

3.索引分配时，每个文件有个索引表，表项指向不同的盘块，或者多级索引表套娃