Multi-mode real-time systems are those which support applications with different modes of operation, where each mode is characterized by a specific set of tasks. At run-time, such systems can, at any time, be requested to switch from its current operating mode to another mode (called "new mode") by replacing the current set of tasks with that of the new-mode. Thereby, ensuring that all the timing requirements are met not only requires that a schedulability test is performed on the tasks of each mode but also that (i) a protocol for transitioning from one mode to another is specified and (ii) a schedulability test for each transition is performed. We propose two distinct protocols that manage the mode transitions upon uniform and identical multiprocessor platforms at run-time, each specific to distinct task requirements. For each protocol, we formally establish schedulability analyses that indicate beforehand whether all the timing requirements will be met during any mode transition of the system. This is performed assuming both Fixed-Task-Priority and Fixed-Job-Priority schedulers.
Among the uniprocessor protocols, the authors of @cite_16 @cite_22 @cite_25 proposed the following protocols. @math A protocol @cite_22 where tasks are assigned priorities according to the Deadline Monotonic Scheduling algorithm and are scheduled with time offsets during the mode change only.
@cite_16 @cite_25 @cite_22
2148250519 2102879646 2099261768 1923579438
We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give a linear-time algorithm to compute all non-dominated solutions for the general uniprocessor problem and a fast arbitrarily-good approximation for multiprocessor problems when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting exact real arithmetic, including the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor. We revisit the classic problem of spreading a piece of information in a group of @math n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903---912, 1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of @math O(logn) when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization). The problem of uniprocessor scheduling under conditions of overload is investigated. The system objective is to maximize the number of tasks that complete by their deadlines. For this performance metric it is shown that, in general, any on-line algorithm may perform arbitrarily poorly as compared to a clairvoyant scheduler. Restricted instances of the general problem for which on-line schedulers ran provide a guaranteed level of performance are identified, and on-line algorithms presented for these special cases. > The main aim of this note is to show that a polynomial-time algorithm for the scheduling problem 1|r j ; p j = p| ∑ Uj given by Carlier in (1981) is incorrect. In this problem we are given n jobs with release times and deadlines. All jobs have the same processing time p. The objective is to find a non-preemptive schedule that maximizes the number of jobs completed by their deadlines. The feasibility version of this problem, where we ask whether all jobs can meet their deadlines, has been studied thoroughly. Polynomial-time algorithms for this version were first found, independently, by Simons (1978) and Carlier (1981). A faster algorithm, with running time O(n log n), was subsequently given by (1981). The elegant feasibility algorithm of Carlier (1981) is based on dynamic programming and it processes jobs from left to right on the time-axis. For each time t, it constructs a partial schedule with jobs that complete at or before time t. Carlier also attempted to apply the same technique to design a polynomial-time algorithm for the maximization version, 1|r j ; p j = p| ∑ Uj , and claimed an O(n3 log n)-time algorithm. His result is now widely cited in the literature. We show, however, that this algorithm is not correct, by giving an instance on which it produces a sub-optimal schedule. Our counter-example can be, in fact, extended to support a broader claim, namely that even the general approach from Carlier (1981) cannot yield a polynomial-time algorithm. By this general approach we mean a class of algorithms that processes the input from left to right and make decisions based on the deadline ordering, and not their exact values. The question remains as to how efficiently can we solve the scheduling problem 1|r j ; p j = p| ∑ Uj . Baptiste (1999) gave an O(n7)-time algorithm for the more general version of this problem where jobs have weights. We show how to modify his algorithm to obtain a faster, O(n5)-time algorithm for the non-weighted case. These last two results are discussed only briefly in this note. The complete proofs can be found in the full version of this paper, see (2004).