Effective Concurrency: Associate Mutexes with Data to Prevent Races

10 thoughts on “Effective Concurrency: Associate Mutexes with Data to Prevent Races”

1. Pingback: Todd Seiler » Concurrency & Parallelism
2. Yes, that’s a useful technique too. The tradeoff is that you then need a special lock type; in this design I decided to illustrate the technique in a way that hooks into the C++0x standard locks so that you can write things like lock_guard<Group1>; (see my reply to a later comment asking about this).

3. David is spot-on that you want mutexes to cover invariants, not just individual pieces of data. How to design the groups of data that should be covered by the same mutex (or, which mutexes protect which data) is the subject of another article. This article focuses only on the question of how to ensure that you then used the mutexes correctly.

4. Re map: Yes, thank the Lords of Templates. For types like that, you write a typedef to get rid of the comma. Fun stuff.

   Re lock_guard: Actually that is correct and slickly intended. The reason I wrote the group to provide lock/try_lock/unlock was specifically to make it satisfy the C++0x mutex concept, so that you can use the group itself with all the C++0x locking machinery including lock_guard<Group1>. Pretty snazzy, huh?

5. Right, that is the other (orthogonal) issue. As mentioned in the intro, this article focuses on eliminating races by associating data with locks; the earlier article focuses on exactly the issue eliminating deadlocks by using lock ordering to ensure locks are taken in a consistent order (typically, but not only, by using lock hierarchies).

   Both parts are necessary, and the techniques compose well.

   In addition to races and deadlocks, there’s actually a third issue: Composability. I intend to cover that one in a future article, possibly next month’s.

6. The PROTECTED_MEMBER macro won’t work for types like map < int,int > due to the comma. I see that you have put parenthesis around it but (map < int,int > ) isn’t a type, is it?

   Also, lock_guard < Group1 > doesn’t seem correct. Group1 is not a mutex.

7. One very important topic (from the “Use Lock Hierarchies” article) that this doesn’t cover is lock ordering — if one thread calls:

   lock_guard hold(data1);
   lock_guard hold(data2);

   and another thread calls:

   lock_guard hold(data2);
   lock_guard hold(data1);

   These will be “correct” in that the testcase won’t complain, but the two threads will deadlock. Sometimes.

8. The previous comment is spot-on. Using mutexes to protect data is a good start, but it doesn’t solve all problems. For instance, to use your ‘transfer-element-between-tables’ example, this code:

   // lock mutTable1
   table1.erase( x );
   // unlock mutTable1
   // lock mutTable2
   table2.insert( x );
   // unlock mutTable2

   would pass your ‘protect-the-data’ test. It however fails the invariant that x is in either table1 or table2. For the purposes of your program, this may not be a problem. But it may be, in which case you need some lock that protects *both* table1 and table2. But a better way to think about it is that your mutex would guarantee that any transfer between table1 and table2 was atomic…no observer could ever see that x was neither in table1 nor table2.

   There is a lot of research in Java about making more general locks…for instance, the @GuardedBy annotation associates locks with data (essentially your approach). See this CERT secure coding rule in Java for more information about using annotations (along with analysis tools) to eliminate race conditions:

   https://www.securecoding.cert.org/confluence/x/cwCMAg

9. Rather than thinking of a mutex as protecting data, I prefer to think of them as protectors of invariants. Lock hierarchies then fall out naturally for invariants involving other invariants naturally. I suspect this distinction would also help in deciding which objects should go in to which ‘MyData’ class.

   I saw something similar on codeproject once, actually (can’t find the link now). The approach taken then was to have something like a ‘guardian’ class that holds a private MyData object and a mutex. To access the MyData object inside, you had to create a special kind of lock whose constructor took a reference to the guardian object. While the lock exists, the guardian’s mutex would acquired as usual but the lock provided a get() method and overloaded the ‘arrow operator’ to return a pointer to the MyData inside the guardian. In this way, you fundamentally could not get to the MyData object without holding the lock. This approach is even more race-free-by-construction as even the asserts aren’t needed!

   I could sketch this out in code, by I fear the commenting system will eat my C++ templates :)

10. “// use table1 and table2 (both are shared)
    table1.erase( x );
    table2.insert( x );

    Quick: What locks should you take to make this code correct?”

    I know that the examples given in the EC series should be seen as illustrative and I don’t want to detract from what the article is trying to teach, but I’d just like to give one answer that I think is relevant for a completely different strategy: Lock x.

    One way of getting concurrency in this case is to have a function

    int lock_number(x)

    that maps keys to any number of locks, and then lock mutex[lock_number(x)].

    Then we know that relevant parts of both table1 and table2 are locked for the duration of the transaction. This assumes that the internals of table1 and table2 are written in such ways that they, too, are split according to the lock_number function.

Comments are closed.