Abstract:
The present disclosure is based on a multi-core or multi-processor virtualized environment that comprises both time-sensitive and non-time-sensitive tasks. The present disclosure describes techniques that use a plurality of criteria to choose a processing resource that is to execute tasks. The present disclosure further describes techniques to re-schedule queued tasks from one processing resource to another processing resource, based on a number of criteria. Through load balancing techniques, the present invention both (i) favors the processing of soft real-time tasks arising from media servers and applications, and (ii) prevents “starvation” of the non-real-time general computing applications that co-exist with the media applications in a virtualized environment. These techniques, in the aggregate, favor the processing of soft real-time tasks while also reserving resources for non-real-time tasks. These techniques manage multiple processing resources to balance the competing demands of soft real-time tasks and of non-real-time tasks.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. provisional application number 61/232,542, filed Aug. 10, 2009, entitled “Supporting Soft Real-Time Virtual Machines.” (Attorney docket 630-470 us). The concepts, but not necessarily the nomenclature, of this provisional application are hereby incorporated by reference. 
         [0002]    Furthermore, this application claims the benefit of U.S. provisional application number 61/254,019, filed Oct. 22, 2009, entitled “Supporting Soft Real-Time Virtual Machines.” (Attorney docket 630-486 us). The concepts, but not necessarily the nomenclature, of this provisional application are hereby incorporated by reference. 
         [0003]    U.S. patent application Ser. No. 12/686,719, filed Jan. 13, 2010, entitled “Credit Scheduler for Ordering the Execution of Tasks,” is related and is hereby incorporated by reference. (Attorney docket 630-482 us). 
         [0004]    If there are any contradictions or inconsistencies between this application and one or more of the cases that have been incorporated by reference, the claims in the present case should be interpreted to be consistent with the language in this case. 
     
    
     FIELD OF THE INVENTION 
       [0005]    The present invention relates to data processing systems in general, and, more particularly, to credit schedulers for ordering the execution of tasks on a processor. 
       BACKGROUND OF THE INVENTION 
       [0006]    When two or more operating systems operate on one piece of hardware, the tasks associated with each operating system contend for the hardware that is available. Without something to mediate their access, one operating system&#39;s tasks could monopolize or over-use the hardware to the detriment of the other operating system&#39;s tasks. When the hardware comprises more than one processor that is available to execute the various tasks, one processor can become over-utilized while another remains under-used. Therefore, a program sits between the operating systems and the hardware to act as a mediator. This program is commonly known as a “hypervisor.” 
         [0007]    One of the jobs performed by the hypervisor is to choose a processor that is to execute one or more tasks. Another job of the hypervisor is scheduling the order of execution of tasks. These are not easy jobs. Some tasks are time-sensitive (e.g., tasks associated with input or output, speech processing, video processing, transmission or reception of signals, etc.) and some tasks are non-time-sensitive or are less-time-sensitive. Whatever the mix of time-sensitive and non-time-sensitive tasks, the respective operating systems are always presenting to the hypervisor tasks to be performed, and if the hypervisor does not wisely choose the processor to execute the tasks or the order for executing those tasks, the performance of the entire system can be degraded. 
         [0008]    The portion of a hypervisor that chooses the hardware and determines the order for executing the tasks is called a “scheduler.” Schedulers in the prior art, however, do not always choose wisely, and, therefore, the need exists for an improved scheduler. 
       SUMMARY OF THE INVENTION 
       [0009]    The present invention enables the scheduling and execution of tasks on a plurality of processors without some of the costs and disadvantages associated with schedulers in the prior art. Tasks generally known in the art as “soft real-time” tasks are time-sensitive tasks that have somewhat flexible (or “soft”) deadlines. Tasks that perform general computing typically are non-time-sensitive tasks. The present invention serves the special needs of soft real-time tasks, and therefore, whether a task is time-sensitive or non-time-sensitive, is material to the operation of the illustrative embodiments disclosed herein. 
         [0010]    Prior art schedulers that manage multi-processor or multi-core computing have been challenged by soft real-time tasks, such as those in media servers and IP PBX applications. This results in poor quality of voice, image, or video. To avoid impairing voice, image, or video quality, prior art schedulers traditionally dedicate physical processing resources to soft real-time applications or else “starve” the non-real-time tasks of processing resources by favoring the soft real-time tasks. These solutions often cost more and generally produce degraded overall performance. 
         [0011]    The present invention addresses these challenges. Through load balancing techniques, the present invention both (i) favors the processing of soft real-time tasks arising from media servers and applications, and (ii) reduces “starvation” of non-real-time general computing applications that co-exist with the media applications in a multi-processor environment. 
         [0012]    The present disclosure in accordance with the illustrative embodiments describes load balancing techniques that apply to a multi-processor virtualization environment. These techniques, in the aggregate, favor the processing of soft real-time tasks while also reserving resources for non-real-time tasks. These techniques manage multiple processing resources to balance the competing demands of soft real-time tasks and of non-real-time tasks. The techniques use a plurality of criteria to choose a processor that is to execute tasks or particular groups of tasks. The present disclosure further describes techniques to re-schedule queued tasks from one processor to another processor, based on a number of criteria. 
         [0013]    Some illustrative embodiments comprise: scheduling by a data-processing system a first task to be executed on a first processor, wherein the first task is at the head of a first queue that comprises a plurality of tasks to be executed on the first processor; scheduling by the data-processing system a second task to be executed on a second processor, wherein the second task is at the head of a second queue that comprises a plurality of tasks to be executed on the second processor; and executing the second task on the first processor before the first task when: (i) the first task and the second task are of equal priority, and (ii) the first task is a non-time-sensitive task, and (iii) the second task is a time-sensitive task. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  depicts a schematic diagram of the salient portions of data-processing system  100  according to the illustrative embodiments of the present invention. 
           [0015]      FIG. 2  depicts a flowchart of the salient steps of data-processing system  100  according to the illustrative embodiments of the present invention. 
           [0016]      FIG. 3A  depicts a flowchart of the salient steps associated with the performance of step  201  according to a first illustrative embodiment of the present invention. 
           [0017]      FIG. 3B  depicts a flowchart of the salient steps associated with the performance of step  201  according to a second illustrative embodiment. 
           [0018]      FIG. 4  depicts a flowchart of the salient steps associated with the performance of step  315 . 
           [0019]      FIG. 5  depicts a flowchart of the salient steps associated with the performance of step  202 . 
           [0020]      FIG. 6  depicts a flowchart of the salient steps associated with the performance of step  501 . 
           [0021]      FIG. 7A  depicts a flowchart of the salient steps associated with the performance of step  502  according to the first illustrative embodiment. 
           [0022]      FIG. 7B  depicts a flowchart of the salient steps associated with the performance of step  502  according to the second illustrative embodiment. 
           [0023]      FIG. 8A  depicts a flowchart of the salient steps associated with the performance of step  503  according to the first illustrative embodiment. 
           [0024]      FIG. 8B  depicts a flowchart of the salient steps associated with the performance of step  503  according to the second illustrative embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0025]    For the purposes of this specification, the term “processor” is defined as a tangible computing resource that is capable of executing a task. 
         [0026]    For the purposes of this specification, the term “task” is defined as at least one operation performed by a processor. 
         [0027]    A first and a second illustrative embodiment are distinguished in regards to  FIGS. 3A and 3B ,  7 A and  7 B,  8 A and  8 B, respectively. In broad terms, the first illustrative embodiment is directed at re-scheduling the tasks that are next to be executed by each processor in the system, i.e., the tasks at the head of each queue; subject to the disclosed criteria, either time-sensitive or non-time-sensitive tasks can be re-scheduled. In broad terms, the second illustrative embodiment is directed at periodically (i) scheduling or re-scheduling tasks to a choice of queues for the respective processors in the system and (ii) re-scheduling of non-time-sensitive tasks that are next to be executed by a processor, i.e., the non-time-sensitive tasks at the head of each queue. 
         [0028]    In general, the methods according to the illustrative embodiments are triggered when a scheduler-related event happens in data-processing system  100 , i.e., an event requiring the scheduler to act. Examples of scheduler-related events are the arrival of a new task, the occurrence of an input/output (“I/O”) event for an existing task, a task relinquishing a processor, a processor becoming idle and available to execute another task, or a time-based trigger. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which the disclosed techniques are triggered by other criteria and considerations. 
         [0029]      FIG. 1  depicts a schematic diagram of the salient portions of data-processing system  100  according to the illustrative embodiments of the present invention. Data-processing system  100  is an apparatus that comprises: receiver  101 ; scheduler  102 ; queues  103 - 1  and  103 - 2 ; processors  104 - 1  and  104 - 2 ; and transmitters  105 - 1  and  105 - 2 . 
         [0030]    Although the illustrative embodiments comprise one receiver  101 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention that comprise any number of receivers, e.g., two receivers, three receivers, etc. For example, a receiver might be dedicated to each queue. 
         [0031]    Although the illustrative embodiments comprise one scheduler  102 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention that comprise any number of schedulers, e.g., two schedulers, three schedulers, etc. 
         [0032]    Although the illustrative embodiments comprise two queues  103 - 1  and  103 - 2 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention that comprise any number of queues, e.g., three queues, four queues, etc. 
         [0033]    Although the illustrative embodiments comprise two processors  104 - 1  and  104 - 2 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention that comprise any number of processors, e.g., three processors, four processors, etc. It will be further clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which a multi-core processor platform comprises some or all of the processors. It will be further clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which a processor comprises multiple cores. 
         [0034]    Although the illustrative embodiments comprise two transmitters  105 - 1  and  105 - 2 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention that comprise any number of transmitters, e.g., one transmitter, three transmitters, etc. 
         [0035]    Although the illustrative embodiments depict the components of data-processing system  100  as being connected to each other as in  FIG. 1 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which the components are differently connected. For example, each queue might receive tasks from a receiver before task scheduling occurs at scheduler  102 . 
         [0036]    Although the illustrative embodiments depict the components of data-processing system  100  as being separate from one another as depicted in  FIG. 1 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which a single physical device comprises one or more of these components. For example, a multi-core processor platform could comprise: some or all of the processors; some or all of the queues; some or all of the receivers; some or all of the transmitters in data-processing system  100 . Furthermore, it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which multiple physical devices are logically associated to comprise one or more of these components. For example, multiple processors that are distinct physical components could be logically associated in a virtualized computing environment. Likewise, a virtualized computing environment could comprise a combination of distinct and combined components in accordance with the present invention, such as a single-core processor and a multi-core processor. 
         [0037]    Although the illustrative embodiments present certain ratios of one type of component to another type of component as depicted in  FIG. 1 , it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which the ratios differ. For example, a single queue could be logically subdivided to serve more than one processor. For example, a single transmitter might transmit output from more than one processor. 
         [0038]    Receiver  101  is hardware that receives a temporal succession of tasks to be executed by processor  104 - 1  or processor  104 - 2  and provides those tasks to scheduler  102 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which receiver  101  is software or a combination of software and hardware. 
         [0039]    For purposes of the present disclosure, each task is identified by T i , wherein i is an integer that represents the relative order of arrival of the task at receiver  101  with respect to other tasks. For example, task T i  arrived at receiver  101  immediately before task T i+1 , wherein i is an integer. It will be clear to those skilled in the art, after reading this disclosure, how to make and use receiver  101 . 
         [0040]    Scheduler  102  is hardware and software that is capable of performing the functionality described in this disclosure and in the accompanying figures. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which scheduler  102  is exclusively hardware or exclusively software. It will be further clear to those having ordinary skill in the art, after reading the present disclosure, that a software-based scheduler  102  is itself executed by a processor. 
         [0041]    In accordance with the illustrative embodiments, scheduler  102  is a “credit” scheduler, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which scheduler  102  is not a “credit” scheduler. The XEN® hypervisor is an example of a hypervisor that comprises a credit scheduler. Furthermore, it will be clear to those skilled in the art that alternative well-known names for a hypervisor include, but are not limited to, a “virtual machine monitor” or “VMM.” It will be clear to those skilled in the art, after reading this disclosure, how to make and use scheduler  102 . 
         [0042]    Queue  103 - 1  is hardware that holds each task and its accompanying parameters, while the task awaits execution by processor  104 - 1 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which queue  103 - 1  is software or a combination of software and hardware. 
         [0043]    Queue  103 - 2  is hardware that holds each task and its accompanying parameters, while the task awaits execution by processor  104 - 2 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which queue  103 - 2  is software or a combination of software and hardware. It will be clear to those skilled in the art, after reading this disclosure, how to make and use queue  103 - 1  and queue  103 - 2 . 
         [0044]    Processor  104 - 1  is hardware that is a processor that executes tasks in the order determined by scheduler  102 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which processor  104 - 1  is a combination of software and hardware. In accordance with the illustrative embodiments of the present invention, processor  104 - 1  comprises one core, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which processor  104 - 1  comprises multiple cores. Furthermore, it will be clear to those skilled in the art that alternative names for a processor include, but are not limited to, “core,” “computing core,” “processing core,” “central processing unit,” “CPU,” “computing resource,” or “processing resource.” 
         [0045]    Processor  104 - 2  is hardware that executes tasks in the order determined by scheduler  102 . In the illustrative embodiments, processor  104 - 2  is a processor identical to processor  104 - 1 , but it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which processor  104 - 1  and  104 - 2  are not identical. 
         [0046]    In the illustrative embodiments, processor  104 - 1  selects the task at the head of queue  103 - 1  to execute next. In the illustrative embodiments, processor  104 - 2  selects the task at the head of queue  103 - 2  to execute next. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which a processor executes its next task from a source other than its corresponding queue. It will be clear to those skilled in the art how to make and use processor  104 - 1  and processor  104 - 2 . 
         [0047]    Transmitter  105 - 1  is hardware that transmits the results of each task execution from processor  104 - 1 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which transmitter  105 - 1  is software or a combination of software and hardware. 
         [0048]    Transmitter  105 - 2  is hardware that transmits the results of each task execution from processor  104 - 2 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which transmitter  105 - 2  is software or a combination of software and hardware. It will be clear to those having ordinary skill in the art, after reading this disclosure, how to make and use transmitter  105 - 1  and transmitter  105 - 2 . 
         [0049]      FIG. 2  depicts a flowchart of the salient steps of data-processing system  100  according to the illustrative embodiments of the present invention. 
         [0050]    At step  201 , a temporal succession of tasks, T 1  . . . T i , is received and analyzed by scheduler  102 . As a result of the analysis, scheduler  102  schedules each task for execution at processor  104 - 1  or  104 - 2  and places the task into corresponding queue  103 - 1  or  103 - 2 , respectively. 
         [0051]    In accordance with the illustrative embodiments, each task T i  arrives at receiver  101  with accompanying parameters. Additional parameters are established upon arrival. Accordingly, each task is accompanied by an attribute of “time-sensitive” or “non-time-sensitive” and by a priority; additionally, the time that the task enters its respective queue is recorded and becomes a parameter of the task. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments that use only some of the parameters described herein, or that use other parameters than those described herein. 
         [0052]    As noted, some tasks are time-sensitive in accordance with the function they perform in data-processing system  100 . For example, speech-processing tasks are time-sensitive tasks. Tasks generally known in the art as “soft real-time” tasks are time-sensitive tasks. Tasks that perform general computing typically are non-time-sensitive tasks. Whether a task is time-sensitive or non-time-sensitive is material to the present invention, as described in more detail below. 
         [0053]    In some embodiments of the present invention, whether a task is treated as a time-sensitive task depends on whether it arrives from a time-sensitive or a non-time-sensitive “domain.” For purposes of this specification, a “domain” is defined as software that is (i) an operating system or (ii) an application using the operating system, and that comprises tasks to be executed by a processor. Because multiple domains can co-exist in data-processing system  100  and each domain requires execution of its tasks on processor  104 - 1  or  104 - 2 , whether a domain is time-sensitive affects the treatment of its constituent tasks. Thus, any task from a time-sensitive domain would be characterized as a time-sensitive task and treated accordingly by scheduler  102 . A voice-processing application is an example of a time-sensitive domain, and therefore any task from the voice-processing application would be treated as a time-sensitive task by scheduler  102 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention that use domains. 
         [0054]    In prior art hypervisors, tasks have a priority attribute that governs at least in part where the task is placed within a queue. Typically, prior art credit schedulers queue an incoming task or some other scheduler-related event at the end of the list of tasks that have the same priority, because credit scheduler queues have a region in the queue for each priority level. The priority levels and their relative meanings are specific to the scheduler platform being used by the implementers. For the XEN credit scheduler, for example, tasks have “boost priority,” “under priority,” “over priority,” or “idle priority” in decreasing priority value. Thus, a task with “boost priority” is of a higher priority than a task with “under priority.” Each of these priority levels has its own region within the queue that the XEN credit scheduler manages. In the preferred embodiments of the present invention, task priority levels are the same as in the XEN credit scheduler. Queuing of incoming tasks to the appropriate priority region of the queue is generally the same in the preferred embodiments as in the XEN credit scheduler, except as disclosed otherwise herein. 
         [0055]    In accordance with some illustrative embodiments, when a task enters a queue, the time that it enters the queue is recorded and becomes associated with the task. Thus, the time that a task entered its respective queue becomes a parameter of the task. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which the queue entry time is not recorded and does not become a parameter associated with a task. 
         [0056]    In accordance with some illustrative embodiments of the present invention, a “runtime parameter,” p i , is associated with each task T i , and represents an expected time of execution of the respective task in the upcoming execution cycle. In some illustrative embodiments of the present invention, the runtime parameter is the execution time of the task in the immediately preceding execution cycle. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which the runtime parameter is based on an average of execution times from a plurality of previous execution cycles. It will be further clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which the runtime parameter is based on other considerations. 
         [0057]    Step  201  is described in greater detail below and in the accompanying figures. 
         [0058]    At step  202 , scheduler  102  analyzes queues  103 - 1  and  103 - 2  and processors  104 - 1  and  104 - 2 . Based on criteria, scheduler  102  may re-schedule a task that is presently at the head of either queue  103 - 1  or  103 - 2  to be executed before another task that is at the head of the other queue. As noted, each processor in the illustrative embodiments executes the task at the head of the processor&#39;s corresponding queue, so that when scheduler  102  re-schedules a task from a first queue to a second queue, that task will be executed sooner than another task that is presently at the head of the first queue. This process is colloquially referred to as “stealing.” It should be noted that a waiting task at the head of a queue can still have a long waiting time, because the corresponding processor must first finish its current task before executing the waiting task. Therefore, stealing (or re-scheduling) the waiting task to be executed on another processor can speed up the task&#39;s overall performance. Step  202  and the criteria that govern re-scheduling of tasks are described in greater detail below and in the accompanying figures. 
         [0059]    It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use the steps associated with data-processing system  100 . It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which steps  201  and  202  and their constituent steps are executed in a different sequence, are sub-divided into other tasks, are selectively skipped, are executed on different timing parameters, or are grouped differently; or are executed by a different component of data-processing system  100 ; or use different data structures than described herein. 
         [0060]      FIG. 3A  depicts a flowchart of the salient steps associated with the performance of step  201  according to a first illustrative embodiment of the present invention. As noted, in general, the methods according to the illustrative embodiments are triggered when a scheduler-related event happens in data-processing system  100 , i.e., an event occurs that requires scheduler  102  to act. 
         [0061]    At step  301 , upon the occurrence of a scheduler-related event, if receiver  101  receives at least one task in a temporal sequence, it triggers scheduler  102  to analyze the received tasks. The scheduler-related event in accordance with the first illustrative embodiment is any of: the arrival of a new task, the occurrence of an input/output (“I/O”) event for an existing task, a task relinquishing a processor, a processor becoming idle and available to execute another task, or a timer trigger. In the first illustrative embodiment, a default 30-millisecond timer acts as a trigger, but it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make alternative embodiments with different timers. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use step  301 . 
         [0062]    At step  302 , scheduler  102  schedules each received task to the same processor that previously executed it in the preceding execution cycle. The task is queued to the queue that corresponds to the chosen processor. This policy reduces cache thrashing by permitting a processor to re-use a cache for a task that it previously executed. This policy is sometimes referred to herein as “cache affinity.” In the case of a new task&#39;s arrival, i.e., a task not previously executed or not executed in the previous execution cycle, scheduler  102  schedules the task to an appropriate processor, which is processor  104 - 1  in the illustrative embodiment. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which tasks are scheduled based on other considerations or other cache policies. 
         [0063]      FIG. 3B  depicts a flowchart of the salient steps associated with the performance of step  201  according to a second illustrative embodiment. As noted, in general, the methods according to the illustrative embodiments are triggered when a scheduler-related event happens in data-processing system  100 , i.e., an event requiring scheduler  102  to act. 
         [0064]    Step  311  represents a timer that triggers scheduler  102  to act in accordance with the second illustrative embodiment, and the timer is referred to herein as “interval X.” Interval X represents the frequency of execution of some of the constituent steps in step  201 —as disclosed in more detail below and in the accompanying figures. Interval X in the illustrative embodiment is one second, but it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which interval X is of a different duration, or in which interval X varies based on other considerations of the implementers. It should be noted that interval X is independent of the duration of the execution cycle referred to elsewhere in this disclosure. 
         [0065]    At step  311 , if interval X has not expired, default scheduling control flows to step  314 . When interval X expires, control flows to step  312 . 
         [0066]    At step  312 , upon the trigger of interval X, scheduler  102  acts with respect to the tasks in data-processing system  100 , by analyzing the waiting tasks in all queues. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use step  312 . 
         [0067]    At step  313 , scheduler  102  determines whether each task is a time-sensitive task or a non-time-sensitive task. For time-sensitive tasks, control flows to step  315 . For non-time-sensitive tasks, control flows to step  314 . 
         [0068]    Step  314  is analogous to step  302  described above. At step  314 , a task is scheduled to the same processor that executed this task in the previous execution cycle. In the case of a new task&#39;s arrival, i.e., a task not previously executed or not executed in the previous execution cycle, scheduler  102  schedules the task to an appropriate processor, which is processor  104 - 1  in the illustrative embodiment. The task is queued to the queue that corresponds to the chosen processor. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which tasks are scheduled differently. 
         [0069]    At step  315 , scheduler  102  schedules each time-sensitive task to one of the processors in data-processing system  100  and places the task in the queue that corresponds to that processor, based on criteria. Step  315  is described in more detail below and in the accompanying figures. 
         [0070]      FIG. 4  depicts a flowchart of the salient steps associated with the performance of step  315 . 
         [0071]    At step  401 , for each of the time-sensitive tasks under analysis by scheduler  102 , T 1  . . . T i , scheduler  102  determines the runtime parameter p i  that is associated with task T i . In the illustrative embodiment, p i  accompanies each task when it arrives, but it will be clear to those skilled in the art, after reading the present disclosure, how to make and use alternative embodiments in another manner of the implementers&#39; choosing. For example, p i  can be calculated upon the arrival of each task, or p i  can be re-calculated based on other considerations. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to implement step  401 . 
         [0072]    At step  402 , scheduler  102  bin-packs the time-sensitive tasks in data-processing system  100 . Bin-packing techniques are well-known in the art. See, e.g., Joseph Malkevitch, Bin Packing and Machine Scheduling, Feature Column Archive, American Mathematical Society, https://www.ams.org/samplings/feature-column/fcarc-packings1 (last visited Apr. 13, 2010). In regards to the particular problem of multi-processor scheduling, one way of phrasing the multi-processor scheduling problem in terms of bin-packing concepts is: “‘Given a set J of jobs where job j i  has length l i  and a number of processors m i , what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?’” Wikipedia online, Multiprocessor Scheduling, http://en.wikipedia.org/wiki/Multiprocessor scheduling (last visited Apr. 15, 2010). 
         [0073]    In the illustrative embodiment, the bin-packing is directed at minimizing the difference in expected utilization among processors for executing the time-sensitive tasks in data-processing system  100 , i.e., load-balancing the processing of time-sensitive tasks. Thus, the bin-packing in accordance with the illustrative embodiment aims to equalize the percentage of time in the next execution cycle that each processor in data-processing system  100  is to spend executing time-sensitive tasks. For purposes of this disclosure, the percentage of time in the next execution cycle that a processor, j, is to spend executing time-sensitive tasks in an execution cycle is defined as “μ j ” wherein j is an integer. 
         [0074]    In accordance with the illustrative embodiment, data-processing system  100  comprises two processors: processor  104 - 1  and processor  104 - 2 ; therefore the bin-packing in step  402  is directed at creating at least one bin-pack for each of the two processors. Thus, in some embodiments, μ 1  for processor  104 - 1  is the sum of the runtime parameters of the tasks in a first bin-pack, taken as a percentage of the total processing capacity of processor  104 - 1 . Likewise, in some embodiments, μ 2  for processor  104 - 2  is the sum of the runtime parameters of the tasks in a second bin-pack, taken as a percentage of the total processing capacity of processor  104 - 2 . 
         [0075]    It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which the bin-packing is directed at other considerations, such as minimizing the number of processors in data-processing system  100  that are to be used for processing time-sensitive tasks, or minimizing the expected execution time of the tasks in each bin-pack, or a combination of considerations, or other considerations. 
         [0076]    Although the illustrative embodiment uses bin-packing to group together time-sensitive tasks, it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which tasks are grouped together other than by bin-packing, or are not grouped together at all and are treated instead one by one in accordance with the disclosures herein. 
         [0077]    At step  403 , a first bin-pack that was created at step  402  is scheduled to be executed by processor  104 - 1 . The tasks in the first bin-pack are placed into the corresponding queue, i.e., queue  103 - 1 . 
         [0078]    At step  404 , a second bin-pack that was created at step  402  is scheduled to be executed by processor  104 - 2 . The tasks in the second bin-pack are placed into the corresponding queue, i.e., queue  103 - 2 . 
         [0079]    Although the illustrative embodiment does not bin-pack the non-time-sensitive tasks (see step  314 ), it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which non-time-sensitive tasks are bin-packed. It will be further clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which non-time-sensitive tasks are grouped other than by bin-packing. 
         [0080]    It should be noted that the priority attribute of a task may govern where to place a task or a bin-pack into a queue. In the illustrative embodiment, the priority of the task is independent of the execution of step  315  as described herein. However, it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments in which the priority of a task is a factor in the bin-packing described herein. 
         [0081]    It should be further noted that, as described below in regards to step  202 , some of the tasks that are scheduled to be executed by a processor at step  201  may be re-scheduled to another processor at step  202 . 
         [0082]      FIG. 5  depicts a flowchart of the salient steps associated with the performance of step  202 . 
         [0083]    As noted, step  202  governs scheduler  102 ′s analysis of tasks at the head of each queue to determine whether to re-schedule a task to another processor. By re-scheduling, scheduler  102  in effect places a task at the head of another queue. In the illustrative embodiments, the task at the head of a queue is the task that is next to be executed by the corresponding processor. It will be clear to those having ordinary skill in the art, after reading the present disclosure, that a task at the head of a queue may be part of a bin-pack that was created in step  402 ; whether a task is part of a bin-pack is independent of the execution of step  202 . 
         [0084]    At step  501 , scheduler  102  compares the task at the head of queue  103 - 1  and the task at the head of queue  103 - 2 . The order of arrival of a task is not relevant, in this context, to whether it is at the head of a queue. Step  501  is described in more detail below and in the accompanying figures. 
         [0085]    At step  502 , scheduler  102  determines whether to re-schedule the task at the head of queue  103 - 1  to run on processor  104 - 2  ahead of the task at the head of queue  103 - 2 . Step  502  is described in more detail below and in the accompanying figures. 
         [0086]    At step  503 , scheduler  102  determines whether to re-schedule the task at the head of queue  103 - 2  to run on processor  104 - 1  ahead of the task at the head of queue  103 - 1 . Step  503  is described in more detail below and in the accompanying figures. 
         [0087]    At step  504 , after analysis and re-scheduling, if any, at steps  502  and  503 , each processor executes the task at the head of its corresponding queue. Thus, processor  104 - 1  executes the task at the head of queue  103 - 1  and processor  104 - 2  executes the task at the head of queue  103 - 2 . 
         [0088]    It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which re-scheduling does not require a re-queuing of a task from one queue to another. For example, re-scheduling in accordance with step  202  may result in immediate execution of the re-scheduled task by the chosen processor. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments of the present invention in which data structures other than queues are used for the scheduling and re-scheduling of tasks to be executed on a chosen processor. For example, a single pointer array may be used to manage all the tasks in data-processing system  100  without using a plurality of queues. 
         [0089]      FIG. 6  depicts a flowchart of the salient steps associated with the performance of step  501 . 
         [0090]    At step  601 , for each task that it is analyzing, scheduler  102  determines whether the task is a time-sensitive task or a non-time-sensitive task. It will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use step  601 . 
         [0091]    At step  602 , for each task, scheduler  102  determines the priority of the task in a manner well-known in the art. As noted, the relative priorities of tasks depend on the hypervisor platform that is used by the implementers. 
         [0092]    At step  603 , for each task, scheduler  102  determines the time that the task entered its respective queue in a manner well-known in the art. 
         [0093]      FIG. 7A  depicts a flowchart of the salient steps associated with the performance of step  502  according to the first illustrative embodiment of the present invention. 
         [0094]    Step  701  is depicted for the convenience of the reader of this disclosure, and it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments that do not comprise step  701 . In step  701 , the task at the head of queue  103 - 1  is defined as T- 1 , and the task at the head of queue  103 - 2  is defined as T- 2 . 
         [0095]    At step  702 , scheduler  102  re-schedules T- 2  by scheduling T- 2  to be executed on processor  104 - 1  ahead of T- 1  when: (i) T- 1  and T- 2  are of equal priority, (ii) T- 1  is a non-time-sensitive task, and (iii) T- 2  is a time-sensitive task. 
         [0096]    At step  703 , scheduler  102  re-schedules T- 2  by scheduling T- 2  to be executed on processor  104 - 1  ahead of T- 1  when: (i) T- 1  and T- 2  are of equal priority, (ii) T- 1  and T- 2  are non-time-sensitive tasks, and (iii) T- 2  entered queue  103 - 2  before T- 1  entered queue  103 - 1 , i.e., T- 2  has been queued longer than T- 1 . 
         [0097]    At step  704 , scheduler  102  re-schedules T- 2  by scheduling T- 2  to be executed on processor  104 - 1  ahead of T- 1  when: (i) T- 2  is of higher priority than T- 1 , and (ii) T- 1  is a non-time-sensitive task. 
         [0098]    At step  705 , absent the conditions set forth above, scheduler  102  does not re-schedule T- 2  and instead leaves T- 1  at the head of queue  103 - 1  and leaves T- 2  at the head of queue  103 - 2 . 
         [0099]      FIG. 7B  depicts a flowchart of the salient steps associated with the performance of step  502  according to the second illustrative embodiment. 
         [0100]    Step  711  is depicted for the convenience of the reader of this disclosure, and it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments that do not comprise step  711 . In step  711 , the task at the head of queue  103 - 1  is defined as T- 1 , and the task at the head of queue  103 - 2  is defined as T- 2 . 
         [0101]    At step  712 , scheduler  102  re-schedules T- 2  by scheduling T- 2  to be executed on processor  104 - 1  ahead of T- 1  when: (i) T- 1  and T- 2  are non-time-sensitive tasks, (ii) T- 1  and T- 2  are of equal priority, and (iii) T- 2  entered queue  103 - 2  before T- 1  entered queue  103 - 1 , i.e., T- 2  has been queued longer than T- 1 . 
         [0102]    At step  713 , scheduler  102  re-schedules T- 2  by scheduling T- 2  to be executed on processor  104 - 1  ahead of T- 1  when: (i) T- 1  and T- 2  are non-time-sensitive tasks, and (ii) T- 2  is of higher priority than T- 1 . 
         [0103]    At step  714 , absent the conditions set forth above, scheduler  102  does not re-schedule T- 2  and instead leaves T- 1  at the head of queue  103 - 1  and leaves T- 2  at the head of queue  103 - 2 . 
         [0104]      FIG. 8A  depicts a flowchart of the salient steps associated with the performance of step  503  according to the first illustrative embodiment. 
         [0105]    Step  801  is depicted for the convenience of the reader of this disclosure, and it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments that do not comprise step  801 . In step  801 , the task at the head of queue  103 - 1  is defined as T- 1 , and the task at the head of queue  103 - 2  is defined as T- 2 . 
         [0106]    At step  802 , scheduler  102  re-schedules T- 1  by scheduling T- 1  to be executed on processor  104 - 2  ahead of T- 2  when: (i) T- 1  and T- 2  are of equal priority, (ii) T- 2  is a non-time-sensitive task, and (iii) T- 1  is a time-sensitive task. 
         [0107]    At step  803 , scheduler  102  re-schedules T- 1  by scheduling T- 1  to be executed on processor  104 - 2  ahead of T- 2  when: (i) T- 1  and T- 2  are of equal priority, (ii) T- 1  and T- 2  are non-time-sensitive tasks, and (iii) T- 1  entered queue  103 - 1  before T- 2  entered queue  103 - 2 , i.e., T- 1  has been queued longer than T- 2 . 
         [0108]    At step  804 , scheduler  102  re-schedules T- 1  by scheduling T- 1  to be executed on processor  104 - 2  ahead of T- 2  when: (i) T- 1  is of higher priority than T- 2 , and (ii) T- 2  is a non-time-sensitive task. 
         [0109]    At step  805 , absent the conditions set forth above, scheduler  102  does not re-schedule T- 1  and instead leaves T- 1  at the head of queue  103 - 1  and leaves T- 2  at the head of queue  103 - 2 . 
         [0110]      FIG. 8B  depicts a flowchart of the salient steps associated with the performance of step  503  according to the second illustrative embodiment. 
         [0111]    Step  811  is depicted for the convenience of the reader of this disclosure, and it will be clear to those having ordinary skill in the art, after reading the present disclosure, how to make and use alternative embodiments that do not comprise step  811 . In step  811 , the task at the head of queue  103 - 1  is defined as T- 1 , and the task at the head of queue  103 - 2  is defined as T- 2 . 
         [0112]    At step  812 , scheduler  102  re-schedules T- 1  by scheduling T- 1  to be executed on processor  104 - 2  ahead of T- 2  when: (i) T- 1  and T- 2  are non-time-sensitive tasks, (ii) T- 1  and T- 2  are of equal priority, and (iii) T- 1  entered queue  103 - 1  before T- 2  entered queue  103 - 2 , i.e., T- 1  has been queued longer than T- 2 . 
         [0113]    At step  813 , scheduler  102  re-schedules T- 1  by scheduling T- 1  to be executed on processor  104 - 2  ahead of T- 2  when: (i) T- 1  and T- 2  are non-time-sensitive tasks, and (ii) T- 1  is of higher priority than T- 2 . 
         [0114]    At step  814 , absent the conditions set forth above, scheduler  102  does not re-schedule T- 1  and instead leaves T- 1  at the head of queue  103 - 1  and leaves T- 2  at the head of queue  103 - 2 . 
         [0115]    It is to be understood that the disclosure teaches just two examples of the illustrative embodiments and that many variations of the invention can easily be devised by those skilled in the art after reading this disclosure and that the scope of the present invention is to be determined by the following claims.