本次笔记内容：
12.12 打开文件的数据结构
12.13 文件的分配
12.14 空闲空间列表
12.15 多磁盘管理-RAID
12.16 磁盘调度
文章目录
打开文件
何谓“打开文件”
打开文件描述：
- 每个被打开的文件一个；
- 文件状态信息；
- 目录项、当前文件指针、文件操作设置等。
文件被打开后，放入打开文件表中。
打开文件表：
- 一个进程一个；
- 一个系统级的；
- 每个卷控制块也会保存一个列表；
- 所以如果有文件被打开将不能被卸载。
如上图，可能两个进程同时打开一个文件，用文件打开表可以管理。
打开文件的锁的保护机制
- 一些操作系统和文件系统提供该功能；
- 调节对文件的访问；
- 强制和劝告：
-
- 强制：根据锁保持情况和需求拒绝访问；
-
- 劝告：进程可以查找锁的状态来决定怎么做。
文件分配
比如，如果要写文件，文件增大，空间如何分配？
大多数文件很小：
- 需要对小文件提供强力的支持；
- 块空间不能太大。
一些文件非常大：
- 必须支持大文件（64-bit 文件偏移）；
- 大文件访问需要相当高效。
如何为一个文件分配数据块
分配方式：
- 连续分配；
- 链式分配；
- 索引分配。
指标：
- 高效：如存储利用（外部碎片）；
- 表现：如访问速度。
方法一：连续分配
如上图，文件头指针会指定起始块位置和文件长度。
产生问题：如果A文件在B文件前，A增长了，则B需要后移。
对于CD-ROM来说，是一种好的分配方法。因其高效性、只读性。
方法二：链式分配
如上图，链式存储很灵活，如果增大，则只需将尾指针后移。
但是问题是，访问必须是串行访问（假设访问链中第二个数据块，必须先找到第一个）。并且，不可靠，如果丢失一个，链就断了。
方法三：索引分配
如上图，专门设置一个索引数据块，一般放在文件头里。文件大小变化时，大量的修改只需要在索引块中。
但是，如果文件本身很小，索引数据块冗余严重；如果文件本身很大，一个索引数据块不够装。
方法三扩展：大文件多级索引块
如上图，可以采用链式（线性扩展，不可靠、不推荐）或多级索引块（分层方式，推荐）对大文件数据块索引信息进行保存。
如上图，在早期Linux里，采用多级索引块方式。小文件直接放在一级索引块里，保证小文件不需要经过多级索引就可以访问。
空闲空间管理
空闲磁盘块，如何被文件系统组织？如何表示？
如上图，用位图代表空闲数据库。1代表磁盘扇区已经被使用。但是要定期扫描空间块，因为如果掉电，磁盘是否空闲的信息可能对不上。
如上图中，对于160GB的磁盘，一个数据库40MB，则内存中需要5MB的位图信息。
如上图，如果刚刚将bit[i]=1时突然掉电，则尽管误认为数据库i被写入了，但是没有丢失信息。如果先写信息，再将bit[i]赋为1，则有可能丢失信息。
如上图，有些文件系统使用链式列表或分组列表表示空闲块。
多磁盘管理-RAID（Redundant Arrays of Independent Drives）
前置知识：
- 磁盘读取中，最慢的是磁头的横向移动；
- 文件系统是分区的、分卷的。
在RAID提出之前，磁盘经常坏。有没有可能通过并行、冗余（多个磁盘存一个内容）提高可靠性？
因此提高RAID（冗余磁盘阵列）。
RAID从RAID0发展到了RAID5、6…数字指磁盘阵列组织方式。
RAID分为软RAID和硬RAID。软RAID是在磁盘之上进行抽象，硬RAID是在芯片层面做处理，操作系统所见到的是一个被映射出的大磁盘。
如上图，RAID0中，把一个数据分成三部分存在三个硬盘上，进行并行读取，时间变为三分之一。
如上图，RAID1中，硬盘起到一个镜像作用。两个磁盘写一个内容。
如上图，RIAD4中，既能提升效率又能保证可靠性。Disk1-4中，某一个出现故障，可以通过Parity Disk进行奇偶校验。
但是，由此，Parity Disk的开销会比其他Disk大很多。
如上图，RAID5中，每个Disk都具有校验能力。则每个Disk开销差不多。RAID5是RAID4的升级。但是RAID4、RAID5只能纠正一个磁盘出错的情况（两个及以上不行）。
如上图，RAID0和RAID1可以分层或嵌套，来获得更多特性。RAID相关的技术还有很多。
磁盘调度
在OS层面，重新组织I/O顺序，来有效减少访问的开销。
如上图，机械运动相比电路很慢，因此优化机械动作，很重要。
磁盘的性能
如上图，对于读或者写的表示，寻道时间+旋转延迟=磁盘访问时间。
如上图是访问时间的计算公式。
- 寻道时间是性能上区别的原因；
- 对单个磁盘，会有一个I/O请求数目；
- 如果请求是随机的，那么会表现得很差。
磁盘调度方法
先进先出
- 按顺序处理请求；
- 公平对待所用进程；
- 在有很多进程的情况下，接近随机调度的性能。
如上图，这种方法随机性很大，磁盘指针来回地条，移动距离很长，开销很大。
最短服务优先
如上图，动态情况下规划，下次访问时与现在磁头最近的位置。
但是，原处的区域可能只需得不到服务，出现“饥饿”现象。
扫描算法（SCAN，电梯算法）
如上图，移到一头，再回来。
C-SCAN方法
如上图，限制磁臂只能向一个方向移动。只能从高到低访问。
C-LOOK
到达最后一个请求处反转，而非最高点。
其他算法
如上图，还有许多算法，比如N-Step-SCAN。
如上图，FSCAN是对N-step-SCAN的简化，将N=2。
对于真实系统来讲，可能需要更复杂算法，或不需要设计算法，因为：
- 硬盘本身在变化；
- 已经有SSD硬盘；
- 硬盘已经高性能、智能化，软件方面可能作用不显著。