Show simple item record

dc.contributor.authorAtlas, Aliaen_US
dc.contributor.authorBestavros, Azeren_US
dc.date.accessioned2011-10-20T05:07:34Z
dc.date.available2011-10-20T05:07:34Z
dc.date.issued1998-05-02en_US
dc.identifier.citationAtlas, Alia; Bestavros, Azer. "Statistical Rate Monotonic Scheduling", Technical Report BUCS-1998-010, Computer Science Department, Boston University, May 2, 1998. [Available from: http://hdl.handle.net/2144/1767]en_US
dc.identifier.urihttp://hdl.handle.net/2144/1767
dc.description.abstractIn this paper we present Statistical Rate Monotonic Scheduling (SRMS), a generalization of the classical RMS results of Liu and Layland that allows scheduling periodic tasks with highly variable execution times and statistical QoS requirements. Similar to RMS, SRMS has two components: a feasibility test and a scheduling algorithm. The feasibility test for SRMS ensures that using SRMS' scheduling algorithms, it is possible for a given periodic task set to share a given resource (e.g. a processor, communication medium, switching device, etc.) in such a way that such sharing does not result in the violation of any of the periodic tasks QoS constraints. The SRMS scheduling algorithm incorporates a number of unique features. First, it allows for fixed priority scheduling that keeps the tasks' value (or importance) independent of their periods. Second, it allows for job admission control, which allows the rejection of jobs that are not guaranteed to finish by their deadlines as soon as they are released, thus enabling the system to take necessary compensating actions. Also, admission control allows the preservation of resources since no time is spent on jobs that will miss their deadlines anyway. Third, SRMS integrates reservation-based and best-effort resource scheduling seamlessly. Reservation-based scheduling ensures the delivery of the minimal requested QoS; best-effort scheduling ensures that unused, reserved bandwidth is not wasted, but rather used to improve QoS further. Fourth, SRMS allows a system to deal gracefully with overload conditions by ensuring a fair deterioration in QoS across all tasks---as opposed to penalizing tasks with longer periods, for example. Finally, SRMS has the added advantage that its schedulability test is simple and its scheduling algorithm has a constant overhead in the sense that the complexity of the scheduler is not dependent on the number of the tasks in the system. We have evaluated SRMS against a number of alternative scheduling algorithms suggested in the literature (e.g. RMS and slack stealing), as well as refinements thereof, which we describe in this paper. Consistently throughout our experiments, SRMS provided the best performance. In addition, to evaluate the optimality of SRMS, we have compared it to an inefficient, yet optimal scheduler for task sets with harmonic periods.en_US
dc.description.sponsorshipNational Science Foundation (CCR-970668)en_US
dc.language.isoen_USen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1998-010en_US
dc.subjectReal-time computing and communicationen_US
dc.subjectAdmission controlen_US
dc.subjectOperating systemsen_US
dc.subjectProbabilistic analysisen_US
dc.subjectQuality of Service (QoS) managementen_US
dc.subjectScheduling algorithms and analysisen_US
dc.titleStatistic Rate Monotonic Schedulingen_US
dc.typeTechnical Reporten_US


Files in this item

This item appears in the following Collection(s)

Show simple item record