taskqueue.hpp revision 113
0N/A * Copyright 2001-2006 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. 0N/A // The first free element after the last one pushed (mod _n). 0N/A // (For now we'll assume only 32-bit CAS). 0N/A // log2 of the size of the queue. 0N/A // Size of the queue. 0N/A // For computing "x mod n" efficiently. 0N/A // These make sure we do single atomic reads and writes. 0N/A // These both operate mod _n. 0N/A // Returns a number in the range [0.._n). If the result is "n-1", it 0N/A // should be interpreted as 0. 0N/A // Returns the size corresponding to the given "bot" and "top". 0N/A // Has the queue "wrapped", so that bottom is less than top? 0N/A // There's a complicated special case here. A pair of threads could 0N/A // perform pop_local and pop_global operations concurrently, starting 0N/A // from a state in which _bottom == _top+1. The pop_local could 0N/A // succeed in decrementing _bottom, and the pop_global in incrementing 0N/A // _top (in which case the pop_global will be awarded the contested 0N/A // queue element.) The resulting state must be interpreted as an empty 0N/A // queue. (We only need to worry about one such event: only the queue 0N/A // owner performs pop_local's, and several concurrent threads 0N/A // attempting to perform the pop_global will all perform the same CAS, 0N/A // and only one can succeed. Any stealing thread that reads after 0N/A // either the increment or decrement will seen an empty queue, and will 0N/A // not join the competitors. The "sz == -1 || sz == _n-1" state will 0N/A // not be modified by concurrent queues, so the owner thread can reset 0N/A // the state to _bottom == top so subsequent pushes will be performed 0N/A if (
sz == (n()-
1))
return 0;
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. 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. 0N/A "Assumption about CAS unit.");
0N/A "Shouldn't be possible...");
0N/A // We fail; a completing pop_global gets the element. But the queue is 0N/A // empty (and top is greater than bottom.) Fix this representation of 0N/A // the empty queue to become the canonical one. 0N/A "Shouldn't be possible...");
0N/A // Note that using "_bottom" here might fail, since a pop_local might 0N/A // have decremented it. 0N/A "Shouldn't be possible...");
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 for (
int i = 0; i <
2 *
_n; i++)
0N/A for (
int k = 0; k <
_n; k++) {
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. 0N/A for (
int j = 0; j <
_n; j++) {
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. 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. 0N/A "n_elems out of range.");
0N/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 "Shouldn't be possible...");
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