二、文件操作的实现

这里主要是以UNIX操作系统为例。

2.1 文件操作的实现

• 创建文件
  建立系统与文件的联系，实质是建立文件的FCB
  

*   在目录中为新文件建立一个目录项（在`UNIX`中还需要`i`节点），根据提供的参数及需要填写相关内容

• 分配必要的存储空间

• 打开文件
  根据文件名目录中检索，并将该文件的目录项读入内存，建立相应的数据结构，为后续的文件操作做好准备。打开文件后一般会返回一个值，这个值一般叫文件描述符或文件句柄，之后的操作是通过文件描述符来进行的。
  

2.2 文件操作：建立文件

create（文件名，访问权限）

• 1、检查参数的合法性
  例如：文件名是否符合命名规则；有无重名文件，合法则进行下一步，否则报错返回。
  
• 2、申请空闲目录项，并填写相关内容
  

• 3、为文件申请磁盘块
  
• 4、返回
  

2.3 文件操作：打开文件

为文件读写做准备：给出文件路径名，获得文件句柄（file handler）或文件描述符（file descripter），需将该文件的目录项读到内存fd = open（文件路径名，打开方式）

1、根据文件路径名查目录，找到目录项（或i节点号）

2、根据文件号查系统打开文件表，看文件是否已被打开，如果是，则共享计数加一，否则，将目录项（或i节点）等信息填入系统打开文件表空表项，共享计数置为一。

3、根据打开方式、共享说明和用户身份检查访问合法性

4、在用户打开文件表中获取一空表项，填写打开方式等，并指向系统打开文件表对应表项，返回信息：fd（文件描述符，是一个非负整数，用于以后读写文件）

2.4 文件操作：指针定位

seek（fd， 新指针位置）：系统为每个进程打开的每个文件维护一个读写指针，即相对于文件开头的偏移地址（读写指针指向每次文件读写的开始位置 ，在每次读写完成后，读写指针按照读写的数据量自动后移相应的数值）

• 1、由fd查用户打开文件表，找到对应的表项
• 2、将用户打开文件表中文件读写指针位置设为新指针的位置，供后继读写命令存取该指针处文件内容。

2.5 文件操作：读文件

read（文件描述符，读指针，要读的长度，内存目的地址）

1、根据打开文件时得到的文件描述符，找到相应的文件控制块（目录项），确定读操作的合法性，读操作合法则进行下一步，否则出错处理。

2、将文件的逻辑块号转换为物理块号。根据参数中的读指针、长度与文件控制块中的信息，确定块号、块数、块内位移

3、申请缓冲区

4、启动磁盘I/O操作，把磁盘块中的信息读入缓冲区，再送到指定的内存区（多次读盘）

5、反复执行3、4直至读出所需数量的数据或读至文件尾

三、文件系统的管理

3.1 文件系统的可靠性

可靠性：抵御和预防各种物理性破坏和人为性破坏的能力

• 块坏问题
  
• 备份
  通过转储操作，形成文件或文件系统的多个副本。
  

3.2 文件系统备份

• 全量转储
  定期将所有文件拷贝到后援存储器
  
• 增量转储
  只转储修改过的文件，即两次备份之间的修改。减少系统开销。
  
• 物理转储
  从磁盘第零块开始，将所有磁盘块按序输出到磁带
  
• 逻辑转储
  从一个或几个指定目录开始，递归地转储子给定日期后所有更改的文件和目录

3.3 文件系统一致性

• 问题的产生：
  磁盘块–>内存–>写回磁盘块
  若在写回之前，系统崩溃，则文件系统出现不一致
  
• 解决方案
  设计一个使用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统
  

3.4 磁盘块的一致性检查

**说明：：**一致性检查时，检查所有的文件和空闲块，检查完之后可能会出现四种结果。第一种是一个一致性的结果，即某个磁盘块要么分配给了某个文件，要么在空闲块中。第二种结果是在空闲块中找不到，但是也没有分配给某个文件，于是我们通过在空闲块表中将磁块标记为一来解决。第三种结果是某个磁盘块在空闲块表中出现了两次，同样是不合理的，对这一位进行修改。最后一种结果是在两个文件中出现，这种情况较为复杂，我们应该在空闲块中找一个，然后将其中一个磁盘块内容拷贝到这个空闲块中，然后将使用块表中的这一位减一。

3.5 文件系统的写入策略

对某些文件做出了修改，那么什么时候将修改后的内容写入到文件中。这里需要考虑文件系统一致性和速度。下面有几种写入策略

通写（write-through）

内存中的修改立即写到磁盘。缺点是速度性能差，如FAT文件系统。

延迟写（lazy-write）

利用回写（write back）缓存的方法得到高速。其缺点就是可恢复性较差，可能会导致信息丢失

可恢复写（tansaction log）

采用事务日志来实现文件系统的写入，既考虑安全性，又考虑速度性能，如NTFS

四、文件系统的安全性

这里我们讨论如何确保未经授权的用户不能存取某些文件？

4.1 文件保护机制

• 用于提供安全性、特定的操作系统机制
• 对拥有权限的用户，应该让其进行相应的操作，否则，应禁止
• 防止其他用户冒充对文件进行操作
• 于是在实现的时候需要考虑用户身份验证和访问控制。对于用户身份我们可以采用比如密码、口令等方式。

4.2 文件的访问控制

有不同的访问控制手段，比如主动控制（使用访问控制表）和能力表（使用权限表）。

• 主动控制
  每个文件一个
  记录用户ID和访问权限
  
• 用户可以是一组用户
  文件可以是一组文件
  

• 能力表
  每个用户一个
  记录文件名及访问权限
  用户可以是一组用户
  文件可以是一组文件
  

4.3 UNIX的文件访问控制

采用文件的二级存取控制，审查用户的身份、审查操作的合法性

第一级：对访问者身份的识别

对用户分类：

*   文件主（`owner`）

• 文件主的同组用户（group）
• 其他用户（other）

• 第二级：对操作权限的识别
  对操作分类：
  

*   读操作（`r`）

• 写操作（w）
• 执行操作（x）
• 不能执行任何操作（-）

五、文件系统的性能

5.1 文件系统的性能问题

• 磁盘服务：速度成为系统性能的主要瓶颈之一。因此，在设计文件系统时应尽可能减少磁盘访问次数
  
• 提高文件系统性能的方法：
  目录项（FCB）分解、当前目录、磁盘碎片整理、块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术等等
  

5.2 提高文件系统性能：块高速缓存（BLOCK CACHE）

又称为文件缓存、磁盘高速缓存、缓冲区高速缓存。是指在内存中为磁盘块设置的一个缓冲区，保存了磁盘中某些块的副本。当对文件系统进行操作的时候：

检查所有的读请求，看所需块是否在块高速缓冲中

如果在，则可直接进行读操作；否则，先将数据块读入块高速缓存，再拷贝到所需的地方。

由于访问的局部性原理，当一数据块被读入块高速缓存以满足一个I/O请求时，和可能将来还会再次访问到这一数据块。

5.3 如何实现块高速缓存

• 块高速缓存的组织方式
• 
• **说明：**在块高速缓存中有若干个数据块，首先将这些块使用一个双向链表组织起来，当要访问这个链的时候就将其从此链中拿出来，然后挂接到链尾，而我们对于某个文件使用的块要检查其是否在高速缓存中，所以这里又使用块号进行散列以提高检查速度。

块高速缓存的置换问题（修改LRU）

因为此缓存的空间肯定是不会很大的，所以当其满时我们需要对其进行置换。对于以后可能会再次使用的块我们将其放在链尾，而对于使用概率很小的块可能就需要将其剔除。

块高速缓存的写入策略

在文件系统中，我们需要考虑该块是否会影响文件系统的一致性。这里如前面所讲，不同的操作系统采用了不同的一致性解决方案。

提前读取

*   思路：每次访问磁盘，多读入一些磁盘块

• 依据：程序执行的空间局部性原理
• 开销：较小（只有数据传输时间）
• 具有针对性

5.4 Windows的文件访问方式

一般有下面三种方式：

不使用文件缓存

*   普通方式

• 通过Windows提供的FlushFileBuffer函数实现

• 使用文件缓存（块高速缓存）

*   预读取。每次读取的块大小、缓冲区大小、置换方式

• 写回。写回时机选择、一致性问题

• 异步模式

*   不再等待磁盘操作的完成。

• 使处理器和I/O并发工作

用户对磁盘的访问通过访问文件缓存来实现：

• 由Windows的Cache Manager实现对缓存的控制

*   读取数据的时候预取

• 在Cache满时，根据LRU原则清除缓存的内容
• 定期更新磁盘内容使其与Cache一致（每秒）

• write-back机制
  

*   在用户要对磁盘写数据时，只更改`Cache`中的内容，由`Cache Manager`决定何时将更新反映到磁盘

5.5 提高文件系统性能：合理分配磁盘空间

分配磁盘块时，把有可能顺序存取的块放在一起（尽量分配在同一柱面上，从而减少磁盘臂的移动次数和距离）

**说明：**我们读取文件系统时，每次都要先找到i节点区，然后再去找到文件位置，如果i节点区在最外道，而相关文件在最里道，则在读取的时候磁臂就需要不断的移动，这样显示效率低下。一种解决方案如(a)，我们将i节点区和相关文件放在距离较近的磁道上；另一种是如(b)，首先将磁道分成了若干组，然后将i节点区也划分成若干部分，每一组磁道都有一个i节点区，而每个文件都和其i节点区在同一组，这样磁臂也不需要很大的移动。

5.6 提高文件系统性能：磁盘调度(重点)

当有多个访盘请求等待时，采用一定的策略，对这些请求的服务顺序调整安排，从而降低平均磁盘服务时间，达到公平、高效的目的。

• 公平
  
• 一个IO请求在有限时间内满足
  

• 高效
  减少设备机械运动带来的时间开销
  

一次访盘时间 = 寻道时间 + 旋转延迟时间 + 传输时间

• 减少寻道时间
• 减少延迟时间

5.7 磁盘调度算法(重点)

例子：假设磁盘访问序列：98、183、37、122、14、124、65、67，这些数字表示柱面号或磁道号。读写头起始位置为53。请计算磁头服务序列和磁头移动总距离（道数）。下面使用几种算法进行计算：

• 1、先来先服务（FCFS）
  
• 按访问请求到达的先后次序服务

*   优点：简单、公平

• 缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利。
• 
• 磁道服务序列和访问序列一致，磁头移动总距离为640，平均80。

2、最短寻道时间优先（Shortest Seek Time First）(重点)

用于磁盘

优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。

优点

改善了磁盘平均服务时间

缺点

造成某些访问请求长期等待而得不到服务

3、扫描算法（SCAN电梯算法）(重点)

当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中遇到的访问请求进行服务，然后判断该方向上是否有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。其实是一种对距离和方向的折中算法。

4、单向扫描算法（C-SCAN）

这是对扫描算法的一种改进。

*   总是从零号柱面开始向里扫描

按柱面（磁道）位置选择访问者

移动臂到达最后一个柱面后，立即带动读写磁头快速返回到零号柱面

返回时不为任何的等待访问者服务

返回后可再次进行扫描

主要的目的是减少了新请求的最大延迟。

5、N-step-SCAN策略

把磁道请求队列分成长度为N的子队列，每一次用SCAN处理一个子队列

在处理某一个队列时，新请求添加到其他子队列中

如果最后剩下请求数小于N，则它们全部都将在下一次扫描时处理

N值比较大时，其性能接近SCAN；当N = 1时，即FIFO

主要是为了解决磁头臂的粘性问题。

6、FSCAN策略

使用两个子队列

扫描开始时，所有请求都在一个队列中，而另一个队列为空

扫描过程中，所有新到的请求都放入另一个队列中

对新请求的服务延迟到处理完所有老请求之后

主要是为了解决磁头臂的粘性问题。本算法及以上都是对磁臂移动的优化算法。

7、旋转调度算法

根据延迟时间来决定执行次序的调度。一般有三种情况：

若干等待访问请求访问同一磁头上的不同扇区

若干等待访问请求访问不同磁头上的不同扇区

若干等待访问请求访问不同磁头上的相同扇区

• 解决方案：

• 对于前两种情况：总是让首先到达读写磁头位置下的扇区先进行传送操作

• 对于第三种情况：这些扇区同时到达读写磁头位置下，可任意选择一个读写磁头进行传送操作
  

5.8 提高文件系统性能：信息优化分布

记录在磁道上的排列方式也会影响输入输出操作的时间。

**说明：**如果信息是按左边那样分布的，那么如果首先读到1号记录，然后花5ms处理，但是此时磁盘已经转到了4号记录，于是如果我们要处理2号记录，则必须将4、5、6、7、8都旋转过去之后才能处理2号记录；而如果信息是按右边那样分布的，当处理完1号记录，而此时磁盘也刚好旋转到了2号记录处，这样就能极大的提高文件系统的性能。

5.9 提高文件系统性能：记录的成组与分解

• 记录的成组
  把若干个逻辑记录合成一组存放在一块的工作
  
• 进行成组操作时必须使用内存缓冲区，缓冲区的长度等于逻辑记录长度乘以成组的块因子（成组的长度）。
  
• 成组的目的：提高了存储空间的利用率；减少了启动外设的次数，提高系统的工作效率。
  

• 记录的分解
  从一组逻辑记录中把一个逻辑记录分离出来
  

典型的例子就是目录文件的存储。

5.10 提高文件系统性能：RAID技术

起始就是独立磁盘冗余阵列（Redundant Arrays of Independent Disks），就是将多块磁盘按照一定要求构成一个独立的存储设备。目的就是提高可靠性和性能。在实现时，需要考虑存储系统的速度、容量、容错、数据灾难发生后的数据恢复。

数据是如何组织的

*   通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能

• 通过把数据分成多个数据块，并行写入/读出多个磁盘，以提高数据传输率（数据分条stripe）
• 通过镜像或校验操作，提供容错能力（冗余信息的保存）
• 最简单的组织方式是镜像，最复杂的是块交错校验。
• 例1：RAID 0 - 条带化

*   数据分布在阵列的所有磁盘上

• 有数据请求时，同时多个磁盘并行操作
• 充分利用总线宽带，数据吞吐率提高，驱动器负载均衡
• 
• 这种方式没有冗余信息保存，即无差错控制，性能是最佳的。

• 例2：RAID 1-镜像

*   最大限度保证数据安全和可恢复性

• 所有数据同时存在与两块磁盘的相同位置
• 磁盘利用率为50%
• 
• 9

数据的安全性是最好的，但是磁盘利用率较低。

• 例3：RAID 4-交错块奇偶校验

*   带奇偶校验

• 以数据块为单位
• 
• 数据保存在前四块盘上，而校验信息保存在第五块盘上。