Constrained rate monotonic analysis and scheduling

A system for applying constrained rate monotonic scheduling to schedule a first schedulable entity onto at least one execution timeline for a first processing entity in a constrained environment, the at least one execution timeline having both first schedulable windows of time and first non-schedulable windows of time based on constraints placed on the execution timeline, the system comprising:

• a first processing entity configured to execute first program instructions contained in a first plurality of schedulable entities, wherein the first processing entity comprises at least one of a processor, a core, and a hyperthread of a hyperthreaded processor;
• and
• a first scheduler configured to schedule the execution of the first plurality of schedulable entities on the first processing entity, wherein the first scheduler:
• determines the available capacity at a rate of the first schedulable entity on a first execution timeline for the first processing entity based on constraints placed on the first execution timeline over a first plurality of time periods, wherein schedulable entities can only be scheduled onto the first execution timeline during the first schedulable windows of time that are not precluded by constraints, wherein the schedulable entities cannot be scheduled onto the execution timeline during the first 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;
• determines when 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 first execution timeline of the first processing entity;
• 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 onto the first execution timeline of the first processing entity, schedules the first schedulable entity onto the first execution timeline for the first processing entity during a first schedulable window of time;
• and
• when the first schedulable entity is scheduled onto the first execution timeline, updates the first available capacity at each of a first plurality of rates including the rate to
• reflect capacity utilized by the first schedulable entity at the rate, wherein the available capacity at two of the plurality of rates is different.

An avionics system comprising:

• a first avionics computer configured for applying constrained rate monotonic scheduling to schedule a first schedulable entity onto at least a first execution timeline for a first processing entity in a constrained environment, the execution timeline having both first schedulable windows of time and first non-schedulable windows of time based on constraints placed on the execution timeline, the first avionics computer having:
• a first processing entity configured to execute first program instructions contained in a first plurality of schedulable entities;
• and
• a first scheduler configured to schedule the execution of the first plurality of schedulable entities on the first processing entity, wherein the first scheduler:
• determines the available capacity at a rate of the first schedulable entity on a first execution timeline for the first processing entity based on constraints placed on the first execution timeline over a first plurality of time periods, wherein schedulable entities can only be scheduled onto the first execution timeline during the first schedulable windows of time that are not precluded by constraints, wherein the schedulable entities cannot be scheduled onto the execution timeline during the first 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;
• determines when 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 first execution timeline of the first processing entity;
• 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 onto the first execution timeline of the first processing entity, schedules the first schedulable entity onto the first execution timeline for the first processing entity during a first schedulable window of time;
• and
• when the first schedulable entity is scheduled onto the first execution timeline, updates the first available capacity at each of a first plurality of rates including the rate to reflect capacity utilized by the first schedulable entity at the rate, wherein the available capacity at two of the plurality of rates is different.