Eliminating receive livelock in an interrupt-driven kernel

ABSTRACT

Most operating systems use interface interrupts to schedule network tasks. Interrupt-driven systems can provide low overhead and good latency at low offered load, but degrade significantly at higher arrival rates unless care is taken to prevent several pathologies. These are various forms ofreceive livelock, in which the system spends all of its time processing interrupts, to the exclusion of other necessary tasks. Under extreme conditions, no packets are delivered to the user application or the output of the system. To avoid livelock and related problems, an operating system must schedule network interrupt handling as carefully as it schedules process execution. We modified an interrupt-driven networking implementation to do so; this modification eliminates receive livelock without degrading other aspects of system performance. Our modifications include the use of polling when the system is heavily loaded, while retaining the use of interrupts ur.Jer lighter load. We present measurements demonstrating the success of our approach.

REFERENCES

• 1: Chran-Ham Chang , Richard Flower , John Forecast , Heather Gray , William R. Hawe , K. K. Ramakrishnan , Ashok P. Nadkarni , Uttam N. Shikarpur , Kathleen M. Wilde, High-performance TCP/IP and UDP/IP networking in DEC OSF/1 for Alpha AXP, Digital Technical Journal, v.5 n.1, p.44-61, Winter 1993
• 2: CHEN, J. B. AND EUSTACE, A. 1995. Kernel instrumentatiion tools and techniques. Tech. Rep. TR-26-95, Harvard Univ. Center for Research in Computing Technology, Cambridge, Mass. Nov.
• 3: Peter Druschel , Gaurav Banga, Lazy receiver processing (LRP): a network subsystem architecture for server systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.261-275, October 29-November 01, 1996, Seattle, Washington, United States
• 4: EUSTACE, A. AND SRIVASTAVA, A. 1995. ATOM: A flexible interface for building high performance program analysis tools. In Proceedings of the 1995 USENIX Conference. USENIX Assoc., Berkeley, Calif., 303-313.
• 5: Kevin Roland Fall, A peer-to peer I/O system in support I/O intensive workloads, University of California at San Diego, La Jolla, CA, 1994
• 6: Kevin R. Fall , Joseph Pasquale , Steven McCanne, Workstation Video Playback Performance with Competitive Process Load, Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, p.170-173, April 19-21, 1995
• 7: Joseph Pasquale , George C. Polyzos, Network Issues for Sequoia 2000, University of California at Berkeley, Berkeley, CA, 1991
• 8: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 9: JACOBSON, V. 1990. Efficient protocol implementation. In bound notes provided at ACM SIGCOMM '90 Tutorial on "Protocols for High-Speed Networks".
• 10: LEFFLER, S. J.~ McCusIcK, M. K.~ KARELS, M. J.~ AND QUARTERMAN, J. S. 1989. The Design and Implementation of the ~.3BSD UNIX Operating System. Addison-Wesley, Reading, Mass.
• 11: MACKLEM, R. 1991. Lessons learned tuning the 4.3BSD Reno implementation of the NFS protocol. In Proceedings of the Winter 1991 USENIX Conference. USENIX Assoc., Berkeley, Calif., 5364.
• 12: MASSALIN, H. AND PU, C. 1990. Fine-grain adaptive scheduling using feedback. Comput. Syst. 3, 1 (Winter), 139-174.
• 13: MOGUL, J. C. 1989. Simple and flexible datagram access controls for UNIX-based gateways. In Proceedings of the Summer 1989 USENIX Conference. USENIX Assoc., Berkeley, Calif., 203-221.
• 14: J. Mogul, Efficient use of workstations for passive monitoring of local area networks, Proceedings of the ACM symposium on Communications architectures & protocols, p.253-263, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 15: J. Mogul , R. Rashid , M. Accetta, The packer filter: an efficient mechanism for user-level network code, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.39-51, November 08-11, 1987, Austin, Texas, United States
• 16: David Mosberger , Larry L. Peterson, Making paths explicit in the Scout operating system, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.153-167, October 29-November 01, 1996, Seattle, Washington, United States
• 17: PERLMAN, R. 1983. Fault-tolerant broadcast of routing information. Comput. Networks 7, 6 (Dec.), 395-405.
• 18: RAMAKRISHNAN, K. K. 1992. Scheduling issues for interfacing to high speed networks. In Proceedings of the Globecom '92 IEEE Global Telecommunications Conference. IEEE, New York, 622-626.
• 19: RAMAKRISHNAN, K. K. 1993. Performance considerations in designing network interfaces. IEEE J. Sel. Areas Commun. 11, 2 (Feb.), 203-219.
• 20: K. K. Ramakrishnan , Lev Vaitzblit , Cary Gray , Uresh Vahalia , Dennis Ting , Percy Tzelnic , Steve Glaser , Wayne Duso, Operating system support for a video-on-demand file service, Multimedia Systems, v.3 n.2, p.53-65, May 1995 [doi>10.1007/BF01219801]
• 21: RANUM, M. J. AND AVOLIO, F. M. 1994. A toolkit and methods for Internet firewalls. In Proceedings of the Summer 1993 USENIX Conference. USENIX Assoc., Berkeley, Calif., 37-44.
• 22: ROMANOW, t. AND FLOYD, S. 1995. Dynamics of TCP traffic over ATM networks. IEEE J. Sel. Areas Commun. 13, 4 (May), 633-641.
• 23: SMITH, J. M. AND TRAW, C. B. S. 1993. Giving applications access to Gb/s networking. IEEE Network 7, 4 (July), 44-52.
• 24: Robert J. Souza , P. G. Krishnakumar , Cüneyt M. Özveren , Robert J. Simcoe , Barry A. Spinney , Robert E. Thomas , Robert J. Walsh, GIGAswitch system: a high-performance packet-switching platform, Digital Technical Journal, v.6 n.1, p.9-22, Winter 1994
• 25: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 26: TRAW, C. B. S. AND SMITH, J. M. 1993. Hardware/software organization of a high-performance ATM host interface. IEEE J. Sel. Areas Commun. 11, 2 (Feb.), 240-253.
• 27: VAHALIA, W.~ GRAY, C. C-r.~ AND TING, D. 1995. Metadata logging in an NFS server. In Proceedings of the 1995 USENIX Conference. USENIX Assoc., Berkeley, Calif., 265-276.
• 28: C. A. Waldspurger, Lottery and Stride Scheduling: Flexible Proportional-share Resource Management, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 29: WALDSPURGER, C. t. AND WEIHL, W. E. 1994. Lottery scheduling: Flexible proportional-share resource management. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX Assoc., Berkeley, Calif., 1-11.
• 30: C. A. Waldspurger , E. Weihl. W., Stride Scheduling: Deterministic Proportional- Share Resource Management, Massachusetts Institute of Technology, Cambridge, MA, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Input/output; Network communication

General Terms:
Performance

Keywords:
interrupt-driven kernel, livelock, polling, scheduling