Name
Abstract | ||
|---|---|---|
Abstract This paper presents a connection between two real-time models: a deadline-based model and a latencybased model. The importance of the latency-based model is proved through a result showing that two deadlines, instead of a latency constraint, over-constrain the real-time applications. Moreover, we give a deadline-marking algorithm based on the relation between deadlines and latency constraints. This algorithm provides non-preemptive feasible schedules for systems with precedence constraints and deadlines, or more complex systems with deadlines and latencies. This is the first step toward non-preemptive schedulability for distributed architectures (without over-constraining the system) like, for example, the automotive applications using protocols such as Controller Area Network (CAN). Keywords: scheduling, real-time, non-preemptive, latency, deadline, periodicity. Real-time systems are, first of all, reactive systems, i.e., an output event produced by actuators reacting to an event coming into the system through sensors. This behavior is commonly,seen in periodic systems of operations. In the classical deadline-based model given in Liu (1976), an operation becomes available at its release time which is repeated periodically. The start time of an operation is greater or equal to its release time. The operation must be scheduled before its deadline which is relative to the release time. The formal definition of this model is given in section 1. We refer to the classical model as the ”deadline-based model”. However, the deadline-based model with release times is not adaptable to some applications such as real-time control. For example, if the start times of input and output operations of a control law are not periodic, then the performances of the controller decrease. In Torngren (1998), the author lists dierent results which take into account this variable delay by increasing the complexity of the control law, but the delay between control law computation and the output operation need to be constant. Therefore, strict periodicity constraints are necessary in these cases (see Korst (1996)). In our model given in Cucu and Sorel (2002) besides the strict periodicity constraints, two other types of constraints may be imposed on these systems. Firstly, since some operations can produce data consumed by other operation(s), we need to specify that a producer operation must be executed before |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10479-007-0279-9 | Annals OR |
Keywords | Field | DocType |
Scheduling,Real-time,Non-preemptive,Latency,Deadline,Periodicity | CAN bus,Complex system,Nonpreemptive multitasking,Latency (engineering),Scheduling (computing),Computer science,Real-time computing,Schedule,Periodic graph (geometry),Automotive industry,Distributed computing | Journal |
Volume | Issue | ISSN |
159 | 1 | 0254-5330 |
Citations | PageRank | References |
4 | 0.47 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liliana Cucu | 1 | 171 | 8.91 |
| Nicolas Pernet | 2 | 5 | 1.55 |
| Yves Sorel | 3 | 247 | 23.94 |