4 ms·
The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when
by imtringued 1y ago
The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when the vast majority of real life queues have no such constraint whatsoever.
If you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will be the first to be assigned to a counter. If there is one counter, the second person has to wait for the first person. If there are two counters, then the second person can go to the second counter. If the second counter works faster than the first counter, then the third person will go to the second counter.
According to the blog post this violates a global processing order constraint (created by who?). The people at the second counter appear to be coming from the future from the perspective of a global processing order constraint.
This is a very strange way to look at queues, because the primary purpose of a queue is to temporarily buffer data when there is insufficient capacity to process incoming requests. Calling something broken because it fulfills its purpose is a very negative way to approach life.
- epgui 1y ago> the primary purpose of a queue is to temporarily buffer data I think if that’s all you care about you’re in the clear. The article is useful in that it considers a more general set of use cases (people do all kinds of weird things) and highlights that a somewhat intuitive assumption one might have may not hold.
- BlackFly 1y agoYes, the author hasn't heard the term "service discipline" before. Sure, queuing theory is easier if you don't consider all the various service disciplines that real life queues use in practice (both physical queues and digital queues).
- SUPERCILEX 1y agoThanks for sharing, I had not! It sounds like "processor sharing" would be the expected mode of operation for lockless queues. But see my comment to the parent, this is not how they work.
- BlackFly 1y agoIn principle there is an infinite number of possibilities for service disciplines, since it is an arbitrary function to select an element from sets. Service disciplines can also include randomness. I only know the basics of the mathematics of queue theory, but my introduction to it gave me the impression that almost anything but the most basic of disciplines didn't have closed form solutions to most questions. Like many models, you can introduce some things as approximations to get close enough answers. I personally prefer simulation, but that has its own problems.
- SUPERCILEX 1y agoThis is actually a great analogy because it exemplifies the misconceptions people have about lockless queues. In the example with multiple counters, in real life each counter could shout out a number and have people approach their respective counters in parallel. But this is not how lockless queues work. Instead, the person at the head of the queue holds a baton and when multiple numbers are called, everybody waiting in the queue goes up to the counter of the person holding the baton. Once that head-of-the-queue has made it to the counter, they give the baton to the person behind them who then drags everybody along to their counter. And so on. The article was arguing for a lockless channel implementation akin to your interpretation of a queue with parallel access to the counters.