OS_theory_4

初识文件管理

文件的逻辑结构

所谓的“逻辑结构”，就是指在用户看来,文件内部的数据应该是如何组织起来的。而物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。

总结

有结构文件

文件目录

FCB

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

FCB 中包含了文件的基本信息 (文件名、物理地址、逻辑结构、物理结构等)，存取控制信息(是否可读/可写、禁止访问的用户名单等)，使用信息(如文件的建立时间、修改时间等)

FCB 实现了文件名和交件之闻的映射、售文件之间的映射。以实现“按名存取“

FCB需要对目录进行哪些操作?

1.搜索:当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项。

2.创建文件:创建一个新文件时，需要在其所属的目录中增加一个目录项。

3.删除文件:当删除一个文件时，需要在目录中删除相应的目录项。

4.显示目录:用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性。

5.修改目录:某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如:文件重命名）

总结

文件的物理结构（文件分配方式）

连续分配方式

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

优点:支持顺序访问和直接访问(即随机访问):连续分配的文件在顺序访问时速度最快

缺点:不方便文件拓展;存储空间利用率低，会产生磁盘碎片

链接分配方式

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

隐式链接

隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

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

缺点:只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接

显式链接——把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT，File Allocation Table)。一个磁盘只会延建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
优点:很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点:文件分配表的需要占用一定 的存储空间。

索引分配方式

定义

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各人逻辑块对应的物理块 (索引表的功能类似于内存管理中的页表一一建立逻辑页面到物理页之间的映射关系) 。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

分类

若文件太大，索引表项太多，可以采取以下三种方法解决:

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

缺点:若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入 0~i-1号索引块，这就导致磁盘I/0次数过多，查找效率低下。

2.多层索引: 建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用《层索引结构，且顶级索引表未调入内存，则访问个数据块只需要K+1次读磁盘操作。

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

3.混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引 (直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)

优点:对于小文件来说，访问一个数据块所需的读磁盘次数更少。

总结

文件存储空间管理

空闲表法

如何分配磁盘块？

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

如何回收磁盘块?

与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况:

1.回收区的前后都没有相邻空闲区;

2.回收区的前后都是空闲区;

3.回收区前面是空闲区;

4.回收区后面是空闲区。

总之，回收时需要注意表项的合并问题。

成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。

UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

总结

文件的基本操作

文件共享

注意:多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

文件保护

口令保护

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

缺点:正确的“口令”存放在系统内部，不够安全。

加密保护

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

缺点:编码/译码，或者说加密/解密要花费一定时间。

总结

如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制。

文件系统的层次结构

一个例子

假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx”的最后100条记录。

1.用户需要通过操作系统提供的接口发出上述请求——用户接口。

2.由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统。

3.不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块(存取控制验证层)。

4.验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区。

5.知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统。

6.要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块。

7、删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块。

文件系统

基本概念

文件

文件是指一组带表示(文件名),在逻辑上有完整意义的信息项序列.信息项时构成文件内容的基本单位,各个信息项之间具有一定的顺序关系.文件包含两部分内容.:

• 文件体:文件本身的数据
• 文件说明:文件存储和管理的相关信息(名字,地址,访问权想,创建时间,修改时间等).

文件是一种对数据的抽象,它使得用户不必关心信息保存在磁盘上的方法和访问细节.

其本质是一组字节序列,源于用户程序对所要输入处理的原始数据和输出结果的长期保存,并按照一定格式呈现.

所有 I/O 设备都可以看作为字节序列的载体,因此 I/O 设备也可以抽象成文件,这就是一切皆文件的含义.

文件管理

• 用户视角(使用逻辑文件)
• 用户关心文件中所要使用的数据,不关系具体的存放形式和位置
• 关心文件系统对外接口
• 操作系统视角(组织和管理物理文件)
• 关心如何实现与文件有关的各个功能模块,包括存储,布局,管理,接口等.

文件系统

文件系统时操作系统中统一管理信息资源的一种软件,管理文件的存储,检索,更新.提供安全可靠的共享和保护手段,并且方便用户使用.
文件系统的任务:

• 统一管理磁盘空间,实施磁盘空间的分配和回收
• 实现文件的按名存取
• 实现文件信息的共享
• 向用户提供一个方便使用的几口
• 提高文件系统性能
• 提供与 IO 系统的统一接口

文件名

当文件创建的时候必须有一个名字方便用户访问.

• 命名规则
• 文件名一定是一个有限长度字符串
• 文件名由两部分组成,模式如下: 文件名.扩展名

文件类型

• 按性质和用途: 系统文件,库文件,用户文件
• 按数据形式:源文件,目标文件,可执行文件
• 按对文件实施的保护级别:只读文件,读写文件,执行文件,不保护文件
• 按逻辑结构:有结构文件,无结构文件
• 按文件中物理结构分:顺序文件,链接文件,索引文件

文件逻辑结构

这是从用户角度看文件,由用户进程对文件的访问方式决定.

• 字节为单位的流式结构:文件是由有逻辑意义,无结构的一串字符组成的集合
• 记录式文件结构:文件由记录组成,可以按照记录读写,每条记录由其内部的结构
• 树形结构:类似B-树

目录管理

目录是由文件说明索引组成的用于文件检索的特殊文件.
文件目录的内容主要是文件访问和控制的信息.

目录内容

• 基本信息:
• 文件名
• 别名:有些操作系统允许文件有别名(alias)
• 文件类型
• 地址信息
• 访问控制信息
• 使用信息

文件目录的分类

• 单级文件目录:只有一个目录:根目录
• 结构简单
• 文件多的时候,检索时间长
• 命名冲突:不同用户的相同作用文件可能是同一个名字,不同用户对同一个文件的命名可能不同
• 不便于共享
• 二级文件目录:在根目录之后给每个用户一个目录
• 多级文件目录:多个目录,几乎所有现代操作系统都采用这个.
• 绝对路径:从根目录开始依次经由的各级目录名，再加上最终的文件名
• 相对路径:结合当前路径进行使用
• 特点:
• 层次清楚
• 解决重命名问题
• 查找速度块
• 目录级别太多,增加路径检索时间

文件系统

定义和目的

定义:
操作系统中与文件管理有关的那部分软件和被管理的文件以及实施管理所需要的数据结构的总体.
目的:

• 方便文件访问
• 并发文件访问和控制
• 统一的用户接口
• 多种文件访问权限
• 执行效率高
• 差错恢复强

文件系统模型的三个层次

• 文件系统的接口(最接近用户的)
• 命令行接口:用户和文件系统的交互的接口
• 程序接口:用户程序和文件系统的接口
• 对象操作管理的软件集合
• 对存储空间的管理
• 对文件目录的管理
• 将文件逻辑地址转换成物理地址的机制
• 读写管理
• 共享和保护功能
• 对象及其属性
• 文件:直接管理对象
• 目录
• 磁盘存储空间

实现方法

文件控制块和文件属性

文件控制块:
为管理文件而设置的数据结构,保存管理文件所需的所有有关信息

• 基本信息
• 文件名
• 物理位置
• 文件逻辑结构:有无结构(记录文件,流式文件)
• 文件物理结构:索引,顺序等
• 访问控制信息
• 文件所有者
• 访问权限
• 使用信息
• 创建时间,上一次修改时间,当前使用信息

文件逻辑结构
提高检索效率,便于修改,降低文件存储费用
文件物理结构
文件在存储介质上的存放方式,表示一个文件在文件存储介质上的位置,链接和编目的方法.

主要结构:连续结构,索引结构,串联结构

文件物理结构

顺序结构

顺序结构

• 优点
• • 结构简单,实现容易,没有额外的空间开销
• • 支持顺序存取和随机存取
• • 连续存取数据块
• 缺点
• • 文件长度固定后不容易改变
• • 不利于文件动态增加和修改

串联/链接文件结构

串联结构

• 优点
• • 空间利用率高
• • 文件动态扩充和修改容易
• • 顺序存取效率高
• 缺点
• • 随机存取效率低
• • 可靠性问题,容易指针出错
• • 指针占据空间

索引结构

系统为每个文件建立一个数据结构:索引表
索引表是磁盘块地址数组,其中第 i 个目录项指向文件的第i块
索引表存在于文件目录,文件开头等位置
索引结构：

访问索引文件:

• 查文件索引号
• 查此磁盘物理块
• 优点
• • 既能顺序存取,又能随机存取
• • 满足了动态增长
• • 充分利用外存空间
• 缺点
• • 空间开销和时间开销

索引表的组织

• 链接模式:多个索引表链接
• 多级索引:讲所有索引表的地址放在另一个索引表
• 综合模式:综合上面二者

目录的主要功能和显示

目录实现需要解决:

• 目录项内容
• • 直接法:目录项 = 文件名 + PCB
• • 间接法:目录项 = 文件名 + PCB的地址
• 长文件名的问题
• • 固定长度
• • 长度可变,分为三部分:目录项长度(固定),文件的属性信息(固定),文件名(改变),问题是删除之后,文件名占的内存不好回收
• • 目录项本身的长度固定，把长度可变的文件名统一放在目录文件的末尾。
• 目录的搜索方式
• • 顺序查询法
• • Hash

保护文件的方法

• 建立副本:把同一个文件保存在不同存储介质
• • 优点: 简单
• • 缺点:设备费用和开销大
• 定时转储
• • 每隔一定时间把文件转储到其他存储介质上，当文件发生故障，就用转储的文件来复原，把有故障的文件恢复到转储时刻文件的状态
• 规定文件的权限:保护文件不被非法篡改
• • 防止未被批准的用户存取文件
• • 防止用户冒充其他用户存取文件
• • 防止核准用户(包括文件属主)误用文件.

文件的一致性检查

• 磁盘块的一致性:
• 每个磁盘块设置两个计数器，一个记录在文件中出现的次数，另一个记录在空闲块中出现的次数，最终检查两个计数器是否存在不一致问题。
• 文件的一致性:
• 每个文件设置两个计数器，一个记录其i节点被引用的次数，另一个记录文件目录中引用它的次数，最终检查两个计数器是否存在不一致问题。

文件的并发访问

文件并发访问控制的目的是提供多个进程并发访问同一文件的机制。

可以利用文件锁定(file lock)协调对文件指定区域的互斥访问

利用进程间通信,协调对文件的访问

文件系统性能提升

磁盘速度限制了文件系统的速度,所以文件系统要尽可能减少对磁盘的访问,常用方法:

• 目录项（FCB）分解、当前目录、磁盘碎片整理、块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术等

块高速缓存

在内存中为磁盘块设置的一个缓冲区，保存了磁盘中某些块的副本。

磁盘块大小

磁盘块大小需要权衡

• 太大了访问次数少,但是碎片多
• 太小了碎片少,访问次数多

基于日志系统的文件系统 LFS

基本思路

将磁盘看作一个日志对待,每次添加文件总是顺序添加到磁盘,每次添加先放入缓存,再一次性读入

数据结构

• 段:包含数据块和元数据的日志
• inode:包含文件的物理块指针
• inode map: 一个存放inode节点在磁盘上位置的表
• 段摘要:段中数据信息
• 段使用情况:段数据块中有效数据的量

读写操作

先操作缓冲区,再操作磁盘

失效恢复

不需要检查整个磁盘,日志回退即可,最近的一次操作就会被覆盖

清理

为了提供连续的空闲磁盘空间,所以需要清理段.

对于访问频繁的段,填充到达0.75之后就会清理,释放出空闲空间
对于访问不频繁的段,达到0.15之后,释放空闲空间