4

I am trying to use Boost's upgrade_lock (using this example, but I run into a starvation issue.

I am actually using the code from this post, but I wanted an up-to-date discussion. I run 400 threads after the WorkerKiller. I run into the exact same problem as anoneironaut, the author of the mentionned post.

I have seen the proposition from Howard Hinnant, but I don't really want to include more external code (moreover I cannot get his to compile as of now) and a comment posted 6 months later states that "Boost uses a fair implementation now" (Dec 3 '12).

The Boost 1.55 documentation states that:

Note the the lack of reader-writer priority policies in shared_mutex. This is 
due to an algorithm credited to Alexander Terekhov which lets the OS decide 
which thread is the next to get the lock without caring whether a unique lock or 
shared lock is being sought. This results in a complete lack of reader or writer
starvation. It is simply fair.".

And the algorithm credited to Alexander Terekhov is the one that Howard Hinnant talks about, so I would expect the 1.55 boost implementation to behave like in Howard Hinnant's answer, which is not the case. It behaves exactly like in the question.

Why is it the case that my WorkerKiller suffers of starvation?

UPDATE: It was observed with this code on:

  • Debian x64, Boost 1.55 (both the Debian version and one compiled from sources), with both clang++ and g++
  • Ubuntu x64, Boost 1.54, with both clang++ (3.4-1ubuntu1) and g++ (4.8.1-10ubuntu9)
Community
  • 1
  • 1
JonasVautherin
  • 7,297
  • 6
  • 49
  • 95
  • What compiler and platform are you running on? I could not reproduce the problem with Boost 1.55 on a VC11 x64 build. – ComicSansMS Feb 14 '14 at 09:35
  • That's interesting. I copied my code [here](https://gist.github.com/anonymous/bd3440d438da82061f22). It was tested on Debian (boost 1.55) and Ubuntu (boost 1.54), using clang++ and g++. – JonasVautherin Feb 14 '14 at 10:17
  • Got it now, I wasn't realising that you were using `upgrade_lock` instead of a plain exclusive lock. – ComicSansMS Feb 14 '14 at 12:05

1 Answers1

2

This is a subtle one. The difference involves the concepts of shared and upgradable ownerships, and their implementations in Boost.

Let's first get the concepts of shared ownership and upgradable ownership sorted out. For a SharedLockable, a thread must decide beforehand whether it wants to change the object (requiring exclusive ownership) or only read from it (shared ownership suffices). If a thread with shared ownership decides it wants to change the object, it first must release its shared lock on the object and then construct a new, exclusive lock. In between these two steps, the thread holds no locks at all on the object. Attempting to construct an exclusive lock from a thread that already holds a shared lock will deadlock, as the exclusive lock constructor will block until all shared locks have been released.

UpgradeLockable overcomes this limitation, by allowing to upgrade a shared lock to an exclusive lock without releasing it. That is, the thread keeps an active lock on the mutex at all times, prohibiting other threads from obtaining an exclusive lock in the meantime. Besides that, UpgradeLockable still allows all operations from SharedLockable, the former concept is a superset of the latter. The question you linked to is only concerned with the SharedLockable concept.

Neither concept, as specified by Boost, requires an implementation to be fair. However, the shared_mutex, which is Boost's minimal implementation for a SharedLockable does give the fairness guarantees quoted in your question. Note that this is an additional guarantee to what the concept actually requires.

Unfortunately, the minimal implementation for upgradable ownership, the upgrade_mutex, does not give this additional gurantee. It still implements the shared ownership concept as a requirement for upgradable ownership, but since fairness is not required for a conforming implementation, they do not provide it.

As pointed out by Howard in the comments, Terekhov's algorithm can be trivially adjusted to work with upgradable locks as well, it's just that the Boost implementation does not support this currently.

Community
  • 1
  • 1
ComicSansMS
  • 51,484
  • 14
  • 155
  • 166
  • Okay, I see. But I don't really get why UpgradeLockable can prevent other threads from obtaining an exclusive lock and not prevent them from obtaining a shared lock... I could use an exclusive mutex to achieve fairness, [like I did in this code](https://gist.github.com/anonymous/4f3f1bbcd7fe565b7876). Anyway, I thought that they all guaranteed fairness, so thanks for your development ;-). – JonasVautherin Feb 14 '14 at 14:07
  • @JonesV Think of it like this: An upgrade lock behaves like a shared lock, with the exception that you can have only one upgrade lock at a time. So an active upgrade lock does prevent other exclusive locks, but not other shared locks (just like an ordinary shared lock). The problem when it comes to fairness is that this behavior does not change when you try to turn the upgrade lock into an exclusive lock: Other shared locks will still get through, even though you already announced that you need an exclusive lock. – ComicSansMS Feb 14 '14 at 14:22
  • I understand this. I meant I don't see why it could not be implemented in a fair manner. The code that I linked in my previous comment seems more fair to me than the original one, at least =). But maybe it is more expensive because of the extra `lock()`/`unlock()` instructions... – JonasVautherin Feb 14 '14 at 14:38
  • 1
    The Terekhov can be trivially adjusted to work with upgradable mutexes: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2406.html#upgrade_mutex_imp – Howard Hinnant Feb 09 '15 at 00:59