<p>An event monitor is a part of a real-time system that can be used to</p><p>check if the system follows the specifications posed on its behavior. This dissertation covers an approach to event monitoring where such specifications (represented by time constraints) are represented by graphs.</p><p>Not much work has previously been done on designing and implementing constraint graph-based event monitors. In this work, we focus on presenting an extensible design for such an event monitor. We also evaluate different data structure types (linked lists, dynamic arrays, and static arrays) that can be used for representing the constraint graphs internally. This is done by creating an event monitor implementation, and conducting a number of benchmarks where the time used by the monitor is measured.</p><p>The result is presented in the form of a design specification and a summary of the benchmark results. Dynamic arrays are found to be the generally most efficient, but advantages and disadvantages of all the data structure types are discussed.</p>

No description available.

- / -

Τα τελευταία χρόνια τα ενσωματωμένα συστήματα πραγματικού χρόνου χρησιμοποιούνται σε ολοένα μεγαλύτερη γκάμα εφαρμογών. Κινητά τηλέφωνα, συσκευές αναπαραγωγής ψηφιακών δίσκων, εκτυπωτές, ψηφιακές φωτογραφικές μηχανές, αποτελούν λίγα παραδείγματα συσκευών που χρησιμοποιούν την τεχνολογία των ενσωματωμένων συστημάτων. Στην παρούσα διπλωματική εργασία ερευνήθηκαν οι δυνατότητες αξιοποίησης του Real-Time Linux σε ενσωματωμένα συστήματα. Μελετήθηκε διεξοδικά ο πυρήνας του λειτουργικού συστήματος Linux και ο αλγόριθμος χρονοδρομολόγησης που χρησιμοποιεί. Αναζητήθηκαν τρόποι μετατροπής του Linux σε λειτουργικό σύστημα για συστήματα πραγματικού χρόνου. Για το σκοπό αυτό, μελετήθηκε η έννοια του πραγματικού χρόνου όσον αφορά την κατασκευαστική διάσταση του συστήματος και το πρόγραμμα της εφαρμογής. Μια κατηγορία συστημάτων παραγματικού χρόνου είναι τα λειτουργικά συστήματα με δυνατότητες πραγματικού χρόνου. Αυτά οργανώνουν και καθορίζουν την χρήση των πόρων των συστημάτων ώστε να είναι ιδανική για εφαρμογές πραγματικού χρόνου πέρα από το περιβάλλον για ανάπτυξη και εκτέλεση των προγραμμάτων που παρέχουν. Γίνεται αναφορά στην έννοια της πολυεπεξεργασίας (multiprocessing), της χρήσης δηλαδή δύο ή και παραπάνω κεντρικών μονάδων επεξεργασίας (CPU) σε ένα υπολογιστικό σύστημα. Λόγω της αύξησης της θερμοκρασίας στα ηλεκτρονικά κυκλώματα με την αύξηση των ταχυτήτων ρολογιού στις κεντρικές μονάδες επεξεργασίας και την μείωση του μεγέθους των ηλεκτρονικών, η ταχύτητα του ρολογιού αλλά και η μείωση του μεγέθους περιορίζονται ώστε να υπάρχει αντοχή στις θερμοκρασίες που αναπτύσσονται. Το γεγονός αυτό σε συνδυασμό με την ιδέα του multiprocessing οδήγησε στην ιδέα των πολλαπλών ανεξάρτητων πυρήνων ανά κεντρική μονάδα επεξεργασίας (multicore systems) για βελτίωση της αποδοτικότητας, ακόμα και των συστημάτων ευρείας κατανάλωσης. Η διαφορά των πολυπύρηνων (multicore) συστημάτων με τα multiprocessing συστήματα, έγκειται στην συνύπαρξη των πυρήνων σε ένα ολοκληρωμένο κύκλωμα (chip) αντί για πολλές κεντρικές μονάδες επεξεργασίας και η ομοιότητα τους, στο ότι ουσιαστικά τα multicore συστήματα εξομοιώνουν λειτουργίες πολυεπεξεργασμού. Πλεόν, πολλά ενσωματωμένα συστήματα διαθέτουν πολυπύρηνους επεξεργαστές καθιστώντας απαραίτητη την ανάπτυξη λειτουργικών συστημάτων πραγματικού χρόνου που να αξιοποιούν στο έπακρο τις δυνατότητες τους. Δοκιμάστηκε και αξιολογήθηκε η επέκταση ASMP-Linux που αποτελεί έναν τρόπο μετατροπής του Linux σε λειτουργικό σύστημα πραγματικού χρόνου. Το ASMP-Linux αξιοποιεί τις ικανότητες πολυεπεξεργασίας ενός συστήματος με τη δυνατότητα δημιουργίας διαμερισμάτων πραγματικού χρόνου σε κάθε στοιχείο επεξεργασίας. Αναπτύχθηκε εφαρμογή αξιολόγησης σε γλώσσα προγραμματισμού C. Τα αποτελέσματα μελετήθηκαν διεξοδικά μέσω γραφημάτων και εξαγωγής στατιστικών μέτρων όπως η μέση τιμή και η τυπική απόκλιση. Μελετήθηκε η περίπτωση χρήσης της εφαρμογής ελέγχου του Festo MecLab, που αναπτύχθηκε από τον διδακτορικό φοιτητή Γεώργιο Δούκα. Το Festo MecLab αποτελεί μια προσομοίωση γραμμής παραγωγής με σταθμούς στοίβαξης, μεταφοράς και χειρισμού. Η εφαρμογή ελέγχου εκτελέστηκε επιτυχώς στο λειτουργικό σύστημα πραγματικού χρόνου ASMP-Linux και περιγράφεται στο παράρτημα Α. Στα πλαίσια της διπλωματικής εργασίας εκτελέστηκε στο Τεχνολογικό Πανεπιστήμιο της Βιέννης μέσω του προγράμματος Erasmus project που αφορά την ανίχνευση και χρονοσφράγιση προγραμμάτων ενσωματωμένων συστημάτων. H τεχνική αναφορά του project παρατίθεται στο παράρτημα Β. / In recent years, embedded real time systems are used in an increasingly wider range of applications. Mobile phones, compact discs players, printers, digital cameras, are a few examples of devices using the technology of embedded systems. This thesis investigated the possibilities of Real-Time Linux in embedded systems. The kernel of the Linux operating system and its scheduling algorithm was studied in detail. Ways of making Linux a real time operating system were sought. For this purpose, the essence of real time on the construction aspect of the system and the program application was studied. A class of real time-systems is real time operating systems. They organize and determine the use of resources systems that are ideal for real-time applications over the development environment and implementation of programs. The concept of multiprocessing, ie the use of two or more central processing units (CPU) on a computer system was also studied. Due to the increasing temperatures in electronic circuits and the reducing size of electronics, a limit in the reducing size is set, in order to withstand high temperatures. This, coupled with the idea of multiprocessing led to the idea multiple independent cores per CPU (multicore systems) to improve efficiency, even that of large-scale consumption. The difference between multi-core and multiprocessing systems is the coexistence of cells in an integrated circuit (chip) instead of several CPU's and their similarity is that multicore systems implement multiprocessing functions. Moreover, many embedded systems have multi-core processors making it necessary to develop real-time operating systems to exploit their full capabilities. We tested and evaluated the ASMP-Linux patch, which is a way of converting Linux operating system in a real time operating system. The ASMP-Linux fully exploits the capabilities of a multiprocessing system by adding the ability to partition the operating system in real time partitions on each independent core/CPU. An assesment application was developed in the C programming language. The results have been studied extensively through graphs and statistical measures such as mean and standard deviation. We studied the use of a control application of the Festo MecLab, developed by the doctoral student George Doukas. The Festo MecLab is a production line simulation that implements functions such as stacking, transport and handling. The control application was executed successfully in the real-time operating system ASMP-Linux and is described in Annex A. As part of this thesis a project on the detection and timestamping programs of embedded systems was performed at the Technical University of Vienna via the Erasmus program. A technical report of the project is given in Annex B.

Real-time systems require a-priori temporal guarantees. While most of the normal operation in such a system is modeled using time-driven, hard-deadline sporadic tasks, event-driven behavior is modeled using aperiodic jobs with soft or no deadlines. To provide good Quality-of- Service for aperiodic jobs in the presence of sporadic tasks, aperiodic servers were introduced. Aperiodic servers act as a sporadic task and reserve a quota periodically to serve aperiodic jobs. The use of aperiodic servers in systems with caches is unsafe because aperiodic servers do not take into account, the indirect cache-related preemption delays that the execution of aperiodic jobs might impose on the lower-priority sporadic tasks, thus jeopardizing their safety. To solve this problem, we propose an enhancement to the aperiodic server that we call a Cache Delay Server. Here, each lower-priority sporadic task is assigned a delay quota to accommodate the cache-related preemption delay imposed by the execution of aperiodic jobs. Aperiodic jobs are allowed to execute at their assigned server priority only when all the active lower-priority sporadic tasks have a sufficient delay quota to accommodate it. Simulation results demonstrate that a Cache Delay Server ensures the safety of sporadic tasks while providing acceptable Quality-of-Service for aperiodic jobs. We propose a Integer Linear Program based approach to calculate delay quotas for sporadic tasks within a task set where Cache Delay Servers have been pre-assigned. We then propose algorithms to determine Cache Delay Server characteristics for a given sporadic task set. Finally, we extend the Cache Delay Server concept to multi-core architectures and propose approaches to schedule aperiodic jobs on appropriate Cache Delay Servers. Simulation results demonstrate the effectiveness of all our proposed algorithms in improving aperiodic job response times while maintaining the safety of sporadic task execution.

Orientador: Takaaki Ohishi / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-21T06:33:46Z (GMT). No. of bitstreams: 1 LeoneFilho_MarcosdeAlmeida_D.pdf: 4843918 bytes, checksum: 9350da4d7c5f9bb7cb858c5d09a0d150 (MD5) Previous issue date: 2012 / Resumo: A principal contribuição desta tese é a proposta de uma metodologia juntamente com a implementação de um sistema de suporte à decisão para dar subsídio à programação diária de sistemas de potência. Basicamente, a metodologia implementada neste trabalho visa melhorar o perfil das tensões em uma rede de transmissão de energia elétrica através de um ajuste fino dos taps dos transformadores. Este processo de otimização dos taps é feito com a utilização de Algoritmos Genéticos de maneira que, ao final deste processo, seja obtido um conjunto de valores de taps que, se aplicados à rede de transmissão, tornará as tensões mais próximas de um mesmo nível de tensão pré-determinado. Além disto, a abordagem proposta não é somente capaz de analisar uma \fotografia" de carga do sistema, mas também é capaz de realizar uma análise diária (em intervalos horários) para melhorar o perfil de tensão durante um dia completo de operação. A metodologia proposta é avaliada inicialmente com os sistemas IEEE-30 barras e IEEE-118 barras para que, finalmente, fosse aplicada para o sistema interligado nacional (SIN) brasileiro. Além disto, um sistema de suporte à decisão foi implementado durante o desenvolvimento deste trabalho. Tal sistema poderia ser usado para proporcionar ao operador do sistema de transmissão meios de avaliar os fluxos da rede através de uma execução de análises de sensibilidade quanto às possíveis utuações de carga em tempo de operação e também avaliar cenários de contingências / Abstract: The main contribution of this thesis is the proposal of a new methodology together with the implementation of a decision support system for real-time transmission grid operation. Hence, a methodology for improving voltage pro- _le for power transmission systems is described in this thesis. Basically, it consists in tuning the transformers taps in a way that the buses voltages in the same area would stay around a pre-specified level. Genetic Algorithms are applied for this optimization process in a way that, at the end of this process, a set of taps values that can drive the power system's voltage closer to a desired voltage level (if applied to it) is obtained. Furthermore, the proposed approach is not only able to analyze a static \picture" of power load, but also to cope with the issue of programming the hourly daily tap strategy according to the variations of the daily load profile. The proposed methodology is first evaluated with the \IEEE-30-bus" and with the \IEEE-118-bus" test cases so that it could be finally applied to the Brazilian interconnected national power system. Besides, a decision support system was implemented during the progress of the work. Such system was designed in a way that it could be possibly used by a grid operator in order to evaluate load flows and also to develop many different studies by analyzing the system's sensitiveness to the load variations at real time operation and also by evaluating a variety of contingencies scenarios / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Orientador: Janito Vaqueiro Ferreira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-20T09:38:04Z (GMT). No. of bitstreams: 1 GordilloCarrillo_CamiloAndres_M.pdf: 5104981 bytes, checksum: cd95669708a4fb537590b77509d111b9 (MD5) Previous issue date: 2012 / Resumo: O conceito de Hardware In the Loop (HIL) é bastante útil em indústrias automotivas e em indústrias espaciais, já que sistemas complexos são difíceis de se modelar. Este conceito proporciona uma grande confiabilidade aos resultados, diminui o risco de avaria dos equipamentos e dos usuários em seu funcionamento, como também uma diminuição do tempo no desenvolvimento de projetos. Tudo isto sem precisar de um orçamento elevado ou protótipos elaborados para realização de testes. Neste trabalho propõem-se duas estratégias para solucionar o problema do atraso (delay) apresentado pelo sinal de resposta nos sistemas HIL em tempo real, levando-se em conta a sequência de execução real dos processos, bem como também outros aspectos como dos sistemas de aquisição e atuação (inercia, limitações de hardware e software, tempo de amostragem). Os resultados obtidos através das estratégias propostas foram analisados e comparados com resultados numéricos em uma bancada experimental obtendo uma boa concordância eliminando o atraso na resposta / Abstract: The Hardware In the Loop (HIL) concept is useful in automotive and spaceship industries, because of the difficulty of modeling complex systems. This concept provides great reliability at the results, decrease the risk of damage to the equipment and to the user operation, as well as decreasing the time of projects development. All of this without requiring a high budget or developing prototypes for testing. This study propose a strategy to solve the delay problem presented by the response signal in real time HIL systems, considering a real execution sequence of the process, as well as other aspects such as in the acquisition and the actuation systems (inertia, hardware and software limitations, sample time). The results obtained through the proposed strategies was analyzed and compared with numerical results in a testing platform with excellent concordance eliminating the delay in the response / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestre em Engenharia Mecânica

An event monitor is a part of a real-time system that can be used to check if the system follows the specifications posed on its behavior. This dissertation covers an approach to event monitoring where such specifications (represented by time constraints) are represented by graphs. Not much work has previously been done on designing and implementing constraint graph-based event monitors. In this work, we focus on presenting an extensible design for such an event monitor. We also evaluate different data structure types (linked lists, dynamic arrays, and static arrays) that can be used for representing the constraint graphs internally. This is done by creating an event monitor implementation, and conducting a number of benchmarks where the time used by the monitor is measured. The result is presented in the form of a design specification and a summary of the benchmark results. Dynamic arrays are found to be the generally most efficient, but advantages and disadvantages of all the data structure types are discussed.

The mixed-criticality toolbox promises system architects a powerful framework for consolidating real-time tasks with different safety properties on a single computing platform. Thanks to the research efforts in the mixed-criticality field, guarantees provided to the highest criticality level are well understood. However, lower-criticality job execution depends on the condition that all high-criticality jobs complete within their more optimistic low-criticality execution time bounds. Otherwise, no guarantees are made. In this paper, we add to the mixed-criticality toolbox by providing a probabilistic analysis method for low-criticality tasks. While deterministic models reduce task behavior to constant numbers, probabilistic analysis captures varying runtime behavior. We introduce a novel algorithmic approach for probabilistic timing analysis, which we call symbolic scheduling. For restricted task sets, we also present an analytical solution. We use this method to calculate per-job success probabilities for low-criticality tasks, in order to quantify, how low-criticality tasks behave in case of high-criticality jobs overrunning their optimistic low-criticality reservation.

Lock-based concurrency control suffers from programmability, scalability, and composability challenges. These challenges are exacerbated in emerging multicore architectures, on which improved software performance must be achieved by exposing greater concurrency. Transactional memory (TM) is an emerging alternative synchronization model for shared memory objects that promises to alleviate these difficulties. In this dissertation, we consider software transactional memory (STM) for concurrency control in multicore real-time software, and present a suite of real-time STM contention managers for resolving transactional conflicts. The contention managers are called ECM, RCM, LCM, PNF, and FBLT. RCM and ECM resolve conflicts using fixed and dynamic priorities of real-time tasks, respectively, and are naturally intended to be used with the fixed priority (e.g., G-RMA) and dynamic priority (e.g., G-EDF) multicore real-time schedulers, respectively. LCM resolves conflicts based on task priorities as well as atomic section lengths, and can be used with G-EDF or G-RMA schedulers. Transactions under ECM, RCM, and LCM may retry due to conflicts with higher priority tasks even when there are no shared objects, i.e., transitive retry. PNF avoids transitive retry and optimizes processor usage by lowering the priority of retrying transactions, thereby enabling other non-conflicting transactions to proceed. PNF, however, requires a priori knowledge of all requested objects for each atomic section, which is inconsistent with the semantics of dynamic STM. Moreover, its centralized design increases overhead. FBLT avoids transitive retry, do not require a priori knowledge of requested objects, and has a decentralized design. We establish upper bounds on transactional retry costs and task response times under the contention managers through schedulability analysis. Since ECM and RCM preserve the semantics of the underlying real-time scheduler, their maximum transactional retry cost is double the maximum atomic section length. This is improved in the design of LCM, which achieves shorter retry costs and tighter upper bounds. As PNF avoids transitive retry and improves processor usage, it yields shorter retry costs and tighter upper bounds than ECM, RCM, and LCM. FBLT\'s upper bounds are similarly tight because it combines the advantages of PNF and LCM. We formally compare the proposed contention managers with each other, with lock-free synchronization, and with multiprocessor real-time locking protocols. Our analysis reveals that, for most cases, ECM, RCM, and LCM achieve higher schedulability than lock-free synchronization only when the atomic section length does not exceed half of lock-free synchronization\'s retry loop length. With equal periods and greater access times for shared objects, atomic section length under ECM, RCM, and LCM can be much larger than the retry loop length while still achieving better schedulability. With proper values for LCM\'s design parameters, atomic section length can be larger than the retry loop length for better schedulability. Under PNF, atomic section length can exceed lock-free\'s retry loop length and still achieve better schedulability in certain cases. FBLT achieves equal or better schedulability than lock-free with appropriate values for design parameters. The schedulability advantage of the contention managers over multiprocessor real-time locking protocols such as Global OMLP and RNLP depends upon the value of $s_{max}/L_{max}$, the ratio of the maximum transaction length to the maximum critical section length. FBLT\'s schedulability is equal or better than Global OMLP and RNLP if $s_/L_ le 2$. Checkpointing enables partial roll-back of transactions by recording transaction execution states (i.e., checkpoints) during execution, allowing roll-back to a previous checkpoint instead of transaction start, improving task response time. We extend FBLT with checkpointing and develop CP-FBLT, and identify the conditions under which CP-FBLT achieves equal or better schedulability than FBLT. We implement the contention managers in the Rochester STM framework and conduct experimental studies using a multicore real-time Linux kernel. Our studies reveal that among the contention managers, CP-FBLT has the best average-case performance. CP-FBLT\'s higher performance is due to the fact that PNF\'s and LCM\'s advantages are combined into the design of FBLT, which is the base of CP-FBLT. Moreover, checkpointing improves task response time. The contention managers were also found to have equal or better average-case performance than lock-free synchronization: more jobs meet their deadlines using CP-FBLT, FBLT, and PNF than lock-free synchronization by 34.6%, 28.5%, and 32.4% (on average), respectively. The superiority of the contention managers is directly due to their better conflict resolution policies. Locking protocols such as OMLP and RNLP were found to perform better: more jobs meet their deadlines under OMLP and RNLP than any contention manager by 12.4% and 13.7% (on average), respectively. However, the proposed contention managers have numerous qualitative advantages over locking protocols. Locks do not compose, whereas STM transactions do. To allow multiple objects to be accessed in a critical section, OMLP assigns objects to non-conflicting groups, where each group is protected by a distinct lock. RNLP assumes that objects are accessed in a specific order to prevent deadlocks. In contrast, STM allows multiple objects to be accessed in a transaction in any order, while guaranteeing deadlock-freedom, which significantly increases programmability. Moreover, STM offers platform independence: the proposed contention managers can be entirely implemented in the user-space as a library. In contrast, real-time locking protocols such as OMLP and RNLP must be supported by the underlying platform (i.e., operating system or virtual machine). / Ph. D.