threadsafe single-consumer, single-producer FIFO on embedded system

Question

I have a TI DSP (TMS320F28235 if anyone cares) that I need to implement a FIFO for queueing information between main-loop code and an interrupt. High-speed execution for this queue is very critical but so is proper operation, and I'm not sure whether I can get away with implementing a FIFO without any explicit synchronization, or if not, where I have to disable interrupts.

I found this page and was wondering if anyone here could comment on its applicability.

Answer 1

The page you found is precisely applicable to your situation. It relies only on word reads and writes being atomic. It is vulnerable to hardware that silently reorders loads and stores. On the other hand, just about every other synchronization algorithm known to Man is also vulnerable to that particular crock.

If you feel like doing some serious computer archaeology, dig up the circular buffer descriptions for the CDC 6600 operating systems. CDC originally developed the technique for communicating between multiple physical processors in the 6600.

Answer 2

NEW and Correct Information

The reference for the instruction set can be found here.

To emulate a lock it is suggested in the documentation that interupts be disabled.

Example ; Make the operation ”VarC = VarA + VarB” atomic:
    DINT ; Disable interrupts (INTM = 1)
    MOVL ACC,@VarA ; ACC = VarA
    ADDL ACC,@VarB ; ACC = ACC + VarB
    MOVL @VarC,ACC ; Store result into VarC
    EINT ; Enable interrupts (INTM = 0)

-- Algorithm pointers --

Interrupts pre-empt main-loop and apparently atomic operations do not exist. Your main-loop has to disable interrupts while it is popping. Since disabling interrupts is like owning a lock in this context you could implement the queue as contiguous memory or ontop of a slist. The former means copying out the memory to the stack of the main-loop on pop, which might be slower -- however provided your FIFO has enough memory you should not have to allocate slist nodes from a heap -- which means no memory management headaches. Of course, memory management headaches won't exist if the slist nodes are of a uniform size.

So, for a pop you must disable interrupts and remove the element -- once done, re-enable the interrupt. For interrupt vectors it is business as usual (you might need to disable the interupts during interupt vector processing -- this is controller dependant).