写在前面
这部分主要是讲数据的持久化, 也就是磁盘存取, 其实对应了内存虚拟化中交换空间那块. 当然还有一些分布式系统的内容, 这里就不提了.
这本书真的很经典!
I/O 设备
寄存器
- 数据寄存器
- 指令寄存器
- 状态寄存器
磁盘寻址
DMA
直接内存访问
中断
慢的系统: 中断
快的系统: 轮询
或者二者结合
(硬件)中断允许 CPU 计算与I/O 操作重叠, 这是提高 CPU 利用率的关键.
磁盘驱动器
性能评价指标
- 寻道时间(多磁道)
- 旋转延迟(单磁道)
磁盘调度
最短寻道时间优先: SSTF
可能导致饥饿
电梯: SCAN
以跨越磁道的顺序来服务磁盘请求
最短定位时间优先: SPTF
视情况而定, 考虑旋转与寻道相比的相对时间, 主要侧重于时间短的.
廉价冗余磁盘阵列: RAID
通过软件支持, 合并多块磁盘, 以得到更大且
透明部署:
对于添加到 OS 中的新功能, 需要考虑这一点, 即是否需要重新写现有的程序.
0 级: 条带化
仅仅以轮转方式将磁盘阵列的块分布在磁盘上.
目的是: 在对数组的连续块进行请求时, 从阵列中获得最大的并行性.
1 级: 镜像
存储两份物理副本
4 级: 奇偶校验
节省空间
通常采用 xor(异或)方法.
5 级: 旋转奇偶校验
4 级的改进.
Linux 文件/目录 API
这部分系统调用都是磁盘 I/O 相关的
Linux 下通过
strace命令追踪系统调用使用情况.
创建文件
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int open(const char *pathname, int flags);
int open(const char *pathname, int flags, mode_t mode);
int creat(const char *pathname, mode_t mode);
int openat(int dirfd, const char *pathname, int flags);
int openat(int dirfd, const char *pathname, int flags, mode_t mode);
读写文件
#include <unistd.h>
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);
改变偏移量
#include <unistd.h>
off_t lseek(int fd, off_t offset, int whence);
直接写入
一般来说会先写到系统的内核缓冲区中, 但是用这个系统调用会直接写入磁盘:
#include <unistd.h>
int fsync(int fd);
重命名
#include <stdio.h>
int rename(const char *oldpath, const char *newpath);
获取文件信息
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
int stat(const char *pathname, struct stat *statbuf);
int fstat(int fd, struct stat *statbuf);
删除文件
实际上是减少链接计数
#include <unistd.h>
int unlink(const char *pathname);
这个操作对应于创建链接(硬链接), 需要 iNode 链接计数的支持, 计数降为 0 自动释放.
创建目录
#include <sys/stat.h>
#include <sys/types.h>
int mkdir(const char *pathname, mode_t mode);
读取目录
#include <sys/types.h>
#include <dirent.h>
DIR *opendir(const char *name);
struct dirent *readdir(DIR *dirp);
int closedir(DIR *dirp);
删除目录
#include <unistd.h>
int rmdir(const char *pathname);
链接
硬链接
仅增加链接计数, 指向目标文件
#include <unistd.h>
int link(const char *oldpath, const char *newpath);
软链接(符号链接)
可以跨文件系统, 并且可以对目录创建软链接
#include <unistd.h>
int symlink(const char *target, const char *linkpath);
挂载文件系统
#include <sys/mount.h>
int mount(const char *source, const char *target,
const char *filesystemtype, unsigned long mountflags,
const void *data);
实现文件系统
需要考虑:
- 数据的存储方式: 数据结构
- 数据的访问方式: 算法
实现文件
下面是一份基本的实现, inode 即 index node, 存储了数据的索引
- Super 代表超级块, 存储文件系统的元信息
- i-bmap: inode 的位图, 标记 iNode 位置.
- d-bmap: 数据的位图, 标记数据位置
- inode: inode 数据
- data: 实际数据存放区域, data region.
--------------------------------------------------------------------
| Super | i-bmap | d-bmap | inode | data |
--------------------------------------------------------------------
bitmap, 位图, 是一种数据结构, 用于指示每个位相应的对象/块的空闲(0)/占用(1)情况
通过(多重)间接指针实现大文件存放.
实现目录
目录本质上也是一个文件, 是一个存储 inode 号和条目名称的列表.
读取和写入
读取
通过 open() 系统调用.
首先寻找 inode, 从而获取关于该文件的一些基本信息(权限信息, 文件大小等), 为此, 文件系统必须能够找到 inode, 这是通过遍历完整的路径名实现的.
从根目录开始 /, 根目录的 inode 为 2, 可以自行查看(ls -ail /)
inode 被读入, 文件系统可以在其中查找指向数据块的指针, 数据块包含根目录的内容, 因此文件系统将使用这些磁盘上的指针来读取目录.
然后递归遍历路径名, 直到找到所需的 inode
不需要读入 i-bmap 等结构, 因为这样的结构是用来分配空间的, 仅读取不会访问分配结构.
open 系统调用导致的 I/O 量与路径名长度成正比, 对于路径中的每个增加的目录, 都必须读取它的 inode 和数据, 如果出现大型目录, 则会读取很多数据块才能找到指定条目.
写入
同样需要先找到对应位置, 然后执行写入, 还可能分配新的块. 每次写入会导致至少 5 个文件 I/O, 即:
- 读取数据位图(d-bmap), 更新已标记新分配的块被使用
- 写入数据位图
- 至少两次读取
- 写入 inode: 采用新块的位置来更新
- 写入真正的数据块本身
优化读写: 缓存(cache)和缓冲(buffer)
划分额略用于为内存分配指定大小的缓存空间, 用于存放磁盘读取数据的缓存
- 静态划分: 早期的实现, 直接指定
- 动态划分: 根据需要(历史信息) 指定
局部性和快速文件系统 FFS
改进
组织结构: 柱面组, 将磁盘划分为一些分组, 是 FFS 用于改善性能的核心机制. 通过在同一组中防止两个文件, FFS 可以确保先后访问两个文件的时候不会导致穿越磁盘的长时间寻道.
分配文件和目录的策略
找到分配数量最少的柱面组(目的是跨组平衡目录)和大量的自由 inode(随后分配一堆文件), 并将目录数据和 inode 放在该分组中.
文件
- 确保在一般情况下将文件的数据块分配到与其 inode 相同的组中, 从而防止 inode 和数据之间的长时间寻道
- 将位于同一目录中的所有文件放在它们所在目录的柱面组中.
针对小文件: 内部碎片的处理
针对大文件
参数化放置
其他改进
- 允许长文件名
- 引入符号链接(软链接
ln -s) - 引入
rename()系统调用(原子)
崩溃一致性: FSCK 和日志
问题引入:
考虑到崩溃(断电或其他问题), 如何更新磁盘?
崩溃一致性
如果在一次写入完成之后系统崩溃或者断电, 磁盘上的结构将会不一致.
FSCK文件系统检查程序
效率低下
即File System Checker,
预写日志系统
数据日志
- 日志写入
- 日志提交
- 加检查点
恢复
- 日志写入
- 日志提交
- 加检查点
- 释放