Hardware Reference
In-Depth Information
The third field
γ
indicates the optimality criterion (performance measure) to be
followed in the schedule.
For example:
L
max
denotes the problem of scheduling a set of tasks with precedence
constraints on a uniprocessor machine in order to minimize the maximum late-
ness. If no additional constraints are indicated in the second field, preemption is
allowed at any time, and tasks can have arbitrary arrivals.
|
prec
|
1
|
f
i
denotes the problem of scheduling a set of tasks on a
three-processor machine. Preemption is not allowed and the objective is to min-
imize the sum of the finishing times. Since no other constraints are indicated in
the second field, tasks do not have precedence nor resource constraints but have
arbitrary arrival times.
3
|
no preem
|
Late
i
denotes the problem of scheduling a set of tasks on a two-
processor machine. Tasks have synchronous arrival times and do not have other
constraints. The objective is to minimize the number of late tasks.
2
|
sync
3.2
JACKSON'S ALGORITHM
The problem considered by this algorithm is 1
of
n
aperiodic tasks has to be scheduled on a single processor, minimizing the maximum
lateness. All tasks consist of a single job, have synchronous arrival times, but can have
different computation times and deadlines. No other constraints are considered, hence
tasks must be independent; that is, cannot have precedence relations and cannot share
resources in exclusive mode.
|
sync
|
L
max
. That is, a set
J
Notice that, since all tasks arrive at the same time, preemption is not an issue in this
problem. In fact, preemption is effective only when tasks may arrive dynamically and
newly arriving tasks have higher priority than currently executing tasks.
Without loss of generality, we assume that all tasks are activated at time
t
=0,so
that each job
J
i
can be completely characterized by two parameters: a computation
time
C
i
and a relative deadline
D
i
(which, in this case, is also equal to the absolute
deadline). Thus, the task set
J
can be denoted as
J
=
{
J
i
(
C
i
,D
i
)
,i
=1
,...,n
}
.
Search WWH ::
Custom Search