Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler

Abstract

Systems need to run a larger and more diverse set of applications, from real-time to interactive to batch, on uniprocessor and multiprocessor platforms. However, most schedulers either do not address latency requirements or are specialized to complex real-time paradigms, limiting their applicability to general-purpose systems.In this paper, we present Borrowed-Virtual-Time (BVT) Scheduling, showing that it provides low-latency for real-time and interactive applications yet weighted sharing of the CPU across applications according to system policy, even with thread failure at the real-time level, all with a low-overhead implementation on multiprocessors as well as uniprocessors. It makes minimal demands on application developers, and can be used with a reservation or admission control module for hard real-time applications.

References

1. 1 S. Brin. Personal communication. www. google, corn, 1999.]]
2. 2 A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Proceedings ACM SIGCOMM, pages 1-12, September 1989.]]
3. 3 K. J. Duda and D. R. Cheriton. Borrowedvirtual-time (BVT) scheduling, ht t p: / / wwwdsg. stanford, edu/pub/bvt, html, 2000.]]
4. 4 I. Stoika et al.. A proportional-share resource allocation algorithm for real-time, time-shared systems. In Proceedings of the 17th IEEE Real-Time Systems Symposium, pages 51-59, December 1996.]]
5. 5 P. Goyal, X. Guo, and H. Vin. A hierarchical CPU scheduler for multimedia operating systems. Proceedings of the Usenix Symposium on Operating System Design and Implementation '96, pages 107-122, October 1996.]]
6. 6 M. Jones, J. Barrera, A. Forin, P. Leach, D. Rosu, and M. Rosu. An overview of the Rialto real-time architecture. Microsoft Research Technical Report MSR-TR- 96-13, July 1996. Microsoft Inc., Redmond, WA.]]
7. 7 M. Jones, D. Rosu, and M. Rosu. CPU reservations and time constraints: Efficient, predictable scheduling of independent activities. Proceedings of the 16th ACM Symposium on Operating System Principles, pages 198-211, October 1997.]]
8. 8 C. W. Mercer, S. Savage, and H. Tokuda. Processor capacity reserves for multimedia operating systems. Proceedings of the IEEE International Conference on Multimedia Computing and Systems, pages 90-99, May 1994.]]
9. 9 J. Mogul and K. Ramakrishnan. Eliminating receive livelock in an interrupt-driven kernel. ACM Trans. on Computer Systems, 15(3):217-252, August 1997.]]
10. 10 J. Nieh, J. Hanko, J. Northcutt, and G. Wall. SVR4 UNIX scheduler unacceptable for multimedia applications. Proceedings of the IEEE International Conference on Multimedia Computing and Systems, pages 35-48, November 1993.]]
11. 11 J. Nieh and M. Lam. The design, implementation, and evaluation of SMART: A scheduler for multimedia applications. Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, pages 184-197, October 1997.]]
12. 12 L. Rowe, K. Patel, and B. Smith. Performance of a software MPEG video decoder. Proc. ACM Multimedia 93, pages 31-39, August 1993.]]
13. 13 J. Stankovic and K. Ramamritham. The Spring Kernel: A new paradigm for real-time systems. IEEE Software, 8(3):62-73, 1991.]]
14. 14 C. Waldspurger and W. Weihl. Lottery scheduling: Flexible proportional-share resource mangement. Proceedings of the First Symposium on Operating System Design and Implementation, pages 1-11, November 1994.]]

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems