Derive discrete formula for priorization algorithm

For priorized scheduling of event-driven jobs in a software system I came up with the following algorithm:

Let there be $k$ priority classes, represented by the first $k$ natural numbers, a finite set of job classes $J$ and for each $j \in J$ there exists an infinite set of possible job instances $I(j)=\{j_1,j_2,\dots\}$.

Define function $prio$, which maps job classes to priority classes and job instances to priority values:

• $prio: J\to \{1,\dots ,k\}$
• $prio: I(j)\to \mathbb{N}$

For each priority class $p$, let $c_p$ be the priority counter associated with that class. These counters are initialized with $c_p:=0$

When job instance $j_i$ enters the system, set:

• $c_{prio(j)}:=c_{prio(j)}+prio\left(j\right)$
• $prio(j_i) := c_{prio(j)}$

Job instances are scheduled in the relative order of their respective priority values. If priority values of two jobs from different classes are equal, the job with lower priority class is scheduled first.

In my intuition, this should yield an algorithm where, under constant workload in all priority classes, jobs with class 1 are executed approximately twice as often as jobs with class 2 and three times as often as jobs with class 3, etc.

I tried with a short example of 3 priority classes and 3 instance insertions for each class.

_____|_____executions per class_____
time | class 1 | class 2 | class 3 |
-----|------------------------------
0  |  0      |  0      |  0      |
-----|------------------------------
1  |  1      |  0      |  0      |
-----|------------------------------
2  |  2      |  0      |  0      |
-----|------------------------------
3  |  2      |  1      |  0      |
-----|------------------------------
4  |  3      |  1      |  0      |
-----|------------------------------
5  |  3      |  1      |  1      |
-----|------------------------------
6  |  3      |  2      |  1      |


I wanted to derive a discrete formula for this, so I can programatically generate a table like the above without simulation. This would be a function of the 3 parameters $k$ (number of prio. classes), $i$ (priority class we are looking at) and $n$ (number of timesteps).

I tried for a while and fiddled around with those parameters but i couldn't get to a result. I also found that I lack methodology in searching for the right solution, which is why I decided to finally sign up on stackoverflow after having lived off others questions and answers for quite some time now.

I am not necessarily looking for answers with the right formula, i would love if someone could give a hint or two on how real mathematicians would tackle this problem, maybe some literature for beginners. I honestly don't even know which field of math this procedure (finding formulas for algorithms) would resort to, or where to start digging. Every single effort is very much appreciated.

• The table you plotted looks like dynamic programming, could you reformulate it as a recursive relation ? Oct 1 '15 at 19:10
• Can a specific job instance enter the system multiple times. You write that (if it can) it will be assigned the same priority every time it enters. Is this your intention? Oct 3 '15 at 22:28
• @EricTowers no this was not intended, sorry for the confusion. A job instance will only enter the system one time. I just introduced the notion of job instances to differentiate between multiple "calls" to the same job. You can safely assume that $y>x \iff \text{$j_x$enters the system before$j_y$}$. Oct 4 '15 at 10:06
• @UriGoren I haven't had the time to actually try it with a recursive relation yet, but your comment just gave me an idea on how it might be done recursively with a conditional defintion. Oct 4 '15 at 10:10

You seem to be describing a batch scheduler: It receives the (potentially infinite) list of job instances at time zero and then instantaneously assigns the schedule of the instances. But your table does not agree. It appears that job instances arrive at undefined times in undefined numbers and that the scheduler cannot schedule an instance until it arrives. There is also no information about a descheduler (an object that clears an instance from a priority (queue) so that the next enqueued instance of that priority can be preformed). With these gaps, I've proceeded with the system as described (infinite sequence of instances and instantaneous simultaneous scheduling at time zero).

There are $k$ priority classes and the number of job instances of each priority class that enters the system is initially zero and then at each step increases by $0$ or $1$. We may therefore model the numbers of each priority class that have entered the system as a point in $\mathbb{N}^k$, $x = (x_1, \dots, x_k)$. The system is driven by some sort of random walk in this space.

Once the $s^\text{th}$ job instance enters the system, we have the relation $\sum_{n=1}^k x_n = s$, so at the $s^\text{th}$ "step", the point $x$ lies on the hyperplane satisfying this relation. This hyperplane advances by the same amount on each step, so we may remove this "drift" and discover that the system is really only engaged in a two dimensional random walk with a constant drift.

The $k$ different priority counters are independent, in the sense that the $c_k$ is only incremented when a job of priority class $k$ enters the system and the entrance of a job of another priority class has no effect on that counter. This means that the values of the priority class counters are independent of the path taken through $\mathbb{N}^k$ -- once the walk arrives at $x$, the values of the priority class counters are $c_i = i x_i$.

(You asked how a "real mathematician" would tackle this problem. I'm not technically a real mathematician yet (for some definitions), but the basic method is induction. Observe that before any job instances enter, the counters are at $(0,0,\dots,0)$, so the formula is initially true. Then from any point $(x_1, x_2, \dots, x_j)$, the entry of a job instance increases one coordinate by exactly the amount the formula says it will. So by induction, the formula holds. This is the sort of general argument one uses for this sort of situation. We are able to make the simpler, more global, argument that I wrote above because the system separates into little systems that don't interact.

This is also where the difference between the online scheduler and the pre-scheduler differ -- an online scheduler cannot cause an entering job instance to travel back in time and be scheduled prior to "now". I.e., the queue of waiting jobs at each priority class cannot contain negative numbers of jobs. Consequently, we also have to model the depth of these queues as well as the number of jobs of each types found so far. Also, the depth of a queue is upper bounded by the number of instances of its type which have come so far. Consequently, not all of the $2k$-dimensional space of counts and depths is accessible, and this lack of accessibility is where the induction becomes hard. If you want to approach this version of the problem, we need to know quite a bit more than was provided in the original question.

Also, if you hadn't asked about how real mathematicians would approach this, I would have recommended routing this question to cs.stackexchange.com)

Consequently, assuming an infinite supply of job instances of each priority class entering the system, those of priority class $1$ will be assigned to successive integers, those of priority class $2$ will be assigned to even integers, ... those of priority class $i$ will be assigned to multiples of $i$. This means that your intuition that $1$ jobs are scheduled twice as frequently as $2$ jobs and thrice as frequently as $3$ jobs is correct.

Answering the question more generically requires more information than provided in the problem: Suppose that the $1$ jobs enter the system one-third as often as $2$ jobs, i.e., $x_1 = (1/3) x_2$. Then there are $x_2$ of $2$ jobs evenly scheduled up to slot $2 x_2$ and $x_2/3$ $1$ jobs scheduled up to $(1/3) x_2$. That is, the queue of $1$ jobs has been severely starved. Then your intuition is (temporarily) incorrect, but only because whatever random process causes jobs to enter the system has had a persistent fluctuation leading to under-entrace of $1$ jobs. If the Law of Large Numbers holds and the entrance of job instances of each priority class is equiprobable, then this fluctuation will pass and eventually the queue of $1$ jobs will "catch up"...

But it can't catch up. Suppose equi-probability actually holds at some point so that $x_1 = x_2 = \cdots = x_k$, then there are $x_1$ priority $1$ jobs scheduled to slot $x_1$, $x_1$ priority $2$ jobs scheduled to slot $2 x_1$, $x_1$ priority $3$ jobs scheduled to slot $3 x_1$, ... $x_k$ priority $k$ jobs scheduled to time $k x_1$. In other words, the last priority $1$ job will be scheduled to start when only half of the $2$ jobs, one-third of the $3$ jobs, et c. have been started. After this time, the priority $2$ and subsequent queues slowly empty, bringing the ratios of jobs scheduled (back) to $1$ for any pair of priorities.

However, back to your question about formulas... Assuming that the probability of entry of a job of each priority class is the same, $p_1 = p_2 = \cdots = p_k$, then the expectation coordinates are all the same and the scenario where the priority $1$s are all scheduled in half the time of the priority $2$s and so on holds. The distribution of locations is expected to be approximately normally distributed with standard deviation the square root of the number of jobs entered so far times the step size. The step size is $\sqrt{1^2 - (\sqrt{3}/3)^2} = \sqrt{2/3}$ (We have a right triangle with a hypotenuse that is one side of a unit cube and with one leg one third the length of the long diagonal.) With 90% probability, we expect the point in the space to be within $1.644...$ standard deviations of the expectation value. Suppose then we have supplied $kN$ job instances; we are 90% likely to find that the point is within $\sqrt{2kN/3}$ of the point $(N,N,\dots, N)$. Suppose for clarity, the discrepancy is entirely in priority class $1$ so that the coordinates for the point are (in 90% of the possible simulations) between $(N - (k-1)/k \sqrt{2kN/3}, N + (1/k)\sqrt{2kN/3}, N + (1/k) \sqrt{2kN/3}, \dots , N + (1/k) \sqrt{2kN/3})$ and $(N + (k-1)/k \sqrt{2kN/3}, N - (1/k)\sqrt{2kN/3}, N - (1/k) \sqrt{2kN/3}, \dots , N - (1/k) \sqrt{2kN/3})$. For huge $N$, the leading term dominates and the result is very near (in a ratiometric sense) to the equiprobable case. For small $N$, the $\sqrt{N}$-sized term can be noticeable. Note also that increasing $k$ decreases the discrepancy in the second and subsequent coordinates. But this is only a single estimate to get an idea for how bad a simulation can deviate from the expected behaviour. To get the formula you're thinking about, we approach it in two steps...

First, we recognize that the marginal distributions of multivariate normal distributions are normally distributed (with the "obvious" mean and standard deviation), so under the normal approximation, with $k$ the number of priority classes, $i$ a particular priority class, and $N$ the number of timesteps, the value in the table is a random variable $$T(k,i,N) = NormalDistribution(N/k, \sqrt{2N/3})/i$$ where the $N/k$ represents equidistribution and each variable contributes $\sqrt{2N/3}$ standard devation, the rms of which is $\sqrt{2kN/3}$. Finally the "$/i$" reminds us that the entries in column $i$ only increment on rows divisible by $i$.

But then we go back to what we knew above. Assuming instantaneous batch scheduling at time zero and a promise that every job class appears infinitely often in the sequence of entering job instances, then each table entry is just $$T(k,i,N) = \left\lfloor \frac{N}{ik} \right\rfloor$$ where $\lfloor \cdot \rfloor$ is the "floor function" or "the greatest integer not greater than" function. For instance, $\lfloor 0 \rfloor = \lfloor 1/k \rfloor = \cdots \lfloor (k-1)/k \rfloor$ and $\lfloor 1 \rfloor = 1$.