taskqueue.hpp revision 1472
7321N/A * Copyright (c) 2001, 2009, Oracle and/or its affiliates. All rights reserved. 7321N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 7321N/A * This code is free software; you can redistribute it and/or modify it 7321N/A * under the terms of the GNU General Public License version 2 only, as 7321N/A * published by the Free Software Foundation. 7321N/A * This code is distributed in the hope that it will be useful, but WITHOUT 7321N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 7321N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 7321N/A * version 2 for more details (a copy is included in the LICENSE file that 7321N/A * You should have received a copy of the GNU General Public License version 7321N/A * 2 along with this work; if not, write to the Free Software Foundation, 7321N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 7321N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 7321N/A // Internal type for indexing the queue; also used for the tag. 7321N/A // The first free element after the last one pushed (mod N). 7321N/A // Increment top; if it wraps, increment tag also. 7321N/A // These both operate mod N. 7321N/A // Returns a number in the range [0..N). If the result is "N-1", it should be 7321N/A // Returns the size corresponding to the given "bot" and "top". 7321N/A // Has the queue "wrapped", so that bottom is less than top? There's a 7321N/A // complicated special case here. A pair of threads could perform pop_local 7321N/A // and pop_global operations concurrently, starting from a state in which 7321N/A // _bottom == _top+1. The pop_local could succeed in decrementing _bottom, 7321N/A // and the pop_global in incrementing _top (in which case the pop_global 7321N/A // will be awarded the contested queue element.) The resulting state must 7321N/A // be interpreted as an empty queue. (We only need to worry about one such 7321N/A // event: only the queue owner performs pop_local's, and several concurrent 7321N/A // threads attempting to perform the pop_global will all perform the same 7321N/A // CAS, and only one can succeed.) Any stealing thread that reads after 7321N/A // either the increment or decrement will see an empty queue, and will not 7321N/A // join the competitors. The "sz == -1 || sz == N-1" state will not be 7321N/A // modified by concurrent queues, so the owner thread can reset the state to 7321N/A // _bottom == top so subsequent pushes will be performed normally. 7321N/A // Return true if the TaskQueue contains any tasks. 7321N/A // Return an estimate of the number of elements in the queue. 7321N/A // Maximum number of elements allowed in the queue. This is two less 7321N/A // than the actual queue size, for somewhat complicated reasons. 7321N/A // Slow paths for push, pop_local. (pop_global has no fast path.) 7321N/A // Initializes the queue to empty. 7321N/A // Push the task "t" on the queue. Returns "false" iff the queue is 7321N/A // If succeeds in claiming a task (from the 'local' end, that is, the 7321N/A // most recently pushed task), returns "true" and sets "t" to that task. 7321N/A // Otherwise, the queue is empty and returns false. 7321N/A // If succeeds in claiming a task (from the 'global' end, that is, the 7321N/A // least recently pushed task), returns "true" and sets "t" to that task. 7321N/A // Otherwise, the queue is empty and returns false. 7321N/A // Delete any resource associated with the queue. 7321N/A // apply the closure to all elements in the task queue 7321N/Atemplate<
class E,
unsigned int N>
7321N/Atemplate<
class E,
unsigned int N>
7321N/Atemplate<
class E,
unsigned int N>
7321N/A // tty->print_cr("START OopTaskQueue::oops_do"); 7321N/A // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, 7321N/A // index, &_elems[index], _elems[index]); 7321N/A // tty->print_cr("END OopTaskQueue::oops_do"); 7321N/Atemplate<
class E,
unsigned int N>
7321N/A // Actually means 0, so do the push. 7321N/A // g++ complains if the volatile result of the assignment is unused. 7321N/Atemplate<
class E,
unsigned int N>
7321N/A // This queue was observed to contain exactly one element; either this 7321N/A // thread will claim it, or a competing "pop_global". In either case, 7321N/A // the queue will be logically empty afterwards. Create a new Age value 7321N/A // that represents the empty queue for the given value of "_bottom". (We 7321N/A // must also increment "tag" because of the case where "bottom == 1", 7321N/A // "top == 0". A pop_global could read the queue element in that case, 7321N/A // then have the owner thread do a pop followed by another push. Without 7321N/A // the incrementing of "tag", the pop_global's CAS could succeed, 7321N/A // allowing it to believe it has claimed the stale element.) 7321N/A // Perhaps a competing pop_global has already incremented "top", in which 7321N/A // case it wins the element. 7321N/A // No competing pop_global has yet incremented "top"; we'll try to 7321N/A // install new_age, thus claiming the element. 7321N/A // We lose; a completing pop_global gets the element. But the queue is empty 7321N/A // and top is greater than bottom. Fix this representation of the empty queue 7321N/A // to become the canonical one. 7321N/Atemplate<
class E,
unsigned int N>
7321N/A // Note that using "_bottom" here might fail, since a pop_local might 7321N/Atemplate<
class E,
unsigned int N>
7321N/A// Inherits the typedef of "Task" from above. 7321N/A // 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. for (
uint i = 0; i <
2 *
_n; i++)
for (
uint 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 (
uint 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 if 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. template<
class E,
unsigned int N>
inline bool // g++ complains if the volatile result of the assignment is unused. template<
class E,
unsigned int N>
inline bool // 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. // Otherwise, the queue contained exactly one element; we take the slow // warning C4522: multiple assignment operators specified // 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* // 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