计算机操作系统 - 第八章：磁盘存储器的管理 - 《计算机专业课笔记》

8.1 外存的组织方式
8.2 文件存储空间的管理
8.3 提高磁盘I/O速度的途径（了解）
8.4 提高磁盘可靠性的技术
8.5 数据一致性控制
参考

💡整理不易，先赞后看，养成习惯💡

8.1 外存的组织方式

文件的组织方式也就是文件如何在外存上的存储方式。
在了解组织方式之前我们需要知道一个前置的知识点：
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。为了便于数据的传输，磁盘块的大小和内存块的大小是一致的。
当然用户无需关心物理块的具体位置等信息，只需要通过逻辑块来操作数据即可。
一般来说，磁盘块的大小都不会很大，否则会引起类似内存块的内碎片等问题，文件的大小一般都会比磁盘块大，所以文件在磁盘中会分块存储。
操作系统想要调用一个完整的文件就需要在磁盘中寻找到对应的磁盘块，下面要探讨的就是如何将文件分块存储在磁盘中。

连续组织方式

连续组织方式又称为连续分配方式，要求为每个文件分配一组相邻接的盘块。

如图所示，文件aaa存放的物理块位置都是连续的。对应文件目录如下：

文件名	起始块号	块数
aaa	4	3

对应物理块和逻辑块的映射方式也很明了：物理块号 = 起始块号 + 逻辑块号
我们都知道磁盘的读取都是通过磁头的移动进行读取的，所以连续的磁盘块存储带来的好处就是：

顺序访问容易
顺序访问速度快（一般来说顺序读写就是最快的）

同样，由于是顺序存储，所以同时支持顺序访问和随机访问。
缺点自然也很明显：

要求为文件分配一个连续的存储空间，但如果文件较大，这个空间很难找打
必须事先知道文件的长度
不能灵活的删除和插入记录，因为为了保持磁盘块连续，一旦插入记录，后面的磁盘块的数据就需要整体迁移，删除记录同理

链接组织方式
对应连续方式，链接组织方式就是使用链表方式串联起所有的磁盘块。
链式组织的优点如下：
消除了磁盘的外部碎片，提高了外存的利用率
对插入、删除和修改记录都非常容易
能适应文件的动态增长，无需事先知道文件的大小。
隐式链接
隐式链接就是在每一个磁盘块中添加一个指针，用于记录下一个磁盘块的位置。

由于这个指针对于用户是透明的，所以叫做隐式链接。
这种方式也有弊端，由于指针是存储在磁盘块的，所以完全不支持随机访问，这样会导致访存效率低下。
举个例子，如果想要访问23号磁盘块，那必须需要先访问9再访问2，最后才能访问到23，为了访问这一个磁盘块需要访问3个磁盘块。
同时只通过一个链接指针将一大批离散的盘块链接起来，其可靠性较差，而且链接指针占用一定的空间。

为了提高检索速度和减小指针多占据的空间，可将几个盘块组成一个簇。进行盘块分配时，是以簇为单位进行的。但会增加碎片。

显式链接

显式链接用于链接文件各物理块的指针显式的存放在内存的一张链接表中。该表在整个磁盘中仅设置一张。

如图所示，文件的目录项只需要记录起始块号即可，在FAT(文件分配表)中，每一个物理块对应记录链接的下一个物理块。
比如这里的文件aaa，首先找到2号物理块，再根据FAT依次找到5、0、1号物理块。当下一块为-1的时候，说明这个物理块已经是文件的最后一块。

💡文件分配表FAT存储在内存当中。

相比于隐式链接，显示链接具备了随机访问的特点。想要找到一个文件逻辑块对应物理块的位置，只需要查找内存中的FAT即可，无需在外存中不断访问磁盘。
举个例子，通过上图我们可以知道文件aaa的逻辑块号和物理块的对应关系：

逻辑块号	物理块号
0	2
1	5
2	0
3	1

这张表实际不在内存中存储的，而是根据FAT表对于链接路径查询可以动态生成的，有了这张表，如果想要访问逻辑块号3，操作系统就可以直接根据此表直接访问物理块号1，无需把前面的2/5/0号物理块访问一遍。
优点：查找记录到内存中的FAT表中查找，提高了检索速度，检索磁盘的访问次数。
缺点：不能直接存取；FAT占较大内存空间。

FAT详解

FAT中引入了“卷”的概念，支持将一个物理磁盘分成四个逻辑磁盘（比如C盘、D盘），每个逻辑磁盘就是一个卷（也称为分区）。

一个卷中包含了文件系统信息，一组文件以及空闲空间。每个卷专门划出一个单独区域存放自己的目录和FAT表。
从上面我们可以知道一个FAT表的基本组成：

物理块号（可以隐式存储）	下一块
x	y

为什么物理块号可以隐式存储？因为物理块号在FAT中是按序递增的，所以可以直接按照顺序推出，本质上无需记录。所以实际上FAT的记录只有一项**下一块**。

FAT技术主要有三种：

FAT12：FAT的表项占据12bit，换算为比特就是1.5B
FAT24：FAT的表项占据16bit，换算为比特就是2B
FAT32：FAT的表项占据32bit，换算为比特就是4B

以FAT12为例，表项占据**12bit**就表示对应物理块的个数有**2****12**** = 4K**个。所以对应FAT12，可以拥有最多的物理块的个数是4K。
如果此时告诉你一个盘块为512B则，一个磁盘最大容量为**2MB=4K×512B**。
如果以簇进行划分，四个盘块为一簇磁盘容量可达8M。

以簇进行划分，那么FAT对应的就不是物理块号，而是簇号。

索引组织方式

单级索引组织方式

实际中，打开某文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起，在访问到某个文件时，将该文件所对应的盘块号一起调入内存。

💡索引分配思想：为每个文件分配一个索引块，把分配给该文件的所有盘块号记录在该索引块中。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。

举个例子：

上图中文件aaa的索引块是7，所以先找到磁盘块**7**，在这个磁盘块中存储的就是文件aaa的所有盘块信息。

FAT把所有的盘块信息存储到了内存中索引组织方式把盘块信息存储到了磁盘中，一个磁盘块对应一个索引表。同样这里的逻辑块号也可以隐式存储。

优点
①索引分配方式支持直接访问当要读文件的第i个盘块时，可以方便地直接从索引块中找到第i块盘的盘块号；
②索引分配方式也不会产生外部碎片当文件较大时，索引分配方式无疑地是优于链接分配方式的。
缺点
① 可能要花费较多的外存空间
② 不适合小文件

多级索引组织方式

假设一种情况，当一个磁盘块的大小为1K，一个索引表项大小是4B，那么一个盘块最多可以包含1K / 4 = 256个索引表项，也就是包含256个磁盘块的映射。
但如果文件的大小超过了256磁盘块的大小之和了，此时就需要更多的索引块指针。
一种方法就是采用链表的方式，但这种方式十分低效：

如图文件aaa需要两个索引块7和15。在7号索引块中的最后一项记录中，会记录下一个索引块的位置，从而实现链接的方式。
更有效的解决方案是多级索引。
一张图就可以明白了：

也就是说文件aaa对应的索引块记录的是二级索引块的位置，也就是所谓的二级索引表。

💡接下来这个求解文件最大长度的计算必须会！ 假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。若某文件采用两层索引，则该文件的最大长度可以到2562561KB=65,536 KB= 64MB 如果是单级索引，最大长度就是256*1K = 256K

再直接记一个结论：

💡采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

优点：

既能顺序存取,又能随机存取
满足了文件动态增长、插入删除的要求也能充分利用外存空间，加快大型文件的查找速度。

缺点：访问一个盘块时，其所需访问的磁盘的次数随着索引级数增加。

增量索引组织方式

增量索引组织方式也可以叫做混合索引组织。
其思想就是：

小型文件直接寻址
中型文件一级索引
大型文件多级索引

如图所示：

这张表中，前五行不用管，是描述目录表的基本信息的。其余如下：

i.addr()：直接寻址，可以根据这一表项直接寻找到磁盘块的位置
single indirect：一级索引方式组织，根据这一表项可以找到对应索引块
double indirect：一级索引方式组织，根据这一表项可以找到对应一级索引表

8.2 文件存储空间的管理

为文件分配磁盘时，除了需要文件分配表外，系统还应该为可分配存储空间设置一个磁盘分配表，用户记录可供分配的存储空间情况。提供相应的分配和回收算法。

其实就类似空闲内存块的分配。

空闲表法和空闲链表法

空闲表法

要点如下：

属于连续分配方式，与内存的动态分配方式雷同一模一样。
系统为外存上的所有空闲区建立一张空闲表
空闲区按起始空闲盘块号递增次序排列

举个例子：

空闲表法中，如果文件想要存储进来，就必须要保证存储磁盘空间连续。
同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
存储空间的回收：采用类似于内存回收的方法。要考虑回收区是否与空闲表中的插入点的前区和后区相邻，对相邻者予以合并。

空闲链表法

空闲链表法顾名思义，就是可以让文件离散存储。
主要有两种方式：
（1）空闲盘块链

把磁盘上所有空闲块以盘块为单位链成一个链。分配时从链首开始摘下适当的盘块，回收时加入到空闲盘块链链尾。
（2）空闲盘区链

把磁盘上所有空闲盘区（每个盘区可包含若干个盘块）链成一个链。在每个盘区上除含有用于指示下一空闲盘区的指针外，还应有指明本盘区大小（盘块数）的信息。分配时可采用首次适应算法。

位示图法

💡位示图利用二进制的一位来表示磁盘中一个盘块的使用情况。
map[m,n] m*n为磁盘的总块数。

上表中：**1**表示该磁盘块被占用，**0**表示该磁盘块空闲。
按照上图所示，一共有16*16 = 256个磁盘块，那么**100**号磁盘块对应的位置就是：

y = 101 // 16 = 6
x = 101 % 16 = 5

对应的位置就是第六行的第五列。

注意磁盘块的下标一般都是从0开始的，所以**100**号磁盘块对应的是第**101**个磁盘块 有些题目位示图下标不一定是从1开始的，有可能是从0开始的

盘块的分配

顺序扫描位示图
找到盘块号对应的x,y
修改位示图，对应的位置由0置为1

盘块的回收

顺序扫描位示图
找到盘块号对应的x,y
修改位示图，对应的位置由1置为0
成组链接法
空闲盘块的组织
这种方法是吧空闲的磁盘块按照成组的形式进行组织，整体示意图如下：

一步步来分析，首先看最左边的部分：

首先这一部分叫做空闲盘块号栈（注意是空闲盘块号，所以存储的是空闲盘块号，而不是空闲盘块），上下两个空白区域不用管。

一个空闲盘块号栈占用一个磁盘块大小。