Mon, 09 Aug 2010 17:51:56 -0700
Merge
1 /*
2 * Copyright (c) 2001, 2010, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * 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 #if TASKQUEUE_STATS
35 const char * const TaskQueueStats::_names[last_stat_id] = {
36 "qpush", "qpop", "qpop-s", "qattempt", "qsteal", "opush", "omax"
37 };
39 void TaskQueueStats::print_header(unsigned int line, outputStream* const stream,
40 unsigned int width)
41 {
42 // Use a width w: 1 <= w <= max_width
43 const unsigned int max_width = 40;
44 const unsigned int w = MAX2(MIN2(width, max_width), 1U);
46 if (line == 0) { // spaces equal in width to the header
47 const unsigned int hdr_width = w * last_stat_id + last_stat_id - 1;
48 stream->print("%*s", hdr_width, " ");
49 } else if (line == 1) { // labels
50 stream->print("%*s", w, _names[0]);
51 for (unsigned int i = 1; i < last_stat_id; ++i) {
52 stream->print(" %*s", w, _names[i]);
53 }
54 } else if (line == 2) { // dashed lines
55 char dashes[max_width + 1];
56 memset(dashes, '-', w);
57 dashes[w] = '\0';
58 stream->print("%s", dashes);
59 for (unsigned int i = 1; i < last_stat_id; ++i) {
60 stream->print(" %s", dashes);
61 }
62 }
63 }
65 void TaskQueueStats::print(outputStream* stream, unsigned int width) const
66 {
67 #define FMT SIZE_FORMAT_W(*)
68 stream->print(FMT, width, _stats[0]);
69 for (unsigned int i = 1; i < last_stat_id; ++i) {
70 stream->print(" " FMT, width, _stats[i]);
71 }
72 #undef FMT
73 }
74 #endif // TASKQUEUE_STATS
76 int TaskQueueSetSuper::randomParkAndMiller(int *seed0) {
77 const int a = 16807;
78 const int m = 2147483647;
79 const int q = 127773; /* m div a */
80 const int r = 2836; /* m mod a */
81 assert(sizeof(int) == 4, "I think this relies on that");
82 int seed = *seed0;
83 int hi = seed / q;
84 int lo = seed % q;
85 int test = a * lo - r * hi;
86 if (test > 0)
87 seed = test;
88 else
89 seed = test + m;
90 *seed0 = seed;
91 return seed;
92 }
94 ParallelTaskTerminator::
95 ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set) :
96 _n_threads(n_threads),
97 _queue_set(queue_set),
98 _offered_termination(0) {}
100 bool ParallelTaskTerminator::peek_in_queue_set() {
101 return _queue_set->peek();
102 }
104 void ParallelTaskTerminator::yield() {
105 assert(_offered_termination <= _n_threads, "Invariant");
106 os::yield();
107 }
109 void ParallelTaskTerminator::sleep(uint millis) {
110 assert(_offered_termination <= _n_threads, "Invariant");
111 os::sleep(Thread::current(), millis, false);
112 }
114 bool
115 ParallelTaskTerminator::offer_termination(TerminatorTerminator* terminator) {
116 assert(_offered_termination < _n_threads, "Invariant");
117 Atomic::inc(&_offered_termination);
119 uint yield_count = 0;
120 // Number of hard spin loops done since last yield
121 uint hard_spin_count = 0;
122 // Number of iterations in the hard spin loop.
123 uint hard_spin_limit = WorkStealingHardSpins;
125 // If WorkStealingSpinToYieldRatio is 0, no hard spinning is done.
126 // If it is greater than 0, then start with a small number
127 // of spins and increase number with each turn at spinning until
128 // the count of hard spins exceeds WorkStealingSpinToYieldRatio.
129 // Then do a yield() call and start spinning afresh.
130 if (WorkStealingSpinToYieldRatio > 0) {
131 hard_spin_limit = WorkStealingHardSpins >> WorkStealingSpinToYieldRatio;
132 hard_spin_limit = MAX2(hard_spin_limit, 1U);
133 }
134 // Remember the initial spin limit.
135 uint hard_spin_start = hard_spin_limit;
137 // Loop waiting for all threads to offer termination or
138 // more work.
139 while (true) {
140 assert(_offered_termination <= _n_threads, "Invariant");
141 // Are all threads offering termination?
142 if (_offered_termination == _n_threads) {
143 return true;
144 } else {
145 // Look for more work.
146 // Periodically sleep() instead of yield() to give threads
147 // waiting on the cores the chance to grab this code
148 if (yield_count <= WorkStealingYieldsBeforeSleep) {
149 // Do a yield or hardspin. For purposes of deciding whether
150 // to sleep, count this as a yield.
151 yield_count++;
153 // Periodically call yield() instead spinning
154 // After WorkStealingSpinToYieldRatio spins, do a yield() call
155 // and reset the counts and starting limit.
156 if (hard_spin_count > WorkStealingSpinToYieldRatio) {
157 yield();
158 hard_spin_count = 0;
159 hard_spin_limit = hard_spin_start;
160 #ifdef TRACESPINNING
161 _total_yields++;
162 #endif
163 } else {
164 // Hard spin this time
165 // Increase the hard spinning period but only up to a limit.
166 hard_spin_limit = MIN2(2*hard_spin_limit,
167 (uint) WorkStealingHardSpins);
168 for (uint j = 0; j < hard_spin_limit; j++) {
169 SpinPause();
170 }
171 hard_spin_count++;
172 #ifdef TRACESPINNING
173 _total_spins++;
174 #endif
175 }
176 } else {
177 if (PrintGCDetails && Verbose) {
178 gclog_or_tty->print_cr("ParallelTaskTerminator::offer_termination() "
179 "thread %d sleeps after %d yields",
180 Thread::current(), yield_count);
181 }
182 yield_count = 0;
183 // A sleep will cause this processor to seek work on another processor's
184 // runqueue, if it has nothing else to run (as opposed to the yield
185 // which may only move the thread to the end of the this processor's
186 // runqueue).
187 sleep(WorkStealingSleepMillis);
188 }
190 #ifdef TRACESPINNING
191 _total_peeks++;
192 #endif
193 if (peek_in_queue_set() ||
194 (terminator != NULL && terminator->should_exit_termination())) {
195 Atomic::dec(&_offered_termination);
196 assert(_offered_termination < _n_threads, "Invariant");
197 return false;
198 }
199 }
200 }
201 }
203 #ifdef TRACESPINNING
204 void ParallelTaskTerminator::print_termination_counts() {
205 gclog_or_tty->print_cr("ParallelTaskTerminator Total yields: %lld "
206 "Total spins: %lld Total peeks: %lld",
207 total_yields(),
208 total_spins(),
209 total_peeks());
210 }
211 #endif
213 void ParallelTaskTerminator::reset_for_reuse() {
214 if (_offered_termination != 0) {
215 assert(_offered_termination == _n_threads,
216 "Terminator may still be in use");
217 _offered_termination = 0;
218 }
219 }
221 #ifdef ASSERT
222 bool ObjArrayTask::is_valid() const {
223 return _obj != NULL && _obj->is_objArray() && _index > 0 &&
224 _index < objArrayOop(_obj)->length();
225 }
226 #endif // ASSERT