Trustworthy Systems

Improving interrupt response time in a verifiable protected microkernel

Authors

Bernard Blackham, Yao Shi and Gernot Heiser

NICTA

UNSW

Abstract

Many real-time operating systems (RTOSes) offer very small interrupt latencies, in the order of tens or hundreds of cycles. They achieve this by making the RTOS kernel fully preemptible, permitting interrupts at almost any point in execution except for some small critical sections. One drawback of this approach is that it is difficult to reason about or formally model the kernel's behavior for verification, especially when written in a low-level language such as C.

An alternate model for an RTOS kernel is to permit interrupts at specific preemption points only. This controls the possible interleavings and enables the use of techniques such as formal verification or model checking. Although this model cannot (yet) obtain the small interrupt latencies achievable with a fully-preemptible kernel, it can still achieve worst-case latencies in the range of 10,000s to 100,000s of cycles. As modern embedded CPUs enter the 1 GHz range, such latencies become acceptable for more applications, particularly when they come with the additional benefit of simplicity and formal models. This is particularly attractive for protected multitasking microkernels, where the (inherently non-preemptible) kernel entry and exit costs dominate the latencies of many system calls.

This paper explores how to reduce the worst-case interrupt latency in a (mostly) non-preemptible protected kernel, and still maintain the ability to apply formal methods for analysis. We use the formally-verified seL4 microkernel as a case study and demonstrate that it is possible to achieve reasonable response-time guarantees. By combining short predictable interrupt latencies with formal verification, a design such as seL4's creates a compelling platform for building critical real-time systems.

BibTeX Entry

  @inproceedings{Blackham_SH_12,
    address          = {Bern, Switzerland},
    author           = {Blackham, Bernard and Shi, Yao and Heiser, Gernot},
    booktitle        = {EuroSys Conference},
    doi              = {http://doi.acm.org/10.1145/2168836.2168869},
    keywords         = {microkernels, worst-case execution time, hard real-time systems, trusted systems, formal
                        verification},
    month            = apr,
    pages            = {323--336},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/5391.pdf},
    publisher        = {USENIX},
    slides           = {https://trustworthy.systems/publications/nicta_slides/5391.pdf},
    title            = {Improving Interrupt Response Time in a Verifiable Protected Microkernel},
    year             = {2012}
  }

Download