Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm trying to find a way to write an application with lock-free IPC on Linux, in C, with multi-core processors.

Let's assume I have process 1 and process 2 that write to a FIFO or shared memory. Then process 3 and process 4 will read from that shared memory or FIFO.

Is this possible with a lock-free algorithm?

Your guidance is highly appreciated.

share|improve this question
    
Can you give some indications or a reference to some external documentation regarding lock-free communication? What is meant exactly with this term? –  Giorgio Jul 21 '12 at 9:07
    
    
If I understand correctly, the problem is the concurrent writes (1, 2) and the concurrent reads (3, 4). The synchronization between writers and readers is already covered by the algorithm described on the linked page. –  Giorgio Jul 21 '12 at 15:38

3 Answers 3

I have seen reference to using ring buffers, and controlled access the location pointers to eliminate or reduce the need for locks. It does not eliminate the need for waits though, and should only work then a ring buffer has one writer and one reader. In your case you would need at least two buffers.

The mechanism as I understand it is:

  • writer waits until there is an open slot (last + 1 != current)
  • writer writes entry in ring buffer.
  • writer updates last entry pointer.

  • reader waits until there is an available entry in the ring buffer (last != current).

  • reader processes entry.
  • reader increments current pointer.

Depending on the wait time used this can either add latency for new items in an empty queue, or burn a lot of CPU cycles in the wait loop. The order of updating the pointer and strict separation of write access is critical for this to work. The writer is only allowed to write the ring buffer entry before incrementing the pointer to make it available to the reader.

share|improve this answer
    
And I've found this one as well on the wikipedia, looks interesting, haven't tried it though concurrencykit.org –  poly Jul 21 '12 at 15:45

Yes it's possible. We use one of the algorithms of the lock-free queue in our project. But these algorithms are really not obvious. If you want to understand them in depth you should be ready to spent couple months for it.

share|improve this answer

Inter process communication cannot be lock-free. Only inter-thread. As far as I am aware.

share|improve this answer
    
I think "lock free" is an attribute of the mechanism, not of the user. The difference between threads and processes becomes pretty thin when you add things like shared memory to the mix. –  tylerl Jul 24 '12 at 5:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.