导图社区 第四章文件管理
操作系统详细思维导图，文件是以硬盘为载体的存储在计算机上的信息集合，本图适合计算机相关专业期末复习，考研学习等。
计算机网络部分详细思维导图，网络应用模型分为C/S模型和P2P模型，本图适合计算机相关专业期末复习，考研学习等。
计算机网络部分详细思维导图，传输层提供端到端的通信（进程与进程），本图适合计算机相关专业期末复习，考研学习等。
计算机网络部分详细思维导图，网络互联是通过路由器进行网络互联和路由选择，异构网络的链路层和物理层均不同，本图适合计算机相关专业期末复习，考研学习等。
社区模板帮助中心，点此进入>>
英语词性
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
法理
刑法总则
【华政插班生】文学常识-先秦
【华政插班生】文学常识-秦汉
文学常识：魏晋南北朝
【华政插班生】文学常识-隋唐五代
民法分论
第四章-文件管理
1. 文件系统基础
I. 文件的概念
文件的定义
文件
以硬盘为载体的存储在计算机上的信息集合
文件的操作
i. 创建文件
分配内存空间
在目录中为新文件创建条目，该条目记录了文件名，在文件系统中的位置等
ii. 写文件
执行系统调用
指出文件名和要写入文件的内容
必须维护该文件的一个写指针
iii. 读文件
指出文件名和要读取文件的内容
必须维护该文件的一个读指针
iv. 文件重定位
文件寻址
将文件位置设置为指定值，不读写
文件的打开与关闭
打开文件
使用open系统调用将指定文件的属性（包括在外存的位置）复杂到内存的打开文件表的一个表目中，并将该编号（索引指针）返回给用户
OS维护一个包含所有打开文件的表（open-file table ）
注意事项
open完成后，后续对文件的任何操作都不再需要文件名，只需要open返回的指针
关联信息
文件指针
跟踪上次文件读写位置作为当前文件的指针
文件打开计数
当打开文件计数器为0时，表示文件不再使用，回收该文件的所有资源
文件磁盘位置
保存在内存
访问权限
保存在打卡文件表中
II. 文件的逻辑结构
I. 流式文件
无结构文件
如二进制文件或字符文件
只能通过穷举搜索的方式
II. 记录式文件
有结构文件
种类
i. 顺序文件
实现
顺序存储
链式存储
优点
批量操作时效率最高
缺点
只有顺序文件才能存储在磁盘上并有效工作
增删改查单条记录比较困难
N条记录平均查找N/2次
ii. 索引文件
定长记录
变长记录
只支持顺序查找
索引表
存取文件时，必需先查找索引表
结构
键
逻辑地址
iii. 索引顺序文件
原理
将顺序文件中的所有记录分成若干组，再为其建立一张索引表，在索引表中为每组第一条记录建立索引，其中含有该记录的关键字值和指向该记录的指针
查找长度
假设将N条记录分成根号N组，则平均查找长度为根号N
iv. 直接文件或散列文件
由散列函数实现记录键值与物理地址间的映射
III. 目录结构
1. 文件目录
包含有关文件的信息如属性，位置，所有权等
Windows中的文件夹
目录文件
将所有文件目录组织起来的文件
只有在NTFS格式下可设置目录权限
2. 文件控制块和索引结点
FCB
目的
实现“按名存取”
文件目录
FCB的有序集合，一个FCB就是一个文件目录项
基本结构
基本信息（文件名，文件物理位置和逻辑结构，物理结构等）
存取控制信息
使用信息
文件的建立和修改时间等
FCB必须连续存放
索引结点
基本原理
将文件名和文件的描述信息分开存放
文件的描述信息形成
文件目录中仅存放文件名以及指向该文件所对应i结点的指针
磁盘索引结点
存放在磁盘上的索引结点
UNIX每个文件都有唯一一个磁盘索引结点
（UNIX中所有设备都被视为特殊文件）
文件长度
以B为单位
3. 目录结构
I. 单级目录结构
文件不能重名
不便于文件共享
II. 两级目录结构
主文件目录（MFD）
记录用户名极其文件目录所在位置
用户文件目录（UFD）
记录该用户文件的FCB信息
不能对文件进行分类
III. 多级目录结构（树形目录结构）
查找效率低
IV. 无环图目录结构
实现了文件共享
为每个共享节点设置一个共享计数器
共享计数器为零时真正删除文件
任何修改都为其它用户可见
IV. 文件共享
1. 硬链接
基于索引结点实现的共享
（查找速度快）
设置链接计数count。当有用户共享该文件时，count加1，同时设置指向该索引节点的指针；当用户不在需要时，count值减1，并删除链接指针
当且仅当count=0时，才能删除文件
防止链接指针悬空
2. 软链接
基于符号链接实现的共享
存放访问的共享文件的路径名
（查找速度慢）
访问文件时，根据文件的路径名去查找，从而实现共享
1. 仅文件拥有者有指向索引结点的指针
其他用户仅有该文件的访问路径
2. 文件主删除文件后，其他用户只是按路径访问时失败了而已，无其他任何影响
3. 存在的问题就是：原文件被用户主删除后，又有其他用户在其目录下创建了同名文件，则会使原文件的共享用户访问到错误的文件
V. 文件保护
1. 口令保护
2. 加密保护
3. 访问控制
用户访问权限
文件属性
2. 文件系统的实现
I. 目录实现
线性列表
使用文件名和存储数据块的指针
最简单
不能重名
哈希表
以文件名作为key，获取value指针
查找迅速
插入删除简单
哈希表长度固定
哈希函数对表长的依赖性
II. 文件实现
研究内容
物理结构
文件的分配方式
磁盘非空闲块
文件存储空间的管理
磁盘空闲块
III. 文件分配方式
1. 连续分配
文件目录表中记录
文件名
开始位置
长度
产生外碎片
（“要多少，给多少”）
2. 链接分配
采用离散分配的方式
解决了外碎片
分类
1. 隐式链接
磁盘块分布在磁盘的任何位置，除最后一个盘快外，每个盘块指向下一块的指针
目录表中记录
起始盘快号
最后一个盘块号
访问任何一个盘快都要从第一个盘快访问
一个盘快损坏会造成后续盘快无法访问
2. 显式链接
将每个盘块末尾指针提取出来，单独存放在一张链表中
文件分配表（FAT）
在磁盘中仅设置一张
支持了直接访问
每个表项存放对应块的下一块链接指针（盘块号）
第一个盘快记录在目录中
还可以标记空闲磁盘块
FAT可以实现存储空间的管理
开机后常驻内存
提高了检索和访存效率
计算FAT所占空间问题
表项的位数必须是4的整数倍
如假设盘块大小1KB，对于1.2MB的软盘，FAT表占用1.8KB
3. 索引分配
将文件的所有盘快号都集中放在一起构成索引表（块）
索引块的地址则保存在目录表中
创建文件
先从空闲空间中取得一块
再将其地址写入到索引表
随机访问
无外碎片
易于增删
索引表占内存
每个文件必须有一个索引块
索引块尽可能小，但太下小又无法处理大文件
解决大文件
链接方案
将多个索引块链接起来
多层索引
第N层指向N-1层索引块
访问磁盘N+1次
混合索引
如10个直接地址项和1个一级索引1个二级索引和一个三级索引
IV. 文件存储空间的管理
1. 空闲表法
属于连续分配方式
为所有空闲区建立一张空闲盘快表，每个空闲区对应一个空闲表项
所有空闲区按始址递增排列
同样可采用首次适应等方法
回收时同样考虑前后空闲区的合并问题
表结构
第一个空闲盘快号
空闲盘块数
2. 空闲链表法
空闲盘快法
以盘块为单位进行链接
空闲盘区法
以盘区为单位进行链接
一个盘区包含了多个盘块
每个盘区上还应有本盘区的盘快数信息
3. 位示图法
用二进制的一位表示磁盘块的使用情况
位示图实际上就是一张二维表
如Linux
定位时注意行和列是从0开始编号还是1开始编号
4. 成组链接法
适用于大型文件系统
如UNIX
V. 提高磁盘IO的方法
1. 提前读
2. 延迟写
3. 虚拟盘（RAM）
用内存空间仿真磁盘
4. RAID（廉价磁盘冗余阵列）
支持并行传输
高可靠性
加快传输
做不到扩充磁盘容量
3. 磁盘的组织与管理
I. 磁盘结构
柱面
所有盘面中相对位置相同的磁道
磁头
决定盘面
扇区
磁盘地址结构
i. （柱面，盘面，扇区）
ii. 原因
可以减少磁头移动时间
读取信息时，所有磁头同步移动；锁定盘面时激活相应的磁头
II. 磁盘调度算法
I. 磁盘调度时间
1. 寻找时间
将磁头移动到指定磁道
Ts=m*n+s
n是磁道数，m是跨越一道的时间，s是启动磁头壁时间
2. 延迟时间
从磁道定位到目标扇区
Tr=1/（2r）
r为转速（转/时间）
3. 传输时间
真正读取信息时间
Tt=b/（r*N）
b是读取数据量，N是磁道总数据量
可以通过OS来优化
II. 典型调度算法
1. FCFS
公平
无“磁壁粘着”，下面三个算法都有
无饥饿现象
2. SSJF
每次处理离当前位置最近的磁道
有饥饿
3. SCAN（电梯调度）
磁头到达请求的磁道号的最值（不一定是磁道最两端）后原路返回至请求磁道号的另一最值处
默认LOOK
不利于远离磁头一端的访问请求
4. C-SCAN
磁头到达请求磁道号的其一最值后，马上回到另一最值处
默认C-Look
III. 减少延迟时间的其他方法
盘面扇区交替编号
盘面错位命名
III. 磁盘管理
1. 初始化
低级格式化（物理分区）
将新磁盘分成扇区
如确定扇区校验码所占位数
为每个扇区采用特别的数据结构
OS将自己的数据结构记录在磁盘上
将磁盘分成一个或多个柱面组成的分区（C盘等）
对物理分区逻辑格式化
创建文件系统（根目录等）
OS将初始文件系统的数据结构存储到磁盘上，包括空闲和已分配的空间和一个初始为空的目录
2. 引导块
计算机运行时需要运行一个初始化程序（自举程序）
自举程序通常保存在ROM中
只在ROM中保存很小的自举装入程序
启动磁盘（系统磁盘）
拥有启动分区的磁盘
装了完整功能的自举程序
3. 坏块
使系统不去使用坏块
硬件故障
OS不能修复
