Time-variant scheduling of affinity groups on a multi-core processor

Abstract

Methods and systems for scheduling applications on a multi-core processor are disclosed, which may be based on association of processor cores, application execution environments, and authorizations that permits efficient and practical means to utilize the simultaneous execution capabilities provided by multi-core processors. The algorithm may support definition and scheduling of variable associations between cores and applications (i.e., multiple associations can be defined so that the cores an application is scheduled on can vary over time as well as what other applications are also assigned to the same cores as part of an association). The algorithm may include specification and control of scheduling activities, permitting preservation of some execution capabilities of a multi-core processor for future growth, and permitting further evaluation of application requirements against the allocated execution capabilities.

We claim: 
     
         1 . A method for scheduling applications on a multi-core processor comprising a plurality of processor cores, the method comprising:
 associating a first at least two processor cores and a first plurality of address spaces with a first affinity group;   associating a second at least one processor core and a second plurality of address spaces with a second affinity group;   scheduling one or more of the first affinity group and the second affinity group to execute on associated cores of the multi-core processor; and   executing the one or more of the first affinity group and the second affinity group on associated cores of the multi-core processor.   
     
     
         2 . The method of  claim 1 , wherein the first affinity group comprises at least one dependency group comprising a plurality of address spaces that share at least one resource. 
     
     
         3 . The method of  claim 2 , further comprising scheduling a plurality of address spaces associated with at least one dependency group. 
     
     
         4 . The method of  claim 2 , wherein the second at least one affinity group comprises at least one of the at least one dependency group. 
     
     
         5 . The method of  claim 1 , wherein only applications associated with the first plurality of address spaces are eligible to be scheduled on the first at least one processor core when the first affinity group is being executed. 
     
     
         6 . The method of  claim 1 , wherein at least one of the first plurality of address spaces is a primary address space eligible to run on any of the first at least one processor core. 
     
     
         7 . The method of  claim 1 , wherein at least one of the first plurality of address spaces is a restart address space eligible to restart on any of the first at least one processor core. 
     
     
         8 . The method of  claim 1 , wherein at least one of the first plurality of address spaces is a background address space eligible to run in the background on any of the first at least one processor core. 
     
     
         9 . The method of  claim 8 , wherein the step of scheduling the background address space further comprises scheduling based on a priority less than a predetermined threshold. 
     
     
         10 . The method of  claim 1 , wherein the step of scheduling further comprises activating one of a plurality of schedules for at least one of the associated cores. 
     
     
         11 . The method of  claim 1 , wherein the step of scheduling comprises scheduling the first affinity group and the second affinity group to execute simultaneously on one or more cores of the multi-core processor. 
     
     
         12 . The method of  claim 1 , wherein the first plurality of address spaces comprises at least one address space in the second plurality of address spaces. 
     
     
         13 . The method of  claim 1 , wherein the first at least one affinity group comprises at least one address space in the second at least one affinity group. 
     
     
         14 . The method of  claim 1 , further comprising scheduling a task to run on a processor core according to a task-core affinity for the task. 
     
     
         15 . The method of  claim 1 , further comprising scheduling a task to run on a processor core according to a task-core affinity if the task has an affinity for the processor core associated with the affinity group scheduled for execution. 
     
     
         16 . The method of  claim 1 , further comprising not scheduling a task for execution with an affinity group if the task has an affinity for a processor core that is not associated with the affinity group. 
     
     
         17 . The method of  claim 1 , wherein the step of scheduling further comprises:
 releasing a first address space for scheduling;   synchronizing the plurality of processor cores;   processing a scheduling event for the first address space; and   assigning the first address space to a processor core for the scheduling event.   
     
     
         18 . A method for scheduling applications on a multi-core processor comprising a plurality of processor cores, the method comprising:
 associating a first at least one affinity group with a first subsystem;   associating a second at least one affinity group with a second subsystem;   wherein the first at least one affinity group has no cores in common and no address spaces in common with the second at least one affinity group, whereby the first subsystem can be scheduled independently of the second subsystem; and   executing one or more of the at least one affinity group associated with the first subsystem and the at least one affinity group associated with the second subsystem on associated subsystems of the multi-core processor.   
     
     
         19 . A system for scheduling applications on a multi-core processor, comprising:
 a multi-core processor comprising a plurality of processor cores;   a plurality of affinity groups each comprising two or more of the plurality of processor cores and a plurality of address spaces; and   a scheduler configured for assigning one or more of the plurality of affinity groups to execute on associated cores of the multi-core processor and for initiating the execution of the one or more of the plurality of affinity groups on associated cores of the multi-core processor.   
     
     
         20 . The system of  claim 19 , wherein only applications associated with the address spaces assigned to an affinity group are eligible to be assigned to the processor cores assigned to the affinity group scheduled for execution. 
     
     
         21 . The system of  claim 19 , wherein at least one of the plurality of affinity groups comprises at least one dependency group comprising a plurality of address spaces that share at least one resource. 
     
     
         22 . The system of  claim 21 , wherein the scheduler is further configured for scheduling a plurality of address spaces associated with at least one dependency group. 
     
     
         23 . The system of  claim 21 , wherein at least two of the plurality of affinity groups share a dependency group. 
     
     
         24 . The system of  claim 19 , wherein the scheduler is further configured for activating one of a plurality of schedules for at least one of the associated cores. 
     
     
         25 . The system of  claim 19 , wherein the scheduler is further configured for scheduling a task to run on a processor core according to a task-core affinity for the task. 
     
     
         26 . The system of  claim 19 , wherein the scheduler is configured to schedule a task to run on a processor core according to a task-core affinity if the task has an affinity for a processor core associated with the affinity group scheduled for execution. 
     
     
         27 . The system of  claim 19 , wherein the scheduler is configured not to schedule a task for execution with an affinity group if the task has an affinity for a processor core that is not associated with the affinity group. 
     
     
         28 . The system of  claim 19 , wherein each of the affinity groups has no processor cores and no address spaces in common with any of the other of the plurality of affinity groups, to permit each of the plurality of affinity groups to be scheduled independently. 
     
     
         29 . The system of  claim 19 , wherein the scheduler is further configured for scheduling a first affinity group and a second affinity group to execute simultaneously. 
     
     
         30 . The system of  claim 19 , wherein the first plurality of address spaces comprises at least one address space in the second plurality of address spaces. 
     
     
         31 . The system of  claim 19 , wherein the first at least one affinity group comprises at least one address space in the second at least one affinity group. 
     
     
         32 . The system of  claim 19 , wherein the scheduler is further configured to propagate timing events of the first processor core to at most, the plurality of processor cores associated with the scheduling event. 
     
     
         33 . The system of  claim 19 , wherein the scheduler is further configured for:
 releasing a first address space for scheduling;   synchronizing the plurality of processor cores;   processing a scheduling event for the first address space; and   assigning the first address space to a processor core for the scheduling event.   
     
     
         34 . A system for scheduling applications on a multi-core processor, comprising:
 a multi-core processor comprising a plurality of processor cores;   a plurality of subsystems each comprising one or more affinity groups, wherein each of one or more affinity groups comprises two or more of the plurality of processor cores and a plurality of address spaces; and   a scheduler configured for assigning one or more of the plurality of affinity groups to execute on associated cores of the multi-core processor and for initiating the execution of the one or more of the plurality of affinity groups on associated cores of the multi-core processor;   wherein each of the subsystems has no processor cores and no address spaces in common with any of the other of the plurality of subsystems, to permit each of the plurality of subsystems to be scheduled and executed independently.