Cheddar - an open-source real-time schedulability tool/scheduling simulator
In few words
Cheddar is a GPL real-time scheduling tool/simulator. 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:
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, ...
- With shared resources (and with FIFO, PCP, PIP, IPCP synchronization protocols)
- With task jitters and offsets
- With various task precedencies models
- With an energy consumption model : 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, ...).
Download Cheddar binaries (current version is Cheddar-3.2, release date :
the 13th of July 2020) :
Users can also can get the Cheddar source code and the previous releases
here.
For installation procedures, please read the "How to install" section in
README.md
See the ChangesLog.pdf file to have history of modifications.
The file REQUESTED_FEATURES.pdf contains the
new features required by users and that we plan to implement in the next releases.
Cheddar is written in Ada, with GNAT and GtkAda Adacore products.
Cheddar is known to run on Linux and
windows boxes, but should run on any Adacore supported platforms
(see AdaCore web site for details).
The source code of Cheddar is available on the Cheddar svn repository.
For compilation procedures, please read refer to the instruction written for your platform
- 01/31/2022 : AADL Inspector and Cheddar has been used to verify the software architecture
of the PLATO payload See
there for further details.
- Fall December 2021, news labs/lectures by the Cheddar team: one at ETR 2021 (update of the lab at ETR in 2015 and 2017), and
another with Cheddar and RTEMS at University of Split. See the documentation section for further details.
- 05/25/2021 : Announce of Ellidiss Technologies (Pierre Dissaux).
AADL Inspector 1.8 has been released.
Scheduling analysis module is upgraded to Cheddar 3.2 kernel.
-
12/21/2020 : coordination of Cheddar is now done by Hai
Nam Tran.
-
11/11/2020 : add videos from users about how to use Cheddar. Thanks to the contributors!
-
07/21/2020 : a new Cheddar's binary release is distributed (Release 3.2)
- 04/15/2019 :
a tutorial (in english) about Cheddar and AADL at CPSWEEK, Montréal, Canada is available. This
tutorial
shows how to use AADLInspector, the commercial version of Cheddar with AADL.
April 2019.
- 01/01/2019. OSATE 2 now includes a new Cheddar plugin allowing AADL users to experiment Cheddar 3.x
analysis features.
The objectives of this plugin is to provide experimental multicore analysis features. For commercial use, it
is always
adviced to use AADLInspector and the potential providing by Ellidiss Tech.
- 01/01/2019.
The Lab-STICC distributes Java classes to build Cheddar models.
Those java classes can be used in any eclipse (or Java) program to produce Cheddar models and
to launch Cheddar. Should be used to implement in java simple transformations from a design
model to a Cheddar analysis model.
-
11/20/2018 : Announce of Ellidiss Technologies (Pierre Dissaux).
Ellidiss announces the availability of their new product: AADL Inspector 1.7.
AADL Inspector is a light-weight standalone analysis tool for textual AADL specifications
It includes a set of static rules checkers, Cheddar for schedulability analysis and Marzhin
for dynamic simulation.
Additional plug-ins can easily be added to fit corporate or project specific analysis requirements.
Please contact Ellidiss' technical support at aadl@ellidiss.fr for further details about these
extended capabilities.
AADL Inspector is available for download at: http://www.ellidiss.com/downloads.asp
and comes with a temporary evaluation license.
- 06/01/2018 :
a new tutorial (in english) about Cheddar and AADL is available. This tutorial
shows how to use AADLInspector, the commercial version of Cheddar with AADL.
June 2018.
-
01/01/2018 :
a new tutorial (in french) about Cheddar and AADL is available. This tutorial
shows how to use AADLInspector, the commercial version of Cheddar with AADL.
January 2018.
-
11/04/2017 : the call for papers of the 2018 Ada-Europe conference is out.
See
here the call for papers. Feel free to contribute !
-
10/10/2017 : a new Cheddar's binary release is distributed (Release 3.1)
-
11/02/2015 : a new Cheddar's binary release is distributed (Release 3.0)
-
08/10/2011 : Announce of Ellidiss Technologies (Pierre Dissaux).
Ellidiss announces the availability of their new product: AADL Inspector.
AADL Inspector is a light-weight standalone analysis tool for textual AADL specifications
It includes a set of static rules checkers, Cheddar for schedulability analysis and Marzhin
for dynamic simulation.
Additional plug-ins can easily be added to fit corporate or project specific analysis requirements.
Please contact Ellidiss' technical support at aadl@ellidiss.fr for further details about these
extended capabilities.
AADL Inspector is available for download at: http://www.ellidiss.com/downloads.asp
and comes with a temporary evaluation license.
- 07/01/2008 : a new Cheddar's release is distributed (Release 2.1)
- 02/12/2007 : a new Cheddar's release is distributed (Release 2.0)
- 01/12/2007 : create a SVN repository for Cheddar (http://beru.univ-brest.fr/svn/CHEDDAR)
- 12/07/2005 : provides solaris binaries
- 11/17/2005 : fix the install Makefile and the INSTALL file to the
linux distribution. The current linux archive contains these updated
files.
- 11/11/2005 : the gtkada compiled libraries are now include in the linux binaries distribution.
- 11/01/2005 : annual Cheddar's release. Current release is now
1.3p5
- 09/11/2004 : new patch on 1.3 (see Last patch section). Current release is now
1.3p4
- 09/08/2004 : a new Cheddar's release is distributed (1.3p3)
- 09/25/2003 : new version of the User's guide.
- 09/09/2003 : new patch on 1.3 (see Last patch section). Current release is now
1.3p2
- 08/28/2003 : new patch on 1.3 (see Last patch section). Current release is now
1.3p1
- 08/26/2003 : a new Cheddar's release is distributed (1.3p0)
- 07/03/2003 : a remote cvs access is now available. If you plan to write
code with Cheddar, contact us to get an account on this cvs repository.
- 05/31/2003 : create a Cheddar users and developpers mailing list and
provide dayly built cvs snapshot.
- 11/21/2002 : release of a new patch, see FIXED_BUGS.txt file for list of fixed bugs.
Current version is now Cheddar-1.2p1.
- 10/21/2002 : improve installation Makefile and online User's guide.
None currently.
Current developments on Cheddar are about the following topics:
- Spacewire analysis.
- Joined scheduling and security analysis.
- NoC support.
- 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:
- 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 .
-
A tutorial about
AADLInspector, Cheddar and AADL :
which shows how to use AADLInspector, the commercial version of Cheddar with AADL for
uniprocessor
scheduling analysis.
CPS-WEEK Conferences, Montréal, Canada.
April 2019, in English. A similar tutorial was given during
Ada Europe Conference, Lisbon, Portugal in June 2018.
The slides
of the tutorials are there, In English.
-
A lecture and tutorial about Cheddar and RTEMS,
for the University of Split in December 2021.
-
A lecture about AADL, with Cheddar for ETR'09. In French.
-
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.
-
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 Release 3.x 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 :
- Videos (tutorials or lectures)
about 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.
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.
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),
Mounir Lallali (Lab-STICC/Université de Bretagne Occidentale),
Jalil Boukhobza (Lab-STICC/ENSTA-B),
Valérie-Anne Nicolas (Lab-STICC/Université de Bretagne Occidentale)
and Frank Singhoff (Lab-STICC/Université de Bretagne Occidentale).
Phd Students working on Cheddar:
Illham Atchadam and Blandine Djika.
Former Phd Students:
Mourad Dridi,
Rahma Bouaziz,
Hai Nam Tran,
Shuai Li,
Vincent Gaudel,
Jérôme Legrand.
The project has been funded by Ellidiss Technologies,
Conseil régional de Bretagne, UBO, Brest Métrople, BPI France,
Conseil département du Finistère, Thales TCS and EGIDE/Campus France PESSOA number 27380SA and 37932TF.
Researches on Cheddar are also performed in collaboration with the following partners:
- S3/Télécom-Paris-Tech,
- MARS/ISAE,
- and 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.
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).