操作系统—文件管理

补充知识

1. UNIX操作系统中，所有设备都视为“特殊文件”
2. 系统级安全管理：注册和登录
3. 防止文件受损——备份。
4. 存取控制矩阵方法用于多用户之间的存取权限保护
5. 磁带——顺序存储设备。用磁带存储文件只能采用顺序存储结构（若允许磁带来回倒带，则可采用其他文件形式）
6. 文件在磁带上通常采用连续存放方法，在磁盘上通常不采用连续存放方法，在内存上采用随机存放方法
7. 若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则：

①若该文件的数据不在内存，则该进程进入睡眠等待状态

②请求read系统调用会导致CPU从用户态切换到核心态

③read系统调用的参数不包含文件名称

5. 提高文件访问速度：提前读、延迟写、为文件分配连续的簇、采用磁盘高速缓存

文件

以硬盘为载体的存储在计算机上的信息集合

• 在系统运行时，计算机进行资源的调度和分配的基本单位：进程
• 在用户进行的输入、输出的基本单位：文件

文件系统

实现对文件的维护管理。为每个文件创建一张【索引表】

• 创建文件：create系统调用
• 读文件：read系统调用
• 写文件：write系统调用
• 删除文件：delete系统调用

索引表

存放文件数据块的磁盘存放位置。

每个表项包含 相应记录的关键字和存放该记录的逻辑地址

文件的属性

1. 名称。文件名称唯一，同一目录下不允许有重名文件
2. 类型
3. 创建者
4. 所有者
5. 位置。文件存放的路径（用户使用）、在外存中的地址（OS使用）
6. 大小
7. 保护
8. 创建时间、最后一次修改时间、最后一次存取时间

文件控制块FCB

实现了文件名和文件之间的映射，存放控制文件需要的各种信息的数据结构，以实现“按名存取”

文件目录

FCB的有序集合。一个FCB = 一个文件目录项。一个文件目录 = 一个文件

• 基本信息。文件名、文件的物理位置、逻辑结构、物理结构
• 存取控制信息。文件主的存取权限、核准用户的存取权限，一般用户的存取权限
• 使用信息。文件建立时间、上次修改时间

索引结点（FCB的改进）

每一个文件都会有唯一的索引结点。

i 结点inode：将文件描述信息单独形成一个数据结构（将文件描述信息从目录项中分离出来） →目的：减少查找文件时的I/O信息量

补充知识

若某文件系统索引结点中有直接地址项和间接地址项，则与单个文件长度有关的因素：间接地址索引的级数、地址项的个数、文件块大小

①磁盘索引结点

存放在磁盘上的索引结点。每个文件有一个唯一的磁盘索引结点

• 每个索引结点中含有13个地址项
• 以字节为单位的文件长度

②内存索引结点

存放在内存中的索引结点

文件的基本操作

• 创建文件create：在外存中找到文件所需的空间，并为之创建一个目录项
• 写文件write：将文件数据从内存写出外存
• 读文件read：从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中（读、写操作都使用同一指针）
• 重新定位文件 / 文件定位
• 删除文件delete：从目录中检索指定文件名的目录项，回收文件占用的磁盘块，删除目录条目
• 截断文件

文件的打开与关闭

①打开open：把指定文件的目录项复制到内存指定的区域

1. 从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限
2. 从外存复制到内存打开文件表的一个表目中，并将该表目的编号（索引）返回给用户
3. 与用户使用打开文件表的编号来指明要操作的文件

②关闭close

1. OS将会从打开文件表中删除这一条目，回收分配给该文件的内存空间等资源
2. 每个关闭操作使close递减

③打开文件表

• 整个系统的打开文件表：包含FCB的副本及其他信息
• 每个进程的打开文件表：包含指向系统表中适当条目的指针
• 系统打开文件表为每个文件关联一个打开计数器Open Count：记录多少进程打开了该文件

对于打开文件表的索引：UNIX-“文件描述符”；Windows-“文件句柄”

1. 文件指针。必须与磁盘文件属性分开保存
2. 文件打开计数
3. 文件磁盘位置
4. 访问权限

文件保护

目的：保护文件数据安全

存取控制，也是文件保护的方法

对文件的访问控制，由 用户访问权限 和 文件属性 共同限制

访问控制列表ACL

规定每个用户名及其所允许的访问类型

优点：使用复杂的访问方式

缺点：长度无法预计并且可能导致复杂的空间管理

• 拥有者。创建文件的用户
• 组。一组需要共享文件且具有类似访问的用户
• 其他。系统内的所有其他用户

文件的逻辑结构

• 逻辑结构（从用户观点）：文件的组织形式
• 物理结构（从实现观点）：文件在外存上的存储组织形式

1.无结构文件（流式文件）

无结构文件是最简单的文件组织形式，由一系列二进制或字符流组成

①以字节为单位

②只能通过穷举搜索进行记录的访问

③管理简单，用户可以方便地对其进行操作

2.有结构文件（记录式文件）

①顺序文件

文件中的记录按顺序排列，记录通常是定长的，可顺序存储（逻辑上相邻，物理上相邻→可变长记录：无法实现随机存取）或以链表形式存储（无法实现随机存取）

• 串结构
• 顺序结构

检索时首先从FCB中读出文件的第一个盘块号

②索引文件

用于对信息处理的及时性要求比较高的场合

• 定长记录文件
• 变长记录文件：只能顺序查找 ——建立索引表（按关键字排序，本身也是一个定长记录的顺序文件）

检索时首先从FCB中读出文件索引块的开始地址

缺点：每个记录对应一个索引表项，因此索引表可能会很大，对存储空间利用率低

③索引顺序文件

含有N个记录的顺序文件，查找某关键字的记录时，平均查找的记录数为N/2个（需要查找N/2次）

在索引顺序文件中，先顺序查找索引表√N / 2次，再在对应的组中顺序查找√N / 2次，总共需查找√N次

④直接文件 / 散列文件

没有顺序的特性

有很高的存取速度，但是会引起冲突

文件的物理结构

• 文件的分配方式：对磁盘非空闲块的管理
• 文件存储空间管理：对磁盘空闲块的管理

文件的逻辑地址：（逻辑块号，块内地址）

1.连续分配

要求每个文件在磁盘上占有一组连续的块

1. 优点：支持顺序访问、直接访问；实现简单、存取速度快；在顺序读写时速度最快
2. 缺点：文件长度不宜动态增加，即不宜拓展；存储空间利用率低，会产生外部碎片（利用“紧凑”解决碎片）

• 读取某个磁盘块时，需要移动磁头
• 访问的两个磁盘块相隔越远，移动磁头所需时间越长
• 物理块号 = 起始块号 + 逻辑块号

2.链接分配

采用 离散分配 的方式，动态地为文件分配盘块。解决了连续分配的外部碎片和文件大小管理的问题

①隐式链接

1. 优点：只适合顺序访问；不会有碎片问题，外存利用率高
2. 缺点：访问效率很低；指向下一个盘块地指针需耗费少量的存储空间

②显式链接

把用于链接文件各物理块的地址，从每个物理块的末尾中提取出来，显式地存放在内存的一张链接表 ——文件分配表FAT（常驻内存。-1表示文件的最后一块，-2表示这个磁盘块是空闲的）

1. 优点：地址转换时不需要访问磁盘，文件访问效率更高；不会产生外部碎片，可很方便地对文件拓展
2. 缺点：文件分配表的需要占用一定的存储空间

3.索引分配

将每个文件所有的盘块号都集中放在一起构成索引块/表。每个文件必须有一个索引块

索引块：索引表存放的磁盘块

数据块：文件数据存放的磁盘块

• 链接方案。一个索引块通常为一个磁盘块 → 磁盘I/O次数过多，查找效率低下
• 多层索引。

类似“多级页表”：采用k层索引结构，且顶级索引表未调入内存，则访问一个数据块只需k+1次读磁盘操作

→缺点：即使是小文件，访问一个数据块仍需k+1次读磁盘

• 混合索引。系统采用直接地址，采用单极索引分配方式/两级索引分配方式

→优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少

超级超级超级重要考点！！！

①会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）

②能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作

1. 优点：很容易实现文件拓展；支持直接访问，且没有外部碎片
2. 缺点：由于索引块的分配，增加了相同存储空间的开销

4.混合索引分配

• 直接地址：存放直接地址
• 一次间接地址：（实质）一级索引分配方式
• 多次间接地址：二次间接地址分配方式