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

• US 7,209,918 B2
• Filed: 09/24/2002
• Issued: 04/24/2007
• Est. Priority Date: 09/24/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Li, Xiaofeng
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): MAHMOUDI, HASSAN
• Application Number:
  US10/253,038
• Publication Number:
  US 20040059733A1
• Time in Patent Office: 1,673 Days
• Field of Search: 707/8, 710/200, 710/241, 710/242, 717/116, 717/118, 717/119
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Apparatus and methods for locking objects in a multi-threaded environment are provided. An example method permits a first thread to lock an object to exclusively execute at least a portion of a routine associated with the object. The method includes, if the object is owned by a second thread, locking the object via an atomic execution and assigning ownership of the object to the first thread. It also includes, if the object is owned by the first thread, locking the object without an atomic execution.

Claims

1. For use in a multi-thread environment, a method of locking an object to permit a thread to exclusively execute at least a portion of a routine associated with the object, the method comprising:

receiving a request to access the object from a first thread;

determining if the object is owned by the first thread;

if the object is owned by a second thread, locking the object and setting a lock owner field to identify the first thread via an atomic execution; and

if the object is owned by the first thread, locking the object and setting the lock owner field to identify the first thread without an atomic execution,

wherein locking the object without an atomic execution comprises;

determining if a first flag field associated with the object has a first predetermined state;

if the first flag field has the first predetermined state, setting a second flag field associated with the object to a second predetermined state;

verifying that the first flag field still has the first predetermined state.

2. A method as defined in claim 1, further comprising, if the object is not owned by any thread, locking the object via a second atomic execution, wherein locking the object via the second atomic execution comprises:

verifying that an object owner field associated with the object is empty;

determining if the first flag field associated with the object has a third predetermined state;

determining if the second flag field associated with the object has the second predetermined state; and

if the first flag field has the third predetermined state and the second flag field has the second predetermined state, setting the first flag field to the first predetermined state and setting the object owner field to identify the first thread.

3. A method as defined in claim 2 wherein if any of:

(1) the object owner field is not empty, (2) the first flag field does not have the third predetermined state, and (3) the second flag field does not have the second predetermined state, the second atomic execution is terminated.

4. A method as defined in claim 2 wherein the third predetermined state and the second predetermined state are identical, and the first predetermined state and the third predetermined state are opposites.

5. A method as defined in claim 2 further comprising:

after the second atomic execution, verifying that the first flag field has the first predetermined state and the second flag field has the second predetermined state.

6. A method as defined in claim 5 further comprising, after the lock owner field is set to identify the first thread, executing the at least the portion of the routine.

7. A method as defined in claim 6 further comprising:

after executing the at least the portion of the routine, setting the first flag field to the first predetermined state; and

setting the second flag field to a fourth predetermined state.

8. A method as defined in claim 7 wherein the third predetermined state and the second predetermined state are identical, the first predetermined state and the third predetermined state are opposites, and the second predetermined state and the fourth predetermined state are opposites.

9. A method as defined in claim 6 further comprising, after executing the at least the portion of the routine, clearing the lock owner field.

10. A method as defined in claim 6 further comprising after executing the at least the portion of the routine, setting the object owner field to identify the first thread.

11. A method as defined in claim 1 wherein determining if the object is owned by the first thread comprises reading an object owner field associated with the object.

12. A method as defined in claim 1 wherein locking the object via an atomic execution comprises:

determining if the second flag field associated with the object has a fourth predetermined state; and

if the first flag field has the first predetermined state and the second flag field has the fourth predetermined state, setting the first flag field to a third predetermined state.

13. A method as defined in claim 12 wherein if any of:

(1) the first flag field does not have the first predetermined state, and (2) the second flag field does not have the fourth predetermined state, the atomic execution is terminated.

14. A method as defined in claim 12 wherein the first predetermined state and the fourth predetermined state are identical, and the first predetermined state and the third predetermined state are opposites.

15. A method as defined in claim 12 further comprising:

after the atomic execution, verifying that the first flag field has the third predetermined state and the second flag field has the fourth predetermined state.

16. A method as defined in claim 15 further comprising, after the lock owner field is set to identify the first thread, executing the at least the portion of the routine.

17. A method as defined in claim 16 further comprising, after executing the at least the portion of the routine, clearing the lock owner field.

18. A method as defined in claim 16 further comprising after executing the at least the portion of the routine, setting an object owner field to identify the first thread.

19. A method as defined in claim 1 wherein if the first flag field does not have the first predetermined state, the locking the object without an atomic execution is terminated.

20. A method as defined in claim 1 wherein the first predetermined state and the second predetermined state are opposites.

21. A method as defined in claim 1 further comprising, after the lock owner field is set to identify the first thread, executing the at least the portion of the routine.

22. A method as defined in claim 21 further comprising:

after executing the at least the portion of the routine, setting the second flag field to a fourth predetermined state.

23. A method as defined in claim 22 wherein the first predetermined state and the second predetermined state are opposites, and the second predetermined state and the fourth predetermined state are opposites.

24. A method as defined in claim 21 further comprising, after executing the at least the portion of the routine, clearing the lock owner field.

25. A tangible medium storing software for locking an object to permit a thread to exclusively execute at least a portion of a routine associated with the object, the tangible medium comprising:

first software to determine an identity of a thread owning the object;

second software to lock the object and to set a lock owner field to identify the first thread via an atomic execution if (1) no thread owns the object or (2) a thread other than the thread seeking to lock the object owns the object, and to lock the object and to set the lock owner field to identify the first thread without an atomic execution if the thread seeking to lock the object owns the object; and

third software to examine a first flag field associated with the object and a second flag field associated with the object to determine a lock status of the object, wherein the third software sets the first flag field and the second flag field to indicate the lock status of the object.

27. A tangible medium as defined in claim 25 wherein the first software reads an object owner field associated with the object to determine the identity of any thread owning the object.

26. A tangible medium as defined in claim wherein the lock status comprises at least one of:

(a) the object has not yet been locked, (b) the object is locked by a thread that does not own the object, (c) the object is locked by a thread that owns the object, and (d) the object is available to be locked.

28. For use in a multi-thread environment, an apparatus for locking an object to permit a thread to exclusively execute at least a portion of a routine associated with the object, the apparatus comprising:

an object owner controller to determine an identity of a thread owning the object;

a lock owner controller to lock the object and to set a lock owner field to identify the first thread via an atomic execution if (1) no thread owns the object or (2) a thread other than the thread seeking to lock the object owns the object, and to lock the object and to set the lock owner field to identify the first thread without an atomic execution if the thread seeking to lock the object owns the object; and

a flag controller to examine a first flag field associated with the object and a second flag field associated with the object to determine a lock status of the object, wherein the flag controller sets the first flag field and the second flag field to indicate the lock status of the object.

29. An apparatus as defined in claim 28 wherein the lock status comprises at least one of:

(a) the object has not yet been locked, (b) the object is locked by a tread that does not own the object, (c) the object is locked by a thread that owns the object, and (d) the object is available to be locked.

30. An apparatus as defined in claim 28 wherein the object owner controller reads an object owner field associated with the object to determine the identity of any thread owning the object.

31. For use in a multi-thread environment, a method of locking an object to permit a thread to exclusively execute at least a portion of a routine associated with the object, the method comprising:

receiving a request to access the object from a first thread;

determining if the object is owned by the first thread;

if the object is owned by the first thread, locking the object and setting the lock owner field to identify the first thread without an atomic execution; and

if the object is owned by a second thread, locking the object and setting a lock owner field to identify the first thread via an atomic execution, wherein locking the object via an atomic execution comprises;

determining if a first flag field associated with the object has a first predetermined state,

determining if a second flag field associated with the object has a second predetermined state, and

if the first flag field has the first predetermined state and the second flag field has the second predetermined state, setting the first flag field to a third predetermined state.

32. For use in a multi-thread environment, a method of permitting a first thread to lock an object to exclusively execute at least a portion of a routine associated with the object, the method comprising:

if the object is owned by a second thread, locking the object via an atomic execution and assigning ownership of the object to the first thread;

if the object is owned by the first thread, locking the object without an atomic execution; and

if the object is not owned by any thread, locking the object via a second atomic execution and assigning ownership of the object to the first thread, wherein locking the object via a second atomic execution comprises;

verifying that an object owner field associated with the object is empty;

determining if a first flag field associated with the object has a first predetermined state;

determining if a second flag field associated with the object has a second predetermined state; and

if the first flag field has the first predetermined state and the second flag field has the second predetermined state, setting the first flag field to a third predetermined state and setting the object owner field to identify the first thread.

33. A method as defined in claim 32 wherein locking the object via an atomic execution comprises:

determining if the first flag field associated with the object has the first predetermined state;

determining if the second flag field associated with the object has the second predetermined state; and

if the first flag field has the first predetermined state and the second flag field has the second predetermined state, setting the first flag field to the third predetermined state.

34. A method as defined in claim 32 wherein locking the object without an atomic execution comprises:

determining if the first flag field associated with the object has the first predetermined state;

if the first flag field has the first predetermined state, setting the second flag field associated with the object to the second predetermined state; and

verifying that the first flag field still has the first predetermined state.