Lock Free

 

Up

Home
PDP-11
PlayMidiCE
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:

bulletFIFO (ring buffer) for passing pointers between cores, between threads, or between ISRs and threads.
 
bulletLIFO (linked list stack) for e.g. pools of resources such as fixed length message buffers.
 
bulletlightweight threads
bulletvoluntary preemptions only, no scheduling or time slicing
bulletISR is viewed as a subroutine of the interrupted thread, therefore can "voluntarily" preempt that thread by waking another
bulletintended for real-time bare metal systems (threads never terminate except by power down)
bulletdata structures are:
bulletthreads -- each represented by a stack. The current SP value is the thread's "handle".
bulletports -- a 32 bit pointer to thread waiting for an event.
bulleta LIFO of voluntarily preempted threads (those threads which have waked another thread)
bulletprimitives are:
bulletspawn new thread
bulletwait for an event at a port
bulletwake the thread waiting at a port
bulletthread states are:
bulletrunning (one per CPU)
bulletwaiting for an event
bulletpreempted (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