Scheduler.cpp

Go to the documentation of this file.
00001 /** @file Scheduler.cpp
00002 * @author Gabor Madl
00003 * @date Created 02/2005
00004 * @brief Scheduler model implementation.
00005 *
00006 *
00007 * =================================================================
00008 * DREAM License v2.0
00009 * 
00010 * DREAM - Distributed Real-time Embedded Analysis Method
00011 * http://dre.sourceforge.net.
00012 * Copyright (c) 2005-2007 Gabor Madl, All Rights Reserved.
00013 * 
00014 * This file is part of DREAM.
00015 * 
00016 * DREAM is free software; you can redistribute it and/or modify it
00017 * under the terms of the GNU General Public License version 2 as
00018 * published by the Free Software Foundation. No future versions of
00019 * the GPL license may be automatically applied to DREAM. It is in
00020 * the sole discretion of the copyright holder to determine whether
00021 * DREAM may be released under a different license or terms. There
00022 * are no restrictions on the use of DREAM for any purpose.
00023 * 
00024 * DREAM is distributed in the hope that it will be useful,
00025 * but WITHOUT ANY WARRANTY; without even the implied warranty of
00026 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
00027 * GNU General Public License for more details.
00028 * 
00029 * You should have received a copy of the GNU General Public License
00030 * along with this program; if not, write to the Free Software
00031 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
00032 * MA 02110-1301, USA.
00033 * 
00034 * By submitting comments, suggestions, code, code snippets,
00035 * techniques (including that of usage), and algorithms, submitters
00036 * acknowledge that they have the right to do so, that any such
00037 * submissions are given freely and unreservedly, and that they
00038 * waive any claims to copyright or ownership. In addition,
00039 * submitters acknowledge that any such submission might become
00040 * part of the copyright maintained on the overall body of code,
00041 * which comprises DREAM. By making a submission, submitter agrees
00042 * to these terms. Furthermore, submitters acknowledge that the
00043 * incorporation or modification of such submissions is entirely
00044 * at the discretion of the moderators of the DREAM project.
00045 * 
00046 * DREAM links to the Libxml2 third party library. Please see 
00047 * COPYING-libxml for the copyright information of Libxml2.
00048 * =================================================================
00049 */
00050 
00051 #include "Scheduler.h"
00052 
00053 namespace DREAM
00054 {
00055 
00056 /////////////////////////////////////////////////////////////////////////////
00057 //
00058 // QoSLevel
00059 //
00060 /////////////////////////////////////////////////////////////////////////////
00061 
00062 QoSLevel::QoSLevel (const double speed, const double power)
00063 : speed_ (speed), power_ (power)
00064 {
00065 }
00066 
00067 inline double QoSLevel::power () const
00068 {
00069         return power_;
00070 }
00071 
00072 inline double QoSLevel::speed () const
00073 {
00074         return speed_;
00075 }
00076 
00077 /////////////////////////////////////////////////////////////////////////////
00078 //
00079 // Scheduler
00080 //
00081 /////////////////////////////////////////////////////////////////////////////
00082 
00083 
00084 Scheduler::Scheduler (const std::string& id, DREAM::System* system_ptr, uint CPUs)
00085 : id_ (id),
00086 CPUs_ (CPUs),
00087 availableCPUs_ (CPUs),
00088 time_ (0),
00089 system_ptr_ (system_ptr),
00090 verbose_ (false)
00091 {
00092 }
00093 
00094 Scheduler::~Scheduler ()
00095 {
00096         std::for_each (thread_map_.begin (), thread_map_.end (), delete_pair ());
00097 }
00098 
00099 void Scheduler::add (DREAM::Node* node_ptr, uint priority)
00100 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00101         throw (DREAM::Exception)
00102 #endif
00103 {
00104         DREAM::THREAD_MAP::iterator thread_iter = thread_map_.find (priority);
00105 
00106         if (thread_iter != thread_map_.end ())
00107         {
00108                 thread_iter->second->add (node_ptr);
00109         }
00110 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00111         else
00112         {
00113                 std::string message;
00114                 message << "Thread pool in Scheduler \"" << id_ << "\" does not have a lane with priority \"" << thread_iter->second->priority () << "\"...";
00115                 throw DREAM::Exception (message);
00116         }
00117 #endif
00118 }
00119 
00120 void Scheduler::add_error (DREAM::Task* task_ptr)
00121 {
00122         std::string message;
00123         trace (message << "MISSED DEADLINE: Node " << task_ptr->id () << " W(t) = " << task_ptr->wcet () << " D(t) = " << task_ptr->deadline () << " S(t) = " <<        task_ptr->subpriority ());
00124         error_avltree_.insert (task_ptr->id (), task_ptr);
00125 }
00126 
00127 void Scheduler::add_thread (DREAM::Thread* thread_ptr)
00128 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00129         throw (DREAM::Exception)
00130 #endif
00131 {
00132         DREAM::THREAD_MAP::iterator thread_iter = thread_map_.find (thread_ptr->priority ());
00133         std::string message;
00134 
00135 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00136         if (thread_iter != thread_map_.end ())
00137         {
00138                 std::string message;
00139                 message << "Thread pool in Scheduler \"" << id_ << "\" already has a lane with priority \"" << thread_ptr->priority () << "\"...";
00140                 throw DREAM::Exception (message);
00141         }
00142 #endif
00143 
00144         thread_map_.insert (DREAM::THREAD_PAIR (thread_ptr->priority (), thread_ptr));
00145 }
00146 
00147 #ifndef DREAM_NON_EXECUTING_TASKS
00148 void Scheduler::check_executed (const DREAM::NODE_MAP* node_map)
00149 {
00150         DREAM::NODE_MAP::const_iterator node_iter;
00151 
00152         for (node_iter = node_map->begin (); node_iter != node_map->end (); node_iter++)
00153         {
00154                 // Check nodes which were not executed
00155                 if (! (node_iter->second->executed ()) )
00156                         add_error ((DREAM::Task*) node_iter->second);
00157         }
00158 }
00159 #endif
00160 
00161 inline uint Scheduler::CPUs () const
00162 {
00163         return 0;
00164 }
00165 
00166 void Scheduler::freeCPU ()
00167 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00168         throw (DREAM::Exception)
00169 #endif
00170 {
00171         if (availableCPUs_ < CPUs_)
00172                 ++availableCPUs_;
00173 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00174         else
00175         {
00176                 std::string message;
00177                 message << "Scheduler \"" << id_ << "\" cannot free unused CPUs...";
00178                 throw DREAM::Exception (message);
00179         }
00180 #endif
00181 }
00182 
00183 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00184 DREAM::Thread* Scheduler::get_thread (uint priority) const
00185         throw (DREAM::Exception)
00186 #else
00187 DREAM::Thread* Scheduler::get_thread (uint priority) const
00188 #endif
00189 {
00190 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00191         if (thread_map_.empty ())
00192                 throw DREAM::Exception ("Scheduler::get_thread () called for empty thread_map_. No Threads are managed by the Scheduler.");
00193 #endif
00194 
00195         DREAM::THREAD_MAP::const_iterator thread_iter = thread_map_.find (priority);
00196 
00197         if (thread_iter != thread_map_.end ())
00198                 return thread_iter->second;
00199 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00200         else
00201                 throw DREAM::Exception ("Scheduler::get_thread () called with invalid priority.");
00202 #else
00203         else
00204                 return NULL;
00205 #endif
00206 }
00207 
00208 bool Scheduler::highestpriority (const DREAM::Node* node_ptr) const
00209 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00210         throw (DREAM::Exception)
00211 #endif
00212 {
00213 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00214         throw DREAM::BaseClassException ("Generic Scheduler does not have priority lanes. Inherited classes may implement this function.");
00215 #else
00216         return false;
00217 #endif
00218 }
00219 
00220 inline std::string Scheduler::id () const
00221 {
00222         return id_;
00223 }
00224 
00225 bool Scheduler::lowestpriority (const DREAM::Node* node_ptr) const
00226 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00227         throw (DREAM::Exception)
00228 #endif
00229 {
00230 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00231         throw DREAM::BaseClassException ("Generic Scheduler does not have priority lanes. Inherited classes may implement this function.");
00232 #else
00233         return false;
00234 #endif
00235 }
00236 
00237 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00238 double Scheduler::next_event (bool deterministic) const
00239         throw (DREAM::Exception)
00240 #else
00241 inline double Scheduler::next_event (bool deterministic) const
00242 #endif
00243 {
00244 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00245         if (thread_map_.empty ())
00246                 throw DREAM::Exception ("Scheduler::next_event () called for empty thread_map_. No Threads are managed by the Scheduler.");
00247 #endif
00248 
00249         double time_step = 0.0;
00250 
00251         for (DREAM::THREAD_MAP::const_iterator thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00252         {
00253                 double temp = thread_iter->second->next_event ();
00254                 
00255                 if (0.0 < temp && temp < time_step)
00256                         time_step = temp;
00257                 else if (time_step == 0.0)
00258                         time_step = temp;
00259         }
00260 
00261         return time_step;
00262 }
00263 
00264 
00265 bool Scheduler::nonpreemptive () const
00266 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00267         throw (DREAM::Exception)
00268 #endif
00269 {
00270 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00271         throw DREAM::BaseClassException ("Generic Scheduler is neither preemptive nor nonpreemptive. Inherited classes may implement this function.");
00272 #else
00273         return false;
00274 #endif
00275 }
00276 
00277 
00278 inline double Scheduler::power () const
00279 {
00280         return qos_current_->power ();
00281 }
00282 
00283 
00284 void Scheduler::qos_add (DREAM::QoSLevel* qos_current)
00285 {
00286         qos_avltree_.insert (qos_current->speed (), qos_current);
00287 }
00288 
00289 
00290 void Scheduler::qos_power (const double power, DREAM::QoSLevel* low, DREAM::QoSLevel* high)
00291 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00292         throw (DREAM::Exception)
00293 #endif
00294 {
00295         QOS_AVLTREE::iterator avltree_iter;
00296 
00297         for (avltree_iter = qos_avltree_.begin (); avltree_iter != qos_avltree_.end (); avltree_iter++)
00298         {
00299                 if (power >= avltree_iter->second->power ())
00300                         break;
00301         }
00302 
00303         high = avltree_iter->second;
00304         if (power == avltree_iter->second->speed ())
00305                 low = avltree_iter->second;
00306         else
00307         {
00308                 if (avltree_iter != qos_avltree_.begin ())
00309                 {
00310                         --avltree_iter;
00311                         low = avltree_iter->second;
00312                 }
00313         }
00314 }
00315 
00316 
00317 void Scheduler::qos_speed (const double speed, DREAM::QoSLevel* low, DREAM::QoSLevel* high)
00318 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00319         throw (DREAM::Exception)
00320 #endif
00321 {
00322         QOS_AVLTREE::iterator avltree_iter;
00323 
00324         for (avltree_iter = qos_avltree_.begin (); avltree_iter != qos_avltree_.end (); avltree_iter++)
00325         {
00326                 if (speed >= avltree_iter->second->speed ())
00327                         break;
00328         }
00329 
00330         high = avltree_iter->second;
00331         if (speed == avltree_iter->second->speed ())
00332                 low = avltree_iter->second;
00333         else
00334         {
00335                 if (avltree_iter != qos_avltree_.begin ())
00336                 {
00337                         --avltree_iter;
00338                         low = avltree_iter->second;
00339                 }
00340         }
00341 }
00342 
00343 
00344 void Scheduler::erase (DREAM::Node* node_ptr, uint priority)
00345 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00346         throw (DREAM::Exception)
00347 #endif
00348 {
00349         DREAM::THREAD_MAP::iterator thread_iter = thread_map_.find (priority);
00350 
00351         if (thread_iter != thread_map_.end ())
00352         {
00353                 thread_iter->second->erase (node_ptr->id ());
00354         }
00355 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00356         else
00357         {
00358                 std::string message;
00359                 message << "Thread pool in Scheduler \"" << id_ << "\" does not have a lane with priority \"" << thread_iter->second->priority () << "\"...";
00360                 throw DREAM::Exception (message);
00361         }
00362 #endif
00363 }
00364 
00365 void Scheduler::reset ()
00366 {
00367         time_ = 0;
00368         availableCPUs_ = CPUs_;
00369         error_avltree_.clear ();
00370 
00371         std::for_each (thread_map_.begin (), thread_map_.end (), reset_pair ());
00372 }
00373 
00374 void Scheduler::schedule (bool israndom)
00375 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00376         throw (DREAM::Exception)
00377 #endif
00378 {
00379 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00380         std::string message;
00381         throw DREAM::BaseClassException
00382                  (message << "Scheduler \"" << id_ << "\" does not schedule. Use the inherited classes which implement this feature.");
00383 #endif
00384 }
00385 
00386 void Scheduler::simulate (bool verbose, bool deterministic)
00387 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00388         throw (DREAM::Exception)
00389 #endif
00390 {
00391 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00392         std::string message;
00393         throw DREAM::BaseClassException
00394                  (message << "Scheduler \"" << id_ << "\" does not simulate. Use the inherited classes which implement this feature.");
00395 #endif
00396 }
00397 
00398 inline double Scheduler::speed () const
00399 {
00400         return qos_current_->speed ();
00401 }
00402 
00403 void Scheduler::stop ()
00404 {
00405         DREAM::THREAD_MAP::iterator thread_iter;
00406         
00407 #ifndef DREAM_NON_EXECUTING_TASKS
00408         if (!Option::non_executing_tasks_)
00409         {
00410                 for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00411                 {
00412                         check_executed (thread_iter->second->get_map ());
00413                 }
00414         }
00415 #endif
00416 
00417         active_ = false;
00418 }
00419 
00420 const DREAM::System* Scheduler::system () const
00421 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00422         throw (DREAM::Exception)
00423 #endif
00424 {
00425         return system_ptr_;
00426 }
00427 
00428 DREAM::System* Scheduler::system ()
00429 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00430         throw (DREAM::Exception)
00431 #endif
00432 {
00433         return system_ptr_;
00434 }
00435 
00436 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00437 void Scheduler::take_transitions ()
00438         throw (DREAM::Exception)
00439 #else
00440 inline void Scheduler::take_transitions ()
00441 #endif
00442 {
00443 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00444         if (thread_map_.empty ())
00445                 throw DREAM::Exception ("Scheduler::take_transitions () called for empty thread_map_. No Threads are managed by the Scheduler.");
00446 #endif
00447 
00448         DREAM::THREAD_MAP::iterator thread_iter;
00449         
00450         std::for_each (thread_map_.begin (), thread_map_.end (), transition_pair ());
00451 }
00452 
00453 const DREAM::THREAD_MAP* Scheduler::thread_map () const
00454 {
00455         return &thread_map_;
00456 }
00457 
00458 uint Scheduler::threadpoolsize () const
00459 {
00460         return thread_map_.size ();
00461 }
00462 
00463 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00464 double Scheduler::time () const
00465         throw (DREAM::Exception)
00466 #else
00467 inline double Scheduler::time () const
00468 #endif
00469 {
00470         return time_;
00471 }
00472 
00473 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00474 void Scheduler::time_step (double time_step)
00475         throw (DREAM::Exception)
00476 #else
00477 inline void Scheduler::time_step (double time_step)
00478 #endif
00479 {
00480 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00481         if (thread_map_.empty ())
00482                 throw DREAM::Exception ("Scheduler::time_step () called for empty thread_map_. No Threads are managed by the Scheduler.");
00483 #endif
00484 
00485         time_ += time_step;
00486 
00487         for (DREAM::THREAD_MAP::iterator thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00488         {
00489                 thread_iter->second->time_step (time_step);
00490         }
00491 }
00492 
00493 void Scheduler::trace (const std::string& output) const
00494 {
00495         if (verbose_)
00496         {
00497                 std::string message;
00498                 message << time_ << ": " << id_ << " " << output;
00499                 std::cout << message << std::endl;
00500         }
00501 }
00502 
00503 inline void Scheduler::verbose (bool verbose)
00504 {
00505         verbose_ = verbose;
00506 }
00507 
00508 void Scheduler::visitor_error_avltree (DREAM::TASK_AVLTREE* task_avltree)
00509 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00510         throw (DREAM::Exception)
00511 #endif
00512 {
00513         DREAM::TASK_AVLTREE::iterator task_iter;
00514 
00515         for (task_iter = error_avltree_.begin (); task_iter != error_avltree_.end (); task_iter++)
00516         {
00517                 task_avltree->insert (task_iter->first, task_iter->second);
00518         }
00519 }
00520 
00521 void Scheduler::visitor_if (DREAM::NODE_MAP* task_map, DREAM::NODE_MAP* channel_map, DREAM::NODE_MAP* timer_map, std::ofstream& f_stream)
00522 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00523         throw (DREAM::Exception)
00524 #endif
00525 {
00526         DREAM::THREAD_MAP::iterator thread_iter;
00527 
00528         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00529         {
00530                 thread_iter->second->visitor_if (task_map, channel_map, timer_map, f_stream);
00531         }
00532 }
00533 
00534 void Scheduler::visitor_map (DREAM::NODE_MAP* task_map, DREAM::NODE_MAP* channel_map, DREAM::NODE_MAP* timer_map)
00535 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00536         throw (DREAM::Exception)
00537 #endif
00538 {
00539         DREAM::THREAD_MAP::iterator thread_iter;
00540 
00541         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00542         {
00543                 thread_iter->second->visitor_map (task_map, channel_map, timer_map);
00544         }
00545 }
00546 
00547 void Scheduler::visitor_task_avltree (DREAM::TASK_AVLTREE* task_avltree)
00548 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00549         throw (DREAM::Exception)
00550 #endif
00551 {
00552         DREAM::THREAD_MAP::iterator thread_iter;
00553 
00554         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00555         {
00556                 thread_iter->second->visitor_task_avltree (task_avltree);
00557         }
00558 }
00559 
00560 void Scheduler::visitor_update_task_avltree (DREAM::TASK_AVLTREE* task_avltree)
00561 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00562         throw (DREAM::Exception)
00563 #endif
00564 {
00565         DREAM::THREAD_MAP::iterator thread_iter;
00566 
00567         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00568         {
00569                 thread_iter->second->visitor_update_task_avltree (task_avltree);
00570         }
00571 }
00572 
00573 void Scheduler::visitor_uppaal (DREAM::NODE_MAP* task_map, DREAM::NODE_MAP* channel_map, DREAM::NODE_MAP* timer_map, std::ofstream& f_stream)
00574 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00575         throw (DREAM::Exception)
00576 #endif
00577 {
00578         DREAM::THREAD_MAP::iterator thread_iter;
00579 
00580         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00581         {
00582                 thread_iter->second->visitor_uppaal (task_map, channel_map, timer_map, f_stream);
00583         }
00584 }
00585 
00586 /////////////////////////////////////////////////////////////////////////////
00587 //
00588 // NonConcurrentScheduler
00589 //
00590 /////////////////////////////////////////////////////////////////////////////
00591 
00592 NonConcurrentScheduler::NonConcurrentScheduler (const std::string& id, DREAM::System* system_ptr)
00593 : DREAM::Scheduler (id, system_ptr, 1)
00594 {
00595 }
00596 
00597 NonConcurrentScheduler::~NonConcurrentScheduler ()
00598 {
00599 }
00600 
00601 void NonConcurrentScheduler::schedule (bool israndom)
00602 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00603         throw (DREAM::Exception)
00604 #endif
00605 {
00606         std::for_each (thread_map_.begin (), thread_map_.end (), transition_pair ());
00607 }
00608 
00609 /////////////////////////////////////////////////////////////////////////////
00610 //
00611 // FixedPriorityScheduler
00612 //
00613 /////////////////////////////////////////////////////////////////////////////
00614 
00615 FixedPriorityScheduler::FixedPriorityScheduler (const std::string& id, DREAM::System* system_ptr, uint CPUs)
00616 : DREAM::Scheduler (id, system_ptr, CPUs)
00617 {
00618 }
00619 
00620 FixedPriorityScheduler::~FixedPriorityScheduler ()
00621 {
00622 }
00623 
00624 inline uint FixedPriorityScheduler::CPUs () const
00625 {
00626         return CPUs_;
00627 }
00628 
00629 bool FixedPriorityScheduler::highestpriority (const DREAM::Node* node_ptr) const
00630 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00631         throw (DREAM::Exception)
00632 #endif
00633 {
00634         DREAM::THREAD_MAP::const_iterator thread_iter;
00635 
00636         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00637         {
00638                 if (thread_iter->first < node_ptr->priority ())
00639                         return false;
00640         }
00641 
00642         return true;
00643 }
00644 
00645 bool FixedPriorityScheduler::lowestpriority (const DREAM::Node* node_ptr) const
00646 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00647         throw (DREAM::Exception)
00648 #endif
00649 {
00650         DREAM::THREAD_MAP::const_iterator thread_iter;
00651 
00652         for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00653         {
00654                 if (thread_iter->first > node_ptr->priority ())
00655                         return false;
00656         }
00657 
00658         return true;
00659 }
00660 
00661 bool FixedPriorityScheduler::nonpreemptive () const
00662 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00663         throw (DREAM::Exception)
00664 #endif
00665 {
00666         return (thread_map_.size () == 1) ? true : false;
00667 }
00668 
00669 void FixedPriorityScheduler::schedule (bool deterministic)
00670         throw (DREAM::Exception)
00671 {
00672         while (0 < availableCPUs_)
00673         {
00674                 uint priority = maxuint;
00675                 uint subpriority = maxuint;
00676 
00677                 DREAM::THREAD_MAP::const_iterator thread_iter;
00678                 for (thread_iter = thread_map_.begin (); thread_iter != thread_map_.end (); thread_iter++)
00679                         if (thread_iter->second->schedulable ())
00680                                 if ((priority == maxuint) || (thread_iter->first < priority))
00681                                         priority = thread_iter->first;
00682 
00683                 if (priority == maxuint)
00684                 {
00685                         // No schedulable threads
00686 #ifdef DREAM_VERBOSE2
00687                         if (Option::verbose1_ && Option::verbose2_)
00688                                 trace ("No schedulable threads");
00689 #endif
00690                         return;
00691                 }
00692 
00693                 DREAM::Thread* thread_ptr = 
00694                         thread_map_.find (priority)->second;
00695 
00696                 const DREAM::NODE_MAP* exec_map_ptr =
00697                         thread_ptr->get_exec_map ();
00698 
00699                 // thread might be a priority lane with multiple threads
00700                 while ((0 < thread_ptr->availablethreads ()) && (0 < availableCPUs_))
00701                 {
00702 
00703                         // Nodes can get deleted from the map while processed
00704                         DREAM::NODE_MAP::const_iterator exec_iter;
00705                         exec_iter = exec_map_ptr->begin ();
00706 
00707                         while (exec_iter != exec_map_ptr->end ())
00708                         {
00709                                 DREAM::Node* node_ptr = exec_iter->second;
00710 
00711                                 DREAM::NODE_MAP::const_iterator exec_iter_next = exec_iter;
00712 
00713                                 if (subpriority == maxuint)
00714                                         subpriority = node_ptr->subpriority ();
00715 
00716                                 // Pick highest subpriority node
00717                                 // Lower number - higher priority
00718                                 if (node_ptr->subpriority () < subpriority)
00719                                         subpriority = node_ptr->subpriority ();
00720 
00721                                 exec_iter = ++exec_iter_next;
00722                         }
00723 
00724                         DREAM::TASK_AVLTREE task_avltree;
00725 
00726                         for (exec_iter = exec_map_ptr->begin (); exec_iter != exec_map_ptr->end (); exec_iter++)
00727                                 if (exec_iter->second->subpriority () == subpriority)
00728                                         task_avltree.insert (exec_iter->first, static_cast <DREAM::Task*> (exec_iter->second));
00729 
00730                         // Check if the solution is unique
00731                         uint size = task_avltree.size ();
00732 
00733                         DREAM::Task *exec_ptr;
00734 
00735                         // Let's pick a random high sub-priority task...
00736                         if (size > 1)
00737                                 if (!deterministic)
00738                                         exec_ptr = task_avltree[ (uint) random (task_avltree.size ())];
00739                                 else
00740                                         throw DREAM::Exception ("Same sub-priorities found in deterministic schedule. The method does not deal with this problem...");
00741                         else
00742                                 exec_ptr = task_avltree.begin ()->second;
00743 
00744 #ifdef DREAM_RACE_CONDITION
00745                         if (Option::race_condition_)
00746                         {
00747                                 if (thread_ptr->recent (exec_ptr))
00748                                 {
00749                                         const DREAM::TASK_AVLTREE* task_avltree_ptr = thread_ptr->get_recent_avltree ();
00750 
00751                                         DREAM::TASK_AVLTREE::const_iterator task_iter;
00752                                         bool comma = false;
00753                                         std::string message;
00754                                         message << "Race condition between ";
00755 
00756                                         for (task_iter = task_avltree_ptr->begin (); task_iter != task_avltree_ptr->end (); task_iter++)
00757                                         {
00758                                                 if (!comma)
00759                                                         comma = true;
00760                                                 else
00761                                                         message << ", ";
00762 
00763                                                 message << task_iter->first << "";
00764                                         }
00765 
00766                                         thread_ptr->trace (message);
00767 
00768                                         // Check which task should actually execute now
00769                                         if (deterministic)
00770 #ifndef DREAM_RACE_CONDITION_ZERO
00771                                                 if (!exec_ptr->zero_delay_race_condition (system_ptr_))
00772                                                         exec_ptr = thread_ptr->scheduler ()->system ()->find_current (task_avltree_ptr, exec_ptr);
00773                                                 else
00774                                                 {
00775                                                         std::string message2;
00776                                                         trace (message2 << "Ignoring race condition between zero-time events");
00777                                                 }
00778 #else
00779                                                 exec_ptr = thread_ptr->scheduler ()->system ()->find_current (task_avltree_ptr, exec_ptr);
00780 #endif
00781                                         else
00782                                         {
00783 #ifndef DREAM_RACE_CONDITION_ZERO
00784                                                 if (!exec_ptr->zero_delay_race_condition (system_ptr_))
00785                                                         exec_ptr = (*task_avltree_ptr) [ (uint) random (task_avltree_ptr->size ())];
00786                                                 else
00787                                                 {
00788                                                         std::string message2;
00789                                                         trace (message2 << "Ignoring race condition between zero-time events");
00790                                                 }
00791 #else
00792                                                 exec_ptr = (*task_avltree_ptr) [ (uint) random (task_avltree_ptr->size ())];
00793 #endif
00794                                         }
00795                                 }
00796                         }
00797 #endif
00798 
00799 #ifdef DREAM_VERBOSE2
00800                         if (Option::verbose1_ && Option::verbose2_)
00801                         {
00802                                 std::string message3;
00803                                 if (size > 1)
00804                                         trace (message3 << "Node " << exec_ptr->id () << " S(t) = " << exec_ptr->subpriority () << " scheduled for execution non-deterministically");
00805                                 else
00806                                         trace (message3 << "Node " << exec_ptr->id () << " S(t) = " << exec_ptr->subpriority () << " scheduled for execution");
00807                         }
00808 #endif
00809 
00810                         thread_ptr->usethread ();
00811                         --availableCPUs_;
00812                         exec_ptr->execute ();
00813                 }
00814         }
00815 }
00816 
00817 void FixedPriorityScheduler::simulate (bool verbose, bool deterministic)
00818 #ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
00819         throw (DREAM::Exception)
00820 #endif
00821 {
00822         if (verbose)
00823                 if (deterministic)
00824                         std::cout << std::endl << "DREAM http://dre.sourceforge.net" << std::endl
00825                                 << "Deterministic discrete event simulation." << std::endl << std::endl;
00826                 else
00827                         std::cout << std::endl << "DREAM http://dre.sourceforge.net" << std::endl
00828                                 << "Non-deterministic discrete event simulation." << std::endl << std::endl;
00829 
00830         verbose_ = verbose;
00831         active_ = true;
00832         double step;
00833 
00834         while (active_)
00835         {
00836                 step = next_event (deterministic);
00837 
00838                 time_step (step);
00839 
00840                 take_transitions ();
00841 
00842                 schedule (deterministic);
00843 
00844                 if (time_ >= Option::simulation_time_)
00845                 {
00846                         stop ();
00847                         trace ("Simulation ended");
00848                 }
00849         }
00850 
00851         verbose_ = false;
00852 }
00853 
00854 }
00855 

Generated on Fri Jul 27 18:30:03 2007 for DREAM by  doxygen 1.5.1