一、文件与文件系统

1.1 文件是什么

• 文件是对磁盘的抽象
• 所谓文件是指一组带标识（标识即为文件名）的、在逻辑上有完整意义的信息项的序列。
• 信息项：构成文件内容的基本单位（单个字节，或多个字节），各信息项之间具有顺序关系

• 文件内容的意义：由文件建立者和使用者解释

  
  1

1.2 如何设计一个文件系统

这里先看文件管理的需求：

• 从用户角度
  文件系统是如何呈现在用户面前：

  • 一个文件的组织
  • 如何命名
  • 如何保护文件
  • 可以实施的操作

• 从操作系统角度：怎样组织、管理文件

  • 文件的描述、分类
  • 文件目录的实现
  • 存储空间的管理
  • 文件的物理地址
  • 磁盘实际运作方式（与设备管理的接口）
  • 文件系统的性能

1.3 文件系统

• 操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用

• 文件系统要完成哪些任务
  1、统一管理磁盘空间，实施磁盘空间的分配与回收
  2、实现文件的按名存取：名字空间--映射-->磁盘空间
  3、实现文件信息的共享，并提供文件的保护、保密手段
  4、向用户提供一个方便使用、易于维护的接口，并向用户提供有关统计信息
  5、提高文件系统的性能
  6、提供与IO系统的统一接口

1.4 文件的分类

按文件性质和用途分类（UNIX），一般分为普通文件、目录文件、特殊文件（设备文件）、管道文件、套接字

• 普通文件
  即用户自己建立的文件，包含了用户的信息，一般为ASCII或二进制文件

• 目录文件
  管理文件系统的系统文件

• 特殊文件
  字符设备文件：和输入输出有关，用户模仿串行I/O设备，例如终端、打印机、网卡等。
  块设备文件：磁盘

1.5 文件的逻辑结构

2
说明：这里是从用户角度看文件，由用户的访问方式确定，这里给出了三种逻辑结构，还可以组织成堆、顺序、索引、索引顺序、散列等结构。第一种是以字节为单位的流式结构，第二种是一种记录式文件结构，最后一种是树形结构。

1.6 典型的文件逻辑结构与文件存取

• 流式文件：构成文件的基本单位是字符
  文件是有逻辑意义、无结构的一串字符的集合
• 记录式文件：文件由若干记录组成，可以按记录进行读写、查找等操作。每条记录有其内部结构
• 文件的逻辑结构与文件存取之间的关系
  顺序存取（访问）
  随机存取：提供读写位置（当前位置）。如UNIX的seek操作。

1.7 文件的存储介质

1.7.1 存储介质与物理块

• 典型的存储介质
  磁盘（包括固态盘SSD）、磁带、光盘、U盘、......
• 物理块（块block、簇cluster）
  信息存储、传输、分配的独立单位
  存储设备划分为大小相等的物理块，统一编号

1.7.2 典型的磁盘结构

3

1.7.3 磁盘访问

一次访问磁盘的请求：读写、磁盘地址（设备号、柱面号、磁头号、扇区号），内存地址（源/目）
完成过程由三个动作组成：

• 寻道（时间）：磁头移动定位到指定磁道
• 旋转延迟（时间）：等待指定扇区从磁头下旋转经过
• 数据传输（时间）：数据在磁盘与内存之间的实际传输

1.7.4 磁盘空间管理

有关数据结构

• 位图
  用一串二进制位反映磁盘空间中分配使用情况，每个物理块对应一位，分配的物理块为0，否则为1。
  申请物理块时，可以在位示图中查找1的位，返回对应的物理块号
  归还时，将对应位转置1。

• 空闲块表
  将所有空闲块记录在一个表中，即空闲块表
  主要两项内容：起始块号，块数

• 空闲块链表
  把所有空闲块链成一个表
  扩展：成组链接法

磁盘地址与块号的转换

4

成组链接法设计思想

5
说明：左上角的是一个专用块，表示一些有用信息，而右边大括号中的都是空闲块。所有空闲块我们分成了若干组，典型的是100块是一组，最后一个空闲组只有99个空闲块。专用块中有20个空闲块号，分别对应右边的空闲块组。每次要使用文件的时候，就从专用块中挑选空闲块，一般从801开始分配。820中的第一块实际上是记录了后面一块800中空闲块的空闲块号和总的空块的数量，后面的以此类推。最后一个组中的0则表示最后一组的标志。

成组链接法：分配算法
分配一个空闲块
查L单元（空闲块数）

• 当空闲块数 > 1 , i = L + 空闲块数；
  从i单元得到一个空闲块号；
  把该块分配给申请者；
  空闲块数减1
• 当空闲块数 = 1， 取出L + 1单元内容（一组的第一块号或0）；
  其值 = 0无空闲块，申请者等待
  其值不等于零，把该块内容复制到专用块
  该块分配给申请者；

把专用块内容读到内存L 开始的区域。

成组链表法：回收算法
归还一块
查L单元的空闲块数

• 当空闲块数 < 100空闲块数加一；
  j := L + 空闲块数
  归还块号填入j单元

• 当空闲块数 = 100， 则把内存中登记的信息写入归还块中；
  把归还块号填入L+ 1单元；
  将L单元置成1。

二、文件控制块和文件目录

2.1 文件属性

• 文件控制块（File Control Block：FCB）
  为管理文件而设置的数据结构，保存管理文件所需的所有有关信息（文件属性或元数据）

• 常用属性
  文件名，文件号，文件大小，文件地址，创建时间，最后修改时间，最后访问时间，保护，口令，创建者，当前拥有者，文件类型，共享计数，各种标志（只读、隐藏、系统、归档、ASCII/二进制、顺序/随机访问、临时文件、锁）

• 基本文件操作

  
  6

2.2 文件目录、目录项与目录文件

• 文件目录

  • 统一管理每个文件的元数据，以支持文件名到文件物理地址的转换
  • 将所有文件的管理信息组织在一起，即构成文件目录

• 目录文件
  将文件目录以文件的形式存放在磁盘上

• 目录项

  • 构成文件目录的基本单元
  • 目录项可以是FCB，目录是文件控制块的有序集合

2.3 文件目录结构的演化

7
说明：最初是以一级目录结构，最后慢慢演化成了树形目录结构。

2.4 与目录相关的概念

• 路径名
  绝对路径名：从根目录开始
  相对路径：从当前目录开始

• 当前目录/工作目录

• 目录操作
  创建目录、删除目录等等

2.4 目录文件之间的关联

8

三、文件的物理结构

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

主要解决两个问题：

• 假设一个文件被划分成N块，这N块在磁盘上是怎么存放的？
• 其地址（块号或簇号）在FCB中是怎样记录的？

3.1 连续（顺序）结构

• 文件的信息存放在若干连续的物理块中
  

  9
  在上图a中，存放者多个连续的文件，在b中有些磁盘空间被还回来了。如果有些块太小，可能就不能再利用了。在FCB中我们只需要给出文件块的首地址和块数即可。

• 优点
  简单
  支持顺序存取和随机存取
  所需的磁盘寻道次数和寻道时间最少
  可以同时读入多个块，检索一个块也很容易

• 缺点

  • 文件不能动态增长，因为可能后面的磁盘空间已经被占据了。如果要增长则需要给出预留空间，但是这样就导致了浪费或重新分配和移动的开销。
  • 不利于文件插入和删除
  • 产生外部碎片：可以使用紧缩技术进行整理

3.2 链接结构

• 一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块
  

  10
  说明：在FCB中我们只需要给出第一块的块号即可。

• 优点

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

• 缺点

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

于是我们可以对此种结构进行某种改造：文件分配表FAT

3.3 文件分配表（FAT）

11
说明：是把所有物理块的表指针都几种存放在一张表中，而不是用一个物理块的一部分来存放指针。从图中可以看到文件A的块号是4，而其下一个物理块的表项为7，最后到值为-1则表示结束。那某文件的起始块号从哪里得到？其实起始块号就记录在了FCB中。这种结构一般用在Windows中。在UNIX中一般采用索引结构。

3.4 索引结构

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

那索引表应该存放在何处？
这里必须知道每个文件的索引表长度是不一样的，于是不能存放在FCB中，因为FCB是固定大小的。于是我们在FCB中只记录索引表的地址。

12
说明：文件B的索引块号是24，索引表是存放在一个物理块中的。索引块中就记录了分配给这个文件的物理块号，可以看到这里我们是可以随机存取的。

• 优点
  保持了链接结构的优点，又解决了其缺点

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

• 缺点

  • 较多的寻道次数和寻道时间
  • 索引表本身带来了系统开销，如：内存、磁盘空间、存取时间

• 组织方式
  问题：索引表很大，需要多个物理块存放时怎么办？

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

• 多级索引与综合模式
  

  13
  说明：图上部分是多级索引模式，此模式中顶级索引表中都记录的是次级索引表地址。而在图下部分则是综合模式，顶级索引表中一部分记录的是直接的物理块，而另一部分是记录的次级索表块地址，即一部分是直接寻址，一部分是间接寻址。

3.5 UNIX的三级索引结构

在UNIX文件系统中采用的是多级索引结构（综合模式）

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

• 问题：采用这种结构，一个文件最大可以达到多少个物理块

  
  14

四、文件系统的实现

4.1 概述

• 实现文件系统需要考虑磁盘上和内存中的内容布局

• 磁盘上
  如何启动操作系统？
  磁盘是怎样管理的？怎样获取磁盘的有关信息？
  目录文件在磁盘上怎么存放？普通文件在磁盘上怎么存放？

• 内存中
  当进程使用文件时，操作系统是如何支持的？
  文件系统的内存数据结构

4.2 相关术语

• 磁盘分区
  把一个物理磁盘的存储空间划分为几个相互独立的部分，称为分区

• 文件卷
  磁盘上的逻辑分区，由一个或多个物理块组成。

  • 一个文件卷可以是整个磁盘或部分磁盘或跨盘（RAID）
  • 同一个文件卷使用同一份管理数据进行文件分配和磁盘空闲空间管理，不同的文件卷中的管理数据是相互独立的。
  • 一个文件卷上包括文件系统信息、一组文件（用户文件、目录文件）、未分配空间
  • 块或簇：一个或多个（2的幂次方）连续的扇区，可寻址数据库

• 格式化
  在一个文件卷上建立文件系统，即建立并初始化用于文件分配和磁盘空闲空间管理的管理数据

4.3 磁盘上的内容

15

• 引导区
  包括了从该卷引导操作系统所需的信息，每个卷（分区）都有一个，通常称为扇区
• 卷信息
  包括该卷的块数、块大小、空闲块数量和指针、空闲FCB数量和指针等等
• 目录文件

4.4 磁盘上文件系统的布局

16

4.5 内存中所需的数据结构（以UNIX为例）

17

五、文件系统实例（UNIX）

5.1 文件目录检索

访问一个文件-->两步骤

• 目录检索
  用户给出文件名-->按文件名查找到目录项/FCB
  根据路径名检索：
  • 全路径名：从根目录开始
  • 相对路径：从当前目录开始
• 文件寻址
  根据目录想/FCB中文件物理地址等信息，计算出文件中任意记录或字符在存储介质上的地址

5.2 目录文件实现时的改进

• 问题：如何加快目录检索？
• 一种解决方案
  目录项分解法：即把FCB分成两部分
  • 符号目录项：文件名，文件号
  • 基本目录项：除文件名外的所有字段
    18
    说明：每个方格表示目录文件（由目录项组成），每个椭圆表示普通文件。如何我们采用目录项分解法，于是符号目录项中的内容就特别简单，此时目录项就变成了符号目录项；基本目录项保存在了磁盘的专用区域。
• 好处
  假设一个FCB占48个字节，物理块大小512字节。符号目录项占8字节（文件名6字节，文件号2字节），基本目录项占48-5 = 42字节。
  这里给出一个目录文件有128个目录项，在分解前则需要13个物理块，分解后符号目录项占2块，基本目录项占11块。总块数是不变的，但是查找一个文件的平均访问磁盘的次数分解前为(1+13)/2=7次，分解后为(1+2)/2 + 1 = 2.5次。于是就提高了文件检索的速度。

六、UNIX文件系统

• FCB= 目录项 +i节点
• 目录项：文件名 +i节点号
• 目录文件由目录项构成
• i节点：描述文件的相关信息
• 每个文件由一个目录项、一个i节点和若干磁盘块构成
  19
  说明：上图是UNIX系统的文件布局。下面看如何查找一个文件
  20
  说明：要查找的文件为/usr/ast/mbox，根目录文件中一个点表示本目录的目录项，两个点表示父目录的目录项，每个目录项都包含文件名和i节点号。从i节点中可以知道这个文件的第一块存放在128这个位置，于是我们读取usr中的内容，从这个目录中去找ast这个文件，以此类推。