BT

Using Messaging and Scheduling for Lock-free Access to Shared State

by Jonathan Allen on Apr 27, 2011 |

In a message passing system there may be times when mutable data must be shared amongst many tasks. In traditional programming this would be handled by a read-writer block, which would allow one writer thread to block all other threads while it updates the shared data. With high performance systems one doesn’t want to ever block threads, so an alternate solution is needed.

One interesting technique is the use of a message passing API and a set of task schedulers. Actions that require only reading data would be processed using a task scheduler that allows as many concurrent threads as there are available cores. As each message is processed its thread is immediately reused for the next available message.

Messages that may need to update the shared data use a separate task scheduler that only allows one message to be processed at a time. This is known as an exclusive scheduler.

CE Scheduler

The magic occurs with the use of what TPL Dataflow calls the “Concurrent-Exclusive Scheduler Pair”. This object combines the two task schedulers, one for the concurrent tasks and one for the exclusive tasks. When there is a message waiting to be processed on the exclusive scheduler no new messages are sent to the concurrent scheduler. Any threads that would have been used by the concurrent scheduler are returned to the thread pool just as if there were no more messages to be processed. Once the exclusive scheduler is done processing all its messages the concurrent scheduler is woken up again and may resume processing when a thread becomes available.

While this technique eliminates the problem with blocking threads on a read-writer lock, care must still be taken to use this technique correctly. Just as with a reader-writer lock, too many write messages can prevent the read messages from being processed. There is also a risk that something that isn’t under the control of the scheduler could update the shared data in an unsafe manner.

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

--- by N T

Another rehash of techniques known since the '70s, presented as an 'innovation'. Maybe they should patent it as well.

Re: --- by Jonathan Allen

The obsession with innovation is rather harmful to the industry. Techniques like this are certainly old, but that doesn't mean they are useless. Nor does it necessarily mean they are well known.

The reason I reported on this technique is that it is far more applicable to developers than it was in the past. You could always do this by rolling your own libraries and chaining callbacks but few had the time. Recently it has become difficult to find a language that isn't planning on supporting this out of the box, soon this will be a required skill for backend developers just as understanding reader/writer locks are today.

Re: --- by clem clem

Cool stuff, although those techniques might be old, they're not necessarily widespread.

a question by Ming Lee

Sorry, I may not get the full point. What's exactly the difference between this approach(Concurrent-Exclusive Scheduler Pair) and traditional RWL?

I guess the main difference comes from the fact this approach is asynchronous since it is message-passing based, in other word, reader/writer thread can send data access/update request can continue working on other stuff, rather than to be blocked with RWLock. Is my understanding right?

Re: a question by Jonathan Allen

That is how I understood it. All the literature I've been reading on both .NET and Erlang stress how important it is to not block threads.

Though it makes me wonder if message passing is vital or if you could do the same thing using just tasks and schedulers. Asynchronous programming and message passing work well together but are separate techniques.

Re: a question by Ming Lee

Thanks for clarification.

I think the 'lock-free' effect comes from the thread sending NON-BLOCKING request to read/update the shared state. In fact, I have implemented a kind of RWL by using the similar approach but the thread just sending blocking request.

I believe whether or not to use such approach instead of RWL depends on how important the up-to-date value of the share data. In other words, RWL is still be best choice if latest updated value of the share data is most important. This approach is such better if thread/process efficiency is more important than how up-to-date value is.

-- by xiong kasey

I think i don't get the point....what is the benefit compare with read-write lock?

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

7 Discuss

Educational Content

General Feedback
Bugs
Advertising
Editorial
InfoQ.com and all content copyright © 2006-2014 C4Media Inc. InfoQ.com hosted at Contegix, the best ISP we've ever worked with.
Privacy policy
BT