I. Basic scheduling simulation features and feasibility tests for independent tasks

In this chapter, you find a description of the most important scheduling and feasibility services provided by Cheddar in the case of independent tasks.

I.1 First step : a simple scheduling simulation

This section shows you how to call the simpliest features of Cheddar.

Cheddar provides tools to check temporal constraints of real time tasks. These tools are based on classical results from real time scheduling theory. Before calling such tools, you have to define a system which is mainly composed of several processors and tasks.

To define a processor, you should first define one or multiple cores. For that choose the "Edit/Hardware/Core" submenu. The window below is then displayed:

Figure 1.1 Adding a core

A core is defined by the following fields (see Figure 1.1):

  1. The name of the core. A core name can be any combination of literal characters including underscore. Space is forbidden. Each core must have a unique name.
  2. The scheduler hosted by the core. Basically, you can choose from a various set of schedulers such as (to get a detailed description on these schedulers, see section I.2):
    • "Earliest Deadline First" (or EDF). Tasks can be periodic or not and are scheduled according to their deadline.
    • "Least Laxity First" (or LLF). Tasks can be periodic or not and are scheduled according to their laxity. The laxity is computed by : L_i = D_i - C'_i in which L_i is the laxity of the task, D_i is the deadline, and C'_i is the remaining capacity.
    • "Least Runtime Laxity First" (a second interpretation of LLF). Tasks can be periodic or not and are scheduled according to their laxity. The laxity is computed by : L_i = D_i - (C'_i + t_i) in which L_i is the laxity of the task, D_i is the deadline, C'_i is the remaining capacity, and t_i is the time passed since the release time of the task.
    • "Rate Monotonic" (or RM, or RMA, or RMS). Tasks have to be periodic, and deadline must be equal to period. Tasks are scheduled according to their period. You have to be aware that the value of the priority field of the tasks is ignored here.
    • "Deadline Monotonic" (or DM). Tasks have to be periodic and are scheduled according to their deadline. You have to be aware that the value of the priority field of the tasks is ignored here.
    • "Posix 1003 Highest Priority First". Tasks can be periodic or not. Tasks are scheduled according to the priority and the policy of the tasks. (Rate Monotonic and Deadline Monotonic use the same scheduler engine except that priorities are automatically computed from task period or deadline). POSIX 1003.1b scheduler supports SCHED_RR, SCHED_FIFO and SCHED_OTHERS queueing policies. SCHED_OTHERS is a time sharing policy. SCHED_RR and SCHED_FIFO tasks must have priorities ranging between 255 and 1. Priority level 0 is reserved for SCHED_OTHERS tasks. The highiest priority level is 255.
    • "Time sharing based on wait time" (which is a Linux-like scheduler) and "Time sharing based on cpu usage". These two schedulers provide a way to share the processor as on a time sharing operatong system. With the first scheduler, the more a ready task waits for the processor and the more its priority increases. With the second scheduler, the more a ready task uses the processor and the more its priority decreases.
    • "Round robin" (with quantum). The processor is regulary shared between all the tasks. A quantum (which is a bound on the time a task keeps the processor) can be given.
    • "Maximum Urgency First based on laxity" and "Maximum Urgency First based on deadline". Such schedulers are based on an hybrid priority assignment : a task priority is made of a fixed part and a dynamic part (see ).
    • "D-Over". This scheduler is an EDF like but which is work fine when the processor is over-loaded. When the processor is over-loaded, D-Over is always able to predict which tasks will miss its deadline (in contrary to EDF).
    • User-defined schedulers ("Pipeline user-defined scheduler", "Automata user-defined scheduler" or "Compiled user-defined scheduler"). These schedulers allow users to define their own scheduler into Cheddar (see section VI for details).
    • ...
  3. If the scheduler is preemptive or not. By default, the scheduler is set to be preemptive.
  4. The quantum value associated with the scheduler. This information is useful if a scheduler has to manage several tasks with the same dynamic or static priority : in this case, the simulator has to choose how to share the processor between these tasks. The quantum is a bound on the delay a task can hold the processor (if the quantum is equal to zero, there is no bound on the processor holding time). At the time we're speaking, the quantum value can be used with the POSIX 1003.1b scheduler (only with SCHED_RR tasks) and the round robin scheduler. With POSIX 1003.1b, two SCHED_RR tasks with the same priority level should share the processor with a POSIX round-robin policy. In this case, the quantum value is the time slot of this round-robin scheduler. Finally, the quantum value could also be used for user-defined scheduler (see part VI for details).
  5. Automaton name. User-defined scheduler can be expressed as an automaton. In this case, the this attribute stores the name of the automaton for the given core.
  6. Capacity ....
  7. Period ....
  8. Priority ....
  9. User Defined Scheduler Source. In the case of a user-defined scheduler, this attribute stores the file name containting the code of the scheduler.
  10. The User Defined Scheduler Source File Name is the name of a file which contains the source code of a user-defined scheduler (see section VI for details).
  11. Start time ....
  12. Speed. This attribute is the speed of the core. Default value is 1 and only positive non null values are accepted for this attribute. When the value of this attribute is equal to n, it means that task are executed n times quicker.
  13. L1 Cache system name ....



Warning : with Cheddar, to add a core (or any object), you have to push the Add button before pushing the Close button. That allows you to define several objects quickly whithout closing the window (you should then push Add for each defined object).

Then you can define a processor. For that choose the "Edit/Entities/Hardware/Processor" submenu. The window below is then displayed :

Figure 1.2 Adding a processor

A processor is defined by the following fields (see Figure 1.2) :

  1. The name of the processor. A processor name can be any combination of literal characters including underscore. Space is forbidden. Each processor must have a unique name.
  2. At the time we're speaking, the network field is not used (planned to be used in order to simulate message scheduling).
  3. Processor type 4 kinds of processor exists in Cheddar:
    • Monocore type. It contains only one core and can run only one task at a time.
    • Identical multicores type. The processor contains several cores that are identical, i.e. have the same scheduling protocol (but with potentionnaly different parameters). All core of such processor have the same speed.
    • Uniform multicores type. The processor contains cores that have different speeds. However speeds have proportional values. All cores of the same processor have to run the same scheduling protocol.
    • Unrelated multicores type. The processor contains cores with differents speeds. Speeds have unrelated values. Again, all cores of the same processor have to run the same scheduling protocol.
  4. Migration type . This attributes specifies how the tasks are allowed to move from one core to another.
    • No migration type. Task cannot move from one core to another. This is typically the case of Multicore ARINC 653 architectures, or also of architectures with the concepts of core affinity (i.e. POSIX standard).
    • Job level migration type. A task running on a core can move to another core only when its current job is completed. Running the smae job on two different cores is not allowed.
    • Time unit migration type. A task can migrate at any core at any time.
  5. Cores table which contain the list of cores initially defined. The user should select one core in the monocore processor case, and almost one core in other case.


Figure 1.3 Adding an address space

The next step in order to run a simulation, is to define an address space. Choose the "Edit/Entities/Software/Address space" submenu. An address space models a piece of memory which contain tasks, buffers or shared resources. The Figure 1.3 shows the widget used to define such a feature. At the time we are speaking, the information you have to provide is :


Figure 1.4 Adding a task

Let see now, how to define a task, the last feature required to perform the most simpliest performance analysis. Choose the "Edit/Entities/Software/Task" submenu. The window of Figure 1.4 is then displayed. This window is composed of 3 sub-parts : the "main part", the "offset part" and the "user's defined parameters part". The main part contains the following informations :

  1. At least, a task is defined by a name (the task name should be unique), a capacity (bound on its execution time) and a place to run it (a processor name and an address space name). The other parameters are optional but can be required for a particular scheduler
  2. A type of task . It describes the way the task is activated. An aperiodic task is only activated once. A periodic task is activated many times and the delay between two activations is a fixed one. A poisson process task is activated many times and the delay between two activations is a random delay : the random law used to generated these delays is an exponential one (poisson process). a sporadic task is a task which is activated many times with a minimal delay between two succesive activations. If the task type is "user-defined", the task activation law is defined by the user (see section VI.2 of this user's guide).
  3. The period. It is the time between two task activations. The period is a constant delay for a periodic task. It's an average delay for a poisson process task. If you have selected a processor that owns a Rate Monotonic or a Deadline Monotonic scheduler, you have to give a period for each of its tasks.
  4. A start time. It is the time when the task arrives in the system (its first activation time).
  5. A deadline. The task must end its activation before its deadline. A deadline is a relative information : to get the absolute date at which a task must end an activation, you should add the time when the task was awoken/activated to the task deadline. Warning : the deadline must be equal to the period if you define a Rate Monotonic scheduler.
  6. A priority and a policy. These parameters are dedicated to the POSIX 1003.1b/Highest Priority First scheduler. Priority is the fixed priority of a task. Policy can be SCHED RR, SCHED FIFO or SCHED OTHERS and describes how the scheduler chooses a task when several tasks have the same priority level. Warning : the priority and the policy are ignored by a Rate Monotonic and a Deadline Monotonic scheduler.
  7. A jitter. The jitter is a maximum lateness on the task wake up time. This information can be used to express task precedencies and to applied method such as the Holistic task response time method.
  8. A blocking time. It's a bound on shared resource waiting time. This delay could be set by the user but could also be computed by Cheddar if you described how shared resources are accessed.
  9. An activation rule. The name of the rule which defines the way the task should be activated. Only used with user-defined task. (see section VI.2 for details).
  10. A criticality level . The field indicates how the task is critical. Currently used by the MUF scheduler or any user-defined schedulers.
  11. A seed . If you define a poisson process task or a user-defined task, you can set here how random activation delay should be generated (in a deterministic way or not). The "Seed" button proposes you a randomly generated seed value but of course, you can give any seed value. This seed value is used only if the Predictable option is selected. If the Unpredictable option is selected, the seed is initialized at simulation time with "gettimeofday".
  12. The text memory size and stack memory size. The fields related to task memory size will be used in the next Cheddar's release in order to perform memory requirement analysis.
The second and the third parts store task information which are less used by users.

The offsets part is a table. Each entry of the table stores two informations : an activation number and a value. The offset part allows the user to change the wake up time of a task on a given activation number. For each activation number stored in the "Activations:" fields, the task wake up time will be delayed by the amount of time given in the "Values" fields.

Finally, the third part (the "User's defined parameters" part) contains task parameters (similar to the deadline, the period, the capacity ...) used by user-defined schedulers. With this part, a user can define new task parameters. A user-defined task parameter has a value, a name and a type. The types currently available to defined user-defined task parameters are : string, integer boolean and double.


Warning : when you create tasks, in most of cases, Cheddar does not check if your task parameters are erronous according to the scheduler you previously selected : these checks are done at task analysis/scheduling. Of course, you can always change task and processor parameters with "Edit menus.



When tasks and processors are defined, we can start the task analysis. Cheddar provides two kind of analysis tools :

  1. Feasibility analysis tools : these tools compute much information without scheduling the set of tasks. Equation references used to compute this feasibility information are always provided with the results. Feasibility services are provided for tasks and buffers.
  2. Simulation analysis tools : With these tools, scheduling has to be computed first. When the scheduling is computed (of course, this step can be long to proceed ...), the resulting scheduling is drawn in the top part of the window and information is computed and displayed in the bottom part of the window. Information retrieved here is only valid in the computed scheduling.The simpliest tools provided by Cheddar check if a set of tasks meet their temporal constraints. Simulation services are also provided for other resources (for buffers for instance).


All these tools can be called from the "Tools" Menu and from some toolbar Buttons :

Figure 1.5 The Cheddar's main window


In the top part of this window, each resource, buffer, message and task is shown by a time line:

  1. For a task time line:
    • Each vertical red line means that the task is activated (woken up) at this time.
    • Each horizontal rectangle means that the task is running at this time. The horizontal rectangle can have a task specific color. This horizontal colored rectangle can be found also on the core time line, which shows how the core is shared by the tasks of the architecture model. Task specific color can be deactivated, i.e. set to black for all tasks with the options windows.
  2. For a resource time line:
    • Each vertical blue line means that the resource is allocated by a task at this time.
    • Each vertical red line means that the resource is relaesed by a task at this time.
    • Each horizontal rectangle means that the resource is used by a task which is running at this time. The color of this horizontal rectangle is set with the same color used in the task time line.
  3. For a message time line:
    • Each vertical blue rectangle means that the message is sent at this time.
    • Each vertical read rectangle means that the message is received at this time.
    • To find the task sending or receiving a message, users have to check the core unit time line of the task time lines to find the related tasks. To produce such a display, users have to define for each message the corresponding dependencies that are used to computed the related events.
  4. For a buffer time line:
    • Each horizontal blue rectangle means that a task writes data into a buffer.
    • Each horizontal red rectangle means that a task reads data from a buffer.
    To find the task writing or readning a data in/from the buffer, users have to check the core unit time line of the task time lines to find the related tasks. To produce such a display, users have to define for each buffer the corresponding dependencies that are used to computed the related events.



The scheduling result can also be saved in XML file. This allows user to run tools on Cheddar scheduling results. The scheduling result of Cheddar is an event table that gives for each time unit the set of events produced by the scheduling simulator. The event table is the data structure which is used by the simulator engine to perform analysis on scheduling. For each event, extra data related to the event is also stored. Here is the main produced events and their data:

Be aware that for scalability, no all events are by default generated by Cheddar. Please refer to the option windows to select which events the simulator will produce or not. Here is an example of event table produced by Cheddar:



To get a summary of the tools provided by Cheddar, see section VI .




I.2 Other Available schedulers and task arrival patterns

In Cheddar, you will find several schedulers. Some of them are directly implemented into the framework ; others can be defined by the user. The list below describes the currently built-in schedulers you may find in the current release: Besides the implemented scheduling protocols listed above, Cheddar provides a mean to define your own scheduling protocols. The current Cheddar's release provides examples of User-defined schedulers stored in some .sc files (see project_examples sub-directory and section VI). These scheduler examples are:

In the same way, Cheddar provides a set of built-in task models. The built-in task models are:


Again, you can define your own task model with user-defined code. Examples of user-defined task provided with this Cheddar release can be found in these files:


I.3 Scheduling options.

Figure 1.6 Scheduling options windows




The submenu "Tools/Scheduling/Options" allows you to tune the way all next scheduling simulations will be done (see Figure 1.6) :




Figure 1.7 Scheduling options windows (both feasibility and simulation)




The submenu "Tools/Scheduling/Scheduling simulation" allows you to tune the way the next scheduling simulation and the next feasibility test will be done (see the Figure 1.7).

Options related to which information the engine has to compute when the scheduling sequence is built are :

Options related to which information the feasibility tests will compute are :






Contact : Frank Singhoff mailto:singhoff@univ-brest.fr
Last update : January, the 4th, 2019