（一）文件系统

文件系统组成：驻留在外存中的数据管理结构（最基础）；驻留在内存中的数据管理结构；文件系统的管理程序代码。

外存数据的损坏会导致文件系统的损坏。

1、外存数据结构

Linux称他的外存数据结构为超级块。

（1）EXT文件系统将分区划分成块组（Block Group）每个块组对应一组连续的存储块。

（2）FAT文件系统在外存的布局

FAT文件系统中，一个目录项就是一个文件控制块，目录是文件控制块的有序集合。一个文件只能有一个名字。

（3）NTFS在外存的布局

、主文件名、系统文件、文件区

（4）Ucore的SFS文件系统

2、内存数据结构

（1）内存数据结构是文件系统及其管理对象在内存的表示，其数据来源于外存数据结构。

内存中的数据结构是用户最近使用的文件系统在内存中的表示，包括：文件系统结构、FCB、目录项、打开的文件对象。（具体实现函数等见ppt）

（2）系统中可能同时存在多种文件系统，统一文件系统的一种方式是建立虚拟文件系统VFS（Virtual File System）略

3、管理程序

安装 eg：把bin下的安装到user中，则user跟bin中一样，原来的不在。 安装 --> 目录树直接拿过去。若再卸载一下，user中原来的内容又出现了。

（二）文件系统管理操作（结合Ucore）

略写，只记录有点知识点。

（1）128M的sts.img做SFS的磁盘，第0块为超级块 --> 根目录 --> 块位图 --> 文件。

磁盘文件sts.img的格式

连续存储（预先写入，也不允许新建）。

从“.”到“..”再往下找到目录项，看到名字是它，就看i节点的位置。

（2）安装

使用文件系统之前，必须先在内存中建立该文件系统的管理结构。建立文件系统管理结构的过程称为安装。

安装的目的--> 建立文件系统的超级结构块，并将其根目录嫁接在安装点目录之上，形成一个全局统一的文件视图。

ucore只有一种文件系统SFS。

mksfs（创建文件系统） --> sfs.img（即为disk0）。

安装（建立fs结构） --> 结构信息从disk0中来。

根据外存把内存文件系统管理结构建立起来。文件所有管理结构串成一个队列，同时存到hash表中方便查找。

多文件系统 --> 把这棵树 dsk1拼到 dsk0中，用其根目录覆盖安装点 --> 全部就一棵树

文件系统只能由超级用户安装。

最早的安装点是静态做的rootfs，仅有一个根目录，名为“/”，父目录是自己，其 inode 号是0。建立在内存块设备之上，设备号是0，块大小是4096.

（3）文件增长时，要为其分配逻辑块——ucroe 从低到高搜索文件系统的块位图

文件长度缩短或删除时，要释放逻辑块。

由于 indirect 块在内存中没有缓存，对它的修改要立刻写回磁盘。

逻辑块分配的原则 —— 尽力维持文件在块设备上的连续性。

SFS 没有考虑这个问题；

EXT 引入预分配机制——为每个文件建立一个预分配窗口（保证各文件的预分配窗口互不重叠，但不保证其中的逻辑快是空闲的）

这个窗口没有了就去下一个：

预分配窗口仅仅限定了搜索范围，其中的逻辑块并未真正分配给文件。动态创建，尺寸动态调整（8~1027）。

Lazy，第一次访问该文件时再创建根目录 inode。访问文件前，需解析路径名，找到与之对应的 FCB，并为其创建inode 结构。

（4）解析路径名

绝对路径名 & 相对路径名（上一讲）

路径名解析的开始位置就是参考点。整个路径名解析过程就是递归的。

如果某个目录项的名字与路径名相同，就可以获得其 ino 号（逻辑块号，对应的逻辑块中只有一个 sfs_disk_inode 结构），将sfs_disk_inode 结构读出，可以为其创建一个 inode 结构。

当 inode 的引用计数变成0时，说明文件已无用户，应释放掉它的 inode 结构。

（5）Linux 文件管理操作流程

（三）

1、文件逻辑结构

文件系统本身关心的是文件的属性及存储位置，用户关心的是文件的逻辑结构。

文件的物理结构描述文件在外存的存储方法；目录结构描述一组文件的组织方法；文件逻辑结构描述文件内容的组织方法。

（1）堆结构（pile）——数据顺序堆在一起，按序搜索、使用文件。

（2）顺序结构

若记录按键值排序，可用折半查找方法定位记录，搜索块。

（3）带索引顺序结构

顺序结构基础上：增加索引表（根据键值建索引）；增加溢出文件（存储新增加的记录）

溢出文件中的记录定期合并到主文件上。

（4）多索引结构：根据不同域为一个文件建立多个索引，每个索引针对一个域。

（5）Hash结构

hash 结构的文件中，每个记录需要一个主键，记录存储的位置时由 hash 函数根据主键值计算得到的。可能有多个记录的 hash 值相同，所以用一个溢出文件保存 hash 值相同的记录。

2、文件存取方式

文件系统不关心文件的逻辑结构，通常将文件看成是一组连续的字节（字节流），或者一个字节数组。每个字节有自己的地址（相对文件开始地址的偏移量）。

连续是指下一字节的偏移量是上一字节的偏移量+1，不管物理上这些字节在什么位置。

文件存取方式：①顺序存取（缺省）；②随机存取

文件存取方式与外存特性有关：磁带——顺序存取；磁盘——即可顺序存取，也可随机存取

文件存取方式与文件逻辑结构有关：堆和顺序结构——顺序存取；索引和 hash——课顺序也可随机