Concurrent computing with reduced locking requirements for shared data

• US 9,563,484 B2
• Filed: 01/27/2016
• Issued: 02/07/2017
• Est. Priority Date: 08/27/2013
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Yellin, Daniel M.
• Primary Examiner(s): NGUYEN, VAN H
• Application Number:
  US15/007,836
• Publication Number:
  US 20160139967A1
• Time in Patent Office: 377 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

Where data are shared by multiple computer processing threads, modifying the data by determining whether modifying data associated with a first computer processing thread violates a constraint associated with the data, and responsive to determining that modifying the data associated with the computer processing thread violates the constraint associated with the data, using the data associated with the first computer processing thread to modify the data shared by the multiple computer processing threads that includes the first computer processing thread, where the constraint associated with the data associated with the first computer processing thread represents a portion of a tolerance value that is associated with the data shared by the multiple computer processing threads and that is divided among multiple constraints, where each of the constraints is associated with a different one of the multiple computer processing threads.

Claims

1. A computer-implemented method, comprising:

determining whether modifying data associated with a first computer processing thread violates a constraint associated with the data; and

using, responsive to a determination that the modifying the data violates the constraint associated with the data, the data to modify data shared by multiple computer processing threads that includes the first computer processing thread, wherein

the constraint represents a portion of a tolerance value that is

a) associated with the data shared by the multiple computer processing threads and

b) divided among a plurality of constraints and each of the plurality of constraints is associated with a different one of the multiple computer processing threads.

2. The method of claim 1, further comprising:

configuring a set of computer software instructions to perform the determining and the using.

3. The method of claim 2, further comprising:

causing each of the multiple computer processing threads to execute a different instance of the computer software instructions.

4. The method of claim 1, wherein

the data shared by the multiple computer processing threads is a single numeric value.

5. The method of claim 1, wherein

the data shared by the multiple computer processing threads is a set of multiple elements.

6. The method of claim 1, wherein

each of the multiple computer processing threads has an associated own thread-local data for storing modifications intended for the data shared by the multiple computer processing thread.

7. A computer hardware system, comprising:

at least one hardware processor configured to initiate the following executable operations;

determining whether modifying data associated with a first computer processing thread violates a constraint associated with the data; and

using, responsive to a determination that the modifying the data violates the constraint associated with the data, the data to modify data shared by multiple computer processing threads that includes the first computer processing thread, wherein

the constraint represents a portion of a tolerance value that is

a) associated with the data shared by the multiple computer processing threads and

b) divided among a plurality of constraints and each of the plurality of constraints is associated with a different one of the multiple computer processing threads.

8. The system of claim 7, wherein the at least one hardware processor is further configured to initiate the following executable operation:

configuring a set of computer software instructions to perform the determining and the using.

9. The system of claim 8, wherein the at least one hardware processor is further configured to initiate the following executable operation:

causing each of the multiple computer processing threads to execute a different instance of the computer software instructions.

10. The system of claim 7, wherein

the data shared by the multiple computer processing threads is a single numeric value.

11. The system of claim 7, wherein

the data shared by the multiple computer processing threads is a set of multiple elements.

12. The system of claim 7, wherein

each of the multiple computer processing threads has an associated own thread-local data for storing modifications intended for the data shared by the multiple computer processing thread.

13. The system of claim 7, wherein the at least one hardware processor is further configured to initiate the following executable operation:

modifying the data associated with the first computer processing thread with a modification intended for the data shared by the multiple computer processing threads upon a determination that the modification does not violate the constraint.

14. A computer program product, comprising:

a hardware storage device having stored therein computer-readable program code for testing a computer software application,

the computer-readable program code, when executed by a computer hardware system, causes the computer hardware system to perform;

determining whether modifying data associated with a first computer processing thread violates a constraint associated with the data; and

using, responsive to a determination that the modifying the data violates the constraint associated with the data, the data to modify data shared by multiple computer processing threads that includes the first computer processing thread, wherein

the constraint represents a portion of a tolerance value that is

a) associated with the data shared by the multiple computer processing threads and

b) divided among a plurality of constraints and each of the plurality of constraints is associated with a different one of the multiple computer processing threads.

15. The computer program product of claim 14, wherein the computer-readable program code further causes the computer hardware system to perform:

configuring a set of computer software instructions to perform the determining and the using.

16. The computer program product of claim 15, wherein the computer-readable program code further causes the computer hardware system to perform:

causing each of the multiple computer processing threads to execute a different instance of the computer software instructions.

17. The computer program product of claim 14, wherein

the data shared by the multiple computer processing threads is a single numeric value.

18. The computer program product of claim 14, wherein

the data shared by the multiple computer processing threads is a set of multiple elements.

19. The computer program product of claim 14, wherein

each of the multiple computer processing threads has an associated own thread-local data for storing modifications intended for the data shared by the multiple computer processing thread.

20. The computer program product of claim 14, wherein the computer-readable program code further causes the computer hardware system to perform:

modifying the data associated with the first computer processing thread with a modification intended for the data shared by the multiple computer processing threads upon a determination that the modification does not violate the constraint.