# HG changeset patch
# User tschatzl
# Date 1377073922 -7200
# Node ID 61521bd65100c37347c8d551d38bc4fabfa262e0
# Parent  31f220c1f78914a63f079a12d047ccefb8480bb2
8022784: TaskQueue misses minimal documentation and references for analysis
Summary: Add appropriate documentation and references to publication to allow easier analysis of the TaskQueue implementation.
Reviewed-by: dholmes, ehelin

diff -r 31f220c1f789 -r 61521bd65100 src/share/vm/utilities/taskqueue.hpp
--- a/src/share/vm/utilities/taskqueue.hpp	Tue Aug 20 10:02:38 2013 -0700
+++ b/src/share/vm/utilities/taskqueue.hpp	Wed Aug 21 10:32:02 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2001, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -132,6 +132,8 @@
 }
 #endif // TASKQUEUE_STATS
 
+// TaskQueueSuper collects functionality common to all GenericTaskQueue instances.
+
 template <unsigned int N, MEMFLAGS F>
 class TaskQueueSuper: public CHeapObj<F> {
 protected:
@@ -249,7 +251,36 @@
   TASKQUEUE_STATS_ONLY(TaskQueueStats stats;)
 };
 
-
+//
+// GenericTaskQueue implements an ABP, Aurora-Blumofe-Plaxton, double-
+// ended-queue (deque), intended for use in work stealing. Queue operations
+// are non-blocking.
+//
+// A queue owner thread performs push() and pop_local() operations on one end
+// of the queue, while other threads may steal work using the pop_global()
+// method.
+//
+// The main difference to the original algorithm is that this
+// implementation allows wrap-around at the end of its allocated
+// storage, which is an array.
+//
+// The original paper is:
+//
+// Arora, N. S., Blumofe, R. D., and Plaxton, C. G.
+// Thread scheduling for multiprogrammed multiprocessors.
+// Theory of Computing Systems 34, 2 (2001), 115-144.
+//
+// The following paper provides an correctness proof and an
+// implementation for weakly ordered memory models including (pseudo-)
+// code containing memory barriers for a Chase-Lev deque. Chase-Lev is
+// similar to ABP, with the main difference that it allows resizing of the
+// underlying storage:
+//
+// Le, N. M., Pop, A., Cohen A., and Nardell, F. Z.
+// Correct and efficient work-stealing for weak memory models
+// Proceedings of the 18th ACM SIGPLAN symposium on Principles and
+// practice of parallel programming (PPoPP 2013), 69-80
+//
 
 template <class E, MEMFLAGS F, unsigned int N = TASKQUEUE_SIZE>
 class GenericTaskQueue: public TaskQueueSuper<N, F> {