操作系统阅读笔记 - Three Easy Pieces

参考资料

免费书籍 PDF 版本
Homework
Projects
其余教辅资料请向contact@epubit.com.cn发送邮件获取
ostep-Projects

第一章 - 虚拟化

第一节 - CPU 虚拟化: 时分共享-进程（和空分共享-磁盘）

进程: 操作系统为正在运行的程序提供的抽象

进程的机器状态组成：

内存
寄存器
- 类型：程序计数器 & 栈指针 & 帧指针
- 3 部分组成：状态，数据，指令

启动程序的过程：操作系统将程序的 代码和静态数据从磁盘加载到内存中，同时为程序的运行时栈和动态内存堆分配内存，最后启动程序，通常是程序入口（以c为例通常是 main(）函数）。
默认情况下进程都有3个文件描述符

标准输入0
标准输出1
标准错误2

进程状态

initial: 创建进程时的状态
running
ready
blocked
final: 僵死状态，待回收，有时候会出现 parent progress 已经被回收但是 child progress 还在僵死状态时，此时有高一级的 init 进程回收，或者直接关机也行（有些垃圾程序只能关机。

# 进程主要状态
running  <----------- 调度|取消调度 ----------> ready
  |                                             |
  |---I/O: start---> blocked --I/O: finished--->|

上下文切换：操作系统保存和恢复该进程的寄存器内容的过程

进程 API(系统调用陷入内核模式,区别于用户模式）

暂时只考虑单 CPU 的情况，不管是什么进程，CPU 都有可能不断中断，切换任意进程，记住就算是亲子（进程）也是不存在尊老爱幼的，谁先运行取决于 CPU 调度程序，所以执行顺序是不确定的。⚠️ 这种不确定性贯穿全文

fork()：调用一次返回两次，争先恐后

fork()虽然复制了 parent progress，但是由于写时复制拥有私有虚拟内存（用户栈），但是调用时返回值却不相同，child progress 的返回值是 0，parent progress 的返回值是 child progress 的 pid。

// 有必要理解一下返回2次, 示例代码（c）如下：
// 头文件省略
// 让我们先假定child progress先运行
int main(int argc, char *argv[])
{
  printf("您好，当前运行进程pid:%d", int getpid());
  int rc = fork()
  // 不考虑fork失败
  if (rc == 0) {
    // child process, 这里根据 rc 的返回值运行一次 - !!返回一次
  } else if (rc > 0) {
    // parent process, 这里根据 rc 的返回值再运行一次 - !!返回两次
  }
}

‼️ 注意：nodejs child_process.fork()虽然调用的是 fork(2),但是却有所不同，衍生的 child progress 不会克隆当前 parent progress，只能通过 IPC 通信。

# 命令行执行: node ./os-notes/chapter-5.js 输出结果:
此消息最新显示
衍生的child progress的 pid：95650
此进程的 pid 是 95649
^C

exec()：鸠占鹊巢，臭不要脸

其他变体：execl(), execle(), execlp(), execv(), execvp()等。‼️ 成功调用不会返回。

exec()会直接覆写当前进程的代码，堆，栈和其他内存空间等。所以新的程序的虚拟地址不变，进程 id 不变

wait()：parent progress 可以通过调用wait()来确保自己后运行，此时 2 种情况：

child progress 先运行，然后 parent progress 运行，天意如此。
parent progress 先运行，马上调用wait()，该系统调用会在 child progress 运行结束后返回，然后 parent progress 输出。
总结：这 3 个系统调用可以用来实现 shell 的很多有用的功能，例如重定向输出，管道的实现方式等。

‼️ 问题：多进程程序是怎么抽象的？

进程是程序运行的一个实例，多进程就是程序运行的多个实例，fork()函数在新的 child progress 中运行相同的程序，child progress 是 parent progress 的复制品，进程上下文中将只有栈内数据不同（通过标记为私有的写时复制，复制时是完全相同的，运行后不同），堆、代码中的数据完全相同，因为 fork 复制进程时只是重新分配了一段虚拟内存复制原进程内容，并且标记为只读，可以通过绘制进程图来了解 fork()。而通过exec()是在当前进程中的上下文中运行另一个新程序，将覆盖当前进程的地址空间（该进程所在的虚拟内存），但是PID(进程 id)不变且继承了调用该函数时已打开的所有文件描述符（即包含stdin,stdout,stderr3 个描述符）。更多内容请参考csapp第八章异常控制流一起食用。

机制: 受限直接执行(limited direct execution, 简称 LDE 协议)

LDE 协议的两个过程：1. 内核初始化陷阱表，并记住位置以便后续执行操作；2. 在进程中设置节点分配内存，用于保存陷入陷阱和返回的信息

此协议下需要解决 2 个问题：

受限制操作：引入用户模式(user mode)**，与之对应的是内核模式(kernel mode)**

用户模式和系统交互通过内核模式暴露一些关键功能，如：访问文件系统，创建或销毁进程，或与其他进程通信以及分配更多内存等，称为系统调用。暴露功能的方式为在启动时设置 陷阱表 系统可以在 用户模式和内核模式中反复横跳
例如：用户模式下进程不能发出 I/O 请求，否则会导致进程终止

进程切换：

需要解决操作系统重新获取占据主动权的问题
- 等待进程执行系统调用或者出错 - 该进程必须是个听话的好孩子才行
- 时钟中断
保存进程上下文：2 种可能，存储位置，存储内容和存储方式均不相同
- 时钟中断时：用户寄存器有硬件隐式保存，使用该进程的内核栈。
- 调度程序切换进程：内核寄存器被软件 OS 保存，并存储在该进程的进程结构的内存中（‼️ 用户栈吗？）。

进程并发：锁？中断中禁止中断 - 禁止套娃？信号？ => 并发章节会详细讨论

# 进程的地址空间：
-------------------------
| 内核栈（代码，数据，堆，栈）|  ----> 用户代码不可见的内存
--------------------------
|   用户栈（运行时创建）     |
--------------------------
|  共享库的内存映射区域      |
---------------------------
|    运行时堆              |
--------------------------
|    读/写段（.data,.bss） |   ----> 从可执行文件加载
--------------------------
|       只读代码段         |   ----> 从可执行文件加载
|（.init,.text,.rodata）  |
--------------------------

进程调度：介绍

如何开发调度策略？想一想什么情况下要使用调度策略？然后弄清楚评价调度策略的关键指标是什么？

工作负载假设：
1. 每一个进程运行相同的时间 -> 完全公平
2. 所有工作同时到达 -> 平均响应时间
3. 一旦开始，每个进程运行到完成 -> 运行时独占CPU
4. 所有进程不涉及I/O -> 进程任务单一
5. 已知每个进程的运行时间 -> 平均周转时间

调度指标：
1. 周转时间 = T完成时间 - T到达时间 => 性能指标
2. 公平
3. 响应时间 = T首次运行 - T到达时间
让我们设置一个时间函数 T(参与进程, 策略, [放开的假设条件])

# 工作进程假设: 基于逐渐放开以上5个假设条件
# test1: 假定目前的进程为（随机排序执行）：A（10s完成），B（10s完成），C（10s完成）
 10s  10s  10s
-----|||||/////30s
  A    B    C
# test2: 假定目前的进程为（随机排序执行）：A（100s完成），B（10s完成），C（10s完成） - 假设1
         100s                   10s  10s
-------------------------------|||||/////120s
  A    B    C
# test3: 假定目前的进程为（随机排序执行）：A（100s完成）0s到达，B（10s完成）10s到达，C（10s完成）10s到达 - 假设1&2
         100s                   10s  10s
-------------------------------|||||/////120s
  A    B    C
# test4: 假定目前的进程为（随机排序执行）：A（100s完成）0s到达，B（10s完成）10s到达，C（10s完成）10s到达 - 假设1&2&3
 10s  10s  10s         90s
-----|||||/////--------------------------120s
  A    B    C           A

先进先出FIFO：队列

平均周转时间：
- Tt(test1,FIFO,[]) = (10 + 20 + 30) / 3 = 20s
- Tt(test2,FIFO,[1]) = (100 + 110 + 120) / 3 = 110s

最短任务优先SJF：FIFO 下一旦出现单个长任务周转时间就很长，改进一下策略

平均周转时间：
- Tt(test2,SJF,[1]) = (10 + 20 + 120) / 3 = 50s
- Tt(test3,SJF,[1,2]) = (100 + 110-10 + 120-10 ) / 3 = 103.3s

最短完成时间优先STCF：SJF 下短任务后到达时，长任务的周转时间并没有改善

平均周转时间：
- Tt(test4,STCF,[1,2，3]) = (120 + 10 + 20) / 3 = 50s
平均周转时间作为唯一指标的话，STCF表现良好。然鹅，引入分时系统后用户要求系统交互性好，所以引入响应时间作为新的指标
平均响应时间：Tr(test4,STCF,[1，2，3]) = (0 + 10 - 10 + 20 - 10) / 3 = 3.3s;
Tr(test1,FIFO,[]) = (0 + 10 - 10 + 20 - 10) / 3 = 3.3s;

轮转RR(Round-Robin): RR 在一个时间片内运行，然后切换到队列的下一个工作，反复切换执行直到所有任务完成。

时间片(time slice)的长度为时钟中断周期的倍数: 以下示例假设 RR 时间片为 1s
平均响应时间：Tr(test1,SJF,[3]) = (0 + 10 + 20) / 3 = 10
平均响应时间：Tr(test1,RR,[3]) = (0 + 1 + 2) / 3 = 1
假设 RR 时间片为 50ms: Tr(test1,RR,[3]) = (0 + 0.05 + 0.1) / 3 = 0.05s
RR 效率的关键就是时间片的大小，然鹅时间片太小会频繁切换进程上下文，影响整体性能
摊销技术：将时间片的大小与切换上下文时间比较，1ms/10ms _ 100% = 10% => 太大；1ms/100ms _ 100% = 1% => 可以考虑
平均周转时间：Tt(test1,RR,[3]) = (26 + 28 + 30) / 3 = 28s ‼️ 周转时间太可怕惹

两种调度程序：SJF,STCF 优化了周转时间，不利于响应时间；RR 优化了响应时间，不利于周转时间，接下来需要放开假设 4 和假设 5

结合I/O: 重叠，当一个进程被I/O阻塞，CPU可以切换其他进程运行
工作进程假设：A 50ms 运行10ms 发出I/O; B 50ms 没有I/O

# 没有重叠
     A   A   A   A  A  B B B B B
CPU: --  --  --  --  --||||||||||
I/O:   --  --  --  --
# 重叠后
CPU: --||--||--||--||--||
I/O:   --  --  --  --

实际上调度程序并不知道每个工作的长度，下一章将通过构建一个调度程序利用最近的使用情况预测未来从而解决未知工作长度的问题：多级反馈队列

多级反馈队列(Multi-level Feedback Queue)

这是我遇到的第二个多级，真是相当美妙的思想，第一个多级是多级页表（这本书它出现在第二章，我发誓我没有跳着看书 🐶）

多级反馈队列要解决 2 个问题：优化周转时间 && 降低响应时间 => 从历史中学习并预测

MLFQ基本规则：
MLFQ有许多独立的队列(queue),每个队列有不同的优先级(priority level)。一个进程只能在一个队列中，MLFQ总是优先执行较高优先级的进程，每个队列中的进程都拥有相同的优先级。
MLFQ的关键在于如何设置优先级。
规则1：若A的优先级 > B的优先级，运行A
规则2：如果A的优先级 == B的优先级，RR（轮转）运行

刚定下 2 个规则就出现一个问题：AB 两个进程在高优先级队列中，CD 两个进程在低优先级队列中，假设 AB 任务一直运行，CD 岂不是等到死都没法运行

如何改变优先级：
先考虑工作负载的类型：1.运行时间短，频繁放弃CPU的交互型工作；2.需要更多CPU时间，响应时间不重要的长时间计算密集型工作。
所以调整算法，增加规则：
规则3：工作进入系统，放到最高优先级 - 单个长工作（密集计算型）
规则4a：工作用完整个时间片后，降低到下一个优先级 - 长工作运行一段时间来了一个短工作（交互型）
规则4b：如果工作在时间片内动释放CPU，则优先级不变 - 交互型短工作执行大量I/O操作
以上实例皆运行良好，但是会出现长工作的饥饿问题：
系统中出现了大量的交互型短工作，导致长工作无法得到CPU
||
提升优先级：S太高长工作会饿死，太低交互型工作得不到合适的CPU时间比例
规则5：周期性提升所有工作的优先级，经过一段时间S，将系统中的素有工作重新加入最高优先级队列
更好的计时方式：修改规则4a & 4b:
规则4：一旦工作用来了某一层的时间配额（无论中间主动放弃了多少次CPU），就降低优先级 => 防止恶意程序愚弄CPU

MLFQ 调优及其他问题

配置多少优先级队列？
每一层队列的时间片设置为多大？
多久提升一次进程的优先级？

大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片，因此这一层的交互工作可以更快的切换，相反，低优先级队列更多的是密集型工作

比例份额

多处理器调度

第二节 - 内存虚拟化

地址空间

内存操作 API

地址转换

分段
分页

快速地址转换
较小的表

交换空间

虚拟化磁盘空间
替换策略
虚拟内存技巧及示例

空闲空间管理

第二章 - 并发

线程

锁

基于并发的数据结构

条件变量

信号量

常见并发问题

基于事件的并发

事件循环：

# 伪代码
while(1) {
  events = getEvents()
  for (e in events)
    processEvents(e)
}

基于事件的服务器如何决定事件的发生顺序？尤其是网络和 I/O

这里我们有一个例子，来首先了解一下select()函数：这个例子是从CSAPP上抄来的，select真是令人印象深刻
假设有一个echo服务器，它很强，一边接收网络请求，一边也可以响应用户的命令行键入请求。肿么办捏，先处理哪一个？更具体的代码示例请参考`《CSAPP》第12章第2节基于I/O多路复用的并发编程`
基于I/O多路复用技术的并发：使用select(),要求内核挂起进程，只有在一个或者多个I/O发生后才将控制权返回给应用程序（说人话：多个I/O请求注册到同一个select, select搞一个集合存储他们的状态，只要有I/O触发那么就由系统调用转回应用程序（用户模式））。

重要 API: select() or poll() 系统调用

select() 检查I/O描述符集合, 地址通过`readfds`,`writefds`, `errorfds`传入；
在每个集合中检查前nfds个描述符。
返回时，select()用给定请求操作准备好的描述符组成的子集替换给定的描述符集合，返回所有集合中就绪描述符的总数。

请注意 select()的超时参数，常见用法是设置为 NULL,但会导致无限期阻塞，直到有可用的就绪描述符。更好的做法是将超时设置为 0，因此让调用的 select()立即返回，这种方式提供了一种构建非阻塞（异步）事件循环的方法。

补充：阻塞与非阻塞接口
阻塞（同步）接口：在返回给调用者之前完成所有工作，非阻塞（异步）接口开始一些工作但是立即返回，从而让所有需要完成的工作都在后台完成。
通常阻塞调用的就是某种I/O。
非阻塞接口可用于任何类型的编程（例如使用线程），但在基于事件的方法中非常重要，因为阻塞的调用会阻塞所有进展。

‼️ 要分清楚并不是所有的非阻塞=异步，I/O 就不是，非阻塞 I/O!==异步 I/O

使用单个 CPU 和基于事件的并发服务器，线程并发的程序中存在的抢占锁释放锁等问题不复存在，因为只有一个线程，不会被其他线程中断，但是请务必记住‼️ 不要阻塞基于事件的服务器，即 node 中，小心使用同步 api.

阻塞系统的调用：I/O 大 boss 如何解决？

异步 I/O(Asyncchronous I/O):

发出异步读取
如何才能知道 I/O 已经完成，并且缓冲区(aio_buf)已经有了数据: aio_error 系统调用检查 aiocbp 引用的请求是否已经完成，如果完成则函数返回成功 （用 0 表示）,否则返回 EINPROGRESS。对于每个未完成的 AIO，应用程序可以调用 aio_error 来周期性的轮询(poll)系统，以确定所述 I/O 是否完成。这条看着很累，看下一条，宝贝。
poll 一个 I/O 害行，1000 个捏恐怕要累屎惹，所以某些系统提供了 基于中断(interrupt) 的方法。使用 UNIX 信号(signal)在异步 I/O 完成时通知一下程序，从而消除了轮询的痛苦，从今以后幸福快乐 🥰。

// AIO control block
struct aiocb {
  int aio_fildes; /* file descriptor */
  off_t aio_offser; /* file offset */
  volatile void *aio_buf; /* location of buffer */
  size_t aio_nbytes; /* length of transfer */
}
// AIO 第一步： 向文件发出异步读取,发出成功后会立即返回并且应用程序可以继续工作
int aio_read(struct aiocb * aiocbp);
// AIO 第二步：
int aio_error(const struct aiocb *aiocbp)

补充：UNIX信号
信号提供了一种与进程通信的方式，可以将信号传递给应用程序，进程将暂停当前工作开始运行信号处理程序。完成后，该进程就回复先前的行为。
每个信号都有名字，如：HUP(挂断),INT(中断),SEGV(段违规)
内核或者程序都可以发出信号
可以用kill命令行工具发出信号，例如：
prompt > ./main & [3] 36705
prompt > kill -HUP 36705
stop wakin' me up...

在没有异步 I/O 的系统中，纯基于事件的方法无法实现。然鹅可以使用某种混合方法，使用线程池来管理未完成的 I/O。参考《flash: an efficient and portable web server》来了解更多。

状态管理：基于事件的方法的另一个复杂问题

当事件处理程序（事件循环中待处理的一个事件）发出异步I/O时，必须打包一些程序状态，以便下一个事件处理程序在I/O完成完成时使用。而基于线程的工作是不需要的，因为状态都保存在线程栈内。
node是如何处理这个问题的？
据鄙人看完的《深入浅出nodejs》后的一些笔记来看，node只是JS运行在单线程上，异步I/O另有线程：
部分线程通过阻塞或非阻塞&轮询技术来完成数据获取，一个线程进行计算处理，通过线程间通信进行数据传递，实现异步I/O，也就是说node处理异步I/O是通过管理线程池来实现的。（没想到吧Σ(⊙▽⊙"a）

太难了

当系统是多核 CPU 时，基于事件的一些简单性（不用加锁，不存在线程中断）就没有了，为了利用多个 CPU，事件服务器必须并行运行多个事件处理程序，这时会出现「缓存一致性」？「加锁！必须加锁!!」,「发生缺页肿么办！被堵死了」等各种问题，现在先不要心塞，后面心塞的还多着呢，抽屉里放点硝酸甘油片啥的 ❤️。

思考：同步 I/O 包含非阻塞 I/O 吗？异步 I/O 呢？

I/O 包含两步：请求和数据复制到缓冲区

I/O 类型	请求	数据复制到缓冲区（aio_buf）	检查 I/O 是否完成的方法
同步 I/O	阻塞	阻塞	等前两步完成也就拿到了
非阻塞 I/O	异步	阻塞	轮询，CPU 很忙
I/O 多路复用	异步	阻塞	轮询，CPU 很忙（linux: epoll;）
异步 I/O	异步	异步	中断时发信号(windows:IOCP)

技术总结：组合使用用于网络的 select()接口和用于磁盘的 AIO 的调用（我猜 node 就是这样）

node 基于 I/O（AIO（通过线程池来实现异步 I/O））多路复用，所以是单线程（JS）、非阻塞、异步 I/O，JS 运行的单线程不会阻塞，但是 I/O 过程有可能是阻塞的，一旦遇到缺页就会卡住，就算主动去非洲客户也不会原谅你，OMG 生活真是苦涩。

思考: node 单线程是怎么实现并发的？

nodejs使用cluster(集群)创建多个共享服务器端口的child progress来利用多核CPU系统
原理是：child_process.fork()衍生的是独立的child progress，和 parent progress只通过IPC管道来通信，可以根据需要随时关闭或者创建，不影响其他进程。
cluster分发连接：主进程负责监听接口，然后循环分发给各child progress。

思考：多个进程为什么可以共享服务器端口？

首先要知道监听描述符和已连接描述的区别，是并发服务器的基础，每次一个请求到达监听描述符时，可以在此时派发fork()一个新进程来连接已连接描述符与客户端通信。服务器调用server.listen({fd:7})将消息发给主进程，parent progress将监听监听描述符并将句柄（handle）派发给child progress，child progress调用server.listen(handle)会显式监听handle而不是与 parent progress通信，child progress还会调用server.listen(0)会收到相同的「随机端口」，随机端口在第一次随机分配，而后都是已知的。
如果需要独立端口，可根据child progress的PID来生成。

思考 again: nodejs 主进程挂了肿么办？所有相关 child progress 会一起被回收还是移交给主进程挂掉时立即重启一个新的 parent progress 呢？

child progress死亡不会影响 parent progress, 不过child progress死亡时（线程组的最后一个线程，通常是“领头”线程死亡时），会向它的 parent progress发送死亡信号. 反之 parent progress死亡, 一般情况下child progress也会随之死亡, 但如果此时child progress处于可运行态、僵死状态等等的话, child progress将被进程1（init 进程，由内核创建，是所有进程的祖先）收养，从而成为孤儿进程. 另外, child progress死亡的时候（处于“终止状态”），parent progress没有及时调用 wait() 或 waitpid() 来返回死亡进程的相关信息，此时child progress还有一个 PCB (Process Control Block进程控制结构)残留在进程表中，被称作僵尸进程.

操作系统阅读笔记 - Three Easy Pieces

参考资料

第一章 - 虚拟化

第一节 - CPU 虚拟化: 时分共享-进程（和空分共享-磁盘）

进程: 操作系统为正在运行的程序提供的抽象

进程 API(系统调用陷入内核模式,区别于用户模式）

机制: 受限直接执行(limited direct execution, 简称 LDE 协议)

进程调度：介绍

多级反馈队列(Multi-level Feedback Queue)

比例份额

多处理器调度

第二节 - 内存虚拟化

地址空间

内存操作 API

地址转换

空闲空间管理

第二章 - 并发

线程

锁

基于并发的数据结构

条件变量

信号量

常见并发问题

基于事件的并发

事件循环：

重要 API: select() or poll() 系统调用

异步 I/O(Asyncchronous I/O):

状态管理：基于事件的方法的另一个复杂问题

太难了

技术总结：组合使用用于网络的 select()接口和用于磁盘的 AIO 的调用（我猜 node 就是这样）

第三章 - 持久性

I/O 设备

磁盘驱动器

RAID 冗余磁盘阵列

文件与目录

文件系统的实现

局部性和快速文件系统

崩溃一致性

日志结构文件系统

数据完整性和保护

思考：数据库

分布式系统

通信基础

Sun 的网络文件系统 NFS (Network File System)

Andrew 文件系统 AFS

思考：与计算机网络的联系

TCP 与 UDP 的比较

TCP 握手挥手机制

TCP 与 UDP 的丢包处理

实践：局部网络中的通信-wireless