Logo Search packages:      
Sourcecode: u++ version File versions

uDeadlineMonotonic.cc

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Philipp E. Lim 1996
// 
// uDeadlineMonotonic.cc -- 
// 
// Author           : Philipp E. Lim and Ashif S. Harji
// Created On       : Fri Oct 27 07:29:18 2000
// Last Modified By : Peter A. Buhr
// Last Modified On : Thu Aug 12 08:32:17 2004
// Update Count     : 12
//
// This  library is free  software; you  can redistribute  it and/or  modify it
// under the terms of the GNU Lesser General Public License as published by the
// Free Software  Foundation; either  version 2.1 of  the License, or  (at your
// option) any later version.
// 
// This library 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 Lesser General Public License
// for more details.
// 
// You should  have received a  copy of the  GNU Lesser General  Public License
// along  with this library.
// 

#define __U_KERNEL__
#include <uC++.h>
#include <uDeadlineMonotonic.h>


#include <uAssert.h>
//#include <uDebug.h>


// compare abstracts the comparison of two task's priorities.  The deadline is
// first checked.  If the deadlines are identical for two tasks, the period or
// frame field is checked.  Non-real-time tasks are always greater in deadline
// than real-time tasks.  Aperiodic tasks get lowest deadline or priority among
// all real-time tasks.  This compare function acts in the same way as strcmp
// in terms of return value.

int uDeadlineMonotonic::compare( uBaseTask &t1, uBaseTask &t2 ) {
    uDuration temp;
    enum Codes { PS_PS, PS_NPS, NPS_PS, R_R, R_NR, NR_R, NR_NR }; // T1_T2
    Codes taskCodes[][4] = { { NR_NR,     NR_R, NPS_PS,     NPS_PS      },
                       { R_NR,      R_R,  NPS_PS,     NPS_PS      },
                       { PS_NPS,  PS_NPS, PS_PS,      PS_PS },
                       { PS_NPS,  PS_NPS, PS_PS,      PS_PS } };

    uAssert( &t1 != NULL && &t2 != NULL );

    uRealTimeBaseTask *rbt1, *rbt2;
    uPeriodicBaseTask *pbt1, *pbt2;
    uSporadicBaseTask *sbt1 = NULL, *sbt2 = NULL;
    int index1, index2;

    rbt1 = dynamic_cast<uRealTimeBaseTask *>(&t1);
    if ( rbt1 == NULL ) {
      index1 = 0;
      pbt1 = NULL;
      sbt1 = NULL;
    } else {
      index1 = 1;

      if ( ( pbt1 = dynamic_cast<uPeriodicBaseTask *>(&t1) ) != NULL ) {
          index1 = 2;
      } else if ( ( sbt1 = dynamic_cast<uSporadicBaseTask *>(&t1) ) != NULL ) {
          index1 = 3;
      } // if
    } // if
      
    rbt2 = dynamic_cast<uRealTimeBaseTask *>(&t2);
    if ( rbt2 == NULL ) {
      index2 = 0;
      pbt2 = NULL;
      sbt2 = NULL;
    } else {
      index2 = 1;

      if ( ( pbt2 = dynamic_cast<uPeriodicBaseTask *>(&t2) ) != NULL ) {
          index2 = 2;
      } else if ( ( sbt2 = dynamic_cast<uSporadicBaseTask *>(&t2) ) != NULL ) {
          index2 = 3;
      } // if
    } // if

    switch ( taskCodes[index1][index2] ){
      case PS_PS:                         // both t1 and t2 periodic or sporadic
      temp = rbt1->uGetDeadline() - rbt2->uGetDeadline();
      if ( temp > 0 ) {
          return 1;
      } else if ( temp < 0 ) {
          return -1;
      } else {                            // real-time tasks have equal deadlines => check their periods or frames
          uDuration period1, period2;

          if ( pbt1 != NULL ) {                 // periodic ?
            period1 = pbt1->uGetPeriod();
          } else if ( sbt1  != NULL ) {         // sporadic ?
            period1 = sbt1->uGetFrame();
          } // if

          if ( pbt2 != NULL ) {                 // periodic ?
            period2 = pbt2->uGetPeriod();
          } else if ( sbt2  != NULL ) {         // sporadic ?
            period2 = sbt2->uGetFrame();
          } // if

          temp = period1 - period2;
          return (temp > 0) ? 1 : (temp < 0) ? -1 : 0;
      } // if
      break;

      case PS_NPS:                              // t1 periodic or sporadic and t2 is not ?
      return -1;
      break;

      case NPS_PS:                              // t1 is not and t2 periodic or sporadic ?
      return 1;
      break;

      case R_R:                                 // both t1 and t2 aperiodic
      temp = rbt1->uGetDeadline() - rbt2->uGetDeadline();
      return (temp > 0) ? 1 : (temp < 0) ? -1 : 0;
      break;

      case R_NR:                          // t1 aperiodic and t2 is not ?
      return -1;
      break;

      case NR_R:                          // t1 is not and t2 is aperiodic ?
      return 1;
      break;

      case NR_NR:                         // both t1 and t1 are non-real-time
      return 0;
      break;

      default:
      uAbort( "(uDeadlineMonotonic *)0x%p.compare : internal error.", this );
      break;
    } // switch
} // uDeadlineMonotonic::compare


void uDeadlineMonotonic::uAddInitialize( uSequence<uBaseTaskDL> &TaskList ) {
#ifdef __U_DEBUG_H__
    uDebugPrt( "(uDeadlineMonotonic &)0x%p.uAddInitialize: enter\n" );
#endif // __U_DEBUG_H__
    uSequence<uBaseTaskDL> List;
    uSeqGen<uBaseTaskDL> i;
    int cnt = 0;
    uBaseTaskDL *ref = NULL, *prev = NULL, *node = NULL;

    // The cluster's list of tasks is maintained in sorted order. This
    // algorithm relies on the kernel code adding new tasks to the end of the
    // cluster's list of tasks.  (Perhaps better to combine adding tasks to a
    // cluster list with initializing newly scheduled tasks so only one call is
    // made in uTaskAdd.)

    uRealTimeBaseTask *rtb = dynamic_cast<uRealTimeBaseTask *>(&(TaskList.uTail()->uGet()));

    if ( rtb == NULL ) {
#ifdef __U_DEBUG_H__
      uDebugPrt( "(uDeadlineMonotonic &)0x%p.uAddInitialize: exit1\n" );
#endif // __U_DEBUG_H__
      return;
    } // exit

    ref = TaskList.uDropTail();

    if ( ref == NULL ) {                        // necessary if uAddInitialize is called from uRemoveInitialize
#ifdef __U_DEBUG_H__
      uDebugPrt( "(uDeadlineMonotonic &)0x%p.uAddInitialize: exit2\n" );
#endif // __U_DEBUG_H__
      return;
    } // exit

    for ( i.uOver(TaskList), prev = NULL; i >> node ; prev = node ) { // find place in the list to insert
      if ( compare( ref->uGet(), node->uGet() ) < 0 ) break;
    } // for
    TaskList.uInsertBef( ref, node );

    // Find out if task was ever on cluster, if so compare verCount with
    // verCount for cluster.  If different or first visit recalculate
    // otherwise, stop after putting task back into task list

    if ( verCount == (unsigned int)rtb->uGetVersion( uThisCluster() ) ) {
#ifdef __U_DEBUG_H__
      uDebugPrt( "(uDeadlineMonotonic &)0x%p.uAddInitialize: exit3\n" );
#endif // __U_DEBUG_H__
      return;
    } // exit

    // either new task or verCounts differ, increment verCount and continue
    verCount += 1;

    for ( i.uOver( TaskList ), cnt = 0, prev = TaskList.uHead(); i >> node; prev = node ) { 
      if ( compare( prev->uGet(), node->uGet() ) != 0 ) {
          cnt += 1;
      } // if
      uBaseTask &t = node->uGet();
      uRealTimeBaseTask *rt = dynamic_cast<uRealTimeBaseTask *>(&t);
      if ( rt != NULL ) {
          uSetBasePriority( *rt, cnt );
          rt->uSetVersion( uThisCluster(), verCount );
          uSetActivePriority( *rt, uGetInheritTask( *rt ) );
      } else {
          if ( uGetBasePriority( t ) == 0 ) {   // if first time, intialize priority for nonreal-time task
            uSetBasePriority( t, __U_MAX_NUMBER_PRIORITIES__ - 1);
          } // if
          uSetActivePriority( t, uGetInheritTask( t ) );
      } // if 
    } // for

    if ( cnt > __U_MAX_NUMBER_PRIORITIES__ ) {
      uAbort( "(uDeadlineMonotonic &)0x%p.uAddInitialize : cannot schedule task as more priorities are needed than current limit of %d.",
            this, __U_MAX_NUMBER_PRIORITIES__ );
    } // if

    while( ! uEmpty() ) {                       // re-arrange ready-queue
      List.uInsertBef( uDrop(), NULL );
    } // while
    while( ! List.uEmpty() ) {
      uAdd( List.uDropHead() );
    } // while

#ifdef __U_DEBUG_H__
//    uSeqGen<uBaseTaskDL> j;
//    uBaseTaskDL *ptr = NULL;
//      for (j.uOver(TaskList); j >> ptr; ) {
//          fprintf(stderr, "0x%p Task with priority %d\n", &(ptr->uGet()), ptr->uGet().uGetActivePriority());
//      }
//      fprintf(stderr, "Leaving uInitialize! \n");
      uDebugPrt( "(uDeadlineMonotonic &)0x%p.uAddInitialize: exit4\n" );
#endif // __U_DEBUG_H__
} // uDeadlineMonotonic::uAddInitialize


void uDeadlineMonotonic::uRemoveInitialize( uSequence<uBaseTaskDL> & ) {
    // Although removing a task may leave a hole in the priorities, the hole
    // should not affect the ability to schedule the task or the order the
    // tasks execute. Therefore, no rescheduling is performed.

//    uAddInitialize( TaskList );
} // uDeadlineMonotonic::uRemoveInitialize


void uDeadlineMonotonic::uRescheduleTask( uBaseTaskDL *TaskNode, uBaseTaskSeq &TaskList ) {
    verCount += 1;
    TaskList.uRemove(TaskNode);
    TaskList.uAddTail(TaskNode);
    uAddInitialize(TaskList);
} // uDeadlineMonotonic::uRescheduleTask


// Local Variables: //
// compile-command: "gmake install" //
// End: //

Generated by  Doxygen 1.6.0   Back to index