Verifying and Allocating Real-Time Tasks on Distributed Processing Units
Alejandro Masrur · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2010
In general, two major issues arise when designing real-time embedded systems upon multiple processors: task allocation and feasibility/schedulability analysis.The task allocation problem is concerned with the assignment of tasks to processors, whereas the feasibility/schedulability analysis deals with testing whether a given set of real-time tasks is schedulable or not.A set of real-time tasks is said to be schedulable or feasible on one or more processors, when all its timing constraints (deadlines) can be guaranteed.Clearly, we cannot allocate real-time tasks to processors that are unable to guarantee their deadlines and, hence, these two problems are interdependent and cannot be handled separately.In this thesis, we provide an integrated framework for task allocation and feasibility analysis.In particular, new better linear-time feasibility tests are used in conjunction with allocation heuristics.This way, we first analyze the case of allocating independent real-time tasks and then extend algorithms to consider task dependencies.The contributions of this thesis are as follows:• A novel technique is proposed to perform the feasibility analysis of both fixed and dynamic-priority scheduling policies.This new technique consists in calculating the maximum loading factor generated by real-time tasks on a single processor.The concept of loading factor is defined as the total execution demand within a specified time interval divided by the length of this interval.Hence, the maximum loading factor is the upper bound on the loading factor which results from considering every possible time interval.As a consequence, if the maximum loading factor of a given task set is less than or equal to unity on a single processor, the processor will be able to comply with the execution demand of all tasks.Thus, the task set is said to be feasible on that processor.• Applying the concept of maximum loading factor, linear-time sufficient feasibility tests are presented for the most general case of task having arbitrary deadlines.We analyze both fixed-priority and dynamic-priority scheduling algorithms.Further, the proposed feasibility tests are shown to be more accurate (i.e., less pessimistic) than the known algorithms with same complexity that can be found in the literature.• The proposed feasibility tests are also combined with well-known bin packing heuristics (e.g., First Fit and First Fit Decreasing) to derive fast polynomial-time allocation algorithms for independent real-time tasks with arbitrary deadlines.By means of a detailed comparison, we further show that these algorithms achieve better task allocations on the average than the ones based on feasibility analysis methods from the literature.This means that the proposed heuristics lead to a bigger reduction of the number of processors, which are necessary to guarantee feasibility for the whole task set.vii • The problem of allocating dependent real-time tasks to multiple distributed processors is analyzed.Particularly, we focus on task communication and system constraints.For the case of communicating tasks, different heuristics are presented to reduce the amount of communication between processors during the allocation procedure.Finally, some additional allocation heuristics are proposed to minimize both the number of processors and the amount of communication between them.In contrast to most communication-aware allocation methods from the literature, the proposed algorithms have polynomial complexity and can possibly be adapted to perform an on-line allocation for communicating tasks.viii Zusammenfassung In Bezug auf die Entwicklung eingebetteter Realzeit-Systeme basierend auf mehreren Prozessoren entstehen im Allgemeinen zwei große Herausforderungen: die Taskallokation und der Echtzeitnachweis.Während sich die Taskallokation mit der Zuordnung von Tasks auf Prozessoren beschäftigt, ist das Echtzeitnachweis-Verfahren dafür verantwortlich, die Machbarkeit des Realzeit-Tasksystems zu prüfen.Ein Realzeit-Tasksystem ist nur dann machbar oder realisierbar, wenn garantiert werden kann, dass alle Zeitschranken (Deadlines) eingehalten werden.Dabei soll eine Task keineswegs einem Prozessor zugeordnet werden, der nicht in der Lage ist, sie rechtzeitig auszuführen.Daher können Echtzeitnachweis und Taskallokation nicht getrennt und müssen als ein Ganzes betrachtet werden.Diese Dissertation befasst sich mit einer ganzheitlichen Betrachtung von Taskallokation und Echtzeitnachweis.Insbesondere werden neue und bessere Echtzeitnachweis-Verfahren linearer Zeit in Verbindung mit Allokationsheuristiken verwendet, wobei die Allokation unabhängiger Realzeit-Tasks zunächst analysiert wird.Darüber hinaus werden die Algorithmen zur Berücksichtigung von Taskabhängigkeiten erweitert.Der wissenschaftliche Beitrag dieser Dissertation kann folgendermaßen zusammengefasst werden: • Eine neuartige Technik zum Echtzeitnachweis wird eingeführt, die bei Scheduling-Verfahren sowohl fester als auch dynamischer Priorität angewandt werden kann.Die vorgestellte Echtzeitnachweis-Technik basiert auf der Berechnung des maximalen Belastungsmaßes, welches das Tasksystem auf einem Einzelprozessor bewirkt.Der Begriff Belastungsmaß wird als das Verhältnis zwischen der gesamten Rechenanforderung innerhalb eines bestimmten Zeitintervalls und der Länge des Zeitintervalls definiert.Das maximale Belastungsmaß ist daher die obere Schranke des Belastungsmaßes, die aus der Betrachtung jedes möglichen Zeitintervalls resultiert.Wenn das maximale Belastungsmaß eines Tasksystems auf einem Einzelprozessor nicht die Einheit übersteigt, dann ist der Prozessor imstande die Rechenanforderung aller Tasks zu entsprechen.Das Tasksystem ist infolgedessen realisierbar auf dem Prozessor.• Für den allgemeinen Fall beliebiger Deadlines werden hinreichende Echtzeitnachweis-Verfahren linearer Zeit, basierend auf dem Begriff des maximalen Belastungsmaßes, präsentiert.Scheduling-Algorithmen mit festen und mit dynamischen Prioritäten werden analysiert.Des weiteren wird gezeigt, dass die vorgestellten Verfahren genauer (d.h.weniger pessimistisch) sind, als bekannte Algorithmen gleicher Komplexität aus der Literatur.• Die vorgeschlagenen Echtzeitnachweis-Verfahren werden mit allgemein bekannten Heuristiken für Bin Packing (z.B.First Fit und First Fit Decreasing) kombiniert, um schnelle ix Allokationsalgorithmen polynomischer Zeit für Realzeit-Tasks mit beliebigen Deadlines abzuleiten.Im Durchschnitt erzielen diese Algorithmen eine bessere Taskzuteilung als dazu konkurrierende Methoden basierend auf Echtzeitnachweis-Methoden aus der Literatur.Das heißt, die vorgestellten Heuristiken führen zu einer kleineren Anzahl von Prozessoren, die zur Realisierbarkeit des gesammten Tasksystems notwendig sind.Letzteres wird anhand eines ausführlichen Vergleichs veranschaulicht.• Die Zuteilung von abhängigen Realzeit-Tasks auf mehrere verteilte Prozessoren wird weiterhin analysiert.Insbesondere werden kommunizierende Tasks und systembedingte Randbedingungen in Erwägung gezogen.Für den Fall kommunizierender Tasks werden verschiedene Allokationsheuristiken zur Reduktion des Kommunikationsumfangs zwischen Prozessoren vorgeschlagen.Zum Schluss werden ergänzende Heuristiken dargestellt, die zur Minimierung der beiden Größen Prozessoranzahl und Kommunikationsumfang unter Prozessoren dienen.In Gegensatz zu den meisten in der Literatur vorgeschlagen kommunikationsbewussten Allokationsmethoden zeichnen sich die in dieser Dissertation dargelegten Algorithmen durch ihre polynomische Komplexität aus.Daher eignen sie sich besonders dafür, auf ihrer Basis eine online Taskallokation unter Berücksichtigung von Kommunikation zu realisieren.x