Method and apparatus to advise spin and yield decisions

Methods and apparatus provide for a busy resource encoder to allow for a finer control of spin versus yield decisions. Specifically, the busy resource encoder allows for the execution a first thread, where the first thread is using a particular resource. Additionally, the busy resource encoder allows for the execution of a second thread, where the second thread requires use of the resource which is locked due to first thread execution. The busy resource encoder creates a busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread. The second thread can then read the busy code to determine to execute one of a spin and a yield routine by the second thread.

BACKGROUND

In conventional systems, the speed and efficiency of many computing applications depend in large part upon the availability of processing resources. To this end, conventional computer systems provide computing architectures that commonly incorporate multithreaded processes that enable the sharing of resources in order to accommodate multiple paths of execution within a computer/operating system. As such, a thread may be characterized as a separately executable portion of a process. Each thread typically has its own distinct program counter and represents a separate movement of a processor through program instruction space and storage. In this manner, a program may be broken-up into multiple different threads. Ideally, this segmentation avoids requiring a computer process to execute a single unitary process or program from start to finish with pronounced intervals of wasted processing time. As such, a thread continuously accesses a resource until either its execution is interrupted or that thread must wait for a resource it requires to become available.

To facilitate coordination of threads and associated resources, threads typically share a priority scheme or schedule that partially dictates allocation of processing cycles as between different threads. A task dispatcher program may use this scheme to assign and dispatch a central processing unit(s) (CPU), timeslice, or other resource to each thread. Such exemplary resources might include hardware registers, database files and other memory resources. Thus, multithreaded operation can provide the illusion of simultaneous execution of multiple programs, given the relatively high processing speeds relative to that of other resources in the computer.

As a consequence, when synchronizing multiple threads of control in conventional systems, often one thread owns a resource that another thread needs. When one thread finds that another thread owns such a resource, the thread can either “spin” to wait for the resource to be released, or “yield”, thereby giving up the processor to be notified when the resource is available.

Spinning is a technique in which a process repeatedly checks to see if a condition is true, such as waiting for keyboard input or waiting for a lock (i.e. a lock on a required resource) to become available. Spinning can also be used to delay execution for some amount of time; this was necessary on old computers that had no method of waiting a specific length of time other than by repeating a useless loop a specific number of times. Spinning can be a valid strategy in certain special circumstances, most notably in the implementation of spinlocks within conventional operating systems designed to run on SMP systems.

A spinlock is a lock where the thread simply waits in a loop (“spins”) repeatedly checking until the lock becomes available. As the thread remains active but isn't performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some typical implementations they may be automatically released. Conventional spinlocks are efficient if threads are only likely to be blocked for a short period of time, as they avoid overhead from operating system process re-scheduling or context switching. For this reason, spinlocks are often used inside typical operating system kernels.

SUMMARY

Conventional computer systems suffer from a variety of deficiencies. For example, spinning can become wasteful if a thread spins for a long period of time. The longer the lock is held on a resource, the greater the risk of interruption by the O/S scheduler. If this happens, other threads will be left spinning on the lock, despite the fact that progress is not made towards releasing the lock. This is especially true on a conventional single-processor system, where each waiting thread of the same priority is likely to waste its full quantum spinning until the thread that holds the lock is finally re-scheduled.

Another deficiency observed in conventional systems is the reality that implementing spinlocks (“spinning”) is difficult because of the possibility of simultaneous access to the lock. Generally, this is only possible with special assembly language instructions, such as atomic test-and-set operations, and cannot be implemented from high level languages like C.

Yet another deficiency associated with spinning in conventional systems is that threads and processes do not have any way to predict the future behavior of a lock on a resource in order to make the right choice between spinning and yielding. Due to this lack of predictability, previous conventional solutions would either have a “locked out” process to either always decide to spin or always decide to yield regardless of the status of the process actually using the sought after resource. Thus, conventional systems provide no way for a thread competing for a resource to predict which decision (to spin or to yield) is ultimately the best choice.

Techniques discussed herein significantly overcome the deficiencies of conventional applications such as those discussed above as well as additional techniques also known in the prior art. As will be discussed further, certain specific embodiments herein are directed to a busy resource encoder. The one or more embodiments of the busy resource encoder as described herein contrast with conventional systems to allow for a finer control of spin versus yield decisions. The busy resource encoder allows such a decision to be made regarding an expected competition for individual resources between one or more threads (i.e. processes, operations) by updating “busy” information (e.g. a BUSY code) as an owner thread progresses in its use of the resource. Specifically, a BUSY encoding is used to provide information from the owner of the resource about when the resource is likely to be available. Such information thereby allows a thread that is waiting and competing for the resource to decide which decision, to spin or to yield, is most likely the most efficient choice.

Specifically, the busy resource encoder allows for the execution of a first thread, where the first thread is using a particular resource. Additionally, the busy resource encoder allows for the execution of a second thread, where the second thread requires use of the resource which is locked due to first thread execution. The busy resource encoder creates a busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread. The second thread can then read the busy code to determine to execute one of a spin and a yield routine by the second thread.

It is to be understood that the system disclosed herein may be embodied strictly as a software program, as software and hardware, or as hardware alone. The embodiments disclosed herein, may be employed in data communications devices and other computerized devices and software systems for such devices such as those manufactured by Sun Microsystems Incorporated of Santa Clara, Calif., U.S.A., herein after referred to as “Sun.”

DETAILED DESCRIPTION

Methods and apparatus provide for a busy resource encoder to allow for a finer control of spin versus yield decisions. Specifically, the busy resource encoder allows for the execution a first thread, where the first thread is using a particular resource. Additionally, the busy resource encoder allows for the execution of a second thread, where the second thread requires use of the resource which is locked due to first thread execution. The busy resource encoder creates a busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread. The second thread can then read the busy code to determine to execute one of a spin and a yield routine by the second thread.

The busy resource encoder allows such a decision to be made regarding an expected competition for individual resources between one or more threads (i.e. processes, operations) by updating “busy” information (e.g. a BUSY code) as an owner thread progresses in its use of the resource. Specifically, a BUSY code is used to provide information from the owner of the resource about when the resource is likely to be available. Such information thereby allows a thread that is waiting and competing for the resource to decide which decision, to spin or to yield, is most likely the most efficient choice.

As a first thread uses a resource it can “lock” that resource, thereby preventing other threads from accessing and using the resource. This can force the other threads to wait for the resource to eventually become available once the first thread has completed using the resource. The busy resource encoder allows a second thread seeking to use a locked resource to make an informed decision in regards to spinning or yielding while the first thread uses the resource.

For the BUSY code, a variable (e.g. address, word, bit, field, tag, or the like) can be reserved to correspond to the resource. Any thread seeking use of the resource can access the variable to obtain information about the availability of the resource. The BUSY code can be manipulated (i.e. updated, set, cleared) by the busy resource encoder according to the progress of the execution of the first thread in regards to its use of the resource. For example, the first thread may not be completely executed, however, it may no longer actually require the resource for its remaining execution steps. Any thread that is locked out from the resource can use the current value of the BUSY code (i.e. the variable) to decide what to do—spin or yield.

A yield value for the BUSY code can be predetermined. When the BUSY code (i.e. the value of the variable used to represent the BUSY code) equals the yield value, then the BUSY code represents to other threads contending for access to the resource that the most efficient choice is to yield. Also, an access value for the BUSY code is predetermined. When the BUSY code equals the access value, then the BUSY code represents to other threads that the first thread is done using the resource and that the resource is now unlocked and is available to be used by a second thread.

The BUSY code corresponding to the resource can also hold a spin value. The spin value represents to a locked out thread how many spin cycles of a spin routine to execute before attempting another read of the BUSY code. It is understood that the busy resource encoder can continually update the BUSY code. As the first thread utilizes the resource to further a portion of the first thread's execution that requires the resource, progress of the first thread is monitored. Such monitoring allows for creating a measure of completeness of the first thread's execution. The busy resource encoder can process the measure of completeness to assign a value (e.g. the access value, the yield value, the spin value) to the BUSY code. As the busy resource encoder is continually updating the BUSY code as a result of the such monitoring, multiple competing threads can make different decisions as to spinning and yielding.

To further a discussion of various embodiments of the busy resource encoder, example pseudocode is provided below. It is understood that a person having ordinary skill in the art would recognize that pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. Such a pseudocode programming language can be augmented with natural language descriptions of the details, where convenient. Regarding the pseudocode below, an example spinning algorithm is provided to allow a thread to spin in order to wait to read (access) an object (“obj”) while a garbage collector thread copies the object:SPIN:LD Obj→fwd, ftest f for BUSY encodingif BUSY goto SPIN

Here, the pseudocode is written according to an expectation that copying an object can be completed within a short duration, so the pseudocode programs a competing thread that is waiting to read (i.e. access) the object to execute the spin routine. However, if the object is large, or requires touching many memory pages, it will ultimately require the competing thread to execute thousands of spin cycles through the pseudocode. At some point in time during the spinning, the alternative of yielding at the outset becomes the better, profitable choice. Conventional systems provide no way for a thread competing for a resource to predict which decision (to spin or to yield) is ultimately the best choice.

Unlike conventional systems, the busy resource encoder provides for a BUSY encoding as an indication of how much longer the resource (i.e. a locked resource) will be busy, thereby providing a thread competing for that resource with greater control and predictability as to the effectiveness and profitability of a spin or yield decision.

In one embodiment where the busy resource encoder involves the provided psuedocode, the forwarding pointer, f, has a lower order bit used as a variable for the BUSY code that can be cleared or set. The busy resource encoder employs a BUSY encoding such that if the lower order bit is clear then “f” represents a forwarding pointer, but if the lower order bit is set then “f” represents a count of the number of cycles until the resource will be available. Thus, when copying a short (i.e. small) object, the garbage collector thread can install a small BUSY encoding (e.g. a small BUSY code), whereas if it were copying a multi-megabyte array (i.e. a large object), it could install a larger BUSY encoding. The competing thread can use the BUSY encoding (along with other information about the state of the machine, other threads, etc.) to make a more informed decision whether to spin or to yield. Hence, the small BUSY code will trigger a spin routine, whereas a larger BUSY code may trigger a decision to yield.

In another embodiment, if the thread using the resource found that the BUSY code was inaccurate (i.e. the time estimate as indicated by the BUSY code was incorrect), the busy resource encoder can update the BUSY code to provide more accurate information to competing threads. Hence, previous competing threads can then reread the “new” BUSY code and any new competing threads can also take advantage of the revised estimate indicated by the “new” busy code. For example, as the garbage collector thread (which currently owns the resource) works its way through a multi-megabyte array, the BUSY encoding can be updated to indicate a lesser waiting time such that any threads that have arrived towards the end of the garbage collector thread's copying would most likely decide that a better choice would be to spin instead of yield.

Conversely, if the garbage collector thread detected that the copy it was executing is taking longer than a previous estimate (e.g., a partial garbage collection needs to fall back on a complete collection), the BUSY encoding would be updated to reflect the new estimate of its use of the resource so any competing threads (current or new), including those currently spinning, would decide to yield instead of spinning once they read the new BUSY code.

In another embodiment, a first thread's execution can complete its use of a resource, thereby setting the BUSY code at a value that indicates to competing threads that the resource is currently available (unlocked). Two spinning threads can be competing for the resource, where one thread (the second thread) is given access to the resource upon reading the “available” status indicated by the BUSY code. Thus, a spinning third thread is still locked out of the resource once the second thread begins consuming the resource. As the second thread furthers its own execution in relation to the resource, the second thread's progress is monitored in order to update the BUSY code. Thus, the the BUSY code can be updated to advise all competing threads to yield even though the first thread had previously set the BUSY code to provide advice to spin. As the second thread begins an execution sequence that will utilize the resource for a long time, the BUSY code can be set to a predetermined “yield” BUSY code that can be identified by all competing threads. Hence, the spinning third thread will complete the number of spin-loops that was advised by the BUSY code based on the first thread. The spinning third thread will attempt to re-read the BUSY code and encounter the second thread's “yield” BUSY code. As a result, the third thread will initiate a yield routine as opposed to continue the spinning routine that was being executed while the first thread was using the resource. It is to be understood that monitoring functionality can be included in the threads themselves or can be included as a distinct functionality provided by a busy resource encoder150that interacts with threads.

Turning now toFIG. 1, a block diagram illustrates an example of architecture for a computer system110that executes, runs, interprets, operates or otherwise performs a busy resource encoder application150-1and/or busy resource encoder process150-2(e.g. an executing version of the application150-1which can be controlled by a user) in relation to the use of resource200according to embodiments herein. The computer system110may be any type of computerized device such as a personal computer, workstation, portable computing device, console, laptop, network terminal or the like.

As shown in the present example, the computer system110includes an interconnection mechanism111such as a data bus, motherboard or other circuitry that couples a memory system112, a processor113, and an input/output interface114. An input device (e.g., one or more user/developer controlled devices such as a keyboard, mouse, touch pad, etc.) couples to the computer system110and processor113through an input/output (I/O) interface114.

The memory system112can be any type of computer readable medium and, in this example, is encoded with a busy resource encoder application150-1that supports generation, display, and implementation of functional operations as will be further explained herein.

During operation of the computer system110, the processor113accesses the memory system112via the interconnect111in order to launch, run, execute, interpret or otherwise perform the logic instructions of the busy resource encoder application150-1. Execution of the busy resource encoder application150-1in this manner produces a busy resource encoder process150-2. In other words, the busy resource encoder process150-2represents one or more portions or runtime instances of the busy resource encoder application150-1(or the entire application150-1) performing or executing within or upon the processor113in the computerized device110at runtime.

Other embodiments of a busy resource encoder disclosed herein also include any type of computerized device, workstation, handheld or laptop computer, or the like configured with software and/or circuitry (e.g., a processor) to process any or all of the method operations disclosed herein. In other words, a computerized device such as a computer or a data communications device or any type of processor that is programmed or configured to operate as explained herein is considered an embodiment disclosed herein.

FIG. 2is a block diagram of a computer system configured with a busy resource encoder150according to embodiments herein. The computerized device110includes a first thread220and a second thread230competing for used of a resource200. It is understood that the computerized device110can involve a multitude of threads competing for a multitude of resources. A busy resource encoder150is further included and provides a BUSY code150-3. The BUSY code150-3corresponds to the resource200and, more particularly, it corresponds to the first thread's220progress of execution in regards to its use of the resource200. As depicted inFIG. 2, the first thread220is executing and utilizing the resource200. Thus, the resource200is “locked” out to any competing threads. Thus, the second thread230must read the BUSY code150-3in order to decide whether it is more profitable to spin or yield while the first thread220uses the resource200.

FIG. 3is a flowchart300of processing steps310-360performed by a busy resource encoder150to create a BUSY code150-3to indicate the progress of the execution of the first thread220in relation to use of the resource200by the first thread220according to embodiments herein. The steps in flowchart300refer to the features illustrated in the block diagrams ofFIGS. 1 and 2.

At step310, the busy resource encoder150executes a first thread220, the first thread220using a resource200. At step320, the busy resource encoder150executes a second thread230, the second thread230requiring use of the resource200which is locked due to first thread220execution. At step330, the busy resource encoder150creates a BUSY code150-3to indicate the progress of the execution of the first thread220in relation to use of the resource200by the first thread220. At step340, the busy resource encoder150reads the BUSY code150-3to determine to execute one of a spin and a yield routine by the second thread230.

At step350, the busy resource encoder150updates the BUSY code150-1to reflect a current state of progress of the execution of the first thread220in relation to use of the resource200by the first thread220. At step360, the busy resource encoder150reads the updated BUSY code150-3. As the busy resource encoder150reads the updated BUSY code150-3, it allows for one or more competing threads to determine to execute either a spin or a yield routine. For a second thread230that previously yielded or started spinning according to a previous BUSY code150-3, the updated BUSY code150-3can provide the second thread230with new advice as to which decision is ultimately more profitable. Based on the updated BUSY code150-3, the second thread230can either continue the routine it initiated according to a previous value of the BUSY code150-3or use the updated value of the BUSY code150-3to make a “new” decision to spin or yield. Additionally, new threads can begin competing for the resource200in between the instances when the second thread230read the BUSY code150-3and the updated BUSY code150-3. Thus, the new competing threads can also read the updated BUSY code150-3to make their own spin or yield decisions.

FIG. 4is a flowchart400of processing steps410-440performed by a busy resource encoder150to update a value of a variable corresponding to the resource200and indicating an availability of the resource200with respect to the progress of the execution of the first thread220according to embodiments herein. The steps in flowchart400refer to the features illustrated in the block diagrams ofFIGS. 1 and 2.

At410, the busy resource encoder150updates a value of a variable (used for the BUSY code150-3), the variable corresponding to the resource200and indicates an availability of the resource200with respect to the progress of the execution of the first thread220. In order to update the BUSY code150-3, at step420, the busy resource encoder150monitors execution of the first thread220in relation to use of the resource200. As a result of monitoring the execution of the first thread220, at step430, the busy resource encoder150produces at least one measure of completeness of the execution of the first thread220in the relation to use of the resource200. At step440, the busy resource encoder150changes the value of the variable (used for the BUSY code150-3) according to the measure of completeness of the execution of the first thread220in the relation to use of the resource200.

FIG. 5is a flowchart500of processing steps510-530performed by the busy resource encoder150to change a value of the variable corresponding to the resource200according to the measure of completeness of the execution of the first thread220in the relation to use of the resource200according to embodiments herein. The steps in flowchart500refer to the features illustrated in the block diagrams ofFIGS. 1 and 2. ForFIG. 5specifically, the order of the steps for flowchart500are arbitrary.

At step510, the busy resource encoder150assigns the variable (used for the BUSY code150-3) a predetermined yield value to indicate to the second thread230to initiate execution of the yield routine. The yield value can be predetermined by the busy resource encoder150and identified by any thread competing for use of the resource200. Upon reading the BUSY code150-3because the resource200is “locked out,” if the second thread230reads the BUSY code150-3as equal to the yield value, the second thread230“knows” that there is a very high probability that executing a yield routine is clearly the most profitable decision—as opposed to spinning.

At step520, the busy resource encoder150assigns the variable (used for the BUSY code150-3) a predetermined access value to indicate to the second thread230that the progress of the execution of the first thread220in relation to use of the resource200by the first thread220is complete and the resource200is unlocked and available to the second thread230. Similar to the predetermined yield value, the access value can be predetermined by the busy resource encoder150and identified by any thread competing for use of the resource200. As the first thread220is done using the resource200, it can progress its execution but release the resource200. Hence, the resource200can be unlocked and available to the second thread230(and/or other threads). The BUSY code150-3can equal the predetermined access value to signal to the second thread230that no decision to spin or yield is necessary, and instead the second thread230can utilize the “unlocked” resource200.

At step530, the busy resource encoder150assigns the variable (used for the BUSY code150-3) a spin value advises the second thread230(and any other competing thread) of a number of spin-loop cycles of the spin routine to be executed by the second thread230before attempting to read the BUSY code150-3again, the spin value based upon the measure of completeness. As the second thread230reads the BUSY code150-3, it is not necessarily relegated to only considering the BUSY code150-3as a determination to spin or yield is made. In some embodiments, the busy resource encoder150allows the second thread230(or any other thread competing for the resource200) to process the BUSY code150-3according to a consideration to variety of system and performance metrics, such as a machine state metric, a second thread metric, and a resource metric.

FIG. 6is a flowchart600of processing step610performed by a busy resource encoder150to read the BUSY code150-3to determine to execute one of a spin and a yield routine by the second thread230according to embodiments herein. The step of flowchart600refer to the features illustrated in the block diagrams ofFIGS. 1 and 2.

At step610, the busy resource encoder150compares the BUSY code150-3against a yield value defined for the second thread230. The yield value defined for the second thread230describes a condition to initiate execution of the yield routine by the second thread230despite the value of the BUSY code150-3. For example, the busy resource encoder150can provide a BUSY code150-3with a spin value to communicate to the second thread230a number of spin cycles to execute before the second thread230reads the BUSY code150-3again. However, if the second thread230has its own defined yield value, it can decide to yield instead of spin. Here the second thread's230yield value can describe a maximum spin cycle count. If the BUSY code150-3represents a spin value that is greater than the maximum spin cycle count (described by the second thread230's yield value), the spinning is not profitable for the second thread230—even though the BUSY code150-3does not equal the predetermined yield value of step510. Thus, even though the BUSY code150-3can “advise” threads to spin, some threads can still choose to yield based on the conditions described by their own yield values.

FIG. 7is a flowchart700of processing steps performed by a busy resource encoder150to read a BUSY code150-3to advise a thread to spin. At step710, a thread230attempting to use a resource200by reading the BUSY code150-3. At step720, if the resource200is available, the thread230can use the resource200at step730. If the resource200is not available, the thread230can decide whether to spin at step740. If spinning is not the most efficient choice, the thread230can yield at step750.

FIG. 8is a flowchart800of processing steps performed by a busy resource encoder150to read a BUSY code150-3to advise a thread to yield. At step810, a thread230attempting to use a resource200by reading the BUSY code150-3. At step820, if the resource200is available, the thread230can use the resource200at step830. If the resource200is not available, the thread230can decide whether to spin at step840. If spinning is not the most efficient choice, the thread230can yield at step850. Once the thread decides to yield, at860, it enters a queue to be notified when to read the BUSY code150-3again.

FIG. 9is a flowchart900of processing steps performed by a busy resource encoder150to change the advice given via the BUSY code150-3. It is understood that steps910-915have been previously described inFIGS. 7 and 8. At step920, when a thread220has been informed that a resource200is available, it can monitor the duration of use of the resource. At step925, if the thread's220use of the resource is for a long duration, the busy resource endcoder150can set the BUSY code150-3to “yield.” At step930, as the thread220uses the resource200, the BUSY code150-3can be changed to “spin” as the thread230nears termination of the its use of the resource200. At step940, competing threads can be notified that the thread220is almost done with the resource200since the BUSY code150-3is telling them to spin and not yield, as in step945.

At step950, the thread220is executing its short term usage of the resource200. However, if a delay occurs, and the thread220will unexpectedly be using the resource200for a longer period of time, the BUSY code150-3can be reset to “yield.” Nonetheless, at step955, once use of the resource200is complete, the busy resource encoder150sets the BUSY code150-3to “available,” thereby notifying any competing threads230that the resource is ready to be used by a new thread at step960.

Other embodiments disclosed herein include software programs to perform the steps and operations summarized above and disclosed in detail below. One such embodiment comprises a computer program product that has a computer-readable medium including computer program logic encoded thereon that, when performed in a computerized device having a coupling of a memory and a processor, programs the processor to perform the operations disclosed herein. Such arrangements are typically provided as software, code and/or other data (e.g., data structures) arranged or encoded on a computer readable medium such as an optical medium (e.g., CD-ROM), floppy or hard disk or other a medium such as firmware or microcode in one or more ROM or RAM or PROM chips or as an Application Specific Integrated Circuit (ASIC). The software or firmware or other such configurations can be installed onto a computerized device to cause the computerized device to perform the techniques explained as embodiments disclosed herein.

Note again that techniques herein are well suited for a busy resource encoder150to allow for a decision to be made regarding an expected contention for individual resources between one or more threads (i.e. processes, operations) by updating “busy” information as a contending operation progresses in its use of the resource. Specifically, a BUSY code150-3is used to provide information from the owner of the resource about when the resource is likely to be available. However, it should be noted that embodiments herein are not limited to use in such applications and that the techniques discussed herein are well suited for other applications as well. While this invention has been particularly shown and described with references to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present application as defined by the appended claims. Such variations are intended to be covered by the scope of this present application. As such, the foregoing description of embodiments of the present application is not intended to be limiting. Rather, any limitations to the invention are presented in the following claims.