Method and system for scheduling threads for execution

Abstract

Techniques for scheduling threads for execution in a data processing system are described herein. According to one embodiment, in response to a request for executing a thread, a scheduler of an operating system of the data processing system accesses a global run queue to identify a global run entry associated with the highest process priority. The global run queue includes multiple global run entries, each corresponding to one of a plurality of process priorities. A group run queue is identified based on the global run entry, where the group run queue includes multiple threads associated with one of the processes. The scheduler dispatches one of the threads that has the highest thread priority amongst the threads in the group run queue to one of the processor cores of the data processing system for execution.

What is claimed is: 
     
         1 . A computer-implemented method, comprising:
 in response to a request for executing a thread, accessing, by a scheduler of an operating system of a data processing system, a global run queue to identify a global run entry associated with the highest process priority, wherein the global run queue includes a plurality of global run entries, each corresponding to one of a plurality of process priorities;   identifying a group run queue based on the global run entry, the group run queue having a plurality of threads associated with one of a plurality of processes; and   dispatching one of the threads that has the highest thread priority amongst the threads in the group run queue to one of a plurality of processor cores of the data processing system for execution.   
     
     
         2 . The method of  claim 1 , wherein each of the global run entries of the global run queue is associated with a list of a plurality of group run queues, each of the group run queues is associated with one of the processes running within the data processing system. 
     
     
         3 . The method of  claim 2 , wherein each of the group run queues includes a list of a plurality of threads associated with a corresponding process, each of the threads being associated with one of a plurality of thread priorities associated with the corresponding process. 
     
     
         4 . The method of  claim 3 , further comprising:
 monitoring processing resource usages amongst all processes being executed by the processor cores of the data processing system; and   modifying priorities of group run queues based on processing resource usages of the corresponding processes, such that one process does not utilize too many process resources that will starve another process.   
     
     
         5 . The method of  claim 4 , wherein modifying priorities of group run queues comprises:
 identifying a first group run queue of a first global run entry that has a processing resource usage greater than a predetermined threshold;   dequeuing the first group run queue from the first global run entry of the global run queue, the first global run entry having a first process priority; and   enqueuing the first group run queue to a second global run entry of the global run queue, without modifying the first group run queue.   
     
     
         6 . The method of  claim 5 , wherein the first process priority is higher than the second process priority. 
     
     
         7 . The method of  claim 1 , wherein each of the processor cores is configured to execute one or more threads of a particular process within a predetermined time slot. 
     
     
         8 . The method of  claim 7 , wherein dispatching one of the threads that has the highest thread priority amongst the threads in the group run queue to one of a plurality of processor cores of the data processing system for execution comprises:
 dispatching a first of the threads of the group run queue to a first of the processor cores for execution;   in response to a signal indicating that the first thread has been suspended, determining whether there is still time remaining within a first time slot associated with the process associated with the group run queue; and   dispatching a second of the threads of the group run queue to the first processor core for execution if there is still time remaining within the first time slot associated with the process.   
     
     
         9 . A non-transitory computer-readable medium having instructions stored therein, which when executed by a computer, cause the computer to perform a method, the method comprising:
 in response to a request for executing a thread, accessing, by a scheduler of an operating system of a data processing system, a global run queue to identify a global run entry associated with the highest process priority, wherein the global run queue includes a plurality of global run entries, each corresponding to one of a plurality of process priorities;   identifying a group run queue based on the global run entry, the group run queue having a plurality of threads associated with one of a plurality of processes; and   dispatching one of the threads that has the highest thread priority amongst the threads in the group run queue to one of a plurality of processor cores of the data processing system for execution.   
     
     
         10 . The non-transitory computer-readable medium of  claim 9 , wherein each of the global run entries of the global run queue is associated with a list of a plurality of group run queues, each of the group run queues is associated with one of the processes running within the data processing system. 
     
     
         11 . The non-transitory computer-readable medium of  claim 10 , wherein each of the group run queues includes a list of a plurality of threads associated with a corresponding process, each of the threads being associated with one of a plurality of thread priorities associated with the corresponding process. 
     
     
         12 . The non-transitory computer-readable medium of  claim 11 , wherein the method further comprises:
 monitoring processing resource usages amongst all processes being executed by the processor cores of the data processing system; and   modifying priorities of group run queues based on processing resource usages of the corresponding processes, such that one process does not utilize too many process resources that will starve another process.   
     
     
         13 . The non-transitory computer-readable medium of  claim 12 , wherein modifying priorities of group run queues comprises:
 identifying a first group run queue of a first global run entry that has a processing resource usage greater than a predetermined threshold;   dequeuing the first group run queue from the first global run entry of the global run queue, the first global run entry having a first process priority; and   enqueuing the first group run queue to a second global run entry of the global run queue, without modifying the first group run queue.   
     
     
         14 . The non-transitory computer-readable medium of  claim 13 , wherein the first process priority is higher than the second process priority. 
     
     
         15 . The non-transitory computer-readable medium of  claim 9 , wherein each of the processor cores is configured to execute one or more threads of a particular process within a predetermined time slot. 
     
     
         16 . The non-transitory computer-readable medium of  claim 15 , wherein dispatching one of the threads that has the highest thread priority amongst the threads in the group run queue to one of a plurality of processor cores of the data processing system for execution comprises:
 dispatching a first of the threads of the group run queue to a first of the processor cores for execution;   in response to a signal indicating that the first thread has been suspended, determining whether there is still time remaining within a first time slot associated with the process associated with the group run queue; and   dispatching a second of the threads of the group run queue to the first processor core for execution if there is still time remaining within the first time slot associated with the process.   
     
     
         17 . A data processing system, comprising:
 a processor having one or more processor cores; and   a memory coupled to the processor for storing instructions, which when executed by the processor, cause the processor to perform operations, the operations including
 in response to a request for executing a thread, accessing, by a scheduler of an operating system executed from the memory, a global run queue to identify a global run entry associated with the highest process priority, wherein the global run queue includes a plurality of global run entries, each corresponding to one of a plurality of process priorities, 
 identifying a group run queue based on the global run entry, the group run queue having a plurality of threads associated with one of a plurality of processes, and 
 dispatching one of the threads that has the highest thread priority amongst the threads in the group run queue to one of a plurality of processor cores of the data processing system for execution. 
   
     
     
         18 . The system of  claim 17 , wherein each of the global run entries of the global run queue is associated with a list of a plurality of group run queues, each of the group run queues is associated with one of the processes running within the data processing system. 
     
     
         19 . The system of  claim 18 , wherein each of the group run queues includes a list of a plurality of threads associated with a corresponding process, each of the threads being associated with one of a plurality of thread priorities associated with the corresponding process. 
     
     
         20 . A computer-implemented method, comprising:
 monitoring processing resource usages of a plurality of processes being executed within a data processing system, each of the processes being associated with one of a plurality of process priorities;   receiving a signal indicating that a process priority of a first of the processes needs to be adjusted due to its processing resource usage;   dequeuing a first group run queue corresponding to the first process from a first list one or more group run queues associated with a first global run entry of a global run queue; and   enququing the first group run queue into a second list of zero or more group run quques associated with a second global run entry of the global run queue without modifying the first group run queue, wherein the global run queue includes a plurality of global run entries, each corresponding to one of the process priorities.   
     
     
         21 . The method of  claim 20 , wherein each of the global run entries is associated with a list of zero or more group run queues, each group run queue being associated with one of the plurality of processes. 
     
     
         22 . The method of  claim 21 , wherein each of the group run queue includes a list of one or more threads that are associated with a process corresponding to the group run queue. 
     
     
         23 . The method of  claim 22 , wherein each of the one or more threads is associated with one of a plurality of thread priorities of the process corresponding to the group run queue.