Integration of non periodic events in real-time systems: application to the event handling in the Real-Time Specification for Java
I’ve been preparing this thesis from October 2005 to December 2008. My supervisor was Serge Midonnet at the Laboratoire d'informatique Gaspard-Monge. I’ve defended this thesis the 8th of December 2008.
On the web
> hal/tel
Downloads
> The manuscript in french (PDF)
> The slides of the talk, in french (PDF)
Erratum
- Page 47 equation 3.6, one should read "j.Ci" instead of "(j-1).Ci"
- Page 62 Alg. 3:
- line 2, "← 0" should be "← t"
- line 5, "+t" is missing
- Page 63, "∀ j ≥ i" behing the second "min" sould be "∀ j ≤ i"
Resume
In computer science, real-time systems are composed by tasks. For each task is associated a temporal constraint called a deadline. We distinguish two kinds of deadline: the hard ones and the soft ones.
Hard tasks have hard deadlines, and a hard deadline must be respected to ensure the correctness of the system. So hard tasks are by essence periodic, or sporadic. Their behavior is well studied and a lot of works have been conducted on their analysis.
On the other hand, aperiodic events can only be handled by aperiodic tasks. For such kind of task, the arrival model is unknown. That allows for burst arrivals, which makes the tasks temporal behavior unpredictable. So aperiodic tasks can only have soft deadlines.
The studied problem in this thesis is then the jointly scheduling of hard periodic tasks with soft aperiodic events, where the response times of soft tasks have to be as low as possible whilst the warranty to meet their deadlines has to be given to hard tasks.
A lot of solutions have been proposed these past two decades. We distinguish solutions based on resource reservation, like task servers and solutions which take benefit from system idle times, like the slack stealer techniques.
The Java programming language has grown in popularity since its first release in 1995. Despite a lot of non real-time compliant characteristics, like its interpretation over a virtual machine, its automated memory gesture or its scheduling model's lack of specification, the language qualities have greatly interested the real-time community.
The first version of the Real-Time Specification for Java (RTSJ) is proposed in early 2000. This specification addresses a lot of problems linked to the memory management or the scheduling of periodic tasks. But if it proposes a model to write aperiodic events, advanced mechanisms for the integration of such events to handle the problem described in the last paragraph are not discussed.
We propose modifications to the main advanced mixed scheduling mechanisms like the Polling Server (PS), the Deferrable Server (DS) or the Dynamic Approximate Slack Stealer (DASS) in order to make their implementation possible with the RTSJ. Indeed, these algorithms are deeply connected to the system scheduler, and have to be adapted in order to be implemented in a userland level.
We propose extensions to current RTSJ API in order to integrate the modified algorithms and to allow the add of other algorithms in a unified framework.
We also proposed some modifications to the RTSJ API in order to address some problem we encounter during the integration of our algorithm, especially in the field of the feasibility analysis algorithm integration in the specification.
Finally we propose a Minimal Approximate Slack Stealer algorithm, Minimal Approximate Slack Stealer (MASS), which is independent of the scheduler implementation and has a lower overhead than MASS. However, this is in the expense of the performances.