第六章 文件管理
2020-06-30 18:25:44 1 举报AI智能生成
登录查看完整内容
《操作系统》第九章文件管理思维导图
作者其他创作
大纲/内容
文件管理
文件存储空间的管理
空闲表法
空闲表
属于连续分配方式，为外存的空闲区建表，包括空闲区第一个盘块号，空闲盘块数
存储空间的分配与回收
与内存动态分配类似，同样采用首次适应、循环首次适应等等
空闲链表法
把所有空闲区拉成一条空闲链
空闲盘块链
以盘块为单位成链
分配回收亦以盘块为单位
空闲盘区链
以空闲盘区（可能含多个盘块）为单位
分配回收方法与动态内存分配类似
位示图法
位示图
利用二进制位来表示盘块的使用情况，0为空闲，1为已分配
将盘块按表格列出，其值为二进制数
盘块分配
步骤
1. 顺序扫描位示图，从中找出一个或一组值为0的二进制位
2.找到的二进制位按行列计算出对应的盘块号
3. 令位示图中对应的二进制位为1
盘块回收
1. 将回收的盘块号转化为位示图的行列号
2.令对应行列号上的值为0
成组链接法
空闲表法和空闲链表法均不适用于大型文件系统，成组链接法结合上述两种方式，并克服了缺点
空闲盘块的组织
将全部的空闲盘块分成若干组，并链的形式连接
把每组的第一个盘块组成栈，栈内元素包含该组盘块数
分配与回收
以元素为单位进行弹栈/压栈
文件共享与文件保护
基于索引结点的共享方式
将共享文件或子目录的索引结点链接到多个用户的目录中，形成有向图
利用符号链实现文件共享
将共享的文件以链接文件的类型添加到其他用户的目录中，在访问时将工具链接文件内的路径读取原文件
磁盘容错技术
第一级容错技术SFT-I
防止磁盘表面缺陷造成的数据丢失
技术
备份目录和文件分配表
热修复重定向
将磁盘的一部分作为热修复重定向区，用于存放当发现磁盘有缺陷时的待写数据
写后读校验方式
数据写入磁盘，又从磁盘上读取进行比较，保证写入正确
第二级容错技术SFT-II
防止磁盘驱动器和控制器故障导致系统不能正常工作
磁盘镜像
将同一磁盘控制器下的磁盘划分为主磁盘和备份磁盘，每次写入数据都需写入备份磁盘
缺点
降低磁盘利用率
磁盘双工
将两台磁盘控制器下的磁盘划分为主磁盘和备用磁盘
基于集群技术的容错
双击热备份、互为备份、公用磁盘等等模式
数据一致性控制
事务
定义
用于访问和修改数据项的程序单位，成功时以托付操作终止事务，失败时需执行夭折操作
事务记录
事务的运行信息（log），存储在稳定存储器中
恢复算法
方法
undo(Ti)：将所有被事务Ti修改过的数据恢复为修改前的数据
redo(Ti)：将所有被事务Ti修改过的数据设置为新值
对于完成操作的事务（已托付），执行redo；对于未完成操作的事务（无托付），执行undo
检查点
作用
将事务记录清理工作经常化。每隔一段时间将事务记录输入到稳定存储器中，同时将检查点输入
新的恢复算法
发生故障后，对最后一个检查点后的事务记录进行处理即可
并发控制
使用互斥锁实现顺序性
类似进程分配
共享锁
允许多个对象读，但不允许写
使用互斥锁和共享锁实现顺序性
在读取时，分配共享锁即可；在写入时，还需分配互斥锁
重复数据的数据一致性问题
重复文件的一致性
其中一个文件被修改时，同时也必须修改其他重复文件
盘块号一致性
对盘块进行空闲计数和分配计数，检查是否有重复或者缺失
链接数一致性检查
建立链接数表，检查索引结点中的共享链接数和表是否一致
文件与文件系统
文件、记录、数据项
数据项
基本数据项
描述对象的某种属性的字符集
组合数据项
由多个基本数据项组成，简称组项
记录
一组数据项的集合，描述一个对象在某方面的属性
能唯一标识记录的几个数据项的集合称为关键字
文件
由创建者所定义的、具有文件名的一组相关数据的集合
有结构文件
有若干记录组成
无结构文件
字符流
属性
文件名
用户通过文件名访问文件
文件类型
如源文件、可执行文件等
文件长度
文件的物理位置
文件的建立时间
文件类型和文件系统模型
按用途分
系统文件
由系统软件构成的文件，不允许用户读写
用户文件
用户所创建的文件
库文件
标准子例程集和常用的例程所构成的文件，允许用户调用，但不允许修改
按数据类型分
源文件
由源程序和数据构成的文件
目标文件
源程序经过编译后的文件
可执行文件
源程序编译链接后形成的文件
按存取控制属性分
只执行文件
用户只能调用执行，不能读写
只读文件
用户可以读取文件，但不能写文件
读写文件
用户可以读写
按组织形式和处理方式分
普通文件
用户文件、操作系统的代码文件、库文件等
目录文件
由文件目录组成，用于管理和实现文件系统功能的系统文件
特殊文件
将各类I/O设备都视为文件
文件系统模型
底层
对象及其属性
目录
磁盘存储空间
中层
对对象操纵和管理的文件集合
对文件存储空间、目录、读写等管理
高层
文件系统的接口
为用户提供，方便使用
命令接口
用户与文件系统交互
程序接口
用户程序与文件系统的接口
文件操作
基本操作
创建文件
删除文件
读文件
写文件
截断文件
将文件全部更新
设置文件的读写位置
使文件读写不是从其始端而是从所设置的位置开始
打开和关闭
打开
将指明文件的属性从外存检索并拷贝到内存打开文件表的表目中，并将该表目的索引返回给用户。（避免重复检索）
关闭
把指明文件从打开文件表中删除
其他文件操作
对文件属性
改变文件名、改变文件拥有者、改变文件访问权等等
对目录
创建/删除目录、改变当前目录等等
实现文件共享
文件的逻辑结构
文件逻辑结构的类型
定长记录
文件中所有的记录长度相同
变长记录
文件中各记录的长度不相同
记录的组织方式
顺序文件
记录按某种顺序排列
索引文件
为可变长记录设置索引表
索引顺序文件
结合上述两种，为文件建立分组索引表，每个表项表示一组记录的第一个记录位置
流式文件，由字符集构成
逻辑记录的排序
按时间或者字典序等方式排列，提高检索效率
读写操作
读写指针步长不变
读写指针步长为上一个记录长度
优缺点
优点
读写大批数据效率高
查找记录效率低
增加删除记录开销大
为变长记录设置索引表，每个表项对应文件中的一个记录，包含长度以及位置（指针）
为文件记录分组建立索引表，每个表项指向一组记录的第一个记录
直接文件和哈希文件
在对记录进行存取时，都需利用记录键值检索记录
直接文件
键值转换，记录键值觉得记录物理地址
哈希文件
通过哈希函数将键值转化为记录地址
外存分配方式
连续分配方式
每个文件分配一组相连接的盘块
访问容易、速度快
要求有连续的存储空间
必须实现知道文件的长度
链接分配
使用链式结构离散分配内存
隐式链接
在文件目录的目录项中，含有指向链接文件第一个和最后一个盘块的指针；每个盘块都含有指向下一个盘块的指针
随机访问低效
链接全靠指针，可靠性差
显式链接
将所有指向盘块的指针存放到一张链接表中并链接起来，该表称为FAT
效率高，查找在内存中进行
不要求连续空间
离散分配，提高外存利用率
增删改容易
FAT和NTFS技术
FAT12
以盘块为基本分配单位
簇
在进行盘块分配时，以簇为基本单位，簇是连续的偶数个盘块
问题
FAT表项少，对磁盘容量有严重限制
FAT16
改进：增加表项数
表项依旧不多
FAT32
改进：进一步增加表项数
减少磁盘空间浪费
表项多，运行速度慢
有最小空间限制，若低于最小空间则需转FAT16等
不向下兼容
NTFS
改进
进一步增加表项数
支持长文件名
具有系统容错、数据一致性等功能
磁盘组织
簇大小可随磁盘大小变化
文件组织
每个卷拥有一张MFT表，通过MFT表控制文件
卷
将一个物理磁盘划分为多个逻辑磁盘（卷）
索引分配
对FAT的改进
高效的直接存取
占用少量内存，FAT需要占用较大的内存
单级索引分配
为每个文件分配一个索引块（记录文件的所有盘块号）
花费较多的外存空间，每个文件都需分配一个索引块
多级索引分配
为索引块建立索引，提高文件的最大长度
混合索引分配
多种索引分配方式相结合
直接地址
直接指向盘块地址
一次间接地址
通过索引块表找到盘块
多次间接地址
通过多个索引块表找到地址
目录管理
要求
按文件名存取
提高目录的检索速度
文件共享
允许文件重名
文件控制块和索引结点
文件控制块（FCB）
FCB集合称为文件目录，一个FCB就是一个文件目录项
基本信息
文件物理位置
文件逻辑结构（有结构/无结构）
文件物理结构（顺序文件/链接文件/索引文件）
存取控制信息类
文件存取权限
使用信息
建立时间
上一次修改时间
当前使用信息（进程锁等）
索引结点
将文件名和FCB分开，使用文件名为FCB建立索引表，提高检索效率
磁盘索引结点
存放在磁盘上的索引结点
包含信息
文件主标识符、文件类型、文件存取权限、文件物理地址等
内存索引结点
当文件打开时，要将磁盘索引结点拷贝到内存索引结点中，并新增部分内容
新增信息
索引结点编号、状态、访问计数、链接指针等等
目录结构
单级目录
整个文件系统只建立一张目录表
查找速度慢
不允许重名
不便于文件共享
两级目录
为每一个用户建立单独的用户文件目录UTD，UTD的目录为MFD
提高检索速度
允许重名
不同用户可使用不同文件名访问同一个共享文件
多级目录结构
树状目录，MTD为根目录，数据文件为树叶，其他目录为树结点
FCB分为数据文件的FCB与目录文件的FCB
路径名
从MTD开始到达数据文件的目录名和数据文件名组成的字符串
当前目录
对各文件的访问基于当前目录（当前目录为某种意义上的根）
目录查询技术
访问过程
用文件名在目录中查询，找出FCB或索引结点，进而找到盘块号，最后通过磁盘驱动程序读入内存
线性检索法
在单级目录中，顺序查找指明文件
在树型目录中，按路径查找
哈希法
建立一张哈希索引文件目录，将文件名转化为索引值
自由主题
0 条评论
回复 删除
下一页
