第五课。多处理器视角的OS

  • 回顾：操作系统是状态机的管理者；

    • 在 sys_sched( 调度的过程中，实际上带来了并发性；
    • 操作系统是世界上最早的并发程序；

  • 通过 Thread.h，可以编写多线程的程序；

    • 操作系统会将线程放在不同的处理器上，CPU使用率会超过 100%

  • Ask More Questions…

    • 线程真的共享内存吗？
    • 线程真的具有独立堆栈吗？堆栈的范围又是多少？
    • 创建线程采用的是哪个系统调用？

共享内存 / 独立堆栈：

  • 逐步 +1 但是乱序输出解释了程序的并发性；
  • 而在函数内定义局部变量输出为1，证实了线程具有独立堆栈；
#include "thread.h"
int x1;

void Tprint(int id) {
    int x2 = 1; printf("%d ", x2);
	x1++; printf("%d\n", x1);
}

int main() {
    for (int i=0; i<5; i++) spawn(Tprint);
}

// Output: 
//1 1
//1 4 
//1 3 
//1 2 
//1 5

堆栈范围/我们可以配置线程吗？

通过写一个死循环的递归，我们可以模拟出内存中的上下边界：

void update_range(int T, int *ptr) {
    if (ptr < low[T]) low[T] = ptr;
    if (ptr > high[T]) high[T] = ptr;
}

void probe(int T, int n) {
    update_range(T, &n);
    long sz = (uintptr_t)high[T] - (uintptr_t)low[T];
    if (sz % 1024 < 32) {
        printf("stack(T%d) > %ld KB\n", T, sz/1024);
    }
    probe(T, n+1);
}

  • 最后我们试出来的答案是 8177KB，这说明编译器默认的堆栈是 8192KB（即 8MB）。

  • 当然，如果程序员需要更大的栈，也可以通过 pthread.h 这个库操作。当然额暂时还不需要了解。


并发：从入门到放弃

1. 原子性

  • 状态机的隐含假设：“世界上只有一个状态机”；

  • 推论：对变量的 load，一定会返回最后一次 store 的值；

  • 因为引入了共享内存的东西，这在多处理器编程中不再成立！！

    • 代码执行放弃了原子性（线程在多处理器上并行）；

例如：支付系统；

unsigned long balance = 100;

void Alipay_withdraw(int amt) {
    if (balance >= amt) {
    // 两个线程可能同时满足这个要求，进入该分支
      usleep(1);  // Unexpected delays
      balance -= amt;
    }
}

  • 指令执行放弃了原子性（处理器不再一次执行一条指令）；

例如：多线程的 for 循环求和导致随机数；

#define N 100000
long sum = 0;

void Tsum() {
	for (int i = 0; i < N; i++) sum++;
}

int main() {
    create(Tsum);
    create(Tsum);
    join();
    printf("sum = %ld\n", sum);
}
// Correct Answer: 2N

  • 为此，标准库大部分函数都保证了 线程安全 的特性！

    • printf 就是从缓冲区一个个字符读出来的；
    • 但是执行 buf[pos++] = ch ( pos 共享) 不会 💥！

  • 互斥和原子性是本学期的重要主题：

    • lock(&lk) & unlock(&lk)
    • 在关键的地方，保证绝对串行化！
    • 程序的其他不冲突的部分依然可以并行执行~

2. 执行顺序

  • 在不同的编译优化下，多线程的单步求和会产生其他的答案：

    • -O1 优化：编译器暂存求和结果，在程序末尾写入，导致了代码执行的非原子性错误，Sum = N；
    • -O2 优化：直接把循环优化掉，转变为 SUM += N，这样答案输出就正确了 Sum = 2N；

  • 出于编译器的 “一致性” 原则，在单线程观测下的结果应该是一致的；

    • 这导致了多线程编程中，编译器很有可能出错！
    • 为了保证顺序执行，我们需要将代码/变量 “不可优化”
      • 插入 “内存壁垒”：asm volatile("":::" memory")
      • 将变量标记位 volatile 类型

3. 可见性

  • 首先额，啥是可见性？
    • 准确来说，是处理器之间的可见性；
    • 不好理解？举个例子！

一个例子：

int x = 0, y = 0;

void T1() {
  x = 1; // store(x)
  asm volatile("" : : "memory"); // compiler barrier
  printf("y = %d\n", y); // load(y)
}

void T2() {
  y = 1; // store(y)
  asm volatile("" : : "memory"); // compiler barrier
  printf("x = %d\n", x);  // load(x)
}

  • 这个程序的输出会是什么？

    • 01, 10, 11 三种对吧。

  • 额，真假？我试出来怎么全都是 00 啊？

    • 怎么解释？我们可以搬出计组里面学的知识了！
    • 首先，多处理器可以并行处理指令，那也得分个先来后到吧；
    • 其次，我们知道一条指令可以被拆成多条 “微指令”，如赋值指令可以拆成 读内存->写寄存器->写内存；
    • 而且，读指令一般是比写指令快的，当 x, y 不等价，对其内存的读写可以交换顺序！
    • 所以 printf 语句在并发的过程中会先执行，导致 00 这个结果的出现。

  • 可见性指的是（个人理解）一个处理器在执行指令的过程中，只能考虑到其本身的可序列性，而无法兼顾其他处理器；

    • x86 采用宽松内存模型，使得单处理器的执行更加高效：
      • 程序进行写操作时，会先将其写到一个缓冲队列里；
      • 不同线程之间具有优先级，在某个时间点会写到共享内存中；
    • 对于 ARM 架构来说，共享内存是在所有进程之间随意通信的；
      • 有点像分布式系统；
      • 最终会达到一致性；

  • 放弃了原子性、顺序执行以及可见性，本质上是对于性能的追求！


第六课。并发编程下的OS

  • 人类的本质是 Sequential Creature；
    • 我们习惯于写顺序执行的代码，不愿意承担“三个放弃”；
    • 然而，确认一个并发程序的可序列性是一个 NPC 问题；

  • 但人类是用于挑战的 Creature；

    • 并发不易理解，我们就通过手段“回退”至顺序执行；
    • 对于若干代码块，使得它们之间以某种顺序执行；
    • 这类问题被称为 “互斥” 。非互斥的代码块可以并行处理
      • 但如果互斥的代码块过多，即使有一万个CPU也难以获得很好的性能，这称作 阿姆达尔定律 。

  • 先做出一个基本假设：内存的读/写可以保持顺序性和原子性！

    • 但是，写操作对应的是“覆盖”，不具备读的能力；
    • 读操作也只能瞬时进行，读完后的瞬间即可被更改；

  • 引入了第一个并发算法： Peterson 算法

    • 假设 A 和 B 争用宿舍厕所，他们每个人有一面旗子，和写着对方名字的纸条；
    • 想进入厕所，A或B首先要举起自己的旗子，并向厕所门贴上对方名字的标签；
    • 门上的标签是覆盖着贴上去的；
    • 如果进行如上操作后， 对方举旗，且门上的名字是对方，则等待；反之可以进入；
    • 离开厕所后，放下自己的旗子；（不需理会门上的标签）

  • 如何验证算法的正确性？

    • 直接把所有的状态给画出来！但是纯坐牢
    • 使用一种自动化的手段，让程序做繁琐的工作！

  • 是否存在 “死锁” 的情况呢？

    • 既然已经用状态机建模了，我们也可以将问题转化为图论问题！
    • 用 绿色点\color{green}绿色点 代表 A 进入，蓝色点\color{blue}蓝色点 代表 B 进入。如果通过一个状态永远无法经过绿色点或者蓝色点，则这个算法是不正确的。

  • 回到现实，如何使我们的假设成立？

    • 读/写一个全局变量被要求是 “原子不可分” 的！但这个假设在现代多处理器上已经不成立了。
    • 为了实现这一点，我们需要编译器与处理器的共同帮助；
      • 处理器提供特殊指令 lock 或者 mfence 保证可见性（原子指令）；
      • 编译器使用 __sync_stnchronize() 函数调用，并使用 volatile 关键词使其不被优化（Compile barrier）；
        • 毕竟如果编译器通过优化，使得关键区域的指令被移到了锁的外边，这就完蛋了。
        • 在 Intel 40386 处理器中，已经引入了该类型的指令；
        • 利用原子指令，Intel 实现了对于总线的全局锁（Bus Lock）！

  • 使用原子指令！如 atomic_inc、atomic_xchg 等。
    • 原子指令是绝对正确的，它不会被其他线程打断；
    • 包含 compile barrier，在此之前的所有指令会被执行；
    • 在该指令之前的指令，会对之后的所有原子指令“可见”。
int xchg(int volatile xptr,int newval) {
	int result;
    asm volatile(
        //指今自带 memory barrier
        "lock xchgl %0, %1"
        : "+m"(*ptr)，"=a"(result)
        : "1"(newval)
        // Compiler barrier
        : "memory"
    );
    return result;
}

  • 如何实现互斥？
    • 做题家很重要，但是学会思考、问出问题同样重要。
    • 自旋锁 ：用 xchg 实现互斥！
      • 厕所门口放着一张红卡，所有人手上只有绿卡；
      • 只有拿着红卡的同学才能进厕所；
      • 想上厕所的人可以和桌子上的卡进行“交换”！
      • 由于原子指令 xchg 保证其正确性，所以只有第一个交换的同学能得到红卡。
#define UNLOCK 0
#define LOCK 1

int table = UNLOCK;

void lock()
{ while (xchg(&table, LOCK)); }
// 只要桌子上摆的不是“解锁”卡，则 lock

void unlock()
{ xchg(&locked, UNLOCK); }
// 用原子指令交换

  • Compare & Exchange 算法：cmpxhcg
    • 一种“无锁”的并发算法实现；
    • 通过比较上一次获得的值是否仍然有效；
    • 如果不一致，则与新的值进行交换；
int cmpxchg(int old, int new, int volatile *ptr) {
  asm volatile(
    "lock cmpxchgl %[new], %[mem]"
      : "+a"(old), [mem] "+m"(*ptr)
      : [new] "S"(new)
      : "memory"
  );
  return old;
}

int cmpxchg_ref(int old, int new, int volatile *ptr) {
  int tmp = *ptr;  // Load
  if (tmp == old) {
    *ptr = new;  // Store (conditionally)
  }
  return tmp;
}

  • 自旋锁的缺陷

    • 性能问题（1）
      • 除了进入临界区的线程，其他处理器的线程都在自旋；
      • 争抢锁的处理器越多，其 CPU 利用率越低；
    • 性能问题（2）
      • 如果线程数量比 CPU 数量多，那么持有自旋锁的线程随时可能被操作系统切换出去！
      • 这样就真的没人在 work 了，实现 100% 资源浪费；

  • 对自旋锁提出质疑

    • 提出一个新的 Benchmark：Scalability
      • 同一计算任务，时间与空间随着处理器数量的增长而变化的趋势；
      • 实际上，随着线程的增长，时间并没有随着并行程度的提高而减少
        • 第一种可能的原因是自旋锁的性能下降；
        • 第二种可能是随着CPU之间的切换，数据也要从不同 CPU 之间的 L1 cache 中搬动，这也是需要时间的；
    • 自旋锁的使用场景比较狭窄
      • 临界区最好不会“拥堵”，且持有自旋锁的过程中不要进行流切换
        • 这也可以通过关中断的操作防止切换，但是这不能阻止其他 CPU 发生切换；
      • 操作系统内核的并发数据结构（短临界区）\color{red}操作系统内核的并发数据结构（短临界区）

  • 实现线程+长临界区的互斥

    • 当某个线程获得锁失败之后，希望将 CPU 资源转让给其他线程使用；

    • C 代码做不到对于 CPU 内核的操作，只能通过系统调用实现！

      • syscall(SYSCALL_lock, &lk); 试图获得锁，失败则切换
      • syscall(SYSCALL_unlock, &lk); 释放锁，有等待则唤醒

    • 实际上还是利用自旋锁去保证并发的正确性；