The advent of performance-critical services such as online brokerage and e-commerce, as well as QoS-sensitive services such as streaming multimedia, makes existing FIFO servers incapable of meeting application QoS req...
详细信息
The advent of performance-critical services such as online brokerage and e-commerce, as well as QoS-sensitive services such as streaming multimedia, makes existing FIFO servers incapable of meeting application QoS requirements. Re-designing server code to support QoS provisioning, on the other hand, is costly and time-consuming. To remedy this problem, we propose a new QoS-provisioning approach that does not require modification of server and QoS code. We develop a middleware, called qContracts, that can be transparently interposed between the server process and the operating system to achieve performance differentiation and soft QoS guarantees. The middleware enables reuse of existing legacy software in QoS-sensitive contexts, and off-loads QoS management concerns from future real-time service programmers. As an example, we show how the Apache web server is endowed with QoS support using qContracts on UNIX. Experimental results show the efficacy of the middleware in achieving the contracted QoS, while imposing less than 1% overhead.
In this paper we experimentally evaluate the performance of a parametrized branch-and-bound (B&B) algorithm for scheduling real-time tasks an a multiprocessor system. The objective of the B&B algorithm is to m...
详细信息
In this paper we experimentally evaluate the performance of a parametrized branch-and-bound (B&B) algorithm for scheduling real-time tasks an a multiprocessor system. The objective of the B&B algorithm is to minimize the maximum task lateness in the system. We show that a last-in-first-out (LIFO) vertex selec.ion rule clearly outperforms the commonly used least-lower-bound (LLB) rule for the scheduling problem. We also present a new adaptive lower-bound cost function that greatly improves the performance of the B&B algorithm when parallelism in the application cannot be fully exploited on the multiprocessor architecture. Finally, we evaluate a set of heuristic strategies, one of which generates near-optimal results with performance guarantees and another of which generates approximate results without performance guarantees.
In a realtime system, tasks are constrained by global end to end deadlines. In order to cater for high task schedulability, these deadlines must be distributed over component subtasks in an intelligent way. Existing ...
详细信息
In a realtime system, tasks are constrained by global end to end deadlines. In order to cater for high task schedulability, these deadlines must be distributed over component subtasks in an intelligent way. Existing methods for automatic distribution of end to end deadlines are all based on the assumption that task assignments are entirely known beforehand. This assumption is not necessarily valid for large realtime systems. Furthermore, most task assignment strategies require information on deadlines in order to make good assignments, thus forming a circular dependency between deadline distribution and task assignment. We present a heuristic approach that performs deadline distribution prior to task assignment. The deadline distribution problem is presented in the context of large distributed hard realtime systems with relaxed locality constraints, where schedulability analysis must be performed offline, and only a subset of the tasks are constrained by predetermined assignments to specific processors. Using experimental results we identify drawbacks of previously proposed techniques, and then show that our solution provides significantly better performance for a large variety of system configurations.
Numerous methods have been proposed to integrate real-time and non-real-time services of the timed-token medium access control (MAC) protocol. One of the key issues in tailoring the timed-token protocol for real-time ...
详细信息
Numerous methods have been proposed to integrate real-time and non-real-time services of the timed-token medium access control (MAC) protocol. One of the key issues in tailoring the timed-token protocol for real-time applications is the synchronous bandwidth allocation (SBA) problem whose objective is to meet both the protocol and deadline constraints. Several non-optimal local SBA schemes and two optimal global schemes have been proposed. Local SBA schemes use only information available locally to each node, and are thus preferred to global schemes because of their lower network-management overhead. However, we formally prove, using the technique of adversary argument, that there does not exist any optimal local SBA scheme. During the preparation for this proof, we also derive a timing property that generalizes the previous findings about the cycle-time properties of the timed-token protocol.< >
Digital computers embedded in critical applications such as flight controls should be equipped with appropriate fault-tolerance schemes to ensure their reliable and safe operation in the presence of component failures...
详细信息
Digital computers embedded in critical applications such as flight controls should be equipped with appropriate fault-tolerance schemes to ensure their reliable and safe operation in the presence of component failures. System reconfiguration, which enhances reliability by dynamically using spatial redundancy, is generally the most time-consuming fault-/error- handling stage. The reconfiguration latency, defined as the time taken for reconfiguring a system upon failure detection or mode change, depends on many parameters, including the size of application programs and data, the CPU and memory speed, built-in testing capabilities, the type of spares to use, the system architecture, and the reconfiguration strategy used. In this paper, we classify the reconfiguration techniques into four types: reconfigurable duplication, reconfigurable N-modular redundancy (NMR), backup sparing, and graceful degradation. For each type of reconfiguration, we evaluate the reconfiguration latency by using several parameters accounting for the aforementioned parameters, and determine if this type of reconfiguration can meet the application required latency.< >
The authors propose a new loading sharing (LS) algorithm for real-time applications that accounts for the effect of future task arrivals on locating the best receiver for each unguaranteed task. The LS algorithm minim...
详细信息
The authors propose a new loading sharing (LS) algorithm for real-time applications that accounts for the effect of future task arrivals on locating the best receiver for each unguaranteed task. The LS algorithm minimizes not only the probability of transferring an unguaranteed task T to an incapable node with Bayesian analysis, but also the probability that a remote node fails to guarantee T because of future arrivals of higher-laxity tasks with queuing analysis. All parameters needed for a node's LS decision are collected/estimated online using time-stamped region-change broadcasts and Bayesian estimation. Simulation results show that the proposed LS algorithm outperforms other existing algorithms in minimizing the probability of dynamic failure, task collisions, and excessive task transfers. The performance improvement becomes more pronounced as the degree of system heterogeneity increases.< >
An analytical model for the performance evaluation of asynchronous hypercubes is presented. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second-generation hypercube systems. ...
详细信息
An analytical model for the performance evaluation of asynchronous hypercubes is presented. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second-generation hypercube systems. Probability of blocking and average message delay are discussed. The communication traffic to find the probability of blocking is the starting point. The traffic analysis can capture any message destination distribution. The average message delay that consists of two parts is found. The analysis is extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated.< >
暂无评论