On the efficient scheduling of non-periodic tasks in hard real-time systems Conference Paper

abstract

• This paper presents linear time, on-line algorithms which guarantee and jointly schedule firm aperiodic, hard sporadic and periodic tasks in fixed-priority real-time systems. We develop and capitalize on a methodology which computes the spare capacity Z(a,b) exactly in time (n), for arbitrary schedule intervals (a,b), which, to the best of our knowledge, is the first linear time algorithm reported in the literature. Previous state of the art methods incur pseudo-polynomial time to guarantee on-line a single aperiodic and incur continuous overhead for slack maintenance. Our method guarantees and schedules firm tasks to receive FIFO or EDF service, incurring a one-time linear cost, of (n) and (n + k), respectively, where k is the number of pending firm tasks.

name of conference

• Proceedings 20th IEEE Real-Time Systems Symposium (Cat. No.99CB37054)

authors

• Liu, Jyh

published proceedings

• 2020 IEEE Real-Time Systems Symposium (RTSS)

author list (cited authors)

• Thomadakis, M. E., & Liu, J.

citation count

• 20

complete list of authors

• Thomadakis, ME||Liu, Jyh-Charn

publication date

• January 1999

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Proceedings - Real-Time Systems Symposium  Journal

Digital Object Identifier (DOI)

• 10.1109/real.1999.818836

start page

• 148

end page

• 151

URL

• http://dx.doi.org/10.1109/real.1999.818836