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>

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