Eliminating receive livelock in an interrupt-driven kernel

ACM Transactions on Computer Systems - Tập 15 Số 3 - Trang 217-252 - 1997
Jeffrey C. Mogul1, K. K. Ramakrishnan2
1Digital Equipment Corporation Western Research Lab, Palo Alto, CA
2AT&T Labs, Florham Park, NJ

Tóm tắt

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 of receive 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.

Từ khóa


Tài liệu tham khảo

CHANG , C.-H. , FLOWER , R. , FORECAST , J. , GRAY , H. , HAWE , W. R. , NADKARNI , A. P. , RAMAKRISHNAN , K. K. ~ SHIKARPUR , U. N. ~ AND WILDE , K. M. 1993 . High-performance TCP/IP and UDP/IP networking in DEC OSF/1 for Alpha AXP . Digital Tech. J. 5 , 1 (Winter), 44-61.]] CHANG, C.-H., FLOWER, R., FORECAST, J., GRAY, H., HAWE, W. R., NADKARNI, A. P., RAMAKRISHNAN, K. K.~ SHIKARPUR, U. N.~ AND WILDE, K. M. 1993. High-performance TCP/IP and UDP/IP networking in DEC OSF/1 for Alpha AXP. Digital Tech. J. 5, 1 (Winter), 44-61.]]

DRUSCHEL , P. AND BANGA , G. 1996 . Lazy Receiver Processing (LRP): A network subsystem architecture for server systems . In Proceedings of the 2rid Symposium on Operating Systems Design and Implementation. USENIX Assoc. , Berkeley, Calif. , 261 - 275 .]] 10.1145/238721.238786 DRUSCHEL, P. AND BANGA, G. 1996. Lazy Receiver Processing (LRP): A network subsystem architecture for server systems. In Proceedings of the 2rid Symposium on Operating Systems Design and Implementation. USENIX Assoc., Berkeley, Calif., 261-275.]] 10.1145/238721.238786

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 .]] 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.]]

FALL , K. ~ PASQUALE , J.~ AND MCCANNE , S. 1995 . Workstation video playback performance with competitive process load . In Proceedings of the 5th International Workshop on Network and Operating Systems Support for Digital Audio and Video. IEEE Communications Society , New York , 179 - 182 .]] FALL, K.~ PASQUALE, J.~ AND MCCANNE, S. 1995. Workstation video playback performance with competitive process load. In Proceedings of the 5th International Workshop on Network and Operating Systems Support for Digital Audio and Video. IEEE Communications Society, New York, 179-182.]]

10.1109/90.251892

JACOBSON , V. 1990. Efficient protocol implementation. In bound notes provided at ACM SIGCOMM '90 Tutorial on "Protocols for High-Speed Networks".]] JACOBSON, V. 1990. Efficient protocol implementation. In bound notes provided at ACM SIGCOMM '90 Tutorial on "Protocols for High-Speed Networks".]]

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 .]] 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.]]

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.]] 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.]]

MASSALIN , H. AND PU , C. 1990 . Fine-grain adaptive scheduling using feedback . Comput. Syst. 3 , 1 (Winter), 139-174.]] MASSALIN, H. AND PU, C. 1990. Fine-grain adaptive scheduling using feedback. Comput. Syst. 3, 1 (Winter), 139-174.]]

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 .]] 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.]]

MOGUL , J. C. 1990 . Efficient use of workstations for passive monitoring of local area networks . In Proceedings of the SIGCOMM '90 Symposium on Communications Architectures and Protocols. ACM , New York , 253 - 263 .]] 10.1145/99508.99562 MOGUL, J. C. 1990. Efficient use of workstations for passive monitoring of local area networks. In Proceedings of the SIGCOMM '90 Symposium on Communications Architectures and Protocols. ACM, New York, 253-263.]] 10.1145/99508.99562

MOGUL , J. C. ~ RASHID , R. F. ~ AND ACCETTA , M. J. 1987 . The Packet Filter: An efficient mechanism for user-level network code . In Proceedings of the 11th Symposium on Operating Systems Principles. ACM , Austin, Texas , 39 - 51 .]] 10.1145/41457.37505 MOGUL, J. C.~ RASHID, R. F.~ AND ACCETTA, M. J. 1987. The Packet Filter: An efficient mechanism for user-level network code. In Proceedings of the 11th Symposium on Operating Systems Principles. ACM, Austin, Texas, 39-51.]] 10.1145/41457.37505

MOSBERGER , D. AND PETERSON , L. L. 1996 . Making paths explicit in the scout operating systern . In Proceedings of the 2rid Symposium on Operating Systems Design and Implementation. USENIX Assoc. , Berkeley, Calif. , 153 - 167 .]] 10.1145/238721.238771 MOSBERGER, D. AND PETERSON, L. L. 1996. Making paths explicit in the scout operating systern. In Proceedings of the 2rid Symposium on Operating Systems Design and Implementation. USENIX Assoc., Berkeley, Calif., 153-167.]] 10.1145/238721.238771

PERLMAN , R. 1983 . Fault-tolerant broadcast of routing information . Comput. Networks 7 , 6 (Dec.), 395-405.]] PERLMAN, R. 1983. Fault-tolerant broadcast of routing information. Comput. Networks 7, 6 (Dec.), 395-405.]]

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 .]] 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.]]

RAMAKRISHNAN , K. K. 1993 . Performance considerations in designing network interfaces . IEEE J. Sel. Areas Commun. 11 , 2 (Feb.), 203-219.]] RAMAKRISHNAN, K. K. 1993. Performance considerations in designing network interfaces. IEEE J. Sel. Areas Commun. 11, 2 (Feb.), 203-219.]]

10.1007/BF01219801

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 .]] 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.]]

ROMANOW , t. AND F LOYD , S. 1995 . Dynamics of TCP traffic over ATM networks . IEEE J. Sel. Areas Commun. 13 , 4 (May), 633-641.]] ROMANOW, t. AND FLOYD, S. 1995. Dynamics of TCP traffic over ATM networks. IEEE J. Sel. Areas Commun. 13, 4 (May), 633-641.]]

SMITH , J. M. AND TRAW , C. B. S. 1993 . Giving applications access to Gb/s networking . IEEE Network 7 , 4 (July), 44-52.]] SMITH, J. M. AND TRAW, C. B. S. 1993. Giving applications access to Gb/s networking. IEEE Network 7, 4 (July), 44-52.]]

SOUZA , R. J. , KRISHNAKUMAR , P. G. , (~) ZVEREN , C. M. , J. SIMCOE , R. , SPINNEY , B. A. , THOMAS , R. E. ~ AND WALSH , R. J. 1994 . GIGAswitch: A high-performance packet switching platform . Digital Tech. J. 6 , 1 (Winter), 9-22.]] SOUZA, R. J., KRISHNAKUMAR, P. G., (~)ZVEREN, C. M., J.SIMCOE, R., SPINNEY, B. A., THOMAS, R. E.~ AND WALSH, R. J. 1994. GIGAswitch: A high-performance packet switching platform. Digital Tech. J. 6, 1 (Winter), 9-22.]]

SRIVASTAVA , t. AND EUS TACE , t. 1994 . ATOM: A system for building customized program analysis tools . In Proceedings of the SIGPLAN '9~ Conference on Programming Language Design and Implementation. ACM , New York , 196 - 205 .]] 10.1145/178243.178260 SRIVASTAVA, t. AND EUSTACE, t. 1994. ATOM: A system for building customized program analysis tools. In Proceedings of the SIGPLAN '9~ Conference on Programming Language Design and Implementation. ACM, New York, 196-205.]] 10.1145/178243.178260

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.]] 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.]]

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 .]] 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.]]

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 .]] 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.]]

WALDSPURGER , C. t. AND WEIHL , W. E. 1995 . Stride scheduling: Deterministic proportionalshare resource management. Tech. Memo. MIT/LCS/TM-528, Massachusetts Institute of Technology Laboratory for Computer Science , Cambridge, Mass. June.]] WALDSPURGER, C. t. AND WEIHL, W. E. 1995. Stride scheduling: Deterministic proportionalshare resource management. Tech. Memo. MIT/LCS/TM-528, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Mass. June.]]

Thông tin
Thông tin xuất bản

ACM Transactions on Computer Systems

Tập 15 Số 3

217-252

Thông tin tác giả