操作系统笔记------文件管理

文件

文件是指由创建者所定义的、具有文件名的若干相关元素的集合。
分类：有结构文件（由若干记录构成的文件），无结构(流式)文件（由字节/字符组成的文件）。
文件属性：文件类型、长度、物理位置、建立时间等。

文件的数据

记录

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。
关键字：记录的唯一标志，由单个或组合数据项形成。
分类：定长记录（记录长度固定），变长记录（记录长度不定）

数据项

数据项是有结构文件的基本单位，是数据组织中可以命名的最小逻辑单位。也称字段。每个数据项包括：名称、数据类型、数据宽度。
分类：基本数据项（单个数据项），组合数据项（若干个数据项集）。

文件类型

用途分类：系统文件，用户文件，库文件。
文件中数据形式分类：源文件，目标文件，可执行文件
存取控制属性：只执行文件、只读文件、读写文件

文件系统

文件系统是操作系统中负责管理和存取文件信息的软件机构，它是由管理文件所需的数据结构和相应的管理软件以及访问文件的一组操作组成。
比如：NTFS, FAT32, HPFS, ext2, CDFS,ZFS,HFS
文件系统模型(三层结构)：文件系统接口，对对象操纵和管理的软件集合，对象及其属性。

文件系统操作

打开文件：核心工作是，在内存设置对文操作的相关数据结构，并将文件基本信息复制到内存。
关闭文件：核心工作是，删除在内存设置的文件数据结构，并将必要的文件修改信息刷新到磁盘。

虚拟技术

逻辑文件：从用户观点出发看到的文件。其结构为文件的逻辑结构，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称文件组织。
物理文件：从系统角度出发看到的文件。其结构为文件的存储结构/物理结构，是指文件在外存上的存储组织形式，与存储介质的存储性能、外存分配形式密切相关。

逻辑结构

顺序文件（有结构文件）

顺序文件中的记录，按照一定的顺序存储和组织，如时间顺序、关键字顺序等。通常按顺序方式进行文件的读写。
读写操作（基于读写指针）：设置读、写指针指向下一条要读、写记录的起始字节位置。读、写指针在读、写文件的过程中自动变化（由系统负责更新，对程序员透明）。

打开文件时候: 读写指针分别指向文件中首字节位置(为0) 。
后续读写文件时：读写指针(定长记录和变长记录文件）变化方式
Wptr := Wptr + Li; Rptr := Rptr + Li;// Li为记录i长度(变长记录)
Wptr := Wptr + L ; Rptr := Rptr + L ;// L为记录长度(定长记录)

批量顺序存取，效率非常高。
查找或修改单条记录困难(记录变长)。
插入删除记录，困难(记录变长，或须保序) 。

索引文件

定长记录的顺序文件，根据记录号可直接存取，其地址为：
Ai = i * L ; // L为记录长度，i为记录号。
但根据记录的关键字或对于变长记录文件，无法直接存取。
在顺序文件基础上，增加索引表，其中存放每条记录的关键字（或记录号）与其文件位置的对应关系。

索引表本身为定长记录结构，支持折半查找。
读写操作：首先根据索引表，由关键字（记录号）找到记录在文件位置，然后调整读写指针，再进行记录读写。可折半查找。

支持记录直接存取；但索引表须占用额外存储空间，尤其当记录数量很大时。

索引顺序文件

为降低索引表的存储开销，为一组记录在索引表中建立一个索引项，而非每条记录一条索引项。
分组方式：按关键字分组，或直接按记录号分组。

读写操作：首先根据索引表，由关键字（记录号）找到记录所在组的文件起始位置，然后调整读写指针，再顺序读写记录，直到找到所要读写的记录。

整合了顺序文件与索引文件的特点。支持记录直接存取；大大降低索引表的存储空间和I/O、计算开销。

直接文件(散列文件)

直接根据记录的关键字（记录号），经简单计算，得到记录在文件的位置。
读写操作：首先根据HASH函数，由关键字（记录号）计算记录在文件起始位置，然后调整读写指针，再读写。

支持记录直接存取；摆脱索引表，存储空间和I/O、计算开销大幅降低。但是会引起冲突，即不同关键字的散列函数值相同。

物理结构

连续分配

要求为每个文件分配一组**相邻接(连续的)**的磁盘块，且文件的逻辑记录的顺序与所存储磁盘块的块号顺序一致。所形成的文件结构称顺序文件结构，物理文件称为顺序文件。

顺序访问容易,顺序访问速度快；通常，它们位于一条磁道上，在进行读／写时，不必移
动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读／写多个盘块。支持逻辑记录直接存取；但是要求连续的存储空间；并且必须事先知道文件长度；

链接分配

采用离散分配思想，为每个文件分配一组不相邻接的磁盘块，且文件的逻辑记录的顺序与所存储磁盘块的块号顺序可不一致.

隐式链接

采用单链表结构，各磁盘块存储指向下个磁盘块的块号。所形成的文件结构称链接文件结构，物理文件称为链接文件。

不存在外部碎片问题，有利于文件插入和删除，有利于文件动态增长和减小，但是读写文件时更多的寻道次数和寻道时间，存取速度慢，不适于随机存取，可靠性容错性差，如指针出错

显式链接

设置文件分配表(File Allocation Table, FAT),集中存储所有的磁盘块号信息。
FAT表：存储磁盘块号（簇号）的数组。

图中文件A,占据磁盘块为4,6,11。文件B,占据磁盘块为9,10,5，核心是单链表的集中存储。
根据FAT数组中存储的磁盘块号所占用的位数分为：FAT12，FAT16，FAT32。
12位磁盘块号：[0，$2^{12}$-1] (FAT12)
16位磁盘块号：[0，$2^{16}$-1] (FAT16)
32位磁盘块号：[0，$2^{32}$-1] (FAT32)

FAT表的磁盘空间管理能力

这里的占用空间是根据FAT数组中存储的磁盘块号所占用的位数和数组的大小来决定的，FAT12占1.5字节，FAT16占2字节，FAT32占4字节。

不存在外部碎片问题，支持记录的插入和删除，有利于文件动态增长和减小，但是读写文件时更多的寻道次数和寻道时间，存取速度慢，支持随机存取，安全性容错性比隐式链接好

索引分配

为每个文件设置索引表，存储其分配到的磁盘块号。所形成的文件结构称索引文件结构，物理文件称为索引文件。

单级索引

假设磁盘块尺寸为4KB，磁盘块号为32bits。则每个磁盘块可以存储磁盘块号的数量为：4K/4 = 1K ；而单级索引支持的文件尺寸为：1K * 4K = 4 M。即小于4M文件的索引表只占1磁盘块。

二级和多级索引

对于索引表的存储，也采用索引表来记录其所占用的磁盘块号。从而形成二级索引。

假设磁盘块尺寸为4KB，磁盘块号为32bits。则每个磁盘块可以存储磁盘块号：4K/4 = 1K （个）；而二级索引支持的文件尺寸为：1K * 1K * 4K = 4G。索引表占用空间：4K + 1K*4K

混合索引

混合使用直接磁盘块号、各级索引表，从而可以既支持小文件的存储，也可以支持大文件的存储。达到降低索引表存储空间和同时支持大中小文件的目的。

假设磁盘块尺寸为4KB，磁盘块号为32bits。直接地址(10个)
直接地址, 支持文件尺寸：10* 4K = 40K ;
一次间接地址, 支持文件尺寸：
支持文件：1K* 4K = 4M ;
总计：40K + 4M ;
二次间接地址, 支持文件尺寸：
支持文件：1K* 1K* 4K = 4G ;
总计：40K + 4M + 4G;
三次间接地址, 支持文件尺寸：
1K* 1K* 1K *4K = 4T ;
总计：40K + 4M + 4G + 4T;

不存在外部碎片问题，读写文件时较多的寻道次数和寻道时间，访问速度慢，支持记录的插入和删除，有利于文件动态增长和减小，既能顺序存取，又能随机存取，索引表本身带来了系统开销(空间，时间)

目录管理

基本要求：“按名存取”逻辑文件名称，文件共享，允许文件重名。

文件控制块(FCB)

文件控制块(FCB, File Control Block)：描述文件信息（文件属性）的数据结构，操作系统据此管理和读写文件。文件控制块包含：

1. 基本信息类：文件名，文件物理位置，文件逻辑结构，文件物理结构
2. 存取控制信息类：各类用户（文件主、核准用户等）存取权限
3. 使用信息类：文件的建立、修改、访问的日期时间，文件当前使用信息

MS-DOS的文件控制块（FAT12/16)（上图）

struct FCB_FAT16 {
	char filename[8];
	char ext[3]; 
	char attribute;//1字节
	char reserved[10];
	short int time;
	short int date;
	short int firstblock;//2字节
	int size ;//4字节
};
1
2
3
4
5
6
7
8
9
10

检索效率问题：FCB中大量信息在检索中无用，但是占用I/O带宽和存储空间。所以将在检索中无用的信息存储至索引结点中。
索引结点：将FCB中的文件名和文件的其余属性信息分开，前者用于组成文件目录，后者形成索引结点。两者之间通过索引结点编号相连。

磁盘索引结点：存放在磁盘，存储除文件名外的文件属性信息。
内存索引结点：存放在内存，除包含复制的磁盘索引结点信息外，还有索引结点编号（标识内存索引结点），状态（指示i结点是否上锁或者被修改），访问计数（有一进程访问i结点，计数加1，访问结束减1），文件所属文件系统的逻辑设备号，链接指针。

目录结构

单级目录结构

整个文件系统中只建立一张目录表（组成一线性表），每文件占用一个目录项。

查找速度慢；不允许重名；不便于文件共享；

二级目录结构

在主文件目录基础上，允许每个用户建立一个目录，文件存放在各用户子目录下。

改善目录检索速度；便于用户间文件重名；便于用户间文件共享；

多级目录结构（树型目录结构）

允许目录下都可以建立子目录，文件可存放在任意子目录下。

层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制，查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度。

路径名(path name)：以多级目录结构中某结点为起点，将到树中其他结点的路径上的目录名、文件名依次连接起来（用/或\隔开），即构成路径名。起点确定，路径名唯一。
绝对路径名：以根结点为起点的路径名。
相对路径名：以除根结点外的任意结点为起点的路径名。

目录查询

线性检索法
分解路径名成各组成部分，然后依次查找各目录名、文件名。

基于索引结点的文件目录检索

先分解出各级的目录，之后随着目录的FCB列表找到对应的目录的索引结点，接着对着索引结点中指向的块号去寻找下一级的目录，直至找到最终的文件。

存储空间管理

空闲表法

系统为外存所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项。

每一项空闲区的盘块是连续的。

空闲链表法

系统为外存所有空闲区拉成一张空闲盘区（块）表
空闲盘块链：结点代表一个空闲盘块；
空闲盘区链：结点代表一个空闲盘区；

位示图法

位示图利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配；

磁盘块号b对应位示图行号i、列号j ( b, i, j均从0开始计数 ):（n为位示图宽度）
i = b / n ; j = b % n;
位示图行号i、列号j 对应磁盘块号b:
b = i * n + j ;

成组链接法

利用链栈存储所有的空闲磁盘块号。链栈的每个空闲结点存储一组（例如100个）磁盘块号，其中最后一个磁盘块号指向下一组所在的磁盘块。

相关操作

初始化：内存设置空闲盘块号栈，可存储一组空闲磁盘块号(链栈一个结点所能存储的磁盘块号数量上限，例如100个)。读磁盘上链栈的栈顶结点到内存，以初始化空闲盘块号栈。（因为栈顶的结点中存有空闲的一组块号，将其读入栈中，栈内的所有块号皆是空闲的，最后的块号所对应的块中记录着下一组空闲的磁盘块组）
盘块分配：如果栈内的块号没有用完直接从栈内取即可，但是当栈内的块号快用完时，也就是到了最后一个块时，将其块号对应块中的内容（也就是下一组空白块的块号读到栈中），这时栈中已近没有刚刚的最后一块的记录了，这时将其分配出去。栈中又充满了空白的块号，同样的最后一个块号对应块中记录着下一组空白块号。
盘块回收：同样如果栈中有空余的位置直接将块号压栈即可，如果栈已经满了，但是新产生了一个空白块，则将栈中所有的块号写到新产生的空白块中，并将栈中的内容移到磁盘中，最后将新加入的空白块号压栈（此时其位于栈底），其指向的是下一组空白的块号。

文件共享

基于索引结点

利用不同文件名或相同文件名（同一目录）指向相同索引结点。


在linux的文件处理中就使用了这一处理，每当有一个文件名指向相应的文件索引时就将其索引节点的索引计数加一，当索引节点的索引计数为0时也就说明没有文件名对这个文件索引进行指向，这时相应的系统会释放相关的文件索引和盘块资源。

基于符号链

利用符号链文件，其中存储被共享的文件路径名称。

事务机制

事务是一系列相关数据项的读写操作。利用事务机制实现数据一致性控制的方法。
事务日志(LOG)：时间顺序存放事务记录，LOG存放在稳定存储器中。
事务记录包括下列4类

1. 事务开始： 开始事务， <Ti, 开始>
2. 读写操作： 访问和修改记录
3. 事务结束，正常：托付事务, <Ti, 托付>
4. 事务结束，异常：夭折事务, <Ti, 夭折>

基本原则：读写数据之前，必须先写事务日志。

事务记录包括

1. 事务名: 事务的唯一标识；
2. 数据项名：被修改数据项的名称（唯一）；
3. 旧值： 修改前数据项的值；
4. 新值： 修改后数据项的值；

事务的崩溃

恢复算法：Undo: 把所有被事务(无托付)修改后的数据项恢复为旧值；Redo: 把所有被事务(有托付)修改后的数据项重新置为新值；

检查点机制

设置检查点，定时刷新事务日志记录和被修改数据到稳定存储器。

恢复算法：可仅对最后一个检查点后的记录进行处理。
Undo: 把所有被事务(无托付)修改后的数据项恢复为旧值；
Redo: 把所有被事务(有托付)修改后的数据项重新置为新值；