Changes between Version 9 and Version 10 of Projects/Scheduler


Ignore:
Timestamp:
Mar 5, 2013, 10:19:37 PM (7 years ago)
Author:
JoelSherrill
Comment:

Update

Legend:

Unmodified
Added
Removed
Modified
  • Projects/Scheduler

    v9 v10  
    1010[wiki:TBR/User/JoelSherrill Joel Sherrill]
    1111
    12 
    1312'''Status:'''
    1413
    15 '''Introduction:''' As part of GSoC 2010, Gedare Bloom refactored the old RTEMS scheduler to create a new modular supercore scheduler, see [http://code.google.com/p/rtems-sched/ rtems-sched]. The goal of that project was to be able to support multiple scheduler implementations in an integrated and configurable infrastructure. The old scheduler was dispersed throughout the thread handling logic of the SuperCore, and capturing the scheduler allows for new scheduling mechanisms to be implemented more easily in RTEMS. His work can be extended by adding additional schedulers to RTEMS. In particular, a scheduler capable of supporting [https://www.rtems.org/bugzilla/show_bug.cgi?id=1729 SMP configurations of RTEMS] or a [wiki:Projects/TinyRTEMS TinyRTEMS] scheduler would be useful.
     14'''Introduction:''' As part of GSoC 2010, Gedare Bloom refactored the old RTEMS scheduler to create a new modular SuperCore scheduler, see [http://code.google.com/p/rtems-sched/ 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 [wiki:TBR/User/JoelSherrill JoelSherrill]. Along the way, the Simple Priority Scheduler was implemented which provides an alternative for [wiki:Projects/TinyRTEMS TinyRTEMS] environments.
    1615
    17 As of Feb 2010, Gedare's refactoring is completely merged and a Simple Priority Based Scheduler is soon to be merged.  Gedare has an Earliest Deadline First (EDF) scheduler is still in the queue to merge.  And an SMP aware scheduler remains to be written.
     16In 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.
    1817
    19 '''Goal:'''
     18 *  alternative uniprocessor schedulers.
     19 *  alternative SMP-aware schedulers.
    2020
    21 '''Requirements:''' The person(s) implementing this should at least be familiar with the design of the new scheduler.
     21Current ideas for improvements:
     22
     23 *  Refactoring of Thread Set Managers and use them in scheduling algorithms. See
     24
     25'''Goal:''' The basic goals are met. Tasks listed are improvements.
     26
     27'''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.
    2228
    2329'''Resources:''' Contact Joel Sherrill or Gedare Bloom. [http://gedare-csphd.blogspot.com/2010/11/rtems-modular-task-scheduler.html A high-level overview of the modular scheduler.]
    24 = Subtasks =
     30= Small related tasks =
    2531
    2632 *  Convert writing a scheduler to texinfo and add to RTEMS Documentation.
     33= Large related tasks =
     34
     35= Thread Ready Set and Block 2-n Refactoring =
     36
     37
     38RTEMS manages sets of tasks/threads. Some are sets waiting on resources which are managed by the SuperCore Thread Queue handler. There is a single set of tasks ready to execute which is managed by the Scheduler. There is a set of tasks executing (1-n depending on number of cores) which are selected for execution by the Scheduler.
     39
     40This task has a series of steps which make this more 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.
     41
     42The currently identified steps in this project are:
     43
     44 *  Create SuperCore Handlers for Task Sets:
     45  *  Refactor "FIFO for Priority Ordering" from Scheduler Simple into something like "ThreadSetSimplePriority"
     46  *  Refactor priority discipline from Thread Queue (e.g. Block 2-n structure) and name it something like "ThreadSetBlock2nPriority"
     47  *  Refactor Thread Set from Deterministic Priority Scheduler and name it something like "ThreadSetDeterministicPriority"
     48 *  Add Scheduler which uses Block2-n
     49 *  Rework Scheduler Simple SMP to use Block 2-n (if feasible)
     50 *  Run Timing Tests with each scheduler as default
     51  *  A report on the performance of each scheduler including graphs.
     52 *  Helping provide more guidance in selecting the appropriate scheduler for an application is needed. The guidance would include the goals of the scheduler along with the time and space characteristics of operations like blocking and readying.
     53  *  Deterministic Priority Scheduler is O(constant)
     54  *  Simple Priority Scheduler has some operations that are O(number of tasks)
     55  *  Simple Scheduler SMP has some O(number of tasks) and others which are O(number of cores)
     56  *  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.
    2757= Related Tasks =
    2858
     
    3060
    3161As the project progresses, you will need to add build instructions, etc and this page will evolve from a project description into a HOWTO.
    32 
    33 
    3462= References =
    3563