Typically, a real-time system consists of a controlling system (i.e., a computer) and a controlled system (i.e., the environment). Real-time systems are those systems where correctness depends on two aspects: i) the logical result of computation and, ii) the time in which results are produced. It is essential to guarantee meeting timing constraints for this kind of systems to operate correctly. Missing deadlines in many cases -- in so-called hard real-time systems -- is associated with economic loss or loss of human lives and must be avoided under all circumstances. On the other hand, there is a trend towards consolidating software functions onto fewer processors in different domains such as automotive systems and avionics with the aim of reducing costs and complexity. Hence, applications with different levels of criticality that used to run in isolation now start sharing processors. As a result, there is a need for techniques that allow designing such mixed-criticality (MC) systems -- i.e., real-time systems combining different levels of criticality -- and, at the same time, complying with certification requirements in the different domains. In this research, we study the problem of scheduling MC tasks under EDF (Earliest Deadline First) and propose new approaches to improve scheduling techniques. In particular, we consider that a mix of low-criticality (LO) and high-criticality (HI) tasks are scheduled on one processor. While LO tasks can be modeled by minimum inter-arrival time, deadline, and worst-case execution time (WCET), HI tasks are characterized by two WCET parameters: an optimistic and a conservative one. Basically, the system operates in two modes: LO and HI mode. In LO mode, HI tasks run for no longer than their optimistic execution budgets and are scheduled together with the LO tasks. The system switches to HI mode when one or more HI tasks run for more than their conservative execution budgets. In this case, LO tasks are immediately discarded so as to be able of accommodating the increase in HI execution demand. We propose an exact test for mixed-criticality EDF, which increases efficiency and reliability when compared with the existing approaches from the literature. On this basis, we further derive approximated tests with less complexity and, hence, a reduced running time that makes them more suitable for online checks.:Contents 1. Introduction 1 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Concepts, Models and Assumptions 7 2.1. Real-Time Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1. Tasks Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Scheduling Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1. Feasibility versus Schedulability . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2. Schedulability Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Mixed-Criticality Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4. Basic Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5. The Earliest Deadline First Algorithm . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1. EDF-VD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.3. Demand Bound Function . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Related Work 17 3.1. Uniprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1. Uniprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . . 18 3.2. Multiprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1. Multiprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . 20 4. Introducing Utilization Caps 23 4.1. Introducing Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1. Fixed utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.2. Optimized utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5. Bounding Execution Demand under Mixed-Criticality EDF 29 5.1. Bounding Execution Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2. Analytical Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.1. The GREEDY Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.2. The ECDF Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3. Finding Valid xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6. Approximating Execution Demand Bounds 41 6.1. Applying Approximation Techniques . . . . . . . . . . . . . . . . . . . . . . . 41 6.2. Devi’s Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2.1. Per-task deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2.2. Uniform deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2.3. Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7. Evaluation and Results 49 7.1. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2. Obtaining Test Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.1. The Case Di = Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.2. The Case Di ≤ Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.3. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.4. Algorithms in this Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.4.1. The EDF-VD and DEDF-VD Algorithms . . . . . . . . . . . . . . . . 51 7.4.2. The GREEDY algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.4.3. The ECDF algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.5. Evaluation of Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.1. 10 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.2. 20 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.5.3. 50 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.5.4. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.6. Evaluation of Execution Demand Bounds . . . . . . . . . . . . . . . . . . . . 61 7.6.1. Comparison for sets of 10 tasks . . . . . . . . . . . . . . . . . . . . . . 61 7.6.2. Comparison for sets of 20 tasks . . . . . . . . . . . . . . . . . . . . . . 64 7.7. Evaluation of Approximation Techniques . . . . . . . . . . . . . . . . . . . . . 67 7.7.1. Schedulability curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.7.2. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.7.3. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.8. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8. Conclusion and Future Work 77 8.1. Outlook/Future Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Bibliography 83 A. Introduction 91 A.1. Multiple Levels of Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.1. Ordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.2. Unordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . 93 B. Evaluation and Results 95 B.1. Uniform Distribution for Task Periods . . . . . . . . . . . . . . . . . . . . . . 95

No description available.

Kollektive biologische Systeme sammeln Informationen und leiten diese intern weiter, um Umweltveränderungen zu detektieren und auf sie zu reagieren. In Tiergruppen können die probabilistischen Entscheidungen von Individuen durch diese kollektive Informationsverarbeitung verbessert werden. Die dem sozialen Austausch zu Grunde liegenden Sinneswahrnehmungen finden jedoch in gängigen Modellen kollektiven Verhaltens kaum Beachtung. Hier untersuche ich, wie der individuelle Zugang zu sozialen Informationen durch visuelle Wahrnehmung und räumliche Gruppenstruktur geformt wird. Zuerst untersuche ich Fluchtwellen in Fischschwärmen in zwei als unterschiedlich riskant wahrgenommenen Kontexten mithilfe empirisch ermittelter visueller Interaktionsnetzwerke. Die beobachtete strukturelle Änderung der Gruppen zwischen den Kontexten erweist sich als essenziell, um die Änderung der Fluchtwellengröße zu erklären und optimiert potenziell die kollektive Informationsverarbeitung im jeweiligen Kontext. Von optimaler Informationsverarbeitung wird in biologischen Systemen oft angenommen, dass sie an Phasenübergängen in deren kollektiver Dynamik stattfindet, sogenannten kritischen Punkten. Die beobachtete strukturelle Änderung ändert den Abstand des Schwarmverhaltens zu einem solchen kritischen Punkt. Jedoch bleiben die Gruppen subkritisch in beiden Kontexten, vermutlich aus Notwendigkeit, tatsächliche Warnungen zu verstärken und falsche zu unterdrücken. Im zweiten Teil vergleiche ich visuelle Netzwerke mit anderen räumlichen Netzwerken bezüglich ihrer Struktur und dem Verhalten von Ausbreitungsprozessen auf ihnen. Einzig visuelle Netzwerke zeigen bei mittleren Gruppendichten Optima in zentralen Netzwerkeigenschaften und behalten realistische Eigenschaften bei hohen und niedrigen Dichten. Abschließend entwickle ich eine analytische Näherung zentraler Netzwerkeigenschaften solcher visuellen Netzwerke. / Collective biological systems gather information and propagate it internally to detect and react to environmental changes. In animal groups the probabilistic decisions of individuals can be improved by this collective information processing. Animals rely on sensory cues for social communication, yet common models of collective behavior neglect this sensory basis of interactions. Here, I investigate how an individual’s access to social information is shaped by visual sensory limitations and spatial group structure. First, escape waves in fish schools are studied under two levels of perceived environmental risk using empirically inferred visual interaction networks. Group-structural change is found to be crucial to explain the observed differences in size of escape waves and potentially optimize collective information processing according to the state of the environment. Optimal information processing in biological systems is often hypothesized to occur at phase transitions in their collective dynamics, so-called critical points. Here, the observed change in group structure modifies the schools’ distance to a critical point. Yet groups stay subcritical in both experimental setups, which may manage a trade-off between sensitivity to true alarms and robustness to false ones. In a second part, visual networks are compared to other spatial networks in structure and behavior of spreading processes on them. Visual networks show a unique dependence on group density with optima in network structural measures at intermediate densities, making them more realistic than other networks at high and low densities. Finally, an analytical approximation of central properties of visual networks is developed. Overall, this thesis identifies group structure as a potential control mechanism of collective information processing, highlights the trade-off associated with criticality in noisy systems and provides a systematic study and analytic approximation of visual sensory networks.

Im ersten Teil analysiere ich die Selbstorganisation zur Kritikalität (hier ein Phasenübergang von Ordnung zu Unordnung) und untersuche, ob Evolution ein möglicher Organisationsmechanismus ist. Die Kernfrage ist, ob sich ein simulierter kohäsiver Schwarm, der versucht, einem Raubtier auszuweichen, durch Evolution selbst zum kritischen Punkt entwickelt, um das Ausweichen zu optimieren? Es stellt sich heraus, dass (i) die Gruppe den Jäger am besten am kritischen Punkt vermeidet, aber (ii) nicht durch einer verstärkten Reaktion, sondern durch strukturelle Veränderungen, (iii) das Gruppenoptimum ist evolutionär unstabiler aufgrund einer maximalen räumlichen Selbstsortierung der Individuen. Im zweiten Teil modelliere ich experimentell beobachtete Unterschiede im kollektiven Verhalten von Fischgruppen, die über mehrere Generationen verschiedenen Arten von größenabhängiger Selektion ausgesetzt waren. Diese Größenselektion soll Freizeitfischerei (kleine Fische werden freigelassen, große werden konsumiert) und die kommerzielle Fischerei mit großen Netzbreiten (kleine/junge Individuen können entkommen) nachahmen. Die zeigt sich, dass das Fangen großer Fische den Zusammenhalt und die Risikobereitschaft der Individuen reduziert. Beide Befunde lassen sich mechanistisch durch einen Aufmerksamkeits-Kompromiss zwischen Sozial- und Umweltinformationen erklären. Im letzten Teil der Arbeit quantifiziere ich die kollektive Informationsverarbeitung im Feld. Das Studiensystem ist eine an sulfidische Wasserbedingungen angepasste Fischart mit einem kollektiven Fluchtverhalten vor Vögeln (wiederholte kollektive Fluchttauchgängen). Die Fische sind etwa 2 Zentimeter groß, aber die kollektive Welle breitet sich über Meter in dichten Schwärmen an der Oberfläche aus. Es zeigt sich, dass die Wellengeschwindigkeit schwach mit der Polarisation zunimmt, bei einer optimalen Dichte am schnellsten ist und von ihrer Richtung relativ zur Schwarmorientierung abhängt. / In the first part, I focus on the self-organization to criticality (here an order-disorder phase transition) and investigate if evolution is a possible self-tuning mechanism. Does a simulated cohesive swarm that tries to avoid a pursuing predator self-tunes itself by evolution to the critical point to optimize avoidance? It turns out that (i) the best group avoidance is at criticality but (ii) not due to an enhanced response but because of structural changes (fundamentally linked to criticality), (iii) the group optimum is not an evolutionary stable state, in fact (iv) it is an evolutionary accelerator due to a maximal spatial self-sorting of individuals causing spatial selection. In the second part, I model experimentally observed differences in collective behavior of fish groups subject to multiple generation of different types of size-dependent selection. The real world analog to this experimental evolution is recreational fishery (small fish are released, large are consumed) and commercial fishing with large net widths (small/young individuals can escape). The results suggest that large harvesting reduces cohesion and risk taking of individuals. I show that both findings can be mechanistically explained based on an attention trade-off between social and environmental information. Furthermore, I numerically analyze how differently size-harvested groups perform in a natural predator and fishing scenario. In the last part of the thesis, I quantify the collective information processing in the field. The study system is a fish species adapted to sulfidic water conditions with a collective escape behavior from aerial predators which manifests in repeated collective escape dives. These fish measure about 2 centimeters, but the collective wave spreads across meters in dense shoals at the surface. I find that wave speed increases weakly with polarization, is fastest at an optimal density and depends on its direction relative to shoal orientation.