The paper addresses the problem of on-line scheduling of mandatory/reward-based systems in which tasks have a hard real-time mandatory part and an optional part with a non-decreasing reward function associated to its execution. Four methods, generically called SH, are proposed. They are based on the detection of singularities, special instants that appear along the execution of the system. By applying some heuristic rules, the singularities and some of the following slots are used to process optional parts. To the best of the authors' knowledge, papers published up to now on the subject of reward maximization require the functions to be continuously differentiable. Moreover, they cannot be executed on-line. On the contrary, the only requirement of the SH methods is that the functions are computable at every instant. After the system is proved to be schedulable by any of the available exact test off-line techniques, SH methods can be executed on-line. Their performance is evaluated using simulations performed on a synthetic set of tasks proposed in one of the outstanding papers on the subject and on sets of tasks randomly generated. The results are analysed and explained. The main conclusionis that , in all cases, the SH methods outperform the Best Incremental Return, often used as a yardstick.

This paper presents a probabilistic model of a client/server multimedia system based on the theory of Markov processes. The server provides different qualities of service (hard real-time, soft real-time and best-effort) and is operated using a new scheduling concept based on a hybrid deterministic/probabilistic analysis. The model also provides answers to some fundamental engineering design questions related to disk price/performance tradeoffs.

When applying the Rate Monotonic discipline to schedule a set of periodic preemptible real-time tasks, the scheduler may be able to distinguish only a limited number of priority levels. This is common in control applications using low cost embedded controllers. If the number of tasks to be scheduled is larger than the number of distinguishable levels, the set of tasks must be partitioned in a set of priority classes. RM can be used only to arbitrate conflicts between tasks of different classes. In this paper a method to determine the minimum number of priority levels necessary to schedule the set of tasks is formally proved and its complexity analysed. Finally, a systematic method to obtain all the possible partitions with the minimum number of classes, resembling the Quine's method to minimize Boolean functions, is also given.

The purpose of the paper is to present a method to validate tentative routes to establish calls with end-to-end timing-constraints in a multihop packet-switching network. Timing release counters are proposed as a mechanism to guarantee that intervals between consecutive releases of messages of the same call are not shorter than the call period. A comparative evaluation of the proposed timing release counters vs. the alternative method of stop-and-go queues is performed.

Hard real-time multitask-multiprocessor systems are one of the more important species of the taxonomic genus of distributed systems. The assignment of m preemptible periodic tasks to be executed in a set of n processors (interconnected through a communications network) is a NP-complete problem that must meet several constraints: time, allocation, resources, communication and precedence. The first three are processor-dependent and the fourth is network-dependent, but all of them can be verified as the assignment process goes on. Precedence constraints, instead, can be best verified when a tentative assignment, meeting the first four constraints, is obtained. In this paper, a formally proved method is presented to validate tentative assignments. In order to solve the problem of jitter in data arrivals, timed release counters are proposed.

A comparative evaluation of standard local area networks operating in time-constrained environments is performed. The analyzed protocols are token bus (IEEE 802.4), token ring (IEEE 802.5), and a modified version of CSMA/CD (carrier-sense multiple-access with collision detection) (IEEE 802.3). The priority disciplines necessary to make the systems crisis-free are discussed in connection with the relationships between the slot time, the number of nodes in the network, and their crisis times. In each case, the efficiency and the production of the system (in Mb/s) as functions of the length of the data field are determined.>