Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1995-06-30
2003-10-14
Banankhah, Majid (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06633897
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to a method and system for improved data processing and in particular to an improved method and system for data processing within a multiprocessor data processing system. More particularly still, the present invention relates to an improved method and system for optimizing thread processing in a multiprocessor data processing system.
2. Description of the Related Art
The use of threads in modern operating systems is well known. Threads allow multiple execution paths within a single address space to run concurrently on a processor. This increases throughput in a multiprocessor system and provides modularity in a uniprocessor system.
A typical multiprocessor data processing system has both a global and a local execution queue. Threads are assigned from the global execution queue to a particular local execution queue associated with a processor on the basis of affinity, that is, threads having a high degree of shared resource utilization are assigned to the same local execution queue. An execution queue is a listing of such threads to be executed in an orderly fashion on a data processing system.
The multiprocessor data processing system must be able to efficiently schedule a thread to execute. Most of these data processing systems have local caches, which is a fast memory dedicated to a particular processor. It is desirable to make use of an already loaded local cache since reloading the cache is a comparatively time consuming operation that causes the processor to be idle while the cache is being reloaded.
The operating system used to control the data processing system typically attempts to make intelligent scheduling decisions to increase throughput and responsiveness. The local execution queue identifies the threads that have run, or will be run, on each processor. Threads that are on the local execution queue will not move to another processor's local execution queue unless acted upon by the operating system as to achieve an equitable load balancing to avoid idle processors, or if it is determined that the threads affinity has been degraded or lost and the cost to run the thread on any other processors in the system is the same.
An additional option is to identify the threads cache utilization, or cache footprint, in order to make the best decision in scheduling. Unfortunately, not all systems are able to have means for identifying a thread's cache utilization or cache footprint.
Accordingly, what is needed is a method and apparatus for scheduling execution or run affinity using a global run queue, which is the only run queue in the system. Additionally, what is needed is a method that allows each processor to know or keep track of the thread that previously ran and is able to attempt to rerun the same thread if possible, to utilize the existing cache footprint.
SUMMARY OF THE INVENTION
It is one object of the present invention to provide a method and system for improved data processing.
It is another object of the present invention to provide an improved method and system for data processing within a multiprocessor data processing system.
It is yet another object of the present invention to provide an improved method and system for optimizing thread processing in a multiprocessor data processing system.
According to the present invention, a method and system for establishing a priority order of threads executed within a multiprocessor data processing system are disclosed. The priority order of threads is maintained on a global queue within the data processing system and the queue order is determined by selecting a most favored runnable thread from among either a current thread, a most favored thread, or an affinity thread. The current thread and affinity thread are only selected if they have the same priority as the most favored thread. Once the thread is chosen, be it the current thread, the most favored thread, or the affinity thread, the chosen thread is taken off the run queue and then is run on the data processing system on a selected processor. An affinity thread pointer is updated to the thread being run to select the next affinity thread or the thread having the greatest affinity. The affinity thread is determined, as being the previous and whether that thread is still runnable.
Alternatively, the system may determine whether a current thread may still be run on one of the plurality of processors and, if so, place that current thread on the run queue. Next, the system selects the thread at the top of the run queue, which has the highest priority. If the affinity thread has equal priority to the highest priority thread, then it is run first within the selected processor within the data processing system.
REFERENCES:
patent: 5136590 (1992-08-01), Polstra et al.
patent: 5168566 (1992-12-01), Kuki et al.
patent: 5222217 (1993-06-01), Blount et al.
patent: 5261053 (1993-11-01), Valencia
patent: 5317738 (1994-05-01), Cochcroft, Jr. et al.
patent: 5515538 (1996-05-01), Kleiman
Vaswani et al, The Implicatious of Cache Affinity on Processor scheduling for Multiprogrammed, Shared Memory Multiprocessors, ACM, 1991.
Browning Luke Matthew
Peek Jeffrey Scott
Banankhah Majid
Bracewell & Patterson L.L.P.
Leeuwen Leslie A. Van
Roberts Diana L.
LandOfFree
Method and system for scheduling threads within a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for scheduling threads within a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for scheduling threads within a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3119547