文件管理
2021-05-07 07:14:47 18 举报AI智能生成
登录查看完整内容
操作系统文件管理脑图
作者其他创作
大纲/内容
文件管理
初识文件管理
概念
数据
数据项
基本数据项（字段）
组合数据项
记录
一组相关数据项的集合
关键字是唯一能标识一个记录的数据项
文件
结构文件
文件由若干个相关记录组成
非结构文件
文件被看成一个字符流
文件属性
文件类型
文件长度
文件的物理位置
文件的创建时间
按用途
系统文件
用户文件
库文件
按数据的形式
源文件
目标文件
可执行文件
按存取控制属性
只执行文件
只读文件
读写文件
按组织形式和处理方式
普通文件
是由ASCII码或二进制码组成的字符文件
目录文件
是由文件目录组成的文件
特殊文件
特指系统中的各类I/O设备
文件定义：一组有意义的信息的集合
文件属性：文件名、标识符、类型、位置、大小、保护信息...
文件系统的组成
与文件管理相关的软件
被管理文件
实施文件管理所需的数据结构
完成的功能
文件内部应该如何被组织起来（文件的逻辑结构）（文件组织）
逻辑结构的要求
首先是有助于提高对文件的检索速度
其次是该结构应方便对文件进行修改
第三是降低文件存放在外存上的存储费用，即尽量减少文件占用的存储空间
文件逻辑结构分类
无结构文件
系统中运行大量的源程序、可执行文件、库函数等所采用的
文件长度以字节为单位。利用读、写指针来指出下一个要访问的字符
有结构文件
信息管理系统和数据库系统中广泛采用
顺序文件
链式存储
无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始一次往后查找
顺序存储
排列方式
串结构：记录顺序与关键字无关，按存入时间的先后进行排序。检索每次必须从头开始，检索费时。
顺序结构：记录按关键字顺序排列，可以利用查找算法进行检索，有更高的检索速度和效率。
可变长记录的顺序文件无法实现随机存取，定长记录可以
定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）
优缺点
所有逻辑文件中顺序文件的存取效率是最高的
缺点
不方便增加/删除记录
交互应用性能差
最佳应用场合：在对文件中的记录进行批量存取时（即每次要读或写一大批记录）
记录寻址
为了访问顺序文件中的一条记录，首先应找到该记录的地址
方法
隐式寻址
定长记录
下一条记录的首地址 = 上一条记录的首地址 + 记录长度
变长记录
下一条记录的首地址 = 上一条记录的首地址 + 上一条记录的记录长度
访问指定记录必须扫描或读取前面的所有记录，访问速度较慢
显示寻址
可对定长记录文件实现直接或随机访问，对变长记录文件不能利用显式寻址方式实现直接或随机访问。
两种方式实现定长记录的随机访问
利用关键字
通过文件中记录的位置
索引文件
建立一张索引表，每个记录对应一个表项，各记录不用保持顺序，方便增加/删除记录
索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可以支持随机存取
若索引表按关键字排列，则可支持快速检索
解决了顺序文件不方便增加/删除记录的问题，同时让不定长记录的文件实现了随机存取，提高了对文件的查找速度，但索引表可能占用很多空间
主要用于对信息处理的及时性要求较高的场合
索引顺序文件
将记录分组，每组对应一个索引表项
检索记录时先顺序查索引表，找到分组，再顺序查找分组
当记录过多时，可建立多级索引表
特征
保留了顺序文件的关键特征
记录是按关键字的顺序组织起来
新的特征
1、引入文件索引表，实现对索引顺序文件的随机访问
2、增加了溢出文件，用它来记录新增加的、删除和修改的记录
文件应如何存放在外存中（文件的物理结构（文件的实现）
文件的分配方式
连续分配（连续组织方式）
为每个文件分配一组相邻接的盘块。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。
优点
1、顺序访问容易
2、顺序访问速度快
1、要求为一个文件分配连续的存储空间，会产生许多外部碎片，严重地降低了外存空间的利用率
2、必须事先知道文件的长度
3、不能灵活地删除和插入记录
4、对于动态增长的文件，很难知道最终大小，难为其分配空间；即时知道，在采用预分配存储空间时，也会使大量的存储空间长期空闲
只适用于长度固定的文件
链接分配（链接组织方式）
隐式链接
在文件目录的每个目录项中，都须含有指向链接文件第一块盘块和最后一个盘块的指针
缺点：只适合于顺序访问，它对随机访问是极其低效的
显式链接
把用于链接文件各物理块的指针显式地存放在内存的一张链接表中（文件分配边FAT）
1、不能支持高效的直接存取
2、FAT需占用较大的内存空间
索引分配（索引组织方式）
单级索引组织方式
为每个文件分配一个索引块（表），把分配给该文件的所有盘块号记录在该索引块中。在建立一个文件时，只须在为之建立的目录项中填上指向该索引块的指针
优点：支持直接访问；不会产生外部碎片；文件较大时，索引分配方式优于链接分配方式
缺点：对于小文件采用索引分配时，索引块的利用率低
多级索引组织方式
缺点：在访问一个盘块时，其所需启动磁盘的次数随着索引级数的增加而增多
增量式索引组织方式
同时兼顾小、中、大及特大型作业，采用多种组织方式来构成文件的物理结构
文件存储空间管理
空闲表法
空闲表中记录每个连续空闲区的起始盘块号、盘块数
分配时采用首次适应、最佳适应等策略；回收时注意表项的合并问题
空闲链表法
空闲盘块链
以盘块为单位组成一条空闲链
分配时从链头依次取出空闲块；回收时将空闲块插到链尾
分配与回收的过程简单；分配与回收的效率较低；空闲盘块链较长
空闲盘区链
以盘区为单位组成一条空闲链
分配时采用首次适应、最佳适应等策略；回收时注意相邻空闲盘区合并的问题
分配与回收的过程复杂；分配与回收的效率较高；空闲盘块链较短
位示图法
一个二进制位对应一个盘块。（字号，位号）或（行号，列号）与盘块号一一对应
盘块号-->(字号，位号）之间的转换公式
m X n位示图，b 盘块号
分配 b = n(i-1)+j
回收
i = (b-1) DIV n + 1
j = (b -1)MOD n + 1
优点：很容易找到一个或一组相邻接的空闲盘块
常用于微型机和小型机
成组链接法
UNIX采用的策略，适合大型文件系统。
文件之间应该如何组织起来（目录结构）
文件目录的实现
文件控制块（实现文件目录的关键数据结构）
基本信息
文件名、文件物理位置、文件逻辑结构...
存取控制信息
文件主的存取权限、核准用户的存取权限以及一般用户的存取权限
使用信息
建立日期和时间、文件上一次修改时间、打开该文件的进程数...
一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
目录管理的要求
实现按名存取（最基本的功能）
提高对目录的检索速度
文件共享
允许文件重名
目录结构
单级目录结构
一个系统只有一张目录表，不允许文件重名
简单，只能实现目录管理中最基本的功能--按名存取
不满足文件目录其他三个要求
查找速度慢
不允许重名
不便于实现文件共享
两级目录结构
不同用户的文件可以重名，但不能对文件进行分类
用户文件目录（UFD） 主文件目录（MFD）。每个用户目录文件都占MFD的一个目录项，其目录项中包含用户名和指向该用户目录文件的指针
基本满足文件目录四方面的要求
用户的隔离会使用户之间不便于共享文件
多级目录结构（树形目录结构）
不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
系统根据“文件路径”找到目标文件
从根目录出发的路径是“绝对路径”
从当前目录出发的路径是“相对路径”
不适合文件共享，其他用户必须经过其属主目录来访问该文件。
无环图目录结构
在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
为共享结点设置一个共享计数器，计数器为0时才真正删除该结点
索引结点（对文件控制块的优化）
除了文件名之外的所有信息都放到索引表中，每个文件对应一个索引结点
目录项中只包含文件名、索引指结点针，因此每个目录项的长度大幅减少
由于目录项长度减少，因此每个磁盘块可以存放更多的目录，因此检索文件时磁盘I/O的次数就少了很多
目录查询技术
线性检索法
Hash方法
操作系统应向上提供哪些功能（create、delete、open、close、read、write 系统调用）
最基本的文件操作
创建文件
分配外存空间，创建目录项
删除文件
回收外存空间，删除目录项
写文件
根据写指针、写出数据量、内存位置 将文件数据从内存写出外存
读文件
根据读指针、读入数据量、内存位置 将文件数据从外存读入内存
设置文件的读/写位置
改顺序存取为随机存取
文件的打开和关闭操作
打开文件
将目录项中的信息复制带内存中的打开文件表中，并将打开文件表的索引号返回给用户
打开文件时并不会把文件数据直接读入内存。“索引号”也称“文件描述符“
打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
每个进程都有自己的打开文件表，系统中也有一张总的打开文件表
进程打开文件表中特有的属性：读写指针，访问权限（只读？读写）
系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该进程）
关闭文件
将进程打开文件表中的相应表项删除
系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项
其他文件操作
有关文件属性的操作
有关目录的操作
实现文件共享的系统调用
对文件系统进行操作的系统调用
操作系统如何管理外存中的空闲块（存储空间的管理）
存储空间的划分与初始化
文件卷（逻辑卷）
目录区与文件区
目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
几种管理方法
操作系统需要提供的其他文件管理功能
文件共享（静态共享方法）
基于有向循环图DAG实现文件共享
有向无循环图
允许一个文件可以有多个父目录，从而以对称的方式实现文件共享
问题
当前用户对共享文件的盘块的增加对其他用户不可见，新增的这部分内容不能被共享
索引结点（硬链接）
各个用户的目录指向同一个索引结点
索引结点中需要链接计数count
某用户想删除文件时，只要删除该用户的目录项，且count--
只有count == 0 时才能真正删除文件数据和索引结点，否则会导致指针悬空
利用符号链接实现文件共享
软链接（符号链接）
在一个Link型的文件中记录共享文件的存放路径（Windows快捷方式）
操作系统根绝路径一层层查找目录，最终找到共享文件
即使软链接指向的共享文件已经被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败（找不到对应目录项）
由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/o，因此用软链接访问共享文件的速度比硬链接慢
符号链接的一个很大的优点：网络共享只需提供该文件所在机器的网络地址及该机器中的文件路径
文件保护
口令保护
为文件设置一个：口令“，用户想要访问文件时需要提供口令，由系统验证口令是否正确
实现开销小，但“口令”一般存放在FCB或索引结点中（也就是存放在系统中），因此不太安全
加密保护
用一个"密码"对文件加密，用户想要访问文件时，需要提供相同的“密码”才能正确的解密
安全性高，但加密/解密需要耗费一定的时间（Eg:异或加密）
访问控制
用一个访问控制列表（ACL）记录各个用户（或各组用户）对文件的访问权限
对文件的访问类型可以分为：读/写/执行/删除等
实现灵活，可以实现负责的文件保护功能
影响安全的因素及采取的措施
人为因素
通过存取控制机制
系统因素
采取系统容错技术
自然因素
建立后备系统
文件系统的层次结构
用户调用接口（第0级）
文件目录系统（第1级）
存取控制模块（第2级）
逻辑文件系统与文件信息缓冲区（第3级）
物理文件系统（第4级）
第五级
辅助分配模块
设备管理程序模块
磁盘管理
磁盘的结构
磁道、扇区、盘面
扇区是磁盘可寻址的最小存储单元，磁盘地址用”柱面号.盘面号.扇区号（或块号）“表示
分类
磁头是否固定
固定头磁盘
活动头磁盘
磁盘可否移动和替换
固定盘磁盘
大容量磁盘
并行方式读写
可换盘磁盘
中小型磁盘设备
串行方式读写
磁盘访问时间
寻道时间：启动磁臂、移动磁头所花的时间
与磁盘调度算法有关
旋转延迟时间：将目标扇区转到磁头下面所花的时间
与磁盘旋转速度相关（线性相关）
传输时间：读/写 数据花费的时间
磁盘调度算法
磁盘调度的目标是使磁盘的平均寻道时间最少
早期的磁盘调度算法
先来先服务（FCFS）
按访问请求到达的先后顺序进行处理
最短寻道时间优先（SSTF）
要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道的时间最短
每次都优先响应距离磁头最近的磁道访问请求
贪心算法的思想，能保证局部最优，但无法保证总的寻道时间最短
缺点：可能会出现饥饿现象
基于扫描的磁盘调度算法
扫描算法（电梯算法、SCAN）
双向扫描
只有磁头移动到最边缘的磁道时才改变磁头移动方向
缺点：对各个位置磁道的响应频率不平均
循环扫描算法（C-SCAN）
单向扫描
只有磁头朝某个方向移动时才响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求
NStepSCAN算法
将磁盘请求队列 分为若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而没处理一个队列时又是按SCAN算法
N= 1，N步SCAN算法便退化为FCFS算法
FSCAN算法
FSCAN只将磁盘请求队列分为两个子队列
1、当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理
2、在扫描期间，将新出现的所有请求磁盘I/O的进程放入等待处理的请求队列
低频考点
LOOK算法
SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向
C-LOOk算法
C-SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回
磁盘初始化
低级格式化/物理格式化：划分扇区
磁盘分区（C盘、D盘）
逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空间管理的数据结构
引导块
计算机启动时需要运行初始化程序（自举程序）来完成初始化
ROM中存放很小的自举装入程序
完整的自举程序存放在初始块（引导块）中
坏块的管理
简单的磁盘：逻辑格式化时将坏块标记出来
坏块对操作系统不透明
复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区
在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化
坏块对操作系统透明
0 条评论
回复 删除
下一页
