Panda3D
 All Classes Functions Variables Enumerations
threadSimpleManager.cxx
00001 // Filename: threadSimpleManager.cxx
00002 // Created by:  drose (19Jun07)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #include "threadSimpleManager.h"
00016 
00017 #ifdef THREAD_SIMPLE_IMPL
00018 
00019 #include "threadSimpleImpl.h"
00020 #include "blockerSimple.h"
00021 #include "mainThread.h"
00022 
00023 #ifdef WIN32
00024 #define WIN32_LEAN_AND_MEAN
00025 #include <windows.h>
00026 #endif
00027 
00028 bool ThreadSimpleManager::_pointers_initialized;
00029 ThreadSimpleManager *ThreadSimpleManager::_global_ptr;
00030 
00031 ////////////////////////////////////////////////////////////////////
00032 //     Function: ThreadSimpleManager::Constructor
00033 //       Access: Private
00034 //  Description: 
00035 ////////////////////////////////////////////////////////////////////
00036 ThreadSimpleManager::
00037 ThreadSimpleManager() :
00038   _simple_thread_epoch_timeslice
00039   ("simple-thread-epoch-timeslice", 0.05,
00040    PRC_DESC("When SIMPLE_THREADS is defined, this defines the amount of time, "
00041             "in seconds, that should be considered the "
00042             "typical timeslice for one epoch (to run all threads once).")),
00043   _simple_thread_volunteer_delay
00044   ("simple-thread-volunteer-delay", 0.0,
00045    PRC_DESC("When SIMPLE_THREADS is defined, this defines the amount of time, "
00046             "in seconds, for which a task that voluntarily yields should "
00047             "be delayed.")),
00048   _simple_thread_yield_sleep
00049   ("simple-thread-yield-sleep", 0.001,
00050    PRC_DESC("When SIMPLE_THREADS is defined, this defines the amount of time, "
00051             "in seconds, for which the process should be put to sleep when "
00052             "yielding the timeslice to the system.")),
00053   _simple_thread_window
00054   ("simple-thread-window", 1.0,
00055    PRC_DESC("When SIMPLE_THREADS is defined, this defines the amount of time, "
00056             "in seconds, over which to average all the threads' runtimes, "
00057             "for the purpose of scheduling threads.")),
00058   _simple_thread_low_weight
00059   ("simple-thread-low-weight", 0.2,
00060    PRC_DESC("When SIMPLE_THREADS is defined, this determines the relative "
00061             "amount of time that is given to threads with priority TP_low.")),
00062   _simple_thread_normal_weight
00063   ("simple-thread-normal-weight", 1.0,
00064    PRC_DESC("When SIMPLE_THREADS is defined, this determines the relative "
00065             "amount of time that is given to threads with priority TP_normal.")),
00066   _simple_thread_high_weight
00067   ("simple-thread-high-weight", 5.0,
00068    PRC_DESC("When SIMPLE_THREADS is defined, this determines the relative "
00069             "amount of time that is given to threads with priority TP_high.")),
00070   _simple_thread_urgent_weight
00071   ("simple-thread-urgent-weight", 10.0,
00072    PRC_DESC("When SIMPLE_THREADS is defined, this determines the relative "
00073             "amount of time that is given to threads with priority TP_urgent."))
00074 {
00075   _tick_scale = 1000000.0;
00076   _total_ticks = 0;
00077   _current_thread = NULL;
00078   _clock = TrueClock::get_global_ptr();
00079   _waiting_for_exit = NULL;
00080 
00081   // Install these global pointers so very low-level code (code
00082   // defined before the pipeline directory) can yield when necessary.
00083   global_thread_yield = &Thread::force_yield;
00084   global_thread_consider_yield = &Thread::consider_yield;
00085 }
00086 
00087 ////////////////////////////////////////////////////////////////////
00088 //     Function: ThreadSimpleManager::enqueue_ready
00089 //       Access: Public
00090 //  Description: Adds the indicated thread to the ready queue.  The
00091 //               thread will be executed when its turn comes.  If the
00092 //               thread is not the currently executing thread, its
00093 //               _jmp_context should be filled appropriately.
00094 //
00095 //               If volunteer is true, the thread is volunteering to
00096 //               sleep before its timeslice has been used up.  If
00097 //               volunteer is false, the thread would still be running
00098 //               if it could.
00099 ////////////////////////////////////////////////////////////////////
00100 void ThreadSimpleManager::
00101 enqueue_ready(ThreadSimpleImpl *thread, bool volunteer) {
00102   // We actually add it to _next_ready, so that we can tell when we
00103   // have processed every thread in a given epoch.
00104   if (!volunteer) {
00105     _next_ready.push_back(thread);
00106 
00107   } else {
00108     // Unless it's a volunteer, in which case we actually put it to
00109     // sleep for the duration of the timeslice, so it won't interfere
00110     // with timeslice accounting for the remaining ready threads.
00111     double now = get_current_time();
00112     thread->_wake_time = now + _simple_thread_volunteer_delay;
00113     _volunteers.push_back(thread);
00114     push_heap(_volunteers.begin(), _volunteers.end(), CompareStartTime());
00115   }
00116 }
00117 
00118 ////////////////////////////////////////////////////////////////////
00119 //     Function: ThreadSimpleManager::enqueue_sleep
00120 //       Access: Public
00121 //  Description: Adds the indicated thread to the sleep queue, until
00122 //               the indicated number of seconds have elapsed.  Then
00123 //               the thread will be automatically moved to the ready
00124 //               queue.
00125 ////////////////////////////////////////////////////////////////////
00126 void ThreadSimpleManager::
00127 enqueue_sleep(ThreadSimpleImpl *thread, double seconds) {
00128   if (thread_cat->is_debug()) {
00129     thread_cat.debug()
00130       << *_current_thread->_parent_obj << " sleeping for " 
00131       << seconds << " seconds\n";
00132   }
00133 
00134   double now = get_current_time();
00135   thread->_wake_time = now + seconds;
00136   _sleeping.push_back(thread);
00137   push_heap(_sleeping.begin(), _sleeping.end(), CompareStartTime());
00138 }
00139 
00140 ////////////////////////////////////////////////////////////////////
00141 //     Function: ThreadSimpleManager::enqueue_block
00142 //       Access: Public
00143 //  Description: Adds the indicated thread to the blocked queue for
00144 //               the indicated blocker.  The thread will be awoken by
00145 //               a later call to unblock_one() or unblock_all().
00146 ////////////////////////////////////////////////////////////////////
00147 void ThreadSimpleManager::
00148 enqueue_block(ThreadSimpleImpl *thread, BlockerSimple *blocker) {
00149   _blocked[blocker].push_back(thread);
00150   blocker->_flags |= BlockerSimple::F_has_waiters;
00151 }
00152 
00153 ////////////////////////////////////////////////////////////////////
00154 //     Function: ThreadSimpleManager::unblock_one
00155 //       Access: Public
00156 //  Description: Unblocks one thread waiting on the indicated blocker,
00157 //               if any.  Returns true if anything was unblocked,
00158 //               false otherwise.
00159 ////////////////////////////////////////////////////////////////////
00160 bool ThreadSimpleManager::
00161 unblock_one(BlockerSimple *blocker) {
00162   Blocked::iterator bi = _blocked.find(blocker);
00163   if (bi != _blocked.end()) {
00164     nassertr(blocker->_flags & BlockerSimple::F_has_waiters, false);
00165 
00166     FifoThreads &threads = (*bi).second;
00167     nassertr(!threads.empty(), false);
00168     ThreadSimpleImpl *thread = threads.front();
00169     threads.pop_front();
00170     _ready.push_back(thread);
00171     if (threads.empty()) {
00172       blocker->_flags &= ~BlockerSimple::F_has_waiters;
00173       _blocked.erase(bi);
00174     }
00175 
00176     return true;
00177   }
00178 
00179   return false;
00180 }
00181 
00182 ////////////////////////////////////////////////////////////////////
00183 //     Function: ThreadSimpleManager::unblock_all
00184 //       Access: Public
00185 //  Description: Unblocks all threads waiting on the indicated
00186 //               blocker.  Returns true if anything was unblocked,
00187 //               false otherwise.
00188 ////////////////////////////////////////////////////////////////////
00189 bool ThreadSimpleManager::
00190 unblock_all(BlockerSimple *blocker) {
00191   Blocked::iterator bi = _blocked.find(blocker);
00192   if (bi != _blocked.end()) {
00193     nassertr(blocker->_flags & BlockerSimple::F_has_waiters, false);
00194 
00195     FifoThreads &threads = (*bi).second;
00196     nassertr(!threads.empty(), false);
00197     while (!threads.empty()) {
00198       ThreadSimpleImpl *thread = threads.front();
00199       threads.pop_front();
00200       _ready.push_back(thread);
00201     }
00202     blocker->_flags &= ~BlockerSimple::F_has_waiters;
00203     _blocked.erase(bi);
00204     return true;
00205   }
00206   return false;
00207 }
00208 
00209 ////////////////////////////////////////////////////////////////////
00210 //     Function: ThreadSimpleManager::enqueue_finished
00211 //       Access: Public
00212 //  Description: Adds the indicated thread to the finished queue.  
00213 //               The manager will drop the reference count on the
00214 //               indicated thread at the next epoch.  (A thread can't
00215 //               drop its own reference count while it is running,
00216 //               since that might deallocate its own stack.)
00217 ////////////////////////////////////////////////////////////////////
00218 void ThreadSimpleManager::
00219 enqueue_finished(ThreadSimpleImpl *thread) {
00220   _finished.push_back(thread);
00221 }
00222 
00223 ////////////////////////////////////////////////////////////////////
00224 //     Function: ThreadSimpleManager::preempt
00225 //       Access: Public
00226 //  Description: Moves the indicated thread to the head of the ready
00227 //               queue.  If it is not already on the ready queue, does
00228 //               nothing.
00229 ////////////////////////////////////////////////////////////////////
00230 void ThreadSimpleManager::
00231 preempt(ThreadSimpleImpl *thread) {
00232   FifoThreads::iterator ti;
00233   ti = find(_ready.begin(), _ready.end(), thread);
00234   if (ti != _ready.end()) {
00235     _ready.erase(ti);
00236     _ready.push_front(thread);
00237   }
00238 }
00239 
00240 ////////////////////////////////////////////////////////////////////
00241 //     Function: ThreadSimpleManager::next_context
00242 //       Access: Public
00243 //  Description: Switches out the currently executing thread and
00244 //               chooses a new thread for execution.  Before calling
00245 //               this, the current thread should have already
00246 //               re-enqueued itself with a call to enqueue(), if it
00247 //               intends to run again.
00248 //
00249 //               This will fill in the current thread's _jmp_context
00250 //               member appropriately, and then change the global
00251 //               current_thread pointer.
00252 ////////////////////////////////////////////////////////////////////
00253 void ThreadSimpleManager::
00254 next_context() {
00255   // Delete any threads that need it.  We can't delete the current
00256   // thread, though.
00257   while (!_finished.empty() && _finished.front() != _current_thread) {
00258     ThreadSimpleImpl *finished_thread = _finished.front();
00259     _finished.pop_front();
00260     unref_delete(finished_thread->_parent_obj);
00261   }
00262 
00263   // Mark the current thread's resume point.
00264 
00265 #ifdef HAVE_PYTHON
00266   // Save the current Python thread state.
00267   _current_thread->_python_state = PyThreadState_Swap(NULL);
00268 #endif  // HAVE_PYTHON
00269 
00270 #ifdef DO_PSTATS
00271   Thread::PStatsCallback *pstats_callback = _current_thread->_parent_obj->get_pstats_callback();
00272   if (pstats_callback != NULL) {
00273     pstats_callback->deactivate_hook(_current_thread->_parent_obj);
00274   }
00275 #endif  // DO_PSTATS
00276 
00277   save_thread_context(_current_thread->_context, st_choose_next_context, this);
00278   // Pass 2: we have returned into the context, and are now resuming
00279   // the current thread.
00280 
00281 #ifdef DO_PSTATS
00282   if (pstats_callback != NULL) {
00283     pstats_callback->activate_hook(_current_thread->_parent_obj);
00284   }
00285 #endif  // DO_PSTATS
00286 
00287 #ifdef HAVE_PYTHON
00288   PyThreadState_Swap(_current_thread->_python_state);
00289 #endif  // HAVE_PYTHON
00290 }
00291 
00292 ////////////////////////////////////////////////////////////////////
00293 //     Function: ThreadSimpleManager::prepare_for_exit
00294 //       Access: Public
00295 //  Description: Blocks until all running threads (other than the
00296 //               current thread) have finished.  This only works when
00297 //               called from the main thread; if called on any other
00298 //               thread, nothing will happen.
00299 ////////////////////////////////////////////////////////////////////
00300 void ThreadSimpleManager::
00301 prepare_for_exit() {
00302   if (!_current_thread->_parent_obj->is_exact_type(MainThread::get_class_type())) {
00303     if (thread_cat->is_debug()) {
00304       thread_cat.debug()
00305         << "Ignoring prepare_for_exit called from " 
00306         << *(_current_thread->_parent_obj) << "\n";
00307     }
00308     return;
00309   }
00310 
00311   if (thread_cat->is_debug()) {
00312     thread_cat.debug()
00313       << "prepare_for_exit\n";
00314   }
00315 
00316   nassertv(_waiting_for_exit == NULL);
00317   _waiting_for_exit = _current_thread;
00318 
00319   // At this point, any non-joinable threads on any of the queues are
00320   // automatically killed.
00321   kill_non_joinable(_ready);
00322 
00323   Blocked::iterator bi = _blocked.begin();
00324   while (bi != _blocked.end()) {
00325     Blocked::iterator bnext = bi;
00326     ++bnext;
00327     BlockerSimple *blocker = (*bi).first;
00328     FifoThreads &threads = (*bi).second;
00329     kill_non_joinable(threads);
00330     if (threads.empty()) {
00331       blocker->_flags &= ~BlockerSimple::F_has_waiters;
00332       _blocked.erase(bi);
00333     }
00334     bi = bnext;
00335   }
00336 
00337   kill_non_joinable(_sleeping);
00338   kill_non_joinable(_volunteers);
00339 
00340   next_context();
00341 
00342   // Delete any remaining threads.
00343   while (!_finished.empty() && _finished.front() != _current_thread) {
00344     ThreadSimpleImpl *finished_thread = _finished.front();
00345     _finished.pop_front();
00346     unref_delete(finished_thread->_parent_obj);
00347   }
00348 }
00349 
00350 ////////////////////////////////////////////////////////////////////
00351 //     Function: ThreadSimpleManager::set_current_thread
00352 //       Access: Public
00353 //  Description: Sets the initial value of the current_thread pointer,
00354 //               i.e. the main thread.  It is valid to call this
00355 //               method only exactly once.
00356 ////////////////////////////////////////////////////////////////////
00357 void ThreadSimpleManager::
00358 set_current_thread(ThreadSimpleImpl *current_thread) {
00359   nassertv(_current_thread == (ThreadSimpleImpl *)NULL);
00360   _current_thread = current_thread;
00361 }
00362 
00363 ////////////////////////////////////////////////////////////////////
00364 //     Function: ThreadSimpleManager::remove_thread
00365 //       Access: Public
00366 //  Description: Removes the indicated thread from the accounting, for
00367 //               instance just before the thread destructs.
00368 ////////////////////////////////////////////////////////////////////
00369 void ThreadSimpleManager::
00370 remove_thread(ThreadSimpleImpl *thread) {
00371   TickRecords new_records;
00372   TickRecords::iterator ri;
00373   for (ri = _tick_records.begin(); ri != _tick_records.end(); ++ri) {
00374     if ((*ri)._thread != thread) {
00375       // Keep this record.
00376       new_records.push_back(*ri);
00377     } else {
00378       // Lose this record.
00379       nassertv(_total_ticks >= (*ri)._tick_count);
00380       _total_ticks -= (*ri)._tick_count;
00381     }
00382   }
00383 
00384   _tick_records.swap(new_records);
00385 }
00386 
00387 ////////////////////////////////////////////////////////////////////
00388 //     Function: ThreadSimpleManager::system_sleep
00389 //       Access: Public, Static
00390 //  Description: Calls the appropriate system sleep function to sleep
00391 //               the whole process for the indicated number of
00392 //               seconds.
00393 ////////////////////////////////////////////////////////////////////
00394 void ThreadSimpleManager::
00395 system_sleep(double seconds) {
00396 #ifdef WIN32
00397   Sleep((int)(seconds * 1000 + 0.5));
00398 
00399 #else
00400   /*
00401   struct timespec rqtp;
00402   rqtp.tv_sec = time_t(seconds);
00403   rqtp.tv_nsec = long((seconds - (double)rqtp.tv_sec) * 1000000000.0 + 0.5);
00404   nanosleep(&rqtp, NULL);
00405   */
00406   
00407   // We use select() as the only way that seems to actually yield the
00408   // timeslice.  sleep() and nanosleep() don't appear to do the trick.
00409   struct timeval tv;
00410   tv.tv_sec = time_t(seconds);
00411   tv.tv_usec = long((seconds - (double)tv.tv_sec) * 1000000.0 + 0.5);
00412   select(0, NULL, NULL, NULL, &tv);
00413 #endif  // WIN32
00414 }
00415 
00416 ////////////////////////////////////////////////////////////////////
00417 //     Function: ThreadSimpleManager::write_status
00418 //       Access: Public
00419 //  Description: Writes a list of threads running and threads blocked.
00420 ////////////////////////////////////////////////////////////////////
00421 void ThreadSimpleManager::
00422 write_status(ostream &out) const {
00423   out << "Currently running: " << *_current_thread->_parent_obj << "\n";
00424 
00425   out << "Ready:";
00426   FifoThreads::const_iterator ti;
00427   Sleeping::const_iterator si;
00428   for (ti = _ready.begin(); ti != _ready.end(); ++ti) {
00429     out << " " << *(*ti)->_parent_obj;
00430   }
00431   for (ti = _next_ready.begin(); ti != _next_ready.end(); ++ti) {
00432     out << " " << *(*ti)->_parent_obj;
00433   }
00434   for (si = _volunteers.begin(); si != _volunteers.end(); ++si) {
00435     out << " " << *(*si)->_parent_obj;
00436   }
00437   out << "\n";
00438 
00439   double now = get_current_time();
00440 
00441   out << "Sleeping:";
00442   // Copy and sort for convenience.
00443   Sleeping s2 = _sleeping;
00444   sort(s2.begin(), s2.end(), CompareStartTime());
00445   for (si = s2.begin(); si != s2.end(); ++si) {
00446     out << " " << *(*si)->_parent_obj << "(" << (*si)->_wake_time - now
00447         << "s)";
00448   }
00449   out << "\n";
00450 
00451   Blocked::const_iterator bi;
00452   for (bi = _blocked.begin(); bi != _blocked.end(); ++bi) {
00453     BlockerSimple *blocker = (*bi).first;
00454     const FifoThreads &threads = (*bi).second;
00455     out << "On blocker " << blocker << ":\n";
00456     FifoThreads::const_iterator ti;
00457     for (ti = threads.begin(); ti != threads.end(); ++ti) {
00458       ThreadSimpleImpl *thread = (*ti);
00459       out << " " << *thread->_parent_obj;
00460 #ifdef DEBUG_THREADS
00461       out << " (";
00462       thread->_parent_obj->output_blocker(out);
00463       out << ")";
00464 #endif  // DEBUG_THREADS
00465     }
00466     out << "\n";
00467   }
00468 }
00469 
00470 ////////////////////////////////////////////////////////////////////
00471 //     Function: ThreadSimpleManager::system_yield
00472 //       Access: Public, Static
00473 //  Description: Calls the appropriate system function to yield
00474 //               the whole process to any other system processes.
00475 ////////////////////////////////////////////////////////////////////
00476 void ThreadSimpleManager::
00477 system_yield() {
00478   if (!_pointers_initialized) {
00479     // Ignore this call before we construct the global ThreadSimpleManager.
00480     return;
00481   }
00482 
00483   if (thread_cat->is_debug()) {
00484     thread_cat.debug()
00485       << "system_yield\n";
00486   }
00487 
00488   // There seem to be some issues with modern operating systems not
00489   // wanting to actually yield the timeslice in response to sleep(0).
00490   // In particular, Windows and OSX both seemed to do nothing in that
00491   // call.  Whatever.  We'll force the point by explicitly sleeping
00492   // for 1 ms in both cases.  This is user-configurable in case 1 ms
00493   // is too much (though on Windows that's all the resolution you
00494   // have).
00495   system_sleep(_global_ptr->_simple_thread_yield_sleep);
00496 }
00497 
00498 ////////////////////////////////////////////////////////////////////
00499 //     Function: ThreadSimpleManager::get_current_time
00500 //       Access: Public
00501 //  Description: Returns elapsed time in seconds from some undefined
00502 //               epoch, via whatever clock the manager is using for
00503 //               all thread timing.
00504 ////////////////////////////////////////////////////////////////////
00505 double ThreadSimpleManager::
00506 get_current_time() const {
00507   return _clock->get_short_raw_time();
00508 }
00509 
00510 ////////////////////////////////////////////////////////////////////
00511 //     Function: ThreadSimpleManager::init_pointers
00512 //       Access: Private, Static
00513 //  Description: Should be called at startup to initialize the
00514 //               simple threading system.
00515 ////////////////////////////////////////////////////////////////////
00516 void ThreadSimpleManager::
00517 init_pointers() {
00518   if (!_pointers_initialized) {
00519     _pointers_initialized = true;
00520     _global_ptr = new ThreadSimpleManager;
00521     Thread::get_main_thread();
00522 
00523 #ifdef HAVE_PYTHON
00524     // Ensure that the Python threading system is initialized and ready
00525     // to go.
00526     PyEval_InitThreads();
00527 #endif
00528   }
00529 }
00530 
00531 ////////////////////////////////////////////////////////////////////
00532 //     Function: ThreadSimpleManager::st_choose_next_context
00533 //       Access: Private, Static
00534 //  Description: Select the next context to run.  Continuing the work
00535 //               of next_context().
00536 ////////////////////////////////////////////////////////////////////
00537 void ThreadSimpleManager::
00538 st_choose_next_context(struct ThreadContext *from_context, void *data) {
00539   ThreadSimpleManager *self = (ThreadSimpleManager *)data;
00540   self->choose_next_context(from_context);
00541 }
00542 
00543 ////////////////////////////////////////////////////////////////////
00544 //     Function: ThreadSimpleManager::choose_next_context
00545 //       Access: Private
00546 //  Description: Select the next context to run.  Continuing the work
00547 //               of next_context().
00548 ////////////////////////////////////////////////////////////////////
00549 void ThreadSimpleManager::
00550 choose_next_context(struct ThreadContext *from_context) {
00551   double now = get_current_time();
00552 
00553   do_timeslice_accounting(_current_thread, now);
00554   _current_thread = NULL;
00555 
00556   if (!_sleeping.empty() || !_volunteers.empty()) {
00557     if (_ready.empty() && _next_ready.empty()) {
00558       // All of our threads are currently sleeping.  Therefore, wake
00559       // the volunteer(s) immediately.
00560       wake_all_sleepers(_volunteers);
00561 
00562       // We should also yield the whole process now, to be polite to
00563       // the rest of the system.
00564       system_yield();
00565       now = get_current_time();
00566     }
00567     wake_sleepers(_sleeping, now);
00568     wake_sleepers(_volunteers, now);
00569   }
00570 
00571   bool new_epoch = !_ready.empty() && _next_ready.empty();
00572 
00573   // Choose a new thread to execute.
00574   while (true) {
00575     // If there are no threads, sleep.
00576     while (_ready.empty()) {
00577       if (!_next_ready.empty()) {
00578         // We've finished an epoch.
00579         _ready.swap(_next_ready);
00580 
00581         if (new_epoch && !_tick_records.empty()) {
00582           // Pop the oldest timeslice record off when we finish an
00583           // epoch without executing any threads, to ensure we don't
00584           // get caught in an "all threads reached budget" loop.
00585           if (thread_cat->is_debug()) {
00586             thread_cat.debug()
00587               << "All threads exceeded budget.\n";
00588           }
00589           TickRecord &record = _tick_records.front();
00590           _total_ticks -= record._tick_count;
00591 
00592           if (record._thread->_run_ticks >= record._tick_count) {
00593             // Ensure we don't go negative.
00594             record._thread->_run_ticks -= record._tick_count;
00595           } else {
00596             // It is possible for this to happen if the application has been
00597             // paused for more than 2^31 ticks.
00598             record._thread->_run_ticks = 0;
00599           }
00600           _tick_records.pop_front();
00601         }
00602         new_epoch = true;
00603         
00604       } else if (!_volunteers.empty()) {
00605         // There are some volunteers.  Wake them.  Also wake any
00606         // sleepers that need it.
00607         if (thread_cat->is_debug()) {
00608           thread_cat.debug()
00609             << "Waking volunteers.\n";
00610         }
00611         // We should yield the whole process now, to be polite to the
00612         // rest of the system.
00613         system_yield();
00614         now = get_current_time();
00615         wake_all_sleepers(_volunteers);
00616         wake_sleepers(_sleeping, now);
00617 
00618       } else if (!_sleeping.empty()) {
00619         // All threads are sleeping.
00620         double wait = _sleeping.front()->_wake_time - now;
00621         if (wait > 0.0) {
00622           if (thread_cat->is_debug()) {
00623             thread_cat.debug()
00624               << "Sleeping all threads " << wait << " seconds\n";
00625           }
00626           system_sleep(wait);
00627         }
00628         now = get_current_time();
00629         wake_sleepers(_sleeping, now);
00630         wake_sleepers(_volunteers, now);
00631         
00632       } else {
00633         // No threads are ready!
00634         if (_waiting_for_exit != NULL) {
00635           // This is a shutdown situation.  In this case, we quietly
00636           // abandoned the remaining blocked threads, if any, and
00637           // switch back to the main thread to finish shutting down.
00638           _ready.push_back(_waiting_for_exit);
00639           _waiting_for_exit = NULL;
00640           break;
00641         }
00642 
00643         // No threads are ready to run, but we're not explicitly
00644         // shutting down.  This is an error condition, an
00645         // unintentional deadlock.
00646         if (!_blocked.empty()) {
00647           thread_cat->error()
00648             << "Deadlock!  All threads blocked.\n";
00649           report_deadlock();
00650           abort();
00651         }
00652         
00653         // No threads are queued anywhere.  This is some kind of
00654         // internal error, since normally the main thread, at least,
00655         // should be queued somewhere.
00656         thread_cat->error()
00657           << "All threads disappeared!\n";
00658         exit(0);
00659       }
00660     }
00661 
00662     ThreadSimpleImpl *chosen_thread = _ready.front();
00663     _ready.pop_front();
00664     
00665     double timeslice = determine_timeslice(chosen_thread);
00666     if (timeslice > 0.0) {
00667       // This thread is ready to roll.  Break out of the loop.
00668       chosen_thread->_start_time = now;
00669       chosen_thread->_stop_time = now + timeslice;
00670       _current_thread = chosen_thread;
00671       break;
00672     }
00673 
00674     // This thread is not ready to wake up yet.  Put it back for next
00675     // epoch.  It doesn't count as a volunteer, though--its timeslice
00676     // was used up.
00677     _next_ready.push_back(chosen_thread);
00678   }
00679 
00680   // All right, the thread is ready to roll.  Begin.
00681   if (thread_cat->is_debug()) {
00682     size_t blocked_count = 0;
00683     Blocked::const_iterator bi;
00684     for (bi = _blocked.begin(); bi != _blocked.end(); ++bi) {
00685       const FifoThreads &threads = (*bi).second;
00686       blocked_count += threads.size();
00687     }
00688 
00689     double timeslice = _current_thread->_stop_time - _current_thread->_start_time;
00690     thread_cat.debug()
00691       << "Switching to " << *_current_thread->_parent_obj
00692       << " for " << timeslice << " s ("
00693       << _ready.size() << " + " << _next_ready.size()
00694       << " + " << _volunteers.size()
00695       << " other threads ready, " << blocked_count
00696       << " blocked, " << _sleeping.size() << " sleeping)\n";
00697   }
00698 
00699   switch_to_thread_context(from_context, _current_thread->_context);
00700 
00701   // Shouldn't get here.
00702   nassertv(false);
00703   abort();
00704 }
00705 
00706 ////////////////////////////////////////////////////////////////////
00707 //     Function: ThreadSimpleManager::do_timeslice_accounting
00708 //       Access: Private
00709 //  Description: Records the amount of time the indicated thread has
00710 //               run, and updates the moving average.
00711 ////////////////////////////////////////////////////////////////////
00712 void ThreadSimpleManager::
00713 do_timeslice_accounting(ThreadSimpleImpl *thread, double now) {
00714   double elapsed = now - thread->_start_time;
00715   if (thread_cat.is_debug()) {
00716     thread_cat.debug()
00717       << *thread->_parent_obj << " ran for " << elapsed << " s of "
00718       << thread->_stop_time - thread->_start_time << " requested.\n";
00719   }
00720 
00721   // Clamp the elapsed time at 0.  (If it's less than 0, the clock is
00722   // running backwards, ick.)
00723   elapsed = max(elapsed, 0.0);
00724 
00725   unsigned int ticks = (unsigned int)(elapsed * _tick_scale + 0.5);
00726   thread->_run_ticks += ticks;
00727 
00728   // Now remove any old records.
00729   unsigned int ticks_window = (unsigned int)(_simple_thread_window * _tick_scale + 0.5);
00730   while (_total_ticks > ticks_window) {
00731     nassertv(!_tick_records.empty());
00732     TickRecord &record = _tick_records.front();
00733     _total_ticks -= record._tick_count;
00734     if (record._thread->_run_ticks >= record._tick_count) {
00735       // Ensure we don't go negative.
00736       record._thread->_run_ticks -= record._tick_count;
00737     } else {
00738       // It is possible for this to happen if the application has been
00739       // paused for more than 2^31 ticks.
00740       record._thread->_run_ticks = 0;
00741     }
00742     _tick_records.pop_front();
00743   }
00744 
00745   // Finally, record the new record.
00746   TickRecord record;
00747   record._tick_count = ticks;
00748   record._thread = thread;
00749   _tick_records.push_back(record);
00750   _total_ticks += ticks;
00751 }
00752 
00753 
00754 ////////////////////////////////////////////////////////////////////
00755 //     Function: ThreadSimpleManager::wake_sleepers
00756 //       Access: Private
00757 //  Description: Moves any threads due to wake up from the sleeping
00758 //               queue to the ready queue.
00759 ////////////////////////////////////////////////////////////////////
00760 void ThreadSimpleManager::
00761 wake_sleepers(ThreadSimpleManager::Sleeping &sleepers, double now) {
00762   while (!sleepers.empty() && sleepers.front()->_wake_time <= now) {
00763     ThreadSimpleImpl *thread = sleepers.front();
00764     pop_heap(sleepers.begin(), sleepers.end(), CompareStartTime());
00765     sleepers.pop_back();
00766     _ready.push_back(thread);
00767   }
00768 }
00769 
00770 ////////////////////////////////////////////////////////////////////
00771 //     Function: ThreadSimpleManager::wake_all_sleepers
00772 //       Access: Private
00773 //  Description: Moves all threads from the indicated sleeping queue
00774 //               to the ready queue, regardless of wake time.
00775 ////////////////////////////////////////////////////////////////////
00776 void ThreadSimpleManager::
00777 wake_all_sleepers(ThreadSimpleManager::Sleeping &sleepers) {
00778   while (!sleepers.empty()) {
00779     ThreadSimpleImpl *thread = sleepers.front();
00780     pop_heap(sleepers.begin(), sleepers.end(), CompareStartTime());
00781     sleepers.pop_back();
00782     _ready.push_back(thread);
00783   }
00784 }
00785 
00786 ////////////////////////////////////////////////////////////////////
00787 //     Function: ThreadSimpleManager::report_deadlock
00788 //       Access: Private
00789 //  Description: 
00790 ////////////////////////////////////////////////////////////////////
00791 void ThreadSimpleManager::
00792 report_deadlock() {
00793   Blocked::const_iterator bi;
00794   for (bi = _blocked.begin(); bi != _blocked.end(); ++bi) {
00795     BlockerSimple *blocker = (*bi).first;
00796     const FifoThreads &threads = (*bi).second;
00797     thread_cat.info()
00798       << "On blocker " << blocker << ":\n";
00799     FifoThreads::const_iterator ti;
00800     for (ti = threads.begin(); ti != threads.end(); ++ti) {
00801       ThreadSimpleImpl *thread = (*ti);
00802       thread_cat.info()
00803         << "  " << *thread->_parent_obj;
00804 #ifdef DEBUG_THREADS
00805       thread_cat.info(false) << " (";
00806       thread->_parent_obj->output_blocker(thread_cat.info(false));
00807       thread_cat.info(false) << ")";
00808 #endif  // DEBUG_THREADS
00809       thread_cat.info(false) << "\n";
00810     }
00811   }
00812 }
00813 
00814 ////////////////////////////////////////////////////////////////////
00815 //     Function: ThreadSimpleManager::determine_timeslice
00816 //       Access: Private
00817 //  Description: Determines the amount of time that should be
00818 //               allocated to the next timeslice of this thread, based
00819 //               on its priority weight and the amount of time it has
00820 //               run recently relative to other threads.
00821 ////////////////////////////////////////////////////////////////////
00822 double ThreadSimpleManager::
00823 determine_timeslice(ThreadSimpleImpl *chosen_thread) {
00824   if (_ready.empty() && _next_ready.empty()) {
00825     // This is the only ready thread.  It gets the full timeslice.
00826     return _simple_thread_epoch_timeslice;
00827   }
00828 
00829   // Count up the total runtime and weight of all ready threads.
00830   unsigned int total_ticks = chosen_thread->_run_ticks;
00831   double total_weight = chosen_thread->_priority_weight;
00832 
00833   FifoThreads::const_iterator ti;
00834   for (ti = _ready.begin(); ti != _ready.end(); ++ti) {
00835     total_ticks += (*ti)->_run_ticks;
00836     total_weight += (*ti)->_priority_weight;
00837   }
00838   for (ti = _next_ready.begin(); ti != _next_ready.end(); ++ti) {
00839     total_ticks += (*ti)->_run_ticks;
00840     total_weight += (*ti)->_priority_weight;
00841   }
00842 
00843   nassertr(total_weight != 0.0, 0.0);
00844   double budget_ratio = chosen_thread->_priority_weight / total_weight;
00845 
00846   if (total_ticks == 0) {
00847     // This must be the first thread.  Special case.
00848     return budget_ratio * _simple_thread_epoch_timeslice;
00849   }
00850 
00851   double run_ratio = (double)chosen_thread->_run_ticks / (double)total_ticks;
00852   double remaining_ratio = budget_ratio - run_ratio;
00853 
00854   if (thread_cat->is_debug()) {
00855     thread_cat.debug()
00856       << *chosen_thread->_parent_obj << " accrued "
00857       << chosen_thread->_run_ticks / _tick_scale << " s of "
00858       << total_ticks / _tick_scale << "; budget is "
00859       << budget_ratio * total_ticks / _tick_scale << ".\n";
00860     if (remaining_ratio <= 0.0) {
00861       thread_cat.debug()
00862         << "Exceeded budget.\n";
00863     }
00864   }
00865 
00866   return remaining_ratio * _simple_thread_epoch_timeslice;
00867 }
00868 
00869 ////////////////////////////////////////////////////////////////////
00870 //     Function: ThreadSimpleManager::kill_non_joinable
00871 //       Access: Private
00872 //  Description: Removes any non-joinable threads from the indicated
00873 //               queue and marks them killed.
00874 ////////////////////////////////////////////////////////////////////
00875 void ThreadSimpleManager::
00876 kill_non_joinable(ThreadSimpleManager::FifoThreads &threads) {
00877   FifoThreads new_threads;
00878   FifoThreads::iterator ti;
00879   for (ti = threads.begin(); ti != threads.end(); ++ti) {
00880     ThreadSimpleImpl *thread = (*ti);
00881     if (thread->_joinable) {
00882       new_threads.push_back(thread);
00883     } else {
00884       if (thread_cat->is_debug()) {
00885         thread_cat.debug()
00886           << "Killing " << *thread->_parent_obj << "\n";
00887       }
00888       thread->_status = ThreadSimpleImpl::TS_killed;
00889       enqueue_finished(thread);
00890     }
00891   }
00892 
00893   threads.swap(new_threads);
00894 }
00895 
00896 ////////////////////////////////////////////////////////////////////
00897 //     Function: ThreadSimpleManager::kill_non_joinable
00898 //       Access: Private
00899 //  Description: Removes any non-joinable threads from the indicated
00900 //               queue and marks them killed.
00901 ////////////////////////////////////////////////////////////////////
00902 void ThreadSimpleManager::
00903 kill_non_joinable(ThreadSimpleManager::Sleeping &threads) {
00904   Sleeping new_threads;
00905   Sleeping::iterator ti;
00906   for (ti = threads.begin(); ti != threads.end(); ++ti) {
00907     ThreadSimpleImpl *thread = (*ti);
00908     if (thread->_joinable) {
00909       new_threads.push_back(thread);
00910     } else {
00911       if (thread_cat->is_debug()) {
00912         thread_cat.debug()
00913           << "Killing " << *thread->_parent_obj << "\n";
00914       }
00915       thread->_status = ThreadSimpleImpl::TS_killed;
00916       enqueue_finished(thread);
00917     }
00918   }
00919   make_heap(new_threads.begin(), new_threads.end(), CompareStartTime());
00920   threads.swap(new_threads);
00921 }
00922 
00923 #endif // THREAD_SIMPLE_IMPL
 All Classes Functions Variables Enumerations