US Patent 9766931 Uniprocessor schedulability testing for non-preemptive task sets

A method of determining schedulability of tasks for uniprocessor execution includes defining a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. A determination of whether the task set is schedulable is made, such that a near-optimal amount of temporal resources required to execute the task set is estimated. Further, a method of determining schedulability of a subtask for uniprocessor execution includes defining a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. A determination of whether a subtask in the task set is schedulable at a specific time is made in polynomial time. Systems for implementing such methods are also provided.