文件系统原理

什么是文件?

文件是指一组带标识的、在逻辑上有完整意义的信息项的序列
信息项:构成文件内容的基本单位,各信息项之间具有顺序关系。

按照文件性质和用途分类(UNIX)

  • 普通文件:一般为ASCII或二进制文件
  • 目录文件:管理文件系统的系统文件
  • 特殊文件:
    • 字符设备文件:和输入输出有关,用于模仿串行IO设备,例如终端、打印机,网卡等;
    • 块设备文件:磁盘

文件目录

  • 文件目录:统一管理每个文件的元数据,以支持文件名到文件物理地址的转换。
  • 目录文件:将文件目录以文件的形式存放在磁盘上。
  • 目录项:目录项可以是FCB(File control Block),目录是文件控制块的有序集合。

文件在存储介质上的存放方式

存储结构,通常的结构有:

连续结构

存储在连续的磁盘工具。

链接结构

一个文件的信息存放在若干不连续的物理块中,各块之间通过指针连接。
优点:

  • 提高了磁盘空间利用率,不存在外部碎片问题
  • 有利于文件的插入和删除
  • 有利于文件的动态扩充

缺点:

  • 存取速度慢,不适于随机存取
  • 可靠性问题,如指针出错
  • 更多的寻道次数和寻道时间
  • 链接指针占用一定的空间

链接结构的一个变形:文件分配表FAT(File Allocation Table)
FAT文件的基本思想:使用一张表记录所有文件的链接指针。

索引结构

  • 一个文件的信息存放在若干不连续物理块中
  • 系统为每个文件建立一个专用数据结构,索引表,并将这些物理块的块号存在在该索引表中。
  • 索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块

优点:
保持了链接结构的优点,又解决了其缺点:

  • 既能顺序存取,又能随机存取
  • 满足了文件动态增长、插入删除的要求
  • 能充分利用磁盘空间

缺点:

  • 较多的寻道次数和寻道时间
  • 索引表本身带来了系统开销

索引表很大,一个物理块不够,则其组织方式:

  • 链接索引方式:一个盘块存一个索引表,多个索引表链接起来
  • 多级索引方式:将文件的索引表地址放在另一个索引表中
  • 综合模式:直接索引方式与间接索引方式结合

UNIX文件系统采用多级索引结构(综合模式)

  • 每个文件的主索引表有15个索引项(FCB中),每项2个字节
  • 前12项直接存放文件的物理块号(直接寻址)
  • 如果文件大小大于12块,则利用第13项指向一个物理块,在该块中存放的是一级索引表。
    假设扇区大小为512字节,物理块等于扇区块大小,一级索引表可以存放256个物理块号
  • 对于更大的文件还可利用第14和第15项作为二级和三级索引表

可见,上述索引结构下UNIX系统中,可存放的最大文件大小为如下数量物理块(物理块为4KB):
$$
12 + 256 + 256^2 + 256^3
$$
即 32GB。

各种文件系统的限制:
NTFS(Windows):支持最大分区2TB,最大文件2TB
FAT16(Windows):支持最大分区2GB,最大文件2GB
FAT32(Windows):支持最大分区128GB,最大文件4GB
Ext2: 最大文件大小, 1TB;最大文件名长度: 255 字符
Ext3: 最大文件大小: 1TB, 最大文件名长度: 255 字符

  • 假设一个文件被划分成N块,这N块在磁盘上是怎么存放的?
  • 其地址(块号或簇号)在FCB中是怎么记录的?

文件系统的实现

磁盘上文件系统的布局:
主引导区 分区表 分区1 分区2 分区3

UNIX文件系统布局:
引导区 超级数据块 空闲区管理 i-节点区 根目录区 文件和目录区

windows的FAT文件系统布局
引导区 文件分配表1 文件分配表2 根目录 其他目录和文件

内存中所需的数据结构

  • 系统打开文件表

    • 整个系统一张
    • 放在内存:用于保存打开文件的FCB
      FCB(i节点)信息 | 引用计数 | 修改标记
  • 用户打开文件表

    • 每个进程一个
    • 进程的PCB中记录了用户打开文件表的位置
      文件描述符 | 打开方式 | 读写指针 | 系统打开文件表索引

如何加快目录检索
目录项分解法:即把FCB分成两部分

  • 符号目录项:文件名,文件号
  • 基本目录项:除文件名外的所有字段·

UNIX文件系统的实现

文件系统的实例(FAT)

引导区 | 文件分配表1 | 文件分配表2 | 根目录 | 其他目录和文件

  • 在FAT16的簇(块)的大小:1,2,4,8,16,32或64个扇区
  • 文件系统的数据记录在“引导扇区”中
  • 文件分配表FAT的作用
    描述簇的分配状态,标注下一个簇的簇号等
  • FAT16表项:2字节,16bits
  • 目录项(FCB):32字节。以FAT16为例:文件名(8字节)、文件扩展名(3字节)、文件属性(1字节)、10字节保留、最后一次修改时间(2字节)、最后一次修改日期(2字节)、起始簇号(2字节)、文件大小(4字节)。
  • 根目录大小固定

主引导记录MBR

主引导记录位于0号扇区,记录了引导代码(占446字节),以及分区表项(1-4,分别占16字节)

分区引导记录DBR

DBR占用一个扇区大小,依次包括转义指令、文件系统标志、BIOS参数块、扩展BIOS参数块,引导代码(410字节)等。

文件分配表FAT

表项在FAT16中的表项为16bits,FAT32中的表项中为32bits。

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

文件操作实现(以unix为例)

  • 创建文件:建立系统与文件的联系,实质是建立文件的FCB。

    • 检查参数的合法性,例如,文件名是否符合命名规范,有没重名文件;
    • 申请空闲目录项,并填写相关内容
    • 为文件申请磁盘块;
    • 返回
  • 打开文件:用户给出文件路径名,获取文件句柄或文件描述符,需将该文件的目录项读入内存

    • 根据文件路径名查找目录,找到目录项(或I节点号);
    • 根据文件号查系统打开文件表,看文件是否已被打开。是,则共享计数加1;否则将目录项(或I节点)等信息填入系统打开文件表空表项,共享计数置1;
    • 根据打开方式、共享说明和用户身份检查访问合法性;
    • 在用户打开文件表中获取一个空表项,填写打开方式等,并指向系统打开文件表对应表项
  • 指针定位
    系统为每个进程打开的每个文件维护一个读写指针,即相对文件开头的偏移地址(读写指针指向每次文件读写的开始位置,在每次读写完成操作后,读写指针按照读写的数据量自动后移相应数值)

    • 由fd查用户打开文件表,找到对应的表项;
    • 将用户打开文件表中文件读写指针位置设为新指针的位置,供后继续写命令存取指针处文件内容
  • 读文件:

    read(文件描述符, 读指针,要读的长度,内存目的地址)
    • 根据打开文件时得到的文件描述符,找到相应的文件控制块(目录项),确定读操作的合法性
    • 将文件的逻辑块号转换为物理块号
    • 申请缓冲区
    • 启动磁盘I/O操作,把磁盘块中的信息读入缓冲区,在传送到指定的内存区
    • 反复上述两个步骤,直到读出所需数量的数据或读到文件尾。

文件系统的管理

文件系统的一致性

问题的产生:
磁盘块->内存->写回磁盘块
若在写回之前,系统崩溃,则文件系统出现不一致

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

  • 磁盘块的一致性检查。unix一致性检查工作过程:
    两张表,每块对应一个表的计数器,初值为0

    • 表一:记录了每个块在文件中出现的次数
    • 表二:记录了每块在空闲表中出现的次数

文件系统的写入策略

考虑文件系统一致性和性能

  • 通写(write-through):内存中的修改立即写入磁盘。
    -缺点:速度性能差,如FAT文件系统
  • 延迟写(Lazy-write):利用回写(write back)缓存的方法得到高速。
    • 缺点:可恢复性能差
  • 可恢复写(transaction log):采用事务日志来实现文件系统的写入,既考虑安全性,又考虑速度性能,如NTFS、EXT3

文件系统的安全

访问控制

  • 主动控制,访问控制表

  • 每个文件一个

  • 记录用户ID和访问权限

  • 用户可以是一组用户

  • 文件可以是一组文件

  • 能力表(权限表)

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

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

  • 第一级:对访问者的识别,对用户分类:
    • 文件主(owner)
    • 文件主的同组用户(group)
    • 其他用户(other)
  • 第二级:对操作权限的识别,对操作分类:
  • 读操作(r)
  • 写操作(w)
  • 执行操作(x)
  • 不能执行任何操作(-)

文件系统的性能

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

提高文件系统性能的方法:目录项(FCB)分解、当前目录、磁盘碎片整理;块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术等

  • 块高速缓存(Block Cache):在内存中为磁盘块设置的一个缓存区,保存了磁盘中某些块的副本

  • 预读取:每次访问磁盘,多读取一些磁盘块。(根据局部性原理)

  • 合理分配磁盘空间:分配磁盘块时,把有可能顺序存取的块放在一起

  • 磁盘调度:当有多个访盘请求等待时,采用一定的策略,对这些请求的服务顺序调整安排,从而降低平均磁盘服务时间,达到公平、高效
    公平:一个I/O请求在有限时间内满足
    高效:减少设备机械运行带来的时间开销

    • FIFO
    • 最短寻道时间优先(Shortest Seek TIme first)
    • 扫描算法SCAN(电梯算法):当设备无访问请求时,磁头不动;当有访问请求时,磁头按一个方向移动,在移动过程中对遇到的访问请求进行服务,然后判断该方向上是否还有访问请求,如果有则继续扫描;否则改变移动方向,并为经过的访问请求服务,如此反复。
    • 单向扫描调度算法(C-SCAN):主要目的是减少了新请求的最大延迟。主要过程:单向扫描调度算法C-SCAN,总是从0号柱面开始向里扫描;按柱面(磁道)位置选择访问者;移动臂到达最后一个柱面后,立即带动读写磁头快速返回到0号柱面;返回时不为任何的等待访问者服务;返回后可再次进行扫描。
    • N-step-SCAN策略:目的:克服“磁头臂的粘性”。过程:把磁盘请求队列分成长度为N的子队列,每一次用SCAN处理一个子队列;在处理某一个队列时,新请求添加到其他子队列中;如果最后剩下的请求数小于N,则它们全部精在下一个扫描时处理
    • 旋转调度算法:根据延迟时间来决定执行次序的调度。三种情况:
      1.若干等待访问者请求访问同一磁头上的不同扇区;
      2.若干等待访问者请求访问不同磁头上的不同编号的扇区;
      3.若干等待访问者请求访问不同磁头上具有相同的扇区。
      对于前两种情况:总是首先到达读写磁头位置下的扇区先进行传送操。
      对于第3种情况:这些扇区同时到达读写磁头位置下,可任意选择一个读写磁头进行传送操作。
    • RAID技术

一次访盘时间 = 寻道时间 + 旋转延迟时间 + 传输时间,我们应该减少寻道时间,减少延迟时间

Was this helpful?

0 / 0

发表回复 0