LITMUS^RT: Linux Testbed for Multiprocessor Scheduling in Real-Time Systems

Dr. James H. Anderson & Students, The University of North Carolina at Chapel Hill

NOTE: This web page discusses an older version of LITMUSRT. Please use the current version unless you have specific interest in the 2010 series.

About

The LITMUSRT project is a soft real-time extension of the Linux kernel with focus on multiprocessor real-time scheduling and synchronization. The Linux kernel is modified to support the sporadic task model and modular scheduler plugins. Both partitioned and global scheduling is supported.

LITMUSRT is the subject of Prof. Anderson's RTNS'10 keynote address. Please have a look at the linked slides for an in-depth discussion of our motivation, the project, and recent research.

Goals

The primary purpose of the LITMUSRT project is to provide a useful experimental platform for applied real-time systems research. In that regard, LITMUSRT provides abstractions and interfaces within the kernel that simplify the prototyping of multiprocessor real-time scheduling and synchronization algorithms (compared to modifying a "vanilla" Linux kernel). As a secondary goal, LITMUSRT serves as a proof of concept, showing that algorithms such as PFAIR can be implemented on current hardware. Finally, we hope that parts of LITMUSRT and the "lessons learned" may find value as blueprints/sources of inspiration for other (both commercial and open source) implementation efforts.

Non-Goals

LITMUSRT is not a production-quality system, and we have currently no plans to turn it into one. LITMUSRT is not "stable," i.e., interfaces and implementations may change without warning between releases. POSIX-compliance is not a goal; the LITMUSRT-API offers alternate system call interfaces. While we aim to follow Linux-coding guidelines, LITMUSRT is not targeted at being merged into mainline Linux. Rather, we hope that some of the ideas protoyped in LITMUSRT may eventually find adoption in Linux.

Current Version

The current version of LITMUSRT is 2010.2 and is based on Linux 2.6.34. It was released on 10/21/2010 and includes plugins for the following scheduling policies:

Please refer to the download and installation sections for details.

Earlier versions, which supported additional scheduling policies, are discussed on separate pages dedicated to the LITMUSRT 2008 (based on Linux  2.6.24) and LITMUSRT 2007 (based on Linux 2.6.20) series.

The first version of LITMUSRT (implemented in Spring 2006) was based on Linux 2.6.9.

Development Plans

There are plans to port LITMUSRT to PowerPC and ARM platforms. Please contact us for details.

Support

The LITMUSRT development effort is being supported by grants from AT&T, IBM, and Northrop Grumman Corps.; the National Science Foundation (grants CNS 0834270 and CNS 0834132); the U.S. Army Research Office (grant W911NF-09-1-0535); and the Air Force Office of Scientific Research (grant FA 9550-09-1-0549).

Collaborators

The LITMUSRT project is led by Dr. James H. Anderson.

The developers of the current version are:

Additional collaborators contributed to the previous LITMUSRT 2008 and LITMUSRT 2007 versions.

We always welcome new contributors; please see Development below for information on how to get access to our source code repository.

Publications

  1. A.Bastoni, B. Brandenburg and J. Anderson, “An Empirical Comparison of Global, Partitioned, and Clustered Multiprocessor Real-Time Schedulers”, Proceedings of the 31th IEEE Real-Time Systems Symposium, to appear, December 2010. PDF. Longer version with all graphs: PDF

  2. J. Anderson, “Real-Time Multiprocessor Scheduling: Connecting Theory and Practice ”, keynote address, 18th International Conference on Real-Time and Network Systems, November 4, 2010. PPTX.

  3. G. Elliott and J. Anderson, “Real-Time Multiprocessor Systems with GPUs”, Proceedings of the 18th International Conference on Real-Time and Network Systems, to appear, November 2010. PDF. Longer version with appendices: PDF

  4. A.Bastoni, B. Brandenburg and J. Anderson “Cache-Related Preemption and Migration Delays: Empirical Approximation and Impact on Schedulability”, Proceedings of the Sixth International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, , pp. 33-44, July 2010. PDF.

  5. B. Brandenburg and J. Anderson, “On the Implementation of Global Real-Time Schedulers”, Proceedings of the 30th IEEE Real-Time Systems Symposium, pp. 214-224, December 2009. PDF. Longer version with all graphs: PDF.

    For reference, all evaluated plugins are provided as part of the following patch (against version 2008.3).

  6. B. Brandenburg and J. Anderson “Reader-Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems”, Proceedings of the 21st Euromicro Conference on Real-Time Systems, pp. 184-193, July 2009. PDF. Long version with blocking terms: PDF.

  7. J. Calandrino and J. Anderson “On the Design and Implementation of a Cache-Aware Multicore Real-Time Scheduler”, Proceedings of the 21st Euromicro Conference on Real-Time Systems, pp. 194-204, July 2009. PDF.

  8. M. Mollison, B. Brandenburg, and J. Anderson “Towards Unit Testing Real-Time Schedulers in LITMUSRT”, Proceedings of the Fifth International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, pp. 33-39, July 2009. PDF.

  9. B. Brandenburg and J. Anderson, “A Comparison of the M-PCP, D-PCP, and FMLP on LITMUSRT”, Proceedings of the 12th International Conference on Principles of Distributed Systems, pp. 105-124, December 2008. PDF.

  10. B. Brandenburg, J. Calandrino, and J. Anderson, “On the Scalability of Real-Time Scheduling Algorithms on Multicore Platforms: A Case Study”, Proceedings of the 29th IEEE Real-Time Systems Symposium, pp. 157-169, December 2008. PDF.

  11. B. Brandenburg and J. Anderson, “An Implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP Real-Time Synchronization Protocols in LITMUSRT”, Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 185-194, August 2008. PDF.

    Note: The work described in this paper took part in a branch that is currently not part of the main distribution. For reference, we provide the branch as a separate download:

    Please don't use this version for active development. If you are interested in this work, it would be best to first port the desired features to a current version of LTIMUSRT and merge them into the main distribution.

  12. A. Block, B. Brandenburg, J. Anderson, and S. Quint, “An Adaptive Framework for Multiprocessor Real-Time Systems”, Proceedings of the 20th Euromicro Conference on Real-Time Systems, pp. 23-33, July 2008. PDF.

  13. B. Brandenburg, J. Calandrino, A. Block, H. Leontyev, and J. Anderson, “Real-Time Synchronization on Multiprocessors: To Block or Not to Block, to Suspend or Spin?”, Proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 342-353, April 2008. PDF.

    Extended version, including all graphs: PDF.

  14. B. Brandenburg, A. Block, J. Calandrino, U. Devi, H. Leontyev, and J. Anderson, "LITMUSRT: A Status Report", Proceedings of the 9th Real-Time Linux Workshop, pp. 107-123, November 2007. PDF.

  15. B. Brandenburg and J. Anderson, "Integrating Hard/Soft Real-Time Tasks and Best-Effort Jobs on Multiprocessors", Proceedings of the 19th Euromicro Conference on Real-Time Systems, pp. 61-70, July 2007. PDF.

  16. J. Calandrino, H. Leontyev, A. Block, U. Devi, and J. Anderson, "LITMUSRT: A Testbed for Empirically Comparing Real-Time Multiprocessor Schedulers ", Proceedings of the 27th IEEE Real-Time Systems Symposium, pp. 111-123, December 2006. PDF.

Download

The source code of LITMUSRT is made available as open source under the terms of the GNU General Public License (GPL). LITMUSRT is released as a patch against Linux. Additionally, it is also available as a git repository (see Development below).

The current release of LITMUSRT is 2010.2. It consists of our Linux kernel modifications in the form of a patch against Linux 2.6.34 and liblitmus, the user-space API for real-time tasks, as well as ft_tools, a collection of tools used for tracing with Feather-Trace (which is part of the LITMUSRT patch).

LITMUSRT 2010.2

Based on Linux 2.6.34. Released in October 2010.

Files:

Major changes since LITMUSRT 2010.1:

LITMUSRT 2010.1

Based on Linux 2.6.32. Released in May 2010.

Files:

Major changes (since LITMUSRT 2008.3):

Please note that the current implementation is a prototype with certain limitations. Most notably, it is not secure in a multiuser context, i.e., real-time system calls do not require superuser privileges.

Older releases: LITMUSRT 2008 series, LITMUSRT 2007 series.

Installation

The current release of LITMUSRT consists of an extension of the Linux kernel that adds support for the sporadic task model, a scheduler plugin infrastructure, and some scheduler plugins, as well as a user-space library that provides the LITMUSRT real-time API. Note that the current implementation only works on the Intel x86-32 and x86-64 architectures.

Patching the Kernel

The extension to the Linux kernel is released as a patch against Linux 2.6.34. To install the LITMUSRT kernel, first download the Linux kernel 2.6.34 and untar it in a directory of your choice (hereafter referred to as $DIR). Second, apply the LITMUSRT patch (see Section Download) and configure, compile, and install the kernel as usual. The patch is -p1 applicable. To summarize, the LITMUSRT kernel can be obtained, patched, and compiled with the following commands:

cd $DIR
# get Linux 2.6.34
wget http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.34.tar.bz2
tar xjf linux-2.6.34.tar.bz2
wget http://www.cs.unc.edu/~anderson/litmus-rt/download/2010.2/litmus-rt-2010.2.patch
mv linux-2.6.34 litmus2010
# apply the LITMUS RT patch
cd litmus2010
patch -p1 < ../litmus-rt-2010.2.patch
# create a working kernel configuration
#  - select HZ=1000
#  - enable in-kernel preemptions
#  - disable NO_HZ
#  - don't use power management options like frequency scaling
#  - disable support for group scheduling
#  - disable "Write protect kernel read-only data structures" (in kernel debug)
make menuconfig
# compile the kernel
make bzImage
make modules
# proceed to install kernel, build initrd, etc.
...

When configuring the kernel, note that there is a menu (at the very end of the list) with LITMUSRT-specific configuration options. For reference, we provide sample 32-bit and 64-bit configurations that are known to work under KVM.

Libraries

The user-space library for real-time tasks, liblitmus, depends on the LITMUSRT kernel kernel and provides its own build system (based on scons). In order to compile liblitmus, you need to adjust the variable LITMUS_KERNEL in the .config file to point to your copy of the kernel. The variables required for building liblitmus can be listed using scons -h command. For reference, we provide a sample config file. Sample output of scons -h is as shown below.

 
scons -h
scons: Reading SConscript files ...
scons: done reading SConscript files.

=============================================
liblitmus --- The LITMUS^RT Userspace Library

There are a number of user-configurable build
variables. These can either be set on the
command line (e.g., scons ARCH=x86) or read
from a local configuration file (.config).

Run 'scons --dump-config' to see the final
build configuration.

Build Variables
---------------

LITMUS_KERNEL: Where to find the LITMUS^RT kernel. ( /path/to/LITMUS_KERNEL )
    default: ../litmus2010
    actual: ../litmus2010

ARCH: Target architecture. (x86_64|sparc64|x86|i686)
    default: x86_64
    actual: x86_64

Use scons -H for help about command-line options.

  

To summarize, the liblitmus can be obtained and compiled with the following commands:

 
cd $DIR
wget http://www.cs.unc.edu/~anderson/litmus-rt/download/2010.1/liblitmus-2010.2.tgz
tar xzf liblitmus-2010.2.tgz
cd liblitmus 
# change LITMUS_KERNEL in .config to point to the kernel source
scons

Please refer to the documentation on how to use the LITMUSRT real-time API as provided by liblitmus.

Documentation

Unfortunately, most of the documentation has yet to be written. To get an overview of the architecture of the kernel extension, we recommend reading the paper “LITMUSRT: A Status Report”.

Real-Time Scheduling Policies

The kernel contains the following real-time scheduling policy implementations:

Only one policy can be active at any time. Initially (i.e., during and after boot), the "Linux" policy is active. You can use the tool showsched (part of liblitmus) to display the name of the currently active policy.

Changing the Active Policy

You can use the tool setsched (part of liblitmus) to select a new plugin at run time.

Screen shot of setsched

Only root can change the active policy, and only when there are no real-time tasks present.

If you do not have the dialog utility installed, then you can still used setsched by passing the desired scheduling policy as a commandline parameter, e.g. type setsched PFAIR to activate the PFAIR plugin.

Selecting the C-EDF Cluster Size

The C-EDF plugin can create clusters based on the sharing of L2 or L3 caches. When the plugin is activated (see above), it configures clusters based on the value last written to /proc/litmus/cluster_cache (either "L2" or "L3"). Note that the C-EDF must be reloaded (for example by switching to the Linux plugin and back to C-EDF) to enact a change to the desired cluster size; changing the cluster size while C-EDF is active is not supported.

Writing Real-Time Tasks

The user space library that provides the LITMUSRT API, liblitmus, contains two example real-time tasks (base_task.c and base_mt_task.c) that both illustrate how to use the API and provide a skeleton for real-time task development. To get started with development, please take a look at these example programs.

Tracing Overheads and Scheduling Decisions

LITMUSRT provides numerous tracing facilities that are discussed in-depth in the tutorial Tracing with LITMUSRT.

Please contact the current maintainer if you have any questions.

Development

Patches and suggestions are very welcome! Both the LITMUSRT kernel and liblitmus are available as a public git repository at http://www.cs.unc.edu/~anderson/litmus-rt/public-repository.

Credits

Valid XHTML 1.0 Strict

Linux is a registered trademark of Linus Torvalds.
The LITMUSRT logo was designed by Jasper McChesney of Break for Sense Design.
Web design by Björn Brandenburg.