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.

In this thesis a replication protocol - PRiDe - is presented, which supports optimistic replication in distributed real-time databases with deterministic detection and forward resolution of transaction conflicts. The protocol is designed to emphasize node autonomy, allowing individual applications to proceed without being affected by distributed operation. For conflict management, PRiDe groups distributed operations into generations of logically concurrent and potentially conflicting operations. Conflicts between operations in a generation can be resolved with no need for coordination among nodes, and it is shown that nodes eventually converge to mutually consistent states. A generic framework for conflict resolution is presented that allows semantics-based conflict resolution policies and application-specific compensation procedures to be plugged in by the database designer and application developer. It is explained how transaction semantics are supported by the protocol, and how applications can tolerate exposure to temporary database inconsistencies. Transactions can detect inconsistent reads and compensate for inconsistencies through callbacks to application-specific compensation procedures. A tool - VADer - has been constructed, which allows database designers and application programmers to quickly construct prototype applications, conflict resolution policies and compensation procedures. VADer can be used to simulate application and database behavior, and supports run-time visualization of relationships between concurrent transactions. Thus, VADer assists the application programmer in conquering the complexity inherent in optimistic replication and forward conflict resolution.

No description available.

¡@¡@Due to wireless communication technologies, positioning technologies, and mobile computing develop quickly, mobile services are becoming practical and important on big spatiotemporal databases management. Mobile service users move only inside a spatial space, e:g: a country. They often issue the K Nearest Neighbor (kNN) query to obtain data objects reachable through the spatial database. The challenge problem of mobile services is how to efficiently answer the data objects which users interest to the corresponding mobile users. One type of kNN query problems is the order-sensitive moving kNN (order-sensitive MkNN) query problem. In the order-sensitive MkNN query problem, the query point is dynamic and unpredictable, the kNN answers should be responded in real time and sorted by the distance in the ascending order. Therefore, how to respond the kNN answers effectively, incrementally and correctly is an important issue. Nutanong et al: have proposed the V*-kNN algorithm to process the order-sensitive MkNN query. The V*-kNN algorithm uses their the V*-diagram algorithm to generate the safe region. It also uses the Incremental Rank Updates algorithm (IRU) to handle the events while the query point passing the bisectors or the boundary of the safe region. However, the V*-kNN algorithm uses the BF-kNN algorithm to retrieve NNs, which is non-incremental. This makes the search time increase while the density of the object increases. Moreover, they do not consider the situation that there are multiple objects at the same order, and the situation that there are multiple events happen in a single step. These situations may cause that the kNN answers are incorrect. Therefore, in this thesis, we propose the Hilbert curve-based kNN algorithm (HC-kNN) algorithm to process the ordersensitive MkNN query. The HC-kNN algorithm can handle the situation that there are multiple events happen in a single step. We also propose new data structure of the kNN answers. Next, we propose the Intersection of Perpendicular Bisectors algorithm (IPB) in order to handle order update events of the kNN answers. The IPB algorithm handles the situation which there are multiple objects at the same order. Finally, based on the Hilbert curve index, we propose the ONHC-kNN algorithm to get NNs incrementally and to generate the safe region. The safe region will not be affected while the density of the object increases. The safe region of our algorithm is larger than that of the V*-kNN algorithm. From our simulation result, we show that the HC-kNN algorithm provides better performance than the V*-kNN algorithm.

Crosscutting concerns are the issues in software that cannot be modularized within a software module. In this thesis work, a detailed evaluation of the use of Aspect Oriented Programming for the implementation of crosscutting concerns in embedded real-time systems is presented. The pilot Audio Switch project implementations are first evaluated in terms of software quality attributes. Then a detailed analysis of the two implementations, according to embedded real-time performance metrics has been carried out. Evaluation results show the benefits of Aspect Oriented Programming in embedded real-time systems.

Software testing is an important phase the of software development cycle which reveals faults and ensures correctness of the developed software. Distributed real-time systems are mostly safety critical systems for which the correctness and quality of the software is much more significant. However, majority of the current testing techniques have been developed for sequential (non real-time) software and there is a limited amount of research on testing distributed real-time systems. In this thesis, a proposed approach in the academic literature testing distributed real-time systems using a distributed test architecture is implemented and compared to existing software testing practices in a software development company on a case study. Evaluation of the results show the benefits of using the considered distributed test approach on distributed real-time systems in terms of software correctness.

In real time embedded systems, more and more developers are choosing the soft processor option to save money, power and area on their boards. Reconfigurability concept of the soft processor gives more options to the designer, also solving the problem of processor obsolescence. Another increasing trend is using real time operating systems (RTOSs) for microprocessors or microcontrollers. RTOSs help software developers to meet the critical deadlines of the real time environment with their deterministic and predictable behaviour. Providing service APIs and fast response times for task management, memory and interrupts / RTOSs decrease the development time of on going, and also future, projects of software developers. Comparing RTOSs on RTOS-specific benchmark criteria, called RTOS benchmarking in the literature, helps software developers to choose the appropriate RTOS for their requirements and provokes RTOS companies to strengthen their products on areas where they are weak. This study will compare three popular RTOSs on Xilinx&rsquo / s soft processor platform MicroBlaze. Xilkernel, &micro / C/OS-II and FreeRTOS are selected among nine available RTOSs for MicroBlaze and are compared against critical RTOS benchmarking criteria, which are task preemption time, task preemption time under load, get/release semaphore time, pass/receive message time, get/release fixed sized dynamic memory time, UART RS-422 message interrupt serving time, RTOS initialization time and memory footprint data. Results are interpreted using architectural concepts of the RTOSs considered.

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.

<p>The emerging need for dynamically scheduled real-time systems requires methods for handling transient overloads. Current methods have in common that they deal with transient overloads as they occur, which gives the real-time system limited time to react to the overload. In this work we enable new approaches to overload management. Our work shows that artificial neural networks (ANNs) can predict future transient overloads. This way the real-time system can prepare for a transient overload before it actually occurs. Even though the artificial neural network is not yet integrated into any system, the results show that ANNs are able to satisfactory distinguish different workload scenarios into those that cause future overloads from those that do not. Two ANN architectures have been evaluated, one standard feed-forward ANN and one recurrent ANN. These ANNs were trained and tested on sporadic workloads with different average arrival rates. At best the ANNs are able to predict up to 85% of the transient overloads in the test workload, while causing around 10% false alarms.</p>