Accelerated simply periodic task sets and their application for RM schedulability tests


Dr. Dirk Müller (TU Chemnitz)


Rate-monotonic (RM) scheduling dominates real-time applications in the industry because of its simplicity and predictability. In spite of this, for RM schedulability analysis, no algorithm of polynomial complexity has been found. Thus, several only sufficient tests have been proposed. Most of them are based on utilization bounds, i.e., inequalities as closed-form tests. Famous examples are the Liu/Layland test, the Hyperbolic Bound and Burchard's bound. Based on the principle of Accelerated Simply Periodic Task Sets (ASPTSs), an alternative non-closed-form approach, we present new algorithms: Specialization with respect to r (Sr) and Distance-Constrained Tasks (DCT). It will be shown that these algorithms achieve better sensitivities (success rates). The price is a higher computational complexity of O(n log n) or O(n2) which reduces their suitability for online admission control. On the other hand, their parallelization potential is a matter of fact that can compensate this drawback.


Mueller, Dirk, Dr.-Ing., Dipl.-Inf.; 1995 High school diploma (Abitur) with deepened mathematical-scientific education at Johannes-Kepler-Gymnasium Chemnitz; Studies of Medical Informatics at University of Leipzig including 2 semesters abroad studies at Mid Sweden University in Sundsvall in Sweden. 2006 Graduation to Dr.-Ing., dissertation ''Sub-pixel filtering for an autostereoscopic multi-perspective 3-D representation of high quality'' in informatics at University of Kassel. 2006-08 Research Associate at Philipps-University of Marburg with topics Idea of Man and IT as well as Model-driven Software Develpoment. In winter term 2007/08 lecturer at University of Applied Sciences Fulda, lecture ''Formal Methods of Software Engineering''. Since 2008 Assistant Professor (Akademischer Rat) at TU Chemnitz, Operating Systems Group. In winter terms 2009/10 and 2010/11 own lecture ''Design of Software for Embedded Systems.''