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

• US 20040059733A1
• Filed: 09/24/2002
• Published: 03/25/2004
• Est. Priority Date: 09/24/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Li, Xiaofeng
• Granted Patent: US 7,209,918 B2
• Time in Patent Office: Days
• US Class Current: 707/8
• 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

27. 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; and

a lock owner controller to lock the object 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 without an atomic execution if the thread seeking to lock the object owns the object.

28. An apparatus as defined in claim 27 further comprising 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.

29. An apparatus as defined in claim 28 wherein the flag controller sets the first flag field and the second flag field to indicate the lock status of the object.

30. An apparatus as defined in claim 29 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.

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

32. An apparatus as defined in claim 27 wherein the lock owner controller locks the object by setting a lock owner field to identify the thread seeking to lock the object.

33. 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.

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 via an atomic execution; and

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

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.

3. A method as defined in claim 2 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.

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

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

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

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

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

setting a lock owner field associated with the object to identify the first thread.

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

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

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

setting the second flag field to a fourth predetermined state.

9. A method as defined in claim 8 wherein the first 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.

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

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

12. 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.

13. A method as defined in claim 1 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.

14. A method as defined in claim 13 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 second predetermined state, the atomic execution is terminated.

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

16. A method as defined in claim 13 further comprising:

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

setting a lock owner field associated with the object to identify the first thread.

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

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

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

20. A method as defined in claim 1 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; and

if the first flag field still has the first predetermined state, setting a lock owner field to identify the first thread.

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

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

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

24. A method as defined in claim 23 further comprising:

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

25. A method as defined in claim 24 wherein the first predetermined state and the second predetermined state are opposites, and the second predetermined state and the third predetermined state are opposites.

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

34. A method as defined in claim 33 further comprising, 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.

35. A method as defined in claim 34 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.

36. A method as defined in claim 33 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; and

if the first flag field still has the first predetermined state, setting a lock owner field to identify the first thread.

35-1. A method as defined in claim 33 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.

37. 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; and

second software to lock the object 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 without an atomic execution if the thread seeking to lock the object owns the object.

38. A tangible medium as defined in claim 37 further comprising 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.

39. A tangible medium as defined in claim 38 wherein the third software sets the first flag field and the second flag field to indicate the lock status of the object.

40. A tangible medium as defined in claim 39 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.

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

42. A tangible medium as defined in claim 37 wherein the second software locks the object by setting a lock owner field to identify the thread seeking to lock the object.