Sunday, December 12, 2010

RTEMS: Adding a new scheduler

In this post I describe how to add a new scheduler implementation to the RTEMS open-source real-time operating system. The scheduler I use as an example is an earliest deadline first (EDF) scheduler which applies the EDF algorithm to schedule periodic tasks and a FIFO policy for non-periodic tasks.  This post demonstrates how to use my modular scheduling framework to extend the scheduling capabilities of RTEMS.



Adding a new scheduler implementation using my framework involves modifying and adding files.  Modified files add the configuration points for the new scheduler and define the internal scheduler data structures that are passed through the scheduling interface. New files implement the new scheduler algorithm. I have submitted these proposed changes as a feature request to the RTEMS project.  With luck, the bugs are ironed out, although I ran into a couple of regressions while re-basing to the RTEMS CVS.

Modified files

The modified RTEMS files include:
  • cpukit/score/include/rtems/score/scheduler.h
  • cpukit/score/include/rtems/score/thread.h
  • cpukit/sapi/include/confdefs.h
  • cpukit/Makefile.am
  • cpukit/rtems/src/ratemonperiod.c
scheduler.h modifications
Three changes are necessary in the scheduler.h file.

First, add #define _Scheduler_EDF (2) where the _Scheduler_USER and _Scheduler_PRIORITY are defined.  Extend the numbering linearly, ordering matters.

Second, add a Scheduler_edf_Per_thread structure that contains the per-thread metadata required by the new scheduler algorithm.
/**
 * Per-thread data related to the _Scheduler_EDF scheduling policy.
 */
typedef struct {
  /** Point back to this thread. */
  Thread_Control                   *this_thread;

  /** This field contains the thread's deadline information. */
  RBTree_Node                       deadline;

  /** 
   * This field points to the last node in the ready queue that has 
   * the same deadline (absolute) as this thread.
   */
  Chain_Node                       *last_duplicate;
} Scheduler_edf_Per_thread;

Third, add to the Ready_queues union a pointer to the structure(s) used to manage ready tasks.
/**
 * This is the structure used to manage the scheduler.
 */
struct Scheduler_Control_struct {
  /**
   *  This union contains the pointer to the data structure used to manage
   *  the ready set of tasks. The pointer varies based upon the type of
   *  ready queue required by the scheduler.
   */
  union {
    /**
     * This is the set of lists (an array of Chain_Control) for
     * priority scheduling.
     */
    Chain_Control                      *priority;

   /**
    * Structure containing the red-black tree, deadline-ordered, and 
    * fifo-ordered queues for EDF scheduling
    */
    struct Scheduler_edf_Ready_queue_Control  *edf;

  } Ready_queues;

  /** The jump table for scheduler-specific functions */
  Scheduler_Operations                  Operations;
};
The ready queue is typically allocated dynamically during scheduler initialization.

thread.h modifications
The only change necessary in the thread.h file is to add a pointer for the per-thread scheduling metadata within the Thread_Control structure by extending the union of pointers at the scheduler field:
/** This union holds per-thread data for the scheduler and ready queue. */
  union {
    Scheduler_priority_Per_thread      *priority;
    Scheduler_edf_Per_thread           *edf;
  } scheduler;

confdefs.h modifications
The changes to confdefs.h are a little more involved. My last post about the scheduling framework goes into detail about how I use confdefs.h to enable user-configurable scheduling.  The following demonstrates how to add a scheduler to the existing confdefs.h scheduler configuration infrastructure.

Enable the scheduler to be built when a user selects CONFIGURE_SCHEDULER_ALL:
/* enable all RTEMS-provided schedulers */
#if defined(CONFIGURE_SCHEDULER_ALL)
  #define CONFIGURE_SCHEDULER_PRIORITY
  #define CONFIGURE_SCHEDULER_EDF
#endif

Where the priority scheduler is set to the default, add a check to see if the new scheduler is configured:
/* If no scheduler is specified, the priority scheduler is default. */
#if !defined(CONFIGURE_SCHEDULER_USER) && \
    !defined(CONFIGURE_SCHEDULER_PRIORITY) && \
    !defined(CONFIGURE_SCHEDULER_EDF)
  #define CONFIGURE_SCHEDULER_PRIORITY
  #define CONFIGURE_SCHEDULER_POLICY _Scheduler_PRIORITY
#endif

If the new scheduler is configured for use, set up its initialization routine for the scheduler entry table and estimate its memory usage:
/* 
 * For additional schedulers, add a check for the configured scheduler 
 * here. Copy the above block for the priority scheduler, and then replace
 * the initialization and policy macros and update the memory usage.
 */

/* Check for EDF scheduler */
#if defined(CONFIGURE_SCHEDULER_EDF)
  #include <rtems/score/scheduleredf.h>
  #define CONFIGURE_SCHEDULER_ENTRY_EDF { _Scheduler_edf_Initialize }
  #if !defined(CONFIGURE_SCHEDULER_POLICY)
    #define CONFIGURE_SCHEDULER_POLICY _Scheduler_EDF
  #endif

  /**
   * define the memory used by the edf scheduler.
   */
  #define CONFIGURE_MEMORY_SCHEDULER_EDF ( \
    _Configure_From_workspace( \
      ((1) * sizeof(Scheduler_edf_Ready_queue_Control)) ) \
  )
  #define CONFIGURE_MEMORY_PER_TASK_SCHEDULER_EDF ( \
    _Configure_From_workspace(sizeof(Scheduler_edf_Per_thread)) )
#else
  #define CONFIGURE_MEMORY_SCHEDULER_EDF ( 0 )
  #define CONFIGURE_MEMORY_PER_TASK_SCHEDULER_EDF ( 0 )
#endif
Memory use estimates are most likely whatever is allocated during scheduler initialization (scheduleredf.c) and the overhead of the per-thread structure (scheduleredfthreadschedulerallocate.c).

Add the new scheduler's entry routine (initialization) to the Scheduler Table at the position defined by the macro in scheduler.h (_Priority_EDF, in this case 2):
#ifdef CONFIGURE_INIT
  /* the table of available schedulers. */
  const Scheduler_Table_entry _Scheduler_Table[] = {
    #if defined(CONFIGURE_SCHEDULER_USER) && \
        defined(CONFIGURE_SCHEDULER_ENTRY_USER)
      CONFIGURE_SCHEDULER_ENTRY_USER,
    #else
      CONFIGURE_SCHEDULER_NULL,
    #endif
    #if defined(CONFIGURE_SCHEDULER_PRIORITY) && \
        defined(CONFIGURE_SCHEDULER_ENTRY_PRIORITY)
      CONFIGURE_SCHEDULER_ENTRY_PRIORITY,
    #else
      CONFIGURE_SCHEDULER_NULL,
    #endif
    #if defined(CONFIGURE_SCHEDULER_EDF) && \
        defined(CONFIGURE_SCHEDULER_ENTRY_EDF)
      CONFIGURE_SCHEDULER_ENTRY_EDF,
    #else
      CONFIGURE_SCHEDULER_NULL,
    #endif   
  };
#endif

Lastly, include the memory overhead for the new scheduler in the calculation for the scheduler's memory overhead.
/**
 * Define the memory overhead for the scheduler
 */
#define CONFIGURE_MEMORY_FOR_SCHEDULER ( \
    CONFIGURE_MEMORY_SCHEDULER_PRIORITY + \
    CONFIGURE_MEMORY_SCHEDULER_EDF \
  )

#define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER ( \
    CONFIGURE_MEMORY_PER_TASK_SCHEDULER_PRIORITY + \
    CONFIGURE_MEMORY_PER_TASK_SCHEDULER_EDF \
  )

Makefile.am modifications
The changes to the cpukit/score/Makefile.am file are for compiling new files. I think this is easiest to show as a diff:
diff -u -p -r1.89 Makefile.am
--- Makefile.am    24 Nov 2010 15:51:27 -0000    1.89
+++ Makefile.am    12 Dec 2010 18:05:23 -0000
@@ -26,7 +26,8 @@ include_rtems_score_HEADERS = include/rt
     include/rtems/score/interr.h include/rtems/score/isr.h \
     include/rtems/score/object.h include/rtems/score/percpu.h \
     include/rtems/score/priority.h include/rtems/score/prioritybitmap.h \
-    include/rtems/score/scheduler.h include/rtems/score/schedulerpriority.h \
+    include/rtems/score/scheduler.h include/rtems/score/scheduleredf.h \
+    include/rtems/score/schedulerpriority.h \
     include/rtems/score/stack.h include/rtems/score/states.h \
     include/rtems/score/sysstate.h include/rtems/score/thread.h \
     include/rtems/score/threadq.h include/rtems/score/threadsync.h \
@@ -55,7 +56,8 @@ include_rtems_score_HEADERS += inline/rt
     inline/rtems/score/coresem.inl inline/rtems/score/heap.inl \
     inline/rtems/score/isr.inl inline/rtems/score/object.inl \
     inline/rtems/score/priority.inl inline/rtems/score/prioritybitmap.inl \
-    inline/rtems/score/scheduler.inl inline/rtems/score/schedulerpriority.inl \
+    inline/rtems/score/scheduler.inl inline/rtems/score/scheduleredf.inl \
+    inline/rtems/score/schedulerpriority.inl \
     inline/rtems/score/stack.inl inline/rtems/score/states.inl \
     inline/rtems/score/sysstate.inl inline/rtems/score/thread.inl \
     inline/rtems/score/threadq.inl inline/rtems/score/tod.inl \
@@ -142,15 +144,25 @@ libscore_a_SOURCES += src/objectallocate
 ## SCHEDULER_C_FILES
 libscore_a_SOURCES += src/scheduler.c
 
+## SCHEDULEREDF_C_FILES
+libscore_a_SOURCES += src/scheduleredf.c \
+    src/scheduleredfblock.c \
+    src/scheduleredfthreadschedulerallocate.c \
+    src/scheduleredfthreadschedulerfree.c \
+    src/scheduleredfthreadschedulerupdate.c \
+    src/scheduleredfschedule.c \
+    src/scheduleredfunblock.c \
+    src/scheduleredfyield.c

ratemonperiod.c modifications
Unfortunately, the EDF scheduling algorithm requires some work to be done whenever a job is released.  In particular, the absolute deadline of the released job needs to be updated.  Since the RTEMS kernel does not have a notion of periodic and non-periodic tasks, I extended the Rate Monotonic Manager to handle EDF tasks.  To support EDF tasks, all that is required is to call a small function that does some work when a job is released.  Currently, this call-out is made when initiating a periodic timer and when a periodic timer fires with or without period overrun.  The relevant code can be seen in my submission. I think this needs some additional cleaning up.
 
New files
The scheduler implementation comprises several new files.  As shown in the Makefile.am modifications above, the new files are:
  • include/rtems/score/scheduleredf.h
  • inline/rtems/score/scheduleredf.inl
  • src/
    • scheduleredf.c
    • scheduleredfblock.c
    • scheduleredfthreadschedulerallocate.c
    • scheduleredfthreadschedulerfree.c
    • scheduleredfthreadschedulerupdate.c
    • scheduleredfschedule.c
    • scheduleredfunblock.c
    • scheduleredfyield.c
I will give a brief description of the contents of each of these files, to give a sense of the organization of a scheduler implementation.  It is arbitrary what files are provided, as long as the scheduler implementation provides an initialization routine and a Scheduler_Operations table.  I tried to capture the requirements of the existing scheduler and the EDF scheduler in designing the modular scheduler, and hopefully it will support additional future schedulers without too much trouble. For details, consult the source.

scheduleredf.h
The header file for a scheduler implementation will contain the function declarations for at least the functions that are installed as pointers in the Scheduler_Operations table.  Additional internal structures and functions may be defined here.

scheduleredf.inl
The inline routines for a scheduler implementation will contain most of the ready queue manipulations and the function bodies for the functions that are reached through the Scheduler_Operations fields.  My schedulers rely on inlining to maintain a minimal call depth, since function calls are costly on some platforms.  Most of these functions are used only once or twice so that code size is not a concern (this argument may need to be revisited for the EDF code).

scheduleredf.c
Initialization of Scheduler_Operations for EDF scheduling, and also allocating and initializing the internal structures (ready queue).

scheduleredfblock.c
Called when a thread suspends. Removes the thread from scheduling and updates queues.

scheduleredfthreadschedulerallocate.c
Called when a thread is created. Allocates the per-thread scheduling data for EDF scheduling.

scheduleredfthreadschedulerfree.c
Called when a thread is destroyed. Frees the per-thread scheduling data.

scheduleredfthreadschedulerupdate.c
Called when a thread's per-thread scheduling data should be updated. Currently this is only when a priority changes.

scheduleredfschedule.c
Called when a scheduling decision is wanted, sets the heir thread according to the scheduling policy (either the earliest deadline or the oldest non-periodic task).

scheduleredfunblock.c
Called when a thread is released or resumed.  Adds the thread to scheduling queues.

scheduleredfyield.c
Called when a thread is willing to yield the processor. In the EDF scheduling, periodic tasks are not allowed to yield (i.e. this is a nop).

2 comments: