第四章 文件管理

4.1 文件系统基础

4.1.1 文件的概念

1.文件的定义

在系统运行时，计算机以进程为基本单位进行资源调度和分配；在用户进行的输入输出中，是以文件为基本单位。

文件系统（File System）在操作系统中供用户实现管理要求。

文件的结构：

1. 数据项：文件系统中最低级的数据组织形式
   • 基本数据项：用于描述对象属性的值。
   • 组合数据项：由多个基本数据组成。
2. 记录：一组相关数据项的集合，描述一个对象在某方面的属性。
3. 文件：创建者定义的一组相关信息的集合。可分为
   • 有结构文件（由一组相似记录组成）
   • 无结构文件（字符流，又称流式文件）

文件并无严格定义，可以是任何内容，访问单元可以是字节、行、记录；

2.文件的属性

根据系统而有所不同，但一般包含：

• 名称：唯一，易读取
• 标识符：表示文件系统内文件的唯一标签，通常为数字，对人不可读
• 类型：被支持不同类型的文件系统使用
• 位置：指向设备和设备上文件的指针
• 大小：当前大小或允许的最大值，常用字节、字、块表示。
• 保护：访问控制信息
• 时间、日期、用户标识

3.文件的基本操作

属于系统调用，对文件进行操作：

• 创建文件（在文件系统找到空间-在目录创建条目）
• 写文件：执行系统调用指明名称和内容，搜索目录。系统必须为此文件维护一个写位置指针，在发生写操作时更新。
• 读文件：执行系统调用指明名称和位置，搜索目录。维护一个读位置指针，在发生操作时更新读指针。
• 文件重定位（文件寻址）：按条件搜索目录，不会读写
• 删除文件：先从目录删除条目，再回首储存空间
• 截断文件：允许文件属性不变并删除内容（将其长度设为0并释放空间，不删除目录项）

4.文件的打开与关闭

许多系统要求在首次使用文件时使用系统调用open，将指定文件的属性（以及物理位置）从外存拷贝到内存中打开文件目录表的一个表中，并且将该项目的索引返回给用户。操作系统维护一个包含所有打开文件信息的表（打开文件表，Open-file Table）。用户需要文件操作时可以直接从该表的索引指定文件，省略了搜索环节。文件不再使用时进程将其关闭，并从打开文件表删除相应条目。

大部分操作系统要求文件在使用之前被显式打开，系统调用open会根据文件名搜索目录并将目录条目复制到打开文件表。如果调用open的请求（创建、只读、读写、添加等）得到允许，进程可以打开文件。open通常返回一个指向打开文件表中一个条目的指针，通过该指针（并非文件名）进行所有IO操作，来简化步骤、节省资源。

open调用完成之后，操作系统对此文件的所有操作都不需要文件名，只需要相应的指针。

因此，进程执行open的实质就是在打开文件表中添加一个条目，并指向整个系统表的相应条目。此外，还有一个文件打开计数器（Open count）来记录打开该文件的进程数目。计数为0时表示文件不被使用，并回收内存资源。若文件被修改过则还需写回外存，并释放文件的文件控制块（FCB，FIle Control Block）。

打开的文件具有以下关联信息（通常在FCB中）：

• 文件指针
• 文件打开计数
• 文件磁盘位置
• 访问权限

4.1.2 文件逻辑结构

文件的逻辑结构：从用户观点看到的文件的组织形式。是从实现观点出发的，又称文件的存储结构。

1. 无结构文件（流式文件）：数据记录并累积、保存，只能穷举搜索
2. 有结构文件
   • 顺序文件：记录按顺序排列，通常记录是定长，以顺序或链表存储，读写记录效率最高，但是查找、增删单个记录比较困难：
     • 串结构：记录之间的顺序和关键字无关，一般由时间先后排列
     • 顺序结构：按关键字排列
   • 索引文件：
     • 定长记录文件：第i项索引*长度；可以直接查找
     • 变长记录文件：前i-1项长度求和+第i项索引，必须顺序查找，可以引入索引表加快检索速度
   • 索引顺序文件：结合二者。索引顺序文件将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。
     • 顺序文件记录的平均查找次数为N/2，若包括了索引文件，假设有sqrt(N)个索引，每个索引指向的组有sqrt(N)个记录，则需要查找：索引平均sqrt(N)/2+组内平均sqrt(N)/2=sqrt(N次，因此大大减小了检查次数。甚至可以用多级索引进一步减小。
   • 直接文件或散列文件（Hash FIle）：给定记录的键值或通过Hash转换的键值直接对应物理地址：存取很快，没有顺序性，但可能会引起冲突。

总之，文件结构都是为了更快查找数据服务的。

4.1.3 目录结构

与文件管理系统和文件集合关联的是文件目录：包含有关文件简单信息（属性、位置、所有权等）

目录管理的基本要求：

• 在用户所需要的文件名和文件之间提供一种映射，因此应该实现“按名存取”
• 效率直接影响系统性能，应该尽量提高目录检索速度
• 共享系统中目录还需控制访问文件的信息。
• 文件应该允许重名：使用树形结构

总之：属于文件之间的“外部”结构

1. 文件控制块和索引结点

1. 文件控制块（FCB）：用来存放控制文件需要的各种信息的数据结构，实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为创建一个新文件，系统会分配一个FCB并存放在文件目录中成为目录项。
   FCB的主要内容：
   • 基本信息
   • 存取控制信息
   • 使用信息（创建时间、修改时间等）
2. 索引节点
   • 检索目录文件时只用文件名，仅当找到一个目录项时（文件名和目录项中的文件名匹配），才需要从该目录项读出文件的物理地址。因此检索目录时不用其他信息，也不调入内存。
   • UNIX等操作系统将文件信息和文件名分开存放，文件信息单独形成称为索引节点的数据结构，简称i结点。此时，文件目录中每个目录项仅由文件名和指向该文件对应的i结点的指针工程。
   • 一个FCB大小为64字节，盘块大小1KB，则每个盘块放入16个FCB（FCB必须连续存放）。而在UNIX中一个目录项仅占16字节，其中14字节是文件名，2字节是i结点指针，节省了系统开销。
   • 存放在磁盘上的索引节点称为磁盘索引节点，主要包括：
     • 文件主标识符
     • 文件类型
     • 文件权限
     • 文件物理地址
     • 文件长度
     • 文件连接计数
     • 文件存取时间
     • 文件被打开时，在内存索引节点增加：索引节点编号、状态、访问计数、逻辑设备号、链接指针。

2. 目录结构

在目录层次的操作有：

• 搜索
• 创建文件
• 删除文件
• 显示目录
• 修改目录

1. 单级目录结构：整个文件系统只建立一张目录表，每个文件占用一个目录项，
   • 访问文件时先按文件名查找FCB。
   • 新建文件时先检索所有目录确保无重名
   • 删除文件时，先找到目录项，回收存储空间再清除目录项
   • 实现了“按名存取”，但是查找慢、不允许重名、不便共享
2. 两级目录结构：将文件目录分为主文件目录（Master File Directory， MFD）、用户文件目录（User File Directory，UFD）
   • 主文件目录项记录用户名和相应用户文件的存储位置，用户文件目录项记录该用户文件的FCB信息。
   • 用户访问文件时，仅需要搜索用户对应的UFD，解决了重名并保证了一定的安全。
   • 缺乏灵活性、不能对文件分类。
3. 多级目录结构（树形目录结构）
   • 用户访问某个文件时用文件的路径名标识文件，路径名是一个由分隔符隔开的各级目录名称组成的字符串
   • 从根目录出发：绝对路径
   • 从当前目录出发：相对路径
   • 每个用户有自己的当前目录，也有系统调用允许用户更改当前目录（cd命令）。
   • 需要各级逐一访问中间节点，增加了磁盘访问速度，且不易共享
4. 无环图目录结构
   在树形目录结构的基础上增加指向同一节点的有向边，使整个目录成为有向无环图，便于文件共享。
   为了保证正常读取共享文件，需要对共享节点增加一个共享计数器，某个用户提出增加对该节点的共享链时计数器+1，用户需要删除时-1，为0时才真正删除该节点，否则仅删除请求用户对该节点的共享链。

4.1.4 文件共享

1.基于索引节点的共享方式（硬链接）

在树形结构目录中，多个用户要求共享一个子目录或文件，必须将共享文件或者子目录连接到多个用户的目录中。

这种方式中引用索引节点（文件物理地址等属性信息），不放在目录项中而是直接放在索引节点中，在文件目录中只设置文件名以及指向相应索引节点的指针。

索引节点中还应有一个链接计数Count表示链接到该索引节点上的用户目录数目。

A创建了一个新文件，则所有者为A，链接计数为1，当B需要共享时，在b的目录创建一个目录项，存放一个指针指向该文件的索引节点，并增加链接计数。

当A删除文件时，由于直接删除会使得B的目录中的指针悬空，因此只应该减小链接计数而不是直接删除，等到链接计数为0才真正删除该文件。

2.符号链接（软连接）

为了用户B共享用户A的文件F，可以由系统创建一个LINK类型的新文件F，将F写入B的目录中，而新文件中只包含对被连接文件F的路径名。称为符号链接或软连接

只有文件拥有者才拥有指向其索引节点的指针。共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引节点的指针，因此不会悬空指针，而所有者A删除后，B依然可以访问新F但是会访问失败。

问题：若在所有者删除后创建了一个同名的F，则旧软连接依然有效，出现不同步的错误。

优点：只需要网络地址和文件路径就可以实现网络共享

软、硬链接的共同问题：每个共享文件都有多个文件名，也就是每增加一个链接，就增加一个文件名，实质上就是每个用户都是用自己的路径名访问共享文件，因此试图遍历文件系统时会多次遍历到该共享文件。

二者都是静态共享方法。除此之外还有动态共享方法。

4.1.5 文件保护

为防止文件共享导致文件被破坏或未经允许的修改，文件系统需要控制读写、执行权限。

文件保护通过口令保护、加密保护、访问控制

1.访问类型

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

此外还有：重命名、复制、编辑的控制。

2.访问控制

最常用的方式是对用户身份进行控制，普遍方式就是巍峨米格文件和目录增加一个访问控制列表（Access Control List，ACL）来规定每个用户名及其允许的访问类型。

优点：可以实现复杂的访问方法
缺点：长度无法预计，可能导致复杂的空间管理

可以使用精简的访问列表解决该问题，包括以下内容：

• 拥有者：创建文件的用户
• 组：一组需要共享文件且有类似访问的用户
• 其他：系统中除了以上二者的所有用户

用三个域列出访问表中这三类用户的访问权限即可。系统在创建文件时将以上信息写入FCB中，访问时按照相应条目确定权限。

口令：建立FCB时提供，并告诉允许共享的其他用户。用户请求访问时必须提供相应口令。口令是直接存在系统中，不够安全。

密码：对文件进行加密，文件被访问时需要秘钥。编码和译码需要一定时间。

4.2 文件系统实现

4.2.1 文件系统层次结构

1. 用户调用接口：为用户提供的文件相关操作如读取、关闭、删除目录等，分别对应一条系统调用。
2. 文件目录系统：管理文件目录，管理活跃文件目录表、读写状态信息表、用户进程的打开文件表、管理和组织设备上的文件目录结构、调用下一级存取控制快。
3. 存取控制验证：对比访问要求和FCB中指示的控制权，确认访问合法性，实现文件保护。
4. 逻辑文件系统、文件信息缓冲区：根据文件逻辑结构将用户要读写的逻辑记录装换为文件逻辑结构内的相应块号。
5. 物理文件系统：把逻辑记录所在的相对块号转为物理地址
6. 分配模块：管理辅存空间，即分配和回收辅存空间
7. 设备管理程序模块：分配设备、设备读写缓冲区、磁盘调度、启动设备、护理中断、释放缓冲区、释放设备

4.2.2 目录实现

打开文件时需要利用路径名找到相应目录项，从其中找到所需信息。

1. 线性列表（对应线性查找）

创建时遍历目录表查找重名，在目录表后增加目录项；删除时搜索目录表释放分配的空间；若要重用，可以标记为不再使用，或者加到空闲目录项表上，或者将目录表最后一个目录项复制到空闲位置并降低目录表长度。也可以使用链表减少增删的开销。

2. 哈希表（散列查找）

根据文件名得到哈希值，返回指向线性列表中元素的指针，查找、插入和删除都很简单，但是需要避免哈希冲突。

4.2.3 文件实现

1.文件分配方式

1. 连续分配
   • 每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上一个线性排序，使得作业访问磁盘需要的寻道次数和寻道时间最小。
   • 可以用第一块的磁盘地址和连续块的数量来定义。如（n,b）代表从b开始连续占有n块。
   • 支持顺序访问和直接访问，实现简单、存取速度快，但文件长度不宜动态增加（容易产生碎片），适合长度固定的文件
2. 链接分配
   • 离散分配，消除了外部碎片，不需要预先知道文件大小，便于增删改。
   • 隐式链接：每个文件对应一个磁盘块的链表，除最后一个块外所有块都具备指向下一个位置的指针（对用户透明），目录包括文件第一块和最后一块的指针。创建新文件时，目录中增加一个新条目，每个目录项都有一个指向文件首块的指针，初始化为NULL，大小为0。系统在运行过程中的指针丢失会导致数据丢失。
   • 显式链接：把放在各个物理块末尾的指针提取出来独立成表（该表在整个磁盘仅有一张）存放在对应块的位置。某一文件的第一个盘块号（每一条链的链首对应的盘块号）填入FCB中。该表被称为文件分配表（File Allocation Table，FAT）。
3. 索引分配
   • 链接分配解决了外部碎片和文件大小，但是除了FAT的链接分配不能有效支持直接访问。索引分配将每个文件的所有盘块号都集中放在一起构成索引块。
   • 每个文件都有索引块，是磁盘块地址的数组。
   • 创建文件时，索引块的所有指针都设为空，首次写入第i块时先从空闲空间取得一个块，再将地址写到索引块第i个条目。
   • 索引分配支持直接访问，没有外部碎片，但索引块过大增加了系统储存空间的开销，索引块过低不支持大空间。解决方案包括：
     • 链接方案：将多个索引块连接起来
     • 多层索引：指向下一层的索引块（每块为4KB，可有1K个4B的指针，指向下一层索引，总共可以支持1K*1K=1M个数据块，允许最大文件为1M*4KB=4GB）
     • 混合索引：结合以上两种。

2.文件存储空间管理

1. 文件存储器空间的划分和初始化。文件存储在文件卷中，每个卷包括各自的目录区（存放FCB）和文件区。逻辑块提供服务前必须提权划分好，建立空闲空间管理表格、存放逻辑卷信息的超级块。
2. 文件存储器空间管理。实质是对空闲块的组织和管理，包括对空闲块的组织、分配、回收。
   • 空闲表法：连续分配方式，类似内存动态分配，表中包含空闲盘块号和相应的空闲盘块数。
   • 空闲链表法：将空闲盘区拉成一条空闲链，根据构成链表的元素不同可分为
     • 空闲盘块链：以盘块为单位拉成链
     • 空闲盘区链：将所有空闲盘区（可有多个盘块）拉成链
   • 位示图法：利用二进制的某位表示磁盘中一个盘块的使用情况。
     分配步骤：
     • ① 顺序扫描位示图，找出一个或一组为0的二进制位
     • ② 将找到的一个或一组为转换为与之对应的盘块号。假定找到的值为0，位于i行j列，则相应盘块号为b=n(i-1)+j。n为每行的位数。
     • ③ 修改位示图，使得map[i,j]=1
       回收步骤：
     • ① 将回收盘块的盘块号转换为i和j（整除、取余）
     • ② map[i,j]=0
   • 成组链接法：空闲表法和空闲链表法的空闲表太大，都不适用于大型文件系统。UNIX利用了成组链接法，把顺序的n个空闲扇区地址保存在第一个空闲扇区内，最后一项指向第二个空闲扇区的首位置；后n个保存在第二个空闲扇区中……则系统只保存指向第一个空闲扇区的指针即可。以上信息都应该放入辅存中的卷头位置，在UNIX称为超级块。

4.3 磁盘组织与管理

4.3.1 磁盘的结构

• 盘片（Platter）
• 磁头（Head），任意时刻所有磁头所处的磁道号相同
• 磁道（Track）：储存数据的同心圆之一
• 扇区（Sector）：磁道中划分的多个固定大小区域
• 盘块：每个扇区称为一个盘块
• 磁道间隙
• 柱面（Cylinder）固定磁头位置的所有磁道形成的圆柱体

CHS：Cylinder、Head、Sector，共同确定硬盘容量。

4.3.2 磁盘调度算法

相关时间：

1. 寻找时间Ts：磁头移动到指定磁道的时间
2. 延迟时间Tr：磁头定位到某磁道扇区的时间
3. 传输时间Tt：读写所需时间，与旋转速度有关

调度算法：

1. 先来先服务FCFS
2. 最短寻找时间优先（Shortest Seek Time First，SSTF）：寻找最近磁道，会产生饥饿
3. 扫描（SCAN）算法（电梯算法）：最近磁道+当前磁头方向，避免饥饿，但两端不公平
4. 循环扫描（Circular SCAN）：总是规定磁头单向移动，循环扫描最近磁道，消除了两端的不公平

4.3.3 磁盘的管理

1.硬盘初始化：

• 首次存储数据之前需要将磁盘分成扇区方便读写：低级格式化（物理分区）。将每个扇区分为头和数据区域、尾部。
• 将操作系统的数据结构记录在磁盘上
  • 1.将磁盘分为多个柱面组成的分区
  • 2.对物理分区进行逻辑格式化（创建文件系统）

2.引导块：

计算机启动需要一个初始化程序（自举程序）初始化CPU、寄存器、设备控制器等信息来启动操作系统，自举程序应该找到磁盘上的操作系统内核来开始操作系统的运行。

自举程序通常保存在ROM（CMOS）中，为避免 改变自举代码需要改变ROM硬件 的问题，只在ROM中保留很小的自举装入程序，将完整的自举程序保存在磁盘的启动块上，启动块在磁盘的固定位置，拥有启动分区的磁盘称为系统磁盘

3.坏块

• 简单磁盘（如电子继承驱动器，IDE，一种ATA）可手动处理坏扇区，如逻辑格式化时在FAT表上标明。
• 复杂磁盘（如小型计算机系统接口，SCSI）：控制器维护一个磁盘坏块链表在使用过程中不断更新。在低级格式化时会流出备用快，在存在坏块时在逻辑上替代坏块：扇区备用