操作系统-并发-互斥

• 互斥困难的根本原因:load 和 store不原子

• 纯软件层面的互斥算法实现太复杂了，下面借助硬件提供的原子指令 实现比peterson简单的互斥协议。

• 硬件提供的原子指令如 : x86-64提供的lock ,xchg ; riscv提供的LR/SC(实现CAS)

• 自旋锁spinlock : 基于xchg实现的spinlock 正确实现临界区互斥。

  • spinlock 缺陷。
    • 除了进入临界区的线程，其他处理器上的线程都在空转
    • 获得自旋锁的线程可能被操作系统切换出去
  • spinlock 使用场景
    • 内核的并发数据结构

• 互斥锁mutex : 在spinlock的基础上实现mutex

  • 目的 : thread在没拿到锁时不自旋空转占用cpu，而是切换到内核并阻塞，然后内核切换到其他thread执行. 避免浪费cpu
  • 由于其目的，故只能是一种syscall

• xv6 : when to lock :

  • if (2 processes access a shared data structure && at least on is writiter) , then lock the shared data structure

如何解决问题

如何解决问题 -> 问题的假设 -> 假设的难点 -> 改变假设

• 找到你依赖的假设，并大胆的打破它
• 如何在多处理器系统上实现互斥?
  • 一开始 软件层面的 peterson算法。太难了。
  • 那么 软件不够 硬件来凑（自旋锁）(利用硬件提供的原子指令实现)
  • 用户不够 内核来凑（互斥锁）(为了让别的thread执行)
  • fast / slow path ：性能优化的重要途径 : futex

互斥困难 根本原因

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

  • 我们看到的东西马上就过时了。不禁让人想起verilog。读的永远是上一时钟周期的值。
  • load (环顾四周) 的时候不能写，只能 “看一眼就把眼睛闭上”
    • 看到的东西马上就过时了
  • store (改变物理世界状态) 的时候不能读，只能 “闭着眼睛动手”
    • 也不知道把什么改成了什么

• 实现一个巧妙地互斥算法是很困难的。

• 我们在这里尽量用简单、粗暴 (稳定)、有效的方法实现互斥。

• 基于以上事实作为假设，我们之前实现一段临界区互斥的方法：软件层面的，如Peterson算法、deckker算法等。很困难

• 那么我们让硬件帮忙，更改一些假设呢？

硬件提供的原子操作

• 汇编中的几条指令可以使得硬件进行原子操作

• lock

  • 原子的实现 load 和 store
  • 汇编的lock前缀,是使用了在硬件层面实现的锁
  • lock是个指令前缀。处理器读到lock 先去上锁。也即，先去获得总线的锁 等到得到总线的锁之后 在执行后面的指令，执行完之后 释放总线上的锁。

    const int N = 100000000;
    int sum = 0;
    void func()
    {
        for(int i=0;i<N;++i)
        {
            asm volatile("lock add $1 , %0 ": "+m"(sum));
            //  ++sum 需要先把sum从内存load到寄存器。然后++寄存器。然后将寄存器store到mem
        }
    }
    //  sum = 200000000

• 汇编中的xchg

  • 最小的 原子的 [load 和 store]：也就是 原子的可以先看一眼 然后改变。
  • 于是，利用汇编中的xchg，实现另一个原子的将两个数值原子的交换的函数。

    //  原子的交换
      //  将addr地址存储的值 和 newval的值 进行原子的交换
      //  并返回addr原本的值。
    int xchg(volatile int *addr,int newval)
    {
        int res;
        asm volatile ("xchg %0 , %1" : "+m"(*addr),"=a"(res) : "1"(newval));
        return res;
    }

• 原子指令的模型

  • 保证之前的store都写入内存（处理器还保证，在一个lock之前发生的所有事情，都可以在后面的lock时被看见）
    • 保证了内存的可见性。
  • 保证load/store不与原子指令乱序（处理器保证，所有带lock的指令 都可以排出一个先后的顺序。）
    • 也因此，就是消灭了并行。

使用原子操作 实现 锁 : 基于xchg 实现 spinlock自旋锁

• 如何用xchg这样的原子指令实现互斥 ?

实现协议

• 人作为thread，物理世界作为 资源： local变量、共享变量、需要互斥进入的临界区。

  人话版

• 还是举例上厕所，多个同学上WC，WC上有锁，钥匙放在桌子上，每个同学手里有一个厕所正在使用的牌子。

• 厕所门口上放一个桌子（共享变量）

  • 初始时 ，桌子上是钥匙

• 在原子操作xchg的基础上，去实现一个互斥的协议。（这就比之前毫无原子操作的假设上实现的Peterson算法简单很多很多）

  • 如果同学A想上厕所。那么lock()，lock如下
    • A闭眼睛
    • 那么 将手中的 NOPE牌子 和 table上的东西（钥匙或者NOPE） 进行交换。
      • 这个交换是基于xchg的原子操作。
        • 拿走table上的东西
        • 将NOPE放在桌子上
    • A睁眼睛
      • 如果手中拿到的是钥匙，那么可以进入厕所。
      • 如果不是钥匙，那么循环上述过程
  • A同学出厕所。那么unlock，unlock如下。
    • 那么 将手中的 钥匙 和 table上的NOPE 进行交换。

• 人 ：thread , NOPE ： local var , 桌子 ：共享变量table , 厕所 ：临界区

实现code

• 如果xchg不是原子的话，那么就可以有多个同学同时拿到table上的YES，一起进入临界区

• code版

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

• 人话版

  // 基于 int xchg(volatile int *addr,int newval);  //  实现见上
  
  #define NOPE 1
  #define YES 0
  
  int table = YES;
  由流程易知
  table 和 同学 手里 有且只有一个YES 多个NOPE
    如果有>1个YES的话，那么就会有多个同学同时进入临界区
    如果有0个YES的话，那么不会有同学进入临界区
  void lock()
  {
  retry:
  //  将table上的标志和我们手中的进行原子的交换(如果我们想要上厕所的话，那么手中最开始一定是个NOPE[禁] , 然后我们要去获得table上的(YES)[钥匙]，去获得进入临界区的机会[打开厕所的门])
  //  如果此时table上是 YES [钥匙]    
      //  那么 xchg之后 我们拿到的就是钥匙 (因为交换的动作是原子的，所以有且只会有一个人拿到了钥匙 不存在重复拿到的情况)
      //  成功拿到 钥匙 ，可以打开WC。于是我们继续向下走（即进入临界区）
  //  如果此时table上是 NOPE [禁止入内]
      //  那么 xchg之后 我们拿到的就是NOPE 
      //  循环等待
      int got_old_table = xchg(&table,NOPE);
      if(got_old_table == NOPE)
          goto retry;
  
      assert(got_old_table == YES);
  }
  
  //  如果有一个没有上锁的人 调用了unlock 那么就会导致这个临界区中可以同时出现两个user
  //  因为table可以同时存在两个yes
  void unlock()
  {
      xchg(&table,YES);
  }

• testSpinLock

  unsigned long long sum = 0;
  const unsigned long long N = 100000;
  void testFunc()
  {
      for(unsigned long long i=0;i<N;++i)
      {
          lock();
          ++sum;
          unlock();
      }
  }
  
  int main()
  {
      std::thread t1(testFunc);
      std::thread t2(testFunc);
      t1.join();
      t2.join();
      std::cout<<sum<<std::endl;
  }
  
  shc@DESKTOP-TVUERHD:~/Code/try/lock$ time ./spinlock
  200000
  real    0m0.018s
  user    0m0.032s
  sys     0m0.000s

原子操作在cpu上怎么实现

• 介绍下前缀lock如何保证硬件的原子操作

原子操作的需求

• atomic test and set 原子的比较、赋值
  • regVal = load(x) ; // 取出regsiter x的值
  • if(regVal == XX) {store (x,YY)} // 如果x存的是XX，那么将YY存入x
• lock xchg 原子的交换值
  • reg = load(x);
  • store(x,XX);
• lock add 原子的++
  • t = load(x)
  • ++t
  • store(x,t)

• 其本质都是

  • load 从内存中加载到reg
  • exec 即处理本地reg运算
  • store 从reg中存到内存

• 实现原子操作就是要 保证 一个内存的状态 可以由 我知道的一个状态，变成我想要他变成的一个状态。

x86-64

前缀lock的早期实现（无cache 只需要锁住主存即可）

• 执行时发现前缀有lock，那么先锁住内存，然后再执行后面的指令，执行完之后释放对内存的锁。
  

前缀lock的现代实现（需要考虑缓存一致性）

• 在 L1 cache 层保持一致性 (ring/mesh bus)

  • 相当于每个 cache line 有分别的锁
  • store(x) 进入 L1 缓存即保证对其他处理器可见
    • 但要小心 store buffer 和乱序执行

• L1 cache line 根据状态进行协调

  • M (Modified), 脏值
  • E ( Exclusive ), 独占访问
  • S (Shared), 只读共享
  • I (Invalid), 不拥有 cache line

应用lock前缀实现上层的原子操作

• 应用lock前缀实现原子的load和store
• 如上的xchg函数 将（exchange操作）load和store作为打包为一个原子的指令。

• 插一条小结
  • 使用 cpu提供的原子指令 的开销就是锁总线的开销以及保持缓存一致性的开销
  • 使用自旋锁的开销 既包括 原子指令的开销，又包括了空转的开销。
  • 使用互斥锁的开销 就是 进入、离开kernel的开销 以及 使用原子指令的开销。
  • 使用futex的开销 ：少量的进入、离开kernel的开销 以及 使用原子指令的开销。（没进入和进入都需要用原子指令）
  • 所以常说的 CAS无锁无锁，这个锁到底说的是什么？
    • 是汇编层面的那个lock前缀？我之前认为是，不过现在看来显然不是，反汇编之后仍然可以看到lock
    • 我现在认为应当指的是 如果不用atomic_int的话，那么对于int sum的++我们理应会使用POSIX库中的pthread_mutex_lock。这个实际上是futex锁，尽管是少量，不过也会有可能进入离开kernel。造成开销。那么如果我们直接用cpu提供的原子指令的话，就完全不必进入离开kernel，而是一直在用户态就可以。
    • 所以我现在认为，所谓的”无锁无锁,无锁开销小“,指的是user无需使用os提供给user的syscall的锁接口.(如pthread_mutex_lock). , 进而无需进入和离开kernel切换上下文. 故开销小.
      • 我是这么认为的. 还没有求证. 不过感觉89不离10

RISC-V

• 基本思想:本地的local的计算不重要，重要的是我要写入的共享内存的状态(当我想要写入时 是否和我之前看到的一样)。本地的local的计算可以重做

CPU 通过 LR and SC 实现原子操作

• Load-Reserved(LR): 在内存上标记 reserved (盯上你了)，中断、其他处理器写入都会导致标记消除
  

  lr.w rd, (rs1) 
    含义如下
    rd = M[rs1]
    reserve M[rs1]

• Store-Conditional(SC): 如果我对于该内存的”盯上”(标记)未被解除，则写入;如果被解除了，那么放弃写入，丢弃本次local计算的结果，稍后重试。
  

  sc.w rd, rs2, (rs1)   
    含义如下
    if still reserved:  如果内存地址rs1上存在加载保留
      M[rs1] = rs2      写入
      rd = 0            存入成功 向reg[rd]写入0
    else:
      rd = nonzero      存入失败（即不存在加载保留，写入非0的errno）

• 通过LR和SC的搭配使用，可以实现对一块mem的原子的load和store

应用LR/SC实现原子操作 ： 原子的Compare and Swap的LR/SC实现

• 可以看到 没有使用锁 就是先了load和store的原子操作

• 所谓的原子的Compare ans Swap的实现

  • 指的是在我们 [compare(load) , (exec) , swap(store)] ,mem没有被其他指令读取、改变。（也就是所谓的没被打断，原子性）

• RISC-V-Reader d的 Compare and Swap
  

• C

  int cas(int *addr, int cmp_val, int new_val) {
    int old_val = *addr;
    if (old_val == cmp_val) {
      *addr = new_val; return 0;
    } else { return 1; }
  }

• 对应的RISCV 汇编

  cas:
    lr.w  t0, (a0)       # Load original value.     
      将mema0的内容加载进t0 并打上flag
    bne   t0, a1, fail   # Doesn’t match, so fail.
    sc.w  t0, a2, (a0)   # Try to update.           
      尝试将a2写入mema0,
        如果a0的flag仍存在，那么写入成功，将标志寄存器t0赋值0代表成功   
        如果a1的flag被改变，那么写入失败，将标志寄存器t0赋值nonzero代表写入失败
    bnez  t0, cas        # Retry if store-conditional failed.
      t0!=0 代表store失败（失败的根本原因是因为不能和load形成原子的操作 从头load开始重新尝试。）
    li a0, 0             # Set return to success.
    jr ra                # Return.
  fail:
    li a0, 1             # Set return to failure.
    jr ra                # Return

spinlock缺陷 性能问题

• 性能问题 1

  • 自旋 (共享变量) 会触发处理器间的缓存同步，延迟增加

• 性能问题 2

  • 除了进入临界区的线程，其他处理器上的线程都在空转
  • 争抢锁的处理器越多，cpu利用率越低
    • 一核处理（进入临界区的thread的核），多核围观。（其他所有没进入临界区的thread）

• 性能问题 3 （比 12都严重）

  • 获得自旋锁的线程可能被操作系统切换出去
    • 那么，这个拿到了spinlock的进入临界区的thread在睡觉，其他没拿到spinlock的thread在空转，并且等待一个 较长时间之后才会释放的锁。（因为拿到锁的thread在睡觉）
    • 那么，0核处理，1核睡觉，多核围观。
    • 实现 100% 的资源浪费
    • 操作系统不 “感知” 线程在做什么

• 由于以上三点，同样的工作，线程数量越多，执行时间越长。对于spinlock尤其明显

  shc@DESKTOP-TVUERHD:~/Code/try/lock$ time ./sum-scalability 1
  sum = 10000000
  
  real    0m0.135s
  user    0m0.132s
  sys     0m0.000s
  shc@DESKTOP-TVUERHD:~/Code/try/lock$ time ./sum-scalability 2
  sum = 10000000
  
  real    0m0.825s
  user    0m1.641s
  sys     0m0.000s
  shc@DESKTOP-TVUERHD:~/Code/try/lock$ time ./sum-scalability 3
  sum = 9999999
  
  real    0m1.162s
  user    0m3.445s
  sys     0m0.000s
  shc@DESKTOP-TVUERHD:~/Code/try/lock$ time ./sum-scalability 4
  sum = 10000000
  
  real    0m1.688s
  user    0m6.670s
  sys     0m0.000s
  shc@DESKTOP-TVUERHD:~/Code/try/lock$ time ./sum-scalability 5
  sum = 10000000
  
  real    0m2.493s
  user    0m12.278s
  sys     0m0.000s

• 对于futex（因为无法获取锁时会阻塞,调度到其他进程而非空转），时间不会随着thread数增大而极度增大

  shc@DESKTOP-TVUERHD:~/Code/try/lock/jyy$ time ./sum-scalability2 1
  sum = 10000000
  
  real    0m0.154s
  user    0m0.145s
  sys     0m0.000s
  shc@DESKTOP-TVUERHD:~/Code/try/lock/jyy$ time ./sum-scalability2 2
  sum = 10000000
  
  real    0m0.786s
  user    0m0.993s
  sys     0m0.564s
  shc@DESKTOP-TVUERHD:~/Code/try/lock/jyy$ time ./sum-scalability2 7
  sum = 9999997
  
  real    0m0.921s
  user    0m1.499s
  sys     0m4.003s
  shc@DESKTOP-TVUERHD:~/Code/try/lock/jyy$ time ./sum-scalability2 15
  sum = 9999990
  
  real    0m1.002s
  user    0m1.685s
  sys     0m9.346s
  shc@DESKTOP-TVUERHD:~/Code/try/lock/jyy$ time ./sum-scalability2 32
  sum = 10000000
  
  real    0m0.916s
  user    0m1.134s
  sys     0m9.653s
  shc@DESKTOP-TVUERHD:~/Code/try/lock/jyy$ 

Scalability : 性能的新维度

• 同一份计算任务，时间 (CPU cycles) 和空间 ( mapped memory) 会随处理器数量的增长而变化
  

spinlock的使用场景

• 临界区几乎不拥堵

  • 几乎不会发生锁的争抢。
  • 比如说 queue作为临界区，threadpool从queue中取任务。取一个任务用100ns，执行一个任务用100ms，不频繁的取队列，锁也就不会争抢，因此可以用spinlock

• 持有自旋锁时禁止执行流切换

  • 但是，这对机器很危险。应用程序也不会有这个权限。

• 真正使用场景：操作系统内核的并发数据结构（短临界区）

操作系统可以关闭中断和抢占

• spinlock的如何使用好是一个很困难的问题。（以前甚至可以发paper）

mutex 互斥锁(os实现的系统调用)

为什么要有互斥锁

• 如果希望实现一个很长的临界区，比如要我在写一个文件的时候，不希望别的thread写。

• 又或者如果我想做一件事情，但是现在做不了，需要等待一个长临界区。我们让另一个任务开始执行。

• 所以，对于让这个动作。让别的thread执行。在用户态用C语言是无法实现的，因此，操作系统应当实现这个系统调用。

• 把锁的实现放到操作系统里就好啦！

  • syscall(SYSCALL_lock, &lk);
    • syscall 进入kernel，关中断，然后进行xchg锁
    • 试图获得 锁，
      • 如果成功上锁，
      • 但如果失败，就切换到其他线程。（切换到其他线程，即让别的thread执行，这个动作只能由os做，user是做不到的）
  • syscall(SYSCALL_unlock, &lk);
    • 释放 锁，如果有等待锁的线程就唤醒

互斥锁实现思路

初始lock = unlocked
临界区 = 更衣室
os = 更衣室管理员
thread = 要进去的人

• 先到的人 thread

  • 成功获得手环，进入更衣室
  • lock 状态 变为 locked

• 后到的人 thread

  • 不能进入更衣室，排队等待
  • 这个后到的thread放入等待队列 执行thread切换（yield）

• 洗完澡出来的人 thread

  • 交还手环给管理员；
  • 管理员把手环再交给排队的人
    • 如果waiting thread queue is not empty，从queue中取出一个thread允许执行
    • 如果waiting thread queue is empty，lock置为 unlocked

• 管理员OS通过使用spin lock来确保 自己处理手环的过程是原子的。

  • 所以，我们站在用户层面看的时候，就可以看到，锁的获取（load看一眼有没有，有的话就拿store；）；和锁的释放是原子的。
  • 到最底层都是用了cpu提供的原子指令如 xchg
  • 我们就是利用的获得释放锁的原子性，来提供临界区互斥（只允许有n个thread）的功能。

关于 spinlock 和 睡眠锁 的快慢分析

• 自旋锁（thread直接共享locked）
  • 更快的fast path
    • xchg成功 -> 立即进入临界区，开销很小
  • 更慢的slow path
    • xchg失败 -> 浪费CPU自选等待

• 睡眠锁（就是上文中的互斥锁，mutex） (通过系统调用访问 locked)
  • 更慢的 fast path
    • 即便上锁成功也需要进出内核 (syscall)
  • 更快的 slow path
    • 上锁失败线程不再占用 CPU

• 今天OS上的锁如何实现
• 小孩子才做选择。我当然是全都要啦！

Futex: Fast Userspace Mutexes

• Fast path: 一条原子指令，上锁成功立即返回。无需进入kernel

• Slow path: 上锁失败，执行系统调用睡眠。需要进入kenrel（系统调用）

  • 性能优化的最常见技巧
    • 看 average (frequent) case 而不是 worst case
  • 绝大多数的时候 都上锁成功 没进入kernel

• POSIX 线程库中的互斥锁 (pthread_mutex)

  • futuex调用的数量远远小于lock和unlock的数量

• 线程库中的锁，在绝大多数情况下都不会触发系统调用，直接用原子指令就解决了。只有在少部分情况下，有争抢的情况下，才会触发系统调用。

• 所以目前我认为 ：futex的好处就是尽量少的触发系统调用？绝大部分情况都不进入内核

---

XV6 6.S801

When to lock

• Constructive rule:
  • if (2 processes access a shared data structure && at least on is writiter) ->
  • lock data structure
  • too strict,相较于lock free programming。但是用锁来实现共享已经足够难了。

Perspective

• Lock perspective
  • lock help avoid last update
    • 防止更新的数据/页/节点被覆盖/丢失。
    • 如防止 list = l 被覆盖
  • lock help amke multi-step to be atomic
    • 使得多步操作原子。
    • 如 l-> next 和 liast = l原子。
  • lock help maintain 不变量
    • 保持list是指向链表首元素的属性。
    • 不变量是跨操作维护的数据结构的属性。通常，操作的正确行为取决于操作开始时不变量是否为真。操作可能暂时违反不变量，但必须在完成之前重新建立它们。例如，在链表的例子中，不变量是list指向列表中的第一个元素，以及每个元素的next字段指向下一个元素。push的实现暂时违反了这个不变量：在第17行，l->next指向list（注：则此时list不再指向列表中的第一个元素，即违反了不变量），但是list还没有指向l（在第18行重新建立）。我们上面检查的竞态条件发生了，因为第二个CPU执行了依赖于列表不变量的代码，而这些代码（暂时）被违反了。正确使用锁可以确保每次只有一个CPU可以对临界区域中的数据结构进行操作，因此当数据结构的不变量不成立时，将没有其他CPU对数据结构执行操作。
• list例子

  struct element {
      int data;
      struct element *next;
  }; 
  
  struct element *list = 0;
  struct lock listlock;
  
  void 
  push(int data)
  {
      struct element *l;
  
      l = malloc(sizeof *l);
      l->data = data;
      acquire(&listlock);
      l->next = list;
      list = l; 
      release(&listlock);
  }

• 如何lock并且尽量做到较好的performance性能
  • need to split up data structure
  • best split is a challenge
  • 方法
    • start with 粗粒度的lock
    • measure performance，是否出现争用
    • 重新设计
    • 是否值得更细粒度，因为越细逻辑越复杂。可能不值得

指令重排

• 人们很自然地会想到程序是按照源代码语句出现的顺序执行的。然而，许多编译器和中央处理器为了获得更高的性能而不按顺序执行代码。如果一条指令需要许多周期才能完成，中央处理器可能会提前发出指令，这样它就可以与其他指令重叠，避免中央处理器停顿。例如，中央处理器可能会注意到在顺序指令序列A和B中彼此不存在依赖。CPU也许首先启动指令B，或者是因为它的输入先于A的输入准备就绪，或者是为了重叠执行A和B。编译器可以执行类似的重新排序，方法是在源代码中一条语句的指令发出之前，先发出另一条语句的指令。
• 编译器和CPU在重新排序时需要遵循一定规则，以确保它们不会改变正确编写的串行代码的结果。然而，规则确实允许重新排序后改变并发代码的结果，并且很容易导致多处理器上的不正确行为。CPU的排序规则称为内存模型（memory model）。
• 例如，在push的代码中，如果编译器或CPU将对应于第4行的存储指令移动到第6行release后的某个地方，那将是一场灾难：

  l = malloc(sizeof *l);
  l->data = data;
  acquire(&listlock);
  l->next = list;
  list = l;
  release(&listlock);

• 如果发生这样的重新排序，将会有一个窗口期，另一个CPU可以获取锁并查看更新后的list，但却看到一个未初始化的list->next。
• 为了告诉硬件和编译器不要执行这样的重新排序，xv6在acquire(kernel/spinlock.c:22) 和release(kernel/spinlock.c:47)中都使用了__sync_synchronize()。__sync_synchronize()是一个内存障碍：它告诉编译器和CPU不要跨障碍重新排序load或store指令。因为xv6在访问共享数据时使用了锁，xv6的acquire和release中的障碍在几乎所有重要的情况下都会强制顺序执行。第9章讨论了一些例外。

Wrap Up

• locks good for correctness , can be bad for perf
• locks complicate programming
• don’t share data structre if you don’t have to
• start with 粗粒度锁 , 在需要时转向细粒度锁
• 使用工具 检测性能和 race

https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_concurrency.html