多处理器编程

• 并发就是操作系统的核心之一
  • 操作系统的很多内部数据结构（如进程列表、页表、文件系统结构）都得考虑数据竞争的可能。
• 并发的很多技术都是源自于操作系统的设计需求和其相应的解决方案

1 多线程编程入门

• 什么是线程: 共享内存的执行流
• 拥有独立的 “上下文” 和栈帧列表，共享全局变量、堆空间
• 线程就是代表着程序的 “执行” 单位，操作系统可以随时运行、暂停、和恢复执行它
• 有了线程，我们可以 “线性的” 写多个执行流，然后他们可以 “并发” 的执行

• 从状态机的角度来看，多个线程就是多个共享内存的状态机
  • 初始状态为线程创建时刻的状态，状态迁移为调度器任意选择一个线程执行一步

值得注意的是：虽然这里是 thread2 执行一步 \(s_2 \to s_2'\)，然而这个状态变化可能包括共享状态，因此可能顺着带着改变了 thread1 的状态 \(s_1 \to s_1'\)。这里和以往地方不同的地方在于，thread1 并没有主动“求变”，而是其不知道的情况下发生了改变！

• Posix 基本线程 API：

• 线程的一生经历初始化、就绪、运行、等待和结束的周期

• 只有在运行阶段，其 Context 才会在 CPU 上，其余都在内核栈上，当线程处于就绪阶段时其 TCB 在 OS 维护的 ready 列表上等待调度，当线程处于等待阶段时，其 TCB 在 OS 维护的同步等待列表上等待同步事件发生

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUMBER_OF_THREADS 10
void *print_hello_world(void *tid){
    printf("Hello World. Greetings from thread %d\n", tid);
    pthread_exit(NULL);
}

int main(int argc, char *argv[]) {
    pthread_t threads[NUMBER_OF_THREADS];
    int status, i;
    for(i=0; i < NUMBER_OF_THREADS; i++){
        printf("Main here. Creating thread %d\n", i);
        status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);
        if (status != 0) {
            printf("Oops. pthread_create returned error code %d\n", status);
            exit(-1);
        }
    }
    // 如果主线程不调用 pthread_join 等待子线程
    // 主线程很可能会在子线程完成打印之前就执行完毕并退出
    // 操作系统会销毁该进程的整个地址空间，未运行完毕的子线程就会被直接 “强制抹杀”
    for(i=0; i < NUMBER_OF_THREADS; i++){
        pthread_join(threads[i], NULL);
    }
}
// 输出极大概率是乱序的

2 原子性丧失

#define N 100000000
#define NUMBER_OF_THREADS 2

long sum = 0;

void *T_sum(void* nothing) {
    for (int i = 0; i < N; i++) {
        sum++;
        // mov  $sum, %rax
        // add  1, %rax
        // mov  %rax, $sum
    }
}

int main() {
    pthread_t threads[NUMBER_OF_THREADS];

    pthread_create(&threads[0], NULL, T_sum,  NULL);
    pthread_create(&threads[1], NULL, T_sum,  NULL);

    for (int i=0; i < NUMBER_OF_THREADS; i++){ pthread_join(threads[i], NULL);}

    printf("sum = %ld\n", sum);
    printf("2*n = %ld\n", 2L * N);
}
// 输出 sum 会远小于 2 亿

• 原子性丧失：[All or nothing] 违背

• 即使我们强制让 sum++ 变成一个 “单个指令” 结果仍然不对

#define N 100000000
#define NUMBER_OF_THREADS 2

long sum = 0;

void *T_sum(void* nothing) {
    for (int i = 0; i < N; i++) {
        asm volatile("incq %0": "+m"(sum)); // 单个指令
    }
}

int main() {
    pthread_t threads[NUMBER_OF_THREADS];
    pthread_create(&threads[0], NULL, T_sum, NULL);
    pthread_join(threads[0], NULL);

    printf("sum = %ld\n", sum);
    printf("2*n = %ld\n", 2L * N);
}

• 原子性丧失：[Isolation] 违背
  • 竞争同一个 data（data race）
  • 可能发生一个线程先做这个指令，但中途（thread1 还没做完）另一个线程也做这个指令，最终导致 sum 的增加不对

3 顺序性丧失

• 顺序性：
  • 程序语句按照既定的顺序执行！
• 然而，只要不影响语义，其实指令是否按照顺序执行并不重要
  • 编译器就会通过 reorder instructions 来优化程序
  • 这些优化在单线程下往往没有问题，但一旦到了多线程，很多逻辑就错了

控制执行顺序：

• 方法 1: 在代码中插入 “优化不能穿越” 的 barrier
  • asm volatile (“” ::: “memory”);
  • Barrier 的含义是告诉编译器这里 “可以读写任何内存”
• 方法2: 使用volatile变量，标记其每次load/store为不可优化
  • bool volatile flag;

4 全局一致性丧失

4.1 内存一致性模型*

• 现代处理器往往允许指令乱序执行（编译器是将原始执行语句打乱，处理器本身面对指令序列进行乱序执行）
  • 比如对于高时延的访存指令（如cache miss），处理器可以选择调度后续其他指令执行，从而隐藏访存操作的时延
• 然而这种乱序会导致多个处理器看到不一致的访存顺序！
• 内存一致性模型（简称内存模型）明确定义了不同核心对于共享内存操作需要遵循的顺序

4.2 顺序一致性模型

顺序一致性模型提供了以下保证:

• 首先，不同核心看到的访存操作顺序完全一致，这个顺序称为全局顺序
• 其次，在这个全局顺序中，每个核心自己的读写操作可见顺序必须与其程序顺序保持一致

可以看成一个 “时间单位” 上只能选择一个线程读或写共享内存一次，最终形成一个统一的全局的访问内存的顺序

int x = 0, y = 0;

void T1() {
    x = 1;  // Store(x); 
    __sync_synchronize(); // a barrier
    int t = y; // Load(y)
    printf("%d", t);
}

void T2() {
    y = 1;
    __sync_synchronize();
    int t = x;
    printf("%d", t);
}

事实上，目前市面上已经没有支持顺序一致性模型的 CPU 了

4.3 TSO(Total Store Ordering)内存模型*

线程 1 看到线程 2 是先读 x，然后写 y，但对于线程 2 而言，其是先执行写 y，然后再读 x（虽然这个顺序被处理器打乱了，因为处理器觉得两个顺序不重要，x 和 y 不存在依赖），因此不再一致

• 图中每个 Thread 下面都有一个写缓冲区
  • 直接把数据写回到主存太慢了
  • 当 CPU 执行写操作 时，它只是把数据丢进自己的 Store Buffer，然后立刻去执行下一条指令
• 破解 0,0 谜题的根源：
  • 当线程 1 把 x=1 放到自己的 Store Buffer 时，这个值对其他线程是不可见的，主存里 x 依然是 0。
  • 此时，线程 1 继续往下执行 t=y。它去主存里读 y，读到了 0。
  • 同理，线程 2 把 y=1 放到自己的缓冲，去主存读 x，也读到了 0。
  • 只有在未来的某个时刻，Store Buffer 里的数据才会被“刷”（Flush）到主存中。

• “一个处理器会比其他处理器更早看到自己的写” 这叫 Store Forwarding。如果线程 1 写了 x=1 到缓冲区，紧接着它自己又去读 x，它会先查自己的缓冲区，发现有 1，就直接用。但如果是线程 2 来读 x，它只能看主存，看到的还是 0。

4.4 宽松内存模型(Relaxed Memory Model)

• 不保证任何不同地址且无依赖的访存操作之间的顺序，也即读读，读写，写读与写写操作之间都可以乱序全局可见

#define NOT_READY 0;
#define READY 1;
int data = 0;
int flag = NOT_READY;

void thread_A(void){
    data = 123;
    // __sync_synchronize() // 插入这个才能使得宽松内存模型正确
    flag = READY;
}

void thread_B(void)
{
    while(flag != READY) ; /* 循环忙等 */
    handle(data);
}

基于共享内存的消息传递机制

• 在 TSO 下：完美运行
  • 因为 x86 保证 “写-写” 不乱序。data = 123 一定会比 flag = READY 先写入主存。只要 Thread_B 看到了旗帜升起，主存里的 data 就必定已经是 123 了。。
• 宽松模型下：灾难发生
  • 由于允许 “写-写” 乱序，CPU 或者内存系统可能会觉得 flag = READY 这条指令更容易执行，于是把它插队到了 data = 123 前面。