Extending futex for kernel to user notification

Abstract

Threads in reactive applications need to service a multitude of events from different sources such as device drivers, communication channels or cooperating threads. While notification about these events can conceptually be understood as a form of "synchronization", most operating systems (including Linux) do not provide a unified abstraction. This paper proposes to separate event delivery and notification, and to provide unified event notification through general-purpose synchronization objects. It demonstrates how this unified mechanism can be implemented in Linux as an extension of the futex mechanism to allow notification from kernel-space. Required modifications are discussed and their impact is assessed. The new event notification mechanism allows to move many thread activation policy decisions into user-space, with benefits for multi-threaded reactive applications: This is demonstrated in a modification of the leader/followers pattern with considerable performance benefits.

References

1. Banga, G., Mogul, J. C., and Druschel, P. A scalable and explicit event delivery mechanism for unix. In ATEC '99: Proceedings of the annual conference on USENIX Annual Technical Conference (Berkeley, CA, USA, 1999), USENIX Association, pp. 19--19.
2. Herlihy, M. A methodology for implementing highly concurrent data structures. In PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming (New York, NY, USA, 1990), ACM, pp. 197--206.
3. Hubertus Franke, Rusty Russell, M. K. Fuss, futexes and furwocks: Fast userlevel locking in linux. In Proceedings of the 2002 Ottawa Linux Summit (2002).
4. IEEE. Portable Operating System Interface (POSIX®) -- Part 1: System Application: Program Interface (API) {C Language}, 2004.
5. Lemon, J. Kqueue - a generic and scalable event notification facility. In Proceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference (Berkeley, CA, USA, 2001), USENIX Association, pp. 141--153.
6. Lever, C., and Boreham, D. malloc() performance in a multithreaded linux environment. In ATEC '00: Proceedings of the annual conference on USENIX Annual Technical Conference (Berkeley, CA, USA, 2000), USENIX Association, pp. 56--56.
7. Lim, B.-H., and Agarwal, A. Reactive synchronization algorithms for multiprocessors. In ASPLOS-VI: Proceedings of the sixth international conference on Architectural support for programming languages and operating systems (New York, NY, USA, 1994), ACM, pp. 25--35.
8. Provos, N., and Lever, C. Scalable network i/o in linux. In ATEC '00: Proceedings of the annual conference on USENIX Annual Technical Conference (Berkeley, CA, USA, 2000), USENIX Association, pp. 38--38.
9. Pyarali, I., Spivak, M., Cytron, R., and Schmidt, D. C. Evaluating and optimizing thread pool strategies for real-time corba. SIGPLAN Not. 36, 8 (2001), 214--222.
10. Salah, K., El-Badawi, K., and Haidari, F. Performance analysis and comparison of interrupt-handling schemes in gigabit networks. Comput. Commun. 30, 17 (2007), 3425--3441.
11. Schmidt, D. C., Rohnert, H., Stal, M., and Schultz, D. Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects. John Wiley & Sons, Inc., New York, NY, USA, 2000.
12. HP OpenVMS Systems Documentation http://h71000.www7.hp.com/doc/731final/5841/5841pro_contents.html.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Communications management

    • Software system structures

      • Software architectures