US Patent: Aparatus and Method For the Real-Time Processing of a Pulality of Tasks

Even in the daily life we have a question of what to do the first in a list of things to do.

The handling of interruption in a classic computer architecture assigns a fixed priority to each event. It happens in reality that a higher priority task interrupts one with lower with lower priority although the later is a final stage of its task. The resource needed to fish this final stage are less than the resource needed to swap the task forth and back (like push/pop the stack, change the execution environment etc.) Indeed, it is mathematically proven that in a real time system 30% idle time for processer is needed to ensure that all tasks are executed in time.  This indicates that there is potential to improve the performance of a system by some better scheduling algorithm.

This paten presents a hardware that implements an algorithm called the Earliest Deadline First that dynamically assigns a task with highest priority if it has the earliest deadline to finish.