Coupled lock allocation and lookup for shared data synchronization in symmetric multithreading environments

• US 8,868,849 B2
• Filed: 02/29/2012
• Issued: 10/21/2014
• Est. Priority Date: 08/17/2011
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Waddington, Daniel, Liu, Tongping, Tian, Chen
• Primary Examiner(s): CHOE, YONG J
• Application Number:
  US13/408,263
• Publication Number:
  US 20130046939A1
• Time in Patent Office: 965 Days
• Field of Search: 711/147, 711/152, 711/E12.094
• US Class Current: 711/147
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

In a shared memory process different threads may attempt to access a shared data variable in a shared memory. Locks are provided to synchronize access to shared data variables. Each lock is allocated to have a location in the shared memory relative to the instance of shared data that the lock protects. A lock may be allocated to be adjacent to the data that it protects. Lock resolution is facilitated because the memory location of a lock can be determined from an offset with respect to the data variable that is being protected by the lock.

Claims

1. A method of using locks in a multithreaded computing system having at least two processors and a shared memory process configuration, comprising:

for each instance of shared data in at least a portion of a shared memory, allocating a lock in the shared memory;

wherein each allocated lock has a corresponding lock location, and wherein the lock location is based on an offset for the lock relative to a memory location of the instance of shared data protected by the lock.

2. The method of claim 1, wherein:

each lock location of each allocated lock is a memory location that is proximate to a memory location of the instance of shared data protected by the lock; and

each allocated lock is allocated to be adjacent to the instance of shared data protected by the lock.

3. The method of claim 1, further comprising:

resolving a lock location for a lock protecting a particular instance of shared data in the shared memory based on a memory location of the particular instance of shared data and an offset relative to the memory location, wherein the lock location is the memory location adjusted by the offset.

4. The method of claim 1, wherein a particular instance of shared data is allocated together with a corresponding lock.

5. The method of claim 1, wherein each allocated lock is automatically allocated by a compiler.

6. The method of claim 1, wherein each allocated lock is implicitly defined with respect to the data it protects via a type system, such that a programmer does not have to explicitly define locks.

7. The method of claim 1, wherein each lock location of each allocated lock is based on an offset for the lock relative to a memory location of the instance of shared data protected by the lock, wherein the offset is based on a size of the instance of shared data protected by the lock.

8. A multithreaded computing system comprising:

at least two processors in a shared memory process configuration in which threads of the at least two processors access a shared memory, wherein accesses to shared data in the shared memory are synchronized, via lock allocation, for individual instances of shared data;

wherein each allocated lock has a corresponding lock location, and wherein the lock location is based on an offset for the lock relative to a memory location of the instance of shared data protected by the lock.

9. The system of claim 8, wherein:

each lock location of each allocated lock is a memory location that is proximate to a memory location of the instance of shared data protected by the lock; and

each allocated lock is allocated to be adjacent to the instance of shared data protected by the lock.

10. The system of claim 8, wherein:

a lock location for a lock protecting a particular instance of shared data in the shared memory is resolved based on a memory location of the particular instance of shared data and an offset relative to the memory location, wherein the lock location is the memory location adjusted by the offset.

11. The system of claim 8, wherein a particular instance of shared data is allocated together with a corresponding lock.

12. The system of claim 8, wherein each allocated lock is automatically allocated by a compiler.

13. The system of claim 8, wherein each allocated lock is implicitly defined with respect to the data it protects via a type system, such that a programmer does not have to explicitly define locks.

14. A method of resolving locks in a multithreaded computing system having at least two processors and a shared memory process configuration, comprising:

for each access to an instance of shared data in at least a portion of a shared memory, determining a memory location of a lock based on an offset for the lock relative to a memory location of the instance of shared data protected by the lock.

15. The method of claim 14, wherein:

each lock location of each allocated lock is a memory location that is proximate to a memory location of the instance of shared data protected by the lock; and

each allocated lock is allocated to be adjacent to the instance of shared data protected by the lock.

16. The method of claim 15, further comprising:

resolving a lock location for a lock protecting a particular instance of shared data in the shared memory based on a memory location of the particular instance of shared data and an offset relative to the memory location, wherein the lock location is the memory location adjusted by the offset.

17. A multithreaded computing system comprising:

at least two processors in a shared memory process configuration in which threads of the at least two processors access a shared memory, wherein lock resolution for a lock protecting an instance of shared data in the shared memory is determined based on an offset for the lock relative to a memory location of the instance of shared data.

18. The system of claim 17, wherein:

each lock location of each allocated lock is a memory location that is proximate to a memory location of the instance of shared data protected by the lock; and

each allocated lock is allocated to be adjacent to the instance of shared data protected by the lock.

19. The system of claim 17, wherein lock resolution for a lock protecting a particular instance of shared data in the shared memory is resolved based on a memory location of the particular instance of shared data and an offset relative to the memory location, wherein the lock has a memory location that is the memory location of the particular instance of shared data adjusted by the offset.

20. A non-transitory computer readable storage medium comprising computer readable instruction which when executed by a processor implement a method comprising:

for each access to an instance of shared data in at least a portion of a shared memory, determining a memory location of a lock based on an offset for the lock relative to a memory location of the instance of shared data protected by the lock.