并发控制互斥笔记

整理总结自蒋炎岩老师的b站课程，https://jyywiki.cn/OS/2022/index.html

多处理器系统中数据的一致性和互斥访问
- 所有的CPU的一级缓存都是连着的，如果是多个CPU的话，用在内存中放置标志位，来保证对当前内容的原子性读取，Xchg指令。
- Lock 指令的现代实现（自旋锁）(类似于悲观锁)
  - ```
  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); }
```
  - 在 L1 cache 层保持一致性 (ring/mesh bus)
    - 相当于每个 cache line 有分别的锁（实际上，这不是传统意义上的锁。在硬件层面，通过缓存一致性协议和高速互连网络，处理器能够确保当一个核心在其L1缓存中修改了某个缓存行时，其他核心能够即时地了解到这一变化。这种机制确保了数据的一致性，而无需显式的锁。）
    - store(x) 进入 L1 缓存即保证对其他处理器可见
      - 但要小心 store buffer 和乱序执行
  - Icache line 根据状态进行协调
    - M (Modified), 脏值
    - E (Exclusive), 独占访问
    - S (Shared), 只读共享
    - I (Invalid), 不拥有 cache line
- Load-Reserved/Store-Conditional（LR/SC）(类似于乐观锁)
  - LR: 在内存上标记 reserved (盯上你了)，中断、其他处理器写入都会导致标记消除
```
lr.w rd, (rs1)
  rd = M[rs1]
  reserve M[rs1]
```
  - SC: 如果 “盯上” 未被解除，则写入
```
sc.w rd, rs2, (rs1)
  if still reserved:
    M[rs1] = rs2
    rd = 0
  else:
    rd = nonzero
```
- 自旋锁的缺陷
  - 性能问题 (0)
    - 自旋 (共享变量) 会触发处理器间的缓存同步，延迟增加
  - 性能问题 (1)
    - 除了进入临界区的线程，其他处理器上的线程都在空转
    - 争抢锁的处理器越多，利用率越低
  - 性能问题 (2)
    - 获得自旋锁的线程
      
      可能被操作系统切换出去
      - 操作系统不 “感知” 线程在做什么
      - (但为什么不能呢？)
    - 实现 100% 的资源浪费
- 自旋锁的使用场景
  - 临界区几乎不 “拥堵”
  - 持有自旋锁时禁止执行流切换
  使用场景：操作系统内核的并发数据结构 (短临界区)
  - 操作系统可以关闭中断和抢占
    - 保证锁的持有者在很短的时间内可以释放锁
- 线程+长临界区的互斥可以解决
  - 把锁的实现放到操作系统里就好啦！
    - ```
    syscall(SYSCALL_lock, &lk);
```
  - 试图获得 lk，但如果失败，就切换到其他线程
- ```
syscall(SYSCALL_unlock, &lk);
```
      - 释放 lk，如果有等待锁的线程就唤醒
    - 其他的线程仍然能继续执行
关于互斥的一些分析
- 自旋锁 (线程直接共享 locked)
  - 更快的 fast path
    - xchg 成功 → 立即进入临界区，开销很小
  - 更慢的 slow path
    - xchg 失败 → 浪费 CPU 自旋等待
- 睡眠锁 (通过系统调用访问 locked)
  - 当没有获取到锁将线程转为就绪状态(会频繁切换上下文)
  - 更快的 slow path
    - 上锁失败线程不再占用 CPU
  - 更慢的 fast path
    - 即便上锁成功也需要进出内核 (syscall)

互斥锁

睡眠锁+自旋锁=互斥锁

先在用户空间自旋

如果获得锁，直接进入
未能获得锁，系统调用

解锁以后也需要系统调用

class Futex:
    locked, waits = '', ''

    def tryacquire(self):
        if not self.locked:
            # Test-and-set (cmpxchg)
            # Same effect, but more efficient than xchg
            self.locked = '🔒'
            return ''
        else:
            return '🔒'

    def release(self):
        if self.waits:
            self.waits = self.waits[1:]
        else:
            self.locked = ''

    @thread
    def t1(self):
        while True:
            if self.tryacquire() == '🔒':     # User
                self.waits = self.waits + '1' # Kernel
                while '1' in self.waits:      # Kernel
                    pass
            cs = True                         # User
            del cs                            # User
            self.release()                    # Kernel

    @thread
    def t2(self):
        while True:
            if self.tryacquire() == '🔒':
                self.waits = self.waits + '2'
                while '2' in self.waits:
                    pass
            cs = True
            del cs
            self.release()