SuperCore? Scheduler

Mentors:

Joel Sherrill

Status:

Introduction: As part of GSoC 2010, Gedare Bloom refactored the old RTEMS scheduler to create a new modular SuperCore? scheduler, see ​rtems-sched. The goal of that project was to be able to support multiple scheduler implementations in an integrated and configurable infrastructure. Prior to Gedare's project, the scheduler was dispersed throughout the thread handling logic of the SuperCore?. Capturing that scheduler in a framework allowed for new scheduling mechanisms to be implemented more easily in RTEMS. His work resulted in the Deterministic Priority Scheduler and Earliest Deadline First (EDF) schedulers. Gedare mentored a GSOC 2011 project to add the Constant Bandwidth Server Scheduler to RTEMS. In parallel with this work, the initial SMP support was developed and the Simple SMP Priority Scheduler was added by JoelSherrill. Along the way, the Simple Priority Scheduler was implemented which provides an alternative for TinyRTEMS environments. For GSOC 2013 Gedare mentored Sreeharshakonduri? to add a Global Earliest Deadline First(G-EDF) Scheduler to RTEMS. This Scheduler is still work in progress and works for aperiodic tasks. In particular, the following are potential areas which are open for student creative solutions. However, any work in these areas needs to be discussed and approved.

• alternative uniprocessor schedulers.
• alternative SMP-aware schedulers.

Current ideas for improvements:

• Refactoring of Thread Set Managers and use them in scheduling algorithms. This is discussed below.

Goal: The basic goals are met. Tasks listed are improvements.

Requirements: The person(s) implementing this should at least be familiar with the design of the new scheduler framework. Additionally, experience in refactoring is a plus.

Resources: Contact Joel Sherrill or Gedare Bloom. ​A high-level overview of the modular scheduler. ​Adding the Global EDF Scheduler to RTEMS= Small related tasks =

• Convert writing a scheduler to texinfo and add to RTEMS Documentation.

Large related tasks

Scheduling arbitrary resources

The scheduler focuses on scheduling threads. Other schedulable entities exist within a system, for example I/O (block, network, etc). One task idea is to make the scheduler even more modular with respect to the schedulable resource. This task requires a feasibility study and design before proceeding.

Thread Ready Set and Block 2-n Refactoring

RTEMS manages sets of threads (aka tasks). Some sets are waiting on resources and are managed by the SuperCore? Thread Queue (threadq) handler. There is a single set of ready to execute and executing threads that are managed by the Thread Scheduler (scheduler).

This task has a series of steps which make this design more obvious at the SuperCore? level. In general, the "package names" suck at this point, but hopefully this explanation and project will make this organization more obvious and flexible. All names proposed in the following are up for discussion.

The currently identified steps in this project are:

• Create SuperCore? Handlers for Thread Sets:
  • Refactor "FIFO for Priority Ordering" from Scheduler Simple into something like "Thread_set_Priority_fifo"
  • Refactor priority discipline from Thread Queue (e.g. Block 2-n structure) and name it something like "Thread_set_Priority_block2n"
  • Refactor Thread Set from Deterministic Priority Scheduler and name it something like "Thread_set_Priority_deterministic"
  • Refactor "RBTree Priority" from EDF and CBS schedulers into their own thread set.
• Rewrite Scheduler infrastructure to use Thread Sets as a pluggable implementation of threads.
• Add a new Scheduler that uses block2n
• Rework Scheduler Simple SMP to use block2n (if feasible)
• Run Timing Tests with each scheduler
  • Report the performance of each scheduler including graphs.
• Help provide guidance in selecting the appropriate scheduler for an application. The guidance would include the goals of the scheduler along with the time and space characteristics of operations like blocking and readying.
  • Deterministic Priority Scheduler is O(constant)
  • Simple Priority Scheduler has some operations that are O(number of tasks)
  • Simple Scheduler SMP has some O(number of tasks) and others that are O(number of cores)
  • Block2N based scheduler would be bounded but worst case basically O(constant). It can iterate a few times but that has a maximum that is designed in.

Scheduler Simulator

The RTEMS Scheduler Simulator is a b based tool based on a subset of the RTEMS SuperCore?, Classic API. and Shell. The focus of this tool is to provide a scripting environment in which thread scheduling scenarios can be repeatedly tested in a deterministic manner. The scripting language allows one to initalize RTEMS with an arbitrary number of CPU cores, create tasks, delete tasks, have clock ticks, and have tasks perform operations and block on Classic API Semaphores. Since Classic API Semaphores can be semaphores or mutexes with priority inheritance or ceiling, this could be used to explore more than Thread Scheduling Algorithms.

The Scheduler Simulator is in ​http://git.rtems.org/rtems-schedsim/git and test scenarios for the Deterministic Priority Scheduler and SMP Simple Priority Scheduler can be found ​here.

This tool was created to support the design, development and debug of the SMP Simple Priority Scheduler. The Scheduler Simulator can be used to explore the impact of various number of CPU cores on an algorithm without having real hardware. It allowed us to create scenarios for 1, 2, and 4 core configurations and debug the algorithm.

Some details:

• When configured, it is provided the directory for RTEMS source code. As of 1 May 2013, it was in sync and working.
• An application is built per scheduler. This is essentially the simple command language with RTEMS configured for a specific scheduler.
• Two schedulers have test scenarios. There are a total of 20 scenario scripts.

The Scheduler Simulator is useful for developing new scheduling algorithms. But it has issues:

• Documentation is currently not included in this tree. There are documents on Writing a Scheduler and Using the Scheduler Simulator but neither has been integrated into this tree.
• Test scripts may be incorrectly named here versus their "official" name in the RTEMS source tree.

Basically the Scheduler Simulator source is out of sync with the main source tree.

Longer term wish list:

• Integrate building this into the RTEMS Source Builder.
• Automate testing of this so it doesn't fail into disrepair again.
• Switch to a waf based build system.

Even longer term wish list:

• Investigate using this framework for similar testing of block device buffer management algorithms.

Related Tasks

Miscellaneous Sections

As the project progresses, you will need to add build instructions, etc and this page will evolve from a project description into a HOWTO.

References

• TBD

Other sections: If you have more to say about the project that doesn't fit in the proposed sections of this template, feel free to add other sections at will.