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.

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.

¡@¡@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.

<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>

<p>Distributed real-time databases can be used to support data sharing</p><p>for applications in wireless ad-hoc networks. In such networks, topology changes frequently and partitions may be unpredictable and last for an unbounded period. In this thesis, the existing database replication protocol PRiDe is extended to handle such long-lasting partitions. The protocol uses optimistic and detached replication to provide predictable response times in unpredictable networks and forward conflict resolution to guarantee progress.</p><p>The extension, pPRiDe, combines update and state transfer strategies. Update transfer for intra-partition communication can reduce bandwidth usage and ease conflict resolution. State transfer for inter partition conflicts removes dependency on a common state between partitions prior to the merge to apply update messages on. This makes the resource usage independent of the life span of partitions. This independence comes at the cost of global data stability guarantees and pPRiDe can thus only provide per partition guarantees. The protocol supports application specific conflict resolution routines for both</p><p>state and update conflicts. A basic simulator for mobile ad-hoc networks has been developed to validate that pPRiDe provides eventual consistency.</p><p>pPRiDe shows that a hybrid approach to change propagation strategy can be beneficial in networks where collaboration by data sharing within long lasting partitions and predictable resource usage is necessary. These types of systems already require the conflict management routines necessary for pPRiDe and can benefit from an existing protocol.</p><p>In addition to pPRiDe and the simulator this thesis provides a flexible object database suitable for future works and an implementation of PRiDe on top of that database.</p>

<p>Admission controllers in dynamic real-time systems perform traditional schedulability tests in order to determine whether incoming tasks will meet their deadlines. These tests are computationally expensive and typically run in n * log n time where n is the number of tasks in the system. An incoming task might therefore miss its deadline while the schedulability test is being performed, when there is a heavy load on the system. In our work we evaluate a new approach for admission control in firm real-time systems. Our work shows that ANNs can be used to perform a schedulability test in order to work as an admission controller in firm real-time systems. By integrating the ANN admission controller to a real-time simulator we show that our approach provides feasible performance compared to a traditional approach. The ANNs are able to make up to 86% correct admission decisions in our simulations and the computational cost of our ANN schedulability test has a constant value independent of the load of the system. Our results also show that the computational cost of a traditional approach increases as a function of n log n where n is the number of tasks in the system.</p>