Mon, 09 Mar 2009 13:28:46 -0700
6814575: Update copyright year
Summary: Update copyright for files that have been modified in 2009, up to 03/09
Reviewed-by: katleman, tbell, ohair
1 /*
2 * Copyright 2001-2009 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
25 # include "incls/_precompiled.incl"
26 # include "incls/_taskqueue.cpp.incl"
28 #ifdef TRACESPINNING
29 uint ParallelTaskTerminator::_total_yields = 0;
30 uint ParallelTaskTerminator::_total_spins = 0;
31 uint ParallelTaskTerminator::_total_peeks = 0;
32 #endif
34 bool TaskQueueSuper::peek() {
35 return _bottom != _age.top();
36 }
38 int TaskQueueSetSuper::randomParkAndMiller(int *seed0) {
39 const int a = 16807;
40 const int m = 2147483647;
41 const int q = 127773; /* m div a */
42 const int r = 2836; /* m mod a */
43 assert(sizeof(int) == 4, "I think this relies on that");
44 int seed = *seed0;
45 int hi = seed / q;
46 int lo = seed % q;
47 int test = a * lo - r * hi;
48 if (test > 0)
49 seed = test;
50 else
51 seed = test + m;
52 *seed0 = seed;
53 return seed;
54 }
56 ParallelTaskTerminator::
57 ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set) :
58 _n_threads(n_threads),
59 _queue_set(queue_set),
60 _offered_termination(0) {}
62 bool ParallelTaskTerminator::peek_in_queue_set() {
63 return _queue_set->peek();
64 }
66 void ParallelTaskTerminator::yield() {
67 os::yield();
68 }
70 void ParallelTaskTerminator::sleep(uint millis) {
71 os::sleep(Thread::current(), millis, false);
72 }
74 bool
75 ParallelTaskTerminator::offer_termination(TerminatorTerminator* terminator) {
76 Atomic::inc(&_offered_termination);
78 uint yield_count = 0;
79 // Number of hard spin loops done since last yield
80 uint hard_spin_count = 0;
81 // Number of iterations in the hard spin loop.
82 uint hard_spin_limit = WorkStealingHardSpins;
84 // If WorkStealingSpinToYieldRatio is 0, no hard spinning is done.
85 // If it is greater than 0, then start with a small number
86 // of spins and increase number with each turn at spinning until
87 // the count of hard spins exceeds WorkStealingSpinToYieldRatio.
88 // Then do a yield() call and start spinning afresh.
89 if (WorkStealingSpinToYieldRatio > 0) {
90 hard_spin_limit = WorkStealingHardSpins >> WorkStealingSpinToYieldRatio;
91 hard_spin_limit = MAX2(hard_spin_limit, 1U);
92 }
93 // Remember the initial spin limit.
94 uint hard_spin_start = hard_spin_limit;
96 // Loop waiting for all threads to offer termination or
97 // more work.
98 while (true) {
99 // Are all threads offering termination?
100 if (_offered_termination == _n_threads) {
101 return true;
102 } else {
103 // Look for more work.
104 // Periodically sleep() instead of yield() to give threads
105 // waiting on the cores the chance to grab this code
106 if (yield_count <= WorkStealingYieldsBeforeSleep) {
107 // Do a yield or hardspin. For purposes of deciding whether
108 // to sleep, count this as a yield.
109 yield_count++;
111 // Periodically call yield() instead spinning
112 // After WorkStealingSpinToYieldRatio spins, do a yield() call
113 // and reset the counts and starting limit.
114 if (hard_spin_count > WorkStealingSpinToYieldRatio) {
115 yield();
116 hard_spin_count = 0;
117 hard_spin_limit = hard_spin_start;
118 #ifdef TRACESPINNING
119 _total_yields++;
120 #endif
121 } else {
122 // Hard spin this time
123 // Increase the hard spinning period but only up to a limit.
124 hard_spin_limit = MIN2(2*hard_spin_limit,
125 (uint) WorkStealingHardSpins);
126 for (uint j = 0; j < hard_spin_limit; j++) {
127 SpinPause();
128 }
129 hard_spin_count++;
130 #ifdef TRACESPINNING
131 _total_spins++;
132 #endif
133 }
134 } else {
135 if (PrintGCDetails && Verbose) {
136 gclog_or_tty->print_cr("ParallelTaskTerminator::offer_termination() "
137 "thread %d sleeps after %d yields",
138 Thread::current(), yield_count);
139 }
140 yield_count = 0;
141 // A sleep will cause this processor to seek work on another processor's
142 // runqueue, if it has nothing else to run (as opposed to the yield
143 // which may only move the thread to the end of the this processor's
144 // runqueue).
145 sleep(WorkStealingSleepMillis);
146 }
148 #ifdef TRACESPINNING
149 _total_peeks++;
150 #endif
151 if (peek_in_queue_set() ||
152 (terminator != NULL && terminator->should_exit_termination())) {
153 Atomic::dec(&_offered_termination);
154 return false;
155 }
156 }
157 }
158 }
160 #ifdef TRACESPINNING
161 void ParallelTaskTerminator::print_termination_counts() {
162 gclog_or_tty->print_cr("ParallelTaskTerminator Total yields: %lld "
163 "Total spins: %lld Total peeks: %lld",
164 total_yields(),
165 total_spins(),
166 total_peeks());
167 }
168 #endif
170 void ParallelTaskTerminator::reset_for_reuse() {
171 if (_offered_termination != 0) {
172 assert(_offered_termination == _n_threads,
173 "Terminator may still be in use");
174 _offered_termination = 0;
175 }
176 }
178 bool RegionTaskQueueWithOverflow::is_empty() {
179 return (_region_queue.size() == 0) &&
180 (_overflow_stack->length() == 0);
181 }
183 bool RegionTaskQueueWithOverflow::stealable_is_empty() {
184 return _region_queue.size() == 0;
185 }
187 bool RegionTaskQueueWithOverflow::overflow_is_empty() {
188 return _overflow_stack->length() == 0;
189 }
191 void RegionTaskQueueWithOverflow::initialize() {
192 _region_queue.initialize();
193 assert(_overflow_stack == 0, "Creating memory leak");
194 _overflow_stack =
195 new (ResourceObj::C_HEAP) GrowableArray<RegionTask>(10, true);
196 }
198 void RegionTaskQueueWithOverflow::save(RegionTask t) {
199 if (TraceRegionTasksQueuing && Verbose) {
200 gclog_or_tty->print_cr("CTQ: save " PTR_FORMAT, t);
201 }
202 if(!_region_queue.push(t)) {
203 _overflow_stack->push(t);
204 }
205 }
207 // Note that using this method will retrieve all regions
208 // that have been saved but that it will always check
209 // the overflow stack. It may be more efficient to
210 // check the stealable queue and the overflow stack
211 // separately.
212 bool RegionTaskQueueWithOverflow::retrieve(RegionTask& region_task) {
213 bool result = retrieve_from_overflow(region_task);
214 if (!result) {
215 result = retrieve_from_stealable_queue(region_task);
216 }
217 if (TraceRegionTasksQueuing && Verbose && result) {
218 gclog_or_tty->print_cr(" CTQ: retrieve " PTR_FORMAT, result);
219 }
220 return result;
221 }
223 bool RegionTaskQueueWithOverflow::retrieve_from_stealable_queue(
224 RegionTask& region_task) {
225 bool result = _region_queue.pop_local(region_task);
226 if (TraceRegionTasksQueuing && Verbose) {
227 gclog_or_tty->print_cr("CTQ: retrieve_stealable " PTR_FORMAT, region_task);
228 }
229 return result;
230 }
232 bool
233 RegionTaskQueueWithOverflow::retrieve_from_overflow(RegionTask& region_task) {
234 bool result;
235 if (!_overflow_stack->is_empty()) {
236 region_task = _overflow_stack->pop();
237 result = true;
238 } else {
239 region_task = (RegionTask) NULL;
240 result = false;
241 }
242 if (TraceRegionTasksQueuing && Verbose) {
243 gclog_or_tty->print_cr("CTQ: retrieve_stealable " PTR_FORMAT, region_task);
244 }
245 return result;
246 }