Methods and apparatus for locking objects in a multi-threaded environment

TECHNICAL FIELD

0001The present disclosure relates in general to computers, and, in particular, to methods and apparatus for locking objects in a multi-threaded environment.

BACKGROUND

0002Programming languages that have built-in thread generating capability, for example JAVA and C# (C sharp), typically include a synchronization mechanism for coordinating thread access to an object. As will be appreciated by those of ordinary skill in the art, the term “thread” refers to a series of processor instructions running on behalf of a user or process, and is logically represented as one or more executing objects. An object is an instance of a class, where a class is a collection of data and methods to operate on the data. In the case of multiple threads of execution, care must be taken to prevent the multiple threads from modifying the same object simultaneously in a way that might leave the object's state corrupted. In particular, there may be critical sections of code or entire methods that must not be executed simultaneously by two or more threads. Thus, multithreaded systems typically provide specialized statements to protect these critical sections.

0003For example, JAVA provides the synchronized statement to protect critical sections of code from being executed simultaneously. Use of the synchronized statement enables acquisition of an exclusive lock of an object identified by the synchronized statement. Thus, a thread is not able to execute a critical section of code until it can obtain an exclusive lock on the corresponding object and once such a lock is obtained, no other thread can access the critical section of code. This protocol ensures that multiple threads cannot execute the critical section at the same time. Of course, application of the synchronized statement is generally used in cases where a particular program creates multiple threads to share data. If only one thread ever accesses a data structure, there is no need to protect it with a synchronized statement.

0004A synchronized statement in JAVA source code is normally converted to instructions in JAVA virtual machine (JVM) language, because, as is known in the art, JAVA source code is first compiled into bytecode (i.e., JVM language) prior to being interpreted into machine code by the JVM. A monitorenter instruction is provided in JVM language to gain an exclusive lock on an object. A monitorexit instruction is provided in JVM language to unlock the exclusive lock on the object. Accordingly, if a thread successfully executes the monitorenter instruction upon an object, that thread is considered to have gained temporary exclusive lock ownership of the object (i.e., it has gained a “lock” on the object to prevent other threads from accessing the critical sections of code). To signify that ownership, the thread's identifier appears in a specialized field associated with the object, for example, a “LockOwner” field in the object. If another thread, or second thread, attempts to execute the monitorenter instruction upon the same object, while the first thread has temporary exclusive ownership of the object, the second thread must wait (i.e., sleep) until the first thread (i.e., current lock owner) executes the monitorexit instruction to release its exclusive lock of the object.

0005The monitorenter instruction for a lock operation typically includes at least two steps. The first step, (referred to herein as the “checking” step), occurs when a thread attempting to gain an exclusive lock on a particular object checks a shared flag of the object. The shared flag indicates whether the object is currently locked by another thread. If the shared flag indicates that no other thread has an exclusive lock on the object (e.g., the shared flag indicates NULL), the thread attempting to gain the exclusive lock is free to perform the second step of “labeling” the object to claim lock ownership of the object. Labeling the object may be accomplished in any number of ways. For example, the shared flag may be altered to reflect the thread's identifier (e.g., a Thread_ID or a start address of the thread's runtime stack). Once labeled with that thread's identifier, the object is temporarily unavailable for locking by other threads.

0006However, in order for the monitorenter instruction to be effective, atomic execution of both of the lock operation steps is required to prevent possible race conditions from occurring (i.e., the labeling step must be performed immediately after the checking step by the same thread, and the two steps operate like one indivisible step.). If not atomically executed, a second thread may be able to interleave itself into the first thread's lock attempt by performing the checking step and erroneously determining that the object is available to be locked immediately after the first thread has performed the checking step. In other words, the second thread may be able to sneak-in before the first thread is able to complete the labeling step necessary to gain an exclusive lock on the object. Thus, atomic execution of the two lock operation steps prevents two threads from concurrently modifying data in a locked region represented by the same object, thereby precluding possible data corruption.

0007Although safe, prior art atomic execution of lock operation steps is expensive in terms of processor clock cycles. For example, the cycles spent in the execution of an atomic lock operation is, in some instances, equivalent to that of many other instructions, (e.g., execution of a few hundred add instructions).

BRIEF DESCRIPTION OF THE DRAWINGS

0008<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of an example computer system.

0009<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating an example implementation of a runtime system operating in the computer system of <figref idref="DRAWINGS">FIG. 1</figref>.

0010<figref idref="DRAWINGS">FIG. 3</figref> is block diagram of an example apparatus constructed in accordance with the teachings of the invention.

0011<figref idref="DRAWINGS">FIG. 3A</figref> is an example set of conditions enforced by the example apparatus of <figref idref="DRAWINGS">FIG. 3</figref>.

0012<figref idref="DRAWINGS">FIGS. 4–6</figref> are a flowchart illustrating an example locking program implementing the apparatus of <figref idref="DRAWINGS">FIG. 3</figref>.

0013<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart illustrating an example unlocking program implementing the apparatus of <figref idref="DRAWINGS">FIG. 3</figref>.

0014<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart illustrating another example unlocking program implementing in another way the apparatus of <figref idref="DRAWINGS">FIG. 3</figref>.

DETAILED DESCRIPTION

0015A block diagram of an example computer system <b>100</b> is illustrated in <figref idref="DRAWINGS">FIG. 1</figref>. The computer system <b>100</b> may be a personal computer (PC), a personal digital assistant (PDA), an Internet appliance, a portable radio telephone, a server, or any other computing device. In the illustrated example, the computer system <b>100</b> includes a main processing unit <b>102</b> powered by a power supply <b>103</b>. The main processing unit <b>102</b> includes one or more processors <b>104</b> electrically coupled by a system interconnect <b>106</b> to one or more memory device(s) <b>108</b>, and one or more interface circuits <b>110</b> electrically coupled to the processor(s) <b>104</b> via the system interconnect <b>106</b>. In the illustrated example, the system interconnect <b>106</b> is an address/data bus. Of course, a person of ordinary skill in the art will readily appreciate that interconnects other than busses may be used to connect the processor(s) <b>104</b> to the memory device(s) <b>108</b>. For example, one or more dedicated lines and/or a crossbar may be used to connect the processor(s) <b>104</b> to the memory device(s) <b>108</b>.

0016The processor(s) <b>104</b> may include any type of well known processor, such as a microprocessor from the Intel Pentium™ family of microprocessors, the Intel Itanium™ family of microprocessors, and/or the Intel XScale™ family of processors. The main memory device <b>108</b> includes a volatile memory such as a dynamic random access memory (DRAM), and also includes a non-volatile memory (e.g., a flash memory). In the illustrated example, the memory device(s) <b>108</b> store a software program which is executed by one or more of the processor(s) <b>104</b> in a well known manner.

0017The interface circuit(s) <b>110</b> may be implemented using any type of well known interface standard, such as an Ethernet interface and/or a Universal Serial Bus (USB) interface. One or more input devices <b>112</b> may be connected to the interface circuits <b>110</b> for entering data and commands into the main processing unit <b>102</b>. Example input devices <b>112</b> include a keyboard, mouse, touch screen, track pad, track ball, isopoint, and/or a voice recognition system.

0018One or more displays, printers, speakers, and/or other output devices <b>114</b> are also connected to the main processing unit <b>102</b> via one or more of the interface circuits <b>110</b>. The display <b>114</b> may be a cathode ray tube (CRTs), a liquid crystal display (LCDs), or any other type of display. The display <b>114</b> generates visual indications of data generated during operation of the main processing unit <b>102</b>. The visual displays may include prompts for human operator input, calculated values, detected data, etc.

0019The computer system <b>100</b> also includes one or more storage devices <b>116</b>. For example, the computer system <b>100</b> may include one or more hard drives, a compact disk (CD) drive, a digital versatile disk drive (DVD), and/or other computer media input/output (I/O) devices.

0020The computer system <b>100</b> also exchanges data with other devices via a connection to a network <b>118</b>. The network connection may be any type of network connection, such as an Ethernet connection, digital subscriber line (DSL), telephone line, coaxial cable, etc. The network <b>118</b> may be any type of network, such as the Internet, a telephone network, a cable network, and/or a wireless network.

0021A block diagram of an example runtime system <b>200</b> operating in the computer system <b>100</b> is illustrated in <figref idref="DRAWINGS">FIG. 2</figref>. The runtime system <b>200</b> is hardware and operating system independent and may therefore be embedded in various products such as web browsers, servers, etc. As illustrated in <figref idref="DRAWINGS">FIG. 2</figref>, the example runtime system <b>200</b> includes a Virtual Machine (VM) <b>202</b> (i.e., a software program that converts bytecode, or platform independent code, into specific processor readable instructions), and an operating system program (OS) <b>204</b> (e.g., a software program such as Windows XP™ which manages other application programs in the computer system <b>100</b>). Implementation of the VM <b>202</b> may be achieved in any number of ways, for example, by an Open Runtime Platform™ (ORP) available from Intel.

0022In the case of an ORP implementation, the VM <b>202</b> preferably includes, inter alia, a Just-In-Time compiler (JIT compiler) <b>206</b> for dynamically compiling the bytecode into processor-specific executable code (as an alternative to interpreting one bytecode instruction at a time). As will be appreciated by those of ordinary skill in the art, the JIT compiler <b>206</b> and the OS <b>204</b> are typically software programs in the form of processor instructions running on the processor <b>104</b>.

0023The VM <b>202</b> may be configured in any number of ways to translate class files into processor instructions. For example, the VM <b>202</b> may be configured as a JAVA virtual machine (JVM) for compiling JAVA bytecode class files (previously compiled from JAVA source code) into machine readable instructions suitable for use by the processor(s) <b>104</b>. The VM <b>202</b> may also be configured as a common language runtime (CLR) platform for compiling C# bytecode portable executable (PE) files into machine readable instructions suitable for use by processor(s) <b>104</b>.

0024As is known, virtual machine operation requires bytecode input. Thus, application source code is first compiled into bytecode prior to re-compilation into processor executable instructions. Thus, for JAVA applications such as SPECjvm98 or SPECjbb2000, the JAVA source code is first compiled into JAVA bytecode (i.e., classfiles) by a JAVA compiler <b>210</b>. Then, upon request by a user (e.g., the runtime platform <b>202</b>), the JAVA bytecode, or JAVA virtual machine instructions, are compiled by the JIT compiler <b>206</b> into processor instructions (i.e., machine code adapted for the particular processor <b>104</b>).

0025As previously mentioned, a thread, or thread of execution, is an instance of a software module running on behalf of a user or process. In the illustrated example, three threads <b>220</b>, <b>222</b>, <b>224</b> are shown, although more or less threads are possible. Scheduling of thread execution on the processor(s) <b>104</b> is performed by the operating system <b>204</b>. In addition, threads of execution such as JAVA threads are implemented by, and operate with, “objects” (i.e., software logical entities that represent the basic building blocks of the program). As is known, each object has associated methods to provide computer instructions and class object characteristics to provide relevant data during execution of the object. For example, a method in one object may call-up a second method in the same or a different object, which may call-up a third method, and so on. Such a chain of calling-up methods provides the basis of thread execution.

0026A multi-threaded process has multiple threads, with each thread executing independently. Each thread may execute on separate processors <b>104</b> (if multiple processors <b>104</b> are available) of the computer system <b>100</b>. For example, in a Graphic User Interface (GUI) based network application such as a Web browser, a user could be listening to an audio clip (provided by a first thread) while scrolling a page (provided by a second thread), and, in the background, the browser could be downloading an image (provided by a third thread). Of course, a multi-threaded program, if running in parallel on a computer system with multiple processors <b>104</b>, will typically run much faster than a multi-threaded program running on a single processor.

0027When executing on processor(s) <b>104</b>, multiple threads such as threads <b>220</b>, <b>222</b>, <b>224</b>, may wish to simultaneously execute the same critical section of code of an object (i.e., a section of code that must not be executed simultaneously by multiple threads). In order to gain access to the critical section of code, a thread must gain exclusive temporary ownership of the object to prevent other threads from simultaneously executing the same critical section of code. Exclusive temporary ownership by a thread of an object is typically gained via execution of a lock instruction, for example, the monitorenter instruction provided in the JVM language. Similarly, the release of exclusive temporary ownership by a thread is typically achieved via execution of an unlock instruction, for example, the monitorexit instruction provided in the JVM language.

0028Execution of either the lock instruction or the unlock instruction causes multiple steps to be performed by a thread. For example, the lock instruction requires the thread to first check a lock status flag of the object (i.e., the checking step). Then, upon determining that the object is not currently locked by another thread, the lock instruction requires the thread to alter the lock status flag by inserting its thread identification number into the flag field (i.e., the labeling step) to indicate to other threads that the object is currently locked and, therefore, unavailable for execution by those other threads.

0029However, in order to prevent a race condition from occurring, the conventional steps of checking and labeling must be performed sequentially by one thread without interruption, or “interleaving,” from another thread. In runtime systems such as the VM <b>202</b>, a method known as “atomic execution” is typically used to prevent interleaving and thereby allow one thread to complete the multiple steps of locking without interruption by another thread. Atomic execution of multiple steps may be achieved in any number of ways. For example, in the case of 32 bit Intel Architecture (IA-32), ensuring atomic execution of a lock operation may be accomplished via the addition of the prefix lock to the processor instruction that is required for the lock operation (e.g., cmpxchg).

0030Safe, atomic execution of the multiple steps required for the lock operation is expensive in terms of processor clock cycles. For example, execution of one lock cmpxchg instruction is equivalent to execution of a few hundred add instructions when using the Intel IA-32 platform. Thus, in the prior art, each thread requires consumption of a relatively substantially large amount of processor clock cycles each time it locks an object. Further, in many cases, because the same thread may sequentially lock and unlock the same object thousands of times before another thread attempts to lock the same object, processor clock cycles are needlessly wasted by unnecessary atomic execution of the locking steps. Accordingly, the safety factor (with respect to race conditions) afforded by atomic execution may result in unnecessary and excessive consumption of valuable processor resources.

0031An example high performance object lock apparatus <b>300</b> is illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. The high performance object lock apparatus <b>300</b> prevents race conditions during a multi-step lock or unlock operation while more efficiently utilizing processor resources. In the illustrated example, the high performance object lock apparatus <b>300</b> interacts with one or more threads, (e.g., the threads <b>220</b>, <b>222</b>) and an object <b>302</b>. The apparatus <b>300</b> includes an object owner controller <b>306</b>, a lock owner controller <b>310</b>, and a flag controller <b>314</b>. In addition, each thread <b>220</b>, <b>222</b> includes an associated thread identifier <b>304</b>. Further, each object <b>302</b> associated with critical code that is subject to exclusive ownership includes an ObjectOwner field <b>308</b>, a LockOwner field <b>312</b>, a Flag <b>1</b> field <b>316</b>, and a Flag <b>2</b> field <b>320</b>.

0032In the illustrated example, the object owner controller <b>306</b>, the lock owner controller <b>310</b>, and the flag controller <b>314</b> are implemented as software stored on a tangible medium such as a CD-ROM, a floppy disk, a hard drive, a digital versatile disk (DVD), or a memory, but persons of ordinary skill in the art will readily appreciate that one or more of the object owner controller <b>306</b>, the lock owner controller <b>310</b>, and the flag controller <b>314</b> could alternatively be implemented by hardware and/or firmware in a well known manner.

0033Fixed Object Owner—Private Lock

0034Implementation of the illustrated apparatus <b>300</b> decreases the overall number of atomic executions required to lock a particular object (thus decreasing the number of processor clock cycles required to execute the methods of the object) because, in the case where a thread seeking to access an object is already the particular object's “owner,” no atomic execution is required to lock the object. This decrease in the overall number of atomic executions is achieved via the addition of one or more modifiable fields in the object, for example, the addition of the ObjectOwner field <b>308</b>, the Flag <b>1</b> field <b>316</b>, the Flag <b>2</b> field <b>320</b>, and the addition of an associated set of conditions or rules for accessing objects (discussed below) enforced by the apparatus <b>300</b>.

0035For example, when a thread <b>220</b> having a thread identifier <b>304</b> (e.g., Thread_A), attempts to execute a critical section of code of the object <b>302</b>, the lock owner controller <b>310</b> of the apparatus <b>300</b> first checks the LockOwner field <b>312</b> to determine if the object <b>302</b> is available for locking. If the object <b>302</b> is available for locking, the object owner controller <b>306</b> of the apparatus <b>300</b> checks the ObjectOwner field <b>308</b> to determine if the object <b>302</b> has an object owner (discussed below), and if applicable, which thread owns the object. If the object <b>302</b> is available for locking, and if the requesting thread <b>220</b> is the “object owner” of the object <b>302</b>, manipulation of the LockOwner field <b>312</b> by the lock owner controller <b>310</b>, and manipulation of the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> by the flag controller <b>314</b>, allows the thread <b>220</b> to lock the object, execute the critical section of code, and then unlock the object without atomically performing the locking steps. In other words, the addition of the ObjectOwner field <b>308</b>, the Flag <b>1</b> field <b>316</b>, the Flag <b>2</b> field <b>320</b> and enforcement of a set of conditions by the apparatus <b>300</b>, enables execution of intermediate instructions between checking the object's availability and labeling the object.

0036Establishment of an object owner may be accomplished in any number of ways. In an example, the object owner is defined to be the first thread to lock the object <b>302</b>. The object owner is identified by storing the thread identifier <b>304</b> of the object owner in the ObjectOwner field <b>308</b> of the object <b>302</b>. Thus, if the thread <b>220</b> is the first to lock the object <b>302</b>, the thread identifier <b>304</b> of the thread <b>220</b> (e.g., Thread_A), is written in the ObjectOwner field <b>308</b>. Similarly, if the thread <b>222</b> is the first to lock the object <b>302</b>, the thread identifier <b>304</b> of the thread <b>222</b> (e.g., Thread_B), is written in the LockOwner field <b>312</b>.

0037<figref idref="DRAWINGS">FIG. 3A</figref> is an example set of conditions, herein referred to as a condition table <b>340</b>, that, when enforced by the apparatus <b>300</b>, eliminates the need for atomic execution during the locking process in a case where a thread seeking to lock the object <b>302</b> (e.g., a requesting thread <b>220</b>) is already the established “object owner” of the object <b>302</b>. As will be appreciated by persons of ordinary skill in the art, the condition table <b>340</b> may be configured in any number of ways to achieve safe locking and unlocking of the object <b>302</b> while reducing consumption of processor resources.

0038Referring to <figref idref="DRAWINGS">FIG. 3A</figref>, the illustrated object status table <b>340</b> includes a Flag<b>1</b> field column <b>342</b>, a Flag<b>2</b> field column <b>344</b>, and a status field column <b>346</b> resulting from the conjunction of the Flag<b>1</b> and Flag<b>2</b> field column <b>342</b>, <b>344</b>. The binary values (i.e., 1 or 0) in the Flag<b>1</b> field column <b>342</b> and the Flag<b>2</b> field column <b>344</b> indicate to the apparatus <b>300</b> whether safe locking and unlocking of the object <b>302</b> can be achieved.

0039For example, if the Flag<b>1</b> field <b>316</b> and Flag<b>2</b> field <b>320</b> both contain the binary value zero, the object <b>302</b> has not yet been locked by any object. If the Flag<b>1</b> field <b>316</b> and Flag<b>2</b> field <b>320</b> contain the binary values zero and one, respectively, the object <b>302</b> is currently locked by a thread other than the object owner and, thus, is not available to be safely locked. If the Flag<b>1</b> field <b>316</b> and Flag<b>2</b> field <b>320</b> contain the binary values one and zero, respectively, the object <b>302</b> is locked by the object owner. Lastly, if the Flag<b>1</b> field <b>316</b> and Flag<b>2</b> field <b>320</b> both contain the binary value one, the object <b>302</b> is unlocked.

0040If the object <b>302</b> does not have an object owner (i.e., no thread identifier <b>304</b> appears in the ObjectOwner field <b>308</b> of the object <b>302</b>), the object <b>302</b> has not yet been locked, and the binary value zero is in both the Flag <b>1</b> field <b>316</b> and the Flag <b>2</b> field <b>320</b>.

0041<figref idref="DRAWINGS">FIGS. 4–6</figref> are a flowchart illustrating an example software program implementing the apparatus of <figref idref="DRAWINGS">FIG. 3</figref>. The software program is stored on a tangible medium such as the memory <b>108</b> and is referred to herein as a fixed object owner high performance object lock method <b>400</b>. Although the example program is described with reference to the flowchart illustrated in <figref idref="DRAWINGS">FIGS. 4–6</figref>, persons of ordinary skill in the art will readily appreciate that other methods of performing the fixed object owner high performance object lock method <b>400</b> are contemplated. For example, the blocks may be changed, the order of execution of the blocks may be changed, and/or blocks may be eliminated.

0042Owner Thread=Null

0043Referring to <figref idref="DRAWINGS">FIG. 4</figref>, the example high performance object lock method <b>400</b> is invoked when a thread (e.g., thread <b>220</b>) attempts to obtain temporary lock ownership of an object (e.g., object <b>302</b>). In response to such an attempt, the lock owner controller <b>310</b> determines if the object <b>302</b> is available for locking (i.e., Flags <b>1</b> and <b>2</b> are both set to “0” or both set to “1”) (block <b>402</b>).

0044If the object is unavailable for locking, control proceeds to block <b>422</b> because the lock owner controller <b>310</b> assumes that a thread other than the requesting thread (e.g., thread <b>222</b>) has achieved a lock on the object and instructs the thread <b>220</b> to wait until the other thread unlocks the object <b>302</b> (block <b>422</b>). After a predetermined waiting period, the lock owner controller <b>310</b> again determines if the object <b>302</b> is available for locking (block <b>402</b>). If the object <b>302</b> is available for locking (block <b>402</b>), the object owner controller <b>306</b> determines if the object <b>302</b> has an object owner by checking the ObjectOwner field <b>308</b> for a thread identifier <b>304</b> (block <b>404</b>).

0045If the object owner controller <b>306</b> determines that there is no thread identifier in the ObjectOwner field <b>308</b>, the object <b>302</b> has not been previously accessed by any thread. Thus, if there is no thread identifier in the ObjectOwner field <b>308</b> (block <b>404</b>, <figref idref="DRAWINGS">FIG. 4</figref>), the object owner controller <b>306</b> re-verifies that there is no thread identifier in the ObjectOwner field <b>308</b> (block <b>406</b>). This verification is performed to ensure no other thread has obtained ownership of the object. If the ObjectOwner field <b>308</b> is no longer a null (block <b>406</b>), control proceeds to block <b>422</b> where the requesting thread enters a wait state as explained above. Otherwise, control proceeds to block <b>408</b>.

0046At block <b>408</b>, the flag controller <b>314</b> checks the Flag<b>1</b> field <b>316</b>. If the Flag<b>1</b> field <b>316</b> is not set to zero, control proceeds to block <b>422</b>. If the Flag<b>1</b> field <b>316</b> is set to zero (block <b>408</b>), the flag controller <b>314</b> checks the Flag<b>2</b> field <b>320</b>. If the Flag<b>2</b> field <b>320</b> is not set to zero, control proceeds to block <b>422</b>. Otherwise, the flag controller <b>314</b> sets the Flag<b>1</b> field <b>316</b> to logic 1 and the object owner controller <b>306</b> writes the thread identifier <b>304</b> of the requesting thread in the ObjectOwner field <b>308</b> (block <b>412</b>). As symbolically indicated by block <b>405</b>, all of blocks <b>406</b>–<b>412</b> are performed via an atomic execution.

0047Upon completion of the atomic execution <b>405</b>, the flag controller <b>314</b> again accesses the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> to ensure that they have remained set to one and zero, respectively (block <b>414</b>). Rechecking the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> ensures that another thread has not interleaved. This rechecking is performed because the atomic operation may succeed or fail. It fails when any of the checked conditions are not satisfied. If the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are no longer set to one and zero, respectively (block <b>414</b>), the flag controller <b>314</b> assumes that another thread such as thread <b>222</b> has a lock on the object <b>302</b>, and instructs the thread <b>220</b> to wait (block <b>422</b>) until the other thread unlocks the object <b>302</b>. Again, the lock owner controller <b>310</b> reinitiates the process of checking if the object <b>302</b> is available to lock (block <b>402</b>) after passing of a predetermined time period (block <b>422</b>).

0048On the other hand, if the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are still set to one and zero, respectively (block <b>414</b>), then the lock owner controller <b>310</b> inserts the thread identifier <b>304</b> of the requesting thread <b>220</b> into the LockOwner field <b>312</b> to label the object thereby indicating to other threads that thread <b>220</b> has a lock on the object <b>302</b> (block <b>416</b>).

0049After insertion of the thread identifier <b>304</b> into the LockOwner field <b>312</b> (block <b>416</b>), the requesting thread <b>220</b> executes the critical section of code of the object <b>302</b> (block <b>418</b>). Thus, during execution of the critical section of code of the object <b>302</b>, the thread identifier <b>304</b> is reflected in the LockOwner field <b>312</b> and the ObjectOwner field <b>308</b>, and the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are set to one and zero, respectively, as shown in <figref idref="DRAWINGS">FIG. 4</figref>

0050After execution of the critical section of code of the object <b>302</b> is completed and unlocking of the object <b>302</b> is desired (block <b>420</b>), control proceeds to an unlocking process <b>500</b> explained below (<figref idref="DRAWINGS">FIG. 7</figref>).

0051Owner Thread=Self

0052Returning to the decision block <b>404</b> (<figref idref="DRAWINGS">FIG. 4</figref>), if the object owner controller <b>306</b> determines that there is an object owner of the object <b>302</b> (i.e., a thread identifier <b>304</b> appears in the ObjectOwner field <b>308</b>), control proceeds to <figref idref="DRAWINGS">FIG. 5</figref> where the lock owner controller <b>312</b> reconfirms the object <b>302</b> is available to lock (block <b>403</b>). If the object is still available to lock (block <b>403</b>), the object owner controller <b>306</b> determines if the thread identifier <b>304</b> of the thread seeking to access the object <b>302</b> appears in the ObjectOwner field <b>308</b> (<figref idref="DRAWINGS">FIG. 5</figref>, block <b>426</b>). If the thread <b>220</b> is the object owner of the object <b>302</b> (e.g., thread <b>220</b> was the first thread to lock the object <b>302</b>), the thread identifier <b>304</b> of the thread <b>220</b> (e.g., Thread_A), will have been previously written in the ObjectOwner field <b>308</b>, and will be identified by the object owner controller <b>306</b>.

0053If the object owner controller <b>306</b> determines that the thread identifier <b>304</b> of the thread <b>220</b> seeking to access the object <b>302</b> (in this example, Thread_A) is already stored in the ObjectOwner field <b>308</b> (thereby indicating that the thread <b>220</b> is the-object owner), the flag controller <b>314</b> examines the status of the Flag <b>1</b> field <b>316</b> (block <b>428</b>). If the Flag <b>1</b> field <b>316</b> of the object being accessed (e.g., object <b>302</b>) indicates that the flag <b>1</b> is set to zero, the flag controller <b>314</b> assumes that another thread such as thread <b>222</b> has a lock on the object <b>302</b> and instructs thread <b>220</b> to wait (block <b>422</b>) until the other thread unlocks the object <b>302</b>. (As previously noted, the lock owner controller <b>310</b> reinitiates the process of determining if the object is available for locking (block <b>402</b>) after a predetermined length of time has expired. If the Flag <b>1</b> field <b>316</b> indicates that the flag <b>1</b> is set to one, the flag controller <b>314</b> sets the Flag <b>2</b> field <b>320</b> to zero (block <b>430</b>).

0054After setting the Flag <b>2</b> field <b>320</b> to zero (block <b>432</b>), the flag controller <b>314</b> again accesses the Flag <b>1</b> field <b>316</b> to ensure that it has remained set to one (block <b>432</b>). Rechecking the Flag <b>1</b> field <b>316</b> a second time ensures that another thread (e.g., thread <b>222</b>) has not interleaved. If the Flag <b>1</b> field <b>316</b> is no longer set to one (block <b>432</b>), the thread <b>220</b> must wait as explained above (block <b>422</b>). If the Flag <b>1</b> field <b>316</b> is set to one (block <b>432</b>), then the lock owner controller <b>310</b> inserts the thread identifier <b>304</b> of the thread requesting access to the object <b>302</b> (e.g., thread <b>220</b>) into the LockOwner field <b>312</b> (block <b>434</b>) thereby indicating to other threads that the thread <b>220</b> has a lock on the object <b>302</b>. It should be emphasized that blocks <b>403</b> and <b>426</b>–<b>434</b> did not involve an atomic execution. On the contrary, if a thread is the object owner of the object <b>302</b>, that object owner thread can repeatedly lock the object <b>302</b> without the use of an atomic execution, thereby more efficiently utilizing valuable processor resources.

0055After insertion of the thread identifier <b>304</b> (i.e., Thread_A) into the LockOwner field <b>312</b> (block <b>434</b>), the requesting thread <b>220</b> executes the critical section of code in the object <b>302</b> (block <b>436</b>). Thus, during execution of the critical section of code in the object <b>302</b>, the thread identifier <b>304</b> of “Thread_A” is reflected in the ObjectOwner field <b>308</b> and the LockOwner field <b>308</b>, and the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are set to one and zero, respectively, as shown in <figref idref="DRAWINGS">FIG. 5</figref>. As a result of the thread identifier <b>304</b> (Thread_A) appearing in the LockOwner field <b>308</b> and the states of the Flag<b>1</b> and Flag<b>2</b> fields <b>312</b>, <b>320</b> being 1, and 0, respectively, during execution of the critical section of code in the object <b>302</b>, other threads (e.g., thread <b>222</b>) are prevented from locking the object <b>302</b> even though an atomic operation is not being employed. In this way, when a thread seeking to lock an available object <b>302</b> is the object owner, locking of the object <b>302</b> is accomplished by setting the Flag<b>2</b> field <b>320</b> to zero (block <b>432</b>) and writing the object owner's thread identifies in the LockOwner field <b>312</b> without requiring an atomic operation.

0056After execution of the critical section of code of the object <b>302</b> is completed and unlocking of the object <b>302</b> is desired (block <b>438</b>), control proceeds to the unlocking process <b>500</b> discussed below in connection with <figref idref="DRAWINGS">FIG. 7</figref>.

0057Owner Thread=Another

0058Returning to decision block <b>426</b> (<figref idref="DRAWINGS">FIG. 5</figref>), if the object owner controller <b>306</b> determines that the thread identifier <b>304</b> in the ObjectOwner field <b>308</b> is not the thread identifier <b>308</b> of the requesting thread (i.e., the requesting thread <b>220</b> is not the object owner), control proceeds to block <b>440</b> of <figref idref="DRAWINGS">FIG. 6</figref>. Referring to <figref idref="DRAWINGS">FIG. 6</figref>, if the object owner controller <b>306</b> determines that the ObjectOwner field <b>308</b> is empty or the ObjectOwner field <b>308</b> contains the thread identifier of the requesting thread (block <b>440</b>), control returns to block <b>402</b> (<figref idref="DRAWINGS">FIG. 4</figref>). If, however, the object owner controller <b>306</b> determines that the object <b>302</b> is owned by a thread other than the requesting thread (i.e., the ObjectOwner field <b>308</b> contains the thread identifier <b>304</b> of “Thread_B,” indicating ownership by thread <b>222</b>) (block <b>440</b>), the flag controller <b>314</b> checks and sets the Flag <b>1</b> and <b>2</b> fields <b>316</b>, <b>320</b> via an atomic execution (block <b>441</b>). Specifically, the flag controller <b>314</b> determines if the Flag <b>1</b> field <b>316</b> is set to one (block <b>442</b>). If the flag controller <b>314</b> determines that the Flag <b>1</b> field <b>316</b> is set to zero, the flag controller <b>314</b> assumes that another thread (such as the thread <b>222</b>) has a lock on the object <b>302</b>. Therefore, the requesting thread <b>220</b> is instructed to wait (block <b>422</b>) until the lock is released as explained above. As shown in <figref idref="DRAWINGS">FIG. 6</figref>, the object owner controller <b>306</b> reinitiates the lock process (block <b>402</b>) after a predetermined length of time has expired (block <b>440</b>).

0059If the flag controller <b>314</b> determines that the Flag <b>1</b> field <b>316</b> is set to one, it checks the Flag <b>2</b> field <b>320</b> to determine if it is set to one (block <b>444</b>). If the Flag <b>1</b> field <b>316</b> is set to one, but the Flag <b>2</b> field <b>320</b> is set to zero (block <b>444</b>), then the flag controller <b>314</b> assumes that a thread other than the requesting thread (such as thread <b>222</b>) has a lock on the object <b>302</b>. Therefore, the thread <b>220</b> is instructed to wait until the other thread unlocks the object <b>302</b> (block <b>422</b>). If the Flag <b>1</b> field <b>316</b> is set to one and the Flag <b>2</b> field <b>320</b> is set to one (block <b>444</b>), then the flag controller <b>314</b> sets the Flag <b>1</b> field <b>316</b> to zero (block <b>446</b>), thereby completing the atomic execution <b>441</b>.

0060After setting the Flag <b>1</b> field <b>316</b> to zero (block <b>446</b>), the flag controller <b>314</b> reassesses the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> to ensure that they have remained set to zero and one, respectively (block <b>448</b>). Rechecking the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> ensures that another thread has not interleaved. If the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are no longer set to zero and one, respectively (block <b>448</b>), the flag controller <b>314</b> assumes that another thread such as the thread <b>222</b> has a lock on the object <b>302</b> and instructs the thread <b>220</b> to wait (block <b>422</b>) until the other thread <b>222</b> unlocks the object <b>302</b>. (As explained above, control proceeds from block <b>422</b> to block <b>440</b> after a predetermined length of time). If the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are set to zero and one, respectively (block <b>448</b>), then the lock owner controller <b>314</b> inserts the thread identifier <b>304</b> of the requesting thread <b>220</b> (e.g., Thread_A) into the LockOwner field <b>312</b> of the object <b>302</b> thereby indicating to other threads that thread <b>220</b> has a lock on the object <b>302</b> (block <b>450</b>).

0061After insertion of the thread identifier <b>304</b> of the requesting thread <b>220</b> (e.g., Thread_A) into the LockOwner field <b>312</b> (block <b>450</b>), the requesting thread <b>220</b> executes the critical section of the code of the object <b>302</b> (block <b>452</b>). Thus, during execution of the critical section of code of the object <b>302</b> (block <b>452</b>), the thread identifier of another thread (e.g., Thread_B of thread <b>222</b>) is reflected in the object owner field <b>308</b> of the object <b>302</b>, while the thread identifier of the executing thread (e.g., Thread_A of thread <b>220</b>) is reflected in the LockOwner field <b>308</b>, and the Flag <b>1</b> and 2 fields <b>316</b>, <b>320</b> are set to zero and one respectively, as shown in <figref idref="DRAWINGS">FIG. 6</figref>.

0062After execution of the critical section of code of the object <b>302</b> is completed and unlocking of the object <b>302</b> is desired (block <b>454</b>), control proceeds to an unlocking process <b>500</b> such as that described below in connection with <figref idref="DRAWINGS">FIG. 7</figref>.

0063Unlocking Object Locked by One of the Above 3 Scenarios

0064In all three locking scenarios—when the ObjectOwner field <b>308</b> reflects the thread identity of: (1) the thread seeking to lock the object, (2) a thread other than the thread seeking to lock the object, or (3) no thread (indicating that no thread has previously accessed the object) the Flag <b>1</b> and Flag <b>2</b> fields are set to an appropriate lock configuration and the LockOwner field <b>312</b> reflects the thread identity of the current thread performing execution of the object <b>302</b>. Referring to <figref idref="DRAWINGS">FIG. 7</figref>, a process <b>500</b> for unlocking is initiated when the thread holding the lock wishes to “unlock” the object <b>302</b>, thereby making it available to other threads.

0065In particular, the process <b>500</b> begins when the lock owner controller <b>310</b> determines whether the thread identifier currently in the LockOwner field <b>312</b> is the thread identifier of the thread seeking to unlock the object (block <b>470</b>). If the lock owner controller <b>310</b> determines that the thread identifier of the thread seeking to unlock the object <b>302</b> is not currently in the LockOwner field <b>312</b>, an exception, or error, is generated (block <b>471</b>). Generation of the exception may cause the application to cease thread execution and to initiate error code handling execution, or may cause the application to abort all execution. If the lock owner controller <b>310</b> determines that the thread identifier of the thread seeking to unlock the object <b>302</b> is currently in the LockOwner field <b>312</b>, the flag controller <b>314</b> sets both the Flag<b>1</b> field <b>316</b> and the Flag<b>2</b> field <b>320</b> to one (blocks <b>474</b> and <b>478</b>). The lock owner controller <b>310</b> then removes the thread identifier <b>304</b> (e.g., Thread_A) from the LockOwner field <b>312</b> (block <b>480</b>). Thus, after unlocking, both the Flag <b>1</b> and Flag <b>2</b> fields <b>316</b>, <b>320</b> are set to one and the lock owner field <b>312</b> is empty. The object <b>302</b> is then available for locking by any thread <b>220</b>.

0066In summary, implementation of the illustrated fixed owner object high performance lock method <b>400</b> reduces the number of times atomic execution is required for locking the object <b>302</b>. In particular, if the thread identifier <b>304</b> reflected in the ObjectOwner field <b>308</b> is the same as the thread identifier <b>304</b> of the thread <b>220</b> wishing to lock the object <b>302</b>, then no atomic execution is required during the locking operation. Thus, in practical applications such as SPECjvm98 and SPECjbb200, because the object owner thread typically locks an “owned” object many times during thread execution, significant processor performance improvements are achieved. In other words, the lock owner controller <b>310</b> and the flag controller <b>314</b> together comprise a lock identifier that determines that, in circumstances such as when the same thread repeatedly locks and unlocks an object <b>302</b>, atomic execution can be dispensed with.

0067Floating Object Owner

0068The apparatus of <figref idref="DRAWINGS">FIG. 3</figref> can be implemented to further reduce the number of atomic operations associated with locking the object <b>302</b> by utilizing “floating” object ownership. <figref idref="DRAWINGS">FIG. 8</figref> is a flowchart illustrating a software program to implement the apparatus of <figref idref="DRAWINGS">FIG. 3</figref> using this alternate approach. The software program is stored on a tangible medium such as the memory <b>108</b> and is referred to herein as a floating object owner high performance object unlock method <b>600</b>. Although the example program is described with reference to the flowchart illustrated in <figref idref="DRAWINGS">FIG. 8</figref>, persons of ordinary skill in the art will readily appreciate that other methods of performing the floating object owner unlock method <b>600</b> are contemplated. For example, the blocks may be changed, the blocks may be performed in a different order, and/or blocks may be eliminated.

0069Implementation of the floating object owner unlock method <b>600</b> allows object ownership to “float”, which contrasts with the example method <b>400</b> of <figref idref="DRAWINGS">FIGS. 4–7</figref> where object ownership was permanently assigned to the first thread to lock the object. Floating ownership decreases the overall number of atomic executions required to lock a particular object (thus decreasing the number of processor cycles) because, in the case where a thread is the object's owner, no atomic execution is required to lock the object. Since different threads can become an object's owner, the incidence of threads locking objects they own increase with the floating ownership approach.

0070The floating object owner unlock method <b>600</b> reassigns object ownership during the object unlocking process (i.e., after completion of object locking and execution of the critical section of code). Therefore, if the same thread repeatedly locks, executes and unlocks the same object without interruption, atomic execution is unnecessary after completion of the first lock/execution/unlock cycle, resulting in considerable processor clock cycle savings. In other words, after the first lock/execution/unlock cycle, repeated locking of an object by the same thread is performed by executing the process of <figref idref="DRAWINGS">FIG. 5</figref> (i.e., object owner=self) which does not require atomic execution.

0071More specifically, when a thread <b>220</b> has completed execution of a critical section of code of an object having an object owner other the current thread (block <b>454</b>, <figref idref="DRAWINGS">FIG. 6</figref>), the thread <b>220</b> can become the new object owner via execution of the floating object owner unlock method <b>600</b>. Upon becoming the object owner of the object <b>302</b>, the thread <b>220</b> can perform subsequent locking operations without atomic execution as shown in <figref idref="DRAWINGS">FIG. 5</figref> until another thread such as thread <b>222</b> locks the object.

0072Referring to <figref idref="DRAWINGS">FIG. 8</figref>, the floating object owner unlock method <b>600</b> begins when the lock owner controller <b>310</b> verifies that the thread identifier (e.g., Thread_A) of the thread that just executed the critical code is identified in the LockOwner field <b>312</b> (block <b>604</b>). If the thread identifier <b>304</b> of the thread that just executed the critical code is not in the LockOwner field <b>312</b>, an exception is generated (block <b>606</b>) as was the case with respect to block <b>471</b> of <figref idref="DRAWINGS">FIG. 7</figref>. If the thread identifier <b>304</b> of the thread that just executed the critical code is in the LockOwner field <b>312</b> (block <b>604</b>), the object owner controller <b>306</b> determines if the thread identifier in the ObjectOwner field <b>308</b> is the thread identifier of the current locking thread (e.g., Thread_A) (block <b>608</b>). If the thread identifier of the currently locking thread is in the ObjectOwner field <b>308</b> (block <b>604</b>), the lock owner controller <b>310</b> removes the thread identifier from the LockOwner field <b>312</b> (block <b>612</b>), and the object becomes available for locking by the same or another thread in accordance with the process shown in <figref idref="DRAWINGS">FIGS. 5</figref> and/or <b>6</b>.

0073If the thread identifier in the ObjectOwner field <b>308</b> is not the thread identifier of the current locking thread (block <b>608</b>), then the object owner controller <b>306</b> replaces the thread identifier <b>324</b> in the ObjectOwner field <b>308</b> with the thread identifier <b>304</b> of the current locking thread (block <b>610</b>). The lock owner controller <b>310</b> then removes the thread identifier from the LockOwner field <b>312</b> (block <b>612</b>), making the object available for locking by the same or another thread. In this way, object ownership “floats” to the thread that most recently locked the object <b>302</b> thereby resulting in overall savings in the number of atomic executions required during the lifetime of the object. Although the object <b>302</b> (<figref idref="DRAWINGS">FIG. 3</figref>) is used to illustrate the floating object owner unlock method <b>600</b>, objects having other structures may be locked via the floating object owner unlock method <b>600</b>.

0074In summary, persons of ordinary skill in the art will readily appreciate that methods and apparatus for locking objects in a multi-threaded environment have been disclosed herein. The example methods and apparatus disclosed herein reduce atomic execution of objects and, therefore, achieve significant processor performance improvements.

0075Although certain apparatus and methods have been described herein, the scope of coverage of this patent is not limited thereto. On the contrary, this patent covers all embodiments of the teachings of the invention fairly falling within the scope of the appended claims either literally or under the doctrine of equivalents.