Method and apparatus for efficient scheduling in a multiprocessor system

• US 5,287,508 A
• Filed: 04/07/1992
• Issued: 02/15/1994
• Est. Priority Date: 04/07/1992
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hejna, Donald J. Jr., Medoff, Barry P.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/864,681
• Time in Patent Office: 679 Days
• Field of Search: 364/DIG. 1 MS File, 395/650, 395/200
• US Class Current: 718/102
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

In the present invention a predetermined number of bits are added to each entry in the process table. These bits are used to indicate the warmth of the cache with respect to the particular schedulable unit such as a process or thread of a process. The scheduler will then review, not only the priority of the schedulable unit, but the warmth of the cache in order to determine the schedulable unit to be scheduled next with respect to a particular processor. For example, these cache warmth bits may be used to identify the processor the schedulable unit previously executed on such that the scheduler will only schedule the schedulable unit with the processor previously executed on in order to take advantage of the schedulable unit data located in the the cache associated with the processor. The system may be extended to provide more sophisticated models for determining cache warmth and the scheduling of processes and process threads.

Claims

1. In a computer system comprising multiple processors and at least one resource associated with, and coupled to, each processor, each processor executing in the context of a schedulable unit for a time slice before switching to execute in the context of another schedulable unit, an apparatus for efficiently scheduling schedulable units to be executed on the processors, said apparatus comprising:

a process table comprising resource warmth information regarding each schedulable unit, each processor being identified by a processor ID and, if said schedulable unit has previously executed in a processor, said resource warmth information comprising information indicating the processor ID of the processor on which the schedulable unit was previously executed;

a process scheduler, said process scheduler coupled to said process table and to each said processor, said process scheduler comprising a comparator to compare the processor ID of a schedulable unit to be scheduled with the corresponding processor ID stored in the process table, such that, if the schedulable unit has executed previously, the schedulable unit is scheduled with the corresponding processor the ID of which matches the processor ID stored in the process table.

2. The apparatus as set forth in claim 1, wherein said resource is a cache memory and said resource warmth information associated with a schedulable unit identifies the number of cache misses that have occurred on the cache associated with the identified processor, said process scheduler utilizing resource warmth information to determine the processor upon which the schedulable unit is to be scheduled by scheduling the schedulable unit to be scheduled with the processor if the number of cache misses does not exceed a second predetermined number.

3. The apparatus as set forth in claim 2, wherein the number of cache misses which have occurred include cache misses due to data in the cache associated with another schedulable unit which cause a line of data in the cache to be replaced with data from another schedulable unit.

4. The apparatus as set forth in claim 2, wherein the cache is divided into a plurality of regions, each region having separate cache miss information, each region utilized by a different group of schedulable units, whereby the effect of extensive use of the cache by a single schedulable unit is minimized.

5. The apparatus as set forth in claim 2, wherein the resource warmth information for a schedulable unit is used to calculate a resource warmth value for the schedulable unit, said apparatus further comprising a total resource warmth value corresponding to the sum of resource warmth values for the schedulable units accessing a resource, wherein when the resource warmth value for a schedulable unit increases, the resource warmth values for other schedulable units accessing the resource decrease in proportion to their respective resource warmth values such that the total resource warmth value remains constant and the resource warmth values more accurately reflect cache usage by the schedulable units.

6. The apparatus as set forth in claim 3, wherein the resource associated with a processor comprises multiple levels of caches and the information indicative of cache warmth comprises information for each cache.

7. The apparatus as set forth in claim 1, wherein said resource warmth information further comprises information to identify the number of time slices since the schedulable unit was last executed on the processor and said schedulable unit is scheduled with the processor if the number of timeslices does not exceed a first predetermined number.

8. The apparatus as set forth in claim 1, wherein said resource comprises a virtual memory and said resource warmth information further comprises information to identify the number of page-faults that have occurred in the virtual memory associated with the identified processor, said process scheduler utilizing that information to determine the processor on which the schedulable unit is to be scheduled by scheduling the schedulable unit to be scheduled with the processor if the number of page-faults does not exceed a third predetermined number.

9. The apparatus as set forth in claim 1, wherein the schedulable unit is a process.

10. The apparatus as set forth in claim 1, wherein the schedulable unit is a thread of a process.

11. In a computer system comprising multiple processors and at least one cache memory associated with, and coupled to, each processor, each processor executing in the context of a schedulable unit for a time slice before switching to execute in the context of another schedulable unit, an apparatus for efficiently scheduling schedulable units to be executed on the processors, said apparatus comprising:

a process table comprising cache warmth information regarding each schedulable unit, each processor being identified by a processor ID and, if said schedulable unit has previously executed in a processor, said cache warmth information comprising information indicating the processor ID of the processor on which the schedulable unit was previously executed;

a process scheduler, said process scheduler coupled to said process table and to each said processor, said process scheduler comprising a comparator to compare the processor ID of a schedulable unit to be scheduled with the corresponding processor ID stored in the process table, such that, if the schedulable unit has executed previously, the schedulable unit is scheduled with the corresponding processor the ID of which matches the processor ID stored in the process table.

12. The apparatus as set forth in claim 11, wherein the schedulable unit is a process.

13. The apparatus as set forth in claim 11, wherein the schedulable unit is a thread of a process.

14. The apparatus as set forth in claim 11, wherein said cache warmth information further comprises information to identify the number of time slices since the schedulable unit was last executed on the processor and said schedulable unit is scheduled with the processor if the number of timeslices does not exceed a first predetermined number.

15. The apparatus as set forth in claim 11, wherein said cache warmth information associated with a schedulable unit identifies the number of cache misses that have occurred on the cache associated with the identified processor, said process scheduler utilizing cache warmth information to determine the processor upon which the schedulable unit is to be scheduled by scheduling the schedulable unit to be scheduled with the processor if the number of cache misses does not exceed a second predetermined number.

16. In a computer system comprising multiple processors and at least one cache memory associated with each processor, each processor executing in the context of a schedulable unit for a time slice before switching to execute in the context of another schedulable unit, a method for efficiently scheduling schedulable units to be executed on the processors, said method comprising the steps of:

providing a process table comprising information regarding each schedulable unit, said process table comprising information indicative of cache warmth, said cache warmth information including information indicative of the processor upon which the schedulable unit was previously executed if the schedulable unit was previously executed;

maintaining in the process table the cache warmth information regarding each schedulable unit;

scheduling a schedulable unit to a processor according to the cache warmth such that if a schedulable unit to be scheduled was previously executed, the schedulable unit to be scheduled is scheduled on the processor upon which schedulable unit to be scheduled was previously executed.

17. The method as set forth in claim 16, wherein said cache warmth information identifies the number of time slices since the schedulable unit was last executed on the processor and said schedulable unit is scheduled with the processor if the number of timeslices does not exceed a first predetermined number.

18. The method as set forth in claim 16, wherein said cache warmth information identifies the number of cache misses that have occurred on the cache associated with the identified processor, said method comprising steps to utilize that information to determine the processor upon which the schedulable unit will subsequently execute by scheduling the schedulable unit to be scheduled with the processor if the number of cache misses does not exceed a second predetermined number.

19. The method as set forth in claim 16, wherein each processor is identified by a processor ID and said process table comprises information indicating the processor ID of the processor upon which the schedulable unit was previously executed, said step of scheduling comprising the steps of comparing the processor ID with the processor ID stored in the process table, whereby the schedulable unit is scheduled with the processor having a processor ID which matches the processor ID stored in the process table.

20. The method as set forth in claim 16, wherein the schedulable unit is a process.

21. The method as set forth in claim 16, wherein the schedulable unit is a thread of a process.