La conception des plateformes aéronautiques s’effectue en tenant compte des aspects fonctionnels et dysfonctionnels prévus dans les scénarios d’emploi des aéronefs qui les embarquent. Ces plateformes aéronautiques sont composées de systèmes informatiques temps réel qui doivent à la fois être précises dans leurs calculs, exactes dans l’instant de délivrance des résultats des calculs, et robustes à tout évènement pouvant compromettre le bon fonctionnement de la plateforme.Dans ce contexte, ces travaux de thèse abordent les ordonnancements temps réel tolérants aux fautes. Partant du fait que les systèmes informatiques embarqués sont perturbés par les ondes électromagnétiques des radars, notamment dans la phase d’approche des aéronefs, ces travaux proposent une modélisation des effets des ondes, dite en rafales de fautes. Après avoir exploré le comportement de l’ordonnanceur à la détection d’erreurs au sein d’une tâche, une technique de validation, reposant sur le calcul de pire temps de réponse des tâches, est présentée. Il devient alors possible d’effectuer des analyses d’ordonnançabilité sous l’hypothèse de la présence de rafales de fautes. Ainsi, cette technique de validation permet de conclure sur la faisabilité d’un ensemble de tâches en tenant compte de la durée de la rafale de fautes et de la stratégie de gestion des erreurs détectées dans les tâches.Sur la base de ces résultats, les travaux décrits montre comment envisager l’analyse au niveau système. L’idée sous-jacente est de mettre en évidence le rôle des ordonnancements temps réel tolérants aux fautes dans la gestion des données erronées causées par des perturbations extérieures au système.Ainsi, le comportement de chaque équipement est modélisé, ainsi que les flots de données échangés et la dynamique du système. Le comportement de chaque équipement est fonction de la perturbation subie, et donne lieu à l’établissement de la perturbation résultante, véritable réponse dysfonctionnelle de l’équipement à une agression extérieure. / The design of avionic platforms takes into account the functional and dysfunctional aspects, which depend on the aircraft operation concept. These avionic platforms embed computer resources that must produce accurate results at the right time, and must be dependable whatever the disturbance.In this specific context, we address the topic of fault tolerant real time scheduling. Since the embedded computer resources are disturbed by electromagnetic waves produced by radar, especially during the aircraft approach, we suggest a model of these wave effects named fault bursts. Afterthe analysis of scheduler behaviour when an error is dectected inside a task, we present a validation technique based on the evaluation of the worst case response time. By this way, we are able to study the task set feasibility under fault burst assumption and according to the error recovery strategy.Then, based on these results, we show a way to analyse the effects of disturbances such as electromagnetic waves at system level. The underlining idea is to demonstrate the main role of fault tolerant real time scheduler in the management of erroneous data. To do that, we suggest an equipment model which integrates the behaviour of the equipement when a disturbance occurs. We also describe thedata flows in order to describe the avionics platform dynamics.

Orientador: Rubens Maciel Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Química / Made available in DSpace on 2018-08-19T04:22:50Z (GMT). No. of bitstreams: 1 Goncalves_EncarnacaodeLourdesBassoliAndreo_D.pdf: 4732830 bytes, checksum: 01a1b5e8274e002cb44c8ed8cd836b0a (MD5) Previous issue date: 2011 / Resumo: As usinas de produção de Etanol estão apresentando necessidades relacionadas ao aumento de produtividade com redução de custos. O processo de produção de etanol necessita de ações que resolvam problemas da automação, tais como variabilidade das malhas de controle, longo tempo de operação de sistema de controle em modo manual. Apresentam problemas de sinergia entre as áreas do processo produtivo, demora na tomada de decisão e dificuldade para definir a ação a ser tomada para solução do problema. Motivados por estes fatores e com a tecnologia de informação e da automação disponível atualmente no mercado, desenvolveu-se um modelo de processo, baseado em variáveis, com origem em diversas fontes (área agrícola, automação, administrativa, industrial), efetuando integrações destas variáveis em uma única base de dados, produção de regras de negócio com alarmes e instruções para tomada de decisões de correção ou mudança do processo produtivo. Este modelo usa os softwares ERP (Enterprise Resource Planning), transacionais, MES (Manufacturing Execution Systems) e automação industrial. Este trabalho apresenta uma revisão bibliográfica com as principais definições necessárias para o desenvolvimento e entendimento do modelo, tais como descrição dos softwares, descrição do processo de automação e descrição do processo produtivo de etanol. Apresenta o modelo proposto e um estudo de caso, onde o modelo foi aplicado em uma unidade produtora de etanol / Abstract: The ethanol production plants are experiencing needs related to increasing productivity while reducing costs. The ethanol production process requires actions that address problems of automation, such as variability of the control loops, long time of operation control system in manual mode. This process has problems of synergy between the areas of the production, delay in decision making and difficulty in defining the action to be taken to solve the problems. Motivated by these factors and the information technology and automation available today, a process model has been developed based on variables, originating from various sources (agricultural area, automation, administrative, industrial), performing integrations of these variables in a single database, production of business rules with alarms and instructions for making decisions to correct or change the production process. This model, use the software ERP (Enterprise Resource Planning), transactional, MES (Manufacturing Execution Systems) and industrial automation. This paper presents a literature review with the main definitions needed for the development and understanding of the model, such as descriptions of the software, description of the automation process and description of the ethanol production process. Presents the proposed model and a case study, where the model was applied in an ethanol production unit / Doutorado / Desenvolvimento de Processos Químicos / Doutor em Engenharia Química

As an increasing position of the world’s communication moves towards the cloud and wireless solutions the requirement for good throughput and low delay increases. One step towards meeting higher requirements is the move from 4G Long Term Evolution (LTE) to 5G New Radio (NR). In order to utilize the potential of 5G NR, software needs to be improved. With the goal to lower the delay for delay critical applications and services when using 5G NR this thesis studies a new scheduler inspired by Earliest Deadline First (EDF) as a soft real-time system scheduler. This new scheduler called Real-Time Inspired Hybrid Scheduler (RTIHS) is proposed where two different schedulers are used depending on if the network traffic is delay critical or not. Delay critical traffic is served by the new Deadline Inspired Scheduler (DIS) scheduler and other traffic by a traditional Round Robin (RR) scheduler. The transmissions that are delay critical are prioritized differently with the use of a constant that has two functions. To determine if the transmission is in time or not, and how close the transmission is to the fixed deadline. Up until the deadline the priority of that transmission is increased with a factor that is affected by how close the current time is to the deadline. If the deadline has been missed the priority is, however, decreased with respect to how much it missed the deadline.RTIHS is implemented and tested in a state-of-the-art system simulator where services such as;Cloud Gaming (CG), Video on Demand (VoD), and web browsing are evaluated. An already existing technology named Low Latency Low Loss Scalable Throughput (L4S) is included in the evaluations to investigate how RTIHS scales. The performance of RTIHS is then compared to a Delay Scheduler(DS) and a RR scheduler that act as the baseline. The results show that RTIHS performs better for CG in terms of delay and nominal rate than the baseline, especially when the network is under high load. Using RTIHS compared to a DS shows an average increase of nominal rate by roughly 6 % and an average decrease of delay by 16 % for the average users. At the same time RTIHS does show higher delay and lower throughput for services such as VoD and web browsing, making its performance for those service worse than the baseline, especially when the network load is high. With the same comparison as before, RTIHS shows an average 17 % higher delay for web browsing and 1 % lower requested video rate than the DS for the average users. This is due to how the evaluated services are prioritized with the limited resources available. Since RTIHS prioritizes CG more, less resources remain for the other services. The baseline is not as biased towards CG and therefore has a lower nominal rate and higher delay for said service but better for the other services in comparison. Activating L4S mitigates the underwhelming performance of RTIHS for VoD and web browsing further improves the performance for CG. This is also true for the baseline which increases performance for CG and further increases the performance for other services with a small amount. With L4S activated the average increase of nominal rate in CG for RTIHS compared to the DS is 13 % for the average users and the average delay decrease is 9 %. Meanwhile the average requested video rate for RTIHS is less than 1 % lower than that of the DS for the average users and the delay for web browsing is 10 % higher than the DS for the average users.

This dissertation first presents an uniprocessor real-time scheduling algorithm called the Generic Benefit Scheduling algorithm (or GBS). GBS solves a previously open real-time scheduling problem: scheduling activities subject to arbitrarily shaped, time/utility function (TUF) time constraints and mutual exclusion resource constraints. A TUF specifies the utility of completing an application activity as an application- or situation-specific function of when that activity completes. GBS considers the scheduling objective of maximizing system-wide, total accrued utility, while respecting mutual exclusion constraints. Since this problem is NP-hard, GBS heuristically computes schedules in polynomial-time. The performance of the GBS algorithm is evaluated through simulation and through an implementation on a Portable Operating System Interface (POSIX)-compliant real-time operating system. The simulation studies and implementation measurements reveal that GBS performs close to, if not better than existing algorithms for the cases that they apply. Further, the results verify the effectiveness of GBS for its unique model. We also analytically establish timeliness and non-timeliness properties of GBS including bounds on activity utilities and mutual exclusion. GBS targets real-time systems that are subject to significant non-determinism inherent in their operating environments e.g., completely unknown activity arrivals. When system uncertainties can be stochastically characterized (e.g., stochastic activity arrivals and execution times), it is possible to provide stochastic assurances on timeliness behavior. The dissertation also presents algorithmic solutions to fundamental assurance problems in TUF-driven real-time systems, including stochastically satisfying individual, activity utility lower bounds and system-wide, total utility lower bounds. The algorithmic solutions include algorithms for processor bandwidth allocation and TUF scheduling. While bandwidth allocation algorithms allocate processor bandwidth share to activities to satisfy utility lower bounds, TUF scheduling algorithms schedule activities to maximize accrued utility. The algorithmic solutions and analysis are extended with a class of lock-free and lock-based resource access protocols to satisfy mutual exclusion constraints. We show that satisfying utility lower bounds with lock-based resource access protocols does not imply doing so with the lock-free scheme, and vice versa. Finally, the dissertation presents a rule-based framework for trading off assurance requirements on utility lower bound satisfaction. / Ph. D.

Recently there has been a growing interest in the use of Low Rate Wireless Personal Area Networks (LR-WPAN) [1] driven by the large number of emerging applications such as home automation, health-care monitoring and environmental surveillance. To fulfill the needs for these emerging applications, IEEE has created a new standard called IEEE 802.15.4 for LR-WPAN, which has been widely accepted as the de facto standard for wireless sensor networks. Unlike IEEE 802.11 [2], which was designed for Wireless Local Area Networks (WLAN), it focuses on short range wireless communications. The goal of the IEEE 802.15.4 LR-WPAN is to support low data rate connectivity among wireless sensors with low complexity, cost and power consumption [3]. It specifies two types of network topologies, which are the beacon-enabled start network and the nonbeacon-enabled peer-to-peer network. For the beacon-enabled network, it defines the Guaranteed Time Slot (GTS) to provide real-time guaranteed service for delay-sensitive applications. In the nonbeacon-enabled network the GTS is reserved time slots such that it is requested, allocated and scheduled to wireless sensors that need guaranteed service for delay-sensitive applications. Existing GTS scheduling algorithms include First-Come-First-Served (FCFS) [1], priority-based [4] and Earliest Deadline First (EDF) [5] methods. Such FCFS and priority-based scheduling methods have critical drawbacks in achieving real-time guarantees. Namely, they fail to satisfy the delay constraints of delay-sensitive transactions. Further, they lead to GTS scarcity and GTS underutilization. On the other hand, the EDF-based scheduling method provides delay guarantee while it does not support delay-sensitive applications where arrival of the first packet has a critical impact on the performance. To solve these problems, we design the optimal work-conserving GTS Allocation and Scheduling (GAS) algorithm that provides guarantee service for delay-sensitive applications in beacon-enabled networks. Not only does the GAS satisfy the delay constraints of transactions, but also it reduces GTS scarcity and GTS underutilization. Further, it supports delay-sensitive applications where arrival of the first packet has a critical impact on the performance. Through the extensive simulation results, we show that the proposed algorithm outperforms the existing scheduling methods. Our algorithm differs from the existing ones in that it is an on-line scheduling and allocation algorithm and allows transmissions of bursty and periodic transactions with delay constraints even when the network is overloaded. In the nonbeacon-enabled peer-to-peer network some operating scenarios for rate-sensitive applications arise when one considers wireless video surveillance and target detection applications for wireless sensor networks. To support such rate-sensitive applications in wireless sensor networks, we present a Multirate-based Service Differentiation (MSD) operating in the nonbeacon-enabled peer-to-peer network. Unlike existing priority-based service differentiation models, the MSD defines the independent Virtual Medium Access Controls (VMACs), each of which consists of a transmission queue and the Adaptive Backoff Window Control (ABWC). Since the VMACs serve multiple rate-sensitive flows, it is possible that more than one data frame is collided with each other when their backoff times expire simultaneously. To solve such a virtual collision in the virtual collision domain, we design the Virtual Collision Avoidance Control (VCAC). The ABWC component adjusts the backoff window to reflect the local network state in the local collision domain. The VCAC component prevents virtual collisions and preempts packets with the minimal cost in the virtual collision domain. By analyzing these algorithms, we prove that the ABWC component enables the achieved data rate to converge to the rate requirement and the VCAC component produces a virtual-collision-free schedule to avoid degradation of the achieved data rate. Through the simulation, we validate our analysis and show the MSD outperforms existing algorithms. / Ph. D.

In this dissertation, we consider the problem of scheduling and synchronization of distributable real-time threads --- Real-Time CORBA's first-class abstraction for programming real-time, multi-node sequential behaviors. Distributable real-time threads can be scheduled, broadly, using two paradigms: node independent scheduling, in which nodes independently construct thread schedules, based on node-level decomposition of distributable thread (or DT) scheduling parameters, and collaborative scheduling, in which nodes collaborate to construct system-wide thread schedules, which may or may not involve scheduling parameter decomposition. While significant literature exists on node independent scheduling, little is known about collaborative scheduling and its concomitant tradeoffs. We design three collaborative scheduling algorithms, called ACUA, QBUA, and DQBUA. ACUA uses theory of consensus and QBUA uses theory of quorums for distributable thread schedule construction. DQBUA extends QBUA with lock-based, local and distributed concurrency control. The algorithms consider a model where distributable threads arrive arbitrarily, have time/utility function time constraints, access resources in an arbitrary way (e.g., arbitrary lock acquire/release order, arbitrary nestings), and are subject to arbitrary node crash failures and message losses. We analytically establish several properties of the algorithms including probabilistic end-to-end termination time satisfactions, timeliness optimality during underloads, bounded exception handling time, and correctness of the algorithms in partially synchronous systems. We implement distributable real-time threads in the Linux kernel as a first-class programming and scheduling abstraction. The resulting kernel, called ChronOS, provides application interfaces for creating and manipulating distributable threads, as well as kernel interfaces and mechanisms for scheduling them (using both independent and collaborative approaches). ChronOS also has failure detector mechanisms for detecting and recovering from distributable thread failures. We implement the proposed scheduling algorithms and their competitors in ChronOS and compare their behavior. Our studies reveal that the collaborative scheduling algorithms are superior to independent scheduling algorithms for certain thread sets, in particular, when thread sections have significantly varying execution time. This variability, especially if the variability is not consistent among the threads, may cause each node to make conflicting decisions in the absence of global information. We observe that collaborative schedulers outperform independent schedulers (e.g., EDF augmented with PIP) in terms of accrued utility by as much as 75%. We identify distributed dependencies as one of the major sources of overhead in collaborative scheduling. In particular, the cost of distributed lock-based concurrency control (e.g., lock management, distributed deadlock detection/resolution) can significantly reduce the problem space for which collaborative scheduling is beneficial. To mitigate this, we consider the use of software transactional memory (or STM), an optimistic, non-blocking synchronization alternative to lock-based concurrency control which has been extensively studied in non real-time contexts. We consider distributable real-time threads with STM concurrency control, and develop techniques for analyzing and bounding their end-to-end response times on distributed single-processor and distributed multiprocessor systems. We also develop contention management techniques, a key component of STM, which are driven by threads' real-time scheduling parameters, and establish their tradeoffs against non-real-time contention managers. / Ph. D.

We consider the problem of scheduling real-time tasks on a multiprocessor system. Our primary focus is scheduling on multiprocessor systems where the total task utilization demand, U, is greater than m, the number of processors on a multiprocessor system---i.e., the total available processing capacity of the system. When U > m, the system is said to be overloaded; otherwise, the system is said to be underloaded. While significant literature exists on multiprocessor real-time scheduling during underloads, little is known about scheduling during overloads, in particular, in the presence of task dependencies---e.g., due to synchronization constraints. We consider real-time tasks that are subject to time/utility function (or TUF) time constraints, which allow task urgency to be expressed independently of task importance---e.g., the most urgent task being the least important. The urgency/importance decoupling allowed by TUFs is especially important during overloads, when not all tasks can be optimally completed. We consider the timeliness optimization objective of maximizing the total accrued utility and the number of deadlines satisfied during overloads, while ensuring task mutual exclusion constraints and freedom from deadlocks. This problem is NP-hard. We develop a class of polynomial-time heuristic algorithms, called the Global Utility Accrual (or GUA) class of algorithms. The algorithms construct a directed acyclic graph representation of the task dependency relationship, and build a global multiprocessor schedule of the zero in-degree tasks to heuristically maximize the total accrued utility and ensure mutual exclusion. Potential deadlocks are detected through a cycle-detection algorithm, and resolved by aborting a task in the deadlock cycle. The GUA class of algorithms include two algorithms, namely, the Non-Greedy Global Utility Accrual (or NG-GUA) and Greedy Global Utility Accrual (or G-GUA) algorithms. NG-GUA and G-GUA differ in the way schedules are constructed towards meeting all task deadlines, when possible to do so. We establish several properties of the algorithms including conditions under which all task deadlines are met, satisfaction of mutual exclusion constraints, and deadlock-freedom. We create a Linux-based real-time kernel called ChronOS for multiprocessors. ChronOS is extended from the PREEMPT_RT real-time Linux patch, which provides optimized interrupt service latencies and real-time locking primitives. ChronOS provides a scheduling framework for the implementation of a broad range of real-time scheduling algorithms, including utility accrual, non-utility accrual, global, and partitioned scheduling algorithms. We implement the GUA class of algorithms and their competitors in ChronOS and conduct experimental studies. The competitors include G-EDF, G-NP-EDF, G-FIFO, gMUA, P-EDF and P-DASA. Our study reveals that the GUA class of algorithms accrue higher utility and satisfy greater number of deadlines than the deadline-based scheduling algorithms by as much as 750% and 600%, respectively. In addition, we observe that G-GUA accrues higher utility than NG-GUA during overloads by as much as 25% while NG-GUA satisfies greater number of deadlines than G-GUA by as much as 5% during underloads. / Master of Science

Today, many embedded or cyber-physical systems, e.g., in the automotive domain, comprise several control applications, sharing the same platform. It is well known that such resource sharing leads to complex temporal behaviors that degrades the quality of control, and more importantly, may even jeopardize stability in the worst case, if not properly taken into account. In this thesis, we consider embedded control or cyber-physical systems, where several control applications share the same processing unit. The focus is on the control-scheduling co-design problem, where the controller and scheduling parameters are jointly optimized. The fundamental difference between control applications and traditional embedded applications motivates the need for novel methodologies for the design and optimization of embedded control systems. This thesis is one more step towards correct design and optimization of embedded control systems. Offline and online methodologies for embedded control systems are covered in this thesis. The importance of considering both the expected control performance and stability is discussed and a control-scheduling co-design methodology is proposed to optimize control performance while guaranteeing stability. Orthogonal to this, bandwidth-efficient stabilizing control servers are proposed, which support compositionality, isolation, and resource-efficiency in design and co-design. Finally, we extend the scope of the proposed approach to non-periodic control schemes and address the challenges in sharing the platform with self-triggered controllers. In addition to offline methodologies, a novel online scheduling policy to stabilize control applications is proposed.

The present work studies methods of scheduling in heterogeneous distributed systems. First there are introduced some theoretical basics which contain not only the scheduling theory itself but also the graph theory and the computational complexity theory. After that, compile-time scheduling methods and some well-known algorithms solving the problem are presented, followed by real-time scheduling basics and by classification of used methods. In the main part of the work there are proposed algorithms which respect additional restrictions. These algorithms are tested via the enclosed application and compared either to each other or to another algorithms which mostly don't respect additional restrictions. The mentioned application and the documentation for this application are a part of this work as well.

La migration récente des plateformes mono-cœur vers multi-cœur, dans le domaine automobile, révèle de grands changements dans le processus de développement du logiciel embarqué. Tout d’abord, les concepteurs de logiciel ont besoin de nouvelles méthodes leur permettant de combler le fossé entre la description des applications (versus Autosar) et le déploiement de tâches. Deuxièmement, l’utilisation du multi-cœur doit assurer la compatibilité avec les contraintes liées aux aspects temps-réel et à la Sûreté de fonctionnement. Au final, les développeurs ont besoins d’outils pour intégrer de nouveaux modules dans leur système multi-cœur. Confronter aux complexités ci-dessus, nous avons proposé une méthodologie afin de repartir, de manière optimale, les applications sous forme de partitions logiques. Nous avons ainsi intégré dans notre processus de développement, un outil de distribution des traitements d’un système embarqué sur différents processeurs et compatible avec le standard AUTOSAR (AUTomotive Open System ARchitecture). Les solutions de partitionnement traitent simultanément l’allocation des applications ainsi que la politique d’ordonnancement. Le périmètre d’étude du partitionnement est automatique, les solutions trouvées étant évaluées par nos fonctions de coût. Elles prennent aussi en compte des critères tels que, le coût de communication inter-cœur, l’équilibrage de la charge CPU entre les cœurs et la gigue globale. Pour la partie ordonnancement, nous présentons une formalisation des dépendances sous forme périodiques pour répondre au besoin automobile. L’algorithme d’ordonnancement proposé prend en compte cette spécificité ainsi que les contraintes temps-réel et fonctionnelles, assurant l’applicabilité de notre méthodologie dans un produit industriel. Nous avons expérimenté nos solutions avec une application de type contrôle moteur, sur une plateforme matérielle multi-cœur. / The recent migration from single-core to multi-core platforms in the automotive domain reveals great challenges for the legacy embedded software design flow. First of all, software designers need new methods to fill the gap between applications description and tasks deployment. Secondly, the use of multiple cores has also to remain compatible with real-time and safety design constraints. Finally, developers need tools to assist them in the new steps of the design process. Face to these issues, we proposed a method integrated in the AUTOSAR (AUTomotive Open System ARchitecture) design flow for partitioning the automotive applications onto multi-core systems. The method proposes the partitions solution that contains allocation of application as well as scheduling policy simultaneously. The design space of the partitioning is explored automatically and the solutions are evaluated thanks to our proposed objective functions that consider certain criteria such as communication overhead and global jitters. For the scheduling part, we present a formalization of periodic dependencies adapted to this automotive framework and propose a scheduling algorithm taking into account this specificity. Our defined constraints from real-time aspect as well as functional aspect make sure the applicability of our method on the real life user case. We leaded experiments with a complex and real world control application onto a concrete multi-core platform.