(semi) rate limited queue with priority for 100% resource utilization

Question

I'm working on a api that will make it possible for different users to queue up jobs for processing, and need a algorithm to make sure that one user doesn't hog up all the resources. This would be easily solved with a round robin queue between the users, but there's one more problem... Some users will have higher priority than others, capped at a certain jobs / minute. How can I design this in a way that doesn't make the priority users totally block the other users and at the same time allow the queue to be processed faster than the rate limits on the users if possible.

The main problem I have is that it would be easy to cap all the users to their rate limits, but that would cause artificial waiting times as the system is usually able to keep up with regular loads. So the algorithm needs to allow users to surpass their rate limit during low load.

TLDR:

• need a queue algorithm
• 2 different priority users, high prio users should take priority
• high prio users should only take priority until their rate limit is reached
• algorithm must allow users to surpass their rate limit if there are resources to spare (no use to idle the CPU, better to process everything as fast as possible)
• no single user can be allowed to block the whole queue for the rest of the users

question from:https://stackoverflow.com/questions/65916833/semi-rate-limited-queue-with-priority-for-100-resource-utilization

Answer 1

Waitting for answers