Bringing Real-time Scheduling Theory and Practice Closer for Multimedia Computing

This paper seeks to bridge the gap between theory and practice of real-time scheduling in the domain of multimedia computer systems. We show that scheduling algorithms that are good in theory, often have practical limitations. However when these algorithms are modified based on practical considerations, existing theoretical results cannot be used as they are. In this paper we motivate the need for new scheduling schemes for multimedia protocol processing, and demonstrate their real-time performance in our prototype implementation. We then explain the observed results by analysis and measurement. More specifically, we show that using strict preemption can introduce overheads in protocol processing such as more context switching and extra system calls. We present our scheduling scheme called rate-monotonic with delayed preemption (RMDP) and show how it reduces both these overheads. We then develop the analyitical framework to analyze RMDP and other scheduling schemes that lie in the region between strict (immediate) preemption and no preemption. Byproducts of our analysis include simpler schedulability tests for non-preemptive scheduling, and a variant of rate-monotonic scheduling that has fewer preemptions. Finally, we measure the overhead due to context switching on Pentium and Sparc-1 machines and its impact on real-time performance. We show that when scheudling clock interrupts occur ever 1 millisecond, RMDP can lessen the overhead of context switching leading to an increase in utilization of as much as 8%