Abstract—
The admission control problem is concerned with
determining whether a new task may be accepted by a system
consisting of a set of running tasks, such that the already admitted
and the new task are all schedulable. Clearly, admission control
decisions are to be taken on-line, and hence, this constitutes a
general problem that arises in many real-time and embedded
systems. As a result, there has always been a strong interest
in developing efficient admission control algorithms for various
setups. In this paper, we propose a novel constant-time admission
control test for the Deadline Monotonic (DM) policy, i.e., the time
taken by the test does not depend on the number of admitted
tasks currently in the system. While it is possible to adapt known
utilization bounds from the literature to derive constant-time
admission control tests (e.g., the Liu and Layland bound, or
the more recent hyperbolic bound), the test we propose is less
pessimistic. We illustrate this analytically where possible and
through a set of detailed experiments. Apart from the practical
relevance of the proposed test in the specific context of DM tasks,
the underlying technique is general enough and can possibly be
extended to other scheduling policies as well.
I. INTRODUCTION
In this paper, we present an efficient constant-time test
for admission control of real-time tasks under the Deadline
Monotonic (DM) policy. Such an admission control test has
to decide whether a new task can be feasibly scheduled (i.e.,
without causing any deadline misses) together with a set of
already accepted tasks currently running in a system. Since
admission control decisions are taken on-line, it is important
to develop efficient algorithms/tests with predictable execution
time which does not depend on the number of tasks in the
system.
The DM policy consists in assigning fixed priorities to
tasks according to their deadlines: the shorter the deadline,
the higher the priority assigned to the task. This scheduling
case is of particular practical relevance because fixed priorities
are supported by most real-time operating systems and, in
addition, DM is the optimal priority assignment for the case
that deadlines (di) are less than periods (pi) [1].
Exact schedulability tests are already known for fixed priorities,
e.g., [2], [3] and [4], however, they are generally not
eligible for admission control. This is because they all have
pseudo-polynomial complexity and thus it is difficult to predict
their running time (which depends not only on the number of
tasks, but also on task parameters, e.g., periods, etc.).
Although the complexity of the admission control problem
is the one of testing schedulability for only one new task in the
system, an exact schedulability test still results in a pseudopolynomial-
time admission control test. Additionally, all exact
schedulability tests require tasks to be sorted according
to decreasing (non-increasing) priority, i.e., increasing (nondecreasing)
deadlines under DM. Of course, it is possible to
sort tasks on-line as they arrive. This way, when a new task arrives,
we only need to add it to a sorted list. However, if a new
task is added to the system, using an exact schedulability test
also implies retesting all already accepted lower-priority tasks.
This is time-consuming and can be impracticable particularly
for a large number of tasks.
On the other hand, we can adapt the utilization bounds
obtained for Rate Monotonic (RM) to the case of DM where
di  pi holds for all tasks. As discussed later, we can use,
for example, the Liu and Layland bound [5] with very little
modification. An admission control test based on this bound
presents constant complexity O(1), however, it becomes rather
pessimistic as the number of accepted tasks grows.
In order to increase accuracy while retaining constant complexity
O(1), we propose a novel admission control test, called
load test, for DM tasks with deadlines less than or equal to
periods. This test calculates an upper bound on the worst-case
response time of tasks considering all already accepted and
the arriving task. If this upper bound is always less than or
equal to the respective deadlines, the accepted and the new
task are going to be schedulable under DM. As shown later,
the load test outperforms the constant-time tests that can be
designed for DM based on approaches from the literature.
This paper is structured as follows: The next two sections
provide a survey of related work and a description of the
used task model and notation. Afterwards, the proposed admission
control test is presented and analyzed in Section IV.
Section V shows the results of an extensive comparison
against approaches with the same complexity based on wellknown
techniques from the literature. Finally, some concluding
remarks are discussed in Section VI.


Download full report
http://date-conferenceproceedings/PAPERS/2010/DATE10/PDFFILES/03.6_1.PDF