文件就是一组有意义的信息/数据的集合

文件的属性

  • 文件名
    主要是给用户看，同一个目录下不允许重名文件
  • 标识符
    一个系统内各文件标识符唯一，对用户毫无可读性，给操作系统看的
  • 类型
    文件扩展名
  • 位置
    文件存放路径，给用户看的；外存中的存放地址，操作系统可见
  • 大小
  • 创建时间
  • 上次修改/访问时间
  • 所有者信息
  • 保护信息

文件的逻辑结构

什么是逻辑结构

逻辑结构：在用户看来，文件内部的数据是如何组织起来

物理结构：操作系统看来，文件的数据如何存放在外存中

无结构文件

又叫流式文件，比如.txt，文件内部的数据由一些二进制或者字符流组成

有结构文件

又叫记录式文件，比如数据库表，由一组相似的记录组成
​记录是一组相关数据项的集合，每条记录有一个数据项可作为关键字
根据各条记录的长度是否相等，分为：定长记录，可变长记录

顺序文件

文件中的记录顺序排列（逻辑上），记录可以定长或可变长。各记录在物理上可以顺序存储或链式存储

链式存储：

逻辑上相邻的记录，在物理上离散存储。
​无论是定长/可变长记录，都无法实现随机存取，只能从链头开始遍历

顺序存储：

逻辑上相邻的记录，在物理上也相邻。
没有说明的情况下，顺序文件指采用顺序存储的顺序文件

  • 可变长记录

    无法实现随机存取

  • 定长记录

    可以实现随机存储。

    如果采用串结构(记录顺序与关键字无关)，无法快速找到某个关键字对应的记录，如果采用顺序结构(记录按关键字排序的)，可以使用折半查找等方法快速找到记录

索引文件

索引表本身是定长记录的顺序文件，索引表项包含索引号，长度，指针，真正的记录可以在物理上离散存储。
可以用不同的数据项建立多个索引表

索引顺序文件

将记录分组，每一个组对应一个索引表项
检索记录时先顺序检索索引表，找到分组，再顺序查找分组查找记录
记录过多时，可以建立多级索引表。例如，对于一个含$10^6$个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。平均查找 150 次

文件目录


目录文件中的一条记录就是一个文件控制块（FCB），一个文件对应一个 FCB，一个FCB就是一个目录项，FCB的有序集合叫“文件目录”
FCB包含了文件的基本信息，存取控制信息，使用信息等等。
FCB 实现了文件名和文件之间的映射。
对目录的操作:搜索、创建文件、删除文件、显示文件、修改文件

目录结构

单级目录结构：

二级目录结构：

多级（树形）目录结构：

通过引入”当前目录”和”相对路径”，可以减少磁盘的 I/O 次数，提升访问文件的效率。
无环图目录结构：

索引节点

索引节点是对 FCB 的改进，使每个目录项长度减小，从而每个磁盘块可以存放更多目录项，减少检索文件时的磁盘 I/O 次数。

文件的物理结构

文件块/物理块

连续分配

优点：支持随机访问；顺序访问时速度最快（移动磁头所需的时间短）
缺点：不方便文件扩展，每次扩展都得迁移到一段连续的空间，代价大；存储空间利用率低，产生磁盘碎片

链接分配

链接分配采取离散分配方式，可以为文件分配离散的磁盘块。

隐式链接

除文件最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块指针和最后一块指针。

方便拓展，磁盘利用率高

不支持随机访问，查找效率低

显式链接

把用于链接文件各物理块的指针显式存在一张表中，即文件分配表（FAT）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

方便拓展，磁盘利用率高。支持随机访问，相比隐式链接，地址转换无需访问磁盘，文件访问效率更高。

文件分配表需要占用存储空间。

索引分配

每一个文件建立一张索引表，其中记录文件的逻辑块对应的物理块。存放索引表的磁盘块叫索引块，存放文件数据的磁盘块叫数据块。

注：文件分配表是一个磁盘对应一张，而索引表是一个文件对应一张。

如果索引表太大，一个索引块装不下，我们可以：

  1. 链接方案：在前一个块中存指向下一个块的指针。
  2. 多层索引：类似多级页表

  1. 混合索引：多种索引分配方式的结合

文件存储空间管理

存储空间划分与初始化

存储空间管理

空闲表法

空闲链表法

空闲盘块链

空闲盘区链

位示图法

(字号, 位号) = (行号, 列号) -> 盘块号

字长16 = 一行有 16 个磁盘块，注意 0 开始 还是 1 开始

盘块号 = 字长*字号 + 位号

成组链接法

UNIX系统采用。适用于大型文件系统。

文件卷的目录区中，专门用一个磁盘块作为超级块，系统启动时读入内存，并且保持内外存超级块数据同步

超级块的作用

分配

  1. 若需要 1 个空闲磁盘块

  1. 若需要 100 个空闲磁盘块

回收

第一个分组没有达到上限，加到其末尾即可

达到上限：

文件基本操作

创建文件

  1. 在外存中找到文件所需的空间

  2. 根据文件路径找到对应目录文件，在目录中创建文件对应的目录项

删除文件

  1. 根据路径找到目录文件，找到文件名对应的目录项

  2. 回收文件占用的磁盘块

  3. 从目录表中删除文件对应的目录项

打开文件

  1. 根据路径找到目录文件，找到文件名对应的目录项，检测用户权限

  2. 将目录项复制到该进程在内存中的打开文件表中，返回表目编号(索引号/文件描述符)。之后用户使用打开文件表的编号来指明要操作的文件。

打开文件表有：进程的打开文件表，系统的打开文件表

关闭文件

  1. 删除进程的打开文件表中对应项
  2. 回收分配给该文件的内存空间等资源
  3. 系统打开文件表的打开计数器count-=1(归零时删除该项)

读文件

进程使用read系统调用完成读操作。需要指明是哪个文件(在支持“打开文件”操作的系统中,只需要提供文件在打开文件表中的索引号即可)，还需要指明要读入多少数据、指明读入的数据要放在内存中的什么位置。

操作系统在处理read系统调用时,会从读指针指向的外存中,将用户指定大小的数据读入用户指定的内存区域中

写文件

需要提供打开文件表中的索引号，写出的数据量，写回外存的数据位置(写指针指向)

文件共享

基于索引结点的共享(硬链接)

基于符号链的共享(软链接)

文件共享

口令保护

FCB中保存口令，访问时与用户提供的口令对比

开销小，但是不够安全

加密保护

用密码对文件数据流加密，访问时用密码解密，比如异或加密

保密性强，不需要存储密码，但是加密/解密要花费一定的时间

访问控制

每一个文件的FCB（或索引结点）中增加一个访问控制表(ACL)，控制各用户的访问权限

精简的访问列表：以组为单位，标记其访问权限。

文件系统层次结构

eg：