Preventing interrupt overload

ABSTRACT

Performance guarantees can be given to tasks in an embedded system by ensuring that access to each shared resource is mediated by an appropriate scheduler. However, almost all previous work on CPU scheduling has focused on thread-level scheduling, resulting in systems that are vulnerable to a lower-level form of overload that occurs when too many interrupts arrive. This paper describes three new techniques, two software-based and one hardware-based, for creating systems that delay or drop excessive interrupt requests before they can overload a processor. Our interrupt schedulers bound both the amount of work performed in interrupt context and its granularity, making it possible to provide strong progress guarantees to thread-level processing. We show that our solutions work and are efficient when implemented on embedded processors. We have also taken a description for a microprocessor in VHDL, modified it to include logic that prevents interrupt overload, synthesized the processor, and verified that it works using simulation. By allowing developers to avoid making assumptions about the worst-case interrupt rates of peripherals, our work fills an important gap in the chain of reasoning leading to a validated system. These techniques cannot replace careful system design, but they do provide a last-ditch safety guarantee in the presence of a serious malfunction.

REFERENCES

• 1: Luca Abeni and Giuseppe Lipari. Compensating for interrupt process times in real-time multimedia systems. In Proc. of the 3rd Real-Time Linux Workshop, Work in Progress Session, Milan, Italy, November 2001.
• 2: I. Broster , A. Burns, An Analysable Bus-Guardian for Event-Triggered Communication, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.410, December 03-05, 2003
• 3: Intel Corporation. 21143 PCI/CardBus 10/100Mb/s Ethernet LAN Controller, October 1998. ftp://download.intel.com/design/network/manuals/27807401.pdf.
• 4: Uwe Dannowski , Hermann Härtig, Policing Offloaded, Proceedings of the Sixth IEEE Real Time Technology and Applications Symposium (RTAS 2000), p.218, May 31-June 02, 2000
• 5: 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
• 6: Jakob Engblom, Andreas Ermedahl, Mikael Nolin, Jan Gustafsson, and Hans Hansson. Worst-case execution-time analysis for embedded real-time systems. Journal of Software Tool and Transfer Technology (STTT), 4(4):437--455, August 2003.
• 7: Ethernut: Tiny embedded Ethernet devices. http://www.ethernut.de.
• 8: Laurent George, Nicolas Rivierre, and Marco Spuri. Preemptive and non-preemptive real-time uni-processor scheduling. Technical Report 2966, INRIA, Rocquencourt, France, September 1996.
• 9: Dan Hildebrand, An Architectural Overview of QNX, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.113-126, April 27-28, 1992
• 10: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 11: Kevin Jeffay , Steve Goddard, A Theory of Rate-Based Execution, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.304, December 01-03, 1999
• 12: Michael B. Jones , Daniela Roşu , Marcel-Cătălin Roşu, CPU reservations and time constraints: efficient, predictable scheduling of independent activities, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.198-211, October 05-08, 1997, Saint Malo, France
• 13: Scott Karlin and Larry Peterson. Maximum packet rates for full-duplex Ethernet. Technical Report TR-645-02, Princeton University, February 2002.
• 14: H. Kopetz, The Time-Triggered Model of Computation, Proceedings of the IEEE Real-Time Systems Symposium, p.168, December 02-04, 1998
• 15: Ian Leslie, Derek McAuley, Richard Black, Timothy Roscoe, Paul Barham, David Evers, Robin Fairbairns, and Eoin Hyden. The design and implementation of an operating system to support distributed multimedia applications. IEEE Journal on Selected Areas in Communications, 14(7):1280--1297, September 1996.
• 16: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 17: Thomas Lundqvist , Per Stenström, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999 [doi>10.1023/A:1008138407139]
• 18: Clifford W. Mercer, Stefan Savage, and Hideyuki Tokuda. Processor capacity reserves for multimedia operating systems. In Proc. of the IEEE Intl. Conf. on Multimedia Computing and Systems, May 1994.
• 19: Jeffrey C. Mogul , K. K. Ramakrishnan, Eliminating receive livelock in an interrupt-driven kernel, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.217-252, Aug. 1997 [doi>10.1145/263326.263335]
• 20: Charles Murray and Catherine Bly Cox. Apollo: The Race to the Moon. Simon and Schuster, 1989.
• 21: Jason Nieh , James G. Hanko , J. Duane Northcutt , Gerard A. Wall, SVR4UNIX Scheduler Unacceptable for Multimedia Applications, Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video, p.41-53, November 03-05, 1993
• 22: OpenCores. http://www.opencores.org.
• 23: John Regehr , Alastair Reid , Kirk Webb , Michael Parker , Jay Lepreau, Evolving real-time systems using hierarchical scheduling and concurrency analysis, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.25, December 03-05, 2003
• 24: John Regehr , John A. Stankovic, Augmented CPU Reservations: Towards Predictable Execution on General-Purpose Operating Systems, Proceedings of the Seventh Real-Time Technology and Applications Symposium (RTAS '01), p.141, May 30-June 01, 2001
• 25: Manas Saksena and Yun Wang. Scalable real-time system design using preemption thresholds. In Proc. of the 21st IEEE Real-Time Systems Symp. (RTSS), Orlando, FL, November 2000.
• 26: Lui Sha, Ragunathan Rajkumar, and Shirish S. Sathaye. Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proc. of the IEEE, 82(1):68--82, January 1994.
• 27: Brinkley Sprunt, Lui Sha, and John P. Lehoczky. Aperiodic task scheduling for hard real-time systems. Real-Time Systems Journal, 1(1):27--60, June 1989.
• 28: TimeSys Corporation. TimeSys Linux. http://timesys.com/.
• 29: K. W. Tindell , A. Burns , A. J. Wellings, An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems, v.6 n.2, p.133-151, March 1994 [doi>10.1007/BF01088593]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management

General Terms:
Design, Performance, Reliability

Keywords:
embedded, interrupts, overload, scheduling