Cache affinity scheduler

• US 5,185,861 A
• Filed: 08/19/1991
• Issued: 02/09/1993
• Est. Priority Date: 08/19/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: Sequent Computer Systems, Inc. (International Business Machines Corporation)
• Inventors: Valencia, Andrew J.
• Primary Examiner(s): RICHARDSON, ROBERT
• Application Number:
  US07/747,658
• Time in Patent Office: 540 Days
• Field of Search: 364/DIG. 1, 364/243, 364/243.4, 364/243.41, 364/243.42, 364/243.44, 364/228.3, 364/228.1, 364/230, 364/229, 364/238.4, 364/240, 395/425, 395/400, 395/775, 395/275, 395/650, 395/200, 395/164, 395/166, 395/325
• US Class Current: 711/120
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

A computing system (50) includes N number of symmetrical computing engines having N number of cache memories joined by a system bus (12). The computing system includes a global run queue (54), an FPA global run queue, and N number of affinity run queues (58). Each engine is associated with one affinity run queue, which includes multiple slots. When a process first becomes runnable, it is typically attached one of the global run queues. A scheduler allocates engines to processes and schedules the processes to run on the basis of priority and engine availability. An engine typically stops running a process before it is complete. When the process becomes runnable again the scheduler estimates the remaining cache context for the process in the cache of the engine. The scheduler uses the estimated amount of cache context in deciding in which run queue a process is to be enqueued. The process is enqueued to the affinity run queue of the engine when the estimated cache context of the process is sufficiently high, and is enqueued onto the global run queue when the cache context is sufficiently low. The procedure increases computing system performance and reduces bus traffic because processes will run on engines having sufficient cache affinity, but will also run on the best available engine when there is insufficient cache context.

Claims

1. A computing system, comprising:

multiple computing engines that run processes, the multiple computing engines being associated with respective cache memories and respective affinity run queues;

cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes;

enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and

decision means responsive to the estimated amount of cache context for deciding whether to enqueue the particular process to a particular one of the affinity run queues.

2. The system of claim 1 in which the certain ones of the processes that are enqueued to the affinity run queues comprise a first set of processes, and the enqueuing means also enqueues a second set of processes to at least one global run queue, where some of the processes are included in both the first and second sets of processes, and in which the decision means decides whether the particular process is to be enqueued to the particular affinity run queue or to one of the global run queues.

3. The system of claim 2 in which each one of the affinity run queues and each one of the global run queues comprises an array of slots arranged in priority, each slot being capable of queuing a linked list of processes.

4. The system of claim 2 in which one of the affinity run queues and one of the global run queues have substantially identical data structure.

5. The system of claim 2 in which there are at least two global run queues and the processes include processes of a particular type, and one of the global run queues may enqueue processes of the particular type and another one of the global run queues may not.

6. The system of claim 1 in which the decision means considers whether the particular process is affinitied or unaffinitied in deciding whether to enqueue the particular process to the particular affinity run queue.

7. The system of claim 1 in which the cache context estimating means includes engine activity measuring means for counting engine activity time occurring from a time when the particular process leaves the particular computing engine to a later time.

8. The system of claim 7 in which the engine activity measuring means includes a counter that counts units of engine activity.

9. The system of claim 7 in which the later time is a time at which the decision means decides whether the particular process is to be queued to the particular affinity run queue.

10. The system of claim 7 in which the processes include user processes and kernel processes, and the engine activity measuring means counts engine activity time occurring during user processes, not during kernel processes.

11. The system of claim 1 in which the decision means is responsive to a number of processes queued to the particular affinity queue in deciding whether the particular process is to be queued to the particular affinity run queue.

12. The system of claim 1 in which the decision means is responsive to a priority of the particular processed queued to the particular affinity queue in deciding whether the particular process is to be queued to the particular affinity run queue.

13. The system of claim 1 in which the decision means is responsive to a number of processes enqueued to the affinity run queue of the particular computing engine and a number of processes enqueued to the affinity run queues of other ones of the computing engines.

14. The system of claim 1 in which the decision means is responsive to a number of the processes that are queued to ones of the affinity run queues other than the particular affinity run queue in deciding whether the particular process is to be queued to the particular affinity run queue.

15. The system of claim 1 in which the decision means is responsive to an anticipated amount of data passing on a system bus in deciding whether the particular process is to be queued to the particular affinity run queue.

16. The system of claim 1 in which the decision means decides whether the particular process is to be queued to the particular affinity run queue in response to the particular process being located in a predetermined section of the affinity run queue.

17. A computing system, comprising:

multiple computing engines that run processes, the multiple computing engines each being associated with a cache memory and an affinity run queue;

cache context estimating means for estimating with respect to a particular one of the processes an amount of cache context of the cache memory associated with a particular one of the multiple computing engines, which ran the particular process;

enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and

decision means responsive to the amount of cache context for deciding whether to enqueue the particular process to the affinity run queue associated with the particular computing engine.

18. A computing system, comprising:

multiple computing engines that run processes, the multiple computing engines each being associated with a respective cache memory, a respective affinity run queue, and at least one global run queue;

cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes;

enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and

decision means responsive to the amount of cache context for deciding whether to enqueue the particular process to the affinity run queue associated with the particular computing engine or to one of the global run queues.

19. A computing system, comprising:

multiple computing engines that run processes including unaffinitied processes and affinitied processes, the multiple computing engines being associated with respective cache memories, respective affinity run queues, and at least one global run queue;

cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes;

enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and

decision means responsive to the estimated amount of cache context for deciding whether a particular unaffinitied process should become affinitied to a particular one of the computing engines and enqueued to the affinity run queue of the particular computing engine, and for deciding whether a particular affinitied process should become unaffinitied and enqueued to one of the global run queues.

20. A computing system, comprising:

multiple computing engines that run processes and are associated with respective affinity run queues, respective particular numbers of the processes being associated with each computing engine, the respective particular numbers being at least zero;

storage means for storing multiple variables each having a value and each respectively associated with the multiple computing engines, each respective particular number corresponding to one of the variables;

sampling means for repeatedly sampling the respective particular numbers of the processes associated with each computing engine;

determining means for determining which of the respective particular numbers of processes are greater than the corresponding variable values;

increasing means for increasing each one of the variable values for which a corresponding respective particular number is determined to be greater; and

moving means for transferring certain ones of the processes from one of the affinity run queues associated with one of the computing engines associated with a highest variable value to one of the affinity run queues associated with one of the computing engines associated with a lowest variable value.

21. The system of claim 20 in which each one of the respective particular number of the processes is an integer equal to a number of the processes in the affinity run queue of the respective computing engine plus one if one of the processes is being run by the respective computing engine when a sample is made.

23. The system of claim 21 further comprising priority considering means for considering a priority of one of the processes in determining whether the process should be transferred.

22. A method for assigning processes to run queues in a multi-engine computing system, the method comprising the steps of:

queuing a process to a global run queue;

running the process on a first computing engine which is associated with a first cache memory;

storing the process in a memory;

storing a first count of a counter associated with the first computing engine at a time that the process is stored;

storing a second count of the counter at a time that the process becomes runnable;

comparing the first and second counts to estimate the amount of cache context remaining in the first cache memory with respect to the process; and

deciding whether to enqueue the process to an affinity run queue associated with the first computing engine or to another run queue based on the estimated amount of cache context.

24. A computing system, comprising:

multiple computing engines that run processes and are associated with respective affinity run queues, respective particular numbers of the processes being associated with each computing engine, the respective particular numbers being at least zero;

storage means for storing multiple variables each having a value and each respectively associated with one of the multiple computing engines, each respective particular number corresponding to one of the variables;

determining means for determining which of the respective particular numbers of processes are greater than the corresponding variable values;

increasing means for increasing each one of the variable values for which a corresponding respective particular number is determined to be greater; and

moving means for transferring certain ones of the processes from one of the affinity run queues associated with one of the computing engines having a particular variable value to another one of the affinity run queues associated with one of the computing engines associated with a lower variable value.

25. The system of claim 24 further comprising priority considering means for considering a priority of one of the processes in determining whether the process should be transferred.