2

My code has multiple queues. Entries are added to those queues by threads. In a working thread, entries are dequeued and processed.

Since there are multiple queues, I am not sure about the dequeue policy of which queue should be examined first. If there is only one queue that has entries, I can dequeue these entries. But if there are multiple queues with entries, I cannot figure out which one should be processed first. I think the dequeue algorithm should be fair, but I have no idea how to define the fairness and how to take it into consideration.

So my question is: is there any (simple, not hard) well-defined algorithm to dequeue multiple queues? How the fairness is defined then?

guan boshen
  • 724
  • 7
  • 15
  • Any reason to not just circularly check each queue? – Mitch Jun 28 '20 at 01:42
  • @MitchelPaulin Thanks for your comment. Do you mean check the first queue (if there is a entry then dequeue it, if not check the next queue?). Does it have a name? Is it widely used? – guan boshen Jun 28 '20 at 01:47
  • [Round robin is the simplest](https://en.wikipedia.org/wiki/Round-robin_scheduling) – user3386109 Jun 28 '20 at 02:30
  • @user3386109 As far as I can see, Round Robin is a load balance algorithm that fairly assigns working load to several servers. However I don't know how to schedule the dequeue process if some queues are empty and some are not empty. When it comes to a non-empty queue, according to Round Robin, should I skip it to examine next queue? – guan boshen Jun 28 '20 at 03:09
  • Another thing you could do to simplify things is every time something comes on one of your multiple queues, pop it and place it into one queue. Then just have your worker threads all read from that queue. – Mitch Jun 28 '20 at 03:32
  • @guanboshen Yes, when a queue is empty, skip it. Move to the next queue until either a non-empty queue is found, or all the queues have been checked. – user3386109 Jun 28 '20 at 05:46
  • 1
    It sounds like you really want to have one queue. Why must you have many? – Matt Timmermans Jun 28 '20 at 14:18
  • @MattTimmermans Yes, multiple queues are required. For example, for real time data, packet drop is okay but long delay is not acceptable, so we usually need a small queue size for that. However, for control data, dropping data can cause big problems. Increase queue size a little bit to reduce the chance the control data is dropped. – guan boshen Jun 29 '20 at 12:51
  • Something like this, then: https://stackoverflow.com/questions/39914148/what-are-some-queuing-mechanisms-for-implementing-round-robin-queues/40065438#40065438 – Matt Timmermans Jun 29 '20 at 13:00

1 Answers1

0

I finally use WRR (Weighted Round-Robin) scheduler for this task, which takes weight (priority) into consideration for multiple queues.

A more advanced way seems to be WFQ (Weighted Fair Queue). I don't use it because it seems too complex for my task.

guan boshen
  • 724
  • 7
  • 15