Dynamic Soft Real Time CPU Scheduler 2.0

This is the dynamic soft real time scheduler by the Monet Group
at the Department of Computer Science, University of Illinois at Urbana-Champaign.

This release has been tested on SunOS 5.7, SGI IRIX 6.5, Linux(RedHat 6.2) , and Windows NT.

* Motivation
* General Description
* Software : DSRT CPU Scheduler, CPU Monitor, and CPU Broker
* DSRT 2.0 under Windows NT^New
* DSRT 2.0 under Linux^New
* DSRT Monitoring^New
* Coordinating Power-Aware Adaptation of Applications and Hardware Resources^New
* DSRT Multi-Processor for Win2K
* Ongoing work
* People
* Publications
* Related Sites
* Mpeg Clips
* Acknowledgement

Motivation

Multimedia applications such as video/audio processing, animation are time-sensitive because these applications need minimal jitter to accomplish a good viewing quality. They require that underlying systems support sufficient and constant processing time so that they can provide Quality of Service(QoS) guarantees to the users in terms of minimum throughput, maximum response time and CPU cycles. However, in current time-sharing environments, these multimedia applications do not perform well when they are scheduled concurrently with the traditional nonreal-time applications. On the other hand, allowing enough CPU to real-time applications may cause nonreal-time applications to use unfair CPU bandwidth. DSRT scheduler targets fair CPU distribution among competent applications as well as guarantee of time constraints of real-time applications. Another issue is that process scheduling has beed discussed inside OS kernel level. So in order to get new scheduling scinario, kernel source code is required to be modified and re-installed. DSRT scheduler is designed as a middleware scheduler and thus it can be used by copying executable scheduler into the target machine withoug modifying underlying kernel.

General Description

The dynamic soft real time scheduler (DSRT) 2.0 is a user-level dynamic scheduler that can schedule soft real time (RT) periodic and aperiodic tasks. The DSRT 2.0 contains the following features

CPU service classes. A RT process first enters a reservation with the DSRT scheduler before its actual real time execution. The reservation describes the processor usage pattern of the RT process during its real time execution. Depending on the type of the applications, their processor usage pattern may be constant, variable, periodic, or aperiodic. The DSRT scheduler provides various classes of reservation:

Periodic constant processing time class.
Periodic constrained constant processing time class.
Periodic variable processing time class.
Aperiodic constant processing time class.
Event class.

Guarantee time sharing (TS) allocation. The TS process will receive a minimum fixed percentage of processor bandwidth so that they will not be starved in the presence of RT processes.
Overrun protection. This means that if a misbehaving RT process (e.g, using more processor time than it has reserved) cannot adversely affect the guarantees that the scheduler made to other behaving RT processes.
System-initiated adaptation. The RT process can specify an adaptation strategy for the DSRT scheduler to automatically adjust the reservation based on the actual usage pattern of the RT process. The DSRT scheduler provides the following adaptation strategies:

range [min, max] adaptation.
exponential average adaptation.
statistical adaptation.

Smart probing. Probing allows the RT application to get an accurate estimation on the reservation parameters, e.g. service class, or percentage of processor utilization.
Reservation re-negotiation. The RT process can modify the reservation parameters.
Scheduler monitor. The scheduler monitor provides various information on the RT processes including their usage, overrun, and deadline misses condition.
Multiprocessor support.
Allocation algorithm/policy for process overruns.

The DSRT 2.0 scheduler has the following improvements over the previously released DSRT 1.0:

CPU service classes.
Smart probing: automatic selection of CPU service class and reservation values.
Multiprocessor support.
Fix various security loopholes.
More monitoring data on the real time processes and the CPU scheduler.

Ongoing work

Currently we are taking two different approaches; adding more functionalities on DSRT scheduler and porting DSRT scheduler into Window NT and Linux based systems. The added features will be as follows.

A new CPU service class for sporadic tasks
CPU broker for CPU brokerage services : scheduler consists of two components (CPU broker and dispatcher)
Advance reservation handling : reservation of CPU bandwidth is made for future use
User-level thread scheduler

People

Primary Advisor

Professor Klara Nahrstedt

Previous members

Hao-hua Chu (Ph.D Graduate, June 1999)
Lintian Qiao (Ph.D Graduate)
Roland Geisler (M.S Graduate, June 1999)
Goutham Garimella (M.S Graduate, June 1999)
Manish Gupta (M.S Graduate, June 1999)
Arun Viswanathan (M.S Graduate, June 2000)
Priti Goel (M.S Graduate, June 2000)
Kihun Kim (M.S Graduate, August 2001)
Diwakar Gupta (M.S Graduate, May 2002)
Jim Jackson (M.S Graduate, May 2002)

Current members

Wanghong Yuan (Ph.D Candidate)
Jiang Qian (Ph.D candidate)

Publications

Journals

W. Yuan, K. Nahrstedt, S. Adve, D. Jones, and R. Kravets, GRACE: Cross-Layer Adaptation for Multimedia Quality and Battery Energy, To appear in IEEE Transaction on Mobile Computing.

Klara Nahrstedt, Hao-hua Chu and Srinivas Narayan, QoS-aware Resource Management for Distributed Multimedia Applications, accepted to Journal on High-Speed Networking, Special Issue on Multimedia Networking.

Conferences

Wanghong Yuan and Klara Nahrstedt, Practical Voltage Scaling for Mobile Multimedia Devices, in Proc. of ACM Multimedia 2004, New York, NY, October, 2004. pdf

Wanghong Yuan and Klara Nahrstedt, Process Group Management in Cross-Layer Adaptation, in Proc. of SPIE/ACM Multimedia Computing and Networking Conference (MMCN'04), Santa Clara, CA, January, 2004. pdf

Wanghong Yuan and Klara Nahrstedt, Energy-Efficient Soft Real-Time CPU Scheduling for Mobile Multimedia Systems, in Proc. of 19th ACM Symposium on Operating Systems Principles (SOSP'03), Bolton Landing, NY, October, 2003. pdf

Wanghong Yuan and Klara Nahrstedt, Buffering Approach for Energy Saving in Video Sensors, in Proc. of IEEE International Conference on Multimedia and Expo (ICME2003), Baltimore, MD, July, 2003. pdf

Wanghong Yuan and Klara Nahrstedt, ReCalendar: Calendaring and Scheduling Applications with CPU and Energy Resource Guarantees for Mobile Devices, in Proc. of IEEE International Conference on Pervasive Computing and Communications (PerCom 2003), Dallas-Fort Worth, Texas, March, 2003. pdf

W. Yuan, K. Nahrstedt, S. Adve, D. Jones, and R. Kravets, Design and Evaluation of A Cross-Layer Adaptation Framework for Mobile Multimedia Systems, in Proc. of SPIE/ACM Multimedia Computing and Networking Conference (MMCN'03), Santa Clara, CA, January, 2003. pdf

S. Adve, A. Harris, C. Hughes, D. Jones, R. Kravets, K. Nahrstedt, D. Sachs, R. Sasanka, J. Srinivasan, W. Yuan, The Illinois GRACE Project: Global Resource Adaptation through CoopEration, in Proc. of Workshop on Self-Healing, Adaptive and self-MANaged Systems (SHAMAN02), New York City, NY, June, 2002. ps

Wanghong Yuan and Klara Nahrstedt, Integration of Dynamic Voltage Scaling and Soft Real-Time Scheduling for Open Mobile Systems, in Proc. of 12th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV '02), pp. 105-114, Miami Beach, Florida, May, 2002. pdf

Wanghong Yuan and Klara Nahrstedt, A Middleware Framework Coordinating Processor/Power Resource Management for Multimedia Applications, in Proc. of IEEE Globecom 2001, San Antonio, Texas, November, 2001. pdf

Wanghong Yuan, Klara Nahrstedt and Xiaohui Gu, Coordinating Energy-Aware Adaptation of Multimedia Applications and Hardware, in Proc. of 9th ACM Multimedia (Multimedia Middleware Workshop), Ottawa, Canada, October, 2001. ps

Wanghong Yuan, Klara Nahrstedt, Kihun Kim, R-EDF: A Reservation-Based EDF Scheduling Algorithm for Multiple Multimedia Task Classes, in Proc. of 7th IEEE Real-Time Technology and Applications Symposium, Taipei, Taiwan, May, 2001. ps

Kihun Kim, Klara Nahrstedt, A Resource Broker Model with Integrated Reservation Scheme, to appear in Proceedings of IEEE International Conference on Multimedia and Expo 2000(ICME2000), NewYork, NY, July 31 - August 2, 2000.

Hao-hua Chu, Klara Nahrstedt, CPU Service Classes for Multimedia Applications, to appear in Proceedings of IEEE International Conference on Multimedia Computing and Systems (IEEE Multimedia Systems '99), Florence, Italy, June 7-11, 1999.

Hao-Hua Chu, Klara Nahrstedt: A Soft Real Time Scheduling Server in UNIX Operating System. IDMS 1997: 153-162

Hao-hua Chu, Klara Nahrstedt, Jiang Qian. Dynamic Soft Real Time Scheduling Framework for Multimedia Environment, submitted to IEEE Real-Time Systems Symposium, December 1999.

Chih-han Lin, Hao-hua Chu, and Klara Nahrstedt, A Soft Real-time Scheduling Server on the Windows NT, 2nd USENIX Windows NT Symposium, Seattle, WA, August, 1998.

Ph.D Theses

Hao-hua Chu, CPU Service Classes: A Soft Real Time Framework for Multimedia Applications, Ph.D. thesis, August 1999.

Wanghong Yuan, GRACE-OS: An Energy-Efficient Mobile Multimedia Operating System, Ph.D. Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, October, 2004. pdf

M.S Theses

Kihun Kim, Extended DSRT System, Department of Computer Science, University of Illinois at Urbana-Champaign, August 2000.

Priti Goel, Thread Management in Dynamic Soft Real-Time Framework for Multi-Threaded Multimedia Applications, Department of Computer Science, University of Illinois at Urbana-Champaign, May 2000.

Arun Kumar Viswanathan, Design and Evaluation of a CPU-aware Communication Broker for RSVP-based Network, Department of Computer Science, University of Illinois at Urbana-Champaign, May 2000.

Roland Geisler, A Remote Monitor System for Distributed Applications Using the Soft Real-time Scheduler, Department of Computer Science, University of Illinois at Urbana-Champaign, May 1999.

Manish Gupta, Reservation Based Distributed Resource Management , Department of Computer Science, University of Illinois at Urbana-Champaign, May 1999.

Goutham Garimella, Advance CPU Reservations with the Dynamic Soft Real-Time Scheduler , Department of Computer Science, University of Illinois at Urbana-Champaign, May 1999.

Technical Reports

Arun K Viswanathan Impact of CPU Reservation on End-to-End Performance of Transport Protocols.

Hao-hua Chu, Klara Nahrstedt, CPU Service Classes for Multimedia Applications, Technical Report UIUCDCS-R-98-2068, UILU-ENG-98-1730, Department of Computer Science, University of Illinois at Urbana-Champaign, August 1998.

Hao-hua Chu, Klara Nahrstedt A Soft Real Time Scheduling Server in UNIX Operating System, Technical Report No. UIUCDCS-R-97-1990, UILU-ENG-97-1704, University of Illinois, January 1997.

Won Jong Jeon, Comments for porting DSRT 2.0 on Linux Operation System., University of Illinois, August 2000.

Acknowledgement

This research is funded by the Air Force grant F30602-97-2-0121, the NSF CCR 96-23867, the NSF PACI grant ACU-96-19019, and in part the NSF CISE CDA 96-24396. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies. If you have questions or comments, send email to Klara Nahrstedt