前言
以下内容源自计算机操作系统（第四版）
关于操作系统，
CSDN有很多的优秀博客。
在这里，
本文摘取其他博客内容，
并附上相关链接，
如有侵权，
联系删除，
仅供学习交流使用
推荐
计算机操作系统(第四版)之文件管理、磁盘存储器的管理要点梳理
第八章 磁盘存储器的管理
8.1 外存的组织方式
文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有：
1）连续组织方式。
2）链接组织方式.
3）索引组织方式。
8.1.1 连续组织方式
为每个文件分配一组连续的相邻物理块, 形成的文件结构称顺序文件结构, 物理文件称顺序文件。这种分配方式保证了记录的逻辑顺序, 与占用盘块的物理顺序一致; 在目录项的"文件物理地址"字段中存放该文件的第一个记录所在盘块号和文件长度(块数)。如:
连续分配的优缺点
优点: 顺序存取简单容易, 也支持直接(随机)存取。 顺序存取速度快, 寻道次数和寻道时间最少。 也适合随机访问, 计算出盘块地址直接访问。 缺点: 易产生外部碎片, 降低外存空间的利用率; 可利 用紧凑法将外部碎片拼接成连续存储空间, 但紧凑 一次需要进行大量的磁盘操作花费大量的时间。 不利于文件的插入和删除。 必须事先知道文件的大小, 对于动态增长的文件效果较差。需要估算预留的连续外存空间, 预留空间不足将引起大片磁盘空间的移动, 预留空间太大将使大量的外存空间长期空闲。
8.1.2 链接组织方式
将文件存放在多个离散的盘块中, 同一文件的盘块链接成一个链表, 消除外部碎片, 显著的提高了外存空间的利用率, 有利于文件插入和删除, 有利于文件的动态扩充。
1. 隐式链接
在文件目录的每个目录项中,都含有指向链接文件第一个盘块和最后一个盘块的指针,
而在每个盘块中都含有指向下一个盘块的指针,只有508字节供使用。
缺点: 只适合顺序访问, 随机访问要从头查找极低效。
可靠性差, 盘块的指针出现问题会导致链断开。
更多的寻道次数和寻道时间。
解决方法:
可将几个盘块组成一个簇, 减少查找指定块的时间。
2. 显式链接
将链接文件各物理块的指针存放在内存的一张链接表中, 整个磁盘仅设一张表称为文件分配表(FAT), 表项的序号是物理盘块号, 每个表项中存放链接指针(下一盘块号)。每个文件的第一个盘块号填入该文件的文件控制块(FCB)的"物理地址"字段中。记录的查找过程全部在内存中进行, 检索速度快、访问磁盘磁盘次数少、可靠性高。
8.1.3 FAT技术
8.1.4 NTFS的文件组织方式
8.1.5 索引组织方式
链接分配存在的问题：
要顺序查找许多盘块号, 不支持高效的直接存取。
FAT占用较大的内存空间。
1. 单级索引分配
为每个文件分配一个集中存放的索引块(表), 该表实质就是磁盘块地址数组,其中第i项存放指向文件的第i块盘块号, 该文件的目录项中存储了指向该索引块的指针;支持直接存取, 如:记录号m 第i块 盘块号
2. 多级索引分配
对于大文件, 当分配的盘块号已装满一个索引块时, 必须另分配索引块, 各索引块通过指针连结起来,文件太大索引块太多时, 检索索引块将是低效的, 此时应为这些索引块再建立一级索引, 形成了两级索引, 必要时还可建立更多级的索引分配方式。
3. 混合(增量式)索引分配方式
索引分配方式的索引块花费较多空间,小文件索引块利用率更低。UNIX用混合索引模式避免此缺点。每个文件的索引结点含13个地址项 i.addr(0)~ i.addr(12), 每项4个字节; 前10项存放直接地址(物理块号), 若文件大于40kB，则用i.addr(10)指向单级索引块进行一次间接寻址,该块中最多可放1k个物理块号,文件可长达4MB; 还可用 i.addr(11) 和 i.addr(12) 作为二次和三次间接寻址, 文件最大长度分别可达4GB和4TB。
对比三种分配的优缺点
连续分配
优点:顺序存取简单高效,寻道距离次数少,访问速度快, 也适合随机访问,算出块地址直接访问。
缺点: 有外部碎片,外存利用率低,插入和删除不容易
链接分配
优点: 消除外存碎片, 外存利用率高, 有利于文件的动态扩充, 容易插入和删除,
缺点:不适合随机访问,可靠性差,寻道次数多速度慢
显式链接分配可显著减少寻道次数,提高检索速度, 但FAT占用了较大的内存空间
索引分配
优点: 链接分配的全部优点, 还适合随机访问,寻道次数少, 检索速度快。
缺点: 索引块费较多空间,小文件尤甚,混合索引可避免
8.2 文件存储空间的管理
为了实现前面任何一种文件组织方式，都需要为文件分配盘块，因此必须知道磁盘上哪些盘块是可用于分配的。故在文件分配磁盘时，除了需要文件分配表外，系统还应为可分配存储空间设置相应的数据结构，即设置一个磁盘分配表，用于记住可供分配的存储空间情况。此外，还应提供对盘块进行分配和回收的手段。不论哪种分配和回收方式，存储空间的基本分配单位都是磁盘块而非字节。
8.2.1 空闲表法和空闲链表法
1. 空闲表法
1）空闲表。
空闲表法属于连续分配方式，它与内存的动态分配方式雷同。
即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列。
2）存储空间的分配与回收。
空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。
系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。
应该说明，在内存分配上，虽然很少采用连续分配方式，然而在外存的管理中，由于这种分配方式具有较高的分配速度，可减少访问磁盘的 I/O 频率，故它在诸多分配方式中仍占有一席之地。例如，在前面所介绍的对换方式中，对对换空间一般都采用连续分配方式。对于文件系统，当文件较小(1～4 个盘块)时，仍采用连续分配方式，为文件分配相邻接的几个盘块；当文件较大时，便采用离散分配方式。另外，对于多媒体文件，为了能减少磁头的寻道时间，也采用连续分配方式。
2. 空闲链表法
1）空闲盘块链。
这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末
尾。
2）空闲盘区链。
这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。
位示图法
8.2.2 位示图
1. 位示图
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘的总块数。位示图也可描述为一个二维数组 map[m, n]。
2. 盘块的分配
根据位示图进行盘块分配时，可分三步进行：
1）顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
2）将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第 i 行、第 j 列，则其相应的盘块号应按下式计算：
b = n * (i - 1) + j；
式中，n 代表每行的位数。
3）修改位示图，令 map[i,j] = 1。
3. 盘块的回收
盘块的回收分两步：
1）将回收盘块的盘块号转换成位示图中的行号 i 和列号 j 。转换公式为：
i = (b - 1) / n + 1；
j = (b - 1) % n + 1；
2）修改位示图。令 map[i,j] = 0。
位示图常用于微型机和小型机中。
8.2.3 成组链接法
空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。在 UNIX 系统中采用的是成组链接法，这是将上述两种方法相结合而形成的一种空闲盘块管理方法，它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。
8.3 提高磁盘I/O速度的途径
其中最主要的技术便是磁盘高速缓存。
8.3.1 磁盘高速缓存(Disk Cache)
磁盘高速缓存的形式
(1) 专用: 在内存中单独开辟一块固定的区域专用。
(2) 共享: 所有空闲内存为缓冲池与请求分页系统共享
1. 数据交付方式
(1) 数据交付
(2) 指针交付
2. 置换算法
常用的算法有:最近最久未使用算法LRU, 最近未使用算法NRU和最少使用算法LFU。
许多系统除了考虑最近最久未使用这一原则外还要考虑：访问频率、可预见性、数据的一致性。
3. 周期性地写回磁盘
根据LRU算法,经常访问的盘块可能长期不被回写,可能导致丢失数据, 可采用周期性(几十秒)地写回磁盘。
8.3.2 提高磁盘I/O速度的其他方法
1. 提前读
预先将下一盘块数据一次读入减少读盘次数。
2. 延迟写
考虑缓冲区的数据不久之后可能还会访问故暂时不写入磁盘, 将它挂在空闲队列的末尾, 当它最久未被访问，到了队列之首要被淘汰时再写入磁盘。
3. 优化物理块的分布
分配物理块时, 把有可能顺序存取的块放在一起, 尽量分布在同一柱面或相邻柱面上, 从而减少磁盘臂的移动次数。但采用线性链表来组织空闲块时比较困难, 此时, 将同一磁道的若干个盘块组织成一簇, 以簇为单位进行分配, 可减少磁头的平均移动距离。
4. 虚拟盘
利用内存空间区仿真磁盘,又称RAM盘; 断电或关机后虚拟盘的数据将丢失, 因此虚拟盘仅放临时数据。与磁盘高速缓存的区别在于：内容由用户控制，而不是OS控制。
8.3.3 磁盘冗余阵列
1. 并行交叉存取
为提高对磁盘的访问速度, 用N台磁盘驱动器组成磁盘阵列, 系统将数据分为若干个子盘块数据分别存储到各个磁盘的相同位置上,并行传输到内存,由于采用了并行存取方式加快了访问速度N-1倍。
2. 廉价磁盘冗余阵列(Redundant Array of Inexpensive Disk)
为提高磁盘存储数据的可靠性,采用冗余存储; 如: N=7, 6个盘做数据盘,1个盘做奇偶校验盘, 校验盘存储6个数据盘的奇偶校验值; 当某个盘损坏时可以用其它6个盘的数据盘恢复数据; RAID 有 0-7级, 其中 0 级无冗余, 1 级是镜像存储冗余50%, 3 级使用专用校验盘, 5 级将校验值螺旋分布在阵列的所有磁盘上。
3. RAID的优点
可靠性高、磁盘的访问速度高、性能/价格比高。
8.4 提高磁盘可靠性的技术
容错技术是通过在系统中设置冗余部件的办法，来提高系统可靠性的一种技术。
磁盘容错技术往往也被人们称为系统容错技术 SFT。可把它分成三个级别：第一级(SFT-I)是低级磁盘容错技术；第二级(SFT-II)是中级磁盘容错技术；第三级是系统容错技术，它基于集群技术实现容错。
8.4.1. 第一级 磁盘容错技术SFT-1
防止因磁盘表面缺陷造成的数据破坏或丢失, 包括双份目录、双份文件分配表和写后读校验等措施
(1)双份目录和双份文件分配表
(2)热修复重定向和写后读校验
热修复重定向:将磁盘的2~3%作为热修复重定向区
写后读校验:写盘后立即读并与原数据校验
8.4.2. 第二级 磁盘容错技术SFT-2
(1) 磁盘镜像
两个磁盘驱动器互为备份
(2)磁盘双工
通道、磁盘控制器和磁盘驱动都为双份
廉价磁盘冗余阵列(RAID):第5章已介绍块
交错校验
8.4.3 基于集群技术的容器功能
8.4.4 后背习题
8.5 数据一致性控制
同一数据存放在不同的文件中, 对它修改时应对不同的文件都统一修改, 才能保证数据的一致性。修改时数据的流向是, 磁盘块内存写回磁盘块。若在写回之前, 系统崩溃, 则文件系统数据出现不一致。
系统应配置保证数据一致性的软件和相应的硬件，硬件采取冗余技术配置一个高度可靠的存储系统, 称为稳定存储器; 目前广泛采用磁盘双工方式来实现稳定存储器。设计保证数据一致性的实用程序, 当系统再次启动时, 运行该程序, 检查磁盘块和目录系统。
8.5.1 事务
1. 事务的定义
事务是用于访问和修改数据的一个程序单位, 由一系列相关的读写操作组成; 被访问的数据可以分散在不同位置, 只有一系列读写操作全部完成才能以托付操作(Commit Operation)终止操作; 而只要有一个操作失败就执行夭折操作(Abort Operation)。
为了保证数据的一致性, 对于夭折事务所操作过的数据必须恢复原来的状态, 使该事务退回(rolled back),保证一个事务对一批数据修改操作,要么全部完成要么 一个也不修改, 这种特性称事务的原子性。
2. 事务记录(Transaction Record)
为了实现事务的原子修改, 用事务记录这种数据结构来实现, 它被存放在稳定存储器中, 用来存储事务运行时数据项修改的全部信息, 故又称为运行记录(Log), 该记录包括下列字段:
事务名
数据项名
旧值
新值
3. 恢复算法
如果系统发生故障,应对以前的事务进行清理, 通过查找事务记录表做如下操作：
(1) 如果在Log表中只有(Ti开始)记录无(Ti托付)记录则调用undo(Ti ) 把所有被Ti修改过的数据恢复为原值。
(2)如果在Log表中既有(Ti开始)记录又有(Ti托付)记录则调用redo(Ti ) 把已被Ti修改过的数据设置为新值。
8.5.2 检查点(Check Points)
1. 检查点的作用
引入检查点的主要目的，是为了对事务记录的清理工作经常化, 设置检查点记录; 每隔一定的时间做一次清理:
将内存中的当前事务记录表的所有记录, 和所有已修改的数据, 输出到稳定存储器中; 再将检查点记录输出到稳定存储器中; 每当出现一个检查点记录便执行恢复操作。
2. 新的恢复算法
发生故障后,恢复算法只需对最后一个检查点之后的事务记录进行处理。
即从最后一个检查点之后的第一个事务记录开始,对所有的事务Tk , 在Log表中出现(Tk托付)记录则执行redo(Tk ), 未出现(Tk托付)记录则执行undo(Tk )。
8.5.3 并发控制
由于事务具有的原子性, 使得一个事务执行完后才允许另一事务执行, 即事务对数据项的修改是互斥的,事务的这种特性称为顺序性,将实现顺序性的技术称为并发控制。可以用互斥信号量来保证事务处理的顺序性,但用的最广的是“锁”。
1. 利用互斥锁实现顺序性
设置一种用于实现互斥的锁, 简称互斥锁,为每一个共享对象设一把互斥锁, 如果事务 Ti 需要对一批对象进行访问,则为了保证事务操作的原子性, 应先获得这批对象的互斥锁, 将他们全部锁住, 如果成功便可以对这批对象执行读写操作,然后全部开锁, 若某对象已被其它事务锁住, 则Ti 要将已锁住的对象全部开锁。
2. 利用互斥锁和共享锁实现顺序性
对于共享文件,写只能互斥进行, 但读操作却允许多个事务同时去读, 显然用互斥锁不能实现同时读, 为此引入另一种锁共享锁。互斥锁仅允许一个事务对相应的对象执行读或写, 共享锁则允许多个事务对相应的对象执行读操作, 同时不允许任何一个事务对相应的对象执行写操作。类似于读者写者问题。
8.5.4 重复数据的一致性问题
1.重复文件的一致性
以UNIX类型的文件系统为例,通常一个文件的目录项由一个文件名和一个索引结点号组成; 当有重复文件时, 一个文件的目录项由一个文件名和若干个索引结点号组成。保证重复文件的一致性用两种方法：
(1) 当一个文件被修改后,可查目录, 从各i结点找到各拷贝的物理位置, 对这些拷贝做同样修改。
(2) 为新修改的文件建立几个新拷贝取代原来的拷贝。
2. 盘块号一致性的检查
两张表，每块对应一个表中的计数器，初值为0
表一：记录了每块在空闲块表中出现的次数
表二：记录了每块在文件中出现的次数
