Deadlines
The best-known example of a time
constraint is a deadline, but it is a simple one and there
are many others (as we will discuss). The use of deadlines
in real-time computing is a relatively recent small fraction
of the overall theory and practice of deadline-based
resource management in various fields (notably logistical
fields).
In particular, the
real-time computing community historically focuses primarily on hard
deadlines (e.g., [ ]). The traditional model of an action having a
hard
deadline at time td is
simply that the action's completion either meets or misses
its deadline,
as illustrated in Figure 1.
Figure 1: Traditional Hard
Deadline
(The semantics of a
deadline -- i.e., the specific way in which system
timeliness depends on whether any particular deadline is met,
such as whether a miss constitutes a failure
-- is not part of the definition of a deadline, contrary to
popular misconception in the real-time computing community
(e.g., [ ]). These consequences are properly specified as part of the
sequencing optimality criteria.)
When the term "deadline" is used without the
qualifier "hard," it refers to the general case of
a deadline -- a soft deadline, of which a
hard deadline is a special case: the action is either more
or less timely, depending on what its completion time is with
respect to its deadline td [Pinedo 02].
Figure 2: Traditional Deadline
(The term "soft deadline"
is almost always used incorrectly in the real-time
computing community, as explained on the
sequencing page.)
"More or less" timely
with respect to a deadline is always measured in terms of
"lateness" and its derivative cases "tardiness" and (to a lesser
extent) "earliness:"
On the next page, we show
that deadlines are a special, limited, case of a more general and
expressive model of time constraints: time/utility
functions.
References
Pinedo 02 Pinedo, M., Scheduling:
Theory, Algorithms, and Systems, 2nd edition, Prentice Hall,
2002, ISBN 0-130-28138-7.
Next: Time/Utility
Functions
Back to Time Constraints
Add to Favorites
Print Page
Download a PDF copy of this page
|
Site Updated
03/30/2008
|
Legal
