Real-time Systems

Description

We are investigating a new model for dynamic and fully integrated multi-class (hard real-time, soft real-time, and non real-time processes) real-time scheduling called Resource Allocation/Dispatching(RAD). RAD allows for the detailed management of both the resources consumed and the timing of the delivery of those resource for each exectuing process. Futhermore, each process, each process can have different requirements with respect to both of these quantities, fully characterizing the real-time behavior of individual processes and allowing for resource delivery precisely tailored to the needs of each process. The RAD model of CPU resource management has led to the development of three distinct CPU resource managers: BEST, RBED, and DQM.

BEST

BEST stands for Best-Effort Enhanced for Soft Real-Time. The BEST scheduler automatically detects processes that exhibit periodic behavior and boosts their scheduling priority so that they may meet their periodic deadlines. Using this technique, the kernel schedules soft real-time processes with periodic deadlines (such as multimedia applications) so that they meet all their deadlines without any a priori knowledge of resource demands. The BEST scheduler is implemented in the Linux kernel.

RBED

RBED is the Resource-Based Earliest Deadline First scheduler, which is a RAD prototype that provides fully integrated scheduling of hard real-time, soft real-time, and best-effort processes. The project purpose is to demonstrate feasibility of the RAD model by replacing the Linux scheduler with a resource-based real-time scheduler. RBED resource allocation is accomplished via dynamic process rate adjustment. RBED dispatching is accomplished via dynamic application period adjustment. Based on the specific processing requirements of each process and the current system state, RBED assigns a target rate of progress and period to each process in the system. Both are enforced at runtime by a modified EDF scheduler that dispatches processes in EDF order but interrupts them via a programmable timer when they have exhausted their alloted CPU for the current period. A proof-of-concept version of RBED is implemented in Linux 2.4.20 kernel.

DQM

The Dynamic QoS Manager is a middleware agent that mediates resource usage among concurrently executing adaptable applications. The DQM monitors the load on system resources and performance statistic provided by applications, and gives feedback so processes may dynamically adjust their resource demands to match an optimally beneficial quality of service for the system.

Status

BEST

Our preliminary experiments show that the BEST prototype meets its basic purpose:enhancing the performance of periodic processes while capturing the benefits of a best-effort model. We plan to further develop the BEST scheduler and implement it with optimal performance.

• The source code of BEST related schedulers are available here.

RBED

The RBED is implemented in Linux 2.4.20 kernel. RBED is designed to support hard real-time (HRT), different soft real-time (MDSRT: Missed Deadline Soft Real-Time, RASRT: Resource Alloation Soft Real-Time, and RBSRT: Rate-Based Soft Real-Time, etc), and best-effort (BE) processes. Currently it supports HRT (natively), MDSRT (multiple periods/dealines with discrete and continuous support), and BE processes seamlessly in the Linux kernel. We are working on RBED's support of RASRT, RBSRT, and also firm real-time processes. Our preliminaly experiment results demonstrate the RAD model is promising. Our results show that RBED is capable of simultaneously supporting hard real-time, soft real-time, and best-effort processes. Its management of best-effort processes closely mirrors that of Linux, its management of soft real-time processes is better than that of Linux, and it provides guaranteed hard real-time performance. In addition, RBED's support of best-effort processes is shown to be better than that of two-level hierarchical systems in which best-effort processes are run in the background of hard real-time processes, and RBED's runtime overhead is only slightly greater than that of Linux.

• If you want to download the RBED patch to the Linux kernel and play with it, please go to here.

DQM

We have developed the Dynamic QoS Manager(DQM) as a middleware mechanism that operates on the collective QoS Level specifications. The prelimilary DQM soft real-time model with multiple QoS levels support in terms of MDSRT has been integrated into RBED framework.

Upcoming Deadlines

• Here are the conference deadlines for Real-Time Systems

Publications

• Timothy Bisson, Scott A. Brandt, Darrell D. E. Long, NVCache: Increasing the effectiveness of disk spin-down algorithms with caching, Proceedings of the 14th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS 2006), September 2006.
• Joel Wu, Scott A. Brandt, The Design and Implementation of AQuA: an Adaptive Quality of Service Aware Object-Based Storage Device, Proceedings of the 23rd IEEE / 14th NASA Goddard Conference on Mass Storage Systems and Technologies, May 2006, pages 209-218.
• Caixue Lin, Scott A. Brandt, Improving Soft Real-Time Performance Through Better Slack Management, IEEE Real-Time Systems Symposium (RTSS 2005), December 2005, pages 3–14.
• Scott A. Brandt, Scott Banachowski, Caixue Lin, Joel Wu, Developing a Complete Integrated Real-Time System, Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT 2005) at the Euromicro International Conference on Real-Time Systems (ECRTS 2005), July 2005.
• Joel Wu, Scott A. Brandt, Hierarchical Disk Sharing for Multimedia Systems and Servers, Proceedings of the 15th ACM International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV 2005), June 2005, pages 189-194.
• Timothy Bisson, Scott A. Brandt, Reducing Energy Consumption with a Non-Volatile Storage Cache, International Workshop on Software Support for Portable Storage (IWSSPS) held in conjunction with the IEEE Real-Time and Embedded Systems and Applications Symposium (RTAS 2005), March 2005.
• Joel Wu, Scott Banachowski, Scott A. Brandt, Automated QoS Support for Multimedia Disk Access, Proceedings of the SPIE, Multimedia Computing and Networking (MMCN 2005), January 2005, pages 103-107.
• Pau Martí, Caixue Lin, Scott A. Brandt, Manel Velasco, Josep M. Fuertes, Optimal state feedback based resource allocation for resource-constrained control tasks, Proceedings of the 25th IEEE Real-Time Systems Symposium (RTSS 2004), December 2004, pages 161-172.
• Caixue Lin, Scott A. Brandt, Efficient soft real-time processing in an integrated system, Work in Progress Proceedings of the 25th IEEE Real-Time Systems Symposium (RTSS WIP 2004), December 2004.
• Scott Banachowski, Scott A. Brandt, Timothy Bisson, Integrating best-effort scheduling into a real-time system, Proceedings of the 25th IEEE Real-Time Systems Symposium (RTSS 2004), December 2004.
• Joel Wu, Scott A. Brandt, Storage Access Support for Soft Real-Time Applications, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2004), May 2004.
• Caixue Lin, Pau Martí, Scott A. Brandt, Scott Banachowski, Manel Velasco, Josep M. Fuertes, Improving control performance using adaptive quality of service in a real-time system, Work in Progress Session of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), May 2004.
• Timothy Bisson, Scott A. Brandt, Adaptive Disk Spin-down Algorithms in Practice, Work-in-Progress Proceedings of the Usenix Conference of File and Storage Technology (FAST 2004), March 2004.
• Scott Banachowski, Joel Wu, Scott A. Brandt, Missed deadline notification in best-effort schedulers, Proceedings of Multimedia Computing and Networking 2004 (MMCN 04), January 2004, pages 123–135.
• Scott Banachowski, Scott A. Brandt, Toward a taxonomy of time-constrained applications, Work in Progress Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS WIP 2003), December 2003, pages 3-6.
• Scott A. Brandt, Scott Banachowski, Caixue Lin, Timothy Bisson, Dynamic integrated scheduling of hard real-time, soft real-time and non-real-time processes, Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS 2003), December 2003, pages 396–407.
• Scott Banachowski, Scott A. Brandt, Better real-time response for time-share scheduling, Proceedings of the Eleventh International Workshop on Parallel & Distributed Real-Time Systems (WPDRTS), April 2003.
• Caixue Lin, Managing the soft real-time processes in RBED, Master's Project Report, University of California, Santa Cruz, March 2003.
• Scott Banachowski, Using the best-effort scheduling model to support soft real-time processing, Master's Project Report, University of California, Santa Cruz, August 2002.
• Scott A. Brandt, Gary Nutt, Flexible soft real-time processing in middleware, Real-Time Systems, 22, January 2002, pages 77-118.
• Scott Banachowski, Scott A. Brandt, The BEST scheduler for integrated processing of best-effort and soft real-time processes, Proceedings of Multimedia Computing and Networking 2002 (MMCN '02), January 2002, pages 46–60.
• Scott Banachowski, Scott A. Brandt, The BEST desktop soft real-time scheduler, Work in Progress Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS WIP 2001), December 2001, pages 9–12.
• Scott A. Brandt, Performance analysis of dynamic soft real-time systems, Proceedings of the 20th IEEE International Performance, Computing and Communications Conference (IPCCC 01), April 2001, pages 379–386.
• Lonnie Welch, Scott A. Brandt, Toward a realization of the value of benefit in real-time systems, Proceedings of the Ninth International Workshop on Parallel & Distributed Real-Time Systems (WPDRTS), April 2001.
• Scott A. Brandt, Gary Nutt, Toby Berk, James Mankovichr, A dynamic quality of service middleware agent for mediating application resource usage, Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS 1998), December 1998, pages 307–317.