Fair job processing algorithm

Question

I have a machine that accepts custom downloads, does some processing on them, and returns a result. It usually takes several minutes to process each received download.

The problem is that multiple users can download many tasks, which basically deny processing to other users for a long time. I was thinking about how to simply install a hard cover and use priority queues, for example. after 5 downloads per hour, all new downloads have a lower processing priority. I basically want to handle ALL tasks, but I don't want the user to upload 1000 tasks to keep everyone waiting.

My question is: is there a better way to do this?

My goal is to minimize the time between loading and returning result. It would be ideal if the algorithm could work in a distributed way.

thanks

Answer 1

Implementation will vary widely depending on what kind of jobs they take and how much time they take, and how much processing time changes, and how fatal a mistake is during the process.

Thus, an easy way to maintain an even distribution of jobs among users is to maintain a list of all users who submitted jobs. When you are ready to get a new job, and not just do the next job from a random queue, banish the users, each time taking the top job from each user.

Again, this can be done in several ways, I would recommend a map from users to their respective list of submitted tasks. Sort through the card keys every time you are ready for a new task. then get a list of tasks for any key you are on, and complete the first task.

This assumes that each task is “atomic” in that one task does not depend on the execution next to the tasks with which it was sent.

Hope this helps, of course, I could completely misunderstand what you are asking.

Answer 2

You do not need to ride on your own. There is a Sun Grid Engine . An open source tool designed for this kind of thing, and if you are willing to pay, there is Platform LSF that I use at work.

Answer 3

What is the maximum number of jobs a user can submit? Can users send 1 task at a time or is it a batch of tasks?

So your algorithm will look something like this.

If the User has submitted jobs Then Check how many jobs per hour If the jobs per hour > than the average Then Modify the users profile to a lower priority Else Check Users priority level and restore End If If the priority = HIGH process right away Else If priority = MEDIUM Check Queue for High Priority If High Priority Found (rerun this loop) Else Process Else If priority = LOW Check Queue for High Priority If High Priority Found (rerun this loop) Else Process Check Queue for Medium Priority If Medium Priority Found (rerun this loop) Else Process Process Queue End If 

Answer 4

You can use a graph algorithm such as Edmond Blossom V to assign all users and tasks to a process. If a user can download more than another user, it would be easier for him to find a process. With the Blossom V algorithm, you can determine the threshold so as not to exceed the maximum process that the server can process.