【16】并发中的饥饿问题以及公平性
【16】并发中的饥饿问题以及公平性
秋雨霏霏 发表于3个月前
【16】并发中的饥饿问题以及公平性
  • 发表于 3个月前
  • 阅读 37
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: Jakob Jenkov 并发指南翻译:Starvation and Fairness

> 如果某个线程因为所需要的资源被其他线程占用而得不到CPU调度,那这种情况就被称之为“饥饿”。 > 如果其他线程一直占用资源,那饥饿的线程就会被“饿死”(类似死锁的情况,一直在阻塞等待某个资源,或者运气比较差,每次都没有抢到)。 > 解决饥饿问题,通常使用“公平”策略,来保障所有的线程都有机会被CPU调度。

Java中的饥饿问题

> 在Java中,通常有以下几种情况导致饥饿: > 1. CPU被高优先级的线程完全占用(打满),而导致低优先级的线程一直没有机会获得CPU > 2. synchronized同步块导致某个线程频繁重入(偏向锁,以及OS调度策略,导致已经获得monitor锁的线程有更多的机会再次获得锁),而导致其他线程只能阻塞等待 > 3. 某个线程在某个对象的条件队列上等待(wait()),而其他线程不断的抢入

优先级导致的饥饿问题

> 可以为每个线程单独设置一个优先级。 > 高优先级的线程可以获得更多CPU时间。 > 在Java中可以设置1~10个等级的优先级。 > 实际上,这个优先级等级依赖于具体的操作系统。 > 对于一般应用来说,保持默认的优先级,就可以了。

同步锁等待导致的饥饿问题

> Java中的synchronized块也会导致饥饿问题。 > Java的synchronized并不保障等待线程的顺序(锁释放后,随机竞争,情况比较复杂,和OS调度有关)。 > 这就会存在一种可能,某个线程运气极差,每次抢锁都没抢到。 > 而且新的线程还在不断地进入等锁的队列,从而导致这个线程就几乎是一直处于等待中。 > 这就使得这个“悲催”的线程就处于“饥饿”中,而且还会悲惨的“饿死”。

条件队列导致的饥饿问题

> 我们知道notify()方法会唤醒对象条件队列中等待的某个线程,但是,可惜这个唤醒是无序的(和VM调度,OS调度有关,甚至底层是随机选取一个,更甚至就是队列中的第一个)。 > 而如果,条件队列不断有新的线程进入,或者在唤醒的那一刻,刚好有其他线程抢入,那都可能导致某个运气不好的线程迟迟不能被唤醒。 > 对这个线程来说,就是进入一种“饥饿”的状态,甚至还会有“饿死”的风险。

Java中的公平性

> 首先,要明确一点。在Java中要想做到100%的公平性基本是不可能的(VM,OS都会有自己的调度策略;抢入等情况也会导致不同的情况发生),所以,我们只能说尽可能的提高同步机制中线程之间的公平性。

> 来看一个简单的同步块代码示例:

public class Synchronizer{

  public synchronized void doSynchronized(){
    //do a lot of work which takes a long time
  }

}

> 如果有多个线程调用doSynchronized()方法,没有获得monitor锁的线程就会进入阻塞等待。 > 但是阻塞等待的线程谁会成为下一个获得锁的线程,这谁也说不准。

使用显式Lock锁替代synchronized内部锁

> 对于Java的synchronized实际上是一个内部的monitor锁。对于这个内部锁,我们无法做更多的控制(不过也有一个好处,不用手动释放锁)。 > 而如果想要对于锁进行更多更细节的控制,则可以使用Lock类。例如:

public class Synchronizer{
  Lock lock = new Lock();

  public void doSynchronized() throws InterruptedException{
    this.lock.lock();
      //critical section, do a lot of work which takes a long time
    this.lock.unlock();
  }

}

> 可以看到,doSynchronized()方法上没有再使用synchronized关键字了。而是使用了Lock,不过要注意一定要记得释放锁(这个只是个简单的例子,实际使用中应该使用finally来释放锁)。

> Lock是一个接口,Java提供了几种实现。不过,我们可以先自己来个简单的时间。例如:

public class Lock{
  private boolean isLocked      = false;
  private Thread  lockingThread = null;

  public synchronized void lock() throws InterruptedException{
    while(isLocked){
      wait();
    }
    isLocked      = true;
    lockingThread = Thread.currentThread();
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "Calling thread has not locked this lock");
    }
    isLocked      = false;
    lockingThread = null;
    notify();
  }
}

> 可以看到,上例的实现中lock()方法,如果同时有多个线程访问,只会有一个线程可以获得锁,而其他线程会阻塞,并进入Lock实例对象的条件队列。 > 另外,要注意lock()方法使用了一个信号通知的标准范式(最后补充中会提到)。 > 这种实现,其实是将锁等待转换成了Lock实例对象的条件等待(等待转移)。不过,这个实现是可以完成加锁/解锁/等待等功能。

(不过,还是要记住这只是个简单的示例,有些问题进行了简化。比如,Lock的条件队列不仅仅是给`isLocked`的条件谓词使用的,也就是说外部其他线程也可以直接调用Lock实例对象的`wait()`方法。)

> 我们再回头看看doSynchronized()方法,要注意,doSynchronized()加锁之后,会执行一个非常耗时的逻辑,然后才会释放锁。 > 这就意味这,锁等待的时间可能会非常长。

> 前面也介绍过同步块的等待顺序是无法保障的。而notify()也是无法保障唤醒顺序的。 > 因此,这个Lock实现是一个无法保障顺序的非公平锁。

公平锁

> 接下来,我们把Lock改造成一个公平锁。 > 主要是针对同步策略以及wait()/notify()的使用上。

> 这里会使用几个知识点: > - 嵌套监控器锁失效 > - 条件失效 > - 信号丢失

> 我们让lock()方法变为排队进入,只有第一个线程可以获得锁,当第一个线程释放锁后,后续的线程按照到达的顺序来依次获得锁。

public class FairLock {
    private boolean           isLocked       = false;
    private Thread            lockingThread  = null;
    private List<QueueObject> waitingThreads =
            new ArrayList<QueueObject>();

  public void lock() throws InterruptedException{
    QueueObject queueObject           = new QueueObject();
    boolean     isLockedForThisThread = true;
    synchronized(this){
        waitingThreads.add(queueObject);
    }

    while(isLockedForThisThread){
      synchronized(this){
        isLockedForThisThread =
            isLocked || waitingThreads.get(0) != queueObject;
        if(!isLockedForThisThread){
          isLocked = true;
           waitingThreads.remove(queueObject);
           lockingThread = Thread.currentThread();
           return;
         }
      }
      try{
        queueObject.doWait();
      }catch(InterruptedException e){
        synchronized(this) { waitingThreads.remove(queueObject); }
        throw e;
      }
    }
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "Calling thread has not locked this lock");
    }
    isLocked      = false;
    lockingThread = null;
    if(waitingThreads.size() > 0){
      waitingThreads.get(0).doNotify();
    }
  }
}
public class QueueObject {

  private boolean isNotified = false;

  public synchronized void doWait() throws InterruptedException {
    while(!isNotified){
        this.wait();
    }
    this.isNotified = false;
  }

  public synchronized void doNotify() {
    this.isNotified = true;
    this.notify();
  }

  public boolean equals(Object o) {
    return this == o;
  }
}

> 首先,可以看到lock()方法不再直接使用synchronized。 > 而是只在有必要的地方使用内部synchronized代码块。

> FairLock会让每一次调用lock(),创建一个QueueObject对象,并放入队列中。通过QueueObject对象来完成wait()/notify()。而且这样,由于QueueObject上等待的,只有创建这个对象的线程,所以唤醒时不存在公平性的问题。 > 而多个QueueObject会进入一个有序的集合,这样FairLock就实现了公平锁的特征。

> 有一点要注意,所有有关锁的状态(isLockedlockingThread)的判断都是在同一个synchronized块中,这样避免了条件失效的问题。

> 另外,QueueObject作为一个信号使用,它的doWait()doNotify()方法完成信号机制。 > 这里doWait()方法,也是使用了一个信号处理范式来避免信号丢失问题。

> 最后,注意queueObject.doWait()方法是需要在一个try - catch块中使用。 > 当InterruptedException异常时(锁等待的线程被中断了),能够将对应的QueueObject移出队列。这一步,很重要。否则,队列中第一个QueueObject是一个已经废弃的等待,那就导致这个锁没有机会得到释放。

性能问题

> 从上面的代码,就能看出公平锁要比一个非公平锁要复杂的多。这也会导致公平锁的性能比较低。 > 在使用时,需要考虑临界区中任务逻辑执行的时间,是否值得使用公平锁。 > 另外,还要考虑竞争的激烈程度,是否需要使用公平锁。


补充几点

  • 条件队列(信号处理)的使用范式
synchronized(lock){
    while ( !conditionPredicate() )
        lock.wait();
}
  • 公平/非公平几点对比

    • 非公平
      • 默认
      • 吞吐量好
      • 各线程表现差异大
      • 闯入锁
        • 让闯入者获得锁继续运行,比唤醒等待线程,再让等待线程开始工作要快的多
    • 公平
      • 伸缩性好
      • 因挂起/重新开始线程的代价带了巨大的性能开销
        • 为了维护等待线程的公平调度
  • 显式锁使用时的注意事项

    • Lock 的实现必须提供具有与内部加锁(monitor)相同的内存可见性的语义
    • 需要确保显式的释放锁
      • finally
    • Java 6 引入偏向锁,平均来说和内部锁的优势不再那么的大了,但在极端情况下仍然占有一定的优势
    • 在Java 5 中,线程转储无法体现
    • 难以被JIT优化
      • 锁省略
      • 粗化锁
标签: 并发 公平锁 饥饿
共有 人打赏支持
粉丝 114
博文 75
码字总数 138343
×
秋雨霏霏
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: