Earliest deadline first scheduling is a dynamic scheduling principle used in real-time operating systems. It places processes in a priority queue. The priority of a process is inversely proportional to its absolute deadline. In other words, the highest priority process is the one with the earliest deadline.
EDF gets an utilization bound of 100% with scheduling periodic processes that have deadlines equal to their periods. Thus, the schedulability test for EDF is:
where Ci are the worst case computation times of the processes and Ti are their respective inter arrival periods (assumed to be equal to the relative deadlines).
If the schedulability test is at most 1 EDF can guarantee that the system is schedulable. That is, EDF guarantees all the deadlines in the system are met. In this case the total CPU utilization is not more than 100%.
In this example, we model a system in which there may be multiple servers that are executed on a processor. To model the structure of such a system, we have specified the following metamodel:
Then, we describe a graphical concrete syntax for it by defining a gcs model. In a gcs model, we associate every class of the metamodel with a picture. This concrete syntax will be used in the definition of the behavioral rules.
We have used e-Motions to model and study the behavior of a schedulable system. For this purpose we have designed five rules.
The InitialRule creates the initial model. This model consists of a processor and three servers which period and execution time attributes are set to certain values. These servers meet the schedulability test. The NAC pattern forbids the triggering of the rule if was already performed before.
The Execution rule models the assignment of a processor to a server. A server gets the processor control if its remExecTime (remaining execution time) attribute is greater than zero, and there is no other server s2 with an earlier deadline and a remExecTime greater than zero (see the NoServerWithSmallerPriority NAC pattern). Additionally, the NoServerInProcessor and NoServerWithoutUpdate NAC patterns forbid the aplication of the rule if the processor is already in use, or if there exist a server whose deadline is equals to 0, i.e., if the value of its deadline has not been properly updated (see the NewPeriod rule below). The duration of the execution will be initially set to the remExecTime of the server, although it could be interrupted earlier by another server (see the StopExecution rule below). At the end of the execution, its starting and ending time are registered in the history attribute of the server.
The StopExecution rule interrupts the execution of a server s2 if another server s1 is found in the model with an earlier deadline. In this case, the remExecTime and history attribute values of the server whose execution is interrupted (s2) are updated.
The DecreaseDeadline ongoing rule decrements the deadline of each server with the passage of time. To not decrease the deadline below zero, we limit the duration of the rule to the deadline server value itself.
Finally, the NewPeriod instantaneous rule initializes the deadline attribute of servers each period. For the case where the servers do not meet the schedulability test, we add the execution time defined for the the server to the possible remaining time value that the server didn't complete during previous periods.
Once the behavior of our system is specified, we can simulate it by using the e-Motions simulation feature. For this example, we can configure the simulation as shown in the following figure.
We do not need to specify an initial model since we have a rule that creates it. Of course, we can simulate the system with different initial configurations by modifying the InitialRule. The result of the simulation can be analyzed by exploring the "history" attribute of each server, which contains pairs of numbers that represents the time at which the server starts and finishes an execution on the processor.
The EDF.zip file contains the project with all files required to try this example: the metamodel definition, the graphical concrete syntax for the metamodel and its corresponding behavioral specifications. To import this project, right click on the navigation view Import...-> General -> Existing Projects into Workspace -> Select archive file and then select the EDF.zip file.