System and method for synchronizing access to shared variables in a virtual machine in a digital computer system

• US 6,141,794 A
• Filed: 10/16/1998
• Issued: 10/31/2000
• Est. Priority Date: 10/16/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Vandette, Robert G., Dice, David, Mann, Ronald J.
• Primary Examiner(s): Chaki, Kakali
• Application Number:
  US09/174,278
• Time in Patent Office: 746 Days
• Field of Search: 717/1, 717/2, 717/5, 717/6, 717/8, 717/9, 707/200, 707/201, 707/202, 709/102, 709/213, 709/312, 709/400
• US Class Current: 717/118
• CPC Class Codes: G06F 8/447 Target code generation
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A code generating system generates, from code in a program, native code that is executable by a computer system. The code generating system may be included in a just-in-time compiler used to generate native code that is executable by a computer system, from a program in Java Byte Code form, and specifically generates, in response to Java Byte Code representative of a synchronization statement that synchronizes access by multiple threads of execution to at least one variable contained in the Java Byte code, one or more native code instructions that implements a wait-free synchronization methodology to synchronization access to the at least one variable. Since the instructions which implement the wait-free synchronization methodology do not require calls to the operating system, they can generally be processed more rapidly than other synchronization techniques which do require operating system calls.

Claims

1. A code generator for generating, from code in a program, native code executable by a computer system, the code generator comprising:

A. a code portion receiver configured to receive a portion of the program code for which the native executable code is to be generated

B. a synchronization statement detector configured to determine whether the received program code portion includes a statement for synchronizing access by multiple execution threads to at least one variable contained within the obtained code; and

C. a native code generator configured to, in response to positive determination by said synchronization statement detector, generate native code for the synchronization statement including a wait-free synchronization construct to synchronize access to the at least one variable.

2. A code generator as defined in claim 1 in which the native code generator is further configured to, in response to a negative determination by the synchronization statement detector, generate native code in a conventional manner.

3. A code generator as defined in claim 1 in which the native code generator is configured to generate the wait-free synchronization construct as including at least one native code instruction configured to enable the computer system to:

A. retrieve a value from a storage location for the variable;

B. perform a predetermined operation in connection with the value to generate a modified value;

C. perform an atomic compare-and-swap operation in connection with the value, the modified value and contents of the storage location to compare the value to the contents of the storage location and

(i) if the value corresponds to the contents of the storage location, store the modified value in the storage location, but

(ii) if the value does not correspond to the contents of the storage location, update the modified value with the contents of the storage location;

D. compare the value and the modified value and, if the value and modified value correspond continue, but, if the value and modified value do not correspond, perform a subsequent iteration of the at least one native code instruction.

4. A code generator as defined in claim 1 in which the program includes instructions in Java Byte Code.

5. A code generator as defined in claim 1 in which the native code generator is in the form of a just-in-time compiler.

6. A code generator as defined in claim 1 in which, if the synchronization statement detector detects synchronization statements for synchronizing access to a plurality of variables, the native code generator generates a wait-free synchronization construct associated with each of said plurality of variables.

7. A code generation method for generating, from code in a program, native code executable by a computer system, the code generation method comprising the steps of:

A. receiving a portion of the program code for which the native executable code is to be generated

B. determining whether the received program code portion includes a statement for synchronizing access by multiple execution threads to at least one variable contained within the obtained code; and

C. in response to positive determination during said synchronization statement determination step, generate native code for the synchronization statement including a wait-free synchronization construct to synchronize access to the at least one variable.

8. A code generation method as defined in claim 7 in which the native code generation step includes the step of, in response to a negative determination by the synchronization statement detector, generating native code in a conventional manner.

9. A code generation method as defined in claim 7 in which the native code generation step includes the step of generating the wait-free synchronization construct to include at least one native code instruction configured to enable the computer system to:

A. retrieve a value from a storage location for the variable;

B. perform a predetermined operation in connection with the value to generate a modified value;

C. perform an atomic compare-and-swap operation in connection with the value, the modified value and contents of the storage location to compare the value to the contents of the storage location and

(i) if the value corresponds to the contents of the storage location, store the modified value in the storage location, but

(ii) if the value does not correspond to the contents of the storage location, update the modified value with the contents of the storage location;

D. compare the value and the modified value and, if the value and modified value correspond continue, but, if the value and modified value do not correspond, perform a subsequent iteration of the at least one native code instruction.

10. A code generation method as defined in claim 7 in which the program includes instructions in Java Byte Code.

11. A code generation method as defined in claim 7 in which the native code generating step includes the step of using a just-in-time compiler.

12. A code generation method as defined in claim 7 in which, if the synchronization statement determination step includes the step of detecting synchronization statements for synchronizing access to a plurality of variables, the native code generation step including the step of generating a wait-free synchronization construct associated with each of said plurality of variables.

13. A computer program product for use in connection with a computer to provide a code generator for generating, from code in a program, native code executable by a computer system, the computer program product comprising a computer-readable medium having encoded thereon:

A. a code portion receiver module configured to enable the computer to receive a portion of the program code for which the native executable code is to be generated

B. a synchronization statement detector module configured to enable the computer to determining whether the received program code portion includes a statement for synchronizing access by multiple execution threads to at least one variable contained within the obtained code; and

C. a native code generator module configured to enable the computer to, in response to positive determination by said synchronization statement detector, generate native code for the synchronization statement including a wait-free synchronization construct to synchronize access to the at least one variable.

14. A computer program product as defined in claim 13 in which the native code generator module is further configured to enable the computer to, in response to a negative determnination during execution of the synchronization statement detector module, generate native code in a conventional manner.

15. A computer program product as defined in claim 13 in which the native code generator module is configured to enable the computer to generate the wait-free synchronization construct as including at least one native code instruction configured to enable the computer system to:

A. retrieve a value from a storage location for the variable;

B. perform a predetermined operation in connection with the value to generate a modified value;

C. perform an atomic compare-and-swap operation in connection with the value, the modified value and contents of the storage location to compare the value to the contents of the storage location and

(i) if the value corresponds to the contents of the storage location, store the modified value in the storage location, but

(ii) if the value does not correspond to the contents of the storage location, update the modified value with the contents of the storage location;

D. compare the value and the modified value and, if the value and modified value correspond continue, but, if the value and modified value do not correspond, perform a subsequent iteration of the at least one native code instruction.

16. A computer program product as defined in claim 13 in which the program includes instructions in Java Byte Code.

17. A computer program product as defined in claim 13 in which the native code generator module is in the form of a just-in-time compiler.

18. A computer program product as defined in claim 13 in which, if the synchronization statement detector module enables the computer to detect synchronization statements for synchronizing access to a plurality of variables, the native code generator enables generation of a wait-free synchronization construct associated with each of said plurality of variables.