Method and apparatus for efficient scheduling in a multiprocessor system

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.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention relates to a method and apparatus for improving the 
efficiency of process scheduling in a multiprocess system. 
2. Art Background 
In a time sharing computer system the CPU is allocated to a process for a 
pre-determined period of time called a time-slice or time quantum at the 
end of which the process is pre-empted and a second process is scheduled 
to begin at the start of the first new time-slice. The process preempted 
is then rescheduled to continue execution at a later time-slice. Process 
scheduling techniques are employed to determine the order in which 
processes have access to the CPU. 
Process scheduling techniques have been extended to multiple-CPU computer 
systems. Processes are allocated a time-slice according to the CPU 
available. A process table is maintained which identifies each process to 
be executed. Each process table entry identifying a process contains a 
priority field for a process scheduling. For example, the priority of a 
process may be a function of the amount of its CPU usage with processes 
getting a lower priority if they have recently used the CPU. A process 
scheduler accesses the process table information and controls which 
processes are allocated the usage of the CPU. For information on process 
scheduling see The Design of the UNIX.RTM. Operating System, Maurice J. 
Bach, pages 247-258 (Prentice-Hall, Inc., 1986) and Operating System 
Concepts, 3rd Ed., Silber Schetz, Peterson and Galvin, pages 97-125 
(Addison-Wesley, 1991). 
Typically in a multiple CPU system, the scheduler will allocate the next 
available CPU to the process having the highest priority for scheduling. 
However, as the multiple process systems become more sophisticated, other 
factors must be considered in scheduling processes to achieve the best 
results. In particular, in a multiple CPU system, cache memories are now 
allocated to each CPU. Applying currently known scheduling techniques 
results in poor usage and efficiency of the cache memories. This is 
illustrated with respect to FIG. 1. FIG. 1a shows at time T0, there are 
five processes in the process queue indicating those processes are ready 
to be executed: A, B, C, D, and E. Since no processes have been executed 
at time T0, the cache contents and the process context for each processor 
are empty. 
Referring to FIG. 1b at time T1, the first process is allocated to the 
first processor, Processor 1. Thus, the process context currently 
executing on Processor 1 is Process A and contents of the cache contain 
data related to Process A. At time T2, referring to FIG. 1c, the next 
process of highest priority is allocated to execute on Processor 2. 
Therefore, the process context of Processor 2 is Process B and the 
contents of the cache contain data related to Process B. At time T3, as 
shown in FIG. 1d, a context switch is performed wherein Process A is 
swapped out from the CPU and the process of highest priority, Process C, 
is swapped in to be executed by Processor 1. Thus, the context of 
Processor 1 is Process C. After some execution of Process C, the cache 
contents will contain data related to Process C as well as pre-existing 
data located in the cache related to Process A. At time T4, referring to 
FIG. 1e, a context switch is performed on Processor 2, wherein Process B 
is swapped out and Process D, the next process to be executed, is swapped 
in. Thus, Processor 2 is executing Process D and the cache contents of the 
cache memory associated with Processor 2 contains a mixture of data 
related to Process B and Process D. Continuing the pattern, it is evident 
that Process E will be scheduled on Processor 1 and Processor 2 will pick 
Process A from the run queue to execute next. This exposes a critical flaw 
in extending current scheduling algorithms to multiple CPU systems. In 
particular, current scheduling algorithms do not account for performance 
penalty of process shuffling among multiple processors. This penalty 
results from a "cold start" of the cache on the new processor which could 
avoided by scheduling the process on a CPU whose cache already contains 
data associated with the process. A method of scheduling which weighs this 
penalty in the scheduling algorithm would greatly improve the performance. 
For purposes of the following discussion, a cache is said to be cold 
relative to a particular process when it contains little or no data 
required for the execution of that process and accesses to the cache will 
miss. A cache is said to be warm with respect to a particular process when 
it contains data required for the execution of the process and accesses to 
the cache will hit. 
Referring to FIG. 1f, the pattern of processor allocation can be extended 
to the processors so that over time a history of processors each process 
executes on can be determined. Note that Process A, which previously ran 
on Processor 0 will be restarted on Processor 1 and will not execute on 
Processor 0 until two processes (C and E) have previously executed on 
Processor 0. This ensures that much of the data from Process A in 
Processor 0's cache will have been replaced with data from Processes C and 
E. If the scheduling interval is approximately equal to the time it takes 
for the executing process to fill half of the cache, it can be seen that 
each process executes at best from a half-full cache when one or more 
intervening process have run on the CPU. Rescheduling takes place at every 
other time interval, such that the rescheduling executions are out of 
phase with one another. 
SUMMARY OF THE INVENTION 
It is therefore an object of the present invention to provide a scheduling 
algorithm to account for the performance penalty of process shuffling 
among multiple processors and resources. 
It is an object of the present invention to provide a system which 
schedules processes according to the priority of the process as well as 
the cache warmth of the cache associated with a particular processor. 
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 
a processor's resource, such as a cache, with respect to a schedulable 
unit, such as a particular 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 to run on the processor it previously executed on, in 
order to take advantage of the data (e.g., process instructions and 
process data) located in the cache associated with the specific processor. 
The system may be extended to provide more sophisticated models for 
determining cache warmth and the scheduling of schedulable units, such as 
processes and threads of processes.

DETAILED DESCRIPTION OF THE INVENTION 
FIG. 2 illustrates a system for implementing the process of the present 
invention. A plurality of processes are executed by a plurality of 
processors 10, 20. Each processor 10, 20 has a cache 30, 40 associated 
with it. The scheduler 50 determines which process to assign to an 
available processor. The process table 60, FIG. 3, contains data regarding 
each active process including the system level context of the process, the 
virtual address memory management information and, in the present 
invention, status bits indicative of the warmth of the cache associated 
with the processor upon which the process was executed. By using priority 
information as well as cache warmth, scheduling queues 70 may be utilized 
to identify the order of processes to be executed. The number of bits 
required to indicate cache warmth is dependent upon the extent of 
information desirable. For example, in one embodiment, a number of bits is 
used to identify the processor number of the processor upon which the 
process was last executed. This similarly will indicate the cache which 
contains data related to the process or the cache which most likely will 
contain data related to the process. Further information such as a count 
of cache misses or a warmth count may also be represented to allow for 
more efficient scheduling algorithms. 
FIG. 4a illustrates one embodiment of the present invention. Referring to 
FIG. 4a, if Process A was previously executed on Processor 1, the cache 
warmth bits may identify a value of 1 indicative of Processor 1. 
Similarly, if Process B executed previously on Processor 2, the binary 
value 10 identifies that Process B was executed by Processor 2. It follows 
that if Process C was executed by Processor 3 a value of 11 would be 
indicative of the cache warmth of the cache associated with Processor 3. 
Thus, the scheduler will schedule Process A with Processor 1 in order to 
minimize the number of cache misses and maximize usage of the data 
associated with Process A already contained in Processor 1's cache, which 
was previously stored in the cache during the earlier time-slice Process A 
was executed by Processor 1. 
FIG. 4b illustrates an alternate embodiment of the present invention 
wherein the cache warmth bits not only identify the processor which 
executed the process, but the number of time-slices prior that the process 
was executed by a particular processor. Thus, for example, if Process A 
was executed by Processor 1 at time-slice 1, Process B was executed by 
Processor 2 at time-slice 2, Process C was executed by processor 3 at 
time-slice 3 and Process D was executed by Processor 1 at time-slice 4, 
the status bits at the end of time-slice 4 may look like that shown in 
FIG. 4b. In particular, Process D was executed by Processor 1, indicated 
by left-most binary value 01, at the current time-slice, indicated by the 
second binary value 00. Similarly, the status bits associated with Process 
A indicate that Process A was previously executed by Processor 1 (as 
indicated by the binary value 01) and was executed 3 time-slice periods 
previously (as indicated by the binary value 11). The scheduler may 
utilize this information to schedule Process A at the next time-slice to 
Processor 1 because Process A, as indicated by the cache warmth status 
bits for Process A located in the process table, was previously executed 
on Processor 1 and has been waiting the longest period of time (as 
indicated by the second binary value) for the availability of Processor 1. 
Similarly, the scheduler may utilize this information to maximize CPU 
utilization and cache warmth by scheduling the more recent processes 
executed by the processors more frequently and scheduling the processes 
least used only when a predetermined number of time-slices have passed. 
Such a scheduling scheme would have a similar effect to increasing the 
time-slice duration, since the maximum latency between execution intervals 
increases. 
The cache warmth bits can also indicate a value to be used by the scheduler 
which indicates a number of cache misses that have occurred for any given 
process. This may then be used to perform scheduling operations. For 
example, the lower number of cache misses for a given process, the more 
likely the cache contains data related to that process. Thus, it may be 
more efficient to give a higher priority to that process while the cache 
contains process relevant data and lower priority to other processes which 
will incur cache misses when executed (because process related data is not 
currently located in the cache) and will therefore require time consuming 
memory operations in order to update the cache. 
Furthermore, the scheduler may utilize the cache warmth information to 
perform load balancing, that is, the scheduler may schedule processes 
which require maximum CPU usage to a single processor while grouping those 
processes which are I/O intensive but not CPU intensive to other 
processors. This information can be derived for example, from information 
in the process table about whether the process was pre-empted or blocked 
on I/O when rescheduling occurred, the number of time slices passed and 
the number of times the processor was allocated to a process. 
For example, if two processes A and B are executing on Processor .phi. and 
Process A is CPU intensive (70% CPU usage) and Process B is I/O intensive 
and not CPU intensive (e.g., a keyboard program, 30% CPU usage), Process A 
will be granted access to Processor .phi. more frequently because Process 
B requires little CPU time. If Process C is allocated to Processor 2 and 
similarly is I/O intensive and not CPU intensive (e.g., 20% CPU usage), 
the scheduler will be able to determine from the cache warmth bits and CPU 
utilization information in the process table (e.g., the amount of time the 
process has been executing) that Processor 2 is underutilized and it would 
be more efficient to allocate Process B to Processor 2 whereby Process A 
can have sole access to Processor 1. 
A problem which sometimes arises in heavily loaded multiprocessing 
environments is resource thrashing. Thrashing of the cache occurs when 
processes executing replace a substantial portion of the processor's cache 
before the next process runs on that processor. The next process scheduled 
on that processor will incur numerous cache misses and also replace a 
substantial portion of the processor's cache entries with its process 
specific data. When the first process is subsequently rescheduled, to the 
same processor and thus, to the same cache, a number of cache misses are 
incurred and the cache entries are again replaced with data related to the 
first process. Because the time-slice interval is fixed and cache misses 
require the CPU to wait idly for data from memory, CPU utilization 
decreases dramatically when cache thrashing takes place. Thus, it is 
preferred that the scheduler take into account the problem of thrashing 
when scheduling processes. In particular, the cache warmth bits may be 
used to detect the presence of thrashing. For example, the cache warmth 
for a scheduled process is compared to a cache warmth threshold value 
indicative of thrashing. Thrashing is found to exist if two successive 
processes exceed the threshold value. Once thrashing is detected, the 
scheduling of processes can be modified to eliminate some of the 
deleterious effects of cache thrashing. For example, if thrashing is 
detected, the duration of time a process executes on a given processor can 
be increased by restricting rescheduling operations to occur at every 
other time interval. (See code in FIG. 6 for example.) 
Although in the preferred embodiment the cache warmth bits are stored in 
the process table for easy access, the information regarding scheduling 
efficiency may incorporate other areas of the kernel and hardware such as 
the MMU or a separate or specified portion of kernel memory. For example, 
information regarding cache warmth for each process may be stored in the 
process description block or process table. Furthermore, the concept of 
cache warmth can be extended to instead track page faults which occur in a 
virtual memory system or other types of systems in which shared resources 
maintain process specific data. 
The scheduler is modified slightly to include logic which utilizes the 
cache warmth bits to determine the priority of processes and the impact 
that scheduling a particular process would have in terms of CPU 
utilization. This logic may be implemented in hardware or software or a 
combination of both. For example, in hardware, a comparator is employed to 
compare the status bits identifying the processor ID upon which the 
process last executed to the processor ID of the next processor available 
to be scheduled. If the IDs do not match, the process will not be 
scheduled to that Processor but will wait to be scheduled upon the 
processor for which the IDs do match. FIG. 6 is an example of scheduler 
code which uses cache warmth to schedule efficiently and decide which 
process to run next. This scheduler also determines if thrashing is 
occurring, and if so, schedules the same process twice in succession to 
increase CPU utilization which would otherwise suffer during thrashing. 
A simple example of comparator logic is set forth in FIG. 5. The cache 500 
comprises an address tag 510 and data 520, 525, 530, 535. The tag 
information generated from the CPU address is compared to the tag from the 
cache and, if they are equal, a cache hit is noted and the data from the 
cache is extracted through the multiplexors 570, 575. If the tags are not 
equal, a cache miss occurs and the counter 560 tracking the misses 
determinative of cache warmth is incremented and the cache is updated with 
data read from memory (not shown). This logic also provides a simple means 
to read the counter 560 by tracking it as an additional cache. A 
predetermined address is used to address the counter. A predetermined 
address is supplied to the cache and the cache supplies the value of the 
counter. 
Preferably, the mechanism which tracks cache warmth, e.g., counter 560 
(FIG. 5), does not record a miss, and therefore increase the cache warmth 
value, when the process is replacing its own data as this replacement is 
not indicative of the change of state of cache warmth. Therefore, in an 
alternative embodiment, the process context of the line of the cache to be 
replaced is compared to the context of the currently executing process. If 
the contexts are associated with the same process, (e.g., the contexts are 
equal), the counter is not incremented. If, however, they are different, 
then the line of memory being placed in the cache will alter the warmth of 
the cache. Once the counter associated with a segment has been determined, 
the method of comparing one scheduling context process of the line being 
replaced and the current executing scheduling context (e.g., executing 
process) process may be employed as outlined above. 
The ability to model the degree to which the process executing on a 
particular CPU modifies the resources (cache or other) associated with 
that CPU is limited by the counter implementation which tracks the 
resource. Ideally, the counter would be able to differentiate the 
processes at the finest level of granularity, i.e., the smallest unit 
manipulated by the scheduling algorithm. For example, in a multiple 
processor system executing multi-threaded processes, the counter would use 
knowledge of the current thread of execution and information about the 
thread of execution of the line being replaced in the cache to determine 
whether or not to increment the counter. In this scheme the cache tags 
must contain added information, the unique ID that specifies the thread of 
execution or which group of threads to which the line belongs. 
The cache and scheduling algorithm can be modified to utilize the technique 
of cache coloring. Coloring refers to segmenting the cache into regions 
and using a predetermined number of bits of the virtual address to 
generate a hash value which selects the cache region to which a process 
address maps. Coloring restricts different processes to different segments 
of the cache, and thus reduces aliasing of several addresses from 
different processes to the same line. In an embodiment which uses cache 
coloring, separate counters are maintained to track the cache warmth 
values in a cache segment. The bits used to generate a hash value also 
distinguish the counters between processes. Once the counter associated 
with a segment has been identified, the method of comparing contexts of 
the line being replaced and the process currently executing may be 
employed as previously discussed. Cache coloring will minimize the effect 
of a single process destroying all data in the cache by restricting its 
addresses to map to only one segment of the cache. Thus, a single process 
will only affect the one region of the cache it maps to, rather than the 
entire cache. 
In an alternative embodiment not only the warmth value for the current 
process is updated, but also the warmth values for all other processes 
that previously executed on the same processor are updated. This provides 
greater accuracy in the cache warmth measurement. The technique operates 
as follows: after the process has run, the current process's cache warmth 
is updated by an increment equal to the number of cache misses which 
occurred. The cache warmth values for all the other remaining processes 
which ran on the same processor are decremented by an amount proportional 
to their respective current cache warmth value. This is illustrated by the 
example below: 
__________________________________________________________________________ 
T1 T2 T3 
__________________________________________________________________________ 
A 50 - (70*50/100) 
= 15 (90*15/100) 
= 90 
B 10 - (70*10/100) 
= 3 - (90*3/100) 
= 0 
C 20 - (70*20/100) 
= 6 - (90*6/100) 
= 1 
D 20 - (70*20/100) 
= 6 - (90*6/100) 
= 1 
E 70 - (90*70/100) 
= 7 
100 100 100 
__________________________________________________________________________ 
At time T1 Processes A, B, C, D respectively have cache warmth values of 
50, 10, 20, 20 for a total cache warmth value of 100 process E is 
currently executing. At time T2 Process E (a new process) has run, 
resulting in a cache warmth value of 70 and a new process is selected for 
execution. The cache warmth values are proportionally adjusted according 
to the following equation: new cache warmth=old cache warmth-(old cache 
warmth * current process cache warmth/total cache warmth). Using these new 
values for warmth, the next process to run is selected. Assuming all 
processes have equal priority, Process A is selected to run at time T2. 
Similarly, at time T3, process A finishes running with a cache warmth value 
of 90. The cache warmth values for processes B,C,D,E are proportionally 
decremented by the amount such that the total number of misses distributed 
among the processes is equal to the increased warmth assigned to the 
process previously executed. It follows that process E, which had the 
greatest proportion of the cache would similarly lose the greatest amount. 
The computed cache warmth values accurately reflects this. 
While the invention has been described in conjunction with the preferred 
embodiment, it is evident that numerous alternatives, modifications, 
variations and uses will be apparent to those skilled in the art in light 
of the foregoing description. In particular, the invention described 
herein can be utilized with a variety of types of resources in order to 
maximize efficient usage of the resource. Further, a variety of types of 
processors may be employed. In addition, the present invention applies not 
only to processes but to the scheduling of any schedulable unit. An 
example of another schedulable unit is a thread of a process. 
A traditional UNIX process contains a single thread of control. This thread 
consists of the sequence of executing instructions along with a minimal 
amount of state variables such as a program counter (PC) and stack frame 
(SF). A multi-processor system in which memory is shared by all processors 
can execute different processes (each with a single thread of control) 
concurrently. It is important to note that each process runs in its own 
memory space and contains a single thread of execution. Thus, concurrent 
process execution is the finest grain of parallelism achievable in a 
multi-processor environment with singly-threaded processes. 
A multi-threaded UNIX process contains several threads of control. Each 
thread in a multi-threaded process consists of the sequence of 
instructions being executed by that particular thread and a collection of 
state variables that are unique to the thread. Thus, each thread contains 
its own PC and SF variables. Multiple threads allow for parallelism and 
concurrent execution within a process when more than one processor is 
available. A multi-processor system in which memory is shared by all 
processors can execute different threads (from one or multiple processes) 
concurrently. It is important to note that each process runs in its own 
memory space as before, but now multiple threads of execution share the 
same memory space, thus the need for unique state variable (PC and SF 
among others) for each thread. Therefore, concurrent thread execution is 
the finest grain of parallelism achievable in a multi-processor 
environment with multiply-threaded processes. For further information see, 
Powell et al., "Sunos Multi-Thread Architecture," USENIX, Winter, 1991. 
From the above discussion, it should be clear that a multiple processor 
system running only one single-threaded process will take the same amount 
of execution time as a single processor system because there is no means 
for parallel execution. However, multi-threaded processes will be able to 
exploit concurrent thread execution, and thus, make use of several 
processors to speed execution of the process. 
The present invention is therefore applicable to any system with multiple 
threads of execution executing concurrently. These threads may consist of 
several singly-threaded processes or threads from one or more 
multi-threaded processes or a mixture of singly-threaded and 
multi-threaded processes.