文件的简介
文件的属性
文件名、标识符、类型、位置、大小、创建时间、上次修改时间、文件所有者信息、保护信息
文件的分类
无结构文件（流式文件）
文件内部的数据是由一系列的二进制或字符流组成，如文本文件（.txt文件）
有结构文件（记录式文件）
由一组相似的记录文件组成，每条记录又由若干个数据项组成，如数据库表。一般来说，每条记录有一个数据项作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录。
记录是一组相关数据项的集合
操作系统应向上提供哪些功能
create、delete、open、close、read、write 系统调用
文件的逻辑结构
逻辑结构 vs 物理结构
逻辑结构：指在用户看来，文件内部的数据应该是如何组织起来的。
物理结构：指的是在操作系统看来，文件的数据是如何存放在外存的。
有结构文件的逻辑结构
根据有结构文件中的各条记录在逻辑上如何组织，可以分为三类。
顺序文件
文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
顺序存储
- 逻辑上相邻的记录物理上也相邻。
链式存储
- 逻辑上相邻的记录物理上不一定相邻。
根据记录之间的顺序与关键字是否有关又可将顺序文件分为
串结构：记录之间的顺序与关键字无关（通常按照记录存入的时间决定记录的顺序）
顺序结构：记录之间的顺序按关键字顺序排列
顺序文件的查找
顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）
索引文件
索引顺序文件
- 当记录过多的时候可以建立多级索引表
文件目录
即我们很熟悉的Windows操作系统的 ”文件夹“。
文件控制块
- 目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该目录下的文件。
- 目录文件中的一条记录就是一个文件控制块（FCB）。
- FCB 实现了文件名和文件之间的映射。使用户程序可以实现 ” 按名存取 “。
FCB中包含
1、文件的基本信息（ 文件名、物理地址、逻辑地址、物理结构等）
2、存取控制信息（是否可读/可写、禁止访问的用户名单等）
3、使用信息（如文件的建立时间、修改时间等）
对目录进行的操作
搜索、创建文件、删除文件、显示目录、修改目录
目录结构
单级目录结构
早期的操作系统并不支持多级目录，整个系统只建立一张目录表，每个文件占一个目录项。
单级目录实现了 " 按名存取 "，但是不允许文件重名。
单级目录不支持多用户操作系统。
两级目录结构
早期的多用户操作系统采用两级目录结构，分为主文件目录 （MFD，Master File Directory）和用户文件目录（UFD，User File Directory）。
优点：两级目录允许不同用户的文件重名，也可以在目录上实现访问限制（检查此时登录的用户名是否匹配）。
缺点：缺乏灵活性，用户不能对自己的文件进行分类。
多级目录结构
又称树形目录结构
用户(或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。从当前目录出发的路径称为相对路径。
系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到“照片”目录的存放位置后，从外存读入对应的目录表；再找到“2015-08”目录的存放位置，再从外存读入对应目录表；最后才找到文件“白拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。
- 相对路径可以减少磁盘 I/O 操作次数。
优点：树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。
缺点：树形结构不便于实现文件的共享。
对此，提出了“ 无环图目录结构 ”。
无环图目录结构
在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。
可以更方便地实现多个用户间的文件共享。
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。
索引结点（FCB的改进）
将除了文件名之外的文件描述信息都放到索引结点中。由于目录项长度减小，因此每个磁盘块可以存放更多各目录项，可以大大提升文件检索速度。
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“ 存放位置 ”即可找到文件。
存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
相比之下内存索引结点中需要增加一些信息，比如:文件是否被修改、此时有几个进程正在访问该文件等。
文件的物理结构
即文件数据应该怎样存放在外存中。
文件块和磁盘块
磁盘块
类似于内存分页，磁盘中的存储单元也会被分为一个个 ” 块 / 磁盘块 / 物理块 “。
很多操作系统中，磁盘块的大小与内存块、页面的大小相同。
内存与磁盘之间的数据交换（即 读/写操作、磁盘I/O）都是以” 块 “ 为单位进行的。
即每次读入一块，或每次写出一块
文件块
在内存管理中, 进程的逻辑地址空间被分为一个个的页面
同样的, 在外存管理中, 为了方便对文件数据的管理, 文件的逻辑地址空间也被分为了一个个的文件块
于是文件的逻辑地址也可以表示为 （逻辑块号, 块内地址）的形式
文件分配方式 —— 连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。
文件目录中记录存放的起始块号和长度（总共占用几个块）
用户给出要访问的逻辑块号，操作系统找到文件对应的目录项（FCB）
物理块号 = 起始块号 + 逻辑块号
需要检查逻辑块号是否合理，当逻辑块号 ≥ 长度就不合法
操作系统可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问( 随机访问 )
优点：连续分配的文件在顺序读/写时速度最快。
缺点：采用连续分配的文件不方便拓展；存储利用率低，会产生难以利用的磁盘碎片。( 可以采用紧凑的方法来处理碎片, 但是需要耗费很大的时间代价 )
文件分配方式 —— 链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。
隐式链接
优点：很方便文件拓展 ；所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。
显式链接
把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table）。
- 一个磁盘仅设置一张 FAT。>
- 开机时，将 FAT 读入内存，并常驻内存。
- FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此 ” 物理块号 “ 字段可以是隐含的。
实现文件的逻辑块号到物理块号的转变
1、用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB）
2、从目录项中找到起始块号，若i > 0，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。 逻辑块号转换成物理块号的过程不需要读磁盘操作。
结论：
采用显式链接方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~ i-1号逻辑块)。
由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。
文件分配方式 —— 索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表一―建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
实现文件的逻辑块号到物理块号的转变
1、用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）
2、从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知道 i 号逻辑块在外存中的存放位置。
可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）。
链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
多层索引
建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
混合索引
多种索引分配方式的结合。
例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引（指向两层索引表)。
文件存储空间管理
空闲表法
适用于连续分配方式。
空闲链表法
空闲盘块链
以盘块为单位组成一组空闲链
适用于离散分配的物理结构。
空闲盘区链
以盘区为单位组成一条空闲链
离散分配、连续分配都使用。
为一个文件分配多个盘块时效率更高
位示图法
如何分配
若文件需要K个块
① 顺序扫描位示图，找到K个相邻或不相邻的“O”；
② 根据字号、位号算出对应的盘块号，将相应盘块分配给文件；
③ 将相应位设置为“1”。
如何回收
① 根据回收的盘块号计算出对应的字号、位号；
② 将相应二进制位设为“ 0 ”。
成组链接法
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。
UNIX 系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为 “超级块”，当系统启动时需要将超级块读入内存。
并且要保证内存与外存中的 “超级块” 数据一致。
文件的基本操作
创建文件
进行 " create 系统调用 "
需要提供的参数：
1、所需的外存空间大小（如：一个盘块，即1KB)
2、文件存放路径（“D:/Demo”）
3、文件名（这个地方默认为“新建文本文档.txt”)
1、在外存中找到文件所需的空间（例如使用空闲链表法、位示图等管理策略，找到空闲空间）
2、根据文件的存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项 。目录项中包含了文件名，文件在外存中的存放位置等信息。
删除文件
进行 " delete 系统调用 "
需要提供的参数：
1、文件存放路径（“ D:/Demo ”)
2、文件名 (“ test.txt ”)
1、根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
2、根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。(回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理)
3、从目录表中删除文件对应的目录项。
打开文件
进行 ” open 系统调用 “
需要提供的要参数：
1、文件存放路径 (“D:/Demo”) 2、文件名 (“test.txt”)
3、要对文件的操作类型（如：r只读；rw读写等)
1、根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
2、将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。
打开文件表
- 打开计数器：记录此时有多少个进程打开了此文件。
- 读写指针：记录该进程对文件的读/写操作进行到的位置。
- 访问权限：如果打开文件时声明的是 ” 只读 “，则该进程不能对文件进行写操作。
关闭文件
进行 ” close 系统调用 “
1、将进程的打开文件表相应表项删除。
2、回收分配给该文件的内存空间等资源。
3、系统打开文件表的打开计数器 count 减1，若count = 0，则删除对应表项。
读文件
进行 ” read 系统调用 “
需要提供的参数
需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可）， 还需要指明要读入多少数据（如：读入1KB）、指明读入的数据要放在内存中的什么位置。
操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
写文件
进行 ” write 系统调用 “
需要提供的参数
需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可）， 还需要指明要写出多少数据（如：写出1KB）、写回外存的数据放在内存中的什么位置
文件共享
操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件。
注意：多个用户共享同一个文件，意味着系统中只有 "一份" 文件数据 。并且只要某个用户改了该文件的数据，其他用户也可以看到文件数据的变化。
基于索引结点的共享方式
索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。
若 count =2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。
若某个用户决定“ 删除 ”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的 count 值减1。
若 count > 0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
当 count = 0 时系统负责删除文件。
基于符号链的共享方式
当 User3 访问 “ ccc ” 时，操作系统判断文件 “ ccc ” 属于 Link 类型文件，于是会根据其中记录的层层查找目录，最终找到 User1的目录表中的 “ aaa ” 表项，于是就找到了文件1的索引结点。
文件保护
口令保护
为文件设置一个 “ 口令 ” （如: abc112233），用户请求访问该文件时必须提供 “ 口令 ”。
-
口令一般存放在文件对应的 FCB 或索引结点中。
-
用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比。
-
如果正确，则允许该用户访问文件。
优点：保存口令的空间开销不多，验证口令的时间开销也很小。
缺点：正确的 “口令” 存放在系统内部，不够安全。
加密保护
使用某个 “ 密码 ” 对文件进行加密，在访问文件时需要提供正确的 “ 密码 ” 才能对文件进行正确的解密。
访问控制
在每个文件的 FCB （或索引结点）中增加一个访问控制列表（Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。
