熟悉完操作系统的第十二篇章，开始学习第十三篇章，关于操作系统的文件系统。

0猜你喜欢

操作系统系列文章

操作系统学习笔记 1概述

操作系统学习笔记 2操作系统介绍

操作系统学习笔记 3内存管理

操作系统学习笔记 4非连续内存分配

操作系统学习笔记 5虚拟内存

操作系统学习笔记 6页面置换算法

操作系统学习笔记 7进程管理

操作系统学习笔记 8CPU调度

操作系统学习笔记 9同步&互斥

操作系统学习笔记 10信号量&管程

操作系统学习笔记 11死锁

操作系统学习笔记 12进程间通信

操作系统学习笔记 13文件系统

13文件系统

  1. 基本概念
  2. 虚拟文件系统
  3. 数据块缓存
  4. 打开文件的数据结构
  5. 文件分配
  6. 空闲空间列表
  7. 多磁盘管理-RAID
  8. 磁盘调度

13.1基本概念

  • 文件系统和文件
  • 文件描述符
  • 目录
  • 文件别名
  • 文件系统种类

13.1.1文件系统和文件

文件系统

一种用于持久性存储的系统抽象

  • 在存储器上：组织、控制、导航、访问和检索数据
  • 大多数计算机系统包含文件系统
  • 个人电脑、服务器、笔记本电脑
  • iPod、Tivo/机顶盒，手机/掌上电脑
  • Google可能是由一个文件系统构成的

文件

文件系统中一个单元的相关数据在操作系统中的抽象

分配文件磁盘空间

  • 管理文件夹（哪一块属于哪一个文件）
  • 管理空闲空间（哪一块是空闲的）
  • 分配算法（策略）

管理文件集合

  • 定位：文件及其内容
  • 命令：通过名字找到文件的接口
  • 最常见：分层文件系统
  • 文件系统类型（组织文件的不同方式）

提供的便利及特征

  • 保护：分层来保护数据安全
  • 可靠性/持久性：保持文件的持久即使发生崩溃、媒体错误、攻击等

文件属性

  • 名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间。。。

文件头

  • 在存储数据中保存了每个文件的信息
  • 保存文件的属性
  • 跟踪哪一块存储块属于逻辑上文件结构的哪个偏移

13.1.2文件描述符

13.1.2.1文件使用模式

实用程序必须在使用前先“打开”文件

1f = open(name, flag);
2...
3... = read(f, ...);
4...
5close(f);

内核跟踪每个进程打开的文件

  • 操作系统为每个进程维护一个打开文件表
  • 一个打开文件描述符是这个表中的索引

13.1.2.2需要元数据来管理打开文件

  • 文件指针：指向最近的一次读写为止，每个打开了这个文件的进程都这个指针
  • 文件打开计数：记录文件打开的次数。当最后一个进程关闭了文件时，允许将其从打开文件表中移除
  • 文件磁盘位置：缓存数据访问信息
  • 访问权限：每个程序访问模式信息

总结：

文件描述符是个概念，具体包括步骤是通过索引找到文件位置，查文件具体属性，比如owner，权限，创建日期等等。

13.1.2.3不同角度

  • 从用户角度，文件是一种持久的数据结构
  • 从系统角度，文件是字节的集合（unix），不会关心你想存储在磁盘上的任何数据结构
  • 从操作系统角度，文件是块的集合（块是逻辑转换单元，而扇区是物理转换单元），块大小和扇区大小，块的大小是4KB

举例说明

当用户说：给我2-12字节空间时会发生什么

  • 获取字节所在的块
  • 返回块内对应部分

如果说要写2-12字节呢

  • 获取块
  • 修改块内对应部分
  • 写回块

在文件系统中的所有操作都是在整个块空间上进行的

  • 举个例子，getc(),putc()：即使每次只访问1字节数据，也会缓存目标数据4096字节

13.1.2.4用户怎么访问文件

在系统层面需要知道用户的访问模式

  • 顺序访问：按字节依次读取

    几乎所有的访问都是这种方式

  • 随记访问：从中间读写

    不常用，但仍然重要。例如，虚拟内存支持文件：内存页存储在文件中

    更加快速-不希望获取文件中间的内容的时候也必须先获取块内所有字节

  • 基于内容访问：通过特征

    许多系统不提供此种访问方式，相反，数据库是建立在索引内容的磁盘访问上（需要高效的随机访问）

    基于内容访问有两个文件，一个是index文件，一个是关系文件，这是典型的数据库。通过index找到对应的关系文件的记录项，数据库通过不同功能的文件来完成基于内容的查找。

13.1.2.5文件内部结构

无结构

  • 单词、比特的队列

简单记录结构

  • 列
  • 固定长度
  • 可变长度

复杂结构

  • 格式化的文档（如MS Word）
  • 可执行文件
  • 。。。

多用户系统中的文件共享是很有必要的

访问控制

  • 谁能够获得哪些文件的哪些访问权限
  • 访问模式：读、写、执行、删除、列举等

文件访问控制列表（ACL）

  • <文件实体， 权限>

Unix模式

  • < 用户|组|所有人， 读|写|可执行>
  • 用户ID识别用户，表明每个用户所允许的权限及保护模式
  • 组ID允许用户组成组，并指定了组访问权限

指定多用户/客户如何同时访问共享文件

  • 和进程同步算法相似
  • 因磁盘I/O和网络延迟而设计简单

Unix文件系统（UFS）语义

  • 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
  • 共享文件指针允许多用户同时读取和写入文件

会话语义

  • 写入内容只有当文件关闭时可见

锁

  • 一些操作系统和文件系统提供该功能

13.1.3 目录

13.1.3.1目录

文件是以目录的方式组织起来

  • 目录是一种特殊的文件

    每个目录都包含了一张表<name, pointer to the header>

  • 目录和文件的树型结构

    早期的文件系统是扁平的（只有一层目录）

  • 层次名称空间

13.1.3.2典型操作

  • 搜索文件
  • 创建文件
  • 删除文件
  • 每局文件
  • 重命名文件
  • 在文件系统中遍历一个路径

操作系统应该只允许内核模式修改目录

  • 确保映射的完整性
  • 应用程序能够读取目录（如ls）

13.1.3.3目录存储文件的数据结构

文件名的线性列表，包含了指向数据块的指针

  • 编程简单
  • 执行耗时

Hash表-hash数据结构的线性表

  • 减少目录搜索时间
  • 碰撞-两个文件名的hash值相同
  • 固定大小

13.1.3.4路径遍历

名字解析：逻辑名字转换成物理资源（如文件）的过程

  • 在文件系统中：到实际文件的文件名（路径）
  • 遍历文件目录直到找到目标文件

举例：解析“/bin/ls”

  • 读取root的文件头（在磁盘固定位置）
  • 读取root的数据块：搜索“bin”项
  • 读取bin的文件头
  • 读取bin的数据块：搜索“ls”项
  • 读取ls的文件头

当前工作目录

  • 每个进程都会指向一个文件目录用于解析文件名
  • 允许用户指定相对路径来代替绝对路径

13.1.3.5文件挂载

一个文件系统需要先挂载在才能被访问

一个未挂载的文件系统被挂载在挂载点上

Linux挂载，指的就是将设备文件中的顶级目录连接到 Linux 根目录下的某一目录（最好是空目录），访问此目录就等同于访问设备文件。

纠正一个误区，并不是根目录下任何一个目录都可以作为挂载点，由于挂载操作会使得原有目录中文件被隐藏，因此根目录以及系统原有目录都不要作为挂载点，会造成系统异常甚至崩溃，挂载点最好是新建的空目录。

13.1.4文件别名

  • 两个或多个文件名关联同一个文件

  • 硬链接：多个文件项指向同一个文件

  • 软链接：以“快捷方式”指向其他文件

  • 通过存储真实文件的逻辑名称来实现

如果删除一个有别名的文件会如何呢

软链接方案（软链接）

  • 这个别名将成为一个“悬空指针”

Backpointers方案（硬链接）

  • 每个文件有一个包含多个Backpointers的列表，用于删除所有的Backpointers
  • Backpointers使用菊花链管理

添加一个间接层，目录项数据结构

  • 链接-已存在文件的另外一个名字（指针）
  • 链接处理-跟随指针来定位文件

目录循环

如何保障没有循环呢

  • 只允许到文件的链接，不允许在子目录的链接
  • 每增加一个新的链接都用循环检测算法确定是否合理
  • 限制路径可遍历文件目录的数量

13.1.5文件系统种类

  • 磁盘文件系统

    文件存储在数据存储设备上，比如磁盘

    例如：FAT，NTFS(windows)，ext2/3，ISO9660等

  • 数据库文件系统

    文件根据其特征是可被寻址（辨识）的

    例如：WinFs

  • 日志文件系统

    记录文件系统的修改/时间

    例如：journaling file system

  • 网络/分布式文件系统

    例如：NFS，SMB，AFS，GFS

  • 特殊/虚拟文件系统

    目的不是为了存数据，以文件的方式展示读写的接口，用于交互访问内核中的数据，例如/proc。多大内存，多少次中断，当前打开进程是多少，通过读写控制一些参数，用于操作系统的内核交互。

网络 / 分布式文件系统

文件可以通过网络内共享 分布是文件系统的问题
文件位于远程服务器 客户端和客户端上的用户辨别起来很复杂
客户端远程挂载服务器文件系统 例如：NFS是不安全的
标准系统文件访问被转换成远程访问 一致性问题
标准文件共享协议：NFS for Uinx，CIFS for Windows 错误处理模式

13.2虚拟文件系统

分层结构

  • 上层：虚拟（逻辑）文件系统
  • 底层：特定文件系统模块

目的

对所有不同文件系统的抽象

功能

  • 提供相同的文件和文件系统的接口
  • 管理所有文件和文件系统关联的数据结构
  • 高效查询例程，遍历文件系统
  • 与特定文件系统模块的交互

卷控制块（Unix:"superblock"）

  • 每个文件系统一个
  • 文件系统详细信息
  • 块、块大小、空余块、计数/指针等

文件控制块（Unix ：“vnode” or “inode”）

  • 每个文件一个
  • 文件详细信息
  • 许可、拥有者、大小、数据库位置等

目录节点（Linux “dentry”）

  • 每个目录项一个（目录和文件）
  • 将目录项数据结构及树型布局编码成树型数据结构
  • 指向文件控制块、父节点，项目列表等

文件系统数据结构

  • 卷控制块（每个文件系统一个）
  • 文件控制块（每个文件一个）
  • 目录节点（每个目录项一个）

持续存储在二级存储中

  • 在分配在存储设备中的数据块中

当需要时加载进内存

  • 卷控制块：当文件系统挂载时进入内存
  • 文件控制块：当文件被访问是进入每次
  • 目录节点：在遍历一个文件路径是进入内存

在操作系统访问文件系统前，数据存储在硬盘上面。硬盘的头几个扇区存储的是卷控制块（Unix:"superblock"），接下来的扇区存的是目录节点（Linux “dentry”），之后的扇区是文件控制块（Unix ：“vnode” or “inode”），最后的是数据块。可以通过文件控制块找到对应的数据块，最终可以实现对文件的读或者写的操作。

13.3数据块缓存

访问CPU和访问硬盘的速度不是一个数量级的。我们会在内存中放入一个缓存，把当前正在用到的或者经常用到的数据，从硬盘放到缓存中来。接下来的访问都可以到内存中来，可以提高效率。

数据块按需读入内存

  • 提供read操作
  • 预读：预选读取后面的数据块

数据块使用后被缓存

  • 假设数据将会再次被使用
  • 写操作可能被缓存和延迟写入

两种数据块缓存方式

  • 普通缓冲区缓存
  • 页缓存：统一缓存数据块和内存块

分页要求

  • 当需要一个页时才将其载入内存

支持存储

  • 一个页（在虚拟地址空间中）可以被映射到一个本地文件中（在耳机存储中）

文件数据块的页缓存

  • 在虚拟内存中文件数据块被映射成页
  • 文件的读/写操作被转换成堆内存的访问
  • 可能导致缺页和/或设置为脏页
  • 问题：页置换-从进程或者文件页缓存中

13.4打开文件的数据结构

打开文件描述

  • 每个被打开的文件一个
  • 文件状态信息
  • 目录项、当前文件指针、文件操作设置等

打开文件表

  • 一个进程一个
  • 一个系统级的
  • 每个卷控制块也会保存一个列表
  • 所以如果有文件被打开将不能被卸载

当一个进程有一个打开文件操作的时候，它会返回一个index，它会指出进程打开文件表中的位置，基于这个位置会找到对应系统打开文件表。因为很可能，不同的进程会打开同一个文件，在系统打开文件表仅会记录一个。如果这个操作是打开目录或者打开文件，这个系统表就会找到对应的inode，这个文件会具体在那个地方。读写操作的时候会有一个偏移量，来处理哪个位置起的数据。这个偏移会经过文件控制块的转换，会转换成一个扇区的编号，实际上的操作就是访问对应的扇区。

  • 一些操作系统和文件系统提供该功能

  • 调节对文件的访问

  • 强制和劝告

    强制：根据锁保持情况和需求拒绝访问

    劝告：进程可以查找锁的状态来决定怎么做

13.5文件分配

大多数文件都很小

  • 需要对小文件提供强力的支持
  • 块空间不能太大

一些文件非常大

  • 必须支持大文件（64-bit文件偏移）
  • 大文件访问需要相当高效

13.5.1如何为一个文件分配数据块

分配方式

  • 连续分配
  • 链式分配
  • 索引分配

指标

  • 高效：如存储利用（外部碎片）
  • 表现：如访问速度

13.5.2连续分配

13.5.3链式分配

13.5.4索引分配

大文件一般会有多级索引，一级索引二级索引三级索引。多级索引块对于大文件和小文件管理会更加的合适。

早期的Unix系统，采用了多级索引的方式

多级索引方式的特点

文件头包含13个指针 影响
10个指针指向数据块 提高了文件大小限制阈值
第11个指针指向间接数据块 动态分配数据块，文件扩展很容易
第12个指针指向二重间接数据块 小文件开销小
第13个指针指向三重间接数据块 只为大文件分配间接数据块，大文件在访问间接数据块是需要大量的查询

13.6空闲空间列表

  • 跟踪在存储中的所有未分配的数据块
  • 空闲空间列表存在哪里
  • 空闲空间列表的最佳数据结构是怎么样的

13.6.1用简单的方式

  • 用位图代表空闲数据块列表：

    111111111111110101010011…

    如果i = 0表明数据块i是空闲，反之则已分配

  • 使用简单但是可能会使一个big vector

    160GB的磁盘->40M blocks->5MB worth of bits

    然而，如果空闲空间在磁盘中均匀分布，那么在找到0之前需要扫描n/r，其中n为磁盘上数据块的总数，r为空闲块的数目

13.6.2需要保护

  • 指向空闲列表的指针

  • 位图

    必须保存在磁盘上

    在内存和磁盘拷贝可能有所不同

    不允许block[i]在内存中的状态为bit[i] = 1，而在磁盘中bit[i] = 0

  • 解决

    在磁盘上设置bit[i] = 1

    分配block[i]

    在内存中设置bit[i] = 1

除了上述的位图方式，还有链式列表和分组列表，也可以快速查找空闲空间列表

13.7多磁盘管理-RAID

13.7.1基本概念

通常磁盘通过分区来最大限度减小寻道时间

  • 一个分区是一个柱面的集合
  • 每个分区都是逻辑上独立的磁盘

  • 分区

    硬件磁盘的一种适合操作系统指定格式的划分

  • 卷

    一个拥有一个文件系统实例的可访问的存储空间（多个disk变成一个卷来管理）

磁盘有不同的分区，不同的分区有不同的文件系统组成。

如下图13-1左边所示，disk1分为2个分区，partA和partB，用于分别放置不同的文件系统。

可以让一个文件系统扩展到多个磁盘中去。下图右边13-1所示，可以看到文件系统位于不同的磁盘上，一个磁盘就是一个device

图13-1 不同的分区的不同的文件系统图 图13-1 不同的分区的不同的文件系统图

使用多个并行磁盘来增加

  • 吞吐量（通过并行）
  • 可靠性和可用性（通过冗余）

RAID-冗余磁盘阵列

  • 各种磁盘管理技术
  • RAID levels：不同RAID分类（如RAID-0，RAID-1，RAID-5）

实现

  • 在操作系统内核：存储/卷管理
  • RAID硬件控制器（I/O）

13.7.2RAID提升访问速度、效率的原因

  • 数据块分成多个子块，存储在独立的磁盘中（和内存交叉相似）

  • 通过更大的有效块大小来提供更大的磁盘带宽（存不同的数据）

    图RAID-0

    RAID-0图 RAID-0图

  • 可靠性成倍增长

  • 读取性能线性增加（存相同的数据，向两个磁盘写入，从任何一个读取）

    图RAID-1

    RAID-1图 RAID-1图

  • 数据块级磁带配有专用奇偶检验磁盘

    允许任意一个故障磁盘中恢复（提高可靠性的同时，又能提高性能）

    例如：存储8,9,10,11,12,13,14,15,0,1,2,3

    图RAID-4

    RAID-4图 RAID-4图

  • 通过四个盘的数据，反推出坏的那个盘的数据，从而使得在Parity Disk去恢复这个数据。Parity Disk存的是纠错码，可以使用前面几个没错的Disk恢复错了的那个Disk。

    无论Disk1-4，写一个数据，对应的Parity Disk也要做写操作，这里有一个瓶颈Parity Disk的读写很频繁。Parity Disk的开销平摊到不同的磁盘中，而不是只在一个磁盘来做奇偶校验，这个时候就出现了RAID-5。RAID-5把奇偶校验块均匀的分布在每个磁盘中，这样每个磁盘的开销都是类似的。开销是均匀的，访问是并行的，高端磁盘阵列常用的方式。

    图RAID-5

    RAID-5图 RAID-5图

13.7.3其他的RAID方式

条带化和奇偶校验按byte-by-byte或者bit-by-bit

  • RAID-0/4/5：block-wise（使用比较多）
  • RAID-3：bit-wise（细粒度太细，不实用）
  • 例如在RAID-3系统中存储bit-string 101

RAID-5：每个条带块有一个奇偶校验块

  • 允许一个磁盘错误

RAID-6：两个冗余块

  • 有一种特殊的编码方式

  • 允许两个磁盘错误

还有分层的形式

  • RAID 0+1和RAID 1+0，既保证效率，也能保证冗错的简单方式，相比RAID-5和RAID-6要更加简单。

13.8磁盘调度

首先，进一步了解一下磁盘结构。旋转来寻道，磁头来前后移动找到位置，读取相应的扇区。一个硬盘来说，会有多个盘片，每个盘片会有1-2个磁头。

13.8.1磁盘性能表示

读取或写入时，磁头必须被定位在期望的磁道，并从所期望的扇区的开始

  • 寻道时间

    定位到期望的磁道所花费的时间

  • 旋转延迟

    从扇区的开始处到到达目的处花费的时间

平均旋转延迟时间=磁盘旋转一周时间的一半

13.8.2I/O时间分类

访问数据I/O的开销=寻道时间+旋转延迟时间+寻道数据访问时间

  • 寻道时间是性能上区别的原因（时间是最慢的）
  • 对单个磁盘，会有一个IO请求数目
  • 如果请求是随机的，那么会表现很差

13.8.3磁盘调度策略

13.8.3.1先进先出（FIFO）

  • 按顺序处理请求
  • 公平对待所有进程
  • 在有很多进程的情况下，接近随机调度的性能

应用程序发出的I/O访问请求，按照发出的顺序，操作系统按照顺序交给磁盘去访问。因为应用程序本身I/O访问的随机性，所以会发现磁头会存在反复横跳的现象。总的磁头距离移动长，意味着磁盘访问开销越大。

FIFO示例

FIFO示例图 FIFO示例图

13.8.3.2最短服务优先（SSTF）

  • 选择从磁臂当前位置需要移动最少的I/O请求
  • 总是选择最短寻道时间

如果I/O请求频繁出现当前的位置，而另外的I/O请求离当前位置较远，那么当前磁头只会的当前位置附近来回移动，而远处请求会持续得不到服务，就会出现饥饿现象。这使得磁盘移动不公平性，不均匀性。

SSTF示例

SSTF示例图 SSTF示例图

13.8.3.3扫描算法（SCAN）

  • 磁臂在一个方向上移动，满足所有未完成的请求，直到磁臂达到该方向上最后的磁道
  • 调换方向
  • 有时被称为elevator algorithm（电梯算法）

SCAN算法示例

SCAN算法示例图 SCAN算法示例图

13.8.3.4循环扫描算法（C-SCAN）

在上面的扫描算法的基础上，进行改进

  • 限制了仅在一个方向上扫描
  • 当最后一个磁道也被访问过了后，磁臂返回到磁盘的另外一端再次进行扫描

13.8.3.5C-LOOK算法

在C-SCAN的基础上改进

  • 磁臂先到达该方向上最后一个请求处，然后立即反转

离终点最接近的请求服务完成之后，再往上走没有新的请求点，所以到了最后一个请求处，会重新从0开始走。

在SSTF、SCAN及CSCAN集中调度算法中，都可能出现磁臂停留在某处不动的情况，例如进程反复请求对某一磁道的I/O操作。我们把这一现象称为“磁臂粘着”（arm stickiness）。

13.8.3.6N-Step-SCAN算法

  • 将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。
  • 而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。
  • 当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可以避免出现粘着现象。

如果N=2，那么就是FSCAN算法

13.8.3.7FSCAN算法

  • 实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。（结合公平性，均匀性，高效性）
  • 一个是由当前所有请求磁盘I/O的进程形成的队列，有磁盘调度按SCAN算法进行处理。
  • 在处理某队列期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列

这样，所有的新请求都将被推迟到下一次扫描时处理。