Dissertations / Theses: 'Real-time scheduling analysis'

1

Applegate, Clarence Bruce 1972. "A scheduling analysis tool for real-time systems." Thesis, Massachusetts Institute of Technology, 2000. http://hdl.handle.net/1721.1/81536.

Full text

Abstract:

Thesis (S.B. and M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.
Includes bibliographical references (leaves 63-65).
by Clarence Bruce Applegate.
S.B.and M.Eng.

APA, Harvard, Vancouver, ISO, and other styles

2

Bouakaz, Adnan. "Real-time scheduling of dataflow graphs." Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00945453.

Full text

Abstract:

The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.

APA, Harvard, Vancouver, ISO, and other styles

3

Chadli, Mounir. "Analyse of real-time systems from scheduling perspective." Thesis, Rennes 1, 2018. http://www.theses.fr/2018REN1S062/document.

Full text

Abstract:

Les logiciels sont devenus une partie importante de notre vie quotidienne, car ils sont maintenant utilisés dans de nombreux périphériques hétérogènes, tels que nos téléphones, nos voitures, nos appareils ménagers, etc. Ces périphériques sont parsemés d’un certain nombre de logiciels intégrés, chacun gérant une tâche spécifique. Ces logiciels intégrés sont conçus pour fonctionner à l’intérieur de systèmes plus vastes avec un matériel varié et hétérogène et des ressources limitées. L'utilisation de logiciels embarqués est motivée par la flexibilité et la simplicité que ces logiciels peuvent garantir, ainsi que par la réduction des coûts. Les Cyber-Physical System (CPS) sont des logiciels utilisés pour contrôler des systèmes physiques. Les CPS sont souvent intégrés et s'exécutent en temps réel, ce qui signifie qu'ils doivent réagir aux événements externes. Un CPS complexe peut contenir de nombreux systèmes en temps réel. Le fait que ces systèmes puissent être utilisés dans des domaines critiques tels que la médecine ou les transports exige un haut niveau de sécurité pour ces systèmes. Les systèmes temps réel (RTS), par définition, sont des systèmes informatiques de traitement qui doivent répondre à des entrées générées de manière externe. Ils sont appelés temps réel car leur réponse doit respecter des contraintes de temps strictes. Par conséquent, l'exactitude de ces systèmes ne dépend pas seulement de l'exactitude des résultats de leur traitement, mais également du moment auquel ces résultats sont donnés. Le principal problème lié à l'utilisation de systèmes temps réel est la difficulté de vérifier leurs contraintes de synchronisation. Un moyen de vérifier les contraintes de temps peut consister à utiliser la théorie de la planification, stratégie utilisée pour partager les ressources système entre ses différents composants. Outre les contraintes de temps, il convient de prendre en compte d'autres contraintes, telles que la consommation d'énergie ou la sécurité. Plusieurs méthodes de vérification ont été utilisées au cours des dernières années, mais avec la complexité croissante des logiciels embarqués, ces méthodes atteignent leurs limites. C'est pourquoi les chercheurs se concentrent maintenant sur la recherche de nouvelles méthodes et de nouveaux formalismes capables de vérifier l'exactitude des systèmes les plus complexes. Aujourd'hui, une classe de méthodes de vérification bien utilisées est les techniques basées sur des modèles. Ces techniques décrivent le comportement du système considéré à l'aide de formalismes mathématiques, puis, à l'aide de méthodes appropriées, permettent d'évaluer l'efficacité du système par rapport à un ensemble de propriétés. Dans ce manuscrit, nous nous concentrons sur l'utilisation de techniques basées sur des modèles pour développer de nouvelles techniques de planification afin d'analyser et de valider la satisfiabilité d'un certain nombre de propriétés sur des systèmes temps réel. L'idée principale est d'exploiter la théorie de l'ordonnancement pour proposer ces nouvelles techniques. Pour ce faire, nous proposons un certain nombre de nouveaux modèles afin de vérifier la satisfiabilité d'un certain nombre de propriétés telles que l'ordonnancement, la consommation d'énergie ou la fuite d'informations
Software’s become an important part of our daily life as they are now used in many heterogeneous devices, such as our phones, our cars, our home appliances … etc. These devices are dotted with a number of embedded software’s, each handling a specific task. These embedded software’s are designed to run inside larger systems with various and heterogeneous hardware and limited resources. The use of embedded software is motivated by the flexibility and the simplicity that these software can guarantee, and to minimize the cost. Cyber-Physical System (CPS) are software used to control physical systems. CPS are often embedded and run in real-time, which means that they must react to external events. A complex CPS can contains many real-time systems. The fact that these systems can be used in critical domains like medicine or transport requires a high level of safety for these systems. Real-Time Systems (RTS) by definition are processing information systems that have to respond to externally generated inputs, and they are called real-time because their response must respect a strict timing constraints. Therefore, the correctness of these systems does not depend only on the correctness of their treatment results, but it also depends on the timings at which these results are given. The main problem with using real-time systems is the difficulty to verify their timing constraints. A way to verify timing constraints can be to use Scheduling theory which is a strategy used in order to share the system resources between its different components. In addition to the timing constraints, other constraints should be taken in consideration, like energy consumption or security. Several verification methods have been used in the last years, but with the increasing complexity of the embedded software these methods reach their limitation. That is why researchers are now focusing their works on finding new methods and formalisms capable of verifying the correctness of the most complex systems. Today, a well-used class of verification methods are model-based techniques. These techniques describe the behavior of the system under consideration using mathematical formalisms, then using appropriate methods they give the possibility to evaluate the correctness of the system with respect to a set of properties. In this manuscript we focus on using model-based techniques to develop new scheduling techniques in order to analyze and validate the satisfiability of a number of properties on real-time systems. The main idea is to exploit scheduling theory to propose these new techniques. To do that, we propose a number of new models in order to verify the satisfiability of a number of properties as schedulability, energy consumption or information leakage

APA, Harvard, Vancouver, ISO, and other styles

4

Rodziewicz, Pawel. "Timing and scheduling analysis of real-time object-oriented models." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ39491.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bate, Iain John. "Scheduling and timing analysis for safety critical real-time systems." Thesis, University of York, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.286151.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Koo, Ja-Ryeong. "Global scheduling on temperature-constrained multiprocessor real-time systems." Texas A&M University, 2008. http://hdl.handle.net/1969.1/85913.

Full text

Abstract:

In this thesis, we study temperature-constrained multiprocessor real-time systems, where real-time guarantees must be met without exceeding safe temperature levels within the processors. We focus on Pfair scheduling algorithms, especially ERfair scheduling scheme (a work-conserving extension to Pfair scheduling) as our main multiprocessor real-time scheduling methodology. Then, we study the benefits of simple reactive speed scaling as described in the real-time multiprocessor systems. In this thesis, in support of the temperature-awareness, we extend the applicability of the reactive speed scaling to global scheduling schemes for multiprocessors. We propose temperature-aware scheduling and processor selection schemes motivated by existing (thermally non-optimal) ERfair scheduling in order to reduce thermal stress and therefore increase the processor utilization. Then, we show that the proposed algorithm and reactive scheme can enhance the processor utilization compared with any constant speed scheme on real-time multiprocessor systems. Additionally, we show how the maximum schedulable utilization (MSU) for partitioning heuristics can be determined on the temperature-constrained multiprocessor real-time systems.

APA, Harvard, Vancouver, ISO, and other styles

7

Coleman, Benjamin J. "Lookahead scheduling in a real-time context: Models, algorithms, and analysis." W&M ScholarWorks, 2004. https://scholarworks.wm.edu/etd/1539623445.

Full text

Abstract:

Our research considers job scheduling, a special type of resource assignment problem. For example, at a cross-docking facility trucks must be assigned to doors where they will be unloaded. The cargo on each truck has various destinations within the facility, and the unloading time for a truck is dependent on the distance from the assigned door to these destinations. The goal is to assign the trucks to doors while minimizing the amount of time to unload all trucks.;We study scheduling algorithms for problems like the cross-docking example that are different from traditional algorithms in two ways. First, we utilize real-time, where the algorithm executes at the same time as when the jobs are handled. Because the time used by the algorithm to make decisions cannot be used to complete a job, these decisions must be made quickly Second, our algorithms utilize lookahead, or partial knowledge of jobs that will arrive in the future.;The three goals of this research were to demonstrate that lookahead algorithms can be implemented effectively in a real-time context, to measure the amount of improvement gained by utilizing lookahead, and to explore the conditions in which lookahead is beneficial.;We present a model suitable for representing problems that include lookahead in a real-time context. Using this model, we develop lookahead algorithms for two important job scheduling systems and argue that these algorithms make decisions efficiently. We then study the performance of lookahead algorithms using mathematical analysis and simulation.;Our results provide a detailed picture of the behavior of lookahead algorithms in a real-time context. Our analytical study shows that lookahead algorithms produce schedules that are significantly better than those without lookahead. We also found that utilizing Lookahead-1, or knowledge of the next arriving job, produces substantial improvement while requiring the least effort to design. When more lookahead information is used, the solutions are better, but the amount of improvement is not significantly larger than a Lookahead-1 algorithm. Further, algorithms utilizing more lookahead are more complex to design, implement, and analyze. We conclude that Lookahead-1 algorithms are the best balance between improvement and design effort.

APA, Harvard, Vancouver, ISO, and other styles

8

Wang, Jinggang. "Soft Real-Time Switched Ethernet: Best-Effort Packet Scheduling Algorithm, Implementation, and Feasibility Analysis." Thesis, Virginia Tech, 2002. http://hdl.handle.net/10919/35277.

Full text

Abstract:

In this thesis, we present a MAC-layer packet scheduling algorithm, called Best-effort Packet Scheduling Algorithm(BPA), for real-time switched Ethernet networks. BPA considers a message model where application messages have trans-node timeliness requirements that are specified using Jensen's benefit functions. The algorithm seeks to maximize aggregate message benefit by allowing message packets to inherit benefit functions of their parent messages and scheduling packets to maximize aggregate packet-level benefit. Since the packet scheduling problem is NP-hard, BPA heuristically computes schedules with a worst-case cost of O(n^2), faster than the O(n^3) cost of the best known Chen and Muhlethaler's Algorithm(CMA) for the same problem. Our simulation studies show that BPA performs the same or significantly better than CMA. We also construct a real-time switched Ethernet by prototyping an Ethernet switch using a Personal Computer(PC) and implementing BPA in the network protocol stack of the Linux kernel for packet scheduling. Our actual performance measurements of BPA using the network implementation reveal the effectiveness of the algorithm. Finally, we derive timeliness feasibility conditions of real-time switched Ethernet systems that use the BPA algorithm. The feasibility conditions allow real-time distributed systems to be constructed using BPA, with guaranteed soft timeliness.
Master of Science

APA, Harvard, Vancouver, ISO, and other styles

9

Stigge, Martin. "Real-Time Workload Models : Expressiveness vs. Analysis Efficiency." Doctoral thesis, Uppsala universitet, Avdelningen för datorteknik, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-219307.

Full text

Abstract:

The requirements for real-time systems in safety-critical applications typically contain strict timing constraints. The design of such a system must be subject to extensive validation to guarantee that critical timing constraints will never be violated while the system operates. A mathematically rigorous technique to do so is to perform a schedulability analysis for formally verifying models of the computational workload. Different workload models allow to describe task activations at different levels of expressiveness, ranging from traditional periodic models to sophisticated graph-based ones. An inherent conflict arises between the expressiveness and analysis efficiency of task models. The more expressive a task model is, the more accurately it can describe a system design, reducing over-approximations and thus minimizing wasteful over-provisioning of system resources. However, more expressiveness implies higher computational complexity of corresponding analysis methods. Consequently, an ideal model provides the highest possible expressiveness for which efficient exact analysis methods exist. This thesis investigates the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced, which generalizes all previously proposed models that can be analyzed in pseudo-polynomial time without using any analysis-specific over-approximations. We develop methods allowing to efficiently analyze variants of the model despite their strictly increased expressiveness. A key contribution is the notion of path abstraction which enables efficient graph traversal algorithms. We demonstrate tractability borderlines for different classes of schedulers, namely static priority and earliest-deadline first schedulers, by establishing hardness results. These hardness proofs provide insights about the inherent complexity of developing efficient analysis methods and indicate fundamental difficulties of the considered schedulability problems. Finally, we develop a novel abstraction refinement scheme to cope with combinatorial explosion and apply it to schedulability and response-time analysis problems. All methods presented in this thesis are extensively evaluated, demonstrating practical applicability.

APA, Harvard, Vancouver, ISO, and other styles

10

Zuhily, Areej. "Scheduling analysis of fixed priority hard real-time systems with multiframe tasks." Thesis, University of York, 2009. http://etheses.whiterose.ac.uk/11090/.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Fan, Ming. "Real-Time Scheduling of Embedded Applications on Multi-Core Platforms." FIU Digital Commons, 2014. http://digitalcommons.fiu.edu/etd/1243.

Full text

Abstract:

For the past several decades, we have experienced the tremendous growth, in both scale and scope, of real-time embedded systems, thanks largely to the advances in IC technology. However, the traditional approach to get performance boost by increasing CPU frequency has been a way of past. Researchers from both industry and academia are turning their focus to multi-core architectures for continuous improvement of computing performance. In our research, we seek to develop efficient scheduling algorithms and analysis methods in the design of real-time embedded systems on multi-core platforms. Real-time systems are the ones with the response time as critical as the logical correctness of computational results. In addition, a variety of stringent constraints such as power/energy consumption, peak temperature and reliability are also imposed to these systems. Therefore, real-time scheduling plays a critical role in design of such computing systems at the system level. We started our research by addressing timing constraints for real-time applications on multi-core platforms, and developed both partitioned and semi-partitioned scheduling algorithms to schedule fixed priority, periodic, and hard real-time tasks on multi-core platforms. Then we extended our research by taking temperature constraints into consideration. We developed a closed-form solution to capture temperature dynamics for a given periodic voltage schedule on multi-core platforms, and also developed three methods to check the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research by incorporating the power/energy constraint with thermal awareness into our research problem. We investigated the energy estimation problem on multi-core platforms, and developed a computation efficient method to calculate the energy consumption for a given voltage schedule on a multi-core platform. In this dissertation, we present our research in details and demonstrate the effectiveness and efficiency of our approaches with extensive experimental results.

APA, Harvard, Vancouver, ISO, and other styles

12

Azhar, Muhammad. "A Stochastic Analysis Framework for Real-Time Systems under Preemptive Priority-Driven Scheduling." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-13100.

Full text

Abstract:

This thesis work describes how to apply the stochastic analysis framework, presented in [1] for general priority-driven periodic real-time systems. The proposed framework is applicable to compute the response time distribution, the worst-case response time, and the deadline miss probability of the task under analysis in the fixed-priority driven scheduling system. To be specific, we modeled the task execution time by using the beta distribution. Moreover, we have evaluated the existing stochastic framework on a wide range of periodic systems with the help of defined evaluation parameters. In addition we have refined the notations used in system model and also developed new mathematics in order to facilitate the understanding with the concept. We have also introduced new concepts to obtain and validate the exact probabilistic task response time distribution. Another contribution of this thesis is that we have extended the existing system model in order to deal with stochastic release time of a job. Moreover, a new algorithm is developed and validated using our extended framework where the stochastic dependencies exist due to stochastic release time patterns.
This is Second Version of the report. Submitted after few modifications made on the order of Thomas Nolte (Thesis Examiner).
START - Stochastic Real-Time Analysis of Embedded Software Systems

APA, Harvard, Vancouver, ISO, and other styles

13

Nolte, Thomas. "Share-Driven Scheduling of Embedded Networks." Doctoral thesis, Mälardalen University, Department of Computer Science and Electronics, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-134.

Full text

Abstract:

Many products are built from more or less independently developed subsystems. For instance, a car consists of subsystems for transmission, braking, suspension, etc. These subsystems are frequently controlled by an embedded computer system. In the automotive industry, as well as in other application domains, there is currently a trend from an approach where subsystems have dedicated computer hardware and other resources (a federated approach) to an approach where subsystems share hardware and other resources (an integrated approach). This is motivated by a strong pressure to reduce product cost, at the same time as an increasing number of subsystems are being introduced.

When integrating subsystems, it is desirable that guarantees valid before integration are also valid after integration, since this would eliminate the need for costly reverifications. The computer network is a resource that is typically shared among all subsystems. Hence, a central issue when integrating subsystems is to provide an efficient scheduling of message transmissions on the network. There are essentially three families of schedulers that can be used: priority-driven schedulers that assign priorities to messages, time-driven schedulers that assign specific time-slots for transmission of specific messages, and share-driven schedulers that assign shares of the available network capacity to groups of messages.

This thesis presents a framework for share-driven scheduling, to be implemented and used in embedded networks, with the aim to facilitate subsystem integration by reducing the risk of interference between subsystems. The framework is applied in the automotive domain.

The initial parts of the thesis give an overview of systems, subsystems and network technologies found and used in the automotive domain. Then, the share-driven scheduling framework is presented, analytically investigated and proven, as well as evaluated in a simulation study. Finally it is shown how the framework is to be configured and used in the context of subsystem integration. The results show that the framework allows for flexible and efficient scheduling of messages with real-time constraints, facilitating integration of subsystems from a network point of view.

APA, Harvard, Vancouver, ISO, and other styles

14

Singh, Jasdeep. "Schedulability Analysis of Probabilistic Real-Time Systems." Thesis, Toulouse, ISAE, 2020. http://www.theses.fr/2020ESAE0010.

Full text

Abstract:

La thèse est une étude d'approches probabilistes pour la modélisation et l'analyse de systèmes temps réel. L'objectif est de comprendre et d'améliorer le pessimisme qui existe dans l'analyse du système. Les systèmes temps réel doivent produire des résultats avec des contraintes de temps réelles. L'exécution des tâches dans le système est basée sur leur pire temps d'exécution. En pratique, il peut y avoir de nombreux temps d'exécution possibles inférieurs au pire des cas. Nous utilisons le temps d’exécution probabiliste dans le pire cas, qui est une distribution de probabilité dans le pire des cas, qui limite tous les temps d’exécution possibles. Nous nous approchons avec le modèle de chaîne de Markov à temps continu pour obtenir des probabilités de manquer une contrainte de synchronisation dans le monde réel. Nous étudions également les systèmes de criticité mixte (MC) car ceux-ci ont également tendance à faire face au pessimisme dans un souci de sécurité. Les systèmes MC consistent en des tâches d’importance ou de criticité ged différentes. Le système fonctionne sous différents modes de criticité dans lesquels l'exécution des tâches de criticité identique ou supérieure est assurée. Nous abordons d’abord les systèmes MC en utilisant la chaîne de Markov en temps discret pour obtenir la probabilité que le système entre dans des niveaux de criticité plus élevés. Nous observons certaines limites de nos approches et nous procédons à la modélisation des systèmes probabilistes MC à l'aide de modèles Graph. Nous remettons en question les approches existantes dans la littérature et fournissons les nôtres. Nous obtenons des calendriers pour les systèmes MC optimisés pour l'utilisation des ressources. Nous faisons également le premier pas vers la dépendance entre les tâches en raison de leur scheduling
The thesis is a study of probabilistic approaches for modelling and analyzing real-time systems. The objective is to understand and improve of the pessimism that exists in the system analysis. Real-time systems must produce results with real world timing constraints. The execution of the tasks within the system is based on their worst case execution time. In practice, there can be many possible execution times below the worst case. We use probabilistic Worst Case Execution Time which is a worst case probability distribution which upper bounds all those possible execution times. We approach with Continuous Time Markov Chain model to obtain probabilities of missing real- world timing constraint. We also study Mixed Criticality (MC) systems because MC systems also tend to cope with pessimism with safety in mind. MC systems consist of tasks with different importance or criticalities. The system operates under different criticality modes in which the execution of the tasks of the same or higher criticality is ensured. We first approach MC systems using Discrete Time Markov Chain to obtain the probability of system entering higher criticalities. We observe certain limitations of our approaches and we proceed to model the MC probabilistic systems using Graph models. We question the existing approaches in the literature and provide our own. We obtain schedules for MC systems which is optimized for resource usage. We also make the first step towards dependence among the tasks due their scheduling

APA, Harvard, Vancouver, ISO, and other styles

15

Hua, Xiayu. "Theoretical Analysis of Real-Time Scheduling on Resources with Performance Degradation and Periodic Rejuvenation." Thesis, Illinois Institute of Technology, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10603696.

Full text

Abstract:

In 1973, Liu and Layland published their seminal paper on schedulability analysis of real-time system for both EDF and RM schedulers. In this work, they provide schedulability conditions and schedulability utilization bounds for both EDF and RM scheduling algorithms, respectively. In the following four decades, scheduling algorithms, utilization bounds and schedulability analyses for real-time tasks have been studied intensively. Amongst those studies, most of the research relies on a strong assumption that the performance of a computing resource does not change during its lifetime. Unfortunately, for many long standing real-time systems, such as data acquisition systems (DAQ), deep-space exploration programs and SCADA systems for power, water and other national infrastructures, the performance of computational resources suffer notably performance degradations after a long and continuous execution period.

To overcome the performance degradation in long standing systems, countermeasures, which are also called system rejuvenation approaches in the literature, were introduced and studied in depth in the last two decades. Rejuvenation approaches recover system performance when being invoked and hence benefit most long standing applications. However, for applications with real-time requirements, the system downtime caused by rejuvenation process, along with the decreasing performance during the system's available time, makes the existing real-time scheduling theories difficult to be applied directly.

To address this problem, this thesis studies the schedulability issues of a real-time task set running on long standing computing systems that suffers performance degradation and uses rejuvenation mechanism to recover.

Our first study in the thesis focuses on a simpler resource model, i.e. the periodic resource model, which only considers periodic rejuvenations. We introduce a method, i.e., Periodic Resource Integration, to combine multiple periodic resources into a single equivalent periodic resource and provide the schedulability analysis based on the combined periodic resource for real-time tasks. By integrating multiple periodic resources into one, existing real-time scheduling researches on single periodic resource can be directly applied on multiple periodic resources.

In our second study, we extend the periodic resource mode to a new resource model, the P²-resource model, in our second work to characterize resources with both the performance degradation and the periodic rejuvenation. We formally define the P²-resource and analyze the schedulability of real-time task sets on a P²-resource. In particular, we first analyze the resource supply status of a given P²-resource and provide its supply bound and linear supply bound functions. We then developed the schedulability conditions for a task set running on a P²-resource with EDF or RM scheduling algorithms, respectively. We further derive utilization bounds of both EDF and RM scheduling algorithms, respectively, for schedulability test purposes.

With the P²-resource model and the schedulability analysis on a single P²-resource, we further extend our work to multiple P²-resources. In this research, we 1) analyze the schedulability of a real-time task set on multiple P²-resources under fixed-priority scheduling algorithm, 2) introduce the GP-RM-P2 algorithm and 3) provide the utilization bound for this algorithm. Simulation results show that in most cases, the sufficient bounds we provide are tight.

As the rejuvenation technology keeps advancing, many systems are now able to perform rejuvenations in different system layers. To accommodate this new advance, we study the schedulability conditions of a real-time task set on a single P²-resource with both cold or warm rejuvenations. We introduce a new resource model, the P²-resource with duel-level rejuvenation, i.e., P²D-resource, to accommodate this new feature. We first study the supply bound and the linear supply bound of a given P²D-resource. We then study the sufficient utilization bounds for both RM and EDF scheduling algorithms, respectively.

APA, Harvard, Vancouver, ISO, and other styles

16

Yekeh, Farahnaz. "Hierarchical server-based communication with switched Ethernet." Thesis, Mälardalen University, School of Innovation, Design and Engineering, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-9914.

Full text

Abstract:

Server-based architectures have recently generated more interests and are currently considered for usage for communication in networks. In parallel, switched Ethernet technology has been widely adopted and used in lots of networked systems. Current requirements of networks for supporting real-time guarantees while being flexible at the same time have made the network designers to consider addition of some features to common switches. The FTT-Enabled Ethernet switch is a switch that has been developed to support the FTT (Flexible Time Triggered) paradigm. Recently, servers have been added in these types of switches in order to efficiently manage their allocated bandwidth to different types of messages.

A hierarchical network of Ethernet switches might be designed in different ways according to the overall goals and properties of the network. In this thesis, after a study on different design solutions, an architecture has been proposed based on FTT-enabled switches, motivated by their support of real-time constraints and server-based communication features. After having created the architecture, a protocol for bandwidth reservation for this hierarchically composed Ethernet switch architecture is developed. Behavior of the designed protocol is described in detail and it has been modeled using Uppaal. Moreover, the temporal behavior (timing) of the network is presented.

APA, Harvard, Vancouver, ISO, and other styles

17

Ferreira, Coelho Rodrigo [Verfasser], and Gerhard [Akademischer Betreuer] Fohler. "Buffer analysis and message scheduling for real-time networks / Rodrigo Ferreira Coelho ; Betreuer: Gerhard Fohler." Kaiserslautern : Technische Universität Kaiserslautern, 2017. http://d-nb.info/1147757747/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Keskin, Ugur. "Time-triggered Controller Area Network (ttcan) Communication Scheduling: A Systematic Approach." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12609877/index.pdf.

Full text

Abstract:

Time-Triggered Controller Area Network (TTCAN) is a hybrid communication paradigm with combining both time-triggered and event-triggered traffic scheduling. Different from the standard Controller Area Network (CAN), communication in TTCAN is performed according to a pre-computed, fixed (during system run) schedule that is called as TTCAN System Matrix. Thus, communication performance of TTCAN network is directly related to structure of the system matrix, which makes the design of system matrix a crucial process. The study in this thesis consists of the extended work on the development of a systematic approach for system matrix construction. Methods for periodic message scheduling and an approach for aperiodic message scheduling are proposed with the aim of constructing a feasible system matrix, combining three important aspects: message properties, protocol constraints and system performance requirements in terms of designated performance metrics. Also, system matrix design, analyses and performance evaluation are performed on example message sets with the help of two developed software tools.

APA, Harvard, Vancouver, ISO, and other styles

19

Guan, Nan. "New Techniques for Building Timing-Predictable Embedded Systems." Doctoral thesis, Uppsala universitet, Avdelningen för datorteknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-209623.

Full text

Abstract:

Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design. On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework. On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem. On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.

APA, Harvard, Vancouver, ISO, and other styles

20

Pop, Traian. "Analysis and Optimisation of Distributed Embedded Systems with Heterogeneous Scheduling Policies." Doctoral thesis, Linköping : Department of Computer and Information Science, Linköpings universitet, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-8934.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Fan, Xing. "Real-Time Services in Packet-Switched Networks for Embedded Applications." Doctoral thesis, Högskolan i Halmstad, Centrum för forskning om inbyggda system (CERES), 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-1984.

Full text

Abstract:

Embedded applications have become more and more complex, increasing the demands on the communication network. For reasons such as safety and usability, there are real-time constraints that must be met. Also, to offer high performance, network protocols should offer efficient user services aimed at specific types of communication. At the same time, it is desirable to design and implement embedded networks with reduced cost and development time, which means using available hardware for standard networks. To that end, there is a trend towards using switched Ethernet for embedded systems because of its hight bit rate and low cost. Unfortunately, since switched Ethernet is not specifically designed for embedded systems, it has several limitations such as poor support for QoS because of FCFS queuing policy and high protocol overhead. This thesis contributes towards fulfilling these requirements by developing (i) real-time analytical frameworks for providing QoS guarantees in packet-switched networks and (II) packet-merging techniques to reduce the protocol overhead. We have developed two real-time analytical frameworks for networks with FCFS queuing in the switches, one for FCFS queuing in the source nodes and one for EDF queuing in the source nodes. The correctness and tightness of the real-time analytical frameworks for different network components in a singel-switch neetwork are given by strict theoretical proofs, and the performance of our end-to-end analyses is evaluated by simulations. In conjunction with this, we have compared our results to Network Calculus (NC), a commonly used analytical scheme for FCFS queuing. Our comparison study shows that our anlysis is more accurate than NC for singel-switch networks. To reduce the protocol overhead, we have proposed two active switched Ethernet approaches, one for real-time many-to-many communication and the other for the real-time short message traffic that is often present in embedded applications. A significant improvement in performance achieved by using our proposed active networks is demonstrated. Although our approaches are exemplified using switched Ethernet, the general approaches are not limited to switched Ethernet networks but can easily be moified to other similar packet-switched networks.

APA, Harvard, Vancouver, ISO, and other styles

22

Rajnoha, Peter. "Analýza jader real-time operačních systémů běžících na platformě FITkit." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236754.

Full text

Abstract:

The project is dedicated to the identification of the problems found while building RT operating systems for use in embedded devices. The project's main topic is the possibility of using RT system in the FITkit platform and it also discusses individual problems and their possible solutions. One of the problems is the way of acquiring the timing information for tasks to ensure their RT properties. We have extended existing simulator for given microcontroller that is also part of the FITkit. The simulator can be used for detailed monitoring of the execution of individual tasks in the system based on dynamic analysis, collecting timing statistics for given blocks of the program or it can be extended by new modules. The RM scheduling mechanism has been integrated into the FreeRTOS system as an example by considering the knowledge of the concrete operating system and acquired timing information.

APA, Harvard, Vancouver, ISO, and other styles

23

Capitanu, Calin. "Fault Detection, Isolation and Recovery : Analysis of two scheduling algorithms." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-300128.

Full text

Abstract:

Unmanned, as well as manned space missions have seen a high failure rate in the early era of space technology. However, this decreased a lot since technology advanced and engineers learnt from previous experiences and improved critical real time systems with fault detection mechanisms. Fault detection, isolation and recovery, nowadays, is generally available in every flying device. However, the cost of hardware can bottleneck the process of creating such a system that is both robust and responsive. This thesis analyses the possibility of implementing a fault detection, isolation and recovery system inside of a single-threaded, cooperative scheduling operating system. The thesis suggests a cooperative implementation of such a system, where every task is responsible for parts of the fault detection. The analysis is done from both the integration layer, across the operating system and its tasks, as well as from the inside of the detection system, where two key components are implemented and analyzed: debug telemetry and operation modes. Results show that it is possible to implement a fault detection system that is spread across all the components of the satellite and acts cooperatively. Furthermore, the comparison with a traditional, dedicated fault detection system proves that errors can be caught faster with a cooperative mechanism.
Obemannade såväl som bemannade rymduppdrag har sett ett högt misslyckande i rymdteknikens tidiga era. Detta har dock förbättrats mycket sedan ingenjörer började lära sig av sina tidigare erfarenheter och utrustade kritiska realtidssystem med feldetekteringsmekanismer. Idag är alla flygande enheter utrustade med feldetekterings-, isolerings- och återställningsmekanismer. Däremot kan kostnaden för hårdvara vara ett problem för processen att skapa ett sådant system som är både robust och mottagligt. Denna uppsats analyserar möjligheten att implementera ett feldetekterings-, isolerings- och återställningssystem inuti ett enkelgängat samarbetsplaneringssystem. Denna uppsats föreslår ett samarbete för implementering av ett sådant system, där varje uppgift ansvarar för delar av feldetekteringen. Analysen görs från både integrationsskiktet, över operativsystemet och dess uppgifter, samt från insidan av detekteringssystemet, där två nyckelkomponenter implementeras och analyseras. Resultaten visar att det är möjligt att implementera ett feldetekteringssystem som täcker alla satellitkomponenter och som är mottaglig. Dessutom visar jämförelsen med ett traditionellt, dedikerat feldetekteringssystem att fel kan fångas snabbare med en mottagligmekanism.
Misiunile spat,iale cu oameni, atât cât s, i fara oameni, au avut o rata a es, ecurilor destul de ridicata în perioada init,iala a erei tehnologiei spat,iale. În schimb, aceasta a scazut semnificativ odata cu dezvoltarea tehnologiei, dar s, i datorita faptului ca inginerii au învat,at din experient,ele precendente s, i au îmbunatat, it sistemele critice în timp real cu mecanisme de detect,ie a erorilor. Sisteme de detect,ie, izolare s, i recuperare din erori sunt disponibile astazi în aproape toate sistemele spat,iale. Însa, costul echipamentelor poate împiedica crearea unor astfel de sisteme de detect,ie, care sa fie robuste s, i responsive. Aceasta teza analizeaza posibilitatea implementarii unui sistem de detect,ie, izolare s, i recuperare de la erori într-un satelit care este echipat cu un procesor cu un singur fir de execut,ie, care are un sistem de planificare cooperativ în sistemul de operare. Aceasta teza sugereaza o implementare cooperativa a unui astfel de sistem, unde fiecare proces este responsabil de câte o parte din detectarea erorilor. Analiza este realizata atât din perspectiva integrarii în sistemul de operare s, i procesele acestuia, cât s, i din interiorul acestui sistem de detect,ie, unde doua elemente importante sunt implementate s, i analizate: telemetria de depanare s, i modurile de operare. Rezultatele arata faptul ca este posibila implementarea unui sistem de detect,ie care este împart, it în toate componentele sistemului unui satelit s, i se comporta cooperativ. Mai departe, comparat,ia cu un sistem tradit,ional, dedicat, de detect,ie a erorilor arata ca erorile pot fi detectate mai rapid cu un sistem cooperativ.

APA, Harvard, Vancouver, ISO, and other styles

24

Huang, Wen-Hung Kevin [Verfasser], Jian-Jia [Akademischer Betreuer] Chen, and Jan [Gutachter] Reineke. "Scheduling algorithms and timing analysis for hard real-time systems / Wen-Hung Kevin Huang ; Gutachter: Jan Reineke ; Betreuer: Jian-Jia Chen." Dortmund : Universitätsbibliothek Dortmund, 2017. http://d-nb.info/1135487804/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Kunert, Kristina. "Architectures and Protocols for Performance Improvements of Real-Time Networks." Doctoral thesis, Högskolan i Halmstad, Inbyggda system (CERES), 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-14082.

Full text

Abstract:

When designing architectures and protocols for data traffic requiring real-time services, one of the major design goals is to guarantee that traffic deadlines can be met. However, many real-time applications also have additional requirements such as high throughput, high reliability, or energy efficiency. High-performance embedded systems communicating heterogeneous traffic with high bandwidth and strict timing requirements are in need of more efficient communication solutions, while wireless industrial applications, communicating control data, require support of reliability and guarantees of real-time predictability at the same time. To meet the requirements of high-performance embedded systems, this thesis work proposes two multi-wavelength high-speed passive optical networks. To enable reliable wireless industrial communications, a framework incorporating carefully scheduled retransmissions is developed. All solutions are based on a single-hop star topology, predictable Medium Access Control algorithms and Earliest Deadline First scheduling, centrally controlled by a master node. Further, real-time schedulability analysis is used as admission control policy to provide delay guarantees for hard real-time traffic. For high-performance embedded systems an optical star network with an Arrayed Waveguide Grating placed in the centre is suggested. The design combines spatial wavelength reuse with fixed-tuned and tuneable transceivers in the end nodes, enabling simultaneous transmission of both control and data traffic. This, in turn, permits efficient support of heterogeneous traffic with both hard and soft real-time constraints. By analyzing traffic dependencies in this multichannel network, and adapting the real-time schedulability analysis to incorporate these traffic dependencies, a considerable increase of the possible guaranteed throughput for hard real-time traffic can be obtained. Most industrial applications require using existing standards such as IEEE 802.11 or IEEE 802.15.4 for interoperability and cost efficiency. However, these standards do not provide predictable channel access, and thus real-time guarantees cannot be given. A framework is therefore developed, combining transport layer retransmissions with real-time analysis admission control, which has been adapted to consider retransmissions. It can be placed on top of many underlying communication technologies, exemplified in our work by the two aforementioned wireless standards. To enable a higher data rate than pure IEEE 802.15.4, but still maintaining its energy saving properties, two multichannel network architectures based on IEEE 802.15.4 and encompassing the framework are designed. The proposed architectures are evaluated in terms of reliability, utilization, delay, complexity, scalability and energy efficiency and it is concluded that performance is enhanced through redundancy in the time and frequency domains.

APA, Harvard, Vancouver, ISO, and other styles

26

Aminifar, Amir. "Analysis, Design, and Optimization of Embedded Control Systems." Doctoral thesis, Linköpings universitet, Programvara och system, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-124319.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

27

M'sirdi, Soukayna Raja. "Modular Avionics Software Integration on Multi-Core COTS : certification-Compliant Methodology and Timing Analysis Metrics for Legacy Software Reuse in Modern Aerospace Systems." Thesis, Toulouse, INPT, 2017. http://www.theses.fr/2017INPT0039/document.

Full text

Abstract:

Les interférences apparaissant dans les multicoeurs sont indésirables dans les systèmes tempsréel critiques, en particulier dans le domaine de l'aéronautique, où le déterminisme du fonctionnement temporel de tout système doit être formellement prouvé lors de la conception du système de manière à pouvoir être certifié et considéré comme opérationnel. Le but de cette thèse est de proposer une approche pour l'intégration logicielle d'applications IMA sur processeur multicoeur, sans impliquer de modification des plateformes logicielle et matérielle, et en respectant un maximum d'exigences de certification et concepts clés de l'avionique actuels, comme le partitionnement spatial et temporel ou encore la certification incrémentale. L'un des objectifs de la thèse est de respecter au maximum les procédés industriels d'intégration actuels de manière à maximiser les chances des contributions résultantes de la thèse d'être réutilisées au sein des industries avioniques. Un second objectif mineur est de permettre de réduire au minimum la phase d'adaptation des différents profils impliqués dans le processus d'intégration logicielle. Enfin, un troisième objectif est d'aider à optimiser le temps passé à effectuer les vérifications temporelles qui peuvent s'avérer difficiles et coûteuses en temps, mais aussi les choix architecturaux, de manière à réduire le time-to-market mais aussi optimiser le design du système en cours de conception. La contribution majeure de cette thèse est la proposition de deux stratégies complètes d'intégration logicielle/matérielle sur multicoeur pour des applications IMA. L'un des deux processus respecte les contraintes majeures de certification actuelles, ce qui en fait une stratégie potentiellement exploitable pour les applications les plus critiques de DAL A de l'aérospatial; la seconde offre un design le plus optimisé possible en termes de réduction de poids masse et consommation énergétique embarqués. Chaque stratégie est dite complète car elle contient: - une analyse temporelle statique qui borne les interférences inter-coeurs et permet de dériver des bornes supérieures de WCETs de manière fiable; - une formulation de problème de programmation par contraintes (PPC) pour l'allocation automatique et optimisée de logiciel sur matériel; la configuration résultante est correcte par construction car le problème de PPC exprimé exploite l'analyse temporelle mentionnée précédemment pour effectuer une vérification temporelle sur chaque configuration testée. - une formulation de problème de PPC pour la génération d'ordonnancement automatique et optimisé; la configuration résultante est correcte par construction car le processus exploite l'analyse temporelle mentionnée précédemment pour effectuer une vérification temporelle sur chaque configuration testée
Interference in multicores is undesirable for hard real-time systems and especially in the aerospace industry, for which it is mandatory to ensure beforehand timing predictability and deadlines enforcement in a system runtime behavior, in order to be granted acceptance by certification authorities. The goal of this thesis is to propose an approach for multi-core integration of legacy IMA software, without any hardware nor software modification, and which complies as much as possible to current, incremental certification and IMA key concepts such as robust time and space partitioning. The motivations of this thesis are to stick as much as possible to the current IMA software integration process in order to maximize the chances of acceptation by avionics industries of the contributions of this thesis, but also because the current process has long been proven efficient on aerospace systems currently in usage. Another motivation is to minimize the extra effort needed to provide certification authorities with timing-related verification information required when seeking approval. As a secondary goal depending on the possibilities, the contributions should offer design optimization features, and help reduce the time-to-market by automating some steps of the design and verification process. This thesis proposes two complete methodologies for IMA integration on multi-core COTS. Each of them offers different advantages and has different drawbacks, and therefore each of them may correspond to its own, complementary situations. One fits all avionics and certification requirements of incremental verification and robust partitioning and therefore fits up to DAL A applications, while the other offers maximum Size, Weight and Power (SWaP) optimization and fits either up to DAL C applications, multipartition applications or non-IMA applications. The methodologies are said to be "complete" because this thesis provides all necessary metrics to go through all steps of the software integration process. More specifically, this includes, for each strategy: - a static timing analysis for safely upper-bounding inter-core interference, and deriving the corresponding WCET upper-bounds for each task. - a Constraint Programming (CP) formulation for automated software/hardware allocation; the resulting allocation is correct by construction since the CP process embraces the proposed timing analysis mentioned earlier. - a CP formulation for automated schedule generation; the resulting schedule is correct by construction since the CP process embraces the proposed timing analysis mentioned earlier

APA, Harvard, Vancouver, ISO, and other styles

28

Khatiri, Mohammed. "Ordonnancement de tâche sur multi-coeur hétérogènes." Thesis, Université Grenoble Alpes, 2020. https://tel.archives-ouvertes.fr/tel-03026378.

Full text

Abstract:

Aujourd'hui, le développement des plates-formes de calcul haute performance (HPC) est considérable, elles sont toujours plus grandes, plus rapides, plus puissantes, mais aussi plus complexes. Ces plates-formes sont plus en plus hétérogènes, dynamiques, mais surtout, distribuées.Ces caractéristiques créent de nouveaux défis pour le problème de ordonnancement qui correspond à l'allocation des tâches aux différentes machines distantes.Le première défi est de savoir comment gérer efficacement l'hétérogénéité des ressources qui peut apparaitre au niveau du calcul ou au niveau des communications. Le deuxième défi est le caractère dynamique des tâches et des données,Pour relever ces défis, il faut accompagner ce développement par des outils logiciels efficaces pour gérer la complexité.Dans cette thèse, nous sommes intéressés aux problèmes d'ordonnancement en ligne et hors-ligne dans des ressources hétérogènes avec un environnement dynamique. La caractéristique de performance cruciale est la communication, qui est ignorée dans la plupart des approches existantes.Dans une première partie, nous analysons l'algorithme d'ordonnancement du vol du travail en ligne sur des plateformes parallèles et distribuées sous plusieurs contextes d'hétérogénéité. Nous commençons par une analyse mathématique d'un nouveau modèle de l'algorithme vol du travail sur plate-forme à mémoire distribuée où les communications entre les processeurs sont modélisés par une grande latence.Ensuite, nous étendons le problème précédent à deux clusters où la communication entre deux processeurs à l'intérieur d'un cluster est beaucoup plus petit qu'une communication externe. Nous étudions ce problème à l'aide de simulations. Ainsi, nous développons un propre simulateur, qui sera utilisé pour simuler différents algorithmes de vol de travail dans différents contextes (différentes topologies, différents types de tâches et différentes configurations).Dans une deuxième partie, nous nous concentrons sur deux problèmes d'ordonnancement hors ligne. Tout d'abord, l'ordonnancement d'un ensemble de tâches périodiques à échéance implicite et synchrones, sur une plate-forme temps réel composée de m processeurs identiques où la communication entre eux est importante. Pour ce problème, nous proposons un nouvel algorithme d'allocation de tâches qui vise à réduire le nombre de migrations de tâches, et limiter la migration (des tâche migrante) à deux processeurs.Ensuite, nous modélisons un problème d'ordonnancement récent, qui concerne les architectures micro-services qui visent à diviser les grandes applications (Applications monolithiques) en plusieurs petites applications (micro-services) connectées. Les micro-services ont des caractéristiques très spécifiques,ce qui rend spécial le problème d'ordonnancement (des micro-services).Sans apporter de solution complète, cette modélisation nous permet d'accéder à plusieurs directions de recherche capables de déterminer des solutions efficaces avec des approximations mathématiques
Today, high performance computing platforms (HPC) are experiencing rapid and significant development, they are bigger, faster, more powerful, but also more complex. These platforms are more and more heterogeneous, dynamic and distributed. These characteristics create new challenges for the scheduling problem which corresponds to the allocation of tasks to the different and remote processors.The first challenge is how to effectively manage the heterogeneity of resources which can appear at the computation level or at the communication level. The second challenge is the dynamic nature of tasks and data, To face this challenge, the development must be supported by effective software tools to manage the complexity. In this dissertation, we are interested in both on-line and off-line scheduling problems in heterogeneous resources on a dynamic environment. The crucial performance feature is the communication, which is ignored in most related approaches.Firstly, we analyze the Work Stealing on-line algorithm on parallel and distributed platforms with different contexts of heterogeneity. We start with a mathematical analysis of a new model of Work Stealing algorithm in a distributed memory platform where communications between processors are modeled by a large latency. Then, we extend the previous problem to two separate clusters, where the communication between two processors inside the same cluster is much less than an external communication. We study this problem using simulations. Thus, we develop a lightweight PYTHON simulator, the simulator is used to simulate different Work Stealing algorithms in different contexts (different topologies, different tasks type and different configurations).In a second part of this work, we focus on two offline scheduling problems. Firstly, we consider the scheduling problem of a set of periodic implicit-deadline and synchronous tasks, on a real-time multiprocessor composed of m identical processors including communication. We propose a new tasks allocation algorithm that aims to reduce the number of tasks migrations,and limits migration (of migrant tasks) on two processors. Secondly, we model a recent scheduling problem, which concerns the textbf {micro-services} architectures which aim to divide large applications (Monolithic applications) into several micro connected applications (micro-services), which makes the scheduling problem of micro-services special.Our model allows us to access several research directions able to identify effective solutions with mathematical approximations

APA, Harvard, Vancouver, ISO, and other styles

29

Khan, Dawood Ashraf. "Schedulability analysis for the design of reliable and cost-effective automotive embedded systems." Thesis, Vandoeuvre-les-Nancy, INPL, 2011. http://www.theses.fr/2011INPL097N/document.

Full text

Abstract:

Automobile système embarqué est une architecture distribuée de l'ordinateur des applications basées sur. La prolifération des systèmes embarqués dans une automobile a apporté de nombreux avantages,tels que le remplacement du système mécanique ancienne avec capteur électronique en réseau et desactionneurs, par exemple, dans des applications telles suspensions adaptatives. Le remplacement des systèmes mécaniques avec ceux électroniques et l'intégration de nouvelles fonctionnalités dans l'électronique soulève une grave préoccupation, c'est de fournir des garanties que ces systèmes embarqués seront en mesure d'effectuer, même dans des environnements difficiles, en particulier dans un système critique pour la sécurité comme un automobile. De plus, ceux-ci l'actualité informatique applications à la demande, imposée par un processus physique.Par exemple, pour éviter un événement catastrophique comme un accident de la demande de freinage doit répondre aux contraintes de minutage. Ce qui implique que la durée de temps entre l'instance de l'application du frein (à la pédale de frein) et l'instance de l'actionnement au niveau des roues d'un véhicule automobile doit être inférieure à la limite. En outre, l'application de freinage est généralement répartie sur le nombre de nœuds, qui sont embarqués communicants les uns avec les autres en utilisant une ressource de communication partagée. Par conséquent, il est important que nous fournissons des garanties que la demande, individuellement et collectivement, est atteinte de ses contrainte temporelle; qui est dans la composition de plusieurs nœuds embarqués. En outre, la prolifération des applications informatiques est également livré avec une hétérogénéité croissante et la complexité de l'architecture intégrée, ce qui conduira à l'augmentation de la complexité de l'analyse pour les systèmes automobiles.Par conséquent, il ya un besoin croissant d'assurer que ces systèmes automobiles embarqués répondre à des contraintes temporelles et de fournir des garanties de sécurité au cours de leur fonctionnement normal ou lors de situations critiques. Cette thèse vise à développer les analyses d'ordonnançabilité pour systèmes automobiles et les réseaux intégrés, avec le but de faciliter,d'une manière rentable et fiable, la conception et l'analyse des systèmes embarqués automobiles. Les analyses sont élaborées et appliquées dans le contexte de l'automobile; de façon à réduire le risque d'échec en raison de délai: les limites du matériel; frais généraux de mise en œuvre, et les interférences dues à la circulation probaliste
Automotive embedded system is a distributed architecture of computer-based applications. The proliferation of embedded systems in an automobile has brought numerous benefits; such as replacement of old mechanical system with networked electronic sensor and actuators, for example, in applications like adaptive suspensions. The replacement of mechanical systems with electronic onesand the integration of new functionality in electronics raises a serious concern; that is to provide guarantees that these embedded systems will be able to perform, even in harsh environments, particularly in a safety-critical system like an automobile.Moreover, these computer-based applications demand timeliness, imposed by a physical process. For example, to avoid a catastrophic event like a crash the braking application has to meet thetiming-constraints. This implies that the time duration between the instance of application of the brake (at brake pedal) and the instance of actuation at the wheels of an automobile should be less than the deadline. Moreover, the braking application is usually spread over number of embedded nodes, which are communicating with each other using a shared communication resource. Therefore, it is important that we provide some guarantees that an application, individually and collectively, is meeting its timing constraint; that is in the composition of multiple embedded nodes. Moreover, theproliferation of computer-based applications also comes with an increasing heterogeneity and complexity of the embedded architecture; which lead to the increase in the complexity of the analysis for the automotive systems Therefore, there is an increasing need to ensure that these automotive embedded systems meet temporal constraints and provide safety guarantees during their normal operation or during critical situations. This thesis aims at developing the schedulability analyses for automotive systems and embedded networks; with the aim to facilitate, in a cost-effective and reliable manner, the design and analysis of automotive embedded systems. The analyses are developed and applied in the automotive context; so as to reduce the risk of deadline failure due to: hardware limitations ; implementation overheads; and nterference due to probabilistic traffic

APA, Harvard, Vancouver, ISO, and other styles

30

Kloda, Tomasz. "Conditions d’ordonnançabilité pour un langage dirigé par le temps." Thesis, Toulouse, ISAE, 2015. http://www.theses.fr/2015ESAE0019/document.

Full text

Abstract:

Les travaux réalisés dans le cadre de cette thèse ont pour objectif de proposer un langage de description temporelle pour des systèmes temps-réel et d’établir les conditions de leur ordonnançabilité sous l’algorithme Earliest Deadline First (EDF). Les langages de description temporelle permettent de spécifier le comportement temporel d’une application indépendamment de son comportement fonctionnel. Le programmeur déclare dans ces langages à quels instants précis doivent être déclenchées et terminées les activités du système. Cette gestion du temps, précise et explicite, apporte au système son caractère déterministe. Le langage proposé, Extended Timing Definition Language (E-TDL), étend des langages dirigés par le temps existants, en particulier Giotto et TDL, en introduisant un nouveau modèle de tâche donné par quatre paramètres : phase, pire temps d’exécution, temps d’exécution logique TEL (intervalle de temps séparant le lancement de la tâche et sa terminaison) et période. L’introduction de ce nouveau modèle de tâche nécessite de revisiter en particulier le problème de l’ordonnançabilité des tâches pour EDF. Cette thèse propose et développe une analyse basée sur la fonction de demande pour des ensembles de tâches décrites en E-TDL et s’exécutant en contexte monoprocesseur. Une condition nécessaire et suffisante est obtenue au travers d’une analyse précise des intervalles séparant les activations de tâches au sein de différents modules s’exécutant indépendamment et pouvant changer de mode à des instants prédéfinis. Une borne de la longueur des intervalles sur lesquels doit s’opérer la vérification est déterminée. Un outil mettant en œuvre cette analyse a été développé
The goal of this research is to define a time-triggered language for modeling real-time systems and to provide the conditions for their schedulability under Earliest Deadline First (EDF). Time-triggered languages separate the functional part of applications from their timing definition. These languages permit to model the real-time system temporal behavior by assigning system activities to particular time instants. We propose a new time-triggered framework, Extended Timing Definition Language (E-TDL), that enhances the basic task model used in Giotto and TDL while keeping compositional and modular structure brought by the latter. An E-TDL task is characterized by: an offset, a worst case execution time, a Logical Execution Time (a time interval between task release and its termination) and a period. The schedulability analysis of the system based on this new task model should be, in particular for EDF, investigated. We develop, on the concept of the processor demand criterion, conditions for the feasibility of an E-TDL system running on a single CPU under EDF. A necessary and sufficient condition is obtained by considering the global schedules that are made up of execution traces occurring at the same time in distinct modules that are able to switch their modes at predefined instants. We estimate a maximal length of the interval on which the schedulability condition must be checked. A tool suite performing the schedulability analysis of the E-TDL systems is developed

APA, Harvard, Vancouver, ISO, and other styles

31

Medina, Roberto. "Deployment of mixed criticality and data driven systems on multi-cores architectures." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLT004/document.

Full text

Abstract:

De nos jours, la conception de systèmes critiques va de plus en plus vers l’intégration de différents composants système sur une unique plate-forme de calcul. Les systèmes à criticité mixte permettent aux composants critiques ayant un degré élevé de confiance (c.-à-d. une faible probabilité de défaillance) de partager des ressources de calcul avec des composants moins critiques sans nécessiter des mécanismes d’isolation logicielle.Traditionnellement, les systèmes critiques sont conçus à l’aide de modèles de calcul comme les graphes data-flow et l’ordonnancement temps-réel pour fournir un comportement logique et temporel correct. Néanmoins, les ressources allouées aux data-flows et aux ordonnanceurs temps-réel sont fondées sur l’analyse du pire cas, ce qui conduit souvent à une sous-utilisation des processeurs. Les ressources allouées ne sont ainsi pas toujours entièrement utilisées. Cette sous-utilisation devient plus remarquable sur les architectures multi-cœurs où la différence entre le meilleur et le pire cas est encore plus significative.Le modèle d’exécution à criticité mixte propose une solution au problème susmentionné. Afin d’allouer efficacement les ressources tout en assurant une exécution correcte des composants critiques, les ressources sont allouées en fonction du mode opérationnel du système. Tant que des capacités de calcul suffisantes sont disponibles pour respecter toutes les échéances, le système est dans un mode opérationnel de « basse criticité ». Cependant, si la charge du système augmente, les composants critiques sont priorisés pour respecter leurs échéances, leurs ressources de calcul augmentent et les composants moins/non critiques sont pénalisés. Le système passe alors à un mode opérationnel de « haute criticité ».L’ intégration des aspects de criticité mixte dans le modèle data-flow est néanmoins un problème difficile à résoudre. Des nouvelles méthodes d’ordonnancement capables de gérer des contraintes de précédences et des variations sur les budgets de temps doivent être définies.Bien que plusieurs contributions sur l’ordonnancement à criticité mixte aient été proposées, l’ordonnancement avec contraintes de précédences sur multi-processeurs a rarement été étudié. Les méthodes existantes conduisent à une sous-utilisation des ressources, ce qui contredit l’objectif principal de la criticité mixte. Pour cette raison, nous définissons des nouvelles méthodes d’ordonnancement efficaces basées sur une méta-heuristique produisant des tables d’ordonnancement pour chaque mode opérationnel du système. Ces tables sont correctes : lorsque la charge du système augmente, les composants critiques ne manqueront jamais leurs échéances. Deux implémentations basées sur des algorithmes globaux préemptifs démontrent un gain significatif en ordonnançabilité et en utilisation des ressources : plus de 60 % de systèmes ordonnançables sur une architecture donnée par rapport aux méthodes existantes.Alors que le modèle de criticité mixte prétend que les composants critiques et non critiques peuvent partager la même plate-forme de calcul, l'interruption des composants non critiques réduit considérablement leur disponibilité. Ceci est un problème car les composants non critiques doivent offrir une degré minimum de service. C’est pourquoi nous définissons des méthodes pour évaluer la disponibilité de ces composants. A notre connaissance, nos évaluations sont les premières capables de quantifier la disponibilité. Nous proposons également des améliorations qui limitent l’impact des composants critiques sur les composants non critiques. Ces améliorations sont évaluées grâce à des automates probabilistes et démontrent une amélioration considérable de la disponibilité : plus de 2 % dans un contexte où des augmentations de l’ordre de 10-9 sont significatives.Nos contributions ont été intégrées dans un framework open-source. Cet outil fournit également un générateur utilisé pour l’évaluation de nos méthodes d’ordonnancement
Nowadays, the design of modern Safety-critical systems is pushing towards the integration of multiple system components onto a single shared computation platform. Mixed-Criticality Systems in particular allow critical components with a high degree of confidence (i.e. low probability of failure) to share computation resources with less/non-critical components without requiring software isolation mechanisms (as opposed to partitioned systems).Traditionally, safety-critical systems have been conceived using models of computations like data-flow graphs and real-time scheduling to obtain logical and temporal correctness. Nonetheless, resources given to data-flow representations and real-time scheduling techniques are based on worst-case analysis which often leads to an under-utilization of the computation capacity. The allocated resources are not always completely used. This under-utilization becomes more notorious for multi-core architectures where the difference between best and worst-case performance is more significant.The mixed-criticality execution model proposes a solution to the abovementioned problem. To efficiently allocate resources while ensuring safe execution of the most critical components, resources are allocated in function of the operational mode the system is in. As long as sufficient processing capabilities are available to respect deadlines, the system remains in a ‘low-criticality’ operational mode. Nonetheless, if the system demand increases, critical components are prioritized to meet their deadlines, their computation resources are increased and less/non-critical components are potentially penalized. The system is said to transition to a ‘high-criticality’ operational mode.Yet, the incorporation of mixed-criticality aspects into the data-flow model of computation is a very difficult problem as it requires to define new scheduling methods capable of handling precedence constraints and variations in timing budgets.Although mixed-criticality scheduling has been well studied for single and multi-core platforms, the problem of data-dependencies in multi-core platforms has been rarely considered. Existing methods lead to poor resource usage which contradicts the main purpose of mixed-criticality. For this reason, our first objective focuses on designing new efficient scheduling methods for data-driven mixed-criticality systems. We define a meta-heuristic producing scheduling tables for all operational modes of the system. These tables are proven to be correct, i.e. when the system demand increases, critical components will never miss a deadline. Two implementations based on existing preemptive global algorithms were developed to gain in schedulability and resource usage. In some cases these implementations schedule more than 60% of systems compared to existing approaches.While the mixed-criticality model claims that critical and non-critical components can share the same computation platform, the interruption of non-critical components degrades their availability significantly. This is a problem since non-critical components need to deliver a minimum service guarantee. In fact, recent works in mixed-criticality have recognized this limitation. For this reason, we define methods to evaluate the availability of non-critical components. To our knowledge, our evaluations are the first ones capable of quantifying availability. We also propose enhancements compatible with our scheduling methods, limiting the impact that critical components have on non-critical ones. These enhancements are evaluated thanks to probabilistic automata and have shown a considerable improvement in availability, e.g. improvements of over 2% in a context where 10-9 increases are significant.Our contributions have been integrated into an open-source framework. This tool also provides an unbiased generator used to perform evaluations of scheduling methods for data-driven mixed-criticality systems

APA, Harvard, Vancouver, ISO, and other styles

32

Bonilha, Iaê Santos. "ESCALONAMENTO DE TAREFAS E FLUXOS DE COMUNICAÇÃO PARA SISTEMAS SEMI-PARTICIONADOS EM ARQUITETURAS NOC." Universidade Federal de Santa Maria, 2014. http://repositorio.ufsm.br/handle/1/5431.

Full text

Abstract:

Despiste the fact that many scheduling models teoretically capable of high system resource utilization were proposed with the development of the real-time system, the industry still uses the first scheduling model proposed for multi-processor real-time systems, the partitioned scheduling model. This scheduling model can guarantee scheduling of task sets up to around 69% processor utilization, which falls pale in comparison to recent scheduling models that can guarantee scheduling up to 97% processor utilization. The motive behind the utilization of the partitioned scheduling as industrial model is the amount of studies made on this model and the development of scheduling analysis capable of providing temporal guarantees for this model on a real system environment. Recent scheduling models, like semi-partitioned scheduling, offer the possibility of a higher system resource utilization, it still lack studies and scheduling analysis capable of provide temporal guarantees under a real environment. The current scheduling analysis for most of the more recent models take advantage of a series of abstractions, failing to provide guarantees under real circumstances. This papers primary objective is to produce a new scheduling analysis for semi-partitioned scheduling, capable of achieving temporal guarantees taking some of the previously abstracted factors, like task communication and the impact f task migration on its communications flows, approximating the scheduling model to real environmental conditions. With the development of such analysis preliminary studies were made on heuristic task mapping algorithms for semipartitioned systems.
Com a popularização de sistemas multi-processador, surgiu uma série de propostas de modelos de escalonamento, na área de sistemas de tempo real que, teoricamente, são capazes de obter um alto aproveitamento dos recursos do sistema. Entretanto, o modelo de escalonamento mais adotado continua sendo um dos primeiros modelos de escalonamento propostos na área, o modelo de escalonamento particionado. O modelo de escalonamento particionado só pode garantir o escalonamento de conjuntos com até cerca de 69% de utilização de processador, sendo limitado se comparado com garantias de escalonamento de até 97% de utilização de modelos mais recentes. O motivo pelo qual o escalonamento particionado continua sendo utilizado é a grande concentração de estudos a respeito do modelo e o desenvolvimento de análises de escalonamento capazes de garantir o escalonamento do modelo em condições reais do sistema. Modelos mais recentes, como o escalonamento semi-particionado, apresentam uma possibilidade de um maior aproveitamento do sistema, porém, ainda possuem estudos limitados e não dispõe de análises de escalonamento capazes de prover garantias temporais para o sistema em condições reais, devido à presença de diversas abstrações no modelo. Neste sentido, este trabalho foca em arquiteturas Network-on-Chip que apresentam comunicação explícita, abstraída nos trabalhos encontrados na literatura. Este trabalho tem como objetivo primário o desenvolvimento de uma análise de escalonamento capaz de prover garantias temporais para o modelo de escalonamento semi-particionado levando em consideração fatores previamente abstraídos, como a necessidade de comunicação entre tarefas e o impacto da migração das tarefas nos seus fluxos de comunicação, aproximando o modelo da realidade. O desenvolvimento de tal análise possibilita o estudo preliminar de algoritmos heurísticos de mapeamento de tarefas, capazes de mapear conjuntos de tarefas levando em consideração migrações de tarefas e comunicação entre tarefas em um modelo de escalonamento semi-particionado.

APA, Harvard, Vancouver, ISO, and other styles

33

Gutiérrez, García José Javier. "Planificación, análisis y optimización de sistemas distribuidos de tiempo real estricto." Doctoral thesis, Universidad de Cantabria, 1995. http://hdl.handle.net/10803/10638.

Full text

Abstract:

La Tesis presenta el desarrollo de una metodología de análisis y diseño de sistemas distribuidos de tiempo real estricto, y su aplicación a una implementación práctica en lenguaje Ada.Se han optimizado los métodos existentes para la planificación y análisis de sistemas distribuidos de tiempo real mediante un algoritmo heurístico para la asignación de prioridades, y la aplicación del algoritmo de servidor esporádico a la planificación de redes de comunicación de tiempo real. También se ha ampliado el campo de aplicación del análisis a sistemas más complejos en los que existe sincronización por intercambio de eventos o paso de mensajes.Se ha demostrado que la metodología propuesta se puede implementar en sistemas de tiempo real prácticos, a través de su aplicación a sistemas distribuidos programados en lenguaje Ada.
The Thesis presents a methodology to analyze and design distributed real-time systems, and its application to a practical implementation.Existing methods for scheduling and analyzing distributed real-time systems have been optimized through a new heuristic algorithm for assigning priorities, and with the application of the sporadic server algorithm for scheduling real-time communication networks. The area of application of the analysis has been extended to more complex systems, like those with synchronization through event exchange or message passing.It has been demonstrated that the proposed methodology can be implemented in practical real-time systems, through the application to a distributed system programmed in the Ada language.

APA, Harvard, Vancouver, ISO, and other styles

34

Brau, Guillaume. "Intégration de l'analyse de propriétés non-fonctionnelles dans l'Ingénierie Dirigée par les Modèles pour les systèmes embarqués." Thesis, Toulouse, ISAE, 2017. http://www.theses.fr/2017ESAE0004/document.

Full text

Abstract:

L'ingénierie des systèmes embarqués repose sur deux activités complémentaires : la modélisation d'une part permet dereprésenter le système, l'analyse d’autre part permet d'évaluer les diverses propriétés non-fonctionnelles (par exemple despropriétés temporelles via l'analyse d’ordonnancement temps réel). Cette thèse s'intéresse à l'intégration entre ces modèleset analyses: comment appliquer une analyse sur une modèle ? Comment gérer le processus d’analyse ? La première partie de cette thèse présente une approche globale afin de répondre à ces questions. Cette approche s'organise autour de quatre couches applicatives: (1) les modèles qui représentent le système, (2) les accesseurs qui permettent d'extraire des données à partir d'un modèle, (3) l'analyse qui traite des données en entrée pour produire des données ou propriétés en sortie, (4) des contrats qui décrivent les interfaces d'une analyse et permettent d'orchestrer le processus d'analyse. La seconde partie de cette thèse est dédiée à l'expérimentation de cette approche sur des systèmes réels provenant du domaine aérospatial : un drone, un robot explorateur et un système de gestion de vol. Nous montrons que les accesseurs permettent d’appliquer diverses analyses d’ordonnancement temps réel sur des modèles architecturaux hétérogènes, par exemples décrits avec le standard industriel AADL (Architecture Analysis and Design Language) ou le nouveau langage dirigé par le temps CPAL (Cyber-Physical Action Language). En outre, nous montrons que les contrats peuvent être utilisés afin d’automatiser des procédures d'analyse complexes : quelle analyse peut être appliquée sur unmodèle ? Quelles analyses remplissent les objectifs visés ? Peut-on combiner des analyses ? Y-a-t-il des interférences entreles analyses ? Etc
The engineering of embedded systems relies on two complementary activities: modeling on the one hand enables torepresent the system, analysis on the other hand makes it possible to evaluate the various non-functional properties (forexample, temporal properties with the real-time scheduling analysis). This thesis deals with the integration between thesemodels and analyses: how to apply an analysis on a model? How to manage the analysis process? The first part of this thesis presents a comprehensive approach to answer these questions. This approach is based on four application layers: (1) models to represent the system, (2) accessors to extract data from a model, (3) analyses to computeoutput data and/or properties from input data (4) contracts to represent the analysis interfaces and orchestrate the analysisprocess. The second part of this thesis deals with the experimentation of this approach with concrete systems coming fromthe aerospace: a drone, an exploratory robot and a flight management system. We demonstrate that the accessors enable toapply various real-time scheduling analyses on heterogeneous architectural models, for example written with the industrystandard AADL (Architecture Analysis and Design Language) or the new time-triggered language CPAL (Cyber-PhysicalAction Language). In addition, contracts make it possible to automate complex analysis procedures: which analysis can beapplied on a given model? Which are the analyses that meet a given goal? Are there analyses to be combined? Are thereinterferences between analyses? Etc

APA, Harvard, Vancouver, ISO, and other styles

35

Strub, Guillaume. "Modeling, Identification and Control of a Guided Projectile in a Wind Tunnel." Thesis, Mulhouse, 2016. http://www.theses.fr/2016MULH8492/document.

Full text

Abstract:

Cette thèse présente une méthodologie de conception et d’évaluation de lois de commande pour projectiles guidés, au moyen d’un prototype placé dans une soufflerie via un support autorisant plusieurs degrés de liberté en rotation. Ce dispositif procure un environnement permettant à la fois de caractériser expérimentalement le comportement de la munition et d’évaluer les performances des lois de commande dans des conditions réalistes, et est mis en œuvre pour l’étude d’autopilotes de tangage et de lacet, à vitesse fixe et à vitesse variable, pour un prototype de projectile empenné piloté par canards. La modélisation d’un tel système aboutit à un modèle non-linéaire dépendant de nombreuses conditions de vol telles que la vitesse et des angles d’incidence. Les méthodes de séquencement de gain basées sur des linéarisations d’un modèle non-linéaire sont couramment employées dans l’industrie pour la commande de ce type de systèmes. A cette fin, le système est représenté au moyen d’une famille de modèles linéaires dont les paramètres sont directement estimés à partir de données recueillies sur le dispositif expérimental. L’observation du comportement à différents points de vol permet de considérer la vitesse de l’air comme unique variable de séquencement. La synthèse des différents contrôleurs est réalisée au moyen d’une méthode H∞ multi-objectifs à ordre et structure fixes, afin de garantir la stabilité et la robustesse du système vis-à-vis d’incertitudes liées à la variation du point de fonctionnement. Ces lois de commande sont alors validées au moyen d’analyses de robustesse, puis par leur implémentation sur le dispositif expérimental. Les résultats obtenus lors d’essais en soufflerie correspondent aux simulations numériques et sont conformes aux spécifications attendues
This work presents a novel methodology for flight control law design and evaluation, using a functional prototype installed in a wind tunnel by the means of a support structure allowing multiple rotational degrees of freedom. This setup provides an environment allowing experimental characterization of the munition’s behavior, as well as for flight control law evaluation in realistic conditions. The design and validation of pitch and yaw autopilots for a fin-stabilized, canard-guided projectile is investigated, at fixed and variable airspeeds. Modeling such a system leads to a nonlinear model depending on numerous flight conditions such as the airspeed and incidence angles. Linearization-based gain scheduling techniques are widely employed in the industry for controlling this class of systems. To this end, the system is represented with a family of linear models whose parameters are directly estimated from experimentally collected data. Observation of the projectile’s behavior for different operating points indicates the airspeed can be considered as the only scheduling variable. Controller synthesis is performed using a multi-objective, fixed-order, fixed-structure H∞ technique in order to guarantee the stability and robustness of the closed-loop against operating point uncertainty. The obtained control laws are validated with robustness analysis techniques and are then implemented on the experimental setup, where wind-tunnel tests results correlate with numerical simulations and conform to the design specifications

APA, Harvard, Vancouver, ISO, and other styles

36

Nguyen, Viet Anh. "Cache-conscious off-line real-time scheduling for multi-core platforms : algorithms and implementation." Thesis, Rennes 1, 2018. http://www.theses.fr/2018REN1S004/document.

Full text

Abstract:

Les temps avancent et les applications temps-réel deviennent de plus en plus gourmandes en ressources. Les plate-formes multi-cœurs sont apparues dans le but de satisfaire les demandes des applications en ressources, tout en réduisant la taille, le poids, et la consommation énergétique. Le challenge le plus pertinent, lors du déploiement d'un système temps-réel sur une plate-forme multi-cœur, est de garantir les contraintes temporelles des applications temps réel strict s'exécutant sur de telles plate-formes. La difficulté de ce challenge provient d'une interdépendance entre les analyses de prédictabilité temporelle. Cette interdépendance peut être figurativement liée au problème philosophique de l'œuf et de la poule, et expliqué comme suit. L'un des pré-requis des algorithmes d'ordonnancement est le Pire Temps d'Exécution (PTE) des tâches pour déterminer leur placement et leur ordre d'exécution. Mais ce PTE est lui aussi influencé par les décisions de l'ordonnanceur qui va déterminer quelles sont les tâches co-localisées ou concurrentes propageant des effets sur les caches locaux et les ressources physiquement partagées et donc le PTE. La plupart des méthodes d'analyse pour les architectures multi-cœurs supputent un seul PTE par tâche, lequel est valide pour toutes conditions d'exécutions confondues. Cette hypothèse est beaucoup trop pessimiste pour entrevoir un gain de performance sur des architectures dotées de caches locaux. Pour de telles architectures, le PTE d'une tâche est dépendant du contenu du cache au début de l'exécution de la dite tâche, qui est lui-même dépendant de la tâche exécutée avant et ainsi de suite. Dans cette thèse, nous proposons de prendre en compte des PTEs incluant les effets des caches privés sur le contexte d’exécution de chaque tâche. Nous proposons dans cette thèse deux techniques d'ordonnancement ciblant des architectures multi-cœurs équipées de caches locaux. Ces deux techniques ordonnancent une application parallèle modélisée par un graphe de tâches, et génèrent un planning statique partitionné et non-préemptif. Nous proposons une méthode optimale à base de Programmation Linéaire en Nombre Entier (PLNE), ainsi qu'une méthode de résolution par heuristique basée sur de l'ordonnancement par liste. Les résultats expérimentaux montrent que la prise en compte des effets des caches privés sur les PTE des tâches réduit significativement la longueur des ordonnancements générés, ce comparé à leur homologue ignorant les caches locaux. Afin de parfaire les résultats ainsi obtenus, nous avons réalisé l'implémentation de nos ordonnancements dirigés par le temps et conscients du cache pour un déploiement sur une machine Kalray MPPA-256, une plate-forme multi-cœur en grappes (clusters). En premier lieu, nous avons identifié les challenges réels survenant lors de ce type d'implémentation, tel que la pollution des caches, la contention induite par le partage du bus, les délais de lancement d'une tâche introduits par la présence de l'ordonnanceur, et l'absence de cohérence des caches de données. En second lieu, nous proposons des stratégies adaptées et incluant, dans la formulation PLNE, les contraintes matérielles ; ainsi qu'une méthode permettant de générer le code final de l'application. Enfin, l'évaluation expérimentale valide la correction fonctionnelle et temporelle de notre implémentation pendant laquelle nous avons pu observé le facteur le plus impactant la longueur de l'ordonnancement: la contention
Nowadays, real-time applications are more compute-intensive as more functionalities are introduced. Multi-core platforms have been released to satisfy the computing demand while reducing the size, weight, and power requirements. The most significant challenge when deploying real-time systems on multi-core platforms is to guarantee the real-time constraints of hard real-time applications on such platforms. This is caused by interdependent problems, referred to as a chicken and egg situation, which is explained as follows. Due to the effect of multi-core hardware, such as local caches and shared hardware resources, the timing behavior of tasks are strongly influenced by their execution context (i.e., co-located tasks, concurrent tasks), which are determined by scheduling strategies. Symetrically, scheduling algorithms require the Worst-Case Execution Time (WCET) of tasks as prior knowledge to determine their allocation and their execution order. Most schedulability analysis techniques for multi-core architectures assume a single WCET per task, which is valid in all execution conditions. This assumption is too pessimistic for parallel applications running on multi-core architectures with local caches. In such architectures, the WCET of a task depends on the cache contents at the beginning of its execution, itself depending on the task that was executed before the task under study. In this thesis, we address the issue by proposing scheduling algorithms that take into account context-sensitive WCETs of tasks due to the effect of private caches. We propose two scheduling techniques for multi-core architectures equipped with local caches. The two techniques schedule a parallel application modeled as a task graph, and generate a static partitioned non-preemptive schedule. We propose an optimal method, using an Integer Linear Programming (ILP) formulation, as well as a heuristic method based on list scheduling. Experimental results show that by taking into account the effect of private caches on tasks’ WCETs, the length of generated schedules are significantly reduced as compared to schedules generated by cache-unaware scheduling methods. Furthermore, we perform the implementation of time-driven cache-conscious schedules on the Kalray MPPA-256 machine, a clustered many-core platform. We first identify the practical challenges arising when implementing time-driven cache-conscious schedules on the machine, including cache pollution cause by the scheduler, shared bus contention, delay to the start time of tasks, and data cache inconsistency. We then propose our strategies including an ILP formulation for adapting cache-conscious schedules to the identified practical factors, and a method for generating the code of applications to be executed on the machine. Experimental validation shows the functional and the temporal correctness of our implementation. Additionally, shared bus contention is observed to be the most impacting factor on the length of adapted cache-conscious schedules

APA, Harvard, Vancouver, ISO, and other styles

37

Marouf, Mohamed. "Ordonnancement temps réel dur multiprocesseur tolérant aux fautes appliqué à la robotique mobile." Phd thesis, Ecole Nationale Supérieure des Mines de Paris, 2012. http://pastel.archives-ouvertes.fr/pastel-00720934.

Full text

Abstract:

Nous nous sommes intéressés dans cette thèse au problème d'ordonnancement temps réel dur multiprocesseur tolérant aux fautes pour des tâches non préemptives périodiques strictes pouvant être combinées avec des tâches préemptives. Nous avons proposé des solutions à ce problème et les avons implantées dans le logiciel SynDEx puis nous les avons testées sur une application de suivi de véhicules électriques CyCabs. Nous avons d'abord présenté un état de l'art sur les systèmes temps réel embarqués et plus précisément sur l'ordonnancement classique monoprocesseur et multiprocesseur de tâches préemptives périodiques. Comme nous nous intéressons aux applications de contrôle/commande temps réel critiques, les traitements de capteurs/actionneurs et les traitements de commande de procédés ne doivent pas avoir de gigue. Pour ces raisons nous avons aussi présenté un état de l'art sur l'ordonnancement des tâches non-préemptives périodiques strictes. Par ailleurs nous avons présenté un état de l'art sur la tolérance aux fautes. Comme nous nous sommes intéressés aux fautes matérielles, nous avons présenté les deux types de redondances : logicielle et matérielle. Les analyses d'ordonnançabilité existantes de tâches non préemptives périodiques strictes dans le cas monoprocesseur ayant de faibles taux de succès d'ordonnancement, nous avons proposé une nouvelle analyse d'ordonnançabilité. Nous avons présenté une stratégie d'ordonnancement qui consiste à ordonnancer une tâche candidate avec un ensemble de tâches déjà ordonnancée. Nous avons utilisé cette stratégie pour ordonnancer des tâches harmoniques et non harmoniques, et nous avons proposé des nouvelles conditions d'ordonnançabilité. Afin d'améliorer le taux de succès d'ordonnancement de tâches non préemptives périodiques strictes, nous avons proposé de garder certaines tâches non préemptives périodiques strictes et d'y ajouter des tâches préemptives périodiques non strictes ne traitant ni les entrées/sorties ni le contrôle/commande. Nous avons ensuite étudié le problème d'ordonnancement multiprocesseur selon une approche partitionnée. Ce problème est résolu en utilisant trois algorithmes. Le premier algorithme effectue une analyse d'ordonnançabilité monoprocesseur et assigne chaque tâche sur éventuellement plusieurs processeurs. Le deuxième algorithme transforme le graphe de tâches dépendantes en un graphe déroulé où chaque tâche est répétée un nombre de fois égal au rapport entre le PPCM des autres périodes et sa période. Le troisième algorithme exploite les résultats des deux algorithmes précédents pour choisir sur quel processeur ordonnancer une tâche et calculer sa date de début d'exécution. Nous avons ensuite proposé d'étendre l'étude d'ordonnançabilité temps réel multiprocesseur précédente pour qu'elle soit tolérante aux fautes de processeurs et de bus de communication. Nous avons proposé un algorithme qui permet de transformer le graphe de tâches dépendantes en y ajoutant des tâches et des dépendances de données répliques et des tâches de sélection permettant de choisir la réplique de tâches allouée à un processeur non fautif. Nous avons étudié séparément les problèmes de tolérance aux fautes pour des processeurs, des bus de communication, et enfin des processeur et des bus de communication. Finalement nous avons étendu les trois algorithmes vus précédemment d'analyse d'ordonnançabilité, de déroulement et d'ordonnancement afin qu'ils soient tolérants aux fautes. Nous avons ensuite présenté les améliorations apportées au logiciel SynDEx tant sur le plan de l'analyse d'ordonnançabilité et l'algorithme d'ordonnancement, que sur le plan de la tolérance aux fautes. Finalement nous avons présenté les travaux expérimentaux concernant l'application de suivi de CyCabs. Nous avons modifié l'architecture des CyCabs en y intégrant des microcontrôleurs dsPICs et nous avons testé la tolérance aux fautes de dsPICs et du bus CAN sur une application de suivi de CyCab.

APA, Harvard, Vancouver, ISO, and other styles

38

Brüggen, Georg von der [Verfasser], Jian-Jia [Akademischer Betreuer] Chen, and Robert I. [Gutachter] Davis. "Realistic scheduling models and analyses for advanced real-time embedded systems / Georg von der Brüggen ; Gutachter: Robert I. Davis ; Betreuer: Jian-Jia Chen." Dortmund : Universitätsbibliothek Dortmund, 2019. http://d-nb.info/1203373074/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Paolillo, Antonio. "Optimisation of Performance Metrics of Embedded Hard Real-Time Systems using Software/Hardware Parallelism." Doctoral thesis, Universite Libre de Bruxelles, 2018. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/277427.

Full text

Abstract:

Optimisation of Performance Metrics of Embedded Hard Real-Time Systems using Software/Hardware Parallelism. Nowadays, embedded systems are part of our daily lives.Some of these systems are called safetycritical and have strong requirements in terms of safety and reliability.Additionally, these systems must have a long autonomy, good performance and minimal costs.Finally, these systems must exhibit predictable behaviour and provide their results within firm deadlines.When these different constraints are combined in the requirement specifications of a modern product, classic design techniques making use of single core platforms are not sufficient.Academic research in the field of real-time embedded systems has produced numerous techniques to exploit the capabilities of modern hardware platforms.These techniques are often based on using parallelism inherently present in modern hardware to improve the system performance while reducing the platform power dissipation.However, very few systems existing on the market are using these state-of-the-art techniques.Moreover, few of these techniques have been validated in the context of practical experiments.In this thesis, we realise the study of operating system level techniques allowing to exploit hardware parallelism through the implementation of parallel software in order to boost the performance of target applications and to reduce the overall system energy consumption while satisfying strict application timing requirements.We detail the theoretical foundations of the ideas applied in the dissertation and validate these ideas through experimental work.To this aim, we use a new Real-Time Operating System kernel written in the context of the creation of a spin-off of the Université libre de Bruxelles.Our experiments are based on the execution of applications on the operating system which run on a real-world platform for embedded systems.Our results show that, compared to traditional design techniques, using parallel and power-aware scheduling techniques in order to exploit hardware and software parallelism allows to execute embedded applications with substantial savings in terms of energy consumption.We present future and ongoing research work that exploit the capabilities of recent embedded platforms.These platforms combine multi-core processors and reconfigurable hardware logic, allowing further improvements in performance and energy consumption.
Optimisation de Métriques de Performances de Systèmes Embarqués Temps Réel Durs par utilisation du Parallélisme Logiciel et Matériel. De nos jours, les systèmes embarqués font partie intégrante de notre quotidien.Certains de ces systèmes, appelés systèmes critiques, sont soumis à de fortes contraintes de fiabilité et de robustesse.De plus, des contraintes de coûts, d’autonomie et de performances s’additionnent à la fiabilité.Enfin, ces systèmes doivent très souvent respecter des délais très stricts de façon prédictible.Lorsque ces différentes contraintes sont combinées dans le cahier de charge d’un produit, les techniques classiques de conception consistant à utiliser un seul cœur d’un processeur ne suffisent plus.La recherche académique dans le domaine des systèmes embarqués temps réel a produit de nombreuses techniques pour exploiter les plate-formes modernes.Ces techniques sont souvent basées sur l’exploitation du parallélisme inhérent au matériel pour améliorer les performances du système et la puissance dissipée par la plate-forme.Cependant, peu de systèmes existant sur le marché exploitent ces techniques de la littérature et peu de ces techniques ont été validées dans le cadre d’expériences pratiques.Dans cette thèse, nous réalisons l’étude des techniques, au niveau du système d’exploitation, permettant l’exploitation du parallélisme matériel par l’implémentation de logiciels parallèles afin de maximiser les performances et réduire l’impact sur l’énergie consommée tout en satisfaisant les contraintes temporelles strictes du cahier de charge applicatif. Nous détaillons les fondements théoriques des idées qui sont appliquées dans la dissertation et nous les validons par des travaux expérimentaux.A ces fins, nous utilisons le nouveau noyau d’un système d’exploitation écrit dans le cadre de la création d’une spin-off de l’Université libre de Bruxelles.Nos expériences, basées sur l’exécution d’applications sur le système d’exploitation qui s’exécute lui-même sur une plate-forme embarquée réelle, montre que l’utilisation de techniques d’ordonnancement exploitant le parallélisme matériel et logiciel permet de larges économies d’énergie consommée lors de l’exécution d’applications embarquées.De futurs travaux en cours de réalisation sont présentés.Ceux-ci exploitent des plate-formes innovantes qui combinent processeurs multi-cœurs et matériel reconfigurable, permettant d’aller encore plus loin dans l’amélioration des performances et les gains énergétiques.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

40

Poczekajlo, Xavier. "Ordonnancement efficace de systèmes embarqués temps réel strict sur plates-formes hétérogènes." Doctoral thesis, Universite Libre de Bruxelles, 2020. https://dipot.ulb.ac.be/dspace/bitstream/2013/313478/3/TOC.pdf.

Full text

Abstract:

Les systèmes embarqués sont de plus en plus présents dans notre quotidien, à l’instar des téléphones ou des équipements des voitures modernes. Les systèmes embarqués modernes utilisent des plates-formes de plus en plus complexes. Après avoir longtemps utilisé un seul processeur, les plates-formes modernes peuvent désormais contenir plusieurs processeurs. Depuis quelques années, afin de continuer à améliorer la performance de ces systèmes à moindre coût, certaines de ces plates-formes embarquent désormais plusieurs processeurs différents, parfois même capables de modifier rapidement leurs caractéristiques pendant l’exécution du système. C’est ce qu’on appelle des plates-formes hétérogènes.Cette thèse traite de l’ordonnancement d’applications temps réel strict pour des plates-formes hétérogènes reconfigurables. Établir une polituqe d’ordonnancement consiste à garantir l’exécution d’ensembles de tâches récurrentes, avec le respect des contraintes temporelles de chaque tâche. Dans un contexte de temps réel strict, une tâche doit nécessairement être pleinement exécutée avant son échéance. Tout retard pourrait compromettre la sécurité du système ou des utilisateurs.Produire un ordonnancement temps réel strict efficace pour de telles plates-formes hétérogènes est particulièrement difficile. En effet, la vitesse d’exécution d’un processeur d’une telle plates-forme dépend à la fois du type du processeur et de la tâche exécutée. Cela rend les tâches difficilement interchangeables et augmente ainsi considérablement la complexité des polituqes d’ordonnancement. De plus, le coût d’une migration – le déplacement d’une tâche en cours d’exécution – d’un processeur à un autre est élevé, ce qui peut rendre les polituqes d’ordonnancement peu efficaces en pratique.Dans cette thèse, deux voies sont explorées pour tirer parti des possibilités offertes par ces plates-formes hétérogènes. Tout d’abord, en proposant un ordonnanceur dit global, qui permet une utilisation théorique de l’entièreté de la plates-forme. Pour atteindre cet objectif, nous isolons différents sous-problèmes, en suivant un schéma établi par la littérature existante. Pour chaque sous-problème, nous proposons une amélioration significative par rapport à l’état de l’art. L’ensemble constitue un nouvel ordonnanceur. Une évaluation empirique montre que ses performances sont bien supérieures à celles des ordonnanceurs existants. De plus, la polituqe d’ordonnancement proposée a une meilleure applicabilité, car elle réduit le nombre de migrations d’un processeur à un autre.Une deuxième voie explorée est le paradigme d’application dite multimode. Nous proposons ici le premier modèle où le matériel comme le logiciel peuvent être modifiés pendant l’exécution de l’application, afin de s’adapter au contexte dans lequel elle se trouve. Enfin, deux nouveaux protocoles utilisant ce modèle sont proposés et évalués. Il est montré théoriquement et empiriquement que ces protocoles présentent une faible complexité et de bonnes performances, et correspondent donc au besoin d’applications réelles.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

41

Fauberteau, Frédéric. "Sûreté temporelle pour les systèmes temps réel multiprocesseurs." Phd thesis, Université Paris-Est, 2011. http://tel.archives-ouvertes.fr/tel-00668537.

Full text

Abstract:

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations (i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance (augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources.

APA, Harvard, Vancouver, ISO, and other styles

42

Mallangi, Siva Sai Reddy. "Low-Power Policies Based on DVFS for the MUSEIC v2 System-on-Chip." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229443.

Full text

Abstract:

Multi functional health monitoring wearable devices are quite prominent these days. Usually these devices are battery-operated and consequently are limited by their battery life (from few hours to a few weeks depending on the application). Of late, it was realized that these devices, which are currently being operated at fixed voltage and frequency, are capable of operating at multiple voltages and frequencies. By switching these voltages and frequencies to lower values based upon power requirements, these devices can achieve tremendous benefits in the form of energy savings. Dynamic Voltage and Frequency Scaling (DVFS) techniques have proven to be handy in this situation for an efficient trade-off between energy and timely behavior. Within imec, wearable devices make use of the indigenously developed MUSEIC v2 (Multi Sensor Integrated circuit version 2.0). This system is optimized for efficient and accurate collection, processing, and transfer of data from multiple (health) sensors. MUSEIC v2 has limited means in controlling the voltage and frequency dynamically. In this thesis we explore how traditional DVFS techniques can be applied to the MUSEIC v2. Experiments were conducted to find out the optimum power modes to efficiently operate and also to scale up-down the supply voltage and frequency. Considering the overhead caused when switching voltage and frequency, transition analysis was also done. Real-time and non real-time benchmarks were implemented based on these techniques and their performance results were obtained and analyzed. In this process, several state of the art scheduling algorithms and scaling techniques were reviewed in identifying a suitable technique. Using our proposed scaling technique implementation, we have achieved 86.95% power reduction in average, in contrast to the conventional way of the MUSEIC v2 chip’s processor operating at a fixed voltage and frequency. Techniques that include light sleep and deep sleep mode were also studied and implemented, which tested the system’s capability in accommodating Dynamic Power Management (DPM) techniques that can achieve greater benefits. A novel approach for implementing the deep sleep mechanism was also proposed and found that it can obtain up to 71.54% power savings, when compared to a traditional way of executing deep sleep mode.
Nuförtiden så har multifunktionella bärbara hälsoenheter fått en betydande roll. Dessa enheter drivs vanligtvis av batterier och är därför begränsade av batteritiden (från ett par timmar till ett par veckor beroende på tillämpningen). På senaste tiden har det framkommit att dessa enheter som används vid en fast spänning och frekvens kan användas vid flera spänningar och frekvenser. Genom att byta till lägre spänning och frekvens på grund av effektbehov så kan enheterna få enorma fördelar när det kommer till energibesparing. Dynamisk skalning av spänning och frekvens-tekniker (såkallad Dynamic Voltage and Frequency Scaling, DVFS) har visat sig vara användbara i detta sammanhang för en effektiv avvägning mellan energi och beteende. Hos Imec så använder sig bärbara enheter av den internt utvecklade MUSEIC v2 (Multi Sensor Integrated circuit version 2.0). Systemet är optimerat för effektiv och korrekt insamling, bearbetning och överföring av data från flera (hälso) sensorer. MUSEIC v2 har begränsad möjlighet att styra spänningen och frekvensen dynamiskt. I detta examensarbete undersöker vi hur traditionella DVFS-tekniker kan appliceras på MUSEIC v2. Experiment utfördes för att ta reda på de optimala effektlägena och för att effektivt kunna styra och även skala upp matningsspänningen och frekvensen. Eftersom att ”overhead” skapades vid växling av spänning och frekvens gjordes också en övergångsanalys. Realtidsoch icke-realtidskalkyler genomfördes baserat på dessa tekniker och resultaten sammanställdes och analyserades. I denna process granskades flera toppmoderna schemaläggningsalgoritmer och skalningstekniker för att hitta en lämplig teknik. Genom att använda vår föreslagna skalningsteknikimplementering har vi uppnått 86,95% effektreduktion i jämförelse med det konventionella sättet att MUSEIC v2-chipets processor arbetar med en fast spänning och frekvens. Tekniker som inkluderar lätt sömn och djupt sömnläge studerades och implementerades, vilket testade systemets förmåga att tillgodose DPM-tekniker (Dynamic Power Management) som kan uppnå ännu större fördelar. En ny metod för att genomföra den djupa sömnmekanismen föreslogs också och enligt erhållna resultat så kan den ge upp till 71,54% lägre energiförbrukning jämfört med det traditionella sättet att implementera djupt sömnläge.

APA, Harvard, Vancouver, ISO, and other styles

43

陳, 暘., and Yang Chen. "REAL TIME SCHEDULING AND ANALYSIS FOR CAN MESSAGES WITH OFFSETS." Thesis, 2012. http://hdl.handle.net/2237/16424.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Sunil, Kumar P. R. "Design and Analysis of Real-time Message Scheduling under FlexRay Protocol." Thesis, 2017. http://etd.iisc.ernet.in/2005/3629.

Full text

Abstract:

A typical automobile system consists of many Electronic Control Units (ECUs) for the purposes of safety, comfort, and entertainment applications. FlexRay is a high bandwidth protocol for such automotive requirements, which facilitates communication between distributed ECUs. This thesis addresses some of the issues associated with the design and implementation of the FlexRay protocol. The number of ECUs that are used in automobiles has an increasing trend to implement more functionality, which demands more bandwidth. By minimizing bandwidth requirements for servicing a given workload of periodic and sporadic real-time tasks, one can connect more ECUs to the same FlexRay bus. With this motivation, the first part of this thesis proposes new algorithms for minimizing bandwidth usage of ECUs in both the static and the dynamic segments of FlexRay. FlexRay provides a time-triggered static segment for the transmission of time critical periodic messages. The static segment consists of a fixed number of static slots each with a fixed duration. The duration of the static slot and the number of slots are design parameters which need to be fixed so as to meet all the deadline requirements of the workload in the application. The static slot duration can be minimized by packing the signals into message frames, while respecting scheduling constraints. Since message frames also contain overhead information, the duration of message frames can be optimized by proper signal packing, based on the network utilization constraints of individual ECUs. The thesis proposes a novel algorithm for packing of signals into message frames and fixing the static slot duration so that the total duration of the static segment is minimized. The dynamic segment of FlexRay caters to the transmission of event-triggered signals. A novel algorithm has been proposed to obtain the minimum duration of the dynamic segment while meeting the deadline constraints of all sporadic messages in their worst-case arrival instances. We also extend all these algorithms to the case of slot multiplexing scheme provided by FlexRay 3.0. Modern automobiles provide infotainment and in-car telemetry functions, which produce a high volume of soft deadline messages. This makes the problem of analyzing scheduling algorithms for such traffic important. The dynamic segment of the FlexRay cycle is used for transmission of such soft deadline messages. The second part of this thesis addresses the issue of analyzing the quality of performance in servicing of the soft deadline tasks in the FlexRay protocol. Two quality measures, namely, the average delay in servicing of the soft deadline tasks and the fraction of tasks that miss their deadlines, are considered. The generation of different soft deadline messages is modeled as independent Poisson processes. The generated messages are queued in different queues and are serviced according to pre-assigned priorities for different queues as per the FlexRay protocol. By analyzing this multiple queue model under some mild assumptions, upper bounds on the arrival rates for different messages are derived so that all the queues are stable. Analytical expressions are also derived for average delay and for deadline miss ratio. The correctness of these approximate analytical expressions are demonstrated through simulation studies.

APA, Harvard, Vancouver, ISO, and other styles

45

Guasque, Ortega Ana. "Study, analysis and new scheduling proposals in partitioned real-time systems." Doctoral thesis, 2020. http://hdl.handle.net/10251/135279.

Full text

Abstract:

[ES] En nuestra vida cotidiana, cada vez más ordenadores controlan nuestro entorno: teléfonos móviles, procesos industriales, asistencia a la conducción, etc. Todos estos sistemas presentan requisitos estrictos para garantizar un comportamiento adecuado. En muchos de estos sistemas, cumplir con las restricciones de tiempo es un factor tan importante como el resultado lógico de los cálculos. Desde hace aproximadamente 40 años, los sistemas en tiempo real son muy atractivos en el campo de la computación y hoy en día se aplican en áreas de gran alcance como aplicaciones industriales, aplicaciones aeroespaciales, telecomunicaciones, electrónica de consumo, etc. Algunos retos a abordar en el campo del tiempo real son el determinismo y la predecibilidad del comportamiento temporal del sistema. En este sentido, garantizar la ejecución del programa y los tiempos de respuesta del sistema son requisitos esenciales que deben cumplirse estrictamente a través de estrategias apropiadas de planificación de tareas. Además, las arquitecturas multiprocesador se están volviendo más populares debido al hecho de que las capacidades de procesamiento y los recursos computacionales de los sistemas están aumentando. Un estudio reciente estima que existe una tendencia creciente entre las arquitecturas multiprocesador a combinar diferentes niveles de criticidad en el mismo sistema. En este sentido, proporcionar aislamiento entre las aplicaciones es extremadamente necesario. La tecnología particionada es capaz de lidiar con este propósito. Además, la gestión de la energía es un problema relevante en los sistemas en tiempo real. Muchos sistemas empotrados de tiempo real, como dispositivos portátiles o robots móviles que requieren baterías, buscan encontrar técnicas que reduzcan el consumo de energía y, como consecuencia, aumenten la vida útil de sus baterías. También se obtienen claros beneficios operativos, financieros, monetarios y ambientales al minimizar el consumo de energía. Con todo ello, este trabajo aborda el problema de planificabilidad y contribuye al estudio de las nuevas técnicas de planificación en sistemas particionados de tiempo real. Estas técnicas proporcionan el tiempo mínimo para planificar de manera factible conjuntos de tareas. Además, se proponen técnicas de asignación para sistemas multiprocesador cuyo objetivo principal es reducir el consumo de energía del sistema global. Finalmente, se presentan los resultados obtenidos así como los trabajos futuros relacionados con este trabajo
[CAT] En la nostra vida quotidiana, cada vegada més ordenadors controlen el nostre entorn: telèfons mòbils, processos industrials, assistència a la conducció, etc. Tots aquests sistemes presenten requisits estrictes per a garantir un comportament adequat. En molts d' aquests sistemes, complir amb les restriccions de temps és un factor tan important com el resultat lògic dels càlculs. Des de fa aproximadament 40 anys, els sistemes en temps real són molt atractius en el camp de la computació i hui dia s' apliquen en àrees de gran abast com a aplicacions industrials, aplicacions aeroespacials, telecomunicacions, electrònica de consum, etc. Alguns reptes a abordar en el camp del temps real són el determinisme i la predictibilitat del comportament temporal del sistema. En aquest sentit, garantir l'execució del programa i els temps de resposta del sistema són requisits essencials que han de complir-se estrictament a través d'estratègies apropiades de planificació de tasques. A més, les arquitectures multiprocessador s'estan tornant més populars a causa del fet que les capacitats de processament i els recursos computacionals dels sistemes estan augmentant. Un estudi recent estima que existeix una tendència creixent entre les arquitectures multiprocessador a combinar diferents nivells de criticitat en el mateix sistema. En aquest sentit, proporcionar aïllament entre les aplicacions és extremadament necessari. La tecnologia particionada és capaç de bregar amb aquest propòsit. A més, la gestió de l'energia és un problema rellevant en els sistemes en temps real. Molts sistemes embebits de temps real, com a dispositius portàtils o robots mòbils que requereixen bateries, busquen trobar tècniques que reduïsquen el consum d'energia i, com a conseqüència, augmenten la vida útil de les seues bateries. També s'obtenen clars beneficis operatius, financers, monetaris i ambientals en minimitzar el consum d'energia. Amb tot això, aquest treball aborda el problema de planificabilitat i contribueix a l'estudi de les noves tècniques de planificació en sistemes particionats de temps real. Aquestes tècniques proporcionen el temps mínim per a planificar de manera factible conjunts de tasques. A més, es proposen tècniques d'assignació per a sistemes multiprocessador l'objectiu principal del qual és reduir el consum d'energia del sistema global. Finalment, es presenten els resultats obtinguts així com els treballs futurs relacionats amb aquest treball.
[EN] In our everyday lives, more and more computers are controlling our environment: mobile phones, industrial processes, driving assistance, etc. All these systems present strict requirements to ensure proper behaviour. In many of these systems, the time at which the action is delivered is as important as the logical result of the computation. About 40 years ago, real-time systems began to attract attention in computing field and nowadays are applied in wide ranging areas as industrial applications, aerospace, telecommunication applications, consumer electronics, etc. Some real-time challenges that must be addressed are determinism and predictability of the temporal behaviour of the system. In this sense, to guarantee program execution and system response times are essential requirements that must be strictly met through appropriate task scheduling strategies. Furthermore, multiprocessor architectures are becoming more popular due to the fact that processing capabilities and computational resources are increasing. A recent study estimates that there is an increasing tendency among multiprocessor architectures to combine different levels of criticality in the same system. In this sense, to provide isolation between applications is extremely required. Partitioned technology is able to deal with this purpose. In addition, energy management is a relevant problem in real-time systems. Many real-time embedded systems, as wearable devices or mobile robots that require batteries, seek to find techniques that reduce the energy consumption and, as a consequence, increase the lifetime of their batteries. Also clear operational, financial, monetary and environmental gains are reached when minimizing energy consumption. Faced with all this, this work addresses the problem of schedulability and contributes to the study of new scheduling techniques in partitioned real-time systems. These techniques provide the minimum time to feasible schedule tasks sets. Moreover, allocation techniques for multicore systems whose main objective is to reduce the energy consumption of the overall system are also proposed. Finally, some of the obtained results are discussed as conclusions and future works are introduced.
Guasque Ortega, A. (2019). Study, analysis and new scheduling proposals in partitioned real-time systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/135279
TESIS

APA, Harvard, Vancouver, ISO, and other styles

46

Li, Jian Xi, and 李建熹. "SU-27 dynamic analysis, gain-scheduling design and real-time simulation." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/32869052015427864158.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Varma, Nikhil Kumar. "Formal analysis of fault tolerant real time multiprocessor allocation and scheduling protocols." Thesis, 2004. http://spectrum.library.concordia.ca/8084/1/MQ94714.pdf.

Full text

Abstract:

Dependable real-time distributed systems rely on allocation and scheduling protocols to satisfy stringent resource and timing constraints. As these protocols have both dependability and real-time attributes, verification of such composite services warrants a rigorous and formal levels of assurance for their correctness. The wide acceptance of formal techniques in the design and development of dependable real-time systems is limited because, most of these formal theories for real-time scheduling have been developed without much regard for their further reuse. This makes the formal specifications and their proof constructs in general difficult to reuse, and to verify or analyze similar or related protocols. To expand the utility of formal techniques, this thesis explores the possibility of effectively defining and then reusing formal theories in order to simplify verification and analysis for a wide spectrum of dependable real-time protocols. We present a modular formal analysis of a fault-tolerant version of a real-time task allocation and scheduling policies. The main aim is to develop a library of formal theories for the identified modules for real-time and dependable services which could be systematically, and if required, repeatedly used to develop different and new composite dependable multiprocessor real-time allocation and scheduling protocols. We demonstrate a rigorous and tool-assisted formal analysis of three multiprocessor real time fault tolerant allocation and scheduling protocols for both periodic and aperiodic task models using the concept of reuasability of previously defined theories. We show the reduced effort in the analysis and verification process by reusing the previously formalized theories. Formal analyses of these protocols have been performed using a mechanized theorem proving environment, called PVS from SRI labs.

APA, Harvard, Vancouver, ISO, and other styles

48

Tseng, Shin-Mu, and 曾新穆. "Design and Analysis of Value-Based Scheduling Policies for Real- Time Database Systems." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/11422700742986440550.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Huang, Tsung-Fu, and 黃宗甫. "Analysis of Scheduling Algorithm for Real-time Services with QoS Guarantee on HFC Network." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/97921373281335421244.

Full text

Abstract:

碩士
國立臺灣科技大學
電機工程系
90
The Data Over Cable Service Interface Specification (DOCSIS) protocol enables the delivery of IP (Internet protocol) traffic over the hybrid fiber coaxial (HFC) network with higher data rate. The availability of greater bandwidth also enables the delivery of high quality audio and video services. Such real-time services require bound delay characteristic. In DOCSIS v1.1, it defines five upstream service flow scheduling services to provide the quality of service (QoS) guarantee and each scheduling service has its associated QoS parameters. According to the parameters, the cable modem termination system (CMTS) must assign the bandwidth in the upstream channel at appropriate time. In order to meet the QoS requirements, the CMTS must adopt a scheduling algorithm among difference services to reduce QoS violation probabiltity. In this paper, we propose a novel QoS scheduling mechanism, which is called EDF (earliest deadline first) scheduling algorithm, to transport real-time service flow. It is shown, via simulation using VoIP (voice over IP) and video conference flow, that proposed scheduling service provides significant improvements as compared to the traditional FCFS (first come first serve) scheduling service, with regard to QoS violation ratio and packet drop ratio.

APA, Harvard, Vancouver, ISO, and other styles

50

Wang, Jia-Chi, and 王家祺. "Design and Analysis of FBPQ: an Efficient Real-time Scheduling Scheme in ATM Networks." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/17610423142114481135.

Full text

Abstract:

碩士
國立交通大學
電信研究所
85
With the growing use of the Internet, the network evolution trends to be wide band and intelligent. In the existing multimedia network, many type of servicerequires real-time delivery, such as EDI, teleconference and video on demand.So, besides upgrading the hardware processing speed, the future network must provide real-time communication and efficient resource management. The ATM network was originally developed for use in the telecommunication network, but dueto it's capability of providng QoS guarantee, it has been used for real- time communication in data communication networks. In order to provide real-time QoS guarantee in ATM network, an additional scheduling module must be employed to handle the diverse types of traffic. In this thesis, we develop the frame-based priority queue(FBPQ) which combines the framing strategy and priority queueing concept to develop an efficient cell scheduling scheme for real-time QoS requirements. Considering implementation complexity, we use both the static and dynamic priority scheduling to implement the FBPQ. We show that FSPQ(frame static priority queue) can enlarge the admission region of the original frame based scheme(S&G, TCRM) and with proper buffering scheme, it may outperform the rate-monotonic scheme. FDPQ(frame dynamic priority queue) adopt the framing mechanism as a rate controller and use earlist-deadline-first service schedulingdiscipline to achieve the user's QoS reqirments. Both of our proposed schemesare efficient and simple, and thus are very at tractive for hardware implementation in high-speed network.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Real-time scheduling analysis'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles