The Old New Thing
Practical development throughout the evolution of Windows.
Latest posts
Lock-free algorithms: The try/commit/(hand off) model
The last lock-free pattern for this week isn't actually lock-free, but it does run without blocking. The pattern for what I'll call try/commit/(hand off) is more complicated than the other patterns, so I'll start off by describing it in words rather than in code, because the code tends to make things more complicated. First, you take the state variable and chop it up into pieces. You need some bits to be used as a lock and as a work has been handed off flag. And if the work that has been handed off is complicated, you may need some more bits to remember the details of the handoff. A common way of doing this ...
Lock-free algorithms: The opportunistic cache
Suppose profiling reveals that a specific calculation is responsible for a significant portion of your CPU time, and instrumentation says that most of the time, it's just being asked to calculate the same thing over and over. A simple one-level cache would do the trick here. Of course, this isn't thread-safe, because if one thread is pre-empted inside the call to , then another thread will see values for and that do not correspond to each other. One solution would be to put a critical section around this code, but this introduces an artificial bottleneck: If the most recent cached result is , , and if two...
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 suspended in the debugger, or somebody might decide to use to nuke it. Any suggestions on how we can share this data without exposure to these types of horrible failure modes? I'm thinking of something like a reader takes the lock, fetches the values, and then checks at sta...
Overheard conversation fragment: I'm over here by the slot machines
While on a trip to Las Vegas, I happened to overhear a woman talking on her mobile phone who, from her body language, was clearly trying to meet up with a friend. We were in the casino of one of the major hotels. She said, "I'm over here by the slot machines." Yeah, that narrows it down. I'll be heading to Vegas for the Niney Awards. If I don't see you at the ceremony, I'll meet you by the slot machines.
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 based on the initial value, combining it with other values that vary depending on the operation you want to perform, and then use an to update the shared value, provided the variable hasn't changed from its initial value. If the value did change, then that means another thre...
Holding down the shift key when right-clicking lets you pin things to the Start menu even when you might have been better off not doing so
Holding the shift key when calling up a context menu is a convention for indicating that you want to see additional advanced options which are normally hidden. One of those options is Pin to Start menu. What is this doing as an extended command? The Pin to Start menu command normally appears on the context menu of a program or a shortcut to a program. The Start menu pin list was intended to be a launch point for programs, so if the item you pick isn't actually a program, the Pin to Start menu item will be hidden. Furthermore, only items on the local hard drive will show Pin to Start menu. This avoids ugliness ...
Patterns for using the InitOnce functions
Letting the smart people do the work for you.
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 access on writes, and mixed access on the treacherous "create if it doesn't already exist" path. Let's see. First of all, the function doesn't allocate the memory for the cache until somebody actually tries to look something up. But duh, that's the whole point of the class:...
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 conditions which can result in one thread using values before they have been initialized: Observe that if the first thread is pre-empted after the value for is initially set, the second thread will think that everything is initialized and may end up using an uninitialized ...