文件

有信息的数据集合。

文件包含的信息：文件名、标识符（操作系统要看）、类型、大小、创建修改时间、所有者、安全信息。

文件管理

文件分为无结构的流式文件和有结构的记录式文件。记录式文件由一条条记录组成。

文件存放在根目录里的目录里。

操作系统应该向上提供给用户的功能：CRUD，打开和关闭文件。

文件存放在外存类似进程在内存中，是分块存放的（救命啊，我刚把那块学过去）。

初次子海外，操作系统还应该提供文件共享和保护功能。

文件的逻辑结构

无结构文件（如txt）很简单。

有结构文件一般有关键字区分各个记录；记录存储长度不同又分为定长和可变长。

有结构文件逻辑结构：

1. 顺序/链式存储。顺序定长存储可以实现随机存取，想找第i位直接起始位置+i*单位长度即可。顺序可变长无法计算，链式存储不连续也无法实现随机存取。顺序定长存储如果物理上也采用顺序存储，则可实现快速检索。
2. 索引文件。对于可变长记录文件，可以建立一个定长的索引表，包含索引号、长度、起始位置指针的信息。检索速度很高。但是索引表和记录数一样，占的空间不小。
3. 索引顺序文件，一条索引代表一组记录。可能查找速度还是很慢，那就建立多级索引。

   类似数据结构中学到的中间表，如果索引中只存储必要的少部分信息（文件名，指针），索引占的小，能放更多的索引，用更少的磁盘块存储，就平均需要访问更少的磁盘块就能找到文件。

​ 外存中的索引节点叫磁盘索引节点，内存中的叫索引节点，可能包含更多信息，如文件是否被修改、同时有几个进程在访问等。

文件目录

文件控制块 FCB 中存储文件名、类型（是否是目录）、权限、地址等信息。

目录支持的功能有：搜索、创建、删除、显示、修改文件。

早期操作系统只支持单文件目录，那就不能重名了。

早期多用户操作系统支持双文件目录，一个主文件目录，其中包含多个用户目录。不同用户目录各自文件可以重名。但是用户自己没办法创建多级目录。

后来的多级目录结构支持多级目录了。

引入当前目录概念：如果没有此概念，我们要找根目录下 /目录1/目录2/照片.jpg，需要三次访存。根目录找目录1，目录1找目录2，目录2找jpg。要是有当前目录的相对路径就会方便得多。

树形目录结构缺点在于不能共享文件。

无环图目录结构

不同用户不同目录下可以访问到相同的共享文件。

共享文件要设置共享计数器。当有用户取消共享后，要删除共享信息，共享计数器--。减为0时删除共享节点。

文件的物理结构

很多操作系统中，磁盘块和内存块、页大小相同，成块成块拿进来。

类似内存，文件存储的逻辑地址分为逻辑块号和块内地址两部分。

连续分配

自不必多说~物理块号=起始块号+逻辑块号。支持顺序访问和随机访问。但是不方便拓展，比如1~3块的A文件想扩展，但是4~6是B文件，不是空闲文件，A文件想拓展只能整体挪到空闲区域；而且还可能产生大量磁盘碎片。

链接分配

隐式链接：FCB存储起始块号和结束块号。像链表一样从第一个找到结尾（每个磁盘块中包含指向下一个盘块的指针，但是这对用户来说是透明的），没法随机存取，但是拓展方便。

显示链接：FCB 中包含起始块号，此外还有一张文件分配表 FAT，其中包含所有块号的下一块指针。隐式链接想找一个块，要先在 FCB 中找到起始位置，再读磁盘，找磁盘里的下一块。显示连接可以先不用读磁盘，根据分配表推测出要找的逻辑块的物理地址再去读磁盘，访问速度更快。

链接分配都不会有外部碎片。

索引分配

每个文件建立一个索引表。索引表存放的磁盘块叫索引块，文件数据存放的磁盘块叫数据块。FAT是一个磁盘对应一张，索引表是一个文件对应一张。

也支持随机存取，也方便拓展，但是索引表占空间。

要是文件太大，索引表一个索引块存不下，需要多个。

可以让索引块之间链接起来。但是不支持顺序存储，要找最后一块就要从头便历。

可以建立多级索引。每级大小不超过一个数据块。k级表访问数据，要访问k+1次磁盘块（k次查找位置，1次查找数据）。

混合索引：

小文件层级小一点。因小文件访问可能频繁一些，就少访问几次。

文件存储空间管理

操作系统的盘有什么用？又叫文件卷，每个文件卷都包含目录区和文件区。

空闲表法

分配磁盘块给用户：类似动态分区分配，可采用首次适应、最佳适应、最坏适应等。

回收磁盘块：也类似动态分区分配，考虑前后有无空闲块。

空闲链表法

空闲盘块链分配：空闲链从链头摘下来k个空闲块，并修改链头位置。

空闲盘块链回收：回收的空闲块挂到空闲链结尾，并修改链尾位置。

空闲盘区链分配：先按算法找到合适的空闲盘区。如果没有合适的，也可以把不同盘区的盘块同时给一个文件。

空闲盘区链回收：如果和空闲盘区挨着，直接合并。否则变成一个单独的空闲盘区挂到队尾。

位示图法

一定注意从0还是1开始！

分配：扫描位图，找到连续的k个0，修改为1.

回收：算出回收盘块的位图字号、位号，置为0.

成组链接法

大文件不适用空闲块法。

超级块存放在内存中，其中包含下一组空闲块块数和块号。

如果没有下一级了，下一组空闲盘块数可以用特殊标识符如-1表示。

空闲分配：如果<100个，从超级块分配就够。

如果=100个，不能直接分配超级块因为这样超级块对后面的链接就消失了。要先把300的内容提到超级块作为新的超级块，再分配。

回收：直接加到超级块上。如果超级块最大大小为100，已经满了，还要回收，就要让新回收的块作为新的超级块，并指向原来的超级块。

文件基本操作

文件创建

需要关注：文件名；文件路径；需要的外存空间。

1. 在外存中找到合适大小的内存空间；
2. 在目录表中更新新文件的信息。

文件删除

1. 根据目录表找到该目录项；
2. 外存中回收内存；
3. 目录表中删除该文件信息。

打开文件

需要用户提供的信息：文件名；文件目录；打开方式（读；写；……）

操作系统先去目录表找到对应的文件，复制到内存中。并且把目录项复制到内存系统的“打开文件表”中。

关闭文件

删除用户打开文件表的对应项；回收空间；系统打开文件表的打开计数器-1，减到0则删除打开文件表的对应项。

读文件

指明要读的文件，要读入多少数据，读入的数据在内存中的位置。读入指定大小放入内存中。

写文件

和read很像。最后再通过write系统调用写回外存。

文件共享

基于索引节点的共享方式（硬链接）：

count说明还有几个进程在共享该文件。

要删除时，count--，若>0则不能删除，=0才能删除。

基于符号链的共享方式（软链接）：

删掉文件1，软链接仍然存在，只是无法通过软链接去访问文件1了。

因为访问共享文件要查询多级目录，进行多次 IO，因此采用软链接。

文件保护

口令保护：规定一个口令，用户要说对应口令才能访问。但是口令保存在系统内部，不安全。

加密保护：用密码对文件加密。如异或加密。有点费时。

访问控制：文件的 FCB 中增加一个访问控制列表 ACL，记录用户可以有哪些权限（读写运行ls）。以组为单位，如：管理员，文件主，文件主的伙伴，陌生人。

文件系统的层次结构

磁盘

磁盘调度算法

先来先服务算法 FCFS：就是单纯的先处理先来的进程。

最短寻找时间优先 SSTF：先找离当前磁道近的。

扫描算法 SCAN：只有磁道移到最外侧之后才允许往回移动，避免 SSTF 的左右横跳。

LOOK 调度算法：改进 SCAN 算法，观察到当前磁道已经是访问请求最右边的磁道后，就可以立即改变磁道移动方向往回。

循环扫描算法 C-SCAN：

C-LOOK 算法：

减少延迟时间

磁盘一直旋转的。如果要读几个相邻的扇区，读了第一个处理的过程中磁盘还在转，处理好了的时候可能又转到不知道哪里去了。可能就会产生很长的延迟时间。

解决办法：交替编号。逻辑上相邻的扇区物理上分开。

为什么磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）？因为更改柱面号需要移动磁头臂，更改盘面号不用移动臂，只需要激活相邻盘面的磁头即可。可以减少磁头移动消耗的时间。

磁盘管理

初始化：

​ 物理格式化：把磁盘划分为扇区。扇区包含头、尾、中间数据部分。头尾会存放一些扇区校验码之类的信息。

​ 磁盘分区：分为几个文件卷。

​ 逻辑格式化：创建文件系统（根目录、管理空间的数据结构如位示图、空闲分区表等）。

​ 磁盘的初始化程序：放在哪里？

​ ROM 只读存储器中的数据出厂时就写好了且不能更改，集成在主板上。但是磁盘的初始化程序说不定以后会更新换代，ROM 中的内容又不能更新，因此初始化程序不放在 ROM 中，而是放在磁盘（C）里。初始化程序的装入程序写在 ROM 中。

坏块的管理：坏掉的扇区。简单的磁盘直接在 FAT 中标记出来防止被使用到（对操作系统不透明）。复杂的磁盘交给磁盘控制器维护坏块链表，而且保留一些备用分区（对操作系统透明）。