操作系统

小熊2026/2/5大约 73 分钟

操作系统

参考小林 Coding、王道考研操作系统视频

操作系统主要包括：进线程管理、内存管理、文件管理、设备管理。

基本概念

操作系统

操作系统是系统资源（软件资源、硬件资源）的管理者，向上层（用户、应用程序）提供方便的服务。

中断

中断是 CPU 暂停当前正在执行的应用程序，保留当前的执行状态，转而去内核态执行中断处理程序来处理紧急事件，处理完毕后，再返回到原程序被暂停的位置继续执行的过程。（简单来说就是中断当前正在进行的任务，去执行另一个任务。）

并发和并行

同时这个词有两个含义，也就是并发或并行。

并发：一个时间段内交替执行多个任务。单核 CPU 中某个时刻只能执行一个任务，每个任务执行一小段时间，就切换另外一个任务，由于 CPU 可以在极短的时间内轮流切换线程，从宏观上可以看成同时。
并行：真正意义的同时。多核 CPU 中多个任务可以同时被不同核心的 CPU 同时执行

单个 CPU 核心某一瞬间只能执行一个执行流，但 I/O 设备、DMA、硬件控制器可以和 CPU 并行工作。

异步

在多道程序环境下，允许多个程序并发执行，争抢系统资源，但是系统资源是有限的，所以进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进。

内核态和用户态

CPU 有两种状态：内核态、用户态

CPU 正在运行操作系统内核程序，就处在内核态，可以执行特权指令。正在运行用户程序，就处在用户态。

如何实现状态的切换？

内核态 -> 用户态：执行一条特权指令，修改 PSW 的标志位为用户态。

用户态 -> 内核态：由中断引发

中断包括内中断（中断信号来自 cpu 内部）、外中断。

内中断（异常）：当前执行的指令是非法的 / 应用程序请求操作系统内核的服务，就会引发一个中断信号，cpu 进入内核态。

外中断：时钟中断、IO 中断。比如当 DMA 把数据写入磁带完成后，磁带机会向 CPU 发送一个中断信号。
CPU 收到信号，会强行暂停当前正在运行的程序，把控制权交给操作系统，让操作系统来处理 “输出完成” 的善后工作。

内存空间分为内核空间和用户空间。

内核空间是操作系统内核访问的区域，独立于普通的应用程序，是受保护的内存空间。

用户空间是普通应用程序可访问的内存区域。cpu 在用户态，只能访问用户空间的数据，执行用户空间的代码；cpu 在内核态，可以访问用户空间和内核空间的数据，但是只能执行内核空间的代码。

系统调用

凡是与共享资源（进程之间共享）有关的操作（存储分配、分配回收内存、IO 操作（写磁盘文件，从网络接口读写数据）、文件管理），应用程序都需要通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。

操作系统结构

大内核：把操作系统主要功能模块都作为系统内核

微内核：只把与硬件紧密联系的模块作为内核

大内核的性能好，看下面这张图：

虚拟机

拓展：原子性：指令不可再分，也就是说 CPU 一旦执行这些指令就必须一口气执行完。

进程管理

PCB 进程控制块

进程的组成：

程序是如何运行的？程序运行前必须先放到内存中，才能被 CPU 处理。
image-20260326141631645

进程控制

管理系统中的所有进程。比如创建新进程、撤销已有进程、实现进程状态转换等等。

用原语实现进程控制。原语的原子性是如何实现的？用关中断指令和开中断指令这两个特权指令来实现。

进程创建：

进程终止：

进程阻塞和唤醒：

进程切换：

运行环境信息也就是进程上下文：进程在运行过程中寄存器存储的中间结果。当进行进程切换的时候，需要把当前的进程上下文保存在 PCB 中。

进程通信

共享存储：把同一块物理内存映射到了多个进程的虚拟地址空间里。多个进程通过这个物理内存进行通信。

消息传递：

直接通信方式：

间接通信方式：

管道通信：

进程只能互斥地访问管道。也就是说同一个时刻只能有一个进程对管道进行读写。这是由操作系统来实现的，不需要代码实现。而共享存储的互斥需要自己用代码实现。（互斥锁或者信号量）

进程同步

进程同步就是我们之前说的步调一致、协同工作，按一定次序执行。

进程互斥：

同时共享：比如进程 A 正在使用打印机资源，在使用的过程中，进程 B 试图访问打印机资源，操作系统会把 B 加入等待队列，在很短的时间片内让 AB 交替使用。如果是互斥共享，B 访问打印机资源会阻塞等待，B 必须等待 A 用完才能用。

进程互斥的四个原则：

忙等待的意思就是进程一直占用处理机资源，等待进入临界区，处理机一直处在忙碌状态，没办法为其他进程服务。

进程互斥

软件实现方法

进程互斥：只有进程 A 访问完打印机资源后，进程 B 才能够访问打印机资源。这就是互斥的使用资源，这就是进程互斥。也可以说进程 A 和进程 B 不能同时访问打印机资源，注意这里的同时是宏观上的同时。

互斥是同步的一种特殊形式。同步强调进程之间的协作关系，互斥强调对共享资源的排他访问。

单标志法：

缺点：

因此单标志法最主要的问题就是违背了空闲让进的原则。

双标志先检查法：

假如两个进程并发执行，0 进程先上处理机，执行完 1 后，时间片用完了，切换到 1 进程，执行 567，访问临界区。假如此时切换回 0 进程，0 进程接着执行 23，也会访问临界区。就发生多个进程同时访问临界区的情况了。

双标志后检查法：

Peterson 算法：

Peterson 算法遵循了空闲让进、忙则等待、有限等待三个原则，但是没有遵循让权等待的原则。（比如按 16278 的次序并发执行 0 和 1 进程。1 号进程会卡在 while 循环，白白浪费 CPU 资源，直到时间片用完。）

动手：按不同的顺序执行会发生什么？
123678
1623
13678
16278

总结：

硬件实现方法

中断屏蔽方法：

为什么不适合用在多处理机。因为某个处理机执行了关中断，在这个处理机上运行的进程就不会被中断，会访问临界区；假如另一个处理机上运行的进程也需要访问临界区，就会发生多个进程同时访问临界区的情况。

TSL 指令：

swap 指令：

总结：

锁

多处理器系统中，若上锁时间短，则等待时间很低：如果一个处理器上有一个进程正在循环等待上锁，另一个处理器有一个进程上锁，使用临界区并快速解锁。那么循环等待上锁的进程不会等很长时间。如果不是忙等，假如等不到锁就下处理器，那么会发生进程切换，系统开销大。所以忙等也是有好处的。

信号量机制

wait 逻辑实际和双标志先检查法是一样的，只不过双标志先检查法中的检查和上锁不是一口气完成的。这里通过原语 wait 实现一口气完成。

wakeup 原语唤醒等待队列中的一个进程，并且刚才释放的资源会被分配给该进程。

用信号量机制来实现进程同步、互斥。

有一些系统资源是需要进程互斥访问的，也就是不能同时访问。访问这种互斥资源的代码称为互斥区。某个时间段只能有一个进程处于临界区。这就是进程互斥。
进程同步：就是让并发的进程按一定的次序执行。

实现进程互斥：

信号量 mutex 代表进入临界区的名额数，初始是 1。如果一个进程对 mutex 执行 P 操作，意思就是该进程申请进入临界区的名额。由于名额数初始是 1，所以该进程能成功申请到名额。

实现进程同步：

上述进程同步场景是：代码 2 必须在代码 4 之前执行。如何实现这种同步？在前操作之后执行 V 操作；在后操作之前执行 P 操作。

总结：

信号量实现进程互斥，初始值是 1；实现进程同步，初始值是 0。

经典问题

生产者消费者问题：

缓冲区属于临界资源，代表在某个时间段不能有多个生产者进程往里面写数据。比如进程 A 发现缓冲区没满，打算往里面写数据，此时时间片用完了，发生了进程调度，进程 B 上处理机运行，往缓冲区写数据。之后 CPU 切换到进程 A，写数据。很可能把 B 写的数据覆盖掉。

image-20260628125707305
image-20260628125822773

死锁的情况：

多生产者 - 多消费者模型

多种类别的生产者和消费者。

即使不专门设置 mutex，也不会出现多个进程同时访问盘子的现象。

原因在于：本题中的缓冲区大小为 1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是 1。因此在任何时刻，最多只有一个进程的 P 操作不会被阻塞，并顺利地进入临界区...

父亲已经通过 P (plate)，准备往盘子里放苹果；母亲也已经通过 P (plate)，准备往盘子里放橘子。母亲将橘子放入盘子中，还没有更新缓冲区指针，此时 CPU 发生进程调度，切换到父亲，由于缓冲区指针没有更新，因此父亲很可能把苹果放入同一个位置，导致数据覆盖。有了 mutex 之后，母亲把橘子放入盘子并更新缓冲区指针后，父亲才可能会把苹果放入盘子。
把水果放入盘子类似下面的代码：
buffer[in] = fruit;//放入盘子
in = (in + 1) % 2;//更新缓冲区指针

读者 - 写者问题

我觉得 3 其实覆盖了 2。如何理解 2 呢，在某一个时间段内只允许一个写者往里面写信息。（比如进程 A 往里面写数据写到一半，cpu 发生进程调度，切换到进程 B，此时进程 B 是不可以写数据的。之后 cpu 切换到 A，A 把数据写完。之后 B 才能写数据。从 A 开始写到写完这一个时间段，只允许 A 往里面写数据。）只有该写者写完了才允许其他的写者去写。视频中说的是同一时刻只允许一个写者往里面写信息，其实说法不对。

如何满足多个读者同时（宏观上的同时）对文件执行读操作的要求：

由第一个读进程负责读之前加锁；由最后一个读进程负责读完了解锁。但这种方式存在问题：比如读者 1 先判断 if，if 成立，执行 P 操作前，进程发生切换，读者 2 判断 if，执行 p 操作，rw 变成 0。然后将 count 加 1。此时 cpu 又切换到读者 1，读者 1 执行 P 操作，由于 rw 是 0，所以读者 1 会阻塞。这样就没有实现多个读者同时对文件执行读操作。

产生这种问题的原因：多个读进程同时（宏观上的同时，不是真的同时，比如单核处理器，进程只能并发执行，某个时刻只能有一个进程访问 count。）对 count 进行访问。

解决方法：设置一个互斥信号量保证读进程对 count 的访问是互斥的。

还存在潜在的问题：只要有读进程还在读，写进程就要一直阻塞等待，可能 “饿死”。因此，这种算法中，读进程是优先的。

可以再设置一个互斥信号量 w，用于实现写优先。仔细分析下读者 1 - 写者 1 - 读者 2 这个并发顺序。

总结：读者 - 写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个 / 最后一个读进程，从而做出不同的处理。

另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现 “一气呵成”，自然应该想到用互斥信号量。

最后，还要认真体会我们是如何解决 “写进程饥饿” 问题的。

哲学家进餐问题

和之前的问题的区别：每个进程需要持有两个临界资源，才能顺利执行某个动作。

先看一种代码形式：如果 0 号哲学家拿了左边的筷子（执行 P 操作），cpu 发生进程切换，切换到 1 号哲学家，也拿起了左边的筷子，依次进行，所有的哲学家都拿了左边的筷子。之后 cpu 切换回 0 号哲学家，此时拿右边的筷子，由于右边的筷子被 1 号哲学家拿了，所以 0 号哲学家会阻塞等待，其它哲学家也同理，造成了死锁。

解决方法：

还有一种解决方法：仅当一个哲学家左右两只筷子都可用时，才允许拿起筷子。设置一个互斥信号量 mutex，拿筷子前进行 P 操作；拿筷子后进行 V 操作。

来看几种并发顺序：假如 0 号哲学家拿了左右两双筷子；进程切换，1 号哲学家拿左边筷子，执行 P 操作发生阻塞；进程切换，2 号哲学家会阻塞在 P (mutex)。尽管 2 号哲学家左右两只筷子都可用，也暂时拿不到。

假如 0 号哲学家拿了左右两双筷子；进程切换，4 号哲学家拿左边的筷子，可以拿；拿右边筷子发生阻塞。虽然 4 号哲学家左右两只筷子不是都可用，但 4 号也允许拿筷子。和前面说的解决方法不一致。

更准确的说法应该是：各哲学家拿筷子这件事必须互斥地执行（一个进程只有左右筷子都拿到后，其它进程才能拿筷子。）。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

再来理解下同时的含义。“同时访问” 指的是：一个进程对共享资源的访问还没结束，另一个进程也开始访问了。

管程

共享数据数据结构：可以理解成生产者消费者模型中的缓冲区。管程类似 C++ 中的类，过程就是类中的方法；数据结构就是类中的数据。
管程第三个特征是什么意思？进程是互斥访问管城的过程的。（一个进程访问完管程的某个过程，其它进程才能访问）

如何互斥的访问缓冲区；缓冲区满了之后，生产者进程如何处理；缓冲区空的时候，消费者进程如何处理等等，这些问题都由管程来解决，不需要生产者消费者进程自己写处理逻辑。

总结：

死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是 “死锁”。

发生死锁后若无外力干涉，这些进程都将无法向前推进。

多个进程访问内存是允许的；只有访问同一份共享数据并且会修改时，才需要互斥。扬声器也不会导致死锁，因为多个程序可以同时播放声音：它们不是直接抢占扬声器，而是把音频数据交给操作系统或音频服务，系统把多个声音混合后输出。
循环等待未必死锁，如何理解：因为有些资源不是只有一个实例。
比如资源 R1 有 2 个，资源 R2 也有 2 个。
进程P1 拿着一个 R1，等待 R2
进程P2 拿着一个 R2，等待 R1
看起来：
P1 等 R2
P2 等 R1
好像有环。但如果系统里还剩一个空闲的 R1 或 R2 ，操作系统仍然可以分配给某个进程，让它继续执行、释放资源，整个系统就能解开。

总结：

死锁的处理策略 —— 预防死锁

为什么不会出现死锁现象：
缺点 2 如何理解：比如 P3 进程需要先使用 7 号打印机资源，之后再使用 5 号资源。但是申请资源的时候只能先申请 5 号资源，等用完 7 号资源后才会用 5 号资源，导致 5 号资源有很长一段时间的空闲期。

死锁的处理策略 —— 避免死锁

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）。

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态（如何判断是否进入不安全状态，只需检查资源分配后系统能否找到一个安全序列），以此决定是否答应资源分配请求。这也是 “银行家算法” 的核心思想。

安全性算法

找不到安全序列的情况：

银行家算法流程：

死锁的处理策略 —— 检测死锁和解除死锁

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。

如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。

相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程。

如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）

如果不能消除所有边，那就代表发生了死锁。比如下面这个图就不能消除所有边：

不阻塞：该进程申请的资源小于等于系统空闲资源数量，就不会发生阻塞。
死锁检测的核心：依次消除与不阻塞进程相连的边，直到无边可消。

信号

信号处理的时机：

如何处理信号：

执行信号处理函数的时候，pending 位就已经置 0 了，而不是处理完才置 0。

信号和异常的关系：

线程

线程的属性：

线程的实现方式：用户级线程内核级线程。

用户级线程：代码逻辑层面的线程。在操作系统眼里还是只有进程的概念，只是我们在代码中用线程库实现了多线程。

内核级线程：操作系统支持的线程。

多线程模型：三种模型

下面这个多线程模型：一个进程对应一个内核级线程，一个内核级线程包含多个用户级线程。这种模型其实就是前面讲的用户级线程。

如果只有进程，在一个进程里面完成听歌、打视频。cpu 调度的基本单位是进程，那么听歌的代码被阻塞，就不能执行打视频的代码了。如果把进程划分为多个线程，cpu 调度的基本单位是线程，那么听歌这个线程被阻塞，CPU 可以执行打视频这个线程。而且在多核处理器中，这两个线程还能并行执行。

线程的状态转换

要管理线程，需要给线程对应的一个数据结构，就是 TCB。类似进程中的 PCB。

切换线程的时候，需要保存线程的运行环境（保存到 TCB 中）。比如程序计数器、堆栈指针、其它寄存器。切换回这个线程时需要从 TCB 中恢复运行环境。

调度

操作系统的三大调度机制，分别是「进程调度 / 页面置换 / 磁盘调度算法」。

调度的三种层次

调度的三个层次：高级调度（从外存调入内存中）、低级调度（cpu 执行哪个进程）、中级调度（哪些进程重回内存）。

进程的挂起态：
一个处于就绪态的进程，如果此时系统负载高、内存不够了，就会把该进程的数据放到外存中，进程进入了就绪挂起态。阻塞态的进程也可能被挂起。运行态进程运行结束后，可能会直接放到外存中，进入就绪挂起态。创建态进程创建完成后，假如内存空间不足，也会进入就绪挂起态。

总结：

进程调度

接下来是进程调度的内容：（进程调度就是内存中有多个进程时，CPU 会先执行谁，后执行谁，按什么顺序）

为什么没办法顺利进行进程调度。因为进程调度代表 CPU 需要从就绪队列中选一个进程来执行。由于之前的进程在访问就绪队列，给它上锁了，所以 CPU 访问不到就绪队列，因此无法顺利进行进程调度。

当一个进程正在使用处理机时，能否强行剥夺处理机，取决于进程调度的方式。

对原来运行的进程数据进行保存：保存到 PCB 中；对新的进程数据进行恢复：从 PCB 中读取进程相关数据，放到相应的寄存器中。

总结：

调度器

调度器：操作系统内核中一个很重要的模块。

调度时机中的 I/O 中断有可能是这种情况：进程等待 I/O 事件，进入阻塞态。假如 I/O 中断了，就会从阻塞态进入就绪态，就绪队列发生改变，会触发调度程序。（这段话不一定对）
抢占式调度策略：时钟中断或 k 个时钟中断会触发调度程序，让调度程序检查就绪队列有没有新进程到达，考虑是否让他抢占 CPU，上处理机运行。

闲逛进程：

调度算法

接下来讲解具体的调度算法。

补充个名词：饥饿。某个作业 / 进程长时间得不到服务，就说作业 / 进程处于饥饿状态。

时间片轮转算法

![image-20260627125913121](/Users/xubenshan/Library/Application Support/typora-user-images/image-20260627125913121.png)

进程响应时间：

优先级调度算法

抢占式优先级调度算法：当就绪队列发生改变的时候，调度机需要检查新的进程优先级是不是比当前运行进程的优先级高，如果高就会发生抢占。

多级队列调度算法

交互式进程优先级为什么比批处理进程要高：在交互式进程场景下，用户需要得到比较及时的响应和反馈。所以优先级应该设高点。
进程调度时选择哪个队列，确定好队列后，选择队列中的哪个就绪进程（队列内的调度策略）上处理机执行。

多处理机调度

每个 CPU 空闲时运行调度程序，从公共就绪队列中选一个进程运行。
为什么要对公共就绪队列上锁：因为多个 CPU 是并行运行的，当两个 CPU 都空闲时，同时执行调度程序，都选择优先级最高的进程，比如进程 1，这样就会发生冲突。所以要上锁。

私有就绪队列天然的实现了处理机亲和性。

总结：

内存管理

前置知识

程序需要加载到内存中，才能被 CPU 执行。为什么不能放在外存（磁盘）执行呢？因为读写磁盘的速度很慢，而 CPU 处理速度很快。这样就不能完全发挥 CPU 的性能。

可见，我们写的代码要翻译成 CPU 能识别的指令。这些指令会告诉 CPU 应该去内存的哪个地址读 / 写数据，这个数据应该做什么样的处理。在这个例子中，我们默认让这个进程的相关内容从地址 #0 开始连续存放，指令中的地址参数直接给出了变量 × 的实际存放地址（物理地址）。

思考：如果这个进程不是从地址 #0 开始存放的，会影响指令的正常执行吗？会影响。
image-20260629122235697
为了解决该问题，有三种装入策略：
image-20260629123652688
绝对装入只适合单道程序，当时还没有操作系统，所以装入模块中的物理地址是由编译器完成的。
image-20260629123833050
可重定位装入又叫静态重定位；动态运行时装入又叫动态重定位。
image-20260629124126908

链接的三种方式：

基本概念

什么是内存管理？要管哪些东西呢？

内存保护：

程序被加载到内存，变成了进程。进程只能看到虚拟地址空间。为什么需要虚拟地址空间？如果使用真实地址，两个进程可能会发生冲突。如果一个程序在 2000 位置写入了数据；另一个程序又在 2000 位置写入，就会覆盖掉原先的值。另外真实物理地址空间很小，运行不了很多程序。如果给每个进程分配一个虚拟地址空间，这样进程之间就隔离开来了，不会互相影响，而且能运行的程序也变多了。

但是 CPU 是要访问真实物理地址的，那么如果将虚拟地址映射到物理地址呢，需要用 CPU 中的内存管理单元 MMU。

操作系统如何管理虚拟地址和物理地址之间的关系？

采用内存分段、内存分页两种方式。

先来看内存分段：

将程序分为栈段、堆段、数据段、代码段等，每个段有自己的属性。为什么会产生外部碎片。

因为程序在内存中是连续的，假如系统有多个进程的话，就会产生大量的小碎片，构不成连续的内存空间。

下面是内存分页：

将虚拟地址和物理地址进行分页，每个页面的大小是 4KB，物理地址的页，叫页框。虚拟地址的页就叫页。

MMU 需要一个东西用来记录虚拟地址页到物理地址页框的关系。叫做页表。页表存储在内存中。

进程的内存映像

32 位系统，默认地址总线是 32 位，这样地址总数就是 2 的 32 次方。按字节寻址（一个地址代表的存储单元大小是一字节），地址空间大小就是 2 的 32 次方 B，也就是 4GB。

注意宏定义的常量不会存储在紫色区域，紫色区域存储的常量是 const 修饰的变量或者常量字符串。宏定义的常量不会分配内存空间。

内存空间扩充 —— 覆盖、交换技术

主要讲两种技术：覆盖技术交换技术。后面还会讲虚拟存储技术。

B 模块和 C 模块不会同时被调用（B 模块调用完后才会调用 C 模块）
覆盖技术的缺点：必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点：对用户不透明，增加了用户编程负担。

交换技术：交换（对换）技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存（进程的 PCB 会保存在内存中，形成挂起队列），把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

问题：

应该在外存（磁盘）的什么位置保存被换出的进程？
什么时候应该交换？
应该换出哪些进程？

内存空间分配与回收

连续分配：指为用户进程分配的必须是一个连续的内存空间。连续分配管理方式：单一连续、固定分区、动态分区。

单一连续分配：

固定分区分配：

动态分区分配：动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。（eg：假设某计算机内存大小为 64MB，系统区 8MB，用户区共 56 MB.)

）

系统要用什么样的数据结构记录内存的使用情况？
当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
如何进行分区的分配与回收操作？

缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有 “大进程” 到达，就没有内存分区可用了。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）

首次适应和邻近适应算法开销小指的是：当空闲分区发生变化时，不用重新排列空闲分区链或空闲分区表。

如何进行分区的回收：在回收分区的时候，如果发现该分区上下有相邻的空白分区，则需要把这些空白分区进行合并，也就需要修改空闲分区表或者空闲分区链。

紧凑技术：就是移动进程占用的内存空间，产生一个连续的大内存空间。

基本分页存储管理

属于非连续分配管理方式。

非连续：给进程分配的是不连续的内存空间

进程没被调度时：页表存放在内存中，页表始址和页表长度等信息存放在进程控制块 PCB 中。进程被调度运行时：操作系统把该进程页表基址装入 CPU 页表寄存器。

问题：

页表是存放在内存中的。每个页表项多大？占几个字节？
如何通过页表实现逻辑地址到物理地址的转换？

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）。为什么呢，看下面这张图：

由于页号是隐含的，因此每个页表项占 3B，存储整个页表至少需要 3*(n+1) B

注意：页表记录的只是内存块号，而不是内存块的起始地址！J 号内存块的起始地址 = J * 内存块大小

这三个步骤第二步我们前面学了，需要通过查找页表，找到页号对应的块号。知道块号就知道了 P 号页面对应的物理块的起始地址。（P 号内存块的起始地址 = P * 内存块大小）

接下来就是如何确定一个逻辑地址对应的页号、页内偏移量（页内偏移量表示：这个地址在该页内部距离页首地址有多少个字节。）？

结论：如果每个页面大小为 2 的 k 次方 B，用二进制数表示逻辑地址，则末尾 K 位即为偏移量，其余部分就是页号。

总结：页面大小刚好是 2 的整数幂有什么好处？
①逻辑地址的拆分更加迅速 —— 如果每个页面大小为 2 的 k 次方 B，用二进制数表示逻辑地址，则末尾 k 位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为 2 的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。
②物理地址的计算更加迅速一 — 根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。

接下来讲解用于逻辑地址和物理地址之间转换的一组硬件机构。

逻辑地址 A 到物理地址 E 的转换过程：

设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下：
①计算页号 P 和页内偏移量 W（如果用十进制数手算，则 P=A/L，W=A% L；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量）
②比较页号 P 和页表长度 M，若 P≥M，则产生越界中断，否则继续执行。（注意：页号是从 o 开始的，而页表长度至少是 1，因此 P=M 时也会越界）
③页表中页号 P 对应的页表项地址 = 页表起始地址 F + 页号 P 页表项长度，取出该页表项内容 b，即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间；页面大小指的是一个页面占多大的存储空间）
④计算 E=bL+W，用得到的物理地址 E 去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了）

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址 F 和页表长度 M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

基本地址变换机构中地址变换过程涉及两次内存访问：找页表项时需要访问内存；访问物理地址对应的内存单元。

具有快表等地址变换机构：

快表，又称联想寄存器（TLB，translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（TLB 不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

快表的工作流程：（0，0）（0，4）这些逻辑地址第一项是页号，第二项是页内偏移。

引入快表后：

①CPU 给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到 90% 以上。

局部性原理：

由于循环，程序会反复访问存放循环体指令的页面；由于数组连续存放，程序会连续访问存放数组元素的页面或相邻页面。

TLB 和普通 Cache 的区别 ——TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本

根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

单级页表存在的问题：

问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

想访问的页面指的是逻辑地址的页面。比如 CPU 执行某条指令要访问某个逻辑地址，该地址对应 3 号页面。但 3 号页面对应的数据 / 指令还没有调入内存。于是产生缺页中断，把这个虚拟页从磁盘 / 外存调入内存。

两级页表的访存次数分析（假设没有快表机构）

第一次访存：访问内存中的页目录表
第二次访存：访问内存中的二级页表
第三次访存：访问目标内存单元

基本分段存储管理

分段中的段号和段内地址通常由 CPU 指令中的逻辑地址格式直接给出，而不是像分页那样用 “逻辑地址 / 页面大小逻辑地址 % 页面大小” 算出来。

段页式管理方式

段页式管理方式中逻辑地址和物理地址的映射过程：

虚拟存储技术

虚拟内存：

如何实现虚拟内存技术：

请求分页存储管理

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

目标页面未调入内存：当前指令要访问的某个虚拟页，此时还没有对应的有效物理页框，也就是页表中该虚拟页对应的页表项 present/valid 位为 0。

请求分页的地址变换过程：

产生缺页中断时，需要保留 CPU 现场，进程阻塞，等调页完成后，唤醒该进程，进程进入就绪队列。等该进程重新上处理机运行时，需要恢复 CPU 现场信息。
CPU 进行地址变换时，若快表命中，则直接使用快表项形成物理地址，不需要访问慢表。但如果 CPU 在快表中修改了访问位或修改位，这些状态最终需要同步回慢表，否则操作系统在页面置换时查看慢表，可能得到过期信息。
快表 TLB 里的页表项被修改后，不必每次都立刻同步到内存中的页表；可以先只改快表，等这个快表项被替换 / 删除 / 失效时，再把修改后的状态写回慢表。删除快表项不代表删除页面，有可能 TLB 空间有限，新的页表项要进来，所以需要删除一些旧的页表项。

总结：

页面置换算法：

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

在扫描的过程中，如果某个页访问位为 1，需要将它置为 0。如果某个页访问位为 0，就将它换出到外存。将新进来的页访问位置为 1。
只要某页被访问，它的访问位就会被修改为 1。算法里面没有提到这个，因为算法关注的是页面置换扫描过程。只说明了扫描过程中页的访问位如何变化。

算法	算法规则	优缺点
OPT	优先淘汰最长时间内不会被访问的页面	缺页率最小，性能最好；但无法实现
FIFO	优先淘汰最先进入内存的页面	实现简单；但性能很差，可能出现 Belady 异常
LRU	优先淘汰最近最长时间没访问的页面	性能很好；但需要硬件支持，算法开销大
CLOCK（NRU）	循环扫描各页面。第一轮淘汰访问位 = 0 的页面，并将扫描过的页面访问位改为 0。若第一轮没选中，则进行第二轮扫描。	实现简单，算法开销小；但未考虑页面是否被修改过
改进型 CLOCK（改进型 NRU）	若用（访问位，修改位）的形式表示，则：第一轮：淘汰（0，0）第二轮：淘汰（0，1），并将扫描过的页面访问位都置为 0 第三轮：淘汰（0，0）第四轮：淘汰（0，1）	算法开销较小，性能也不错
LFU	优先淘汰访问次数最少的页面	能反映访问频率；但不能很好反映最近访问情况，可能长期保留过去频繁访问但当前不再使用的页面

页面分配策略

如果程序并发度下降，就会导致资源利用率不高。（CPU 和 IO 设备理论可以并行工作。如果内存中有很多进程，并发度高，有些是计算密集型，有些是 IO 型，比如有 3 个进程：进程 A：正在用 CPU 计算；进程 B：正在等待磁盘 I/O；进程 C：正在等待网络 I/O。 B、C 可以让磁盘、网卡等 I/O 设备工作；与此同时，CPU 可以去执行 A。这样就能充分利用 CPU 和 IO 设备。）

系统会锁定一些页面，这些页面中的内容不能置换出外存（如：重要的内核数据可以设为 “锁定”）

程序在没有运行之前，是存放到磁盘的文件区的。

抖动现象：

总结：

内存映射文件

内存映射文件 — 一操作系统向上层程序员提供的功能（系统调用）

方便程序员访问文件数据
方便多个进程共享同一个文件

调用 mmap 后，那么文件内容会映射到进程虚拟地址空间中的内存映射区。注意内存映射只是建立了文件数据和虚拟内存之间的映射关系，并没有真的把文件数据放入内存中。当需要访问某个文件数据时，需要通过缺页中断把文件页调入内存。

为什么说文件数据的 IO 操作完全由操作系统负责：因为程序员不再显式调用 read() 、 write() 来搬运文件数据，而是由操作系统负责把文件内容调入内存、把修改后的内容写回磁盘。

char *p = mmap(...);//得到内存映射的起始位置
char c = p[0];   // 读文件内容
p[10] = 'A';     // 修改文件内容 用操作内存的方式操作文件。

//内存映射场景下访问文件的流程：
进程访问 p[0]
  ↓
p[0] 属于进程虚拟地址空间中的某个虚拟页
  ↓
发现这个虚拟页还没有对应的物理页框
  ↓
发生缺页中断
  ↓
操作系统从磁盘读取文件对应部分
  ↓
把数据放入物理内存中的某个物理页框
  ↓
修改页表：虚拟页 → 物理页框
  ↓
进程继续访问 p[0]

内存碎片分为外部内存碎片和内部内存碎片。外部碎片是指未使用的内存块太分散了，没有足够大的连续内存空间。内部碎片是指分配的内存有一些空闲的。比如在内存对齐场景下，程序分配了 12 个字节，但有些字节没有存储数据。

内存分段容易产生外部碎片；内存分页容易产生内部碎片。

页面置换算法：由于进程虚拟地址空间中的页全部映射到物理内存中，所以当进程需要访问某个在物理内存中不存在的页时，就会触发缺页中断，进行虚拟地址和物理地址之间的映射，将该页加载到内存中。如果内存满了，操作系统会将一些不常访问的页从内存放到磁盘中，该将那些页放入瓷盘中，就涉及到了页面置换算法。

在 linux 系统下，虚拟地址空间被分为了 0-4G，地址从低往高分别是代码区、常量区、全局 / 静态区（已初始化的、未初始化的）、堆、栈、内核区。

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

Linux 相当于屏蔽了 CPU 逻辑地址的概念，只显示了虚拟地址空间。

调度篇

文件管理

文件初识

文件 —— 就是一组有意义的信息 / 数据集合

计算机中存放了各种各样的文件，一个文件有哪些属性？文件内部的数据应该怎样组织起来？
文件之间又应该怎么组织起来？

从下往上看，OS 应提供哪些功能，才能方便用户、应用程序使用文件？从上往下看，文件数据应该怎么存放在外存（磁盘）上？

总结：

文件的逻辑结构

所谓的 “逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而 “物理结构” 指的是在操作系统看来，文件
的数据是如何存放在外存中的。

类似于数据结构的 “逻辑结构” 和 “物理结构”。如 “线性表” 就是一种逻辑结构，在用户角度看来，线性表就是一组有先后关系的元素序列，如：ab, c, d, e ……
“线性表” 这种逻辑结构可以用不同的物理结构实现，如：顺序表 / 链表。顺序表的各个元素在逻辑上相邻，在物理上也相邻；而链表的各个元素在物理上可以是不相邻的。因此，顺序表可以实现 “随机访问”，而 “链表” 无法实现随机访问。

根据有结构文件中的各条记录在逻辑上如何组织，可以分为三类：顺序文件、索引文件、索引顺序文件。

在可变长记录中，需要额外空间存放每条记录的长度。
如果我要找第 i 条记录的起始位置，那么就需要知道前 i 条记录占用的空间大小。所以不能实现随机存取。
为什么串结构的顺序文件增加 / 删除一个记录比较简单：增加记录的时候可以把该记录直接放在最后。删除记录的时候可以把最后一个文件放到删除的位置。

顺序文件：默认就是顺序存储的文件。顺序文件有串结构、顺序结构。不同点：是否按关键字顺序排列。不定长记录的顺序文件无法实现随机存取（不用从第 1 条记录开始一条一条往后读，而是可以直接跳到某个位置读取。）。因此出现了索引文件。就是给每条记录建立一个索引项，索引项构成了索引表。索引表是定长的顺序文件。但索引表可能会占用比文件还要大的内存空间。所以出现了索引顺序文件。把记录进行分组，每个分组对应一个索引项。如果文件记录很大的话，为什么提高查找效率，可以建立多级索引表。

文件目录

目录文件中的每条记录就是一个文件控制块（FCB）。一个 FCB 就是一个文件目录项。FCB 的有序集合称为文件目录。

目录类型文件在外存中存放的是 “目录项集合”，也就是这个目录下面有哪些文件 / 子目录，以及它们对应的 FCB 或物理位置信息。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了 “无环图目录结构”。

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据 “存放位置” 即可找到文件。
存放在外存中的索引结点称为 “磁盘索引结点”，当索引结点放入内存后称为 “内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

文件的物理结构

顺序访问：要想访问文件块 2，需要先访问文件块 0、文件块 1。
随机访问：要想访问文件块 2，可以直接访问，不需要访问它前面的文件块。

连续分配方式要求每个文件在磁盘上占有一组连续的块。
优点：支持顺序访问和直接访问（即随机访问）；连续分配的件在顺序访问时速度最快缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片

读入 i 号逻辑块，总共需要 i+1 次磁盘 I/O，这里没有把查找 FCB 的磁盘 I/O 算进去。
它默认的是：FCB 已经找到，或者已经在内存中。

采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。

由于在开机的时候 FAT 是常驻内存的，所以逻辑块号转换成物理块号不需要磁盘 IO 操作。

每个索引块额外存储了指针，也就是下一个索引块地址。如果想得到逻辑块号 256 对应的物理块号，就需要先将 7 号索引块读入内存，得到指针信息，再将 15 号索引块读入内存。

总结：

文件存储空间管理

文件基本操作

文件共享

文件保护

文件系统层次结构

文件系统全局结构

虚拟文件系统

设备管理

IO 控制器

数据交换中的 “输出” 指的是主机向 IO 设备发送数据这个方向。

从图能看出控制器和设备之间的接口可能不止一个，所以一个 IO 控制器可能控制多个 IO 设备。
cpu 通过控制线，向 IO 控制器发出一个具体的 IO 指令。同时通过地址线，向 IO 控制器说明自己要操纵的是哪个设备。如果 CPU 要输出数据，则需要通过数据总线，把数据写入数据寄存器。然后 IO 逻辑从寄存器中取得该数据，通过控制器与设备的接口输出到具体的设备中。IO 指令可能会有一些参数，会放到控制寄存器中。为了实现对设备的管理，CPU 还会从状态寄存器中读出各个设备的状态。

值得注意的小细节：①一个 I/0 控制器可能会对应多个设备；
②数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制 / 状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便 CPU 操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像 I/O；另一些计算机则采用 I/O 专用地址，即寄存器独立编址。

IO 控制方式

即：用什么样的方式来控制 I/O 设备的数据读 / 写

程序直接控制方式：cpu 不断轮询。

为什么 CPU 读到 IO 设备的数据时，还要将数据转存到内存中。具体原因见上图 C 程序。比如 scanf，cpu 从键盘中读取一个数之后，需要把这个数赋值给变量 a，变量 a 是在内存中的。也就是说数据会被写到某个内存单元中。

CPU 每次从 I/O 数据寄存器读取数据时通常只读一个字；但一次 I/O 请求或一次启动 I/O 的读命令（CPU 告诉 I/O 控制器：开始进行读操作。），可以对应多个字的连续传输，

I/O 请求：操作系统 / 程序层面的 “一次任务”
在操作系统教材的抽象模型中，一次 CPU 的 I/O 读指令通常只从 I/O 数据寄存器读取一个字 / 一个数据单位；如果一次 I/O 请求要读多个字，就需要多次这样的读指令。

为什么说 CPU 和 IO 设备只能串行工作：不是说 IO 工作的时候，CPU 不工作。而是说在程序直接控制方式下，CPU 必须全程参与 I/O 操作，不能脱身去执行别的任务。CPU 利用率低，因为 CPU 的大量时间花在了等待设备、查询状态、搬运数据。

中断驱动方式：

IO 完成后，CPU 可以先让等待 IO 的进程从阻塞态变成就绪态，也可以直接恢复该进程的运行环境，从阻塞态变成执行态。

缺点：

每个字在 I/O 设备与内存之间的传输，都需要经过 CPU。
I/O 设备每准备好一个字，通常就向 CPU 发一次中断（教材的理解），请求 CPU 来处理这个字。所以如果有大量的数据，需要进行频繁的中断处理会消耗较多的 CPU 时间。
大致流程：

程序发出IO请求，假如要读3个字
        ↓
I/O 设备准备好第 1 个字
        ↓
设备发中断
        ↓
CPU 执行中断服务程序，把第 1 个字读到内存
        ↓
I/O 设备准备好第 2 个字
        ↓
设备再次发中断
        ↓
CPU 把第 2 个字读到内存
        ↓
I/O 设备准备好第 3 个字
        ↓
设备再次发中断
        ↓
CPU 把第 3 个字读到内存
        ↓
本次 I/O 请求完成

DMA 方式：

DMA 控制器在完成一个数据块或多个数据块传输后，向 CPU 发出中断。告诉 CPU 可以进行后续处理了，比如更新进程状态、唤醒等待 I/O 的进程、检查传输结果、准备下一次 I/O。

DMA 控制器内部每次读取数据的单位还是字，会把读取的字放到寄存器中暂存，所有的字读取完了再传给内存。

每次读写只能是连续的块，如果想读取离散的几个块，那就需要 CPU 发出多次 IO 指令。

缺点：CPU 每发出一条 I/O 指令，只能读 / 写一个或多个连续的数据块。

通道控制方式：

总结：

IO 软件层次结构

设备独立性软件要实现的功能：

向上层提供系统调用。
设备保护。不同用户对设备的访问权限不同。
差错处理。对设备的一些错误进行处理。
设备的分配与回收。
数据缓冲区管理。可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异
建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序。用户或用户层软件发出 IO 操作相关系统调用的系统调用时，需要指明此次要操作的 l/o 设备的逻辑设备名（eg：去学校打印店打印时，需要选择打印机 1 / 打印机 2 / 打印机 3，其实这些都是逻辑设备名）

不同设备的内部硬件特性也不同，这些特性只有厂家才知道，因此厂家须提供与设备相对应的驱动程序，CPU 执行驱动程序的指令序列，来完成设置设备寄存器，检查设备状态等工作。

IO 应用程序接口

用户调用 write 系统调用时，设备独立软件会把用户准备好的数据复制到内核区（套接字对应的这片缓冲区）。设备独立软件还会调用网络控制器驱动程序来处理这片数据。驱动程序会把数据输出到网络设备上。数据通过网络传输到另一个机器的网卡上，网卡接收到数据了就会发起中断，CPU 去执行中断处理程序，唤醒网络控制器驱动程序，把网卡的数据复制到内核中，用户再通过 read 系统调用，设备独立软件会把数据复制到用户空间。

阻塞 IO 和非阻塞 IO

阻塞 I/0：应用程序发出 I0 系统调用，进程需转为阻塞态等待。eg：字符设备接口 —— 从键盘读一个字符 get
非阻塞 I/O：应用程序发出 I/O 系统调用，系统调用可迅速返回，进程无需阻塞等待。eg：块设备接口 —— 往磁盘写数据 write

王道这里讲的有些问题。 write() 不是天然的非阻塞 I/O。要看 socket 的状态，如果 socket 是阻塞的， write() 就是阻塞 IO，也就是发送缓冲区满了，此时 write 会阻塞；只有 socket 被设置为 O_NONBLOCK 后， write() 才表现为非阻塞调用。

设备驱动程序接口

IO 核心子系统

IO 调度和设备保护

假脱机技术

共享设备和独占设备。

共享设备：能够被多个进程同时使用的设备（同时有两个含义，一个真的同时，一个宏观上同时，微观上交替）。比如进程 A 使用某个打印机，还没使用完，CPU 发生进程调度，进程 B 上处理机运行，也使用该打印机。该打印机就属于共享设备。

独占设备：进程 A 使用完该设备，其它进程才能使用。

设备的分配与回收

进程请求打印机输出：进程获得打印机资源后，将要打印的数据传给打印机，然后就会阻塞。直到打印机打印完成后才会被唤醒。

进程 P 发出 I/O 请求
↓
系统给 P 分配 I/O 设备
↓
P 被阻塞，等待 I/O 完成
↓
I/O 完成后，P 被唤醒
↓
P 继续使用 CPU 执行

对于 P 来说，P 的 cpu 执行和 IO 操作不能同时进行，所以说它们是串行工作。

缺点：
①用户编程时必须使用 “物理设备名”，底层细节对用户不透明，不方便编程
②若换了一个物理设备，则程序无法运行
③若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名。

缓冲区管理

速度不匹配指的是 CPU 处理数据的速度远远快于大多数 I/O 设备读写数据的速度。

所以 CPU 不能像访问寄存器、内存那样，直接等着设备慢慢传数据。否则 CPU 会大量空等，效率很低。

假如一个程序执行： write(fd, buf, 4096);
如果没有缓冲区，会发生什么？
理想化地看，如果每次 write() 都必须等磁盘真的写完，流程就是：
进程产生 4KB 数据
        ↓
CPU 发出磁盘写请求
        ↓
磁盘开始写入
        ↓
CPU/进程等待磁盘写完
        ↓
磁盘写完后，进程才能继续执行
问题在于：
CPU 产生 4KB 数据可能非常快
磁盘真正写入 4KB 数据可能慢得多
于是 CPU 很快把数据准备好了，但磁盘还没写完。
这时候如果进程必须等磁盘，就会出现：
CPU：我已经准备好下一批数据了
磁盘：上一批还没写完
CPU：那我只能等
这就是速度不匹配。

数据粒度不匹配是什么：比如输出进程每次可以生成一块数据，但 I/o 设备每次只能写入一个字符，也就是说输出进程只能一个字符一个字符往 IO 设备写。

结论：采用单缓冲策略，处理一块数据平均耗时 Max (C,T)+M

缓冲区要把数据传送到进程的用户空间，比如 C 中的 scanf，把键盘输入的数据传到某个存储单元中。CPU 用完该数据（处理完工作区的数据后），缓冲区才能把新的数据传送到该存储单元（才能把新数据传送到工作区）。

容易忘的一个点：磁盘 IO 速度慢，指的是把数据从磁盘读到内存，以及将内存中的数据写到磁盘。
CPU 负责发起和控制磁盘读 / 写请求，真正的大量数据搬运通常由磁盘控制器 + DMA 完成。
只有在比较早期或简单的 程序直接控制 I/O 方式下，CPU 才可能反复读取设备寄存器，再把数据写入内存，相当于 CPU 亲自搬运数据。感觉这就是前面讲的 IO 控制方式。
比如程序执行：
read(fd, buf, 4096);
大致流程是：
用户进程调用 read()
        ↓
CPU 陷入内核态，执行操作系统代码
        ↓
操作系统根据 fd 找到文件、页缓存、磁盘块位置
        ↓
设备驱动向磁盘控制器发出读命令
        ↓
磁盘控制器从磁盘读取数据
        ↓
DMA 把数据直接搬到内存的内核页缓存
        ↓
磁盘读完后发中断通知 CPU
        ↓
CPU 执行中断处理程序
        ↓
内核把数据从页缓存复制到用户 buf
        ↓
read() 返回

循环缓冲区：

缓冲池：

磁盘结构

磁盘管理

拥有启动分区的磁盘称为启动磁盘或系统磁盘（C 盘）

扇区备用对于操作系统是透明的，因为当操作系统想要访问某个坏块时，磁盘控制器会用一个好的块来替换坏块，所以在操作系统眼里自己访问的是好块。

一次磁盘 IO 操作所需要的时间

一次磁盘 IO 操作所需要的时间：

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。操作系统只能影响寻道时间。

从磁盘读出的数据先放在磁盘控制器缓冲区中，再通过 DMA 到内核页缓存，最后可能复制到用户缓冲区。ppt 中的传输时间严格上是把数据读出到磁盘控制器缓冲区的时间。但为了简化模型，可以认为传输时间包含把数据传输到内存的时间。

减少磁盘延迟时间的方法：

00，000，000-00，001，111 这个范围正好就是某个磁道的所有扇区。磁盘转一圈只能读取扇区 0、1、2、3。原因前面说过了，因为磁头读入一个扇区数据后需要花时间处理，所以磁头读完扇区 0，转到扇区 1 的时候不能接着读了。所以需要转两圈才能读完整个磁道。

磁头的作用：磁头负责感知磁盘表面该扇区的磁性变化，把它转换成电信号。磁盘控制器会把这些电信号解码成 01 数据，放入控制器的缓冲区中。

思考：为什么？磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）

答：读取物理地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间

减少延迟时间的方法：

先看一个场景：读取 0 号盘面和 1 号盘面的某个磁道。先读 0 号盘面，磁盘转两圈，最后磁头停到下图所示位置。接下来读 1 号盘面的数据，由于刚读完 000，00，111 磁盘块，磁头需要进行一些处理，所以 000，01，000 第一次划过 1 号盘面的磁头下方时，不能立刻读取数据。

磁盘调度算法

在多核 CPU 场景下，可以有多个进程同时请求访问磁道。所以需要磁盘调度，决定先处理哪个请求。在单核 CPU 场景下，请求是先后发出的，但是由于磁盘处理慢，可能进程 A 的请求还没有处理完，进程 B、C 也发出了请求，所以多个请求会在磁盘队列中积累，因此单核 CPU 场景下也需要磁盘调度决定处理顺序。

固态硬盘 SSD

对于磁盘来说，逻辑块号对应的是磁盘块 / 扇区；对于固态硬盘来说，逻辑块号对应的是一个页。在 SSD 内部，读 / 写的最小物理粒度通常是一个 page。

从 SSD 中读取数据的大概流程：
CPU 负责下达命令。（很多人以为是 CPU 亲自去 SSD 里把数据一点点搬出来，这是错误的。CPU 非常宝贵，它只负责 “发号施令”。CPU 会将操作系统打包好的 “读取命令” 放入内存中的一个特定队列里，敲一下 “门铃”（写 doorbell 寄存器），告诉 SSD：“有任务了，你自己来领一下！”）
SSD 内部的主控芯片 负责执行闪存层面的物理读取（把数据从 NAND 颗粒读到 SSD 缓存）。
DMA 控制器 负责执行数据搬运（把数据从 SSD 缓存搬到电脑内存）。