There are several periodic tasks (Period, Execution time),
e.g.:
- A = (20, 9)
- B = (12, 4)
- C = (4, X)
What methods/tests can be used for finding the maximum execution time X for which the task set will be schedulable by Rate Monotonic.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Which version of "rate-monotonic scheduling"? Can you explain it and/or show a non-trivial simple example? $\endgroup$– John L.Commented Dec 3, 2018 at 23:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
First of all, this problem is (weakly) NP-hard, see this paper by Ekberg and Yi, because it generalizes the problem of deciding which task sets are schedulable by Rate Monotonic.
However, assuming that your periods and execution times are integers, you can find the answer in pseudopolynomial time. Simply try all values of $X$ from $0$ to $p$, where $p$ is the period of the task with variable execution time. For each of these values, simulate the Rate Monotonic algorithm until time $\max_{i=1}^n p_i$ (that is, the largest period in your task set), to check that the task set is schedulable. The largest value of $X$ for which your task set results schedulable in the simulation will give you the answer.
You might be able to do somewhat better if you have more information about your tasks. For example, if the variable task is the one with largest period (not true in your example), I think the following will work:
Simply simulate the Rate Monotonic algorithm time step by time step, as if $X$ was infinitely large, and doing the following in addition:
Initialize a counter $K$ to zero.
At every time unit in which Rate Monotonic tells you to run the lowest priority task, you increase the counter $K$ by one.
After $p_n$ time units (where $p_n$ is the period of your lowest-priority task), stop the simulation.
The value of $K$ at the end of the simulation will be the largest possible value of $X$.
