Patent ID: 6957431

Claim:
A computer program product for improving scheduling of tasks, the computer program product embodied on one or more computer readable media for execution on a computer and comprising: computer-readable program code for computing whether execution of a plurality of schedulable tasks is feasible, wherein each of the tasks has an associated cost and an associated deadline; computer-readable program code for computing a task-specific maximum cost extension allowable for a subsequent execution of each task, wherein the maximum cost extensions for all the tasks, when taken together, allow the execution of the plurality of tasks to remain feasible and wherein the maximum cost extension allowable for each task is computed incrementally by using, for a first subsequent execution, a fixed percentage of the associated cost for the task to compute a revised cost and by using, for other subsequent executions, a fixed percentage of the revised cost for the task; and computer-readable program code for using, upon determining that any of the schedulable tasks exceeds its associated cost during its subsequent execution, the maximum cost extension for that task as an upper limit on additional allowable execution time for the task.