3 ms·
Not sure if I'm following. In many (most?) multiple-producer/multiple-consumer cases it is completely irrelevant if the work-queue guarantees a strict insertion
by w0utert 7y ago
Not sure if I'm following. In many (most?) multiple-producer/multiple-consumer cases it is completely irrelevant if the work-queue guarantees a strict insertion/removal order, as long as the queue is 'fair' (time in queue is distributed evenly over all work items). If that's all you need, a lock-free implementation using atomic operations does not have to be complicated, or what am I missing here?
- dragontamer 7y agoA "work-queue" doesn't have strict ordering in many multithreaded programs. But a "queue" or "fifo" is expected to have a strict ordering. The confusion comes in because many programmers expect a strict-ordering on "work-queues", especially because many work-queues are made out of simple queues or fifos. The big decision point for many is finally deciding, and/or realizing, that strict-ordering is not necessary in many pragmatic use cases. But this also comes with a double-edge sword: many algorithms require strict-ordering of tasks. --------- Take a Breadth First Search, as an example. One core assumption of BFS is that the first solution you come across will be the solution closest to the root. Ex: If searching for "Checkmate" in a chess puzzle, the BFS implementation will ALWAYS find the shortest checkmate. Lets say you're in a situation with "many checkmates", checkmate in 5-moves, checkmate in 7-moves... etc. etc. But you want to absolutely find the shortest one. BFS is clearly the answer. But ONLY if your queue is strictly FIFO. Now if you parallelize the BFS search by replacing the true FIFO queue with a pseudo-FIFO parallel queue, its no longer guaranteed to find the shortest checkmate.