Stochastic Analysis of a resource reservation system

An unmistakable trend in embedded systems is the growth of soft real-time computing. A soft real-time application is one for which deadlines can occasionally be missed, but the probability of this event has to be controllable and predictable. This work is aimed to close the gap in the research of stochastic real-time analysis related to resource reservation scheduling algorithms. This dissertation attempts to: 1. give a quick overview of classic real-time analysis 2. analyze the problems related to use the well-known techniques in the context of soft real-time applications: • overvalue the assignation of parameters as in hard real- time systems based on worst case execution times • time and memory complexity using the known theoretical stochastic analysis 3. propose solutions able to overcome the limitation showed in point 2 4. show some specific examples (theoretical and practical) in which resource reservation lead to advantages. The novel contributions of this thesis are: • a new bound to predict the probability of a deadline misses in a resource reservation systems • a very efficient numeric solution for matrix generated with well-know abstraction models of reservation based on Quasi Birth Death Markov Process • an analytical solution, with some conservative approximations, for the same models. • a new model for specific applications, like interrupts. • experiments using resource reservation in different contexts The thesis is evolved following two different approaches: 1. the first based on the exact model of reservation, and the contributions is: • define a new pessimistic bound, efficient in term of computation, able to overcome the problem of complete knowledge of the computation time. The solution is an approximation of the real solution of the model. 2. the second based on an approximation model in which the novel contributions are: • presents an exact and numeric efficient solution for the model based on Quasi Birth and Death Markov Process • introduces an approximate analytical solution which can be computed with no complexity and which is reversible These techniques are applicable since the minimum interarrival of a request is greater than a server period. Unfortunately exists situations in which this assumption is not feasible. An important example is using resource reservation to scheduling interrupts. In order to consider also this situation, another important novel result of this thesis is: • to introduce a new model for scheduling interrupts In addition, some practical examples of using resource reservation are presented.