Fork Join 工作窃取队列

不积跬步,无以至千里。不积小流,无以成江海。

简介

它并非使用 BlockingQueue,而是基于一个普通的数组得以实现。

所谓工作窃取算法,是指一个 Worker 线程在执行完毕自己队列中的任务之后,可以窃取其他线程队列中的任务来执行,从而实现负载均衡,以防有的线程很空闲,有的线程很忙。这个过程要用到工作窃取队列。

如何工作的

1、Worker 线程自己,在队列头部,通过对 queueTop 指针执行加、减操作,实现入队或出队,这是单线程的。

2、其他 Worker 线程,在队列尾部,通过对 queueBase 进行累加,实现出队操作,也就是窃取,这是多线程的,需要通过 CAS 操作。

注意:queueTop 不是 volatile 类型,queueBase 是 volatile 类型。

特点

  • 整个队列是环形的,也就是一个数组实现的 RingBuffer。并且 queueBase 会一直累加,不会减小;queueTop 会累加、减小。最后,queueBase、queueTop 的值都会大于整个数组的长度,只是计算数组下标的时候,会取 queueTop&(queue.length-1),queueBase&(queue.length-1)。因为 queue.length 是2的整数次方,这里也就是对 queue.length 进行取模操作。

当 queueTop-queueBase=queue.length-1 的时候,队列为满,此时需要扩容;

当 queueTop=queueBase 的时候,队列为空,Worker 线程即将进入阻塞状态。

  • 当队列满了之后会扩容,所以被称为是动态的。

扩容

在 queueBase 一端,是多线程访问的,但它们只会使 queueBase 变大,也就是使队列中的元素变少。所以队列为满,一定发生在 queueTop 一端,对 queueTop 进行累加的时候,这一端却是单线程的!队列的扩容恰好利用了这个单线程的特性!即在扩容过程中,不可能有其他线程对 queueTop 进行修改,只有线程对 queueBase 进行修改!