第七章 文件系统
7.1 引言
7.2 文件的组织
7.3 文件目录
7.4 文件和目录的使用
7.5 文件共享
7.6 外存存储空间管理
7.7 文件系统举例信息 是计算机系统中的 重要资源 。操作系统中的一个重要组成部分,文件系统,就负责信息的组织、存储和访问。
文件系统的功能就是提供 高效、快速和方便的信息存储和访问功能 。本章的主要内容就是 信息的组织 。
7.1 引言
7.1.1 文件管理的目的
7.1.2 文件系统的基本概念
7.1.3 文件系统的结构和功能元素返回
7.1.1 文件管理的目的
方便 的文件访问和控制：以符号名称作为文件标识，
便于用户使用；
并发 文件访问和控制：在多道程系统中支持对文件的并发访问和控制；
统一 的用户接口：在不同设备上提供同样的接口，
方便用户操作和编程；
多种文件访问 权限,在多用户系统中的不同用户对同一文件会有不同的访问权限；
优化性能,存储效率、检索性能、读写性能；
差错恢复,能够验证文件的正确性，并具有一定的差错恢复能力；
返回
7.1.2 文件系统的基本概念
文件体,文件本身的信息；
文件说明,文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访问权限、访问时间等；
返回
1,文件文件 是具有 符号名 的 数据项的集合 。 文件名 是文件的标识符号。文件包括两部分：
2,文件系统文件系统是操作系统中 管理文件的机构,提供文件 存储和访问 功能。
3,目录目录是由 文件说明索引 组成的用于 文件检索 的特殊文件 。
7.1.3 文件系统的结构和功能元素返回
1,文件系统的结构应用程序多种文件类型 （划分记录，顺序或索引等）
基本 I / O 管理 （ I / O 缓存和调度，性能优化）
物理 I / O （基本文件系统）
外部存储器文件系统
2,文件管理的服务功能元素
文件访问,文件的创建、打开和关闭，文件的读写；
目录管理,用于文件访问和控制的信息，不包括文件内容
文件结构管理,划分记录，顺序，索引
访问控制,并发访问和用户权限
限额 (quota)：限制每个用户能够建立的文件数目、占用外存空间大小等
审计 (auditing)：记录对指定文件的使用信息（如访问时间和用户等），保存在日志中
(文件系统向上层用户提供的服务 )
3,文件系统的实现功能元素
文件的分块存储,与外存的存储块相配合
I/O缓冲和调度,性能优化
文件定位,在外存上查找文件的各个存储块
外存存储空间管理,如分配和释放。主要针对可改写的外存如磁盘。
外存设备访问和控制,包括由设备驱动程序支持的各种基本文件系统如硬盘，软盘,CD ROM等
(文件系统要实现的功能模块 )
7.2 文件的组织 (file organization)
7.2.1文件的组织
7.2.2 文件的组织类型返回文件组织讨论 文件的内部逻辑结构,主要考虑因素是文件 存储性能 和 访问性能 。
7.2.1文件的组织
文件逻辑结构的设计要求：
– 访问性能：便于检索；便于修改
– 存储性能：向物理存储转换方便，节省空间
文件的不同组织层次：域、记录、文件返回文件的组织是指从 用户观点 出发讨论文件 内部的逻辑结构 (logical structure)或 用户访问模式 ；它可以 独立于在外存上的物理存储 。
7.2.2 文件的组织类型返回
1,无结构文件文件体为 字节流,不划分记录，顺序访问，每次读写访问可以指定任意数据长度。当前操作系统中常用的文件组织。
2,累积文件 (pile)
文件体为 无结构记录序列,通过 特定分隔符 来划分记录，各 记录大小和组成可变 。 新记录总是添加到文件末尾 。如日志 log，或电子邮件的邮箱文件 (mailbox)。
检索必须从头开始 。
3,顺序文件 (sequential file)
文件体为 大小相同 的 排序 记录序列。它由一个 主文件和一个 临时文件 组成。记录大小相同，按某个关键字域 (key field)排序，存放在主文件 (master file)中。 新记录 暂时保存在日志或事务文件 (log file or transaction
file)中,定期归并 入主文件。
4,索引顺序文件 (indexed-sequential file)
在索引文件中，可 将关键字域中的取值划分若干个区间 （如
A~Z可以划分为 A到 Z共 26个区间），每个区间对应一个索引项，后者指向该区间的开头记录。 新记录 暂时保存在溢出文件中，定期归并入主文件。
通过划分层次，在记录数量较大时，比顺序文件大大缩短检索时间。 顺序文件是 N/2(这时可使用折半查找 )，而索引顺序文件（ 一级索引 ）是 i/2 + N/(2*i)，其中 i为索引长度。索引还可以是 多级 的。如：有 1000,000条记录的顺序文件的平均检索长度为 500,000，而在添加一个有 1000条索引项的索引文件后，平均检索长度为 1000。
在顺序文件（主文件 main file）的基础上，另外建立 索引 (index)和 溢出文件 (overflow file)。这样做的目的是加快顺序文件的 检索速度 。
关键字 逻辑地址姓名 其它属性
A
B
Z
An Bing
An Kang
An Qing
Bao Rong
Bi Jing
Bon Long
索引文件顺序文件索引顺序文件
5,索引文件 (indexed file)
记录大小不必相同,不必排序,存放在主文件
(primary file)中。索引文件与索引顺序文件的区别在于主文件不排序。另外建立索引,每个索引项指向一个记录,索引项按照记录中的某个关键字域排序。对同一主文件，可以针对不同的关键字域相应建立 多个索引 。索引文件的记录项通常较小,查找速度快,便于随机访问 (random access)。
6,哈希文件或直接文件 (hashed file or direct file)
记录大小相同。由主文件和溢出文件组成。 记录位置由哈希函数确定。 检索时给出记录编号，通过哈希函数计算出该记录在文件中的相对位置。 访问速度快,
但在 主文件中有空闲空间 。
7.3 文件目录
7.3.1 目录内容
7.3.2 目录结构类型
7.3.3 文件别名的实现返回目录是由 文件说明索引 组成的 用于文件检索 的特殊文件。文件目录的内容主要是 文件访问的控制信息 （不包括文件内容）。
7.3.1 目录内容
文件名,字符串，通常在不同系统中允许不同的最大长度。可以修改。有些系统允许同一个文件有多个别名 (alias)；
别名的数目；
文件类型,可有多种不同的划分方法，如：
– 有无结构（记录文件，流式文件）
– 内容（二进制，文本）
– 用途（源代码，目标代码，可执行文件，数据）
– 属性 attribute（如系统，隐含等）
– 文件组织（如顺序，索引等） 返回目录的内容是 文件属性信息 (properties)，其中的一 部分 是 用户可获取 的。
1,基本信息
2,地址信息
存放位置,包括哪个设备或文件卷 volume，以及各个存储块位置；
文件长度 （当前和上限）：以字节、字或存储块为单位。可以通过写入或创建、打开、关闭等操作而变化。
3,访问控制信息
文件所有者（属主）,通常是创建文件的用户，
或者改变已有文件的属主；
访问权限 （控制各用户可使用的访问方式）：如读、写、执行、删除等；
4,使用信息
创建时间
最后一次读访问的时间和用户
最后一次写访问的时间和用户
7.3.2 目录结构类型
一级目录,整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。它具有如下的特点：
– 结构简单；
– 文件多时，目录检索时间长；
– 有命名冲突：如重名 (多个文件有相同的文件名 ) 或别名 (一个文件有多个不同的文件名 )
二级目录,在根目录下，每个用户对应一个目录
（第二级目录）；在用户目录下是该用户的文件，
而不再有下级目录。适用于多用户系统，各用户可有自己的专用目录。
返回目录结构讨论目录的组织结构，设计目标是检索效率。
多级目录,或称为树状目录 (tree-like)。在文件数目较多时，便于系统和用户将文件分散管理。
适用于 较大的文件系统 管理。目录级别太多时，
会增加路径 检索时间 。
– 目录名,可以修改。
– 目录树,中间结点是目录，叶子结点是目录或文件。
– 目录的上下级关系,当前目录 (current directory,
working directory),父目录 (parent directory),子目录 (subdirectory),根目录 (root directory)等；
– 路径 (path)：每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示；
A B C根目录
E P
A B D F E D B G A E
H I J K A B C
D E
L M N A
多级目录组织
改进的多级目录,为了提高 目录检索速度,
可把目录中的文件说明（文件描述符）信息分成两个部分：
– 符号文件目录,由 文件名 和 文件内部标识 组成的树状结构，按文件名排序；
– 基本文件目录 （索引节点目录）：由 其余文件说明信息 组成的 线性结构,按文件内部标识排序；
1
内部名
ID
其它信息 地址
2
3
4
5
6
7
8
9
10
11
基本文件目录( I D 1 )
ID4
ID5
ID7
ID9
ID10
ID11
文件名 ID
3Tu-Lide
8Tu-Qi
根目录( I D 2 )
文件名 ID
7Products
5Rooms
Tu-Lide的 目录(ID3)
4Software
6Tools
文件名 ID
T o o l s 的目录( I D 6 )
11SA-SD
10Univer
文件名 ID
10Univer
5Classroom
Tu-Lide的 目录(ID3)
9Tools
基本文件目录
Tu-Lide的 目录(ID3)
Products RoomsSoftware Tools
根目录( I D 2 )
Tu-Lide Tu-Qi
Tu-Lide的 目录(ID8)
Univer ClassroomTools
T o o l s 的目录( I D 6 )
SA-SDUniverID4 ID5ID7 ID9
ID10ID11
符号文件目录的层次结构
7.3.3 文件别名的实现
基于索引结点
基于符号链接返回提供文件共享的方法有两种：各用户通过唯一的共享文件的 路径名 访问共享文件（该方法的访问 速度慢,适用于不经常访问的文件共享），或利用多个目录中的不同文件名来描述同一共享文件（即 文件别名,该方法的访问 速度快,但会 影响文件系统的树状结构,适用于经常访问的文件共享，同时 存在一定的限制 ）。文件别名的实现方法有以下两种：
1,基于索引结点 (index node)的文件别名
UNIX举例,"ln source target ; rm source"则该文件还存在，文件名为 target；
限制：不能跨越不同文件卷；通常不适用于目录（在
UNIX中只对超级用户允许），否则由树状变为网状。
也称为硬链接（ hard link）；基于改进的多级目录结构,将目录内容分为两部分：文件名和索引结点 。前者包括文件名和索引结点编号，后者包括文件的其他内容（包括属主和访问权限）。通过 多个文件名链接
(link)到同一个索引结点,可建立同一个文件的 多个彼此平等的别名 。别名的数目记录在索引结点的链接计数中，若其减至 0，则文件被删除。
2,基于符号链接 (symbolic link,shortcut)的文件别名
UNIX举例,"ln -s a b ; rm a"则文件 a不存在,b
能被控制但无法访问。若 a是目录,"ln -s
/user/a /tmp/b"则 "cd /tmp/b ; cd,."是进入目录
"/user"而不是 "/tmp"；
缺点：空间和时间开销更大。如果设置不当，
上下级目录关系可能会形成环状。
它是一种 特殊类型的文件,其内容是 到另一个目录或文件路径的链接 。建立符号链接文件，并 不影响原文件,实际上它们各是一个文件。可以建立任意的别名关系，甚至原文件是在其他计算机上。
7.4 文件和目录的使用
7.4.1 文件访问
7.4.2 文件控制
7.4.3 目录管理
7.4.4 伪文件 (pseudo file)
返回这一部分讨论操作系统提供的与文件系统相关的 API。
7.4.1 文件访问
打开 open：为文件读写所进行的准备。给出文件路径，
获得文件句柄 (file handle)，或文件描述符 (file
descriptor)。需将该文件的目录项读入到内存中。
关闭 close：释放文件描述符，把该文件在内存缓冲区的内容更新到外存上。
复制文件句柄 dup：用于子进程与父进程间的文件共享，复制前后的文件句柄有相同的文件名、文件指针和访问权限；
返回文件访问是指围绕文件内容读写进行的文件操作。
读 read,写 write和 移动文件读写指针 lseek：系统为每个打开文件维护一个读写指针 (read-write pointer)，它是相对于文件开头的偏移地址 (offset)。读写指针指向每次文件读写的开始位置，在每次读写完成后，读写指针按照读写的数据量自动后移相应数值。
执行 exec：执行一个可执行文件；
修改文件的访问模式 （ fcntl和 ioctl）：提供对打开文件的控制，如：文件句柄复制、读写文件句柄标志、
读写文件状态标志、文件锁定控制、流（ stream）的控制；
7.4.2 文件控制
创建 （ creat和 open）：给出文件路径，获得新文件的文件句柄；
删除 unlink：对于 symbolic link和 hard link，删除效果是不同的；
获取文件属性 （ stat和 fstat）,stat的参数为文件名,fstat的参数为文件句柄；
修改文件名 rename；
修改文件属主 chown,修改访问权限 chmod：与相应系统命令类似；
文件别名控制,创建 symlink或 link，读取链接路径 readlink； 返回文件控制是指围绕文件属性控制进行的文件操作。
7.4.3 目录管理
进行文件访问和控制时，由操作系统 自动更新目录内容
目录创建 mkdir,删除 rmdir,修改目录名
rename。只适用于超级用户,mknod（ 建立文件目录项 ）和 unlink（ 删除目录项 ）
修改当前目录 chdir；
返回目录管理是指目录访问和目录属性控制。
7.4.4 伪文件 (pseudo file)
特点
– 内容 并不保存在外存上，而是 在其他外部设备上或内存里
– 随文件类型的不同,适用于某些文件访问和控制的系统调用,
如,open,read,write,close,chmod,chown。
– 创建时使用特定的系统调用,如：创建管道 pipe，创建管套
socket，创建设备文件 mknod
类型
– 设备,字符设备或块设备,可以直接访问设备中的字节数据或数据块。如终端、硬盘、内存等。在 UNIX中称为特殊文件 (special file)。
– 进程间通信,本计算机或通过网络。如：管道，管套等。
返回伪文件是指具有文件某些特征的系统资源或设备，它们的访问和控制方式与文件类似。
7.5 文件共享
7.5.1 文件的访问权限
7.5.2 文件的并发访问返回
7.5.1 文件的访问权限
文件访问类型,
– 读 read：可读出文件内容；
– 写 write（修改 update或添加 append）：可把数据写入文件；
– 执行 execute：可由系统读出文件内容，作为代码执行；
– 删除 delete：可删除文件；
– 修改访问权限 change protection：修改文件属主或访问权限返回设置文件访问权限的目的是为了在多个用户间提供 有效的 文件 共享机制 ；
用户范围类型,
– 指定用户
– 用户组
– 任意用户
访问类型和用户范围的组合,
– 访问矩阵,矩阵的一维是每个目录和文件，另一维是用户范围，每个元素是允许的访问方式
– 访问策略 (policy)：每种文件访问方式，所允许或禁止的用户范围。可以将文件访问方式推广到其他操作如用户管理，备份，网络访问等。
7.5.2 文件的并发访问
访问文件之前，必须先打开文件：如果文件的 目录内容 不在内存，则将其从外存读入，否则，仍使用已在内存的目录内容。这样，多个进程访问同一个文件都使用内存中同一个目录内容，保证了文件系统的一致性。
文件锁定 (file lock)：可以协调对文件指定区域的互斥访问
– Solaris 2.3中 lockf的锁定方式：
F_UNLOCK：取消锁定；
F_LOCK：锁定；如果已被锁定，则阻塞；
F_TLOCK：锁定；如果已被锁定，则失败返回
F_TEST：锁定测试；
利用 进程间通信,协调对文件的访问；
返回文件并发访问控制的目的是提供多个进程 并发访问 同一文件的机制。
7.6 外存存储空间管理
7.6.1 文件存储空间分配 (file
allocation)
7.6.2 外存空闲空间管理 方法
(free space management)
7.6.3 文件卷返回讨论如何高效地进行数据存储
7.6.1 文件存储空间分配 (file allocation)
预分配 (preallocation)：创建时 (这时已知文件长度 )一次分配指定的存储空间，如文件复制时的目标文件。
动态分配 (dynamic allocation)：需要存储空间时才分配（创建时无法确定文件长度），
如写入数据到文件。
返回
1,新创建文件的存储空间（文件长度）分配方法
2,文件存储单位：簇（ cluster）
簇的大小
– 两个极端,大到能容纳整个文件，小到一个外存存储块；
– 簇较大,提高 I/O访问性能,减小 管理开销 ；
但 簇内碎片浪费 问题较严重；
– 簇较小,簇内的碎片浪费较小，特别是 大量小文件 时有利；但存在 簇编号空间不够 的问题（如 FAT12,16,32）；
文件的存储空间通常由多个分立的 簇 组成，而每个簇包含若干个 连续的扇区 (sector)。
簇的分配方法：两种
– 簇大小可变，其上限较大,I/O访问性能较好，文件存储空间的管理困难（类似于动态分区存储管理）
– 簇大小固定，较小：文件存储空间使用灵活，但
I/O访问性能下降，文件管理所需空间开销较大
文件巻容量与簇大小的关系
– 文件卷容量越大，若簇的总数保持不变即簇编号所需位数保持不变，则簇越大。缺点：簇内碎片浪费越多
– 文件卷容量越大，若簇大小不变，则簇总数越多，
相应簇编号所需位数越多。如簇编号长度为 12、
16,32二进制位，即构成 FAT12,FAT16,FAT32。
3,文件存储分配数据结构
连续分配 (contiguous)：只需记录 第一个簇的位置,
适用于预分配方法。可以通过紧缩 (compact)将外存空闲空间合并成连续的区域。
链式分配 (chained)：在每个簇中有 指向下一个簇的指针 。可以通过合并 (consolidation)将一个文件的各个簇连续存放，以提高 I/O访问性能。
索引分配 (indexed)：文件的第一个簇中记录了该文件的 其他簇的位置 。可以每处存放一个簇或连续多个簇（只需在索引中记录连续簇的数目）。
采用怎样的数据结构来记录一个 文件的各个部分的位置 。
7.6.2 外存空闲空间管理 (free space management)方法
位示图 (bitmap)：每一位表示一个簇，取值 0和 1分别表示空闲和占用。
空闲空间链接 (chained free space)：每个空闲簇中有指向下一个空闲簇的指针，所有空闲簇构成一个链表。不需要磁盘分配表，节省空间。每次申请空闲簇只需取出链表开头的空闲簇即可。
空闲空间索引 (indexed free space)：在一个空闲簇中记录其他几个空闲簇的位置。
返回外存空闲空间管理的数据结构通常称为 磁盘分配表
(disk allocation table)，分配的基本单位是簇。 文件系统可靠性 包括检错和差错恢复。空闲空间的管理方法：
三种，均适用于上述几种文件存储分配数据结构；
注：可以上述方法结合，应用于不同的场合。如,位示图 应用于索引结点表格,链接和索引 结合应用于文件区的空闲空间。
7.6.3 文件卷
磁盘分区 (partition)：通常把一个 物理磁盘 的存储空间划分为几个相互独立的部分，称为 "分区 "。一个分区的参数包括,磁盘参数 （如每道扇区数和磁头数）,分区的起始和结束柱面 等。
文件卷 (volume)：或称为 "逻辑驱动器 (logical drive)"。
在同一个文件卷中 使用同一份管理数据 进行文件 分配和外存空闲空间管理,而在不同的文件卷中使用相互独立的管理数据。
– 一个文件不能分散存放在多个文件卷中,其最大长度不超过所在文件卷的容量。
– 通常一个 文件卷只能存放在一个物理外设上 （并不绝对），
如一个磁盘分区或一盘磁带。
返回
格式化 (format)：在一个文件卷上 建立文件系统,即：
– 建立并初始化 用于进行文件分配和外存空闲空间管理的 管理数据 。
– 通常，进行格式化操作使得一个文件卷上 原有的文件都被删除 。
扩展文件卷集 (extended volume set)：一个文件卷由一个或几个磁盘上的 多个磁盘分区 依次连接组成。可以容纳长度大于磁盘分区容量的文件。
– 实例,Windows NT中的扩展文件卷集。
磁盘交叉存储 (disk interleaving),将一个文件卷的存储块依次分散在多个磁盘上 。如 4个磁盘，则磁盘 0
上是文件卷块 0,4,8,…,磁盘 1上是文件卷块 1,5,
9,… 。
– 优点,提高 I/O效率 。如果需要访问一个文件的多个存储块，而它们分散在多个磁盘上，则可以 并发地向多个磁盘发出请求,并可在此基础上提供文件系统的 容错功能 。关键,磁盘访问时间大部分由旋转等待时间组成 。
– 需要相应硬件设备：如多个硬盘连接在同一个或不同的
SCSI接口上，或者两个硬盘连接在一个或不同的 IDE接口上（两个硬盘连接在同一个 IDE接口上，不能提高 I/O效率）
– 实例,Windows NT中的 条带卷 (stripe set)，每个文件卷块的大小是 64KB。
– 类似例子：在虚拟存储器中建立 多个交换区,分散在多个磁盘上
D i sk 0
D i sk 1
D i sk 2
D i sk 3
C y cl i ng W ai t
D at a T r ans f er
t
R eques t C om pl et e
多个磁盘上的交换区访问
7.7 文件系统举例
7.7.1 MS DOS的文件系统
7.7.2 Windows NT的文件系统
7.7.3 UNIX的文件系统返回
7.7.1 MS DOS的文件系统返回多级目录，不支持文件别名，无用户访问权限控制
1,磁盘文件卷结构
F A T 1 F A T 2 Roo t
Di r ec t or y
Dat a
( F i l e & Di r ec t or y )
Boo t
Rec or d
V ol um e S t ru ct ur e i n M S DO S
Se ct or # 0 N1 2N
文件卷 (volume)信息：记录在 引导记录的扇区中。包括：簇大小，根目录项数目,FAT表大小，磁盘参数（每道扇区数，磁头数），文件卷中的扇区总数，簇编号长度等
– 逻辑扇区号,三元组（柱面号，磁头号，扇区号）
－ >一个文件卷中从 0开始对每个扇区编号，优点：
屏蔽了物理磁盘参数的不同
– 允许 同时访问的文件卷数目上限 可以由 config.sys
文件中的 LASTDRIVE= 语句指定
– 簇 (cluster)：由若干个扇区组成。在一个文件卷中从 0开始对每个簇编号。
每个 FAT表项所占位数是 簇编号 的位数，其值是
（以 FAT12为例）：
– 0：表示该簇空闲
– FF7h：物理坏扇区
– FF8h~FFFh：表示该簇是文件的最后一个簇
– 其他值：表示该簇被文件占用，而且表项中的值是文件下一个簇的编号。
FAT表,两个镜像，互为备份。文件卷中的每个簇均对应一个 FAT表项，文件分配采用链式分配方法。
目录：是目录项的顺序文件 (即大小相同的排序记录序列 )，不对目录项排序。
– 若目录中包含的文件数目较多，则搜索效率低。
– 每个目录项大小为 32字节，其内容包括：文件名（ 8+3个字符），属性（包括文件、子目录和文件卷标识），最后一次修改时间和日期，文件长度，第一个簇的编号。
– 在目录项中，若第一个字节为 E5h，则表示空目录项；若为 05h，则表示文件名的第一个字符为 E5h。
– 文件名不区分大小写
823h
800h
...
F A T
850h
823h
..,800hF F 8h
850h
...
Di r Ent r y
F i l e1
...
2,打开文件管理
系统文件表 (SFT,System File Table)和 任务文件表 (JFT,Job File Table)：
– SFT包含 系统的所有打开文件,可以由几个表项依次连接组成。
– JFT包含 该任务（进程）的所有打开文件 。 JFT表项内容是 到 SFT表项的索引 。
– SFT的表项数目 可由 config.sys文件中的 FILES=
来语句指定，默认是 8。
7.7.2 Windows NT的文件系统
NTFS为改进的多级目录结构，支持文件别名（符号链接方式）；
NTFS文件由多个文件属性构成，每个属性由属性名和属性流（ stream,简单字节队列）组成；用户可自定义属性；
NTFS支持用户权限管理：
– 有 5种权限划分：读、写、运行、删除和修改权限；
– 支持按用户、用户组分配权限；
NTFS文件支持数据压缩功能；
NTFS卷结构支持容错功能；
返回
1,概述
2,Windows NT的文件系统结构远程文件操作过程
3,与文件系统相关的数据结构
4,NTFS卷结构
NTFS的结构以卷为单位,卷与磁盘分区相关；卷由一组文件和未分配空间组成；
NTFS以簇为基本硬盘分配单位,簇的大小为物理扇区的整数倍，通常为 2K倍。
NTFS卷上的所有数据（包括用于引导、定位、空间分配等文件系统管理数据）都以 文件 的形式保存；
文件引用号,在主文件表中每个文件记录有一个 64
位的文件引用号；它由文件号和顺序号组成，文件号（ 48位,47~0）是文件在主文件表中的位置序号，
顺序号（ 16位,63~48）在每次重复使用该文件记录时加 1；
NTFS的元文件
主文件表 （ $MFT）：文件记录数组，每个记录为
1KB；每个文件对应一个或多个文件记录；
主文件表副本 （ $MFTMirr）：是主文件表中前几项的副本，用于在主文件表不能读取时的元文件定位；
卷结构日志 （ $LogFile）：记录所有影响 NTFS卷结构的操作，用于系统失败后的卷恢复；
空间分配位图 （ $Bitmap）：标识卷中每个簇的分配状态，即：空闲和已被分配；
引导文件 （ $Boot）：引导程序代码；
坏簇文件 （ $BadClus）：记录卷中据有损坏位置；
卷文件 （ $Volume）：卷名、文件系统版本、卷状态
（卷是否被损坏）；
属性定义表 （ $AttrDef）：卷中支持的属性类型列表；
5,NTFS文件属性
NTFS文件是属性的集合,通常所说的文件内容是指未命名数据属性流；
例：我们定义两个数据属性,ntfile(数据 )和 ntfile:data(自定义数据 )。在向 FAT复制时，自定义属性会丢失。
echo test....data >ntfile
echo test....user defined data >ntfile:data
more <ntfile
more <ntfile:data
copy ntfile h:ntfile (H为 NTFS)
copy ntfile f:ntfile (F为 FAT)
more <h:ntfile
more <h:ntfile:data
more <f:ntfile
more <f:ntfile:data
NTFS文件属性的存储形式
常驻属性 （ Resident Attribute）：属性流直接存放在主文件表中；标准信息和文件名总是常驻的。
非常驻属性 （ Nonresident Attribute）：属性流的存放不在主文件表中；大文件的数据属性、大目录的文件名索引属性等长度可增加的属性为非常驻的。
常驻属性非常驻属性
NTFS文件结构
NTFS目录结构
6,NTFS的数据压缩
稀疏文件压缩,稀疏文件是指相对于文件大小而言只有少量非零数据的文件。压缩方法为省略（不保存）只包含零的簇。
非稀疏文件压缩,NTFS首先把文件分成 16个簇为一组的压缩单位；分别对各压缩单位进行压缩，当压缩后不能节约一个簇时，不压缩而直接存储；当压缩后可节约至少一个簇时，只分配相应空间，存储压缩后的数据。
NTFS支持基于文件、目录和卷的压缩。
稀疏文件压缩非稀疏文件压缩
7,NTFS卷结构
卷集,是由 1到 32个硬盘分区构成的单一文件卷，可在不影响已存储数据的条件下把一个硬盘分区增加到卷集中。
可用于,合并多个小硬盘分区,形成跨越多个小硬盘的更大卷；动态增加卷的大小。
通常一个文件卷与一个硬盘分区相对应，但 NTFS支持由多个硬盘分区构成的文件卷,以提高文件 I/O效率,
提供 动态增加卷大小 和 容错 功能。
Span
Span
Span
Span
C:
20 0 MB
D:
10 0 MB
G:
50 MB
Disk 0
E:
10 0 MB
F:
12 5 MB
G:
25 0 MB
Disk 1
E:
50 MB
F:
20 0 MB
G:
12 5 MB
Disk 2
Tota l Size
C,20 0 MB
D,10 0 MB
E,15 0 MB
F,32 5 MB
G,42 5 MB
条带卷,由 2个以上的分布在不同物理硬盘上的大小相同的分区，
以 64KB大小的条带为单位组合成的文件卷。条带卷可 使数据在硬盘间的分布趋于平均,通过多个并行的硬盘
I/O来提高文件
I/O速度。
Strip e 1
Strip e 4
Strip e 7
Strip e 1 0
Disk 0
Strip e 2
Strip e 5
Strip e 8
Strip e 1 1
Disk 1
Strip e 3
Strip e 6
Strip e 9
Strip e 1 2
Disk 2
镜像卷：由 2个分布在 不同物理硬盘上的大小相同的分区,通过完全复制构成的单一文件卷。镜像卷有一半的空间用于冗余数据存储。可用于：数据的 冗余存储,当数据不可读时，自动从镜像分区中读取；通过 平衡读取操作 来提高文件读取效率。
Duplex
C,FA T
20 0 MB
D,NT FS
10 0 MB
E,N TFS
12 5 MB
Disk 0
C,FA T
20 0 MB
D,NT FS
10 0 MB
F,FA T
30 0 MB
Disk 1
带校验的条带卷：
由 3个以上 的分布在不同物理硬盘上的 大小相同 的分区，以 64KB大小的条带为单位组合成的带校验的文件卷。由 N个分区构成的带校验条带卷有 1/N的空间用于冗余数据存储,可恢复一个条带的错误。
可用于：数据的冗余存储 (容错 )；
提高文件 I/O速度 。
Stripe 1
Pa rity
Stripe 5
Stripe 7
Disk 0
Stripe 2
Stripe 3
Pa rity
Stripe 8
Disk 1
Pa rity
Stripe 4
Stripe 6
Pa rity
Disk 2
7.7.3 UNIX的文件系统
改进的多级文件目录,可以建立 文件别名 （索引结点方式和符号链接方式），有 用户访问权限控制
（文件的读 R、写 W和执行 X，相应于目录的检索文件、增删文件和进入目录）
– 注意：如果对文件具有写权限，而对文件所在目录没有写权限，仍然可以改变该文件的长度（如添加数据），因为除文件名外的其他文件目录内容都存放在索引结点而不是在目录文件。
文件类型,常规文件 (ordinary file)、目录文件
(directory)、特殊文件 (special file)如外设、先进先出文件 (FIFO)如命名管道；
返回
1,概述
2,磁盘文件卷结构
超级块,描述文件系统的状态，包括磁盘空闲块栈，
空闲 i结点栈
i节点 （ inode list）：存放文件说明信息，每项 64字节
目录文件,每个目录项 16字节。文件名区分大小写。
文件分配,直接索引，一级、二级、三级间接索引
i n o d e
T a b l e
Da t a
( F i l e & Di r e c t o r y )
Bo o t
Re c o r d
V o l um e S t r uc t ur e i n U NI X
Se c t o r # 0 1
Super
Bl o c k
3,空闲 i结点的分配和释放
每次从磁盘上寻找一批空闲 i结点，把它们的编号记录在 内存的空闲 i结点栈 中。其中,铭记” i结点
(remembered inode)是栈中编号最大的 i结点。
i结点分配 时，移出栈顶的 i结点。若到达 "铭记 "i结点则表示栈已空，需要从磁盘上重新寻找。 (铭记 i
结点在栈底 )
652,.,f r ee i nod es
0 1
571 566 em pt y
4922
i nde xr em e m ber ed i nod e
as s i gn i nod e f r ee i nod e
I node L i s t i n S u per B l ock
i结点释放 时，若栈未满，则把被释放 i结点放入栈顶。
若栈已满，则判断被释放 i结点的编号小于 "铭记 "i结点编号，则把前者替换 "铭记 "i结点，否则被释放的 i结点不入栈。
问题举例：这里的问题出在内存中的 i结点栈与磁盘上的状态不一致。如：分配空闲 i结点 100和 150；释放 i结点 100而“铭记” i结点变为 100；分配 i结点 100，则需要重新从磁盘上寻找空闲 i结点；此时 i结点 150还在内存 i
结点表中，如果它尚未更新到磁盘上，那么从磁盘上会找到空闲的 i结点 150。 (由于内外存不同步而产生问题，
内存已分配而外存没有反映出来 )
问题的解决：从空闲 i结点栈中得到 i结点编号之后，还需要对其在内存 i结点表中进行查找 (相当于进行核对 )；
如果找到，说明这个 i结点并非空闲。
4,磁盘空闲块的分配和释放
采用成组链接法,把链表和索引相结合。每一组 50块，用 索引表 表示；各组间通过链表指针串在一起，构成 链表 。链表的开头是超级块中的磁盘空闲块栈，在运行时被读入到内存中。 栈计数 count是栈中的空闲块数目，栈中的元素是空闲块编号。链表中的每一块都存放一个类似的空闲块栈
分配过程,查看超级块中是否 count == 1；若不是，则弹出栈顶元素 N,--count；若是，则弹出栈顶元素 N，把空闲块 N中的栈（包括栈计数）读入到超级块中；返回空闲块编号 N
释放过程,被释放空闲块为编号 N。查看超级块中是否栈已满（如 count == 50）；若不是，则 N入栈,++count；若是，
则将超级块中的栈（包括栈计数）写入到空闲块 N，然后把 N
放入超级块中的栈顶并置 count为 1。
41
350
187
Sup er Bl oc k
count
50
0
40
400
351
...,..
0
49
count 50
450
401
...
0
49
count 46
0
...
...
0
45
count
#350 #400 L as t O ne
...
成组链接
6,打开文件管理
...
5
...
9
U s er Fi l e D es cr i pt ors Fi l e T abl e
5
0
0
...
8
...
6
0
P r o ce s s A
P r o ce s s C
O f f s et
7 8
dup ( )
...
5
...
9
0
P r o ce s s B 8
2 3193 r
2 5609 rw
Count Read/ W r i t e
Mo de
./ f i l e1
F i l e Si ze
I node T abl e
81234
Count
f or k( )
内存 i结点表,空闲的内存 i结点－ >组织成链表；占用的内存 i结点－ >哈希表（对冲突采用链表方式解决）
进程所进入的目录,包括各个打开文件的目录路径，
以及进程的当前目录
– 进入一个目录，如果该目录文件的内存 i结点已经存在，则只需把内存 i结点的引用计数加 1，否则读入该目录文件的磁盘 i结点并建立内存 i结点。
– 系统起动之后，进入根目录并建立相应内存 i结点，直到系统关闭
– 退出目录：如关闭文件或修改当前目录
目录路径查找,把目录路径分解为各级目录名，然后逐级进入目录并查找。如：目录路径为 /usr/include/sys，
则各级目录名为 usr,include,sys。
安装和拆卸文件卷,mount和 umount
小结
文件管理的目的，文件系统结构和功能元素
文件的组织
文件目录
文件和目录的使用
文件共享
外存存储空间管理：文件分配，空闲空间管理，文件卷
举例,MS DOS,Windows NT,UNIX
作业
文件系统的系统调用实现
实现多级目录文件系统实验四
7.1 引言
7.2 文件的组织
7.3 文件目录
7.4 文件和目录的使用
7.5 文件共享
7.6 外存存储空间管理
7.7 文件系统举例信息 是计算机系统中的 重要资源 。操作系统中的一个重要组成部分,文件系统,就负责信息的组织、存储和访问。
文件系统的功能就是提供 高效、快速和方便的信息存储和访问功能 。本章的主要内容就是 信息的组织 。
7.1 引言
7.1.1 文件管理的目的
7.1.2 文件系统的基本概念
7.1.3 文件系统的结构和功能元素返回
7.1.1 文件管理的目的
方便 的文件访问和控制：以符号名称作为文件标识，
便于用户使用；
并发 文件访问和控制：在多道程系统中支持对文件的并发访问和控制；
统一 的用户接口：在不同设备上提供同样的接口，
方便用户操作和编程；
多种文件访问 权限,在多用户系统中的不同用户对同一文件会有不同的访问权限；
优化性能,存储效率、检索性能、读写性能；
差错恢复,能够验证文件的正确性，并具有一定的差错恢复能力；
返回
7.1.2 文件系统的基本概念
文件体,文件本身的信息；
文件说明,文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访问权限、访问时间等；
返回
1,文件文件 是具有 符号名 的 数据项的集合 。 文件名 是文件的标识符号。文件包括两部分：
2,文件系统文件系统是操作系统中 管理文件的机构,提供文件 存储和访问 功能。
3,目录目录是由 文件说明索引 组成的用于 文件检索 的特殊文件 。
7.1.3 文件系统的结构和功能元素返回
1,文件系统的结构应用程序多种文件类型 （划分记录，顺序或索引等）
基本 I / O 管理 （ I / O 缓存和调度，性能优化）
物理 I / O （基本文件系统）
外部存储器文件系统
2,文件管理的服务功能元素
文件访问,文件的创建、打开和关闭，文件的读写；
目录管理,用于文件访问和控制的信息，不包括文件内容
文件结构管理,划分记录，顺序，索引
访问控制,并发访问和用户权限
限额 (quota)：限制每个用户能够建立的文件数目、占用外存空间大小等
审计 (auditing)：记录对指定文件的使用信息（如访问时间和用户等），保存在日志中
(文件系统向上层用户提供的服务 )
3,文件系统的实现功能元素
文件的分块存储,与外存的存储块相配合
I/O缓冲和调度,性能优化
文件定位,在外存上查找文件的各个存储块
外存存储空间管理,如分配和释放。主要针对可改写的外存如磁盘。
外存设备访问和控制,包括由设备驱动程序支持的各种基本文件系统如硬盘，软盘,CD ROM等
(文件系统要实现的功能模块 )
7.2 文件的组织 (file organization)
7.2.1文件的组织
7.2.2 文件的组织类型返回文件组织讨论 文件的内部逻辑结构,主要考虑因素是文件 存储性能 和 访问性能 。
7.2.1文件的组织
文件逻辑结构的设计要求：
– 访问性能：便于检索；便于修改
– 存储性能：向物理存储转换方便，节省空间
文件的不同组织层次：域、记录、文件返回文件的组织是指从 用户观点 出发讨论文件 内部的逻辑结构 (logical structure)或 用户访问模式 ；它可以 独立于在外存上的物理存储 。
7.2.2 文件的组织类型返回
1,无结构文件文件体为 字节流,不划分记录，顺序访问，每次读写访问可以指定任意数据长度。当前操作系统中常用的文件组织。
2,累积文件 (pile)
文件体为 无结构记录序列,通过 特定分隔符 来划分记录，各 记录大小和组成可变 。 新记录总是添加到文件末尾 。如日志 log，或电子邮件的邮箱文件 (mailbox)。
检索必须从头开始 。
3,顺序文件 (sequential file)
文件体为 大小相同 的 排序 记录序列。它由一个 主文件和一个 临时文件 组成。记录大小相同，按某个关键字域 (key field)排序，存放在主文件 (master file)中。 新记录 暂时保存在日志或事务文件 (log file or transaction
file)中,定期归并 入主文件。
4,索引顺序文件 (indexed-sequential file)
在索引文件中，可 将关键字域中的取值划分若干个区间 （如
A~Z可以划分为 A到 Z共 26个区间），每个区间对应一个索引项，后者指向该区间的开头记录。 新记录 暂时保存在溢出文件中，定期归并入主文件。
通过划分层次，在记录数量较大时，比顺序文件大大缩短检索时间。 顺序文件是 N/2(这时可使用折半查找 )，而索引顺序文件（ 一级索引 ）是 i/2 + N/(2*i)，其中 i为索引长度。索引还可以是 多级 的。如：有 1000,000条记录的顺序文件的平均检索长度为 500,000，而在添加一个有 1000条索引项的索引文件后，平均检索长度为 1000。
在顺序文件（主文件 main file）的基础上，另外建立 索引 (index)和 溢出文件 (overflow file)。这样做的目的是加快顺序文件的 检索速度 。
关键字 逻辑地址姓名 其它属性
A
B
Z
An Bing
An Kang
An Qing
Bao Rong
Bi Jing
Bon Long
索引文件顺序文件索引顺序文件
5,索引文件 (indexed file)
记录大小不必相同,不必排序,存放在主文件
(primary file)中。索引文件与索引顺序文件的区别在于主文件不排序。另外建立索引,每个索引项指向一个记录,索引项按照记录中的某个关键字域排序。对同一主文件，可以针对不同的关键字域相应建立 多个索引 。索引文件的记录项通常较小,查找速度快,便于随机访问 (random access)。
6,哈希文件或直接文件 (hashed file or direct file)
记录大小相同。由主文件和溢出文件组成。 记录位置由哈希函数确定。 检索时给出记录编号，通过哈希函数计算出该记录在文件中的相对位置。 访问速度快,
但在 主文件中有空闲空间 。
7.3 文件目录
7.3.1 目录内容
7.3.2 目录结构类型
7.3.3 文件别名的实现返回目录是由 文件说明索引 组成的 用于文件检索 的特殊文件。文件目录的内容主要是 文件访问的控制信息 （不包括文件内容）。
7.3.1 目录内容
文件名,字符串，通常在不同系统中允许不同的最大长度。可以修改。有些系统允许同一个文件有多个别名 (alias)；
别名的数目；
文件类型,可有多种不同的划分方法，如：
– 有无结构（记录文件，流式文件）
– 内容（二进制，文本）
– 用途（源代码，目标代码，可执行文件，数据）
– 属性 attribute（如系统，隐含等）
– 文件组织（如顺序，索引等） 返回目录的内容是 文件属性信息 (properties)，其中的一 部分 是 用户可获取 的。
1,基本信息
2,地址信息
存放位置,包括哪个设备或文件卷 volume，以及各个存储块位置；
文件长度 （当前和上限）：以字节、字或存储块为单位。可以通过写入或创建、打开、关闭等操作而变化。
3,访问控制信息
文件所有者（属主）,通常是创建文件的用户，
或者改变已有文件的属主；
访问权限 （控制各用户可使用的访问方式）：如读、写、执行、删除等；
4,使用信息
创建时间
最后一次读访问的时间和用户
最后一次写访问的时间和用户
7.3.2 目录结构类型
一级目录,整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。它具有如下的特点：
– 结构简单；
– 文件多时，目录检索时间长；
– 有命名冲突：如重名 (多个文件有相同的文件名 ) 或别名 (一个文件有多个不同的文件名 )
二级目录,在根目录下，每个用户对应一个目录
（第二级目录）；在用户目录下是该用户的文件，
而不再有下级目录。适用于多用户系统，各用户可有自己的专用目录。
返回目录结构讨论目录的组织结构，设计目标是检索效率。
多级目录,或称为树状目录 (tree-like)。在文件数目较多时，便于系统和用户将文件分散管理。
适用于 较大的文件系统 管理。目录级别太多时，
会增加路径 检索时间 。
– 目录名,可以修改。
– 目录树,中间结点是目录，叶子结点是目录或文件。
– 目录的上下级关系,当前目录 (current directory,
working directory),父目录 (parent directory),子目录 (subdirectory),根目录 (root directory)等；
– 路径 (path)：每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示；
A B C根目录
E P
A B D F E D B G A E
H I J K A B C
D E
L M N A
多级目录组织
改进的多级目录,为了提高 目录检索速度,
可把目录中的文件说明（文件描述符）信息分成两个部分：
– 符号文件目录,由 文件名 和 文件内部标识 组成的树状结构，按文件名排序；
– 基本文件目录 （索引节点目录）：由 其余文件说明信息 组成的 线性结构,按文件内部标识排序；
1
内部名
ID
其它信息 地址
2
3
4
5
6
7
8
9
10
11
基本文件目录( I D 1 )
ID4
ID5
ID7
ID9
ID10
ID11
文件名 ID
3Tu-Lide
8Tu-Qi
根目录( I D 2 )
文件名 ID
7Products
5Rooms
Tu-Lide的 目录(ID3)
4Software
6Tools
文件名 ID
T o o l s 的目录( I D 6 )
11SA-SD
10Univer
文件名 ID
10Univer
5Classroom
Tu-Lide的 目录(ID3)
9Tools
基本文件目录
Tu-Lide的 目录(ID3)
Products RoomsSoftware Tools
根目录( I D 2 )
Tu-Lide Tu-Qi
Tu-Lide的 目录(ID8)
Univer ClassroomTools
T o o l s 的目录( I D 6 )
SA-SDUniverID4 ID5ID7 ID9
ID10ID11
符号文件目录的层次结构
7.3.3 文件别名的实现
基于索引结点
基于符号链接返回提供文件共享的方法有两种：各用户通过唯一的共享文件的 路径名 访问共享文件（该方法的访问 速度慢,适用于不经常访问的文件共享），或利用多个目录中的不同文件名来描述同一共享文件（即 文件别名,该方法的访问 速度快,但会 影响文件系统的树状结构,适用于经常访问的文件共享，同时 存在一定的限制 ）。文件别名的实现方法有以下两种：
1,基于索引结点 (index node)的文件别名
UNIX举例,"ln source target ; rm source"则该文件还存在，文件名为 target；
限制：不能跨越不同文件卷；通常不适用于目录（在
UNIX中只对超级用户允许），否则由树状变为网状。
也称为硬链接（ hard link）；基于改进的多级目录结构,将目录内容分为两部分：文件名和索引结点 。前者包括文件名和索引结点编号，后者包括文件的其他内容（包括属主和访问权限）。通过 多个文件名链接
(link)到同一个索引结点,可建立同一个文件的 多个彼此平等的别名 。别名的数目记录在索引结点的链接计数中，若其减至 0，则文件被删除。
2,基于符号链接 (symbolic link,shortcut)的文件别名
UNIX举例,"ln -s a b ; rm a"则文件 a不存在,b
能被控制但无法访问。若 a是目录,"ln -s
/user/a /tmp/b"则 "cd /tmp/b ; cd,."是进入目录
"/user"而不是 "/tmp"；
缺点：空间和时间开销更大。如果设置不当，
上下级目录关系可能会形成环状。
它是一种 特殊类型的文件,其内容是 到另一个目录或文件路径的链接 。建立符号链接文件，并 不影响原文件,实际上它们各是一个文件。可以建立任意的别名关系，甚至原文件是在其他计算机上。
7.4 文件和目录的使用
7.4.1 文件访问
7.4.2 文件控制
7.4.3 目录管理
7.4.4 伪文件 (pseudo file)
返回这一部分讨论操作系统提供的与文件系统相关的 API。
7.4.1 文件访问
打开 open：为文件读写所进行的准备。给出文件路径，
获得文件句柄 (file handle)，或文件描述符 (file
descriptor)。需将该文件的目录项读入到内存中。
关闭 close：释放文件描述符，把该文件在内存缓冲区的内容更新到外存上。
复制文件句柄 dup：用于子进程与父进程间的文件共享，复制前后的文件句柄有相同的文件名、文件指针和访问权限；
返回文件访问是指围绕文件内容读写进行的文件操作。
读 read,写 write和 移动文件读写指针 lseek：系统为每个打开文件维护一个读写指针 (read-write pointer)，它是相对于文件开头的偏移地址 (offset)。读写指针指向每次文件读写的开始位置，在每次读写完成后，读写指针按照读写的数据量自动后移相应数值。
执行 exec：执行一个可执行文件；
修改文件的访问模式 （ fcntl和 ioctl）：提供对打开文件的控制，如：文件句柄复制、读写文件句柄标志、
读写文件状态标志、文件锁定控制、流（ stream）的控制；
7.4.2 文件控制
创建 （ creat和 open）：给出文件路径，获得新文件的文件句柄；
删除 unlink：对于 symbolic link和 hard link，删除效果是不同的；
获取文件属性 （ stat和 fstat）,stat的参数为文件名,fstat的参数为文件句柄；
修改文件名 rename；
修改文件属主 chown,修改访问权限 chmod：与相应系统命令类似；
文件别名控制,创建 symlink或 link，读取链接路径 readlink； 返回文件控制是指围绕文件属性控制进行的文件操作。
7.4.3 目录管理
进行文件访问和控制时，由操作系统 自动更新目录内容
目录创建 mkdir,删除 rmdir,修改目录名
rename。只适用于超级用户,mknod（ 建立文件目录项 ）和 unlink（ 删除目录项 ）
修改当前目录 chdir；
返回目录管理是指目录访问和目录属性控制。
7.4.4 伪文件 (pseudo file)
特点
– 内容 并不保存在外存上，而是 在其他外部设备上或内存里
– 随文件类型的不同,适用于某些文件访问和控制的系统调用,
如,open,read,write,close,chmod,chown。
– 创建时使用特定的系统调用,如：创建管道 pipe，创建管套
socket，创建设备文件 mknod
类型
– 设备,字符设备或块设备,可以直接访问设备中的字节数据或数据块。如终端、硬盘、内存等。在 UNIX中称为特殊文件 (special file)。
– 进程间通信,本计算机或通过网络。如：管道，管套等。
返回伪文件是指具有文件某些特征的系统资源或设备，它们的访问和控制方式与文件类似。
7.5 文件共享
7.5.1 文件的访问权限
7.5.2 文件的并发访问返回
7.5.1 文件的访问权限
文件访问类型,
– 读 read：可读出文件内容；
– 写 write（修改 update或添加 append）：可把数据写入文件；
– 执行 execute：可由系统读出文件内容，作为代码执行；
– 删除 delete：可删除文件；
– 修改访问权限 change protection：修改文件属主或访问权限返回设置文件访问权限的目的是为了在多个用户间提供 有效的 文件 共享机制 ；
用户范围类型,
– 指定用户
– 用户组
– 任意用户
访问类型和用户范围的组合,
– 访问矩阵,矩阵的一维是每个目录和文件，另一维是用户范围，每个元素是允许的访问方式
– 访问策略 (policy)：每种文件访问方式，所允许或禁止的用户范围。可以将文件访问方式推广到其他操作如用户管理，备份，网络访问等。
7.5.2 文件的并发访问
访问文件之前，必须先打开文件：如果文件的 目录内容 不在内存，则将其从外存读入，否则，仍使用已在内存的目录内容。这样，多个进程访问同一个文件都使用内存中同一个目录内容，保证了文件系统的一致性。
文件锁定 (file lock)：可以协调对文件指定区域的互斥访问
– Solaris 2.3中 lockf的锁定方式：
F_UNLOCK：取消锁定；
F_LOCK：锁定；如果已被锁定，则阻塞；
F_TLOCK：锁定；如果已被锁定，则失败返回
F_TEST：锁定测试；
利用 进程间通信,协调对文件的访问；
返回文件并发访问控制的目的是提供多个进程 并发访问 同一文件的机制。
7.6 外存存储空间管理
7.6.1 文件存储空间分配 (file
allocation)
7.6.2 外存空闲空间管理 方法
(free space management)
7.6.3 文件卷返回讨论如何高效地进行数据存储
7.6.1 文件存储空间分配 (file allocation)
预分配 (preallocation)：创建时 (这时已知文件长度 )一次分配指定的存储空间，如文件复制时的目标文件。
动态分配 (dynamic allocation)：需要存储空间时才分配（创建时无法确定文件长度），
如写入数据到文件。
返回
1,新创建文件的存储空间（文件长度）分配方法
2,文件存储单位：簇（ cluster）
簇的大小
– 两个极端,大到能容纳整个文件，小到一个外存存储块；
– 簇较大,提高 I/O访问性能,减小 管理开销 ；
但 簇内碎片浪费 问题较严重；
– 簇较小,簇内的碎片浪费较小，特别是 大量小文件 时有利；但存在 簇编号空间不够 的问题（如 FAT12,16,32）；
文件的存储空间通常由多个分立的 簇 组成，而每个簇包含若干个 连续的扇区 (sector)。
簇的分配方法：两种
– 簇大小可变，其上限较大,I/O访问性能较好，文件存储空间的管理困难（类似于动态分区存储管理）
– 簇大小固定，较小：文件存储空间使用灵活，但
I/O访问性能下降，文件管理所需空间开销较大
文件巻容量与簇大小的关系
– 文件卷容量越大，若簇的总数保持不变即簇编号所需位数保持不变，则簇越大。缺点：簇内碎片浪费越多
– 文件卷容量越大，若簇大小不变，则簇总数越多，
相应簇编号所需位数越多。如簇编号长度为 12、
16,32二进制位，即构成 FAT12,FAT16,FAT32。
3,文件存储分配数据结构
连续分配 (contiguous)：只需记录 第一个簇的位置,
适用于预分配方法。可以通过紧缩 (compact)将外存空闲空间合并成连续的区域。
链式分配 (chained)：在每个簇中有 指向下一个簇的指针 。可以通过合并 (consolidation)将一个文件的各个簇连续存放，以提高 I/O访问性能。
索引分配 (indexed)：文件的第一个簇中记录了该文件的 其他簇的位置 。可以每处存放一个簇或连续多个簇（只需在索引中记录连续簇的数目）。
采用怎样的数据结构来记录一个 文件的各个部分的位置 。
7.6.2 外存空闲空间管理 (free space management)方法
位示图 (bitmap)：每一位表示一个簇，取值 0和 1分别表示空闲和占用。
空闲空间链接 (chained free space)：每个空闲簇中有指向下一个空闲簇的指针，所有空闲簇构成一个链表。不需要磁盘分配表，节省空间。每次申请空闲簇只需取出链表开头的空闲簇即可。
空闲空间索引 (indexed free space)：在一个空闲簇中记录其他几个空闲簇的位置。
返回外存空闲空间管理的数据结构通常称为 磁盘分配表
(disk allocation table)，分配的基本单位是簇。 文件系统可靠性 包括检错和差错恢复。空闲空间的管理方法：
三种，均适用于上述几种文件存储分配数据结构；
注：可以上述方法结合，应用于不同的场合。如,位示图 应用于索引结点表格,链接和索引 结合应用于文件区的空闲空间。
7.6.3 文件卷
磁盘分区 (partition)：通常把一个 物理磁盘 的存储空间划分为几个相互独立的部分，称为 "分区 "。一个分区的参数包括,磁盘参数 （如每道扇区数和磁头数）,分区的起始和结束柱面 等。
文件卷 (volume)：或称为 "逻辑驱动器 (logical drive)"。
在同一个文件卷中 使用同一份管理数据 进行文件 分配和外存空闲空间管理,而在不同的文件卷中使用相互独立的管理数据。
– 一个文件不能分散存放在多个文件卷中,其最大长度不超过所在文件卷的容量。
– 通常一个 文件卷只能存放在一个物理外设上 （并不绝对），
如一个磁盘分区或一盘磁带。
返回
格式化 (format)：在一个文件卷上 建立文件系统,即：
– 建立并初始化 用于进行文件分配和外存空闲空间管理的 管理数据 。
– 通常，进行格式化操作使得一个文件卷上 原有的文件都被删除 。
扩展文件卷集 (extended volume set)：一个文件卷由一个或几个磁盘上的 多个磁盘分区 依次连接组成。可以容纳长度大于磁盘分区容量的文件。
– 实例,Windows NT中的扩展文件卷集。
磁盘交叉存储 (disk interleaving),将一个文件卷的存储块依次分散在多个磁盘上 。如 4个磁盘，则磁盘 0
上是文件卷块 0,4,8,…,磁盘 1上是文件卷块 1,5,
9,… 。
– 优点,提高 I/O效率 。如果需要访问一个文件的多个存储块，而它们分散在多个磁盘上，则可以 并发地向多个磁盘发出请求,并可在此基础上提供文件系统的 容错功能 。关键,磁盘访问时间大部分由旋转等待时间组成 。
– 需要相应硬件设备：如多个硬盘连接在同一个或不同的
SCSI接口上，或者两个硬盘连接在一个或不同的 IDE接口上（两个硬盘连接在同一个 IDE接口上，不能提高 I/O效率）
– 实例,Windows NT中的 条带卷 (stripe set)，每个文件卷块的大小是 64KB。
– 类似例子：在虚拟存储器中建立 多个交换区,分散在多个磁盘上
D i sk 0
D i sk 1
D i sk 2
D i sk 3
C y cl i ng W ai t
D at a T r ans f er
t
R eques t C om pl et e
多个磁盘上的交换区访问
7.7 文件系统举例
7.7.1 MS DOS的文件系统
7.7.2 Windows NT的文件系统
7.7.3 UNIX的文件系统返回
7.7.1 MS DOS的文件系统返回多级目录，不支持文件别名，无用户访问权限控制
1,磁盘文件卷结构
F A T 1 F A T 2 Roo t
Di r ec t or y
Dat a
( F i l e & Di r ec t or y )
Boo t
Rec or d
V ol um e S t ru ct ur e i n M S DO S
Se ct or # 0 N1 2N
文件卷 (volume)信息：记录在 引导记录的扇区中。包括：簇大小，根目录项数目,FAT表大小，磁盘参数（每道扇区数，磁头数），文件卷中的扇区总数，簇编号长度等
– 逻辑扇区号,三元组（柱面号，磁头号，扇区号）
－ >一个文件卷中从 0开始对每个扇区编号，优点：
屏蔽了物理磁盘参数的不同
– 允许 同时访问的文件卷数目上限 可以由 config.sys
文件中的 LASTDRIVE= 语句指定
– 簇 (cluster)：由若干个扇区组成。在一个文件卷中从 0开始对每个簇编号。
每个 FAT表项所占位数是 簇编号 的位数，其值是
（以 FAT12为例）：
– 0：表示该簇空闲
– FF7h：物理坏扇区
– FF8h~FFFh：表示该簇是文件的最后一个簇
– 其他值：表示该簇被文件占用，而且表项中的值是文件下一个簇的编号。
FAT表,两个镜像，互为备份。文件卷中的每个簇均对应一个 FAT表项，文件分配采用链式分配方法。
目录：是目录项的顺序文件 (即大小相同的排序记录序列 )，不对目录项排序。
– 若目录中包含的文件数目较多，则搜索效率低。
– 每个目录项大小为 32字节，其内容包括：文件名（ 8+3个字符），属性（包括文件、子目录和文件卷标识），最后一次修改时间和日期，文件长度，第一个簇的编号。
– 在目录项中，若第一个字节为 E5h，则表示空目录项；若为 05h，则表示文件名的第一个字符为 E5h。
– 文件名不区分大小写
823h
800h
...
F A T
850h
823h
..,800hF F 8h
850h
...
Di r Ent r y
F i l e1
...
2,打开文件管理
系统文件表 (SFT,System File Table)和 任务文件表 (JFT,Job File Table)：
– SFT包含 系统的所有打开文件,可以由几个表项依次连接组成。
– JFT包含 该任务（进程）的所有打开文件 。 JFT表项内容是 到 SFT表项的索引 。
– SFT的表项数目 可由 config.sys文件中的 FILES=
来语句指定，默认是 8。
7.7.2 Windows NT的文件系统
NTFS为改进的多级目录结构，支持文件别名（符号链接方式）；
NTFS文件由多个文件属性构成，每个属性由属性名和属性流（ stream,简单字节队列）组成；用户可自定义属性；
NTFS支持用户权限管理：
– 有 5种权限划分：读、写、运行、删除和修改权限；
– 支持按用户、用户组分配权限；
NTFS文件支持数据压缩功能；
NTFS卷结构支持容错功能；
返回
1,概述
2,Windows NT的文件系统结构远程文件操作过程
3,与文件系统相关的数据结构
4,NTFS卷结构
NTFS的结构以卷为单位,卷与磁盘分区相关；卷由一组文件和未分配空间组成；
NTFS以簇为基本硬盘分配单位,簇的大小为物理扇区的整数倍，通常为 2K倍。
NTFS卷上的所有数据（包括用于引导、定位、空间分配等文件系统管理数据）都以 文件 的形式保存；
文件引用号,在主文件表中每个文件记录有一个 64
位的文件引用号；它由文件号和顺序号组成，文件号（ 48位,47~0）是文件在主文件表中的位置序号，
顺序号（ 16位,63~48）在每次重复使用该文件记录时加 1；
NTFS的元文件
主文件表 （ $MFT）：文件记录数组，每个记录为
1KB；每个文件对应一个或多个文件记录；
主文件表副本 （ $MFTMirr）：是主文件表中前几项的副本，用于在主文件表不能读取时的元文件定位；
卷结构日志 （ $LogFile）：记录所有影响 NTFS卷结构的操作，用于系统失败后的卷恢复；
空间分配位图 （ $Bitmap）：标识卷中每个簇的分配状态，即：空闲和已被分配；
引导文件 （ $Boot）：引导程序代码；
坏簇文件 （ $BadClus）：记录卷中据有损坏位置；
卷文件 （ $Volume）：卷名、文件系统版本、卷状态
（卷是否被损坏）；
属性定义表 （ $AttrDef）：卷中支持的属性类型列表；
5,NTFS文件属性
NTFS文件是属性的集合,通常所说的文件内容是指未命名数据属性流；
例：我们定义两个数据属性,ntfile(数据 )和 ntfile:data(自定义数据 )。在向 FAT复制时，自定义属性会丢失。
echo test....data >ntfile
echo test....user defined data >ntfile:data
more <ntfile
more <ntfile:data
copy ntfile h:ntfile (H为 NTFS)
copy ntfile f:ntfile (F为 FAT)
more <h:ntfile
more <h:ntfile:data
more <f:ntfile
more <f:ntfile:data
NTFS文件属性的存储形式
常驻属性 （ Resident Attribute）：属性流直接存放在主文件表中；标准信息和文件名总是常驻的。
非常驻属性 （ Nonresident Attribute）：属性流的存放不在主文件表中；大文件的数据属性、大目录的文件名索引属性等长度可增加的属性为非常驻的。
常驻属性非常驻属性
NTFS文件结构
NTFS目录结构
6,NTFS的数据压缩
稀疏文件压缩,稀疏文件是指相对于文件大小而言只有少量非零数据的文件。压缩方法为省略（不保存）只包含零的簇。
非稀疏文件压缩,NTFS首先把文件分成 16个簇为一组的压缩单位；分别对各压缩单位进行压缩，当压缩后不能节约一个簇时，不压缩而直接存储；当压缩后可节约至少一个簇时，只分配相应空间，存储压缩后的数据。
NTFS支持基于文件、目录和卷的压缩。
稀疏文件压缩非稀疏文件压缩
7,NTFS卷结构
卷集,是由 1到 32个硬盘分区构成的单一文件卷，可在不影响已存储数据的条件下把一个硬盘分区增加到卷集中。
可用于,合并多个小硬盘分区,形成跨越多个小硬盘的更大卷；动态增加卷的大小。
通常一个文件卷与一个硬盘分区相对应，但 NTFS支持由多个硬盘分区构成的文件卷,以提高文件 I/O效率,
提供 动态增加卷大小 和 容错 功能。
Span
Span
Span
Span
C:
20 0 MB
D:
10 0 MB
G:
50 MB
Disk 0
E:
10 0 MB
F:
12 5 MB
G:
25 0 MB
Disk 1
E:
50 MB
F:
20 0 MB
G:
12 5 MB
Disk 2
Tota l Size
C,20 0 MB
D,10 0 MB
E,15 0 MB
F,32 5 MB
G,42 5 MB
条带卷,由 2个以上的分布在不同物理硬盘上的大小相同的分区，
以 64KB大小的条带为单位组合成的文件卷。条带卷可 使数据在硬盘间的分布趋于平均,通过多个并行的硬盘
I/O来提高文件
I/O速度。
Strip e 1
Strip e 4
Strip e 7
Strip e 1 0
Disk 0
Strip e 2
Strip e 5
Strip e 8
Strip e 1 1
Disk 1
Strip e 3
Strip e 6
Strip e 9
Strip e 1 2
Disk 2
镜像卷：由 2个分布在 不同物理硬盘上的大小相同的分区,通过完全复制构成的单一文件卷。镜像卷有一半的空间用于冗余数据存储。可用于：数据的 冗余存储,当数据不可读时，自动从镜像分区中读取；通过 平衡读取操作 来提高文件读取效率。
Duplex
C,FA T
20 0 MB
D,NT FS
10 0 MB
E,N TFS
12 5 MB
Disk 0
C,FA T
20 0 MB
D,NT FS
10 0 MB
F,FA T
30 0 MB
Disk 1
带校验的条带卷：
由 3个以上 的分布在不同物理硬盘上的 大小相同 的分区，以 64KB大小的条带为单位组合成的带校验的文件卷。由 N个分区构成的带校验条带卷有 1/N的空间用于冗余数据存储,可恢复一个条带的错误。
可用于：数据的冗余存储 (容错 )；
提高文件 I/O速度 。
Stripe 1
Pa rity
Stripe 5
Stripe 7
Disk 0
Stripe 2
Stripe 3
Pa rity
Stripe 8
Disk 1
Pa rity
Stripe 4
Stripe 6
Pa rity
Disk 2
7.7.3 UNIX的文件系统
改进的多级文件目录,可以建立 文件别名 （索引结点方式和符号链接方式），有 用户访问权限控制
（文件的读 R、写 W和执行 X，相应于目录的检索文件、增删文件和进入目录）
– 注意：如果对文件具有写权限，而对文件所在目录没有写权限，仍然可以改变该文件的长度（如添加数据），因为除文件名外的其他文件目录内容都存放在索引结点而不是在目录文件。
文件类型,常规文件 (ordinary file)、目录文件
(directory)、特殊文件 (special file)如外设、先进先出文件 (FIFO)如命名管道；
返回
1,概述
2,磁盘文件卷结构
超级块,描述文件系统的状态，包括磁盘空闲块栈，
空闲 i结点栈
i节点 （ inode list）：存放文件说明信息，每项 64字节
目录文件,每个目录项 16字节。文件名区分大小写。
文件分配,直接索引，一级、二级、三级间接索引
i n o d e
T a b l e
Da t a
( F i l e & Di r e c t o r y )
Bo o t
Re c o r d
V o l um e S t r uc t ur e i n U NI X
Se c t o r # 0 1
Super
Bl o c k
3,空闲 i结点的分配和释放
每次从磁盘上寻找一批空闲 i结点，把它们的编号记录在 内存的空闲 i结点栈 中。其中,铭记” i结点
(remembered inode)是栈中编号最大的 i结点。
i结点分配 时，移出栈顶的 i结点。若到达 "铭记 "i结点则表示栈已空，需要从磁盘上重新寻找。 (铭记 i
结点在栈底 )
652,.,f r ee i nod es
0 1
571 566 em pt y
4922
i nde xr em e m ber ed i nod e
as s i gn i nod e f r ee i nod e
I node L i s t i n S u per B l ock
i结点释放 时，若栈未满，则把被释放 i结点放入栈顶。
若栈已满，则判断被释放 i结点的编号小于 "铭记 "i结点编号，则把前者替换 "铭记 "i结点，否则被释放的 i结点不入栈。
问题举例：这里的问题出在内存中的 i结点栈与磁盘上的状态不一致。如：分配空闲 i结点 100和 150；释放 i结点 100而“铭记” i结点变为 100；分配 i结点 100，则需要重新从磁盘上寻找空闲 i结点；此时 i结点 150还在内存 i
结点表中，如果它尚未更新到磁盘上，那么从磁盘上会找到空闲的 i结点 150。 (由于内外存不同步而产生问题，
内存已分配而外存没有反映出来 )
问题的解决：从空闲 i结点栈中得到 i结点编号之后，还需要对其在内存 i结点表中进行查找 (相当于进行核对 )；
如果找到，说明这个 i结点并非空闲。
4,磁盘空闲块的分配和释放
采用成组链接法,把链表和索引相结合。每一组 50块，用 索引表 表示；各组间通过链表指针串在一起，构成 链表 。链表的开头是超级块中的磁盘空闲块栈，在运行时被读入到内存中。 栈计数 count是栈中的空闲块数目，栈中的元素是空闲块编号。链表中的每一块都存放一个类似的空闲块栈
分配过程,查看超级块中是否 count == 1；若不是，则弹出栈顶元素 N,--count；若是，则弹出栈顶元素 N，把空闲块 N中的栈（包括栈计数）读入到超级块中；返回空闲块编号 N
释放过程,被释放空闲块为编号 N。查看超级块中是否栈已满（如 count == 50）；若不是，则 N入栈,++count；若是，
则将超级块中的栈（包括栈计数）写入到空闲块 N，然后把 N
放入超级块中的栈顶并置 count为 1。
41
350
187
Sup er Bl oc k
count
50
0
40
400
351
...,..
0
49
count 50
450
401
...
0
49
count 46
0
...
...
0
45
count
#350 #400 L as t O ne
...
成组链接
6,打开文件管理
...
5
...
9
U s er Fi l e D es cr i pt ors Fi l e T abl e
5
0
0
...
8
...
6
0
P r o ce s s A
P r o ce s s C
O f f s et
7 8
dup ( )
...
5
...
9
0
P r o ce s s B 8
2 3193 r
2 5609 rw
Count Read/ W r i t e
Mo de
./ f i l e1
F i l e Si ze
I node T abl e
81234
Count
f or k( )
内存 i结点表,空闲的内存 i结点－ >组织成链表；占用的内存 i结点－ >哈希表（对冲突采用链表方式解决）
进程所进入的目录,包括各个打开文件的目录路径，
以及进程的当前目录
– 进入一个目录，如果该目录文件的内存 i结点已经存在，则只需把内存 i结点的引用计数加 1，否则读入该目录文件的磁盘 i结点并建立内存 i结点。
– 系统起动之后，进入根目录并建立相应内存 i结点，直到系统关闭
– 退出目录：如关闭文件或修改当前目录
目录路径查找,把目录路径分解为各级目录名，然后逐级进入目录并查找。如：目录路径为 /usr/include/sys，
则各级目录名为 usr,include,sys。
安装和拆卸文件卷,mount和 umount
小结
文件管理的目的，文件系统结构和功能元素
文件的组织
文件目录
文件和目录的使用
文件共享
外存存储空间管理：文件分配，空闲空间管理，文件卷
举例,MS DOS,Windows NT,UNIX
作业
文件系统的系统调用实现
实现多级目录文件系统实验四
