Liuye Notebook
0%

操作系统原理-文件系统2

发表于 更新于 分类于 ， 阅读次数： Valine：

阅读更多

1 文件系统实例-FAT

1.1 Windows-FAT6文件系统

  • 簇大小：1、2、4、8、16、32或64扇区
  • 文件系统的数据记录在“引导扇区”中
  • 文件分配表FAT的作用：描述簇的分配状态、标注下一簇的簇号等
  • FAT表项：2字节
  • 目录项：32字节
  • 根目录大小固定

fig1

1.1.1 主引导区-MBR

主引导区MBR是Main Boot Record的缩写，记录0号扇区，格式见下表

fig2

1.1.2 FAT文件系统-DBR

分区引导扇区DBR是Domaines Barons de Rothschild的缩写，格式见下表

fig3

1.1.3 引导扇区-BIOS参数块

fig4

1.1.4 引导扇区-扩展BIOS参数块（EBPB）

fig5

1.1.5 文件分配表FAT

文件分配表FAT是File Allocation Table的缩写

  • 可以把文件分配表看成是一个整数数组，每个整数代表磁盘分区的一个簇号
  • 状态：未使用、坏簇、系统保留、被文件占用（下一簇簇号）、最后一簇（0xFFFF）
  • 簇号从0开始编号，簇0和簇1是保留的

fig6

1.1.6 FAT16目录项

fig7

1.2 FAT32文件系统

FAT32文件系统与FAT16文件系统的差异如下

  • FAT32的根目录区（ROOT区）不是固定区域、固定大小，而是数据区的一部分，采用与子目录文件相同的管理方式
  • 目录项仍占32字节，但分为各种类型（包括：“.”目录项、“…”目录项、短文件名目录项、长文件名目录项、卷标项（根目录）、已删除目录项（第一字节为0xE5）等）
  • 支持长文件名格式
  • 支持Unicode
  • 不支持高级容错特性，不具有内部安全特性

1.2.1 FAT32目录项

fig8

1.2.2 一般长文件名的实现方式

方式1

  1. 文件长度
  2. 文件属性
  3. 长文件名
  • 每个文件占用的空间非固定，因此必须在开头指明长度，详见左图

方式2

  1. 文件名指针
  2. 文件属性
  • 每个文件占用的空间固定，文件名用一块额外的区域来维护，以一个特殊字符作为文件名之间的间隔，详见右图

fig9

1.2.3 FAT32长文件名目录项格式

fig10

例子：文件名为The quick brown.fox，采用Unicode编码

fig11

2 文件操作的实现

2.1 创建文件

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

  • 在目录中为新文件建立一个目录项，根据提供的参数及需要填写相关内容
  • 分配必要的存储空间

create（文件名，访问权限）

  1. 检查参数的合法性
    • 例如：文件名是否符合命名规则
    • 有无重名文件
    • 合法→步骤2，否则→报错、返回
  2. 申请空闲目录项，并填写相关内容
  3. 为文件申请磁盘块
  4. 返回

2.2 打开文件

打开文件：根据文件名在文件目录中检索，并将该文件的目录项读入内存，建立相应的数据结构（文件描述符/文件句柄），为后续的文件操作做好准备

  • 为文件读写做准备，给出文件路径名，获得文件句柄(file handle)或文件描述符(file descriptor)，需将该文件的目录项读到内存

fd=open（文件路径名，打开方式）

  1. 根据文件路径名查目录，找到目录项（或I节点号）
  2. 根据文件号查系统打开文件表，看文件是否已被打开
    • 是 → 共享计数加1
    • 否则 → 将目录项 (或I节点)等信息填入系统打开文件表空表项，共享计数置为1
  3. 根据打开方式、共享说明和用户身份检查访问合法性
  4. 在用户打开文件表中获取一空表项，填写打开方式等，并指向系统打开文件表对应表项

返回信息：fd：文件描述符，是一个非负整数，用于以后读写文件

2.3 指针定位

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

seek（fd, 新指针的位置）

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

2.4 读文件

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

  1. 根据打开文件时得到的文件描述符，找到相应的文件控制块（目录项）
    • 确定读操作的合法性
    • 读操作合法→②，否则→出错处理
  2. 将文件的逻辑块号转换为物理块号
    • 根据参数中的读指针、长度与文件控制块中的信息，确定块号、块数、块内位移
  3. 申请缓冲区
  4. 启动磁盘I/O操作，把磁盘块中的信息读入缓冲区，再传送到指定的内存区（多次读盘）
  5. 反复执行③、④直至读出所需数量的数据或读至文件尾

3 文件系统的管理

3.1 文件系统的可靠性

文件系统的可靠性是指：抵御和预防各种物理性破坏和人为性破坏的能力

  • 坏块问题

备份：通过转储操作，形成文件或文件系统的多个副本

名词解释

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

3.2 文件系统的一致性

问题的产生：

  • 磁盘块 → 内存 → 写回磁盘块
  • 若在写回之前，系统崩溃，则文件系统出现不一致

解决方案：设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统

3.2.1 磁盘块一致性检查

UNIX一致性检查工作过程：

  • 两张表，每块对应一个表中的计数器，初值为0
  • 表一：记录了每块在文件中出现的次数
  • 表二：记录了每块在空闲块表中出现的次数

fig12

3.3 文件系统的写入策略

通写（write-through）

  • 内存中的修改立即写到磁盘
  • 缺点：速度性能差
  • 例： FAT文件系统

延迟写（lazy-write）

  • 利用回写（write back）缓存的方法得到高速
  • 可恢复性差

可恢复写（transaction log）

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

4 文件系统的安全性

4.1 文件保护机制

文件保护机制有如下作用：

  • 用于提供安全性、特定的操作系统机制
  • 对拥有权限的用户，应该让其进行相应操作，否则，应禁止
  • 防止其他用户冒充对文件进行操作

4.2 文件的访问控制

主动控制：访问控制表

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

能力表(权限表)

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

4.2.1 UNIX的文件访问控制

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

  1. 第一级：对访问者的识别，对用户分类：
    • 文件主（owner）
    • 文件主的同组用户（group）
    • 其他用户（other）
  2. 第二级：对操作权限的识别，对操作分类：
    • 读操作（r）
    • 写操作（w）
    • 执行操作（x）
    • 不能执行任何操作（-）

5 文件系统的性能

磁盘服务→速度成为系统性能的主要瓶颈之一。因此，设计文件系统应尽可能减少磁盘访问次数

提高文件系统性能的方法：

  • 目录项(FCB)分解、当前目录、磁盘碎片整理
  • 块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术…

5.1 块高速缓存

块高速缓存又称为文件缓存、磁盘高速缓存、缓冲区高速缓存，是指：在内存中为磁盘块设置的一个缓冲区，保存了磁盘中某些块的副本

  • 检查所有的读请求，看所需块是否在块高速缓存中
  • 如果在，则可直接进行读操作；否则，先将数据块读入块高速缓存，再拷贝到所需的地方
  • 由于访问的局部性原理，当一数据块被读入块高速缓存以满足一个I/O请求时，很可能将来还会再次访问到这一数据块

块高速缓存的实现

  • 块高速缓存的组织
  • 块高速缓存的置换（修改LRU）
  • 块高速缓存写入策略

5.2 提前读取

提前读取是指：每次访问磁盘，多读入一些磁盘块

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

5.3 WINDOWS的文件访问方式

Windows有如下三种文件访问方式

  1. 不使用文件缓存
    • 普通方式
    • 通过Windows提供的FlushFileBuffer函数实现
  2. 使用文件缓存
    • 预读取。每次读取的块大小、缓冲区大小、置换方式
    • 写回。写回时机选择、一致性问题
  3. 异步模式
    • 不再等待磁盘操作的完成
    • 使处理器和I/O并发工作

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

  • 由Windows的Cache Manager实现对缓存的控制
    • 读取数据的时候预取
    • 在Cache满时，根据LRU原则清除缓存的内容
    • 定期更新磁盘内容使其与Cache一致（1秒）
  • Write-back机制
    • 在用户要对磁盘写数据时，只更改Cache中的内容，由Cache Manager决定何时将更新反映到磁盘

fig13

阴影部分为需要访问的数据，数据在磁盘、系统缓存和进程地址空间有3份拷贝，通常下用户对数据的修改并不直接反映到磁盘上，而是通过write-back机制由lazy writer定期地更新到磁盘

5.4 合理分配磁盘空间

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

fig14

5.5 磁盘调度

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

  • 公平：一个I/O请求在有限时间内满足
  • 高效：减少设备机械运动带来的时间开销

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

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

下面以一个例子来说明不同磁盘调度算法之间的差异

  • ：假设磁盘访问序列：98，183，37，122，14，124，65，67
  • 读写头起始位置：53
  • 要求计算：
    • 磁头服务序列
    • 磁头移动总距离（道数）

5.5.1 先来先服务（FCFS）

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

  • 优点：简单，公平
  • 缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利

磁盘访问序列：98，183，37，122，14，124，65，67
读写头起始位置：53
磁头移动总距离（道数）：640磁道。(平均80)

fig15

5.5.2 最短寻道时间优先（Shortest Seek Time First）

最短寻道时间优先（Shortest Seek Time First）：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先

  • 优点：改善了磁盘平均服务时间
  • 缺点：造成某些访问请求长期等待得不到服务

磁盘访问序列：98，183，37，122，14，124，65，67
读写头起始位置：53
磁头移动总距离（道数）：236磁道(平均29.5)

fig16

5.5.3 扫描算法SCAN（电梯算法）

扫描算法SCAN（电梯算法）：

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

磁盘访问序列：98，183，37，122，14，124，65，67
读写头起始位置：53
磁头移动总距离（道数）：218磁道。(平均27.25)

fig17

5.5.4 单向扫描调度算法C-SCAN

单向扫描调度算法C-SCAN，减少了新请求的最大延迟

  • 总是从0号柱面开始向里扫描
  • 按柱面(磁道)位置选择访问者
  • 移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面
  • 返回时不为任何的等待访问者服务
  • 返回后可再次进行扫描

5.5.5 N-step-SCAN策略

N-step-SCAN策略，克服“磁头臂的粘性”

  • 把磁盘请求队列分成长度为N的子队列，每一次用SCAN处理一个子队列
  • 在处理某一个队列时，新请求添加到其他子队列中
  • 如果最后剩下的请求数小于N，则它们全都将在下一次扫描时处理
  • N值比较大时，其性能接近SCAN；当N＝1时，即FIFO

###FSCAN策略

FSCAN策略，克服“磁头臂的粘性”

  • 使用两个子队列
  • 扫描开始时，所有请求都在一个队列中，而另一个队列为空
  • 扫描过程中，所有新到的请求都放入另一个队列中
  • 对新请求的服务延迟到处理完所有老请求之后

5.5.6 旋转调度算法

旋转调度：根据延迟时间来决定执行次序的调度

  • 三种情况：
    • 若干等待访问者请求访问同一磁头上的不同扇区
    • 若干等待访问者请求访问不同磁头上的不同编号的扇区
    • 若干等待访问者请求访问不同磁头上具有相同的扇区
  • 解决方案：
    • 对于前两种情况：总是让首先到达读写磁头位置下的扇区先进行传送操作
    • 对于第三种情况：这些扇区同时到达读写磁头位置下，可任意选择一个读写磁头进行传送操作

5.6 信息的优化分布

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

例子：处理程序要求顺序处理8个记录；磁盘旋转一周为20毫秒/周；花5毫秒对记录进行处理

fig18

对于图左

  • 信息连续存放
  • 当读取信息1之后，经过5毫秒处理，此时磁头已经旋转至信息4位置处，若要读取信息2，还得空等15毫秒，让磁头旋转至信息2处，造成了时间的浪费

对于图右

  • 信息交替存放
  • 当读取信息1之后，经过5毫秒处理，此时磁头已经旋转至信息2处，此时恰好可以直接读取信息2，无须等待
  • 当读取信息2之后，经过5毫秒处理，此时磁头已经旋转至信息3处，此时恰好可以直接读取信息3，无须等待
  • 直至读完所有信息

5.6.1 记录的组成与分解

记录的成组：把若干个逻辑记录合成一组存放一块的工作

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

记录的分解

  • 从一组逻辑记录中把一个逻辑记录分离出来
  • 典型例子—目录文件

5.7 RAID技术

RAID（独立磁盘冗余阵列）(Redundant Arrays of Independent Disks)：多块磁盘按照一定要求构成一个独立的存储设备

  • 目标：提高可靠性和性能
  • 考虑：磁盘存储系统的速度、容量、容错、数据灾难发生后的数据恢复

数据是如何组织的？

  • 通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能
  • 通过把数据分成多个数据块，并行写入/读出多个磁盘，以提高数据传输率（数据分条stripe）
  • 通过镜像或校验操作，提供容错能力（冗余）

最简单的RAID组织方式：镜像
最复杂的RAID组织方式：块交错校验

5.7.1 RAID0-条带化

  • 数据分布在阵列的所有磁盘上
  • 有数据请求时，同时多个磁盘并行操作
  • 充分利用总线带宽，数据吞吐率提高，驱动器负载均衡

fig19

5.7.2 RAID1-镜像

  • 最大限度保证数据安全及可恢复性
  • 所有数据同时存在于两块磁盘的相同位置
  • 磁盘利用率50%

fig20

5.7.3 RAID4-交错块奇偶校验

  • 带奇偶校验
  • 以数据块为单位

fig21

6 参考

  • 《MOOC-操作系统原理-陈向群》