OS-4-文件管理思维导图模板_ProcessOn思维导图、流程图

文件结构

逻辑结构

无结构文件

有结构文件

由记录组成，记录由若干数据项组成，可选其一作为关键字
根据其长度，可分为定长记录、可变长记录

顺序文件
记录顺序排列

串结构
记录顺序与关键字无关

顺序结构
记录顺序按关键字排列

一般不考虑链式存储的文件

索引文件
文件具有索引表

为文件记录建立索引表，索引表必须顺序存储。
索引表可看做定长记录表

可使可变长记录文件也可以随机存取和快速查找

索引顺序文件
将数据分组，建立索引表

索引表表项对应一组记录

一个表项对应的一组记录按顺序组织

可以建立多级索引表

物理结构
分配模式

顺序分配

要求文件在磁盘上占有连续的块

支持顺序读写、随机(直接)读写

在顺序读写时速度最快

不便于拓展(需要整体迁移)，产生磁盘碎片(可以紧凑，开销大)

链接分配

隐式链接分配
(默认)

每块末有一个指向下一块的指针

该指针用户不可见

不支持随机访问

显式链接分配

用专用的文件分配表FAT存储
某一个物理块指向下一块的指针

每个磁盘只有一张FAT，开机时读入并常驻内存。

由于表项大小一致，物理块号可以是隐藏的。

显著快于隐式链接，支持随机访问

索引分配

单级索引

为每个文件建立索引表

若物理块号长度固定
则表项可隐含逻辑块号

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

支持随机访问，易于实现文件拓展，文件很大时，索引表一块装不下，
而使用链接法链接索引块会使随机读取能力丧失，且会读取很多次内存，效率极低

多级索引

各层索引表不能大于一块

对于大小为s的磁盘块，表项大小为i，则一块可以存储s/i个表项
n级索引可以存储(s/i)个索引项。文件大小最大可为s(s/i)

对于n层索引，且顶级索引未调入内存，
访问一个块需要n+1次读磁盘

混合索引

顶级索引表既可以包含地址，也可以包含一级间接索引，还包含二级间接索引。

通常考察计算给定索引表的最大文件长度

求读磁盘次数是，注意顶级索引表是否已经调入内存

文件存储空间管理

存储空间划分、初始化

文件卷/逻辑卷
(C:、D:)

目录区和文件区

部分OS支持超大型文件，支持多个
物理磁盘组成一个文件卷

管理方法

空闲表

表项为首个空闲盘块号、连续空闲盘块数

分配

首次适应、最佳适应、最坏适应等

回收

注意表项合并

空闲链表法

空闲盘块链

以空闲物理块为单位成链

OS保存链头、链尾指针

分配

从链头开始逐个分配，完成后修改链头

回收

将空闲块逐个挂到链尾，完成后修改链尾

空闲盘区链

以空闲盘区为单位成链

盘区指连续物理块

盘区不一定等大

OS保存链头、链尾指针

分配

先按特定适应方式确定是否有整个盘区可供分配

若否，可以离散分配

分配完修改指针、盘区大小

回收

注意是否合并

不合并者，挂到链尾

位示图法

用二进制位代表盘区状态

字号，位号对应盘块：主要考察点

一般以连续的“字”存储。

掌握“块号↔字位号”

注意起始位是否是0号

分配

顺序扫描空闲块

回收

计算对应字位号，设为0

注意题目要求如何表示。

成组链接法
(UNIX超级块)

适用于大型文件系统

？

磁盘

基本概念

磁盘结构

磁盘按半径划分出磁道，按弧度范围划出扇区

扇区的存储量相同

越靠内数据密度越大

盘面、柱面

硬盘可能由多个盘片组成，其一面或两面称为盘面

所有盘片相对位置相同的磁道组成柱面

磁盘的物理地址

可由柱面号-盘面号-扇区号唯一确定一个磁盘块

之所以不以盘面-柱面-扇区为编址方案，
是因为柱面是唯一依赖磁臂移动的维度，
置于高地址可降低连续读写的磁臂负担

磁盘的读写

磁头对准磁道/柱面

激活指定盘面对应的磁头

扇区到达即可读写

分类

活动头磁盘

磁臂来回伸缩带动磁头指向磁道

固定头磁盘

磁头固定，每个磁道一个磁头

盘片是否可更换

可换盘磁盘

固定盘磁盘

磁盘调度

一次读写需要的时间

寻道时间

启动磁臂s

移动磁臂m/磁道

延迟时间

目标扇区转动到磁头下方
的时间

由于读完一个块需要一定时间处理，不能立即
读取下一扇区的块，读连续块需要额外转动多圈

传输时间

向磁盘磁道容量为N的磁盘写入
b字节的传输时间为

减少磁盘延迟

交替编号：逻辑上相邻的扇区在物理上有间隔

错位命名：不同的盘面对应的扇区编号不同

调度算法

FCFS

最短寻道时间
SSTF

可能饥饿

扫描算法
SCAN

磁头只有移动到最外磁道才能内移
磁头只有移动到最内磁道才能外移
来回扫描

亦称“电梯算法”

无饥饿，对各个磁道响应不均匀

改进：LOOK算法

若当前方向上没有
更多请求，立即换向

循环扫描
C-SCAN

单向扫描，回程不响应请求，快速回程

改进：C-LOOK算法

若当前方向上没有
更多请求，立即换向

回程只需要回程到
最开始的请求位置

磁盘管理

初始化

St1.低级格式化
(物理格式化)

将磁道划分为扇区

扇区头、尾

校验码等

数据区域

St2.磁盘分区
(按若干柱面组织)

分为不同的逻辑卷

St.3.逻辑格式化

创建文件系统、根目录、
位示图/空闲分区表等

引导块

由于开机需要的自举装入程序需要存在ROM中，更改不便，
可以将完整的自举装入程序存在磁盘中，由ROM中的引导程序指导装入，
以提高扩展性，存放自举装入程序的块称为引导块，亦称启动分区/启动块

引导块必须在磁盘的固定位置

拥有引导块的磁盘称为启动盘/系统盘

坏块处理

坏块是硬件故障，OS不可修复

若在FAT上对坏块进行标记，坏块对OS可见

若通过磁盘本身的“磁盘控制器”
硬件维护的坏块链表进行管理，
坏块对OS不可见

预留备用扇区作为替换
，称为扇区备用技术

基本概念

文件

有意义的信息/数据的集合

文件属性

文件名

同一目录下不允许文件重名

标识符

面向OS，全系统唯一

类型

便于指定打开方式

位置

存放路径(面向用户)
外存地址(面向OS)

保护信息

权限等

大小、上次修改、创建时间等

文件内部如何组织

无结构文件(流式文件)

有结构文件(记录式文件)

逻辑结构

文件之间如何组织

文件目录

OS应为上层提供功能

创建

Create系统调用
需要提供：大小、路径、名称

寻找空间

在对应文件目录中创建条目

删除

Delete系统调用
需要提供：路径、名称

回收磁盘块，删除目录项

读

Read系统调用
基于已经打开的文件
需要提供：进程打开
文件表的编号

需要名称和读入块的内存位置

搜索并找到目录项

进程维护一个读位置的指针
存储在进程的打开文件表中

写

Write系统调用

需要名称和读入块的内存位置

搜索并找到目录项

进程维护一个写位置的指针
存储在进程的打开文件表中
通常重用读指针

打开与关闭

不能简单理解为窗口的存在

OS打开文件表
只有一张

打开文件命

文件指针，对进程唯一

文件打开计数器
(OS打开文件表特有)

=0

回收资源

若文件被修改过，写回外存

文件磁盘位置

进程打开文件表

打开文件名

读写指针，对进程唯一
(进程打开文件表特有)

访问权限

系统表索引号

Open系统调用
需要：路径，名称，
操作类型(r/rw)

将对应文件目录项复制到打开文件表中

无需反复读目录，打开文件表均在内存中

返回一个打开文件表表项的索引号
即一个表项的指针，亦称为“文件描述符”

Close系统调用

对应OS表项的打开计数-1。

进程的打开文件表对应项删除

文件重定位
(文件寻址)

按条件搜索目录并将当前文件位置设为指定值
不会读写文件

截断

允许文件属性不变的同时删除文件内容，设其长度为0并释放空间

OS对存储硬件进行管理

文件的存储

在磁盘中块状存储

地址转换、逻辑地址、物理地址、块号、块内地址等

离散存储 vs 连续存储

磁盘块的管理

文件共享

基于索引结点的共享
(硬链接)

FCB的索引结点指针指向同一索引节点

设置引用计数以记录访问者数

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

创建一个包含被共享文件存放路径的文件
(类似Win快捷方式)

软链接的文件索引结点在创建时复制目标的引用计数

删除目录项会导致快捷方式找不到目标文件

IO操作很多，性能很差

有向无环图

文件保护

口令保护

要求用户访问时提供口令

口令存储在FCB中

存储和验证开销均小

系统内部存在口令，非常危险

加密保护

对文件进行加密，用户需要提供秘钥

系统保存密文

加密解密消耗一定时间

访问控制

FCB中增加访问控制表Access-Control List

表明不同用户对该文件操作的权限

用户很多时，存储ACL的开销很大，可以引入用户组来降低开销

实现灵活，可以实现复杂的文件保护

文件系统对访问权限采用继承策略

文件系统的层次结构

用户接口

向上层用户提供的简单易用的功能接口
处理用户的系统调用请求

文件目录系统

根据用户给出的路径找到相应的FCB或索引结点

存取控制模块

主要实现文件保护相关功能

逻辑文件系统与
文件信息缓冲区

根据上层给出的文件记录号
将其转换为逻辑地址

索引表从外存调出后存入缓冲区中

物理文件系统

将逻辑地址转换为实际物理地址

辅助分配模块

负责文件存储空间管理(分配、回收)

设备管理模块

直接与硬件交互，负责分配设备、分配
设备缓冲区、磁盘调度、启动/释放设备

拓展

UNIX：一切皆文件

全是字节流

文件目录

文件目录 &
文件控制块FCB

目录文件是一种有结构文件，一个表项对应一个文件

表项就是FCB，文件目录就是FCB的有序集合

FCB包含文件基本信息

实现了文件名和文件的映射
用户可以按名存取

FCB必须连续存放

方法

搜索

根据用户给出的文件名搜索目录中的FCB

创建文件

创建文件时将FCB插入目录

删除文件

删除对应FCB

显示目录

显示目录中的内容

修改目录

文件属性发生变化时，需要修改FCB的对应字段

索引结点
(i结点)

由于搜索只关心文件名，可以将其他文件属性放入索引节点，简化为一个索引指针

目录项可以只由文件名、索引指针构成

目录表大小降低，系统开销降低

一次IO只能读入一块，块数多时间显著增加

索引结点无需常驻内存

磁盘索引结点(未调入内存时)

内存索引结点(调入内存后)

增加一些信息，如是否被修改
同时访问者数等

目录结构

不允许文件重名

两级目录结构

分为主文件目录(MFD)和用户文件目(UFD)

允许不同用户拥有同名文件

实际上对应不同文件

用户无法对自己的文件分文件夹

多级目录结构(树形)

即现代OS目录

需要使用文件路径名标识文件

从根目录出发的路径称为绝对路径

从“当前目录”出发的路径称为相对路径

不便于实现文件共享

无环图目录结构
有向无环图

不同目录的数据项可以指向同一个文件

删除比较复杂

为被共享文件设置一个共享计数器，记录被共享次数

被删除则删除FCB，并计数器-1
直到计数器为0才真正删除