Another look at Peterson

December 6, 2008

I had another read of Bartosz Milewski recent blog post about the different memory orderings of c++0x.

The most interesting thing about the blog post (that I missed last time) was actually the proposed Peterson locking algortithm that used some none default c++0x  memory orderings for the stores and loads of its atomic variables. It turns out that his proposed implementation is broken. Yupp, that’s right, even some of the experts on concurrency can get lost when straying from the straight and narrow road of  default sequential memory ordering. Exactly why the implementation is broken, and another implementation that actually works (by Dmitriy V’jukov) , is explained (or even proven) on Anthony Williams blog.

Anthony’s blog post was a very informative read. I probably read it ten times until I (think I) understood why one implementation was broken and the other wasnt. Lots of “ahaa – no wait a minute – oh OK, I think I see what you did there” moments. Reasoning about concurrency is allot like pealing an onion, there is always another layer underneath that you didn’t know about. 

(The problem as I understand it, was that the atomic variable “victim” was read and written by both threads,  and one needed to make sure that the writes that happen before on the first  thread where synchronized to the the reads that happen after on the second thread. Because the memory ordering for the write on the first thread was release only, and the read on the second thread was acquire only, the second thread could read an old value from it invalid cached even though the variable had been overwritten by the the first thread.)

Writing correct concurrent code is an interesting but complex task, and anyone claiming different are probably writing broken code but dont realize. If guess the thing to take from all this is that unless you can prove that its Okay to use a more relaxed memory model than the sequential consistent one, you really shouldn’t.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: