3.1-并发控制：互斥

复习

• 状态机、状态机、状态机

本次课回答的问题

• Q: 如何在多处理器上实现线程互斥？

本次课主要内容

• 自旋锁的实现
• 互斥锁的实现

一、共享内存上的互斥

在共享内存上实现互斥

失败的尝试

• mutex-bad.py

(部分) 成功的尝试

• peterson-barrier.c

实现互斥的根本困难：不能同时读/写共享内存

• load (环顾四周) 的时候不能写，只能 “看一眼就把眼睛闭上”
  • 看到的东西马上就过时了
• store (改变物理世界状态) 的时候不能读，只能 “闭着眼睛动手”
  • 也不知道把什么改成了什么
• 这是简单、粗暴 (稳定)、有效的《操作系统》课

二、自旋锁 (Spin Lock)

x86 原子操作：LOCK 指令前缀

#include "thread.h"

#define N 100000000

long sum = 0;

void Tsum() {
  for (int i = 0; i < N; i++) {
    asm volatile("lock addq $1, %0": "+m"(sum));
  }
}

int main() {
  create(Tsum);
  create(Tsum);
  join();
  printf("sum = %ld\n", sum);
}

编译优化

gcc -O2 -lpthread sum-atomic.c && ./a.out

sum = 200000000

实现互斥：自旋锁

int table = YES;

void lock() {
retry:
  int got = xchg(&table, NOPE);
  if (got == NOPE)
    goto retry;
  assert(got == YES);
}

void unlock() {
  xchg(&table, YES)
}

int locked = 0;
void lock() { while (xchg(&locked, 1)) ; }
void unlock() { xchg(&locked, 0); }

实现互斥：自旋锁 (cont’d)

并发编程：千万小心

• 做详尽的测试 (在此省略，你们做 Labs 就知道了)
• 尽可能地证明 (model-checker.py 和 spinlock.py)

原子指令的模型

• 保证之前的 store 都写入内存
• 保证 load/store 不与原子指令乱序

class Spinlock:
    locked = ''

    @thread
    def t1(self):
        while True:
            while True:
                self.locked, seen = '