Cheddar - open-source GNU GPL real-time scheduling simulator/analyzer

In few words

Cheddar is a GNU GPL real-time scheduling simulator/schedulability tool. Cheddar allows you to model software architectures of real-time systems and to check their schedulability or other performance criteria.

As many schedulability analysis tools, schedulability can be assessed by scheduling simulations or feasibility tests.

With Cheddar, the modeling of the system to verify can be made with either AADL or with its own internal architecture design language, aka CheddarADL. Some experiments also exist with MARTE UML and other ADL languages such as PPOOA or MOSART. Finally, Cheddar hosts a domain specific language inside its scheduling simulator that allows users to design new task models or scheduling policies.

To summarize, Cheddar can help you: to perform schedulability analysis during early verifications at design time, to teach scheduling analysis or to quickly prototype new real-time scheduling policies or task models.

History

Cheddar is developed and maintained by a team composed of the Lab-STICC laboratory UMR CNRS 6285, from the University of Brest and Ellidiss Technologies.

The Cheddar project was started in 2002 by Frank Singhoff, University of Brest. The full list of the contributors can be reach there. Since 2008, Ellidiss Technologies also contributes to the development of Cheddar and provides industrial support of it by their commertial tool called AADLInspector .

Main features

Cheddar is composed of two independent parts: an editor to model the real-time system to be analyzed, and a framework to perform analysis.

The editor allows you to describe systems composed of cores, processors, cache units, network-on-chips which own software components (e.g. tasks, shared resources, buffers). Cheddar includes its own ADL, namely Cheddar ADL for such modeling work. However, Cheddar is also able to handle fully compliant AADL V2 models with Ellidiss AADL V2 parser to their commercial product AADLInspector.

The framework, called "Cheddar Kernel", can be called alone (e.g. by a shell script) or embedded in a toolset. Cheddar is currently used/embedded in:

• AADLInspector and STOOD (commercial products of Ellidiss Tech),
• AADL OSATE2 toolset (OSATE2 is managed by CMU/SEI, its Cheddar plugin is managed by Lab-STICC),
• TASTE (from the ESA/European Space Agency) and Ocarina (from TPT/ISAE/ESA),
• RAMSES (LTCI/Télécom Paris) ,
• PPOOA (ETS Ingenieros Industriales).
• MOSART, from the LIAS at ENSMA.
• Polarsys Time4sys .

The main provided analysis tools are:

• Scheduling simulations
  • With preemptive and non preemptive scheduling policies
  • With uniprocessor, Multiprocessor and hierarchical scheduling policies
  • With usual uniprocessor: RM, DM, LLF, EDF, POSIX queue policies (SCHED_RR/FIFO/OTHER), EDH, MUF, Round-Robin, D-over, time sharing policies
  • DAG models: HLFET
  • With hierarchical scheduling policies: several TSP scheduling policies including ARINC 653 and aperiodic servers (sporadic, deferable, polling, priority exchange), Round robin
  • With multiprocessor policies: global RM/DM/EDF/LLF/MUF, Proportionate Fair, EDZL, RUN (unsafe prototype), LLREF
  • With L1 instruction cache entities
  • With different type of tasks: aperiodic, periodic, task activated with a poisson process, sporadic, Multiframe, ramdomly activated, periodic inner periodic, sporadic inner sporadic.
  • With shared resources (and with FIFO, PCP, PIP, IPCP synchronization protocols)
  • With task jitters and offsets
  • With various task precedencies models
  • With energy models : DVFS, EDH
• Extract information from scheduling simulation, such as
  • Worst/best/average task response times, task missed deadlines
  • Number of preemption, number of context switch
  • Worst/best/average shared resource blocking time
  • Deadlock and priority inversion
  • Worst/average buffer utilization factor, message worst/average waiting time
• Apply feasibility tests on tasks and buffers
  • Compute worst case task response time on periodic task set
  • Several methods to compute worst case response time with linear and tree transactions: Tindell, Palencia, ...
  • Apply processor utilization feasibility tests.
  • Compute bound on buffer size (when buffers are shared by periodic tasks)
  • Worst case shared resource blocking time
  • Memory footprint of software entities
  • Apply feasibility tests based on demand function.
• Schedulability with models of hardware components
  • CRPD analysis for L1 instruction cache interference analysis and scheduling simulation
  • NoC and spacewire communication delays analysis
  • Memory interferences (DRAM) analysis
• Shared resources support (both scheduling simulation and worst case blocking time analysis). Supported protocols: PIP, PCP, IPCP
• Tools to express and perform analysis with task dependencies:
  • Model task transaction (linear or tree) and compute worst case response time
  • Scheduling simulation tasks according to task precedencies
  • Compute Tindell Holistic end to end response time.
  • Apply Chetto and Blazewicz algorithms.
• Algorithms to assign priorities to tasks and shared resources
  • Rate Monotonic, Deadline Monotonic, Audsley task priority assignment
  • Task priority assignment according to CRPD
  • Shared resource ceiling priority assignement (for PCP like policies)
• Cheddar provides a way to quickly define user-defined schedulers to model specific scheduling of ad-hoc applications/systems (ex: ARINC 653)
  • User-defined scheduling policies (based on pipeline models or automaton models)
  • User-defined task model policies, to express and handle specific task activation policies
  • User-defined analysis on scheduling simulation, to look for specific properties on scheduling simulation result
• Partitionning tools for periodic task set
  • Provide classical policies such as: Best fit, General Task fit, Fist fit, Small fit and Next fit.
  • Implementation of the PAES meta-heuristic to allow Cheddar users to compute Pareto Front. Such a Meta-Heuristic has been used to 1) compute partitionning of MILS architecture with objective functions to minimize missed deadlines and maximize security properties 2) assign a set of functions to a set of tasks with objective functions to minimize the number of preemptions and minimiz missed deadlines.
• Apply MILS security analysis
  • Can be run jointly with schedulability analysis to compute partitionning
  • Security verifications with Biba, Bell-Lapadula, Chinese wall, Wharshall

The picture below is a screenshot of Cheddar: on the top of the picture, scheduling is drawn according to the scheduling policy of each core and processor. On the bottom, some task information is computed and displayed (response times, missed deadlines, processor utilization factor, ...).

To download and install Cheddar, please refer to the Download & Install section in Cheddar 3.3 User Guide

To download and compile Cheddar from its source code, please refer to the Download & Compile section in Cheddar 3.3 User Guide

No support is currently available in the team.

Current developments on Cheddar are about the following topics:

1. Spacewire analysis.
2. Joined scheduling and security analysis.
3. Mixed-criticality support for CNN models.
4. GERICOS (LESIA platform) and schedulability analysis for Space multicore architectures.
5. Scheduling anomalies detection..
6. Design space exploration with PAES implementation.

• The first publication about Cheddar: Cheddar: a Flexible Real Time Scheduling Framework. F. Singhoff, J. Legrand, L. Nana, L. Marcé. ACM SIGAda Ada Letters, volume 24, number 4, pages 1-8. Edited by ACM Press, New York, USA. December 2004, ISSN:1094-3641.
• Several tutorials in English or in French about Cheddar:
  1. A tutorial about Cheddar at ETR'2015, ETR'2017, and ETR'2021, both in french, or in english, Two documents for those tutorials giving hints about scheduling analysis with Cheddar, one in English for ETR'15 and a second in French for ETR'17 .
  2. Several tutorials about AADL, AADLInspector and Cheddar. Such tutorials explain how doing scheduling analysis with the AADL language and the AADLInspector/Cheddar tools:
     • Full day tutorial at a SEA-UE teaching week, Brest. October 2022. In English.
     • Full day tutorial at CPS-WEEK Conferences Montréal, Canada. April 2019, in English.
     • Full day tutorial at Ada Europe Conference, Lisbon, Portugal. June 2018. In English.
  3. A lecture and tutorial about Cheddar and RTEMS, for the University of Split in December 2021 and October 2022. This lecture/labs is presented by a set of videos.
  4. A lecture about AADL, with Cheddar for ETR'09. In French.
  5. Some labs from the Master degree at Univ. Brest about AADL, AADLInspector (and then Cheddar), Ocarina and a bit of OSATE, Last update in December 2020. Frank Singhoff. The slides of the labs are there (in English). The labs itself is in French.
• Special thanks to Sam Siewert from Univ. of Colorado/Boulder who made nice videos to teach how students may use Cheddar.
• Cheddar Architecture Description Language reference guide. C. Fotsing, A. Plantec, V. Gaudel, S. Rubini, S. Li, H. N. Tran, L. Lemarchand, P. Dissaux, J Legrand, F. Singhoff. January 2013. Lab-STICC technical report.
• A FAQ about several issues you may have when using Cheddar.
• A text book on Ada and real-time scheduling analysis published by Cambridge University press: Building Parallel, Embedded, and Real-Time Applications with Ada. J. W. McCormick, F. Singhoff, J. Hugues. Cambridge University Press, UK, 365 pages, April 2011. ISBN-13: 9780521197168. This book has several exercises on real-time scheduling analysis with solutions computed by Cheddar. Exercises solutions of this book are freely available from the Cambridge University Press website.
• About how to use Cheddar with AADL: Scheduling and Memory requirement analysis with AADL. F. Singhoff, J. Legrand, L. Nana, and L. Marcé. ACM SIGAda Ada Letters, volume 25, number 4, pages 1-10. Edited by ACM Press, New York, USA, November 2005, ISSN:1094-3641.
  You may also be interested by the list of AADL properties to use with Cheddar: The Cheddar AADL Property sets (Release 2.x). Frank Singhoff. LISyC technical report number singhoff-03-07. February 2007.
• Cheddar 3.3 User's Guide. Lab-STICC technical report.
• All the publications related to Cheddar: can be downloaded here.
• Last but not least, all document to compile, install and run Cheddar: can be reached here.

We distribute Cheddar with a set of AADL and XML examples, but this section also contains a set of contributions from Cheddar's users:

• Several videos (tutorials or lectures) about Cheddar. To learn, for example, how to use Cheddar with OSATE (from SEI/CMU) of wit TASTE (from the ESA). there is also 2 videos from Sam Siewert from from University of Boulder/Colorado to teach scheduling analysis with Cheddar.
• The teaching corner: contains a set of real-time scheduling courses or labs built with the help of Cheddar.
• This webpage shows some research or example of user ... that may help you to discover how to use Cheddar.

To do a bug report, to find compilation instructions and developer documentations, a work space is available for Cheddar software developers on this wiki.

You can also report bugs and new tested platforms to cheddar@listes.univ-brest.fr (Warning: this is a private mailing-list. To post, you have to subscribe to the mailing-list first).

Main contact point and coordinator: Hai Nam Tran, hai-nam.tran@univ-brest.fr

Cheddar users and developers share information with a mailing list hosted by the University of Brest.

To post to the list, send e-mail to cheddar@listes.univ-brest.fr. Warning: this is a private mailing-list (i.e. to post on this mailing-list, you have to subscribe to it).

To subscribe to the list: send a request to sympa@listes.univ-brest.fr with the following text in the body of your e-mail:

SUBSCRIBE cheddar foo@bar.com

where foo@bar.com is your email address.

To unsubscribe to the list: send a request to sympa@listes.univ-brest.fr with the following text in the body:

SIGNOFF cheddar

Cheddar is developed and maintened by a team composed of members from the Lab-STICC laboratory UMR CNRS 6285/Université de Bretagne Occidentale and Ellidiss Technologies.

Main involved people: Pierre Dissaux (Ellidiss Technologies), Jérôme Legrand (Ellidiss Technologies), Alain Plantec (Lab-STICC/Université de Bretagne Occidentale), Stéphane Rubini (Lab-STICC/Université de Bretagne Occidentale), Laurent Lemarchand (Lab-STICC/Université de Bretagne Occidentale), Hai Nam Tran (Lab-STICC/Université de Bretagne Occidentale), Valérie-Anne Nicolas (Lab-STICC/Université de Bretagne Occidentale) and Frank Singhoff (Lab-STICC/Université de Bretagne Occidentale).

Phd Students working on Cheddar: Alan Le Boudec, Blandine Djika and Sébastien Levieux.

Former Phd Students: Illham Atchadam, Mourad Dridi, Rahma Bouaziz, Hai Nam Tran, Shuai Li, Vincent Gaudel, Jérôme Legrand.

The project has been funded by Université de Bretagne Occidentale, Lab-STICC UMR 6285, Ellidiss Technologies, Conseil régional de Bretagne, Brest Métropole, BPI France, Conseil département du Finistère, Thales DMS and communications, EGIDE/Campus France PESSOA number 27380SA and 37932TF, MOSAR Horizon 2020 project under grant agreement No 821996.

Researches on Cheddar are also performed in collaboration with the following partners:

• S3/Télécom-Paris-Tech,
• AADL committee members, CMU/SEI
• University of Lisbon/LASiGE laboratory.

The following people have also contributed to the project: see the author section in README.md

Thanks to people who sent us bug reports and/or advices: B. Baron, P. Mueller, H. Bonnin, T. Ren, K. Bryan, N. Hoogland, V. Hugel, J. Stemerdink, T. Vergnaud, F. Rodrigues de la Rocha, G. Laurens, V. Hugel, C. Valle, Su Young Lee, P. Wong, and M. Zanconi, ...

In the framework of the Campus France/FCT projects NORTH and SAPIENT, José Rufino was involved in the Cheddar project.

José Rufino passed away in summer 2018. This summer, we lose someone with which we could always count, we could talk to and be heard, we could receive back nice words and incentives. José had a strong voice, but we never heard him raising his voice to anyone. We also lose his deep technical knowledge in the area of real-time and embedded systems, his ideas and persistence in pursuing them, his scientific honesty and strict rigour and his great collaborative skills. We will miss him. José devoted perhaps most of his time to his students. He cared to pass them his knowledge always seeking to improve the reading materials, preparing exercises, looking for new ways to make them learn more and better. He was considered a very demanding teacher, a characteristic that many students are only able to appreciate years later. He was also extremely dedicated and competent teacher. We believe that there will hardly be a student who will not remember Jose in a positive way. So the students will miss him.

José Rufino was one of the kindest and educated persons we ever met. José was a very reserved person, maybe his kindness was too great and he didn't like to bother us with his problems. Despite so many years knowing him, there are only very few things we know from his private life, what he liked and what he used to do when away from the university. He loved an old car that belonged to his father, which he kept in good shape as he knew a lot about automotive mechanics and he could do the repairs by himself. But he didn't drive this car (at least not always), as he preferred to use public transportation to avoid traffic jams when going to work. He was taking care of his relatives who lived in Alentejo (far from Lisbon), so he was going there very often and, from time to time, would do maintenance works on that house. That's how he was. He lived his life thinking about the others and not about himself. We will miss him. Who know well how much we lose by not having him with us any longer.

Antonio Casimiro, who met José in 1989 and worked together for almost 30 years. Frank Singhoff, Laurent Lemarchand, Stéphane Rubini, Hai Nam Tran, Jalil Boukhobza, your friends from the Cheddar team.