Method and apparatus for concurrent thread synchronization

• US 6,167,424 A
• Filed: 10/27/1997
• Issued: 12/26/2000
• Est. Priority Date: 11/04/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lindholm, Timothy G., Bak, Lars
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/957,955
• Time in Patent Office: 1,156 Days
• Field of Search: 707/8, 707/103, 707/1, 709/100, 709/104, 709/315, 709/106, 709/305, 712/28, 711/125
• US Class Current: 718/100
• CPC Class Codes: G06F 9/4488 Object-oriented
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Methods and apparatus for locking and unlocking objects using synchronized threads are disclosed. According to one aspect of the present invention, a computer-implemented method for using a first thread to obtain a header value of an object includes replacing contents of a header of the object with a sentinel which identifies an execution stack associated with the first thread. Once the object contents are replaced with the sentinel, a determination is made regarding whether the object contents include a header value of the object, and when it is determined that the object contents do not include the header value of the object, a determination is made as to when the object is in the process of being studied by a second thread. In one embodiment, when it is determined that the object is not in the process of being studied by the second thread, the method involves adding the first thread to a list associated with the stack.

Claims

1. A computer-implemented method for obtaining a header value of an object using a first thread, the object including an object header, the first thread having an associated execution stack and having a first thread execution priority, the method comprising:

a) replacing contents of the object header with a sentinel which identifies the stack;

b) determining whether the contents include a header value of the object; and

c) when it is determined that the contents do not include the header value of the object, determining when the object is being studied by a second thread.

2. A computer-implemented method as recited in claim 1 wherein when it is determined that the object is not in the process of being studied by the second thread, the method further includes:

adding the first thread to a list associated with the stack, the list being arranged to indicate that the first thread is awaiting access to the object; and

returning the contents to the object header.

3. A computer-implemented method as recited in claim 1 further including:

receiving a notification for the first thread to access the object; and

repeating steps a)-c).

4. A computer-implemented method as recited in claim 1 wherein when it is determined that the object is in the process of being studied by the second thread, the method further includes:

resolving the contents to identify the second thread;

determining whether a second thread execution priority associated with the second thread is less than the first thread execution priority.

5. A computer-implemented method as recited in claim 4 wherein when it is determined that the second thread execution priority is less than the first thread execution priority, the method further includes boosting the second thread execution priority to the first thread execution priority.

6. A computer-implemented method as recited in claim 5 further including:

incrementing a counter associated with the second thread to indicate that the second thread execution priority has been boosted;

adding the second thread and the counter to a queue of boosted threads, the queue of boosted threads being associated with the first thread; and

repeating steps a)-c).

7. A computer-implemented method as recited in claim 1 wherein when it is determined that the contents include the header value, the method further includes:

storing the contents on the stack in a particular location; and

storing a pointer in the object header, wherein the pointer is arranged to identify the particular location.

8. A computer-implemented method as recited in claim 7 further including unboosting a second thread execution priority of the second thread, wherein the second thread execution priority was boosted to the first thread execution priority.

9. A computer-implemented method as recited in claim 8 wherein unboosting the second thread execution priority of the second thread involves unboosting the second thread execution priority to an assigned execution priority of the second thread.

10. A computer-implemented method as recited in claim 1 further including constructing the sentinel.

11. A computer-implemented method for returning a header value of an object to the object, the header value being stored on an execution stack associated with a first thread, the object including an object header, the first thread having a first thread execution priority, the method comprising:

a) exchanging contents of the object header for a sentinel arranged to identify the execution stack; and

b) using the contents to determine if the object is being studied by a second thread; and

c) when it is determined that the object is not being studied by the second thread, replacing the sentinel with the header value.

12. A computer-implemented method as recited in claim 11 wherein when it is determined that the object is being studied by the second thread, the method further includes:

resolving the contents to identify the second thread;

determining whether a second thread execution priority associated with the second thread is less than the first thread execution priority.

13. A computer-implemented method as recited in claim 12 wherein when it is determined that the second thread execution priority is less than the first thread execution priority, the method further includes boosting the second thread execution priority to the first thread execution priority.

14. A computer-implemented method as recited in claim 13 further including:

incrementing a counter associated with the second thread to indicate that the second thread execution priority has been boosted;

adding the second thread and the counter to a queue of boosted threads, the queue of boosted threads being associated with the first thread; and

repeating steps a)-c).

15. A computer program product for associating an object with a first thread, the object including an object header, the first thread having an associated stack allocated in a memory associated with a computer system, the computer program product comprising:

computer code that obtains contents of the object header; and

computer code that stores the contents of the object header at a first location within the stack;

computer code that stores a reference indicator in the object header, the reference indicator being arranged to identify the stack;

computer code that determines when the contents of the object header do not include a header value;

computer code that determines when the object is in the process of being studied by a second thread when the contents of the object header do not include the header value; and

a computer readable medium that stores the computer codes.

16. A computer program product according to claim 15 wherein the computer readable medium is a data signal embodied in a carrier wave.

17. A computer program product according to claim 15 further including computer code that updates a status indicator associated with the object to indicate that the reference indicator is stored in the object header.

18. A computer program product according to claim 17 wherein the contents of the object header are the header value, and the computer code that updates the status indicator includes computer code that updates the status indicator to indicate that the object is accessible to the first thread.

19. A computer program product according to claim 15 wherein the reference is a sentinel, the computer program product further including:

computer code that stores a forwarding pointer in the object header when it is determined that the contents of the object header are the header value, the forwarding pointer being arranged to identify the first location within the stack.

20. A computer program product according to claim 19 further including:

computer code that returns the contents of the object header to the object header when it is determined that the contents of the object header are not the header value; and

computer code that updates a status indicator associated with the object to indicate that the contents of the object header are in the object header when it is determined that the contents of the object header are not the header value.

21. A computer program product according to claim 19 further including computer code that determines whether the contents of the object header identify a second location within the stack when it is determined that the contents of the object header are not a header value.

22. A computer program product according to claim 21 further including:

computer code that returns the contents of the object header to the object header when the contents of the object header identify a second location within the stack; and

computer code that stores an indicator value in the first location within the stack when the contents of the object header identify a second location within the stack, the indicator value being arranged to indicate that the header value is stored in the second location within the stack.

23. A computer system including a memory which includes a plurality of threads, each of the plurality of threads having an associated stack, the computer system comprising:

a processor coupled to the memory; and

an object including an object header, the object header being arranged to contain a header value which includes information relating to the object, wherein a first thread selected from the plurality of threads is arranged to obtain the header value and to place a first reference indicator in the object header, the first reference indicator being arranged to identify the stack associated with the first thread; and

a second thread selected from the plurality of threads, the second thread being arranged to obtain the reference indicator from the object header and to use the reference indicator to determine that the object is not available to the second thread.

24. A computer system as recited in claim 23 wherein the object includes a status indicator that is arranged to indicate that the first reference indicator is stored in the object header.

25. A computer system as recited in claim 23 wherein the stack associated with the first thread is arranged to store the header value in a first location, wherein the first reference indicator is arranged to identify the first location.

26. A computer system as recited in claim 23 wherein the second thread is arranged to place a second reference indicator in the object header, the second reference indicator being arranged to identify the stack associated with the second thread, the computer system further including a third thread selected from the plurality of threads which is arranged to obtain the second reference indicator from the object header, the third thread further being arranged to place a third reference indicator in the object header, the third reference indicator being arranged to identify the stack associated with the third thread.