Archive

Posts Tagged ‘C#’

Article Summary: “What Every Dev Must Know About Multithreaded Apps”

March 11th, 2009

There is a great MSDN Magazine article about multithreading applications called “What Every Dev Must Know About Multithreaded Apps“, written by Vance Morrison, an architect on the .NET Runtime Team.

I read the article a long time ago, but I decided to re-read it and to post a short summary here, just to make sure I remember the important points of it. The summary has links to the corresponding sections in Vance’s article. 


Introduction

  • The fundamental requirement for writing correct programs is the same whether the program is sequential or multithreaded: all code in the program must protect any invariants that other parts of the program need, but preserving program invariants is much more difficult in the multithreaded case.

Threads and Memory

  • The tricky part of multithreaded programming is how threads communicate with one another.
  • The most commonly deployed multithreaded communication model is called the shared memory model:
    • In this model all threads have access to the same pool of shared memory.
    • Its advantage and also its biggest problem is that multithreaded programs are programmed in much the same way as sequential programs.
    • The model does not distinguish between memory that is being used strictly for thread local use (like most locally declared variables), and memory that is being used to communicate with other threads (like some global variables and heap memory).

Races

  • There are four conditions needed for a race to be possible:
    • There are memory locations (typically global/static variables or heap memory reachable from global/static variables) that are accessible from more than one thread.
    • There is a property associated with these shared memory locations that is needed for the program to function correctly. Typically, the property needs to hold true before an update occurs for the update to be correct.
    • The property does not hold during some part of the actual update.
    • Another thread accesses the memory when the invariant is broken, thereby causing incorrect behavior.

Locks

  • The most common way of preventing races is to use locks to prevent other threads from accessing memory associated with an invariant while it is broken. This removes the fourth condition required for a race, thus making it impossible to happen.
  • In the Microsoft .NET Framework locks are implemented by the System.Threading.Monitor class.
  • The lock statement in C# is a shortcut for the following:

            System.Threading.Monitor.Enter(someObject);

            try

            {

                // body

            }

            finally

            {

                System.Threading.Monitor.Exit(someObject);

            }

  • Exceptions in a lock block must be properly handled. The lock is there to ensure an invariant, so it’s important to make sure that the invariant wasn’t broken as a result of the exception.
  • A simple lock statement is appropriate if there is no useful cleanup to do or if everything in its body is read-only.

Using locks properly

  • Locks provide mutual exclusion for regions of code, but generally programmers want to protect regions of memory.
  • For a lock to provide mutual exclusion for a region of memory, no writes to that memory can occur without entering the same lock. In a properly designed program, associated with every lock is a region of memory for which it provides mutual exclusion. There is no obvious artifact of the code that makes this association clear, and yet this information is absolutely critical for anyone reasoning about the multithreaded behavior of the program.
  • Every lock should have a specification associated with it that documents the precise region of memory (set of data structures) for which it provides mutual exclusion.
  • While having memory regions protected by different locks that overlap is not strictly incorrect, it should be avoided because it is not useful.

How many locks?

  • The main disadvantage of having more than one lock is the complexity involved. The program has more parts associated with it so there is more opportunity for programmer error.
  • It is best to have few locks that protect large regions of memory and only split them when lock contention is shown to be a bottleneck on performance.

Taking Locks on Reads

  • A lock should always be entered before writing a memory location. When memory is read the case is a little more complicated because it depends on the programmer’s expectations.
  • In general, when code needs a program invariant, all locks associated with any memory involved with the invariant must be taken.
  • For multithreaded applications the programmer’s mindset should change from believing that nothing changes unless it is explicitly changed to believing that everything changes unless locks are used to prevent it.

What Memory Needs Lock Protection?

  • An easy and correct answer would be that all memory needs to be protected by a lock, but this would be overkill for most apps.
  • Memory can be made safe for multithreaded use in one of several ways:
    • Memory that is only accessed by a single thread is safe because other threads are unaffected by it. This includes most local variables and all heap-allocated memory before it is published (made reachable to other threads). Once memory is published, however, it falls out of this category and some other technique must be used.
    • Memory that is read-only after publication does not need a lock because any invariants associated with it must hold for the rest of the program (since the value does not change).
    • Memory that is actively updated from multiple threads generally uses locks to ensure that only one thread has access while a program invariant is broken.
    • In certain specialized cases where the program invariant is relatively weak, it is possible to perform updates that can be done without locks. Typically, specialized compare-and-exchange instructions are used. These techniques are best thought of as special, lightweight implementations of locks. 
  • A general rule should be that all program memory should fall into one of three buckets: thread exclusive, read-only, or lock protected.

Methodical Locking

  • In a well-designed class, clients only access its internal state by calling its instance methods. If a lock is taken on entry to any instance method, and released on exit, there is a systematic way of ensuring that all accesses to internal data (instance fields) only occur when the lock is held. Classes that follow this protocol are called monitors (NOTE: So in essence monitors are classes that thread-safe because they synchronize access to their internal data. See this Wikipedia article about monitors for a better explanation of the concept).
  • The concept of a monitor is one of the simplest and most useful techniques for methodical locking.
  • The name of a lock in the .NET Framework is System.Threading.Monitor, a type specifically tailored to support the monitor concept.
  • .NET locks operate on System.Object to make the creation of monitors easier.
  • Every object has a built-in lock that can be used to protect its instance data. By embedding the body of every instance method in a lock(this) statement, a monitor can be formed (NOTE: Jeffrey Richter, in his “CLR via C#, Second edition“ book, explains why using lock(this) or lock(typeof(ClassName)) isn’t a good idea. See [1] in the footnotes).
  • There is a special attribute, [MethodImpl(MethodImplAttributes.Synchronized)], that can be placed on instance methods to automatically insert the lock(this) statement (NOTE: Since this attribute will surround the method’s code with a lock(this) is it’s an instance methof or a lock(typeof(typename)) if it’s a static method, you should never use this attribute either. Again, see [1] in the footnotes).
  • .NET locks are reentrant, meaning that the thread that has entered the lock can enter the lock again without blocking. This allows methods to call other methods on the same class without causing the deadlock that would normally occur.
  • Indiscriminate use of monitors can result in either too little or too much locking.
  • An important weakness with the monitor concept is that it provides no protection if the class gives out updatable pointers to its data.
  • Monitors don’t address the more complicated situation when multiple locks need to be taken.
  • Generally speaking, most reusable code (like container classes) should not have locks built into it because it can only protect itself, and it is likely that whatever code uses it will need a stronger lock anyway. The exception to this rule is when it is important that the code works even with high-level program errors. The global memory heap and security-sensitive code are examples of exceptional cases.
  • It is less error prone and more efficient to have just a few locks that protect large amounts of memory. A single lock that protects many data structures is a good design if it allows the desired amount of concurrency. If the work each of the threads will do doesn’t require many updates to shared memory, consider taking this principle to the extreme and having one lock that protects all shared memory. It works well for applications whose worker threads don’t interact much.
  • In cases where threads read shared structures frequently, but write to them infrequently, reader-writer locks such as System.Threading.ReaderWriterLock can be used to keep the number of locks in the system low (NOTE: Jeffrey Richter also says in his “CLR via C#, Second edition” book that he doesn’t recommend that anyone ever use this class, see [2] in the footnotes). This type of lock has one method for entering for reading and one for entering for writing. The lock will allow multiple readers to enter concurrently, but writers get exclusive access. Since readers now don’t block one another, the system can be made simpler (containing fewer locks) and still achieve the necessary concurrency.
  • Lock usage can often be at odds with normal object-oriented program abstraction because locking is really another independent dimension of the program that has its own design criteria (other such dimensions include lifecycle management, transactional behavior, real-time constraints, and exception-handling behavior).
  • If some method does not take locks itself, but expects its caller to provide that mutual exclusion, then that requirement is a precondition of calling that method and should be in its interface contract.
  • If a data abstraction might take a lock or call client (virtual) methods while holding a lock, that also needs to be part of the interface contract. 
  • There is little that class library designers can do to make the library friendlier to multithreading, because locking just one data structure is rarely useful. It is only when the threading structure of program is designed that locks can be usefully added.

Deadlock

  • Once a program has more than one lock deadlock becomes a possibility, which is another reason to avoid having many locks in the system.
  • Deadlocks can only occur if there is a circular chain of threads such that each thread in the chain is waiting on a lock already acquired by the next in line. For example, if one thread tries to enter Lock A and then Lock B, while simultaneously another thread tries to enter Lock B and then Lock A, it is possible for them to deadlock if each enters the lock that the other owns before attempting to enter the second lock.
  • Deadlocks are generally prevented in one of two ways:
    • The best way to prevent deadlock is to have few enough locks in the system that it is never necessary to take more than one lock at a time.
    • If the former is impossible, deadlock can also be prevented by having a convention on the order in which locks are taken. Each lock in the system is assigned a “level”, and the program is designed so that threads always take locks only in strictly descending order by level. This protocol makes cycles involving locks, and therefore deadlock, impossible. If this strategy does not work (can’t find a set of levels), it is likely that the lock-taking behavior of the program is so input-dependent that it is impossible to guarantee that deadlock cannot happen in every case. Typically, this type of code falls back on timeouts or some kind of deadlock detection scheme.
  • An analysis must be made to determine why more than one lock has to be taken simultaneously.
  • Taking multiple locks is only necessary when code needs to get exclusive access to memory protected by different locks. This analysis typically either yields a trivial lock ordering that will avoid deadlock or shows that complete deadlock avoidance is impossible.

The Cost of Locks

  • Another reason to avoid having many locks in a system is the cost of entering and leaving a lock.
  • The lightest locks use a special compare/exchange instruction to check whether the lock is taken, and if it isn’t, they enter the lock in a single atomic action. This special instruction is relatively expensive (typically ten to hundreds of times longer than an ordinary instruction).
  • There are two main reasons for this expense, and they both have to do with issues arising on a true multiprocessor system:
    • The compare/exchange instruction must ensure that no other processor is also trying to do the same thing. Fundamentally, this requires one processor to coordinate with all other processors in the system. This is a slow operation and accounts for the lower bound of the cost of a lock (dozens of cycles).
    • The other reason for the expense is the effect inter-process communication has on the memory system. After a lock has been taken, the program is very likely to access memory that may have been recently modified by another thread. If this thread ran on another processor, it is necessary to ensure that all pending writes on all other processors have been flushed so that the current thread sees the updates. The cost of doing this largely depends on how the memory system works and how many writes need to be flushed. This cost can be pretty high in the worst case (possibly hundreds of cycles or more).
  • The cost of a lock is can be significant. If a frequently called method needs to take a lock and only executes a hundred or so instructions, lock overhead is likely to be an issue. The program generally needs to be redesigned so that the lock can be held for a larger unit of work.
  • As the number of processors in the system grows locks become the main impediment in using all the processors efficiently:
    • If there are too few locks in the program, it is impossible to keep all the processors busy since they are waiting on memory that is locked by another processor.
    • If there are many locks in the program, it is easy to have a “hot” lock that is being entered and exited frequently by many processors. This causes the memory-flushing overhead to be very high, and throughput again does not scale linearly with the number of processors. The only design that scales well is one in which worker threads can do significant work without interacting with shared data.

A Quick Word on Synchronization

  • Locks don’t really provide a mechanism for threads to synchronize.
  • The principles for synchronizing threads without introducing races are not much different from the principles for proper locking.
  • In the .NET Framework synchronization functionality is implemented in the ManualResetEvent and AutoResetEvent classes. These classes provide Set, Reset, and WaitOne methods: the WaitOne method causes a thread to block as long as the event is in the reset state. When another thread calls the Set method, AutoResetEvents will allow one thread that called WaitOne to unblock, while ManualResetEvents will unblock all waiting threads.
  • Generally, events are used to signal that a more complicated program property holds.
  • In general, it’s a bad idea to hold locks while waiting on events.

Conclusion

  • The difference between sequential and multithreaded programs is that protecting program invariants is more complicated in the multithreaded case. 
  • It requires a significantly higher degree of discipline to build a correct multithreaded program:
    • Ensuring through tools like monitors that all thread-shared, read-write data is protected by locks.
    • Carefully design which memory is protected by which lock.
    • Controlling the extra complexity that locks inevitably add to the program.
  • Good designs are typically the simplest, and for multithreaded programs this means having the fewest number of locks that achieve the needed concurrency.

 


Footnotes

[1] Simply stated, when you lock on the this pointer or the object’s type, you open the possibility for malicious code to deadlock threads that use that type. For a complete explanation see pages 636-639 of “CLR via C#, Second Edition“.

[2] The ReaderWriterLock class has three flaws: its performance is awful, even when there is not contention on the lock, it has a policy of favoring readers over writers, “writers get starved for time and do not complete their work in a timely fashion”, and finally it supports recursion, meaning that the thread that enters the lock must be the thread that exits it (Richter consider this a bug because it’s becoming commonplace to have a thread enter a lock and start an operation to access some data and have another thread to complete the operation and exit the lock, specially likely in a asynchronous programming model). See pages 642-643 of “CLR via C#, Second Edition“.

So that’s it. If you are new to multithreading programming I strongly suggest you to read the original article. Happy coding!

Julián Hidalgo .NET, C#, Threading , ,

The New Features in C#4

February 9th, 2009

I finally watched the talk about the future of C# that Anders Hejlsberg presented at the last PDC. I had previously read a short paper about the new features in C#4 and a couple of posts by Eric Lippert (look for the five parts series called “The Future of C#”), so I knew about most what he was talking about, but he helped me to understand the whys and to put everything in perspective.

Each C# version’s feature set has been centered on a theme, which helps to prioritize the proposals and to focus the development efforts. So far we’ve had:

  • C# 1.0: Managed code (that is, creating a compiler for managed code)
  • C# 2.0: Generics
  • C# 3.0: LINQ

Of course, in practice there are always features that don’t fit well within the major theme of a version (for example anonymous methods have nothing to do with generics, partial methods had nothing to do with LINQ, and so on). I suggest you to read this post by Eric Lippert to see his slightly different point of view about this topic. For C# 4.0 the theme is dynamic programming (according to Anders, for Lippert it looks more like a “grab-bag”), but what does this mean in terms of features? Here they are:

  • Dynamically typed objects
  • Optional and named parameters
  • Improved COM interoperability
  • Co-variance and contra-variance

According to Lippert, this may seem like a small set of features, and I agree, but he says it was deliberate:

Some feedback that we received loud and clear through the C# 3.0 ship cycle was “this is awesome, we need these language features immediately!” and, somewhat contradictorily, “please stop fundamentally changing the way I think about programming every couple years!” Rather than trying to find some way to yet again radically increase the expressiveness and power of the language, we decided to spend a cycle on making what we already have work better with the other stuff in our programming platform infrastructure.

Let me review each feature in more detail.

Dynamically typed objects

C# 4.0 will allow you “to write method, operator and indexer calls, property and field accesses, and even object invocations which bypass the C# static type checking and instead gets resolved at runtime”. This was implemented by introducing a new type called “dynamic“, which under the hoods is just an object type marked with the new Dynamic attribute, so basically we have objects that are statically typed to be dynamic (!). In my opinion this is a clever idea because it flows nicely through the type system, and works well with things like refactoring.

In practice, this means that code that currently looks like this in C# 3.0 (assume the GetCalculator method returns an object whose type is not known at compile time):

 

Could look like this in C# 4.0:

Here the variable calc is statically typed to be dynamic, the invocation of the Add method is dynamic and there’s also a dynamic conversion of the result to an integer. This is more or less what you can do in Visual Basic when you turn off the strict option, the key difference being the new dynamic type. When the operands are dynamic:

  • Member selection is deferred to run-time
  • At run-time the actual type(s) is(are) substituted for dynamic
  • The static result type of an operation is dynamic

I bet this is going to be a controversial feature for many people because after all C# is supposed to be a strongly typed language. Anders himself acknowledged this after presenting the feature: “So now you may go, well, gosh Anders have you gone start driving mad? Haven’t you told us for ten years that static typing is the right and only way, and now you are being heretical?”. I admit I didn’t like it at all at first, but after thinking about it I decided I prefer to maintain 10 lines of dynamic code than 100 lines of reflection based code. If it’s not type-safe then at least I want it to be readable.

If you want to know all the details about this feature I strongly recommend you to read these excellent (and long) series of posts:

Optional and named parameters

A parameter is declared optional by providing a default value for it:

public void MyMethod(int x, int y = 5, int z = 7);

In C# 4.0 you can pass any of those parameters by name, and you can also omit y and z:

MyMethod(1, 2); // omitting z – equivalent to MyMethod(1, 2, 7)
MyMethod(1); // omitting both y and z – equivalent to MyMethod(1, 5, 7)
MyMethod(1, z: 3); // passing z by name
MyMethod(x: 1, z: 3); // passing both x and z by name

I see two big benefits derived from these features (beside the COM thing I mention later):

  • How many times have you seen a method with a boolean parameter like MyMethod(bool closeTheThing)? I don’t know about you, but I always fear to pass the wrong value. If you really care about it (and you own the code) you can always create an enumeration, but it’s quite tiresome. Passing those values by name can really improve the readability of your code with almost no effort (MyMethod(closeTheThing:true)).
  • No more overloads just to make default parameters possible!

Check out this nice post by Sam NG for more details about this feature.

Improved COM interoperability

I don’t care about this too much since I’ve never had to interop with COM that much. The improvements are the following:

  • The optional and named parameters help a lot to improve the COM interop experience. Check out this post by Scott Hanselman to see how a piece of 53 lines of C# 3.0 code that uses the Office Automation libraries is reduced to only 13 lines in VB.NET. The code in C# 4.0 will look just as succinct now.
  • COM’s variant types can now be imported as dynamic.
  • “ref” parameters are now optional.
  • No PIAs: “the C# compiler will bake the small part of the PIA that a program actually uses directly into its assembly. At runtime the PIA does not have to be loaded”.

As you can see, the most important improvements are due to the other new features in the language.

Co-variance and contra-variance

Finally we’ll have some variance support in .NET! I’ve wanted this for a long time so I was quite glad when I heard it would be implemented, but there are a few limitations though. Here are some things to keep in mind:

  • It’s only supported for interface and delegate types (which is disappointing), due to a limitation in the CLR.
  • Technically speaking (that is, from a computer science perspective) they are implementing “statically checked definition-site variance”.
  • Value types are always invariant, so for example IEnumerable<int> is not IEnumerable<object>. This is similar to existing rules for arrays.
  • ref and out parameters need an invariant type.

So how does it work?

  • A co-variant type is signaled with the “out” keyword. It can appear in output positions only, and can be treated as less derived. Example: IEnumerable<out T>.
  • A contra-variant type is signaled with the “in” keyword. It can appear in input positions only, and can be treated as more derived safely. Example: IComparer<in T>.

(Does the “statically checked definition-site variance” thing make more sense now?)

I think the value of this feature can be captured in a phrase that Anders said during the talk: “You’ll be able to do things that you were surprised you couldn’t do”.

C# and VB

Another important announcement made in the talk was that C# and VB will co-evolve from now on, meaning that the same features will be introduced to both of them at the same time (when it makes sense of course). “Co-evolution is the right way to evolve these languages” said Anders, and I think this is totally true. Well, I like the idea of having the VB team copying the features that the C# team introduces, but I’m not so sure if I like it the other way around :)

Highlights of the presentation

Here are a few interesting things that Anders mentioned:

  • There are 3 trends going on in programming: declarative, dynamic, and concurrent.
  • The new paradigm is being multi-paradigm. According to Hejlsberg, C# 3 is already a functional programming language, since it has all the basic features that you need to write functional code (look at Eric Lippert’s definition of a functional programming language: “When I say “functional language”, I mean a language in which it is possible without undue difficulty to program in a functional style”. Not all people would agree with him of course.)
  • There’s a shift from imperative to declarative programming, and lots of talk about DSLs and functional programming.
  • On the dynamic vs. static languages debate, people really want to have the good features from both sides.
  • Concurrency is the elephant in the room. There is no single silver bullet that’s going to fix it and make everything concurrent.
  • The usual problem about concurrency was to make many logical tasks work on fewer CPUs. The new one is making a single logical task run on multiple CPUs.
  • The Parallel Extensions for .NET make great use of all the new functional features in C# 3, allowing them to try out new things without actually commit to a syntax until it has proved to be the right model (I assume this means that at some point in the future the language will be expanded with special constructs for concurrency).
  • Compiler as a service. This is basically about exposing the functionality of the compiler to the programmer, something that’s been tried already in languages like Boo for example. I’m sure it will be a really interesting feature, but first of all they need to write their compiler in managed code (right now it’s coded in C++), which I bet is not a short task. In the talk Anders showed a nice demo, a little interpreter (coded in a couple of lines) that’s able to execute lines of C# code as they are entered, just like the Ruby or Python interpreters we’ve all seen.

OK, that was a long post (I hope it wasn’t too boring). I really suggest you to go watch the presentation and get the CTP. See you next time!

Julián Hidalgo .NET, C# ,