# US 2014/0208330 A1 · Method and apparatus for efficient scheduling of multithreaded programs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0208330 A1 - Document ID: US20140208330A1 - Status: Published application - Kind: A1 - Application number: 13/873,640 - Filed: 2013-04-30 - Published: 2014-07-24 - Earliest claimed: 2013-01-22 - Assignees: Oracle International Corporation - Inventors: Kishore Kumar Pusukuri; Eric C. Saxe; Darrin P. Johnson - Web page: https://patentgrep.com/patent/US20140208330A1 ## CPC - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals} - G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores - G06F 2209/483: Multiproc - G06F 2209/485: Resource constraint - G06F 2209/5018: Thread allocation - G06F 2209/508: Monitor - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In general, the invention relates to a non-transitory computer readable medium comprising instructions, which when executed by a processor perform a method. The method includes obtaining lock overhead times for a plurality of threads, generating a set of thread groups, wherein each of the plurality of threads is assigned to one of the plurality of thread groups based on the lock overhead times, allocating at least one core of a multi-core system to each of the plurality of thread groups, and assigning a time-quantum for each of the plurality of thread groups, wherein the time-quantum for each of the plurality of thread groups corresponds to an amount of time that threads in each of the plurality of thread groups can execute on the at least one allocated core. ## Claims ### Claim 1 A non-transitory computer readable medium comprising instructions, which when executed by a processor perform a method, the method comprising: obtaining lock overhead times for a plurality of threads; generating a set of thread groups, wherein each of the plurality of threads is assigned to one of the plurality of thread groups based on the lock overhead times; allocating at least one core of a multi-core system to each of the plurality of thread groups; and assigning a time-quantum for each of the plurality of thread groups, wherein the time-quantum for each of the plurality of thread groups corresponds to an amount of time that threads in each of the plurality of thread groups can execute on the at least one allocated core. ### Claim 2 (depends on 1) The non-transitory computer readable medium of claim 1, the method further comprising: executing the threads in each of the thread groups on the at least one allocated core for the assigned time-quantum. ### Claim 3 (depends on 1) The non-transitory computer readable medium of claim 1, wherein assigning each of the plurality of threads to one of the plurality of thread groups comprises using a k-means algorithm. ### Claim 4 (depends on 1) The non-transitory computer readable medium of claim 1, wherein assigning each of the plurality of threads to one of the plurality of thread groups comprises placing threads with similar lock overhead times in a same thread group. ### Claim 5 (depends on 1) The non-transitory computer readable medium of claim 1, wherein each of the lock overhead times corresponds to a percent of execution time that one of the plurality of threads waits for at least one lock. ### Claim 6 (depends on 1) The non-transitory computer readable medium of claim 1, wherein allocating at least one core of the multi-core system to each of the plurality of thread groups comprises using a processor utilization of threads in the corresponding thread group. ### Claim 7 (depends on 1) The non-transitory computer readable medium of claim 1, wherein allocating the at least one core of the multi-core system to each of the plurality of thread groups comprises using G cores = G util Total util  ( Total cores ) , wherein Gcores is a number of cores allocated to a thread group of the plurality of thread groups, wherein Gutil is a processor utilization for the thread group, wherein Totalutil is a sum of all processor utilizations for the plurality of thread groups, and wherein Totalcores a number of cores in the multi-core system. ### Claim 8 (depends on 7) The non-transitory computer readable medium of claim 7, wherein Gutil is calculated using G util = ∑ T = 1 N  T util , wherein Tutil is a processor utilization for a thread in the thread group, and wherein N is a number of threads in the thread group. ### Claim 9 (depends on 1) The non-transitory computer readable medium of claim 1, wherein assigning the time-quantum for each of the plurality of thread groups comprises using a time-quantum table specifying a time-quantum for each processor utilization range. ### Claim 10 (depends on 1) The non-transitory computer readable medium of claim 1, wherein each of the plurality of threads in one of the plurality of thread groups are assigned a same priority level. ### Claim 11 A system comprising: a plurality of cores; a thread monitor, wherein the thread monitor is configured to perform a method, the method comprising: obtaining lock overhead times for a plurality of threads; a scheduler, wherein the scheduler is configured to perform a method, the method comprising: generating a set of thread groups, wherein each of the plurality of threads is assigned to one of the plurality of thread groups based on the lock overhead times; allocating at least one core of the plurality of cores to each of the plurality of thread groups; and assigning a time-quantum for each of the plurality of thread groups, wherein the time-quantum for each of the plurality of thread groups corresponds to an amount of time that threads in each of the plurality of thread groups can execute on the at least one allocated core. ### Claim 12 (depends on 11) The system of claim 11, wherein the system comprises a per-thread data structure for each of the plurality of threads, wherein the per-thread data structure is configured to store lock overhead times for each of the plurality of threads. ### Claim 13 (depends on 11) The system of claim 11, wherein all threads in one of the plurality of thread groups are set to a same priority level. ### Claim 14 (depends on 11) The system of claim 11, the method further comprising: executing the threads in each of the thread groups on the at least one allocated core for the assigned time-quantum. ### Claim 15 (depends on 11) The system of claim 11, wherein assigning each of the plurality of threads to one of the plurality of thread groups comprises using a k-means algorithm. ### Claim 16 (depends on 11) The system of claim 11, wherein assigning each of the plurality of threads to one of the plurality of thread groups comprises placing threads with similar lock overhead times in a same thread group. ### Claim 17 (depends on 11) The system of claim 11, wherein each of the lock overhead times corresponds to a percent of execution time that one of the plurality of threads waits for at least one lock. ### Claim 18 (depends on 11) The system of claim 11, wherein allocating at least one core of the multi-core system to each of the plurality of thread groups comprises using a processor utilization of threads in the corresponding thread group. ### Claim 19 (depends on 11) The system of claim 11, wherein allocating the at least one core of the multi-core system to each of the plurality of thread groups comprises using G cores = G util Total util  ( Total cores ) , wherein Gcores is a number of cores allocated to a thread group of the plurality of thread groups, wherein Gutil is a processor utilization for the thread group, wherein Totalutil is a sum of all processor utilizations for the plurality of thread groups, and wherein Totalcores a number of cores in the multi-core system. ### Claim 20 (depends on 11) The system of claim 11, wherein assigning the time-quantum for each of the plurality of thread groups comprises using a time-quantum table specifying a time-quantum for each processor utilization range.