Next-Generation Real-Time Device Drivers Project:
Integrating Schedulability Theory with Driver Implementation Practices

Participants

• Theodore P. (Ted) Baker - Professor, FSU
• An-I (Andy) Wang - Associate Professor, FSU
• Kartik Gopalan - Associate Professor, SUNY Binghamton
• Mark Stanovich - PhD student, FSU
• Mark Lewandowski - MS, FSU
• Michael Hines - MS FSU; PhD SUNY Binghamton
• Jian Wang - MS Beijing University; PhD student, FSU, then SUNY Binghamton
• Kwame-Lante Wright - Undergraduate student, Cooper Union, REU at SUNY Binghamton
• Charles Weddle - MS, FSU; PhD student, FSU
• Christopher Meyers - MS, FSU; PhD student, FSU
• Sarah Diesburg - PhD student, FSU
• Jin Qian - MS, FSU
• Kyle Martin - BS, FSU
• Peter Gavin - BS, FSU; PhD student, FSU
• Daniel Rosenthal - BS, FSU;

Description

Device drivers are operating system components that are typically developed independently by hardware vendors and third parties, often under the assumption that the driver is the only time-critical component in the operating system. Device drivers execute with full kernel privileges and can circumvent the system's scheduling mechanisms to meet their own requirements. This, in turn, interferes with the execution and timing of other applications and device drivers.

This project, supported in part by the National Science Foundation under grant CNS-0509131, seeks to improve the state-of-the-art in device driver support for embedded real-time applications. The approach involves fitting the scheduling of device driver execution within the operating system via paradigms for which model-based schedulability testing can be performed. The research studies representative examples of existing device drivers to determine how they fit well-understood formal models for schedulability analysis. It explores how the drivers, the operating system's device driver scheduling mechanisms, and formal models can be improved to achieve more predictable performance for real-time applications. The research activities include formal analysis, prototype implementation of new architectural features, and performance testing.

This research strives to address problems that the device drivers in current operating systems pose for real-time analysis. Besides disseminating results through conventional meetings and publications, and training graduate and undergraduate students, this project seeks to advance real-time computing practice through the dissemination of real-time kernel code and benchmark programs.

Linux Kernel Patches

We have developed patches to the Linux kernel which permit the scheduling of device drivers according to a sporadic server policy. This permits schedulability analysis of the system including the device driver, and allows one to adjust the balance between the quality of I/O service provided by the device driver and the degree of scheduling interference the device driver causes for other tasks. The idea is explained in our paper "Modeling Device Driver Effects in Real-Time Schedulability Analysis: Study of a Network Driver", which appears in the Proceedings of the 13th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'07).

We have also developed patches to the Linux kernel that allow disk I/O requests to be throttled in a way that allows deadlines to be guaranteed for certain I/O requests while maintaining high overall bandwidth, using off-the-shelf hardware. This work also provides an interface that allows a process to specify the deadlines of its I/O requestes. The ideas are explained in our paper "Throttling on-disk schedulers to meet soft-real-time requirements", which appears in the proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'08).

Links to all the Linux kernel patches may be found at http://www.cs.fsu.edu/~baker/drivers/linux_patches/.

MemX

The MemX system, developed in the Operating Systems and Networks (OSNET) Lab at Binghamton University, provides a mechanism to virtualize the collective memory resources of machines in a cluster with zero modifications to applications or operating system. Development of MemX was supported in part by this grant. The code is publicly available at http://memx.googlecode.com.

XenLoop

XenLoop is a fully transparent and high performance inter-VM network loopback channel, in the Xen virtual machine environment. XenLoop does not sacrifice user or kernel-level transparency and yet achieves high communication performance between co-resident guest VMs. It intercepts outgoing network packets and sheperds the packets destined to co-resident VMs through a high-speed inter-VM shared memory channel that bypasses the virtualized network interface. Guest VMs using XenLoop can migrate transparently across machines without disrupting ongoing network communications, and seamlessly switch between the standard network path and the XenLoop channel. XenLoop's development was support in part by this grant. The code is publicly available at http://osnet.cs.binghamton.edu/projects/xenloop.html.

Courses

Development of the course Linux Device Driver and Kernel Programming was supported in part by this grant.

Publications

The following publications were supported in part by this project.

Journal Articles

1. Jian Wang, Kwame-Lante Wright, and Kartik Gopalan, "Xenloop : A transparent high performance inter-VM network loopback", Journal of Cluster Computing -- Special Issue on HPDC, vol. 12(2), p. 141, 2009.
2. Michael Hines, Umesh Deshpande, and Kartik Gopalan, "Post-copy live migration of virtual machines", SIGOPS Operating Systems Review, vol. 43(3), p. 14, 2009.
3. T.P. Baker, M. Cirinei and M. Bertogna, "EDZL scheduling analysis", Real-Time Systems, 40, 3 p. 264, 2008 .
4. Baruah, S; Baker, T, "Schedulability analysis of global EDF", Real-Time Systems, vol. 38, p. 223, 2008.
5. K. Gopalan and T-C Chiueh and Y-J Lin, " Slack allocation techniques for intra-path load balancing", Journal of High Speed Networks, vol. 16, no. 3, p. 211, 2007.

Conference Papers

1. Mark Stanovich, Theodore Baker, An-I Andy Wang, and Michael Gonzalez Harbour, "Defects of the POSIX Sporadic Server and how to correct them", Proc. 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'10), Stockholm, Sweden, April 2010. (Pre-publication version available as FSU Computer Science Technical report TR-091026.)
2. Michael Hines and Kartik Gopalan, "Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning", International Conference on Virtual Execution Environments (VEE), Washington, DC, March 2009.
3. Theodore Baker and Sanjoy Baruah, "Sustainable multiprocessor scheduling of sporadic task systems", Proc. 2009 Euromicro Conference on Real-Time Systems (ECRTS'09), Dublin, Ireland, July 2009.
4. S. K. Baruah and T.P. Baker, "Global EDF schedulability analysis of arbitrary sporadic task systems", Proc. 2008 EuroMicro Conference on Real-Time Systems (ECRTS'08), Prague, Czech Republic, July 2008.
5. T. P. Baker, A. Wang, M.J. Stanovich, "Fitting Linux device drivers into an analyzable scheduling framework", Proc. OSPERT 2007, the Workshop on Operating Systems Platforms for Embedded Real-time Applications, 2007.
6. Mark Lewandowski, Mark Stanovich, Theodore Baker, Kartik Gopalan, An-I Andy Wang, "Modeling Device Driver Effects in Real-Time Schedulability Analysis: Study of a Network Driver", Proc. 13th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 57-68, Bellevue, WA, April 2007.
7. Mark J. Stanovich, Theodore P. Baker, and An-I Andy Wang. "Throttling on-disk schedulers to meet soft-real-time requirements", Proc. the 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 331-341, St. Louis, MO, April 2008. (Pre-publication version available as FSU Computer Science Technical report TR-071025.)
8. Jian Wang, Kwame-Lante Wright, and Kartik Gopalan, " XenLoop : A transparent high performance inter-VM network loopback", Proceedings of the International Symposium on High Performance Distributed Computing (HPDC), Boston, MA, June 2008.
9. Jin Qian, Christopher Meyers, and An-I Andy Wang, "A Linux Implementation Validation of Track-Aligned Extents and Track-aligned RAIDs", Proc. 2008 USENIX Annual Technical Conference, June 2008.
10. M. Hines, K. Gopalan, " MemX: Supporting large memory applications in Xen virtual machines", Proc. International Workshop on Virtualization Technology in Distributed Computing (VTDC), Reno, NV, Nov. 2007.
11. T.P. Baker and M. Cirinei, "Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks", Springer Lecture Notes in Computer Science No. 4878, Principles of Distributed Systems, p. 62, vol. 4878, 2007. (Pre-publication version available as FSU Computer Science Technical report TR-061001.)
12. K. Gopalan and K-D Kang, " Coordinated allocation and scheduling of multiple resources in real-time operating systems", Proc. of Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT 2007), Pisa, Italy, July 2007.
13. T.P. Baker, "A comparison of global and partitioned EDF schedulability tests for multiprocessors", Proc. International Conference on Real-Time and Network Systems, p. 119, 2006.
14. T. P. Baker and M. Cirinei, "A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks", Proc. 27th IEEE Real-Time Systems Symposium (RTSS '06), Rio de Janeiro, p. 170. (Pre-publication version available as FSU Computer Science Technical report TR-060401.)
15. N. Fisher, T.P. Baker, and S.K. Baruah, "Algorithms for determining the demand-based load of a sporadic task system", Proc. 12th IEEE International Conf. on Embedded and Real-Time Computing Systems and Applications, Sydney, Australia p 135, August 2006. (Pre-publication version available as FSU Computer Science Technical report TR-051201.)
16. M. Hines, J. Wang, K. Gopalan, " Distributed Anemone: Transparent low-latency access to remove memory in commodity clusters", Proc.International Conference on High Performance Computing, p. 509, Dec. 2006.
17. M. Hines, M. Lewandowski, J. Wang, K. Gopalan, "Implementation experiences in transparently harnessing cluster-wide memory", Proc. International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), 2006. (Pre-publication version available as FSU Computer Science Technical report TR-060608.)
18. M. R. Hines, M. Lewandowski, and K. Gopalan, Anemone: Adaptive network memory engine, abstract in Proc. 20th ACM Symposium on Operating Systems Principles, Brighton, UK, 2005. (Full paper availbale as FSU Computer Science Technical report TR-0500128.)

Other Publications

1. Michael Hines, "Techniques for collective physical memory ubiquity within networked clusters of virtual machines", PhD Dissertation, Dept. of Computer Science, Binghamton University, August 2009.
2. Mark J. Stanovich. "Throttling on-disk schedulers to meet soft-real-time requirements". Master's Thesis, Department of Computer Science, Florida State University, Tallahassee, FL, April 3, 2008.
3. J. Qian and A. Wang, "A Behind-the-scenes story on applying cross-layer coordination to disks and RAIDs", Technical Report TR-071015, Department of Computer Science, Florida State University, October 2007.
4. T.P. Baker and S.K.Baruah, "Schedulability analysis of multiprocessor sporadic task systems", chapter in Handbook of Real-Time and Embedded Systems, ISBN 1-58488-678-1, CRC Press, 2008. (Pre-publication version available as FSU Computer Science Technical report TR-060601.)
5. T. P. Baker and M. Cirinei, "A unified analysis of global EDF and fixed-task-priority schedulability or sporadic task systems on multiprocessors", FSU Computer Science Technical report TR-060401.)
Accepted for publication in a special issue of the Journal of Embedded Computing, but the journal seems to have gone out of business before it appeared in print.
6. Mark Lewandowski, "Latency reduction techniques for remote memory access in Anemone", Master's Thesis, Dept. of Computer Science, Florida State University, 2005.