System and method for reducing synchronization overhead in multithreaded code

• US 6,662,364 B1
• Filed: 11/05/1999
• Issued: 12/09/2003
• Est. Priority Date: 11/05/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: HP Inc.
• Inventors: Vandervoorde, Mark Thierry, Ghemawat, Sanjay, Burrows, Michael
• Primary Examiner(s): Banankhah, Majid A.
• Assistant Examiner(s): Ali, Syed J
• Application Number:
  US09/434,831
• Time in Patent Office: 1,495 Days
• Field of Search: 709/100-108, 709/400
• US Class Current: 718/102
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A system and method for implementing mutual exclusion locks (mutexes) is provided. Mutexes of the present invention designate whether they are to be synchronized using fast nonatomic load/store sequences or, alternatively, expensive atomic hardware instructions. When a requesting thread requests a target mutex, the target mutex is synchronized using the method designated by the target mutex. In some embodiments, the designated synchronization method may be changed to the atomic method when the requesting thread is not the thread associated with the target mutex. In other embodiments, the designated synchronization method may be determined by a heuristic function. For example, the synchronization method may be changed to the atomic method when a mutex request counter, which penalizes thread changes, underflows. Other possible heuristic functions may consider factors such as whether the recursion overflow bit of the target mutex has been set, the percentage of mutexes, created by a predetermined call state, that have been converted to the atomic method, and/or the overall percentage of mutexes in the system that have been converted to the atomic method.

Claims

1. A method for controlling a request from a requesting thread to acquire a target mutex, said target mutex capable of specifying a first synchronization mode, a second synchronization mode, and a thread associated with said target mutex, the method comprising the steps of:

determining whether said target mutex is in said first synchronization mode or said second synchronization mode; and

(a) when said target mutex is in said first synchronization mode, said method additionally comprises querying whether said requesting thread is the thread associated with said target mutex;

wherein;

(i) when said requesting thread is the thread associated with said target mutex, said request to acquire said target mutex is granted without using atomic machine instructions to assure that no thread is operating on said target mutex; and

(ii) when said requesting thread is not the thread associated with said target mutex, said method additionally includes executing a verification procedure that ensures that no thread is operating on said target mutex; and

(b) when said target mutex is in said second synchronization mode, said method additionally comprises the steps of;

assuring, with atomic machine instructions, that no thread is operating on said target mutex; and

granting said request to acquire said target mutex;

wherein said thread associated with said target mutex is associated with said target mutex even when said target mutex is not held by any thread.

2. The method of claim 1, wherein executing said verification procedure includes:

placing said target mutex in said second synchronization mode;

ensuring, with atomic machine instructions, that no thread is operating on said target mutex; and

granting said request to acquire said target mutex.

3. The method of claim 1, wherein executing said verification procedure includes:

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

choosing, based on a heuristic function, to (i), set said target mutex to said second synchronization mode or to (ii), associate said requesting thread with said target mutex;

determining whether said target mutex is in said first synchronization modeor said second synchronization mode, wherein, when said target mutex is in said second synchronization mode, said method additionally comprises a step of assuring, with atomic machine instructions, that no thread is operating on said target mutex;

resuming said thread associated with said target mutex;

releasing said supervisor mutex; and

granting said request to acquire said target mutex.

4. The method of claim 3, wherein the suspending step comprises:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

5. The method of claim 3, wherein when, in the resolving step, it is determined that said thread associated with said target mutex is in a target mutex operating sequence, said requesting thread executes a procedure selected from the group consisting of

(i) backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) pushing said thread associated with said target mutex out of said target mutex operating sequence, and

(iii) an operation comprising the steps of:

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

6. The method of claim 3, wherein said heuristic function includes testing at least one value selected from the group consisting of:

(i) a setting of a recursive overflow bit associated with said target mutex; and

(ii) a conversion value, which represents a percentage of mutexes created by a particular call state, that are in said second synchronization mode.

7. The method of claim 1, wherein said target mutex includes a mutex request counter, the method further comprising the steps of:

incrementing said mutex request counter when said mutex request counter is below a predefined overflow value; and

performing an overflow function on said mutex request counter when said mutex request counter exceeds said overflow value; and

said verification procedure of step a(ii) comprises;

decrementing said mutex request counter by a thread penalty amount;

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

choosing, based on a heuristic function, to (i), set said target mutex to said second synchronization modeor to (ii), associate said requesting thread with said target mutex;

determining whether said target mutex is in said first synchronization modeor said second synchronization mode, wherein, when said target mutex is in said second synchronization mode, said method additionally comprises a step of assuring, with atomic machine instructions, that no thread is operating on said target mutex;

resuming said thread associated with said target mutex;

releasing said supervisor mutex; and

granting said request to acquire said target mutex.

8. The method of claim 7, wherein said step of performing the mutex request counter overflow function comprises setting said mutex request counter to a number that is determined by a calculation selected from the group consisting of:

dividing said mutex request counter by a number greater than one; and

setting said mutex request counter to a predetermined constant.

9. The method of claim 7, wherein the suspending step comprises:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

10. The method of claim 7, wherein when, in the resolving step, it is determined that said thread associated with said target mutex is in a target mutex operating sequence, said requesting thread executes a procedure selected from the group consisting of

(i) backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) pushing said thread associated with said target mutex out of said target mutex operating sequence, and

(iii) an operation comprising the steps of:

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

11. The method of claim 7, wherein said heuristic function includes testing at least one value selected from the group consisting of:

(i) a setting of a recursive overflow bit associated with said target mutex; and

(ii) a conversion value, which represents a percentage of mutexes created by a particular call state, that are in said second synchronization mode.

12. The method of claim 1, wherein said target mutex includes a mutex request counter, the method further comprising the steps of:

incrementing said mutex request counter when said mutex request counter is below a predefined overflow value; and

performing an overflow function on said mutex request counter when said mutex request counter exceeds said overflow value; and

said verification procedure of step a(ii) comprises;

decrementing said mutex request counter by a thread penalty amount;

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

associating said requesting thread with said target mutex; and

granting said request to acquire said target mutex.

13. The method of claim 12, wherein said step of performing the mutex request counter overflow function comprises setting said mutex request counter to a number that is determined by a calculation selected from the group consisting of:

dividing said mutex request counter by a number greater than one; and

setting said mutex request counter to a predetermined constant.

14. The method of claim 12, wherein the suspending step comprises:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

15. The method of claim 12, wherein when, in the resolving step, it is determined that said thread associated with said target mutex is in a target mutex operating sequence, said requesting thread executes a procedure selected from the group consisting of

(i) backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) pushing said thread associated with said target mutex out of said target mutex operating sequence, and

(iii) an operation comprising the steps of:

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

16. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a mutex control procedure for controlling a request from a requesting thread to acquire a target mutex, said target mutex capable of specifying a first synchronization mode, a second synchronization mode, and a thread that is associated with said target mutex even when the target mutex is not held by any thread, the mutex control procedure including instructions for;

receiving a request to acquire said target mutex from a requesting thread;

(a) when said target mutex is in said first synchronization mode, and wherein;

(i) when said requesting thread is the thread associated with said target mutex, said request to acquire said target mutex is granted without using atomic instructions to assure that no thread is operating on said target mutex; and

(ii) when said requesting thread is not the thread associated with said target mutex, verging that no thread is operating on said target mutex;

(b) when said target mutex is in said second synchronization mode, assuring, with atomic machine instructions, that no thread is operating on said target mutex; and

granting said request to acquire said target mutex.

17. The computer program product of claim 16, wherein the instructions for verifying that no thread is operating on said target mutex include instructions for:

placing said target mutex in said second synchronization mode;

ensuring, with atomic machine instructions, that no thread is operating on said target mutex; and

granting said request to acquire said target mutex.

18. The computer program product of claim 16, wherein the instructions for verifying that no thread is operating on said target mutex include instructions for:

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

choosing, based on a heuristic function, to (i) set said target mutex to said second synchronization modeor to (ii), associate said requesting thread with said target mutex;

determining whether said target mutex is in said first synchronization modeor said second synchronization mode, and when said target mutex is in said second synchronization mode, assuring, with atomic machine instructions, that no thread is operating on said target mutex;

resuming said thread associated with said target mutex;

releasing said supervisor mutex; and

granting said request to acquire said target mutex.

19. The computer product of claim 18, wherein the instructions for suspending the thread associated with said target mutex comprises instructions for:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

20. The computer product of claim 18, further including a procedure, to be executed when the resolving instructions determine that said thread associated with said target mutex is in a target mutex operating sequence, the procedure selected from the group consisting of:

(i) a procedure for backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) a procedure for pushing said thread associated with said target mutex out of said target mutex operating sequence, and (iii) a procedure for;

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

21. The computer program product of claim 16, wherein said target mutex includes a mutex request counter, and the mutex control procedure further includes instructions for:

incrementing said mutex request counter when said mutex request counter is below a predefined overflow value; and

performing an overflow function on said mutex request counter when said mutex request counter exceeds said overflow value; and

verifying that no thread is operating on said target mutex, the instructions for verifying including instructions for;

decrementing said mutex request counter by a thread penalty amount;

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

choosing, based on a heuristic function, to (i), set said target mutex to said second synchronization mode or to (ii), associate said requesting thread with said target mutex;

determining whether said target mutex is in said first synchronization modeor said second synchronization mode, and when said target mutex is in said second synchronization mode, assuring, with atomic machine instructions, that no thread is operating on said target mutex;

resuming said thread associated with said target mutex;

releasing said supervisor mutex; and

granting said request to acquire said target mutex.

22. The computer product of claim 21, wherein said mutex request counter overflow function comprises instructions for setting said mutex request counter to a number that is determined by a calculation selected from the group consisting of:

dividing said mutex request counter by a number greater than one; and

setting said mutex request counter to a predetermined constant.

23. The computer product of claim 21, wherein the instructions for suspending the thread associated with said target mutex comprises instructions for:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

24. The computer product of claim 21, further including a procedure, to be executed when the resolving instructions determine that said thread associated with said target mutex is in a target mutex operating sequence, the procedure selected from the group consisting of:

(i) a procedure for backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) a procedure for pushing said thread associated with said target mutex out of said target mutex operating sequence, and (iii) a procedure for;

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

25. The computer product of claim 21, wherein said heuristic function includes instructions for testing at least one value selected from the group consisting of:

(i) a setting of a recursive overflow bit associated with said target mutex; and

(ii) a conversion value, which represents a percentage of mutexes created by a particular call state, that are in said second synchronization mode.

26. The computer program product of claim 16, wherein said target mutex includes a mutex request counter, and the mutex control procedure further includes instructions for:

incrementing said mutex request counter when said mutex request counter is below a predefined overflow value; and

performing an overflow function on said mutex request counter when said mutex request counter exceeds said overflow value; and

verifying tat no thread is operating on said target mutex the instructions for verifying including instructions for;

decrementing said mutex request counter by a thread penalty amount;

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

associating said requesting thread with said target mutex; and

granting said request to acquire said target mutex.

27. The computer product of claim 26, wherein said mutex request counter overflow function comprises instructions for setting said mutex request counter to a number that is determined by a calculation selected from the group consisting of:

dividing said mutex request counter by a number greater than one; and

setting said mutex request counter to a predetermined constant.

28. The computer product of claim 26, wherein the instructions for suspending the thread associated with said target mutex comprise instructions for:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

29. The computer product of claim 26, further including a procedure, to be executed when the resolving instructions determine that said thread associated with said target mutex is in a target mutex operating sequence, the procedure selected from the group consisting of:

(i) a procedure for backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) a procedure for pushing said thread associated with said target mutex out of said target mutex operating sequence, and

(iii) a procedure for;

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

30. The computer product of claim 26, wherein said heuristic function includes instructions for testing at least one value selected from the group consisting of:

(i) a setting of a recursive overflow bit associated with said target mutex; and

(ii) a conversion value, which represents a percentage of mutexes created by a particular call state, that are in said second synchronization mode.

31. A computer system for controlling acquisition of a target mutex that is capable of specifying a first synchronization mode, a second synchronization mode, and a thread associated with said target mutex, the computer system comprising:

at least one central processing unit;

a memory;

at least one bus connecting the at least one central processing unit and the memory; and

at least one thread, including a requesting thread;

the memory including a mutex controller and said target mutex;

wherein said mutex controller includes instructions for;

determining, in response to a request to acquire said target mutex by said requesting thread, whether said target mutex is in said first synchronization modeor said second synchronization mode; and

(a) when said target mutex is in said first synchronization mode, said mutex controller queries whether said requesting thread is the thread associated with said target mutex, and, in response to said query;

(i) grants said request to acquire said target mutex when said requesting thread is the thread associated with said target mutex without using atomic instructions to ensure that no other thread is holding said mutex; and

(ii) performs a verification procedure that ensures that no thread is operating on said target mutex when said requesting thread is not the thread associated with said target mutex; and

(b) when said target mutex is in said second synchronization mode, said mutex controller ensures, with atomic machine instructions, that no thread is operating on said target mutex and grants said request to acquire said target mutex;

wherein said thread associated with said target mutex is associated with said target mutex even when said target mutex is not held by any thread.

32. The computer system of claim 31, wherein said verification procedure includes instructions for:

placing said target mutex in said second synchronization mode;

ensuring, with atomic machine instructions, that no thread is operating on said target mutex; and

granting said request to acquire said target mutex.

33. The computer system of claim 31, wherein said verification procedure comprises instructions for:

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

choosing, based on a heuristic function, to (i), set said target mutex to said second synchronization mode or to (ii), associate said requesting thread with said target mutex;

determining whether said target mutex is in said first synchronization modeor said second synchronization mode, and, when said target mutex is in said second synchronization mode, assuring, with atomic machine instructions, that no thread is operating on said target mutex;

resuming said thread associated with said target mutex;

releasing said supervisor mutex; and

granting said request to acquire said target mutex.

34. The computer product of claim 33, wherein said instructions for suspending the thread associated with said target mutex comprises instructions for:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

35. The computer product of claim 33, including a procedure to be executed when the resolving instructions determine that said thread associated with said target mutex is in a target mutex operating sequence, the procedure selected from the group consisting of:

(i) a procedure for backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) a procedure for pushing said thread associated with said target mutex out of said target mutex operating sequence, and (iii) a procedure for;

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

36. The computer product of claim 33, wherein said heuristic function includes instructions for testing at least one value selected from the group consisting of:

(i) a setting of a recursive overflow bit associated with said target mutex; and

(ii) a conversion value, which represents a percentage of mutexes created by a particular call state, that are in said second synchronization mode.

37. The computer system of claim 31, wherein said target mutex includes a mutex request counter, the mutex controller further including instructions for:

incrementing said mutex request counter when said mutex request counter is below a predefined overflow value; and

performing an overflow function on said mutex request counter when said mutex request counter exceeds said overflow value; and

said verification procedure comprises instructions for;

decrementing said mutex request counter by a thread penalty amount;

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

choosing, based on a heuristic function, to (i), set said target mutex to said second synchronization modeor to (ii), associate said requesting thread with said target mutex;

determining whether said target mutex is in said first synchronization modeor said second synchronization mode, and when said target mutex is in said second synchronization mode, assuring, with atomic machine instructions, that no thread is operating on said target mutex;

resuming said thread associated with said target mutex;

releasing said supervisor mutex; and

granting said request to acquire said target mutex.

38. The computer product of claim 37, wherein said mutex request counter overflow function comprises instructions for setting said mutex request counter to a number that is determined by a calculation selected from the group consisting of:

instructions for dividing said mutex request counter by a number greater than one; and

instructions for setting said mutex request counter to a predetermined constant.

39. The computer product of claim 37, wherein said instructions for suspending the thread associated with said target mutex comprises instructions for:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

40. The computer product of claim 37, including a procedure to be executed when the resolving instructions determine that said thread associated with said target mutex is in a target mutex operating sequence, the procedure selected from the group consisting of:

(i) a procedure for backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) a procedure for pushing said thread associated with said target mutex out of said target mutex operating sequence, and

(iii) a procedure for;

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

41. The computer product of claim 37, wherein said heuristic function includes instructions for testing at least one value selected from the group consisting of:

(i) a setting of a recursive overflow bit associated with said target mutex; and

(ii) a conversion value, which represents a percentage of mutexes created by a particular call state, that are in said second synchronization mode.

42. The computer system of claim 31, wherein said target mutex includes a mutex request counter, the mutex controller further including instructions for:

incrementing said mutex request counter when said mutex request counter is below a predefined overflow value; and

performing an overflow function oh said mutex request counter when said mutex request counter exceeds said overflow value; and

said verification procedure comprises instructions for;

decrementing said mutex request counter by a thread penalty amount;

acquiring a supervisor mutex;

suspending the thread associated with said target mutex;

resolving whether said suspended thread is in a sequence operating on said target mutex;

associating said requesting thread with said target mutex; and

granting said request to acquire said target mutex.

43. The computer product of claim 42, wherein said mutex request counter overflow function comprises instructions for setting said mutex request counter to a number that is determined by a calculation selected from the group consisting of:

instructions for dividing said mutex request counter by a number greater than one; and

instructions for setting said mutex request counter to a predetermined constant.

44. The computer product of claim 42, wherein said instructions for suspending the thread associated with said target mutex comprises instructions for:

(i) requiring that said requesting thread own a control mutex associated with said requesting thread;

(ii) requiring that said thread associated with said target mutex own a control mutex associated with said thread; and

(iii) suspending said thread associated with said target mutex when said requesting thread does own both said control mutex of said requesting thread and said control mutex of said thread associated with said target mutex.

45. The method of claim 42, including a procedure to be executed when the resolving instructions determine that said thread associated with said target mutex is in a target mutex operating sequence, the procedure selected from the group consisting of:

(i) a procedure for backing said thread associated with said target mutex out of said target mutex operating sequence,

(ii) a procedure for pushing said thread associated with said target mutex out of said target mutex operating sequence, and

(iii) a procedure for;

(1) resuming said thread associated with said target mutex for a period of time;

(2) suspending said thread associated with said target mutex;

(3) determining whether said suspended thread associated with said target mutex is in said target mutex operating sequence; and

(4) repeating steps 1, 2 and 3 when said suspended thread associated with said target mutex is in said target mutex operation sequence.

46. A method for controlling a request from a requesting thread to acquire a target mutex capable of specifying a thread associated with said target mutex, the method comprising the step of querying, without use of atomic machine instructions, whether said requesting thread is the thread associated with said target mutex, wherein:

(i) when said requesting thread is the thread associated with said target mutex, said request to acquire said target mutex is granted, and

(ii) when said requesting thread is not the thread associated with said target mutex, said method additionally includes executing a verification procedure that ensures that no thread is operating on said target mutex;

wherein said associated thread being associated with said target mutex even when no thread holds the target mutex.

47. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising a mutex control procedure for controlling a request from a requesting thread to acquire a target mutex capable of specifying a thread associated with said target mutex, the mutex control procedure including instructions for:

querying, without use of atomic machine instructions, whether said requesting thread is the thread associated with said target mutex;

verifying that no thread is operating on said target mutex; and

granting said request to acquire said target mutex;

wherein said associated thread being associated with said target mutex even when no thread holds the target mutex.

48. A computer system for controlling acquisition of a target mutex capable of specifying a thread associated with said target mutex, the computer system comprising:

at least one central processing unit;

a memory;

at least one bus connecting the at least one central processing unit and the memory; and

at least one thread, including a requesting thread;

the memory including a mutex controller and said target mutex;

wherein said mutex controller includes instructions for;

determining, in response to a request to acquire said target mutex by said requesting thread, whether said requesting thread is the thread associated with said target mutex, and, in response to said request;

(i) granting said request to acquire said target mutex when said requesting thread is the thread associated with said target mutex; and

(ii) performing a verification procedure that ensures that no thread is operating on said target mutex when said requesting thread is not the thread associated with said target mutex;

wherein said associated thread being associated with said target mutex even when no thread holds the target mutex.

49. A computer system, comprising:

a CPU; and

memory coupled to said CPU, said memory storing a mutex usable to provide controlled access to a resource, said mutex programmed to specify one of a plurality of synchronization techniques related to using said mutex among multiple threads;

wherein said CPU is adapted to program said mutex from one synchronization technique to another synchronization technique;

wherein a thread is associated with the mutex even if no thread owns the mutex and wherein one of the synchronization techniques uses atomic operations and, when the associated thread requests the mutex, another synchronization does not use atomic operation.