并发编程最基本问题：我们希望原子式执行一系列指令 但是由于单处理器上的中断(或者多个线程在多处理器上并发执行)我们做不到

所以我们运用锁

28.1 锁的基本思想

  • lock()尝试获取锁 如果没有其他线程持有锁 那么该线程会获得锁 进入临界区 如果锁被另一线程持有 那么该调用就不会返回 这样 当持有该锁的线程位于临界区 其他线程就无法进入临界区

锁的持有者一旦unlock()锁就变成可用的了：

①如果没有其他等待线程(即没有其他线程用过lock()并卡在那里) 锁就变成可用状态

②如果有线程卡在lock() 其中一个就会注意到锁状态的变化 获得该锁 进入临界区

28.2 Pthread锁

  • 任何临界区都是用同一个大锁(粗粒度方案)
  • 用不同的锁保护不同的数据和结构 从而允许更多线程进入临界区(细粒度方案)

28.4 评价锁

①锁是否有效 能够阻止多个线程进入临界区

②公平性 当锁可用时 是否每一个竞争线程有公平的机会抢到锁 是否有竞争锁的线程会饿死 一直无法获得锁

③性能 使用锁之后增加的时间开销

28.5 控制中断

最早的互斥解决方案质疑 是在临界区关闭中断

  • 优点：没有中断 线程可以确定它的代码会继续执行下去 不会被其他线程干扰
  • 缺点： 要求我们允许所有调用线程执行特权操作(打开关闭中断)即信任这种机制不会被滥用

①一个贪婪的程序可能在开始的时候就调用lock() 从而独占处理器 如果一直死循环就必须重启系统了

②不支持多处理器 如果多个线程运行在不同CPU上 每个线程都试图进入同一个临界区 即使关闭中断也没有用 线程可以运行在其他处理器上

③关闭中段导致中断丢失 假如磁盘完成IO读取 但CPU错失了这一事实 那么操作系统如何知道去唤醒等待读取的进程

④效率低

28.6 测试并设置指令(原子交换)

如果没有硬件支持 自旋锁 自旋等待在等待其他线程释放锁的时候会浪费时间

尤其是在单处理器上的上 一个等待线程 等待的目标甚至无法运行

28.7 实现可用的自旋锁

自旋锁 一直自旋 利用CPU周期 直到锁可用

在单处理器上，需要抢占式的调度器，即不断通过时钟中断一个线程，运行其他线程。否则，自旋锁在单CPU上无法使用 因为一个自旋的程序永远不会放弃CPU

28.8 评价自旋锁

①正确

②不公平 自旋的线程在竞争条件下可能会永远自旋 可能会导致饿死

③ 单CPU 性能开销相当大 (加上一个线程持有锁进入临界区时被抢占 调度器可能会运行其他每一个线程。而其他线程都在竞争锁 都会在放弃CPU之前 自旋一个时间片 浪费CPU周期)

多CPU 性能还不错(如果线程数大致等于CPU数)

28.9 比较并交换

  • 无等待同步 比较并交换强于测试并设置
  • 自旋锁实现 两者无差别

28.10 链接的加载和条件式存储指令

  1. //加载
  2. int LoadLinked(int *ptr){
  3.     return *ptr;
  4. }
  5. //条件存储
  6. int StoreConditional(int *ptr,int value){
  7.     if(no one has updated *ptr since the LoadLinked to this address){
  8.         *ptr=value;
  9.         return 1;   //success!
  10.     }else return 0; //failed to update
  11. }

条件式存储：只有在上一次加载的地址在期间都没有更新时 才会成功

28.11 获取并增加

原子地返回特定地址的旧值，并且让该值自增1

此处查看原书代码

  • 本方法能够保证所有线程都能抢到锁

28.12 & 28.13 解决自旋过多

  • 在要自旋的时候放弃CPU 让其他线程运行 让出线程本质上取消调度了它自己。

在单处理器上 yield方法十分有效。

然而如果多线程反复竞争一把锁。假如有100个线程，一个线程持有锁，在释放锁前被抢占，其他99个线程分别调用lock()，发现锁被抢占，然后让出CPU。那么这99个程序会一直处于运行yield这种模式 直到持有锁的线程再次运行 上下文切换成本太大 而且可能会有饿死情况 一个线程不断谦让地yield 而其他线程反复进入临界区

28.14 使用队列：休眠替代自旋

自旋和让出CPU(yield)真正问题是存在太多偶然性 调度程序决定如何调度 如果调度不合理就会出问题

因此 必须显式地事假某种控制 决定锁释放时 谁能抢到锁 需要一个队列来保存等待锁的线程

  • Solaris提供的支持： | park() | unpark(threadID) | | —- | —- | | 让调用线程休眠 | 唤醒threadID的线程 |
  1. //通过队列来控制  避免饿死
  2. typedef struct{
  3.     int flag;
  4.     int guard;
  5.     queue_t *q;
  6. }lock_t;
  8. void lock_init{
  9.     m->flag = 0;
  10.     m->guard = 0;
  11.     queue_init(m->q);
  12. }
  14. void lock(lock_t *m){
  15.     while(TestAndSet(&m->guard,1) == 1)
  16.         ;
  17.     if(m->flag==0){
  18.         m->flag=1; //有线程获得锁了
  19.         m->guard=0;
  20.     }else{
  21.           queue_add(m->q,gettid());  //挨个让未获得锁的线程入队并让他们休眠
  22.         m->guard = 0;
  23.         park();
  24.     }
  25. }
  27. void unlock(lock_t *m){
  28.     while(TestAndSet(&m->guard,1) == 1)
  29.         ;
  30.     if(queue_empty(m->q))
  31.         m->flag = 0;
  32.     else
  33.         unpark(queue_remove(m->q)); //一次只让一个线程醒过来 hold lock for next thread!!
  34.     m->guard = 0; 
  35. }

PS.思索了一阵子终于想通 有种大仇得报的感觉……

  • 唤醒线程是从该线程休眠的地方继续执行的，那么怎么让从park()处苏醒的线程获得锁呢？就是直接将释放锁的线程的权限转交传递给获得锁的线程
  • 可能出现的竞争条件 在一个线程将要park()之前 切换到持有锁的线程 并且它释放了锁，那么之前的那个将要park()的线程将长眠不醒。因为线程已经入队，但是还没睡就被持有锁的线程通过unlock()从队里pop出来并唤醒，那么等到我要睡的时候，就醒不过来了

Solaris通过separk()调用解决这个问题。通过该函数，线程表明自己马上就要park。如果刚好另一个线程被调度了并且调用了unpark，那么后面我自己的park就直接返回，不睡觉了。

28.15 Linux提供futex

每个futex都关联一个特定的物理内存位置，也有一个事先建好的内核队列 调用者通过futex调用来睡眠或者唤醒