4

In paper http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2660.htm an algorithm is presented that does not need to hold a lock during the initialization of a local static variable but still causes concurrent flow of control through the variable definition to wait until initialization finished.

The paper says that this has the advantage of avoiding a possible deadlock

The core problem with function-local static-duration object initialization is that the containing function may be invoked concurrently, and thus the definition may execute concurrently. Failing to synchronize may introduce a race condition. The obvious solution is to synchronize. The problem is that such synchronization may introduce deadlock if the synchronization involves holding a lock while the initializer executes.

Can someone please give an example which demonstrates where the deadlock described above occurs?

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212

2 Answers2

4

If you're going to hold a lock during a local static initialization there are two possible designs:

  1. Allocate a mutex per static.
  2. Allocate just one mutex for all statics.

I'm not 100% positive, but I believe the quote to which you refer implicitly assumes design 2. And indeed the algorithm introduced in the paper uses just one mutex for all statics (called mu in the code).

Under design 2, you get deadlock as described by this stack overflow answer. That is, unless you don't actually hold the mutex while doing the initialization. This is accomplished by having a tri-state flag per static that indicates one of: not initialized, being initialized, already initialized. And use the global mutex to set the flag, but unlock it during the initializer.

Community
  • 1
  • 1
Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • ah that makes sense. The paper also says that GCC uses that deadlock-prone algorithm. The linked answer certifies it. thanks. – Johannes Schaub - litb Oct 22 '11 at 18:58
  • This answer has just been down-voted twice. Anyone care to elaborate? Or is it just a random, senseless drive by? I'm into providing accurate information. I believe this answer to be accurate. If an elaboration is needed, just ask. Or at least leave a comment here with a rationale for the down-vote. – Howard Hinnant Oct 26 '11 at 01:28
  • someone had some downvote fun a few hours ago on some of my answers/questions: http://img40.imageshack.us/img40/5457/snapshot96.png . Perhaps it was the same user? If the system thinks it was abusive downvoting it will not count those downvotes though. – Johannes Schaub - litb Oct 26 '11 at 05:28
3

This is a simple extension of the classic deadlock to the case where one of the locks is compiler-provided.

void A2B() { a.Lock(); B(); a.Unlock(); }
void B() { b.Lock(); ...; b.Unlock(); }
void B2A() { b.Lock(); A();  b.Unlock(); }
void A() { a.Lock(); ...; a.Unlock(); }

The classic deadlock occurs if one thread calls A2B() and another thread calls B2A().

In the static initialization lock, the compiler provides the b lock.

int A() { a.Lock(); ...; a.Unlock(); return 0; }
void B2A() { static int v = A(); }
void A2B() { a.Lock(); B2A(); a.Unlock(); }

If you assume a lock around static initialization, then the code is secretly converted to

void B2A() {
    if (!initialized) {
      b.Lock(); // standard double-check-lock
      if (!initialized) v = A();
      initialized=true;
      b.Unlock();
   }
}

One thread calls A2B() and the other calls B2A().

Raymond Chen
  • 44,448
  • 11
  • 96
  • 135
  • This "classic deadlock" is also called lock inversion. – Steve Jessop Oct 22 '11 at 15:00
  • If we don't hold the lock while initializing `v`, will we not have the same deadlock if others need to wait until `v` has been initialized? One thread calls `B2A` and enters the initialization. The other thread calls `A2B` and locks `a` and calls `B2A` and needs to wait until `v`'s initialization is finished. Now the first thread calls `A` and needs to wait until `a` has been unlocked by `A2B`. – Johannes Schaub - litb Oct 22 '11 at 15:00
  • The original C++ standard avoided this problem by saying "If you call B2A twice, and the first call is still busy trying to initialize `v`, then the second call just continues with an uninitialized `v`". – Raymond Chen Oct 22 '11 at 15:30