Java Fork/Join 协程

一、概览

        Fork/Join并行方式是获取良好的并行计算性能的一种最简单同时也是最有效的设计技术。Fork/Join并行算法是我们所熟悉的分治算法的并行版本,典型的用法如下:

Result solve(Problem problem) {
    if (problem is small) {
        directly solve problem
    } else {
        split problem into independent parts
        fork new subtasks to solve each part
        join all subtasks
        compose result from subresults
    }
}

        fork操作将会启动一个新的并行Fork/Join子任务。join操作会一直等待直到所有的子任务都结束。Fork/Join算法,如同其他分治算法一样,总是会递归的、反复的划分子任务,直到这些子任务可以用足够简单的、短小的顺序方法来执行。

下图来自:http://www.voidcn.com/article/p-nuusnhzd-d.html
这里写图片描述
        可以看出核心操作有以下几点:

  1. fork
  2. join
  3. 线程池

二、Fork

        将任务压入workQueue

public final ForkJoinTask<V> fork() {
        Thread t;
        if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
            ((ForkJoinWorkerThread)t).workQueue.push(this);
        else
            ForkJoinPool.common.externalPush(this);
        return this;
    }

三、Join

        等待任务结束或中断

public final V join() {
        int s;
        if ((s = doJoin() & DONE_MASK) != NORMAL)
            reportException(s);
        return getRawResult();
    }

四、线程池与work−stealing算法

这里写图片描述

  • 每一个工作线程维护自己的调度队列中的可运行任务。
  • 队列以双端队列的形式被维护(注:deques通常读作『decks』),不仅支持后进先出 —— LIFO的push和pop操作,还支持先进先出 —— FIFO的take操作。
  • 对于一个给定的工作线程来说,任务所产生的子任务将会被放入到工作者自己的双端队列中。
  • 工作线程使用后进先出 —— LIFO(最新的元素优先)的顺序,通过弹出任务来处理队列中的任务。
  • 当一个工作线程的本地没有任务去运行的时候,它将使用先进先出 —— FIFO的规则尝试随机的从别的工作线程中拿(『窃取』)一个任务去运行。
  • 当一个工作线程触及了join操作,如果可能的话它将处理其他任务,直到目标任务被告知已经结束(通过isDone方法)。所有的任务都会无阻塞的完成。
  • 当一个工作线程无法再从其他线程中获取任务和失败处理的时候,它就会退出(通过yield、sleep和/或者优先级调整,参考第3节)并经过一段时间之后再度尝试直到所有的工作线程都被告知他们都处于空闲的状态。在这种情况下,他们都会阻塞直到其他的任务再度被上层调用。
  • 使用后进先出 —— LIFO用来处理每个工作线程的自己任务,但是使用先进先出 —— FIFO规则用于获取别的任务,这是一种被广泛使用的进行递归Fork/Join设计的一种调优手段。引用[5]讨论了详细讨论了里面的细节。

        让窃取任务的线程从队列拥有者相反的方向进行操作会减少线程竞争。同样体现了递归分治算法的大任务优先策略。因此,更早期被窃取的任务有可能会提供一个更大的单元任务,从而使得窃取线程能够在将来进行递归分解。

        作为上述规则的一个后果,对于一些基础的操作而言,使用相对较小粒度的任务比那些仅仅使用粗粒度划分的任务以及那些没有使用递归分解的任务的运行速度要快。尽管相关的少数任务在大多数的Fork/Join框架中会被其他工作线程窃取,但是创建许多组织良好的任务意味着只要有一个工作线程处于可运行的状态,那么这个任务就有可能被执行。

Work-Stealing 的适用场景是不同的任务的耗时相差比较大,即某些任务需要运行较长时间,而某些任务会很快的运行完成,这种情况下用 Work-Stealing 很合适;但是如果任务的耗时很平均,则此时 Work-Stealing 并不适合,因为窃取任务时不同线程需要抢占锁,这可能会造成额外的时间消耗,而且每个线程维护双端队列也会造成更大的内存消耗。所以 ForkJoinPool 并不是 ThreadPoolExecutor 的替代品,而是作为对 ThreadPoolExecutor 的补充。

五、协程

        其实早在JDK1的时代,Java的线程被称为GreenThread,那个时候就已经有了Fiber,但是当时不能与操作系统实现N:M绑定,所以放弃了。现在Quasar凭借ForkJoinPool这个成熟的线程调度库。另外,如果你希望你的代码能够跑在Fiber里面,需要一个很大的前提条件,那就是你所有的库,必须是异步无阻塞的,也就说必须类似于node.js上的库,所有的逻辑都是异步回调,而自Java里基本上所有的库都是同步阻塞的,很少见到异步无阻塞的。而且得益于J2EE,以及Java上的三大框架(SSH)洗脑,大部分Java程序员都已经习惯了基于线程,线性的完成一个业务逻辑,很难让他们接受一种将逻辑割裂的异步编程模型。

        但是随着异步无阻塞这股风气起来,以及相关的coroutine语言Golang大力推广,人们越来越知道如何更好的榨干CPU性能(让CPU避免不必要的等待,减少上下文切换),阻塞的行为基本发生在I/O上,如果能有一个库能把所有的I/O行为都包装成异步阻塞的话,那么Quasar就会有用武之地,JVM上公认的是异步网络通信库是Netty,通过Netty基本解决了网络I/O问题,另外还有一个是文件I/O,而这个JDK7提供的NIO2就可以满足,通过AsynchronousFileChannel即可。剩下的就是如何将他们封装成更友好的API了。目前能达到生产级别的这种异步工具库,JVM上只有Vert.x3,封装了Netty4,封装了AsynchronousFileChannel,而且Vert.x官方也出了一个相对应的封装了Quasar的库vertx-sync。

本文参考:
Java Fork/Join 框架
次时代Java编程(一):Java里的协程
Java 多线程(5):Fork/Join 型线程池与 Work-Stealing 算法

个人微信公众号:
这里写图片描述

作者:jiankunking 出处:http://blog.csdn.net/jiankunking

相关文章
相关标签/搜索