**排序方式：**共有7条查询结果，搜索用时 78 毫秒

**1**

1.

Algorithms and complexity concerning the preemptive scheduling of periodic,real-time tasks on one processor

**总被引：4，自引：0，他引：4**We investigate the preemptive scheduling of periodic, real-time task systems on one processor. First, we show that when all parameters to the system are integers, we may assume without loss of generality that all preemptions occur at integer time values. We then assume, for the remainder of the paper, that all parameters are indeed integers. We then give, as our main lemma, both necessary and sufficient conditions for a task system to be feasible on one processor. Although these conditions cannot, in general, be tested efficiently (unless P=NP), they do allow us to give efficient algorithms for deciding feasibility on one processor for certain types of periodic task systems. For example, we give a pseudo-polynomial-time algorithm for synchronous systems whose densities are bounded by a fixed constant less than 1. This algorithm represents an exponential improvement over the previous best algorithm. We also give a polynomial-time algorithm for systems having a fixed number of distinct types of tasks. Furthermore, we are able to use our main lemma to show that the feasibility problem for task systems on one processor is co-NP-complete in the strong sence. In order to show this last result, we first show the Simultaneous Congruences Problem to be NP-complete in the strong sense. Both of these last two results answer questions that have been open for ten years. We conclude by showing that for incomplete task systems, that is, task systems in which the start times are not specified, the feasibility problem is

_{2}^{p}-complete.This work was supported in part by National Science Foundation Grant No. CCR-8711579. Some of these results were presented at the 15th Symposium on Mathematical Foundations of Computer Science, 1990. 相似文献2.

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical
multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.
A quantitative characterization of its worst-case performance is provided in terms of

相似文献

*resource augmentation*.Nathan Wayne Fisher (Corresponding author)Email: |

3.

Carlos C. Amaro Author Vitae Sanjoy K. Baruah Author Vitae Author Vitae Wolfgang A. Halang Author Vitae 《Automatica》2003,39(6):957-967

Temporal load-balancing—“spreading out” the executions of tasks over time—is desirable in many applications. A form of temporal load-balancing is discussed, scheduling to maximize minimum minimum global inter-completion time (MGICT-scheduling). It is shown that MGICT-scheduling is, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MGICT-scheduled. The technique is applied to a Defense Network System. Simulation results indicate that the proposed strategy achieves higher communication performance in multiprocessor systems. Specifically, our strategy significantly reduces average message delay and percentage of delayed messages. 相似文献

4.

Sanjoy K. Baruah 《Real-Time Systems》2006,32(1-2):9-20

The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several identical processors
is considered. The exact problem has previously been proven intractable even upon single processors; sufficient conditions
are presented here for determining whether a given periodic task system will meet all deadlines if scheduled non-preemptively
upon a multiprocessor platform using the earliest-deadline first scheduling algorithm.
Supported in part by the National Science Foundation (Grant Nos. CCR-9988327 and ITR-0082866).

**Sanjoy Baruah**is a professor of Computer Science at the University of North Carolina at Chapel Hill. He received his Ph.D. from the University of Texas at Austin in 1993. His research and teaching interests are in scheduling theory, real-time and safety-critical system design, and resource-allocation and sharing in distributed computing environments. 相似文献5.

Sanjoy K. Baruah 《Real-Time Systems》2003,24(1):93-128

The recurring real-time task model for hard-real-time task is studied from a feasibility-analysis perspective. This model generalizes earlier models such as the sporadic task model and the generalized multiframe task model. Algorithms are presented for the static-priority and dynamic-priority feasibility-analysis of systems of independent recurring real-time tasks in a preemptive uniprocessor environment. 相似文献

6.

Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task’s relative
deadline parameter is constrained to be no larger than its minimum inter-arrival separation. This paper introduces new analysis
techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in
this manner. For tasks with deadlines greater than their minimum inter-arrival separation, two models are considered, with
and without an implicit intra-task job precedence constraint. The new analyses yield schedulability conditions that strictly
dominate some previously proposed tests that are generally accepted to represent the current state of the art in multiprocessor
edf schedulability analysis, and permits the derivation of an improved speed-up bound.

相似文献

Sanjoy K. BaruahEmail: |

7.

This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared
to an optimal algorithm such as Earliest Deadline First (EDF).
The quantitative metric used in this comparison is the processor speedup factor, equivalent to the factor by which processor
speed needs to increase to ensure that any taskset that is schedulable according to an optimal scheduling algorithm can be
scheduled using fixed priority pre-emptive scheduling, assuming an optimal priority assignment policy. 相似文献

**1**