An improved schedulability test for uniprocessor periodic task systems. Unpublished Manuscript. Available at http://www.cs.unc.edu/˜uma/papers.html

We present a sufficient linear-time schedulability test for preemptable, asynchronous, periodic task systems with arbi-trary relative deadlines, scheduled on a uniprocessor by an optimal scheduling algorithm. We show analytically and em-pirically that this test is more accurate than the commonly-used density condition. We also present and discuss the re-sults of experiments that compare the accuracy and execution time of our test with that of a pseudo-polynomial-time schedu-lability test presented previously for a restricted class of task systems in which utilization is strictly less than one.