[concurrency-interest] Idempotent work stealing (2009)

Doug Lea dl at cs.oswego.edu
Mon Dec 28 19:13:13 EST 2009


Kimo Crossman wrote:

> Idempotent work stealing (2009) ...

> This paper was interesting to me when it came out, both for the different
> approach taken for work stealing and for the emphasis on not using atomic
> instructions like CAS to improve speed..

As is briefly mentioned in the internal documentation
(http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166y/ForkJoinWorkerThread.java?view=log)
The current FJ work-stealing algorithm is similar to
one of those one by Maged Michael et al but uses one
bookkeeping CAS per task execution. This is needed to
aggressively null out queue slots to in turn ensure
executed tasks can be quickly GCed, but additionally
serves to avoid need for task state CAS upon running.
You would otherwise need that secondary CAS in the normal
case where tasks should not be run more than once.
If you don't need either of these features
(prompt GCability and at-most-once execution) then
their algorithm is likely faster, but this is too
uncommon a case to support in j.u.c.

> 
> (I'm surprised to not find a Search function for the archives of this list)
> 


(You can search the archives on http://concurrency.markmail.org/ .
But including "concurrency-interest" in google searches
is often at least as good because it also finds other things
that reference list discussions.)

-Doug




More information about the Concurrency-interest mailing list