Don’t Call A Delegate From Within A Critical Section

Before talking about value and reference types and delegates/closures, let me point out that Monitor-based locking has a fundamental flaw when working with delegates (the same flaw that it has with virtual method calls on objects): you can never safely call a delegate inside a lock-block that is holding a lock on a resource that is conceivably reachable by the delegate (hint of a return to the issue of “closing over” local variables). This is because it’s possible that the delegate will start a thread that attempts to lock the same resource that you’ve locked, an attempt which will result in deadlock.

 In the following program, the Library is running in its own thread, spinning on the lines 34-47, which call back to myDelegate() on line 42. This callback is in the middle of a critical section, lines 38-44, which have locked this.

Now consider the function LockAndTalk(), lines 79-97. It, too, has a critical section, beginning at line 86. It attempts to lock a resource, in this case, the Library which it is using. If it succeeds, we consider the callback to be a success. And, if the Library‘s delegate callback is set to Client‘s FineCall(), everything works fine, because the Line 86 lock of the Library and the line 38 lock of the same Library occur within the same thread.

However, consider what happens when the Library’s delegate callback is set to BadCall() (lines 58-69), which looks a lot like FineCall(), but happens to call the function LockAndTalk() in the context of a separate thread. Now, the locks at line 86 and 38 are called within separate threads and deadlock.

As soon as you enclose a callback (virtual method or delegate) within the language-promoted Monitor-based strategies of C# ( lock ) or Java ( synchronized ), you’ve shot yourself in the foot.

I’m late for my Frisbee game, so I guess I’ll have to leave an example that produces a deadlock via a captured outer variable for another day…

 

    1 //Never call a delegate inside a lock

    2 using System;

    3 using System.Threading;

    4 using System.Collections;

    5 

    6 delegate void VoidDelegate();

    7 

    8 class Library

    9 {

   10     VoidDelegate myDelegate;

   11     public VoidDelegate MyDelegate

   12     {

   13         set { myDelegate = value; }

   14     }

   15 

   16     Thread t;

   17 

   18     public void Run()

   19     {

   20         ThreadStart ts = new ThreadStart(ThreadCaller);

   21         t = new Thread(ts);

   22         t.Name = “Library thread”;

   23         t.Start();

   24     }

   25 

   26     public void Stop()

   27     {

   28         t.Abort();

   29         t.Join();

   30     }

   31 

   32     void ThreadCaller()

   33     {

   34         while (true)

   35         {

   36             Console.WriteLine(Thread.CurrentThread.Name +

   37               ” asking for lock on “ + this.GetHashCode());

   38             lock (this)

   39             {

   40                 Console.WriteLine(Thread.CurrentThread.Name +

   41                   ” acquired lock”);

   42                 myDelegate();

   43                 Thread.Sleep(1000);

   44             }

   45             Console.WriteLine(Thread.CurrentThread.Name +

   46               ” released lock”);

   47         }

   48     }

   49 }

   50 

   51 class Client

   52 {

   53     internal void FineCall()

   54     {

   55         LockAndTalk();

   56     }

   57 

   58     internal void BadCall()

   59     {

   60         ThreadStart ts = new ThreadStart(LockAndTalk);

   61         Thread t = new Thread(ts);

   62         t.Name = “BadClient”;

   63         t.IsBackground = true;

   64         t.Start();

   65         while (callDone == false)

   66         {

   67             Thread.Sleep(1000);

   68         }

   69     }

   70 

   71     Library l;

   72     public Library Library

   73     {

   74         set { l = value; }

   75     }

   76 

   77     protected bool callDone = false;

   78 

   79     public void LockAndTalk()

   80     {

   81         callDone = false;

   82         while (callDone == false)

   83         {

   84             Console.WriteLine(this.GetType() +

   85               ” asking for lock on “ + l.GetHashCode());

   86             lock (l)

   87             {

   88                 Console.WriteLine(Thread.CurrentThread.Name +

   89                   ” acquired lock”);

   90                 Console.WriteLine(“Delegate executed”);

   91                 Thread.Sleep(1000);

   92                 callDone = true;

   93             }

   94         }

   95         Console.WriteLine(Thread.CurrentThread.Name +

   96           ” released lock”);

   97     }

   98 }

   99 

  100 

  101 class TestingClass

  102 {

  103     static Library l;

  104     TestingClass(Client c, VoidDelegate myDelegate)

  105     {

  106         l = new Library();

  107         c.Library = l;

  108         l.MyDelegate = myDelegate;

  109         l.Run();

  110 

  111         Thread.Sleep(10000);

  112         Console.WriteLine(“Ending test now…”);

  113         l.Stop();

  114     }

  115 

  116     public static void Main()

  117     {

  118         Client c = new Client();

  119         new TestingClass(c, c.FineCall);

  120         Console.WriteLine(“Okay, that went fine.”);

  121 

  122         Client c2 = new Client();

  123         new TestingClass(c2, c2.BadCall);

  124 

  125     }

  126 }

Example of Surprising Closure Behavior

What do you expect to be outputted from this program (note that line 19 captures the outer variable “i”)?

 

    1 using System;

    2 using System.Collections.Generic;

    3 using System.Text;

    4 using System.Threading;

    5 

    6 delegate void VoidDelegate();

    7 

    8 class Program

    9 {

   10     public static void Main(string[] args)

   11     {

   12         List<VoidDelegate> closures = new List<VoidDelegate>();

   13         //Create a bunch of closures

   14         for (int i = 0; i < 10; i++)

   15         {

   16             VoidDelegate myClosure = delegate

   17             {

   18                 //Capture outer variable

   19                 Console.WriteLine(i);

   20             };

   21             closures.Add(myClosure);

   22         }

   23 

   24         foreach (VoidDelegate closure in closures)

   25         {

   26             closure();

   27         }

   28         Console.ReadKey();

   29     }

   30 }

 

Contrast with the output of this Ruby program:

 

closures = Array.new()

#Create a bunch of closures
10.times { | i |
  myClosure = lambda {

    #Capture outer variable
    puts(i)
  }
  closures.push(myClosure)
}

closures.each { | myClosure |
  myClosure.call()
}

The Myth of Elite Programmer Employment

James Robertson, advocating that people give 1-3 elite Smalltalkers a chance to take on a project that would take “commodity” programmers 6 months, says “Which will cost you more: Those two “cowboys”, or the 10 “commodity” developers? Heck, let’s say you find yourself 2 really good people, and pay them each $175k per year, as opposed to paying each of the 10 commodity guys $80k?”

Let me tell you a story: there’s this programmer — let’s call him Gary — who architected a system for a startup company and wrote some of the foundational code. Six years later, the company calls up Gary and says “We’re doing $100M a year in transactions on the system and, without significant alteration of your initial architecture, can handle somewhere in excess of 10,000 simultaneous users. We’re interested in ‘taking things to the next level’ and are looking for someone to help us architect it and write some of the foundational code.”

So Gary, who is generally thankful that he can get by making a modest living as an independent contractor, thinks “gee, here’s a situation where I am justified in charging an ‘elite’ consulting rate. Whatever I charge these guys, they will have every reason in the world to pay it.” So let’s say that X equals the rate that Gary charged these guys six years ago. What’s your guess as to the rate at which the company walked away from negotiating a 5-month contact with Gary?

$170M FBI Software Failure: 730KLoc * $232.88 / line

$170,000,000 / 730,000 = $232.88.

Choice “incompetent software project management” quotes:

“[T]he FBI made a fateful choice: It wanted SAIC to build the new software system from scratch rather than modifying commercially available, off-the-shelf software. Later, the company would say the FBI made that decision independently; FBI officials countered that SAIC pushed them into it….”

“Most important, the FBI planned to launch the new software all at once, with minimal testing beforehand….”

“[T]he FBI had few people in house with the expertise to develop the kind of sophisticated information technology systems that it would need. As a result, the agency had been turning increasingly to private contractors for help….In essence, the FBI has left the task of defining and identifying its essential operational processes and its IT concept of operations to outsiders.”

“[T]he SAIC software was incomplete, inadequate and so poorly designed that it would be essentially unusable under real-world conditions. Even in rudimentary tests, the system did not comply with basic requirements.”

“[SAIC] kept 200 programmers on staff doing “make work,” he said, when a couple of dozen would have been enough. The company’s attitude was that “it’s other people’s money, so they’ll burn it every which way they want to,” he said.”

“[SAIC] Executive Vice President Arnold Punaro submitted testimony to Congress …. FBI officials, he said, took a “trial and error, ‘we will know it when we see it’ approach to development.” ” [Changing user requirements on a $170M project? Heaven forfend! — Larry]


Daniel Guttman captures the problem: “[T]he legal fiction is that the government knows what it’s doing and is capable of taking charge. The contractors are taking advantage of that legal fiction.” But thank God that’s over: “Azmi and other FBI officials say Sentinel is designed to be everything VCF was not, with specific requirements, regular milestones and aggressive oversight.”

I feel so much better now.

Java May Get Closures: Functional Programming on the March!

Gilad Bracha has a substantive proposal to add closures to Java (for those familiar with .NET but not Java, this is generally equivalent to adding delegates and C# 2.0’s anonymous delegates). The proposal has slightly cleaner syntax than what is in C# but I believe would reprise an issue that C# has, in that “captured outer variables” are shallow copies. This means that when an outer object with reference semantics is closed over, you can end up creating a very thread-hostile functional data structure. Monitor-based thread safety, already a very weak model, is weakened further by the proliferation of implicit objects (i.e., closures that use reference semantics on closed-over outer variables).

Not that any design decision that creates implicit deep copies would be without its issues! Adding closures to the JVM/CLR object model is, like generics, a tough nut to crack. One of the problems I had with the addition of generics to the CLR is that they were absorbed into the standard Common Type System before they had a chance to play out in the real world. One of the great advantages that the JVM and CLR had in their early days was that they very pragmatically reflected lessons learned from real-world uses of languages like C++ (e.g., string representation issues), Delphi (e.g., component models), and Smalltalk (e.g., ‘everything is an object’). Necessarily, today’s VM advances are less road-driven. While there’s nothing wrong with that, I think that standardization of such advances and their implementations should be more cautious.

Update: See my post for an example of the surprising behavior resulting from C#’s design.