os_文件

第十章 文件系统接口

文件结构

• 目的

  • 便于程序理解文件内容

• 结构分类

  • 无结构：文字流、字节流
  • 简单记录结构：线性、固定长度、可变长度
  • 复杂结构：格式化文档、多媒体文件

为什么要有文件打开操作？

• 优点

  • 方便文件共享
  • 提高文件存取效率

• 实现打开操作需要的数据结构

  • 打开文件表：跟踪打开文件
  • 文件指针：指向最后一次读写的位置，每个进程1个
  • 打开文件计数器：打开文件的次数
  • 文件存储位置：文件在存储设备上的位置信息
  • 访问权限：每个进程的访问权限

逻辑文件及其访问方式

• ✨逻辑文件

  • 文件内容组织方式
  • 面向用户

• ✨文件的目录

  • 文件组织方式
  • 文件属性

• ✨物理文件

  • 文件存储方式
  • 面向系统

逻辑文件

• 文件呈现在用户面前的组织结构
• 又称为文件逻辑结构

• 逻辑文件决定了文件访问方法

  • 顺序访问

    • 最简单的访问方式
    • 文件信息按照顺序存放，一个记录一个记录依次访问
    • 顺序文件
    • 典型设备：磁带

  • 直接访问（随机访问）

    • 可以直接定位到文件的某条记录进行访问
    • 直接文件
    • 典型设备：磁盘

顺序文件

• 访问方式：顺序访问
• 依次访问数据，不能直接跳转到文件的指定位置
• 记录不等长

• 优点

  • 节省存储空间

• 缺点

  • 访问效率差

• 例子

  • 记录平均长度：40B，1M条记录长度：40MB
  • 访问第1万条记录：必须把0-9999个记录读入后才知道第1万条记录的首址
  • 需要读入的数据有40*10001 = 400040B

直接（随机）文件

• 访问方式：直接（随机）访问
• 直接通过计算得到需要读写记录的位置，直接跳转进行文件读写
• 记录等长

• 优点

  • 访问效率好

• 缺点

  • 浪费存储空间

• 例子

  • 记录长度：100B，1M条记录：100MB
  • 访问第1万条记录：计算得到第1万条记录的首地址为10000*100 = 100 0000
  • 从100 0000处开始读入100B
  • 需要读入的数据：100B

索引文件

• 结合顺序文件和直接文件

• 基本方法

  • 为顺序文件建立索引表
  • 记录不等长

• 例子

  • 记录平均长度：40B，索引表项大小：4B，1M条记录长度：44MB

  • 访问第1万条记录

    • 计算得到第1万条记录的索引项在索引表中的首地址：10000*4 = 40000
    • 从索引表地址40000处读入4个字节，内容为第1万条记录在顺序文件中的首地址P
    • 从顺序文件地址P处读入40个字节
  • 需要读入的数据：4+40= 44B

文件访问方式，即逻辑文件，是影响文件访问效率的因素之一

思考题

如何组织一个输入法文件的存储结构？

文件目录

文件控制块 FCB

• File Control Block

• 存放操控文件所需的各类文件属性信息

  • 文件名，长度，创建时间，存放位置，访问控制权限…
• 类似一个索引项

目录项

• 存放一个文件的各类属性

  • 包括文件在存储设备的存放地址
• 有的系统等同于文件控制块

目录

• 包含着所有文件信息的节点集合
• 根据文件名检索文件的桥梁
• 目录项的有序集合

目录文件

• 目录组织形式
• 目录作为一个文件存在于文件系统

目录相关操作

• 搜索文件

• 创建文件

• 删除文件

• 打开目录

• 创建目录

• 删除目录

• ……

• 这些操作和文件本身无关

文件检索过程

• 文件检索是一个遍历目录项的过程

  1. 打开目录文件
  2. 从磁盘读入该目录文件的1个块，该块包含若干个目录项
  3. 根据文件名遍历内存中的该块，如找到则结束
  4. 判断该目录文件是否还有物理块没有读入，如有，转2；如果没有，说明该目录中没有该文件名的文件，结束遍历
• 目录项由于经常变化，所以一般不排序

• 平均遍历目录项数：(1+n)/2

  • 不包括文件查不到的情况

目录性能

• 块 Block：内存和存储设备数据交换的基本单位

  • 一个物理块一般为4KB、8KB和16KB等

• 目录性能：读入尽可能少的物理块

• 假设

  • 目录项大小 = ds bytes
  • 目录中最多文件数 = n
  • 物理块大小 = b

• 可计算得

  • 目录文件大小 = ds*n bytes
  • 目录文件需要的物理块数目 = ds*n/b
  • 检索一个文件需要平均读入的块数 = (ds*n/b+1)/2

• 降低读块数的方法

  • 降低ds
  • 降低n

• 降低ds的方法

  • 采取i Node，目录文件将变小，类似一张索引表

• 例子

  • 物理块大小为4KB

  • 目录中有1万个文件，每个文件的目录项（FCB）大小为2KB

    • 目录文件大小 = 20000KB
    • 目录文件需要的物理块数 = 5000块
    • 检索文件平均需要访问的物理块数 = 2500.5块

  • 使用的i node = 64B

    • 目录文件大小 = 640000B = 625KB
    • 目录文件需要的物理块数 = 157块
    • 检索文件平均需要访问的物理块数 = 79块

文件保护

• 文件存取类型

• 读，写，执行，添加，删除，列表清单

• 文件的所有者有权控制

  • 能做什么
  • 由谁来做

• 访问模式

  • 读/写/执行

• 建立一个组，加入一些用户
  

• 对特定的文件或目录，定义适当的访问权限

目录结构

目录结构的设计目标

• 效率

  • 快速定位文件位置
  • 提高文件访问效率

• 命名

  • 方便用户使用
  • 同名的不同文件
  • 不同名的相同文件

• 分组

  • 文件分组（子目录）
  • 兼顾效率和方便性

单层目录

• 所有文件都在同一个目录中，只有一级目录：根目录（/）

• 优点

  • 结构简单

• 缺点

  • 检索效率差

    • 目录下文件太多
  • 不能有同名文件，而且一个文件只能有一个名称
  • 不能分组

双层目录

• 每个用户都有自己的目录结构

• 优点

  • 不同用户可有相同文件名的文件
  • 比单层目录提高检索效率高

• 缺点

  • 无法分组
  • 同一个用户不能拥有相同文件名的文件

• 从根目录开始到文件的路径，称为路径名

  • /user4/a
  • /user1/a

树形目录

• 是双层目录的扩展：2层=>N层

• 特点

  • 检索高效

    • 子目录多导致每个每个目录下文件减少
  • 可以分组
  • 允许重名

• 绝对路径

  • 从根目录开始的路径名

• 相对路径

  • 从当前目录开始的路径名
  • 可以提高检索效率
• 目录项占1个物理块 | 目录文件 | 目录项 | 平均读入块数 | | —- | —- | —- | | / | spell | 0 | | spell | mail | (1+7)/2 = 4 | | mail | prt | (1+4)/2 = 2.5 | | prt | first | (1+2)/2 = 1.5 |

• 如果使用绝对路径

  • 根目录一般在内存
  • 所以需要读入4+2.5+1.5 = 8个物理块

• 如果使用相对路径

  • 当前目录在内存
  • 读入1.5个内存块

无环图目录

• 文件共享

  • 不同目录中的文件指向同一个物理文件，也就是他们的内容相同

• 树形目录不能实现文件共享，图型目录可以实现

  • 无环图目录
  • 通用图目录（有环）

• 两种共享文件的方式

  • 硬链接 Linux

• 符号链接 Windows 即快捷方式

通用图目录

• 有环图

• 如何保证无环？

  • 仅允许指向文件的链接，不允许指向子目录的链接
  • 垃圾回收
  • 每当加入新链接时，使用环路检测算法判断是否正确
  • 优化遍历目录算法，避免对环的重复搜索

第十一章 文件系统实现

文件系统

• 系统角度

  • 对存储设备的空间进行组织和分配
  • 负责文件检索、读写等操作
  • 目标：存取速度和存储空间效率

• 用户角度

  • 提供按名存取的文件访问机制
  • 文件的组织管理
  • 目标：方便的文件存储机制

文件系统的层次架构

• I/O控制

  • 设备驱动程序
  • 中断

• 设备驱动程序

  • 控制I/O设备运行
  • 向硬件控制器发送专门控制命令
  • 操作系统通过设备驱动程序控制设备

• 基本文件系统

  • 物理块读写
  • 向设备驱动程序发送控制命令

• 文件组织模块

  • 管理文件、逻辑块和物理块
  • 把文件的逻辑地址转换成物理地址
  • 管理空闲空间
  • 为文件分配物理块

• 逻辑文件系统

  • 管理文件系统中的元数据

    • 除了文件数据外的所有结构数据
  • 文件按名存取
  • 文件目录组织管理
  • 把文件名转换成文件ID，文件句柄
  • 管理FCB
  • 存储保护

基本概念

• 物理块：一个或2个扇区组成，基本文件读写单位

• 分区 Partition ：磁盘分割成若干个独立的空间，每个空间称为分区

  • 主分区：能够安装操作系统的启动分区
  • 扩展分区：不能直接使用，必须分成若干逻辑分区

• 卷（逻辑磁盘）Volume： 磁盘上的逻辑分区

  • 一般每个卷都可以建立一个文件系统

文件系统的实现

• 两种文件系统

  • 磁盘文件系统
  • 内存文件系统

• 磁盘文件系统

  • 引导控制块：包含了引导操作系统的各种信息，在主分区才有

    • UFS：引导块
    • NTFS：分区引导扇区

  • 分区控制块：包含分区信息

    • 总的块数、空闲块数、块的大小
    • UFS：超级块
    • NTFS：主控文件表
  • 目录和FCB
  • 用户目录

• 内存文件系统

  • 分区表：所有安装分区的信息
  • 目录缓冲结构：保存最近访问的目录信息
  • 系统打开文件表
  • 进程打开文件表
• 文件操作需要用到内存文件系统，该系统目的是通过缓冲技术提高文件系统性能

虚拟文件系统

• 目的

  • 支持多个系统
  • 把多个文件系统整合成一个目录结构
  • 为用户屏蔽各个文件系统的差异

• 虚拟文件系统 VFS

  • 提供了一种面向对象的方法来实现文件系统
  • 为不同类型的文件系统提供了接入VFS的接口
  • 为用户提供了统一的系统调用API

• 文件系统接口

  • 统一的应用程序访问问价的接口
  • 例如：open, close, read, write

• VFS接口

  • 为各类不同的文件系统定义VFS接口
  • 符合该接口的文件系统都可以接入VFS

网络文件系统

• Network File System
• 用于通过局域网或广域网访问远程文件的软件系统的实现

• 优点

  • 节省存储空间
  • 实现共享

连续分配

物理块

• 读写存储设备的基本单位

  • 文件读写操作时，以块为单位进行
  • 例如程序需要读取1个字节，则OS把包含该字节的一块都读入
  • 优点：减少读写次数，提高效率

• 存储设备的基本分配单位

  • 以物理块为单位，为文件分配存储空间
  • 例如即使文件的大小为1字节，也给它分配4096字节（物理块的大小）的存储空间。

• 和内存的页面大小相对应

  • 页面大小：4KB
  • 物理块大小：4KB的整数倍

逻辑块

• 在文件空间中的块

  • 大小和物理块一致
  • 一个逻辑块存储在一个物理块中

存储空间的分配方式

• 连续存储空间

  • 连续分配

• 离散存储空间

  • 链接分配
  • 索引分配

连续分配

• 每个文件在磁盘上占用一组连续的物理块

• FCB包含

  • 起始块号
  • 长度

地址映射

• 逻辑地址 LA：文件内的相对地址
• 物理地址 (B, D)：存放在物理块中的地址
• 物理块大小：S

• 物理地址

  • LA ÷ S 的商 = 逻辑块号Q
  • LA ÷ S 的余数 = 块内偏移 D
  • 物理块号 B = Q + 起始块号

• 例

  • 读取文件中偏移量为12321位置的数据（块大小为4KB），起始块号 = 6
  • Q = 12321/4KB = 3
  • D = 33
  • B = 3 + 6 = 9

优点

• 支持随机访问

  • 可以直接访问指定快块号的物理块

• 存取速度快

  • 上一个块到下一个块的移动距离短
• 适用一次性写入操作

缺点

• 浪费空间

  • 小空间无法分配

• 文件不能动态增长

  • 当文件A的前面有文件存储，后面也有文件存储的时候，文件A的存储空间就被固定了

• 不利于文件的插入和删除

  • 需要移动数据

连续分配的改进

• Veritas File System

• 基于扩展的文件系统（局部连续）

  • 扩展是一组连续的磁盘块集合
  • 扩展在文件分配时被分配
  • 一个文件可能包含一个或多个扩展
  • 需要指向下一个扩展的指针

链接分配

• 文件信息存放在若干个不连续的物理块中
• 文件的所有物理块通过指针连接成链表结构

• 分类

  • 显式链接
  • 隐式链接

隐式链接

• 链表的指针隐藏在物理块中，每个物理块中的指针指向下一个物理块
• FCB给出文件的首块地址
• 文件结束于空指针

• 每个物理块用于存放文件信息的空间变小

  • 因为指针本身需要占用空间
  • 4KB的物理块，指针有4B，因此物理块只能存放4092B的数据

地址映射

• 逻辑地址：LA
• 物理地址：(B, D)
• 物理块大小：S，指针大小：P

• 确认物理地址

  • 逻辑块号 Q = LA ÷ (S-P) 的商
  • 块内偏移 D = LA ÷ (S-P) 的余数
  • 块号 B = 链表中第 Q 项对应的物理块块号

优点

• 可以离散存放，提高磁盘的利用率
• 可以动态扩充文件大小
• 便于文件的插入和删除操作

缺点

• 无法实现随机访问，访问文件慢

  • 访问第 i 块，需要把 0-(i-1) 块都读入
• 可靠性差

优化方法：多块集合成组

显式链接

• 隐式链接的问题

  • 指针分散存放
  • 为了读入一个指针需要读入整个物理块

• 显式链接

  • 指针集中存放，所有指针存放在一张链接表中
  • 先访问链接表，在访问物理块，提高了检索速度
• 链接表一般在文件系统装载时装入内存

• 链接表大小

  • 表项16位（FAT16）：最大2*2Bytes = 128KB
  • 表项32位（FAT32）：最大2*4Bytes = 16GB

• 不适合大容量的磁盘

  • 比如4TB的磁盘，物理块4KB
  • 链接表大小 = （4TB/4KB）*4Bytes = 4GB
• 显示链接的例子：FAT32

FAT 32

• 两个FAT表

• 每个物理块固定为4KB — 32KB

• FAT表的表项占据32位

• 最大表项数位2项

• 单个文件不能大于4G

• FAT32 管理的单个最大磁盘空间：4KB*2 = 16TB

索引分配

• 隐式链接分配问题

  • 指向下一个块的指针分散在各个块中

• 改进：文件分配表 FAT

  • 系统：存放指针的文件分配表
  • 大文件系统会导致文件分配表过大

• 解决方法：分散的 FAT

  • 每个文件一张文件分配表，即索引表

索引分配

• 索引块

  • 存放指向文件每个物理块块号的物理块
  • 索引块的第 i 个项：存放第 i 个逻辑块对应的物理块块号
• FCB指向索引块

• 优点

  • 支持随机访问

    • 先访问索引块，在访问具体块
  • 离散存放，没有碎片

• 缺点

  • 需要额外的空间存放索引表
  • 磁盘访问时间增加，物理块分布在各个磁盘

地址映射

• 逻辑地址：LA

• 物理地址：(B, D)

• 物理块大小：S，指针大小：P

• 确认物理地址

  • 逻辑块号 Q = LA ÷ S 的商
  • 块内偏移 D = LA ÷ S 的余数
  • 块号 B = 索引表中第 Q 项存放的块号

• 对于大文件

  • 物理块大小 S = 4KB
  • 表项大小：4个字节
  • 每个物理块存放的块号数目 = 4K / 4 = 1K个
  • 单级目录的最大文件 = 1K * 4KB = 4MB
  • 解决方法：多级索引

多级索引

• 把索引块通过链表组织（无长度限制）

  • 访问的块号 B = 索引表中第Q1块索引块中第Q2项存放的块号
  • 块内偏移 D = R2
  • Q1 = LA / (S * (S-P)) 的商
  • R1 = LA / (S * (S-P)) 的余数
  • Q2 = R1 / S 的商
  • R2 = R1 / S 的余数

• 把索引通过索引组织（有长度限制）

• 二级索引

  • 外层索引表 （一个物理块）
  • 内层索引表 （物理块数目 = 外层索引表的项数）

索引和文件大小

• 假设

  • 物理块大小 S = 4KB
  • 索引项大小 = 4B

• N级索引文件大小 = (1K)*4KB

  • 单级索引：4MB
  • 二级索引：4GB
  • 三级索引：4TB

联合策略

• 混合多种索引

  • 每块4KB

• 0级索引

  • 即FCB中的12个指针指向12个块

• 1级索引

  • 1K块

• 2级索引

  • 1M块

• 三级索引

  • 1G块

空闲空间管理

空闲空间管理方法

• 空闲表
• 空闲链表
• 位示图
• 成组链接

空闲表

• 空闲区

  • 连续的未分配物理块集合

• 空闲表

  • 每个表项对应一个空闲区

  • 内容

    • 空闲区的第一块号
    • 空闲块的快数
  • 适用于连续分配
  • 需要占额外的空间
• 分配和回收方式：类似内存的连续分配

空闲链表

• 把磁盘上所有的空闲块连接在一个链表中

• 分配

  • 从链表头依次摘下适当数目的空闲块

• 回收

  • 空闲块加入链表尾部

• 优点

  • 不需要专用块存放管理信息

• 缺点

  • 增加I/O操作，得到连续空间难

位示图

• 利用二进制位（1bit）来表示一个块的使用情况

  • 1表示空闲
  • 0表示已分配

• 所有块都有一个二进制位与之对应

  • 分配 1=>0，回收 0=>1
• 所有块对应的位形成位示图

• 存储位示图本身需要额外的空间，存放在物理块中

  • 磁盘空间 = 2Bytes = 1GB
  • 块大小 = 2Bytes
  • 位数 = 2bits = 32KB
• 必要容易的到连续的物理块

• 块号计算

  • 假设已知位示图中位置

    • 第 i 个字节， 第 j 位
    • **块号 k = i 8 + (7 - i)

  • 假设已知块号k

    • i = [ k / 8 ]
    • j = 7 - k % 8

成组链接

• 结合空闲表和空闲链表

• 例子：UNIX

  • 把空间块分成若干组，每100个块分一组

  • 每组第一个空闲块记录

    • 空闲块总数

    • 下一组空闲块首块的块号

      • 0表示该组是最后一组
    • 本组其他空闲块的块号列表

• 如果要分配50块空闲块

  • 从前往后分配，从第一组开始分配，分完再分下组

  • 上例中，就是先分配第一组的全部（10块）

  • 再分配第二组的前40块

空闲块回收

• 先把释放的空闲块放到第一组
• 满100块后，在第一组之前再开辟一组
• 原来的第一组变成第二组，新组为第一组

一致性检查

• 将目录结构数据和磁盘空闲块结构相比较，纠正发现的不一样

  1. 空闲块在某个文件的物理块中
     

  2. 非空闲块不属于任意一个文件
     

  3. 一个物理块属于多个文件

空闲空间整理

• 把不连续的空间快集合在一起
• 有利于给文件分配连续的物理块

第十二章 大容量存储器结构

✨ 传输时间，磁盘调度

磁盘结构和管理

磁盘结构

• 盘片

  • 存储数据的介质
  • 正反两面可以存储数据

• 磁头

  • 读写数据，沿磁盘半径移动
  • 有多少盘面就有多少磁头

• 主轴

  • 马达驱动，使盘片旋转
  • 固定速度旋转
• 接口
• 磁盘控制器
• 缓冲区

盘片结构

• 磁道

  • 磁头在盘片表面划出的圆形
  • 盘面划分为数目相等的磁道
  • 从盘面外缘“0”开始编号

• 扇区

  • 磁道被等分为若干个弧段，称为扇区
  • 扇区大小：512字节

• 柱面

  • 具有相同编号的磁道形成一个援助，称为柱面
  • 有几个磁道就有几个柱面

地址映射关系

• 块号：LBA

• 磁盘地址：(C, H, S)

  • 柱面 Cylinder
  • 磁头 Head
  • 扇区 Sector
• SPT：每个磁道最大扇区数
• HPC：最大磁头数

✨ 磁盘访问时间

• 磁盘旋转速度：60 — 250 转/秒

  • RPM：每分钟旋转次数

• 定位时间/随机访问时间

  • 寻道时间：移动磁臂到所需磁道时间

    • 平均寻道时间：1/3 磁道移动 （1-4ms）

  • 旋转延迟：等待扇区移动到磁头下时间

    • 平均旋转1/2圈时间：1/(2*RPM/60)

• 传输时间

  • 传输率：传输总字节数除以传输时间

• 磁盘访问时间

  • 随机访问时间

    • 寻道时间
    • 旋转延迟时间
  • 传输时间
  • 系统开销时间

• 例题

  • 4KB 块，7200RPM 磁盘，5ms 平均寻道时间，1Gb/sec 传输率，0.1ms 控制开销
    5ms + 1000/(2*7200/60)ms + 4KB / 1Gb/sec + 0.1ms
    = 5.1ms + 4.17ms + 0.03ms
    = 9.30ms

磁盘管理

• 低级格式化

  • 将磁盘分成扇区，以便磁盘控制器读写

• 分区

  • 将磁盘分成分区
  • 主分区和扩展分区

• 高级格式化

  • 逻辑格式化，创建文件系统

• 引导快

  • 自举系统保存在 ROM 中
  • 自举程序装载引导快程序

磁盘调度和RAID

磁盘调度

• 目标：减少磁盘访问时间

• 访问时间

  • 寻道时间：磁头移动到访问扇区所在磁道的时间
  • 旋转延迟时间：将访问扇区转到磁头下的时间
  • 传输时间：将数据从磁盘送到内存的时间
• 寻道时间最小化，寻道时间 ≈ 寻道距离

• 假定有一个序列（0 — 199 道）

  • 98, 183, 37, 122, 14, 124, 65, 67
  • 磁头当前位置在 53

先来先服务算法 FCFS

• 按照请求提交时间访问

• 优点

  • 简单、公平
  • 易实现

• 缺点

  • 寻道时间长

最短寻道时间优先算法 SSTF

• Shorted Seek Time First
• 每次移动到离现在位置最近的磁道

• 优点

  • 寻道时间短

• 缺点

  • 存在饥饿
  • 磁头频繁变换移动方向
  • 增加寻道时间

扫描算法 SCAN

• 磁头从磁盘一端向另一端移动，沿途响应服务请求

• 优点

  • 同一方向扫描，寻道时间短

• 缺点

  • 有的请求等待时间长

循环扫描算法 C-SCAN

• 单项处理请求

  • 磁头从磁盘外道（0道）移到内道过程中处理请求
  • 内道移动到外道的过程中不处理请求

• 优点

  • 更均匀的等待时间，从磁道199移动道0的时间很短
• 总的磁头移动为382柱面

循环 Look 算法 C-LOOK

• C-SCAN 的变形
• 磁头之移动到一个方向上最远请求为止，而不是继续到磁盘尽头
• 总的磁头移动为322柱面

磁盘调度算法的选择

• 性能主要依赖于请求的数量和类型

  • 磁盘服务请求很大程度上受文件分配方法影响
  • SSTF 较为普遍且很有吸引力
  • SCAN 和 C-SCAN 适合磁盘大符合系统
• SSTF 或 LOOK 是比较合理的缺省算法

第十三章 I/O 系统

举例说明 spooling 技术