Synchronization techniques in a multithreaded environment

• US 6,862,635 B1
• Filed: 07/27/1999
• Issued: 03/01/2005
• 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): BANANKHAH, MAJID A
• Application Number:
  US09/361,671
• Time in Patent Office: 2,044 Days
• Field of Search: 718/100, 718/102, 718/104, 711/52, 711/56, 711/57, 711/58, 711/156, 711/168, 709/213, 709/234, 710/52, 710/310, 712/239
• US Class Current: 710/52
• 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 computer system for accessing a buffer of data, the method comprising:

defining a write pointer to point to a location within the buffer;

when adding data to the buffer;

fetching the write pointer;

adding an indication of a size of the data to the write pointer; and

storing the data into the buffer starting at a location indicated by the fetched write pointer; and

setting the synchronization access mode of the write pointer to be either normal or sync to effect the behavior of adding data to the buffer.

2. The method of claim 1 wherein the fetching and adding includes executing a fetch and add operation.

3. The method of claim 1 wherein when the synchronization access mode of the write pointer is set to normal, the storing includes overwriting data previously stored in the buffer and not yet read.

4. The method of claim 1 wherein when the synchronization access mode of the write pointer is set to sync, the storing includes waiting to overwrite data previously stored in the buffer until the data has been read.

5. The method of claim 1 wherein the setting of the synchronization access mode of the write pointer is transparent to the adding of the data to the buffer.

6. A method in a computer system for accessing data, the method comprising:

defining a pointer to point to a location within the data, the pointer having a synchronization access mode;

setting the synchronization access mode of the pointer to be either unsynchronized or synchronized to effect a desired behavior of accessing the data;

allowing accessing code to access the data using the pointer with the current setting of the synchronization access mode;

changing the synchronization access mode of the pointer to effect the desired behavior of accessing the data; and

allowing accessing code to access the data using the pointer with the changed setting of the synchronization access mode.

7. The method of claim 6 wherein the setting of the synchronization access mode is changed to change the desired behavior of accessing the data.

8. The method of claim 6 wherein when the synchronization access mode is set to unsynchronized, access to the location within the data is permitted regardless of whether location is empty or full.

9. The method of claim 6 wherein when the synchronization access mode is set to sync, read access to the location within the data is permitted only when the location is full.

10. The method of claim 9 after when the read access, the location is set to empty.

11. The method of claim 6 wherein when the synchronization access mode is set to sync, write access to the location within the data is permitted only when the location is empty.

12. The method of claim 11 wherein after the write access, the location is set to full.

13. The method of claim 6 wherein the behavior of the accessing code is modified without modifying the accessing code.

14. The method of claim 6 including storing in forwarding locations at located past an end of the data pointers to locations at the other end of the data, the pointers having forwarding enabled so that when a forwarding location is accessed, the access is directed to the pointed to location at the other end of the data.

15. The method of claim 6 including storing a pointer to an invalid location in a location adjacent to the data with forwarding of that location enabled so that when the location adjacent to the data is accessed an exception is raised.

16. The method of claim 6 wherein the data is accessed by multiple readers and writers.

17. The method of claim 6 wherein the data is accessed by multiple producers.

18. The method of claim 6 wherein the data is accessed by multiple consumers.

19. The method of claim 6 including

when access to the location within the data by a thread is blocked;

enabling an exception to be raised when the location is next accessed; and

blocking the thread; and

when an exception is raised as a result of access by another thread to that location,

completing the access by that other thread to that location; and

restarting execution of the blocked thread.

20. The method of claim 19 wherein when access by the thread to the location is blocked, saving a state of the thread and storing a reference to the thread in the location.

21. The method of claim 20 wherein the reference is a pointer to a data structure that identifies the blocked thread and the saved state.

22. The method of claim 21 wherein the data structure indicates the value that was stored in the location before storing the reference.

23. A method in a computer system for reading from a buffer of data, the method comprising:

defining a pointer to point to a location within the buffer, the pointer having a synchronization access mode;

setting the synchronization access mode of the pointer to be either normal or sync to effect a desired behavior of accessing the buffer; and

under control of accessing code, reading from a location within the buffer using the pointer wherein a behavior of the accessing code depends on the setting of the synchronization access mode of the pointer and the behavior of the accessing code can be changed without modifying the accessing code.

24. The method of claim 23 wherein the setting of the synchronization access mode is changed to change the desired behavior of accessing the buffer.

25. The method of claim 23 wherein when the synchronization access mode is set to normal, the reading from the location within the buffer is permitted when the location is empty.

26. The method of claim 23 wherein when the synchronization access mode is set to sync, the reading from the location within the buffer is permitted only when the location is full.

27. The method of claim 23 wherein when the synchronization access mode is set to sync, writing to the location within the buffer is permitted only when the location is empty.

28. The method of claim 23 including storing in forwarding locations at located past an end of the buffer pointers to locations at the other end of the buffer, the pointers having forwarding enabled so that when a forwarding location is accessed, the access is directed to the pointed to location at the other end of the buffer.

29. The method of claim 23 including storing a pointer to an invalid location in a location adjacent to the buffer with forwarding of that location enabled so that when the location adjacent to the buffer is accessed an exception is raised.

30. The method of claim 23 including

when reading from the location within the buffer by a thread is blocked,

enabling an exception to be raised when the location is next accessed via a write access;

and

blocking the thread; and

when an exception is raised as a result of a write access to that location by another thread;

completing the write access to that location by that other thread; and

restarting execution of the blocked thread to complete the reading from the location.

31. A method in a computer system for writing to a buffer of data, the method comprising:

defining a pointer to point to a location within the buffer, the pointer having a synchronization access mode;

setting the synchronization access mode of the pointer to be either normal or sync to effect a desired behavior of accessing the buffer; and

under control of accessing code, writing to a location within the buffer using the pointer wherein behavior of the accessing code depends on the setting of the synchronization access mode of the pointer and can be changed without modifying the accessing code.

32. The method of claim 31 wherein the setting of the synchronization access mode is changed to change the desired behavior of accessing the buffer.

33. The method of claim 31 wherein when the synchronization access mode is set to normal, the writing to the location within the buffer is permitted when the location is full.

34. The method of claim 31 wherein when the synchronization access mode is set to sync, the writing to the location within the buffer is permitted only when the location is empty.

35. The method of claim 31 wherein when the synchronization access mode is set to sync, reading from the location within the, buffer is permitted only when the location is full.

36. The method of claim 31 including storing in forwarding locations located past an end of the buffer pointers to locations at the other end of the buffer, the pointers having forwarding enabled so that when a forwarding location is accessed, the access is directed to the pointed to location at the other end of the buffer.

37. The method of claim 31 including storing a pointer to an invalid location in a location adjacent to the buffer with forwarding of that location enabled so that when the location adjacent to the buffer is accessed an exception is raised.

38. The method of claim 31 including

when writing by a thread to the location is blocked;

enabling an exception to be raised when the location is next accessed via a read access; and

blocking the thread; and

when an exception is raised as a result of a read access by another thread to that location;

completing the read accessing from that location by that other thread; and

restarting execution of the blocked thread to complete the writing to the location.

39. A computer system for accessing data, comprising:

a buffer of data;

a read pointer and a write pointer that point to locations within the buffer, each pointer having a synchronization access mode being set to either unsynchronized or synchronized to effect a desired behavior of accessing the buffer of data;

a plurality of accessing programs that access the buffer of data using the read and write pointers; and

means for changing the setting of the synchronization access mode of a pointer to effect a change in the desired behavior of accessing the buffer of data without modifying the accessing programs.

40. The computer system of claim 39 the desired behavior of accessing the data is changed by changing the setting of the synchronization access mode of the pointers.

41. The computer system of claim 39 wherein when the synchronization access mode of the pointers is set to unsynchronized, access to the location within the data is permitted regardless of whether location is empty or full.

42. The computer system of claim 39 wherein when the synchronization access mode of the read pointer is set to synchronized, read access to the location within the data is permitted only when the location is full.

43. The computer system of claim 39 wherein when the synchronization access mode of the write pointer is set to synchronized, write access to the location within the data is permitted only when the location is empty.

44. The computer system of claim 39 wherein each accessing program operates in a different thread.

45. The computer system of claim 39 including storing in forwarding locations located past an end of the buffer pointers to locations at the other end of the data, the pointers having forwarding enabled so that when a forwarding location is accessed, the access is directed to the pointed to location at the other end of the buffer.

46. The computer system of claim 39 including storing a pointer to an invalid location in a location adjacent to the buffer with forwarding of that location enabled so that when the location adjacent to the buffer is accessed an exception is raised.

47. The computer system of claim 39 wherein the data is accessed by multiple reading threads and writing threads.

48. The computer system of claim 39 including

when access by a thread to a location pointed to by a pointer is blocked;

enabling an exception to be raised when the location is next accessed; and

blocking the thread; and

when an exception is raised as a result of access by another thread to that location;

completing the access by that other thread to that location; and

restarting execution of the blocked thread.

49. A computer system for accessing data, comprising:

means for storing data within a buffer;

means for pointing to locations within the buffer, the pointing means having a synchronization access mode;

means for changing the synchronization access mode of the pointing means; and

means for accessing the data of the buffer using the pointing means wherein the accessing behavior depends on the synchronization access mode of the pointing means.

50. The computer system of claim 49 wherein the accessing means includes multiple producers and multiple consumers of the data within the buffer.

51. The computer system of claim 49 wherein the pointing means includes a read pointer and a write pointer.

52. The computer system of claim 49 wherein when the synchronization access mode is set to synchronized, access to the location within the buffer is permitted regardless of whether location is empty or full.

53. The computer system of claim 49 wherein when the synchronization access mode is set to synchronized, read access to the location within the buffer is permitted only when the location is full.

54. The computer system of claim 49 wherein when the synchronization access mode is set to synchronized, write access to the location within the buffer is permitted only when the location is empty.

55. The computer system of claim 49 wherein the behavior of the accessing means is modified without modifying the accessing means.