Recentes pesquisas têm investigado modelos de garantia de desempenho baseados em restrições temporais, parametrizadas pela especificação de limites superiores de tempo médio de resposta. Este trabalho estende o desenvolvimento da política de escalonamento de temporeal EBS, aplicável a esse problema, apresentando um mecanismo de controle de admissão de requisições em aplicações com tais requisitos. A abordagem baseia-se em um método adaptativo capaz de administrar o nível de degradação do sistema, de forma a isolar o efeito do comportamento de um usuário sobre a qualidade de serviço oferecida aos demais usuários. Também é proposta uma modificação na implementação do algoritmo originalmente definido para a EBS, de forma a diminuir sua complexidade temporal. Resultados de simulação demonstram a efetividade dos mecanismos propostos / In recent research works performance guarantee models based on temporal constraints with specified response-time upper bounds have been investigated. This work extends the development of the EBS real-time scheduling policy, applicable to this problem, by proposing an admission control mechanism. The introduced approach is based on an adaptive model which, based on the system degradation level, tries to isolate the impact of the behavior of a given user upon the quality of service offered to the other users. Its also proposed a new algorithm to reduce the complexity order of the original EBS implementation. Simulation results illustrate the effectiveness of proposed methods

A Qualidade de Serviço oferece aos Sistemas de Tempo Real garantias das restrições temporais de aplicações tais como comércio eletrônico, vídeo conferência, telemedicina, entre outras que necessitam de confiabilidade e desempenho para efetivação dos seus serviços. Contribuições nessas áreas têm focado a provisão de qualidade de serviço em termos absolutos, descritos num limite máximo de média de tempo de atendimento, destinado às aplicações Web. Todavia, o controle de qualidade baseado em tempo médio de resposta durante todo o período de serviço prestado, não restringe os tempos de resposta quanto a sua dispersão. Um valor médio razoável pode ser resultado da combinação de tempos de resposta elevados e pequenos. O objetivo deste trabalho é reduzir a dispersão dos atrasos em sistemas escalonados com a política EBS (Exigency Based Scheduling ), definidos pela diferença positiva entre o tempo de resposta da requisição do usuário e o valor médio contratado, em um modelo de contrato determinado por janelas deslizantes de operações. A EBS é uma política de escalonamento que define um modelo de contratos de tempo médio de resposta avaliados durante todo o tempo de serviço. Avalia-se a dispersão dos atrasos, pois, é preferível que haja a possibilidade dos tempos de resposta ficarem substancialmente abaixo da média contratada. Os resultados são obtidos utilizando métodos de simulação dos algoritmos desenvolvidos durante o projeto / Quality of Service offers Real Time Systems guarantees the time constraints of applications such as electronic commerce, video conferencing, telemedicine, among others that need reliable and effective performance for their services. Contributions in these areas have made the provision of service quality in absolute terms, out of a maximum average time of service for Web applications. However, quality control based on average response time for the entire period of service, does not restrict the response time to their dispersion. A reasonable average value may be the result of the combination of response times of high and low. Objective of this research is reduce the delays dispersion in systems scheduled with policy EBS (Exigency Based Scheduling), defined by the positive difference between the response time of user request and the average contract value, in a model contract by a sliding operation windows. The EBS is a scheduling policy that defines a contracts model for an average response time evaluated throughout the time of service. We analyze the delays dispersion because it is preferable that there is the possibility of response time becomes substantially below the average contracted. Results are obtained using simulation methods of the algorithms developed during the project

<p>Embedded computer systems have become ubiquitous. They are used in a wide spectrum of applications, ranging from household appliances and mobile devices to vehicle controllers and medical equipment. This dissertation deals with design and verification of embedded systems, with a special emphasis on the real-time facet of such systems, where the time at which the results of the computations are produced is as important as the logical values of these results. Within the class of real-time systems two categories, namely hard real-time systems and soft real-time systems, are distinguished and studied in this thesis.</p><p>First, we propose modeling and verification techniques targeted towards hard real-time systems, where correctness, both logical and temporal, is of prime importance. A model of computation based on Petri nets is defined. The model can capture explicit timing information, allows tokens to carry data, and supports the concept of hierarchy. Also, an approach to the formal verification of systems represented in our modeling formalism is introduced, in which model checking is used to prove whether the system model satisfies its required properties expressed as temporal logic formulas. Several strategies for improving verification efficiency are presented and evaluated.</p><p>Second, we present scheduling approaches for mixed hard/soft real-time systems. We study systems that have both hard and soft real-time tasks and for which the quality of results (in the form of utilities) depends on the completion time of soft tasks. Also, we study systems for which the quality of results (in the form of rewards) depends on the amount of computation allotted to tasks. We introduce quasi-static techniques, which are able to exploit at low cost the dynamic slack caused by variations in actual execution times, for maximizing utilities/rewards and for minimizing energy.</p><p>Numerous experiments, based on synthetic benchmarks and realistic case studies, have been conducted in order to evaluate the proposed approaches. The experimental results show the merits and worthiness of the techniques introduced in this thesis and demonstrate that they are applicable on real-life examples.</p>

<p>Systems controlled by embedded computers become indispensable in our lives and can be found in avionics, automotive industry, home appliances, medicine, telecommunication industry, mecatronics, space industry, etc. Fast, accurate and flexible performance estimation tools giving feedback to the designer in every design phase are a vital part of a design process capable to produce high quality designs of such embedded systems.</p><p>In the past decade, the limitations of models considering fixed task execution times have been acknowledged for large application classes within soft real-time systems. A more realistic model considers the tasks having varying execution times with given probability distributions. No restriction has been imposed in this thesis on the particular type of these functions. Considering such a model, with specified task execution time probability distribution functions, an important performance indicator of the system is the expected deadline miss ratio of tasks or task graphs.</p><p>This thesis proposes two approaches for obtaining this indicator in an analytic way. The first is an exact one while the second approach provides an approximate solution trading accuracy for analysis speed. While the first approach can efficiently be applied to monoprocessor systems, it can handle only very small multi-processor applications because of complexity reasons. The second approach, however, can successfully handle realistic multiprocessor applications. Experiments show the efficiency of the proposed techniques.</p> / Report code: LiU-Tek-Lic-2002:58.

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.

We present a formally specified event specification language (Solicitor). Solicitor is suitable for real-time systems, since it results in resource-predictable and efficient event monitors. In event monitoring, event expressions defined in an event specification language control the monitoring by matching incoming streams of event occurrences against the event expressions. When an event expression has a complete set of matching event occurrences, the event type that this expression defines has occurred. Each event expression is specified by combining contributing event types with event operators such as sequence, conjunction, disjunction; contributing event types may be primitive, representing happenings of interest in a system, or composite, specified by event expressions. The formal specification of Solicitor is based on a formal schema that separates two important aspects of an event expression; these aspects are event operators and event contexts. The event operators aspect addresses the relative constraints between contributing event occurrences, whereas the event contexts aspect addresses the selection of event occurrences from an event stream with respect to event occurrences that are used or invalidated during event monitoring. The formal schema also contains an abstract model of event monitoring. Given this formal specification, we present realization issues of, a time complexity study of, as well as a proof of limited resource requirements of event monitoring. We propose an architecture for resource-predictable and efficient event monitoring. In particular, this architecture meets the requirements of realtime systems by defining how event monitoring and tasks are associated. A declarative way of specifying this association is proposed within our architecture. Moreover, an efficient memory management scheme for event composition is presented. This scheme meets the requirements of event monitoring in distributed systems. This architecture has been validated by implementing an executable component prototype that is part of the DeeDS prototype. The results of the time complexity study are validated by experiments. Our experiments corroborate the theory in terms of complexity classes of event composition in different event contexts. However, the experimental platform is not representative of operational real-time systems and, thus, the constants derived from our experiments cannot be used for such systems.

Embedded computer systems have become ubiquitous. They are used in a wide spectrum of applications, ranging from household appliances and mobile devices to vehicle controllers and medical equipment. This dissertation deals with design and verification of embedded systems, with a special emphasis on the real-time facet of such systems, where the time at which the results of the computations are produced is as important as the logical values of these results. Within the class of real-time systems two categories, namely hard real-time systems and soft real-time systems, are distinguished and studied in this thesis. First, we propose modeling and verification techniques targeted towards hard real-time systems, where correctness, both logical and temporal, is of prime importance. A model of computation based on Petri nets is defined. The model can capture explicit timing information, allows tokens to carry data, and supports the concept of hierarchy. Also, an approach to the formal verification of systems represented in our modeling formalism is introduced, in which model checking is used to prove whether the system model satisfies its required properties expressed as temporal logic formulas. Several strategies for improving verification efficiency are presented and evaluated. Second, we present scheduling approaches for mixed hard/soft real-time systems. We study systems that have both hard and soft real-time tasks and for which the quality of results (in the form of utilities) depends on the completion time of soft tasks. Also, we study systems for which the quality of results (in the form of rewards) depends on the amount of computation allotted to tasks. We introduce quasi-static techniques, which are able to exploit at low cost the dynamic slack caused by variations in actual execution times, for maximizing utilities/rewards and for minimizing energy. Numerous experiments, based on synthetic benchmarks and realistic case studies, have been conducted in order to evaluate the proposed approaches. The experimental results show the merits and worthiness of the techniques introduced in this thesis and demonstrate that they are applicable on real-life examples.

A problem when testing timeliness of event-triggered real-time systems is that response times depend on the execution order of concurrent tasks. Conventional testing methods ignore task interleaving and timing and thus do not help determine which execution orders need to be exercised to gain confidence in temporal correctness. This thesis presents and evaluates a framework for testing of timeliness that is based on mutation testing theory. The framework includes two complementary approaches for mutation-based test case generation, testing criteria for timeliness, and tools for automating the test case generation process. A scheme for automated test case execution is also defined. The testing framework assumes that a structured notation is used to model the real-time applications and their execution environment. This real-time system model is subsequently mutated by operators that mimic potential errors that may lead to timeliness failures. Each mutated model is automatically analyzed to generate test cases that target execution orders that are likely to lead to timeliness failures. The validation of the theory and methods in the proposed testing framework is done iteratively through case-studies, experiments and proof-of-concept implementations. This research indicates that an adapted form of mutation-based testing can be used for effective and automated testing of timeliness and, thus, for increasing the confidence level in real-time systems that are designed according to the event-triggered paradigm.

This dissertation concerns testability of event-triggered real-time systems. Real-time systems are known to be hard to test because they are required to function correct both with respect to what the system does and when it does it. An event-triggered real-time system is directly controlled by the events that occur in the environment, as opposed to a time-triggered system, which behavior with respect to when the system does something is constrained, and therefore more predictable. The focus in this dissertation is the behavior in the time domain and it is shown how testability is affected by some factors when the system is tested for timeliness. This dissertation presents a survey of research that focuses on software testability and testability of real-time systems. The survey motivates both the view of testability taken in this dissertation and the metric that is chosen to measure testability in an experiment. We define a method to generate sets of traces from a model by using a meta algorithm on top of a model checker. Defining such a method is a necessary step to perform the experiment. However, the trace sets generated by this method can also be used by test strategies that are based on orderings, for example execution orders. An experimental study is presented in detail. The experiment investigates how testability of an event-triggered real-time system is affected by some constraining properties of the execution environment. The experiment investigates the effect on testability from three different constraints regarding preemptions, observations and process instances. All of these constraints were claimed in previous work to be significant factors for the level of testability. Our results support the claim for the first two of the constraints while the third constraint shows no impact on the level of testability. Finally, this dissertation discusses the effect on the event-triggered semantics when the constraints are applied on the execution environment. The result from this discussion is that the first two constraints do not change the semantics while the third one does. This result indicates that a constraint on the number of process instances might be less useful for some event-triggered real-time systems.

This thesis addresses the issues of data management in embedded systems' software. The complexity of developing and maintaining software has increased over the years due to increased availability of resources, e.g., more powerful CPUs and larger memories, as more functionality can be accommodated using these resources. In this thesis, it is proposed that part of the increasing complexity can be addressed by using a real-time database since data management is one constituent of software in embedded systems. This thesis investigates which functionality a real-time database should have in order to be suitable for embedded software that control an external environment. We use an engine control software as a case study of an embedded system. The findings are that a real-time database should have support for keeping data items up-todate, providing snapshots of values, i.e., the values are derived from the same system state, and overload handling. Algorithms are developed for each one of these functionalities and implemented in a real-time database for embedded systems. Performance evaluations are conducted using the database implementation. The evaluations show that the real-time performance is improved by utilizing the added functionality. Moreover, two algorithms for examining whether the system may become overloaded are also outlined; one algorithm for off-line use and the second algorithm for on-line use. Evaluations show the algorithms are accurate and fast and can be used for embedded systems.