Search code examples
algorithmsortingtime-complexityscheduling

Prioritizing different types of messages

I have t different message types, that can arrive to queue q at a different time. Number of messages that arrive at a particular time can vary. Every type has some priority.

I need to write an algorithm that will order this messages in priority queue with following rules:

  • organize messages so higher priority of t is first message in queue.
  • beside priority, we need also to take into consideration that messages of lower priority still need to show up in a queue at some percentage (e.g. every 10th message will be message with priority 2, and every 100th message will be with priority 3 etc.).
  • if there are already messages with lower priority on head of the queue, higher priority should come before those on arrival
  • if there are already messages with lower priority on head of the queue, and we do not receive more higher prior. messages - when taking from queue we take those with lower priority first

Example1:

  • t1 - priority 1 (showing up 5 in 8)
  • t2 - priority 2 (showing up 2 in 8)
  • t3 - priority 3 (showing up 1 in 8)

Possible state of this queue (first 8 messages)

q = t1,t1,t2,t1,t1,t2,t1,t3

Example2:

after 5 t2 messages arrive to an empty queue I have:

q = t2,t2,t2,t2,t2

now if there are 10 t1 messages that arrive, I need following distribution:

q = t1,t1,t2,t1,t1,t2,t1,t1,t2,t1,t1,t2,t1,t1,t2

Is there already some algorithm that implements this functionality?

Solution

  • My idea is to keep three different queues for each priority. Maintain the count of number messages in each queue.

    Let ratio1 = c1 / (c1 + c2 + c3). In your example, c1, c2, c3 are 5, 2, 1 respectively.

    Pick (n1 * ratio1) messages from first queue, then pick (n2 * ratio2) messages from second queue, so on. n1, n2, n3 are number of messages currently in queue 1, 2, 3 respectively.

    I explained my overall idea. You can extend this to any number of queues.

    I thought of naming the above scheme as Priority based Round Robin algorithm. I searched for this name and I found a relevant article as well. Hope it helps.