Affiliations: University of North Carolina at Chapel Hill, Chapel
Hill, NC 27599, USA
Note: [] Corresponding author. James H. Anderson. E-mail:
anderson@cs.unc.edu
Abstract: In soft real-time applications, tasks are allowed to miss their
deadlines. Thus, less-costly scheduling algorithms can be used at the price of
occasional violations of timing constraints. This may be acceptable if
reasonable tardiness bounds (i.e., bounds on the extent to which deadlines may
be missed) can be guaranteed. In this paper, we consider soft real-time applications implemented
on multiprocessors. Pfair scheduling algorithms are the only known means of
optimally scheduling hard real-time applications on multiprocessors. For this
reason, we consider the use of such algorithms here. In the design of Pfair
scheduling algorithms, devising schemes to correctly break ties when several
tasks have the same deadline is a critical issue. Such tie-breaking schemes
entail overhead that may be unacceptable or unnecessary in soft real-time
applications. In this paper, we consider the earliest pseudo-deadline first
(EPDF) Pfair algorithm, which avoids this overhead by using no tie-breaking
information. Our main contributions are twofold. First, we establish a
condition for ensuring a given tardiness under EPDF. The condition for ensuring
a tardiness of one quantum is very liberal and should often hold in practice.
Second, we present simulation results involving randomly-generated task sets,
including those that do not satisfy our condition. In these experiments,
deadline misses rarely occurred, and no misses by more than one quantum ever
occurred.
