Scheduling of threads for clusters of processors

A method of a system comprising a plurality of processors, comprising:

• associating each respective processor of the plurality of processors with a collection of clusters, wherein each cluster of the collection of clusters represents a respective different subset of the plurality of processors, and the respective processor is a member of each cluster of the collection of clusters;
• maintaining data structures of respective ready queues for corresponding clusters of the collection of clusters, the ready queues comprising a first ready queue including a first data structure associated with a first cluster of the collection of clusters, and a second ready queue including a second data structure associated with a second cluster of the collection of clusters, wherein each respective data structure of the data structures comprises elements representing thread priorities, an element of the respective data structure is associated with an ordered list of threads, and threads ready for execution on a first processor of the plurality of processors are represented in the first data structure of the first ready queue, and in the second data structure of the second ready queue, and wherein each respective cluster of the collection of clusters is further associated with a mask indicating which elements of the data structure for the respective cluster are associated with non-empty ordered lists of threads, where a non-empty ordered list of threads includes one or more threads;
• using the mask to search the data structure for the respective cluster for a thread to schedule, wherein the mask is to produce an index referring to an element of the data structure for the respective cluster, the element referred to by the index associated with the non-empty ordered list of threads;
• and
• scheduling, by a scheduling executive, a given thread for execution on the first processor based on selecting the given thread from data structures of a plurality of ready queues including the first data structure of the first ready queue and the second data structure of the second ready queue, wherein the given thread is selected from threads ready for execution on the first processor that are represented in the data structures of the plurality of ready queues.

A non-transitory machine-readable storage medium comprising instructions that upon execution cause a system to:

• associate each respective processor of a plurality of processors with a collection of clusters, wherein each cluster of the collection of clusters represents a respective different subset of the plurality of processors, and the respective processor is a member of each cluster of the collection of clusters;
• maintain data structures of respective ready queues for corresponding clusters of the collection of clusters, the ready queues comprising a first ready queue including a first data structure associated with a first cluster of the collection of clusters, and a second ready queue including a second data structure associated with a second cluster of the collection of clusters, wherein each respective data structure of the data structures comprises elements representing thread priorities, an element of the respective data structure is associated with an ordered list of threads, and threads ready for execution on a first processor of the plurality of processors are represented in the first data structure of the first ready queue, and in the second data structure of the second ready queue, and wherein each respective cluster of the collection of clusters is further associated with a mask indicating which elements of the data structure for the respective cluster are associated with non-empty ordered lists of threads, where a non-empty ordered list of threads includes one or more threads;
• use the mask to search the data structure for the respective cluster for a thread to schedule, wherein the mask is to produce an index referring to an element of the data structure for the respective cluster, the element referred to by the index associated with the non-empty ordered list of threads;
• and
• select, by a scheduling executive in an operating system (OS) kernel, a given thread for execution on the first processor by accessing data structures of a plurality of ready queues including the first data structure of the first ready queue and the second data structure of the second ready queue, wherein the given thread is selected from threads ready for execution on the first processor that are represented in the data structures of the plurality of ready queues.