Technical experience sharing, welcome to follow and provide guidance

RTEMS supports various scheduling algorithms, with the default being a priority-based scheduler. To understand these scheduler algorithms, this article lists the types of schedulers supported by RTEMS for subsequent testing and research.

1. Simple Priority Scheduling

The Simple Priority Scheduler is a simplified algorithm based on priority scheduling, initialized as follows:

    #define CONFIGURE_SCHEDULER_TABLE_ENTRIES 
      RTEMS_SCHEDULER_TABLE_SIMPLE( dflt, CONFIGURE_SCHEDULER_NAME )

#define SCHEDULER_SIMPLE_ENTRY_POINTS \
  { \
    _Scheduler_simple_Initialize,         /* initialize entry point */ \
    _Scheduler_simple_Schedule,           /* schedule entry point */ \
    _Scheduler_simple_Yield,              /* yield entry point */ \
    _Scheduler_simple_Block,              /* block entry point */ \
    _Scheduler_simple_Unblock,            /* unblock entry point */ \
    _Scheduler_simple_Update_priority,    /* update priority entry point */ \
    _Scheduler_default_Map_priority,      /* map priority entry point */ \
    _Scheduler_default_Unmap_priority,    /* unmap priority entry point */ \
    SCHEDULER_DEFAULT_SMP_OPERATIONS \
    _Scheduler_default_Node_initialize,   /* node initialize entry point */ \
    _Scheduler_default_Node_destroy,      /* node destroy entry point */ \
    _Scheduler_default_Release_job,       /* new period of task */ \
    _Scheduler_default_Cancel_job,        /* cancel period of task */ \
    _Scheduler_default_Start_idle         /* start idle entry point */ \
    SCHEDULER_DEFAULT_SET_AFFINITY_OPERATION \
  }

2. Priority Scheduling

The Priority Scheduler is the default priority-based scheduler, initialized as follows:

#define RTEMS_SCHEDULER_TABLE_PRIORITY( name, obj_name ) \
  { \
    &SCHEDULER_PRIORITY_CONTEXT_NAME( name ).Base.Base, \
    SCHEDULER_PRIORITY_ENTRY_POINTS, \
    RTEMS_ARRAY_SIZE( \
      SCHEDULER_PRIORITY_CONTEXT_NAME( name ).Ready \
    ) - 1, \
    ( obj_name ) \
    SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( true ) \
  }
#define SCHEDULER_PRIORITY_ENTRY_POINTS \
  { \
    _Scheduler_priority_Initialize,       /* initialize entry point */ \
    _Scheduler_priority_Schedule,         /* schedule entry point */ \
    _Scheduler_priority_Yield,            /* yield entry point */ \
    _Scheduler_priority_Block,            /* block entry point */ \
    _Scheduler_priority_Unblock,          /* unblock entry point */ \
    _Scheduler_priority_Update_priority,  /* update priority entry point */ \
    _Scheduler_default_Map_priority,      /* map priority entry point */ \
    _Scheduler_default_Unmap_priority,    /* unmap priority entry point */ \
    SCHEDULER_DEFAULT_SMP_OPERATIONS \
    _Scheduler_priority_Node_initialize,  /* node initialize entry point */ \
    _Scheduler_default_Node_destroy,      /* node destroy entry point */ \
    _Scheduler_default_Release_job,       /* new period of task */ \
    _Scheduler_default_Cancel_job,        /* cancel period of task */ \
    _Scheduler_default_Start_idle         /* start idle entry point */ \
    SCHEDULER_DEFAULT_SET_AFFINITY_OPERATION \
  }

3. Earliest Deadline First Scheduling

The Earliest Deadline First scheduling determines task priority based on the task’s deadline, initialized as follows:

#define RTEMS_SCHEDULER_TABLE_EDF( name, obj_name ) \
  { \
    &SCHEDULER_EDF_CONTEXT_NAME( name ).Base, \
    SCHEDULER_EDF_ENTRY_POINTS, \
    SCHEDULER_EDF_MAXIMUM_PRIORITY, \
    ( obj_name ) \
    SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( true ) \
  }
#define SCHEDULER_EDF_ENTRY_POINTS \
  { \
    _Scheduler_EDF_Initialize,       /* initialize entry point */ \
    _Scheduler_EDF_Schedule,         /* schedule entry point */ \
    _Scheduler_EDF_Yield,            /* yield entry point */ \
    _Scheduler_EDF_Block,            /* block entry point */ \
    _Scheduler_EDF_Unblock,          /* unblock entry point */ \
    _Scheduler_EDF_Update_priority,  /* update priority entry point */ \
    _Scheduler_EDF_Map_priority,     /* map priority entry point */ \
    _Scheduler_EDF_Unmap_priority,   /* unmap priority entry point */ \
    SCHEDULER_DEFAULT_SMP_OPERATIONS \
    _Scheduler_EDF_Node_initialize,  /* node initialize entry point */ \
    _Scheduler_default_Node_destroy, /* node destroy entry point */ \
    _Scheduler_EDF_Release_job,      /* new period of task */ \
    _Scheduler_EDF_Cancel_job,       /* cancel period of task */ \
    _Scheduler_default_Start_idle    /* start idle entry point */ \
    SCHEDULER_DEFAULT_SET_AFFINITY_OPERATION \
  }

4. Constant Bandwidth Scheduling

The Constant Bandwidth Server scheduling is an extension based on EDF, where tasks are allocated a fixed bandwidth (budget) by default, and then scheduled based on deadlines.

#define RTEMS_SCHEDULER_TABLE_CBS( name, obj_name ) \
  { \
    &SCHEDULER_CBS_CONTEXT_NAME( name ).Base, \
    SCHEDULER_CBS_ENTRY_POINTS, \
    SCHEDULER_CBS_MAXIMUM_PRIORITY, \
    ( obj_name ) \
    SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( true ) \
  }
#define SCHEDULER_CBS_ENTRY_POINTS \
  { \
    _Scheduler_EDF_Initialize,       /* initialize entry point */ \
    _Scheduler_EDF_Schedule,         /* schedule entry point */ \
    _Scheduler_EDF_Yield,            /* yield entry point */ \
    _Scheduler_EDF_Block,            /* block entry point */ \
    _Scheduler_CBS_Unblock,          /* unblock entry point */ \
    _Scheduler_EDF_Update_priority,  /* update priority entry point */ \
    _Scheduler_EDF_Map_priority,     /* map priority entry point */ \
    _Scheduler_EDF_Unmap_priority,   /* unmap priority entry point */ \
    SCHEDULER_DEFAULT_SMP_OPERATIONS \
    _Scheduler_CBS_Node_initialize,  /* node initialize entry point */ \
    _Scheduler_default_Node_destroy, /* node destroy entry point */ \
    _Scheduler_CBS_Release_job,      /* new period of task */ \
    _Scheduler_CBS_Cancel_job,       /* cancel period of task */ \
    _Scheduler_default_Start_idle    /* start idle entry point */ \
    SCHEDULER_DEFAULT_SET_AFFINITY_OPERATION \
  }

5. SMP Scheduler Extensions

To support SMP, the Simple Priority, Priority, and EDF schedulers have been extended for SMP support, as follows:

#define RTEMS_SCHEDULER_TABLE_SIMPLE_SMP( name, obj_name ) \
  { \
    &SCHEDULER_SIMPLE_SMP_CONTEXT_NAME( name ).Base.Base, \
    SCHEDULER_SIMPLE_SMP_ENTRY_POINTS, \
    SCHEDULER_SIMPLE_SMP_MAXIMUM_PRIORITY, \
    ( obj_name ) \
    SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( false ) \
  }
#define RTEMS_SCHEDULER_TABLE_PRIORITY_SMP( name, obj_name ) \
  { \
    &SCHEDULER_PRIORITY_SMP_CONTEXT_NAME( name ).Base.Base.Base, \
    SCHEDULER_PRIORITY_SMP_ENTRY_POINTS, \
    RTEMS_ARRAY_SIZE( \
      SCHEDULER_PRIORITY_SMP_CONTEXT_NAME( name ).Ready \
    ) - 1, \
    ( obj_name ) \
    SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( false ) \
  }
#define RTEMS_SCHEDULER_TABLE_EDF_SMP( name, obj_name ) \
  { \
    &SCHEDULER_EDF_SMP_CONTEXT_NAME( name ).Base.Base.Base, \
    SCHEDULER_EDF_SMP_ENTRY_POINTS, \
    SCHEDULER_EDF_MAXIMUM_PRIORITY, \
    ( obj_name ) \
    SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( false ) \
  }

6. Other Schedulers

In addition to the above schedulers, there are SMP schedulers based on CPU affinity priority, such as RTEMS_SCHEDULER_TABLE_PRIORITY_AFFINITY_SMP, which adjusts the priority-based scheduler according to CPU affinity, ensuring that a task is allowed to run only on a specific CPU.

There are also preemptive SMP schedulers that support CPU affinity settings.

7. Default System Scheduler

The default system scheduler is the priority scheduler, defined as follows:

#if !defined(CONFIGURE_SCHEDULER_CBS) \
  && !defined(CONFIGURE_SCHEDULER_EDF) \
  && !defined(CONFIGURE_SCHEDULER_EDF_SMP) \
  && !defined(CONFIGURE_SCHEDULER_PRIORITY) \
  && !defined(CONFIGURE_SCHEDULER_PRIORITY_AFFINITY_SMP) \
  && !defined(CONFIGURE_SCHEDULER_PRIORITY_SMP) \
  && !defined(CONFIGURE_SCHEDULER_SIMPLE) \
  && !defined(CONFIGURE_SCHEDULER_SIMPLE_SMP) \
  && !defined(CONFIGURE_SCHEDULER_STRONG_APA) \
  && !defined(CONFIGURE_SCHEDULER_USER)
#if defined(RTEMS_SMP) && _CONFIGURE_MAXIMUM_PROCESSORS > 1
    #define CONFIGURE_SCHEDULER_EDF_SMP
#else
    #define CONFIGURE_SCHEDULER_PRIORITY
#endif
#endif

The configuration effect is as follows:

#ifdef CONFIGURE_SCHEDULER
  /*
   * Ignore these warnings:
   *
   * - invalid use of structure with flexible array member
   *
   * - struct has no members
   */
  #pragma GCC diagnostic push
  #pragma GCC diagnostic ignored "-Wpedantic"
  CONFIGURE_SCHEDULER;
  #pragma GCC diagnostic pop
#endif

const Scheduler_Control _Scheduler_Table[] = {
  CONFIGURE_SCHEDULER_TABLE_ENTRIES
};

Then we expand the macro definitions as follows:

  static struct { Scheduler_priority_Context Base; Chain_Control Ready[ ( 255 + 1 ) ]; } _Configuration_Scheduler_priority_dflt;
const Scheduler_Control _Scheduler_Table[] = {
  { &_Configuration_Scheduler_priority_dflt.Base.Base, { _Scheduler_priority_Initialize, _Scheduler_priority_Schedule, _Scheduler_priority_Yield, _Scheduler_priority_Block, _Scheduler_priority_Unblock, _Scheduler_priority_Update_priority, _Scheduler_default_Map_priority, _Scheduler_default_Unmap_priority,

We can see that the default scheduler we configured is indeed the priority scheduler, and there is only one. Remember when we looked at the initialization code earlier, in the rtems_initialize_data_structures function, it calls _Scheduler_Handler_initialization, which is implemented as follows:

void _Scheduler_Handler_initialization(void)
{
size_t n;
size_t i;

  n = _Scheduler_Count;

for ( i = 0 ; i < n ; ++i ) {
    const Scheduler_Control *scheduler;
#if defined(RTEMS_SMP)
    Scheduler_Context       *context;
#endif

    scheduler = &_Scheduler_Table[ i ];
#if defined(RTEMS_SMP)
    context = _Scheduler_Get_context( scheduler );
#endif
    _ISR_lock_Initialize( &context->Lock, "Scheduler" );
    ( *scheduler->Operations.initialize )( scheduler );
  }
}

This directly calls the initialize function of the scheduler. Thus, the initialization of the scheduler begins.