October 2005

published: Mon, 24-Oct-2005   |   updated: Fri, 5-Aug-2016
Turnstone's open space

Here are the articles that were published in October 2005.

Lock-free data structures: the queue

Last time we looked at implementing a lock-free stack, a stack that can be used in multithreaded applications but that doesn't need locks (such as mutexes) in order to provide thread-safe operation. This gave us an appreciation for one of the basics of lock-free programming: the Compare-And-Swap (CAS) function. This time we'll look at how to implement a queue, another very basic data structure, but this time things start getting difficult. Read more...

Lock-free data structures: the stack

It's a fact that lock-based concurrency doesn't scale: only one thread at a time can execute the thread-safe code that's being protected by a lock or a mutex. The more threads there are accessing the lock, the more will be just sitting there waiting. Read more...

Priority Queue For Limited Priorities

Recently, my brother-in-law, who programs in VB.NET, needed a priority queue that also had some behaviors of a normal queue: dequeue should remove the highest priority item as usual, but if there were two or more objects with the same priority, they should be removed in arrival order (also known as FIFO or first-in-first-out order). The normal heap implementation of a priority queue could not do that since it takes no account of arrival order; the only ordering is by priority and if there were several items with the same priority, they'd be returned in some non-deterministic order. Read more...

More on TDD depression

Holy cow, I seemed to have struck a nerve with my previous post. Read more...

TDD depression

Over the past year or so, I've become more and more aware that the big companies that provide development tools just don't understand test- driven development (TDD). In fact, I'd go even further, a lot of companies that write software don't seem to get it either. So, I'm depressed. (Updated Tue 18-Oct-2005) Read more..