Potential bug related to non preemptive EDF

[Dimitris Deligiorgis]

si the file attached for the description of the bug

[singhoff]

Cheddar Bugs and Warnings Report
In the sphere of my postgraduate final project I was assigned to develop a hard real time simulator based on Cheddar tool. Of course Cheddar is a really large scale tool covering a wide variety of algorithms and a lot of different task’s characteristics. The tool I am going to develop is quite simple supporting only three main algorithms and a really basic set of task characteristics. Also it has some additional characteristics the Cheddar doesn’t.
I used Cheddar as a model, so I run a lot of scenarios and I managed to discern some special points that I would like to report to you.
1.Cheddar does not represent EDF algorithm behavior correctly all the times. See an example below, with 3 periodic tasks, one non preemptive processor and one address space.

Task Characteristics:

Name
Period
Capacity
Deadline
Start Time
T1
5
2
5
0
T2
7
3
7
0
T3
7
2
6
0

Cheddar’s respond:

Watching the above screenshot, we can determine that at 11 unit of time T3 has completed its execution and T1 & T2 are now available to be executed. But according to EDF algorithm T2 has higher priority than T1 because its deadline is at 14 which is earliest of 15 (T1 deadline). However T1 takes the CPU.
2.When an algorithm is preemptive, knows all information, about tasks and has the ability to start and stop each task according to its priority. Let’s see the above example again with the same task set but with EDF preemptive.

Now we can observe that EDF works fine at 11 temporal point as T2 takes the CPU which has higher priority than T1 because it has earliest deadline. But let’s focus at 15 unit of time, T1 has lost its deadline however CPU continue to execute T1 for another unit of time. The intelligence of a preemptive algorithm is to stop a task when it has lost its deadline however the approach of preemptive EDF from Cheddar doesn’t seem to respond with this way of thinking.
3.Cheddar faces the aperiodic tasks with a really static way. I mean that Cheddar gives the same results independently of how many times we simulate a scenario. Take a look below to see what I mean.

Task Characteristics:

Name
Period
Capacity
Deadline
Start Time
T1
5
2
5
0
T2
7
3
7
0
T3
-(aperiodic)
2
7
0

Cheddar’s respond (0 to 35):

Cheddar will give exactly the same results, so as many times we execute the scenario. But the reason of the existence of an aperiodic task in a simulated system is that this task is non predictable. I mean that the unit of time that a task will come to the system is absolutely random. However Cheddar does not respond with this way.
The use of an aperiodic task in a simulated system is really important because the more random an aperiodic task is, the more realistic a simulator does. Real systems have many unpredictable factors that can affect the performance of a system and some tasks lose their deadlines if an aperiodic task comes at a critical point. So we understand how important is to approach an aperiodic task with a really random way in order to have a more realistic simulator.
4.The way that Cheddar faces the start at time of a task is really strange. Let’s take a look of two simple tasks with one EDF preemptive processor.

Task Characteristics:

Name
Period
Capacity
Deadline
Start Time
T1
5
2
2
1
T2
8
3
8
0

Cheddar’s respond:

We can see the Cheddar displaces right the period of T1 task for one unit of time (=start time) and I cannot understand why it does that. Executing the scenario we observe that the task set is schedulable as no one task missed its deadline. But how is this possible as T1 starts at 1 having deadline at 2 and at the same time has execution time 2 units of time.