SourceForge.net Logo

The Project

For lack of a better SourceForge name, mmLinux (multimedia linux) is a project dedicated to adding real time extensions to the Linux kernel. SourceForge page here:

	http://sourceforge.net/projects/mmlinux/
	IRC channel #mmlinux/irc.freenode.net

This project is created to explore BSD/OS SMPng style concepts and techniques, such as heavy weight interrupts (interrupt threads), blocking mutexes with priority inheritance (simple priority inheritence and priority ceiling emulation) and how these mechanisms can make a stock Linux kernel "mostly preemptive". Fully preemptive kernels are an intrinstic property of nearly all real time operating systems.

This is the next logical step forward from Robert Love's preemption work that is now included in 2.6+. This patch has adds some additional preemption critical sections primitives and semantics into Linux.

The first part of this involves merging TimeSys's preemption patches into a recent version of 2.6.x. These patches add two fundamental changes to the kernel: 1) replacement of standard spinlocks using sleeping mutexes with priority inheritance and 2) the use of interrupt threads with respect to scheduler priority.

(1) is important because critical sections bounded by spinlocks are atomic entities to the system scheduler and cannot be preempted until they finish executing by releasing the spinlock. The use of sleeping locks, however, allows for preemption anywhere inside these critical sections and makes it possible to preempt the active thread so that another thread of higher priority can respond to events. This "preemptability" is a key property of real time systems.

The use of (2) supports the new concurrency model by processing interrupts in a thread and handle them as if it was running on another processor. It allows for the replacement of various Linux interrupt critical sections, spin_lock_irq*(), and other places with blocking locks that permit preemption.

Some papers of interest:

Cases for full preemption in the Linux kernel:

by TimeSys

	http://www.timesys.com/files/whitepapers/Preemptible_Kernel_1_1.pdf
	http://linuxdevices.com/articles/AT6106723802.html

by MontaVista

  	http://www.mvista.com/dswp/PreemptibleLinux.pdf

FreeBSD's SMPng project documentation discussing the use of BSD/OS's SMPng infrastructure:

	http://www.FreeBSD.org/smp/
	http://www.usenix.org/events/bsdcon02/full_papers/baldwin/baldwin_html/index.html

Against The Grain

Priority inversions/violations are created by the use of preemptable critical sections and must be addressed somehow. The two mainstream techniques solving this problem involve some kind of "priority inheritance" that either uses (1) a simple lazy/late detection mechanisms in the lock itself that triggers a kind of priority analysis when detecting the violation or (2) a priority ceiling enabled lock that alters thread priority according to some kind of static analysis of the overall system such as rate monotonic analysis. In the occurance of a simple case, priority inheritance using (1) works by detecting the violation, temporarily raising the priority of the thread owning the resource, allowing it to make progress thereby releasing the lock, and then finally allows the higher priority (priority inverted) thread to acquire it.

There are arguments both "for" and "against" the use of systems like that for RT usage. I have a vague opinion, but I'm going to reserve talking about that until I can get proof of concept kernel working, and then gather some statistics to backing this.

[Priority ceiling emulation, (2), isn't apart of this discussion, since it's a more formal method to resolve complicated priority problems using rate/deadline monotonic analysis. I'm only talking here about simple priority inheritance, (1), as it relates to general purpose OS design.]

Lecture notes explaining priority inversion:

	http://www.informatik.uni-kiel.de/inf/von-Hanxleden/teaching/ss02/rt-prog/lectures/Lecture_24.pdf

Here's a discussion surrounding the use of simple priority inheritance and this sketches the various circumstances with how it is used, along with opinions about it:

Mars Pathfinder's real time application crashing because of a priority inheritance issue:

	http://research.microsoft.com/research/os/mbj/Mars_Pathfinder/Mars_Pathfinder.html

For priority inheritance:

	http://linuxdevices.com/articles/AT5698775833.html

Against priority inheritance:

  	http://linuxdevices.com/articles/AT7168794919.html
Application Techniques

A very good article, from author that is "against" priority inheritance, about how applications not depending on the heavy use of fixed priority scheduling should be constructed. It is a good survey of real time programming constructs that includes the use of lockless algorithms and other things that simplify locking/interrupt handling for "just in time" style applications under RTLinux. It also discusses how the classic Mars Pathfinder failure is misunderstood because of an "implicit synchronization" point inside the application. It's very interesting. Although it's about real time applications techniques, it can be use as a commentary on a broader discussion of SMP kernel development and the use of light weight locking structures inside the Linux kernel. This stands in contrast to how both Solaris and FreeBSD-current are currently built and have a tendency to be overly complicated. FreeBSD's particular use of BSD/OS's SMP facilities is particularly over complicated.

This article is a very good read and indirectly criticizes what might be an abuse of priority inheritance techniques in general purpose operating systems. It basically implies that priority inheritance techniques are broadly misused to cover up contention problems inside the kernel, which then creates weird scheduling problems. This stands in contrast to development attitudes of real time operating systems, such as QNX and TimeSys Linux, where simple priority inheritance is used sparingly to correct for specific priority inversion problems inside an application. There seems to be a historical and intellectual disjointedness between both groups with regard to how these techniques are use. This seperation needs to be elaborated on later, specifically the over use of it in general purpose operating systems.

I basically agree his, Victor's, technical analysis as well as his suggestions regarding the design of RT applications, but not his conclusion about why priority inheritance should be completely excluded from a RTOS. It is too extreme and can't handle certain overload situations properly such as long held critical sections for complex algorithms. However, it did change my previous view point and I now believe that using simpler locking, with emphasis on the removal of contention, is the correct solution for a scalable multiprocessing kernel design rather than abusing priority inheritance techniques and the scheduler to work around latency problems. More on this later. The article:

  	http://linuxdevices.com/articles/AT3209822608.html

Current Logs and Downloads

This is a log of my current work with a rough outline of what I've been thinking here. Compilable (made up word) code, but in need of serious debugging (hot off rsync :)) source code here.

Future

Incorporating these BSD/OS 5.x concepts, via the TimeSys Linux patches, will hopefully enable the stock Linux scheduler, or other QoS schedulers build on top of it, to have much stronger scheduling semantics and precise control over CPU resource allocation for the entire operating system. Not exactly sure what that means [:-)]. But the assumption here is that the combination of low latency response to high resolution timers, <50us, would enable a resource allocation schedulers to throttle an IO channel as a result of controlling a thread specifically attached to that IO channel. "quality of service" control would then be inheritent for all kernel resources. High latency would otherwise make temporally aware schedulers like this less effective. This goes far beyond what traditional schedulers do in Unix and other operating systems.

My hope is that some off shoot of the Linux kernel would be able to achieve the real time capabilties of Silicon Graphic's IRIX, yet integrate some of the more modern real time operating system research innovations like CMU's scheduler reservations into the operating system. The first step in order to achieve this is to make Linux pervasively hard real time.

Like this:

	http://www-2.cs.cmu.edu/~rajkumar/linux-rk.html

and this:

	http://www.srcf.ucam.org/~dmi1000/linux-srt/

A more novel and adaptive implementation of scheduler reservations using a CBS (constant bandwidth server) algorithm:

	http://www.linuxdevices.com/articles/AT6078481804.html

Multiprocessor extensions to scheduler reservations:

	http://research.microsoft.com/~mbj/papers/tr-99-59_abstract.html
"The Fourth Real Time Linux Workshop" links:

Real time Linux links to steal ideas from:

	http://linuxdevices.com/articles/AT6476691775.html
IRIX REACT/pro Real Time Links

... related to this project.

Silicon Graphic's REACT/pro documenting their real time facilities such as the "frames" scheduler and how it can be driven by a vertical retrace interrupt (VBL) to sync up with video redrawing. It's a bit old school, but is still a very interesting read since it is the closest production system to what my goals are at this time:

	http://techpubs.sgi.com/library/tpl/cgi-bin/getdoc.cgi?coll=0650&db=bks&srch=&fname=/SGI_Developer/REACT_PG/sgi_html/pr02.html

Shielded processors (akin to IRIX processor isolation for RT tasks):

	http://www.linuxdevices.com/articles/AT2643744995.html

Out Of Band Things (not that off topic)

More evil things concerning synchronization, RCU (read-copy-update) papers:

	http://lse.sourceforge.net/locking/rcupdate.html