导图社区 操作系统之文件系统
王道操作系统之文件系统思维导图，有助于帮助您熟悉知识要点，加强记忆。有需要的同学，可以收藏下哟。
社区模板帮助中心，点此进入>>
论语孔子简单思维导图
《傅雷家书》思维导图
《童年》读书笔记
《茶馆》思维导图
《朝花夕拾》篇目思维导图
《昆虫记》思维导图
《安徒生童话》思维导图
《鲁滨逊漂流记》读书笔记
《这样读书就够了》读书笔记
妈妈必读：一张0-1岁孩子认知发展的精确时间表
文件系统
文件和文件系统
文件的数据组成
数据项（字段）
构成文件的基本单位，是数据组织中可以命名的最小逻辑单位
基本数据项：单个数据项 组合数据项：若干个数据项集
记录
是一组相关数据项的集合，描述一个对象在某方面的属性
关键字：记录的唯一标志，由单个或组合数据项形成
定长记录、变长记录
文件
由创建者所定义、具有文件名的若干相关元素的集合
有结构文件：若干个记录构成的文件 无结构（流式）文件：由字节/字符组成的文件（不存在内部结构）
文件类型
用途：系统文件、用户文件、库文件
数据形式：源文件、目标文件、可执行文件
存取控制：只执行文件、只读文件、读写文件
负责管理和存取文件信息的软件机构。由相应的数据结构，管理软件以及访问文件的一组操作组成
文件系统操作（三部曲）
打开文件：在内存设置对文件操作的相关数据结构，并将文件基本信息复制到内存
读写等文件操作
关闭文件：删除在内存中设置的数据结构，并将必要的文件修改信息刷新到磁盘
文件的逻辑结构
基本概念
虚拟技术
逻辑文件：从用户的角度看到的文件，用户可以直接操作的数据及其结构，独立于文件的物理特性
物理文件：从系统角度看到的文件，是文件在外存上的存储组织方式
文件目录：逻辑文件到物理文件的映射
顺序文件
按照一定顺序储存和组织记录（通常按照顺序方式进行文件的读写）
顺序文件的读写
设置读、写指针（由系统负责更新，对程序员透明）
打开文件：Rptr=0，Wptr=0
后续读写文件： （变长记录）每次加Li， （定长记录）每次加定长L
批量顺序存取，效率非常高 查找或修改单条记录困难 插入删除记录 困难
索引文件
在顺序文件的基础上，增加一张索引表，存放每条记录的关键字与其在文件中的位置
索引文件读写
根据索引表，由关键字找到记录在文件中的位置，然后调整读、写指针，进行记录的读写
支持记录直接存取 当记录数量很大时，索引表会占用额外存储空间
索引顺序文件
为一组记录在索引表中建立一个索引项，并非为每一个记录建立索引项（按关键字分组或按记录号分组）
读/写过程
首先根据索引表，找到记录所在分组的起始位置，调整读写指针，顺序查找，直到找到所要读写的记录
支持记录直接存取 大大降低了索引表的存储空间和I/O、计算开销
直接文件（用于小型文件）
根据记录的关键字（记录号），经过简单的计算（使用哈希函数），得到记录在文件的位置
首先根据HASH函数，有关键字（记录号）计算记录在文件的位置，调整读写指针，并进行读写
支持记录直接存取 脱离索引表，存取空间和I/O，计算开销大大降低
文件的物理结构 （外存分配方式）
连续分配
为每个文件分配一组相邻的磁盘块，且文件的逻辑记录的顺序和存储磁盘块的块号顺序一致，形成的文件结构称为顺序文件结构，物理文件称为顺序文件
顺序访问容易，速度快 支持逻辑记录直接存取 要求连续的存储空间 必须事先知道文件的长度 容易造成碎片
链接分配
每一个文件分配一组不相邻的磁盘块，且文件逻辑记录顺序和磁盘块号的顺序也不一致
隐式链接
单链表结构，各存储块指向下一个存储块的块号，形成的文件结构是链接文件结构，物理文件称为链接文件
不存在外部碎片问题 有利于插入和删除 有利于文件动态的增长和减小 读写时需要更多的寻道次数和寻道时间，存取时间慢 不适合随机存取，“单线联系” 容错性差，如果中间一个存储块的指针出故障，后面的存储块访问不到
显式链接
设置文件分配表（FAT），集中存储所有的磁盘块号信息，单链表的集中存储
不存在外部碎片问题 支持记录的插入和删除 有利于文件动态的增长和减小 读写时需要更多的寻道次数和寻道时间，存取时间慢 支持随机存取 安全性容错性比隐式好
索引分配
设置索引表，存储分配到的物理块号，形成的文件结构是索引文件结构，物理文件是索引文件
单级索引
假设磁盘块尺寸为4KB，磁盘块号为32bits = 4byte 每一个磁盘块可以存储磁盘数量是 4K/4 = 1K 单级索引支持的文件尺寸为1K*4K=4M 索引表占用的空间是4K
二级索引
二级索引支持的文件尺寸为1K*1K*4K = 4G 索引表占用的空间是4K +1K*4K
混合索引分配
直接地址（10个）10*4K=40K 一级间接地址：1K*4K= 4M 二级间接地址：1K*1K*4K = 4G 三级间接地址：1K*1K*1K*4K=4T 总计：40K + 4M + 4G + 4T
既能顺序存取，也能随机存取 索引表本身带来了开销
目录管理
”按名存取“（逻辑文件名称）、提高文件目录检索速度、文件共享、允许文件重名
文件控制块（FCB）
文件信息的数据结构、管理和读写文件。基本信息类、存取控制信息类、使用信息类
文件目录：看作文件控制块FCB数组
检索效率问题：FCB中大量信息用不到，只是放文件名和扩展名，就可以查找更多些信息
索引结点
文件名和文件的其余属性分开，前者构成文件目录，后者形成索引结点，两者通过索引结点编号相连
磁盘索引结点
存放在磁盘，除文件名外的文件属性信息
内存索引结点
除包含复制的磁盘索引结点信息外 索引结点的编号、状态、访问计数 文件所属的文件系统的逻辑设备号、链接指针
目录结构
单级目录结构
只建立一张目录表（组成一张线性表），每一个文件占用一个目录项
查找速度慢 不允许重名 不便于文件共享
二级目录结构
在主文件的基础上，允许每一个用户建立一张目录表，文件存放在各用户子目录下
解决了重名问题、提高检索效率、便于用户间文件共享
多级目录结构
允许目录下都可以建立子目录，文件可以存放到任意子目录下
彻底解决重名、提高检索效率、（逻辑文件名，路径名保证唯一性）
路径名
绝对路径名：以根结点为起点的路径名 例：E/M
相对路径名：以除根结点外的任意结点为起点的路径名 /B/E/M
目录查询技术 （逻辑文件到物理文件的映射）
线性检索法：分解路径名各组成部分，依次查找各目录名和文件名 基于索引结点的文件目录检索
首先读入第一个文件分量名，从根目录中的文件名进行比较，找到匹配项的索引结点，再通过索引结点找到该文件分量名放在多少号磁盘块中......（后面依次类推）
文件存储空间管理
空闲表法
为外存所有空闲区建立一张空闲表，每一个空闲区对应一个空闲表项
系统为所有外存空闲区拉成一个空闲盘区（块）链 空闲盘块链：结点代表一个空闲盘块； 空闲盘区链：结点代表一个空闲盘区；
位示图法
用二进制的位表示磁盘中一个盘块的使用情况，“0”表示盘块空闲，“1”表示已经分配
磁盘块号是b，行号i，列号j，位示图宽度n i=b/n ， j=b%n b=i*n + j
成组链接法（UNIX）
利用链栈存储所有空闲磁盘块号，每一个结点存储一组（例如100个）磁盘块号，其中最后一个磁盘块号指向下一组所在的磁盘块
磁盘初始化：内存设置空闲盘块号栈，存储一组空闲磁盘块号，读磁盘上链栈的栈顶点到内存，初始化空闲盘块号栈
盘块回收过程
回收的磁盘块号，直接存入内存空闲盘块号栈
如果栈满，则将栈中数据写回这个回收的磁盘块，清空内存空闲盘块号栈，将回收的磁盘块号入栈。
盘块分配过程
直接从内存空闲盘块号栈中，出栈一个盘块号，分配出去
如果是栈中最后一个盘块，出栈这个盘块，将该盘块中的数据调入到内存空闲盘块号栈中，再分配这个最后一个盘块
文件共享
基于索引结点的共享
原理：利用不同文件名指向相同的索引结点
过程：当C目录创建一个文件形成一个索引结点，Owner=C、Count=1。 B目录要共享这个文件指向这个索引结点，Owner=C、Count=2。 当删除C文件后，B文件仍指向这个索引结点，Owner=C、count=1。 （当Count=0时，文件才会被彻底删除）
基于符号链的共享
原理：利用符号链文件，其中存储被共享的文件路径名称（符号链就是路径名，例如\C\A）
数据一致性控制
数据一致性：保存在多个文件中的同一数据，在任何情况下都必须保证相同
事务机制
事务是一些列相关数据项的读写操作（事务的执行必须保持原子操作性）
实现一致性控制
设置事务日志，按时间顺序存放事务记录，包括①开始事务②读写操作③托付事务（正常事务结束）④夭折事务（异常事务结束）
读写数据之前，必须先写事务日志
事务记录
事务名、数据项名、旧值、新值
事务的崩溃
在事务托付前出现崩溃点，那么之前修改的所有事务记录全部恢复成旧值，使用Undo<Ti>
在事务托付后出现崩溃点，将之前修改的数据项重置为新值，并能够存入磁盘中，使用Redo<Ti>
检查点机制
定时刷新事务日志记录和被修改数据到稳定存储器（解决了随着时间的推移，记录的数据越来越多，一旦发生故障，事务记录清理起来就会非常费时）
恢复算法：仅对最后一个检查点后的记录进行处理
