The following paper was originally published in the Proceedings of the USENIX 1996 Annual Technical Conference San Diego California January 1996 Eliminating Receive Livelock in an Interrupt driven Kernel Jeffrey Mogul DEC Western Research Laboratory K K Ramakrishnan AT T Bell Laboratories For more information about USENIX Association contact 1 Phone 510 528 8649 2 FAX 510 548 5738 3 Email office usenix org 4 WWW URL http www usenix org Eliminating Receive Livelock in an Interrupt driven Kernel Jeffrey C Mogul Digital Equipment Corporation Western Research Laboratory K K Ramakrishnan AT T Bell Laboratories 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 of receive livelock in which the system spends all 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 eliminates receive livelock without degrading other aspects of system performance We present measurements demonstrating the success of our approach 1 Introduction Most operating systems use interrupts to internally schedule the performance of tasks related to I O events and particularly the invocation of network protocol software Interrupts are useful because they allow the CPU to spend most of its time doing useful processing yet respond quickly to events without constantly having to poll for event arrivals Polling is expensive especially when I O events are relatively rare as is the case with disks which seldom interrupt more than a few hundred times per second Polling can also increase the latency of response to an event Modern systems can respond to an interrupt in a few tens of microseconds to achieve the same latency using polling the system would have to poll tens of thousands of times per second which would create excessive overhead For a general purpose system an interrupt driven design works best Most extant operating systems were designed to handle I O devices that interrupt every few milliseconds Disks tended to issue events on the order of once per revolution first generation LAN environments tend to generate a few hundred packets per second for any single end system Although people understood the need to reduce the cost of taking an interrupt in general this cost was low enough that any normal system would spend only a fraction of its CPU time handling interrupts The world has changed Operating systems typically use the same interrupt mechanisms to control both network processing and traditional I O devices yet many new applications can generate packets several orders of magnitude more often than a disk can generate seeks Multimedia and other real time applications will become widespread Client server applications such as NFS running on fast clients and servers can generate heavy RPC loads Multicast and broadcast protocols subject innocent bystander hosts to loads that do not interest them at all As a result network implementations must now deal with significantly higher event rates Many multi media and client server applications share another unpleasant property unlike traditional network applications Telnet FTP electronic mail they are not flow controlled Some multi media applications want constant rate low latency service RPC based client server applications often use datagram style transports instead of reliable flowcontrolled protocols Note that whereas I O devices such as disks generate interrupts only as a result of requests from the operating system and so are inherently flow controlled network interfaces generate unsolicited receive interrupts The shift to higher event rates and non flowcontrolled protocols can subject a host to congestive collapse once the event rate saturates the system without a negative feedback loop to control the sources there is no way to gracefully shed load If the host runs at full throughput under these conditions and gives fair service to all sources this at least preserves the possibility of stability But if throughput decreases as the offered load increases the overall system becomes unstable Interrupt driven systems tend to perform badly under overload Tasks performed at interrupt level by definition have absolute priority over all other tasks If the event rate is high enough to cause the system to spend all of its time responding to interrupts then nothing else will happen and the system throughput will drop to zero We call this condition receive livelock the system is not deadlocked but it makes no progress on any of its tasks Any purely interrupt driven system using fixed interrupt priorities will suffer from receive livelock under input overload conditions Once the input rate exceeds the reciprocal of the CPU cost of processing one input event any task scheduled at a lower priority will not get a chance to run Yet we do not want to lightly discard the obvious benefits of an interrupt driven design Instead we should integrate control of the network interrupt handling sub system into the operating system s scheduling mechanisms and policies In this paper we present a number of simple modifications to the purely interrupt driven model and show that they guarantee throughput and improve latency under overload while preserving the desirable qualities of an interrupt driven system under light load 2 Motivating applications We were led to our investigations by a number of specific applications that can suffer from livelock Such applications could be built on dedicated singlepurpose systems but are often built using a generalpurpose system such as UNIX and we wanted to find a general solution to the livelock problem The applications include Host based routing Although inter network routing is traditionally done using specialpurpose usually non interrupt driven router systems routing is often done using more conventional hosts Virtually all Internet firewall products use UNIX or Windows NT systems for routing 7 13 Much experimentation with new routing algorithms is done on UNIX 2 especially for IP