NC State University

Department of Computer Science Colloquia 2002-2003

Date:   Thursday, February 6, 2003
Time:   3:30 PM (talk)
Place:   136 EGRC, Centennial Campus (click for courtesy parking request)

Speaker:   Anand Srinivasan , UNC Chapel Hill

Efficient and Flexible Fair Scheduling of Real-time Tasks on Multiprocessors

Abstract:   Two trends are evident in work on real-time computing. First, sophisticated applications with high computational demands are becoming commonplace. Examples of such applications include tracking systems, telepresence systems, etc. Second, multiprocessors are becoming extremely cost-effective. Given these two trends, multiprocessor real-time designs will continue to be of growing importance. The objective of my research is to provide timeliness guarantees to real-time tasks on multiprocessor systems. Currently, partitioning is the favored approach for scheduling real-time tasks on multiprocessors. However, techniques based on partitioning are not suitable in highly-dynamic systems such as tracking systems. Our research has focused on fair scheduling algorithms as a means to guarantee timeliness constraints on multiprocessors. We have developed an efficient proportionate-fair (Pfair) scheduling algorithm called PD^2 that can be used to optimally schedule real-time tasks on multiprocessors. Experiments conducted by us have shown that, for static real-time systems, PD^2 is competitive with, and often outperforms, task partitioning. We have also presented schemes for handling dynamic task systems and integrating scheduling of non-real-time tasks. We have further developed a notion of rate-based scheduling that is more general than the well-known periodic and sporadic task models. This model is preferable for handling a variety of situations that commonly arise in real-time systems. For instance, the rate-based model is well-suited for systems in which tasks may self-suspend, block, or have jittered releases. We have shown that PD^2 is optimal for scheduling such tasks as well. In this talk, I will present the PD^2 algorithm and also discuss the concept of rate-based scheduling.

Short Bio:   Anand Srinivasan is currently a Ph.D. candidate in the Department of Computer Science at UNC-Chapel Hill. He is working with Prof. James Anderson in the area of real-time systems. His current research interests are in the area of real-time systems, operating systems, scheduling theory, multimedia networking, and QoS guarantees. Mr. Srinivasan obtained his M.S. from UNC-Chapel Hill in 2000 and Bachelor of Technology in Computer Science and Engineering from IIT-Bombay (India) in 1998.

Hosts:   Robert Fornaro and Mladen Vouk, Computer Science, NCSU.

Colloquia Home Page.