Patent ID: 8621473

Claim:
A method for applying constrained rate monotonic scheduling to schedule a first schedulable entity onto an execution timeline for a first processing entity in a constrained environment, the execution timeline having both schedulable windows of time and non-schedulable windows of time based on constraints placed on the execution timeline, the method comprising: determining available capacity at a rate of the first schedulable entity on the execution timeline for the first processing entity based on the constraints placed on the execution timeline over a plurality of time periods, wherein schedulable entities can only be scheduled onto the execution timeline during the schedulable windows of time that are not precluded by the constraints, wherein the schedulable entities cannot be scheduled onto the execution timeline during the non-schedulable windows of time that are precluded by the constraints placed on the execution timeline, wherein neither previously scheduled schedulable entities nor overhead are constraints placed on the execution timeline; determining whether enough available capacity at the rate of the first schedulable entity exists to schedule the first schedulable entity with a first budget at the rate onto the execution timeline; and when enough available capacity at the rate of the first schedulable entity exists to schedule the first schedulable entity with the first budget at the rate, scheduling the first schedulable entity onto the execution timeline for the first processing entity during a first schedulable window of time; when the first schedulable entity is scheduled onto the execution timeline, updating the available capacity at each of a plurality of rates including the rate to reflect the capacity utilized by the first schedulable entity at the rate, wherein the available capacity at two of the plurality of rates is different.