Techniques for providing improved affinity scheduling in a multiprocessor computer system

Techniques for controlling a thread on a computerized system having multiple processors involve accessing state information of a blocked thread, and maintaining the state information of the blocked thread at current values when the state information indicates that less than a predetermined amount of time has elapsed since the blocked thread ran on the computerized system. Such techniques further involve setting the state information of the blocked thread to identify affinity for a particular processor of the multiple processors when the state information indicates that at least the predetermined amount of time has elapsed since the blocked thread ran on the computerized system. Such operation enables the system to place a cold blocked thread which shares data with another thread on the same processor of that other thread so that, when the blocked thread awakens and runs, that thread is closer to the shared data.

BACKGROUND

Conventional time-limited affinity scheduling within a multiprocessor computer system typically involves the scheduling subsystem of the computer system unparking and preferentially dispatching a thread onto the processor on which the thread last ran if less than a predetermined time period has elapsed since the thread last ran (i.e., the thread is still “warm”). This affinity-aware manner of scheduling during the predetermined time period enables the computer system to enjoy more-efficient operation since it is likely that a warm thread retains some residual affinity for the processor on which that thread recently ran. Specifically, using time-limited affinity-aware scheduling, the odds are much improved that the code cache, data cache and translation lookaside buffer (i.e., a cache of virtual to physical memory translations), still contain information used by the thread when it last ran on that processor. Furthermore, it is likely that the thread will access much of that same data after it resumes execution.

It should be understood that time-limited affinity-aware scheduling reduces the so-called “cache reload transient” penalty. In particular, when a “cold” thread is initially dispatched onto a processor, the cold thread will start to access its own code, data and translations displacing previous information in the caches and populating the caches and translation lookaside buffers (TLBs) with its own thread-specific information. During this period (the cache reload transient), the thread incurs a significant number of cache misses and translation misses, significantly slowing its execution. If the caches use a write-back policy instead of a write-through policy, when the cold thread misses, it will have to wait again while its data is loaded from memory into the cache. That is, when the cold thread misses, cached data which is likely associated with another thread will be evicted from the cache. Next, new data for the cold thread must be brought into the cache. Accordingly, there are two penalties, namely, the write-back of the cached data and then the subsequent loading of the new data into the cache. This situation would also occur if the thread is unparked after a substantial amount of time has passed (e.g., if the thread becomes cold again due to the expiration of the predetermined time period).

Before presenting an example of time-limited affinity scheduling, a brief discussion of the taxonomy of cache misses will be provided. As a thread executes on a processor, the following can be found in the processor's cache:A. Shared read-only executable code (i.e., it is typical for threads to share code but access distinct data).B. Shared read-only data (e.g., a table that never changes).C. Shared read-write data (e.g., data protected by a lock or mutex mechanism of some kind in order to coordinate access to the data and avoid interference between threads).D. Private thread-specific read-write data (e.g., a thread's own stack).E. Residual data and code installed in the cache by the execution of some prior thread, but that has not yet been displaced by the current thread.
By convention, no locks or mutex mechanisms are needed to access (A), (B) and (D).

Furthermore, on a multiprocessor system, copies of shared read-only elements may reside in the caches of multiple processors at the same time. For read-write data, however, in order to provide coherency and a consistent view of memory, only one processor typically can have a “dirty” or modified copy in its caches at a given time. If some other processor needs to modify or read that dirty cache line, the processor with the dirty copy must pass the cache line to the requesting processor by way of the coherency interconnect.

There are two types of caches misses. A cache miss against read-only lines, such as executable code, will be satisfied from memory. A miss against a dirty cache line incurs more latency on most architectures as the system needs to “steal” or migrate the cache line from the processor that owns the cache line (i.e., the processor that has the cache line in modified/dirty state). Both types of misses incur latency (which impacts the missing CPU) and consume memory and coherency interconnect bandwidth which can impact the throughput of the system as a whole, as the coherency and memory channels have fixed bandwidth. That bandwidth usually is a fixed resource, and efforts to conserve bandwidth yield improve scalability.

The following is an example of conventional time-limited affinity scheduling in a JAVA®-equipped multiprocessor system. Suppose that the system has threads which share access to a critical section of memory (commonly referred to as a “synchronized block”) using a user-mode mutual exclusion technique. In particular, suppose that a first thread and a second thread coordinate access to the critical section using JAVA monitors provided by a JAVA Virtual Machine. Along these lines, suppose that the first thread is currently running on a first processor and that the second thread is currently blocked after running on a second processor. Furthermore, suppose that the first thread currently owns a lock on the critical section and is in the process of writing data to the critical section, i.e., the first thread owns a monitor and the second thread resides on the entry list of that monitor.

When the first thread finishes its work, the first thread relinquishes the lock on the critical section and wakes the second thread. That is, the first thread exits the monitor and calls a JAVA routine to unpark the second thread (e.g., “unpark( )”). It should be understood that threads “park” themselves and that, once parked, a thread is ineligible to run until it is subsequently unparked by some other thread. Parked threads do not appear on the dispatch queue (“ready queue”) so the system scheduler will never dispatch a parked thread. Unparking a thread makes the thread runnable and places the thread on a ready queue.

In response to the JAVA procedure call, the scheduling subsystem places the second thread on the ready queue of one of the processors, and eventually picks the second thread from that ready queue for running. When the second thread begins execution, the second thread can attempt to obtain ownership of the monitor in order to access the critical section.

When the scheduling subsystem places the second thread onto the ready queue of one of the processors, the scheduling subsystem looks at state information of the second thread to (i) determine how much time has elapsed since the second thread last ran, and (ii) identify the processor that last ran the second thread. If less than the predetermined time period has elapsed (i.e., if the second thread is still warm), the scheduling subsystem performs affinity-aware scheduling by moving the second thread onto the ready queue of the processor that last ran the second thread, i.e., the second processor. Accordingly, some of the cached executable thread code for the second thread may still reside in the cache thus alleviating the need to re-cache that executable thread code.

However, if more than the predetermined time period has elapsed (i.e., if the second thread is now cold), the scheduling subsystem disregards affinity (i.e., the system operates in an affinity-unaware manner) by moving the second thread onto the ready queue of the least-utilized processor which may or may not be the second processor. Here, it is unlikely that any executable thread code for the second thread remains cached. Accordingly, the multiprocessor system places a higher value on operating in a load balanced manner vis-à-vis an affinity-aware manner, and thus schedules the second thread on the processor which is least busy.

SUMMARY

Improved techniques utilize state information of a blocked thread to provide “pull” affinity for a particular processor of a computerized system after a predetermined amount of time has elapsed since the blocked thread ran on the computerized system (i.e., after the blocked thread has become cold). For example, suppose that a running thread (i) shares data with a blocked thread within a cache and (ii) sets state information of the blocked thread to identify affinity for the same processor of the running thread. If the running thread relinquishes access to the shared data, and if the blocked thread awakens and runs on the same processor (i.e., the newly awakened thread is “pulled” toward the processor of the running thread), the newly awakened thread will be able to access the shared data from the same cache without requiring the system to perform burdensome cache coherency tasks.

Critically, for a JAVA® monitor (lock) or a mutex, if a thread T1releases a lock L that protects data X, and a thread T2is competing for L, then (by the nature of locking) thread T2will likely access X. It is this property (or observation) that is leveraged in pull-affinity. As such, pull affinity benefits all of (A), (B), (C) and (D). That is, pull-affinity improves the cache miss rate for read-only lines, read-write lines and translation buffers.

One embodiment is directed to a method of controlling a thread on a computerized system having multiple processors. The method involves accessing state information of a blocked thread, and maintaining the state information of the blocked thread at current values when the state information indicates that less than a predetermined amount of time has elapsed since the blocked thread ran on the computerized system. The method further involves setting the state information of the blocked thread to identify affinity for a particular processor of the multiple processors when the state information indicates that at least the predetermined amount of time has elapsed since the blocked thread ran on the computerized system. Such operation enables the system to place a cold blocked thread which shares data with another thread on the same processor of that other thread so that, when the blocked thread awakens and runs, that thread is closer to the shared data.

DETAILED DESCRIPTION

Improved techniques utilize state information of a blocked thread to provide “pull” affinity for a particular processor of a computerized system after a predetermined amount of time has elapsed since the blocked thread ran on the computerized system. For example, if another thread (i) shares data with the blocked thread within a cache and (ii) sets state information of the blocked thread to identify affinity for a processor having convenient access to the same cache, the blocked thread will likely run on that processor and thus enjoy certain optimizations when it awakens and accesses the shared data from the same cache. In particular, such “pulling” of the blocked thread toward that processor increases the opportunity to reduce cache coherency traffic (i.e., there would be no need to copy the shared data from one cache to another which would otherwise consume processor cycles and interconnect bandwidth), thus enhancing operation of the system as a whole even though the predetermined amount of time has elapsed making it unlikely that there is any executable thread code remaining cached within the system when the blocked thread awakens.

FIG. 1shows a computerized system20which is well-suited for running pull affinity scheduling techniques. The computerized system20includes multiple processor groups22(A),22(B), . . . (collectively, processor groups22), a set of storage devices24(e.g., one or more disk drives), and an interconnection mechanism26. Although the interconnection mechanism is shown as a multi-drop bus, a variety of alternative interconnection topologies are suitable for providing data transfer between the processor groups22and the storage devices24(e.g., one or more buses, a network of point-to-point connections, one or more loops, combinations thereof, etc.).

Each processor group22includes multiple processors28and local memory30. For example, the processor group22(A) includes processors28(A)(1),28(A)(2) and local memory30(A). Similarly, the processor group22(B) includes processors28(B)(1),28(B)(2) and local memory30(B), and so on.

The processors28are configured to run a multiprocessing operating system32and higher level code34(e.g., one or more user-mode applications written in JAVA, C, C++, shell scripts, command files, combinations thereof, etc.) which are stored in a non-volatile manner within the set of storage devices24. The operating system32includes an improved scheduler36and other operating system constructs38(e.g., predetermined operating system settings, operating system utilities, plug-ins, code to provide a JAVA Virtual Machine, etc.). One or more computer program products40deliver the operating system32and the code34to the set of storage devices24from an external source. Although the computer program product40is illustrated as a diskette by way of example only, a variety of communications and storage media are suitable for use (e.g., a set of CD-ROMs, tapes, memory cards or sticks, network downloads, propagated signals, combinations thereof, etc.).

Once the operating system32and the code34are properly installed within the computerized system20, the computerized system20generates an operating environment or platform (e.g., Solaris, Linux, Windows/NT, etc.) by running the operating system32. The operating system32then runs the code34within this environment. In particular, the multiprocessor configuration of the computerized system20enables the system20to concurrently run multiple streams of execution (e.g., processes, threads, etc.) which are hereinafter generally referred to as threads42.

Preferably, the scheduler36operates using (i) conventional time-limited affinity scheduling for threads42which are still warm, and (ii) pull affinity for threads42which have become cold. A short summary of conventional time-limited affinity in the context of the computerized system20will be discussed before proceeding to a more-detailed discussion of pull affinity.

Suppose that two threads42(1),42(2) are configured to share data within a portion44of the local memory30(A). Further suppose that the thread42(2) has recently transitioned from a running state to a blocked (or parked) state after running on the processor28(A)(2). In particular, suppose that the thread42(2) has just finished writing data to the shared memory portion44, and has just relinquished ownership of a lock on the shared memory portion44. At this point, the operating system32has updated state information corresponding to the thread42(2) to identify, among other things, the processor28on which the thread42(2) last ran and a time stamp of when the thread42(2) last ran (i.e., the processor28(A)(2)). Currently, code46(i.e., cache lines) for the thread42(2) remains cached in the local memory30(A).

While the thread42(2) remains blocked, suppose that the thread42(1) performs some useful work and then unparks the thread42(2). In particular, suppose that the thread42(1) acquires ownership of the lock on the shared memory portion44, accesses the data therein, relinquishes ownership of the lock, and directs the scheduler36to wake the blocked thread42(2) before parking itself. In response, the scheduler36moves the thread42(2) onto the ready queue of one of the processors28for subsequent dispatch and execution.

When the scheduler36moves the thread42(2) onto the ready queue of one of the processors28, the scheduler36looks at the state information of the thread42(2). In particular, the scheduler36determines whether the thread42(2) is still warm by comparing the time stamp of when the thread42(2) last ran to a current time stamp to determine whether a predetermined amount of time has elapsed (e.g., two minutes, 30 seconds, a predefined number of clock cycles, etc.). This predetermined amount of time (i.e., a predefined threshold) is preferably a preset tuning parameter which can be changed by a system administrator (e.g., see the operating system constructs38inFIG. 1).

If less than the predetermined amount of time has elapsed since the thread42(2) last ran, the thread42(2) is considered warm because it is likely that at least some of the thread code46remains resident in the local memory30(A) to make it worth while to dispatch the thread42(2) on the same processor28on which it last ran. It should be understood that the term “thread code” in this context is intended to generally include executable code of the thread but also corresponding data and translations. Accordingly, the scheduler36identifies the processor28on which the thread42(2) last ran from the state information and moves the thread42(2) onto the ready queue of that same processor28(i.e., the processor28(A)(2)). This procedure is commonly referred to as time-limited affinity scheduling which results in significant operation savings since such scheduling increases the odds that a new copy of the thread code46will not need to be re-cached from the set of storage devices24(see the code34inFIG. 1).

Furthermore, avoidance of re-caching the thread code46alleviates the need to consume other resources within the computerized system20as well (e.g., updating of the translation lookaside buffer (TLB), contention for use of the interconnection mechanism26, contention for memory bandwidth, etc.).

It should be understood that conventional computer systems typically would operate in an affinity-unaware manner once the predetermined time period has elapsed by ignoring affinity information for a cold thread when queuing that thread for execution. That is, since the thread is now cold and it is unlikely that the thread code remains cached at that point and the conventional system would next look to load balancing the operating of the system.

However, in contrast to these conventional computer systems and as will be explained in further detail below, the computerized system20is configured to provide pull affinity after the predetermined amount of time has passed. Here, the scheduler36is capable of moving a cold thread42onto the ready queue of a processor28running another thread42which shares data with the cold thread42. In particular, state information of the thread42(2) is set to increase the odds that the scheduler36will move the thread42(2) onto the ready queue of the processor28(A)(1) (i.e., the processor28for the thread42(1)) rather than another processor28(e.g., rather than any of the processors28of the processor group22(B). Accordingly, the cold thread42will have convenient access to the local memory30containing the shared data44when it awakens thus alleviating the need for extensive operations to move the shared data between caches (i.e., no cache coherency operations are required to move the data44to the local memory30(B)). As a result, pull affinity improves cycle per instruction (CPI) performance of the computerized system20and is extremely well-suited for heavily synchronized multithreaded applications running on symmetric multi-processing (SMP) systems.

Pull affinity improves the performance of individual threads that partake in the pull affinity protocol, but it also improves the scalability and throughput of the system as a whole. On a multiprocessor system, other unrelated threads that happen to run in parallel with threads using pull affinity will benefit as the threads using pull affinity consume of the contended and shared resources such as memory bandwidth and coherency interconnect bandwidth. The pull affinity capabilities of the computerized system20will now be further explained in connection withFIGS. 1 and 2.

FIG. 2shows a sequence of operations which is supported by the computerized system20ofFIG. 1. The first column shows activity by the thread42(1), the second column shows activity by the operating system32(e.g., the scheduler36), and the third column shows activity by the thread42(2) which shares data through the portion44of the local memory30(A) (also seeFIG. 1). Time elapses in the downward direction. For illustration purposes only, the sequence is in the context of a JAVA Virtual Machine.

At time T1, the thread42(1) is running on the processor28(A)(1) and the thread42(2) has recently transitioned to a blocked state. While the thread42(1) runs on the processor28(A)(1), the thread42(1) accesses the portion44of the local memory30(A) which is shared between the threads42(1),42(2) (also seeFIG. 1).

At time T2, the thread42(1) has finished accessing the shared memory portion44and now gives up a lock on the portion44. In particular, the thread42(1) relinquishes a JAVA monitor associated with the portion44, and the monitor is marked as unowned.

At time T3, the thread42(1) unparks the thread42(2) and applies pull affinity to the thread42(2) if appropriate. In some arrangements, this operation is embodied as a call to an improved operating system call (e.g., a single routine called “unparkPull( )”). In response, the operating system32checks the state information of the thread42(2) to determine whether the thread42(2) is still warm. In particular, operating system32compares the time stamp in the state information with the current time to determine whether the predetermined amount of time has elapsed since the thread42(2) last ran.

If the operating system32determines that less than the predetermined amount of time has elapsed since the thread42(2) last ran, the operating system32concludes that that the thread42(2) is still warm so that (i) conventional time-limited scheduling affinity is appropriate and (ii) pull affinity is inappropriate. Accordingly, the operating system32maintains the current affinity settings within the state information of the thread42(2), and simply moves the thread42(2) onto a ready queue based on the current affinity settings. Such operation increases the odds that the thread42(2) will execute on the same processor28(i.e., the processor28(A)(2)) on which the thread42(2) last ran in order to avoid re-fetching cache lines (i.e., the code46) for the thread42(2).

However, if the operating system32determines that the predetermined amount of time has elapsed since the thread42(2) last ran, the operating system32concludes that the thread42(2) has become cold so that (i) conventional time-limited scheduling affinity is inappropriate (i.e., it is unlikely that the code46for the thread42(2) is still cached) and (ii) pull affinity is now appropriate. That is, the operating system32changes the affinity settings within the state information of the thread42(2) to provide pull affinity for the processor even though the thread code46for the thread42(2) may no longer reside in the local memory30(A). To provide pull affinity, the operating system32sets the state information to have affinity for the processor28which runs the thread42(1) (i.e., the processor28(A)(1)), and resets the time stamp to the current time to make the thread42(2) appear warm again. As a result, if the thread42(2) awakens shortly thereafter, the scheduler36can move the thread42(2) onto the ready queue of the processor28on which the thread42(1) last ran in order to improve the chance of the awakened thread42(2) having easy access to the data shared between the threads42(1),42(2). This situation is preferable to running the thread42(2) on a processor28of the processor group22(B) which would require movement of the shared data in the local memory30(B). That is, if the awakened thread42(2) runs on the processor28(A)(1), there is no need to move the shared data44between caches thus saving the computerized system20from performing unnecessary cache coherency operations, and from tying up the interconnection mechanism26unnecessarily.

At time T4, the thread42(1) parks itself. The operating system32responds by transitioning the thread42(1) to a blocked state.

At time T5, the operating system32dispatches the thread42(2), and the thread42(2) executes. If the thread42(2) executes on the processor28(A)(2) with time-limited affinity (i.e., the original predetermined amount of time has not yet elapsed), the code46for the thread42(2) remains within the local memory30(A) thus alleviating the need to re-fetch that code from the set of storage devices24. Furthermore, if the thread42(2) executes on the processor28(A)(1) due to pull affinity (i.e., the blocked thread42(2) became cold but then the operating system32applied pull affinity), the shared memory portion44is available to the thread42(2) thus alleviating the need to perform extensive cache coherency operations. However, if the thread42(2) executes on a processor28without affinity (i.e., the thread42(2) was placed on a processor28in a load balancing manner and neither the thread code46nor the shared data44remains cached), there is no significant penalty to the thread42(2) and the outcome is, in general, neutral (i.e., the system20must re-fetch both the thread code46and the shared data44in a conventional manner).

In summary, once the thread42(2) runs on a processor28, the thread42(2) is free to attempt to obtain the ownership of the lock on the shared memory portion44(e.g., a JAVA monitor). If the thread42(2) is successful, the thread42(2) can then access the shared data.

Additionally, it should be understood that time-limited affinity attempts to run an awakened thread42on the same processor28on which the thread42last ran. This operation improves the opportunity for an awakened thread42to utilize cached thread code46(i.e., the cache thread code46may not yet have been overwritten by other code) thus alleviating the need to re-cache that code46.

If too much time has passed for time-limited affinity to be useful and the thread42is now cold, pull affinity attempts to run the thread42on the same processor28which ran another thread42which awakened the thread42. In the example above, the pull affinity increases the odds that the thread42(2) runs on the processor28(A)(1) which is not the processor28(A)(2) on which the thread42(2) last ran. Nevertheless, this operation provides potential performance improvement by increasing the opportunity for the awakened thread42(2) to utilize cached shared data (i.e., the shared memory portion44) may not yet have been overwritten by other code) thus alleviating the need to move the shared data between caches. Further details of pull affinity will now be provided with reference toFIG. 3.

FIG. 3is a flowchart of a procedure50which is performed by the thread42(1). In step52, the thread42(1) runs on the processor28(A)(1) and accesses the shared memory portion44while owning a lock on the portion44(e.g., a monitor).

In step54, the thread42(1) gives up the lock on the portion44. At this point, the thread42(1) is through accessing the portion44and is ready to block itself.

In step56, the thread42(1) wakes the thread42(2) in order to allow the thread42(2) to perform useful work by calling an improved routine which unparks the thread42(2) and applies pull affinity onto the thread42(2) if appropriate. In some arrangements, the improved routine is a single JAVA procedure call (e.g., unparkPull( )). Alternatively, the improved routine is executable code belonging to the thread42(1) itself.

In step58, the thread42(1) blocks itself. At this point, the thread42(1) transitions into a blocked state and can be unparked upon some event. For example, the thread42(2) can give the thread42(1) pull affinity if the thread42(1) becomes cold, and then awaken the thread42(1) in a similar manner.

It should be understood that the procedure50utilizes an improved JAVA platform by effectuating pull affinity on another thread42(2) using a simple JAVA procedure call. Accordingly, pull affinity is well-suited for high level applications which run multiple threads of execution. As a result, the above-described pull affinity techniques are capable of running in virtually any situation using user-mode synchronization services (e.g., POSIX 1003.1c, “pthreads” condvars and mutexes, etc.). Further details of the invention will now be provided with reference toFIG. 4.

FIG. 4is a flowchart of a procedure70which is performed by the thread42(2). In step72, the thread42(2) initially resides in a parked or blocked state with state information identifying affinity for the processor28on which the thread42(2) last ran, i.e., the processor28(A)(2). The state information further identifies a time stamp showing when the thread42(2) last ran. The operating system32maintains this state information on behalf of the thread42(2).

In step74, the thread42(2) awakens by running on one of the processors28. If the thread42(2) awakened with pull affinity due to the thread42(1), the thread42(2) will enjoy convenient access to the shared memory portion44which remains resident in the local memory30(A) without imposing a cache coherency burden on the system20. The thread42(2) is then capable of attempting to acquire ownership of the lock on the shared memory portion44(e.g., a monitor). If the thread42(2) is unsuccessful in obtaining the lock, the thread42(2) can park itself (e.g., the thread42(2) can move onto an entry list of the monitor). However, if the thread42(2) successfully acquires ownership of the lock, the thread42(2) can then access the shared data. Furthermore, the thread42(2) is capable of subsequently relinquishing the lock, and awakening the thread42(1) with applied pull affinity if appropriate in a manner similar to that shown in the procedure50ofFIG. 3. Further details will now be provided with reference toFIG. 5.

FIG. 5is a flowchart of a procedure90which is performed by the operating system32(e.g., the scheduler36) when supporting pull affinity scheduling of the two threads42(1),42(2). In step92, the operating system32receives a signal from the thread42(1) running on the processor28(A)(1) to unlock the shared memory portion44(see step54inFIG. 3), and marks the monitor for the portion44as being unowned.

In step94, the operating system32receives a signal from the thread42(1) to unpark the blocked thread42(2) and apply pull affinity if appropriate (see step56inFIG. 3). Accordingly, the operating system32accesses the state information of the blocked thread42(2) and determines whether the blocked thread42(2) is still warm by comparing the time stamp within the state information of the thread42(2) with the current time. If the blocked thread42(2) is still warm, the operating system32maintains the current affinity settings of the blocked thread42(2) thus allowing the blocked thread42(2) to enjoy conventional time-limited affinity for the processor28(A)(2) on which the blocked thread42(2) last ran. That is, the operating system32maintains the state information of the blocked thread42(2) at current values since the state information indicates that less than the predetermined amount of time has elapsed since the blocked thread42(2) ran.

However, if the operating system32determines that blocked thread42(2) is cold, the operating system32sets the affinity settings of the thread42(2) to identify the processor28(A)(1) since the thread42(1) which initially signaled the operating system32to awaken the thread42(2) is running on the processor28(A)(1). Additionally, the operating system32resets the time stamp to the current time so that the blocked thread42(2) appears warm again. Accordingly, the state information of the blocked thread42(2) again indicates that less than the predetermined amount of time has elapsed since the thread42(2) ran on the computerized system20.

To unpark the blocked thread42(2), the operating system32moves the thread42(2) onto the ready queue of the processor28based on the state information of the thread42(2). Accordingly, the thread42(2) is now ready for execution.

In step96, the operating system32receives a signal from the thread42(1) to park the thread42(1) (see step58inFIG. 3). The operating system32responds by transitioning the thread42(1) to a blocked state. Preferably, the operating system32stores the identity of the processor28(A)(1) and the current time in the state information of the thread42(1) to allow the thread42(1) to enjoy affinity scheduling as well.

In step98, the operating system32executes the thread42(2) on one of the processors28. It should be understood that other circumstances could arise which causes the thread42(2) to be stolen from the ready queue on which it resides (e.g., a sophisticated dispatching algorithm which aggressively moves threads42among ready queues for other optimization reasons such as load balancing).

Based on the above, it should be understood that the operating system32will avoid dispatching the thread42(2) onto the processor group22(B) unless the predetermined amount of time has transpired since setting pull affinity for the thread42(2). That is, if the operating system32dispatches the thread42(2) onto a processor28of the processor group22(B), it is because (i) so much time has elapsed that it is extremely unlikely that there is any remaining cached thread code46or remaining cached shared data44, and (ii) the system20has determined that running the thread42(2) provides some other benefit (e.g., load balancing to an infrequently utilized processor28).

As mentioned above, improved techniques utilize state information of a blocked thread42(2) to provide pull affinity for a particular processor28of a computerized system20after a predetermined amount of time has elapsed since the blocked thread42ran on the computerized system20. For example, if another thread42(1) both (i) shares data with the blocked thread42(2) within a cache30and (ii) sets state information of the blocked thread42(2) to identify affinity for a processor28having convenient access to the same cache30, the odds are advantageously increased that the thread42(2) will run on that processor28and thus enjoy certain optimizations when it awakens and accesses the shared data from that same cache30. In particular, such “pulling” of the blocked thread42(2) toward that processor28increases the opportunity to reduce undesirable coherency traffic that would otherwise be generated if the blocked thread42(2) did not have access to the same cache lines shared by the thread42(1). Moreover, it should be understood that the potential savings in system performance provided by pull affinity by reusing cache lines storing shared data is substantial, while the potential loss if the application of pull affinity is unsuccessful is minimal (e.g., the cost of a failure of the blocked thread42(2) to run on the same processor28(A)(1) as the unparking thread42(1) is, in general, neutral compared to the performance of conventional systems).

For example, the computerized system20is capable of imposing a limit on the total number of blocked threads42having affinity for a particular processor28(e.g., see the operating system construction38inFIG. 1). In some arrangements, the limit is a tunable preset number (e.g., one, two, etc.) which is controlled by a systems administrator. Such a limit prevents threads42from clustering onto and overwhelming a single processor28. Rather, when the limit is reached, other performance optimization schemes can take place such as load balancing among less utilized processors28(e.g., excess threads on long dispatch queues are stolen by less-busy processors28).

Additionally, it should be understood that a variety of architectures are suitable for use by the computerized system20. For example, in some multiprocessor-per-die-based arrangements, there are processing units which reside on the same die and share a common on-die cache. Such cases include chip multiprocessing (CMP), chip multithreading (CMT), hyperthreaded and multi-core systems among others (e.g., an eight-way Pentium® hyperthreaded system). Furthermore, in some non-uniform memory access (NUMA) based arrangements, there are processing units which reside in a single node with an adjacent cache. Such cases include CC-NUMA and NUMA systems among others. Other configurations are suitable for use as well such as irregular configurations, distributed configurations, and the like.

Based on the above-provided description, it should be understood that, in practice if thread U unparks thread V, it is likely that threads U and V communicate through shared memory. If thread V is not recently-run, the system20biases the kernel's dispatch queue selection mechanism to preferentially place thread V on the dispatch queue of a processor that is “near” the processor on which thread U currently runs. In the case of a CC-NUMA or NUMA system, “near” means on the same node. In the case of a CMT, CMP, HyperThreaded, or multi-core system, “near” means on the same die, and sharing a common level 2 cache.

For example, suppose that a 4-way SMP system has multi-core processors #0and #1residing on one die and sharing a common on-die level 2 cache. Further suppose that the system has multi-core processors (or CPUs) #2and #3residing on yet another die and sharing a common on-die level 2 cache. If thread U running on CPU #0unparks thread V, and thread V is not recently run, then using pull affinity, thread U might artificially mark thread V as having affinity for CPU #0. Thread U then unparks thread V.

This increases the odds that the scheduler (via the unpark operation) will place thread V on the dispatch queue of a processor, such as CPU #1, that shares the level 2 cache with thread V. That, in turn, means that the shared cache lines likely required by thread V will already be in the level 2 cache of CPU #1where thread V resumes execution. In the absence of pull affinity, thread V might resume on CPU #2or CPU #3. When thread V then accessed the cache lines shared with thread U, the accesses would generate undesirable coherency traffic.

Furthermore, it should be understood that the computerized system20allows for disabling pull affinity (e.g., user-mode code can simply use unpark( ) rather than unparkPull( )) to avoid certain situations in which pull affinity is either less effective or possibly detrimental. For example, in applications that wake gangs of worker threads42, the performance of the computerized system20may be better if pull affinity is not used and the threads42are dispersed over all of the processors28. As another example, for a thread42which performs a “notify all” operation (e.g., notifyAll( )), it may be more efficient to allow the system20to simply load balance the notified threads42rather than use pull affinity.

Additionally, it should be understood that the above-described pull affinity techniques were described as being implemented as a dedicated “improved” unparkPull( ) operation by way of example only. In other arrangements, these pull affinity techniques are implement in other ways. For example, Solaris®, Linux and Windows, respectively, provide processor_bind( ), sched_setaffinity( ) and SetThreadIdealProcessor( ) to establish affinity between threads and processors. These facilities can be used to transiently establish affinity between a thread and a processor. Specifically, prior to waking a first thread, an unlocking second thread can set the first thread's affinity to the processor on which the unlocking second thread is running. Immediately after the first thread wakes up, the first thread would cancel this affinity. Such modifications and enhancements are intended to belong to various configurations and arrangements of the computerized system20.