The Old New Thing

Lock-free algorithms: Update if you can I'm feeling down

A customer was looking for advice on this synchronization problem: We have a small amount of data that we need to share among multiple processes. One way to protect the data is to use a spin lock. However, that has potential for deadlock if the process which holds the spinlock doesn't get a chance to release it. For example, it might be ...

Lock-free algorithms: The try/commit/(try again) pattern

The singleton constructor pattern and the example we saw some time ago are really special cases of the more general pattern which I'll call try/commit/(try again). I don't know if this pattern has a real name, but that's what I'm calling it for today. The general form of this pattern goes like this: We calculate the desired new value ...

Lock-free algorithms: The singleton constructor (answer to exercises)

A few days ago, I asked you to make an existing class multithread-safe. The class caches objects called which are indexed by a 32-bit ID. The cache is implemented as an array that dynamically resizes as more items are added to it. A naïve multithreaded version might use a slim reader-writer lock with shared access on reads, exclusive ...

Lock-free algorithms: The one-time initialization

A special case of the singleton constructor is simply lazy-initializing a bunch of variables. In a single-threaded application you can do something like this: This works fine in a single-threaded program, but if the program is multi-threaded, then two threads might end up trying to lazy-initialize the variables, and there are race ...

Lock-free algorithms: Choosing a unique value (solutions)

Last time, I left a warm-up exercise consisting of a code fragment which tries to compute a unique process-wide value. Here it is again: It may be easier to enumerate what the function does right rather than what it does wrong. Um, the words are correctly-spelled. That's about it. Damien was the first to note that the author ...

Lock-free algorithms: The singleton constructor

The first half may be familiar to many (most?) readers, but there's an interesting exercise at the bottom. A very useful pattern for the Interlocked* functions is lock-free lazy initialization via . Yes, that's a really long function name, but it turns out every part of it important. This is a double-check lock, but without the locking. ...

Windows is not a .NET Framework delivery channel either

We learned a while ago that Windows is not an MFC delivery channel. And, since you asked, it's not a .NET Framework delivery channel either. If you're developing a program that uses the .NET Framework, you have to have a backup plan if the version of the .NET Framework you need is not installed on the computer. This might mean including a ...