I wonder if non-RM/DM priority assignment is really better for MP
The example in my previous post is, I think, typical of the problems used to show the nastyness of scheduling for a multi-processor. It has three tasks:
- t1 uses 80% of a processor with a period/deadline of 100.
- t2 uses 50% of a processor with a period/deadline of 40.
- t3 uses 25% of a processor with a period/deadline of 40.
Deadline-monotonic priority assignment will give t1 the lowest priority, giving it no way to get the 80% it needs. Whenever all three tasks want to run at the same time, another task will preempt t1. All those preemptions leave it with a worst-case response time of 110. Too late.
Audsley's algorithm was designed for systems where DM priority assignment does not work because all deadlines are not <= period. It works by finding a task that will meet its deadline when it has the lowest priority, giving that task that priority, and then continuing with the remaining set of tasks to find a task for the next lowest priority. I don't think it was intended for MP scheduling, but the applet is using it there.
Audsley's algorithm sees that t3 can succeed with the lowest priority, t2 with the next lowest, and t1 needs the highest priority.
I wonder whether this is an isolated example, or does choosing priorities this way consistently work better than DM for MP systems.
If it does consistently work well, this is a fine application for software. Using priority to express importance is famously a bad idea for hard real-time systems, and selecting priorities by intuition is unreliable. Audsley's algorithm may select priorities well, but it is too tedious for a human. It takes O(tasks-squared) time, and its inner loop uses the MP RTA algorithm which is worse than tasks-squared-- maybe tasks-squared-times-max-period-in-timer-units. Work like that calls for a computer.
- peterd's blog
- Login or register to post comments
I don't think Audsley's algorithm always works in this case.
The applet uses a refined version of the MP RTA algorithm that runs the basic analysis multiple times refining (reducing) the amount of interference due to higher priority tasks based on their previously-computed response times. For any one pass, I don't yet see a way for the relative priorities of higher-priority tasks to change the response time being computed, but with multiple passes, I think the order matters.
That would mean that Audsley's algorithm is a heuristic for setting priorities, but if it says there's no feasible priority choice, it's not necessarily right.
I hope I'm wrong.
Audsley's algorithm won't always work in a single queue MP
There is no efficient optimal algorithm (e.g., Audsley's algorithm) for priority assignments in a single-queue MP - a heuristic is the best we can hope for. The MP optimal scheduling problem is known to be NP-hard (i.e., computationally intractable). However, it should be possible to bound the response time for the MP schedule given any particular priority assignment such as would be produced with a heuristic.
Also, it is known that greedy algorithms will not likely be optimal - the optimal schedule will likely involve leaving processors idle sometimes while ready threads remain on the ready queue. I'm not aware of any actual MP scheduling algorithms that account for non-greedy approaches. Certainly Rate Montonic (RMS), Deadline Monotonic (DMS), Earliest Deadline First (EDF), and Least Laxity First (LLF) are greedy.
For this discussion, an "optimal" algorithm means that if the algorithm is unsuccessful, no successful result is possible. Audsley's algorithm, RMS, DMS, EDF, and LLF all have optimality properties for some set of single processor schedules, but none are optimal for MP's.
Of course, as with any NP-hard problem, an exhaustive search could generate an optimal solution as long as the problem remains small (i.e., a small number of processors, threads, and blocking sources.)
Thanks Doug
It's always useful (if sad) to know that something is known to be NP-hard.
But, it's surprising how well Audsley's algorithm works as a heuristic. Sometimes its choices are a bit surprising.
If you want to experiment, don't use small numbers of tasks. The applet really does go exponential-time for finding priorities for <= 16 tasks.