来源：操作系统_清华大学(向勇、陈渝)
参考文章：
1.总体介绍
基本概念、虚拟文件系统、数据块缓存、打开文件的数据结构、文件分配、空闲空间列表、多磁盘管理-RAID、磁盘调度
2.基本概念
3.文件系统和文件
文件系统：一种用于持久性存储的系统抽象。
在存储器上，文件系统用于组织、控制、导航、访问和检索数据。
文件：文件系统中一个单元的相关数据在操作系统中的抽象。
4.文件系统的功能
文件系统的功能：
5.文件和块
文件属性：名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间、…
文件头：
1.在存储元数据中保存了每个文件的信息
2.保存文件的属性
3.跟踪哪一块存储块属于逻辑上文件结构的哪个偏移
6.文件描述符
文件描述符—用整数代表f
必须先打开文件
f = opea(name , flag)
…
…= read(f,..)
…
close(f)
内核跟踪每个进程打开的文件：
1.操作系统为每个进程维护一个打开文件表
2.一个打开文件描述符是这个表中的索引
内核跟踪每个进程打开的文件，需要元数据来管理：
1.文件指针，指向最近的一次读写位置，每个打开了这个文件的进程都指向这个指针
2.文件打开计数，记录文件打开的次数，当最后一个进程关闭了文件时，允许将其从打开文件表中移除
3.文件磁盘位置：缓存数据访问信息
4.访问权限：每个程序访问模式信息
用户视图：持久的数据结构
系统访问接口：
1.字节的集合（UNIX）
2.系统不会关心你想存储在磁盘上的任何的数据结构！
操作系统内部视角：
1.块的集合（块是逻辑转换单元，而扇区是物理转换单元）
2.块大小 <> 扇区大小，在unix中块的大小是4kb
当用户说：给我2-12字节空间时会发生什么
1.返回字节所在的块
2.返回块内对应部分
如果说要写2-12字节呢？
1.获取块，
2.修改块内对应部分
3.写回块
在文件系统中的所有操作都是在整个块空间上进行的
用户怎么访问文件：
1.顺序访问—按字节依次读取，几乎所有访问都是这种方式
2.随机访问—从中间读写，更快速
3.基于内容访问—通过特征，类似数据库，很少
文件内部的结构：应用系统打开复杂文件，但对操作系统该文件可能很简单
文件内部结构：
无结构：单词，比特的队列
简单记录结构：列，固定/可变长度
复杂结构：格式化文档（MS Word, PDF），可执行文件，。。。
多用户系统中的文件共享是很必要的：
1.访问控制：
谁能获得哪些访问权限；
访问模式：读、写、执行、删除，列举
2.文件访问控制列表（ACL）
<文件实体，权限>
3.unix模式
< root/admin, colleagues, others, read, write, execute >
不同用户层级有不同的权限和访问模式
多用户/客户如何同时访问共享文件：
unix文件系统UFS语义：
会话语义：
锁：
一些操作系统和文件系统提供该功能
寻找文件：
名字解析，逻辑名字转换成物理资源
绝对路径—>依次查找—> 先读文件头，再读数据块，搜索子项，如此递归
举例：解析“/bin/ls”
1.读取root的文件头（在磁盘固定位置），
2.读取root的数据块，搜索“bin”项
3.读取bin的文件头
4.读取bin的数据块，搜索“ls”项
5.读取ls的文件头
8.文件别名
文件别名
两个或者多个文件名关联同一个文件
文件别名实现：
如果删除一个有别名的文件会如何？
如果是软链接，这个别名会成为一个空指针
如果是硬链接，可能有一个隐形计数器，删除一次减一，直到为0时才真正删除
其他管理别名方式：Backpointers方案、添加一个间接层
backpointers 反向指针方案：
1.每个文件有一个包含多个backpointers的列表，所以删除所有backpointers
2.Backpointers使用菊花链管理
有了链接机制，就可能出现循环
如何保证没有循环呢？
9.文件系统种类
文件系统的类别
- 文件可以通过网络被共享（文件位于远程服务器、客户端远程挂载服务器文件系统、标准系统文件访问转换成远程访问、标准文件共享协议：NFS for Unix，CIFS for Windows）
- 分布式文件系统的问题，辨别用户很复杂，一致性问题，错误处理模式，安全性问题等等
10.虚拟文件系统
分层结构，接口暴露给用户，屏蔽底层差异性，上层是虚拟（逻辑）文件系统，底层是特定文件系统模块
除了设备I/O外，还有网络I/O、等等
虚拟文件系统目的：对所有不同文件系统的抽象
虚拟文件系统的功能：
基本数据结构：
11.数据缓存
数据块缓存：
1.数据块按需读入内存（提供read（）操作、预读：预选读取后面的数据块）
2.数据块使用后被缓存（假设数据将会再次被使用、写操作可能被缓存和延迟写入）
3.两种数据块缓存方式，缓存的粒度 （1.普通缓冲区缓存 2.页缓存：统一缓存数据块和内存页）
文件数据块的页缓存
1.在虚拟内存中文件数据块被映射成页
2.文件的读/写操作被转换成对内存的访问
3.可能导致缺页、脏页
4.相应算法，尽量减少对硬盘的读写次数，类似之前的算法
二级存储（secondary storage，auxiliary storage）是计算机主存储器或内存之外的所有可访问数据存储器。
二级缓存（L2 CACHE）是处理器内部的一些缓冲存储器。它分内部和外部两种芯片：内部的芯片二级缓存运行速度与主频相同，而外部的二级缓存则只有主频的一半。
由于一级缓存容量的限制，为了再次提高CPU的运算速度，在CPU外部放置一高速存储器，即二级缓存。
12.打开文件的数据结构
共享机制：强制和劝告（进程可以查找锁的状态来决定）。
13.文件分配
要应对不同大小的文件
大多数文件都很小：
1.需要对小文件提供强力的支持
2.块空间不能太大
一些文件非常大：
1.必须支持大文件（64-bit 文件偏移）
2.大文件访问需要相当高效
如何为一个文件分配数据块：
1.连续分配
2.链式分配
3.索引分配
评价指标：
1.时间高效（如访问速度）
2.空间高效（如存储利用，外部碎片）
连续分配：
文件头指定起始块和长度
位置/分配策略（最先匹配，最佳匹配），类似内存的分配
优点：文件读取表现好，高效的顺序和随机访问
劣势：碎片，文件增长问题（预分配，按需分配），类似数组
最好用于只读文件
链式分配：
以数据块链表方式存储，文件头包含了到第一块和最后一块的指针
优点：创建，增大缩小容易，没有碎片
缺点：不可能真正地随机访问，可靠性（破坏一个链然后整个文件都崩了）
索引分配：
每个磁盘块（索引项），为每个文件创建一个名为索引数据块的非数据数据块（到文件数据块的指针列表）
文件头包含了索引数据块
优点：创建，增大缩小都很容易，没有碎片，支持直接访问
缺点：当文件很小时，存储索引的开销，如何处理大文件？
大文件采用分层的方式，类似内存管理的思想：
14.空闲空间列表
跟踪在存储中的所有未分配的数据块
空闲空间列表存储在哪里？
用位图代表空闲数据块列表
11111001111，如果i = 0 代表数据块为空闲
空闲空间列表的最佳数据结构是什么样的？
假设空闲空间在磁盘中均匀分布，那么找到空闲数据块前需要扫描n/r
n —-磁盘上数据块的总数
r —- 空闲块的总数
为了一致性，需要保护
位图必须保存在磁盘上，不允许block在内存中的状态为1而在磁盘中为0
需要在硬盘中完成把Block置为1之后再真正分配
15.多磁盘管理-RAID
raid：
磁盘通过分区来最大限度减小寻道时间，一个分区是一个柱面的集合，各个分区逻辑上独立。
分区：硬盘磁盘的一种适合操作系统指定格式的划分
卷：一个拥有一个文件系统实例的可访问的存储空间
通常常驻在磁盘的单个分区上
实现：
1.在操作系统内核：存储/卷管理
2.RAID硬件控制器（I/O）
16.磁盘调度