Quantum Bit Designs

There are many aspects to multithreaded software design and development that can make it very difficult. I have come across several subtle bugs that can easily bite you if you are not careful. Since many developers may never find a “do not do this” guide that includes these subtleties, I will be explaining them with the hope of helping you improve your multithreading capabilities.

Part 1 is in regards to working with thread-safe collections. There are many ways to make a thread safe collection, such as rolling your own, deriving from a collection and wrapping access to the underlying collection via locks, or using the thread-safe framework collections. We will use the framework’s thread-safe queue in today’s example.

Queue myThreadsafeQueue = Queue.Synchronized(new Queue());

That is how easy it is to make a thread-safe queue. It is just as easy to make a thread-safe list using ArrayList.Synchronized. Sorry, there are no built in thread-safe generic collections (but it is not too difficult to create your own by deriving from a generic collection). So what is a thread-safe collection? It basically means that if you were to execute the following from two different threads, the collection will internally lock on an object and only allow one method to execute at a time:

myThreadsafeQueue.Enqueue(new object());

All method and property calls can therefore be safely called from multiple threads. The real danger that can be difficult to see is when a collection needs to be enumerated. Consider the following way to work on a queue:

while (myThreadsafeQueue.Count > 0)
{
object myObject = myThreadsafeQueue.Dequeue();
//do some work with myObject
}

Do you see the bug? I’m sure the veterans do. The flaw is that between the call to get the Count and the call to Dequeue() an object, another thread could have cleared out the queue. This would mean that when the above code executes, the call to Dequeue() will occur with an empty queue and will thus throw an exception. The solution is to lock on the collection’s SyncRoot object while enumerating:

lock (myThreadsafeQueue.SyncRoot)
{
while (myThreadsafeQueue.Count > 0)
{
object myObject = myThreadsafeQueue.Dequeue();
//do some work with myObject
}
}

Since the SyncRoot object is the object that the collection internally uses to perform synchronization, if the Clear() method is called on the collection from another thread, that thread and method call will block until the Lock(myThreadsafeQueue.SyncRoot) finishes executing. The general rule is as follows:

“Any time a collection is being enumerated, to maintain thread safety, all collection operations should be wrapped in a lock using the SyncRoot object.”

If this rule is not followed, weird exceptions can occur. For example, if you do a ‘foreach’ loop on a thread-safe ArrayList and another thread modifies the collection, you can get the error:

InvalidOperationException: “Collection was modified; enumeration operation may not execute.”

A sample is attached that demonstrates the correct and incorrect way to access a queue safely from multiple threads. Note: If you do decide to derive from a generic collection, it is best to internally lock using the already existing ICollection.SyncRoot object.

Sample: SubtleMultithreadingBugs

The Grand Solution – Thread safe binding to a collection and properties that are modified from any thread.

History
-WPF supports cross thread property change notification.
-WPF does not support cross thread collection change notification.
-Part 1 introduced the ObservableBackgroundList<T> that allows cross thread collection change notification from a single worker thread.
-Part 2 described WPF’s lack of support for cross thread property change notification for items that are in the cross thread collection binding.
-Part 3 introduced a solution that allows cross thread property change notification from any thread for the items in the cross thread collection binding.

We are now ready to make the final leap and introduce a solution that supports binding to a collection that can be modified from any thread (including the UI thread). The class is called ObservableList<T>. Here is how to use it:

1. Pass in the UI’s Dispatcher to the constructor
2. Bind to the ObservableCollection property
3. Use the list from any thread by wrapping all list operations in a using block that utilizes the method AcquireLock.

The ObservableList is made thread-safe by acquiring a lock before accessing the list (including just reads). The AcquireLock method is the way to lock the list and prevent other threads from modifying the list while the list is being accessed by the thread owning the lock. Below is a screenshot of a sample application that demonstrates simulating a server that has many worker threads that update the collection and modify properties.

This is an example of how to wrap all list operations in a using block where _activeTasks is an ObservableList<Task>:

using (TimedLock timedLock = this._activeTasks.AcquireLock())
{
foreach (Task task in this._activeTasks)
{
task.PercentComplete = 100;
}
}

The TimedLock is an IDisposable class that locks on an object passed into its constructor and then unlocks when the TimedLock is disposed. ‘Using’ ensures that no matter what happens inside the using parenthesis, the IDisposable.Dispose() method will be called on the TimedLock, thus releasing the lock. If any single thread has acquired the TimedLock then all other threads will block (provided they follow the same pattern). Even the UI thread must acquire the lock before accessing the ObservableList (but WPF does not need to lock on the ObservableCollection). The TimedLock was taken from IanG’s blog and is nothing more than a lock with a timeout to help debugging scenarios.

Quiz for the experts: In the ObservableList<T> all change requests are always posted to the UI thread via the Dispatcher, even when the UI thread is the thread accessing the list. Why did I design it so the UI thread takes a performance hit and still posts change requests to itself? One might think that when the UI thread is executing, all change requests from other threads are automatically blocked until the UI is done, so it should be safe to update the list directly. This turns out to be false. I myself am not a threading guru, but if anyone gets the right answer you can wear that award

We now have solution with the following features:

Features
-Allows WPF to bind to a collection that is modified from any thread
-Allows WPF to bind to properties of items in the collection that are modified from any thread
-No lock required if used from a single worker thread
-Relatively simple (compared to some other attempts)
-Non-blocking

Downsides
-Requires two lists internally
-The ObservableCollection list should not be modified
-Disposable or DependencyObjects should not be used

Despite these negatives, the community now has a solution to suit developers’ WPF, binding, and multithreading needs.

Disclaimer: Although I spent a considerable amount of time studying and testing the design and concepts described in this series, as well as beating the heck out of the ObservableList<T> with a quad core CPU and 10+ threads each modifying the collection and properties at full speed, I am still human and this is just a blog post. Do your own research and testing, and as always, use at your own risk. I will keep this post updated if there are any issues. I personally believe we can put this topic to rest until WPF adds native support for all of these features.

UPDATE: Microsoft has recognized the property/collection change race condition bug and will fix it in a future version of the framework.

Download the Sample: MultithreadedObservableListSample

Property Change Notification from Worker Threads Solution

Update: The final solution has been posted.

Part 2 described why you should not modify properties of items in a collection that is on a worker thread. The solution is to listen for the events ourselves and then raise the PropertyChanged event from the UI thread. If we can do this, property and collection change events will be raised on the UI thread, WPF will be happy, and everything will work. The first step to catching the property change event is to create a new interface:

public interface ICollectionItemNotifyPropertyChanged : INotifyPropertyChanged
{
event PropertyChangedEventHandler CollectionItemPropertyChanged;
void NotifyPropertyChanged(PropertyChangedEventArgs e);
}

Items in our collection now must implement ICollectionItemNotifyPropertyChanged such as:

public class Task : ICollectionItemNotifyPropertyChanged
{
public event PropertyChangedEventHandler PropertyChanged;
public event PropertyChangedEventHandler CollectionItemPropertyChanged;
public int PercentComplete
{
get { return _percentComplete; }
set
{
_percentComplete = value;
OnCollectionItemPropertyChanged(”PercentComplete”);
}
}
public void NotifyPropertyChanged(PropertyChangedEventArgs e)
{
OnPropertyChanged(e);
}
protected void OnPropertyChanged(PropertyChangedEventArgs e)
{
PropertyChangedEventHandler handler = this.PropertyChanged;
if (handler != null)
{
handler(this, e);
}
}
protected void OnCollectionItemPropertyChanged(string propertyName)
{
PropertyChangedEventHandler handler = this.CollectionItemPropertyChanged;
if (handler != null)
{
handler(this, new PropertyChangedEventArgs(propertyName));
}
}
}

Now when the ObservableBackgroundList gets a request to add or remove an item from its ObservableCollection, it can attach to the CollectionItemPropertyChanged event. When that event is raised (from any thread) the handler will always post to the UI thread a method that will raise the PropertyChanged event.

private void StartListening(T source)
{
ICollectionItemNotifyPropertyChanged item = source as ICollectionItemNotifyPropertyChanged;
if (item != null)
{
item.CollectionItemPropertyChanged += new PropertyChangedEventHandler(item_CollectionItemPropertyChanged);
}
}
private void StopListening(T source)
{
ICollectionItemNotifyPropertyChanged item = source as ICollectionItemNotifyPropertyChanged;
if (item != null)
{
item.CollectionItemPropertyChanged -= new PropertyChangedEventHandler(item_CollectionItemPropertyChanged);
}
}
void item_CollectionItemPropertyChanged(object sender, PropertyChangedEventArgs e)
{
this._dispatcher.BeginInvoke(DispatcherPriority.Send,
new PropertyChangedCallback(PropertyChangedFromDispatcherThread),
sender,
new object[] { e }
);
}
private void PropertyChangedFromDispatcherThread(T source, PropertyChangedEventArgs e)
{
ICollectionItemNotifyPropertyChanged item = source as ICollectionItemNotifyPropertyChanged;
item.NotifyPropertyChanged(e);
}

Here is a diagram that shows how CollectionItemPropertyChanged events are caught and used to raise PropertyChanged events from the UI thread:

Now all PropertyChanged events are raised from the UI thread and there are no threading issues to worry about. We can even raise the CollectionItemPropertyChanged events from any number of workers, but the collection can still only be modified from one worker. The following sample demonstrates these concepts in action.

ObservableListSample1

Update: The final solution has been posted.

Update: The final solution has been posted.

As it turns out, I was not the first to design a simple, lock-free, cross-thread collection binding solution. Beatriz Costa’s InvokeOC<T> class works too, and she did it in 2006. Her article can be found here. In her sample she uses locks to simulate using it from multiple threads, but what I did not realize during my research is that it will work perfectly without locks from a single worker thread (provided the UI thread does not modify the collection). Thanks Josh Smith for making me revisit her sample. Her design consists of a single collection deriving from ObservableCollection, overriding the collection change methods, and enforcing that the collection is synchronously updated on the UI thread. Here is example code that shows an overridden method:

protected override void InsertItem(int index, T item)
{
if (dispatcherUIThread.CheckAccess())
{
base.InsertItem(index, item);
}
else
{
dispatcherUIThread.Invoke(DispatcherPriority.Send,
new InsertItemCallback(InsertItem), index, new object[] { item });
}
}

By using ‘Invoke’ the worker thread will block until the UI updates the collection. This blocking ensures that both the worker and UI thread will be reading the most up to date copy at the same time, therefore both threads can read the collection at the same time. However, without locks it is not thread-safe, so you can only modify the collection from one worker thread. She also includes another class called BeginInvokeOC<T>, but it is not reliable so do not use it under any circumstance.

At this point there are two solutions for cross thread collection binding to a collection on a single worker thread:
-InvokeOC<T>: A blocking single collection
-ObservableBackgroundList<T>: A non-blocking double collection

Property Change Notification from Worker Threads

I mentioned in the previous article that I was going to address the issue of potentially flooding the UI thread with notifications. After some research into the solution I decided that the added complexity was not worth the gain and I may revisit the scenario another time. Instead, I want to move on to the guts of the issues at hand for cross thread collection binding.

Developers that bind to a collection from a separate thread will almost certainly bind to properties on the objects in the collection. A percentage of these developers will then want to change some of these properties from the worker thread. Unfortunately, this is not supported out of the box in .NET 3.5 and 3.0 SP1 (I am not sure about .NET 3.0). The reason has to do with the way WPF listens for property and collection change events. In short it is believed that the lack of support is because the static event manager that is handling the change events is not properly synchronized when property changes come from a worker thread. Here is another diagram to illustrate what happens when collection and property change events are raised:

Since the ‘Event Manager’ is static, it is inherently shared between any thread that accesses it. And since collection change events are required to come from the UI thread but property change events are not, the two events can conflict with each other when a property change occurs from a worker thread. An exception that can result from this conflict is:

“Unable to cast object of type ‘System.Collections.Specialized.HybridDictionary’ to type ‘ListenerList’.”

All hope is not lost, since Part 3 will include a solution to get around this problem.