前言

之前用SpringBoot的时候就很好奇，SpringBoot究竟是如何启动的呢？今天花了点时间稍微研究了一下，认真看下到底是如何实现的。

1
2
3
4
5
6

@SpringBootApplication
public class MainApplication {
	public static void main(String[] args) {
		SpringApplication.run(MainApplication.class, args);
	}
}

可以看到就是这个类的main方法启动了整个框架，主题就是一个SpringApplication类的一个静态的run方法，把当前类作为类对象进行了传入，并且还把参数也顺手传递了进去。就这么简单。所以重要的其实就是SpringApplication这个类。

除了这个类之外，还不要忽略了@SpringBootApplication这个注解，正是注解+代码结合在一起才让spring真正的启动了起来。

前言

今天握手和挥手问题被面试官问到了。正好有点闲情，做个实验记录下加深自己对TCP的了解吧。

面试的题目：

• 如果客户端想要去和服务端建立连接，首先需要进行三次握手。那么如果服务端机器宕机了会怎么样呢（三次握手没建立前）？
• 如果客户端已经和服务端建立连接了，然后服务器上面的进程突然挂了，那么会怎么样呢？

PS，简单的握手和状态变化可以参考这篇文章，如果连最基本的都不了解还是先去通读吧。

前言

老实说，面试面来面去也就这么五六种设计模式，所以打算抽出点时间详细的了解下这五种设计模式。

单例

考的最多，同时也算是最常用的一种模式了，可以有以下几种实现：

• 懒汉式：只有当需要的时候才创建对象，线程不安全
• 饿汉式：在类加载的时候直接就创建好，非常简单。
• double check：懒汉式的一种，通过两次的if判断来满足线程安全。
• 静态内部类：懒汉式的一种，利用了静态内部类线程安全的特点
• 枚举：JVM自带的一种关键字实现，可以确保线程安全。

项目中用到了，之前只是简单的使用，现在需要好好的复习一波。

简介

rabbitmq是时下一款热门的消息中间件。有着高可靠，易扩展和丰富的功能等特性。

消息队列中间件（Message Queue Middleware，简称MQ）一般具有两种模式，一种是P2P，另一种就是发布和订阅模式。

消息中间价另外一大好处是，它可以帮助你暂时存储消息，这样就达成了良好的异步消息传递。

MQ的优点：

• 解耦
• 存储
• 削峰
• 顺序保证（部分）
• 异步通信
• 可恢复性

rabbitmq优点总结：

• 可靠性，通过持久化，传输确认和发布确认等机制来保证。
• 路由灵活
• 扩展性强
• 可用性高
• 支持多种协议
• 提供了易用的界面

前言

AbstractQueuedSynchronizer框架为Doug Lea大神为JDK所写的并发框架，在JDK1.5的时候正式加入了JDK，它是之后的各类锁的实现底层，所以了解它就可以有效了解这些锁的机制。它本质上是通过一个state来实现的。

内部类

首当其冲的是一个Node内部类，我这里只摘取比较重要的属性，首先默认是共享锁：

1
2
3
4

/** Marker to indicate a node is waiting in shared mode */
static final Node SHARED = new Node();
/** Marker to indicate a node is waiting in exclusive mode */
static final Node EXCLUSIVE = null;

然后有一个状态：

1
2
3
4
5
6
7
8

// 当前节点在队列中的状态
volatile int waitStatus;   

// 下面这些静态变量用来代表状态
static final int CANCELLED =  1;
static final int SIGNAL    = -1;
static final int CONDITION = -2;
static final int PROPAGATE = -3;

并且为这个状态定义了一堆的相关常量，这里省略。

除此之外，由于我们要构造一个链表来保存相关的Node，所以Node节点中还有对前驱节点后后置节点的引用。而且Node节点本身代表了一个线程，所以有一个线程的引用：

1
2
3
4

volatile Node prev;
volatile Node next;

volatile Thread thread;

AQS类

组成

往简单的说，AQS其实就是一个状态+一个链表组成的东西：

1
2
3

private transient volatile Node head;
private transient volatile Node tail;
private volatile int state;

对，就这三个属性（其它压根不重要）构成了AQS。其中的state就是用来实现可重入的机制的，每次进入都对其加一，离开锁就减一。

基础知识

线程安全性

线程安全，主要是这对那些共享的和可变的变量的访问来说的。这很容易理解，如果一个变量它都不是共享的，那就不会有线程安全问题；同理如果变量都不可变，那么再多的线程同时访问也不会有问题。

而当一个变量必须要被共享而且是可变的时候，那么就必须有同步机制来进行控制。

集合概述

java中的容器，都是实现了Map接口，或者是实现了Collection接口（Collection接口继承自Iterable）。下面这张图很形象说明了各种容器之间的关系：

那么可以聊一下这些橙色的接口了：

• List：有顺序，且可以是重复的。
• Queue：一端负责进，一端负责出。
• Dequeue：两端都可以进，两端都可以出。
• Set：无序且不可重复。
• SortedSet：其中的元素都是有顺序的。
• Map：使用键值对来保存数据的。
• SortedMap：可以对key进行排序。

写这篇的主要目的是为了简单复习一下，并且捎带再详细读一下JDK的源码，学习下人家是如何设计的

36. I/O Devices

input/output (I/O) device，显然是计算机必不可少的两个部分。

系统架构

CPU直接通过专用的内存总线和内存进行数据传输。另一些设备通过通用IO总线和系统交流，PCI就是其中的一部分（和显卡连接的，当然不止显卡）最后，也是最低级的就是一些周边设备的总线了，比如USB之类的与你的键盘、硬盘、鼠标等慢速设备进行连接。

注意，总线越快，那么就会越短，所以内存总线不能插太多.的设备。现在也有部分设备把内存和图形放到了同一个重要的层面上，大概长这样：

可以看到网络是通过PCIe进行连接的，所以速度很快。而图形和内存被直接与CPU进行连接，CPU还直接和一块io片通过DMI连接。

一个典型的设备

我们模拟一个设备，这个设备并不是真的。

可以看到一个设备主要分成了两个部分，上面代表了这个设备的“系统”，这部分被称为接口，是因为可以通过操控这个接口来控制整个设备。第二部分就是internal structure，这个相当于接口的实现部分，简单的设备就是一块物理芯片，而复杂一点的会包含一个简单的CPU。

一种典型的协议

还是上面的设备图，一个设备有状态寄存器，命令寄存器和数据寄存器，听名字就知道是干什么的了，操作系统只需要操作这三个寄存器，就能得到相应的结果。数据会在使用CPU的前提下，首先从内存到磁盘的寄存器中，然后磁盘会将寄存器中的值放到内部的盘面上。如果设备的CPU的时间被用来进等待数据从磁盘数据寄存器中，那么就叫做**programmed I/O (PIO)**。

一个简单的协议可能可以这么设计：

1. 不停判断设备是否是忙的，即轮询polling。
2. 如果设备不忙，就把数据写到data寄存器中。
3. 把命令写到command寄存器中，然后开始执行。
4. 继续等待，直到设备完成（可能成功也可能失败）。

这个协议看上去简单，而且也能工作，但是有很多问题：比如需要不停判断设备的状态，这样会导致CPU浪费。

通过中断

不是通过设备的轮询，而是通过让设备自己触发一个硬件中断，然后CPU就会跳转到操作系统指定好的interrupt handler中去，操作系统会执行相关的操作，比如唤醒一个进程去操作。

当然如果你的设备足够快，那么用轮询也是OK的。如果不确定设备的快慢，可以先轮询一会会，然后在使用中断。

在网络中也不建议使用，因为到达一个包就触发一次中断，可能会引起活锁：操作系统永远在处理中断反而没把精力花在处理数据上面了。

有一种优化就是合并，就是不要完成任务就去触发中断，而是稍微等一等，没准能和别的中断合并，减少系统负担。

DMA更有效的数据传输

如果需要将大量数据写入到磁盘中，也就是说需要CPU时间，把数据从内存搬动到设备中，对于大数据来说这部分时间还是很多的。

这个问题的解决办法是**Direct Memory Access (DMA)**，该设备对应的是芯片上的DMA控制器，它无需CPU过多的干预就可以在内存和设备之间传输消息。

还是上面的例子，CPU这次不是直接把数据从内存搬动到设备了，而是告诉DMA，数据放在内存哪里了，需要搬动多少，然后接下来就交给DMA去处理，DMA完成之后会触发中断告知已经完成。

设备通信

硬件该如何与设备进行通信呢？

有两种主流的方法

• 一种是显式的IO指令，该指令让OS把数据发送给设备寄存器，接下来就按照协议的内容操作。在x86上，通过in和out可以与设备进行交流。如果要发送数据给设备，那就指定好data寄存器已经对应的port，然后执行指令。当然这个指令是特权的，所以只有操作系统可以进行操作。
• 另外一种是通过memory- mapped I/O，内存映射IO。首先硬件把设备的寄存器映射成内存地址，那么OS只需要向内存写东西，就可以直接写到设备里取了。

这两种方式各有优缺点，而且目前仍然都在使用。

设备驱动

由于设备千千万，所以这里只能从大体上聊。我们如何才能使大多数OS设备保持中立，从而隐藏主要OS子系统中设备交互的详细信息？

答案就是抽象。在操作系统最低级层次中，有一个软件，叫做device driver，这个软件把和设备的交互细节全部封装在了里面，也就是操作系统通过它可以便利地操作硬件，而且这个驱动程序本身就是由硬件制造厂商提供的，所以能够充分发挥其作用。

举一个真正访问设备的例子。一个应用希望访问一个文件的内容，首先会产生一个read系统调用，然后通过文件系统，在到Generic Block Interface，然后是Generic Block Layer，再到Specific Block Interface，最后才是设备驱动。当然也可以不走文件系统，而是直接通过raw interface来访问。

一项研究表明，操作系统中70%的代码是设备驱动。

总结

在这一章中，对操作系统如何和设备进行交互有了基本的了解，具体讲了两种技术：DMA和中断，同样介绍两种方式去访问设备寄存器：指令和内存映射IO。最后还了解了一下设备驱动。

37. Hard Disk Drives

这一章中，了解一下硬盘是如何存储数据的，接口是什么。

接口

一个扇区是512字节，而硬盘有许许多多的这样的扇区，每个扇区都可以读和写。

大部分系统都是用页来作为基本单位的，也就是4K，但是硬盘只能保证对一个扇区（512字节）的读写是原子性的。

如果读取连续两块block（block和sector是等价的），那么速度会明显快于读取两块分开的block。顺序读是最快，而且远远快于随机读写。

基本结构

这个建议找个视频看看。

简单的硬盘

The Rotational Delay

就是虽然已经定位到了对应的一圈，但是还需要等待磁盘转到指定的位置才可以读写。

Seek Time

如果之前的磁道是错误的，还需要移动磁臂，移动到指定的磁道上面才可以。当然移动并没有想象中那么简单，因为需要什么加速减速啥的，涉及到一些物理的惯性之类的问题。

其它的细节

使用 track skew来保证就算跨越磁道，读取也是正确的。

第二点就是明显外部的扇区比内部的扇区多。

最后，一个重要的部分就是cache，也可以叫做track buffer，大概再8-16M之间。

在写入的时候，硬盘有一个选择：到底是等数据真正落到了磁道上之后，才报告完成呢，还是只要到了硬盘的内存中，就报告完成呢？

IO时间

T_I/O = T_seek + T_rotation + T_transfer ，这里给一个参考值：seek=4ms，rotation=2ms，transfer=0.03ms

显而易见嘛，需要先把磁头移动到磁道，然后要等待转到指定的扇区，最后还需要把数据写上去。

文中举了一个例子来说明，顺序读写的速度几乎是随机的200倍-300倍。

硬盘调度

之前在CPU虚拟化的时候提到过job scheduling，分成FIFO，SJF，RR等，而在磁盘这里有所不同，磁盘的job是可以预估出大概要花多少时间的，所以在这里，使用SJF是非常合适的。

SSTF: Shortest Seek Time First

该算法在早期的硬盘中很流行，核心思路就是根据磁头目前的位置，选择出最近的磁道，以最小化seek time。

但是也有弊端，首先是操作系统它并不知道硬盘的这个结构，所以操作系统实现了nearest-block-first (NBF)，即地址最接近的块优先。其次是第二个问题，饥饿。也就是我们只要解决了饥饿问题，这算法就非常的棒。

电梯算法（也叫SCAN）

我们把磁头从最外面到最里面（或者反向也可）称为一次sweep，如果有一个请求，并不会立即处理，而是在下一次sweep中处理。

这个就跟我们电梯一模一样，我从20楼坐电梯到1楼，当我达到3楼的时候，一个人进来了想要上去4楼，按了4。如果使用SSTF，那么就应该让它先，但是如果用电梯算法，我会先到1楼，然后才处理他的请求。

然而，这些算法其实都没有表现的很好，因为我们只考虑了seek time，而忽略了rotation time。

SPTF: Shortest Positioning Time First

和之前的页面置换算法中的那个完美算法一样，这个算法也是不现实的，只能说尽量逼近。

其它调度问题

在现代操作系统中，操作系统的调度器决定好request，然后交给磁盘，磁盘已经有能力自己来实现SPTF了。

另外一功能就是I/O merging，这一部分在OS中完成。

总结

我们了解了硬盘是如何工作的。

38. RAIDS

我们希望中的硬盘：快速，容量大，可靠。而RAID就是通过让多块硬盘共同工作，来完成这个任务的。

个人觉得raid这一章，其实是完全没必要写在操作系统中的，因为大部分人接触不到这个技术，需要的时候再拿出来翻翻看即可。

RAID接口

当文件系统产生一个逻辑IO的请求的时候，RAID内部则必须要计算出那个硬盘来完成这个request。raid其实甚至可以说是一个小型的系统，有CPU，有内存还有磁盘。

错误模型

raid被设计用来从错误中恢复，所以知道错误模型很有帮助。

第一种模型叫做fail-stop，磁盘要么是工作的，要么的坏的。而一旦坏了则是很容易检测到的。

剩下的模型等下介绍。

如何评估raid

我们从三个角度来陪你一股股，第一个是capacity，第二个是reliability，最后一个是performance。在接下来的内容中，我们认为一个block的大小是4K。

RAID0：striping

这其实压根不算是raid，因为根本没有redundancy。简单来说就是把多个硬盘合并成一个。把每个块按照磁盘分，比如0，4，8分给磁盘1，1，5，9分给磁盘2，以此类推。这个的好处是最大限度提高并行性。

RAID1：复制

在读取的时候可以任选其中一部分，但是写入的时候需要两个都写。

显然，从容量的角度来说，只有所有硬盘总和的一半（甚至更低，如果复制的多的话）。性能方面，读取性能和单硬盘的速度是一样的，在写入方面由于是并行写入的，所以速度也差不到哪里去，但是会略有下降（因为是取两者中比较差的那个）。

在多个硬盘中写入会遇到一个问题：内容更新不一致的问题，我们希望写入到两个硬盘中是原子性的，有一种办法能够解决：使用write-ahead log。

剩下的跳过

实际中暂时真的用不上。

39. Interlude: Files and Directories

操作系统如何操作这些可持久化设备，具体的API是什么呢，如何实现呢？

文件和目录

两个抽象：file和directory。

file其实就是一个字节数组，每个文件都有一个low-level name（不是文件名，而是inode number），directory其实和文件一样，也有low-level name（不是目录名字，而是inode number），只不过它里面的内容就是一堆（文件名-inode number）的pair，这样就可以堆砌出一棵树，树的根就是/，

创建文件

通过open这个系统调用就可以创建一个文件，该函数返回一个文件标识符，对于每个进程来说，唯一的一个整数。文件标识符是由操作系统来管理的，每个进程都有一个文件标识符的数组，标识了每个打开的文件。

读写文件

系统中读取一个文件最简单的命令应该就是cat了，然后我们还可以用strace来追踪命令执行过程中使用的系统调用并展示在屏幕上，所以可以用strace cat 文件：

这里只截取了部分重要的内容，可以看到首先最重要的是打开文件（只读模式），并且返回了文件描述符3。因为每个进程都有三个默认已经打开的文件，分别是标准输入0，标准输出1和标准错误2，所以只能从3开始了（大多数情况下是3）。

然后打开文件之后就可以用read读取了，可以看到第一个参数是3，就是用来指代那个文件，第二个参数指向了一个缓冲区buffer，该缓冲区用来存放结果，第三个是缓冲区的长度，上图中是128KB，返回值是6，说明真正的长度是6字节。

然后就是往文件描述符1写入内容，也就是在屏幕上打印。

然后紧接着又是一个读取，但是因为已经读完了，所以返回了0。最后就是关闭文件了。

不顺序读写

之前学习了如何把一个文件从头读到尾，这一部分学习读取文件的一部分。用到了另外一个系统调用——lseek。

1

off_t lseek(int fildes, off_t offset, int whence);

第一个参数是文件描述符，第二个是偏移量，第三个指明了offset的含义：从头开始计算，从当前开始计算还是从尾开始计算。

从上面也不难推论出，对于进程打开的每个文件，操作系统都知道当前的位置，而lseek则是用来改变这个位置的系统调用。下面是操作系统对于文件的抽象：

1
2
3
4
5
6
7

struct file {
    int ref;
    char readable;
    char writable;
    struct inode *ip;
    uint off;
};

操作系统对于每个打开的文件（不管是不是同一个文件）都维护了一个结构，所以如果同时打开了一个文件两次，那么会有两个文件描述符，虽然都是指向相同的文件，但是offset是独立的。

同时操作系统整体维护了一个叫open file table的东西，其实就是file的数组，这东西可不是进程独享的，而是整个系统共享的。进程持有一个file数组，是该进程打开的文件描述符的集合，而操作系统则有open file table，是整个操作系统打开的文件描述符的集合。这两个数组都允许有相同的文件，即一个文件可以打开多次，在数组中创建多个。

fork和dup

之前说了，每个进程打开的文件都是各自独立的。那么当使用fork来创建子进程的时候呢？

仔细观察上面的file结构体，可以发现还有一个ref，说明有多少个引用。如果真的是进程之间完全独立，那么根本就不需要这个整数了。所以在父子进程之间，这个文件是共享的，而这是非常有用的。

除了fork之外，还有一个调用是dup，这个调用接受一个文件标识符作为参数，并且返回一个文件标识符。

系统调用——fsync

通常我们使用了write系统调用之后，操作系统为了效率考虑，不是马上写到硬盘上去，而是写到内存的一个buffer里去，然后过一会再写回到磁盘中。当使用fsync的时候就可以强行把数据写入到磁盘中。

然而事实上，你可能还需要把该文件对应的目录也强行刷一遍。

文件重命名

在Linux中，如果希望重命名一个文件，用的是mv指令‘；而mv指令底层用的是rename这一系统调用。这个系统调用很有意思，它（通常）是原子性的。

获取关于文件的信息

除了访问文件，我们希望文件系统能够存储关于文件的一些信息，即metadata，为了访问这些metadata，我们可以使用stat系统调用。而这些信息其实就是存储在inode中的。

删除文件

本质上是unlink系统调用，为什么不用delete或者是别的代表删除的词汇呢？这里可以暂且先放一放，看完后面的目录之后再决定。

创建目录

在Linux中，万物皆文件。但是目录也算是一个特殊的文件了，因为你不能直接在目录中写。这是因为需要保证目录数据的完整性，所以你不能直接修改目录的数据，只能通过间接的创建文件等方式来修改。

如果要创建目录，可以用mkdir命令，这同时也是一个系统调用，当一个目录创建完成之后，默认有两个目录，分别是.和..

读取目录

读取目录其实用的就是ls，和文件不同，读取目录的过程有三个系统调用，opendir，readdir和closedir。

下面是通过这三个系统调用实现的一个简易版ls：

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

#include <sys/types.h>  
#include <dirent.h>
#include <stdio.h>
#include <assert.h>
int main(int argc, char *argv[])
{
    DIR *dp = opendir(".");
    assert(dp != NULL);
    struct dirent *d;
    while ((d = readdir(dp)) != NULL)
    {
        printf("%lu %s\n", (unsigned long)d->d_ino, d->d_name);
    }
    closedir(dp);
    return 0;
}

删除目录

系统调用rmdir（Linux命令同名），这个调用必须确保目录是空的（只有.和..）才可以。

硬链接

现在我们来解决上面的问题，为什么删除是unlink呢。link的本质上其实就是创建对文件的一个引用而已。该引用具有和源文件相同的inode。

我们在创建文件的时候，其实做了两件事：首先是创建了一个inode，这个inode会存储文件的信息，包括大小，在磁盘中的block等等。其次就是把文件的名字link到文件，并且放到目录中。

如果只是link（系统命令ln）到一个文件的话，那么其实本质上只是在目录创建了一条inode和文件名的对应关系，同时对应的inode上面增加一个引用计数，几次而已。

当系统执行unlink的时候，会通过reference count来确认有多少个引用。它当然会断开指定的文件名和inode之间的联系，同时吧reference count减一，如果减完之后发现是0了，那么就会去硬盘中释放对应的Block的内容，此时真正把文件删除。

符号链接

硬链接不可以创建目录的复制（怕成环，比如一个子目录是祖父目录的硬链接，这样你可以永远cd下去，像du这类的统计磁盘空间的程序就会出问题，因为它会一直循环下去），不可以跨越文件系统（inode本身只在同一个文件系统中独一无二）。硬链接的本质，其实就是创建了一个文件名到inode的关系而已。

软链接的本质，其实是一个文件的绝对路径，通过它你可以找到真实的文件，所以路径越长，软连接的大小就越大。

Permission Bits And Access Control Lists

文件系统也抽象了磁盘，就如之前所述的文件和目录。但是和之前的CPU内存抽象不同，文件和目录是共享的，所以需要有一种机制来保护这些共享资源。

第一种就是permission bits，这块Linux都讲烂了，所以跳过先。这里稍微留意的就是：对于目录的执行权限，就是你能不能进入目录的意思。

对于目录来说，还有一个叫access control list (ACL)的东西。简单点说就是谁可以访问，谁不可以访问。

挂载文件系统

假设我们现在手头上有一个硬盘，然后需要写入文件系统，那么就需要使用mkfs命令，就可以写入文件系统了。

但是，一旦文件系统创建了，我们需要做的就是访问它，通过一棵统一的文件树来进行访问。通过mount系统调用可以完成，简单来讲就是把一个目标的挂载点，粘贴到原有的统一的文件树中。

我为什么需要挂载呢？我直接访问/dev/sda1不行吗？

不行，因为你不知道内容的格式，你必须指定相应的文件系统，才可以进行读取和写入。

总结

虽然这部分内容多又杂，但是细读一遍收获颇丰。

家庭作业

1. 自己实现一个stat：

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

   #include <stdio.h> #include <sys/stat.h> int main(int argc, char const *argv[], char *envp[]) { struct stat mystat; if (argc != 2) { fprintf(stderr, "Usage: %s <pathname>\n", argv[0]); return -1; } if (stat(argv[1], &mystat) == -1) { perror("fatal error"); } printf("inode = %ld\n", (long)mystat.st_ino); printf("link = %d\n",mystat.st_nlink); return 0; }

   就是通过一个系统调用把数据放到结构体里面，然后读取结构体里面的内容就可以知道对应的内容了，剩下的部分就。

2. 实现ls，并且实现对应的参数-l。其实这里主要是使用getopt这个函数来获取命令行参数，并且利用课上的demo进行扩写。

3. 实现tail命令。主要熟练使用lseek这个函数。

4. 实现一个递归的东西。

40. File System Implementation

在这一部分，我们实现一个简单的文件系统——vsfs (the Very Simple File System)。

思考方式

我们从两个方面来思考，首先是文件系统的数据结构。应该使用什么样的数据结构来组织数据和metadata。其次就是文件系统的访问方式，怎么把这些系统调用映射到这个数据结构呢？

整体思考

首先我们需要把硬盘分成blocks，那既然是一个简单的系统，我们就只用一种大小：4K（在我的Mac上和ubuntu上，默认的页大小也正好是4K，这样刚好一一对应）。有了block之后，我们需要知道我们在里面写些什么呢？用户的数据呗，这是自然的。我们把这部分称为data region。文件系统自然还要能够追踪这些用户数据，这部分信息叫做metadata，为了能够保存这些信息，我们需要一种叫inode的数据结构。我们把所有的inodes放到一起存放，并且放在一起叫做inode table。

现在有了用户数据存储区和一个inode table，之后我们需要一个数据结构来追踪，哪些数据存储区是空着的，哪些inode是可以使用的，这部分的数据结构的选择有很多，为了间接性，我们选择了bitmap，一个bitmap对应数据区，另外一个对应inode。

最后还需要一块superblock，来记录整个文件系统的信息。所以当挂载一个文件系统的时候，只需要读取它的superblock，就可以知道一些关键参数，并执行相对应的操作。

下面是一个简单的示意图：

Inode

inode其实是index node的缩写，每一个inode都有一个数字，叫做i-number。在文件系统中，只要给定一个i-number，就可以直接计算出inode位于硬盘的哪个位置。

上图是ext2文件系统的inode内容。这其中最重要的就是就是如何通过inode来找到数据块。最简单的实现就是在里面保存指针，指向真正的block，但是如果这么做，你的文件就不能很大了。

多层index

为了支持更大的文件，我们可以通过层次目录结构来解决。使用 indirect pointer，我不直接指向data block，而是指向另外一个block，这个block里面存放了很多直接pointer。

除了这个方法，还可以使用extents，即我只需要指定数据文件是从哪里开始的，长度多少就可以指定了，缺点么就是文件内容它必须在硬盘中是连续的。

甚至你还可以让data block组成一个链表。当然如果直接去遍历链表，效率是非常低的。于是在操作系统内存中有一个hashtable，key是数据块的地址，值则是下一个数据块的地址。这个思想就是著名的file allocation table（FAT）文件系统——Windows早期的文件系统。

目录组织

在目录中，就是一些pairs，每一个pair里面是文件名和Inode号。假设一个目录下有3个文件（不包含默认的两个），那么data block可能就长这样：

为什么需要reclen呢？因为当删除目录中的文件的时候，下一次可能会有新的文件到来，此时就需要这个字段。

空闲空间管理

之前提到过用到了两个bitmap，分别用来管理inode和data block。由于空闲空间是要分配给新的文件的，而顺序读取的速度远快于随机读取，所以最好能保证连续性。

访问路径

首先我们假设superblock已经放到内存里面了，其余的则全部还在硬盘里。

读文件

现在你要读取一个文件，第一步首先是找到它并且打开它。所以操作系统首先要找到对应的inode，然而目前只有superblock和文件的路径信息。所以不得不进行遍历。

所有的遍历肯定是从根路径开始的。我们如果要找到inode，必须先找到inumber，根据inumber可以直接计算出inode。但是这里有个循环的问题了，inumber需要首先找到它的父目录，父目录中才有对应的信息，但是根路径的父目录是谁？根路径没有父目录。所以在大多数系统中都规定了，根目录的inode是2。通过计算即可知道，inode是磁盘中的第一个inode block，所以去读取内容。

通过读取inode的内容，可以知道data block在哪里；通过读取data block，就可以知道里面存储了哪些文件以及文件的inode，然后就可以递归了查找了。

最终能够找到指定的文件，并且通过open系统调用把它的内容读取进内存中。然后文件系统还需要给这个进程分配一个文件描述符。有了文件描述符，就可以进行接下来的各项操作了。

写文件

首先文件必须被打开，这个过程上面有了，不在赘述。在写文件的时候，需要一个决定应该写到哪个block里面。所以写IO很麻烦：需要更新两个bitmap，需要读取和重写inode，还需要重写数据块。

如果是新建文件，除了上面的修改，还需要到对应的目录中进行修改。所以肯定需要有相应的优化措施。

Caching and Buffering

缓存和缓冲可以有效解决这些问题。

从上面的例子我们不难发现，访问任何一个文件都是从根目录下开始找的。早期的系统使用固定大小的cache来保存常用的Block，这部分大概会占用大约10%的内存。

现代的操作系统用的则是dynamic partitioning，把内存的虚拟页面和磁盘文件系统的block集成到统一的page cache中。这样就有了更大灵活性。

如果是写文件，那么使用的是write buffering，通首先，过延时，可以把一些工作聚集在一起做。其次，系统可以决定什么时候执行IO，得到最高的性能。最后，没准可以抵消（创建了文件但是转念一想不对又删除了）。

数据库系统除外，它们对数据正确性要求极高，所以一般就直接写到硬盘里了，甚至都不使用操作系统提供的文件系统，而是直接使用物理磁盘的接口。

总结

在这一章里我们见识了如何实现一个文件系统。

41. Locality and The Fast File System

结合上一章的vsfs，我们不难得出硬盘上的数据结构是这个样子的（漏掉了两个Bitmap）：

问题：性能低下

早期的操作系统把硬盘当成随机存取的设备使用，数据散落在磁盘各个角落，导致其性能极其低下，当然这个可以通过磁盘碎片整理工具来解决。另外一个问题是早期的block太小了，只有512字节。

柱面

首先我们来改善磁盘对应的数据结构。把磁盘分成柱面，然后把几个连续的柱面合成一个组。这些细节对于操作系统来说是透明的。在操作系统上，是把一个一个block组成 block groups。也就是物理上实际是柱面组，但是逻辑上是一个一个块组。逻辑上，我们只需要把两个文件放到同一个组（物理上就是放到同一个柱面组）里，就可以快速读取了。其中每个组的结构是这样的：

每个组都有一个superblock的拷贝。通过分组，可以有效降低整体的负担。

策略：如何安放文件和目录

我们可以把相关的东西放在一起，不相关的东西分开放。那么问题来了，什么是相关的，什么是不相关的呢？

首先放置的是目录，用一个简单的方法：找到一个柱面组，目录分配的少并且inode空闲的数量多。

然后放置的是文件，文件又分成两部分，首先操作系统确保一个文件的所有data block都放到一个柱面组里，其次是把同一个目录下的文件都放在一个柱面组里。

Measuring File Locality

大部分的文件彼此之间的距离都比较近。

大文件除外

大文件并不受上面的策略影响，它会分散放置在各个group里面。

总结

这一部分主要介绍了对原来操作系统缓慢的文件系统的改进。

42. Crash Consistency: FSCK and Journaling

如何对抗系统崩溃或者突然断电等问题是硬盘需要解决的。

一个具体的例子

为了简单起见，我们现在假设要往一个文件里追加一些内容，那么需要修改磁盘中的三个部分：Inode部分，data的bitmap部分和data block部分。那么会有什么情况发生呢？

• 只更新了data block。因为inode里面没记录，同时data bitmap也没有，所以更新的data block跟没写入是一样的。
• 只更新了inode。由于data block里没有数据，所以读到的是垃圾数据。而且更为严重的是，inode显示可以读取，但是bitmap里面对应的Block却是空的。
• 只更新了bitmap。这样会造成space leak，因为这块空间在inode里面没有记录，永远也释放不了了。
• 同时更新了inode和bitmap。造成垃圾数据的问题。
• 同时更新了inode和data block。冲突问题。
• 同时更新了bitmap和data block。没有inode的内容就没有文件使用，更新了也白更新。

我们希望文件系统保持一致性，但是断电随时可能会发生。我们把这个不一致的问题称为crash-consistency problem。

解决办法1：文件系统checker

早期系统允许上面的情况发生，并且尝试去修复它——fsck。当然你并不能期望它能够解决垃圾数据的问题，它需要在文件系统挂载之前就运行，具体有这些步骤：

• 首先确认一下superblocks。
• 接下来扫描inodes等，对系统里block的分配情况有一个了解。然后根据扫描结果，fsck自动构造出一个bitmap，然后与原来的bitmap进行比较。
• 详细确认每一个inode的情况
• 检查link数量。如果发现一个inode没有被任何目录使用，那么就把它放到lost+found目录中。
• 越界block等检查。
• 其它检查等。

这个命令非常非常的慢，虽然有用但是…太慢了。

解决办法2：Write-Ahead Logging

write-ahead logging，aka journaling，这个办法是从数据库那里“偷”过来的。现在，Linux中的ext3 ext4和Windows的NTFS都是用的这个想法。

核心思想是，在动手更新之前，首先先记录好，然后再开始做。

现在假设我们又想写文件了，还是原来的配方。那我们首先把我们要更新的三个部分写到日志里。日志一共有五个部分，除了要更新的这三个部分（注意，这三个部分是物理日志，即这三个块的内容和最后要到对应位置上面的是完完全全一模一样的）外，还有一个事务头（包含了ID等信息）和事务的尾巴（同样包含了ID等信息）。只要这个事务成功写入了日志（日志也在磁盘上），那么就可以把这些数据真正写到磁盘中对应的位置去了。这个对应的进程叫checkpointing。

当然，在你写入日志文件的时候，也可能发生断电，所以为了保护，文件系统会保证，只有当数据齐全之后，才会加上事务的尾巴。即最后的过程是这个样子的：

1. 将事务的内容，包括事务的头部块和内容部分写入到日志中
2. 将事务的提交块（最后的那一块）写入，写入完成则事务提交
3. 将真正的块写入到磁盘真正的位置。

恢复

如果断电发生在事务还没提交之前，那么就直接无视。

如果发生在事务已经提交，但是还没有写入到硬盘，那么就需要重新再做一次，所以相应的日志就叫做redo logging。

这里仅仅解决了数据冲突的问题，并不能解决数据丢失的问题，事实上，（在极端情况下）没有任何设备可以保证数据的不丢失，除非每次你都愿意等待真正落盘之后才通知你完成。

聚合在一起

显然如果真的每次都先写日志，然后真正写入数据的话，那么会导致磁盘读取写入过于频繁，所以可以使用缓冲技术，把所有的都缓冲到一个事务中去。

元数据日志

根据上面的描述，其实我们在日志中写入的是所有的数据部分，而这种日志叫做数据日志，data journaling，常见的如Linux的ext3系统就是数据日志。但是我们真的有必要把所有的数据写入到日志的磁盘中吗？其实只需要修改下顺序，就可以不用把额外的数据块写入到日志中：

1. 把数据写入到磁盘的最终位置
2. 把事务的开始块、元数据写入到日志中
3. 把事务的结束块（也叫提交块）写入到日志，提交事务。这一步开始前要确保前面的1和2完成，而1和2谁先开始、谁先完成并不重要。
4. 把元数据写入到文件系统的最终位置处。
5. 释放空间。

总结

这一章介绍了通过fsck来保证数据的一致性，但是由于这个检查的太慢，所以一般不采用；然后介绍了基于日志的方法，其中一种叫数据日志。它要把数据写入到日志系统中，另外一种是只需要写元数据就可以了。

我个人的理解：数据日志的感觉就是我先把数据写入到日志系统里面，相当于有了一个备份，有了备份然后再去真正的磁盘处进行写入。而元数据日志则是把数据写入这一部分去掉了，所以可以提升效率。

43. Log-structured File Systems

在前面的学习中，一共提出了两种文件系统，一种是VSFS，就是用来讲述文件系统基本概念的；还有一种是上面提到的FFS，然而FFS仅仅是把在同一个目录下的数据放在一个柱面上进行保存而已。

然后在上一章中提到，为了能够在磁盘崩溃的时候保证一致性，需要有对应的措施。

而在这一章里面，则是学习一个更加现代化，表现更加优异的文件系统——LFS。

LFS的设计人员发现，内存越来越大，而且磁盘中写入的性能成为了其瓶颈，因此迫切需要把日常的一些写入工作变成是顺序写入的以提高性能。

按序写入磁盘

之前讲到VSFS的时候，提到了文件系统必须要有三部分（忽略超级块）：inode和数据的空闲列表（位图）、inode部分和数据部分，而这三个部分在VSFS中，是固定在指定位置的，也正是因为固定在了指定位置，所以才导致了写入速度极其不佳（因为不是顺序写入），而LFS的核心就在于，它把所有的inode和数据块更新顺序写到磁盘上，这样就变成了顺序写入。

如何查找inode

现在inode并不是在硬盘的指定位置了，也就是之前的通过Inode直接计算出inode磁盘地址的方法失效了。

LFS通过使用一种叫做imap的数据结构解决这一问题，即只要有imap，那输入给imap一个inode，就可以得到对应的inode磁盘块的地址。

那问题又来了，imap应该放在磁盘的哪里？如果imap放在磁盘的指定位置，那又回到和最原始的文件系统一样的想法了，所以imap其实是保存在对应的inode的旁边的。

所以其实这是一个永无止境的问题，如果希望 跳出这个循环，那必然需要在磁盘的固定位置处进行存放，才可以打破这个僵局。

检查点

LFS在磁盘上确实有这么一个区域（磁盘的开头），叫做检查点区域（checkpoint region），通过它可以知道最新的imap。而这个检查点更新时间特别久，所以性能影响很小。

LFS读取文件

第一步，必然是从检查点区域读取数据放到内存中，然后就可以获得imap数据，也放到内存中。这样给定每一个inode，都可以直接获取到inode对应的磁盘地址，有了磁盘地址，接下来就一切好说了。

垃圾收集

LFS需要对时时刻刻把新数据和新的inode更新到磁盘中，所以旧的一部分数据就免不了成为了垃圾。

LFS清理是按照段进行清理的。它在清理的时候会读取旧的段，然后把旧的段和新的段进行整合，然后释放空间，把新的段写入到磁盘中。

确定块死活

每个段的头部都会有一个摘要，记录了该段中每个数据块的inode号和偏移量（即这个数据块是文件的哪一部分）。

这样只要有了摘要，就知道了该数据块属于文件的哪一部分。此时LFS只需要去imap里面根据对应的inode就可以找到这个文件的所有数据块，然后根据偏移量可以知道这个当前在段中的这个数据块，是不是inode里面指向的那个数据块。如果是则说明还有效，否则就死亡。

当然还有一些特殊的优化，比如利用版本号。当删除一个文件的时候，直接版本号加一，简单的通过版本号的检查，可以避免上面冗长的检查。

44. SSD

45. Data Integrity and Protection

虚拟机

这并不属于

26. Concurrency: An Introduction

我们之前学过的内容，是如何把单个CPU抽象化成多个。

在这一部分，我们介绍一种新的抽象：thread。多线程程序有多余一个以上的执行点，每个线程其实就是分开的进程，只不过有一个不同：线程之间共享address space，所以它们可以共享数据。

线程的状态和进程也非常像，它也有一个程序计数器，每个线程也有自己的寄存器。所以如果线程进行切换，也是有context switch发生的。之前进程的上下文切换，会把状态保存在**process control block (PCB)，而线程则是会放到thread control blocks (TCBs)**里面。当然在线程的context switch之间，address space是不会变的，也就是完全用不到页表切换，所以我们说线程切换比较廉价。

另外一个不同的是栈的不同。之前的单线程进程是只有一个栈的，而在多线程进程中有，每个线程都有一个栈，这些栈就叫做 thread-local。

为什么使用线程？

两个主要的原因，第一个是parallelism并行性，如果有多于一个CPU，那么如果进程只有一个线程，多CPU就发挥不出功效。第二个原因是可以有效避免进程被IO阻塞，一个线程被阻塞了，可以让另外一个线程执行。

当然上面的这些，都可以通过多进程来实现，然而线程因为天然共享地址空间，所以在共享数据方面有优势。

线程创建的例子

线程一旦创建完毕，可以由调度器来决定线程上面时候执行。所以除非用特定的操作，否则线程的执行顺序是不一定的，这一切都是由OS scheduler来完成的。

共享数据问题

假设有一个共享的变量x，有多个线程希望去同时修改它，最后的结果大概率是不会如你所愿的。

问题的关键

• race condition：多个线程想要同时进到critical section里面并且进行修改共享数据。
• 同时可以导致race condition的代码叫critical section：这部分的代码会访问共享的资源，而且不能同时运行多个线程。
• 一个indeterminate程序包含一个或者多个race condition，程序的结果不确定。
• 我们真正希望的是这段代码是mutual exclusion，即当一个线程正在critical section的时候，另外所有的线程都无法进入。

原子性

一个有效的解决办法就是原子性，如果有一个指令能够把多条指令合并在一起，之前的问题就不会发生了，然而实际中出于效率原因，我们并没有这样子的指令。

我们要求硬件提供的是一种叫synchronization primitives同步原语的东西，再加上操作系统的帮助，我们就可以得到我们想要的。

还有一个问题：等待另一个

除了上面提到的对于共享资源的访问，还有一个问题就是有些时候，一个线程必须等待另外一个线程完成，这个应该怎么办呢？

为什么是操作系统来解决？

因为操作系统本身就是一个concurrent程序。

家庭作业

1. dx在这里的作用显然就是一个计数器。
2. 显然不可能会有竞态条件，都是运行三次。
3. 是，在两个线程之间频繁切换了。
4. 运行程序，确保你理解了这个程序。
5. 其余省略。

27. Interlude: Thread API

如何创建并且操作线程呢？

线程创建

pthread_create函数，有四个参数：

• pthread_t *thread：用来指定你的创建的线程
• pthread_attr_t *attr：指定这个线程的属性，可以在这里设定栈的大小或者优先级什么的，当然最常见的还是NULL，因为默认的就足够好用了。
• void *(*start_routine)(void*)：类似于java中的run函数，在C语言里面就是执行哪一段代码。
• void *arg：上面的函数的参数。

等待另一个线程完成

直接调用pthread_join()，传入两个参数，分别是要等待哪个线程，第二个参数是你希望线程给你返回什么，比如线程A希望线程B去做一些事，所以肯定要B的返回结果。

锁

1
2

int pthread_mutex_lock(pthread_mutex_t *mutex); 
int pthread_mutex_unlock(pthread_mutex_t *mutex);

当你的线程有critical section的时候，需要确保正确性的时候，就可以用锁了，用法非常简单：

1
2
3
4

pthread_mutex_t lock;
pthread_mutex_lock(&lock);
x = x + 1; // or whatever your critical section is 
pthread_mutex_unlock(&lock);

如果线程得到了锁，就会从第二句返回，否则就会一直卡在第二句。当然上面的代码其实是错误的，因为首先这个锁并没有被初始化，可以通过静态初始化或者运行时初始化；其次是它没有错误检查。

除此之外，还有两个函数：

1
2

int pthread_mutex_trylock(pthread_mutex_t *mutex); 
int pthread_mutex_timedlock(pthread_mutex_t *mutex,struct timespec *abs_timeout);

第一个函数是尝试一次，如果能得到就得，得不到就立刻返回。第二个函数可以指定时间，如果超时了且还没获得锁就返回。这两个函数尽量少用（为什么？）

Condition Variables条件变量

1
2

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); 
int pthread_cond_signal(pthread_cond_t *cond);

如果要使用条件变量，那还需要一个相关的锁。第一个是让线程去睡眠，等待另外的线程叫醒它，第二个就是叫醒相关的条件变量的线程。这里有几点需要注意：当你去叫醒别的线程的时候，必须确保你有锁，这样不会让两个线程进入条件竞争。当你去睡眠的时候，必须释放锁；当醒来之前，必须取回锁。

尤其是wait这个函数，非常有意思。它会主动放弃这个锁，然后去睡眠。当别的线程唤醒对应的条件的时候，wait这个函数在返回之前，又能够重新拿到这把锁。也就是当这个函数返回的时候，它又拿到了锁。

总结

我们介绍了如何创建线程，如果使用互斥量（mutex）以及如何通过条件变量来进行线程的等待和唤醒。

28. Locks

之前说了只要原子性代码就不会有问题，但是没有这样的银弹，所以需要用lock机制来自己保证原子性。

基本想法

我们假设我们的critical section是这样的：balance = balance + 1;，如果要使用锁，我们只需要这样：

1
2
3
4

lock_t mutet = ...		// 初始化
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

上面的代码看上去简洁，注意的是当一个线程得到锁了，其它线程就会在得到锁的那一句卡住，直到锁被释放。锁被释放的时候，可以是线程自己注意到（通常通过循环）锁被释放了，也可以是被通知了。

Pthread Locks

POSIX库用的互斥量的名字叫mutex，用来提供线程之间的互斥。

制作一个锁

从程序员的角度来说，理解锁是非常简单的，但是底层呢？硬件方面是如何支持的，操作系统是如何支持的呢？

评估锁

在正式开始之前，我们需要明白我们的目标是什么，以及我们需要知道我们要如何评估锁的实现呢？

首先，锁必须要能够完成它最基本的功能——提供互斥。

其次是公平性，不能让某些线程处于饥饿状态。

最后一个是性能，因为有了锁肯定性能会下降。我们比较无锁状态，单CPU状态和多CPU状态下的锁的表现。

控制中断

最早的实现互斥的是通过关闭中断来完成的。

在我们进入critical section之前，我们确保中断关闭，也就意味着我们进入到critical section中的时候不会发生线程的切换，那么自然就是原子性的。当我们从critical section出来的时候需要再次打开中断。中断的关闭和打开都是通过物理的指令来完成的。

这种方法的优点就是简单，缺点却是一大堆：首先打开中断和关闭中断需要特权操作，这需要对线程的充分信任。一旦程序执行死循环，那么只有重启系统才可以了。其次，这个方法对多处理器无效。因为你只关闭了当前线程所在的CPU的中断，另外一个CPU上面的线程照样可以访问。再有，关闭中断可能导致一些丢失问题，比如恰好一个IO完成了，但是现在中断是关闭的。最后也是最不重要的，这个方法效率很低，因为开关中断的指令CPU执行的很慢。

所以综上所述，也只有操作系统在执行自己的代码的时候（自己当然信任自己啦）会使用这个方法。

A Failed Attempt: Just Using Loads/Stores

我们可以有一个简单的想法，通过使用一个变量来控制。还别说，我当时初次接触的时候真的是这么想的。显然这个方法是错误的……因为可以同时两个线程都进入到critical section里面。其次是性能也贼低，因为不停在循环中浪费时间。当然有大佬通过两个变量真的做到了，但是意义不大….因为现在都是硬件支持了。

使用Test-And-Set来解决问题

早期的多处理器系统中提供了这么一条指令（目前就算是单处理器也提供了）：test-and-set (也叫 atomic exchange），思路很简单，就是把原来旧的值old_value替换成新的值，并且返回旧的值，就像下面的函数所示的一样：

1
2
3
4
5

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // fetch old value at old_ptr 
    *old_ptr = new; // store ’new’ into old_ptr 
    return old; // return the old value
}

最最与众不同的是，这个“函数”它本身是原子性的。

然后就可以构造出spin lock，这是最简单的锁，简单的自旋，还有一个条件是这个必须在抢占式调度器上使用，如果不抢占，那这个自旋将会永远的旋下去…

评估自旋锁

最主要的是锁的正确性：显然自旋锁满足了。第二个是公平性，自旋锁显然没有保证公平性。第三个就是性能指标，在单处理器上，性能很糟糕，因为调度器会让每个线程都跑一次，然而只有一个线程真正再跑，其它都是在虚度时间（并不会让出时间）；但是如果CPU的数量和线程数相等的话，这个性能就很不错了。

Compare-And-Swap

在一些系统中，另一条指令就是大名鼎鼎的compare-and-swap，这个提供三个参数，old，expected和new，如果old和expected相等，那么就把old设置成new，否则就不设置。最后返回最初的old的值。

根据上面的分析我们不难得到，compare-and-swap就是升级版的Test-And-Set，在将来，我们会用这条指令实现lock-free synchronization。但是目前，它的功能和test-and-set是一模一样的。

Load-Linked and Store-Conditional

在一些平台中提供了这么一对指令来帮忙：load-linked 和 store-conditional，下面是它们的C的伪代码：

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

int LoadLinked(int *ptr){
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (no update to *ptr since LoadLinked to this address) {
        *ptr = value;
        return 1;  // succcess!
    }else{
        return 0; // fail to update
    }
}

第一条指令就像load指令，就是把命令从内存中取来放到寄存器里。

第二条指令只有在没有更新的时候才能成功，并且成功更新。

注意！上面是伪代码，它们其实是指令，所以是原子性的。

Fetch-And-Add

这也是一条指令，同样的伪代码见下：

1
2
3
4
5

int FetchAndAdd(int *ptr){
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

同样可以用这条代码来完成上锁的操作。

经过这些指令，不难发现，只要一条指令中对值进行了修改，并且能够获得原来的值，就能够用来上锁。

自旋太多了

自旋是非常浪费时间的，因为除了空等，什么也做不了，那么要怎么做呢？

Yield

与其自旋浪费时间，不如直接把CPU时间让出来，yield能够让线程从running态转到ready态。但是到目前为止，我们都没有处理饥饿问题。如果运气差，一个线程是完全可能这辈子都在进行yield操作的。

sleep代替spin

为了避免饥饿问题的发生，我们需要控制哪个线程应该在锁被释放之后去得到锁。我们可以用一个队列来追踪所有等待相同锁的线程。

简单起见，我们使用两个调用，park()让线程去睡眠，unpark(threadid)让其苏醒。在java中，可以理解LockSupport.parkNanos和Thread.sleep几乎是一样的，只不过sleep会抛出异常，而park不会。

不同的操作系统不同的支持

我们可以使用这么多的命令来完成我们的锁，但是不同的操作系统支持不一样。

两阶段锁

就是结合了上面的两种，首先先自旋一会，如果不行就进入睡眠。

总结

所以锁其实就是靠的硬件（指令，且指令本身是原子性的）加上 操作系统的算法来实现的。当然大家都有各自的区别。

家庭作业

略。

29. Lock-based Concurrent Data Structures

通过对数据结构加锁，可以实现thread safe，如何加锁则成为了关键。既要能保证正确性，又要有高性能。

当然数据结构千千万，这里当然不可能全部涵盖。

并发计数器

就是最简单的用来计数的，每当当用increment方法的时候把value加一。只需要在每个操作的最开始添加锁，然后在操作结束的时候释放锁，就能保证正确性了。有一种数据结构，使用monitors构造，和它非常像，而且它的锁是自动获取自动释放的。

但是这个有一个性能问题，在单CPU上表现良好，但是到了多核中反而性能下降。

可扩展性

研究人员研究了如何去打造更加具有扩展性的计数器，其中的一个方法就是approximate counter，核心思路就是使用多个local counter，每个CPU核心对应一个，除此之外还有一个global counter。每个counter，包括global都有一个锁。

当运行的时候，每个CPU的counter都会各自更新，然后这个local的值会定期（记做时间S）传输给global（当然需要先获取锁），然后把这个global的值加上自己的值，并把自己清零。

显然如果S越短，那么性能就越低，但是能够保证global的值更加准确。这也是另外一个trade-off：accuracy/performance trade-off

并发链表

我们在这一部分仅关注链表的插入，其余的诸如查找，删除的留给自己思考。

插入操作是这样的，首先锁住链表，然后创建一个新的节点，并且利用头插法插入到链表中，最后释放锁。有一个小细节就是当malloc失败（也就是申请新节点失败）的时候，也需要释放锁。

然而这种异常处理被证明了很容易出错，因为异常的路径千千万，而我们只处理了一条。所以我们需要对其进行改进，保证其不会出错。

修改方法也很简单，只有插入链表的操作才需要进行加锁，创建节点的那部分不需要上锁。

改进

现在已经可以得到正确的并发链表了，但是扩展性不够好。研究者研究了一个叫hand-over-hand locking的东西，思路也很简单，不要一次就把整个链表给锁了，而是锁其中的一个节点。在链表中遍历的时候，首先先去把下一个节点锁了，然后释放当前的这个节点，这也是hand-over-hand的来源。

但是说是改进，其实虽然锁的粒度变小了，其实效率到底有没有提升呢？因为你每次移动节点都需要获取释放锁，其实比单个锁的链表也快不到哪里去，只是支持较高的并发性。

并发队列

当然，通过一把大锁，是可以实现的，就像上面的链表一样，所以这一部分我们就省略了。

核心思路也很简单，使用两个锁，一个锁头一个锁尾，然后和链表一样，仅仅锁住操作队列的代码，而不会去锁。除此之外队列还有一个大小，如果超过了的话，线程就需要等待，这部分的内容留到条件变量中详细介绍。

并发hashtable

这一部分我们以一个固定大小的hashtable来作为例子。emmm 其实本质上就是之前开发的一个并发链表作为底层结构。

总结

我们在这一部分介绍了一下并发的数据结构，从计数器，链表到队列，最后是哈希表。我们在这一章节学习了一个重要的原则：在控制流中记得释放锁，只锁住真正操作链表的部分，其余的都不要上锁。

30. Condition Variables

锁不是唯一的用来构件并发程序的唯一方法。在很多情况下，线程希望在执行之前检查某一个条件是否满足。在这里可以通过锁加上一个全局变量来做，但是线程就会使用自旋，这非常消耗CPU时间。

定义

为了达成上面的条件，线程可以使用一个叫condition variable（之前被叫做private semaphores）的东西，本身是一个queue，如果一个线程期望的条件不满足，就会放到这个条件变量的queue里面去，另外的线程可以通过使用对应条件变量的signal方法来唤醒队列中的线程。

条件变量本身还需要锁进行配合，当使用wait的时候，会释放锁并且去sleep，且这个操作是原子性的。当线程醒来的时候，会先去获取锁然后才从函数中返回。这是为了避免race condition。

在使用wati/signal的时候牢记这几点：必须要有一个全局的变量来控制；对全局变量的控制必须加锁；使用wait的时候请配合while使用；在执行signal和wait的时候，请确保自己有锁。

生产者消费者问题

producer/consumer problem，也被称为bounded buffer problem问题，首先由Dijkstra提出，并且之后人们在此基础上发明了semaphore，一个又可以作为锁又可以作为条件变量的东西。

生产者消费者的一个典型应用就是web server，生产者不断把http request放进来，而消费者则不断取出来并且处理。同理你在shell里使用管道符，也是一个生产者一个消费者。

首先还是从最简单的出发，我们有一个长度为1的数组和一个全局变量count。生产者的任务就是确保count是0，然后把count置成1，并且把自己的数据放到数组中。而消费者则相反。

如果仅仅是单个生产者和单个消费者，那么是很简单的，代码也能很好地运行。但是如果一个生产者多个消费者就会有问题出现了：消费者1首先因为没有资源而去睡眠了；生产者生产了资源并且通知了消费者1，消费者1成功醒来，但是CPU却被别的消费者抢走并且成功的消费，而当时间片再度回到消费者1的时候，它无法完成消费。

根本原因是，生产者只是唤醒了睡眠的消费者，但是消费者不一定能真正消费到。

改进

只需要把if改成while，即当睡眠的消费者醒来的时候，再判断一下资源到底存不存在，如果存在才去消费。这也告诉我们一个道理：有的时候反复确认总是好的，因为只要消耗极少量的资源就可以确保事情万无一失。

然而，就算把if改成了while，还是有问题的。现在假设消费者都去睡眠了，然后生产者生产好了，并且唤醒了其中一个消费者（注意只是去唤醒了一下，此时线程还没醒）。然后生产者又想继续去生产，但是它发现满了，所以去睡眠了。此时消费者才真正的苏醒，然后开开心心的消费了数据，并且需要通过条件变量来唤醒，但是！目前生产者和其中一个消费者都在睡眠呢，该唤醒谁呢？假设不小心把另一个消费者唤醒了，那个消费者醒来一看没有数据，就又去睡眠了。好了，此时三个人都睡眠了，谁也唤醒不了了。

关键就在于，消费者不应该唤醒消费者，同理生产者也不应该唤醒生产者。

简单的解决方法

使用两个条件变量就行了呀。

正确的解决方法

之前的方法已经可以保证正确性了，接下来要做的就是提高性能和并发性。只需要把之前的长度为1的数组变大就行了。

Covering Conditions

类比java中的notify，如果仅仅是notify，可能有线程应该醒来但是没有醒来，而如果使用的是notifyAll，那么就可以都醒来了。这个就是covering condition，因为它覆盖了全部的线程，缺点么就是全部的线程都会醒，而其中的大部分又会马上去睡觉。而且，这个也可以用到之前的生产者消费者的问题中，这样只需要一个条件变量就可以了。

总结

在这一章里面我们介绍了一下利用条件变量完成的wait/notify机制。

31. Semaphores

我们介绍了lock和condition variables，Edsger Dijkstra，第一个想到把两者合二为一。

定义

本质上，信号量是一个int值，我们可以通过sem_wait()和sem_post()来进行修改，而Dijkstra本人把前者称为P，后者称为V。

信号量需要初始化，而且它除了可以在同一个进程的线程之间共享，还可以在不同的进程之间共享。

sem_wait的逻辑是，把信号量减一，如果信号量是负数了就wait；sem_post的逻辑是加一，如果有一个或者多个线程在等待，那么唤醒一个。

Binary Semaphores

我们首先把信号量当成锁来用：只需要把信号量的初始值设置成1即可。

然后通过sem_wait()进入critical section，通过sem_post()来退出。

Semaphores For Ordering

在这里我们假设一个线程parent希望在子线程完成之后唤醒，那么我们应该怎么做呢？

把信号量的初始量设置成0，这样只要parent执行sem_wait()就会进入睡眠，然后子线程就会执行，当子线程执行完成之后，执行sem_post()并且唤醒parent。而且就算是子线程先执行，逻辑上也是正确的。

生产者消费者问题

初次尝试

我们使用两个信号量，empty和full，通过使用两个信号量，可以保证数组长度是1（即只能存放一个）的情况下是正确无误的。

当数组长度大于1的时候，就会有问题了。假设了两个生产者同时执行，那么就相当于这两个生产者之间没有任何的互斥，可以彼此打断对方。

解决方法：增加互斥量

修改数组的index和在其中填入数据其实是critical section，所以其实需要锁来解决。所以只需要在之前的代码中加入锁就可以了。真的吗？加入锁会出现这么一个情况：消费者先执行，所以先获得了锁，但是它消费不了，因为现在没东西让它消费，于是它只好阻塞（不释放锁）。然后生产者无法获得锁，自然无法生产数据。这样死锁就形成了。

最后解决办法

其实，只需要换一下信号量和锁的位置就可以了，也就是让加锁和解锁最贴近critical section。

读写锁

如果所有的线程仅仅是读取内容，那么甚至都不需要锁，所以我们需要一种新的机制来来支持更好的并发。

读写锁本质上也是通过信号量来完成的，获取读锁是很容易的，而获取写锁，需要等所有人的读锁释放了之后才可以。

The Dining Philosophers

哲学家就餐问题。我们假设5个哲学家，一共五把fork，然后每个哲学家需要两个fork才可以进餐。我们首先假设有5个信号量。

错误的方法

我们先把所有的信号量设置成1，那么获取fork的代码就很简单，只需要让左右边的fork都sem_wait即可。显然这个方法不行，一个最简单的反例：所有哲学家都拿起了自己左手边的fork，那么就无法获取到右手的fork——死锁就诞生了。

打破依赖

上面的问题之所以会发生，就是因为他们形成了一个环，所以我们只需要让最后一个哲学家稍微变一变：他是先拿右手边的fork，然后再拿左手边的。（这是Dijkstra解决问题的方法）

线程限制

另外一个信号量的作用就是限制线程的数量。

如何实现信号量

我们就用mutex和condition variables来完成信号量吧——一个结构体，里面有一个value（就是信号量的值），还有一个锁和一个条件变量。

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

void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while (s->value <= 0)
        Cond_wait(&s->cond, s->value--;
    Mutex_unlock(&s->lock);
}
void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

总结

信号量简单且使用，有了它我个人觉得完全就不需要锁和条件变量了。

在一章里面我们学习了一些案例和一些解决办法。

32. Common Concurrency Problems

并发中最常见的问题，应该就是死锁问题了吧。除了死锁，这一章我们还将学习并发下遇到的问题。

问题的类型

引用了一篇文章，该文章的作者分析了四个有名的软件并且找到了它们在并发下的问题。这四个软件分别是Mysql、Apache、Mozilla和OpenOffice。

非死锁BUG

这部分主要有两类，一类是atomicity violation的bug和order violation的bug。

Atomicity Violation Bug

违反原子性的bug。

1
2
3
4
5
6
7

// thread 1:
if(a){
    fputs(a,....);
}

// thread 2:
a = NULL;

第一个线程判断a是不是NULL，如果不是则进行操作，而第二个线程把a改成了NULL。

显然，如果第一个线程成功通过了if判断，然后恰好发生时间片中断，此时到了第二个线程，然后第二个线程把a改成了null，当再次回到第一个线程的时候，由于此时a已经是Null了，所以就会出现问题。如果使用的语言是java，那就是空指针异常。

解决方法也是相当简单，只需要都加锁和解锁就可以了。

Order-Violation Bugs

1
2
3
4
5
6
7
8
9

// thread 1:
void init(){
    mThread = createThread(mMain,...);
}

// thread 2:
void mMain(){
    mState = mThread->State;
}

在线程2里面的代码，需要mThread为非空才可以。然而如果线程2在创建完成之后立马运行，那么可能会导致mThread目前还是空的，这样也会导致空指针异常。

为了保证有序性，即必须先执行线程1，然后再执行线程2才能保证不出现问题，那只需要用到条件变量即可。

非死锁bug总结

大部分的bug都是属于上面那两种的，所以我们需要尽量避免这种问题。当然现在有一堆工具可以检测这些问题，但是修复起来就不是那么容易了。

死锁bug

死锁为什么会发生呢？

首先是系统太复杂了，其次是封装，由于封装我们并不了解所有的内容，所以会发生问题。

死锁的四个条件

• Mutual exclusion：线程声明了对资源的独占控制，锁就是最典型的例子。
• Hold-and-wait：线程持有分配给它的资源，并且等待额外的资源。
• No preemption：资源一旦分配给线程，就无法强制剥夺。
• Circular wait：形成了一个环。

只要这四个条件中有一个不满足，死锁就不会发生。

避免死锁

Circular wait

最常用也是最有用的方法，就是你写代码永远不要有Circular wait，最直白的方法就是提供一个锁获取的顺序，然后根据锁的顺序来写代码。

当然在复杂系统中这么做可能不是很合适，所以我们需要有partial ordering。一个简单的方法就是，通过判断两个锁在内存中的地址，比如你可以规定低地址的锁优先，只要你一直保持这么干，就可以确保避免死锁。

Hold-and-wait

这个可以通过一把全局锁来避免，即所有的线程都先去争抢一把锁，然后抢到了之后再去申请别的锁。 首先获取一把锁，保证在获取所有锁的过程中不会被中断。

该技术对性能的影响大，所以不推荐使用。

No Preemption

这部分最主要的原因就是只有当unlock执行的时候，锁才会被释放。很多库都提供了这么一个函数，pthread mutex trylock()，要么获取到锁，要么直接失败返回。所以我们可以去尝试一下获取别的锁，如果失败了，那么可以把自己的锁也释放掉，这样可以避免死锁。

但是在这种情况下会出现一种叫livelock活锁的东西，就是两个线程都首先获取一把锁，然后尝试去获取对方的锁，结果发现失败了，那么就释放自己的锁，不断的重复。避免活锁最简单的方法就是为线程加一个随机的延时。

Mutual Exclusion

这一部分其实并不可避免，因为我们的程序必然是有critical section的。所以我们只能不加锁，那么就只剩下乐观锁这么一条路了。

通过计划避免死锁

最好能够避免死锁，而不是防止死锁。我们要做的就是根据各个线程获取锁的情况来判断。其中一个著名的算法就是银行家算法。但是这个算法大部分只有在嵌入式系统中，即知道所有任务以及知道所有的锁的情况下，才有用，所以在大型系统中，银行家算法用的并不多。

检测和恢复

最后的方法是，允许死锁偶尔出现，但是能够检测到死锁并且去处理它。

本部分没有细说怎么做，只是说数据库里用的比较多——通过构造图并且检测里面有没有回路来检测，允许死锁的发生，但是发生了之后要能够检测到它。

总结

我们学习了一些在并发情况下会出现的问题，第一种是非死锁问题，比较容易修复。第二种就是死锁，我们可以破坏它的四个条件来避免死锁；最后还通过数据库的例子简单介绍了一下死锁的检测和恢复。

33. Event-based Concurrency (Advanced)

更多的并发（以及并发带来的问题），出现在GUI中，或者是出现在互联网的那些server中，这种称之为event-based concurrency。

那么有没有办法，我们压根就不用多线程呢？只要不用多线程，这并发的问题不就解决了么？

Event Loop

思路非常简单，就是简单地等待事件发生，发生了之后你去确认下事情的类型，然后做一些工作。听上去简单，但是实现起来就没那么容易了。

系统调用——select(poll)

这个系统调用很简单，就是确认有没有传入的IO。以服务器为例子，就是检查一下有没有数据包到达，如果有的话就去进行操作。下面是select的代码：

1
2
3
4
5

int select(int nfds,
	fd_set *restrict readfds,
	fd_set *restrict writefds,
	fd_set *restrict errorfds,
	struct timeval *restrict timeout);

select会检查IO描述符的集合（就是上面的三个fd_set），来检查它们中是否有文件描述符已经准备好了。第一个数字则是用来指定数量。返回值是有多少个文件描述符已经ready了。

这个系统调用允许你检查文件描述符是否可读可写，可读相当于通知web server目前有数据包抵达了，可写则是让服务知道这已经好了。

poll系统调用和select非常像。

阻塞系统调用

如果，一个事件要求你去触发一个系统调用，而且这个系统调用可能会被阻塞呢？

一个简单的例子：客户端希望服务器去读取服务器上的文件并且返回给它，这一过程中必然有open()系统调用，然后read()系统调用。这个在多线程情况下没有所谓，但是到了这里，就会阻塞整个server了，所以在这个系统里，不能有阻塞式系统调用。

解决：异步IO

异步IO就是允许进行了IO请求之后立刻返回，并不等待结果就直接返回。一个典型的AIO的例子如下：

1
2
3
4
5
6

struct aiocb {
    int aio_fildes;
		off_t aio_offset;
    volatile void *aio_buf;
    size_t aio_nbytes;
};

这四个参数分别指定了要读取的文件标识符，要读取的偏移量，读完之后应该放到哪里，读多少个字节。

有了这个结构体，只需要进行系统调用aio_read并且把这个结构体传入即可。

那么我们怎么知道异步IO完成了呢？同样使用系统调用aio_error，同样也是传入对应的结构体，如果已经完成了那么就返回0，否则返回别的。显然如果我们要多次去确认异步IO是否完成，是很痛苦的，因为要轮询导致效率低下，所以实际中可以用信号来进行通知。

问题：State Management

在一次循环中，event handler需要打包保存程序的状态，以便接下来的event hander使用。最简单的就是使用一个hash表来记录，这样异步完成之后还能接着操作。

events还存在什么问题？

假如我们从单CPU系统扩展到了多CPU系统，那么系统会并行跑一些event handler，所以就不得不配以锁。

还有别的问题，比如缺页中断，此时操作系统不得不阻塞，那么整个系统又停下来了，虽然说了要避免显式的阻塞，但是缺页中断属于隐式阻塞。

第三个问题是，万一使用event handler处理的事务，从非阻塞变成了阻塞，你很难发现。

第四个问题是，虽然大多数系统支持异步IO，但是并不能很好的和网络IO兼容。

总结

这一部分主要是介绍了基于事件的并发，发现有很多问题，而且也不简单。

并发这一部分到这里就结束了。在这一部分，首先学习了如何创建线程，如何实现一把锁，以及如何在锁的帮助下实现一些并发的数据结构。然后通过条件变量学习了如何让一个线程等待另外一个线程，引出了经典的生产者和消费者问题。然后通过信号量，相当于串联了之前的锁和条件变量。通过实际中系统的问题引出了死锁及其解决方案，最后又拔高了一点，介绍了select这个系统调用，即不通过多线程也能完成高并发任务（虽然要求很多就是了）。