操作系统篇 A

# 并发：介绍

经典观点：一个程序只有一个执行点（一个程序计数器，存放执行的指令），那么所有的执行都是顺序执行的。但是多线程（multi-threaded）程序有多个执行点，此处区别进程，多线程程序中，线程之间共享地址空间，能够访问到相同的数据。

类比进程，当两个线程运行在一个处理器上，从运行 A 线程到运行 B 线程，一定会发生上下文切换（context switch），进程的状态保存到 PCB 中，线程的状态保存到 TCB（Thread Control Block）中。唯一与进程上下文切换不同的是，线程切换上下文，地址空间保持不变，也就是不需要切换当前使用的页表。

在并发中最经典的程序问题就是多个线程累加同一个变量：

static volatile int counter = 0;

void *

mythread(void *arg){

    printf("%s: begin\n", (char *) arg);

    int i;

    for (i = 0; i < 1e7; i++) {

    	counter = counter + 1;

    }

    printf("%s: done\n", (char *) arg);

	return NULL;

}

int

main(int argc, char *argv[]){

    pthread_t p1, p2;

    printf("main: begin (counter = %d)\n", counter);

    Pthread_create(&p1, NULL, mythread, "A");

    Pthread_create(&p2, NULL, mythread, "B");

    // join waits for the threads to finish

    Pthread_join(p1, NULL);

    Pthread_join(p2, NULL);

    printf("main: done with both (counter = %d)\n", counter);

    return 0;

}

希望最终 counter 得到的结果是 20000000，但是往往结果不是对的，而且每次都不一样。关键的指令在于：

mov 0x8049a1c, %eax

add $0x1, %eax

mov %eax, 0x8049a1c

变量 counter 位于地址 0x8049a1c 。在这 3 条指令中，先用 x86 的 mov 指令，从内存地址处取出值，放入 eax 。然后，给 eax 寄存器的值加 1（0x1）。最后， eax 的值被存回内存中相同的地址。

这其实就是 c 代码中的 counter = counter + 1 ，整个程序失败的点在于这行 c 代码不是原子执行。如果线程 A 在执行完 add 指令后中断，此时 counter 还是 50，A 线程的 eax=51 ，轮到 B 执行完这三行指令，此时 counter=51 ，再次轮到 A，就会将 51 再次存入 counter ，相当于 A 线程在本次循环中并没有使 counter 增加。

由于执行这段代码的多个线程可能导致竞争状态，因此我们将此段代码称为临界区 （critical section）。临界区是访问共享变量（或更一般地说，共享资源）的代码片段，一定不能由多个线程同时执行。

我们真正想要的代码就是的互斥（mutual exclusion）。这个属性保证了如果一个线程在临界区内执行，其他线程将被阻止进入临界区。

这些术语都是 Dijkstra 创造的，此处给出一些术语补充：

• 临界区（critical section）是访问共享资源的一段代码，资源通常是一个变量或数据结构。
• 竞态条件（race condition）出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致了令人惊讶的（也许是不希望的）结果。
• 不确定性（indeterminate）程序由一个或多个竞态条件组成，程序的输出因运行而异，具体取 决于哪些线程在何时运行。这导致结果不是确定的（deterministic），而我们通常期望计算机系统给出确 定的结果。
• 为了避免这些问题，线程应该使用某种互斥（mutual exclusion）原语。这样做可以保证只有一 个线程进入临界区，从而避免出现竞态，并产生确定的程序输出。

为了保证安全的访问临界区，有两种方法，要么对临界区的操作是原子操作，要么就是对临界区的操作上锁。将一系列动作原子化（atomic）背后的想法可以简单用一个短语表达：“全部或没有”。要么都发生了，要么都没有发生，不会出现中间状态。

本部分最重要的部分就是对临界区和资源的理解，本质上来说，我们需要锁住的不是临界区，而是临界区访问的资源，有可能很多个不同的临界区都会访问同一个资源。

# 并发：锁

锁的本质就是一个变量，现实生活中，锁的状态只有打开和关闭两种状态（别和我扯什么撬开状态），锁变量其实也就是表示锁的状态，最简单的就是 0 表示打开，1 表示关闭。复杂点的，我们也可以保存：持有锁的线程，请求获取锁的线程队列，但这些信息会隐藏起来，锁的使用者不会发现。

在 c 语言中， lock() 和 unlock() 函数分别表示尝试获取锁和释放锁。在其他语言中，也有类似的方法。

# 评价锁

我们需要一些标准来评判一把锁的实现效果：

• 互斥性：这是最基本的，阻止多个线程进入临界区。
• 公平性（ fairness ）：当锁可用时，是否每一个竞争线程有公平的机会抢到锁？这其实考验的是等待队列的设计，像 AQS 使用的就是先进先出。
• 性能：是使用锁之后增加的时间开销。考虑这个是非常必要的，因为有时真的只有一个线程在执行，但是它还是要执行上锁解锁的操作，当然，还有其他需要考虑的场景。

# 控制中断

最早的互斥方案之一就是在临界区关闭中断，也就是说，此时线程 A 在临界区不会发生上下文切换。这个解决方案是为单处理器 系统开发的。

void lock() {

    DisableInterrupts();

}

void unlock() {

    EnableInterrupts();

}

控制中断是使用特殊的硬件指令，背后的实现是由硬件支持的， CAS 也是由硬件支持的。这种方法优点就是简单，但是缺点十分明显：

• 这种方法要求我们允许所有调用线程执行特权操作（打开 / 关闭中断），但是恶意程序一开始调用关闭中断就会一直霸占处理器。

• 多处理器不适用。多个线程在多 CPU 上，每个线程都试图进入同一个临界区，关闭中断也没用。

• 关闭中断导致中断丢失，可能会导致严重的系统问题。假如磁盘设备完成了读 取请求，但 CPU 错失了这一事实，那么，操作系统如何知道去唤醒等待读取的进程？

• 效率低。与正常指令执行相比，现代 CPU 对于关闭和打 开中断的代码执行得较慢。

# 原子交换

如果不依赖硬件，我们可以这么实现一个锁：

typedef struct lock_t {int flag;} lock_t;

void init(lock_t *mutex) {

    mutex->flag = 0; // 0 表示没有上锁

}

void lock(lock_t *mutex) {

    while(mutex->flag == 1) {

        // 什么都不做，空等待，这就叫做 spin-wait   自旋

    }

    mutex->flag = 1;

}

void unlock(lock_t *mutex) {

    mutex->flag = 0;

}

可以看到这种锁有一些问题：

• 正确性：你可能会觉得上述代码完全没有问题的，但是如果 AB 两个线程都调用 lock 函数，假设 A 先调用，然后经过了 while 循环，此时发生中断，轮到 B，经过 while 循环，又发生中断，那么此时两个线程相当于都拿到了锁，因为他们之后都会执行 mutex->flag = 1; 的操作。导致问题的本质就是 —— 上锁的过程不是原子的。
• 性能：可以看到，如果一个线程拿不到锁，就会一直自旋，直到它的时间片执行完或者拿到锁。自旋等待在等待其他线程释放锁的 时候会浪费时间。尤其是在单处理器上，一个等待线程等待的目标线程甚至无法运行（至 少在上下文切换之前）！

为了解决这些问题，我们需要硬件的支持 —— 原子交换。它们基本上在不同的平台上做同样的事，通常称为测试并设置指令（test-and-set）。回顾上述代码，我们在 lock() 函数中的行为可以归为：测试 flag ，设置 flag 。

这个指令的工作内容，我们用 c 代码演示一下：

int TestAndSet(int *old_ptr, int new) {

    int old = *old_ptr;

    *old_ptr = new;

    return old;

}

只不过这个操作是原子进行的。它原子的实现了：给变量赋予新值并返回旧值。那我们的锁的实现代码就可以改为：

void lock(lock_t *mutex) {

    while(TestAndSet(&mutex->flag, 1) == 1)

        ;// spin-wait

}

只有当旧值为 0 才算此次上锁成功。这样就是原子上锁了，尽管还是没有解决自旋浪费性能的问题。这样的锁就叫做自旋锁（spin lock）。

自旋锁不提供公平性，在竞争状态下，自旋的线程甚至会永远自旋（回忆一下进程切换，如果不人为的设置一些 FIFO 什么的，有些进程会被饿死）。同时，自旋锁在单 CPU 下开销很大，在多 CPU 情况该性能不错。

上文讲了测试并切换 TAS ，其实还有比较并切换 CAS ，c 语言伪代码为：

int compareAndSwap(int *ptr, int expected, int new) {

    int actual = *ptr;

    if(actual == expected)

        *ptr = new;

    return actual;

}

同样是返回旧值（你可以思考一下为什么返回的是旧值），总体思路就是，检测变量的旧值是否是期望值，如果是，就赋新值，返回旧值。如果用 CAS 实现上述自旋锁：

void lock(lock_t *mutex) {

    while(CompareAndSet(&mutex->flag ,0, 1) == 1) {

        ; //spin-wait

    }

}

# 解决自旋

• 让出时间片，即在要自旋的时候，放弃 CPU。

void lock(lock_t *mutex) {

    while(CompareAndSet(&mutex->flag ,0, 1) == 0) {

        yield();

    }

}

我们假定操作系统提供原语 yield() ，线程可以调用它主动放弃 CPU， 让其他线程运行。 yield() 系统调用能让线程由 running 变为 readying 。但是这个方法没有处理本质问题：频繁的上下文切换。线程饿死的情况也没解决。

• 使用队列：休眠代替自旋

前面一些方法的真正问题是存在太多的偶然性。因此，我们必须显式地施加某种控制，决定锁释放时，谁能抢到锁（这样才能保证公平的）。

处于休眠状态的线程永远不会分配到 CPU 资源，当等待的事件出现，休眠状态的线程才会转换到可运行的状态。

在 c 语言中，Solaris 提供了两个调用： park()/unpark(ThreadID) 。前者能够让调用线程休眠，后者会唤醒 ThreadID 标识的线程。使用两个调用实现锁，可以让调用者在获取不到锁时休眠，在锁可用时被唤醒，看一下《操作系统导论》里面给的例子：

typedef struct lock_t {

    int flag;

    int guard;

    queue_t *q;

} lock_t;

void lock_init(lock_t *m) {

    m->flag = 0;

    m->guard = 0;

    queue_init(m->q);

}

void lock(lock_t *m) {

    while(TestAndSet(&m->guard, 1) == 1)

        ;// spin-wait

    if(m->flag == 0) {

        m->flag = 1; // 获得锁

        m->guard = 0;

    } else {

        queue_add(m->q, gettid());

        m->guard = 0;

        park();

    }

}

void unlock(lock_t *m) {

    while(TestAndSet(&m->guard, 1) == 1) 

        ;// spin-wait

    if(queue_empty(m->q)) 

        m->flag = 0; // 没有线程竞争锁

    else 

        unpark(queue_remove(m->q)); // 从队首取出线程，不需要改变 flag

    m->guard = 0;

}

下面解释一下代码：

• flag ：表示锁是否被占用，0 表示没有线程占用锁，1 表示有线程
• guard ：注意，线程获取锁并不是一个原子过程（ lock 函数），但是我们应该让 lock()/unlock() 在某些代码保证并发安全。之前我们的做法：

void lock(lock_t *mutex) {

    while(CompareAndSet(&mutex->flag ,0, 1) == 1) {

        ; //spin-wait

    }

}

确实能保证 lock 内部的并发安全，但是使用 flag 自旋的缺点上文也详述过。所以不能用锁的状态来自旋。此处使用 guard 来自旋。当 guard=0 时，表示没有线程正在改变锁的状态；当 guard=1 时，表示有线程正在改变锁的状态，此时不允许任何线程也跟着来修改锁的状态。

锁的状态包括了 flag，queue。

所以其他线程都会先围绕 guard 自旋一会。这个过程非常短，因为线程修改锁的状态花费的时间也非常短。

• 释放锁时，如果队列里还有线程在等待，不需要改变 flag 。举个例子，假设临界区代码为：

lock(&my_lock);

count++; // 临界区

unlock(&my_lock);

假设只有 AB 两个线程，线程 A 在获取锁后，B 也获取锁，失败后 B 加入等待队列。当 A 执行到 unlock() 代码后，唤醒 B 线程，也许 B 不会立刻被分配时间片，但是此时 flag 仍然为 1，其他线程哪怕拿到时间片获取锁，也需要休眠进入队列。直到 B 分配到时间片，B 从哪里开始继续执行呢？

queue_add(m->q, gettid());

m->guard = 0;

park(); // 从这里被唤醒，也就是 lock () 函数的结尾

相当于在 lock() 结束， count++; 之前被唤醒。在临界区被唤醒，天生自带锁。

# 参考

https://www.jianshu.com/p/3e79ae25bfb6

https://pages.cs.wisc.edu/~remzi/OSTEP/Chinese/26.pdf

https://pages.cs.wisc.edu/~remzi/OSTEP/Chinese/28.pdf