1
$\begingroup$

I'm trying to write a small task scheduling function that takes a list of tasks, each with an assigned priority. These tasks are meant to update some values in a database, and some need to run more frequently than others.

I'm using priorities to represent the frequency, so if task A has priority 1 and task B has priority 2, then task B should run twice as often as task A regardless of the available resources. Eventually I want to combine this will multiple threads, but for now I'm using a single loop that runs one task or another depending on the last time each task ran.

The formula I'm using is very simple, but it's wrong although not completely wrong:

task.priority * (now - task.timestamp)

Note that now is not real time because it's just increased by 1 every time a task runs. And timestamp represents the value that now had the last time the task started running.

What I do is apply the formula above to all available tasks and run the one with the largest number. But the formula is wrong because it gives the wrong frequencies. Suppose task A ran on time 1, task B ran on time 2 and I want to know which task to run on time 3. The value of both tasks would be 2, so it'd have to just run a random task. But the task it should run is task B, because that'd produce the sequence ABB, which has the exact frequency assigned by their priorities.

I tried adding 1 to now and it fixed it for the A:1 and B:2 priorities, but for A:1 and B:3 priorities it gives me the wrong frequencies again (this time it runs task B way too often). Is there a way to calculate the number I need given only the task priorities and timestamps? I feel like I may need to plug in my formula some aggregate value taken from the timestamps of all tasks, but I'm not sure which value or where to put it in the formula.


Edit: So I think I found a solution based on Ethan's suggestion by tracking the time a task is first added to the task list and the number of times it has run so far. Here is my updated function:

task.priority * (now - info.start) / (info.runs + 1)

Here, start is when the task was added to the list, which also allows me to dynamically add tasks while the loop is running, and runs is how many times it has run since the start, so the right side of the multiplication is the average interval between each run. The +1 just avoids dividing by 0.

$\endgroup$

1 Answer 1

1
$\begingroup$

You probably should use cumulative information rather than relying on when each task was last run.

For each task, normalize its priority by scaling by the total of the task priorities. Now the priority of a task is the proportion of times it is to run.

Keep a cumulative list of the proportions of times each task has run.

Calculate next task to run from that list in some satisfactory way - some measure of how much its desired-proportion is less than its proportion-so-far.

The next job might be determined by the maximum difference between the desired-proportion and the proportion-so-far or by the ratio that's furthest from $1$. Which produces better answers in the context of your application?

I suggest testing with relatively long strings of jobs, not very small examples.

This kind of scheduling strategy should work in a multithreaded situation.

$\endgroup$
2
  • $\begingroup$ This was my fear, having to keep track of previous timestamps. But I guess it makes sense since timestamps can only exist on specific timeslots, while priorities can take any value, so timestamps contain less information than priorities (this is clear if you had for instance tasks/priorities A:1, B:1.1). But maybe I could use some kind of moving average instead of a list... $\endgroup$
    – Juan
    Commented Aug 20, 2023 at 19:25
  • $\begingroup$ I'm not suggesting you keep the whole history, nor need you keep any timestamps at all. You just keep the total number of times each job has run. When you schedule a job you increase its run count by $1$. $\endgroup$ Commented Aug 20, 2023 at 19:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .