~/bin/Cheddar-3.3-Linux64-bin
HOWTO_INSTALL.txt$ cd ~/bin/Cheddar-3.3-Linux64-bin) and run Cheddar ($ ./cheddar)
In this section, we will design our first Cheddar model.
Let describe the architecture of the real-time system we want to verify. For such a purpose, we will use the Cheddar built-in ADL (ADL stands for Architecture Description Language), called Cheddar ADL. Cheddar ADL is an architecture description language dedicated to real-time scheduling analysis. A Cheddar ADL model is composed of a description of both the hardware and of the software part of the system to analyse. Those models can be written with any editors, but in the sequel, we will use the graphical editor of Cheddar as follow:
processor components embedding each one or several
core components with optionnal cache components.
A core component models a unit of computation, i.e. an entity providing the support to run one or several tasks.
core component, use the menu Edit/Hardware/Core which opens the windows of the Figure 2:
core component is defined by the following attributes:
Name: the unique name of the component, here, core1.
Scheduler type: the way tasks will be allowed to share the core,
i.e. the scheduling policy
assigned to the core.
In the window above, the core component owns a preemptive fixed priority scheduler compliant with POSIX 1003
(value POSIX_1003_Highest_Priority_First_Protocol for the Scheduler type attribute).
In Cheddar, with such scheduler, allowed priority values ranges from 0 to 255
(255 is the highiest priority level).
As with Linux, priority 1 to 255 are devoted to SCHED_RR and SCHED_FIFO tasks
while
priority level 0 is devoted to the SCHED_OTHER policy.
Such policies allow Cheddar to compute a deterministic scheduling even when the software architecture
model have several tasks with equal priorities.
Preemptive type: specicy if the scheduler is preemptive or not. Add: allows you to add a component to the architecture model.
Delete: allows you to delete a component from the architecture model.
Before pushing this button, you must select the targetted component in the component list in the right side of the window.
Modify: this button has a behavior similar to the Delete button, excepts that the
component is updated with the values of the attributes in the left part of the window.
Close: closes the window and validates all the updates made since the windows was opened.
Cancel: closes the window and cancels all the updates made since the windows was opened.
core1 is defined, we can define processor components that
use
core1 with the
Edit/Hardware/Processor menu, which displays the following windows:
cpu1 which is composed of the core1
component.
Adding or deleting a core inside a processor can be achieved with the buttons
Add and Delete from the subwindows called Cores Table.
In this lab, we restrict ourself with uniprocessor architecture models. Then,
processor only contains
one core component and then, we need to set Processor Type and Migration Type
attributes
respectively to
Monocore Type and
No Migration Type values.
task Cheddar ADL component type and
resource component type).
Other software components exist in Cheddar ADL, but they are not required there (See the
Cheddar ADL reference guide for further details).
task and
resource components have to be defined inside
Address Space components.
An Address Space component can be seen as a entity modelling
the concept of
an application, or a Unix process address space, or even an ARINC 653 partition.
Edit/Software/Address space)
shows you how to define an
Address Space for this tutorial.
The only attributes we have to define are
Name and Cpu Name.
For the next exercises, we have to define one
Address Space component for each processor component.
However, for specific analysis as ARINC 653 or more generally,
hierarchical architecture models,
more attributes have to be specified for such kind of component.
Edit/Software/Task:
Name: the unique name of the component.
Task type: the type of the task, which specifies how the task will be released.
A task may be periodic, sporadic, released according to a poisson process (e.g. poisson task type),
GMF, aperiodic, ...
Capacity: the WCET of the task.
Period: the delay between two successive release times of the task.
Deadline: the deadline the task has to meet. It is a delay relative to the period of the task (i.e. not an absolute deadline).
Address space name and CPU name where the task is supposed to be located/run.
Priority: priority level assigned to the task. 255 is the higher level of priority; 0 is the lower.
Capacity = 2, Deadline = 6, Period = 6 Capacity = 2, Deadline = 9, Period = 9 Capacity = 3, Deadline = 12, Period = 12 Priority attributes were assigned according to Rate Monotonic within the allowed priority range (from 1 to 255). Deadline). Start time is set to 0 in order to model a synchronous task set. File/Save XML Project: a system modeled in Cheddar can be exported in a XML file respecting the Cheddar ADL format.
File/Open XML Project: a model can be imported to Cheddar to be analyzed.
In this tutorial, for several exercises, the models are available to download.
In this last section, we show how to perform an analysis of the architecture model previously designed.
From the menu Tools and for a given
architecture model, we can perform 3 types of analysis with Cheddar:
Under the menu, some buttons allow you to quickly access to a summary of those Cheddar analysis features
(all analysis features can be accessed by the Tools menu).
Indeed, the 
button starts a scheduling simulation and the
button computes a sample of
feasibility tests for a basic periodic task set.
Basically, the button computes
worst case task response time following the
Joseph et Pandia [JOS 86] method extended for any Deadline and classical CPU bound tests.
Again, for specific feasibility tests (e.g. transactions), see the Tools menu.
Figures 6 et 7 show a screenshot of Cheddar for the model edited in section
I.2, and for results produced by buttons
and
.
We can see there worst case response times computed by the
Joseph and Pandia [JOS 86] method and also by the scheduling simulation
on the feasibility interval.
Feasibility tests on cpu utilization factor cannot be applied there
as the tool cannot be
sure that priorities have been assigned according to Rate Monotonic. To apply this test, one
must change the
scheduling policy of the core1 component with the Rate_Monotonic_Protocol value.
We can also notice in the time lines that vertical red rectangles show task release times.
Horizontal rectangles
show when tasks are running. Many other display options exist there and can be modified by the
Tools/Scheduling/Scheduling Options menu.
Let see now our first true exercise.
and ,
check that you get the results of the figures 6 and 7.
Capacity = 2, Deadline = Period = 6, Start time = 0
Capacity = 8, Deadline = Period = 24, Start time = 0
Capacity = 4, Deadline = Period = 12, Start time = 0
).
From this simulation, check the schedulability of this task set.
In the sequel, we will experiment and compare 3 classical scheduling policies.
Capacity = 4, Deadline = Period = 8, Start time = 0
Capacity = 5, Deadline = Period = 10, Start time = 0
). Earliest_Deadline_First_Protocol for the Scheduler type attribute).
Do again questions 2 and 3. Task Type (see. figure 5): Period=Deadline=8, Capacity=4, Start time = 0
Period=Deadline=16, Capacity=8, Start time = 0
Deadline=15, Capacity=4, Start time = 0
).
What can you see now? Period=Deadline=9, Capacity=4, Start time = 0
Period=Deadline=8, Capacity=3, Start time = 0
Li(t),
the laxity of a task i at time t
can be computed by Li(t)= Deadline - remaining(t) where remaining(t) is the
remaining capacity of the task at time
t.
). Least_Laxity_First_Protocol for the Scheduler type attribute).
Do again questions 2 and 3. In the previous exercises, we assumed the tasks as independent. In the sequel, we illustrate the use of Cheddar with dependent tasks: with tasks sharing resources according to classical protocols such as PCP or PIP.
Period=Deadline=6, Capacity=2, Start time = 0
Period=Deadline=8, Capacity=2, Start time = 0
Period=Deadline=12, Capacity=5, Start time = 0
We assume a preemptive fixed priority scheduling policy and we apply Rate Monotonic to assign priorities.
We also assume that tasks T1 and T3 share a resource named S. T1 and T3 access to S in mutual exclusion:
Edit/Software/Resource menu which displays the following window:
Name : the unique name of the shared resource.
CPU Name and Address space name: give where the resource is located.
State: is the status of the resource.
A Cheddar ADL resource may be seen as a
counting semaphore.
A Cheddar ADL resource has an integer value.
When a task allocates a resource, its counter is
decremented. When a task releases a resource, its counter is incremented.
When this counter is equal or less than 0, a task which requests the resource
is blocked as the resource is already allocated.
For our exercises,
State must be set to 1.
Protocol: is the protocol to apply when a resource is handled by a task.
The value No Protocol means that the simulator will apply no priority inheritance and that
the blocked tasks on the semaphore are stored in a FIFO queue.
In this exercise and in the next one, we will alo use the values
Priority Inheritance Protocol (or PIP) and
Priority Ceiling Protocol (or PCP)
when we need to apply inheritance protocols.
Right now, you must set this attribute with the value
No Protocol for the resource S.
Priority assignment : specify if the ceiling priority of
the resource component
will be computed automatically by Cheddar, or assigned manually by you.
For our exercises, we have to set this attribute to
Automatic Assignment.
Begin is the start time of each critical section and End
is the critical section completion time.
The buttons Add and Delete allow the designer
to create or remove a critical section for a given resource.
As an example, the Figure 8 shows how to express that T1
needs the resource at the beginning of its 2nd unit of time and
releases the resource at the end of this unit of time.
Again in this Figure, we can see that T3 needs the resource during all its capacity
(i.e. before starting
the 1st unit of time and after its 5th unit of time).
).
You should get the scheduling simulation of the Figure 9.
Tools/Scheduling/Scheduling Options menu).
Furthermore, bleu vertical rectangles show when the resources are locked while red vertical rectangles show
when resources are unlocked.
Priority Inheritance Protocol (or PIP), and compute again the scheduling simulation.
With PIP, a task which blocks another with a higher priority, runs its critical section
with the blocked task priority.
button, compute the worst case response time with the
Joseph et Pandia method and compare those results with the one computed during the scheduling simulation.
What can you see? Explain.
Period=Deadline=31, Capacity=8, Start time = 0
Period=Deadline=30, Capacity=8, Start time = 2
Start time attribute.
We use a fixed priority preemptive scheduling policy for such task set.
T1 and T2 require the access to the shared resources R1 and R2 as follows:
PIP (Priority Inheritance Protocol).
).
Priority Ceiling Protocol in the Figure 8).
For such a purpose, you have to update both R1 and R2.
PCP works as follows:
We investigate a system embedded in a car which displays various data to the driver. This system is composed of several tasks and we expect to verify their timing behavior.
The system is composed of 5 tasks:
We assume that all tasks start their first activation at the same time. Furthermore, all tasks must complete their current activation before they have to start the next one.
We assume an execution platform composed of one processor which provides a preemptive fixed priority scheduler. Priorities range from 0 to 31. 0 is the lowest priority value. The system does not allow designers to assign the same priority value to several tasks.
Question 1:
Question 2:
With Cheddar, from the priority assignment of the previous question, compute the
worst case response times with the Joseph and Pandia method for the
SENSOR_1, the SENSOR_2, and the SENSOR_3 task.
Question 3:
In fact, tasks
SENSOR_1,
SENSOR_2,
and SENSOR_3
share a memory area protected by a semaphore (i.e. accessed in mutual exclusion).
SENSOR_1 et SENSOR_2 needs this memory during all their capacity
while
SENSOR_3 only needs it during the 2 first units of time of its capacity.
The semaphore protecting the memory applies the PIP protocol.
Explain why the worst case response times computed in the previous question are not true
anymore.
Question 4:
With Cheddar, compute the scheduling of this task set on the 60th first units of time.
Say when the shared resource is allocated and released. Say also if some priority inversions
occur. Finally say when the priorities of the tasks change due to PIP.
Question 5:
For the questions 5 and 6, we now assume that all tasks are independent.
In order to activate more frequently the tasks, we experiment the scheduling of those
tasks on a two processor platforms : processors
a and b.
Migrations of the tasks are not allowed: we then apply a partitionning approach.
The tasks are defined according to those parameters:
Capacity = 4, Period=Deadline= 6 Capacity = 2, Period=Deadline= 20 Capacity = 2, Period=Deadline= 3 Capacity = 2, Period=Deadline= 5 Capacity = 2, Period=Deadline= 5
Question 6:
In fact, tasks were assigned to processors randomly.
All tasks can run on both processors.
Processors
a and
b only differ from their execution speed:
On
processor b, a task runs twice more quickly than on
processor a.
Assign tasks to processors
a and b such as all task deadlines can be met.
Explain your choice.
| Tasks | Priorities | Periods/Deadlines | WCET |
|---|---|---|---|
| SCHED_BUS | 1 | 125 ms | 25 ms |
| DATA | 2 | 125 ms | 25 ms |
| CONTROL | 3 | 250 ms | 25 ms |
| RADIO | 4 | 250 ms | 25 ms |
| VIDEO | 5 | 250 ms | 25 ms |
| MESURE | 6 | 5000 ms | 50 ms |
| FORECAST | 7 | 5000 ms | Between 50 ms and 75 ms |