#文件管理
文件系统概念
心态崩了，一大节笔记没保存。不写这节了。
文件系统实现
上一节内容讨论的是逻辑结构的话，这节内容主要是在讨论存储结构
文件系统层次结构
一般可以分成：“用户调用接口-文件目录系统-存取控制验证模块（软件验证合法性）- 逻辑文件系统与文件信息缓冲区（逻辑记录转逻辑块号）- 物理文件系统（逻辑块转物理地址）- 辅助分配模块（管理空闲空间和回收辅存） - 设备管理程序模块（分配设备等）”
目录实现
目录的实现就是为了查找，因此可分为两种目录实现方式：线性列表和哈希表，分别对应线性查找和散列查找。
线性列表
使用存储文件名和数据块的线性表。 优点：实现简单 缺点：查找费时
哈希表
根据文件名得到一个值，并返回指向相信列表中元素的指针。 优点：查找快速，插入删除简单。 缺点：哈希表长度固定，拓展性差
文件实现
文件分配方式
注意和逻辑结构区分
连续分配
连续分配要求每个文件在磁盘上占有一组连续的块。这种方式访问磁盘时所需要的寻道数和寻道时间最小。 优点：简单，存取速度快 缺点：文件长度不易拓展，容易产生外部碎片
链接分配
采取离散分配的方式，显著提高了磁盘利用率。除了最后一个盘块，每个盘块都有指向下一个盘块的指针，这些指针对于用户透明，目录中包括了第一块的指针和最后一块的指针。 优点：无外部碎片，磁盘利用率高 缺点：只能顺序访问，并且稳定性不高，指针也会消耗空间。
上述是隐式链接分配法，为了解决上述问题，使用显示链接分配法。显示存放各物理块指针，将他们都放到了一个叫做FAT的表中，每个表项存放下一块的指针。FAT表不仅记录了各块的先后关系，还记录了空闲的块位置。FAT表系统启动时会读入内存，这样也同时减少了访问磁盘的次数。
索引分配
索引分配主要提供了直接访问的功能。他把所有的盘块号都放在了一个索引块中。每个文件都有索引块，索引块的第i个条目对应文件第i个块的指针。索引分配无外部碎片。 索引块的大小适应个严重的问题，太小的索引块无法存放文件所有块指针，但过大会浪费空间。因此可以采用以下机制解决：
- 链接方案 一个索引块为一个硬盘块，为了处理大文件，可以把多个索引块链接起来。
- 多层索引 学习多级页表好榜样。
- 混合索引 把多种索引分配方法结合，比如系统采用直接地址，又采用单级索引或两级索引。（多重套娃）
文件存储空间管理
空闲表法
类似于内存管理中的动态分配方式，同样也有最佳适应算法、循环首次适应算法等。
空闲链表法
把所有空闲盘曲拉成一条空闲链。 优点：分配回收简单 缺点：分配需要多次
位示图法
用一个二位图来表示表示磁盘中每一块的使用情况。 标号从1开始，i行，j列，n表示一行的数量，b表示块号 盘块分配公式：$b=n(i-1)+j$ 盘块回收公式：$i = (b-1)DIV n+1\quad j=(b-1)MOD n +1$
标号从0开始 盘块分配：$b=n*i+j$ 盘块回收：$i=b DIV n \quad j = b MOD n$
成组链接法
前两者不适合用于大文件系统，因此unix使用成组链接法。大概方法就是一个扇区大部分空间都用作与存储数据，留一个存储另一个扇区的地址，如此循环 套娃。
Linux虚拟文件系统四大对象：
- 超级块(super block)
- 索引节点(inode)
- 目录项(dentry)
- 文件对象(file)
一个超级块对于一个独立的文件系统。保存文件系统的类型、大小、状态等等。
磁盘组织与管理
磁盘的结构
多个扇区围成一个圆，形成磁道，多个磁道和成一个圆面，形成盘片，多个圆面形成一个柱体。每个横切面称为柱面。
磁盘调度算法
- 寻找时间$T_S$，读写信息时移动到相应磁道所需时间。包括了跨越n条磁道时间外，还包括启动磁臂时间s。后者耗时较长。
- 延迟时间$T_r$，磁头定位到某扇区所需要时间。旋转速度r，则$T_r=\frac{1}{2r}$。
- 传输时间$T_t$，每次读写字数b，每秒转速r，磁道上字节数N $T_t=\frac{b}{rN}$
常见的算法有以下几种：
先来先服务
具有公平性。若有大量进程竞争使用，效率近似于随即调度。
最短寻找时间
优先处理与当前所在磁道最近的磁道。会产生饥饿现象
SCAN算法
电梯调度，循环进行。局部性性能不如前两者。
C-SCAN
到尾部后回到首部重新开始，不像scan算法还是从尾部循环到首部。避免了偏向于处理最里或最外的请求。
两种scan算法都可以用look算法优化，即如果前方没有要处理的请求，则立马回头是岸。
为了减少寻道时间，可以采用交替编号的方法。
磁盘的管理
磁盘初始化
- 低级格式化（物理分区） 也就是分磁道 扇区啥的
- 分区 也就是分我们所谓的cde盘
- 逻辑格式化 创建文件系统
引导快
计算机启动需要初始化程序，一般存在ROM中，为了避免代码需要修改，所以rom只存放很小的程序，完整功能程序放在了启动块上。
坏块
系统可以标记坏块，不再使用，但不能修复坏块。
易错点
- 读取数据时间中，影响最大的时寻找时间
- 校验码的确定是低级格式化完成的
- 磁臂黏着：总是访问某个磁道而不响应其他磁道请求 FCFS不会导致这种现象