南京大学操作系统课程3

设备和驱动程序

插入u盘后会发现/dev下会发生变化

/dev/下的对象不会凭空创建

udisks2才是真正执行mount的程序

实际上我们看到的计算机设备都是输入输出设备。有些设备既能做输入也可以做输出，比如u盘。

输入输出设备是能够与CPU交换数据的接口、控制器。

给寄存器一个内存地址（address docider），CPU就可以直接使用质量（in/out/MMIO）和设备交换数据。

我们可以预先定义好寄存器中每个值被写入会触发什么动作，然后用io设备写入寄存器，触发预先设定的动作。

比如一根线、一条质量（树莓派上就有），GIPO（general purpose input/output）极简的模型 memory-mapped I/O 直接读取电平信号。

串口（Serial Port）是一种用于串行通信的硬件接口，常用于计算机与外部设备（如传感器、单片机、工业设备等）之间的数据传输。

现在的键盘都是软件完成的，但是早期cpu性能受限，需要其他硬件来帮忙做一些事情。比如每按下一个键盘，都会给CPU发送一次中断操作。

8042负责安排以什么频率将键盘上的信号发给cpu。

最早的打印机有个小的解释器。把所有用来划线的指令都物理写出来。将回边语言翻译成机械部件动作的设备。

如果cpu想要更多的IO设备。我们想要兼容位置的设备，因此就出现了总线。

总线提供了设备的虚拟化。总线上会有许多设备。如芯片控制器，核显，独显，温度控制器，usb接口。

usb总线上还会挂在许多设备。如鼠标，麦克风，键盘。

如今pcie6.0 x16带宽达到了128GB/s。总线自带DMA。现代的告诉设备都是直插PCIE的。

程序不能直接访问寄存器，设备可以在程序之间共享的。仔细想想CPU和内存也都是设备。因此我们需要有个新的机制实现设备的虚拟化。这个机制就是文件。

对于硬件设备，它们都是文件和控制接口。操作系统可以直接用文件的API来操作这些设备。

代码会将读写操作翻译成设备能够看懂的指令。这个程序就叫设备驱动程序。目前操作系统能帮忙自动安装驱动，但更早的时候设备驱动都需要自己安装。

对于linux系统来说，如果想实现设备驱动程序，只需要实现file_operation的结构体即可。用来吧系统调用翻译成设备能听懂的数据。

比如/dev/null这个目录写入的所有数据都会被吞掉。读取任何数据都读取不到。即丢弃所有写入它的数据。

它底层实现方式就是读取直接返回0，写入直接返回count（收到字节什么都不做）。

设备对应的文件都是虚拟的。 设备不仅仅是数据还有配置。有俩种实现的方法：

• 控制最为数据流的一部分（ANSI Escape code）
• 提供一个新接口（request-response）

因此设备最复杂的部分，设备是通过IO ctl来控制的。每个设备都有自己的IO ctl。

对于一个io设备来说，非数据的功能全部靠这个系统调用。设备的复杂性是无法降低的，就是有那么多功能.

UNIX的复杂：复杂的hidden specification和procfs。

linux /dev/kvm是干什么的

/dev/kvm是 Linux 系统中用于硬件虚拟化加速的字符设备文件，主要作用是为 KVM（Kernel-based Virtual Machine）提供直接访问 CPU 虚拟化扩展（如 Intel VT-x 或 AMD-V）的能力。

io ctl是一个万能接口，用于处理设备特定操作，这些操作无法通过标准文件I/O实现。由于不同设备控制需求千差万别，ioctl必须高度定制化，导致七参数和用法高度依赖具体驱动实现。

存储设备原理

持久设备需要能够寻址+用电路改写。最早的存储设备是磁带。

纸袋（今天是塑料）上均匀黏上铁磁性颗粒

只需要一个机械部件转动定位。读取：放大感应电流，写入：电磁头（电磁铁）改变磁畴磁化方向。

通过电磁感应写入读取数据。通过切割磁感线得到感应电流。因为这是一维的结构因此卷起来存储很多数据。

比如磁带正反面可以都印刷数据，这样就不需要进行倒带了，直接翻一下磁带即可。但是磁带不能够随机访问，需要通过转轴遍历数据。

磁带价格低，容量高，可靠性高。顺序读写需要等待定位，随机读写完全不行。因此应用场景是冷数据的存档和备份。比如为了数据合规合法，需要保存这个数据。磁带在计算机早期是主力存储设备。

之后出现了磁鼓。用旋转的二维平面存储数据（无法内卷，容量变小）读写延迟不会超过旋转周期。

磁盘在二维平面上防止许多磁带。

因此磁头只需要一个自由度就可以了。磁盘是很稳定的，哪怕近距离用强磁铁都很难磁化。内部有屏蔽和保护机制。磁道的大小可以做到微米级。可以做到每秒5400转。只要bit排布的足够，磁盘就可以进行良好的随机读取。

工程优化，把bit竖起来排布。磁盘正面反面都存数据

磁盘：价格低：高密度，低成本，容量高（2.5d上万个磁道）

顺序读写较高，随机读写勉强。在剧烈震动等情况下，可能会导致数据丢失。

读写需要到对应的磁道，7200rpm->120rps->寻道时间8.3ms。转轴将盘片旋转到读写的位置，读写头的移动时间通常也需要几个ms。

软盘

计算机上的软盘驱动程序，可移动的盘片。最初的成本很低，就是个纸壳子。3.5英寸软盘为了提升可靠性，已经是硬的了。A盘和B盘就是为软盘所用的。最早的硬盘都是需要冷插拔，因此需要软盘可以热插拔。最早的程序甚至没有用户态和内核态，都完整的执行在操作系统上。最早的游戏是通过多张软盘发行的。

价格低：极低成本

容量低：裸露介质，密度受限。

可靠性低，不要抱有太大的期望。

顺序读写：低，随机读写低。

光盘

通过激光扫过表面，就能读出坑的信息来。光盘最有趣的特性：容易复制。

光盘的坑是挖在透明塑料膜上的，压盘后上反射膜。

3s生产一张blue ray 100GB（33，000MB/s）写入速度。他的复制速度比任何存储介质来得快。

光盘价格低，容量高上百G（没有那么高），可靠性高（不能划伤有数据的那面）

顺序读硬盘，随机读低（很难写入）。最早光盘的大小是贝多芬的第九交响曲（74分钟） 。

因为是在空气中旋转，无法以较高的速度旋转。可以通过相变材料控制光盘是否可写。

现在甚至有技术可以在玻璃中间挖坑，实现上千年的存储。

固态

存储介质的致命缺陷

磁：机械部件（无法避免ms 机延迟）

坑（光）：挖坑效率低，填坑困难。

存储特性：价格低（大规模集成电路）。容量高，可靠性高：集成电路封装，不怕摔。SSD没有机械运动部件。

读写性能极高，且有极高的扩展性。（电路天然是必行的）。

而且容量大，速度快。买的容量越大速度就越快。ssd开启了u盘时代。

当flash memory越做越小的时候，可能会导致放电放不干净。这是一个致命的问题，比如充放电的次数过多时，电子可能永远无法被释放。

因此在上千次的操作下就会发生损坏。但是一个文件保存几千次，现在通常不会造成损坏。

这是因为SSD、u盘甚至tf卡里都藏了完整的操作系统。

每次写入擦除次数较少的那块区域。类似虚拟内存。因此随着时间的推移，整个硬盘会变的越来越慢。u盘在这个问题上尤为明显。

u盘，sd卡，ssd都是NAND flash。但是软件硬件的复杂程度不同，效率和寿命也不同。

因此不要买过渡便宜的硬盘。设备是可以伪造的，可以伪造乘另一个厂商的设备。甚至可以伪造容量。

存储系统经过多年的变化在操作系统中的抽象没有发生变化。

寻址能力需要付出代价，无论是磁盘还是电路。

解决方法就是按块访问。blocks devices也快要是普通的文件，可以直接mmap到进程地址空间。

如果做透明的抽象，就会导致读放大和写放大。因此linux做了BIO抽象

Request/Response接口。多个系统访问硬盘需要向BIO队列提交请求。下层BIO+驱动负责调度。一次请求可以读取很多块。block io会将请求转发给设备。

目录树管理

在存储器上，操作系统（文件系统）实现了目录树结构的文件系统，使我们能以直观的方式有序的操作数以万计的持久化对象。

磁盘=块（字节）序列

一本书：每一页纸存储了数据，支持随机访问。（翻到某一页）

文件是虚拟的磁盘

看不到一页纸的概念，支持read，write，lseek，ftruncate。那么如何彩礼操作系统众多文件。

信息的局部性：将磁盘文件组织成层次结构。分层索引就可以利用信息的局部性。所有以.开头的文件默认情况下ls都不展示，是隐藏文件。实际上隐藏.开头的行为不是操作系统的行为，只是为了偷懒。

因此就有了约定俗成的目录HFS filesystem Hierarchy standard。

macos有完整的poxis兼容层，因此不依赖linux特性则有可能在macos上运行起来。

目录树api支持增删改查

• mkdir 创建目录
• rmdir：删除目录
• getdents：读取目录

硬链接：系统中可能有同一个运行库的多个版本。可以理解为，一个数据起多个不同的名字。允许一个文件被多个文件引用。比如.是指向自己的，·..·是指向上级目录的。

软链接（符号链接），在文件里存储一个提示跳转，软连接也是一个文件，当引用这个文件时，去找另一个文件。类似windows的快捷方式。甚至可以用软链接来做状态机的状态迁移。软连接可以用来伪造文件系统。

Nix操作系统把所有的所有版本都集中存储。然后用符号链接构建完全虚拟的环境。完全确定性的构建任意环境。

文件系统文件描述符返回的就是文件。文件是操作系统中的对象

ls -l可以查看对象的属性，包含类型，权限，引用计数等。

有一个好用不火的操作系统特性叫做向量索引vectorfs。这是后加的特性，不是所有文件系统都支持。兼容性奇差，当cp文件时xattrs就会消失。需要cp --preserve=xattr。

UNIX/Linux一切都在/。windwos下一个驱动器一棵树。

linux的目录都在mount下，可以把块上的目录树放到已有的目录中。每次进行挂在的时候操作系统会创建一个新的回环设备。

Btrfs（B-tree File System，通常念作 "Butter FS"或 "B-tree FS"）是一种现代的高级文件系统，最初由 Oracle 开发，现已成为 Linux 内核的一部分。它被设计用于解决传统文件系统（如 ext4）的局限性，提供更强的数据管理功能、容错能力和可扩展性。

OverlayFs也叫UnionFS 联合挂载

看到的每个linux目录可能都是假的，在OverlayFS中

• lowerdir：只读层（修改会被丢弃）
• upperdir：可写层（修改会被保留）
• worker：操作系统用的临时目录

常用于容器场景，当修改下层文件时，OverlayFS会先将文件复制到上层（upperdir），再修改副本，原始文件保持不变。

我们可以用一个ubuntu的文件基础，来用overlayFS创建多个系统的复制。

文件系统可以看做是一个有向图。

文件系统实现

文件系统实现了树或图的目录结构，提供了丰富的API。让我们进行增删改查。实际上文件系统就是在存储系统之上实现一恶搞支持修改查询的数据结构，实现它是理所应当的。

块设备上的数据结构Abstract DataType（ADT）。就像我们在内存里做的一样。只不过不是随机访问内存。但是直接将磁盘映射到内存中，就会造成读放大写放大。

Logical volume manager（LVM）

Logical Volume Manager (LVM) 是Linux环境下的一种磁盘管理机制，它提供了比传统分区更灵活的磁盘管理方式。LVM允许将多个物理磁盘或分区组合成逻辑卷组，然后在这些卷组上创建逻辑卷，这些逻辑卷可以像普通分区一样使用。LVM可以在原有磁盘上扩展逻辑卷。LVM还支持快照功能。

5.25软盘单面160kib。有320个512B扇区。在这样的系统上选择什么文件系统呢？这样的情况下任何复杂的结构都会造成浪费。

文件实现方式 struct block *的链表，任何复杂的高级数据结构都显得浪费。

目录就是一个普通的文件，操作系统会把文件内容解读乘struct dentry[]

在每个数据块后放置指针：实现简单，无需单独开辟存储空间，但是数据大小不是$2^k$ 2的整数倍，lseek无限放大。（比如要定位最后一部分数据，需要重新从头扫描文件）

将指针存放在文件系统中的某个区域：局部性更好lseek更快。集中存放的数据损坏将导致数据丢失。

160K的软盘，有512字节的扇区。320个扇区，12bit entry，480B。只需要同一个扇区就能存下next[]，即便容量翻倍也就俩个扇区。

因此这个next方案也叫做，File allocation table：集中保存所有指针。

在内存里缓存一份FAT（天生一次也要读完512B）延迟写回，读写放大的问题就全解决了。因此采用将指针放在文件系统的某个区域的方案。集中存储的指针容易损坏？那存n份就行！延迟写会，写放大就不那么严重了。（存俩份FAT指针。）

在文件分配表（FAT）文件系统中，簇（Cluster）是磁盘空间管理的基本单位，也是操作系统分配存储空间的最小单元。

簇由一组连续的扇区（Sector）组成，大小由文件系统格式化时决定（如4KB、8KB等）。

FAT表通过记录簇的分配状态（空闲/占用）和文件占用的簇链（Cluster Chain）来管理文件存储。

FAT表中每个指针，在FAT12的时候是12个bit，16的时候是16个bit，FAT32是32个bit。FAT表本质是一个簇（cluster）链表，记录了每个簇的使用状态以及文件数据的存储位置。FAT表是一个链表。

隐式链表：FAT 通过簇号串联文件占用的物理簇，形成逻辑上的链表结构。例如：

文件 A 占用簇 2 → 簇 5 → 簇 8，则 FAT 表中：

FAT[2]=5, FAT[5]=8, FAT[8]=EOF。

类似数组形式，但是数组的value中会写着下一个索引号，来形成类似链表

这种设计允许文件数据在磁盘上非连续存储，通过 FAT 表动态追踪簇链。

FAT的目录就是个普通的文件。目录下面有很多目录项，每个entry都是固定长度的，前8个字节是文件名后三个字节是扩展名。之后还要一些扩展信息，比如最后修改时间，最后访问时间，创建时间。文件大小。还有最重要的first cluster指向的是FAT表。

访问目录，按照目录中的文件名定位到，FAT表的起始位置，通过FAT表的类似在数组中存链表的结构，按照自己的偏移量进行读取。最后按照fat表的块地址访问自己需要的文件。

但是如今看来8+3的文件名已经不够用了。还希望老系统能够兼容新系统就做出了调整。

FAT适合小文件，大大文件的随机访问就不太行了。4gb的文件跳到末尾有$2^{20}$次next操作，缓存能部分解决这个问题

在FAT时代，磁盘连续访问性能更佳，使用时间久了会产生磁盘碎片。维护若干个FAT副本防止元数据的损坏可能造成轻微写放大。

如今的UEFI分区文件格式还是FAT。

更号的文件系统：观察统计数据

• 大部分文件是2KB的小文件(配置文件)
• 平均文件大小上涨到了200K
• 大的文件越来越大
• 文件系统文件树越来越多
• 文件通常比较小,可能有20个文件或更小

然而FAT文件系统不支持硬链接。我们想支持任意大小文件的随机访问。因此我们需要结构化的node

iNode (index node）

保存ls -l里的各种metadata。它会在磁盘上专门的区域上划出一块空间来，存放inode，每个inode对应文件系统里的文件或者目录。

inode保存了文件持有者，访问时间，创建时间，组编号，最后修改时间等。在minix中就已经存在inode了。除此之外还有一个非常重要的数据结构。

将文件的偏移量映射到了块id

map<int,int>(file offset->block id)

如何设计这个map引入了ext2数据结构。

SuperBlock 文件系统的块级元数据。

inode数量，block_per_block以第一个superblock为准。

每个文件都有一个inode。比如小于等于40kb的文件可以直接查表，得到文件的位置。文件变大后可以做多级索引，类似b-tree的结构。越大的文件数量越小，中等大小的文件只需要用多1层索引，1层不够用用俩层。因此它兼顾了所有大小的文件。这个设计考虑了实际数据访问的概率分布。

ex2的目录文件，是在文件上的数据结构

map<string,int>(name->inode)

基本定位流程

从根目录开始：每个文件系统有一个固定的根inode（通常是inode 2）

逐级解析路径

读取目录文件内容（目录也是文件，有对应的inode）

在目录条目中查找下一级目录或文件名对应的inode编号

根据inode编号访问目标inode

ext2不是固定长度的文件。

ext2性能可靠性：

bitmap,inode都有集中存储的局部性，通过内存缓存来减少读写放大。通过将inode放在近似的位置，有很好的局部性。通过内存缓存可以减少读写放大。大文件支持O(1)的随机读写。支持链接（一定程度上减少空间浪费）inode在磁盘上连续存储，便于缓存、预取。依然有碎片问题.

但可靠性依然是很大的问题。

文件系统本质就是数据结构。因此数据结构可以不用实现在操作系统内核中。比如fuse filesystem in userspace。

任何数据结构都是可以的，比如B-Tree FileSystem。

安卓使用的f2fs（flash firendly），就是针对随机读写进行优化变成顺序读写。

还有华为的enhanced read -only FileSystem（erofs）

数据库系统

raid能用便宜的磁盘做可靠的存储系统。

数据结构的multi-write在崩溃时导致不一致状态。

崩溃一致性：数据结构的multi-write在崩溃时导致不一致的状态，通过flush机制和journaling实现崩溃的一致性。

当写入磁盘时会社区复杂数据结构。 当写入的时候需要更新inode，size，time，index，bwrite。实际上会有多个块操作。

所有的写请求都会先到达缓存，计算机系统会按照它认为最佳的顺序写入。HDD磁头的动态规划就是一个例子。如果只有一部分数据落盘，文件系统就会陷入不一致的状态。

因此有一个File System Checking的机制FSCK，根据磁盘上已有的G(V,E)恢复出最可能的数据结构。

操作系统提供了sync命令，用于让所有的数据刷盘后才会进行下一个操作。

fsync

其中有很多更细粒度的api，比如fsync去刷新指定文件描述符关联的数据和元数据。

sync>syncfs>fsync>fdatasync

在 Unix/Linux 中，若目标文件已存在，rename会原子性地替换它（前提是权限允许）。Windows 的 ReplaceFileAPI 也提供类似保证。

若进程在 rename前崩溃，原始文件保持完好；若在 rename后崩溃，新内容已原子生效。但是跨卷的操作可能是非原子的。

数据库

在单个文件中我们可以继续抽象。将所有数据写入一个文件中。但是文件系统并不可靠，需要fsync等API进行直接交互，还会存在效率问题。

一个简单的想法是利用目录树。这样我们就可以利用unix世界中所有的工具了。比如find，grep。甚至还可以做符号链接做数据关联。文件系统可以用flock做并发操作。数据故障时，数据不能丢。

我们希望并发性，持久性，原子性。我们想要比目录和文件更好用的API。

关系型数据库relational database。

一个非常简单的模型：a relational model of data for large shared data banks。每一行对象，都可以用id索引其他对象。

ACID数据库atomicity，consistency，Isolation，durability。

在很长一段时间内，数据库+raid是一种绝对可靠的设计。数据库还能额外支持事务，这个对原子性的支持非常重要。

实现

实现查询=实现编译优化。

Raid

没有一个绝对可靠谱的存储设备。比如内核panic，不分失效，ecc纠错失败。fail slow。

小概率事件的大量重复必然发生。

我们想用软件来实现高可靠。

A Case for redundant arrays of inexpensive disk(RAID)，后来也有人解读乘independent

把多个不可靠的磁盘虚拟成一个非常可靠而且性能高的磁盘。这是一个反向的虚拟化，把很多个资源虚拟为一个资源。

Raid成就了计算机系统的黄金时代。

Raid（虚拟化）=虚拟块到（磁盘，块号）的映射。虚拟磁盘块可以存储在任何物理磁盘上，物理磁盘可以读并行；存储>1份即可实现容错。

Raid-0：更大的容量、更快的速度

• 读速度x2；写速度x2，quiz

RAID-1镜像（容错）

• 保持俩块磁盘完全一样
• 读速度x2；写速度保持一致。

如果我们假设不会有俩块盘不会同时发生故障。比如机柜中一般有多个硬盘，当板卡发现磁盘故障时，会自动切换盘。

我们可以做到100块盘里，99块都是数据。

可以用异或对数据进行恢复。这样子任意的数据盘损坏都可以算出来，包括奇偶盘。但是奇偶计算会成为瓶颈。任何数据的写入都会导致partity的改变。

因此我们要让parity均匀分布在各个磁盘。至此Raid杀死了IBM 3380这样走可靠性的盘。

磁盘fail-stop：如何感知磁盘下线。软件会定期对磁盘的健康状态做检查。

raid物理磁盘不能完美同步，如果遇到断点了，可能会导致潜在的数据不一致。因此现在的raid卡都有电池。

GFS在上面做了更高层的抽象。谷歌做了个疯狂的事情，存下整个互联网的数据。(某种意义上谷歌的出现是必然的)

分布式RAID。阿里云elastic block storage（EBS fast 24）。磁盘可能出现fail-slow，对于特定负载或者所有负载，或者周期性的变慢。

bflush（Buffer Flush)

fsync 将文件数据和元数据（如 inode）从内核缓冲区强制写入物理磁盘，并等待磁盘确认完成。

磁盘上的数据通常是按块读写，而不是随机写。磁盘提供的接口。磁盘提供了接口。bwrite,bread,bflush。

磁盘可以在任何情况下出问题，但是我们可以检查理论上所有崩溃时的可能性。来做出对应的调整。FSCK可以用来恢复出最可能的数据结构。最早的时候，windows在突然断电后第一次启动都要这样做。