Priority queue in Java so each producer gets one turn at a time

96 views Asked by At

If I have multiple users (not countable), who each are putting work items on a queue, how can I implement a queue so that each user gets one turn at a time?

For example, if I have users A B C, and have a queue like [A A B C D A A B C A], I'd want it to be processed in this order [A B C D A B C A A]

This would be easy to implement but what if more work comes in while processing the current queue elements. So:

  • Start with queue: [A A B C D A A B C A]
  • Process the queue: A B C D
  • Queue is now: [A A A B C A]
  • More work is added: [A A A B C A D E A B C]
  • Process the queue A B C D E

etc

I do not know ahead of time how many different possible users there will be, so cannot simply iterate through a predefined list of users and do work (if there is any) for each. I don't care about the order that each user's work gets processed, as long as no user gets two units work while other users have work waiting.

1

There are 1 answers

2
vicg On BEST ANSWER

So the way I would solve this problem off the top of my head would be to have a hashmap where the different users (ie A, B, C, D etc) would be the keys and the value associated with each key would be the number of "turns" they have left. Then you can simply iterate through the map, check if the "user" has any more "turns" left, if they do, process it, if they don't, go to the next "user".

edit: Use an array protected by mutex locks or some threadsafe ordered object to hold every user being processed. Also add the users to a concurrenthashmap as keys where the value associated with each key is the number of steps until they are done. Have another variable which holds the current position on the list.