Adaptive lock for a computing system having multiple runtime environments and multiple processing units

• US 9,424,103 B2
• Filed: 09/30/2014
• Issued: 08/23/2016
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: Hong Kong Applied Science And Technology Research Institute Co., Ltd.
• Original Assignee: Hong Kong Applied Science And Technology Research Institute Co., Ltd.
• Inventors: Al, Yi, Xu, Lin, Lu, Jianchao, Zhang, Shaohua
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): Wang, Ben C
• Application Number:
  US14/501,026
• Publication Number:
  US 20160092280A1
• Time in Patent Office: 693 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 8/456 Parallelism detection
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• 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

Abstract

A method for operating a lock in a computing system having plural processing units and running under multiple runtime environments is provided. When a requester thread attempts to acquire the lock while the lock is held by a holder thread, determine whether the holder thread is suspendable or non-suspendable. If the holder thread is non-suspendable, put the requester thread in a spin state regardless of whether the requester thread is suspendable or non-suspendable; otherwise determines whether the requester thread is suspendable or non-suspendable unless the requester thread quits acquiring the lock. If the requester thread is non-suspendable, arrange the requester thread to attempt acquiring the lock again; otherwise add the requester thread to a wait queue as an additional suspended thread. Suspended threads stored in the wait queue are allowable to be resumed later for lock acquisition. The method is applicable for the computing system with a multicore processor.

Claims

1. A method for operating a lock in a computing system having plural processing units, the lock being acquirable and releasable by plural threads generated in the computing system where each of the threads is either suspendable or non-suspendable, the method comprising:

in response to a lock-acquiring attempt made by a requester thread among the plural threads when the lock is held by a holder thread among the plural threads, determining, by a first processing unit that is assigned to execute the requester thread, whether the holder thread is suspendable or non-suspendable;

when the first processing unit determines that the holder thread is non-suspendable, configuring, by the first processing unit, the requester thread to be in a spin state regardless of whether the requester thread is suspendable or non-suspendable, wherein the spin state is characterized by the requester thread continually making the lock-acquiring attempt and the first processing unit checking whether the attempt is successful;

when the first processing unit determines that the holder thread is suspendable, determining, by the first processing unit, whether the requester thread is suspendable or non-suspendable unless the requester thread quits acquiring the lock;

when the first processing unit determines that the requester thread is non-suspendable after the holder thread is determined to be suspendable, arranging, by the first processing unit, the requester thread to make the lock-acquiring attempt again; and

when the first processing unit determines that the requester thread is suspendable after the holder thread is determined to be suspendable, adding, by the first processing unit, the requester thread to a wait queue as an additional suspended thread, wherein the wait queue is configured to store plural suspended threads that are allowable to be resumed by one of the plural processing units.

2. The method of claim 1, further comprising:

when the holder thread releases the lock, performing a lock-release procedure by one of the plural processing units wherein the lock-release procedure comprises;

(a) if the wait queue has one or more suspended threads, selecting one suspended thread from the wait queue, and resuming this selected suspended thread so that this resumed thread is re-arranged to acquire the lock.

3. The method of claim 2, wherein the performing of the lock-release procedure is further configured such that the lock-release procedure is performed only when the holder thread is suspendable.

4. The method of claim 1, further comprising:

when the lock is not held by any of the plural threads and the requester thread makes the lock-acquiring attempt, acquiring, by the first processing unit, the lock so that a shared resource corresponding to the lock becomes accessible by the requester thread.

5. The method of claim 1, wherein:

the lock is realized as a lock context that is a data structure in a global shared memory block of the computing system, the global shared memory block being visible to the plural threads and accessible by the plural processing units; and

the wait queue is realized as another data structure in the global shared memory block.

6. The method of claim 5, wherein:

the lock context includes a lock state for indicating whether or not the lock is held, and a holder type for indicating whether the holder thread is suspendable or non-suspendable when the lock is held; and

the wait queue includes a tag for each of suspended threads stored in the wait queue, the tags for the suspended threads being configured such that an order of arrival of all the suspended threads in the wait queue is determinable.

7. The method of claim 6, further comprising:

fetching, by the first processing unit, the lock state'"'"'s value from the lock context;

comparing, by the first processing unit, the fetched value of the lock state with a pre-determined value so as to determine whether the lock is held by any of the plural threads; and

when it is determined that the lock is not held by any of the plural threads, updating, by the first processing unit, the lock state and the holder type in order that the requester thread acquires the lock.

8. The method of claim 7, wherein the fetching of the lock state'"'"'s value, the comparing of the fetched value with the pre-determined value and the updating of the lock state and the holder type are configured to be performed in one atomic operation when it is determined that the lock is not held.

9. A computing system comprising:

plural processing units; and

a global shared memory block, a portion of which is assignable to establish a lock for controlling accessibility of a shared resource in the computing system, the lock being acquirable and releasable by plural threads that are generable in the computing system, each of the threads being configured to be either suspendable or non-suspendable, the global shared memory block being configured to be visible to the plural threads and accessible by the plural processing units;

wherein the lock is configured to be operated according to the method of claim 1.

10. The computing system of claim 9, wherein the plural processing units are located in a multicore processor.

11. A computing system comprising:

plural processing units; and

a global shared memory block, a portion of which is assignable to establish a lock for controlling accessibility of a shared resource in the computing system, the lock being acquirable and releasable by plural threads that are generable in the computing system, each of the threads being configured to be either suspendable or non-suspendable, the global shared memory block being configured to be visible to the plural threads and accessible by the plural processing units;

wherein the lock is configured to be operated according to the method of claim 2.

12. The computing system of claim 11, wherein the plural processing units are located in a multicore processor.

13. A computing system comprising:

plural processing units; and

a global shared memory block, a portion of which is assignable to establish a lock for controlling accessibility of a shared resource in the computing system, the lock being acquirable and releasable by plural threads that are generable in the computing system, each of the threads being configured to be either suspendable or non-suspendable, the global shared memory block being configured to be visible to the plural threads and accessible by the plural processing units;

wherein the lock is configured to be operated according to the method of claim 5.

14. The computing system of claim 13, wherein the plural processing units are located in a multicore processor.

15. A computing system comprising:

plural processing units; and

a global shared memory block, a portion of which is assignable to establish a lock for controlling accessibility of a shared resource in the computing system, the lock being acquirable and releasable by plural threads that are generable in the computing system, each of the threads being configured to be either suspendable or non-suspendable, the global shared memory block being configured to be visible to the plural threads and accessible by the plural processing units;

wherein the lock is configured to be operated according to the method of claim 6.

16. The computing system of claim 15, wherein the plural processing units are located in a multicore processor.

17. A computing system comprising:

plural processing units; and

a global shared memory block, a portion of which is assignable to establish a lock for controlling accessibility of a shared resource in the computing system, the lock being acquirable and releasable by plural threads that are generable in the computing system, each of the threads being configured to be either suspendable or non-suspendable, the global shared memory block being configured to be visible to the plural threads and accessible by the plural processing units;

wherein the lock is configured to be operated according to the method of claim 7.

18. The computing system of claim 17, wherein the plural processing units are located in a multicore processor.

19. A method for operating a lock in a computing system having plural processing units, the lock being acquirable and releasable by plural threads generated in the computing system where each of the threads is either suspendable or non-suspendable, the method comprising:

in response to a lock-acquiring attempt made by a requester thread among the plural threads when the lock is held by a holder thread among the plural threads, determining, by a first processing unit that is assigned to execute the requester thread, whether the holder thread is suspendable or non-suspendable;

when the first processing unit determines that the holder thread is non-suspendable, configuring, by the first processing unit, the requester thread to be in a spin state regardless of whether the requester thread is suspendable or non-suspendable, wherein the spin state is characterized by the requester thread continually making the lock-acquiring attempt and the first processing unit checking whether the attempt is successful;

when the first processing unit determines that the holder thread is suspendable, determining, by the first processing unit, whether the requester thread is suspendable or non-suspendable unless the requester thread quits acquiring the lock; and

when the first processing unit determines that the requester thread is suspendable after the holder thread is determined to be suspendable, adding, by the first processing unit, the requester thread to a wait queue as an additional suspended thread, wherein the wait queue is configured to store plural suspended threads that are allowable to be resumed by one of the plural processing units.

20. A computing system comprising:

plural processing units; and

a global shared memory block, a portion of which is assignable to establish a lock for controlling accessibility of a shared resource in the computing system, the lock being acquirable and releasable by plural threads that are generable in the computing system, each of the threads being configured to be either suspendable or non-suspendable, the global shared memory block being configured to be visible to the plural threads and accessible by the plural processing units;

wherein the lock is configured to be operated according to the method of claim 19.