计算机操作系统(四)文件

4文件

4.1文件管理

4.1.2文件的逻辑结构

无结构文件：流式文件，一系列二进制流/字符流组成

有结构文件：记录式文件

• 每条记录有个数据项可作为关键字
• 定长记录，可变长记录

顺序文件

记录逻辑上顺序排列

• 可以是定长/变长的
  物理上：可以顺序存储或链式存储

顺序文件

• 串结构：记录之间的顺序与关键字无关
• 顺序结构：记录之间的顺序按关键字顺序排列

顺序存储

• 可变长记录：
  • 无法实现随机存取
• 定长记录：
  • 可实现随机存取
  • 若采用串结构，无法快速找到某个关键字对应的记录
  • 若采用顺序结构，可以快速找到某个关键字对应的记录
• 缺点：增删记录比较困难
  链式存储
• 无法实现随机存取
  • 每次只能从第一个记录开始依次往后查找

索引文件

索引表本身是定长记录的顺序文件

检索速度快
主要用于对信息处理的及时性要求比较高的场合

可以用不同的数据项建立多个索引表

索引顺序文件

不是为每个记录对应一个表项
而是一组记录对应一个索引表

多级索引顺序文件

分更多级别的分组，大大减少了查找次数

4.1.3文件目录

文件控制块

目录文件中的一条记录：文件控制块FCB

FCB中包含了文件的基本信息(文件名、物理地址、逻辑结构、物理结构等)等
实现了文件名和文件之间的映射，使得可以按名存取

需要对目录进行哪些操作

• 搜索
• 创建文件
• 删除文件
• 显示目录
• 修改目录

目录结构：单级目录结构

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

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

不适用于多用户OS

目录结构：两级目录结构

分为主文件目录，用户文件目录

主文件目录记录用户名和用户文件目录存放位置

• 用户文件目录由用户文件FCB组成
  • 允许不同用户的文件重名

但缺乏灵活性，用户不能对自己的文件进行分类

目录结构：多级目录结构

树形目录结构
用/分隔各级目录，从根目录出发的路径是绝对路径

需要从外存读入根目录表，一层层向下读取对应的目录表

从当前目录出发的是相对路径

相对路径，减少了磁盘I/O，加快了文件访问速度
不便于实现文件共享

目录结构：无环图目录结构

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

可以用不同的文件名指向同一个文件
甚至可以共享同一个目录

需要为每个共享节点设置一个共享计数器

• 删除只是对共享计数器减1
• 只有当共享计数器为0时，才删除节点

共享文件不是复制文件，各个用户使用的是同一个文件

索引节点(FCB的改进)

简化FCB，除了文件名之外的文件描述信息放在索引节点

一个磁盘块中会有更多的目录项，减少了IO
大大提升文件检索速度

外存中的索引节点：磁盘索引节点
内存中的索引节点：内存索引节点

• 还需要些额外信息：如文件是否被修改，被几个进程访问等

4.1.4文件的物理结构

OS对磁盘的管理

• 对非空闲磁盘块的管理：存放的文件数据的磁盘块
• 对空闲磁盘块的管理

文件的逻辑地址空间也被分块
逻辑块号，块内地址

文件分配方式：连续分配

每个文件在磁盘上占有一组连续的块

文件目录中记录存放的起始块号，长度
物理块号=起始块号+逻辑块号

优点：

• 连续分配支持顺序访问和直接访问(随机访问)

读取某个磁盘块时，需要移动磁头
访问的两个磁盘块相隔越远，移动磁头所需时间就越长

优点：

• 连续分配的文件在顺序读/写时速度最快

缺点：

• 连续分配的文件不方便拓展
• 存储空间利用率低，会产生难以利用的磁盘碎片
  可以紧凑，但是代价大

文件分配方式：链接分配

采取离散分配方式

• 隐式链接
• 显式链接

隐式链接

缺点：
只支持顺序访问，不支持随机访问
指向下个盘块的指针也耗费存储空间

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

显式链接

把用于链接文件各个物理块的指针显示存放在表中
文件分配表FAT

一个磁盘仅设置一张FAT
开机时读入内存并常驻

FCB只需要存储起始块号
逻辑块号转换成物理块到的过程不需要读磁盘操作(FCB常驻内存)

支持随机访问(访问i号逻辑块前，不需要依次访问之前的逻辑块)

优点：
不会产生外部碎片，方便扩展
地址转换不需要访问磁盘，文件访问效率更高

缺点：FAT需要占用一定存储空间

文件分配方式：索引分配

为每个文件建立一张索引表
表中记录了文件的各个逻辑块对应的物理块
建立逻辑页面到物理页的映射关系

索引表存放的磁盘块：索引块
文件数据存放的磁盘块：数据块

支持随机访问，文件拓展也很容易实现

链接方案

如果索引表太大，可以将多个索引块连接起来存放

访问第二个索引块中的索引表，

• 则需要读入索引表第一个块，找到最后的指针，读入第二个索引块
  缺点：若文件很大，尾部索引的磁盘访问操作太多，查找效率低下

索引分配

建立多层索引(类似多级页表)
第一层索引块指向第二层索引块

各层索引表大小不能超过一个磁盘块

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

缺点：小文件访问一个数据块的磁盘操作次数依旧为k + 1次

混合索引

多种索引分配方式的结合
即包含直接地址索引(指向数据块)，又包含一级间接索引(指向单层索引表)，还包含二级间接索引(指向两层索引表)

优点：对于小文件，访问一个数据块的读磁盘次数更少

注意：

• 根据多层索引、混合索引结构计算出文件的最大长度
  • 各级索引表最大不能超过一个块
• 分析访问某个数据块所需的读磁盘次数
  • FCB中会存有指向顶级索引块的指针
  • 注意：顶级索引块是否已调入内存

4.1.5逻辑结构VS物理结构

逻辑结构：文件内部信息的组织方式
用户建立的

• 将整个文件视为连续的逻辑地址空间
  物理结构：将文件分块后在磁盘中的组织形式
  OS建立的
• 负责逻辑块号到物理块号的映射

4.1.6文件存储空间管理

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

存储空间的划分与初始化

将物理磁盘划分为逻辑卷

文件卷：

• 目录区：
  • 存放文件目录信息
  • 用于磁盘存储空间管理的信息
• 文件区：
  • 用于存放文件数据

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

文件卷可由多个物理磁盘组成

存储空间管理：空闲表法

空闲盘块表：

• 第一个空闲盘块号
• 从这个块号开始的空闲盘块数

适用于连续分配方式

分配连续的存储空间：可采用首次适应、最佳适应、最坏适应等算法

与动态分区分配类似
回收时：注意表项的合并问题

存储空间管理：空闲表法

• 空闲盘块链
  • 以盘块为单位组成一条空闲链
• 空闲盘区链
  • 以盘区(连续的盘块)为单位组成一条空闲链
  • 记录当前盘区的长度、下一个盘区的指针

OS保存链头、链尾指针

分配：从链头取走盘块，修改链头指针

• 或者，从链头检索盘区，
  • 可以用动态分配算法进行查找，
  • 也可以将不同盘区的盘块同时分给一个文件
    回收：挂到链尾，修改链尾指针
• 盘区要注意合并相邻的空闲区间

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

盘区链为一个文件分配多个盘块时效率更高

存储空间管理：位示图法

位示图：每个二进制位对应一个盘块
一般用连续的字(字节)来表示
可以用(字号, 位号)对应一个盘块号
或者(行号，列号)

要能自己推出盘块号与(字号，位号)相互转换的公式

(字号, 位号) = (i, j)的二进制位对应的盘块号b = n * i + j
b号盘块对应的字号i = b / n, 位号j = b % n

分配：

• 顺序扫描，找到k个相邻/不相邻的0
• 根据字号、位号算出对应的盘块号，分配给文件
• 将相应位设为1

回收：

• 根据回收的盘号计算出对应的字号、位号
• 将相应二进制位设为0

连续分配、离散分配都适用

存储空间管理：成组链接法

空闲表法、空闲链表法不适用于大型文件
UNIX系统使用成组链接法

文件卷的目录区中，专门用一个磁盘块作为超级块

• 系统启动时超级块读入内存
• 且要保证内存与外存的超级块数据一致

超级块：

• 当前组空闲盘块数
• 下一组(跟超级快结构一样)所在的块号
• 空闲块号
• 空闲块号…

若已经没有下一组空闲块，则块号为一个特殊值

每个分组中的块号不需要连续

分配：

• 检查第一个分组中的空闲块
  • 如果够，分配空闲块
• 修改相应数据(删掉超级块中的空闲块号，减少下一组空闲盘块数)

若分配很多空闲块导致当前超级块空了

• 将下一个组的内容复制过来
  这样就不会失去与下个组的连接了

回收：

• 若第一个分组没满，插入进入
• 若满了，则创建一个新的分组
  • 新分组作为第一个分组，下一个分组指向原来的第一个分组

4.1.7文件的基本操作

创建文件

• Create系统调用
  参数：
• 所需外存空间大小
• 文件存放路径
• 文件名

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

删除文件

• Delete系统调用
  参数
• 文件存放路径
• 文件名

1.找到文件名对应的目录项
2.回收文件占用的磁盘块
3.从目录表中删除文件对应的目录项

打开文件

• open
  参数
• 文件存放路径
• 文件名
• 对文件的操作类型

1.找到文件名对应的目录项，检查用户是否有指定操作权限
2.将目录项赋值到内存中的打开文件表中，返回对应表项的编号
用户使用打开文件的编号来指明要操作的文件

用户的进程打开文件表：多个用户进程，实现文件共享，便于文件管理

• 编号、文件名、读写指针、访问权限、系统表索引号、…
  系统的打开文件表：只有一个
• 编号、文件名、外存地址、打开计数器…

关闭文件

• close

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

读文件

• read
  指明文件索引号，读入多少数据，放在内存什么位置

从读指针指向的外存中，将指定大小的数据读入用户指定的内存区域中

写文件

• write
  文件索引号、写多少数据，存放在内存中什么位置

从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存

4.1.8文件共享

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

各个用户的目录项指向同一个索引结点
索引结点中设置一个链接计数变量count
count等于0时才删除文件数据和索引节点

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

软链接文件中存放对应文件的路径(类似快捷方式)

软连接共享文件时要查询多级目录，会有多次磁盘I/O

4.1.9文件保护

口令保护

为文件设置口令，存放在FCB或索引节点中

• 用户请求访问文件时必须提供口令

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

缺点：正确的口令存放在系统内部，不够安全

加密保护

使用某个密码对文件加密

• 访问文件时需要提供正确的密码才能对文件进行正确的解析

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

缺点：编码/译码需要花费一定时间

访问控制

在文件FCB(或索引节点)中增加一个访问控制列表(ACL)

• 表中记录了各个用户可以对该文件执行哪些操作

读、写、执行、添加、删除、列表清单

若计算机中用户过多，访问控制列表可能很大
精简访问列表：以组为单位，标记各组用户可以对文件执行哪些操作

• os管理分组的信息
• 用户访问时，os检查用户所属组是否有权限

4.2文件系统

4.2.1文件系统的层次结构

• 用户接口：提供简单易用的接口
• 文件目录系统：目录、目录项相关管理工作
• 存取控制模块：保证文件数据安全，文件保护相关功能
• 逻辑文件系统与文件系统缓冲区：将记录号转换为对应的逻辑地址
• 物理文件系统：把文件逻辑地址转换为实际的物理地址
  • 辅助分配模块：复制文件存储空间的管理
  • 设备管理模块：直接与硬件交互
    • 设备

4.2.2文件系统布局

物理格式化：低级格式化
划分扇区，检测坏扇区，用备用扇区替换坏扇区

逻辑格式化：高级格式化
磁盘分区，完成各区文件系统初始化

UNIX文件系统：

• 引导块
• 超级块
• 空闲空间管理
• i结点区
• 根目录
• 其他文件、目录

文件系统在内存中的结构：
内核区：

• 目录缓存：近期访问过的目录文件：加速
• 系统打开文件表
• 进程(用户)打开文件表
  用户区：
• 文件描述符

4.2.3虚拟文件系统

普通文件系统

• 不同设备的文件系统可能不同，系统调用可能也不同
  分别对不同文件系统编程很麻烦

虚拟文件系统
特点：

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

vnode

• 文件名、文件大小、…
• 函数功能指针
  • 指向对应文件系统提供的函数功能

文件系统挂载：文件系统安装/装载

• 在VFS中注册新挂载的文件系统
  • 内存中的挂载表：包含每个文件系统的相关信息
• 新挂载的文件系统，要向VFS提供一个函数地址列表
• 将新文件系统加到挂载点
  • 将新文件系统挂载在某个父目录下