about the work items - theoretically, they could implement lock-free queues with Interlocked functions
Please note that a lock-free queue implemented with InterlockedCompareExchange() and friends is, in actuality, not necessarily
as “wonderful” solution as it may seem to be at the first glance. For example, consider a busy queue with insertions and removal getting performed by multiple CPUs all the time. By the virtue of bus locking that interlocked functions imply, only one of them may be successful
at any particular moment, right. Therefore, all other contenders will have to repeat their attempts, and do it in a loop until eventually succeeding.
In terms of bus pressure, this is, apparently, much worse than a “classical” test-and-set-based spinlock with its “thundering herd”
scenario, which may occur when a current owner releases a lock. At this point all the contenders break out of their inner loops,
and attempt an interlocked test-and-set all at once, although only one of them may succeed at the time. This is why it is called
a “thundering herd” scenario, which puts an unnecessary pressure on the system bus.
In case of test-and-set-based implementation of a spinlock, the above mentioned “thundering herd” scenario arises only in spikes,
i.e. may occur only when a current owner releases a lock. The system bus may “take a breath and relax” while the spinlock is being held.
However, in case of a lock-free queue there is no chance of a respite for a bus - what you are getting here is a tight polling loop
of interlocked operations, with all the pressure on the system bus that it implies.
In fact, if you look at the whole thing from the system bus’s perspective, what you are going to see in the place of this fancy " lock-free queue" is just the most naive implementation of spinlock acquisition ever known,
[enter ironical mode]
although Mr.Kyler believes this is the only proper spinlock implementation in existence.
https://community.osr.com/discussion/comment/122444#Comment_122444
[begin quote]
Everything on this thread has been worthless. Everyone knows the correct implementation of a spinlock is:
SPIN: BBSSI #0,LOCK,SPIN
- Dan.
[end quote]
[leave ironical mode]
Certainly, I am not saying that a lock-free queue is necessarily worse than a spinlock - surely it has its own advantages.
Unlike a spinlock, it does not have an owner, and, hence, does not need to get released. Therefore, even if you get preempted after a successful operation on a queue you are not going to block anything. Furthermore, once an operation on it is atomic, it has no chance of getting into an inconsistent state due to interrupt or preemption. As a result, there is no need to subject these operations to any IRQL-related constraints.
The only thing that I am saying is that these algorithms should be used judiciously, because they may do more harm than good
under some workloads, at least if implemented naively. Therefore, everything should be judged on case-by-case basis. One has to bear in mind that any particular interlocked operation per se is not THAT expensive., at least as long as it gets performed occasionally. The real overhead comes in only when you start performing them in a loop. Therefore, the main issue here is with a loop. As long as you can find a way to avoid it, everything is going to be just fine. For example, when you are in a position to do something useful in between your attempted interlocked ops, a lock-free queue seems to be, indeed, quite an attractive option
However, taking into consideration the specifics of a workitem queue, I would say that it is, apparently, better off with being protected by a spinlock.
Anton Bassov
