Les systèmes embarqués temps réel nécessitent une analyse temporelle pour valider leur comportement temporel.Afin de réduire le coût de développement, l’analyse doit être effectuée à une phase précoce au moment de la modélisationpour détecter les anomalies de conception. L’analyse d’ordonnançabilité est une des analyses temporelles qui permettentde s’assurer du bon fonctionnement du système conçu. Elle est issue de la théorie de l’ordonnancement temps réel.Plusieurs méthodes et tests analytiques ont été proposés par la communauté académique mais peu sont les tests adoptéspar les industriels. En effet, l’utilisation des tests d’analyse exige une large connaissance des travaux de recherches - misà jour régulièrement - afin de choisir la méthode la plus adaptée aux systèmes conçus pour les valider ou les dimensionnerpour le cas des systèmes qui sont en cours de conception.Cette thèse s’intéresse à cette utilisation minimaliste de la théorie de l’ordonnancement dans l’industrie, et propose dessolutions d’aide à la décision basées sur l’ingénierie dirigée par les modèles. Nos solutions visent à augmenter l’applicabilitéde la théorie de l’ordonnancement, à faciliter le choix des tests appropriés et à réduire le surdimensionnement qui peutêtre généré au moment de la conception. Ces solutions sont implémentées dans un Framework appelé MoSaRT offrantdes fonctionnalités pour les concepteurs (modeleurs et analystes) afin d’améliorer le processus de conception des systèmestemps réel en vue de leur ordonnançabilité. / Real-time embedded systems need to be analyzed at an early stage in order to detect temporal vulnerabilities. Indeed,software development costs are sharply impacted by wrong design choices made in the early stages of development, inparticular during the design phase, but often detected after the implementation. The schedulability analysis is one of themain analyses required to ensure the timing correctness of a real-time system. Indeed, the real-time scheduling theoryhas been devoted to propose different models providing several levels of expressiveness, and different analytical methodswith different levels of accuracy. The utilization of the real-time scheduling theory in practical cases could be profitable.Unfortunately, it is not sufficiently applied and research results have been exploited in an industrial context only to amodest extent to date. Actually, a difficulty faced by the real-time designers is to find the appropriate analysis testshelping to validate properly the system and also to reduce the over-dimensioning. This thesis is interested in the chasmexisting between real-time design community and real-time analysis community. The purpose of our work is to fill thegap between the modeling of real-time systems and the scheduling analysis. Then, we propose a decision aiding solutionbased on model-driven engineering. Our solution is dedicated (i) to increase the usage of the real-time scheduling theory,(ii) to facilitate the scheduling analysis tests choice and (iii) to reduce the pessimism during the design phase of real-timesystems.Our proposal is embodied as a framework unifying the designers and analysts efforts. The framework called MoSaRToffers a design language very close to the taxonomy of real-time scheduling theory. Moreover, MoSaRT provides ananalysis repository concept to enhance the applicability of the scheduling theory and also to improve the way designerscheck their designs.

As embedded software and platforms become more complicated, many safety properties are left to simulation and testing. MRICDF is a formal polychronous language used to guarantee certain safety properties and alleviate the burden of software development and testing. We propose real-time extensions to MRICDF so that temporal properties of embedded systems can also be proven. We adapt the extended precedence encoding technique of Prelude and expand upon current schedulability analysis techniques for multi-periodic real-time systems. / Master of Science

Cyber-Physical Systems (CPS) are widely deployed in critical applications which are subject to strict timing constraints. To ensure correct timing behavior, much of the effort has been dedicated to the development of validation and verification methods for CPS (e.g., system models and their timing and schedulability analysis). As CPS is becoming increasingly complex, there is an urgent need for efficient optimization techniques that can aid the design of large-scale systems. Specifically, techniques that can find good design options in a reasonable amount of time while meeting all the timing and other critical requirements are becoming vital. However, the current mindset is to use existing schedulability analysis and optimization techniques for the design optimization of time-critical CPS. This has resulted in two issues in today's CPS design: 1) Existing timing and schedulability analysis are very difficult and inefficient to be integrated into well-established optimization frameworks such as mathematical programming; 2) New system models and timing analysis are being developed in a way that is increasingly unfriendly to optimization. Due to these difficulties, existing practice for optimization mostly relies on meta or ad-hoc heuristics, which suffers either from sub-optimality or limited applicability. In this dissertation, we seek to address these issues and explore two new directions for developing optimization algorithms for time-critical CPS. The first is to develop {em optimization-oriented timing analysis}, that are efficient to formulate in mathematical programming framework. The second is a domain-specific optimization framework. The framework leverages domain-specific knowledge to provide methods that abstract timing analysis into a simple mathematical form. This allows to efficiently handle the complexity of timing analysis in optimization algorithms. The results on a number of case studies show that the proposed approaches have the potential to significantly improve upon scalability (several orders of magnitude faster) and solution quality, while being applicable to various system models, timing analysis techniques, and design optimization problems in time-critical CPS. / Doctor of Philosophy / Cyber-Physical Systems (CPS) tightly intertwine computing units and physical plants to accomplish complex tasks such as control and monitoring. They are often deployed in critical applications subject to strict timing constraints. For example, many control applications and tasks are required to finished within bounded latencies. To guarantee such timing correctness, much of the effort has been dedicated to studying methods for delay and latency estimation. These techniques are known as schedulability analysis/timing analysis. As CPS becomes increasingly complex, there is an urgent need for efficient optimization techniques that can aid the design of large-scale and correct CPS. Specifically, techniques that can find good design options in reasonable amount of time while meeting all the timing and other critical requirements are becoming vital. However, most of the existing schedulability analysis are either non-linear, non-convex, non-continuous or without closed form. This gives significant challenge for integrating these analysis into optimization. In this dissertation, we explore two new paradigm-shifting approaches for developing optimization algorithms for the design of CPS. Experimental evaluations on both synthetic and industrial case studies show that the new approaches significantly improve upon existing optimization techniques in terms of scalability and quality of solution.

Le cloud computing est l’accomplissement du rêve de nombreux informaticiens désireux de transformer et d’utiliser leurs logiciels comme de simples services, rendant ces derniers plus attractifs et séduisants pour les utilisateurs. Dans le cadre de cette thèse, les technologies du cloud computing sont présentées, ainsi que les principaux défis que ce dernier va rencontrer dans un futur proche, notamment pour la gestion et l’analyse des données. A partir de la théorie moderne d'ordonnancements des tâches, nous avons proposé une gestion hiérarchique d’ordonnancements des tâches qui satisfait aux différentes demandes des cloud services. D’un point de vue théorique, nous avons principalement répondu à trois questions cruciales de recherche. Premièrement, nous avons résolu le problème de l'allocation des ressources au niveau de l’utilisateur. Nous avons en particulier proposé des algorithmes basés sur la théorie des jeux. Avec une méthode Bayésienne d’apprentissage, l'allocation des ressources atteint l'équilibre de Nash parmi les utilisateurs en compétition malgré une connaissance insuffisante des comportements de ces derniers. Deuxièmement, nous avons abordé le problème d'ordonnancements des tâches au niveau du système. Nous avons trouvé un nouveau seuil pour l'utilisation d’ordonnancements des tâches en ligne, considérant le dispositif séquentiel de MapReduce. Ce seuil donne de meilleurs résultats que les méthodes existantes dans l’industrie. Troisièmement, nous avons défini un critère de comparaison pour les tests d’ordonnancements de tâches en ligne. Nous avons proposé un concept de fiabilité d'essai pour évaluer la probabilité qu'un ensemble de tâches aléatoires passe un essai donné. Plus la probabilité est grande, plus la fiabilité est élevée. Un test présentant une grande fiabilité garantit une bonne utilisation du système. D’un point de vue pratique, nous avons développé un simulateur basé sur le concept de MapReduce. Ce simulateur offre un environnement directement utilisable par les chercheurs familiers avec SimMapReduce, leur permettant de s’affranchir des aspects informatiques d’implémentations et leur permettant notamment de se concentrer sur les aspects algorithmiques d’un point de vue théorique. / Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Real-time system refers to the computing, communication, and information system with deadline requirements. To meet these deadline requirements, most systems use a mechanism known as the schedulability test which determines whether each of the admitted tasks can meet its deadline. A new task will not be admitted unless it passes the schedulability test. Schedulability tests can be either direct or indirect. The utilization based schedulability test is the most common schedulability test approach, in which a task can be admitted only if the total system utilization is lower than a pre-derived bound. While the utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this dissertation, we develop a general framework that allows effective derivation of schedulability bounds for different workload patterns and schedulers. We introduce an analytical model that is capable of describing a wide range of tasks' and schedulers'€™ behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform proof of schedulability bounds. We introduce two types of workload constraint functions, s-shaped and r-shaped, for flexible and accurate characterization of the task workloads. We derive parameterized schedulability bounds for arbitrary static priority schedulers, weighted round robin schedulers, and timed token ring schedulers. Existing utilization bounds for these schedulers are obtained from the closed-form formula by direct assignment of proper parameters. Some of these results are applied to a cluster computing environment. The results developed in this dissertation will help future schedulability bound analysis by supplying a unified modeling framework and will ease the implementation practical real-time systems by providing a set of ready to use bound results.

No description available.

Real-time system refers to the computing, communication, and information system with deadline requirements. To meet these deadline requirements, most systems use a mechanism known as the schedulability test which determines whether each of the admitted tasks can meet its deadline. A new task will not be admitted unless it passes the schedulability test. Schedulability tests can be either direct or indirect. The utilization based schedulability test is the most common schedulability test approach, in which a task can be admitted only if the total system utilization is lower than a pre-derived bound. While the utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this dissertation, we develop a general framework that allows effective derivation of schedulability bounds for different workload patterns and schedulers. We introduce an analytical model that is capable of describing a wide range of tasks' and schedulers'€™ behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform proof of schedulability bounds. We introduce two types of workload constraint functions, s-shaped and r-shaped, for flexible and accurate characterization of the task workloads. We derive parameterized schedulability bounds for arbitrary static priority schedulers, weighted round robin schedulers, and timed token ring schedulers. Existing utilization bounds for these schedulers are obtained from the closed-form formula by direct assignment of proper parameters. Some of these results are applied to a cluster computing environment. The results developed in this dissertation will help future schedulability bound analysis by supplying a unified modeling framework and will ease the implementation practical real-time systems by providing a set of ready to use bound results.

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.

Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Data aggregation is extensively used in data management systems nowadays. Based on a data aggregation taxonomy named DAGGTAX, we propose an analytic process to evaluate the run-time platform and time-related parameters of Data Aggregation Processes (DAP) in a real-time system design, which can help designers to eliminate infeasible design decisions at early stage. The process for data aggregation design and analysis mainly includes the following outlined steps. Firstly, the user needs to specify the variation of the platform and DAP by figuring out the features of the system and time-related parameters respectively. Then, the user can choose one combination of the variations between the features of the platform and DAP, which forms the initial design of the system. Finally, apply the analytic method for feasibility analysis by schedulability analysis techniques. If there are no infeasibilities found in the process, then the design can be finished. Otherwise, the design must be altered from the run-time platform and DAP design stage, and the schedulability analysis will be applied again for the revised design until all the infeasibilities are fixed. In order to help designers to understand and describe the system and do feasibility analysis, we propose a new UML (Unified Modeling Language) profile that extends UML with concepts related to real-time data aggregation design. These extensions aim to accomplish the conceptual modeling of a real-time data aggregation. In addition, the transferring method based on UML profile to transfer the data aggregation design into a task model is proposed as well. In the end of the thesis, a case study, which applies the analytic process to analyze the architecture design of an environmental monitoring sensor network, is presented as a demonstration of our research.