Why I still like obstruction freedom

Recently I’ve tried to change Shielded to use encounter-time locking. As opposed to the current implementation, which employs commit-time locking, this new version would lock an object on every write attempt. This would certainly speed it up, I figured. No IShielded would have to have thread-local storage for it’s temporary data – if a thread locks a field, it can write directly into some private members*. Commit time checking simplifies, knowing that every changed field must already be locked. Sounds great.

The first thing that broke was a test. Some of them would create and wait for a thread which is in deliberate conflict with them. After changing to encounter-time locking, this produced a deadlock. This is, of course, not a problem, since no thread should do that 😉

But, one thing would not fit into this concept well – the commutes. For as long as a thread keeps a field locked, no other thread can do anything with it, not even a commute. This seriously undermines the concept. The results of the tests might have indicated this, with performance becoming less smooth, the speed varying more during a longer test. (Shielded is full of commutable ops, most notably on Count fields of the included collections.)

Locking a field to make sure a longer running transaction succeeds is easy to do. A Changed event handler which throws (or, I don’t know, Monitor.Wait-s) for all but one thread would do the trick just fine. The encounter-time version was, basically, doing this to EVERY field, and producing very little gain otherwise.

Ennals argues that obstruction freedom is an unnecessary requirement for an STM, and that it could be made faster by removing it. Although much of the argument is true, and an encounter-time solution would be faster, the paper creates another problem. It requires that the value of a field be available without any indirection, in order to reduce cache misses. This makes it impossible to have MVCC, which in turn means that reader progress cannot be guaranteed. A thread which only reads some data will, in the commit-time locking version, proceed without even trying to enter the global lock. With encounter-time locking and the no-indirection requirement, it must block on conflict with a writer, and then be restarted!

Another claim in the paper is made, which seems almost ridiculous. The paper says that obstruction freedom means we are unable to control the number of concurrently executing transactions, and must allow for all N of them to execute in parallel. In all practical settings, nobody would be prevented from counting and limiting the number of parallel transactions simply to be so thoroughly obstruction-free. You are free to start and run them at any pace you please. (See Queue.cs for a simple example.)

All in all, commutes and reader progress are the reasons why Shielded still employs commit-time locking, and is obstruction-free during a transaction run. If needed, locking and parallelism control can easily be added to ensure proper prioritization.

* Something similar was implemented in LocalStorage recently. If there’s only one thread changing a field, it will use a private member for storage.


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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