# US 12,118,384 B2 · Scheduling of threads for clusters of processors > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,118,384 B2 - Document ID: US12118384B2 - Status: Granted - Kind: B2 - Application number: 17/452,872 - Filed: 2021-10-29 - Published: 2023-05-04 - Granted: 2024-10-15 - Earliest claimed: 2021-10-29 - Assignees: BlackBerry Limited - Applicants: BlackBerry Limited - Inventors: Elad Lahav - Web page: https://patentgrep.com/patent/US12118384B2 ## CPC - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5061: {Partitioning or combining of resources} - G06F 2209/505: Clust - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In some examples, a system includes a plurality of processors and a kernel scheduler. The kernel scheduler associates 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. For each corresponding cluster of the collection of clusters, the kernel scheduler maintains a data structure associated with a ready queue of the kernel scheduler, the data structure comprising elements representing thread priorities, wherein an element of the data structure is associated with an ordered list of threads in the ready queue. ## Claims ### Claim 1 A system comprising: a plurality of processors; and a kernel scheduler to: associate 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; 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 schedule the 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. ### Claim 2 (depends on 1) The system of claim 1, wherein the first processor is associated with a first collection of clusters, the first collection of clusters comprising the first cluster that includes all processors of the plurality of processors, the second cluster that includes only the first processor, and a third cluster that includes processors having a first characteristic. ### Claim 3 (depends on 2) The system of claim 2, wherein a second processor is associated with a second collection of clusters, the second collection of clusters comprising the first cluster that includes all processors of the plurality of processors, a fourth cluster that includes only the second processor, and a fifth cluster that includes processors having a second characteristic different from the first characteristic. ### Claim 4 (depends on 1) The system of claim 1, wherein the kernel scheduler is to: schedule the thread for execution on the first processor by traversing the data structures of the plurality of ready queues to select the thread from threads represented in the data structures of the plurality of ready queues. ### Claim 5 (depends on 1) The system of claim 1, wherein the elements of each data structure of the first data structure and the second data structure are arranged in an order of thread priorities, and wherein the kernel scheduler is to identify, according to the order of thread priorities of the elements in each data structure of the first data structure and the second data structure, the thread to schedule for execution on the first processor. ### Claim 6 (depends on 5) The system of claim 5, wherein each given thread in the ordered list of threads is associated with a timestamp corresponding to a time the given thread was placed in the ordered list of threads, and wherein the kernel scheduler is to identify the thread for execution on the first processor further based on the timestamps. ### Claim 7 (depends on 6) The system of claim 6, wherein the threads in the ordered list of threads are arranged in order according to when the threads were placed in the ordered list of threads. ### Claim 8 (depends on 7) The system of claim 7, wherein the kernel scheduler is to: in response to a preemption of a thread scheduled for execution from the ordered list of threads, assign a specified timestamp to the preempted thread to maintain the preempted thread at a beginning of the ordered list of threads. ### Claim 9 (depends on 6) The system of claim 6, wherein an element of the first data structure has a first thread priority and is associated with a first ordered list of threads, and an element of the second data structure also has the first thread priority and is associated with a second ordered list of threads, and wherein the kernel scheduler is to: use timestamps associated with one or more threads in the first ordered list of threads and one or more threads in the second ordered list of threads to decide which thread from the first ordered list of threads or the second ordered list of threads to schedule for execution on the first processor. ### Claim 10 (depends on 1) The system of claim 1, wherein the kernel scheduler is to schedule the thread for execution on the first processor by further accessing a third data structure of a third ready queue, the third data structure including an element representing threads ready for execution on the first processor. ### Claim 11 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. ### Claim 12 (depends on 11) The method of claim 11, wherein the first processor is associated with a first collection of clusters, the first collection of clusters comprising the first cluster that includes all processors of the plurality of processors, the second cluster that includes only the first processor, and a third cluster that includes processors having a first characteristic, and wherein a second processor is associated with a second collection of clusters, the second collection of clusters comprising the first cluster that includes all processors of the plurality of processors, a fourth cluster that includes only the second processor, and a fifth cluster that includes processors having a second characteristic different from the first characteristic. ### Claim 13 (depends on 11) The method of claim 11, wherein the elements of each data structure of the first data structure and the second data structure are arranged in an order of thread priorities, and wherein the scheduling executive identifies, according to the order of thread priorities of the elements in each data structure, the given thread to schedule for execution on the first processor. ### Claim 14 (depends on 13) The method of claim 13, wherein each thread in the ordered list of threads is associated with a timestamp corresponding to a time the thread was placed in the ordered list of threads, and wherein the scheduling executive identifies the given thread to schedule for execution further based on the timestamps. ### Claim 15 (depends on 14) The method of claim 14, wherein an element of the first data structure has a first thread priority and is associated with a first ordered list of thread s, and an element of the second data structure also has the first thread priority and is associated with a second ordered list of threads, the method comprising: using, by the scheduling executive, timestamps associated with one or more threads in the first ordered list of threads and one or more threads in the second ordered list of threads to decide which thread from the first ordered list of threads or the second ordered list of threads to schedule for execution on the first processor. ### Claim 16 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. ### Claim 17 (depends on 16) The non-transitory machine-readable storage medium of claim 16, wherein the instructions upon execution cause the system to: as part of selecting the given thread for execution on the first processor, access a first mask associated with the first cluster, and identify a first element of the first data structure containing a non-empty linked list using indicators in the first mask, where a first indicator of the indicators in the first mask set to a first value indicates presence of the non-empty linked list in the first element of the first data structure, and a second indicator of the indicators in the first mask set to a second value indicates an empty second element of the first data structure.