Synchronization techniques in a multithreaded environment

• US 7,904,685 B1
• Filed: 06/12/2003
• Issued: 03/08/2011
• Est. Priority Date: 11/13/1998
• Status: Expired due to Term

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Alverson, Gail A., Kahan, Simon H., Porterfield, Allan, Koblenz, Brian D., Smith, Burton J., Callahan, Charles David II
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Birkhimer; Christopher D
• Application Number:
  US10/461,979
• Time in Patent Office: 2,826 Days
• Field of Search: 711/163, 711/E12.023
• US Class Current: 711/163
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Various techniques for manipulating data using access states of memory, access control fields of pointers and operations, and exception raising and exception trapping in a multithreaded computer system. In particular, the techniques include synchronization support for a thread blocked in a word, demand evaluation of values, parallel access of multiple threads to a list, synchronized and unsynchronized access to a data buffer, use of forwarding to avoid checking for an end of a buffer, use of sentinel word to detect access past a data structure, concurrent access to a word of memory using different synchronization access modes, and use of trapping to detect access to restricted memory.

Claims

1. A method in a multithreaded architecture computer system for processing of a thread waiting for access to a memory location, the multithreaded architecture computer system having a plurality of threads, the method comprising:

when access by a thread to the memory location is blocked,

enabling an exception to be raised each time the memory location is accessed while execution of the thread is blocked, wherein the raising of the exception is enabled by setting a trap bit associated with the memory location, and

blocking execution of the thread so that the thread does not attempt to access the memory location before the thread is restarted; and

detecting access to the memory location while execution of the thread is blocked and the trap bit associated with the memory location is set;

raising the exception as a result of the detected access to the memory location while execution of the thread is blocked and the trap bit associated with the memory location is set;

in response to the exception being raised,

completing the detected access to the memory location,

restarting execution of the thread in response to completing the detected access so that the thread can attempt to access the memory location,

if access to the memory location by the thread is successful, allowing the thread to continue its execution, and

if access to the memory location by the thread is not successful,

enabling the exception to be raised each time the memory location is accessed while execution of the thread is blocked, wherein the raising of the exception is enabled by setting a trap bit associated with the memory location, and

blocking execution of the thread so that the thread does not attempt to access the memory location before the thread is restarted.

2. The method of claim 1 wherein when access by the thread to the memory location is blocked,

saving the state of the thread;

and

storing a reference to the thread in the memory location.

3. The method of claim 2 wherein the stored reference is a reference to a data structure that identifies the thread and the saved state.

4. The method of claim 3 wherein the data structure indicates the value that was stored in the memory location before storing the reference.

5. The method of claim 1 wherein when access by the thread to the memory location is blocked, storing a reference to the thread in the memory location.

6. The method of claim 1 wherein multiple threads are simultaneously blocked on the memory location.

7. The method of claim 6 including storing a reference to the blocked threads in the memory location.

8. The method of claim 7 wherein the stored reference is a pointer to a list identifying the blocked threads.

9. The method of claim 8 wherein the list is a linked list.

10. The method of claim 1 wherein when the exception is raised as a result of the detected access to the memory location, determining whether the thread will not block after the detected access completes and unblocking the thread when the thread will not block after the detected access completes.

11. The method of claim 1 wherein when the exception is raised as a result of the detected access to the memory location, determining whether the detected access will be blocked and blocking execution of the thread attempting the detected access when the detected access will be blocked.

12. The method of claim 1 wherein access to the memory location is blocked as a result of a retry limit being exceeded.

13. The method of claim 1 wherein the enabling of an exception includes setting an exception to be raised when the memory location is next accessed.

14. The method of claim 1 wherein restarting the execution of the thread includes simulating the execution of an instruction of the thread whose access to the memory location was blocked.

15. The method of claim 1 wherein when an exception is raised as a result of the detected access to the memory location, before completing the detected access to the memory location:

determining the effect of the detected access to the memory location;

when the effect indicates that the thread can continue, restarting the thread; and

redoing the detected access.

16. The method of claim 1 wherein when an exception is raised as a result of the detected access to the memory location, before completing the detected access to the memory location:

determining the effect of the detected access to the memory location; and

when the effect indicates that the thread cannot continue,

determining whether the thread that attempted the detected access can continue;

when it is determined that the thread that attempted the detected access can continue,

simulating execution of accessing the memory location by the thread that attempted the detected access; and

returning to execution of the thread that attempted the detected access.

17. The method of claim 1 wherein when an exception is raised as a result of the detected access to the memory location, before completing the detected access to the memory location:

determining the effect of the detected access to the memory location; and

when the effect indicates that the thread cannot continue,

determining whether the thread that attempted the detected access can continue, and

when it is determined that the thread that attempted the detected access cannot continue,

adding the thread that attempted the detected access to a collection of threads waiting to access the memory location, and

blocking execution of the thread that attempted the detected access.

18. A computer-readable medium containing a data structure comprising:

a reference stored in a blocking memory location, the reference identifying a waiter list data structure; and

the waiter list data structure containing information identifying a thread that is blocked waiting for access to the blocking memory location and identifying a prior value of the blocking memory location prior to the reference being stored in the blocking memory location, wherein the execution of the thread is blocked so that the thread does not attempt to access the blocking memory location before the thread is restarted as a result of the blocking memory location being accessed; and

wherein each time the blocking memory location is accessed, the reference of the blocking memory location is used to access the waiter list data structure, which is used to identify the thread that is blocked and the prior value of the blocking memory location, so that the thread can be restarted.

19. The computer-readable medium of claim 18 wherein the waiter list data structure includes an indication of the state of the thread when it became blocked.

20. The computer-readable medium of claim 18 wherein the waiter list data structure identifies a plurality of threads that are blocked waiting to access the blocking memory location.

21. The computer-readable medium of claim 20 wherein the waiter list data structure is a linked list.

22. The computer-readable medium of claim 18 wherein the blocking memory location contains an indication that a trap is to occur when the blocking memory location is accessed.

23. A method in a computer system for waiting for access to a memory location, comprising:

under control of a first thread,

attempting to access the memory location, and

when the memory location cannot be accessed,

enabling a trap to occur each time the memory location is accessed while execution of the first thread is blocked;

blocking execution of the first thread so that the first thread does not attempt to access the memory location before a thread other than the first thread attempts to access the memory location;

under control of the thread other than the first thread,

attempting to access the memory location wherein the trap occurs;

in response to the trap occurring as a result of the thread other than the first thread accessing the memory location, transferring control to a trap handler;

under control of the trap handler,

unblocking execution of the first thread so that the first thread can attempt to access the memory location; and

allowing access to the memory location by the first thread.

24. The method of claim 23 wherein attempting to access the memory location under control of the first thread results in a retry limit to be exceeded.

25. The method of claim 23 wherein the first thread is blocked because the attempted access is a synchronized access.

26. The method of claim 23 wherein blocking execution of the first thread includes saving a state of the first thread and storing a reference to the first thread in the memory location.

27. The method of claim 26 wherein the stored reference is a reference to a data structure that identifies the first thread and the saved state.

28. The method of claim 23 wherein multiple threads are simultaneously blocked on the memory location.

29. The method of claim 28 including storing a reference to the blocked threads in the memory location.

30. The method of claim 29 wherein the stored reference is a pointer to a list identifying the blocked threads.

31. The method of claim 23 wherein allowing access to the memory location by the first thread includes completing execution of the attempted access to the memory location by the thread other than the first thread.