An Efficient Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems.
AbstractMany time-critical applications require predictable performance and tasks in these applications have deadlines to be met. In this paper, we propose an efficient algorithm for nonpreemptive scheduling of dynamically arriving real-time tasks (aperiodic tasks) in multiprocessor systems. A real-time task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of parallelization of the task. We use this parallelism in tasks to meet their deadlines and, thus, obtain better schedulability compared to nonparallelizable task scheduling algorithms. To study the effectiveness of the proposed scheduling algorithm, we have conducted extensive simulation studies and compared its performance with the myopic [8] scheduling algorithm. The simulation studies show that the schedulability of the proposed algorithm is always higher than that of the myopic algorithm for a wide variety of task parameters.
Introduction
Multiprocessors have emerged as a powerful computing means for real-time applications such as avionic
control and nuclear plant control, because of their capability for high performance and reliability. The
problem of multiprocessor scheduling is to determine when and on which processor a given task ex-
ecutes. This can be done either statically or dynamically. In static algorithms, the assignment of tasks
to processors and the time at which the tasks start execution are determined a priori. Static algorithms
This work was supported by the Indian National Science Academy, and the Department of Science and Technology.
[9, 12] are often used to schedule periodic tasks with hard deadlines. The main advantage is that, if a
solution is found, then one can be sure that all deadlines will be guaranteed. However, this approach is
not applicable to aperiodic tasks whose characteristics are not known a priori. Scheduling such tasks in
a multiprocessor real-time system requires dynamic scheduling algorithms. In dynamic scheduling [3, 8],
when new tasks arrive, the scheduler dynamically determines the feasibility of scheduling these new tasks
without jeopardizing the guarantees that have been provided for the previously scheduled tasks. Thus
for predictable executions, schedulability analysis must be done before a task's execution is begun. A
feasible schedule is generated if the timing and resource constraints of all the tasks can be satisfied, i.e.,
if the schedulability analysis is successful. Tasks are dispatched according to this feasible schedule.
@
@
@
@ @R
OEAE
OEAE
OEAE
Current schedule
Dispatch queues
Processors
Min. length of
dispatch queues
Fig.1 Parallel execution of scheduler and processors
oe
tasks
Task queue
Scheduler
Dynamic scheduling algorithms can be either distributed or centralized. In a distributed dynamic
scheduling scheme, tasks arrive independently at each processor. When a task arrives at a processor,
the local scheduler at the processor determines whether or not it can satisfy the constraints of the
incoming task. The task is accepted if they can be satisfied, otherwise the local scheduler tries to find
another processor which can accept the task. In a centralized scheme, all the tasks arrive at a central
processor called the scheduler, from where they are distributed to other processors in the system for
execution. In this paper, we will assume a centralized scheduling scheme. The communication between
the scheduler and the processors is through dispatch queues. Each processor has its own dispatch queue.
This organization, shown in Fig.1, ensures that the processors will always find some tasks in the dispatch
queues when they finish the execution of their current tasks. The scheduler will be running in parallel
with the processors, scheduling the newly arriving tasks, and periodically updating the dispatch queues.
The scheduler has to ensure that the dispatch queues are always filled to their minimum capacity (if
there are tasks left with it) for this parallel operation. This minimum capacity depends on the average
time required by the scheduler to reschedule its tasks upon the arrival of a new task [10].
It was shown in [3] that there does not exist an algorithm for optimally scheduling dynamically
arriving tasks with or without mutual exclusion constraints on a multiprocessor system. These negative
results motivated the need for heuristic approaches for solving the scheduling problem. Recently, many
heuristic scheduling algorithms [8, 13] have been proposed to dynamically schedule a set of tasks with
computation times, deadlines, and resource requirements. In [13], it was shown for uniprocessor systems
that a simple heuristic which accounts for resource requirements significantly outperforms heuristics,
such as scheduling based on Earliest Deadline First (EDF), which ignore resource requirements. For
multiprocessor systems with resource constrained tasks, a heuristic search algorithm, called myopic
scheduling algorithm, was proposed in [8]. The authors of [8] have shown that an integrated heuristic
which is a function of deadline and earliest start time of a task performs better than simple heuristics
such as the EDF, least laxity first, and minimum processing time first.
Meeting deadlines and achieving high resource utilization are the two main goals of task scheduling
in real-time systems. Both preemptive [12] and non-preemptive algorithms [8, 9] are available in the
literature to satisfy such requirements. The schedulability of a preemptive algorithm is always higher
than its non-preemptive version. However, the higher schedulability of a preemptive algorithm has to
be obtained at the cost of higher scheduling overhead. Parallelizable task scheduling, considered in this
paper, is an intermediate solution which tries to meet the conflicting requirements of high schedulability
and low overhead. Most of the known scheduling algorithms [8, 9, 12] consider that each task can be
executed on a single processor only. This may result in missing of task deadlines due to poor processor
utilization. Moreover, tasks would miss their deadlines when their total computation time requirement
is more than the deadline. These are the motivating factors to go in for parallelizable task scheduling.
However, in our simulation study, we assume that the computation times of tasks are less than their
deadlines in order to compare the results with a non-parallelizable task scheduling algorithm.
The parallelizable task scheduling problem has been studied earlier for non-real-time systems [2, 4, 11]
and is proved to be NP-complete. Many researchers, assuming sublinear task speedups due to inter-processor
communication overhead, have proposed approximation algorithms [2, 4] for the problem. A
heuristic algorithm for precedence constrained tasks with linear speedup assumption is reported in [11].
In real-time systems tasks have additional constraints, namely, ready times and deadlines. This makes
the real-time scheduling problem harder than non-real-time scheduling. In [5], with linear overhead
assumption, an optimal pseudo-polynomial time algorithm is proposed to schedule imprecise computational
tasks in real-time systems. This solution is for static scheduling and cannot be applied to the
dynamic case considered in this paper. In [1], algorithms for scheduling real-time tasks on a partitionable
hypercube multiprocessor are proposed. Here the degree of parallelization of a task is not determined
by the scheduler, rather it is specified as part of the requirements of the task itself, i.e., the scheduler
cannot change the degree of parallelization of a task for meeting its deadline. In [7], a parallelizable
task scheduling algorithm, for dynamically scheduling independent real-time tasks on multiprocessors
is proposed. This work assumes the tasks to be periodic. Most importantly, the algorithms reported
in [1, 5, 7] do not consider resource constraints among tasks which is a practical requirement in any
complex real-time system.
Parallelizable real-time task scheduling has wide applicability in problems such as robot arm dynamics
and image processing. For example, the robot arm dynamics problem consists of two computational
modules: computation of the dynamics and the solution of a linear system of equations, both of them
exhibit high degree of parallelism and have real-time constraints [14]. Similarly, a typical real-time image
processing application involves pixel-level operations such as convolution which can be carried out in
parallel on different portions of the image, and operations in a task such as matching, grouping, and
splitting of objects can also be done in parallel.
The objective of our work is to propose a dynamic scheduling algorithm which exploits parallelism
in tasks in order to meet their deadlines thereby increasing the performance of the system. The rest of
the paper is structured as follows: The task model and definitions are stated in Section 2. In Section
3, we present our dynamic scheduling algorithm and in Section 4, we evaluate its performance through
simulation studies. Finally, in Section 5, some concluding remarks are made.
Basics
2.1 Task Model
We assume that the real-time system consists of m processors, where m ? 1.
1. Each task T i is aperiodic and is characterized by its arrival time (a i ), ready time (r i ), worst case
computation time
is the worst case computation time of T i , which is the
upper bound on the computation time, when run on j processors in parallel, where 1 - j - m.
2. A task might need some resources such as data structures, variables, and communication buffers
for its execution. Every task can have two types of accesses to a resource: (a) exclusive access, in
which case, no other task can use the resource with it or (b) shared access, in which case, it can
share the resource with another task (the other task also should be willing to share the resource).
Resource conflict exists between two tasks T i and T j if both of them require the same resource and
one of the accesses is exclusive.
3. When a task is parallelized, all its parallel subtasks, also called split tasks, have to start at the
same time in order to synchronize their executions.
4. Tasks are non-preemptable, i.e., once a task or a split task starts execution, it finishes to its
completion.
5. For each task T i , the worst case computation time for any j and k with
i . This is called the sublinear speedup assumption and the sublinearity is due to the overheads
associated with communication and synchronization among the split tasks of a task.
2.2 Terminology
Definition 1: A task is feasible in a schedule if its timing constraint and resource requirements are met
in the schedule. A schedule for a set of tasks is said to be a feasible schedule if all the tasks are feasible
in the schedule.
Definition 2: A partial schedule is a feasible schedule for a subset of tasks. A partial schedule is said
to be strongly feasible if all the schedules obtained by extending the current schedule by any one of the
remaining tasks are also feasible [8].
Definition 3: EAT s
) is the earliest time when resource R k becomes available for shared (or
exclusive) usage [8].
Definition 4: Let P be the set of processors, and R i be the set of resources requested by task T i . Earliest
start time of a task T i , denoted as EST(T i ), is the earliest time when its execution can be started, defined
as: EST (T i
(EAT u
k )), where avail time(j) denotes the
earliest time at which the processor P j becomes available for executing a task, and the third term denotes
the maximum among the earliest available times of the resources requested by task T i , in which
for shared mode and exclusive mode.
3 The Dynamic Task Scheduling Algorithm
In this section, we present our dynamic scheduling algorithm which exploits parallelism in tasks to meet
their deadlines. In the context of this paper, dynamic scheduling algorithm has complete knowledge about
currently active set of tasks, but not about the new tasks that may arrive while scheduling the current
set. The proposed parallelizable task scheduling algorithm is a variant of myopic algorithm proposed in
[8]. The myopic algorithm is a heuristic search algorithm that schedules dynamically arriving real-time
tasks with resource constraints. A vertex in the search tree represents a partial schedule. The schedule
from a vertex is extended only if the vertex is strongly feasible. The strong feasibility is checked for the
first K tasks in the current task queue, which is also known as feasibility check window. Larger the size
of the feasibility check window higher the scheduling cost and more the look ahead nature.
The proposed scheduling algorithm is similar to the myopic algorithm except that it parallelizes a
task whenever its deadline cannot be met, and has the same scheduling cost of myopic algorithm. The
degree of parallelization (i.e., the number of split tasks) of a task is chosen in a way that the task's
deadline is just met. For scheduling a task, the processor(s) and the resource(s) which have minimum
earliest available time are selected. The scheduling cost of the parallelizable task scheduling algorithm
is made equal to the myopic algorithm by performing feasibility check for only K tasks, where K - K,
as compared to K in the myopic algorithm. The value of K depends on the number of tasks parallelized
and their degrees of parallelization, i.e., the feasibility check is done till the sum of the degrees of parallelization
of these tasks reaches K. In other words, in a parallelizable task scheduling algorithm, the
number of tasks checked for feasibility is less than or equal to the size of the feasibility check window
(K). In the worst case, if none of the tasks need to be parallelized, the parallelizable task scheduling
algorithm behaves like the myopic algorithm, in which case K. The parallelizable task scheduling
algorithm for scheduling a set of currently active tasks is given below:
Parallelizable Task Scheduling(K, max-split) /* K: size of feasibility check window,
max-split: maximum degree of parallelization of a task; both are input parameters. */
begin
1. Order the tasks (in the task queue) in non-decreasing order of their deadlines and then start with an empty partial
schedule.
2. Determine whether the current vertex (schedule) is strongly feasible by performing feasibility check for K or less
than K tasks in the feasibility check window as given below:
ffl Let K be the count of the number of tasks for which feasibility check has been done.
be the (K 1)-th task in the current task queue.
ffl Let num-split be the maximum degree of parallelization permitted for the current task T i .
ffl Let cost be the sum of degree of parallelization over all the K tasks for which feasibility check has been done
so far.
(a)
(b) While (feasible is TRUE)
i. If (K \Gamma cost ! num-split) then
ii. Compute
iii. Find the smallest j such that EST (T i
iv. If (such j exists) then cost
v. Else if (num-split ! max-split) then break.
vi. Else feasible = FALSE.
3. If (feasible is TRUE) then
(a) Compute the heuristic function (H) for the first K tasks, where
(b) Extend the schedule by the task having the best (smallest) H value.
4. Else
(a) Backtrack to the previous search level.
(b) Extend the schedule by the task having the next best H value.
5. Move the feasibility check window by one task.
6. Repeat steps (2-5) until termination condition is met.
end.
The termination conditions are either (a) a complete feasible schedule has been found, or (b) maximum
number of backtracks or H function evaluations has been reached, or (c) no more backtracking is possible.
The heuristic function H is an integrated heuristic which captures the deadline and
resource requirements of task T k , where W is a constant which is an input parameter. The algorithm
backtracks only when the deadline of a task cannot be met using any degree of parallelization upto
max-split. The time complexity of the proposed algorithm for scheduling n tasks is O(Kn) which is
same as that of the myopic algorithm.
Fig.2b is a feasible schedule produced by the parallelizable task scheduling algorithm for the task set
given in fig.2a with 4 processors and 1 resource having 2 instances. The arrival time (a i ) of all the tasks
in Fig.2a is 0. For this, the input values for K, W, number of backtracks, and max-split are taken as 4,
1, 1, and 2, respectively. Fig.2c and Fig.2d show the search tree constructed by the myopic scheduling
algorithm for the task set given in Fig.2a. The myopic algorithm is unable to produce a feasible schedule
for this task set, whereas the proposed algorithm is able to produce a feasible schedule for the same task
set. The search tree constructed by the proposed algorithm is given in Fig.2c and Fig.2e. In Fig.2b, the
tasks T 11 and T 13 are parallelized and scheduled on processors P 2 and P 4 , and P 1 and P 3 , respectively.
task ready time comp. time deadline resource
share
28
exclusive
Fig.2a An example of real-time task set
T2T 48
Fig.2b Feasible schedule produced by the parallelizable task scheduling algorithm
In Fig.2c-2e, each node of the search tree is represented by two boxes: the left box shows the
earliest available time of processors for executing a new task, and the right box which has two entries
(separated by a comma) correspond to earliest available time of resource instances with one entry per
resource instance. In each entry, the value within (without) parenthesis indicates the available time of
that particular resource instance in exclusive (shared) mode. For example, entry such as 0(30),34(34)
indicates that the first instance of the resource is available for shared mode at time 0 and for exclusive
mode at time 30, and the second instance of the resource is available for shared and exclusive mode at
time 34. In Fig.2c-2e, the forward arcs correspond to extending the schedule, whereas the backward arcs
correspond to backtracking. The label T a (b) on a forward arc denotes that the task T a is scheduled on
processor P b . For example, T 13 (3; 1) denotes that the task T 13 is parallelized and scheduled on processors
(1)
Infeasible due to T 11
Infeasible due to T 13
(1)
41,37,41,37
Fig.2c Portion of the search tree common to both the algorithms
Fig.2d Portion of the search tree specific to myopic algorithm
Fig.2e Portion of the search tree specific to
parallelizable task scheduling algorithm
For illustrating the working of myopic algorithm, consider the first vertex of Fig.2d. At that point,
tasks are in the feasibility check window. EST
Similarly the other three tasks are also feasible. Therefore, the current schedule is
strongly feasible. The heuristic values for these four tasks are 58, 61, 61, and 64, respectively. The best
task is T 10 and the schedule is extended by scheduling it on P 3 . The new vertex thus obtained is not
strongly feasible because T 11 is not feasible, hence the algorithm backtracks to the previous vertex, and
extends the schedule from there using the next best task T 11 .
For parallelizable task scheduling, consider the vertex after scheduling T 10 in Fig.2e. The feasibility
check window size will be 3 since only three tasks are to be scheduled. Out of these three, only T 11
(with are checked for feasibility since feasibility checking of T 13 exceeds K.
Therefore, the schedule is extended by scheduling T 12 on P 1 . Now,
both T11 and T13 have the same H value. That is, First, the schedule is extended by
T 11 by parallelizing it and scheduling its split tasks on P 2 and P 4 . Finally, T 13 is scheduled. Note that,
all the tasks are feasible in the schedule.
4 Simulation Studies
To study the effectiveness of task parallelization in meeting task's deadline, we have conducted
extensive simulation studies. Here, we are interested in whether or not all the tasks in a task set can
finish before their deadlines. Therefore, the most appropriate metric is the schedulability of task sets
[8], called success ratio, which is defined as the ratio of the number of task sets found schedulable (by a
scheduling algorithm) to the number of task sets considered for scheduling. The parameters used in the
simulation studies are given in Fig.3. Schedulable task sets are generated for simulation using the
following approach.
1. Tasks (of a task set) are generated till schedule length, which is an input parameter, with no idle
time in the processors, as described in [8]. The computation time c 1
i of a task T i is chosen
randomly between MIN C and MAX C.
2. The deadline of a task T i is randomly chosen in the range SC and (1 +R)   SC, where SC is the
shortest completion time of the task set generated in the previous step.
3. The resource requirements of a task are generated based on the input parameters USeP and
ShareP.
4. The computation time c j
of a task T i when executed on j processors, j - 2, is equal to
1. For example, when c 1
the computation times c 2
are 7, 5,
and 4, respectively.
Each point in the performance curves (Figs.4-8) is the average of 5 simulation runs each with 200 task
sets. Each task set contains approximately 175 to 200 tasks by fixing the schedule length to 800 during
the task set generation. For all the simulation runs, the number of instances of every resource is taken
as 2.
Figs.4-8, represent the success ratio by varying R, W, UseP, num-btrk, and K, respectively. When
max-split is 1, the task is considered to be non-parallelizable and the algorithm behaves like the
myopic algorithm. Note that the scheduling costs for different values of max-split are equal. This is
achieved by making the number of tasks checked for feasibility (K) as a variable, as discussed in the
previous section, i.e., when max-split=1, Figs.4-8, it is
interesting to note that an increase in degree of parallelization increases the success ratio for the
speedup function used.
parameter explanation
MIN C minimum computation time of tasks, taken as 30.
MAX C maximum computation time of tasks, taken as 60.
R laxity parameter denotes the tightness of the deadline.
UseP probability that a task uses a resource.
ShareP probability that a task uses a resource in shared mode, taken as 0.5.
K size of feasibility check window.
W weightage given to EST(T i ) for H calculation.
num-btrk number of backtracks permitted in the search.
num-proc number of processors considered for simulation.
num-res number of resource types considered for simulation.
max-split maximum degree of parallelization of a task.
Fig.3 Simulation parameters
4.1 Effect of Laxity Parameter
Fig.4 shows the effect on success ratio by the laxity parameter (R). This helps in investigating the
sensitivity of task parallelization on varying laxities. From Fig.4, it is clear that lower values of
max-split are more sensitive to change in R than higher values of max-split. For example, the success
ratio offered by max-split=1 varies from 47.2%-99.4% as compared to the variation in success ratio
offered by max-split=4. This is due to the fact that tasks experience more degree of
parallelization (in order to meet their deadlines) when their laxities (deadlines) are tight, but the same
tasks with higher laxities rarely need parallelization since their deadlines can be met without
parallelizing them. This shows that task parallelization is more effective for tasks having tighter laxities.
4.2 Effect of W Parameter
The sensitivity of the integrated heuristic for various degrees of task parallelization is studied in Fig.5.
The effect of W for different values of max-split offers similar trend as the success ratio increases
initially with increasing W and saturates for larger values of W. Increasing W beyond 6.0 would
decrease the success ratio (which is not shown in Fig.5). This is because when when W is very large,
the integrated heuristic behaves like a simple heuristic which takes care of only the availability of
processors and resources ignoring task's deadline. Similarly, when W=0, the success ratio would be
very poor as the integrated heuristic reduces to EDF which is also a simple heuristic.
Success
Laxity parameter
Fig.4 Effect of R paramter
Success
parameter
Fig.5 Effect of W parameter
4.3 Effect of Resource Usage
The effect of resource usage on success ratio is shown in Fig.6 by fixing R , K, num-btrk, and ShareP
values as 0.09, 7, 10, and 0.5, respectively. From Fig.6, we observe that the success ratio decreases with
increasing UseP. This is due to more resource conflicts among tasks which make the value of EST(T i ),
for task T i , decided by the availability of required resources rather than by the availability of processors
and ready time of the task T i . For lower values of resource usage (UseP), the difference between
success ratio offered by max-split=4 and max-split=1 is less compared to at higher values of UseP.
This shows that task parallelization is more effective when the resource constraints among tasks are
high. Another study (not shown) is when UseP is fixed and ShareP is varied, in which the success ratio
increases with increasing ShareP.
4.4 Effect of Number of Backtracks
In Fig.7, the impact of number of backtracks on the success ratio is plotted for various values of
max-split. From the plots, it is interesting to note that the success ratio does not improve significantly
with increasing values of num-btrk for all values of max-split. This clearly motivates the need for
finding techniques which increase the success ratio with increasing scheduling cost by fixing the number
of backtracks. The exploitation of parallelism in a task proposed in this paper is one such technique as
demonstrated by our simulation results for different values of max-split.
Success
Resource usage probability
Fig.6 Effect of resource usage probability
Success
Number of backtracks
Fig.7 Effect of number of backtracks
4.5 Effect of Size of the Feasibility Check Window
Fig.8 shows the effect of varying feasibility check window (K) on success ratio for different values of
max-split. Note that for larger values of K, the algorithm has more look ahead nature, and the number
of H function evaluations in a feasibility window is more which also means an increase in scheduling
cost. Increasing the size of the feasibility check window (K) increases the success ratio for all values of
max-split. This effect is more for lower values of max-split, i.e., larger values of max-split is less
sensitive to changes in K. This indicates that more task sets can be feasibly scheduled by allowing task
parallelization than by non-parallelizable task scheduling for the same scheduling cost.
Conclusions
Meeting deadlines and achieving high resource utilization are the two main goals of task scheduling in
real-time systems. Both preemptive and non-preemptive algorithms are available in the literature to
satisfy such requirements. The schedulability of a preemptive algorithm is always higher than its
non-preemptive version. However, the higher schedulability of a preemptive algorithm has to be
obtained at the cost of higher scheduling overhead. Parallelizable task scheduling, considered in this
paper, is an intermediate solution which tries to meet the conflicting requirements of high
schedulability and low overhead. In this paper, we have proposed a new algorithm based on
parallelizable task model for dynamic scheduling of tasks in real-time multiprocessor systems. We have
demonstrated through simulation that the task parallelization is a useful concept for achieving better
schedulability than allowing more number of backtracks without parallelization. The simulation studies
show that the success ratio offered by our algorithm is always higher than that of the myopic algorithm
for a wide variety of task parameters. From the simulation studies, the following inferences are drawn.
ffl Task parallelization is more effective when tasks have tighter laxities and when resource
constraints among tasks are high. The sensitivity of W for different values of task parallelization
offers similar trend. Increasing the size of the feasibility check window (K) increases the success
ratio for all values of max-split.
ffl The impact of number of backtracks on the success ratio is less significant compared to the other
parameters. This clearly indicates the need for spending the scheduling cost on task
parallelization rather than on backtracking.
Success
Size of feasibility check window
Fig.8a Effect of K with 8 processors
Success
Size of feasibility check window
Fig.8b Effect of K with processors
Resource reclaiming from a schedule consisting of parallelizable real-time tasks is possible when the
actual computation times of tasks are less than their worst case computation times. The resource
reclaiming algorithms proposed in [6, 10] cannot be applied here because these algorithms are ignorant
of the fact that some of the tasks are parallelized and scheduled on more than one processor. Therefore,
the problem of resource reclaiming from parallelized tasks needs further research.



--R

"On-line hard real-time scheduling of parallel tasks on partitionable multiprocessors,"
"Approximate algorithms for the partitionable independent task scheduling problem,"
"Multiprocessor on-line scheduling of hard real-time tasks,"
"An approximate algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems,"
"Algorithms for scheduling imprecise computations,"

"A new approach for scheduling of parallelizable tasks in real-time multiprocessor systems,"
"Efficient scheduling algorithms for real-time multiprocessor systems,"
"Allocation and scheduling of precedence-related periodic tasks,"
"Resource reclaiming in multiprocessor real-time systems,"
"A heuristic of scheduling parallel tasks and its analysis,"
"Scheduling processes with release times, deadlines, precedence, and exclusion relations,"
"Scheduling tasks with resource requirements in hard real-time systems,"
"Parallel processing for real-time simulation: a case study,"
--TR

--CTR
Wei Sun , Chen Yu , Xavier Defago , Yuanyuan Zhang , Yasushi Inoguchi, Real-time Task Scheduling Using Extended Overloading Technique for Multiprocessor Systems, Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.95-102, October 22-26, 2007
Mohammed I. Alghamdi , Tao Xie , Xiao Qin, PARM: a power-aware message scheduling algorithm for real-time wireless networks, Proceedings of the 1st ACM workshop on Wireless multimedia networking and performance modeling, October 13-13, 2005, Montreal, Quebec, Canada
G. Manimaran , Shashidhar Merugu , Anand Manikutty , C. Siva Ram Murthy, Integrated scheduling of tasks and messages in distributed real-time systems, Engineering of distributed control systems, Nova Science Publishers, Inc., Commack, NY, 2001
G. Manimaran , C. Siva Ram Murthy, A Fault-Tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems and Its Analysis, IEEE Transactions on Parallel and Distributed Systems, v.9 n.11, p.1137-1152, November 1998
R. Al-Omari , Arun K. Somani , G. Manimaran, Efficient overloading techniques for primary-backup scheduling in real-time systems, Journal of Parallel and Distributed Computing, v.64 n.5, p.629-648, May 2004
Wan Yeon Lee , Sung Je Hong , Jong Kim, On-line scheduling of scalable real-time tasks on multiprocessor systems, Journal of Parallel and Distributed Computing, v.63 n.12, p.1315-1324, December
Xiao Qin , Hong Jiang, A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters, Journal of Parallel and Distributed Computing, v.65 n.8, p.885-900, August 2005
real-time systems;multiprocessor;dynamic scheduling;parallelizable tasks;resource constraints