US5287508A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for efficient scheduling in a multiprocessor system
Assignee: Sun Microsystems Inc
•
Filing: 1992-04-07
•
Granted: 1994-02-15
•
Expires: 2012-04-07
Abstract
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.
Inventors
- 👤 Donald J. Hejna, Jr.
- 👤 Barry P. Medoff
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 01:52
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5027; G06F9/5033; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864; G06F12/0893; G06F12/0895
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
186 words
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.
Claim 2
Dependent Claim
186 words
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.
Claim 3
Dependent Claim
86 words
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.
Claim 4
Dependent Claim
49 words
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.
Claim 5
Dependent Claim
51 words
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.
Claim 6
Dependent Claim
107 words
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.
Claim 7
Dependent Claim
32 words
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.
Claim 8
Dependent Claim
54 words
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.
Claim 9
Dependent Claim
83 words
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.
Claim 10
Dependent Claim
15 words
The apparatus as set forth in claim 1, wherein the schedulable unit is a process.
Claim 11
Dependent Claim
18 words
The apparatus as set forth in claim 1, wherein the schedulable unit is a thread of a process.
Claim 12
Dependent Claim
187 words
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.
Claim 13
Dependent Claim
187 words
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.
Claim 14
Dependent Claim
15 words
The apparatus as set forth in claim 11, wherein the schedulable unit is a process.
Claim 15
Dependent Claim
18 words
The apparatus as set forth in claim 11, wherein the schedulable unit is a thread of a process.
Claim 16
Dependent Claim
54 words
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.
Claim 17
Dependent Claim
79 words
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.
Claim 18
Dependent Claim
163 words
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.
Claim 19
Dependent Claim
163 words
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.
Claim 20
Dependent Claim
50 words
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.
Claim 21
Dependent Claim
74 words
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.
Claim 22
Dependent Claim
82 words
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.
Claim 23
Dependent Claim
15 words
The method as set forth in claim 16, wherein the schedulable unit is a process.
Claim 24
Dependent Claim
18 words
The method as set forth in claim 16, wherein the schedulable unit is a thread of a process.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-02-14 | 1997-08-16 | 1998-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-14 | 2001-08-16 | 2002-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-14 | 2005-08-16 | 2006-02-15 | $7700.00 | Window Closed / Lapsed |