陈浪平的博客

4. The Abstraction: The Process

如果说在操作系统哪个抽象是最重要的，我肯定会回答：进程。进程就是对运行着的程序的抽象。程序本身就是在磁盘中躺着，有了操作系统，才让这些在磁盘中的字节变得鲜活了起来。

通过时间片分享（time sharing）技术，可以让多个进程轮流执行，每个进程就好像拥有一个独立的虚拟CPU一样。

为了能够实现CPU虚拟化，OS需要同时使用低级别的机制（mechanisms）和一些高级别的策略（policies）。

The Abstraction: A Process

要彻底理解进程是什么，我们就需要理解当程序运行的时候，它可以更新或者读取什么东西？

第一个显然是内存，指令在内存里，程序需要的数据也在内存里，所以进程包含了一个叫地址空间（address space）的东西。

第二个是寄存器，因为很多指令都需要显式修改寄存器的值。寄存器包含程序计数器（program counter，有时候也叫做指令指针instruction pointer），栈指针以及栈帧指针。

第三个是程序需要写东西回磁盘，所以需要进行IO，自然包括当前进程打开的文件列表。

进程API

本章不具体讨论这些api，只是概括性了解一下。

• create：操作系统必须要有api能够创建出新进程。当你在shell中敲命令或者是在桌面程序中双击的时候，其实就是对应的进程的创建。
• destory：进程执行完成后一般会自己关闭，当然用户也可以强行关闭。
• wait：进程有时候需要等待别的进程。
• Miscellaneous Control：杂项控制，比如操作系统有的时候需要暂停某个进程
• status：还需要有一些接口能够得着进程的状态。

进程创建

那么，是如何把磁盘中的程序弄到内存中变成进程的呢？首先需要把磁盘中的程序，load它的代码段和程度段到内存，即指定的地址空间中。在早期操作系统中，是把程序整个放到内存中的，而现在的操作系统是懒加载，即只有在需要的时候才放入内存。

放入内存之后，就需要为栈分配空间，为堆分配空间（malloc分配的是堆空间），并且堆空间会随着程序运行而增长（当然也可以减小）。

然后每个进程默认是有三个文件描述符的，对应标准输入，标准输出和标准错误。

在做完这些之后，进程的舞台就已经准备好了，接下来操作系统就去执行main()，这样就把CPU转移到了新的进程上了。

进程状态

• Running：此时进程正在使用CPU。
• Ready：可以运行，但是操作系统没有让它运行。
• Blocked：在一些事情发生之前，进程一直需要等待。最简单的例子就是如果一个进程需要IO等待，那么就进入这个状态，别的进程就可以获得CPU了。当IO完成的时候，是直接让这个阻塞的进程马上运行，还是等一下才运行，这取决于操作系统是如何调度的。但是通常来说，一个进程IO完成的时候，应该尽快让它执行，这样可以有效提高资源利用率。

数据结构

操作系统是一个程序，那么和别的程序一样，它当然也有自己的数据结构。

首先是对于context：

1
2
3
4
5
6
7
8
9
10

struct context{
  int eip;
  int esp;
  int ebx;
  int ecx;
  int edx;
  int esi;
  int edi;
  int ebp;
}

然后是对于进程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct proc{
  char *mem;        // 该进程内存的开始的地方
  uint sz;          // 进程占用了多少内存空间
  char *kstack;     // 进程栈的最底层
  enum proc_state state;    // 进程状态
  int pid;          // 进程id
  struct proc *parent;      // 父进程
  void *chan;       // 如果不是0则睡眠
  int killed;       // 如果不是0则死亡
  struct file *ofile[NOFILE]; // 打开的文件
  struct inode *cwd;        // 当前目录
  struct context context;   // 上下文
  struct trapframe *tf;     // 对于中断所对应的帧
}

操作系统通常会使用进程链表来控制所有的进程。但是有的时候人们的关注点不在于多个进程，而在于单个进程，PCB，process control block里面就包含了进程的所有信息。即可以理解为PCB就是进程链表中的一个节点。

总结

上面就是对一个进程的抽象，接下来就是对高级的策略和低级的机制的讲解，看看它们是如何虚拟化CPU的。

家庭作业部分

1. 运行程序，使用参数-l 5:100,5:100，CPU的利用率是多少，你是怎么知道的?

   100%，因为根本就没有IO操作，当然不需要等待。

2. 运行程序，使用参数-l 4:100,1:0，表示有两个进程，一个进程运行4条指令，还有一个进程执行一个IO操作（1条开始指令，4个等待周期，一条done指令）。

3. 把程序切换成-l 1:0,4:100，有什么不同？

   可以发现最明显的不同就是当第一个进程进入到等待的时候，第二个可以立马去执行，这样总体时间会短很多。

4. 剩下的没什么好说的，跳过。

交换两个进程，可能会让任务执行得更快；或者是允许进程之间进行切换，也会让系统整体运行得更快。

5. Interlude: Process API

Unix中最有趣的是，创建进程可以使用一对系统调用——fork()和exec()，还有一个是进程等待的，叫wait()。

系统调用——fork()

本科的时候学习这个函数的时候就觉得非常奇怪，一个函数返回两个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
    printf("hello world, pid = %d \n", (int) getpid());
    int rc = fork();
    if (rc < 0) {
        fprintf(stderr, "fork");
    } else if (rc == 0) {
        printf("child process pid = %d\n", (int) getpid());
    } else {
        printf("father process pid = %d\n", (int) getpid());
    }
    return 0;
}

请用sudo运行这个程序。这个程序会先输出hello world，之后就可能先输出child，可能先输出father，纯凭运气。

不知道你发现没有，这个fork系统调用，为什么跟我们平时写的函数一模一样呢？这里的fork，首先确实是一个procedure call，但是在这个里面，隐藏了一条trap指令，通过设置系统调用的相关变量，并且执行trap，就可以执行系统调用了。也就是别人已经帮你封装好了。

简单来说，编写C语言其实实际上需要调用库函数，而库函数里面写的就是调用操作系统内核的一些函数调用——只是在大多数情况下，它们的名字相同，所以会有我直接在调用操作系统内核的错觉。

系统调用——wait()

上面说了哪个进程先输出纯看运气，但是在实际中，一般都是父进程fork一个子进程，派它去完成任务，然后父进程返回，所以我们一般会让父进程等待在其完成，使用这个系统调用。

当然事无绝对，是存在一些情况，当子进程还没完成但是wait()就已经返回了，即僵尸进程的由来。

系统调用——exec()

如果你想调用别的进程，那么就可以使用这个系统调用，它有好几个变种。具体就是通过这个系统调用，传入你要执行的命令（进程名字），并且把参数传过去，就可以执行了。

具体的过程是，给定一个可执行的程序的名字和一些参数，然后加载这个程序的代码和数据，覆盖掉自己原来的代码段和数据段，当然堆栈部分也要重新初始化，相当于把自己变成了那个程序。所以如果使用exec系统调用，并没有创建新的进程。而且这个系统调用成功了之后，是不会返回的。

分析API

为什么要这么设计呢？这样设计可以让shell在fork之后执行代码，在exec之前执行代码。具体来说，当我们打开shell，输入一个命令，此时shell就可以知道上哪里去找到这个命令的可执行文件，并且使用fork来创建子进程，并且在子进程使用exec或者它的变体来执行任务，同时父进程进行wait。一旦父进程的wait返回，说明已经执行完毕，此时又再次显示提示符。

如果执行的命令进行了重定向，那么在创建完子进程之后，进行exec之前，shell关闭掉它的标准输出，并且打开指定的文件，这样就会重定向到指定的文件了。

如果关闭了标准输出，那么当使用open系统调用的时候，就会把打开的文件的文件描述符置成STDOUT_FILENO，这样就会输出到文件中去了。

系统调用pipe和上面的原理很相似，在上面的例子中，进程的输出被连接到内核的pipe中，另外一个进程的标准输入也连接到同一根管道，这样就可以将一个进程的输出作为另一个程序的输入，连成一条链。

进程控制和用户

除了上面三个系统调用，还有一些用来和进程进行沟通的方法。比如kill系统调用会发送信号给进程。

在很多shell中，可以通过一些键盘的组合键来发送信号给当前正在运行的进程。

进程通过使用signal系统调用来捕捉这些信号，当信号到来的时候，进程会暂停自己正常的运行，转而执行一段特殊的代码来响应这个信号。当然不是任何用户都能够发送信号给进程的，这个也是操作系统进行控制的。

发送信号的本质上其实是触发中断；而CPU在执行每一条指令之后，都会判断有没有中断发生，以此来保证不会错过信号的处理。

有用的工具

通过ps命令可以查看正在运行的进程（大概率就是ps和你的shell），top展示了系统中的进程并且消耗的资源。

家庭作业

1. 如果有一个变量，在父进程创建子进程之前就已经存在，那么父进程和子进程分别分别修改了这个变量之后，结果是什么呢？

   因为子进程会获得父进程所有的一切的复制，所以这个变量在子进程里面也会有，而且这个变量和父进程的那个变量已经完完全全没有任何关系了。

2. 如果父进程使用open系统调用打开了一个文件，然后创建了子进程，那么它们两个可以同时拥有这个文件描述符吗，它们可以同时对这个文件进行写入操作吗？

   经过实际编写代码验证，一个文件的文件描述符在两个进程中是一致的，都为3，但是文件的最后内容，我自己写的程序是父进程等待子进程完成，这样得到的结果是拼接的内容。但是如果是两个进程同时，我感觉可能会出现相互影响的结果。

3. 如何在不使用wait的情况下，保证子进程先结束呢？

   emmm 说实话不会。

   查阅资料，可以首先暂停（pause）父进程，然后到子进程完成自己的任务之后，通过kill发送一个SIGCONT信号给父进程，父进程就会继续进行了。

4. 为什么exec会有这么多的变种呢？

   

   可以从man手册里面看到，这六种变种。明显就是参数不一样，比如有给定文件，有给定路径的；有给定环境变量的，没有给定环境变量的等。从历史的角度来说，随着历史的发展，越来越多的需求需要，那么就提出了更多的函数。

5. wait函数返回的是什么？如果在子进程返回会发生什么情况？

   在子进程中返回的是-1，父进程中的wait返回的是子进程的pid。

6. waitpid和wait有什么区别呢？

   waitpid可以指定等待的进程pid。

7. 如果父进程创建了一个子进程，然后在子进程里面关闭了标准输出，然后使用了printf，会发生什么呢？

   屏幕中啥都不显示。

8. 编写一个程序，它能够创建两个子进程，并且子进程之间利用管道进行通信。

   蛮有意思的一个小程序，其实一共有三个进程，分别是父进程和子进程1和子进程2。

6. Mechanism: Limited Direct Execution

操作系统通过时间片分享机制来实现虚拟化，但是要解决几个问题：怎么保证较高的效率？控制权问题怎么解决呢？

操作系统必须保证自己掌握着系统的控制权。

最简单的实现：有限直接执行

不难想到一种叫limited direct execution的方法：当操作系统开始一个程序的时候，做好准备工作，然后调用该进程的main方法，接着程序就执行，直到执行完毕最终返回。返回之后操作系统进行一些清理工作。

但是这么做明显也有问题：进程执行的时候，操作系统如何发送信号给进程呢？怎么保证这个进程不瞎搞事呢，比如这个进程恶意霸占了CPU，导致整个系统只有这个进程在运行呢？

问题1：限制操作

直接执行程序的话，显然会非常快，因为程序直接运行在CPU上。但是问题是如果这个进程需要操作一些高权限的操作，例如IO或者是其他资源呢？

通过设置用户态和内核态，就可以解决这个问题。运行在用户态的代码，就不可以处理IO请求，如果强行这么做，处理器会触发一个异常并且跳转到操作系统中，接着操作系统就会（大部分情况下）干掉这个进程。而操作系统就运行于内核态，不受限制。

那如果用户态的代码真的需要去从文件中获取信息呢？现代的硬件提供了一种能力，能够让用户程序使用一个系统调用，内核会暴露一些关键的函数给用户程序，以便使用。

为了能够执行一个系统调用，程序必须使用一条特殊的指令——trap。这条指令可以同时跳转到内核并且提高内核的优先级。结束的使用使用return-from-trap指令，跳转到用户程序的同时并且降低优先级。

内核同时还有一个trap table，这东西在操作系统启动的时候（操作系统启动的时候当然是内核态）进行初始化。

也就是通过内核态和用户态之间的切换，保证了进程不能想做什么就做什么。

问题2：在进程中切换

听上去进程切换不难，但是有一个问题：在进程A使用CPU的时候，操作系统并没有在运行啊，如果操作系统没有运行，它怎么进行切换进程的操作呢？（实际上它也确实无能为力），那操作系统要如何去夺权呢？

在早期的mac os中，使用的是合作模型：操作系统信任进程在执行一段时间的CPU之后会放弃CPU时间，这样OS就能够执行别的任务，使用的是yield系统调用。也即是OS只需要等待系统调用，当进程执行系统调用，那么CPU时间就会回到自己这里。显然，模型建立在信任之上的话，一旦有恶意程序不调用系统调用，而且也不放弃，那么整个系统就完蛋了。

所以需要一种方式强行拿回CPU时间，怎么办呢？使用timer interrupt（时钟中断）。本质上是使用一个硬件，这个硬件能够每隔一段时间，自动触发一个中断，只要中断触发，那么当前运行的进程就停止，中断处理程序会执行（会保存进程的状态），这样OS就得到了CPU控制权。所以在系统启动的时候，不仅要设置trap table，也同样需要设置这个定时器。

不管是进程自愿放弃CPU时间，还是通过定时OS强制获取了控制权，OS都需要考虑接下来让哪个进程来运行，这一部分就是通过scheduler来完成的。

（注：这一段描述的内容一直处在内核模式中）如果OS决定切换进程执行，那么OS就需要执行context switch，做法也很简单，就是把进程的寄存器保存起来（保存到用户的stack中），然后把将要执行的进程的寄存器恢复（从用户stack中恢复），这样当return-from-trap指令运行的时候，就可执行接下来的进程了。

更为具体的，当定时器中断发生的时候，A的寄存器内容由硬件来隐式保存，保存到A的内核栈中，并且跳转到特权模式上，使用对应的陷阱处理程序。陷阱处理程序处理陷阱，就是调用switch()函数。而当操作系统决定切换进程的时候，A的寄存器被操作系统显式进行保存，保存到内存的进程结构中去，同时也把将要执行的进程B的内存读取到寄存器里面来，然后跳转到B的内核栈，并且把完成之后从trap返回，并且硬件会把将要执行的进程的内核栈给恢复到B的寄存器中，跳转到用户态。

下面这张图就说明了这个过程：

并发下的问题

比如系统调用的时候，发生了时间中断，这怎么办呢？

当你正在处理一个中断，另外一个中断发生了，怎么办呢？

这些问题会在第二部分完成，但是这里先简单来回答一下。通过在处理中断的时候，disable interrupts屏蔽中断。这样就不会导致CPU被抢走。还有一些锁机制来解决这些问题，在多进程中非常有用。

总结

在这部分我们学到了一些low-level的机制来实现CPU虚拟化，通过在系统启动的时候设置好trap table和interrupt timer，可以有效解决这些问题。

我们还留下一个问题，接下来，应该让哪一个进程来执行呢？

家庭作业

手动测试一下一个system call和一个context switch的时间。

测试system call非常简单，难的是测试context switch的时间。思路：在单CPU上运行两个进程，并且使用两根管道连接它们。第一个进程，在管道A中写，并且等待从管道B中读。因为第一个进程需要等待管道B来读取，所以操作系统就把阻塞了，然后转到第二个进程，第二个进程是往管道B里面写，同时等待管道A中读，当第二个进程需要读的时候，它也阻塞了，此时又切换回第一个进程，这样循环就建立了。通过多次重复，就可以得出结果了。

linux下有一个sched setaffinity系统调用可以保证两个进程运行在同一个CPU中。

实测在阿里云学生机上面，系统调用是0.287微秒，进程上下文切换是1.343微秒。

7. Scheduling: Introduction

低级别的机制，例如进程间的上下文切换我们已经了解了。现在我们需要理解高级别的策略了。

工作量假设

workload，即工作量，对于我们之后做出决策是至关重要的，但是目前我们的假设是有一点不切实际的，但是最终会成为一个可行的方案。再次强调，接下来的内容有点荒唐，但是请先接受。

1. 所有的进程运行的总时间一致。
2. 进程同时抵达。
3. 一旦开始，进程就必须执行完成（不可被中断）
4. 所有进程只使用CPU
5. 每个进程需要的时间是确定的

调度的指标

我们需要有指标来评估每种调度的好坏。目前只使用一个叫turnaround time的指标。计算也很简单，就是一个job完成的时间点减去这个job开始的时间点。

FIFO

先到先得，也叫First Come, First Served (FCFS)。如果假设每个job运行的时间是10ms，那么非常容易计算出turnaround time的平均是20ms。

现在，我们把假设1去掉。那么每个job的时间就不再是相同了，如果按照先来先得，那么如果第一个进程使用了超级久的时间，这样turnaround time的平均值就会非常大。

SJF

**Shortest Job First (SJF)**，最短优先。看上去非常完美，也可以证明确实是最优解。但是一旦我们把条件2放松，即进程并不是同时抵达的，这个算法就崩掉了：一个超级费时的job先到了，因为整个系统中只有它，那么当然是让它运行，接下来到了几个用时短的进程，但是由于条件3的存在，它们只能等待。

STCF

Shortest Time-to-Completion First。接下来我们把条件三也去掉，这样我们可以通过之前讲述的定时中断来打断进程的运行从而完成。这样就可以通过preempt（抢占）来缩短。

任何时候，只要当一个新的job加进来，定时器就会决定哪个job会最快完成，那么就让它执行。

新的指标：响应时间

之前我们通过放宽123三个条件，完成了这三个算法的构思。但是现在的应用，很多都是用户在屏幕前操作，所以这里需要新增一个指标——response time响应时间。

响应时间的定义也简单： 响应时间 = 第一次运行的时间 - 到达的时间

显然在这个指标下，STCF表现异常差劲，它会让最先完成的进程完成，而最后完成的那个进程，需要等待超级久的时间。

Round Robin

RR算法，让进程执行一个time slice，或者也叫scheduling quantum，然后切换到下一个job。不停重复，直到job完成。注意，时间片的大小，必须是时间中断的倍数。显然如果时间片越小，那么响应时间越短。当然太小的，context switch就会比较多，这部分开销就会变大。所以时间片大小的决策，也是一个trade-off的过程。

有得必有失，RR的turnaroud time是所有算法中，最糟糕的，没有之一。

合并IO

这里，我们将放宽条件4。当一个进程需要IO操作的时候，系统会让其阻塞，所以对于调度器来说，阻塞之后选哪个进程继续运行是一个问题。同理当IO完成的时候，如何抉择也是同样的。

No More Oracle

最后一个条件，操作系统其实压根不知道这个进程需要多久，也就是，还需要继续改进。

总结

本章中我们提出了两种度量方法，也提出了4种调度算法，明白了在turnaround time和response time之间的不可调和的矛盾。

8. Scheduling: The Multi-Level Feedback Queue

**Multi-level Feed- back Queue (MLFQ)**，最为有名的进程调度算法，中文翻译成多级反馈队列。

提出这个算法的人，获得了图灵奖，在现代操作系统中有着极其重要的作用。该算法同时着眼于之前我们提到的两个度量：turnaround time 和 response time。

MLFQ：基础规则

首先有很多个列队，每一个队列都分配了一个不同的优先级，一个job只能属于一个队列，在优先级更高的队列中的job会优先执行。如果一堆jobs在同一个队列中，那么使用RR算法调度。总结起来就是两条：

• 规则1：优先级队列高的job先执行，只要有优先级高的队列，那么优先级低的队列中的job是无法执行的。
• 规则2：同一优先级的job之间使用RR。

显然现在的问题就是，我们如何把job放到队列中去，MLFQ算法会根据它对job的观察，来进行调整。通俗讲就是通过过去推测未来。

如何改变优先级？

接下来我们先做出一些假设：

• 规则3：当一个job到来的时候，它的优先级是当前系统中最高的。
• 规则4a：如果一个job使用了全部的时间片，那么优先级就需要降低。
• 规则4b：如果一个job还没有用完时间片就放弃了CPU时间，那么优先级不变。

这里显然会导致一个问题，如果一个进程不使用完时间片，那么它的优先级永远是最高的，而之前规则1规定了，在有高优先级的情况下，低优先级是不能执行的，这就会导致饥饿问题。

第二个问题就是，job只要没用完时间片，比如在即将用完之前，去读取一个文件，那么就会放弃CPU，这样就能一直保证在最高的优先级队列中。

最后一个问题是，如果一个进程一开始用CPU比较多，然后掉到了低优先级队列，之后进程改变了状态，但是它永远都在优先级低的队列中了，这不公平。

优先级提升

为了防止饥饿问题的产生，最简单的方法就是定期提升所有job的优先级，所以规则5诞生了：

• 规则5：经过一定的时间，把所有的job放到最高优先级的队列中去。

Better Accounting

接下来需要解决的问题是，怎么解决之前提到的第二个问题，即如果有恶意的进程，故意在时间片用完之前放弃CPU来保持高优先级，所以我们只需要修改下规则4a和4b即可，修改过后的规则如下：

• 规则4：只要一个进程用完了它所给的时间，就会被降级。

调整和一些其他的问题

如何具体参数化这个调度器呢？

越高级的队列的时间片越小等等，但是这个问题终究还是多种多样的，因为不同的实现是不同的。

9. Scheduling: Proportional Share

这一部分介绍另外一种调度器——比例分享调度器，有时候也叫做公平调度器。

它基于这么一个需求：希望每个job所占的CPU百分比是固定的。

基本想法：用中彩票的思想

就最简单的想法就是用ticket，假设两个进程A和B，A有75张tickets，B有25张，那么A就有75%的CPU，B有75%的CPU。那么只需要生成一个随机数，如果落到了0-74之间执行A，否则执行B即可。

ticket机制

ticket currency，即每个进程还可以接着对自己获得tickets再次进行分配。ticket transfer，一个进程还可以把自己的ticket交给别的进程。ticket inflation，没想到吧，这东西还能通货膨胀，当然这必须在一个进程互相信任的系统中，一个进程如果确实需要更多的CPU，那它就可以增加自己手中的ticket。

实现

实现真的超级简单：一个链表其中每个节点是进程，一个良好的随机数生成器，一个数字记录系统中ticket的总数。只需要生成一个随机数，遍历链表，找到那个进程，然后它就可以执行了。

如何分配ticket？

这是一个棘手的问题，其中的一种解决方法是：用户有一些选票，他可以把这些选票分配给任何job。然而这并不是一个实际的方法，因为它根本没告诉你到底怎么做。

为什么不是确定性而是使用随机呢？

随机在对于比较长的时间中，效果不错，但是如果是时间很短的进程，可能就没那么理想，于是就有了stride scheduling，一种确定的公平的调度器。也是很简单：每个job都有一个stride，可以理解为就是ticket的倒数。具体算法就是：每次选择最小的stride的进程（一开始大家都是0，那么随机选择即可），执行它，然后加大它的stride（加大方法就是它目前的值加上一个stride）。不停循环即可。

因为stride是票数的倒数，所以票数越大，stride就越小；stride越小，每次需要加的stride也小，就越可能执行到。

这个算法的最大缺点是需要维护一个global的状态，不然当有新的进程到来的时候，因为肯定是0，那么新进程会一直霸占CPU，而显然在随机算法那里不会有这个问题。

Linux的CFS

Completely Fair Scheduler (CFS)，完全公平的调度方法。大多数的调度算法，都基于固定时间片，CFS则不然，它的目标就是在所有的进程之间公平分配。

基本想法

通过一个叫virtual runtime (vruntime)的东西。只要进程运行，那么这个vruntime就会增长。每个进程的vruntime都会以相同的速度增长，当需要调度的时候，就让最低的vruntime的进程执行。

显然如果调度频繁，那么context switch开销大；不频繁则保证不了公平性。所以使用了一些控制参数来进行调控。

第一个参数是sched_latency，该参数用来调控在切换之前，一个进程应该运行多久。典型的值是48ms，所以如果有4个任务那么就是每个进程运行12ms。

第二个参数 min_granularity，因为如果进程太多，那么会导致每个进程分到的时间太少了，这个值就是用来保证每个进程分到的时间不会低于这个值。

注意，CFS本身也需要用到定时中断，所以也必须是倍数。

加权

当然CFS允许给某些进程更高的优先级。但是它使用的不是ticket机制，而是用的nice等级，一个从-20到+19的值。数字越小优先级越高（-20优先级最高）

根据这张表格，可以把nice值映射到一个权重，然后可以计算出每个进程应该占据的时间片大小，公式如下：

同时，vruntime的计算公式也要变更一下：

emmmm里面的数学原理暂不深究了。

用红黑树

对于一个调度器来说，它必须马上让一个进程执行，但是之前是一个链表，通过链表寻找会比较耗时。CFS就通过一颗红黑树来代替链表。

红黑树只记录可以运行的进程，如果进程睡眠或者阻塞了，就会被从红黑树中移除。

处理IO进程和睡眠进程

之前说了如果进程睡眠或者阻塞，会被从红黑树中移除。那当醒来的时候，它的vruntime会很小，那岂不是就一直霸占CPU了吗？不会的，CFS会将这些进程的vruntime设置成红黑树中最小的vruntime。

总结

在这一部分我们讨论了什么是按比例分配的调度算法，分别有彩票型、stride型和CFS这三种。前两种都是理论型的，只有CFS是真正实现了的。而CFS本身也特别像RR，只不过是带了权重的RR。

从上面的分析中我们也发现，如果一些进程因为IO或者睡眠等问题放弃CPU，那么之后会得到更多的CPU。

但是对于一些云平台，按照比例分配的调度算法可以发挥它们的优点，比如我固定分配30%给我的虚拟机。

10. Multiprocessor Scheduling (Advanced)

之前讲述的都是在单核CPU中，这一章我们将来学习在多核CPU中如何进行调度。

多处理器架构

多处理架构通过cache来共享数据。在单CPU架构中，cache的存在是为了加速；在多CPU中，每个CPU都有自己的缓存，这就导致了cache coherence（缓存一致性）问题的发生。

cache是基于局部性原理的，即时间局部性和空间局部性。

如果要解决缓存一致性问题，有一个解决办法：CPU可以通过总线去监视别的CPU（bus snooping），每个cache都通过观察总线来得知内存的变化，如果CPU知道自己的cache中的数据变了，要么更新这个数据，要么抛弃这个数据。

Synchronization

在共享数据的时候，mutual exclusion primitives（互斥原语，最典型的就是锁）能够保证正确性。

还举了一个删除链表头节点的例子，在多线程环境中会出现问题。

Cache Affinity

Cache Affinity，缓存关联性。一个进程获得CPU时间的时候，会在CPU缓存和TLB中建立一堆状态。如果下一次这个进程还是在同一个CPU上跑，那么就能够运行得很快。如果每次都换一个CPU跑（由于缓存一致性协议的存在，能够保证进程是可以正确运行的），那么速度就会比较慢。所以调度算法应该尽可能让某个进程一直运行在相同的CPU上。

单队列调度

最简单的就是把所有的jobs放到一个队列中，我们管这个叫single-queue multiprocessor scheduling，简称为SQMS。就是根据现在有多少个CPU，来选择多少个最佳作业。比如有三个jobABC，然后只有两个CPU，那么这个算法就把CPU分给AB，下一轮分给CA……

它的缺点是缺乏可扩展性，编程人员需要为其加入一些锁，来保证它运行的正确性。从上面的描述中也可以看到，它缺乏关联性。如果要能够具有缓存关联性，那么算法会比较复杂，书中没有介绍。

多队列调度

multi-queue multiprocessor scheduling，MQMS，用来进行优化。拥有多个队列，每个队列都是一个调度算法。当一个job进入系统的时候，会被分配一个队列（通过随机或者别的什么方法），接下来就是独立调度了，避免了共享和同步的问题。

但是又有新的问题了：负载均衡。如果某一个CPU队列中的任务完成了，那么CPU就会空闲。可以通过migration来解决这个问题，而在队列之间移动继承，需要一个叫work stealing的技术，简单来说就是每个队列每隔一定时间去看看别的队列的情况，如果发现别的队列比自己忙，就偷一些job过来放到自己这里。

Linux Multiprocessor Schedulers

很遗憾，在linux中并没有一种公共的解决方案来解决这多处理器调度的问题，目前有三种方案：O(1)、CFS和BFS，这里只简单介绍一下。BFS使用了单队列，而另外两个使用的是多队列。所以从这个角度来说，单队列和多队列其实都是成功的算法。

总结

单队列非常的简单，在负载均衡这部分表现优异，但是在缓存关联性这块表现不佳。对队列恰好相反。

11. 对CPU虚拟化的阶段性总结

我们学习了OS如何虚拟化CPU，有很多机制：trap和trap handler，timer interrupt，在进程切换的时候OS和硬件是如何保存它们的状态的。同时可以看到OS是一个偏执狂，它既希望自己能够控制机器，又希望程序能够跑得足够快。同时我们学到在turnaround time 和 response time不可调和的矛盾，就算在现在，linux也在为三个多处理器调度而争论的喋喋不休。

13. The Abstraction: Address Spaces

早期的系统

早期的系统，压根就没有对内存的抽象，操作系统放在内存的低地址中，然后用户程序使用其余的部分。

多程序和时间分享

然后就有了多程序系统，操作系统通过context switch进行切换来使用CPU，但是内存中的程序呢？难道每一次context switch就需要把整个程序从内存中移入和移除吗？所以我们必须在内存中保留进程，那么就需要对内存地址进行保护。

Address Space

所以我们需要抽象出一个物理内存的概念，这样可以方便使用——于是address space地址空间就诞生了。在系统中执行的程序的眼里，地址空间就是物理内存。

为了简便起见，地址空间里面有三个部分：代码，堆，栈。

代码位于地址空间的低地址，接下来是堆，而栈则位于最高地址。堆和栈通过不停增长来填补空白区域。

也就是当程序运行的时候，堆栈部分会进行扩大或者缩小。

目标

接下来开始虚拟内存，我们需要首先指定好目标：

1. 虚拟内存必须是透明的
2. 虚拟内存必须高效，通过使用TLB，能够调和时间和空间。
3. 虚拟内存必须具备安全性，意味着只有进程自己可以修改自己的内存内容。

总结

我们对虚拟内存有了最基本的认识，也提出了目标，接下来就来实现这些目标。

特别提醒：你在程序中打印的地址全部是虚拟地址，无一例外。

1
2
3
4
5
6
7

int main(int argc, char *argv[]) {
    printf("location of code : %p\n", main);
    printf("location of heap : %p\n", malloc(100e6));
    int x = 3;
    printf("location of stack: %p\n", &x);
    return x;
}

这段程序的输出看上去像是真的物理地址，然而其实还是虚拟地址。

14. Interlude: Memory API

内存种类

程序只能控制两部分内存，一部分是栈，但是这部分的分配和回收是隐式的，所以这部分的内存可以理解为是自动的，由编译器自动帮我们完成的。第二部分是堆内存，这部分的分配和回收就是显式的了，所以要慎重！

系统调用——malloc

通过传入一个具体的空间的值（字节为单位），这个系统调用会替你去堆空间开辟空间，如果成功返回指向新开辟空间的指针，否则返回NULL。

在使用malloc的时候，我们一般搭配sizeof使用，需要注意sizeof是一个编译期间才知道结果的函数，所以要谨慎使用。

1
2
3
4
5
6
7

//64位机器中
int main(int argc, char *argv[]) {
    void *x = malloc(10 * sizeof(int));
    printf("%d\n", sizeof(x));	// x=8
    int y[10];
    printf("%d\n", sizeof(y));  // y=40
}

为什么malloc返回的是一个void*，这是为了让程序员自己决定应该强制转型成什么。

系统调用——free

free只有一个参数，那就是malloc返回的那个参数。从这里你可以看到，申请的内存的长度，并没有被当成参数传入，所以这部分由库自己来解决的。

常见错误

在java中，内存的分配和回收都是交给垃圾回收器的，所以很爽。但是在c语言中，就需要自己管理，于是就有下面这些错误。

忘记分配内存了

1
2
3

char *src = "hello";
char *dst; // oops! unallocated
strcpy(dst, src); // segfault and die

这个会引发一个段错误。

没有分配足够的空间

就算没有分配足够的空间，程序也能运行，但是其实上发生了一个buffer overflow的问题。至于不同的操作系统如何对待这个问题，见仁见智了。

忘记初始化内存空间

问题不是很严重，但是需要尽量避免。

忘记释放内存空间

典型的memory leak，在长时间运行的程序中（操作系统本身就是这么一个程序），这是一个非常严重的问题。就算是像java这种语言，一样会遭遇这个问题。

短时间的程序可能不是那么严重，因为一旦进程运行完毕，操作系统就会回收进程的所有内存，这这部分内存自然包含了你malloc的内存，所以影响不是很大，但是！！请一定记住malloc了就free。

过早释放空间

你的程序还需要一块空间但是你却过早的使用free释放了它，导致一个叫dangling pointer的问题（野指针，悬空指针）

重复释放一块空间

double free问题，至于会发生什么问题，it depends

参数错误

free的参数，必须要是malloc返回的指针，所以别瞎释放。

底层OS支持

其实malloc和free准确讲应该是一个库函数，它们底层依靠别的系统调用来实现。

其中一个底层系统调用就是brk，该指令用来改变程序中堆的末尾地址，通过传入一个地址来进行修改。所以增大或者减小heap的实际就是通过这个系统调用来实现的。另外一个sbrk作用一样，只不过传入一个增加的地址大小。

虽然底层是通过brk和sbrk来实现的，但是实际中请千万不要去使用。

brk的本质其实就是移动了堆顶层的一个指针，这样就可以让堆空间增加了。

mmap的本质则是在堆和栈之间找到一块空间，分配给它。显然当我们需要的空间比较多的时候使用mmap，而空间比较小的时候brk即可（但是记得自己不要使用）

除了上面提到的，你还可以通过mmap系统调用来获得一片匿名的内存地址空间，称为swap space。和heap非常像，但是不是heap。

其它调用

calloc，就是malloc加上初始化内存为0。 realloc用来改变分配的内存的大小。

总结

这部分我们介绍了内存分配的API以及其可能存在的问题。

15. Mechanism: Address Translation

之前的CPU的部分，我们用到了limited direct execution，主要思想就是普通的东西进程自己解决，但是需要特殊的东西的时候需要操作系统来帮忙。这种方法既保证了高效性，同时也保证了对硬件的控制。同样的，在内存虚拟部分，我们也需要这两个目标——高效且保持控制。

hardware-based address translation，通过硬件来完成虚拟内存到真实物理内存的映射。而操作系统则必须能够管理内存，并知道哪些内存正在使用。

假设

我们首先假设地址空间必须被连续的放在物理内存中，所以我们也同时假设地址空间的地址必须比真实物理内存的小，最后我们假设所有的地址空间都是一样大的。上述假设的存在是为了便于理解，之后会慢慢去除这些假设。

一个例子

下面是一个最简单的C语言的代码片段：

1
2

int x = 3000;
x = x + 3;

这段代码，假设编译完成之后的汇编代码是这样子的：

1
2
3

movl 0x0(%ebx), %eax   ;把ebx的内容移动到eax中   			内存空间位置：128
addl $0x03, %eax       ;把3加到eax中							 	内存空间位置：132	
movl %eax, 0x0(%ebx)   ;把eax放回到ebx						 	内存空间位置：135

毫无疑问这三条汇编是在程序的代码段中，那么程序就是这么执行的：

1. 从地址128中取来第一条指令
2. 执行这条指令，即把ebx指向的内容（其实就是x，位于栈中）放到eax中
3. 从地址132中取来第二条指令
4. 执行，这一条不需要和内存交互
5. 从地址135中取来第三条指令
6. 执行，并且把eax的值放回到ebx中。

动态迁移（基于硬件）

dynamic relocation，使用两个寄存器，一个是base register，另外一个是bounds register（AKA limit register）。通过使用它们可以保证我们的进程只会在自己的空间中运行。这个方法就是我们最常说的，基址寄存器+界限寄存器的组合。

程序自己以为自己的内存空间从零开始，但是通过基址寄存器，可以轻松的找到它在内存中的真正地址。由于这是在程序运行的时候完成的，所以才叫dynamic。

至于界限寄存器么，就是一开始用来判断有没有越界的。可以有两种实现，第一种是存放虚拟地址的上界，第二种是存放真实物理地址的上界，两种在逻辑上是完全相等的，为了简便，我们采用的是第一种。

注意！这两个寄存器的真实位置是在CPU上，人们称那些在处理器中，帮助进行address translation的那部分为memory management unit (MMU)

硬件支持的总结

之前我们说CPU提供两种模式，分别是用户态和内核态，CPU需要一个处理器状态字，以此来表明目前自己运行在哪个模式下，通过一些特殊场景（系统调用或者中断），CPU可以切换自己的模式。

然后CPU还集成了电路能够完成base register和limit register这俩寄存器的功能，而且电路非常简单，时间损耗几乎可以忽略不计。此外，硬件还需要提供特殊的指令能够更改这两个寄存器的值，当然这些指令必须是特权的，只有在内核态才可以执行。

下面是一张表格的总结：

操作系统的问题

硬件提供了那么多的功能，操作系统就有了新问题需要解决：

• 在进程创建的时候，需要为其开辟内存空间，在之前的假设中（每块大小固定），这非常容易。操作系统本身维护了一个叫free list的列表来追踪哪个内存空间是空闲的。你可能会说要是大小不固定该怎么办呢？这不是本章讨论的问题。
• 进程结束之后需要回收空间，只需要简单将那块内存加入到free list中即可。
• 当context switch的时候，由于CPU的base register和limit register只有一对，所以需要保存并且加载它们的值，那么应该把它们放那里呢？process control block (PCB)中。
• 第四点，操作系统需要提供异常处理器（在系统启动的时候就创建好），这样如果有进程想要访问别的进程的内存，CPU会触发一个异常，然后异常处理器就可以处理——直接干掉那个进程。

上图展示了在启动的时候OS命令硬件都做了什么：首先是操作系统内核初始化了陷阱表，然后是硬件会记住这几个地址：系统调用处理程序的地址、时钟处理程序的地址、非法内存访问处理程序、非法指令处理程序。然后内核就会启动定时器，硬件在内核的操作下启动定时器，每隔一段时间触发一个时钟中断。操作系统还会初始化一个进程表（用来管理进程）、一个空闲内存空间表。启动到此结束。

到系统需要运行A进程的时候，它需要在进程表中为它分配条目、在空闲内存空间表中为它找到指定的空间、从PCB中取出对应的基址寄存器和界限寄存器的值，做完这一步才从trap中返回。

总结

在这一部分我们扩展了LDE，有了地址转化，操作系统可以轻松掌控各个进程的内存，而且由于是硬件支持的，所以非常高效。

当然也有缺点，比如如果一个程序的堆和栈都比较小，那么中间一大片内存就被浪费了，被称为internal fragmentation，这主要是由于我们采用的每个进程固定的大小所造成的，所以我们需要一个更好的机制来充分利用内存空间，显然对于base和bounds来说，太粗粒度了，我们接下来进行讨论。

家庭作业

1. 计算对应的地址，非常简单。
2. 假设最大的虚拟地址是929，那么界限寄存器的值应该设置成多少？我一开始以为是929即可，后来发现需要930，所以说明了界限寄存器的值是取不到的。
3. 计算最大的base寄存器的值。也很好算

16. Segmentation

之前也提到了，因为使用base + bound寄存器会浪费空间，为了解决这个问题而生。

广义的base和bounds

Segmentation就是为了解决这个问题的。之前说的base + bound 浪费空间，是因为base + bound指定的是一整块空间，那为什么不再分的细一点，使用逻辑的段来代替地址空间呢？

一个段是一个连续的地址空间，那么我们可以有三个段，分别是代码段、堆段和栈段。这样这三个部分就可以分别定位，而不是要在一块空间中了，这样也就不会有堆栈之间的空间的浪费了。为了实现这个，只需要三对寄存器保存即可。

所以段错误其实就是访问非法地址的错误，但是其实就算计算机不支持分段，该术语仍然正确。

然后又提出了offset的概念，表示相对于自己当前的段偏移的字节数，只有把offset加上base才是真正的物理地址。

我们应该使用哪个段呢？

硬件上使用的是段寄存器，那么问题来了，需要知道偏移量才可以计算出真正的地址，如何知道偏移量呢？

一种简单的方法就是根据地址划分，前几位是段，后几位是offset。因为我们说了我们有三个段，所以只需要前两位作为段号，剩下的作为偏移量。

栈怎么办呢

因为栈是向低地址方向增长的，所以其实我们还需要一位来记录数据结构增长的方向。

共享支持

那既然有了一位代表增长的方向，为什么不多来几位来丰富功能呢？为了支持共享，拿出一个protection bits，如果设置成read-only，那么就可以进行共享——而且进程本身还并不知情。

但是与此对应的是，除了要验证bound寄存器的值，还需要验证protection bits的值。一旦有进程强行写一个只读段，那么硬件就会触发异常，进入处理程序来处理这个异常。

段的粒度

目前只有三种段，所以是粗粒度的coarse-grained，因为它把地址空间分成比较大的块。但是在早期的系统中，反而是细粒度的，更加灵活。

如果需要的段比较多，那么就需要一个segment table来保存信息。

操作系统支持

看上去用段来进行内存分配非常不错，但是还是有一些问题的存在：

1. 操作系统在context switch的时候应该干些什么？当然是需要保存相关的寄存器的值啦。
2. 在内存大小变动的时候（比如创建对象需要扩大heap的时候），操作系统需要更新寄存器的值。
3. 为段找到物理内存是一件麻烦的事情。

随着使用，内存马上会千疮百孔，就很难找出一片合适的空间来使用了，这个问题称为external fragmentation。一个解决方法就是对内存进行压缩，但是压缩的成本比较大，因为需要停止进程，而且所需时间也不少。另外一种解决方法是使用一个free-list管理算法，尽最大努力让大块内存能够分配，具体的实现有best-fit，worst-fit, first-fit以及更为复杂的buddy algorithm，但是不论怎么努力，内存碎片，永远存在。

内部碎片简单来说就是堆与栈之间空闲的内存空间，外部碎片则是各个段之间的内存空间。因为最开始是给一整个程序分配内存，所以会有内部碎片；优化了之后是给每个程序的每个段进行分配，所以会有外部碎片。

总结

内存分段让内存分配更加灵活，避免了大段内存空间的浪费。同时也很效率，同时还支持共享。

接下来我们要解决两个问题：第一个是碎片问题，第二个是段的分法还是不够细，期望找到一种更好的方法。

家庭作业

1. 比较简单，就直接跳过了。只不过我觉得如果是段错误，那么说明任何一个都无法匹配，不知道为什么答案里面居然有违反了哪一个，这点不甚理解。
2. 将第一题中的所有有效地址中最高和最低的列出来。
3. 只需要将两个段的有效长度加起来小于总物理内存即可达成。

17. Free-Space Management

这部分我们将要探索一下free-space management，空闲空间管理。对于固定大小的比较简单，而对于随机大小的则比较难。

假设

之前我们也留下了一个问题，为什么在释放内存的时候不需要指明大小呢？

内存的分配，可以是操作系统分配空间给进程，也可以是进程本身使用malloc来分配heap空间。这两个分配内存空间都可以使用free list来完成。

在内存中管理堆空间中空闲的块的数据结构叫做free-list（这段话应该有点问题），包含了对所有空间的引用。虽然叫list，但是实际上不一定是list。

internal fragmentation：每当请求内存的时候，都会分给固定大小的内存块，这样就造成了内部的浪费。

external fragmentation：频繁回收和分配，会导致小的内存块夹杂在已经分配的内存块之间，所以叫外部碎片。操作系统使用segmentation的时候和用户使用malloc的时候都会发生这个问题。

我们接下来主要关注external fragmentation——堆中的空间碎片。因为内部碎片的问题很简单，就是因为你给了程序它请求空间更多的内存，导致了内部碎片的发生。

我们假设，一旦一个程序使用了malloc分配了内存，那么就会返回堆中的一个指针，可以说这块内存被这个程序所拥有了，所以没办法做压缩。

最后我们假设分配连续的内存空间，并且在某些条件下，内存区域是可以增长的。

低级别的机制

我们首先介绍大多数分配中使用的机制。

• 讨论基础的分割和合并
• 如何快速且轻松的追踪内存区域的大小。
• 如何构造上面所说的free-list

分割和合并

free-list可以是一个链表，每个节点记录了当前可以使用的空闲内存的起始点和长度。对于大于所有节点的长度的内存块，遍历链表可以得到NULL，而对于等于长度的，可以找到一个完美的点来契合，那么对于小于指定长度的呢？它会找到一个节点能够分配出空间，然后对这个节点进行分割，并对链表进行了修改。

同理进行空间释放的时候，就会把几个空闲的节点进行合并，制造出一块大的连续的空间。

追踪分配空间的大小

只需要在分配空间的时候，在head block里面保存信息就行了。由于这部分需要占据一定的空间，我们假设是N，所以当用户要求分配10个字节的空间的时候，真正需要去找N+10字节的空间来满足需求。

实现Free List

当我们分配一个新节点的时候，你需要使用malloc来为节点分配内存，而是需要在空闲的空间中创建出一个list，即一开始heap创建的时候就有一个list，然后这个list只有一个头部信息。

调整Heap大小

一开始程序分配到的heap会比较下，然后通过sbrk系统调用来增大heap。具体就是通过OS找到一些空闲的物理页，然后会把这些空闲的物理页给需求的进程。

基本策略

Best fit

通过扫描整个链表，找到所有能够满足要求的最小值。

Worst Fit

扫描整个链表找到最大的那块内存，分配。研究表明这个策略效果很差。

First Fit

从链表开始，只要找到第一个能够放得下，就使用。由于只要找到第一个就可以使用，不需要扫描整个list，所以效率较高。

Next Fit

和First fit相同的思路，只不过是它还有一个指针指向了链表当前的位置，这样下次的查找就从这个位置开始找，这样可以有效均衡整个链表。

其它的方法

Segregated Lists

如果某个应用经常申请固定大小的，那么使用一个单独的list来分配。这样就不会再有碎片的问题了，而且查找和使用都会很快。

当系统启动的时候，会为内存对象分配一些object caches，这些object caches就是segregated free list。比如inode，由于之后要频繁使用，所以为它开辟了一个list，之后如果需要为inode申请内存，只需要去对应的list中获取即可。而且这么做也有池化的优势，避免了数据结构的创建和销毁，节省了时间消耗。

Buddy Allocation

因为合并是一个非常重要的过程，所以有一些对合并进行改进的操作，其中一个就是binary buddy allocator，二分伙伴分配程序。

一开始空闲空间指定为2^N，如果有请求空闲的内存，那么就把空闲空间一分为二，直到找到足够大的空间。

假设有一块64K的空间，需要分配7KB。那就不停分下去，直到8KB（所以会有内部碎片的问题）。因为分的时候是一分为二，所以合并的时候会非常简单。

其它办法

上面也提到了一些算法的缺点就是需要遍历整个链表，这就导致了速度慢，那么可以用别的数据结构来代替链表提升性能。

总结

我们介绍了一些初级的内存分配算法。

家庭作业

1. 第一个作业是没有启用合并的，会发现内存随着malloc和free越来越支离破碎。
2. 使用WORST来代替上面的BEST策略，观察结果。发现碎片更多了。
3. 使用FIRST来代替上面的策略，观察结果。发现搜索的次数减少了。
4. 空闲列表的排序规则，也会影响策略的结果。
5. 如果不合并，会发现后面根本无法得到新的且满足要求的内存块；只有开启了空闲内存合并功能最后才能分配的出内存。
6. 内存分配得越多，越不容易分配的出内存空间来。
7. 如果希望能够得到高度碎片化的空间，有什么好的办法？

18. Paging: Introduction

有这么一种说法，操作系统使用了两种方法来解决空间的管理问题：第一种是把东西（这里指的是内存）切分成大小可变的块，比如在虚拟内存中的segmentation，这个方法的问题是存在碎片；第二种是把东西（这里指的是内存）分成大小相等的块，我们称之为paging。与此同时，我们把物理内存看成是一个数组，其中的每一个元素都是page frames。

一个简单的例子

图就省略了，脑补即可。paging技术相比之前的段技术，最大的优点就是灵活性，其次的优点是简单。

为了记录每个进程所使用的虚拟页和物理页之间的关系，我们需要一个叫page table的数据结构来记录一下，该数据结构是每一个进程都有的。

假设有一条指令被从内存中已经读到了CPU中，并且即将要开始执行，这条指令是movl <virtual address>, %eax，为了能够执行这条指令，我们首先要把这个虚拟地址分成两部分： virtual page number (VPN)和offset。接下来通过查表，可以把这个VPN转换成真实物理的页的号码，即physical frame number (PFN)，这样就能找到真实的物理地址了，如下图所示（64字节的地址空间，128字节的物理内存空间，页的大小16字节）：

上面的这部分是非常好理解的，那么问题是：这个page table在哪里呢？有多大，里面典型的内容是什么？分页会让系统变慢吗？

page table在哪里

在32位的寻址空间中，一页的大小普遍是4KB，即12位，那么剩下的20位就是VPN，那就需要2²⁰条记录，假设一条记录（page table entry (PTE)）只有4字节，那也要4MB，而且这是每个进程的！显然这也太大了，如果一个系统有100个进程，那内存就要分400MB空间在这上面。这个page table太大的问题，这里先暂时放一放，并不打算解决。

page table被放到内存中，由操作系统管理。所以页表本身其实不是由MMU这些硬件来管理的，而是操作系统的软件管理的。

page table究竟是什么

最简单的实现是一个数组，叫做linear page table，数组的下标是VPN（我一开始理解成map了，是错误的），里面的内容是PTE（PTE本身就包含了PFN，见下图）

这个PTE里面除了存PFN，还存放了valid bit用来指示这个页有没有启用，比如一开始程序就代码段和堆栈的页被启用了；protection bits（如果一个页只允许读但是你强行要写的话，就会进入trap然后把控制权转移给OS）；present bit（0）用来指示这个页是在物理内存中还是在磁盘中；dirty bit用来指明该页是不是已经在内存中被修改过了；reference bit (a.k.a. accessed bit)表明这个页被使用了多少次，在之后的页置换中有作用；还有2的U/S位用来指示在用户态的进程能否访问这个页。

也就是在以极致省空间为前提下，可以让PTE=PFN。

分页慢

除了页表太大意外，还有一点就是慢。显然操作系统需要首先获取到页表，执行转换工作，然后再去对应的物理页中把数据取回来。也就是我们额外进行了一次内存的操作，势必会让程序跑得慢。

获取页表，我们可以假设有一个page-table base register寄存器里面存放了当前进程的页表的位置。

现在的问题有俩：页表所占空间太大以及查询页表需要额外的时间导致程序变慢，我们需要解决这两个关键的问题。

内存追踪

这部分用一个简单的例子来完成。假设有一个长度为1000的数组，我们现在要将其每个元素都赋值成0。然后将其反编译，可得如下结果：

1
2
3
4

1024 movl $0x0,(%edi,%eax,4)
1028 incl %eax
1032 cmpl $0x03e8,%eax
1036 jne  0x1024

第一条指令：首先计算出虚拟地址（edi放的是数组基址，eas放的是index，4是int的字节数），然后把0扔进去。

第二条指令：index 加一的操作

第三条指令：比较一下当前的index和1000。

第四条指令：如果index比1000小，则跳到1024，即第一条。

为了讨论的方便，我们假设虚拟地址的寻址空间是64K，页的大小是1K。并且我们假设我们知道页表位于物理内存的1K处。

接下来，我们需要知道指令的位置，从上面看到是从1024开始的，也就是说从第二页（VPN=1，因为是从0开始计数的）开始的，我们假设VPN1被映射到了PFN4。

然后是数组本身，一共是4000字节，那么我们假设虚拟地址是40000~440000，并且对应关系是（VPN39对应PFN7，40对应8）。

那么程序真正运行的时候会这么做：

1. 需要取得对应的指令，那么就首先需要去页表里面查出，这条指令对应的虚拟地址的真正物理地址在哪里。
2. 然后指令需要被放到CPU里面去执行
3. 可以看到还有一个mov指令，也需要把虚拟地址转换成真实地址。

所以一次循环里，我们一共访问内存10次，4次是把指令放到内存中，一次更新index，还有五次是进行地址转化。

总结

我们介绍了paging技术，同时也发现了它的两个问题，耗费内存空间以及多次查询导致的效率低下问题，接下来的两章就用来解决它们。

家庭作业

1. 页表的大小就是虚拟内存空间大小/每一页的大小。为什么我们不希望每一页的大小非常大呢？因为如果非常大，就会有很多内部空间被浪费掉。同样每一页要是太小，那么页表就会很大，所以如何确定每一页的大小是很有意义的。
2. 随着地址空间中的页被分配到对应的物理空间，越来越多的地址变得有效。

19. 更快速——TLB

我们如何来加速地址转换的这个过程呢，并且尽可能少的使用内存。有没有什么硬件能帮助我们实现，操作系统需要怎么配合呢？

物理（硬件）层次上，有一个硬件translation-lookaside buffer（TLB）来帮助我们，它本身是MMU的一部分（也就是在CPU上的），本质上就是一块cache用来记录虚拟地址到真实物理地址的记录，所以还有一个名字叫address-translation cache。

所以在实际中，我们会首先去TLB里面看看有没有映射，如果有那就直接用（意味着不需要去内存的页表中查找了）

基本算法

硬件层面的算法：首先需要从虚拟地址中获取VPN，检查一下TLB里面有没有对应的记录，如果找到了，就说明是TLB hit，直接就可以进行转换。之后进行保护检查，如果检查通过就说明是可以访问的内存，那么就访问。如果没找到，那么就是TLB miss，我们就需要做一些额外的工作。硬件需要首先在内存中找到page table，并找到对应的那条转换记录，把记录放入到TLB中，然后重新找一次。

这里是不是很好奇为什么不是直接返回而是需要再找一次？？明明已经知道物理地址了，却还要“大费周章”？

这是因为用户态只能使用虚拟地址，也就是你找到的物理地址不能直接给用户程序，而是只能放到TLB里面，然后让用户再次执行这段指令。

举例说明

一段非常简单的代码：

1
2
3
4

int sum = 0;
for (i = 0; i < 10; i++) {
	sum += a[i]; 
}

我们在这里忽略sum和i，同时忽略从内存中取指令。当需要a[0]的时候，首先抽取出它的VPN，然后首先去TLB里面找，自然没找到。然后就会去页表里面找，并放一份到TLB中。接下来a[1]的时候就可以直接在TLB里找了（a[0]和a[1]有极大可能性在同一页中，其实a[0]~a[9]都有极大的可能在同一页里），速度大大提高。

所以在这次数组更新中，TLB的命中情况是这样的：miss,hit,hit,hit,hit….miss,hit,hit,hit…很显然，是空间连续性导致了这一结果。接下来，由于时间连续性，这段代码很有可能再被使用，所以命中率也非常非常高。

谁处理TLB Miss？

是操作系统还是硬件来处理呢？

早些时候用的复杂指令集，硬件可以完全处理这个错误。通过page-table base register，硬件是可以知道page table放在内存的哪里的。在IntelX86架构中，使用的是multi-level page table，而寄存器使用的CR3。所以其实绝大部分目前的计算机，还是用的硬件来处理的。

现在部分的计算机用的是精简指令集，这些指令集有software-managed TLB，如果TLB miss产生了，硬件会发生一个异常，暂停当前的进程并进入到内核态，使用trap handler，那么就可以更新TLB了。这里注意，回去之后需要执行的指令和一般的系统调用不太一样，别的都是哪条指令触发了系统调用，回去的时候调用的是下一条，而TLB这里回去的仍然是同一条（这个特性也决定了一定要特别小心，否则就是死循环），所以从这里也不难发现，进入到内核的时候，其实保存的程序计算器至少有两种模式：一种是指向当前的指令，另一种是指向下一条指令。

用软件实现的好处是简单，灵活性高，硬件实现简单。

TLB内容是什么？

一个典型的TLB里面可能有32/64/128个条目，其中的一条条目可能是这样的：

这里的other bits 和之前的PTE非常的像，但是是不同的！PTE中的有效位，是指进程可不可以访问这一个物理页；而TLB的一条，是指这个映射有没有效。显然如果在TLB都无法生效，进程压根就找不到对应的物理页，后面的PTE自然也就无所谓了。

TLB的问题：Context Switch

当进程进行切换的时候，显然TLB的内容也要切换（可以由硬件实现，也可以由操作系统实现，还可以两者一起）。

最简单的实现就是清空掉（这里的清空是把有效位设置成0，软件实现的话用指令，硬件实现的话就是当页表基址寄存器的值发生变化的时候用指令清空）TLB，有一条指令可以做到。当然代价就是下一次同一个进程再来的时候，又要重新进行缓存，这样子效率很低。

然后有一些系统支持多个进程共享TLB，通过一个address space identifier (ASID)的域，也就是用来分辨不同的进程的，这样就算是两条TLB的条目，也可以区分是哪个进程留下的。

问题：代替策略

对于所有的cache来说，一个避不开的问题就是cache replacement，当TLB满的时候，我们需要替换出一个，那么把哪一条记录踢出去呢？显然一切以最高命中率为前提来设计。接下来我们将会学习，在这里我们仅仅是介绍一下least-recently-used（LRU）。这个算法充分利用了空间连续性；当然也可以用随机剔除的方法。

真实TLB条目

选取了一台32位机器，使用软件管理TLB，其中页的大小是4KB，所以VPN是20位，offset是12位。但是奇怪的是，VPN在上图中居然只有19位，其实其中一半空间由内核使用。而PFN是24位的，所以可以支持物理内存为64G的机器。

上面还有一个G，如果该标志置位，说明这个页是所有进程共享的，那么自然就忽略掉ASID了。

然后是3bit长的一个Coherence位，D位的意思是dirty位，V位是valid位。灰色部分的是未使用。

总结

通过TLB我们可以有更快的速度来找到虚拟内存对应的真实物理空间。

当然有一个问题，要是一个程序需要的页数超过了TLB的数量，程序运行就会很慢，在下一章里我们讨论如何解决这个问题。而且这个技术也被数据库管理系统大量使用。

家庭作业

测量你的CPU的TLB的大小。

20. 更小的表

TLB的存在帮助我们快速的进行地址转换，但是还遗留了一个页表占据超多内存空间的问题。

简单的解决方法：更大的页

只要我的页更大，那么相应的VPN就会变小，这样页表的数目就会变少。当然更大的页带来的问题就是空间的浪费，也就是内部碎片的问题。所以大部分操作系统使用的还是4KB的页大小（当然其实大部分系统都支持各种页大小）。在数据库中，可以让页大小高达4MB并且在里面存放最常用的数据，这TLB只需要一条记录，自然就会减小页表的大小了。

混合：paging和segment

hybrid，我个人倾向于将其翻译为中庸，即采用了两种方法的长处。

这里我们使用paging和segmentation结合在一起。我们可以将程序分成三段，分别是代码段、堆段和栈段，然后将这三个段分别对应三张页表。

回忆一下我们在segmentation中的做法，有一个base寄存器和一个limit寄存器。在这一部分，在MMU中仍然保留有这个结构。但是我们用base来指向page table的物理地址，而limit寄存器则用来指向page table的结尾。

现在来假设一下，32位地址空间，前两个比特用来判断是哪个段的。那么当TLB miss的时候，通过查看前两个比特就可以知道是应该使用哪一对寄存器，然后到对应的地方去找。

缺点是什么？缺点是不够灵活，万一存在一个巨大的稀疏的堆，这样页表项又被浪费掉了；而且会有外部碎片的产生。于是人们接着寻找更好的方法

多级页表

舍弃掉分段的话，可以使用multi-level page table，相当于把一个数组变成了一棵树，这也是很多操作系统采用的。

简单来说就是通过page directory，利用多级目录的思想来“压缩”页表。

在page directory中的条目被称为page directory entries，它包含了一个valid bit和一个page frame number (PFN)。如果PDE是valid，那么就说明这条页目录条目所指向的页中，至少有一条是有效的。说起来拗口，其实就是如果在页目录表中的一条数据不是valid的，就说明它压根不指向任何一个页表。

这种方式最明显的优点就是节省空间（代价就是你要在内存中多查一次或者多次）

详细例子

有16KB虚拟内存空间，页的大小是64字节，所以虚拟内存的空间是14（2¹⁴ = 16KB）比特的，8比特用来给VPN，6比特用来给offset，页表拥有2⁸=256个条目。如果一个条目的大小是4字节，那么如果用传统的线性数组的方法，页表需要消耗1KB的空间。

256个条目，而一个页的大小是64字节，一个条目的大小是4字节，也就说一个页可以存放下16个条目，那么256个条目只需要16页就可以放下了，对应到page directory中就是16条记录，分别对应了16个页。256*4/64 = 16页。

所以我们将地址的前4比特作为页的查找项。有了这四个比特，我们就可以找到页目录中对应的那一条记录，通过这条记录我们能够找到对应的页表，然后再根据在PTE中的索引，我们就可以找到最终的记录了。

多余两层结构

在我们的例子中，只有一层是页目录，接下来就是页表了，但是实际中可能会有多余两层的结构出现

Inverted Page Tables

为了更省空间，还可以让所有进程共享一个page table，于是就有了这个方法。

把页表放到磁盘中

尽管我们已经竭尽所能的缩小了页表，但是仍然有可能页表太大了以致于内存放不下，操作系统通过吧课表放到kernel virtual memory里，并且允许系统把一部分页表swap到磁盘中来缓解压力，这也是下一部分学习的内容。

总结

我们知道了页表不是简简单单通过一个数组实现的，而是通过更为复杂的数据结构。通过时间来交换空间。这里注意的是，如果命中了TLB，那么在多级的页表也不会影响速度；而TLB本身命中率是非常高的，所以这种看上去用速度换空间的做法是非常可取的。

家庭作业

1. 如果是一个页表，那么需要一个寄存器来定位它。那么两级页表呢？三级呢？答：那当然是两个和三个喽。
2. 很好的一个测试，强烈推荐做一下。

21. Beyond Physical Memory: Mechanisms

之前我们有一个假设是所有的page table都能放到内存中的，当内存放不下的时候，就需要磁盘来进行帮忙了。

Swap Space

第一件要做的事情就是我们要确保物理磁盘中是有这个空间的，我们把这块空间叫做swap space，因为我们把页从内存中交换到磁盘上，或者从磁盘中换回来。

Present Bit

当从虚拟页面转化到物理页面的时候，有一个标志位——present bit用来指示这个页到底在不在物理内存中。如果在的话那么一切照旧，如果不在的话那么就会有一个page fault（其实应该叫page miss更为贴切）产生。

page错误产生之后，page-fault handler就会执行，OS会处理。

Page fault

之前提到过TLB可以由硬件实现，也可以软件实现。而page fault则一律交给操作系统来完成。当缺页中断产生的时候，操作系统需要知道缺失的页在磁盘的哪里，这个地址一般被存放在页表中，即代替了原来应该存放真实物理内存地址。

那么为什么这里需要操作系统来做，而硬件不再插手了呢？第一是因为磁盘慢（硬件就算插手了也没啥速度的优势），第二是操作磁盘更加复杂（只有操作系统才知道一些更加具体的信息）。

一旦缺失的页被找到并且被放入物理内存，操作系统就可以更新页表，把之前放在磁盘中的位置更新成真实物理内存的地址了。

这里需要注意的是，当缺页的时候是去磁盘中找的，也就是在进行IO，所以进程会进入阻塞状态，此时操作系统安排别的进程执行。

内存满了怎么办？

内存满了的话，那就只能踢掉已经在内存里的页了。当然这需要用到page-replacement policy，而这个策略的好坏直接影响了操作系统的执行速度，所以非常重要，我们将在下一章中深入理解。

页错误处理流程

到了现在，应该有能力来总结一下内存访问的流程了：

1. 访问TLB看能否命中，如果命中则可以直接获取对应的物理地址，结束。
2. 如果无法命中TLB，那么看看能否直接从PTE中获取PFN，并将其放入到TLB中，重新执行当前的指令，当然就可以命中啦。
3. 如果无法命中TLB，而且发现当前的页不是valid的，那么就直接抛出异常，让操作系统去处理。

什么时候发生页替换

之前我们假设的是当内存满了的时候，但是实际中这显然不合适，内存中始终会有一块区域是空着的，操作系统通过high watermark (HW)和low watermark (LW)来帮助执行。如果发现当前内存中可用的页数量低于LW了，那么操作系统就执行一个后台线程，把内存清理清理，直到可用的页数量到HW。这个线程的名字就叫做swap daemon，

总结

本章我们了解了一个存在位present bit，如果是0那么就会引发page fault，并且交给page-fault handler来处理。值得注意的是，这些过程对于进程来说都是透明的。

22. Beyond Physical Memory: Policies

在这一章我们研究在内存中，是通过什么策略来把页换出内存的。

缓存管理

我们将主内存视为虚拟内存的缓存，那么我们要做的就是就是尽量降低cache misses。

average memory access time，平均内存访问时间，计算公式如下：

T_M的意思是直接在内存中访问的时间，T_D表示直接访问磁盘的时间。显然这个磁盘访问的时间是远远大于内存访问时间的。

最佳策略

这个策略中心思想很简单：在所有页中，假设每个页都会在未来的某段时间后被用到，那么选择最远的未来被用到的那个页，踢出去。

然而未来是无法知晓的，所以这种方法并不能实现，但是可以作为衡量的标准（即完美的标准）。

FIFO

早期的系统都是为了避免复杂性，所以使用了简单的方法来实现，这其中就包括了FIFO。有一个队列来实现，当需要替换的时候就把最先进来的页给踢出去。

这里还有一个有趣的现象，就是当扩大cache的时候，命中率反而下降的问题。

随机

实现很简单，然后实际效果嘛，全看运气。

LRU

我们再一次使用过去来推测未来。如果某个页过去被用到了多次，那么将来它很有可能再被用到。

一个程序会经常用到一些特别的代码（比如在循环中），我们应该把这些东西留存在内存之中。

Least-Frequently-Used (LFU)是最少被使用的页面换出，Least-Recently- Used (LRU)是最近最少使用的页。

一个例子

如果抛开时间和空间的局部性原则，那么通过测试，FIFO、随机和LRU这三种的命中率是一致的。

接下来我们使用二八原则，即80%时间使用的都是20%的页。结果是LRU明显好于FIFO和随机。

最后再来一个对FIFO和LRU最极端的例子：循环取页，且页的总数总是大于cache，所以一开始LRU和FIFO的命中率是0，但是随机算法却还有着不错的表现。

实现

我们必须要有一个数据结构来保存相关的信息。

针对FIFO，我们可以有一个list，而且只需要在两个时候更新：当页被剔出内存和当页加入进来的时候。

随机的话只需要一个良好的随机数发生器即可。

对于LRU，我们还需要知道哪个是最近最少使用的，一种思路就是在page上新增一个代表时间的东西，当页被使用的时候更新这个时间，当页需要被踢出内存的时候操作系统遍历扫描这个时间，找到最小的那个。显然遍历来说，时间成本有点太高了，那退一步说，我们可不可以不用找到最小的那个，而是使用比较小的那个呢？

近似LRU

完美的LRU对于性能影响较大，所以我们这里是用近似LRU——同时也是很多现代操作系统的选择。这个需要硬件的支持，每一页都有use bit，只要一个页被使用了，那么这个bit就是1。硬件不会将这个位置0，只有操作系统会置0。

clock algorithm是一个简单的算法，假设有一个环形的list，时针从某一个页开始（随便哪个都行），当页需要被踢出内存的时候，时针开始看它指向的那个页的use bit是不是1，如果是的话就把它置成0，并且移动到下一个页；如果是0的话，那么就可以直接踢出内存了。

脏页

如果一个页在内存中被修改了，那么必须将它写回到磁盘里。如果页并没有脏，那么直接丢掉就好了。所以硬件支持一个dirty bit，用来显示这个页是不是被修改过。这样上面的那个时钟算法除了考虑use bit之外，还可以考虑这个标志，尽量找那些干净的替换。

其它策略

除了上面的这些，操作系统还需要考虑其它的内容，比如什么时候把页换进来呢？最简单的就是当需要的时候呗，当然也可以未卜先知提前拿进来：比如第P个页拿进来了，那么就顺手把P+1也带进来。

另外一个策略就是操作系统如何把脏页写回到磁盘，最简单的当然是每次写一次，但是其实很多系统会把这些脏页聚合在一起，然后一次性写。

Thrashing抖动

在结束这章之前，我们还有一个问题，如果超额分配了怎么办，即目前所有程序需要的内存超过了物理内存，发生了抖动。

早期的操作系统有一套复杂的机制来检测和解决，最简单的就是随机干掉几个进程，还取了个admission control的名字…这和我们生活中有时候挺像的：与其执行很多任务，不如专心做少点的任务。

总结

我们在这部分介绍了一些页面置换策略，操作系统最后使用近似的LRU——时钟算法，当然其实还有一种更简单的策略——买更多的内存（笑）

23. Complete Virtual Memory Systems

终于到了虚拟内存的最后了，这部分我们将总体回顾一下，并且聊一聊虚拟内存的细节部分。

我们具体以两个系统为例，一个是VAX/VMS操作系统，尽管现在已经50岁了，但是一些idea还是那么有用；另外一个就是大名鼎鼎的linux了。

VAX/VMS

这个系统的主架构师是之后Windows系统的领导者，为了简便，下面就用VMS来代替了。

内存管理硬件

VMS操作系统的进程寻址空间是32位的，一个页是512字节，所以offset是9位，VPN是23位。其中VPN的前两位用来标记是哪个段的，所以它的管理方法用的是段页式。

整个内存的低部分是进程空间，进程空间里的一般放的是用户代码和堆（朝下生长），另一部分是栈，朝上生长，而整个内存的高部分的一半则是操作系统空间。

该系统由于页比较小，所以如果用简单的数组来作为页表的，那么每个进程的页表会非常大，系统的设计者想了两个办法，第一个是把堆栈分开，这样堆栈之间的内存就不需要记录进页表。第二个是操作系统会分配内核的空间，但是这也导致了复杂性的加剧。

真实的地址空间

我们之前只是简单的假设了三个：代码段和堆栈，但是实际上在VMS中这个复杂的多。

在进行context switch的时候，需要切换P0和P1的寄存器，但是不需要切换S的寄存器。

上面的图还可以解释为什么下面这段代码是错误的：

1
2
3
4
5

int main(int argc, char *argv[]) {
    int *p = NULL;
    *p = 10;
    return 0;
}

在C语言中，NULL是0，而第0页可以看到是不可用的。

至于为什么操作系统在物理内存中的地址是不变的，有一些优点：首先是如果执行系统调用write，那么操作系统会首先把数据从进程中复制到自己的结构中。

页替换

这个操作系统的PTE里面没有reference bit，意味着硬件无法支持LRU，必须操作系统自己来。它使用了一种叫segmented FIFO的策略：每个进程都有一个最大的页数能够放在内存中resident set size (RSS)，当一个进程的页数超过这个RSS了，就把最先进来的页踢出去。当然这么做效率不好，所以有一些改进：新增两条second- chance lists，分别对应了干净的页和修改过的页。如果另外一个进程需要页，那么首先从干净的列表中查找，这样可以大大改进FIFO的效率。同样的页进行了页的聚集，把要修改的页一次性写入。

其它的tricks

VMS还有两大法宝，分别是demand zeroing和copy-on-write，这两个其实都是偷懒的办法。

demand zeroing就是当一个进程需要页的时候，操作系统会找到一个页，然后把页清零，但是清零这个过程比较耗时间，所以操作系统知识简单把这个页标记一下，当真的要读取这个页或者往这个页里面写东西的时候，触发一个trap，然后OS才真正把这个页清零。

copy-on-write也差不多，当操作系统需要把一个页从一个地方复制到另外一个地方的时候，它可以不复制，而是指向需要被复制的页并将其标记为read only，如果只是读取一下，那么不会有任何问题。如果真的需要写了，那么就trap到OS，OS就需要真正的去复制一份。

copy-on-write最大的用处应该就是在fork系统调用的时候了，因为需要复制父进程的所有空间，所以如果真正去复制了，会很慢；而且这其中大部分的空间都会被exec给覆盖掉，所以用这个技术特别有用。

linux

地址空间

可以看到这是Linux的内存结构图，和上面的VMX其实是挺像的。在32位的机器上，用户空间和内核空间的分界点是内存的四分之三处。

稍微有点奇怪的是kernel部分，分了两层，一块叫kernel logical addresses，如果需要在这块空间里分配空间，那么就使用kmalloc。很多之前的结构其实都放在这里，比如page table，每个进程都有的kernel stack。而且这部分的内容，是不能被交换到磁盘中去的，而且这部分的内容是直接映射到物理内存中的最开始的位置的。因为这部分是操作系统中最重要的地方，而且是连续的，都是被分配到了物理内存的开始处。

还有一部分是kernel virtual address，在这部分分配内存的话，需要使用vmalloc，而且这部分的内存大概率它不是连续的，这部分内存经常被用来作为buffer，而且这部分还可以用来做为内存的扩展，不过由于目前都是64位机器了，所以这功能也就算了吧。

页表结构

和之前的VMX不同，Linux采用的是多级页表的组织结构，一个寄存器里面存放了页目录的位置，剩下的交给硬件来处理。

然后就是从32位到64位的转变了，64位的机器使用了四级的结构，一个虚拟地址示意图如下所示：

最左边16位并没有被使用。最右边的offset还是12位，说明页的大小还是4K。随着内存的扩大，以后可能还会有五级和六级，想想看，我只是为了把虚拟内存转化为真实物理内存，就需要六次内存访问，这是多么大的开销。

更大的页

更大的页，能够有效减少映射条目，这样可以提高TLB的命中率。在最开始的时候，Linux开发者知道数据库需要这方面的支持，所以希望能够让这些应用使用更大的页，这样只有小部分软件收到影响（而且还是值得的）。随着时间的推移，Linux新增了huge page的支持，可以让操作系统自己来选择这个软件应该使用多大的页，而这个过程对于软件来说是完全透明的。

page cache

为了有效缓解从磁盘中读取和写入的缓慢，大多数操作系统使用了caching缓存系统，Linux自然也不例外。

从三个地方获取了数据并保存在内存中：memory-mapped files，file data以及metadata从设备中获取的（通过read和write系统调用），每个进程都有的堆栈的页。这些内存被放在了page cache hash table，这样能够加快查找速度。

这个page cache会知道里面的条目是不是脏了，脏掉的数据会被一个叫pdflush的后台线程写回到磁盘中。可能是每隔一段时间，也可能是因为脏页太多了。

有时候Linux运行比较慢，就会使用2Q的变种：LRU有效但是可以有替代品，比如有一个进程重复访问一个大文件，那么LRU就会把其它文件踢出内存。Linux有两个lists来完成，第一个是inactive list，当你第二次访问的时候，就会放到active list里。所以如果要把页换出去，优先考虑的是inactive list。

安全性和缓冲溢出

可能古老的操作系统VMX和现代操作系统Linux之间的区别就是安全性了。

其中一个安全问题就是buffer overflow攻击，可能会影响到用户程序甚至是操作系统，精心构造的攻击确实可以造成privilege escalation特权提升。最简单的防御手段就是让某一部分区域的代码无法执行，通过设置NX位。

另外一个问题是return-oriented programming (ROP)，攻击者可以利用在内存中的一些别的程序的代码（称为gadgets）来构造自己的攻击代码。为了解决这个问题，Linux使用了address space layout randomization (ASLR)，地址随机化。

其它安全问题：Meltdown And Spectre

问题的根源来自，CPU进行了疯狂的优化，这其中有一项是推测要执行的指令并且提前执行，如果猜中了可以提高效率，猜错会有补偿。

emmm 接下来的内容现在不想看了。

总结

这部分我们浏览了两大操作系统，观察了它们是如何进行内存虚拟化的。同时还额外学习了一些安全知识。

到这里，对于这本书的第一部分算是看完了，稍微来进行梳理一下。

首先这部分主要讲了两个部分的虚拟化，一个是CPU，另外一个就是内存。

• CPU这块首先了解了进程，并且了解了进程相关的系统调用，明白了在shell中是如何进行命令执行的。然后引出了LDE，来解决操作系统中部分操作的限制问题和进程的切换问题。接下来介绍了进程的一些调度算法，包括FIFO，SJF和最终的MLFQ，其中穿插了RR，还额外介绍了一种百分比的调度算法。

• 内存这块呢，首先介绍了地址空间，然后是照理是一些系统调用。接下来讲到了如何进行地址的映射，并且通过分段来解决碎片的问题。之后再进一步了解了分页，以及TLB和多级页表。同时也了解了页的交换算法，最后还用了两个具体的系统做了例子。

虚拟机部分

该部分是全书的附录部分的内容。

多年以前，IBM把大型机卖给了企业，然而企业却希望大型机可以运行多个操作系统。不得已，IBM就引入了一个间接层解决了这个问题，这个层叫做Virtual Machine Monitor，VMM。它让操作系统以为自己在控制硬件，实际上是它在控制硬件。也就是操作系统欺骗进程，让进程以为自己拥有全部的CPU时间和全部的内存空间，而VMM也是在用相同的方法欺骗着操作系统，但是它不知道，谁又在欺骗它呢？

虚拟化CPU

在欺骗CPU这一维度，VMM做的事情和操作系统的惊人的相似：都是受限直接运行。也就是如果在VMM上面运行操作系统，只需要跳到操作系统的第一条指令就可以了。所以不妨把VMM就当成是操作系统，而把原来的操作系统看成是进程，本质上其实也就是在做进程的上下文切换而已——但是显然操作系统的上下文切换需要保存比进程上下文切换更多的信息。

系统调用

首先先来看一个open的系统调用：

1
2
3
4
5
6
7

open: 
push dword mode 
push dword flags 
push dword path 
mov eax, 5 
push eax 
int 80h

前三个是把参数入栈，然后在eax里面放入了5，并且把eax入了栈，最终执行一条int 80h的指令。

当执行int指令的时候，首先会通过修改PC把控制转移到操作系统中，其实是跳转到对应的陷阱处理程序（并且从用户态转换成内核态），这是操作系统在启动的时候就创建好的。然后到对应的代码中进行对应的操作，返回。

但是如果加了一层VMM之后就很有意思了。在操作系统启动的时候，会试图安装好陷阱处理程序，而这个过程是需要硬件的支持的，也可以理解为操作系统陷入了硬件。当然在这里，其实是操作系统陷入了VMM，这个时候VMM就可以记录下陷阱处理程序在内存的哪个角落，等到真正的系统调用发生的时候，VMM让操作系统跳转到对应的内存去处理。这里操作系统并不能真正处于内核模式，否则它就能够直接访问硬件了，而是用一种在用户模式和内核模式之间的模式。

虚拟化内存

思路和上面的虚拟化CPU其实是一样的。

本来用的复习书籍是《现代操作系统》，但是我感觉那书真的是不太适合我，就换了一本《Operating Systems: Three Easy Pieces》，纯英文版的。

书名中的三个部分，分别对应了虚拟化（virtualization）， 并发（concurrency）和持久化（persistence）三个部分，这边打算用三篇文章来记录这三个部分，本篇博客就整体介绍一下整个操作系统。

对操作系统的介绍

程序到底是什么？一个运行着的程序就是CPU从内存中获取指令，将指令解码，执行指令，最后不停重复的过程。

操作系统本身也是一个软件，只不过它控制了物理的资源，并且对这些物理资源进行了抽象，所以我们也可以说操作系统是一台虚拟机。对了让使用者更好的使用，操作系统提供了API这个概念，这些API就被称为system call——系统调用，这些系统调用有时也被称作标准库（standard library）

对CPU的虚拟化

可以同时运行多个程序，而每个程序似乎是同时运行的。

对内存的虚拟化

如果关闭了内存随机化，那么所有程序打印的它们的地址都是相同的，这其实是操作系统做了内存映射。

并发

由于有多个程序一起运行，所以会出现一点问题。

持久化

把数据保存到磁盘中。

操作系统历史

有兴趣可以自行了解。

数据库的复习。主要用的书籍是《MySQL技术内幕InnoDB存储引擎》第二版。

体系结构和存储引擎

数据库和实例

这点非常重要，后续的一些概念会用到，所以这里着重区分一下这俩。

数据库：本质上是文件的集合。这些文件保存的位置可以通过select @@datadir;查看。大概如下图所示（部分）

实例：数据库实例就是真正用于操作数据库文件的。而且实例在操作系统的表现上，就是一个进程。所以我们和数据库之间进行通信，用的就是进程之间的通信方式。

体系结构

自底向上可以看到，首先是文件系统，因为mysql本身就是把数据和索引放到文件系统中的。接下来是各种各样的存储系统，当然我们这里以InnoDB为主。再上去就是mysql的一些优化器执行器等。这里注意，不同的存储引擎，针对的是表，而不是数据库。

存储引擎

反正日常中真的是基本只使用InnoDB，所以其他的我觉得就算了。InnoDB它支持事务，支持MVCC，支持行级锁，支持聚簇索引，支持外键。代价就是它的存储文件非常之大。

连接mysql

之前说了mysql数据库实例是一个进程，所以可以通过进程间通信的方法，来连接数据库实例。

1. TCP/IP套接字。用的最多的就是它，可以跨设备进行通信。当你使用mysql命令指定主机的时候，用的就是这种方式。
2. 命名管道和共享内存。在同一台windows机器上，可以使用命名管道和共享内存的方式进行连接，但是我没有使用过。至于为什么是在Windows上支持而linux不支持，找了博客说的理由是，linux上已经有域套接字这种更好的方法了，所以不需要命名管道和共享内存的方法。
3. Unix域套接字。linux上使用，只能本机使用，相比起socket，速度快。默认连接本机的mysql用的就是这个方法。

InnoDB存储引擎

再次说一下它的特点：支持行锁，支持MVCC，支持外键，提供一致性非锁定读，同时设计用来最有效的利用CPU和内存。

InnoDB体系架构

简单来说就是有很多个内存块，这些内存块组成了内存池（上图的内存池）内存池负责维护数据结构，并且能够缓存磁盘上的数据，对redo log进行缓冲等。

InnoDB的线程

可以发现InnoDB使用的是多线程模型，有不同的线程来完成不同的工作：

• master thread：将缓冲池中的数据异步刷新到磁盘
• io thread：为了提高性能，InnoDB是用的是AIO的方式来处理写IO请求的，而这个线程主要就是负责IO请求的回调。下图中可以看到有4个读和4个写回调的线程（如果你CPU核心多，可以调大这些数值）。读线程的ID总是小于写线程的。

• purge thread：清除线程的意思，当事务提交之后，undolog就已经完成它的一部分使命了（别的事务可能使用MVCC在使用，所以不能马上删除），那么就用这个线程来回收undolog所使用的页。
• page cleaner thread：脏页的刷新操作专门交给这个线程来完成。

InnoDB的内存

数据库的文件都是保存在磁盘中的（使用NDB存储引擎的除外）。简单来说就是利用了内存作为了缓冲，第一次读取的时候从磁盘读取，读完之后还会把页放入到缓冲区，这样下次使用可以直接读取内存中的页而不是磁盘中的。同样如果对数据进行了修改，那么先修改缓冲区的页，然后以一定频率再写回到磁盘中。而且读取的命中率高达99%以上。

可以看到我这台使用了134M的内存空间。那么具体的缓冲池缓冲的页，有哪些呢？

大部分都被数据页和索引页给占据了，但是还有少部分是插入缓冲等信息。同时还可以使用多个缓冲池（图中只有一个缓冲池，红框框起来的），然后页会使用哈希算法给平均分配给各个缓冲池中。

在innodb中，缓冲池页的大小默认是16K，默认使用LRU进行缓冲池中的数据也和索引页的管理（只有数据页部分和索引页使用LRU），但是它这个lru不是直接把最新的数据放到链表头部，而是放到链表的某一个位置，由midpoint指定，然后在这个midpoint前面的就是最新的数据，而后面的就是老一些的数据了。这么做的理由是，如果你进行全部的扫描，那么每个页如果都放到头部，反而会把真正的热点数据给顶掉了。所以需要先把页插入到中间的位置，如果这个页真的是热点数据，再放到头部去。

除了LRU这个列表之外，还有一个flush列表，在其中的页表示的是数据已经脏掉了，需要重写回磁盘中。

从上图还可以看到红框外有一个叫重做日志缓冲的区域，用来将重做日志先放到这里，然后再写到重做日志的文件中去，所以这块空间不用很大，绝大部分只需要8M即可。

还剩下最后的一块空间是额外内存池，应该是用来存放LRU，锁这些信息的。

checkpoint

缓冲就是为了能够提高效率，带来的问题也很明显：修改数据只是先到内存，然后再找机会写回到磁盘中。但是如果还没写回磁盘，系统挂了，那岂不是数据就不正确了吗？innodb使用了write ahead log策略，就是我先写好重做日志，然后再去修改页。这样可以通过事后重做来进行补救。

innodb有两种checkpoint，分别是：

• sharp checkpoint：数据库关闭，把所有脏页都写回到磁盘
• fuzzy checkpoint：每隔一定时间，从脏页列表中刷新一定比例的页回磁盘；LRU尾端移除的页如果是脏页，那么就需要写回磁盘；重做日志文件不可用的时候，需要将页强制刷新到磁盘中；脏页太多了也需要触发，保证内存缓冲区有足够的可用的页。

master thread

该线程每秒执行的任务：

• 一定把日志缓冲刷新到磁盘中，就算这个事务没提交。所以就算特别大的事务，提交的时间也是极短的。
• 可能会合并插入缓冲。这个并不一定每秒发生，如果innodb判断当前IO压力小，就可以执行。
• 可能会刷新脏页到磁盘。这个也并不一定每秒发生。

该线程每10秒执行的任务：

• 可能会刷新100个脏页到磁盘。我个人挺好奇为什么是指定数量的。
• 一定合并插入缓冲。
• 一定将日志刷新到磁盘中。
• 一定删除无用的undo页。
• 一定刷新100个或者10个脏页到磁盘。是不是似乎和第一个矛盾了？

关键特性

• 插入缓冲
• 两次写
• 自适应哈希索引
• 异步IO
• 刷新邻接页

插入缓冲

主键是行的唯一标识，而行记录的插入顺序就是按照主键递增的顺序，也就是聚集索引是顺序的，不需要磁盘随机读取。（也有少部分主键用类似UUID的，这样就不是顺序的了）

而除了主键外，我们还会在别的列上定义辅助索引（secondary index），然后在插入的时候，由于是按照主键插入到页里的，但是在非聚集索引里，需要花时间去找到应该放到哪个位置。innodb则是使用了insert buffer，如果插入的非聚集索引页在缓冲池中，那么可以直接插入；否则就先放到insert buffer中，等过一会一起操作，这样提高性能。当然这么做的前提有两点：1.索引是辅助索引 2. 索引不是唯一的（唯一的相当于对于每一条行，你都肯定要花时间去B+树里找）

举个例子就是，你是一个司机，需要把乘客从A运到B，但是你为了多赚一点，肯定希望有两个乘客，它们都想去B，那么你就只需要运一趟就可以了。

当然除了插入缓冲，还可以有更新缓冲和删除缓冲，道理都是一样的。

实现方式是使用一棵所有表格都共享的B+树，非叶子节点放的是表的id，页的偏移量（合在一起称search key）。当辅助索引要插入到页里面的时候，如果该页不在缓冲池中，那么首先构造好search key，然后查询B+树，把记录插入到子节点中。

两次写

假如正在把页写回去的时候，正好宕机了，那么可能会出现只写了部分数据进去。可能会说，那我用重做日志可以恢复呀。重做日志记录的是修改，所以我们首先需要一个页的副本，然后通过在这个页的副本上面进行重做，才能还原真正的结果。所以解决方法就是在写入到磁盘上面之前，还去保存一份副本就可以了。

自适应哈希索引

如果对索引页建立哈希索引能够带来速度提升，那么就建立。此过程无需人为干预。

异步IO

这个就不说了。值得注意的是Macos不支持操作系统的原生AIO。

刷新邻接页

当脏页刷新到磁盘时，会检查当前脏页的所在区的所有页，如果有就一起刷了，这样可以把多个IO合并成一个IO操作。

文件

参数文件

mysql在启动的时候需要读取配置文件，配置文件的顺序可以使用mysql --help | grep my.cnf来查看配置文件的位置，而且后一个配置文件会覆盖掉前一个配置文件相同的配置项。

参数本身分为动态参数和静态参数，静态参数只要实例启动了就不能进行更改，动态参数则会根据会话范围或者是实例范围来生效。

日志文件

日志可以分为错误日志（error log）、二进制日志（binlog）、慢查询日志（slow query log）和查询日志（log），这些日志都默认存放在datadir下面，可以通过show global variables like 'datadir';查看

错误日志

当数据库遇到问题的时候应该首先查看这个。在数据库中可以使用show variables like 'log_error';来查看错误日志文件的位置。

慢查询日志

简单来说就是可以通过设置一个阈值，当一句SQL的时间超过了这个阈值的时候，就会记录到慢查询日志中去。这个阈值可以通过show variables like 'long_query_time';进行查看，默认是10秒。

还有一个参数是如果你查询没有用到索引，那就把这条查询语句放入到慢查询日志中去，通过show variables like 'log_queries_not_using_indexes';，默认是关闭的。当然如果打开了这个选项，而每次查询又都不使用索引，那么这个日志文件会很大，所以可以指定每分钟最多纪录多少次。

日志文件的地址可以通过show global variables like '%slow%';查看。由于这个日志文件一般会比较庞大，所以有一个mysqldumpslow的命令可以帮助你更好分析这个日志文件。

查询日志

纪录所有对MySQL数据库请求的信息，不论是否成功。

二进制日志

对于数据库执行更改的所有操作。该值日主要是为了能够对数据库进行恢复，当然也能够进行数据库的复制和审计。

这个日志是用二进制记录的，所以直接用cat等命令进行查看会乱码，需要用mysqlbinlog命令进行查看。

套接字文件

在Unix下，连接本地的mysql可以使用Unix域套接字方式，这个文件的位置可以通过show variables like 'socket';查看，然后就可以通过mysql -S /var/run/mysqld/mysqld.sock进行登录了。

pid文件

通过show variables like 'pid_file';可以找到这个文件，这个文件里的数字就是当前MySQL的进程ID号。

表结构定义文件

每个表都有对应的文件，不论你采用什么存储引擎，都会有个.frm的表格来记录表格的结构定义。当然直接用cat来查看肯定是不行的。

存储引擎文件

从这部分开始就是innodb专属的了。

表空间文件

innoDB将数据部分按照表空间进行存放。默认有一个叫ibdata1的文件，它就是默认的表空间文件。可以把所有的表的数据都存放在一个文件中，也可以对每个表格分开存放数据，通过show variables like 'innodb_file_per_table';参数可以得知。这里需要注意的是，单独的表空间文件仅存储该表的数据、索引和插入缓冲BITMAP等信息，其余信息还是放在默认的表空间中。

重做日志文件

在innodb的数据目录下会有两个文件：ib_logfile0和ib_logfile1的文件，它们就是redo log file。一个innodb至少有一个重做日志文件组，一个组下面至少有2个重做文件，就是上面的那两个。这两个文件大小相同，并且通过循环写入的方式运行：即先写到文件0中，写满了就写到1中，1写满了又去写0.

那么重做日志和之前的二进制日志有什么区别呢？二进制日志并不针对某个存储引擎，而重做日志针对的是innodb。二进制记录的是逻辑的内容，比如执行了一条update命令，而重做日志记录的是每个页的更改情况，是一种物理情况。最后二进制日志文件在事务提交前进行提交，只会往磁盘里写一次，而事务执行过程中，会不断有日志被写入到重做日志中去（具体是先放到内存的缓冲中，然后再写到磁盘）。

表

索引组织表

在innodb中，表都是按照主键顺序进行组织存放的，称之为索引组织表。一个表如果没有手动指定，那么会选择第一个（不是你建表的顺序，而是你建立索引的顺序）非空且唯一的索引，如果还是没有，则innodb会自动创建一个6字节大小的指针。

逻辑存储

所有的数据被逻辑放到表空间中，然后表空间又可以分成段（segment）、区（extent）、页（page）。

表空间

如果启用了每张表单独一个文件，那么数据索引和插入缓冲bitmap页放到单独的文件中，但是回滚信息，插入缓冲索引页，系统事务信息都还是放到公共的文件中去。

段

从上面的图的左上角可以看到每个表空间都是分成一段一段的，常见的段有数据段、索引段和回滚段。

区

区，是由连续的页组成的，上图中的右下角就是一个区的示意图，且一个区保证是1MB大小（64个page，每个page16KB），为了连续性，innodb会一次性申请4~5个区。

但是如果每个表都用到至少一个区，而一个区大小一定是1MB，那就有点浪费了，所以在申请之前，会先用32个页大小的碎片页来存放数据。

页

页是innodb中，磁盘管理的最小单位，每个页是16KB，可以进行设置。

行

每个页最多存放7992行数据。

InnoDB行记录格式

通过show table status like '具体的表名';可以查看表中的行记录的格式。

compact行记录格式

字面意思是紧凑型的。那显然如果一个页能够存放更多的行，就可以有效减少页的读取，提升数据库的性能。而compact的格式如下图所示：

• 变长字段长度列表用来指示列的长度（就是如果一个列的长度不一定，就用这个值，最典型的就是varchar了），如果小于255字节，用1字节表示；如果大于255字节，用2字节表示，所以最大也就是65535。而且注意这个是逆序存放的，也就是如果列1长度是3字节，列2长度是2字节，这个头部的字段会是02 03。

• 接下来是null标志位，如果这一行数据里面有null值，则置为1。长度是固定的1字节。假设第二列和第三列是Null，那么这个字节转化成二进制就是:0000 0110，所以在mysql中，null是不消耗空间的。

• 然后是定长5字节的记录头信息。记录了这一条记录有多少条记录，记录的类型和下一条记录的相对位置。

• 接下来就是用户的数据了。其中null是不占用任何空间的，然后还有两个隐藏列，分别是事务ID列和回滚指针列，如果没有定义主键，那么还会有一个6字节的rowid列，所以非常推荐有主键。

redundant行记录格式

• 第一个字段和之前有一点点区别，分别是每一列数据的偏移量。假设第一列是01，然后第二列长度是02，那么就应该是03 01（03 = 02 + 01），而且需要倒序。
• 记录头里面有一项信息比较重要，就是这一行一共有多少列。由于这项信息最多是10比特，所以一行中最多1023列。

对于varchar类型的null值，redundant是不会消耗空间的，而char则需要消耗空间。

看到这里有个疑问，只记录变长的列的长度，那我是怎么知道定长的列的长度的呢？查表结构吗？

行溢出

一页的大小是16KB，而一行最大的可以到65535字节，显然远远超过了页，那是通过什么方法放进去的呢。

所以遇到列太大的问题，innodb的做法是，保存一部分前缀，然后将剩余的部分放到溢出页中。

compressed和dynamic行记录格式

之前说到如果某一列数据太大，那么会保留一部分前缀，剩余部分放到溢出页中。而这俩的做法是，全部放到溢出页中，在数据页里面只留下一个20字节的指针。同时还支持压缩算法。

char和varchar

在使用多字节字符集类型的时候，char(n)中的n代表的是字符的长度，假设你用的是gbk，那么char(10)可以放下10个汉字，占据20字节。所以在多字节字符集下，char和varchar在实际行存储中，只有char是需要填充0x20这个区别。

Innodb数据页结构

约束、视图和分区

暂时跳过。

索引和算法

概述

innodb支持B+树索引、全文索引和自适应哈希索引（无法人为干预）。

在使用B+树索引的时候，首先找到被查找的那一行所在的页，把它读入到内存里，然后在内存中，通过页的page directory结构进行二分查找，但是由于在磁盘中找到页的时间远远大于在内存中的操作时间，所以一般会忽略掉内存中的操作时间。

B+树

B+树是为磁盘设计的一种平衡查找树，所有记录节点都是按照键值的大小存放在同一层叶子节点上，然后叶子节点指针进行连接。

###B+树索引

B+树的高度一般是2-4层，即只需要2-4次IO就可以找到对应的行所在的页。数据库中的B+树索引可以分为聚集索引和辅助索引，它们内部实现都是B+树，区别在于叶子节点存放的是否是一整行数据。

聚集索引

按照表的主键构造一棵B+树，叶子节点中存放的数据就是行数据，所以称叶子节点为数据页。

而在非数据页（就是在非叶子节点上）存放的仅仅是键值以及指向数据页的偏移量。

辅助索引

叶子节点存放的是书签（bookmark）而不是对应的行数据，书签本质上是一个主键的值，所以你查完辅助索引之后，还需要去聚集索引里再从头查一次。

cardinality

对于低选择性的，例如国家字段、性别字段等，是没有必要增加B+树字段的。那么如何判断一个索引是否是具有高选择性的呢？就是靠的cardinality这个值，用来表示索引中不重复记录的预估值。

在Innodb中，该值会在insert操作和update操作的时候，并且满足一定条件的时候才进行更新（毕竟这玩意儿的更新耗费系统资源），而且更新的算法是通过随机采样获得的，所以该值只是一个大概的值。

B+树的使用

联合索引

简单来说就是多个列作为一个索引来使用。并且数据是按照第一列先排好序，在第一列相同的情况下再判断第二列，以此类推。实际例子就是我在商城订单的表中，对用户id和订单时间做了联合索引，这样子查询某个用户的所有订单会快很多（然而由于数据量太小，我是完完全全没有察觉出来有变快）

覆盖索引

从辅助索引中就可以得到查询的记录，不需要再去查询聚集索引的记录。比如有一个表，有列A~列Z，我已经创建了一个联合索引(A,B)，那么如果我只是需要查询AB两列的数据，那么只需要到辅助索引去查询一下数据即可，不需要去聚集索引那里再去走一遍。

Multi-Range Read优化

简写为MRR，当你从辅助索引中查出数据之后，需要进行回表，而回表操作是比较乱的，所以这个时候可以根据查出的数据，按照主键来进行一次排序操作，之后就可以较为快速的去聚簇索引里面访问了。

Index Condition Pushdown优化

原来正常的查询，首先根据索引查找记录，然后通过where语句来过滤记录。而使用这个技术就可以在查找记录的同时就把条件给过滤掉了。

哈希算法

虽然内存中的读取速度非常快，但是如果内存庞大，在其中找到某一页还是比较费时的，这个时候就需要哈希算法来帮助了。

哈希索引本质上就是一个hashmap，记录了每张表所在的位置，所以哈希索引对于条件精确的查找效率极高，但是对于范围查找则无能为力。

全文索引

显然如果条件是where content like '%word%'，这样的查询用不了索引，没办法就只能去全文检索了。全文检索效率不高，所以针对英文，还是有解决办法的。

倒排索引

核心思想是记录了单词和单词在哪个文档中的映射关系。

具体的说，假设有一张表有两列，一列是ID，还有一列是文本内容，那么就可以构造这么一个倒排索引：

以第一行作为例子，说明单词code在文档1中出现了，具体位置在第6字节；同时在第4个文档也出现了，出现位置在第8字节。

为了提高全文检索的并行性，这样的表格有6张，且按照latin编码进行分区，被持久化保存在磁盘中。还有一个FTS Index Cache用来提高性能，其本身是一个红黑树。和之前的思想一致，如果在对应的表中更新了数据，那么会在这个FTS Index Cache中做对应的修改，之后找时间再同步回磁盘的表格中。

PS：innodb的全文检索是不支持中文的。

全文检索

注意！上面的是全文索引，这部分是全文检索，两者是非常不同的。

emm 书中介绍了全文检索的用法…没有讲原理，我就不赘述了。

锁

innodb存储引擎中的锁

有两种标准的行级锁：共享锁和排它锁。只有共享锁和共享锁之间是兼容的，其它都是互斥的。

意向锁是将锁定的对象分成多个层次，如果需要访问底层的行记录，需要去对表和页加意向锁，其中任何一个环节没得到意向锁就需要等待。具体来说有两种意向锁，分别是意向共享锁和意向排它锁。

一致性非锁定读

如果有一个事务对行进行delete或者update的操作，这时候肯定是加了排它锁，那么innodb不会因为加了排它锁就去等待，而是去读取行的一个快照信息，这就是一致性非锁定读。它的实现就是通过undo段来实现的。一个行记录可能有多个快照，这就是多版本并发控制MVCC。

在read commited 和 repeatable read隔离级别下，用的就是非锁定一致性读，只不过读取的快照数据是不同的。对于read commited读取的是最新的一份快照数据，而对于repeatable read则是读取的是事务开始时候行数据版本。

一致性锁定读

select ... for update加的是一个排它锁，select ... lock in share mode加的是一个共享锁。但是就算加了排它锁，上面的一致性非锁定读还是可以获取到快照信息。

自增长问题

一般来说我们都是让主键进行自增长的，实现起来也很方便，就是用一个计数器。在并发下面由于操作不是原子性的，所以innodb使用的是特殊的表锁机制：事务等待前一个插入语句完成（而不是事务完成）。之后使用了互斥量进行操作，不过没有详细讲述。

锁的算法

行锁的算法

• record lock：锁定单行
• gap lock：锁定一个范围，但是不包含记录本身
• next-key lock：上面两者结合，锁定自己+一个范围，左开右闭。当查询的列是唯一索引的情况下，会降级成record lock

解决幻读

利用next-key lock就可以解决幻读问题。

事务

最简单的事务就是一旦出现问题就回到最原始的状态，而稍微改进一点就是在操作中加入保存点，就像游戏有存档一样。

事务的实现

事务的隔离性，是通过锁来实现的；原子性和持久性通过redo log实现；一致性是通过undo log实现的。

redo

在数据库运行的时候，不需要对redo log文件进行读取操作。只需要确保，在事务提交的时候，将这些操作写入到磁盘的文件中即可。当然如果设置不是每次事务commit都强制写入磁盘可以大大提升效率，但是机器宕机的时候可能会发生最后的那些数据丢失的问题。

二进制日志binlog和重做日志redolog之间的区别：

• 二进制日志是mysql数据库上层生成的，任何存储引擎对数据库更改都会产生，而重做日志仅仅由innodb生成。
• 二进制日志是一种逻辑日志，记录了使数据库发生改变的语句。而重做日志是记录的是页的修改。
• 二进制日志只是在事务提交完成后，一次性写入；重做日志会随着事务的进行而不停写入。

重做日志是通过块的方式保存的，一块的大小是512字节。其中还需要有12字节的头部和8字节的尾部。一个一个的块组合在一起就成了log group。

重做日志还有一个特性，就是它是幂等的，

undo

与redo不同，undo存放在数据库内部的段中，段则位于共享表空间中。而且undo存的是逻辑修改：对于Insert，innodb会使用delete修改回去；对于delete则使用insert修改回去；对于update则使用反向update修改回去。

mvcc也是通过undo日志来完成的。用户读取一行记录，如果这条记录别的事务在使用，那么就可以通过undo来读取之前的信息，实现一致性非锁定读。所以事务完成之后，undolog也不能马上删除，因为可能有别的事务需要读取之前的undo log来实现mvcc，具体的删除交给线程来判断。

最后，undo log也会产生redo log。

分布式事务

在使用分布式事务的时候，隔离级别必须设置成串行化。

外部分布式XA

XA由多个资源管理器，一个事务管理器和一个应用程序组成。

• 资源管理器RM：通常一个数据库就是一个资源管理器。
• 事务管理器TM：协调各个事务

简单来说就分成两个阶段，第一阶段TM告知各个RM进行准备，如果所有人都准备好了，那么TM就告知进行提交或者进行回滚；只要有一个RM没有准备好，大家就都需要回滚。

内部XA

在事务提交的时候，希望先写二进制日志，然后再写重做日志。且希望这两个操作是原子的，这主要是为了主从之间的一致性问题。

备份与恢复

跳过。目前用不到。

性能调优

CPU

我个人目前接触到数据库用的比较多的操作就是查询数据，偶尔插入或者修改一两条数据。所以针对我这种用户，显然是IO性能需要强悍一点，CPU可以一般。当然如果CPU是多核的。那么可以通过修改之前提到的写线程和读线程的数量来充分利用CPU的多核性能。

内存

内存当然是越大越好啊，如果大到能把整个数据库都放进去，速度就是美滋滋的了。但是实际中并没有很多钱来买内存，所以需要预估出来活跃的数据有多少，并且根据活跃的数据来分配内存，活跃数据可以通过查看缓存的命中率来看，如果命中率地狱99%，那就需要警惕了。

磁盘

如果是传统的机械硬盘，可以组成RAID来提高性能，或者是通过吧数据文件分布在各个硬盘中来达到负载均衡。

如果用的是固态硬盘，可以增加innodb_io_capacity的值。

RAID

这部分就算了吧。

操作系统

我是一直在linux下使用mysql的

记录下目前自己看过的书以及想看的书，也发表下自己的看法，书的种类不限，其中大部分都是技术相关的书籍。

本博文是对《Redis设计与实现》的读书笔记，这书写的真的是挺好的，值得一看。本书基于Redis2.9，而我看的时候最新版本的Redis是6.0，所以代码部分我是直接用的6.0。

数据结构和对象

Redis一共有五种基本对象（Object），分别是：

• 字符串对象 string object
• 哈希对象 hash object
• 列表对象 list object
• 集合对象 set object
• 有序集合对象 sorted set object

而每一种对象的背后，起码有两种数据结构来对其进行实现，这些对象都是一个个redisObject，下面是redisObject的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef struct redisObject {
    // 具体是什么对象
    unsigned type:4;
    // 对象用的底层实现是什么
    unsigned encoding:4;
    // 下面的lru先忽略
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    // 引用计数
    int refcount;
    // 指向底层具体的结构
    void *ptr;
} robj;

字符串对象底层结构

字符串的底层可以有三种，分别是int、raw和embstr。

int自然不必多说，如果我需要保存字符串”12345”，那么我完全可以用int来保存它（当然不能超过阈值）。

如果要表示的字符串它不是数字，那么有两种情况：

1. 该字符串的长度大于32字节，那么用SDS来保存，即为raw编码来实现。
2. 该字符串长度小于32字节，那么使用embstr的编码来保存。

SDS

首先新增了两个属性分别是free和len，一个用来指明还有多少空间剩余，一个则是指明数组的长度（不包括最后一个\0）。

这个数据结构的空间分配也有点意思：如果len的值小于1MB，那么还会额外为SDS分配等量的free空间。总空间则是len+free+1。如果len大于了1MB，那么就只会分配给1MB的空间。也就是每次Redis都会浪费一半的空间。在释放空间的时候，并不是直接释放，而是惰性释放，只有调用相关api的时候才真正的释放。

同样因为使用了len这个数值作为判断依据，所以可以保存二进制的数据。

raw编码和embstr编码

raw编码和embstr编码都使用的是一种叫SDS的结构，该结构就是为了在普通的char []数组上，封装了一个长度（len）和空余空间（free）这两个属性（在Redis6.0里面我看到是有5种SDS，其实就是len和free单位的变化）。 len的意思就是当前字符串占的长度，比如hello的长度就是5（当然第6位是\0，即空字符是不计算在len中的），而free则是还剩下多少空间没使用。

使用SDS的好处是，首先strlen()的时间复杂度变成了O(1)，其次是不用担心缓冲区溢出，再来就是可以有效减少内存分配的次数，最后就是可以有效的存储二进制数据。SDS最底层用的还是char buf[]，所以最后字符串最后一位还是\0，只不过这个最后一位不计算在len中。

那么它们的区别是什么呢？

raw编码会调用两次内存分配函数，分别分配redisObject和sds，而embstr则只会调用一次内存分配函数，将redisObject和sds紧紧挨着放在同一块内存中。同时embstr是只读的，也就是如果你要使用APPEND这类的函数来操作字符串，那么会先将其转换成raw编码的。

###哈希对象底层结构

哈希底层结构是ziplist或者hashtable。

ziplist

从名字上看这是一个压缩的列表，如果列表里的数字比较小，字符串又比较短，那么就可以使用ziplist来作为底层的数据结构。为什么能用来作为哈希对象的底层结构呢？其实只要是列表，那我完全可以list[0]作为key，list[1]作为value，以此类推即可。这个数据结构主要是从节约内存的角度来考虑的，它长这个样子：

接下来是对每一部分的说明：

可以看到，正是因为每一个列表的节点长度都是由节点保存的内存来决定，而不是固定大小，所以才可以节约内存。

对于每一个entryX，都记录了它前一个节点的长度，所以我们可以很轻松的通过指针减，从zltail开始不断往前遍历ziplist。

也就是ziplist其实在内存中是倒着存放你的数据的，但是因为读起来也是倒着读的，所以其实压根没有影响。

而压缩表最需要注意的就是有的时候可能会一个变化导致整个压缩表都需要更新，此时就非常消耗性能了。

hashtable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 整个hashtable
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
  
    // sizemask = size-1，用来计算索引的
    unsigned long sizemask;
    unsigned long used;
} dictht;

// 其中的一条key-value
typedef struct dictEntry {
    void *key;
    union {
        // 值可以从下面四选一
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

所以hashtable的整体构造图如下图所示：

上图中还发生了哈希碰撞，可以看到是后来的k1v1，在链表中的位置是在k0v0之前的——即使用的是头插法而不是尾插法。跟java中的hashmap如出一辙。扩容方法都是一致的，乘以二进行扩容。

dict

在hashtable基础之上，又封装了一层：

1
2
3
4
5
6
7

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

其中最重要的就是ht[2]这个hashtable数组，ht[0]就是原先的hashtable，而当需要rehash的时候，就会把值慢慢移动到ht[1]中（注意是慢慢的，而不是一次性，否则要重新计算那么多hash，CPU受不了），一旦开始移动了，就不会再往ht[0]中存放数据了。

列表对象底层结构

列表对象可以由ziplist数据结构和linkedlist数据结构作为底层数据结构，ziplist上面已经讲过了，而linkedlist就是双向列表，最最基础的数据结构了，不可能不会。

集合对象底层结构

集合对象的底层结构可以由hashtable（只使用它的键值对中的键，所有的值一律为null即可）和intset（注意和insert的区别）来实现。

intset

1
2
3
4
5
6

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

contents里面存的是按照从小到大排列的整数，其类型不一定是int8_t，而是由encoding来指定的。

显然这个数据结构就是用来实现整数的集合的。而这个contents就是用来存放这些整数的，按照从小到大的顺序，且不会重复。

这个数据结构要弄清楚的就是升级和降级，升级就是原来存的每一个元素都是16位的，结果发现来了一个特别大或者特别小的数字，那么16位不够用，就需要对所有的元素进行一次升级，将它们升级到和这个数字一样的大小。降级也是同理。注意，由于是新来的数字导致了需要升级，所以这个数字必然是最大的或者最小的，所以其实效率还是可以接受的。

有序集合对象底层结构

有序集合，就是每一个元素都有一个值，按照该值的大小对集合进行排序。它的底层结构可以是ziplist或者skiplist（面试常考）。

跳表

跳表的实质跟二叉树非常像，基本思想都是一开始上来先减掉一半，然后接着砍一半。

第一列是跳表的基本结构，第二列可以看到是L32~L1的结构，接下来就分别是三个元素o1o2和o3，以及它们的分数1.0，2.0和3.0

每一列（除了L32那列）的层数，都是随机生成的，为的就是防止插入和删除需要来维持数据结构而浪费过多时间。

具体的更加详细的数学证明可以参考 这篇博客，如果只是简单使用理解，相信是非常简单的。

单机数据库

数据库

在redis中，用redisServer这个数据结构来代表redis的服务器，里面最重要的就是redisDb *db;这个数组，每一个元素都对应了一个数据库，而这个数据库下面最重要的就是dict *dict这个结构，也就是数据库底层就是一个字典（还给这个字典取了个好听的名字叫key space，键空间），还有一个属性是dbnum，默认是16，这也就是为什么默认redis里面默认就有16个数据库。而在redisClient中则是用redisDb *db;来指向目前正在操作的数据库类型。

Redis中有4个指令可以用于操作数据库设置键的过期时间：

1. EXPIRE key ttl：多少秒后过期
2. PEXPIRE key ttl：多少毫秒后过期
3. EXPIREAT key timestamp：在某个时间戳（秒为单位）后过期
4. PEXPIREAT key timestamp：在某个时间戳（毫秒为单位）后过期

这四个可以很轻松进行转化，所以在Redis中会都转化成第四个进行操作。为了实现这个，Redis对每个数据库都有一个对应的叫expires的字典，该字典保存了键的过期时间（如果没有过期时间，则这个字典中就不会有相应的值）。实际中，这个字典的key保存的是声明了过期时间的对象（这个会和dict中共享，所以对象是不会重复的，也就是空间其实是很省的），然后value自然就是过期的unix timestamp（毫秒为单位）了。

对于键的过期操作，也有三种，分别是：

• 定时删除：在给键设置过期时间的同时，创建一个定时器，只要过期时间一到，键就被删除。可以即时释放内存空间，但是对CPU不友好，并不推荐。
• 惰性删除：键过期了不管，但是当获取键的时候，先去检查一下有没有过期，过期了就顺手删掉。对CPU友好，但是对内存不友好。
• 定期删除：每隔一段时间对数据库进行检查。使用的是抽查模式，而不是遍历。

Redis在实际中用的是惰性删除和定期删除。

过期删除键对数据库的影响，只有一条比较违背常识：当主从服务器中都有一个key到了过期的时候，如果去从服务器访问这个key，这个key可以正常读写不被删除，只有当去主服务器进行读的时候，才会在所有的服务器上删除这个过期的key。这么做的目的是统一

总得来说就是一个server下面有一个db数组，对应了多个db，然后每个db下面有两个字典，一个存放真实的键值对，一个存放过期时间。

持久化

持久化有两种，一种是保存了从数据库开始到现在为止的所有操作（当然是需要优化过的），还有一种就是把内存里的数据给直接存到磁盘里，至于具体磁盘里的格式，我个人觉得是没必要掌握的。

事件

Redis服务器需要处理两类事件：

• 文件事件：客户端和服务器之间，服务器相互之间都是通过套接字来进行连接的，文件事件就是对套接字操作的抽象（所以你可以直接理解为，如果客户端要向服务器发送消息，本质上就是在写一个文件，其余同理）
• 时间事件：服务器中有一些操作需要每隔多久的时间来执行，这类操作就被抽象成了时间事件。

文件事件

我们都知道Redis是单进程单线程来进行处理套接字的，这就需要解决阻塞的问题，而一般的解决办法就是用多进程/多线程来进行处理，而Redis则是使用IO多路复用，相当于当某一个socket可读可写了，就由操作系统来通知Redis服务器，这样Redis服务器就去读写，整体的结构就如图所示：

当客户端对套接字执行write操作，类似于你现在需要从客户端发送一条命令给服务器，对应的服务器的套接字就变得可读，于是就产生了AE_READABLE事件。

同理，当客户端对套接字执行read操作的时候，套接字产生AE_WRITEABLE事件。

产生事件的类型，其实就是根据服务器对于socket的读写来确定的。所以我们可以说Redis服务器是一个事件驱动的程序，发生了对应的事件，就调用不同的处理器进行处理。

时间事件

Redis服务器中就只有一个叫serverCron的函数作为时间事件的处理函数，基本理念就是每隔100ms进行一次检查操作。

多机数据库

复制

复制其实很简单，因为Redis是内存数据库，所以当我们从磁盘中恢复一个Redis的时候，就相当于在复制这个Redis数据库。现实中碰到的一个问题是复制可能需要的量太大了（毕竟从磁盘到内存的速度肯定是远远大于你在网络中传输的速度），这个需要额外使用一个缓存区，这样当一个服务器掉线的时候，服务器只需要把该服务器掉线之后的那些命令发送给它就能实现同步了。

同步

从服务器在复制主服务器的内容的时候，是通过SYNC这个命令来完成的。主服务器在收到这个命令之后，会使用BGSAVE命令来生成一个RDB文件，并且记录下从开始BGSAVE之后的所有命令。这样只需要把这个RDB文件发送给从服务器，并且把记录下来的命令也一并发给从服务器就可以了。

传播

在同步完成之后，主从两者的状态就一致了，接下来只要让任何命令都传播一下就好了。

部分重同步

每当主服务器向从服务器发送N个字节的数据之后，就把自己的offset+N。同理，从服务器收到之后也加上N。所以只需要比对一下offset就可以知道同步的状态了。而为了同步，主服务器还有一块缓冲区（缓冲区记录了偏移量以及对应的字节）用来保存最近的命令。这样从服务器如果断线之后，只需要把自己的offset发过来，主服务器根据缓冲区就可以知道到底是进行部分重同步呢，还是完整重同步。

除此之外，当从服务器第一次连接到主服务器的时候，主服务器会发送自己的id给从服务器，以便之后从服务器断线重连后判断。

心跳检测

从服务器每隔一秒发送一次offset。这个可以用来检测两者的网络连接是否正常，并且主服务器能够知晓从服务器目前的状态，并根据从服务器的状态来进行调整。

sentinel（高可用）

当sentinel检测到主服务器下线的时候，它会通知其中一个从服务器，将其作为主服务器，并通知其他所有的从服务器，让它们听命于新的主服务器。如果之前的主服务器上线了，那么也只有乖乖做从服务器的份。

基本步骤

sentinel本身是一个特殊的Redis服务器，只不过里面使用了不同的命令表，所以对于一般的服务器能用的指令对它是不生效的。

在配置文件里可以写好需要监视的主服务器的ip/port。在启动好sentinel之后，就需要向服务器创建两个链接。一个用来向主服务器发送命令并接收恢复，另外一个是用来订阅连接的。

sentinel会每隔10秒向被监视的主服务器发送INFO命令，来获取它们的信息（主服务器会自动向sentinel返回从服务器的信息），然后sentinel就可以知道从服务器的信息，并且会向从服务器同样建立命令连接和订阅连接。

接下来，sentinel也会向从服务器默认每隔10秒发送一次INFO命令，获取信息。

此时相当于sentinel已经知道了所有服务器的状态信息，接下来它会通过每隔2秒一次的频率，通过命令连接向服务器的频道发送一条信息。并且sentinel自身也会通过订阅连接向服务器发送订阅内容。这里有一点点绕，简单来说就是sentinel通过命令连接给每个（主从都要）服务器发送一条消息到频道中，并且还通过订阅链接从频道中接受信息。这个如果只有一台sentinel的话，看上去很蠢，因为这个其实是为了多台sentinel之间共享信息而设计的。然后sentinel就会跟别的sentinel建立命令连接。

总结：每隔10秒向所有主从服务器发送INFO命令来更新，每隔2秒向订阅连接发送消息并且接受消息，相当于每隔2秒更新其它sentinel的消息。

检测下线

sentinel会每隔一秒向所有的服务器（主、从、其余sentinel）发送一个PING，来判断它们是否在线。超过一定时间不回复，或者都是无效的回复的话，就主观认定下线了。

然后此时sentinel会向别的sentinel去询问它们关于这台服务器的下线与否的判断（因为不同sentinel配置的下线时间是不同的），根据得到的回复进行进一步判断。

如果一个服务器被认定为客观下线了，那么监视这个服务器的各个sentinel会协商出一个领头sentinel，这个算法就是raft算法。这里简单描述一下：每一轮选举都有一个计数器来指示这是第几轮，不论选举是不是成功，都会自增。所有的sentinel都会要求将自己作为领头的，而只有收到超过半数支持的sentinel才是真正的领头sentinel。你可能会担心这样冲突会不会导致最后没有一个sentinel能称为领头的？这个靠的是时间差，一般来说总有一个sentinel能够最先发起选票，这样大家都会投它。

接下来这个领头的sentinel会选取一个从服务器，令它成为主服务器，并且让所有其他的从服务器让它作为主服务器。

它的核心思想就是向被监视的主服务器发送INFO命令，来获取它们的信息（主服务器会自动向sentinel返回从服务器的信息），同时sentinel之间也会通过频道来接手别的sentinel的信息，彼此之间互相了解。当sentinel检测的服务器下线的时候，它就会向所有的监视这个服务器的sentinel发出询问，如果半数sentinel认为它下线了，那么就需要做一个故障转移（利用raft算法选举行的主服务器并进行一系列操作）

集群

集群的本质，你可以理解为一个大的数据库，然后每个redis都是它的一部分。集群一共有16384个槽，这些槽被所有节点分了，每个槽必定属于其中的一个redis。然后每个Redis都是知道任何一个槽都是由谁来负责的（通过互相之间信息沟通）。所以任何一个节点在接受到命令，并且计算出对应的数据在哪个槽的时候，都能够知道应该去哪个redis里面获取数据。

集群中的各个节点都是互相进行通信的，如果有个节点发现了超过半数的节点认为一个节点下线了，那么就会发送一条该节点下线了的消息广播给大家。此时就会从该下线的主服务器的从服务器中选举（raft算法）出一个来代替它作为新的主服务器并且负责指定的槽。

独立功能的实现

这部分其实涵盖了内容的发布和订阅、事务、lua脚本、排序（用的就是快排）、二进制位数组（本质上就是字节数组，没啥好说的）、慢查询日志（链表）和监视器。

事务

事务的四大特性，看看Redis是如何实现的：

• 原子性：由于Redis中是通过一个事务列表来保存所有的命令，最后一次执行的，所以具有原子性。但是Redis本身是不支持事务回滚的，作者的观点是要简单高效。
• 一致性：
  • 命令在进入事务队列的时候就出错了，那么就不会执行，所以数据肯定是一致的。
  • 命令在执行的时候搓了，服务器可以进行对应的错误处理（告知客户），出错的命令是不会对数据库进行任何修改的，所以不会对事务的一致性产生影响。我个人理解，书里这么写是有问题的，那我如果对一个客户加100元钱正确执行了，扣100元的执行错误了，你跟我说一致性没问题吗？
  • 服务器停机。如果是什么措施都没有的，那新的数据库是空的，所以数据是一致的（？？？？我理解不能），如果是RDB模式，算了书里真的是完全颠覆了我的三观…..
• 隔离性：这个最好理解，单线程，肯定没人干扰，绝对隔离。
• 耐久性：这个主要是看你对Redis的设置。

作者认为，ACID中只有耐久性Redis是需要看配置来决定是否满足的，其它三个都满足。我个人认为，它仅仅满足了隔离性，耐久性看配置，原子性和一致性压根没满足，因为它允许其中的一条命令失败。

本博文对应《深入理解java虚拟机》第五部分，第十二章和第十三章。

物理机内存模型

我们先来看看物理机是怎么做的，这样可以更好的了解java是怎么做的。

在多处理器中，是通过处理器缓存来解决内存速度过慢的问题的，即先从内存到缓存，然后CPU再从缓存中读取（这里为了说明问题，忽略了多级缓存等中间真实存在的东西而将它们合称为缓存），也就是多个处理器它不是从内存中直接读取数据的，这样势必造成处理器A的缓存刚从内存中读取了数据，处理器B就更新了缓存，也就是常说的缓存一致性问题。当然为了避免这种情况的发生，人们发明了一些协议来确保，这些用在“物理机”上的协议不是博客关注的要点。

本文对应《深入理解java虚拟机》第四部分，即第十章和第十一章，主要讲了编译器相关的部分。

前端编译

本书一共介绍了三种编译器，分别是前端编译器（负责把.java文件编译成.class文件），即时编译器（把字节码文件编译成本地机器码）和提前编译器（直接把java代码编译成机器码）。接下里来的内容就是对javac这款用java写的编译器进行的分析。

编译过程

由于真的是没学过《编译原理》，那些什么词法分析，语法分析是真的看不懂，所以这里就直接把这些过程直接省略了，这部分我的重点是对一些语法糖的理解。

注解处理器

目前用到的几乎所有框架，都可以通过@xxx来进行注解式编程，极大地提升了我们的效率。而这些注解，实际上就是靠着注解处理器，在编译的过程来替我们完成这些复杂代码的编写的。

语法糖

语法糖分析包含泛型、自动装箱拆箱分析。

泛型

在java中，List<String>和List<Integer>本质上是同一种类型——List，而在C#中则是两种类型。这是java为了能够兼容以前的代码，不得不进行的一种妥协，除了实现起来方便（几乎只需要修改部分编译器的内容）以外，其它在性能、灵活性等均被完爆……

接下来看看泛型是如何实现的。其实只需要将代码编译一下，然后反编译一下就知道了。

emmmm 我使用IDEA进行反编译发现反编译回来的代码仍然带着泛型……可能是太智能了吧。

总得来说就是会把List<String>类型擦除，变成List，然后每次放入取出的时候进行强制类型转化。

接下来谈谈java泛型的缺点：

1. 不支持原生类型：List<int> list = new ArrayList<>(); //报错，这是因为int没办法转成Object。
2. 由于编译器就自动把泛型擦掉了，那么运行的时候自然无法得知。但是由于有Signature参数，实际我们还是能够通过反射的方法获取到类型的。
3. 针对重载的问题。部分编译器上可能会通过下面的代码（我的无法通过，确实是应该通过不了的）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class GenericTest {
    public static String method(ArrayList<String> list){
        System.out.println("method1");
        return "";
    }

    public static int method(ArrayList<Integer> list){
        System.out.println("method2");
        return 1;
    }
    public static void main(String[] args) {
        method(new ArrayList<String>());
    }
}

自动装箱、拆箱和增强for循环

自动装箱和拆箱我想一般人都非常好理解，只需要等价替换即可。比如Integer i = 10;会被编译器自动装箱成Integer i = Integer.valueOf(10);。

增强for循环也很好理解，本质上其实就是使用了目标对象的iterator来进行的遍历而已。

接下来是面试中可能也会问道的一段代码分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class AutoBoxTest {
    public static void main(String[] args) {
        Integer a = 1;
        Integer b = 2;
        Integer c = 3;
        Integer d = 3;
        Integer e = 321;
        Integer f = 321;
        Long g = 3L;
        System.out.println(c == d);             // true JVM会缓存-128~127
        System.out.println(e == f);             // false 同第一条
        System.out.println(c == (a + b));       // true == 不发生自动拆箱，除非遇到运算符
        System.out.println(c.equals(a + b));    // true 类型相同，值也相同
        System.out.println(g == (a + b));       // true == 不发生自动拆箱，除非遇到运算符
        System.out.println(g.equals(a + b));    // false 类型不同，值相同
    }
}

条件编译

当java遇到if(true)这样子的代码的时候，会自动把else里面相关的代码给去掉，因为反正也不可能会被运行到。

后端编译

这里讲的后端编译就是讲的JIT及时编译器。

以Hotspot虚拟机为例，其内部同时有解释器与编译器，两者同时运行，且两者各有优缺点。

mixed mode即说明运行的时候既用解释器，也用即时编译器。

解释器的存在可以让程序无需编译直接启动；编译器的存在可以让一些热点代码被编译成机器码从而提升java的运行效率。而且编译器还有三个，分别是客户端编译器（C1）、服务端编译器（C2）和实验性质的Graal编译器。

编译对象和条件

那么到底满足什么条件会触发编译器呢？编译哪些东西呢？

• 被多次调用的方法。
• 被多次执行的循环体。

而循环体只可能是在方法中的，所以其实面向的就是方法来进行即时编译。虚拟机同时还通过对方法栈进行周期性检查，如果发现某个方法经常在栈顶，则说明是热点方法；或者是通过一个计数器，当超过计数器的数值的就认为是热点方法，当然计数器的开销会比较大，因为每个方法都需要维护一个计数器。

当确定需要进行即时编译的时候，并不是直接交给编译器然后进行等待，而是交给编译器后继续由解释器进行执行，当下次再执行到的时候就可以用优化过的机器码来加速了。

提前编译器

基本从来没接触过的东西，类似于C++的那种编译器，全部给编译好。听上去很不错，这样效率不是大大提升了么？但是这么做其实是和java的目标不太一致，java本来就是为了跨平台而考虑的，而提前编译会要求一些物理机的信息来进行优化。

不过我们还是可以针对我们最常用的一些库来进行提前编译，这样能够在自己机器上测试的时候极大的提速。

本篇对应《深入理解java虚拟机》第九章，通过几个案例的讲述来深入理解。

tomcat的类加载器

Tomcat一共有三组目录用来存放java的类库，然后还有一个是web程序自带的/WEB-INF/*目录，分别代表的含义：

• /common目录下，可以被tomcat和所有的web程序使用
• /server目录下，只有tomcat可以使用该类库
• /shared目录下，只有所有的web程序可以使用，Tomcat本身却无法使用。
• /WEB-INF下，仅仅该web应用程序可以使用。

Tomcat实现了多个类加载器来分别加载这些类库。当然不论什么类加载器必然是需要实现双亲委派模型的，于是就有下面这张图了。

其中每个类加载器对应各自目录下的类库的加载，而且一般会有多个WebApp类加载器和多个Jsp类加载器。Jsp加载器的目的是为了实现热更新，即当JSP发生变化的时候，直接换一个JsperLoader来加载最新的JSP文件。

本博文对应《深入理解java虚拟机》第八章

概述

java虚拟机通常会有解释器（解释执行）和即时编译器（编译执行）两种选择，而且大部分的虚拟机都是包含这两种引擎的。

栈帧结构

java虚拟机以方法作为最基本的执行单元，而之前也提到过，一个栈帧对应了一个方法。

栈帧存储了方法的局部变量表、操作数栈、动态链接和方法的返回地址等信息。一个方法从开始执行到执行结束，对应的是在虚拟机栈里面从入栈到出栈的全过程。

在编译的时候，栈帧需要多大的局部变量表，多深的操作数栈其实已经知道了，并且写到了方法表的Code属性里。也就是说栈帧需要多少内存，完全是在编译的时候就已经决定好了。

局部变量表

局部变量表用来存放方法的参数（别忘了隐形参数this）+内部定义的局部变量。

虚拟机使用“槽”—slot的概念来存放这些数据，除了long和double，都可以用32位放下，就称这32位为一个槽。如果对于long和double的读取，虚拟机不允许用任何方式单独访问其中的一个槽，必须两个一起。

槽是可以复用的，当一个槽里面的数据的作用域已经超出了当前的代码，那这个槽显然就可以被用来存放新的数据了。下面用一个例子来说明这一举措，这一例子我个人觉得非常有用。

1
2
3
4
5
6
7

public static void main(String[] args) {
    // 分配64M空间
    {
        byte[] placeHolder = new byte[64 * 1024 * 1024];
    }
    System.gc();
}

带上vm参数：-verbose:gc可以看到垃圾回收的详情，如下图所示：

然后是稍微修改一点点的代码，改成这样子：

1
2
3
4
5
6
7
8

public static void main(String[] args) {
    // 分配64M空间
    {
        byte[] placeHolder = new byte[64 * 1024 * 1024];
        placeHolder = null;
    }
    System.gc();
}

然后瞬间就回收了很多：

这个解释起来也很简单，第一段代码中，虽然离开了placeHolder的作用区域，但是并没有新的槽被使用，而局部变量表作为GC Roots中的一员，显然是不会被回收的。然而当对其赋值null的时候，相当于读写了局部变量表，这就导致了变量槽的变更，所以就能够回收掉这64M的内存。

当然平时的时候没有必要这么做，因为你随便另外一个变量赋值也能达到相同的效果，而且还有编译器优化等。

操作数栈

程序翻译而成的指令，要进行相应的操作，用的就是操作数栈。以加法为例，iadd指令会取出栈顶的两个元素，然后对它们进行求和之后再放回栈顶。

两个方法，从本质上讲是属于两个栈帧的，而每个栈帧都会有一个操作数栈，理论上这两个操作数栈应该毫无关系，但是实际中却会让一个栈帧的操作数栈和另外一个栈帧的局部变量表进行重合，这样做的目的是为了能够方便的共享数据。

动态连接

我们需要知道当前栈帧对应的是哪个方法，于是在每个栈帧中就会有一个指向运行时常量池的引用，当我们把这个引用（符号引用）转化为真实地址的时候，就叫动态连接。

返回地址

方法要么正常结束返回，要么遇到了异常且没有在方法中得到处理，这种方式退出的话是没有返回值的。

如果方法是正常退出，我们只需要去找到调用当前的方法的PC计数器，PC计数器的值就是返回地址。当方法是异常退出的时候，那就需要通过异常处理器来确定了。

方法调用

这里的方法调用，不是要讲进入到方法内部执行方法内部的代码，而是确定要调用哪个方法。

之前讲到过，class文件里面存储的是符号引用，所以还需要到运行时常量池里面找到对应的内存地址（即直接引用）。

在java中，有静态方法和私有方法这两种方法，它们的特点是，不可以通过继承等方法弄出一个新的版本来，所以它们适合在类加载的时候就进行解析（之前就分析过了）

同时java也支持五种方法调用的指令，它们分别是：

• invokestatic：调用静态方法
• invokespecial：调用构造方法、私有方法和父类中的方法
• invokevirtual：调用虚方法
• invokeinterface：调用接口方法，在运行的时候才确定是哪个实现该接口的对象
• invokedynamic：在运行时动态解析出所引用的方法，然后再执行

静态方法、私有方法、构造方法和父类方法这四种，可以在解析的时候就能确定，再加上一个final修饰的方法，可以在类加载的时候就直接把符号引用变成直接引用。

分派

静态分派

分派揭示了多态特征的基本体现，深入了解它，就可以知道“重载”和“重写”的最基本原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class StaticDispatch {
    static abstract class Human {
    }

    static class Man extends Human {
    }

    static class Woman extends Human {
    }

    public void sayHello(Human human) {
        System.out.println("hello guy!");
    }

    public void sayHello(Man man) {
        System.out.println("hello man!");
    }

    public void sayHello(Woman woman) {
        System.out.println("hello woman!");
    }

    public static void main(String[] args) {
        Human man = new Man();
        Human woman = new Woman();
        StaticDispatch sd = new StaticDispatch();
        sd.sayHello(man);
        sd.sayHello(woman);
    }
}

这段代码会输出两个hello guy。也就是说虽然方法进行了重载，但是这俩都选择了第一个方法。

上面的Human我们称之为变量的静态类型（Static Type），而Man则成为叫实际类型（Actual Type）或者叫运行时类型（Runtime Type）。显然在编译器就可以知道静态类型，而实际类型则需要到运行期才可以知晓。

重载的时候，确定使用哪个方法，完全取决于传入参数的数量和数据类型。上面的代码中，静态类型都是Human，实际类型一个是Man一个是Woman，但是重载是通过参数的静态变量类型来作为判决依据的，所以就选择了Human。真想使用的话，得使用强制类型转化：sd.sayHello((Man)man);才可以。

动态分派

静态分派影响了重载，而动态分派则影响了重写。还是一样先来个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class DynamicDispatch {
    static abstract class Human {
        protected abstract void sayHello();
    }

    static class Man extends Human {
        @Override
        protected void sayHello() {
            System.out.println("man say hello");
        }
    }

    static class Woman extends Human {
        @Override
        protected void sayHello() {
            System.out.println("woman say hello");
        }
    }

    public static void main(String[] args) {
        Human man = new Man();
        Human woman = new Woman();
        man.sayHello();
        woman.sayHello();

        man = new Woman();
        man.sayHello();
    }
}

理解了上面的例子的话，这个例子就非常容易了。重写看重的是实际类型。

根据字节码我们可以看出最终影响重写的，是invokevirtual指令，该指令大致分成几个步骤：

1. 找到栈顶元素（man）所指向对象的实际类型（Man），记做C
2. 看看C能否找到描述符和简单名称都相符的方法，并进行权限验证，找到就返回直接引用。
3. 否则就按照继承的关系从下往上找
4. 找到最顶层都没找到的话，就返回异常。

上面也说了，是invokevirtual这个指令才这么做的，也就是说只会对方法有效，而字段无效；所以当父类的字段子类也有的时候，这两个字段内存中都会存在，但是子类的字段会盖过父类的。

单分派与多分派

静态分派和动态分派解决了重载和重写的问题。下面是一段示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Dispatch {

    static class QQ {

    }

    static class _360 {

    }

    public static class Father {
        public void hardChoice(QQ arg) {
            System.out.println("father chose qq");
        }

        public void hardChoice(_360 arg) {
            System.out.println("father chose 360");
        }
    }


    public static class Son extends Father {
        @Override
        public void hardChoice(QQ arg) {
            System.out.println("son chose qq");
        }

        @Override
        public void hardChoice(_360 arg) {
            System.out.println("son chose 360");
        }
    }

    public static void main(String[] args) {
        Father father = new Father();
        Son son = new Son();
        father.hardChoice(new _360());
        son.hardChoice(new QQ());
    }

}

很简单，相信任何人都知道该程序会输出什么。我们按照编译过程+执行过程的流程来走一遍。

首先编译器发现了father调用了hardChoice，那么根据father的静态类型是Father，所以定位到了Father里面，看到hardChoice发生了重载，那么也就是有两条invokevirtual指令，分别是参数为360的和参数是QQ的，于是就得到了确认。也就是说，静态分派根据方法名字+方法参数才确定了使用哪一个重载方法，所以说静态分派是多分派类型。

到了运行期，虚拟机已经明确知道需要执行哪个类的哪个方法了，唯一影响的，就只有该方法的接受者的实际类型是什么，显然这里father的实际类型就是Father，所以我们说动态分派是单分派类型。

总结下来就是，java是一种静态多分派、动态单分派的语言。

动态语言支持

java虚拟机的字节码指令从第一台虚拟机到今天，都只增加过一条指令invokedynamic，所以我们需要围绕它来了解一下java对动态语言的支持。

java.lang.invoke包

Python里面有一个很不错的“特性”，可以把函数赋值给一个参数，然后代入到方法中，这样函数本身就被“传”了进去，最典型的应用就是排序算法了。

但是java不可以，它不能把函数当成一个参数给传入进去，java中实际的做法是让一个类继承Comparator接口，并且新建出对象，传入对象来解决。

为了解决这个短板，引入了这个包，它提供了一种新的动态确定目标方法的机制，称为“方法句柄”Method Handle。当然如果只是相同的效果，那么其实反射早就可以完成了，但是反射没有它来的底层。

invokedynamic指令

该指令的第一个参数是一个invokedynamic_info常量，该常量有三项信息，分别是：引导方法，方法类型和名称。引导方法固定是返回java.lang.invoke.CallSite对象，该对象就是最终需要执行的目标方法。

基于栈的字节码解释执行引擎

这部分我个人觉得偏向于编译原理，所以可能比较难懂。

javac编译器完成了词法分析、语法分析、构造抽象语法树，并且遍历语法树生成线性字节码指令流。而解释器则在虚拟机内部，所以java的编译可以说是半独立实现。

javac编译器最后得到的.class文件，即字节码指令流，是一种基于栈的指令集架构，即依赖于操作数栈来完成指令的工作。而我们日常使用的PC则使用的是基于寄存器的指令集。

举一个1+1的例子来更直观的区分这两种指令集的区别，首先是基于栈的：

1
2
3
4

iconst_1   // 把1压入栈中
iconst_1   // 把1压入栈中
iadd			 // 弹出2个数字，相加，放回栈顶
istore_0   // 放回到局部变量表的第0个slot中

基于寄存器的

1
2

mov eax,1
add eax,1

java的这套基于栈的指令集，考虑的是可移植性的问题，当然性能肯定没有寄存器的那么优秀。而且我们也可以发现，所需要的指令数会比仅仅使用寄存器的多不少。更加要命的是，栈是在内存中的，而内存的速度肯定是远远比不上寄存器的。

这里提一句android的Dalvik虚拟机就是基于寄存器的，尽可能把虚拟机的寄存器映射到物理机的寄存器中去获得更好的性能。

本书一共分成五个部分，分别是

• 走近Java，了解java的过去现在和未来的走向

  • 第一章 介绍了java体系的发展史，并且介绍如何独立编译一个OpenJDK7（并没有写博文）

• 自动内存管理机制：只有了解了虚拟机是如何管理内存的，才能写出更加优秀的代码

  • 第二章：内存是如何划分的，各个区域常见的内存溢出异常介绍及实例代码。
  • 第三章 分析了 垃圾收集算法、常见的垃圾回收器以及Post not found: java内存分配机制 java内存分配机制 。
  • 第四章 介绍了 JDK相关的命令行工具以及可视化工具。
  • 第五章 介绍了几个实际的案例。