The preemptive scheduling of sporadic tasks on a uniprocessor is considered. A task may arrive at any time, and is characterized by a value that reflects its importance, an execution time that is the amount of processor time needed to completely execute the task, and a deadline by which the task is to complete execution. The goal is to maximize the sum of the values of the completed tasks. An online scheduling algorithm that achieves optimal performance when the system is underloaded and provides a nontrivial performance guarantee when the system is overloaded is designed. The algorithm is implemented using simple data structures to run at a cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant. Upper bounds on the best performance guarantee obtainable by an online algorithm in a variety of settings are derived.>

The authors study the performance of online algorithms in environments where no value is obtained for the partial execution of a request. They prove that no online scheduling algorithm can have a competitive factor greater than 0.25 times the optimal. They further refine this bound by considering the effect of the loading factor. Other models of task systems (for example, tasks systems consisting of many types of task requests), are considered. Similar upper bounds on the competitive factor that can be made by online scheduling algorithms in these environments are proved. It is shown that the performance bound of 0.25 is tight by means of a simple online uniprocessor scheduling algorithm has a competitive factor of 1/4. The authors extend the discussion to systems with dual processors. They show that the upper bound for the dual-processor online scheduling problem is 1/2 if all tasks have the same value density. This bound is tight if the tasks all also have zero laxity.>

Consideration is given to the preemptive scheduling of hard-real-time sporadic task systems on one processor. The authors first give necessary and sufficient conditions for a sporadic task system to be feasible (i.e., schedulable). The conditions cannot, in general, be tested efficiently (unless P=NP). They do, however, lead to a feasibility test that runs in efficient pseudo-polynomial time for a very large percentage of sporadic task systems.>

In this paper, we define a restricted logspace oracle hierarchy which turns out to be equivalent to the logspace alternation hierarchy (of Chandra, Kozen and Stockmeyer) and thus is contained within the second level of the logspace oracle heirarchy (of Ruzzo, Simon and Tompa). We then examine problems concerning various types of “fair” computations with respect to $\omega $-Finite State Machines ($\omega $-FSM’s) and $\omega $-One Counter Machines ($\omega $-1CM’s). For example, we consider the nonemptiness problem for $\omega $-FSM’s and $\omega $-1CM’s where acceptance is defined in the usual fashion, but with a fairness constraint imposed on accepting computations. Our results yield problems that are complete not only for LOGSPACE and PTIME but the second and third levels of the restricted logspace oracle hierarchy as well. As far as we know, these are the first natural problems shown to be complete for various levels of the logspace alternation hierarchy. The problems are also of independent interest. In fact, the nonemptiness problem (with fairness constraints) for w-machines has been shown to have immediate applications to the verification of concurrent finite state programs. Furthermore, the results can be used to strengthen known results concerning some related fairness problems that involve temporal logic (e.g. model checking).

Consider a network of two communicating finite state machines which exchange messages over two one-directional, unbounded channels, and assume that each machine receives the messages from its input channel based on some fixed (partial) priority relation. We address the problem of whether the communication of such a network is deadlock-free and bounded. We show that the problem is undecidable if the two machines exchange two types of messages. The problem is also undecidable if the two machines exchange three types of messages, and one of the channels is known to be bounded. However, if the two machines exchange two (or less) types of messages, and one channel is known to be bounded, then the problem becomes decidable. The problem is also decidable if one machine sends one type of message and the second machine sends two (or less) types of messages; the problem becomes undecidable if the second machine sends three types of messages. The problem is also decidable if the message priority relation is empty. We also address the problem of whether there is a message priority relation such that the priority network behaves like a FIFO network. We show that the problem is undecidable in general, and present some special cases for which the problem becomes decidable.