【操作系统笔记】OS_文件管理(12)

李明燮(li_mingxie)
OS
Page content

这一篇整理了操作系统的文件管理相关的内容。

1.基本概念

1.1 文件系统和文件

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

  • 在存储上: 组织,控制,导航,访问和检索数据
  • 在大多数计算机系统包含文件系统
  • 个人电脑,服务器,笔记本电脑
  • ipod,tivo,机顶盒,手机,电脑
  • google可能也是由一个文件系统构成的

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

文件系统的功能:

  • 分配文件磁盘空间
    • 管理文件块(哪一块属于哪一个文件)
    • 管理空闲空间(哪一块是空闲的)
    • 分配算法(策略)
  • 管理文件集合
    • 定位文件及其内容
    • 命名: 通过名字找到文件的接口
    • 最常见: 分层文件系统
    • 文件系统类型(组织文件的不同方式)
  • 提供的便利及特征
    • 保护: 分层来保护数据安全
    • 可靠性,持久性: 保持文件的持久即使发生崩溃,媒体错误,攻击等

文件和块:
文件属性: 名称,类型,位置,大小,保护,创建者,创建时间,最久修改时间…
文件头: 在存储元数据中保存了每个文件的信息,保存文件的属性,跟踪哪一块存储块属于逻辑上文件结构的哪个偏移

1.2 文件描述符

文件使用模式:

使用程序必须在使用前先"打开"文件

f = open(name, flag);
...
... = read(f, ...);
...
close(f);

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

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

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

  • 文件指针: 指向最近的一次读写位置,每个打开了这个文件的进程都这个指针
  • 文件打开计数: 记录文件打开的次数 - 当最后一个进程关闭了文件时,允许将其从打开文件表中移除
  • 文件磁盘位置: 缓存数据访问信息
  • 访问权限: 每个程序访问模式信息
  • 用户视图: 持久的数据结构
  • 系统访问接口: 字节的集合(UNIX);系统不会关心你想存储在磁盘上的任何的数据结构;
  • 操作系统内部视角:块的集合(块是逻辑转换单元,而扇区是物理转换单元);大小<> 扇区大小: 在UNIX中, 块的大小是 4KB
  • 当用户说: 给我2-12字节空间时会发生什么?获取字节所在的快;返回快内对应部分;
  • 如果要写2-12字节? 获取块, 修改块内对应部分, 写回块

在文件系统中的所有操作都是在整个块空间上进行的: getc() putc() 即使每次只访问1字节的数据,也会缓存目标数据4096字节(一个磁盘块)

用户怎么访问文件: 在系统层面需要知道用户的访问模式

  • 顺序访问: 按字节依次读取(几乎所有的访问都是这种方式)

  • 随机访问: 从中间读写(不常用,但是仍然重要,如: 虚拟内存支持文件,内存页存储在文件中;更加快速,不希望获取文件中间的内容的时候也必须先获取块内所有字节)

  • 内容访问: 通过特征; 文件内部结构:

  • 无结构: 单词,比特的队列

  • 简单记录结构: 列,固定长度,可变长度

  • 复杂结构: 格式化的文档(word, PDF), 可执行文件, …

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

  • 访问控制: 谁能够获得哪些文件的哪些访问权限; 访问模式: 读,写,执行,删除,列举等

  • 文件访问控制列表(ACL): <文件实体, 权限>

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

  • 指定多用户,客户如何同时访问共享文件: 和过程同步算法相似
    因磁盘IO和网络延迟而设计简单

  • UNIX文件系统(UFS)语义: 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
    共享文件指针允许多用户同时读取和写入文件

  • 会话语义:写入内容只有当文件关闭时可见

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

1.3 目录

  • 文件以目录的方式组织起来
  • 目录是一类特殊的文件: 每个目录都包含了一张表<name, pointer to file header>
  • 目录和文件的树形结构: 早期的文件系统是扁平的(只有一层目录)
  • 层次名称空间: /spell/mail/prt/first /programs/p/list

典型操作

  • 搜索文件
  • 创建文件
  • 删除文件
  • 枚举目录
  • 重命名文件
  • 在文件系统中遍历一个路径

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

确保映射的完整性,应用程序能够读目录(ls)

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

编程简单,执行耗时

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

减少目录搜索时间,碰撞,固定大小

  • 名字解析: 逻辑名字转换成物理资源(如文件)的过程: 在文件系统中: 到实际文件的文件名(路径)
    遍历文件目录直到找到目标文件

  • 举例: 解析"/bin/ls": 读取root的文件头(在磁盘固定位置) 读取root的数据块: 搜索bin项 读取bin的文件头 读取bin的数据块: 搜索ls项 读取ls的文件头

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

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

1.4 文件别名

  • 两个或多个文件名关联同一个文件:
  • 硬链接: 多个文件项指向一个文件
  • 软链接: 以快捷方式指向其他文件
  • 通过存储真实文件的逻辑名称来实现

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

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

Backpointers 方案

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

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

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

我们如何保证没有循环呢?

  • 只允许到文件的链接, 不允许在子目录的链接
  • 每增加一个新的链接都用循环检测算法确定是否合理

更多实践

限制路径可遍历文件目录的数量

1.5 文件系统种类

  • 磁盘文件系统: 文件存储在数据存储设备上,如磁盘; 例如: FAT,NTFS,ext2,3,ISO9660等
  • 数据库文件系统: 文件根据其特征是可被寻址的; 例如: WinFS
  • 日志文件系统: 记录文件系统的修改,事件; 例如: journaling file system
  • 网络,分布式文件系统: 例如: NFS,SMB,AFS,GFS
  • 特殊,虚拟文件系统

2.虚拟文件系统

分层结构:

  • 顶层: 文件,文件系统API
  • 上层: 虚拟(逻辑)文件系统 (将所有设备IO,网络IO全抽象成为文件,使得接口一致)
  • 底层: 特定文件系统模块
  • 目的: 对所有不同文件系统的抽象
  • 功能: 提供相同的文件和文件系统接口 管理所有文件和文件系统关联的数据结构 高效查询例程,遍历文件系统 与特定文件系统模块的交互

数据结构:

卷[第四声]控制块(UNIX: “superblock”)

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

文件控制块(UNIX: “vnode” or “inode”)

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

目录节点(Linux: “dentry”)

  • 每个目录项一个(目录和文件)
  • 将目录项数据结构及树形布局编码成树形数据结构
  • 指向文件控制块,父节点,项目列表等

其中: 卷控制块(每个文件系统一个),文件控制块(每个文件一个),目录节点(每个目录项一个)

持续存储在二级存储中: 在分配在存储设备中的数据块中

当需要时加载进内存

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

3.数据块缓存

  • 数据块按需读入内存: 提供 read() 操作
    预读: 预先读取后面的数据块
  • 数据块使用后被缓存: 假设数据将会再次被使用
    写操作可能被缓存和延迟写入
  • 两种数据块缓存方式: 普通缓冲区缓存
    页缓存: 同一缓存数据块和内存页

分页要求: 当需要一个页时才将其载入内存
支持存储: 一个页(在虚拟地址空间中)可以被映射到一个本地文件中(在二级存储中)

4.打开文件的数据结构

打开文件描述

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

打开文件表

  • 一个进程一个

  • 一个系统级的

  • 每个卷控制块也会保存一个列表

  • 所以如果有文件被打开将不能被卸载

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

  • 调节对文件的访问

  • 强制和劝告: 强制 - 根据锁保持情况和需求拒绝访问
    劝告 - 进程可以查找锁的状态来决定怎么做

5.文件分配

大多数文件都很小

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

一些文件非常大

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

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

分配方式

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

指标

  • 高效: 如存储利用(外部碎片)
  • 表现: 如访问速度

连续分配:
文件头指定起始块和长度
位置,分配策略: 最先匹配,最佳匹配,…

  • 优势: 文件读取表现好;高效的顺序和随机访问
  • 劣势: 碎片;文件增长问题

链式分配:
文件以数据块链表方式存储
文件头包含了到第一块和最后一块的指针

  • 优势: 创建,增大,缩小很容易;没有碎片
  • 劣势: 不可能进行真正的随机访问;可靠性

索引分配:
为每个文件创建一个名为索引数据块的非数据数据块(到文件数据块的指针列表)
文件头包含了索引数据块

  • 优势: 创建,增大,缩小很容易;没有碎片;支持直接访问
  • 劣势: 当文件很小时,存储索引的开销大;处理大文件难

6.空闲空间列表

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

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

11111101101110111 如果 i = 0表明数据块i是空闲的,反之是分配的

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

  • 160GB disk → 40M blocks → 5MB worth of bits
  • 然而,如果空闲空间在磁盘中均匀分布,那么再找到"0"之前需要扫描 磁盘上数据块总数 / 空闲块的数目

需要保护:

  • 指向空闲列表的指针
  • 位图: 必须保存在磁盘上; 在内存和磁盘拷贝可能有所不同; 不允许block[i]在内存中的状态为bit[i]=1而在磁盘中bit[i]=0

解决: 在磁盘上设置bit[i] = 1; 分配block[i]; 在内存中设置bit[i] = 1

7.多磁盘管理 - RAID

  • 通常磁盘通过分区来最大限度减小寻道时间: 一个分区是一个柱面的集合 每个分区都是逻辑上独立的磁盘
  • 分区: 硬件磁盘的一种适合操作系统指定格式的划分
  • 卷: 一个拥有一个文件系统实例的可访问的存储空间(通常常驻在磁盘的单个分区上)

使用多个并行磁盘来增加: 吞吐量(通过并行),可靠性和可用性(通过冗余) RAID - 冗余磁盘阵列: 各种磁盘管理技术;RAID levels: 不同RAID分类,如RAID-0,RAID-1,RAID-5 实现: 在操作系统内核: 存储,卷管理; RAID硬件控制器(IO)

RAID-0

  • 数据块分成多个子块, 存储在独立的磁盘中: 和内存交叉相似
  • 通过更大的有效块大小来提供更大的磁盘带宽

RAID-1

  • 可靠性成倍增长
  • 读取性能线性增加(向两个磁盘写入,从任何一个读取)

RAID-4

数据块级磁带配有专用奇偶校验磁盘: 允许从任意一个故障磁盘中恢复
条带化和奇偶校验按byte-by-byte或者bit-by-bit: RAID-0,4,5: block-wise ;RAID-3: bit-wise

RAID-5

每个条带快有一个奇偶校验块,允许有一个磁盘错误

RAID-6

两个冗余块,有一种特殊的编码方式,允许两个磁盘错误

8.磁盘盘调度

读取或写入时,磁头必须被定位在期望的磁道,并从所期望的扇区开始
寻道时间: 定位到期望的磁道所花费的时间
旋转延迟: 从扇区的开始处到到达目的处花费的时间

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

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

CIFO

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

最短服务优先:
选择从磁臂当前位置需要移动最少的IO请求
总是选择最短寻道时间

skan

磁臂在一个方向上移动,满足所有为完成的请求,直到磁臂到达该方向上最后的磁道
调换方向

c-skan

限制了仅在一个方向上扫描
当最后一个磁道也被访问过了后,磁臂返回到磁盘的另外一端再次进行扫描
c-loop(c-skan改进):
磁臂先到达该方向上最后一个请求处,然后立即反转

欢迎大家的意见和交流

email: li_mingxie@163.com