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
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.
/**The ready queue is typically allocated dynamically during scheduler initialization.
* 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;
};
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 )
#endifMemory 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
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).
0 comments:
Post a Comment