01.初始文件管理
文件的定义
- 一组有意义的信息的集合。
文件的属性
- 文件名、标识符、类型、位置、大小、保护信息等。
- 文件内部应该如何被组织起来(文件的逻辑结构)
- 文件之间应该如何被组织起来(目录结构)
- 操作系统应该向上提供哪些功能(
create、delete、open、close、read、write
系统调用) - 文件应如何放在外存中(文件的物理结构)
- 操作系统如何管理外存中的空闲块(存储空间的管理)
操作系统需要提供的其他文件管理功能
文件共享
文件保护
02.文件的逻辑结构
2.1无结构文件
无结构文件
- 文件内部的数据就是一系列二进制流或字符流组成。又称“
流式文件
”。
- 文件内部的数据就是一系列二进制流或字符流组成。又称“
2.2有结构文件
有结构文件
- 由一组相似的记录组成,又称“
记录式文件
”。 - 每条记录有若干个数据项组成。
- 如:数据库表文件。一般来说,每条记录有一个数据项可作为
关键字
(作为识别不同记录的ID)。 - 根据各条记录的长度(占用的存储空间)是否相等,又可分为
定长记录
和可变长记录
两种。
- 由一组相似的记录组成,又称“
2.3有结构文件的逻辑结构
顺序文件
- 文件中记录一个接一个地顺序排列(逻辑上),记录可以是
定长
的或可变长
的。 各个记录在物理上可以
顺序存储
或链式存储
。链式存储
:无论是定长/可变长记录,都无法实现随机存取,每次只能从第一个记录开始依次往后查找。顺序存储
:可变长记录
:无法实现随机存取
。每次只能从第一个记录开始依次往后查找。定长记录
:可实现随机存取
。记录长度为L,则第i个记录存放的相对位置是i*L。若采用串结构,无法快速找到某关键字对应的记录。- 若采用
顺序结构
,可以快速找到某关键字对应的记录
(如折半查找)
- 文件中记录一个接一个地顺序排列(逻辑上),记录可以是
索引文件
- 建立一张索引表,每个记录对应一个表项。各记录不用保持顺序,方便增加/删除记录。
索引表本身就是定长记录的顺序文件
,一个索引表项就是一条定长记录,因此索引文件可支持随机存取。若索引表按关键字顺序排列,则可支持快速检索
。- 解决了顺序文件不方便增/删记录的问题,同时让不定长记录的文件实现了随机存取。但索引表可能占用很多的空间。
索引顺序文件
- 将记录分组,每组对应一个索引表项。
- 检索记录时先顺序查索引表,找到分组,再顺序查找分组。
- 当记录过多时,可建立多级索引表。
03.文件目录
3.1文件控制块(实现文件目录的关键数据结构)
- 一个文件对应一个FCB,一个FCB就是一个目录项,多个FCB组成文件目录。
- 对目录的操作:
搜索、创建文件、删除文件、显示文件、修改文件
。
3.2目录结构
单级目录结构
- 一个系统只有一张目录表,
不允许文件重名
。
- 一个系统只有一张目录表,
两级目录结构
- 不同用户的文件可以重名,但
不能对文件进行分类
。
- 不同用户的文件可以重名,但
多级(树形)目录结构
- 不同目录下的文件可以重名,可以对文件进行分类,
不方便文件共享
。 - 系统根据“文件路径”找到目标文件。
- 从根目录出发的路径是“
绝对路径
” - 从“
当前目录
”出发的路径是“相对路径
”
- 不同目录下的文件可以重名,可以对文件进行分类,
无环图目录结构
- 在树形目录结构的基础上,增加一些指向同一节点的有向边,使整个目录成为一个有向无环图。
- 为共享结点设置一个共享计数器,
计数器为0时才真正删除该结点
。
3.3索引结点(对文件控制块的优化)
除了文件名之外的所有信息都放到索引结点中,每个文件对应一个索引结点
。- 目录项中只包含文件名、索引结点指针,因此每个目录项的长度大幅减小。
- 由于目录项长度减小,因此每个磁盘块可以存放更多个目录项,因此检索文件时磁盘I/O的次数就少了很多。
04.文件的物理结构
4.1文件块、磁盘块
4.2文件分配方式
连续分配
连续分配
方式要求每个文件在磁盘上占有一组连续的块
。- 读取某个磁盘块时,需要移动磁头。访问的两个磁盘块相隔越远,移动磁头所需时间就越长。
连续分配的文件在顺序读/写时速度最快
。- 物理上采用
连续分配,存储空间利用率低,会产生难以利用的磁盘碎片
。 优点
:支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快。缺点
:不方便文件拓展;存储空间利用率低,会产生持磁盘碎片。
链接分配
隐式链接
- 除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
优点
:很方便文件拓展,不会有碎片问题,外存利用率高。缺点
:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。
显式连接
- 把用于链接文件各物理块的指针显式地存放在一张表中,即
文件分配表
(FAT,File Allocation Table
)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存,并常驻内存
。 优点
:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问
。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高
。缺点
:文件分配表的需要占用一定的存储空间。
- 把用于链接文件各物理块的指针显式地存放在一张表中,即
索引分配
索引分配
允许文件离散地分配在各个磁盘中,系统会为每个文件建立一张索引表
,索引表中记录了文件的各个逻辑块对应的物理块
。(索引表的功能类似于内存管理中的页表--建立逻辑页面到物理页面之间的映射关系)。- 索引表存放的磁盘块称为
索引块
。 - 文件数据存放的磁盘块称为
数据块
。
链接方案
:如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。
多层索引
:建立多层索引(原理类似于多级页表
)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
混合索引
:多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引
(直接指向数据块
),又包含一级间接索引
(指向单层索引表)、还包含两级间接索引
(指向两层索引表)。
05.文件存储空间管理
存储空间的划分与初始化
- 文件卷(逻辑卷),目录区、文件区的概念。
目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据。
空闲表法
- 空闲表中记录每个连续空闲区的起始盘块号、盘块数。
- 分配时可采用
首次适应、最佳适应等策略;回收时注意表项的合并问题
。
空闲链表法
空闲盘块链
- 以
盘块
为单位组成一条空闲链。 - 分配时从链头依次取出空闲块,回收时将空闲块查到链尾。
- 以
空闲盘区链
- 以
盘区
为单位组成一条空闲链。 - 分配时可采用首次适应、最佳适应等策略;回收时注意相邻空闲盘区合并问题。
- 以
位示图法
- 一个二进制位对应一个盘块。(字号,位号)或(行号,列号)与盘块号一一对应。
重要考点
:要能够自己退出盘块号->(字号,位号)之间的相互转换公式。需要注意的题目条件
- 二进制位0/1到底哪个代表空闲,哪个代表不空闲。
- 字号、位号、盘块号到底是从0开始还是从1开始。
成组链接法
- UNIX采用的策略,适合大型文件系统。
06.文件的基本操作
创建文件
- 分配外存空间,创建目录项。
删除文件
- 回收外存空间,删除目录项。
打开文件
将目录项中的信息复制到内存中的打开文件表中,并将打开文件表的索引号返回给用户
。- 打开文件之后,对文件的操作不再需要每次都查询目录,可以根据内存中的打开文件表进行操作。
- 每个进程有自己的打开文件表,系统中也有一张总的打开文件表。
- 进程打开文件表中特有的属性:读写指针、访问权限(只读?只写?)
- 系统打开文件表中特有的属性:打开计数器(有多少个进程打开了该文件)
关闭文件
- 将进程打开文件表中的相应表项删除。
- 系统打开文件表的打开计数器减1,若打开计数器为0,则删除系统表的表项。
读文件
- 根据读指针、读入数据量、
内存位置将文件数据从外存读入内存
。
- 根据读指针、读入数据量、
写文件
- 根据写指针、写出数据量、内存位置将文件数据从内存写出外存。
07.文件共享
硬链接
- 各个用户的目录项指向同一个索引结点。
- 索引结点中需要有链接计数count
- 某用户想删除文件时,只是删除该用户的目录项,且count--。
- 只有count==0时才能真正删除文件数据和索引结点,否则会导致指针悬空。
软链接(符号链接)
- 在一个Link型的文件中记录共享文件的存放路径(Windows快捷方式)。
- 操作系统根据路径一层一层查找目录,最终找到共享文件。
- 即使软链接指向的共享文件已被删除,Link型文件依然存在,只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)。
- 由于用软链接的方式访问共享文件时要查询多级目录,会有多次磁盘I/O,因此用软链接访问。
08.文件保护
8.1口令保护
为文件设置一个“
口令
”(如:abc112233),用户请求访问该文件时必须提供“口令
”。- 口令一般存放在文件对应的
FCB
或索引结点
中。用户访问文件前需要先输入“口令”,操作系统会将用户提供的口令与FCB中存储的口令进行对比,如果正确,则允许该用户访问文件。
- 口令一般存放在文件对应的
优点
:保存口令的空间开销不多,验证口令的时间开销也很小。缺点
:正确的“口令”存放在系统内部,不够安全。
8.2加密保护
- 使用某个“密码”对文件进行加密,在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
优点
:保密性强,不需要在系统中存储“密码”。缺点
:编码/译码,或者说加密/解密要花费一定时间。
8.3访问控制
- 在每个文件的FCB(或索引结点)中增加一个
访问控制列表
(Access-Control List,ACL
),该表中记录了各个用户可以对该文件执行哪些操作。
09.文件系统的层次结构
- 用一个例子来辅助记忆文件系统的层次结构:
假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。
- 用户需要通过操作系统提供的接口发出上述请求——
用户接口
。 - 由于用户提供的是文件的存放路径,因此需要操作系统一层一层地查找目录,找到对应的目录项——
文件目录系统
。 - 不同的用户对文件有不同的操作权限,因此为了保证安全,需要检查用户是否有访问权限——
存取控制模块(存取控制验证层)
。 - 验证了用户的访问权限之后,需要把用户提供的“记录号”转变为对应的逻辑地址——
逻辑文件系统与文件信息缓冲区
。 - 知道了目标记录对应的逻辑地址后,还需要转换成实际的物理地址——
物理文件系统
。 - 要删除这条记录,必定要对磁盘设备发出请求——
设备管理程序模块
。 - 删除这些记录后,会有一些盘块空闲,因此要将这些空闲盘块回收——
辅助分配模块
。
- 用户需要通过操作系统提供的接口发出上述请求——
10.磁盘的结构
磁盘、磁道、扇区的概念
- 磁盘由表面涂有磁性物质的圆形盘片组成。
- 每个盘片被划分为一个个磁道,每个磁道又划分为一个个扇区。
如何在磁盘中读/写数据
- 磁头移动到目标位置,盘片旋转,对应扇区划过磁道才能完成读/写。
盘面、柱面的概念
- 磁盘有多个盘片“摞”起来,每个盘片有两个盘面。
- 所有盘面中相对位置相同的磁道组成柱面。
磁盘的物理地址
柱面号、盘面号、扇区号
。
磁盘的分类
根据磁头是否可移动
- 固定头磁盘(每个磁道有一个磁头)。
- 移动头磁盘(每个盘面只有一个磁头)。
根据盘片是否可更换
- 固定盘磁盘。
- 可换盘磁盘。
11.磁盘调度算法
11.1一次磁盘读/写操作需要的时间
寻找时间(寻道时间)
:启动磁臂、移动磁头所花的时间
。延迟时间
:将目标扇区转到磁头下面所花的时间。传输时间
:读/写数据花费的时间。
11.2先来先服务(FCFS)
- 按访问请求到达的先后顺序进行处理。
优点
:公平缺点
:如果有大量进程竞争使用磁盘,请求访问的磁道很分散,则FCFS性能很差,寻道时间长。
11.3最短寻找时间优先(SSTF)
- 每次都优先响应距离磁头最近的磁道访问请求。
- 贪心算法思想,能保证眼前最优,但无法保证总的寻道时间最短。
缺点
:可能导致饥饿。
11.4扫描算法(电梯算法、SCAN)
- 只有磁头移动到最边缘的磁道时才可以改变磁头移动方向。
缺点
:对各个位置磁道的响应频率不平均。
11.5循环扫描算法(C-SCAN)
- 只有磁头朝某个方向移动时才会响应请求,移动到边缘后立即让磁头返回起点,返回途中不响应任何请求。
11.6LOOK算法
- SCAN算法的改进,只要在磁头移动方向上不再有请求,就立即改变磁头方向。
11.7C-LOOK算法
- C-SCAN算法的改进,只要在磁头移动方向上不再有请求,就立即让磁头返回。
12.减少延迟时间的方法
交替编号
具体做法
:让编号相邻的扇区在物理上不相邻。原理
:读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区。
错位命名
具体做法
:让相邻盘面的扇区编号“错位”。原理
:与“交替编号”的原理相同。“错位命名法”可降低延迟时间。
磁盘地址结构的设计
- 为什么要用(
柱面号,盘面号,扇区号
)的结构。不用(盘面号,柱面号,扇区号)的结构。 原因
:在读取地址连续的磁盘块时,前者更不需要移动磁头
。
- 为什么要用(
13.磁盘的管理
磁盘的初始化
低级格式化/物理格式化
:划分扇区。- 磁盘分区(
C盘、D盘、E盘
)。 逻辑格式化
:建立文件系统(建立根目录文件、建立用于存储空间管理的数据结构)。
引导块
- 计算机启动时需要运行初始化程序(自举程序)来完成初始化。
- ROM中存放很小的自举装入程序。
- 完整的自举程序存放在初始块(引导块)中。
坏块的管理
简单的磁盘
:逻辑格式化时将坏块标记出来。复杂的磁盘
:磁盘控制器维护一个坏块链,并管理设备用扇区。
评论已关闭