A QoS-driven resource allocation framework based on the risk incursion function and its incorporation into a middleware architecture and mechanisms supporting distributed fault-tolerant real-time computing applications.

摘要

This dissertation attempts to significantly advance the state-of-the-art in constructing distributed real-time safety-critical applications by establishing a middleware architecture to support the execution of these applications on COTS (commercial-off-the-shelf) platforms, and by incorporating a resource allocation framework effective in meeting the application's QoS (quality-of-service) requirements such as timeliness and fault tolerance.; A QoS-driven resource allocation framework based on a QoS requirement specification scheme, named the RIF (risk incursion function) scheme which was formulated by Kane Kim in recent years, is established in this research. It is a multi-level framework that covers from the application QoS requirement specifications to the scheduling algorithms of various computation resources and supports multiple QoS dimensions such as timeliness, fault tolerance, and deadline handling. The system designers first describe the QoS requirements of a real-time application using an RIF set, and then as the application is decomposed into a group of cooperating objects, a set of RIM (risk incursion potential function) is derived from the original RIF set. The framework contains three RIPF-driven resource allocators that schedule the processor, the network bandwidth, and the I/O devices, respectively. Several resource allocation algorithms based on the derived RIPF set are proposed. First, the optimal solution is proven to be NP-hard for a RIPF-driven scheduling problem, and then some sub-optimal algorithms with polynomial execution times are proposed. According to the analysis and the experimental data obtained in this research, the RIPF-driven resource schedulers can schedule various resources at least as efficiently as the deadline-driven schedulers, and one such scheduler which can do a better job in the case where not all deadlines can be met under the deadline-driven schedulers, is also presented.; The RIF-based resource allocation framework incorporates two real-time fault tolerance schemes, PSTR/SNS (primary shadow TMO replication/supervisor-based network surveillance), which is based on previous research done by Kane Kim, and PPTR/SNS (primary passive TMO replication/SNS) schemes. PSTR/SNS is an active replication scheme with one primary and one shadow station, while PPTR/SNS is a semi-active replication scheme with one primary and one passive station. If the primary station becomes faulty, its shadow or passive partner can detect it and become a primary station in a short bounded time. The types of faults and their occurring frequencies, the operational rules, and the analysis of the fault detection and recovery time bounds of these two schemes are presented in this dissertation.{09}The main strength of these two real-time fault tolerance schemes is in that they enable relatively easy determination of tight bounds on the fault detection and recovery latency through an analysis, which is of great importance in constructing many hard-real-time applications.; A middleware architecture, named TMOSM (time-triggered message-triggered object support middleware), has been established to support the development and execution of the distributed real-time safety-critical applications. By adding the RIF-based resource allocation framework and the real-time fault tolerance schemes onto TMOSM, a middleware architecture, named ROAFTS (real-time object-oriented adaptive fault tolerance support), has been obtained. The development of several prototype applications show that the implementation of TMOSM and ROAFTS architectures can support highly efficient and economic development of complex distributed real-time applications with action timings of the precision in the range of ten milliseconds.