taskqueue.cpp 8.1 KB
Newer Older
D
duke 已提交
1
/*
X
xdono 已提交
2
 * Copyright 2001-2009 Sun Microsystems, Inc.  All Rights Reserved.
D
duke 已提交
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 *
 */

# include "incls/_precompiled.incl"
# include "incls/_taskqueue.cpp.incl"

28 29 30 31 32 33
#ifdef TRACESPINNING
uint ParallelTaskTerminator::_total_yields = 0;
uint ParallelTaskTerminator::_total_spins = 0;
uint ParallelTaskTerminator::_total_peeks = 0;
#endif

D
duke 已提交
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
int TaskQueueSetSuper::randomParkAndMiller(int *seed0) {
  const int a =      16807;
  const int m = 2147483647;
  const int q =     127773;  /* m div a */
  const int r =       2836;  /* m mod a */
  assert(sizeof(int) == 4, "I think this relies on that");
  int seed = *seed0;
  int hi   = seed / q;
  int lo   = seed % q;
  int test = a * lo - r * hi;
  if (test > 0)
    seed = test;
  else
    seed = test + m;
  *seed0 = seed;
  return seed;
}

ParallelTaskTerminator::
ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set) :
  _n_threads(n_threads),
  _queue_set(queue_set),
  _offered_termination(0) {}

bool ParallelTaskTerminator::peek_in_queue_set() {
  return _queue_set->peek();
}

void ParallelTaskTerminator::yield() {
63
  assert(_offered_termination <= _n_threads, "Invariant");
D
duke 已提交
64 65 66 67
  os::yield();
}

void ParallelTaskTerminator::sleep(uint millis) {
68
  assert(_offered_termination <= _n_threads, "Invariant");
D
duke 已提交
69 70 71
  os::sleep(Thread::current(), millis, false);
}

72 73
bool
ParallelTaskTerminator::offer_termination(TerminatorTerminator* terminator) {
74
  assert(_offered_termination < _n_threads, "Invariant");
D
duke 已提交
75 76
  Atomic::inc(&_offered_termination);

77
  uint yield_count = 0;
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
  // Number of hard spin loops done since last yield
  uint hard_spin_count = 0;
  // Number of iterations in the hard spin loop.
  uint hard_spin_limit = WorkStealingHardSpins;

  // If WorkStealingSpinToYieldRatio is 0, no hard spinning is done.
  // If it is greater than 0, then start with a small number
  // of spins and increase number with each turn at spinning until
  // the count of hard spins exceeds WorkStealingSpinToYieldRatio.
  // Then do a yield() call and start spinning afresh.
  if (WorkStealingSpinToYieldRatio > 0) {
    hard_spin_limit = WorkStealingHardSpins >> WorkStealingSpinToYieldRatio;
    hard_spin_limit = MAX2(hard_spin_limit, 1U);
  }
  // Remember the initial spin limit.
  uint hard_spin_start = hard_spin_limit;

  // Loop waiting for all threads to offer termination or
  // more work.
D
duke 已提交
97
  while (true) {
98
    assert(_offered_termination <= _n_threads, "Invariant");
99
    // Are all threads offering termination?
D
duke 已提交
100 101 102
    if (_offered_termination == _n_threads) {
      return true;
    } else {
103 104 105
      // Look for more work.
      // Periodically sleep() instead of yield() to give threads
      // waiting on the cores the chance to grab this code
D
duke 已提交
106
      if (yield_count <= WorkStealingYieldsBeforeSleep) {
107 108
        // Do a yield or hardspin.  For purposes of deciding whether
        // to sleep, count this as a yield.
D
duke 已提交
109
        yield_count++;
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

        // Periodically call yield() instead spinning
        // After WorkStealingSpinToYieldRatio spins, do a yield() call
        // and reset the counts and starting limit.
        if (hard_spin_count > WorkStealingSpinToYieldRatio) {
          yield();
          hard_spin_count = 0;
          hard_spin_limit = hard_spin_start;
#ifdef TRACESPINNING
          _total_yields++;
#endif
        } else {
          // Hard spin this time
          // Increase the hard spinning period but only up to a limit.
          hard_spin_limit = MIN2(2*hard_spin_limit,
                                 (uint) WorkStealingHardSpins);
          for (uint j = 0; j < hard_spin_limit; j++) {
            SpinPause();
          }
          hard_spin_count++;
#ifdef TRACESPINNING
          _total_spins++;
#endif
        }
D
duke 已提交
134 135 136 137 138 139 140 141 142 143 144 145 146 147
      } else {
        if (PrintGCDetails && Verbose) {
         gclog_or_tty->print_cr("ParallelTaskTerminator::offer_termination() "
           "thread %d sleeps after %d yields",
           Thread::current(), yield_count);
        }
        yield_count = 0;
        // A sleep will cause this processor to seek work on another processor's
        // runqueue, if it has nothing else to run (as opposed to the yield
        // which may only move the thread to the end of the this processor's
        // runqueue).
        sleep(WorkStealingSleepMillis);
      }

148 149 150
#ifdef TRACESPINNING
      _total_peeks++;
#endif
151 152
      if (peek_in_queue_set() ||
          (terminator != NULL && terminator->should_exit_termination())) {
D
duke 已提交
153
        Atomic::dec(&_offered_termination);
154
        assert(_offered_termination < _n_threads, "Invariant");
D
duke 已提交
155 156 157 158 159 160
        return false;
      }
    }
  }
}

161 162 163 164 165 166 167 168 169 170
#ifdef TRACESPINNING
void ParallelTaskTerminator::print_termination_counts() {
  gclog_or_tty->print_cr("ParallelTaskTerminator Total yields: %lld  "
    "Total spins: %lld  Total peeks: %lld",
    total_yields(),
    total_spins(),
    total_peeks());
}
#endif

D
duke 已提交
171 172 173 174 175 176 177 178
void ParallelTaskTerminator::reset_for_reuse() {
  if (_offered_termination != 0) {
    assert(_offered_termination == _n_threads,
           "Terminator may still be in use");
    _offered_termination = 0;
  }
}

179 180 181 182 183 184 185
#ifdef ASSERT
bool ObjArrayTask::is_valid() const {
  return _obj != NULL && _obj->is_objArray() && _index > 0 &&
    _index < objArrayOop(_obj)->length();
}
#endif // ASSERT

186 187
bool RegionTaskQueueWithOverflow::is_empty() {
  return (_region_queue.size() == 0) &&
D
duke 已提交
188 189 190
         (_overflow_stack->length() == 0);
}

191 192
bool RegionTaskQueueWithOverflow::stealable_is_empty() {
  return _region_queue.size() == 0;
D
duke 已提交
193 194
}

195
bool RegionTaskQueueWithOverflow::overflow_is_empty() {
D
duke 已提交
196 197 198
  return _overflow_stack->length() == 0;
}

199 200
void RegionTaskQueueWithOverflow::initialize() {
  _region_queue.initialize();
D
duke 已提交
201 202
  assert(_overflow_stack == 0, "Creating memory leak");
  _overflow_stack =
203
    new (ResourceObj::C_HEAP) GrowableArray<RegionTask>(10, true);
D
duke 已提交
204 205
}

206 207
void RegionTaskQueueWithOverflow::save(RegionTask t) {
  if (TraceRegionTasksQueuing && Verbose) {
D
duke 已提交
208 209
    gclog_or_tty->print_cr("CTQ: save " PTR_FORMAT, t);
  }
210
  if(!_region_queue.push(t)) {
D
duke 已提交
211 212 213 214
    _overflow_stack->push(t);
  }
}

215
// Note that using this method will retrieve all regions
D
duke 已提交
216 217 218 219
// that have been saved but that it will always check
// the overflow stack.  It may be more efficient to
// check the stealable queue and the overflow stack
// separately.
220 221
bool RegionTaskQueueWithOverflow::retrieve(RegionTask& region_task) {
  bool result = retrieve_from_overflow(region_task);
D
duke 已提交
222
  if (!result) {
223
    result = retrieve_from_stealable_queue(region_task);
D
duke 已提交
224
  }
225
  if (TraceRegionTasksQueuing && Verbose && result) {
D
duke 已提交
226 227 228 229 230
    gclog_or_tty->print_cr("  CTQ: retrieve " PTR_FORMAT, result);
  }
  return result;
}

231 232 233 234 235
bool RegionTaskQueueWithOverflow::retrieve_from_stealable_queue(
                                   RegionTask& region_task) {
  bool result = _region_queue.pop_local(region_task);
  if (TraceRegionTasksQueuing && Verbose) {
    gclog_or_tty->print_cr("CTQ: retrieve_stealable " PTR_FORMAT, region_task);
D
duke 已提交
236 237 238 239
  }
  return result;
}

240 241
bool
RegionTaskQueueWithOverflow::retrieve_from_overflow(RegionTask& region_task) {
D
duke 已提交
242 243
  bool result;
  if (!_overflow_stack->is_empty()) {
244
    region_task = _overflow_stack->pop();
D
duke 已提交
245 246
    result = true;
  } else {
247
    region_task = (RegionTask) NULL;
D
duke 已提交
248 249
    result = false;
  }
250 251
  if (TraceRegionTasksQueuing && Verbose) {
    gclog_or_tty->print_cr("CTQ: retrieve_stealable " PTR_FORMAT, region_task);
D
duke 已提交
252 253 254
  }
  return result;
}