Master Thesis MSTR-2015-13

BibliographyKayarat, Rekha: Advanced Multi-core Simulation of Real-Time Embedded Systems.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis (2015).
131 pages, english.
Abstract

To achieve the need for high-performance processors, the industry saw a shift from increasing processor clock speed on a single processor to designing systems with multiple cores. For such systems to be truly useful in an embedded hard real-time environment, it is required that they be supported by robust scheduling and resource allocation algorithms. The robustness of a scheduling algorithm is determined by its various performance metrics, like its optimality, the utilisation it provides and its ability to reduce the overall scheduling overhead. Also important is its ability to handle sporadic tasks as and when they arise, and still be able to ensure overall system schedulabilty. The features of any good resource allocation algorithm include its ability to ensure fairness, avoid deadlocks and limit the time for which a task is denied a resource. To satisfy such a tall order, many scheduling algorithms and resource allocation algorithms have been proposed in the last two decades. Many of these scheduling algorithms, are based on the concept of \proportionate progress". They guarantee optimality and promise a 100% utilisation of the available cores, but they are susceptible to a large number of preemptions and migrations. Several algorithms have since been proposed to improve that aspect, some of which are based on a concept called \Deadline Partitioning Fairness technique or DP-Fair". The early multi-core algorithms that were based on the optimal uniprocessor algorithm Earliest Deadline First (EDF) produced fewer preemptions and migrations in their schedules but were considered non-optimal, until recently when Nelissen introduced the multiprocessor scheduling algorithm U-EDF (an Unfair algorithm based on EDF). U-EDF promises optimality and a 100% utilisation of the available cores. Algorithms from these three groups are considered in this thesis work. The multiprocessor resource allocation algorithm Flexible Multiprocessor Locking Protocol (FMLP) is also considered with scheduling algorithms Partitioned EDF (P-EDF) and Pseudo-Deadline2 (PD2). The adoption of these scheduling algorithms by the industry is something that still has to be seen. The focus of this thesis work is threefold. First, and perhaps the most important, is the study of some of the important multi-core scheduling algorithms, and their implementation in the SAVORS (Simulation And Visualisation Of Real-time Scheduling) simulator. The SAVORS simulation framework, which is the result of previous thesis works, is still a one-of-a-kind simulation system that o ers synchronous simulation and visualisation capabilities. It is important to keep such a simulator up-to-date, and hence this work extends its capabilities by including some of the latest multi-core algorithms that have been published, as late as 2014. Scheduling policies for sporadic task systems are also newly added to the SAVORS simulator. The second main contribution of this thesis work is an automatic task generation system with the capability to generate various task models with random parameters. It helps avoid the manual creation of simulation models by the SAVORS user and helps study the behaviour of scheduling algorithms under di erent task models. The third main contribution of this thesis work is the results of a performance comparison of the scheduling algorithms PD2, BF2 (Boundary Fair algorithm with 2 tie breaking parameters) and U-EDF based on their scheduling overhead (number of preemptions and migrations).

Full text and
other links
PDF (1658105 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Software Technology, Programming Languages and Compilers
Superviser(s)Plödereder, Prof. Erhard; Prokharau, Mikhail; Northover, Mandy
Entry dateJuly 30, 2018
   Publ. Computer Science