1
$\begingroup$

The scenario is something like this

  • I have tasks that get requested, with a category and a priority
  • For simplicity let's assume that rate of incoming tasks and completion is about the same, with some existing backlog of tasks
  • Each category of tasks can only be completed at some certain rate
  • Completion of tasks is handled out of the system, so we can assume that deciding to take on a certain task is equivalent to completing it

So I want some way of deciding which tasks to complete at a given time, given the existing tasks and their priorities, and the limits on completion within a certain category

One greedy algorithm would be to just organize each category by priority, and then at each decision point take in as many tasks as is allowed by that category's rate, but the problem with this is that if a lot of high priority tasks come in low priority tasks will just sit in the backlog, potentially forever.

I've looked at some scheduling concepts like round robin scheduling and multilevel priority queues, but they don't seem to fit what I want - tasks can't be paused/rescheduled as in round robin, and multi priority queues seems like it'd still have the problem of getting to low priority tasks (could just make the priorities more stratified, but then it's just back to the original problem with deciding how many tasks to take from each queue)

Any advice on what I should look into? Maybe it's a sort of "repeated knapsack" thing?

$\endgroup$
2
$\begingroup$

What you can do is to add another parameter to your tasks, something that I would call dynamic priority delta. Or what is equivalent, you can implement some mechanism to increase or decrease the priority of each task on top of multilevel priority queues.

The basic idea is simple. "A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.", reads section 5.3.6 of Operating Systems Concepts, seventh edition. For an extreme simple example, you can just increase priority level by one if a task has waited for an hour. Here is more excerpt from that book.

In general, a multilevel feedback-queue scheduler is defined by the following parameters:

  • The number of queues
  • The scheduling algorithm for each queue
  • The method used to determine when to upgrade a process to a higher- priority queue
  • The method used to determine when to demote a process to a lower- priority queue
  • The method used to determine which queue a process will enter when that process needs service

The definition of a multilevel feedback-queue scheduler makes it the most general CPU-scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it is also the most complex algorithm, since defining the best scheduler requires some means by which to select values for all the parameters.

Your situation might be even more complex since your task are also labelled with category. Without more information, I cannot advise further into your scheduling algorithm.

I encourage to read chapter "CPU Scheduling" of Operating System Concepts by Avi Silberschatz, Peter Baer Galvin and Greg Gagne. For even more content, read chapter "Uniprocessor Scheduling" and "Multiprocessor and Real-Time Scheduling" of Operating System Internals and Design Principles by William Stallings. Although they are talking about CPU or processor scheduling, most of the concepts and algorithms are the same as in or can be applied to job/task scheduling. You will find lots of inspirations and ideas and references.

$\endgroup$
0
$\begingroup$

One solution that I've read about, but haven't tried implementing myself as of yet, is to slowly increase the priority of tasks as time goes on. For instance, each time you pop off requests you could update all lower-priority tasks (or after every X requests have been popped off, etc). Thus eventually all tasks will get to execute.

$\endgroup$
0
$\begingroup$

Most every operating system under the sun has it's take on this. Check an operating systems text, they describe some simple variants.

For Linux, the standard is the Completely Fair Scheduler (CFS); but there are others to handle real time tasks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.