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).

Read More

Architectural simulators

As a researcher in the areas of operating systems, compilers, and computer architecture, I spend a lot of time dealing with simulators.  An inordinate amount of time.  Much of this time is spent figuring out how well a given simulator provides:

1. Useful timing measurements (cycle-accurate)
2. Support for fully functional OSs (full-system)
3. Auxiliary features for specific experiments
4. Support for useful hardware platforms and instruction sets
5. Openness to modifying microarchitectural features
6. Availability of technical support

In my current work, I'm interested in actively developed simulators that support cycle-accurate full-system simulation with a detailed memory hierarchy on out-of-order uniprocessor or multicore RISC architecture models with the SPARC, MIPS, or ARM instruction sets that supports extending the pipeline and instruction set.  The rest of this article discussed my efforts in finding simulators to meet my needs.



A brief aside: I received a complaint that I write too much, so I have taken the effort to highlight in blue the important points I want to make; coloring is less work than thinking about how to be more concise.  If you are familiar with architectural simulators, this should speed up processing my drivel.  I go in to details about the 6 features listed above, then review some architectural simulators and processor emulators with respect to the above criteria.

The first two features, cycle-accuracy and full-system simulation, tend to be unavailable simultaneously. Cycle accurate simulation improves on simulators that provide only instruction set simulation by adding detailed timing (delay) and modelling of the microarchitectural features of a processor.  Cycle accuracy has been available in open academic simulators for a number of years, with the dominant player being SimpleScalar.  However, SimpleScalar fell behind the fast-moving industry, so that its usefulness is limited in modern research although it still is an approachable system for students or for embedded systems. Full-system simulation models the low-level hardware necessary to support running an OS and applications without modification. The defining features of a full-system simulator include support for interrupts, memory management hardware (MMU / TLB), low-level buses/interconnects, peripherals (e.g. keyboard, mouse), IO devices including disk and networking, and other functionally relevant system components.

The third feature that I investigate comes in the additional architectural modelling that is provided for supporting research.  Perhaps the two most important "auxiliary" features of a simulator are a detailed memory hierarchy and an accurate power model. A detailed memory hierarchy exposes the timing and functionality of elements along the path from the CPU to main memory.  Among other things, this includes the cache parameters (line size, set size, associativity, access latency), cache behavior or policy, memory access latencies on cache misses, and, more recently, details of the interconnect between caches and memories. A detailed memory hierarchy is necessary for cycle accurate and functional simulation, although the details required by both may vary.  Accurate power estimation involves modelling the power demand of an architecture by estimating the energy dissipated by accessing architectural features (dynamic power) and the power loss due to leaking energy regardless of changes in hardware state (static/leakage power). Approaches to power estimation are derived from efforts to measure the power of real platforms using repeated executions of instructions to construct estimates of the power of accessing architectural features.  Estimates are validated by running complex workloads and measuring the observed power of a real platform and comparing it with the predicted power of the simulator.  A common tool for the microarchitecture power research in academia is WATTCH, which has been integrated in a number of simulators.  CACTI is commonly used for estimating the power dissipated by caches.  It is also important to account for memory power, especially when proposing solutions that trade-off performance and power such as dynamic voltage and frequency scaling (DVFS); current tools fall short on accounting for off-chip memory costs.

The supported hardware platforms and instruction sets of a given simulator also interacts with the ability to modify its low-level features.  Some modern simulators target the x86(_64) architecture, but since actual x86 implementations do not directly implement x86 instructions it is difficult to model x86 accurately. (Although PTLsim does claim to capture the cycle overheads of all elements of actual x86 implementations.) Instead, the hardware translates at run-time the machine code into one or more RISC-like instructions called micro-ops (μops). This indirection makes it difficult to do low-level compiler work, and pretty much impossible to build an architecture that can trap x86 instructions at the assembly language level. It is also difficult to create realistic prototypes, since the actual implementation details are obscured and proprietary.  I mainly look for support of superscalar out-of-order (OoO) RISC architectures, which are useful for architectural and language research due to the straightforward mapping from instructions to architecture pipelines while still having complexity in the pipeline. One caveat to that last statement is that many academics, and even some in industry, have stated the the future of CMP is in simpler cores; so CMP researchers may seek less sophisticated processor pipelines. Also of importance when considering what simulator to use is the set of architectures modelled, for example OoO versus in-order, superscalar vs VLIW, CMP vs SMP vs SMT vs uni, and so on.

The last two items on my list tend to be opposed to each other: open-source simulators tend to be supported by small communities of academic (graduate students) users, whereas commercially supported simulators tend to not allow much tinkering with the microarchitecture (since the source code is not open, and the simulator implementation is proprietary).  It is critical that the microarchitecture simulated be open or extensible to enable research that modifies pipeline elements, adds new features, changes dataflow and control paths, etc.  All the simulators of which I'm aware that provide enough flexibility for architectural research do so by providing the source code for modification, thus precluding proprietary/commercial simulators. There have been efforts to provide a plug-in framework for microarchitecture research, although I'm not aware of any current commercial simulators that support such plug-ins.

Simulators
The following notes cover some simulators that I have used or looked into using. The UW architecture group has a page of links that covers many of the available architecture simulators and related tools.

SimpleScalar

An easy-to-modify, academically licensed source-available cycle-accurate simulator that lacks full-system capabilities and only supports uniprocessor architectures including the Alpha, MIPS, and ARM instruction sets.  This simulator is no longer actively maintained or supported.

SESC

An academic project out of UIUC, SESC is a cycle-accurate superscalar OoO simulator that supports CMP (multicore) platforms.  The only instruction set supported is MIPS, and there is no support for full-system simulation.

Simics

Originally an academic project, Simics was commercialized by Virtutech and sold to Wind River, an Intel subsidiary.  Virtutech, and now Wind River, provide academic licensing for Simics, which provides a limited set of the full Simics suite of processor models.  The most detailed models in the academic suite are the SPARC models, followed by the x86.  Simics provides full-system functional simulation with multicore platforms that executes an in-order model with 1 cycle per instruction.  The microarchitectural interface (MAI) provided a plug-in framework for researchers to observe instructions and hook timing functionality to simulate varying feature latency; however, MAI is no longer supported by versions of Simics past 4.0.  Simics also allows for user decoders to be defined that can re-define the functional behavior of instructions.  User decoders support ISA extensions and tweaks while still maintaining functional fidelity.

GEMS

Multifacet GEMS (more commonly just Simics GEMS) is a project from UW-Madison that provides modules for Simics without using the MAI. GEMS implements an OoO processor (Alpha) model for the SPARC-V9 instruction set with a detailed CMP memory network (specifically, the UltraSPARC III+ instruction set).  GEMS is composed of two primary modules, Opal and Ruby.  Opal is the OoO cycle-accurate simulator that relies on Simics for some of the difficult full-system features; when Opal does something that is detected as functionally incorrect, it squashes its work and reads architected state from Simics.  Ruby is a complex memory subsystem intended for easing research in the protocols and interconnects of CMPs.  Opal is designed to call into Ruby for its detailed memory hierarchy, although Opal also has a simple two-level memory hierarchy that is usable in uniprocessor mode. Most work uses Opal+Ruby, and some researchers only use Ruby (since they are only interested in the memory subsystem), and there are even efforts to port Ruby to other simulators to provide the detailed memory hierarchy.

PTLsim

PTLsim is an open-source cycle-accurate x86 simulator.  The base PTLsim does not provide full-system simulation nor does it model multicore, although full-system features are provided through Xen and more recently KVM/Qemu.  MPTLsim was also presented at DAC, but I have not seen any mention of its implementation.  It is an interesting project though, especially if x86 is a compelling architecture for a particular research problem.  I haven't personally tried to use PTLsim, although our group did task an undergrad to give it a whirl -- he had difficulty with building and running it, although this was for PTLsim/X.  The newer version relying on KVM might be better supported.

M5

I have previously talked about M5 on this blog. It is another academic simulator, originating at Michigan, that provides a combination of full-system (FS) or processor emulation (SE), cycle-accuracy, and architectural models, although at present only the ALPHA instruction set is supported in FS mode with a cycle-accurate (OoO) model. I believe the origin of M5 was to study networking, so the memory hierarchy is not particularly robust. There is an effort called GEM5 (clever!) to port the Ruby memory hierarchy to M5.  Community support for M5 is decent, although best-effort.

Emulators
Loosely related to architectural simulators are processor emulators and hypervisors.  I looked at using two of these, but they do not model the architecture in detail enough to support easy microarchitectural research or cycle-accurate timing.

Bochs

A full-system emulator for some of the x86 and x86_64 ISAs that is based on binary translation.  When I looked into Bochs, it did not support multicore or SMP, although that may have changed as it is still an active project. I also read, but never verified, that the emulation in Bochs is very time-consuming.

Qemu

Another binary-translating proceessor emulator, QEMU supports a broader range of architectures and is fairly efficient.  I actually do use it for rapid prototyping in some work that I do, but only for application and kernel development, not for architectural research.  It is an active project.

Well, that wraps up my view on the current architectural simulators.  If you have any experiences, differing opinions, or other simulators that have compelling features please feel free to drop me a line.

Read More