ISSN:
1432-0541
Keywords:
Algorithm
;
Computational complexity
;
Scheduling
;
Periodic task
;
Nonpreemptive task
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we study the problem of scheduling a set of periodic tasks nonpreemptively in hard-real-time systems, where it is critical for all requests of the tasks to be processed in time. A taskT is characterized by itsarrival time A, itsperiod P, and itsexecution time C. Starting fromA, a new request ofT arrives in everyP units of time, requestingC units of processing time, and itsdeadline coincides with the arrival of the next request ofT. All requests must be processed nonpreemptively to meet their corresponding deadlines. We show that the problem of testing the feasibility of a given task set {T 1,T 2,⋯,T n} satisfyingP 1+1=ki pi, wherek i; is an integer ≥ 1 for 1≤i ≤ n−1, on a single processor is NP-hard in the strong sense, even if all tasks have the same arrival time. For task sets satisfyingP i+1=K Pi, whereK is an integer ≥ 2 for 1≤ i ≤ n−1 and all tasks have the same arrival time, we present linear-time (in the number of requests) optimal scheduling algorithms as well as linear-time (in the number of tasks, i.e.,n) algorithms for testing feasibility in both uniprocessor and multiprocessor systems. We also extend our results to more general task sets.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01940882
Permalink