导图社区 第4章 文件管理
该模板是一张关于408考研,期末操作系统第四章文件管理思维导图,专为计算机专业学生、考研 / 软考备考者、计算机基础课程学习者打造,是系统梳理操作系统文件管理核心知识的高效学习工具。思维导图的结构化呈现方式,将文件的基本概念、文件的实现与管理、磁盘的组织与管理、文件系统四大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入高频考点标注、原理示意图,帮助使用者快速构建文件管理的知识体系,精准攻克文件分配方式、目录结构、磁盘调度算法等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将文件逻辑结构、物理分配方式、目录管理、磁盘调度算法、文件系统实现等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机基础课程学习者,模板清晰呈现了文件管理的核心概念、原理与经典算法,可用于入门学习、知识框架搭建,快速建立对操作系统文件管理逻辑的整体认知。模板完整覆盖文件管理核心考点:从文件的基本概念、逻辑结构与物理分配方式,到文件目录管理、磁盘的物理结构与调度算法,再到文件系统的层次结构、实现原理与性能优化,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。该模板借助万兴脑图软件绘制,助力计算机学习者高效掌握操作系统文件管理知识。
编辑于2026-05-07 15:44:52这是一篇关于408考研,期末考试,计算机组成原理,输入输出系统思维导图,专为计算机专业学生、考研(如 408 统考)/ 软考备考者、计算机硬件底层原理学习者打造,是系统梳理 I/O 系统核心知识的高效学习工具。思维导图的结构化呈现方式,将 I/O 系统的基本概念、I/O 接口、I/O 控制方式、中断处理流程四大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入高频考点标注、原理示意图与对比表格,帮助使用者快速构建输入 / 输出系统的知识体系,精准攻克 I/O 控制方式对比、DMA 传输原理、中断处理流程、磁盘调度算法等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将 I/O 接口的软硬件构成、程序查询 / 中断 / DMA 控制方式的差异、中断响应与处理全过程、磁盘调度计算等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机底层原理学习者,模板清晰呈现了主机与外设数据交互的完整逻辑,可用于入门学习、硬件原理学习的知识框架搭建,快速建立对计算机输入输出系统的整体认知。模板完整覆盖输入 / 输出系统核心考点:从 I/O 系统的基本概念、接口的分类与工作原理,到程序查询、中断、DMA 三种核心 I/O 控制方式的对比;从中断响应与完整处理流程,到磁盘调度算法、DMA 传输原理等计算类高频考点,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。该模板借助万兴脑图软件绘制,助力计算机学习者高效掌握输入 / 输出系统核心知识。
这是一篇关于408考研,期末考试,计算机组成原理,总线的思维导图,专为计算机专业学生、考研 / 软考备考者、计算机底层原理学习者打造,是系统梳理总线系统核心知识的高效学习工具。思维导图的结构化呈现方式,将总线概述、总线仲裁、总线操作和定时、总线标准四大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入关键原理示意图、性能计算要点与对比说明,帮助使用者快速构建总线系统的知识体系,精准攻克总线分类、仲裁方式、传输定时与性能分析等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将总线的特性与分类、集中式 / 分布式仲裁方式、同步 / 异步传输定时、总线性能指标计算等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机底层原理学习者,模板清晰呈现了计算机系统中各部件通过总线进行数据传输的完整逻辑,可用于入门学习、硬件原理学习的知识框架搭建,快速建立对计算机系统互连机制的整体认知。模板完整覆盖总线系统核心考点:从总线的基本概念、分类与特性,到总线仲裁的集中式与分布式实现;从总线操作的同步 / 异步 / 半同步定时方式,到总线标准与性能指标计算,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。
这是一篇关于408考研,期末考试,计算机组成原理,中央处理器的思维导图,专为计算机专业学生、考研 / 软考备考者、计算机底层原理学习者打造,是系统梳理 CPU 核心知识的高效学习工具。思维导图的结构化呈现方式,将 CPU 的功能和基本结构、指令执行过程、数据通路、控制器、指令流水线、多处理器系统六大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入高频考点标注、关键概念对比与计算要点,帮助使用者快速构建 CPU 工作原理的知识体系,精准攻克数据通路设计、流水线性能分析、中断处理流程等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将 CPU 结构、指令执行周期、数据通路设计、硬布线 / 微程序控制器对比、流水线冲突处理、多处理器系统分类等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机底层原理学习者,模板清晰呈现了 CPU 从指令取指到执行的完整工作流程,可用于入门学习、底层原理学习的知识框架搭建,快速建立对计算机核心部件的整体认知。模板完整覆盖中央处理器核心考点:从 CPU 的功能与基本结构、指令执行的完整过程,到数据通路的设计原理与分类;从硬布线与微程序控制器的工作原理与对比,到指令流水线的性能指标、冲突处理与多发技术;再到多处理器系统的基本概念与硬件多线程技术,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。
社区模板帮助中心,点此进入>>
这是一篇关于408考研,期末考试,计算机组成原理,输入输出系统思维导图,专为计算机专业学生、考研(如 408 统考)/ 软考备考者、计算机硬件底层原理学习者打造,是系统梳理 I/O 系统核心知识的高效学习工具。思维导图的结构化呈现方式,将 I/O 系统的基本概念、I/O 接口、I/O 控制方式、中断处理流程四大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入高频考点标注、原理示意图与对比表格,帮助使用者快速构建输入 / 输出系统的知识体系,精准攻克 I/O 控制方式对比、DMA 传输原理、中断处理流程、磁盘调度算法等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将 I/O 接口的软硬件构成、程序查询 / 中断 / DMA 控制方式的差异、中断响应与处理全过程、磁盘调度计算等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机底层原理学习者,模板清晰呈现了主机与外设数据交互的完整逻辑,可用于入门学习、硬件原理学习的知识框架搭建,快速建立对计算机输入输出系统的整体认知。模板完整覆盖输入 / 输出系统核心考点:从 I/O 系统的基本概念、接口的分类与工作原理,到程序查询、中断、DMA 三种核心 I/O 控制方式的对比;从中断响应与完整处理流程,到磁盘调度算法、DMA 传输原理等计算类高频考点,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。该模板借助万兴脑图软件绘制,助力计算机学习者高效掌握输入 / 输出系统核心知识。
这是一篇关于408考研,期末考试,计算机组成原理,总线的思维导图,专为计算机专业学生、考研 / 软考备考者、计算机底层原理学习者打造,是系统梳理总线系统核心知识的高效学习工具。思维导图的结构化呈现方式,将总线概述、总线仲裁、总线操作和定时、总线标准四大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入关键原理示意图、性能计算要点与对比说明,帮助使用者快速构建总线系统的知识体系,精准攻克总线分类、仲裁方式、传输定时与性能分析等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将总线的特性与分类、集中式 / 分布式仲裁方式、同步 / 异步传输定时、总线性能指标计算等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机底层原理学习者,模板清晰呈现了计算机系统中各部件通过总线进行数据传输的完整逻辑,可用于入门学习、硬件原理学习的知识框架搭建,快速建立对计算机系统互连机制的整体认知。模板完整覆盖总线系统核心考点:从总线的基本概念、分类与特性,到总线仲裁的集中式与分布式实现;从总线操作的同步 / 异步 / 半同步定时方式,到总线标准与性能指标计算,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。
这是一篇关于408考研,期末考试,计算机组成原理,中央处理器的思维导图,专为计算机专业学生、考研 / 软考备考者、计算机底层原理学习者打造,是系统梳理 CPU 核心知识的高效学习工具。思维导图的结构化呈现方式,将 CPU 的功能和基本结构、指令执行过程、数据通路、控制器、指令流水线、多处理器系统六大核心模块拆解为层级清晰、逻辑连贯的分支框架,同时融入高频考点标注、关键概念对比与计算要点,帮助使用者快速构建 CPU 工作原理的知识体系,精准攻克数据通路设计、流水线性能分析、中断处理流程等重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言,这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理,将 CPU 结构、指令执行周期、数据通路设计、硬布线 / 微程序控制器对比、流水线冲突处理、多处理器系统分类等零散知识点系统化,降低理解与记忆难度,提升备考效率;对于计算机底层原理学习者,模板清晰呈现了 CPU 从指令取指到执行的完整工作流程,可用于入门学习、底层原理学习的知识框架搭建,快速建立对计算机核心部件的整体认知。模板完整覆盖中央处理器核心考点:从 CPU 的功能与基本结构、指令执行的完整过程,到数据通路的设计原理与分类;从硬布线与微程序控制器的工作原理与对比,到指令流水线的性能指标、冲突处理与多发技术;再到多处理器系统的基本概念与硬件多线程技术,均以思维导图形式清晰呈现,层级分明,便于快速查阅、重点标记与按需编辑修改,适配备考笔记、课程复习提纲、学习课件等多种场景。
第四章 文件管理
文件系统
文件的概念
文件
一组有意义的信息/数据集合
UNIX 操作系统中,所有设备都被视为特殊的文件
UNIX 操作系统控制和访问外部设备的方式和访问一个文件的方式是相同的。
文件的属性
文件名
同一目录下不允许有重名文件
标识符
操作系统用于区分各个文件的一种内部名称
类型
操作系统可以为同一类型的文件设置默认的启动程序
位置
文件存放的路径
让用户使用
在外存中的地址
操作系统使用,对用户不可见
保护信息
对文件进行保护的访问控制信息(设置用户权限)
补充
数据传输
CPU的数据交换以字为单位
内存与外存之间的数据交换以块为单位
即读/写操作、磁盘I/O
外存数据读入内存以块为单位
每次读或写出一块
外存管理
磁盘中的存储单元
分为一个个的块/磁盘块/物理块
很多操作系统中,磁盘块的大小与内存块、页面的大小相同
文件的逻辑地址空间
分为了一个一个的文件“块”
方便对文件数据的管理
文件的逻辑地址可以表示为(逻辑块号,块内地址)
操作系统将逻辑地址转化为外存的物理地址(物理块号,块内地址)
块内地址的位数取决于磁盘块的大小
注
块都从0开始编号
操作系统以块为单位为文件分配存储空间
文件再小也要占据一块
外存
由一个个存储单元组成
每个存储单元可以存储一定量数据
每个存储单元对应一个物理地址
用户通过逻辑地址来操作自己的文件
操作系统要负责实现从逻辑地址到物理地址的映射
文件目录
目录/文件目录
一种有结构文件
FCB 的有序集合
目录文件中存放的是子目录和数据文件的信息。
一个目录中既可能有子目录,又可能有数据文件
由记录组成
记录/文件目录项
每条记录对应一个放在该目录下的文件
一条记录就是一个FCB
关系
一个文件对应一个FCB,一个FCB就是一个目录项,多个FCB组成文件目录
文件控制块FCB
实现文件目录的关键数据结构
实现“按名存取”
FCB 中包含
文件的基本信息
文件名、物理地址、逻辑结构、物理结构等
存取控制信息
是否可读/可写、禁止访问的用户名单等
使用信息
如文件的建立时间、修改时间等
基本的还是文件名、文件存放的物理地址。
功能
实现了文件名和文件(文件实际地址)之间的映射
使用户(用户程序)可以实现“按名存取
例子
双击“照片”文件后
操作系统会在目录表中找到关键字“照片”对应的目录项
从外存中将“照片”目录的信息读入内存
“照片” 目录中的内容就可以显示出来
对目录进行的操作
搜索
当用户要使用一个文件时,系统要根据文件名搜索目录,找到该文件对应的目录项
创建文件
创建一个新文件时,需要在其所属的目录中增加一个目录项
删除文件
当删除一个文件时,需要在目录中删除相应的目录项
显示目录
用户可以请求显示目录的内容
如显示该目录中的所有文件及相应属性
修改目录
某些文件属性保存在目录中,因此这些属性变化时需要修改相应的目录项
文件重命名
目录结构
单级目录结构
特点
一个系统只有一张目录表
每个文件占一个目录项
实现了“按名存取”
不允许文件重名
适用
早期操作系统
创建文件
先检查目录表中有没有重名文件
不重名
建立文件
将新文件对应的目录项插入目录表中
两级目录结构
采用两级目录结构
主文件目录(MFD,Master File Directory)
记录用户名及相应用户文件目录的存放位置
用户文件目录(UFD,User Flie Directory)
由该用户的文件FCB组成
适用
早期的多用户操作系统
不同用户的文件可以重名
文件名虽然相同,但对应不同文件
可以在目录上实现访问限制
检查此时登录的用户名是否匹配
缺点
缺乏灵活性
用户不能对自己的文件进行分类
多级目录结构/树形目录结构
不同目录下的文件可以重名
路径
文件路径
字符串
各级目录之间用“/”隔开
用户(或用户进程)要访问某个文件时要用文件路径名标识文件
系统根据“文件路径"找到目标文件
绝对路径
从根目录出发的路径
系统根据绝对路径一层一层地找到下一级目录
eg
从外存读入根目录的目录表
找到“照片”目录的存放位置
从外存读入对应的目录表
找到“2015-08”目录的存放位置
从外存读入对应目录表
找到文件“自拍.jpg”的存放位置

整个过程需要3次读磁盘I/O操作
当前目录
此时已经打开的目录文件
目录表已经调入内存
目录表已调入内存,可以将其设为当前目录
在 Linux 中,“.”表示当前目录
相对路径
从当前目录出发的“相对路径
磁盘I/O的次数减少,提升了访问文件的效率
优点
可以方便地对文件进行分类
层次结构清晰
能够更有效地进行文件的管理和保护
缺点
不便于实现文件的共享
补充
UNIX
采用树形目录结构
文件信息存放在索引结点中
超级块是用来描述文件系统的
无环图目录结构
实现
在树形目录结构的基础上,增加一些指向同一节点的有向边,使整个目录成为一个有向无环图
为每个共享结点设置一个共享计数器
共享计数器
记录此时有多少个地方在共享该结点
用户提出删除结点的请求
并不会直接删除共享结点
只是删除该用户的FCB、并使共享计数器减1
共享计数器减为0时,才删除结点
优点
方便地实现多个用户间的文件共享
注
可以用不同的文件名指向同一个文件/目录
指向同一个目录(共享同一目录的所有内容)
只要一个用户修改了文件数据,所有用户都可以看到文件数据的变化
共享文件不同于复制文件
各用户指向同一个文件

文件目录管理部分
索引结点
存储了文件描述信息
系统为了实现文件名与文件信息分开而设计的数据结构
将文件描述信息从目录项中分离
除了文件名之外的文件描述信息都放在索引节点
包括文件在外存中的存放位置
每个文件对应一个索引结点
当找到文件名对应的目录项时,才需要将索引结点调入内存
概念
磁盘索引结点
存放在外存中的索引结点
内存索引结点
当索引结点放入内存后
需要增加一些信息
文件是否被修改、此时有几个进程正在访问该文件等。
好处
文件检索速度提升
磁盘的盘块中可以存放更多的目录项,减少检索文件时的I/O信息量
每个目录项的长度大幅减小
目录项中只包含文件名、索引结点指针
文件结构
文件的逻辑结构
取决于用户
在用户看来文件内部的数据应该是如何组织起来的
是用户组织数据的结构形式
数据组织形式来自需求
按文件是否有结构分类
无结构文件/流式文件
文件内部的数据是一系列二进制流或字符流
如:Windows 操作系统中的 .txt 文件。
有结构文件/记录式文件
由一组相似的记录组成
概念
数据项
文件系统中最基本的数据单位
记录
一组数据项的集合
如:数据库表文件。
每条记录有一个数据项可作为关键字
作为识别不同记录的ID
根据各条记录的长度(占用的存储空间)是否相等
定长记录
可变长记录
有结构文件的逻辑结构
各条记录在逻辑上如何组织
顺序文件
特点
文件中的记录一个接一个地顺序排列(逻辑上)
记录可以是定长的或可变长的
各个记录在物理上可以顺序存储或链式存储。
排序
串结构
记录之间的顺序与关键字无关
通常按照记录存入的时间决定记录的顺序
顺序结构
记录之间的顺序按关键字排序
存储
链式存储
无法实现随机存取
只能从头依次查找
逻辑上相邻的记录物理上不一定相邻(类似于链表)
顺序存储
逻辑上相邻的记录物理上也相邻(类似于顺序表)
可变长记录
无法实现随机存取
定长记录
可实现随机存取
记录长度为L,则第i个记录存放的相对位置是i*L
串结构
无法快速找到关键字对应的记录
顺序结构
可以快速找到关键字对应的记录(折半查找)
实现快速检索
即根据关键字快速找到对应记录
注
一般来说,考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件
缺点
增加/删除一个记录比较困难
如果是串结构则相对简单
索引文件
解决
可变长记录文件在顺序文件中必须从头查找问题
索引表
本质
定长记录的顺序文件
可以随机访问
每个记录对应一个索引表项
可以用不同的数据项建立多个索引表。
不同关键字
特点
可以快速找到第i 个记录对应的索引项。
每当要增加/删除一个记录时,需要对索引表进行修改。
可将关键字作为索引号内容,若按关键字顺序排列,则还可以支持按照关键字折半查找。
优点
很快的检索速度
文件中的记录可以在物理上离散存放
缺点
存储空间的利用率低
每个记录对应一个索引表项,因此索引表可能会很大
应用
主要用于对信息处理的及时性要求比较高的场合
索引顺序文件
索引表
本质
定长记录的串结构的顺序文件
一组记录对应一个索引表项
不需要按关键字顺序排列
检索效率
索引顺序文件结构
记录分组,先查组,再查组中的记录
类似分块查找
多级索引顺序文件
进一步提高检索效率
Tips:
要为N 个记录的文件建立K 级索引,则最优的分组是每组N^(1/(K+1)) 个记录。
K层索引块,p^(k+1)个数据块
检索一个记录的平均查找次数是((N^(1/(K+1) )/2) * (K+1)
一层平均次数((N^(1/(K+1) )/2
文件分配方式(文件的物理结构)
操作系统
操作系统组织物理存储块的结构形式
文件数据怎样存放在外存
取决于文件系统设计者针对硬件结构所采取的策略
硬件结构
如磁带介质很难实现链接结构和索引结构
策略
存储介质特性和操作系统的管理方式
分类
连续分配
每个文件在磁盘上占有一组连续的块
特点
起始块号、长度
文件目录中记录存放起始块号、长度
长度:总共占用几个块

(逻辑块号,块内地址)→(物理块号,块内地址)
只需转换块号就行,块内地址保持不变
要访问的逻辑块号
操作系统找到该文件对应的目录项(FCB)
检查用户提供的逻辑块号是否合法
逻辑块号≥长度 就不合法
物理块号= 起始块号+ 逻辑块号
缺点
不方便拓展。
存储空间利用率低
难以利用的磁盘碎片(外部碎片)
紧凑来处理碎片,但耗费很大的时间代价
优点
在顺序读/写时速度最快
读取某个磁盘块时,需要移动磁头
访问的两个磁盘块相隔越远,移动磁头所需时间就越长
可以直接算出逻辑块号对应的物理块号
支持顺序访问和直接访问(即随机访问)
顺序访问
依次来
直接访问/随机访问
直接找某个
链式分配
采取离散分配的方式
可为文件分配离散的磁盘块
分类
隐式链接
特点
起始块号、结束块号
文件目录包括文件第一块的指针和最后一块的指针
也可以增加一个字段来表示文件的长度
指向下一个盘块的指针
除了文件的最后一个磁盘块外,每个磁盘块中都会保存指向下一个盘块的指针
这些指针对用户是透明的
要访问的逻辑块号i
操作系统
找到该文件对应的目录项(FCB)
从目录项中找到起始块号(即0号块),将0号逻辑块读入内存
由此知道1号逻辑块存放的物理块号,于是读入1号逻辑块……
读入i号逻辑块,总共需要 i+1 次磁盘 I/O操作
缺点
指向下一个盘块的指针也需要耗费少量的存储空间。
查找效率低
只支持顺序访问
不支持随机访问
优点
方便文件拓展
外存利用率高
所有的空闲磁盘块都可以被利用
不会有碎片问题
显式链接
特点
只记录起始块号
目录中只需记录文件的起始块号
需要文件分配表(FAT)
把用于链接文件各物理块的指针显式地存放在一张表中
文件分配表(FAT)
eg,创建a文件依次存放在磁盘块2,5,0,1
一个磁盘一张FAT
开机时,将FAT读入内存,并常驻内存
查表不需要访问磁盘操作
ds:一个逻辑卷/分区一张
表项
磁盘有多少块,就有多少表项
FAT 的各个表项在物理上连续存储
每一个表项长度相同
物理块号”字段可以是隐含的
内容
创建文件后即可得知下一块的块号
用-1表示文件的结尾
要访问的逻辑块号i
操作系统
找到该文件对应的目录项(FCB)从目录项中找到起始块号
若i>0
查询内存中的文件分配表FAT
找到i 号逻辑块对应的物理块号
逻辑块号转换成物理块号的过程不需要读磁盘操作
缺点
文件分配表的需要占用一定的存储空间。
优点
方便文件拓展,并且支持随机访问。
外存利用率高
不会有碎片问题
查找效率高
支持顺序访问
也支持随机访问
访问i号逻辑块时,并不需要依次访问之前的0~i-1号逻辑块
文件的访问效率高
地址转换时不需要访问磁盘
可以分配磁盘块
操作系统可以通过FAT对文件的存储空间进行管理
当某进程请求操作系统分配个磁盘块时,操作系统只需在FAT中找到-2的的表项,然后分配给进程
注
考试题目中遇到未指明隐式/显式的“链接分配”,默认指的是隐式链接的链接分配
索引分配
注意:
有的题目也会将其称为索引文件,要与逻辑结构的索引文件根据语境判断
特点
允许文件离散地分配在各个磁盘块中
索引块
目录中需要记录文件的索引块是记号磁盘块
索引表
记录了文件的各个逻辑块对应的物理块
概念
索引表
一个文件对应一张索引表
每个文件都有一张自己的索引表
对索引文件存取时,必须先查找索引表
类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系
逻辑块号可以是隐含的
区别
索引块
索引表存放的磁盘块称为索引块
保存了索引表的内容
数据块
文件数据存放的磁盘块称为数据块
实际用于保存数据的块
要访问的逻辑块号i
操作系统
找到该文件对应的目录项(FCB)
从目录项中可知索引表存放位置
将索引表从外存读入内存
查找索引表即可知i 号逻辑块在外存中的存放位置
缺点
但是索引表需要占用一定的存储空间
优点
支持随机访问
文件拓展容易
需要给文件分配一个空闲块,并增加一个索引表项
如何解决一个块装不下一张索引表的问题
链接方案
将多个索引块链接起来存放
FCB中只用记录第一个索引块的块号
缺点
查找效率低
地址转换次数多
各个索引块之间是用指针链接起来
找到i号索引块
必须先依次读入0~i-1号索引块
磁盘I/O次数过多
逻辑块越往后,就要顺序读入更多的索引块
多层索引
建立多层索引
原理类似于多级页表
原理
第一层索引块指向第二层的索引块
若采用多层索引,则各层索引表大小不能超过一个磁盘块
采用K层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要K+1次读磁盘操作
缺点
即使是小文件,访问一个数据块依然需要K+1次读磁盘。
混合索引
多种索引分配方式的结合
例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表) 。

优点
对于小文件来说,访问一个数据块所需的读磁盘次数更少
重要考点
①要会根据多层索引、混合索引的结构计算出文件的最大长度
Key:各级索引表最大不能超过一个块
②要能自己分析访问某个数据块所需要的读磁盘次数
Key:FCB中会存有指向顶级索引块的指针,因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作
注意题目条件——顶级索引块是否已调入内存
文件的某种逻辑结构支持随机存取/随机访问
采用这种逻辑结构的文件,可以根据记录号直接算出该记录对应的逻辑地址(逻辑块号,块内地址)
由逻辑文件和索引表组成
索引项只包含每条记录的长度和在逻辑文件中的起始位置
因为每条记录都要有一个索引项,因此提高了存储代价。

逻辑结构和物理结构对比
文件内部各条记录链式存储:
由创建文件的用户自己设计
文件整体用链接分配:
由操作系统决定
索引文件的索引表:
用户自己建立
映射:关键字→记录存放的逻辑地址
索引分配的索引表:
操作系统建立
映射:逻辑块号→物理块号
逻辑结构
用户(文件创建者)的视角
在用户看来,整个文件占用连续的逻辑地址空间
文件内部的信息组织完全由用户自己决定,操作系统并不关心
物理结构
由操作系统决定文件采用什么物理结构存储
操作系统负责将逻辑地址转变为(逻辑块号,块内偏移量)的形式,并负责实现逻辑块号到物理块号的映射
文件存储空间管理
操作系统需要对磁盘块进行哪些管理
对非空闲磁盘块的管理(存放了文件数据的磁盘块)
文件的物理结构/文件分配方式要探讨的问题
连续分配、链接分配、索引分配
对空闲磁盘块的管理
文件存储空间管理(文件空闲空间管理)
操作系统如何管理外存中的空闲块(存储空间的管理)
文件存储空间管理/ 外存空闲空间管理
存储空间的划分与初始化
存储空间的划分
将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)
存储空间的初始化
文件卷划分为目录区、文件区
目录区
主要存放文件目录信息(FCB)
用于磁盘存储空间管理的信息
文件区
用于存放文件数据
支持超大型文件
可支持由多个物理磁盘组成一个文件卷
传统文件系统管理空闲磁盘的方法
空闲表法
记录每个空闲区间的起始位置,空闲区间长度
适用于
连续分配方式
如何分配磁盘块:
为一个文件分配连续的存储空间
与内存管理中的动态分区分配很类似
同样可采用首次适应、最佳适应、最坏适应等 算法来决定要为文件分配哪个区间。
如何回收磁盘块:
与内存管理中的动态分区分配很类似
①回收区的前后都没有相邻空闲区;
②回收区的前后都是空闲区;
③回收区前面是空闲区;
④回收区后面是空闲区。
回收时需要注意表项的合并问题
空闲链表法
空闲盘块法
空闲盘块中存储着下一个空闲盘块的指针
以盘块为单位组成一条空闲链
操作系统保存着链头、链尾指针。
如何分配
从链头开始依次摘下K 个盘块分配,并修改空闲链的链头指针
如何回收
回收的盘块依次挂到链尾,并修改空闲链的链针。
适用于
离散分配的物理结构
为文件分配多个盘块时可能要重复多次操作

空闲盘区法
以盘区为单位组成一条空闲链
连续的空闲盘块组成一个空闲盘区
适用
离散分配、连续分配都适用
为一个文件分配多个盘块时效率更高
空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针
操作系统保存着链头、链尾指针。
如何分配
可以采用首次适应、最佳适应等算法,从链头开始检索,找到一个大小符合要求的空闲盘区,分配给文件
若没有合适的连续空闲块
也可以将不同盘区的盘块同时分配给一个文件
注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收
若回收区和某个空闲盘区相邻,则需要将回收区合并到空闲盘区中。
若回收区没有和任何空闲区相邻,将回收区作为单独的一个空闲盘区挂到链尾。

位示图法
位示图
每个二进制位对应一个盘块
在本例中,“0”代表盘块空闲, “1”代表盘块已分配。
用一位标识是否被分配
位示图一般用连续的“字”来表示
如本例中一个字的字长是16位,字中的每一位对应一个盘块。因此可以用(字号,位号)对应一个盘块号。当然有的题目中也描述为(行号,列号)


适用
连续分配、离散分配都适用
注
(字号,位号)/(行号,列号)与盘块号
(字号, 位号)=(i, j) 的二进制位对应的盘块号b = ni + j(从0开始)
b号盘块对应的字号i = b/n,位号j = b%n(从0开始)
题目条件:
盘块号、字号、位号到底是从0开始还是从1开始
二进制位 0/1 到底哪个代表空闲,哪个代表不空闲
位图所占空间大小只取决于外存空间的总大小(盘块数量),与当前空闲块数量无关
如何分配
若文件需要K个块
①顺序扫描位示图,找到K个相邻或不相邻的“0”;
②根据字号、位号算出对应的盘块号,将相应盘块分配给文件;
③将相应位设置为“1”。
如何回收
①根据回收的盘块号计算字号、位号;
②将相应二进制位设为“0”
成组链接法
理解即可,不方便用文字描述的知识点也很难作为考题
UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
成组链接法
将所有空闲盘块分成若干组
每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号
第一组的空闲盘块总数和空闲盘块号存放在内存的专用栈中,称为空闲盘块号栈。
适用于
大型文件系统
空闲表法、空闲链表法不适用于大型文件系统
空闲表或空闲链表可能过大
超级块
文件卷的目录区中专门用一个磁盘块作为“超级块”
当系统启动时需要将超级块读入内存
保证内存与外存中的“超级块”数据一致
超级块中记录了下一组空闲盘块数,空闲块号
若已经没有下组空闲快,设为某特殊值
最后一个分组要比其他分组更少一块“-1”
注
成组链接中每个分组的盘块数量有上限

100表示下一个空闲盘块的分组总共有100个空闲盘块
在倒数第二个分组的第一个盘块可以设置特殊的值-1,代表再下一个分组是最后一一个分组
如何分配?
Eg :需要100个空闲块 ①检查第一个分组的块数是否足够。100=100,是足够的。 ②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息,因此 300号块的数据需要复制到超级块中。
超级块充当链头作用,保留下一块信息
将分组分配出去之前,需要将这个分组指向下一个分组的信息全部复制过去

如何回收?
Eg :假设每个分组最多为100个空闲块,此时第一个分组已有99个块,还要再回收一块。
第一个分组没满,将要回收的数据插到第一个分组中,并将超级块下一组的空闲盘块数加一
需要将超级块中的数据复制到新回收的块中,并修改超级块的内容,让新回收的块成为第一个分组。
Eg:假设每个分组最多为100个空闲块,此时第一个分组已有100个块,还要再回收一块。 .需要将超级块中的数据复制到新回收的块中,并修改超级块的内容,让新回收的块成为第一个分组。

将新回收的块作为一个分组,将超级块中的内容复制到新回收的块中,新回收的块作为一个新的分组拥有了指向下一个分组的链接的指针,超级块的数据指向新分组,并将下一个分组数改为1
特殊
文件分配表(FAT)
FAT 的表项与物理磁盘块一一对应,并且可以用一个特殊的数字-1 表示文件的最后一块,用-2表示这个磁盘块是空闲的(当然也可用-3.-4 来表示)
FAT 不仅记录了文件中各个块的先后链接关系,还标记了空闲的磁盘块
操作系统可以通过 FAT 对文件存储空间进行管理
文件的基本操作
创建文件(“create 系统调用”)
分配外存空间,创建目录项
提供的参数
1. 所需的外存空间大小(如:一个盘块,即1KB)
2. 文件存放路径("D:/Demo")
3. 文件名(这个地方默为"新建文本文档.txt")
操作系统在处理 Create 系统调用时,主要做了两件事:
1. 在外存中找到文件所需的空间
2.
根据文件存放路径的信息找到该目录对应的目录文件
此处就是 D:/Demo 目录
在目录中创建该文件对应的目录项
目录项中包含了文件名、文件在外存中的存放位置等信息。
系统能创建文件数目的上限
考虑可以有多少个不同文件
eg,某文件系统的目录项由文件名和索引节点号构成
不同目录下的文件的文件名可以相同,所以在考虑系统创建最多文件数量时,只需考虑索引节点的个数,即创建文件数量上限= 索引节点数量上限
删除文件(“delete”系统调用)
回收外存空间,删除目录项
提供的参数
1. 文件存放路径("D:/Demo")
2. 文件名
操作系统在处理 delete系统调用时,主要做了三件事:
1.
根据文件存放路径的信息找到该目录对应的目录文件
从目录中找到文件对应的目录项
2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息,回收文件占用的磁盘块
3. 从目录表中删除文件对应的目录项。
打开文件(“open”系统调用)
提供的参数
1. 文件存放路径("D:/Demo")
2. 文件名
3. 对文件的操作类型(r只读、rw读写)
open系统调用
int open (char *filename ,int flags,mode_t mode)
open 将文件名转换为文件标识符,返回数字
flags参数指明进程如何访问这个文件 O_RDONLY O_WRONLY O_RDRW
操作系统在处理 open系统调用时,主要做了两件事:
1.
根据文件存放路径的信息找到该目录对应的目录文件
从目录中找到文件名对应的目录项
检查用户是否有指定操作的权限
2.
将文件项复制到内存中用户进程的“打开文件表”中
将对应的表目的编号(索引号/文件描述符/句柄)返回给用户
之后用户使用打开文件表的编号指明要操作的文件
加快文件的访问速度

注
打开文件时并不会把文件数据直接读入内存
open()调用
会在进程的用户打开文件表中增加一个对应的表目,并返回该表目的索引号
系统打开文件表只有在文件实体第一次被打开时才增加一个表目,也才会通过文件 I0 将对应的索引节点从磁盘读入内存
当open()调用的不同文件互为硬链接时,所打开的文件实体是一样的。
好处
打开文件之后
对文件的操作不再需要每次都查询目录
可以根据内存中的打开文件表进行操作
系统的打开文件表
整个系统只有一张
记录包含所有正在被使用的文件信息
有多少个进程打开了此文件
方便实现某些文件管理的功能
入尝试删除某个文件
系统检查系统打开文件表,确认此时是否有进程正在使用该文件
打开计数器
进程的用户打开文件表
进程本身打开了哪些文件信息
读/写指针
记录了该进程对文件的读/写操作进行到的位置
访问权限
系统表索引号
指向系统的打开文件表
关闭文件(“close”系统调用)
操作系统在处理 Close系统调用时,主要做了三件事:
1. 将进程的打开文件表相应表项删除
2. 回收分配给该文件的内存空间等资源
3. 系统打开文件表的打开计数器count 减1
若 count = 0,则删除对应表项。
将文件当前的控制信息从内存写回磁盘
注
关闭文件并不意味着将文件数据写回磁盘
写文件操作才会写回磁盘(不考虑延迟写)
注
读/写文件之前,要“打开文件”
读/写文件结束之后,要关闭文件
读文件(“read”系统调用)
根据读指针、读入数据量、内存位置将文件数据从外存读入内存
用文件描述符即可指明文件,不用需要用到文件名
根据文件描述符即可找到内存中对应的FCB
文件还未读入内存
系统会根据FCB中的地址找到文件在外存中的地址,并将文件内容读入内存中
再将文件的数据缓冲区首指针返回给用户进程
文件本来就已经被调入内存
直接返回首指针即可
提供的参数
打开文件中的索引号
指明是哪个文件
在支持“打开文件”操作的系统中,只要提供文件在打开文件表中的索引号即可
读入多少数据
数据在内存中的位置
读入的数据要放在内存的什么位置
read系统调用: ssize_t read (int fd,void *buf, size_t n)
从描述符为fd的当前文件位置复制最多n个字节到内存位置buf
返回值为-1表示错误
为0表示EOF
否则表示实际传送的字节数量
写文件(“write”系统调用)
提供的参数
打开文件中的索引号
写入多少数据
数据在内存中的位置
将更改过的文件数据写回外存
根据写指针、写出数据量、内存位置 将文件数据从内存写出外存
write系统调用: ssize_t write (int fd,const void *buf, size_t n)
从内存位置buf复制至多n个字节到描述符fd的当前文件位置
可用几个基本操作完成更复杂的操作
比如:“ 复制文件”:先创建一个新的空文件,再把源文件读入内存,再将内存中的数据写到新文件中
操作系统需要提供的其他文件管理功能
文件共享
使多个用户可以共享使用一个文件
两种共享方式
基于索引结点的文件共享方式(硬链接)
索引结点inode
文件目录瘦身策略
目录项只包含文件名、索引结点指针
检索文件时只需用到文件名
将除了文件名之外的其他信息放到索引结点中
链接计数变量count
表示链接到本索引结点上的用户目录项数
每个文件创建时,至少有一个目录项指向其 inode(引用计数 ≥ 1)
表示硬盘上有几个目录项指向 inode
删除文件实际上是删除目录项,减少引用计数
引用计数归零时,inode 和磁盘空间才可回收
只要count>0,说明还有用户在使用该文件
若这种情况下删除文件会导致指针悬空
每个文件也都有count计数器,来记录自己与其他文件的连接数,其值默认为1,也就是说,我们只创建一个文件,啥都不干,就有1的计数
但其实空的文件夹引用计数是2。其中含有两个隐藏的文件.和..。这两个文件分别指向了本目录和上层目录,都是硬链接
硬链接没有自己的inode,其增加的对源文件的inode引用计数
在UNIX中会在硬盘中分配一整片连续的空间,存放的都是一个个inode结点,每个inode结点对应一个具体的文件。
可以像数组一样编号
每个inode结点编号大小相等
结合inode结点号以及每一个inode结点的大小,再结合硬盘当中inode结点的起始存放位置,可以确定任意一个文件对应的inode结点
通过文件的路径找到与一个文件所对应的目录项后,根据目录项找到文件所对应的inode编号,直接查到文件所对应的inode结点
特点
不同用户的目录项指向同一个文件的索引结点
不同用户对于这个文件取的名可以不同
用户删除文件
操作系统只是删除文件在该用户目录中对应的目录项
count--
只有 count ==0时才能真正删除文件数据和索引结点
应用
文件备份
文件共享
节省磁盘空间

基于符号链的共享方式(软链接)
目的
使用户B能共享用户A的文件F
实现
系统创建一个LINK类型的新文件,也取名为F,并将F写入用户B的目录中
操作系统根据路径一层层查找目录,最终找到共享文件
本质
存储的是目标文件的路径字符串
软链接拥有自己的inode,其存储了指向的文件的路径
Link 类型的文件
由系统创建
类似于快捷方式
记录共享文件的存放路径
特点
文件的拥有者有指向其索引结点的指针
共享该文件的其他用户只有该文件的路径名
软链接指向的共享文件被删
Link型文件依然存在
通过 Link 型文件中的路径去查找共享文件会失败
找不到对应目录项
软链接可以跨文件系统,且可以对目录进行链接;硬链接不可以
软链接甚至可以对不存在的文件进行链接
缺点
会有多次磁盘I/O
软链接的方式访问共享文件时要查询多级目录
软链接访问共享文件的速度要比硬链接更慢
当文件拥有者删除共享文件后,有人在同一路径下创建了另一个同一名称的文件,则该符号链仍然有效,会导致错误
注
符号链接实现的共享本身不限制修改

注
区分
共享
系统中只有“一份”文件数据
用户修改了该文件的数据,其他用户也可以看到文件数据的变化
复制
系统中会有“好几份”文件数据
用户修改了自己的那份文件数据,对其他用户的文件数据没有影响。
硬链接和软链接都是静态链接的方法
文件系统中还存在着两个进程对同一个文件进行操作,即动态链接
多个进程打开一个文件
读/写指针的位置不同,它们保存在各自的用户打开文件表中
不同进程获得的文件描述符是各自独立的,分别指向各自的用户打开文件表中的一项
计数值的计算
引用计数 ≠ 缓存状态,不是计数值不等于0就是文件已经被打开
inode 是否在内存缓存中取决于是否曾被访问过
解析路径找到 inodeA
发现 inodeA 不在缓存 →
触发磁盘读取
软链接/符号链接文件
是个新文件
不影响引用计数
当移动源文件的时候,软链接会失效,删除软链接文件对源文件无影响
建立符号链接时,引用计数值直接设置为1,不受被链接文件的影响
始终为1
创建符号链接文件涉及文件索引结点的磁盘读取操作
为新文件分配新inode并写入数据
删除被链接文件时,删除操作对于符号链接是不可见的
硬链接
影响引用计数
建立硬链接时,引用计数值加1
其引用计数值直接复制
每个硬链接都直接指向同一个inode(文件数据块)
所有硬链接(包括原始文件和后续创建的硬链接)都是平等的,没有主次之分
删除任何一个硬链接只是减少inode的引用计数,并不会立即删除文件数据
文件保护
保证不同的用户对文件有不同的操作权限
针对文件访问权限的保护
防止用户文件被他人存取或盗窃
口令保护
特点
为文件设置一个“口令"
一般存放在文件对应的 FCB 或索引结点中
用户请求访问该文件时必须供“口令"
实现
操作系统会将用户提供的口令与FCB中存储的口令进行对比,如果正确,则允许该用户访问文件
优点:保存口令的空间开销不多,验证口令的时间开销也很小。
缺点:口令存放在系统内部,不够安全。
加密保护
实现
使用某个“密码”对文件进行加密
访问文件时需提供正确的“密码”才能对文件进行正确的解密
比如异或加密

优点:保密性强,不需要在系统中存储“密码”
缺点:编码/译码,或者说加密/解密要花费一定时间。
控制用户对文件的访问方式
访问控制/存取控制
实现
在文件的FCB(或索引结点)中增加一个访问控制列表( ACL)
记录了各个用户可以对该文件执行哪些操作。
缺点
有的计算机可能会有很多个用户,因此访问控制列表可能会很大
精简的访问列表
以“组”为单位,标记各“组”用户可以对文件执行哪些操作
每个用户都会从属于其中的一个或者两个分组
用户想访问文件时,系统会检查该用户所属的分组是否有相应的访问权限
优点
实现灵活,可以实现复杂的文件保护功能
因为访问控制的级别和保护力度较小
缺点
相对于加密保护机制,访问控制机制的安全性较差
特点
访问控制机制必须由操作系统实现
若访问控制不由系统实现,则系统本身的安全性就无法保证
加密机制若由系统实现,则加密方法将无法扩展。
如果对某个目录进行了访问权限的控制,那也要对目录下的所有文件进行相同的访问权限控制
拒绝项的优先级高于允许项
注
访问权限属于文件所持有
每类用户的访问权限可能有
因此可将用户访问权限抽象为一个矩阵,其行代表用户类别,列代表访问权限
补充
系统级安全管理包括
注册
登录
对一个文件的访问
用户访问权限
文件属性限制
包括保存在FCB 中对文件访问的控制信息
口令
用户优先级
是指在多个用户同时请求该文件时应该先满足谁
异步 I/O
指发出 I/O请求后,系统不必等待 I/O完成,而继续执行其他任务,当 I/O完成后再通知系统
提高了 CPU 利用率
目录项分解
将目录项分解为符号目录项和基本目录项
符号目录项包括文件名和文件号
基本目录项包括文件号和文件其他描述信息
查找时只需查找符号目录,减少了磁盘占用空间
减少了读盘次数
文件高速缓存
以减少磁盘 I/O 次数
磁盘调度算法
减少寻道时间,提高磁盘 I/O 速度
4.3文件系统
文件系统层次结构
用户接口
向上层的用户提供简单易用的功能接口
处理用户发出的系统调用请求(Read、Write、Open、Close 等系统调用)
文件目录系统
根据用户给出的文件路径找到相应的FCB或索引结点。
所有和目录、目录项相关的管理工作都在本层完成
如:管理活跃的文件目录表、管理打开文件表等
存取控制模块/存取控制验证层
实现文件保护相关功能
验证用户是否有访问权限
保证文件数据的安全
逻辑文件系统与文件信息缓冲区
将记录号转换为对应的逻辑地址
用户指明想要访问文件记录号
逻辑文件系统的功能
对文件按名存取
进行文件目录组织管理
将文件名转换为文件描述符或文件句柄
进行存储保护
物理文件系统
把上一层提供的文件逻辑地址转换为实际的物理地址
辅助分配模块
负责文件存储空间的管理
负责分配和回收存储空间
设备管理模块
直接与硬件交互,负责和硬件直接相关的一些管理工作。
如:分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等
文件系统的全局结构(布局)
文件系统存放在磁盘(外存)中
多数磁盘划分为一个或多个分区
每个分区中有一个独立的文件系统
在每个分区中可以建立各自独立的文件系统
第一步:物理格式化/低级格式化
划分扇区,检测坏扇区,并用备用扇区替换坏扇区
坏扇区对操作系统透明
意识不到坏扇区存在
第二步:逻辑格式化/高级格式化
磁盘分区(分卷Volume)后,对各分区进行逻辑格式化,完成文件系统初始化
分区:eg,C盘
注
逻辑格式化后,灰色部分就有实际数据了,白色部分还没有数据
只有新建了文件之后白色部分才会填充上数据
文件系统在外存(磁盘)中的结构

硬盘的主引导扇区由三部分组成
主引导程序
也称主引导记录(MBR)
用于系统启动时将控制转给用户指定的并在分区表中登记了的某个活动分区
分区表
给出每个分区的起始和结束地址
结束标志
其值通常为AA55
主引导记录(Master Boot Record, MBR)
位于磁盘的0号扇区,用来引导计算机,MBR后面是分区表
分区表
记录每个分区大小,起始地址,地址范围
表中的一个分区被标记为活动分区,当计算机启动时,BIOS 读入并执行MBR。
MBR做的第一件事是确定活动分区,读入它的第一块,即引导块
引导块(boot block)
Windows 系统称之为分区引导扇区。
MBR执行引导块中的程序后,该程序负责启动该分区中的操作系统。
为统一起见,每个分区都从一个引导块开始,即使它不含有一个可启动的操作系统,也不排除以后会在该分区安装一个操作系统。
除了从引导块开始,磁盘分区的布局是随着文件系统的不同而变化的。
超级块(super block)
包含文件系统的所有关键信息
可以迅速地找到磁盘分区里面所有的空闲块
描述文件系统
在计算机启动时,或者在该文件系统首次使用时,超级块会被载入内存
超级块中的典型信息包括
分区的块的数量
块的大小
空闲块的数量和指针
空闲的FCB数量
FCB指针等
空闲空间管理
可以判断特定的磁盘块是否空闲
文件系统中空闲块的信息,可以使用位示图或指针链接的形式给出
i结点区
每个文件对应一个结点,i结点说明了文件的方方面面
索引结点
每个文件都会有与之对应的索引结点
UNIX文件的所有索引结点都是连续存放在i结点区
每个索引结点大小都相同,可以根据下标定位到任何索引结点存储的位置
索引文件
会为文件中各个记录建立一个索引表
为了查询这些记录对应的逻辑地址就需要查询索引表在
查询文件的索引表之前,要先把索引表调入内存的文件信息缓冲区中
根目录
存放文件系统目录树的根部
其他所有的目录和文件
磁盘的其他部分
文件系统在内存中的结构
目录缓存
近期访问过的文件数据
注:
近期访问过的目录文件会缓存在内存中,不用每次都从磁盘读入,这样可以加快目录检索速度
系统打开文件表
整个系统只要一张
进程/用户打开文件表
每个进程一张包含在每个进程的PCB之中,记录了某个进程当前打开了哪些文件
不会保存FCB,只会保存索引
文件描述符可以理解为指向进程打开文件表的指针

将目录M读入主存,检查目录项
将目录项复制到系统打开文件表中
表示这个文件被打开
同时设置打开计数
虚拟文件系统和文件系统挂载(安装)
虚拟文件系统VFS
用户在打开文件时,只需要根据虚拟文件系统制定的标准来写自己的代码

存在问题
参数列表,参数格式不同
不同的文件系统,表示文件数据结构各不相同。打开文件后,其在内存中的表示就不同
文件信息
索引结点读入主存

只要读入目录项,FCB中就包含了想要知道的关于文件的所有信息
特点
①向上层用户进程提供统一标准的系统调用接口,屏蔽底层具体文件系统的实现差异
无须考虑具体的文件系统和实际的存储介质。
新的文件系统只要支持并实现这些接口,即可安装和使用。

②VFS要求下层的文件系统必须实现某些规定的函数功能,如: open/read/write。一个新的文件系统想要在某操作系统上被使用,就必须满足该操作系统VFS的要求
③每打开一个文件,VFS就在主存中新建一个 vnode(包含文件各种信息),用统一的数据结构表示文件,无论该文件存储在哪个文件系统。

函数功能指针
不同文件系统需要实现虚拟文件系统规定的一些函数功能。 函数功能指针指向对应文件系统的函数功能列表
只要open打开了一个文件之后要对文件进行的任何操作(read等)可以先找到文件的vnode,然后根据当中记录的这个函数功能指针再找到具体的对应的这个文件系统的函数功能列表,然后去执行这个具体的函数——可以实现从上至下一层层函数调用
虚拟文件系统可以用一个统一的数据结构vnode来表示任何一个文件信息,无论文件存放在哪一种文件系统之中
inode与 vnode的区别
vnode只存在于主存中,每个被打开的文件在主存中都会有一个与之对应的vnode
inode(索引结点)即会调入主存,也会在外存中存储 inode
如打开的文件在UFS文件系统中,找到文件对应目录项后,会把文件的 inode从外存读入主存,并将读入的 inode中的各种信息复制到 vnode中
为了实现VFS,Linux主要抽象了四种对象类型
每个VFS对象都存放在一个适当的数据结构中
其中包括对象的属性和指向对象方法( 函数)表的指针。
超级块对象:
表示一个已安装(或称挂载)的特定文件系统
索引结点对象:
表示一个特定的文件
目录项对象:
表示一个特定的目录项
文件对象:
表示一个与进程相关的已打开文件
文件系统挂载(mounting)
即文件系统安装/装载---如何将一个文件系统挂载到操作系统中?

如U盘插入电脑,U盘的文件系统需要挂载到操作系统上
挂载到操作系统的虚拟文件系统里
挂载了三个文件系统
在虚拟文件系统的挂载表中有三个表项分别指向
虚拟文件系统中有三个表项挂在三个信息
文件系统挂载要做的事:
①在VFS中注册新挂载的文件系统。内存中的挂载表(mount table)包含每个文件系统的相关信息,包括文件系统类型、容量大小等。
在内存中,虚拟文件系统管理一个数据结构——挂载表
要挂载一个新的文件系统时,要虚拟文件系统之中新建表项,指向文件系统
虚拟文件系统发现新的文件系统
②新挂载的文件系统,要向VFS提供一个函数地址列表

每一个文件系统对open,read……函数的实现各不相同
每个系统调用存放在什么地址
让虚拟文件系统来调用我们新挂载的文件系统所提供的功能函数
③将新文件系统加到挂载点mountpoint),也就是将新文件系统挂载在某个父目录下

挂载点
盘符编号标识一个新的设备,文件系统
一个新加入文件系统,需要把他挂载到某一个特定的位置,可以在某个原本存在的父目录下,
只有确定了新文件系统挂载的位置,才可以正常访问/使用这个文件系统
补充
单个文件的大小限制
磁盘剩余容量大小的限制
FCB 和FAT表等结构的限制
利用磁盘阵列技术,一个文件系统可将数据存放到多个磁盘上
4.3磁盘的组织和管理
文件系统(File system)提供高效和便捷的磁盘访问,以便允许存储、定位、提取数据。
磁盘的结构
磁盘
磁盘的表面由一些磁性物质组成,可以用这些磁性物质来记录二进制数据
磁道
磁盘的盘面被划分成一个个磁道。一"圈”就是一个磁道
扇区
磁道又被划分成扇区
每个扇区就是一个 “磁盘块”
各个扇区存放的数据量相同(如1KB)
最内侧磁道上的扇区面积最小,因此数据密度最大

盘面和柱面
盘面
一个盘片可能会有两个盘面
每个盘面对应一个磁头
所有的磁头都是连在同一个磁臂上的,因此所有磁头只能“共进退”
柱面
所有盘面中相对位置相同的磁道组成柱面

磁盘的物理地址
可用(柱面号,盘面号,扇区号)来定位任意一个“磁盘块”。
如何在磁盘中读/写数据
可根据该地址读取一个"块“
1. 根据"柱面号“移动磁臂,让磁头指向指定柱面;
2. 激活指定盘面对应的磁头;
3. 磁盘旋转的过程中,指定的扇区会从磁头下面划过,这样就完成了对指定扇区的读
磁盘的分类
活动/移动头磁盘
磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道
每个盘面只有一个磁头
固定头磁盘
磁头不可移动的称为固定头磁盘。
每个磁道一个磁头

可换盘磁盘
盘片可以更换
固定盘磁盘
盘片不可更换
补充
块
物理块
相当于扇区
逻辑块
相当于簇
操作系统是以块为单位给文件分配存储空间的
一个逻辑块可以有一个或多个物理块来组成
一个逻辑块至少由一个物理块组成
UNIX
Linux
簇
一般一个簇由若干个扇区组成
很多系统中( 如DOS系统),磁盘存储空间的分配以“簇”为单位。
注意,计算分配的磁盘空间大小时按簇
“每道的所有扇区组成一个簇”
这个条件是在暗示我们,一个文件肯定是占用整数个簇(即整数个磁道)
读写b字节的数据一定是要读写整数个磁道,而不是在各个磁道读某几个扇区。
Windows
磁盘扇区
物理上限制的读/写一次的基本单位
簇/块
操作系统限制的存储空间分配基本单位
磁盘调度算法
一次磁盘读/写操作需要的时间
寻找时间(寻道时间)Ts:
在读/写数据前,将磁头移动到指定磁道所花的时间。
寻找过程为机械运动,时间较长,影响较大。
和磁盘调度算法、磁臂移动速度有关
启动磁头臂假设耗时为s;
启动时间:和磁盘驱动器的物理、电气特性有关
移动磁头
假设磁头匀速移动,每跨越一个磁道耗时m,共需要跨越n 条磁道
寻道时间Ts=s+m*n
操作系统的磁盘调度算法会直接影响寻道时间
延迟时间TR:
通过旋转磁盘,使磁头定位到目标扇区所需要的时间。
磁盘转速为r 转/分(秒),则平均所需的延迟时间TR=(1/2)*(1/r)=1/2r
转一圈所需要的时间
1/r
找到目标扇区平均需要转半圈,因此再乘以 1/2
传输时间Tt:
从磁盘读出或向磁盘写入数据所经历的时间
假设“磁盘转速为r,此次读/写的字节数为b,每个磁道上的字节数为N。则传输时间T=(1/r)*(b/N)
总的平均存取时间Ta = Ts + 1/2r + b/(rN)
注
延迟时间,传输时间和转速有关
转速:硬件固有属性
操作系统无法优化
旋转延迟
旋转延迟的大小与磁盘调度算法无关
旋转延迟的大小取决于磁盘空闲空间的分配程序
旋转延迟的大小与文件的物理结构有关
连续分配,链接分配
文件的物理结构与磁盘空间的分配方式相对应
扇区数据的处理时间对旋转延迟有关
扇区数据的处理时间主要影响传输时间
转几个扇区之后可以处理下一个扇区的数据
磁盘调度算法
先来先服务算法(FCFS)
根据进程请求访问磁盘的先后顺序进行调度。
优点
公平
如果请求访问的磁道比较集中的话,算法性能还算过的去
缺点
如果有大量进程竞争使用磁盘,请求访问的磁道很分散,则FCFS在性能上很差,寻道时间长。
最短寻找时间优先算法(SSTF)
SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。
保证每次的寻道时间最短,但是并不能保证总的寻道时间最短。
贪心算法的思想
只是选择眼前最优,但是总体未必最优
优点
性能较好,平均寻道时间短
缺点
可能产生”饥饿“现象
磁头在一个小区域内来回来去地移动
每次移动都要比较两边
扫描算法(SCAN)/电梯算法
思想
只有磁头移动到最外侧磁道的时候才往内移动
移动到最内侧磁道的时候才能往外移动。
由于磁头移动的方式很像电梯,因此也叫电梯算法。
向外侧移动
向磁道号增大的方向移动

优点
性能较好,平均寻道时间较短,不会产生饥饿现象
缺点
只有到达最边上的磁道时才能改变磁头移动方向。
一定要走到头
事实上,处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
SCAN算法对于各个位置磁道的响应频率不平均
(解决:循环扫描算法)
假设磁头正在往右边移动,且刚处理过90号磁道,那么下次处理90号磁道的请求就需要等磁头移动很长一段距离:而响应了184号磁道的请求之后,很快又可以再次响应184号磁道的请求了)
LOOK算法
如果磁头在移动方向没有别的请求,就可以改变磁头的移动方向

优点
不需要每次都移动到最外侧或最内侧才改变磁头方向
寻道时间进一步缩短
循环扫描算法(C-SCAN)
规定
只有磁头朝某个特定方向移动时才处理磁道访问请求
走到头
返回时直接快速移动至起始端而不处理任何请求。
磁头移动距离不要漏掉这一部分

优点
比起SCAN 来,对于各个位置磁道的响应频率很平均。
缺点
只有到达最边上的磁道时才能改变磁头移动方向
事实上,处理了184号磁的访问请求之后就不需要再往右移动磁头了
磁头返回时其实只需要返回到18号磁道即可,不需要返回到最边缘的磁道
另外,比起SCAN算法来,平均寻道时间更长
C-LOOK调度算法
如果磁头移动的方向上已经没有磁道访问请求了,就可以立即让磁头返回,并且磁头只需返回到有磁道访问请求的位置即可。

优点
比起 C-SCAN 算法来,不需要每次都移动到最外侧或最内侧才改变磁头方向,使寻道时间进一步缩短
若无特殊说明,默认SCAN算法和C-SCAN算法为LOOK和C-LOOK算法
磁头移过的磁道数计算
采用 SCAN 算法,依次访问磁道788,845,911.999,700,432.396,165,164,25,磁头移动的距离是(999-734)+(999-25)=1239。
不需要一个个得算,算整体
采用 SSTF 算法时,依次访问的磁道是 700,788,845911,432,396,165,164,25,磁头移动的距离是(734-700)+(911-700)+(911-25)=1131
减少延迟时间
处理时间
磁头读入一个扇区数据后需要一小段时间处理
如果逻辑上相邻的扇区在物理上也相邻,则读入几个连续的逻辑扇区,可能需要很长的"延迟时间”
磁盘地址结构的设计
为什么磁盘的物理地址是(柱面号,盘面号,扇区号) 而不是(盘面号,柱面号,扇区号)?
原因
读取地址连续的磁盘块时,采用(柱面号,盘面号,扇区号)的地址结构可以减少磁头移动消耗的时间
若物理地址结构是(盘面号,柱面号,扇区号),且需要连续读取物理地址(00, 000, 000)~(00, 001, 111)的扇区:需要启动磁头臂,将磁头移动到下一个磁道
若物理地址结构是(柱面号,盘面号,扇区号),且需要连续读取物理地址(000, 00, 000)~(000, 01, 111)的扇区:由于柱面号/磁道号相同,只是盘面号不同,因此不需要移动磁头臂。只要激活相邻磁头即可
减少延迟时间的方法
交替编号
让编号相邻的扇区在物理上不相邻
使读取连续的逻辑扇区所需要的延迟时间更小。
错位命名
让相邻盘面的扇区编号“错位"
不同盘面之间错位命名
原理:
与"交替编号"的原理相同。“错位命名法"可降低延迟时间
0号盘面的0号扇区下面对应的可能是1号盘面的7号扇区
磁盘的管理
磁盘初始化
1. 进行低级格式化(物理格式化)
是磁盘制造商在生产磁盘时进行的操作
新磁盘是空白盘,必须分成扇区以便磁盘控制器能进行读/写操作
负责创建磁盘的物理结构
负责创建磁盘的物理结构
步骤
将磁盘的各个磁道划分为扇区
确定管理扇区所需要的各种数据结构
注
管理扇区所需要的各种数据结构一般存放在头、尾两个部分
扇区校验码
校验码用于校验扇区中的数据是否发生错误
如奇偶校验、CRC循环冗余校验码等
控制信息(如扇区号、磁道号等)
这些信息在低级格式化阶段被写入磁盘,因此磁盘控制器能够理解如何访问各个扇区
一个扇区的组成
头
数据区域
一个扇区可以存放的数据大小相等
尾
前一个数据库指向下一个数据块的指针可以保存在尾部
链接指针不用占用数据区域
2. 将磁盘分区
将磁盘分为由一个或多个柱面组成的分区
每个分区由若干柱面组成
C盘、D盘、E盘
每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中
3. 进行高级格式化(逻辑格式化)
创建文件系统
包括
创建文件系统的根目录
初始化存储空间管理所用的数据结构(如位示图、空闲分区表)
对空闲磁盘块进行管理的数据进行初始化
操作系统将初始的文件系统数据结构存储到磁盘上
这些数据结构包括空闲和已分配的空间及一个初始为空的目录
注
操作系统的引导程序
位于磁盘活动分区的引导扇区
必然产生在分区之后
引导块/启动块/启动分区
初始化程序(自举程序)
完成计算机开机时需要进行的一系列初始化工作
位置
磁盘
完整的自举程序放在磁盘的启动块(即引导块/启动分区)上
启动块位于磁盘的固定位置
ROM(只读存储器)
只存放很小的“自举装入程序”
注: ROM一般是出厂时就集成在主板上的
数据在出厂的时候就写入了,并且以后不能再修改
万一需要更新自举程序,将会很不方便,因为ROM中的数据无法更改
启动磁盘/系统磁盘
拥有启动分区的磁盘称为启动磁盘或系统磁盘(如C盘)
步骤
开机时计算机先运行“自举装入程序”
通过执行该程序就可找到引导块
将完整的“自举程序”读入内存,完成初始化
坏块的管理
坏块
坏了、无法正常使用的扇区
硬件故障
操作系统是无法修复
应该将坏块标记出来,以免错误地使用到它
简单的磁盘
在逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查
标明哪些扇区是坏扇区
比如:在 FAT 表上标明
坏块对操作系统不透明
操作系统在对存储空间进行管理时,要读取文件分配表的内容,坏块记录在文件分配表中
复杂的磁盘
磁盘控制器(磁盘设备内部的一个硬件部件)会维护一个坏块链表
在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化
会保留一些“备用扇区”,用于替换坏块。
这种方案称为扇区备用
这种处理方式中,坏块对操作系统透明(不可知)
固态硬盘SSD
原理
基于闪存技术Flash Memory
没有机械部件
SSD优势最主要体现在随机存取的速度上
属于电可擦除ROM,即EEPROM
与U盘无本质差别,只是容量更大,存取性能更好
组成
闪存翻译层
负责翻译逻辑块号,找到对应页
地址变换的操作
存储介质:
多个闪存芯片(FlashChip)
每个芯片包含多个块 (block)
每个块包含多个页(page)
读写性能特性
读/写单位
页
相当于磁盘的“扇区"
“擦除”单位
块
擦干净的块,其中的每页都可以写一次,读无限次
支持随机访问
闪存翻译层
系统给定一个逻辑地址,闪存翻译层可通过电路迅速定位到对应的物理地址
随机读写不需要机械操作
速度明显高于磁盘
读快、写慢。(随机写慢)
擦除块慢
自身相比写速度慢于读速度
要写的页如果有数据,则不能写入,需要将块内其他页全部复制到一个新的(擦除过的)块中,再写入新的页
与机械硬盘相比的特点
SSD
没有机械部件,用电路控制访问位置
读写速度快,随机访问性能高
安静无噪音、耐摔抗震、能耗低、造价更贵
缺点
容易磨损
SSD的一个“块"被擦除次数过多(重复写同一个块)可能会坏掉
机械硬盘
通过移动磁臂旋转磁盘控制访问位置,有寻道时间和旋转延迟
机械硬盘的扇区不会因为写的次数太多而坏掉
磨损均衡技术
思想
将"擦除"平均分布在各个块上,以提升使用寿命
动态磨损均衡
写入数据时,优先选择累计擦除次数少的新闪存块
静态磨损均衡
SSD监测并自动进行数据分配、迁移
老旧的闪存块承担以读为主的储存任务
较新的闪存块承担更多的写任务
通常表现更优秀

SSD的写操作
当要更新的页(目标页)所在块(Block)中还有其他有效数据页时
寻找新块(或空白页)
控制器首先会寻找一个新的、已经擦除干净的块(或至少是目标页所在块的空白页)。更常见的是找一个全新的空白块。
写入更新数据 + 复制有效数据
将原块中的有效数据复制到空白块中
再把想写入的数据写入目标页
更新映射表:
一旦新块的数据写入完成(并校验无误),SSD 内部的闪存翻译层会立即更新其内部的 逻辑地址到物理地址的映射表
原来指向旧块中目标页和其他有效页的逻辑地址,现在都指向新块中对应的新物理页。
固态硬盘逻辑地址对应的物理地址可能会变
闪存翻译层修改正确映射关系
标记原块为无效:
系统要读/写的逻辑块号的数据存放在
存放在磁盘(机器硬盘)中对应磁盘块/扇区
磁盘读写单位以块为单位
固态硬盘中
逻辑块对应固态硬盘中的页

块:理解为磁道
页:理解为扇区
补充
可以改善磁盘设备I/O性能的是
重排I/O请求次序
也就是进行 I/O 调度
也就是题目给的混乱的请求次序,我们通过算法得到访问顺序
采用不同的调度算法磁头移动的磁道数不同
预读和滞后写:
预读(提前读) :
原理
在读当前块的同时,也将下一个盘块提前读入内存缓冲区
适用
采用顺序访问方式对文件进行访问
可预知下一次要读的盘块
优点
磁盘I/O次数可能减少
在访问下一个盘块时就不需要再启动磁盘,从而提升磁盘I/O速度
滞后写(延迟写) :
原理
缓冲区A中的数据本该立即写回磁盘,但没有立即把A中的数据写回磁盘,而是将缓冲区A挂到空闲缓冲区队列。
如果有别的进程申请使用该缓冲区时,才把A中的数据写回磁盘。
局部性原理
数据在不久之后有可能再次被访问
优点
只要缓冲区A仍在队列中,任何访问该数据的进程,都可以直接读出其中的数据而不必访问磁盘
可以减少磁盘I/O次数,改善性能
优化文件物理块的分布:
在采用链接组织和索引组织方式时,可以将一个文件分散在磁盘的任意位置
但如果安排的过于分散,则访问该文件时会增加磁头的移动距离。
而如果把文件物理块安排在相邻的一些磁道上,则访问文件时磁头移动距离就能减少,从而改善磁盘设备I/O性能。
在一个磁盘上设置多个分区不能改善磁盘设备I/O性能,反而可能会降低
操作系统相关数据所在盘经常会被访问,磁头来回移动
补充
逻辑XXX
都是为方便用户而设计的
逻辑地址
用户编程只需要关心逻辑地址(从0开始),而逻辑地址到物理地址的映射、转换则由操作系统负责
文件的逻辑地址
用户编程只需要文件的逻辑结构,但这种逻辑结构在物理上是如何存储的则由操作系统设计者针对硬件结构来选择(如磁带介质很难实现链接结构和索引结构)
逻辑设备名
用户程序中要使用某个I/O设备,只需要提供逻辑设备名即可,操作系统负责实现从逻辑设备名到实际物理设备的映射。即时换了一台物理设备,用户程序也不需要改变
从系统角度看,文件系统负责对文件的存储空间进行组织、分配,负责文件的存储并对存入文件进行保护、检索。
从用户角度看,文件系统根据一定的格式将用户的文件存放到文件存储器中适当的地方,当用户需要使用文件时,系统根据用户所给的文件名能够从文件存储器中找到所需要的文件。
是否会产生饥饿问题考虑系统中总是持续存在某个进程/磁道的访问