Latest on the Beta Applet
Today I made two changes to the applet:
- Clicking on the header for a column will sort the results table on that column. No, clicking on it twice won't sort it in reverse order. :-)
- There's now an exponential time algorithm for finding a feasible set of priority assignments for MP systems. The applet will try this algorithm if the Audsley's algorithm (heuristic) fails and there are no more than 16 tasks.
Sixteen is pretty conservative. The applet could probably search for priorities over 20, or even 25 tasks quickly enough that users wouldn't assume the applet was wedged. Maybe I'll increase it sometime, but if I do I'm likely to implement a progress bar so there'll be some sign of life.
There's another exponential time algorithm that would be fun to add. Ted Baker has an exponential time search for exact feasibility results on MP systems. I wonder if there's any point in having the applet make heroic (exponential time) efforts to get precise values for up to somewhere around 25 tasks, and then fall back to approximate results?
- peterd's blog
- Login or register to post comments
Bugs -- already
When the applet uses the exponential-time search for a feasible set of priority assignments, it will display what it finds, but --- here's the bug --- the block at the top of the results area always says that it didn't find a feasible priority assignment.
Putting a positive spin on this. Until I fix the bug, this artifact reveals the cases where Audsley's algorithm failed and exhaustive search succeeded.
Bug fixes
It turns out that even a bound of 16 on the exponential algorithm is way too high. Less than 8 works better.
Now, the message at the beginning of the message block indicates whether the priority assignment was exhaustive or heuristic. If it searched exhaustively and didn't find working priorities, the message says "No priority assignment makes this system feasible." If it uses the heuristic, it says "No feasible priority assignment was found."
The fixed applet is on the web page. As normal, you need to restart your browser if it remembers the old applet.