多处理器编程-从入门到放弃

(Updated: )
操作系统

放弃原子性

状态机的隐含假设

世界上只有一个状态机

  • 没有其他任何人能”干涉”程序的状态
  • 推论: 对变量的load一定返回本线程最后一次的store的值
    • 这也是编译优化的基本假设

但共享内存推翻了这个假设

1
2
3
4
int Tworker(){
    printf("%d\n", x);  // Global x  
    printf("%d\n", x);   
}
  • 其他线程随时可以修改x
    • 导致两次可能读到不同的x

放弃指令/代码执行原子性假设

处理器一次执行一条指令的基本假设在今天的计算机系统上不再成立(我们的模型作出了简化的假设)

单处理器多线程

  • 线程再运行时可能被中断, 切换到另一个线程执行

多处理多线程

  • 线程根本就是并行执行的

放弃执行顺序

放弃程序的顺序执行假设

代码示例: 多线程求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "thread.h"

#define N 100000000

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);
}
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
42
43
44
45
46
47
48
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdatomic.h>
#include <assert.h>
#include <unistd.h>
#include <pthread.h>

#define NTHREAD 64
enum { T_FREE = 0, T_LIVE, T_DEAD, };
struct thread {
  int id, status;
  pthread_t thread;
  void (*entry)(int);
};

struct thread tpool[NTHREAD], *tptr = tpool;

void *wrapper(void *arg) {
  struct thread *thread = (struct thread *)arg;
  thread->entry(thread->id);
  return NULL;
}

void create(void *fn) {
  assert(tptr - tpool < NTHREAD);
  *tptr = (struct thread) {
    .id = tptr - tpool + 1,
    .status = T_LIVE,
    .entry = fn,
  };
  pthread_create(&(tptr->thread), NULL, wrapper, tptr);
  ++tptr;
}

void join() {
  for (int i = 0; i < NTHREAD; i++) {
    struct thread *t = &tpool[i];
    if (t->status == T_LIVE) {
      pthread_join(t->thread, NULL);
      t->status = T_DEAD;
    }
  }
}

__attribute__((destructor)) void cleanup() {
  join();
}

如果添加编译优化?

  • O1: 100000000
    • 原因: R[eax] = sum; R[eax] += N; sum = R[eax]
  • O2: 200000000
    • 原因: sum += N; 编译器将求和过程给优化成一个常数N

多个线程同时执行sum++. 我们可以使用inline assembly要求把求和翻译成一条指令, 但除非引入额外的硬件机制, 依然无法保证单条指令再多处理器上执行的原子性, 具体原因继续看下面.

另外一个例子:

1
2
3
while(!done);
// would be optimized to
if(!done) while(1)

编译器对内存访问”eventually consistent”的处理导致共享内存作为线程同步工具的失效.

保证执行顺序

  • C状态和汇编状态机的”可观测行为等价”
  • 方法1: 插入”不可优化”代码
    • asm volatile(“” ::: “memory”);
      • “Clobbers memoruy”
  • 方法2: 标记变量load/store为不可优化
    • 使用volatile变量
1
2
3
extern int volatile done; 

while(!done);

放弃处理器间的可见性

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
int x = 0, y = 0;

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

void T2() {
  y = 1;  // Store(y)
  __sync_synchronize();
  printf("%d", x); // Load(x)
}

遍历模型告诉我们: 01, 10, 11

然而, 机器永远是对的. 实际情况还存在又00

线程处理器也是(动态)编译器

错误(简化)的假设

  • 一个CPU执行一条指令到达下一状态

实际的实现

  • 电路将连续的指令”编译”成更小uops
    • RF[9] = load(RF[7] + 400)
    • store(RF[12], RF[13])
    • RF[3] = RF[4] + RF[5]

即一条指令可以由多条微指令组成

在任何时刻, 处理器都维护一个uop的”池子”

  • 与编译器一样, 做”顺序执行”假设: 没有其他处理器”干扰”
  • 每一周期执行尽可能多的uop - 多路发射, 乱序执行, 按序提交

放弃多处理器间内存访问的即时可见性

满足单处理器eventual memory consistency的执行, 在多处理器系统上可能无法序列化

当x!=y时, 对x,y的内存读写可以交换顺序

  • 它们甚至可以在同一个周期里完成(只要load/store unit支持)
  • 如果写x发生cache miss, 可以让读y先执行
    • 满足”尽可能执行uop”的原则, 最大化处理器性能
1
2
3
    # <----------+
movl $1, (x)   # |
movl (y), %eax # |
  • 在多处理上表现
    • 两个处理器分别看到y=0和x=0

为了提供共享内存系统的性能, 系统中并非只有一个”全局共享内存”. 每个处理器都有自己的缓存, 并且通过硬件实现的协议维护一致性. 在x86多处理器系统中, 允许store时暂时写入处理器本地的store buffer, 从而延迟对其他处理器的可见性.

宽松内存模型-Relaxed/Weak Memory Model

Take-away Messages

在一个简化的模型中, 多线程/多进程程序就是”状态机的集合”, 每一步选一个状态机执行一步. 然而, 真实的系统可能带来一些复杂性.

  • 指令/代码执行原子性假设不再成立
  • 程序的顺序执行假设不再成立
  • 多处理间内访问无法即使可见

然而, 人类本质上是物理时间(宏观时间)中的”sequential creature”, 因此我们在编程时, 也”只能”习惯单线程的顺序/选择/循环结构, 真是多处理器上的并发编程是非常具有挑战性的”底层技术”.