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