文件管理

文件的属性

文件名：同一目录下不允许有同名文件 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称
类型
位置：文件的存放路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
大小
创建时间
上次修改时间
创建者
保护信息：对文件进行保护的访问控制信息

文件内部的数据组织方式

1. 无结构文件（如文本文件），由一些二进制或字符流组成，又称流式文件
2. 有结构文件（如数据库表），由一组相似的记录构成，又称记录式文件

文件如何存放在外存
逻辑块号+块内地址

文件的逻辑结构

顺序文件

1. 顺序存储，逻辑上相邻的记录物理上也相邻（类似于顺序表）
2. 链式存储，逻辑上相邻的记录物理上不一定相邻（类似于链表）

1. 串结构：记录之间的顺序与关键字无关
2. 顺序结构：记录之间的顺序按关键字顺序排列

1. 记录定长
2. 记录可变长

链式存储无法实现随机存取，每次只能从第一个记录开始往后查找
顺序可变长记录无法实现随机存取，每次只能从第一个记录开始往后查找
顺序存储定长记录可实现随机存取，若采用串结构，无法快速找到某关键字对应的记录，若采用顺序结构可以快速找到某关键字对应的记录

串结构比顺序结构的增删更简单，因为串结构不需要关键字按顺序排列

索引文件

建立一张索引表以加快文件检索速度，每条记录对应一个索引项
索引项本身是定长记录的顺序文件，因此可以快速找到第i个记录对应的索引项
将关键字作为索引号内容，若按关键字顺序排列，还可以支持按照关键字对半查找
每当要增加/删除一个记录，需要对索引表进行修改
主要用于对信息处理的及时性要求比较高的场合
还可以用不同的数据项建立多个索引表

多级索引

文件目录

目录本身就是一种有结构文件，由一条条记录组成，每条记录对应一个该存放在该目录下的文件

文件控制块FCB：目录文件中的一条记录，实现了文件名和文件之间的映射，使用户可以按名存取。包含文件名、物理地址、逻辑结构、物理结构、存储控制信息、使用信息等，最基本的是文件名和文件存放的物理地址

单级目录：不允许文件重名

两级目录：主文件目录，用户文件目录
不同用户的文件可以重名，也可以实现访问限制，usr1不可以访问usr2的文件

多级目录结构
绝对路径：从根目录出发的路径，/照片/2015/自拍.jpg，三次读盘IO操作
相对路径：从当前目录出发，./2015/自拍.jpg，两次读盘IO操作

无环图目录结构
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录。可以为共享节点设置共享计数器，共享计数器为0时，真正删除文件

文件的物理结构——磁盘分配

磁盘块：在很多操作系统中，磁盘块的大小与内存块、页面的大小相同
磁盘IO、读写操作：内存和磁盘之间的数据交换，以块为单位进行，每次读入一块，或者每次写出一块
文件的逻辑地址也可以表示为逻辑块号和块内地址的形式
用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射

连续分配：每个文件在磁盘上占有一组连续的块
此时文件目录项中需要记录文件的起始块号和长度（占用了多少个块）
用户给出要访问的逻辑块号时，操作系统需要检查用户提供的逻辑块号是否合法（逻辑块号≥长度）
优点1：可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（随机访问）
优点2：读取磁盘块时，需要移动磁头，访问的两个磁盘块相距越远，移动磁头所需时间越长。因此连续分配的文件在顺序读写时速度最快
缺点：物理上采用连续分配的文件不方便拓展（需要移动）；会产生磁盘碎片，使得空间利用率降低（可以用紧凑技术，需要很大的时间代价）

链接分配：采取离散分配，通过指针链接将磁盘块连接

1. 隐式链接
   目录中记录了文件存放的起始块号和结束块号，也可以增加一个字段来表示文件的长度
   除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的
   缺点：只支持顺序访问，不支持随机访问，指向下一个盘块的指针需要耗费少量存储空间
   优点：方便拓展文件，无碎片，空间利用率高
2. 显式链接
   把用于链接文件各物理块的指针显式存放在一张表中（文件分配表FAT，在内存中），一个磁盘只会建立一张文件分配表，开机时文件分配表放入内存，并常驻内存
   文件目录中只需要记录文件的起始块号
   逻辑块号转换成物理块号的过程不需要读磁盘操作
   优点：方便文件拓展，不会有碎片问题，外存利用率高，支持随机访问，相对于隐式链接地址转换时不需要访问磁盘，因此文件访问效率更高
   缺点：文件分配表需要占用一定的存储空间

默认是隐式链接

索引分配：系统为每个文件建立一张索引表，表中记录文件的各个逻辑块对应的物理块（相当于页表），索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块
目录中需要记录文件的索引块是几号磁盘块，索引表中逻辑块号是隐藏的

与显式链接的区别：FAT是整个磁盘对应一张FAT，索引表是一个文件对应一张索引表

支持随机访问，容易实现文件拓展
索引表需要占用空间

如果索引表太大怎么办

1. 链接方案：将多个索引块链接起来存放
   目录项中只需要记录第一个索引块
   想要访问最后一个索引块，需要顺序读入前面所有索引块，IO操作多，低效
2. 多层索引：建立多级索引（类似多级页表），使第一层索引块指向第二层的索引块，根据具体情况可以再建立第三层、第四层
   若采用多层索引，各层索引表大小不能超过一个磁盘块
   两级索引就只需要三次磁盘IO操作（顶级索引表未调入内存）
3. 混合索引：多种索引分配方式的结合，比如，一个文件的顶级索引中，包含直接地址索引（直接指向数据块）和一级间接索引（指向单层索引表）和两级间接索引（指向两层索引表）
   对于小文件，只需较少的读磁盘次数