taskqueue.hpp revision 342
6443N/A * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved. 6443N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 6443N/A * This code is free software; you can redistribute it and/or modify it 6443N/A * under the terms of the GNU General Public License version 2 only, as 6443N/A * published by the Free Software Foundation. 6443N/A * This code is distributed in the hope that it will be useful, but WITHOUT 6443N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 6443N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 6443N/A * version 2 for more details (a copy is included in the LICENSE file that 6443N/A * You should have received a copy of the GNU General Public License version 6443N/A * 2 along with this work; if not, write to the Free Software Foundation, 6443N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 6443N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 6443N/A * CA 95054 USA or visit www.sun.com if you need additional information or 6443N/A // The first free element after the last one pushed (mod _n). 6443N/A // (For now we'll assume only 32-bit CAS). 7097N/A // log2 of the size of the queue. 6443N/A // For computing "x mod n" efficiently. 6443N/A // These make sure we do single atomic reads and writes. 6443N/A // These both operate mod _n. 6443N/A // Returns a number in the range [0.._n). If the result is "n-1", it 6443N/A // should be interpreted as 0. 7097N/A // Returns the size corresponding to the given "bot" and "top". 6443N/A // Has the queue "wrapped", so that bottom is less than top? 6443N/A // There's a complicated special case here. A pair of threads could 6443N/A // perform pop_local and pop_global operations concurrently, starting 6443N/A // from a state in which _bottom == _top+1. The pop_local could 6443N/A // succeed in decrementing _bottom, and the pop_global in incrementing 7097N/A // _top (in which case the pop_global will be awarded the contested 6443N/A // queue element.) The resulting state must be interpreted as an empty 7097N/A // queue. (We only need to worry about one such event: only the queue 7097N/A // owner performs pop_local's, and several concurrent threads 7097N/A // attempting to perform the pop_global will all perform the same CAS, 7097N/A // and only one can succeed. Any stealing thread that reads after 7097N/A // either the increment or decrement will seen an empty queue, and will 7097N/A // not join the competitors. The "sz == -1 || sz == _n-1" state will 7097N/A // not be modified by concurrent queues, so the owner thread can reset 7097N/A // the state to _bottom == top so subsequent pushes will be performed 6443N/A // Return "true" if the TaskQueue contains any tasks. 7097N/A // Return an estimate of the number of elements in the queue. 7097N/A // Maximum number of elements allowed in the queue. This is two less 7097N/A // than the actual queue size, for somewhat complicated reasons. 6443N/A // Slow paths for push, pop_local. (pop_global has no fast path.) 7097N/A // Initializes the queue to empty. 7097N/A // Push the task "t" on the queue. Returns "false" iff the queue is 7097N/A // If succeeds in claiming a task (from the 'local' end, that is, the 7097N/A // most recently pushed task), returns "true" and sets "t" to that task. 7097N/A // Otherwise, the queue is empty and returns false. 7097N/A // If succeeds in claiming a task (from the 'global' end, that is, the 7097N/A // least recently pushed task), returns "true" and sets "t" to that task. 7097N/A // Otherwise, the queue is empty and returns false. 6443N/A // Delete any resource associated with the queue. 7097N/A // apply the closure to all elements in the task queue // tty->print_cr("START OopTaskQueue::oops_do"); for (
int i = 0; i <
iters; ++i) {
// tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, // index, &_elems[index], _elems[index]); // tty->print_cr("END OopTaskQueue::oops_do"); // Actually means 0, so do the push. // This queue was observed to contain exactly one element; either this // thread will claim it, or a competing "pop_global". In either case, // the queue will be logically empty afterwards. Create a new Age value // that represents the empty queue for the given value of "_bottom". (We // must also increment "tag" because of the case where "bottom == 1", // "top == 0". A pop_global could read the queue element in that case, // then have the owner thread do a pop followed by another push. Without // the incrementing of "tag", the pop_global's CAS could succeed, // allowing it to believe it has claimed the stale element.) // Perhaps a competing pop_global has already incremented "top", in which // case it wins the element. // No competing pop_global has yet incremented "top"; we'll try to // install new_age, thus claiming the element. "Assumption about CAS unit.");
"Shouldn't be possible...");
// We fail; a completing pop_global gets the element. But the queue is // empty (and top is greater than bottom.) Fix this representation of // the empty queue to become the canonical one. "Shouldn't be possible...");
// Note that using "_bottom" here might fail, since a pop_local might "Shouldn't be possible...");
// Inherits the typedef of "Task" from above. // Returns "true" if some TaskQueue in the set contains a task. for (
int i = 0; i < n; i++) {
// The thread with queue number "queue_num" (and whose random number seed // is at "seed") is trying to steal a task from some other queue. (It // may try several queues, according to some configuration parameter.) // If some steal succeeds, returns "true" and sets "t" the stolen task, // otherwise returns false. assert(0 <= i && i <
_n,
"index out of range.");
for (
int i = 0; i <
2 *
_n; i++)
for (
int k = 0; k <
_n; k++) {
// Just try the other one. // Just try the other one. // Sample both and try the larger. // Just try the other one. for (
int j = 0; j <
_n; j++) {
// When to terminate from the termination protocol. // A class to aid in the termination of a set of parallel tasks using // TaskQueueSet's for work stealing. // "n_threads" is the number of threads to be terminated. "queue_set" is a // queue sets of work queues of other threads. // The current thread has no work, and is ready to terminate if everyone // else is. If returns "true", all threads are terminated. If returns // "false", available work has been observed in one of the task queues, // so the global task is not complete. // As above, but it also terminates of the should_exit_termination() // method of the terminator parameter returns true. If terminator is // NULL, then it is ignored. // Reset the terminator, so that it may be reused again. // The caller is responsible for ensuring that this is done // in an MT-safe manner, once the previous round of use of // the terminator is finished. "n_elems out of range.");
// This value cannot be n-1. That can only occur as a result of // the assignment to bottom in this method. If it does, this method // resets the size( to 0 before the next call (which is sequential, // since this is pop_local.) // This is necessary to prevent any read below from being reordered // before the store just above. // This is a second read of "age"; the "size()" above is the first. // If there's still at least one element in the queue, based on the // "_bottom" and "age" we've read, then there can be no interference with // a "pop_global" operation, and we're done. "Shouldn't be possible...");
// Otherwise, the queue contained exactly one element; we take the slow // This is a container class for either an oop* or a narrowOop*. // Both are pushed onto a task queue and the consumer will test is_narrow() // to determine which should be processed. void*
_holder;
// either union oop* or narrowOop* // Operators to preserve const/volatile in assignments required by gcc // Initialize both stealable queue and overflow // Save first to stealable queue and then to overflow // Retrieve first from overflow and then from stealable queue // Retrieve from stealable queue // Retrieve from overflow