HomePublicationsPhD Thesis

Schedulability Analysis of Multiprocessor Real-time Systems Using Pruning
Ref: CISTER-TR-160703       Publication Date: 12, Jul, 2016

Abstract:
We address a range of schedulability analysis problems for multiprocessor real-time systems. As most of these problems are NP-complete and no efficient solutions have been so far proposed, we tackle these problems by employing mathematical optimization combined with the dynamic pruning of the solution search space. We show that such an approach results in solving algorithms of a significantly lower time and space complexity compared to other state-of-the-art solutions. In the best case, the complexity can be reduced from exponential down to just linear.
We use the pruning approach to solve a range of schedulability analysis problems. We first derive an exact schedulability test for sporadic real-time tasks, scheduled by Global Fixed Priority (GFP). Our test is faster and less memory consuming, compared to all previously known exact tests. We achieve such results by pruning the state space through employing such constraints as i) a sufficient schedulability condition, ii) the length bound for the longest release sequence to be considered, iii) critical job release instants, iv) an optimized clock transition between checked system states, as well as others. We also extend the test to continuous-time schedulers (e.g. an event-driven scheduler, which is opposed to a tick-driven scheduler), discarding the assimption of discrete time and integer task parameters, by employing linear programming methods combined with the search space pruning, instead of naive enumeration methods.
Another considered problem is the schedulability analysis of compositional multiprocessor real-time systems. Our solution is based on solving a set of mixed-integer non-convex optimization problems. Due to their high complexity, no existing solver could efficiently determine a solution. To make solving possible, we first prune the solution search space, exploring the theoretical insides of the scheduling problem, and then employ an adequate optimization solver over a reduced search space, so that it quickly finds an optimal solution. The resulted search space is so narrow, that approximate solvers perform almost as good as exact ones: in most cases an approximate solver finds a true global optimum, but significantly faster compared to an exact solver.
All solutions have been implemented in C++ and Matlab environments, and they are publicly available.

Artem Burmyakov

Document:

View
PDF Download
PDF