Operating System Contribution to Composable Timing Behaviour in High-Integrity Real-Time Systems

The development of High-Integrity Real-Time Systems has a high footprint in terms of human, material and schedule costs. Factoring functional, reusable logic in the application favors incremental development and contains costs. Yet, achieving incrementality in the timing behavior is a much harder problem. Complex features at all levels of the execution stack, aimed to boost average-case performance, exhibit timing behavior highly dependent on execution history, which wrecks time composability and incrementaility with it. Our goal here is to restitute time composability to the execution stack, working bottom up across it. We first characterize time composability without making assumptions on the system architecture or the software deployment to it. Later, we focus on the role played by the real-time operating system in our pursuit. Initially we consider single-core processors and, becoming less permissive on the admissible hardware features, we devise solutions that restore a convincing degree of time composability. To show what can be done for real, we developed TiCOS, an ARINC-compliant kernel, and re-designed ORK+, a kernel for Ada Ravenscar runtimes. In that work, we added support for limited-preemption to ORK+, an absolute premiere in the landscape of real-word kernels. Our implementation allows resource sharing to co-exist with limited-preemptive scheduling, which extends state of the art. We then turn our attention to multicore architectures, first considering partitioned systems, for which we achieve results close to those obtained for single-core processors. Subsequently, we shy away from the over-provision of those systems and consider less restrictive uses of homogeneous multiprocessors, where the scheduling algorithm is key to high schedulable utilization. To that end we single out RUN, a promising baseline, and extend it to SPRINT, which supports sporadic task sets, hence matches real-world industrial needs better. To corroborate our results we present findings from real-world case studies from avionic industry.

Motorisches Lernen in Drosophila melanogaster

In der vorliegenden Arbeit wurden die durch Training induzierten motorischen Gedächtnisleistungen der Taufliege Drosophila melanogaster beim Überklettern von acht symmetrisch verteilten Lücken auf einem rotierenden Ring untersucht. Durch den auf sie einwirkenden optischen Fluss der vorbeiziehenden äußeren Umgebung wurden die Fliegen angeregt, diesem optomotorischen Reiz entgegenzuwirken und die Lücken laufend zu überqueren. Durch Training verbessert und langfristig gelernt wird die kompensatorische Lückenüberquerung X+ gegen die Rotation. In der aus diesem Training erhaltenen Lernkurve war eine überdurchschnittlich hohe Leistungsverbesserung nach einem einzigen Trainingslauf mit einem zeitlichen Bestand von ca. 40 Minuten abzulesen, um danach vom motorischen Gedächtnisspeicher trainierter Fliegen nicht mehr abgerufen werden zu können. Nach einer Ruhephase von einem bis mehreren Tagen wurden die Fliegen auf mögliche Langzeitlernleistungen untersucht und diese für verschiedene Intervalle nachgewiesen. Sowohl die Leistungsverbesserung während des Trainings, als auch der Lerneffekt nach 24h bleiben in mutanten rutabaga2080 sowie rut1 Fliegen aus. Betroffen ist das Gen der Adenylylzyklase I, ein Schlüsselprotein der cAMP-Signalkaskade, die u.a. im olfaktorischen und visuellen Lernen gebraucht wird. Damit ergab sich die Möglichkeit die motorischen Gedächtnisformen durch partielle Rettung zu kartieren. Die motorische Gedächtniskonsolidierung ist schlafabhängig. Wie sich herausstellte, benötigen WTB Fliegen nur eine Dunkelphase von 10h zwischen einem ersten Trainingslauf und einem Testlauf um signifikante Leistungssteigerungen zu erzielen. In weiterführenden Versuchen wurden die Fliegen nachts sowie tagsüber mit einer LED-Lampe oder in einer Dunkelkammer, mit einem Kreisschüttler oder einer Laborwippe depriviert, mit dem Ergebnis, dass nur jene Fliegen ihre Leistung signifikant gegenüber einem ersten Trainingslauf verbessern konnten, welche entweder ausschließlich der Dunkelheit ausgesetzt waren oder welchen die Möglichkeit gegeben wurde, ein Gedächtnis zunächst in einer natürlichen Schlafphase zu konsolidieren (21Uhr bis 7Uhr MEZ). In weiteren Experimenten wurden die experimentellen Bedingungen entweder während des Trainings oder des Tests auf eine Fliege und damit verbunden auf eine erst durch das Training mögliche motorische Gedächtniskonsolidierung einwirken zu können, untersucht. Dazu wurden die Experimentparameter Lückenweite, Rotationsrichtung des Lückenringes, Geschwindigkeit des Lückenringes sowie die Verteilung der acht Lücken auf dem Ring (symmetrisch, asymmetrisch) im Training oder beim Gedächtnisabruf im Testlauf verändert. Aus den Ergebnissen kann geschlussfolgert werden, dass die Lückenweite langzeitkonsolidiert wird, die Rotationsrichtung kurzzeitig abgespeichert wird und die Drehgeschwindigkeit motivierend auf die Fliegen wirkt. Die symmetrische Verteilung der Lücken auf dem Ring dient der Langzeitkonsolidierung und ist als Trainingseingang von hoher Wichtigkeit. Mit Hilfe verschiedener Paradigmen konnten die Leistungsverbesserungen der Fliegen bei Abruf eines Kurz- bzw. Langzeitgedächtnisses hochauflösend betrachtet werden (Transfer). Die Konzentration, mit der eine WTB Fliege eine motorische Aufgabe - die Überquerung von Lücken entgegengesetzt der Rotationsrichtung - durchführt, konnte mit Hilfe von Distraktoreizen bestimmt werden. Wie sich herausstellte, haben Distraktoren einen Einfluss auf die Erfolgsquote einer Überquerung, d.h. mit zunehmender Distraktionsstärke nahm die Wahrscheinlichkeit einer Lückenüberquerung ab. Die Ablenkungsreize wirkten sich weiterhin auf die Vermessung einer Lücke aus, in dem entweder "peering"-artigen Bewegungen im Training durchgeführt wurden oder je nach Reizstärke ausschließlich nur jene Lücken vermessen wurden, welche auch überquert werden sollten.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Dynamic distance analysis : new geometric data structures and algorithms for the real-time calculation of tolerance violating regions in the digital mockup process

In vielen Industriezweigen, zum Beispiel in der Automobilindustrie, werden Digitale Versuchsmodelle (Digital MockUps) eingesetzt, um die Konstruktion und die Funktion eines Produkts am virtuellen Prototypen zu überprüfen. Ein Anwendungsfall ist dabei die Überprüfung von Sicherheitsabständen einzelner Bauteile, die sogenannte Abstandsanalyse. Ingenieure ermitteln dabei für bestimmte Bauteile, ob diese in ihrer Ruhelage sowie während einer Bewegung einen vorgegeben Sicherheitsabstand zu den umgebenden Bauteilen einhalten. Unterschreiten Bauteile den Sicherheitsabstand, so muss deren Form oder Lage verändert werden. Dazu ist es wichtig, die Bereiche der Bauteile, welche den Sicherhabstand verletzen, genau zu kennen. rnrnIn dieser Arbeit präsentieren wir eine Lösung zur Echtzeitberechnung aller den Sicherheitsabstand unterschreitenden Bereiche zwischen zwei geometrischen Objekten. Die Objekte sind dabei jeweils als Menge von Primitiven (z.B. Dreiecken) gegeben. Für jeden Zeitpunkt, in dem eine Transformation auf eines der Objekte angewendet wird, berechnen wir die Menge aller den Sicherheitsabstand unterschreitenden Primitive und bezeichnen diese als die Menge aller toleranzverletzenden Primitive. Wir präsentieren in dieser Arbeit eine ganzheitliche Lösung, welche sich in die folgenden drei großen Themengebiete unterteilen lässt.rnrnIm ersten Teil dieser Arbeit untersuchen wir Algorithmen, die für zwei Dreiecke überprüfen, ob diese toleranzverletzend sind. Hierfür präsentieren wir verschiedene Ansätze für Dreiecks-Dreiecks Toleranztests und zeigen, dass spezielle Toleranztests deutlich performanter sind als bisher verwendete Abstandsberechnungen. Im Fokus unserer Arbeit steht dabei die Entwicklung eines neuartigen Toleranztests, welcher im Dualraum arbeitet. In all unseren Benchmarks zur Berechnung aller toleranzverletzenden Primitive beweist sich unser Ansatz im dualen Raum immer als der Performanteste.rnrnDer zweite Teil dieser Arbeit befasst sich mit Datenstrukturen und Algorithmen zur Echtzeitberechnung aller toleranzverletzenden Primitive zwischen zwei geometrischen Objekten. Wir entwickeln eine kombinierte Datenstruktur, die sich aus einer flachen hierarchischen Datenstruktur und mehreren Uniform Grids zusammensetzt. Um effiziente Laufzeiten zu gewährleisten ist es vor allem wichtig, den geforderten Sicherheitsabstand sinnvoll im Design der Datenstrukturen und der Anfragealgorithmen zu beachten. Wir präsentieren hierzu Lösungen, die die Menge der zu testenden Paare von Primitiven schnell bestimmen. Darüber hinaus entwickeln wir Strategien, wie Primitive als toleranzverletzend erkannt werden können, ohne einen aufwändigen Primitiv-Primitiv Toleranztest zu berechnen. In unseren Benchmarks zeigen wir, dass wir mit unseren Lösungen in der Lage sind, in Echtzeit alle toleranzverletzenden Primitive zwischen zwei komplexen geometrischen Objekten, bestehend aus jeweils vielen hunderttausend Primitiven, zu berechnen. rnrnIm dritten Teil präsentieren wir eine neuartige, speicheroptimierte Datenstruktur zur Verwaltung der Zellinhalte der zuvor verwendeten Uniform Grids. Wir bezeichnen diese Datenstruktur als Shrubs. Bisherige Ansätze zur Speicheroptimierung von Uniform Grids beziehen sich vor allem auf Hashing Methoden. Diese reduzieren aber nicht den Speicherverbrauch der Zellinhalte. In unserem Anwendungsfall haben benachbarte Zellen oft ähnliche Inhalte. Unser Ansatz ist in der Lage, den Speicherbedarf der Zellinhalte eines Uniform Grids, basierend auf den redundanten Zellinhalten, verlustlos auf ein fünftel der bisherigen Größe zu komprimieren und zur Laufzeit zu dekomprimieren.rnrnAbschießend zeigen wir, wie unsere Lösung zur Berechnung aller toleranzverletzenden Primitive Anwendung in der Praxis finden kann. Neben der reinen Abstandsanalyse zeigen wir Anwendungen für verschiedene Problemstellungen der Pfadplanung.

Studio e sviluppo di un'infrastruttura di supporto alla schedulazione di hard/soft real-time tasks in ambiente QNX.

La tesi tratta lo studio del sistema QNX e dello sviluppo di un simulatore di task hard/soft real-time, tramite uso di un meta-scheduler. Al termine dello sviluppo vengono valutate le prestazioni del sistema operativo QNX Neutrino.

Real-time adaptive models for the personalized prediction of glycemic profile in type 1 diabetes patients

Prediction of glycemic profile is an important task for both early recognition of hypoglycemia and enhancement of the control algorithms for optimization of insulin infusion rate. Adaptive models for glucose prediction and recognition of hypoglycemia based on statistical and artificial intelligence techniques are presented.

Cancer classification using the Immunoscore: a worldwide task force

Prediction of clinical outcome in cancer is usually achieved by histopathological evaluation of tissue samples obtained during surgical resection of the primary tumor. Traditional tumor staging (AJCC/UICC-TNM classification) summarizes data on tumor burden (T), presence of cancer cells in draining and regional lymph nodes (N) and evidence for metastases (M). However, it is now recognized that clinical outcome can significantly vary among patients within the same stage. The current classification provides limited prognostic information, and does not predict response to therapy. Recent literature has alluded to the importance of the host immune system in controlling tumor progression. Thus, evidence supports the notion to include immunological biomarkers, implemented as a tool for the prediction of prognosis and response to therapy. Accumulating data, collected from large cohorts of human cancers, has demonstrated the impact of immune-classification, which has a prognostic value that may add to the significance of the AJCC/UICC TNM-classification. It is therefore imperative to begin to incorporate the 'Immunoscore' into traditional classification, thus providing an essential prognostic and potentially predictive tool. Introduction of this parameter as a biomarker to classify cancers, as part of routine diagnostic and prognostic assessment of tumors, will facilitate clinical decision-making including rational stratification of patient treatment. Equally, the inherent complexity of quantitative immunohistochemistry, in conjunction with protocol variation across laboratories, analysis of different immune cell types, inconsistent region selection criteria, and variable ways to quantify immune infiltration, all underline the urgent requirement to reach assay harmonization. In an effort to promote the Immunoscore in routine clinical settings, an international task force was initiated. This review represents a follow-up of the announcement of this initiative, and of the J Transl Med. editorial from January 2012. Immunophenotyping of tumors may provide crucial novel prognostic information. The results of this international validation may result in the implementation of the Immunoscore as a new component for the classification of cancer, designated TNM-I (TNM-Immune).

Characterizing full-body reach duration across task and viewpoint modalities

The full-body control of virtual characters is a promising technique for application fields such as Virtual Prototyping. However it is important to assess to what extent the user full-body behavior is modified when immersed in a virtual environment. In the present study we have measured reach durations for two types of task (controlling a simple rigid shape vs. a virtual character) and two types of viewpoint (1st person vs. 3rd person). The paper first describes the architecture of the motion capture approach retained for the on-line full-body reach experiment. We then present reach measurement results performed in a non-virtual environment. They show that the target height parameter leads to reach duration variation of ∓25% around the average duration for the highest and lowest targets. This characteristic is highly accentuated in the virtual world as analyzed in the discussion section. In particular, the discrepancy observed for the first person viewpoint modality suggests to adopt a third person viewpoint when controling the posture of a virtual character in a virtual environment.

Effects of task modality, length and complexity on time for activities in lucid dreams

Introduction: Nocturnal dreams can be considered as a kind of simulation of the real world on a higher cognitive level (Erlacher & Schredl, 2008). Within lucid dreams, the dreamer is aware of the dream state and thus able to control the ongoing dream content. Previous studies could demonstrate that it is possible to practice motor tasks during lucid dreams and doing so improved performance while awake (Erlacher & Schredl, 2010). Even though lucid dream practice might be a promising kind of cognitive rehearsal in sports, little is known about the characteristics of actions in lucid dreams. The purpose of the present study was to explore the relationship between time in dreams and wakefulness because in an earlier study (Erlacher & Schredl, 2004) we found that performing squads took lucid dreamers 44.5 % more time than in the waking state while for counting the same participants showed no differences between dreaming and wakefulness. To find out if the task modality, the task length or the task complexity require longer times in lucid dreams than in wakefulness three experiments were conducted. Methods: In the first experiment five proficient lucid dreamers spent two to three non-consecutive nights in the sleep laboratory with polysomnographic recording to control for REM sleep and determine eye signals. Participants counted from 1-10, 1-20 and 1-30 in wakefulness and in their lucid dreams. While dreaming they marked onset of lucidity as well as beginning and end of the counting task with a Left-Right-Left-Right eye movement and reported their dreams after being awakened. The same procedure was used for the second experiment with seven lucid dreamers except that they had to walk 10, 20 or 30 steps. In the third experiment nine participants performed an exercise involving gymnastics elements such as various jumps and a roll. To control for length of the task the gymnastic exercise in the waking state lasted about the same time as walking 10 steps. Results: As a general result we found – as in the study before – that performing a task in the lucid dream requires more time than in wakefulness. This tendency was found for all three tasks. However, there was no difference for the task modality (counting vs. motor task). Also the relative time for the different lengths of the tasks showed no difference. And finally, the more complex motor task (gymnastic routine) did not require more time in lucid dreams than the simple motor task. Discussion/Conclusion: The results showed that there is a robust effect of time in lucid dreams compared to wakefulness. The three experiments could not explain that those differences are caused by task modality, task length or task complexity. Therefore further possible candidates needs to be investigated e.g. experience in lucid dreaming or psychological variables. References: Erlacher, D. & Schredl, M. (2010). Practicing a motor task in a lucid dream enhances subsequent performance: A pilot study. The Sport Psychologist, 24(2), 157-167. Erlacher, D. & Schredl, M. (2008). Do REM (lucid) dreamed and executed actions share the same neural substrate? International Journal of Dream Research, 1(1), 7-13. Erlacher, D. & Schredl, M. (2004). Time required for motor activity in lucid dreams. Perceptual and Motor Skills, 99, 1239-1242.

Children's performance estimation in mathematics and science tests over a school year: A pilot study

The metacognitve ability to accurately estimate ones performance in a test, is assumed to be of central importance for initializing task-oriented effort. In addition activating adequate problem-solving strategies, and engaging in efficient error detection and correction. Although school children's' ability to estimate their own performance has been widely investigated, this was mostly done under highly-controlled, experimental set-ups including only one single test occasion. Method: The aim of this study was to investigate this metacognitive ability in the context of real achievement tests in mathematics. Developed and applied by a teacher of a 5th grade class over the course of a school year these tests allowed the exploration of the variability of performance estimation accuracy as a function of test difficulty. Results: Mean performance estimations were generally close to actual performance with somewhat less variability compared to test performance. When grouping the children into three achievement levels, results revealed higher accuracy of performance estimations in the high achievers compared to the low and average achievers. In order to explore the generalization of these findings, analyses were also conducted for the same children's tests in their science classes revealing a very similar pattern of results compared to the domain of mathematics. Discussion and Conclusion: By and large, the present study, in a natural environment, confirmed previous laboratory findings but also offered additional insights into the generalisation and the test dependency of students' performances estimations.

Time for actions in lucid dreams: effects of task modality, length, and complexity

The relationship between time in dreams and real time has intrigued scientists for centuries. The question if actions in dreams take the same time as in wakefulness can be tested by using lucid dreams where the dreamer is able to mark time intervals with prearranged eye movements that can be objectively identified in EOG recordings. Previous research showed an equivalence of time for counting in lucid dreams and in wakefulness (LaBerge, 1985; Erlacher and Schredl, 2004), but Erlacher and Schredl (2004) found that performing squats required about 40% more time in lucid dreams than in the waking state. To find out if the task modality, the task length, or the task complexity results in prolonged times in lucid dreams, an experiment with three different conditions was conducted. In the first condition, five proficient lucid dreamers spent one to three non-consecutive nights in the sleep laboratory. Participants counted to 10, 20, and 30 in wakefulness and in their lucid dreams. Lucidity and task intervals were time stamped with left-right-left-right eye movements. The same procedure was used for these condition where eight lucid dreamers had to walk 10, 20, or 30 steps. In the third condition, eight lucid dreamers performed a gymnastics routine, which in the waking state lasted the same time as walking 10 steps. Again, we found that performing a motor task in a lucid dream requires more time than in wakefulness. Longer durations in the dream state were present for all three tasks, but significant differences were found only for the tasks with motor activity (walking and gymnastics). However, no difference was found for relative times (no disproportional time effects) and a more complex motor task did not result in more prolonged times. Longer durations in lucid dreams might be related to the lack of muscular feedback or slower neural processing during REM sleep. Future studies should explore factors that might be associated with prolonged durations.

Turning univalent stimuli bivalent: Synesthesia can cause cognitive conflict in task switching

In this study we investigated whether synesthetic color experiences have similar effects as real colors in cognitive conflict adaptation. We tested 24 synesthetes and two yoke-matched control groups in a task-switching experiment that involved regular switches between three simple decision tasks (a color decision, a form decision, and a size decision). In most of the trials the stimuli were univalent, that is, specific for each task. However, occasionally, black graphemes were presented for the size decisions and we tested whether they would trigger synesthetic color experiences and thus, turn them into bivalent stimuli. The results confirmed this expectation. We were also interested in their effect for subsequent performance (i.e., the bivalency effect). The results showed that for synesthetic colors the bivalency effect was not as pronounced as for real colors. The latter result may be related to differences between synesthetes and controls in coping with color conflict.

Prioritizing – the task strategy of the powerful?

Previous research has shown that power increases focus on the main goal when distractor information is present. As a result, high-power people have been described as goal-focused. In real life, one typically wants to pursue multiple goals at the same time. There is a lack of research on how power affects how people deal with situations in which multiple important goals are present. To address this question, 158 participants were primed with high or low power or assigned to a control condition, and were asked to perform a dual-goal task with three difficulty levels. We hypothesized and found that high-power primed people prioritize when confronted with a multiple-goal situation. More specifically, when task demands were relatively low, power had no effect; participants generally pursued multiple goals in parallel. However, when task demands were high, the participants in the high-power condition focused on a single goal whereas participants in the low-power condition continued using a dual-task strategy. This study extends existing power theories and research in the domain of goal pursuit.

Ego depletion and persistent performance in a cycling task

We tested the assumption that persistent performance in an exhausting indoor cycling task would depend on momentarily available self-control strength (N = 20 active participants). In a within-subjects design (two points of measurement, exactly seven days apart), participants’ self-control strength was experimentally manipulated (depletion: yes vs. no; order counterbalanced) via the Stroop test before the participants performed a cycling task. In line with our hypothesis, hierarchical linear modelling (HLM) revealed that participants consistently performed worse over a period of 18 minutes when they were ego depleted. In addition, HLM analysis revealed that depleted participants invested less effort in the cycling task, as indicated by their lower heart rate. This effect escalated over time, as indicated by a time × condition interaction. These results indicate that self-control strength is necessary to obtain an optimal level of performance in endurance tasks requiring high levels of persistence. Practical implications are discussed.

The distinction between real and fictional worlds: Investigating individual differences in fantasy understanding

In this paper, two studies are reported in which children’s ability to distinguish reality from fantasy was investigated. In Experiment 1, children of different ages made pairwise comparisons of 12 pictures of fictional figures and 3 photographs of real people by evaluating on a 6-point scale how easily these figures could meet each other. The results revealed that fantasy/reality distinction develops with age: 7–8-year-old showed a fundamental categorical distinction (comparable to that of adults) whereas 3–4-year-old treated the real world like one of many worlds. In Experiment 2, we took an individual differences approach and tested 116 4–5-year-old who performed the same fantasy task. In addition, they were presented with theory-of-mind tasks and tests measuring non-verbal intelligence and language skills. The results showed that, after statistically controlling for age, non-verbal intelligence, and language skills, theory-of-mind abilities still significantly contributed to the prediction of fantasy understanding.