The Art of Thread Synchronization

I attended a NETDA lecture by Jeffrey Richter on Monday, in which spoke on “The Art Of Thread Synchronization.” Last year, Jeffrey talked about new Platform vs Library versioning features in Orcas and Longhorn, the contents of which is mentioned in a prior post.

Jeffrey Richter is co-founder of Wintellect, a well-known training and consulting firm. He wrote Applied Microsoft .NET Framework Programming, which is a must have for advanced .NET developers. He is a contributing editor at MSDN Magazine and also consults with both the Microsoft .NET Framework team and the Indigo team.

He reviewed the variety of threading mechanisms in .NET, and demonstrated how one could implement some of the same locks in handwritten code, superior to the versions included in the framework in both performance (eliminating kernel mode transitions), correctness, and fairness (locks are served in FIFO order). He made clear that many of the System.Threading classes are not very optimized or optimal in their performance. He reimplemented a SpinLock, an Optex lock, a ReaderWriterLock and a few others. He also showed how one could write Interlocked versions of other operations such as the bitwise AND operator.

Some problems in the framework include the following:

• Whidbey includes Int64 versions of CompareExchange, Exchange, Increment and Add in the Interlocked class. Unfortunately, these functions can’t be guaranteed to work on a 32–bit processor, and thus shouldn’t really be included in the framework.
• ReaderWriterLock has a very serious flaw, which prevented its use in MSN website, because it could lead to starvation for writers, if too many readers are using the lock. Richter produced a superior ReaderWriterLock implementation, that both performs better and gives priority to writers to eliminate starvation; this new lock will be included in the Orcas version of the framework
• Many of the framework’s locks perform poorly because of excessive kernel mode transitions. He showed benchmark results, which demonstrated an order of magnitude or two deterioration in performance due to kernel mode transitions alone. For the fastest performance, a developer should rely only on the methods on the Interlocked class, which neither waits nor transitions to kernel mode. Locks should be designed to call into the kernel only during contention, which can be checked for by using Interlocked.CompareExchange.

Jeffrey invented a super-fast thread synchronization lock, SoaReaderWriterLock, that never puts any thread in a wait state. He applied for a patent and sold the idea to Microsoft. Richter urged Microsoft to relax restrictions to the use of the lock. Microsoft agreed to allow the technique to developers of Windows application but not other platforms like Linux.

His description of the lock was very impressive. The lock mechanism works differently from traditionally block schemes which rely on the try-finally mechanism. It is based on Service Oriented Architecture, in which methods are called in a “Fire and Forget” manner. A delegate is first passed to a Lock when it is first entered. The delegate is either service immediately or sent to a reader or writers queue, where it will later be dispatched to a threadpool. In effect, the application becomes the scheduler instead of the operation system: After one delegate executes, the next available one is called immediately without any intermediate wait state.

The Wintellect site currently contains the PowerCollections library, which works only on Whidbey, but Jeffrey Richter will soon be adding a PowerThreading library as well to correct for the deficiencies in the .NET Framework. The SOA lock will also be included with the aforementioned restrictions.

After the talk, I spoke to Richter about his prior versioning talk, and he mentioned that there was a lot of pushback from groups all over Microsoft and that the versioning strategy will not survive as originally planned. Software development apparently is a fluid process.

Comments

[Matt]

Are the ReaderWriterLock issues documented anywhere on the web? Where can I find more details of SoaReaderWriterLock>

[Wesner Moise]

You'll have an opportunity to learn more about when Richter releases his PowerThreading library. At that time, I'll mention it on my blog.

[Sean McLeod]

Is the Jeffrey's talk available in electronic form, slides, audio recording etc.?

[Wesner Moise]

Wintellect does not allow slides of talks to be displayed, but Richter may produce a PDF file. You would simply need to check the Wintellect site for more information.

Another thing I wanted to note is that Richter was asked to write a Concurrency column in MSDN. He might do it, but most likely not because he has limited time.

[Robert Hurlbut]

Thanks for this link. Concurrency and .NET is a topic I am very interested in and I hope to put some of my own research and others like this into articles and/or book.

[Daniel Moth]

Blog link of the week 15

[Anonymous]

"He applied for a patent and sold the idea to Microsoft under the condition that the technique can still be freely used for Windows application but not other platforms like Linux." -- god. what a schmuck.

[zzz]

So which is it? Jeff went for patent or someone at MS came up with the patent idea?

netda: "Jeff co-invented this lock and sold the idea to Microsoft, which is patenting it."

wes: "He applied for a patent and sold the idea to Microsoft. Richter urged Microsoft to relax restrictions to the use of the lock. Microsoft agreed to allow the technique to developers of Windows application but not other platforms like Linux."

anonymous: "He applied for a patent and sold the idea to Microsoft under the condition that the technique can still be freely used for Windows application but not other platforms like Linux."

And now for the obvious question.. Is it really too late to fix atleast some of the issues - why wait for Orcas??

[Wesner Moise]

ZZZ, only individual inventors can patent inventions, not corporations. Individuals can however assign patents to someone else.

[Jeffrey Richter]

I am the inventor of the lock. The patent has been assigned to Microsoft. Microsoft paid me to assign to them the rights. Microsoft has placed the restriction on it that it can only be used on Microsoft platforms including Windows and .NET Fx.

[Chui Tey]

Just from the description alone, it doesn't sound like a lock at all. I must be missing something.

[identy]

Jeffrey Richter, The patent has been assigned to Microsoft. Microsoft paid me to assign to them the rights.... EGO?

[Wesner Moise]

It is a lock, but you need to change the style of writing.

Instead of writing a traditional lock block...

lock(obj)
{
// code inside lock
}
// code after lock

you write somthing like,

myLock.AcquireWriterLock(delegate(LockContext context)
{
// code inside lock here
context.ReleaseLock();
// my code after lock
});

The lock automatically gets released at the end of the call if you forget to release it. In a non-threaded environment, the delegate is immediately called; otherwise, the delegate is called immediately after the currently executed delegate is finished.

[Wesner Moise]

One possibly erroneous remark he made was that it was not possible to have an atomic long operation in a 32–bit machine. See A practical multi-word compare and swap operation

[Wesner Moise]

http://citeseer.ist.psu.edu/harris02practical.html

[Timbo]

Sounds like Continuation Passing Style (here's an explaination: http://www.sidhe.org/~dan/blog/archives/000185.html)
used in the Scheme language. It's also used a lot in Haskell for IO (Monads).

But I don't understand why this would make concurrent programming any easier. Or is it about making it faster, not easier? Or is it just another tool in the toolbox?

[Stephan Eggermont]

Well, it's an American software patent, so nobody knows if it's new and innovative...