Lock Free

Lock Free Data Structures

I got my hands on an ARM Cortex-A9 MPCore development box at work and have been experimenting with lock free data structures. I have permission from Management to put this on SourceForge as soon as Legal gets me the appropriate blurbage to put at the top of each file.

The advantage of lock free structures is that you don't have to disable interrupts, lock the bus, or grab a mutex when you access shared structures.

The disadvantage is that writing lock free algorithms, and getting them to work all the time, is REALLY tricky.

The code I'm working on is intended mainly for real time bare metal apps or proprietary OS running on a multi-core ARMv7 system (ARM11 or Cortex), where Linux or vxWorks would be too slow.

(Apparently) working so far:

FIFO (ring buffer) for passing pointers between cores, between threads, or between ISRs and threads.

LIFO (linked list stack) for e.g. pools of resources such as fixed length message buffers.

lightweight threads

voluntary preemptions only, no scheduling or time slicing

ISR is viewed as a subroutine of the interrupted thread, therefore can "voluntarily" preempt that thread by waking another

intended for real-time bare metal systems (threads never terminate except by power down)

data structures are:

	threads -- each represented by a stack. The current SP value is the thread's "handle".
	ports -- a 32 bit pointer to thread waiting for an event.
	a LIFO of voluntarily preempted threads (those threads which have waked another thread)

primitives are:

	spawn new thread
	wait for an event at a port
	wake the thread waiting at a port

thread states are:

	running (one per CPU)
	waiting for an event
	preempted (linked to the LIFO)

I have been studying how to implement a lock free FIFO queue (linked list with head and tail pointers). This appears to be a more than usually difficult problem. People have been writing papers on this for the last 20 years but no one has a nice clean (and reliable) solution yet. It has been said that the solution to this problem is worth a PhD.

Last modified: December 31, 2009