并发编程

原子性问题如何解决
- 源头：线程切换。解决方式：禁用线程切换。操作系统做线程切换是依赖CPU中断的，所以只需要禁止中断即可。
- 在单核 CPU 场景下，同一时刻只有一个线程执行，禁止 CPU 中断，意味着操作系统不会重新调度线程，也就是禁止了线程切换，获得 CPU 使用权的线程就可以不间断地执行，所以两次写操作一定是：要么都被执行，要么都没有被执行，具有原子性。
- 但是在多核场景下，同一时刻，有可能有两个线程同时在执行，一个线程执行在 CPU-1 上，一个线程执行在 CPU-2 上，此时禁止 CPU 中断，只能保证 CPU 上的线程连续执行，并不能保证同一时刻只有一个线程执行，如果这两个线程同时写 long 型变量高 32 位的话，那就有可能出现我们开头提及的诡异 Bug 了。
- 互斥：同一时刻只能有一个线程执行。只要能够保证对共享变量的修改是互斥的，无论单核还是多核CPU都没有影响。
- 简易锁模型。
- 互斥执行的代码称之为临界区。这里首先明确两点：第一我们的锁是什么？第二我们要保护的是什么？
- 简单来说就是锁和资源要有对应关系。下图是对锁模型的改进：
- 为要保护的资源R创建一把锁，同时在进入和离开临界区的时候要加锁和解锁。这里的关键是自家的锁不要拿来锁了别家的东西。
- Java中提供的锁技术：synchronized。它可以修饰的东西比较多：包括非静态方法、静态方法、代码块。加锁 lock() 和解锁 unlock() 在哪里呢？其实这两个操作都是有的，只是这两个操作是被 Java 默默加上的，Java 编译器会在 synchronized 修饰的方法或代码块前后自动加上加锁 lock() 和解锁 unlock()，这样做的好处就是加锁 lock() 和解锁 unlock() 一定是成对出现的，毕竟忘记解锁 unlock() 可是个致命的 Bug（意味着其他线程只能死等下去了）。修饰静态方法时，锁定的是当前类的Class对象；修饰非静态方法，锁定的是当前实例对象this。
- 示例：
```
class SafeCalc {
  long value = 0L;
  synchronized long get() {
    return value;
  }
  synchronized void addOne() {
    value += 1;
  }
}
```
- 注意这里的addOne和get都是声明了synchronized。怎么理解呢？对于addOne，有了synchronized的修饰，里面的value的累加操作就是原子性的，无论是单核还是多核同一时刻只会有一个线程执行；可见性参照管程的概念：对一个锁的解锁是Happens-Before于后续对这个锁的加锁。我们知道synchronized修饰的临界区是互斥的，也即同一时刻只会有一个线程执行临界区的代码，这样前一个线程在临界区修改的共享变量（该操作在解锁之前），对于后续进入临界区的（该操作在加锁之后）线程是可见的。所以对于addOne多个线程执行原子性和可见性都是有保证的。这里面的get方法也是要加synchronized修饰的，因为如果不加锁，一个线程对临界区的加锁修改共享变量对于另一个线程对该共享变量的读取是不可见的，就导致出现读取的值不对的情形。
- 受保护资源和锁之间的关联关系是 N:1 的关系。对上述的示例做些改动：
```
class SafeCalc {
  static long value = 0L;
  synchronized long get() {
    return value;
  }
  synchronized static void addOne() {
    value += 1;
  }
}
```
- 看到addOne是静态方法，这把锁保护的就是SafeCalc这个类；而get的那把锁则是保护的类对象实例，同时存在两把锁，但是保护的却是同一个资源即value。两个之间就没有了互斥性，自然会存在并发问题。
- 上述互斥锁使用之前一定要搞清楚锁定对象和受保护资源的关系。多把锁不能保护同一个资源。
如何保护多个资源？
- 这些资源之间没有关系。用不同的锁对对受保护资源进行精细化管理，能够提升性能，称之为细粒度锁。
- 多个资源之间有关系。这种场景下要保证多个资源共享同一把锁，最佳的可实践方式就是对类进行加锁，这样所有类的实例都是共享的同一把锁。这种情况下的考虑就需要采用一个更大粒度的锁了。（但这种方式存在一个问题就是所有操作都是串行的，性能上是不可取的）
- 原子性的本质不是不可分割，这只是外在表现，其本质是多个资源之间有一致性的要求，操作的中间状态对外不可见。。例如，在 32 位的机器上写 long 型变量有中间状态（只写了 64 位中的 32 位），在银行转账的操作中也有中间状态（账户 A 减少了 100，账户 B 还没来得及发生变化）。所以解决原子性问题就是保证中间状态对外不可见。

如何解决上面的多资源有关系的粗粒度的处理方式带来的串行性能问题呢？

以入账、转账为例，如果要保证操作都是并发进行，一种可实践的方式就是采用两把锁，转出账本一把，转入账本一把。但是这种情况可能会带来死锁的问题，解决死锁要满足4个条件：
1. 互斥，共享资源 X 和 Y 只能被一个线程占用
2. 占有且等待，线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X
3. 不可抢占，其他线程不能强行抢占线程 T1 占有的资源
4. 循环等待，线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待
解决方式：
- 条件2对于占有且等待可以一次性获取申请所有的资源
- 条件3对于不可抢占，占有部分资源的线程进一步申请其他资源不可得的情况下，可以主动释放它所占有的资源
- 对于条件4的循环等待，可以按序申请资源来预防。

对于上述解决方式从代码上该如何操作呢？

对于账户转账问题可以增加一个账户管理员的身份，每次申请转出和转入账本的时候，必须通过账户管理员查看这两个账本是否同时存在，然后决定是否借出
对应到代码中，某一账户需要执行转账操作时，需要同时锁定和释放资源。

  class Allocator {
    private List<Object> als =
      new ArrayList<>();
    // 一次性申请所有资源
    synchronized boolean apply(
      Object from, Object to){
      if(als.contains(from) ||
          als.contains(to)){
        return false;  
      } else {
        als.add(from);
        als.add(to);  
      }
      return true;
    }
    // 归还资源
    synchronized void free(
      Object from, Object to){
      als.remove(from);
      als.remove(to);
    }
  }

  class Account {
    // actr 应该为单例
    private Allocator actr;
    private int balance;
    // 转账
    void transfer(Account target, int amt){
      // 一次性申请转出账户和转入账户，直到成功
      while(!actr.apply(this, target))
        ；
      try{
        // 锁定转出账户
        synchronized(this){              
          // 锁定转入账户
          synchronized(target){           
            if (this.balance > amt){
              this.balance -= amt;
              target.balance += amt;
            }
          }
        }
      } finally {
        actr.free(this, target)
      }
    } 
  }

破坏不可抢占条件。核心是要能够主动释放它占有的资源，这一点 synchronized 是做不到的。原因是 synchronized 申请资源的时候，如果申请不到，线程直接进入阻塞状态了，而线程进入阻塞状态，啥都干不了，也释放不了线程已经占有的资源。sdk层面是可以解决的。并发包下的Lock。

破坏循环等待条件。对资源进行排序，按序申请资源。这个实现非常简单，我们假设每个账户都有不同的属性 id，这个 id 可以作为排序字段，申请的时候，我们可以按照从小到大的顺序来申请。比如下面代码中，①~⑥处的代码对转出账户（this）和转入账户（target）排序，然后按照序号从小到大的顺序锁定账户。这样就不存在“循环”等待了。

class Account {
private int id;
private int balance;
// 转账
void transfer(Account target, int amt){
  Account left = this        ①
  Account right = target;    ②
  if (this.id > target.id) { ③
    left = target;           ④
    right = this;            ⑤
  }                          ⑥
  // 锁定序号小的账户
  synchronized(left){
    // 锁定序号大的账户
    synchronized(right){ 
      if (this.balance > amt){
        this.balance -= amt;
        target.balance += amt;
      }
    }
  }
} 
}

前面采用死循环等待while(!actr.apply(this, target))的方式破坏且占用等待条件，如果apply比较耗时或者并发冲突量大的话，这种方案就不适用了。对于这种情况可以想到的一种方式就是等待–通知的机制
- 一个完整的等待 - 通知机制：线程首先获取互斥锁，当线程要求的条件不满足时，释放互斥锁，进入等待状态；当要求的条件满足时，通知等待的线程，重新获取互斥锁。
- 在Java中采用内置的synachronized配合wait、notify和notifyAll即可。
```
class Allocator {
  private List<Object> als;
  // 一次性申请所有资源
  synchronized void apply(
    Object from, Object to){
    // 经典写法
    while(als.contains(from) ||
        als.contains(to)){
      try{
        wait();
      }catch(Exception e){
      }   
    } 
    als.add(from);
    als.add(to);  
  }
  // 归还资源
  synchronized void free(
    Object from, Object to){
    als.remove(from);
    als.remove(to);
    notifyAll();
  }
}
```
- notify() 是会随机地通知等待队列中的一个线程，而 notifyAll() 会通知等待队列中的所有线程。使用notify的风险在于可能导致有的线程永远不会被通知到。所以建议尽量使用notifyAll()。
- 思考题：wait和sleep的区别？
活锁问题
- 各自等待一个随机时间，简单但非常有效。Raft这类分布式一致性算法也用到了该方法。
饥饿问题：线程因无法访问所需资源而无法执行下去的情况
- 线程之间是存在优先级的，如果CPU繁忙的情况下，优先级低的得到执行的机会很少，就有可能得不到分配机会一直处于等待的饥饿状态
- 一种常见的解决方案是：公平的分配资源。在并发编程中主要使用公平锁。即先来后到，线程等待是有顺序的，排在等待对垒前面的线程会优先获得资源。
锁的过度使用会导致串行化的范围过大，这样就有性能问题了。从方案层面，最好的方案就是使用无锁的算法和数据结构或者减少锁持有的时间(互斥锁的本质是将并行的程序串行化，所以要增加并行度，一定要减少持有锁的时间)。
管程，指的是管理共享变量以及对共享变量的操作过程，让他们支持并发。
- 计算机操作系统中对于管程有这段描述：
- 在利用管程实现进程同步时，当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上。仅当另一个进程访问完成并释放该资源后，管程才又调用signal原语，唤醒等待队列中的队首进程列+相应操作。。但是，考虑这样一种情况：当一个进程调用了管程后，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除；在此期间，如果该进程不释放管程，则其它进程就无法进入管程，被迫长时间等待。为了解决这个问题，引入条件变量condition。通常，一个进程被被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问智能在管程中进行。
- 理解起来，调用管程的进程，在管程中可能因为某些资源限制而被阻塞或挂起；为了不占用管程资源，同时又不能直接退出管程，就需要在管程中按照被阻塞或挂起的原因，分别挂到不同的等待队列上，而条件变量conditions就是分门别类的队

并发编程

并发编程

CATALOG

FEATURED TAGS

FRIENDS