操作系统----文件管理 参考王道操作系统与小林coding图解操作系统
前置：简单的个人学习笔记上传，仅供参考，想要md文档的可以评论留言
参考内容
CSDN博主 BitHachi的博文 《王道操作系统》学习笔记总目录+思维导图
CSDN博主 小林coding的图解操作系统
4 文件管理
4.1 文件管理与文件系统概述
4.1.1 文件管理主要内容
-
文件系统的层次机结构
-
文件的内部组织，即文件的逻辑机构
-
文件的外部组织，即目录机构
-
文件的存放，文件的分配方式，即文件的物理结构
-
空闲磁盘的管理
-
操作系统提供的对文件的基本操作
-
操作系统提供的额外功能：文件共享与问价加密
4.1.2 文件系统的层次
4.1.3 文件的逻辑结构
-
无结构文件
- 文件内部的数据就是一系列二进制流或者字符流组成，没有明显的结构特性，又称“流式文件”。
-
有结构文件：由一组相似的记录组成，又称“记录式文件”
-
按照记录的长度是否相等进行分类
记录：参考数据库表的行记录，一行记录又由若干个数据项(列)组成
每个记录一般还会有一个数据项作为关键字，标识每条记录（主键）
- 定长记录
- 可变长记录
-
根据记录的逻辑组织方式分类
- 顺序文件：逻辑上是连续存储的
- 物理存储方式
- 顺序存储，类似于顺序表，物理上连续
- 链式存储，类似于链表，物理上不一定连续
- 记录的存放顺序
- 串结构：按照记录存放的时间顺序链接
- 顺序结构：按照关键字的顺序进行排序
- 物理存储方式
- 索引文件
- 通过建立索引表，记录索引与记录之间的关系（参考数据库索引）
- 索引顺序文件
- 一个索引对应一组记录
- 每组记录是一个顺序文件
- 多级索引顺序文件按
- 顶级索引
- 低级索引
- 顺序表
- 顺序文件：逻辑上是连续存储的
-
4.1.4 文件的目录结构
- 文件目录的实现
- 目录项（文件控制块/FCB）
- 用来存放文件的文件名和索引节点的指针
- 以及其它目录项的层级关联关系
- 索引节点（inode）
- 用来记录文件的元信息
- 文件大小
- 访问权限
- 创建，修改时间
- 数据在磁盘的位置
- 用来记录文件的元信息
- 目录项（文件控制块/FCB）
- 目录的结构
- 单级目录结构
- 整个系统建立一张目录表，每个文件占一个目录项
- 两级目录结构
- 主文件目录
- 记录用户名及响应的用户文件目录的存放位置
- 用户文件目录
- 存放用户的文件，由用户的文件FCB组成
- 主文件目录
- 多级目录结构（树形目录结构）
- 绝对路径
- 当前目录和相对路径
- 可以减少磁盘I/O的次数
- 有向无环图目录结构
- 在树形目录结构的基础上，增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图，可以利用不同的文件名指向同一个文件，方便文件共享。
- 单级目录结构
4.1.5 文件的物理结构（物理存储分配）
-
文件块，物理块
- 与内存相似，物理磁盘也被分为大小相等的块（物理块），文件的逻辑地址也被分成了大小相等的文件块。
- 操作系统为文件分配存储空间都是以块为单位的
- 通过（逻辑块号，块内地址）得到（物理块号，块内地址）
-
分配方式
-
连续分配
- 每个文件在磁盘上占有一组连续的块
- 索引节点记录文件的起始块号和块的个数
- 优缺点
- 文件的顺序读写快
- 不方便扩展，容易产生磁盘碎片
-
非连续分配：链式分配和索引分配
-
链式分配：隐式链接和显式链接
-
隐式链接
-
索引节点记录文件存放的起始块号和结束块号
-
除了结束块号，每个块都要存放指向下一个块的指针
-
优缺点
- 不支持随机访问，只能顺序访问，指针存储也要消耗空间
- 可以解决碎片问题，方便文件扩展
-
-
显式链接
- 只需记录文件的起始块号
- 把用于链接文件各物理块的指针显示的存放在一张表中，即文件分配表（File Allocation Table，FAT）
- FAT存放在内存中并且常驻内存
- 优缺点
- 解决了碎片问题，而且支持随机访问
- 不适用于大磁盘，大磁盘的FAT会占用太多内存
-
-
索引分配：为每个文件都建立索引表，索引表记录文件的逻辑块对应的物理块，索引节点记录索引块（即记录索引表所在的物理块）
-
链式索引块：
- 索引表太大，一个索引块装不下，可以将多个索引块链接起来
- 只能顺序访问多个索引块，而且指针受损会损坏文件
-
多级索引：
- 建立多层索引，第一层的索引块指向第二层的索引块
- 各层的索引表的大小不能超过一个物理块的大小
- 各级索引表未调入内存的情况下，访问一个数据块需要 k+1 次磁盘I/O
- 优缺点
- 对小文件而言，也要进行 k+1 次磁盘I/O
-
混合索引
- 多种索引方式结合，既包含含直接索引，又包含一级间接索引，还包含多级间接索引
-
-
-
4.1.6 空闲磁盘的管理算法
-
空闲表法
- 适用于连续分配方式
- 为所有的空闲空间建立一张表，表中包含空闲空间的第一个块号和空闲块的个数
-
空闲链表法
- 空闲盘块链：以盘块为单位组成一条空闲链
- 空闲盘区链：以盘区为单位组成一条空闲链 (连续的空闲盘块组成空闲盘区)
-
位示图法
- 利用二进制的一位表示磁盘的使用情况，每个盘块都有一个二进制位与其对应
- 值为0表示对应的盘块空闲，值为1表示盘块已经分配
-
成组链接法
4.1.7 文件的基本操作
-
创建文件（create系统调用）
- 在外存找到空闲空间
- 在对应路径的目录表中创建目录项
-
删除文件（delete系统调用）
- 找到文件名对应的目录项和索引节点
- 回收磁盘
- 删除目录项和索引节点
-
打开文件（open）
-
根据文件名找到目录项和索引节点，确定当前用户的权限
-
在当前文件的相关信息放入当前进程和系统的打开文件表中
-
根据打开文件表的编号进行后续的操作
每个进程有一个打开文件表，每条记录都有一个编号，此外还有文件名，读写指针，访问权限，系统打开文件表中对应的索引号
整个系统只有一个打开文件表，记录文件名，外存地址，打开计数器等
-
-
-
关闭文件（close）
- 删除进程的打开文件表中对应的表项
- 回收分配给该文件的内存空间等资源
- 系统的打开文件表的打开计数器count - 1,若count =0，则删除对应的表项
-
读文件（read）
- 根据读指针将数据从外存读到内存
-
写文件（write）
- 根据写指针将指定大小的数据写回外存
4.1.8 文件的共享 软链接和硬链接
-
硬链接
- 多个目录项的索引节点指针指向同一个索引节点（inode）
-
软链接
- 相当于重新建立了一个文件，这个文件有独立的索引节点，但是文件的内容是另一个文件的路径（类似于windows中的快捷方式），访问软链接时相当于访问到了另外一个文件。
4.1.9 文件的保护
- 口令保护
- 为文件设置一个访问口令，访问文件时必须提供正确的口令
- 加密保护
- 通过加密算法对文件进行加密
- 访问控制
- 增加访问控制权限列表，记录每个用户对该文件的执行权限
4.2 磁盘组织与管理
4.2.1 磁盘的结构
-
磁盘：磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据
-
磁道：磁盘的盘面被划分为一个个磁道，每一圈都称为磁道
-
扇区：磁道被分为一个个扇区，每个扇区就是一个磁盘块
- 最内侧磁道上的扇区面积最小，因此数据密度最大
-
盘面：一个盘片可能会有正反两个盘面
-
柱面：所有盘面中 相对位置相同的磁道组成柱面
-
磁盘的分类
-
按磁头能够移动
- 活动头磁盘：磁臂来回伸缩带动磁头定位磁道
- 固定头磁盘：每个磁盘的每个磁道都有一个磁头
-
按照盘片能否更换
- 可换盘磁盘
- 固定盘磁盘
-
-
磁盘的读写
- 需要把磁头移动到想要读写的扇区所在的磁道，磁盘转起来，让目标扇区从磁头下面划过，才能完成对扇区的读写操纵
- 一次磁盘读写需要花费的时间
- 寻道时间：磁头移动到指定磁道花费的时间
- 启动磁头臂的时间
- 移动磁头的时间
- 延迟时间：旋转磁盘使磁头定位到目标扇区所需要的时间
- 传输时间：磁盘读出或者写入磁盘的时间
- 寻道时间：磁头移动到指定磁道花费的时间
- 减少延迟时间的方法
- 交替编号：让编号相邻的扇区在物理上不相邻
- 错位命名：让相邻盘面的扇区编号“错位”
- 使用（柱面号，盘面号，扇区号）的磁盘地址结构
- 在读取地址连续的磁盘块时，可以减少磁头的移动
4.2.2 磁盘调度算法
图片说明：假定进程的请求顺序为：55，58，39，18，90，160，150，38，184号磁道，磁头的初始位置为100号磁道
-
先来先服务（FCFS)
- 根据进程请求访问磁盘的先后顺序进行调度
-
最短寻找时间优先算法（SSTF)
- 优先处理与当前磁头所在磁道最近的磁道，可以保证当前最短，不能保证总的最短（贪心）
- 可能产生“饥饿”现象：磁头在一个小区域内来回移动
- 优先处理与当前磁头所在磁道最近的磁道，可以保证当前最短，不能保证总的最短（贪心）
- 扫描算法（SCAN）
- 规定只有磁头移动到最外侧磁道时才能往内移动，移动到最内侧此道的时候才能往外移动，返回时可以响应
- 优缺点
- 不会产生饥饿
- 中间部分的磁道会比较占便宜，中间部分比其他部分响应频率比较多，每个磁道的响应频率存在差异
-
循环扫描算法（C-SCAN)
-
只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动到起始端而不处理任何请求
-
-
LOOK算法
- 磁头仅在每个方向上移动到最远的请求位置，然后立即反向移动，不需要移动到磁盘的最末端，在反向移动的途中会响应请求
- C-LOOK算法
- 磁头移动到最大磁道的请求位置就返回，返回的途中不响应请求
4.2.3 磁盘的管理
-
磁盘初始化
- 进行低级格式化(物理格式化)，将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域(如512B大小)、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码(如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)
- 将磁盘分区，每个分区由若干柱面组成(即分为我们熟悉的C盘、D盘、E盘)
- 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构(如位示图、空闲分区表)
-
引导块
- 计算机开机时需要进行一系列的初始化工作，这些初始化工作通过执行初始化程序（自举程序）完成
- 初始化程序可以放到主板继承的只读存储器（ROM）中，但是修改不方便，可以将“自举装入程序”放入ROM，通过执行该程序找到引导块，引导块中存放完整的自举程序。
-
坏块的管理
- 对于简单的磁盘，可以在逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明。(在这种方式中，坏块对操作系统不透明)
- 对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件)会维护一个坏块链表。在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化。
会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。
片转存中…(img-PUkO4Sfy-1650618330704)]
-
最短寻找时间优先算法（SSTF)
- 优先处理与当前磁头所在磁道最近的磁道，可以保证当前最短，不能保证总的最短（贪心）
- 可能产生“饥饿”现象：磁头在一个小区域内来回移动
- 优先处理与当前磁头所在磁道最近的磁道，可以保证当前最短，不能保证总的最短（贪心）
[外链图片转存中…(img-zbgSeqhc-1650618330704)]
- 扫描算法（SCAN）
- 规定只有磁头移动到最外侧磁道时才能往内移动，移动到最内侧此道的时候才能往外移动，返回时可以响应
- 优缺点
- 不会产生饥饿
- 中间部分的磁道会比较占便宜，中间部分比其他部分响应频率比较多，每个磁道的响应频率存在差异
[外链图片转存中…(img-X4ESx4qX-1650618330705)]
-
循环扫描算法（C-SCAN)
-
只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动到起始端而不处理任何请求
[外链图片转存中…(img-OX7C1ZaE-1650618330705)]
-
-
LOOK算法
- 磁头仅在每个方向上移动到最远的请求位置，然后立即反向移动，不需要移动到磁盘的最末端，在反向移动的途中会响应请求
[外链图片转存中…(img-mh1Wdw0m-1650618330705)]
- C-LOOK算法
- 磁头移动到最大磁道的请求位置就返回，返回的途中不响应请求
[外链图片转存中…(img-Hz2CCUSo-1650618330705)]
4.2.3 磁盘的管理
- 磁盘初始化
- 进行低级格式化(物理格式化)，将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域(如512B大小)、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码(如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)
- 将磁盘分区，每个分区由若干柱面组成(即分为我们熟悉的C盘、D盘、E盘)
- 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构(如位示图、空闲分区表)
- 引导块
- 计算机开机时需要进行一系列的初始化工作，这些初始化工作通过执行初始化程序（自举程序）完成
- 初始化程序可以放到主板继承的只读存储器（ROM）中，但是修改不方便，可以将“自举装入程序”放入ROM，通过执行该程序找到引导块，引导块中存放完整的自举程序。
- 坏块的管理
- 对于简单的磁盘，可以在逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明。(在这种方式中，坏块对操作系统不透明)
- 对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件)会维护一个坏块链表。在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化。
会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。