Scheduler.h

Go to the documentation of this file.

/** @file Scheduler.h
* @author Gabor Madl
* @date Created 02/2005
* @brief Scheduler model implementation.
*
*
* =================================================================
* DREAM License v2.0
* 
* DREAM - Distributed Real-time Embedded Analysis Method
* http://dre.sourceforge.net.
* Copyright (c) 2005-2007 Gabor Madl, All Rights Reserved.
* 
* This file is part of DREAM.
* 
* DREAM is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation. No future versions of
* the GPL license may be automatically applied to DREAM. It is in
* the sole discretion of the copyright holder to determine whether
* DREAM may be released under a different license or terms. There
* are no restrictions on the use of DREAM for any purpose.
* 
* DREAM 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 for more details.
* 
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
* 
* By submitting comments, suggestions, code, code snippets,
* techniques (including that of usage), and algorithms, submitters
* acknowledge that they have the right to do so, that any such
* submissions are given freely and unreservedly, and that they
* waive any claims to copyright or ownership. In addition,
* submitters acknowledge that any such submission might become
* part of the copyright maintained on the overall body of code,
* which comprises DREAM. By making a submission, submitter agrees
* to these terms. Furthermore, submitters acknowledge that the
* incorporation or modification of such submissions is entirely
* at the discretion of the moderators of the DREAM project.
* 
* DREAM links to the Libxml2 third party library. Please see 
* COPYING-libxml for the copyright information of Libxml2.
* =================================================================
*/

#ifndef DREAM_SCHEDULER
#define DREAM_SCHEDULER

namespace DREAM
{
        class Scheduler;
        class System;
}

#include "Task.h"
#include "Thread.h"
#include "Exception.h"
#include "System.h"

namespace DREAM
{

struct take_transitions;

/** The base class for QoS properties.
* The base class that contains QoS properties for the Schedulers. The current implementation captures voltage- and frequency-scaling.
* @todo Implement dynamic power modeling using this class.
*/
class QoSLevel
{
public:
        /** Constructor for the class.
        * @param speed is the speed corresponding to the QoS-level.
        * @param power is the power level corresponding to the QoS-level.
        */
        QoSLevel (const double speed, const double power);

        /** Destructor. */
        ~QoSLevel () {};

        /** Returns the speed parameter. */
        double speed () const;

        /** Returns the power parameter. */
        double power () const;

protected:
        /** The speed corresponding to the QoS-level. */
        const double speed_;

        /** The power level corresponding to the QoS-level. */
        const double power_;
};

/** Basic Scheduler model.
* The base class of the Scheduler implementation in the DRE Semantic Domain.
*/
class Scheduler
{
public:
        /** Constructor. */
        Scheduler (const std::string& id, DREAM::System* system_ptr, uint CPUs = 1);

        /** Destructor. */
        virtual ~Scheduler ();

        /** Puts a Node into the Scheduler pool - thread_map_.
        * This function implements the mapping of Nodes to a platform processor in the
        * DRE Semantic Domain. The scheduler will know about this Node and manage its execution.
        * @param node_ptr is a pointer to the Node which will be put in the Scheduler pool - thread_map_.
        * @param priority specifies the priority of the Thread to which the Node will be added.
        */
        virtual void add (DREAM::Node* node_ptr, uint priority)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Adds a Task in the error AVL tree - error_avltree_.
        * @param task_ptr is a pointer to the Task which will be put in the error AVL tree - error_avltree_.
        */
        virtual void add_error (DREAM::Task* task_ptr);

        /** Adds a Thread into the Scheduler pool - thread_map_.
        * This function implements the mapping of Threads to a platform processor in the
        * DRE Semantic Domain. The scheduler will know about this Thread and manage its execution.
        * @param thread_ptr is a pointer to the Thread which will be put in the Scheduler pool - thread_map_.
        */
        virtual void add_thread (DREAM::Thread* thread_ptr)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the number of CPUs managed by the Scheduler. 
        * It returns 0 by default because non-concurrent Schedulers do not need a CPU, it is only used in the DREAM implementation.
        */
        virtual uint CPUs () const;

        /** Frees an available CPU (Resource) of the Scheduler. */
        virtual void freeCPU ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns a Thread from the list.
        * @param priority specifies the priority of the Thread to be returned.
        * @return pointer to the Thread.
        */
        virtual DREAM::Thread* get_thread (uint priority) const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Generic Schedulers do not have priority lanes.
        * Inherited classes may implement this feature.
        */
        virtual bool highestpriority (const DREAM::Node* node_ptr) const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the name of the Scheduler.
        * @return The id_ of the Scheduler.
        */
        virtual std::string id () const;

        /** Generic Schedulers do not have priority lanes.
        * Inherited classes may implement this feature.
        */
        virtual bool lowestpriority (const DREAM::Node* node_ptr) const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Return the time of the next event generated by the thread_map_. */
        virtual double next_event (bool deterministic) const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** The generic scheduler does not implement this function. Throws Exception. */
        virtual bool nonpreemptive () const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the power level cooresponding to the current QoS level. */
        virtual double power () const;

        /** Adds a QoS level to the Scheduler.
        * Note that the Scheduler has the ownership of the QoSLevel data structure and it manages its lifecycle.
        * @param qos_ptr is the pointer to the QoSLevel data structure.
        */
        virtual void qos_add (DREAM::QoSLevel* qos_ptr);

        /** Returns the two QoSLevels closest to the parameter power level, one consuming less, the other consuming more than the parameter.
        * If the parameter power level can be found then both the low and the high values will refer to the optimal QoSLevel object. 
        * If not, the two closest mathes are obtained. We build on the assumption that faster QoS levels involve larger power levels.
        * This case is ture in general as power is in a squared relation with speed. Special cases might be implemented later...
        * @param power is the parameter power level for which we would like to find the QoSLevel objects.
        * @param low is set to the fastest speed that is not faster than the speed parameter.
        * @param high is set to the slowest speed that is not slower than the speed parameter.
        */
        virtual void qos_power (const double power, DREAM::QoSLevel* low, DREAM::QoSLevel* high)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the two QoSLevels closest to the parameter speed, one being slower the other being faster than the parameter.
        * If the parameter speed can be found then both the low and the high values will refer to the optimal QoSLevel object. If not, the two closest mathes are obtained.
        * @param speed is the parameter speed for which we would like to find the QoSLevel objects.
        * @param low is set to the fastest speed that is not faster than the speed parameter.
        * @param high is set to the slowest speed that is not slower than the speed parameter.
        */
        virtual void qos_speed (const double speed, DREAM::QoSLevel* low, DREAM::QoSLevel* high)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Removes a Node from the Scheduler pool - thread_map_.
        * This function is called when redeploying Nodes to different platform processors.      
        * @param node_ptr is a pointer to the Node which will be removed from the Scheduler pool - thread_map_.
        * @param priority specifies the priority of the Thread from which the Node will be deleted.
        */
        virtual void erase (DREAM::Node* node_ptr, uint priority)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Resets Nodes managed by the scheduler (when restarting the simulation). */
        virtual void reset ();

        /** Generic Schedulers do not schedule.
        * Inherited classes may implement this feature.
        */
        virtual void schedule (bool deterministic)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Generic Schedulers do not simulate.
        * Inherited classes may implement this feature.
        */
        virtual void simulate (bool verbose, bool deterministic = false)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the speed corresponding to the current QoS level. */
        virtual double speed () const;

        /** Stops the Scheduler. */
        virtual void stop ();

        /** Returns the System that owns the Scheduler. */
        virtual const DREAM::System* system () const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the System that owns the Scheduler. */
        virtual DREAM::System* system ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Takes transitions in every Thread in the thread_map_. */
        virtual void take_transitions ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns the Thread map thread_map_. */
        virtual const DREAM::THREAD_MAP* thread_map () const;

        /** Return the size of the thread pool - thread_map_. */
        virtual uint threadpoolsize () const;

        /** Returns the (global) time of the Scheduler. */
        virtual double time () const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Time jump.
        * @param time_step specifies the time step to be made.
        */
        virtual void time_step (double time_step)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Function used to output info.
        * @param output is the std::string to be displayed.
        */
        virtual void trace (const std::string& output) const;

        /** Specifies whether simulation messages will be supressed or not.     */
        virtual void verbose (bool value);

        /** This function builds the error list.
        * The function is used by genetic algorithms.
        * @param task_avltree stores the list of Nodes from the Scheduler error list.
        */
        virtual void visitor_error_avltree (DREAM::TASK_AVLTREE* task_avltree)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** This function is part of the IF system description generator.
        * @param task_map stores the Task pointers.
        * @param channel_map stores the Channel pointers.
        * @param timer_map stores the Timer pointers.
        * @param f_stream is the output stream to be written to.
        */
        virtual void visitor_if (DREAM::NODE_MAP* task_map, DREAM::NODE_MAP* channel_map, DREAM::NODE_MAP* timer_map, std::ofstream& f_stream)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** This function fills the IDs (names) of tasks, channels and timers to the parameter lists.
        * The function is used to generate output for model checkers.
        * @param task_map stores the Task pointers.
        * @param channel_map stores the Channel pointers.
        * @param timer_map stores the Timer pointers.
        */
        virtual void visitor_map (DREAM::NODE_MAP* task_map, DREAM::NODE_MAP* channel_map, 
                DREAM::NODE_MAP* timer_map)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                        throw (DREAM::Exception)
#endif
        ;

        /** This function builds the task list for manipulation.
        * The function is used by genetic algorithms.
        * @param task_avltree stores the Task pointers.
        */
        virtual void visitor_task_avltree (DREAM::TASK_AVLTREE* task_avltree)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** This function updates task values in the system.
        * The function is used by genetic algorithms.
        * @param task_avltree stores the Task pointers.
        */
        virtual void visitor_update_task_avltree (DREAM::TASK_AVLTREE* task_avltree)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** This function is part of the Uppaal system description generator.
        * @param task_map stores the Task pointers.
        * @param channel_map stores the Channel pointers.
        * @param timer_map stores the Timer pointers.
        * @param f_stream is the output stream to be written to.
        */
        virtual void visitor_uppaal (DREAM::NODE_MAP* task_map, DREAM::NODE_MAP* channel_map, 
                DREAM::NODE_MAP* timer_map, std::ofstream& f_stream)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                        throw (DREAM::Exception)
#endif
        ;

protected:

#ifndef DREAM_NON_EXECUTING_TASKS
        /** Puts non-executed nodes in the error AVL tree.
        * @param node_map specifies the map which is checked for non-executed Nodes.
        */
        virtual void check_executed (const DREAM::NODE_MAP* node_map);
#endif

        /** Flag to signal end of event loop. */
        bool active_;

        /** The number of available Processors (Resources) which can execute Threads. */
        uint availableCPUs_;

        /** The number of Processors (Resources) which can execute Threads. */
        uint CPUs_;

        /** The name of the Scheduler. */
        std::string id_;

        /** Queue for Tasks that missed the deadline etc. */
        DREAM::TASK_AVLTREE error_avltree_;

        /** List of all the Threads managed by the Scheduler - the Scheduler thread pool. */
        DREAM::THREAD_MAP thread_map_;

        /** Clock for the Scheduler. */
        double time_;

        /** Specifies whether simulation messages will be supressed or not. */
        bool verbose_;

        /** A map that stores the available QoS levels for this Scheduler. */
        QOS_AVLTREE qos_avltree_;

        /** Pointer to the current QoS-level. */
        QoSLevel* qos_current_;

        /** Pointer to the system.
        * Used by tasks to figure out their next branching points.
        */
        DREAM::System* system_ptr_;
};


/** Non-concurrent Scheduler model.
* This implementation can be used to manage non-concurrent Nodes such as Channels the DRE Semantic Domain.
*/
class NonConcurrentScheduler : public DREAM::Scheduler
{
public:
        /** Constructor. */
        NonConcurrentScheduler (const std::string& id, DREAM::System* system_ptr);

        /** Destructor. */
        virtual ~NonConcurrentScheduler ();

        /** Schedules a Node for execution in a non-concurrent fashion. */
        virtual void schedule (bool israndom = true)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;
};

/** Fixed priority-based Scheduler model.
* This class is the implementation of the static priority-based Scheduler in the DRE Semantic Domain.
*/
class FixedPriorityScheduler : public DREAM::Scheduler
{
public:
        /** Constructor. */
        FixedPriorityScheduler (const std::string& id, DREAM::System* system_ptr, uint CPUs = 1);

        /** Destructor. */
        virtual ~FixedPriorityScheduler ();

        /** Returns the number of CPUs managed by the FixedPriorityScheduler. */
        virtual uint CPUs () const;

        /** Returns true if the Task is deployed on the highest priority Thread. */
        virtual bool highestpriority (const DREAM::Node* node_ptr) const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns true if the Task is deployed on the lowest priority Thread. */
        virtual bool lowestpriority (const DREAM::Node* node_ptr) const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Returns true if the Scheduler is non-preemptive (has only 1 thread). */
        virtual bool nonpreemptive () const
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Schedules a Node for execution.
        * This function will choose the highest subpriority Node in the highest priority frame and schedule it for execution
        * by calling Node::execute (). Multiple Tasks will be scheduled from multi-threaded Lanes on a multiprocessor platform.
        * @param deterministic specifies whether randomness is allowed.
        */
        virtual void schedule (bool deterministic)
                throw (DREAM::Exception);

        /** Starts deterministic simulation.
        * This simulation will simulate a deterministic trace of the system.
        */
        virtual void simulate (bool verbose, bool deterministic = false)
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;
};

}

#endif

---