MANAGING FAIRNESS FOR LOCK AND UNLOCK OPERATIONS USING OPERATION PRIORITIZATION

• US 20180293114A1
• Filed: 09/07/2017
• Published: 10/11/2018
• Est. Priority Date: 04/05/2017
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Mukherjee, Shubhendu Sekhar, Akkawi, Isam Wadih, Asher, David, Bertone, Michael, Carlson, David Albert, Dobbie, Bradley, Kessler, Richard Eugene
• Granted Patent: US 10,331,500 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Managing lock and unlock operations for a first thread executing on a first processor core includes, for each instruction included in the first thread and identified as being associated with: (1) a lock operation corresponding to a particular lock stored in a particular memory location, in response to determining that the particular lock has already been acquired, continuing to perform the lock operation for multiple attempts using associated operation messages for accessing the particular memory location, or (2) an unlock operation corresponding to a particular lock stored in a particular memory location, releasing the particular lock from the first thread using an associated operation message for accessing the particular memory location. Selected operation messages associated with an unlock operation are prioritized over operation messages associated with a lock operation.

Claims

1. A processor comprising:

a plurality of processor cores; and

instruction management circuitry configured to manage lock and unlock operations for a first thread executing on a first processor core of the plurality of processor cores, the managing including;

for each instruction included in the first thread and identified as being associated with a lock operation corresponding to a particular lock stored in a particular memory location, in response to determining that the particular lock has already been acquired, continuing to perform the lock operation for a plurality of attempts using associated operation messages for accessing the particular memory location, and

for each instruction included in the first thread and identified as being associated with an unlock operation corresponding to a particular lock stored in a particular memory location, releasing the particular lock from the first thread using an associated operation message for accessing the particular memory location;

wherein the processor is configured to prioritize selected operation messages associated with an unlock operation over operation messages associated with a lock operation.

2. The processor of claim 1, wherein the processor further includes interconnection circuitry configured to connect each processor core to a memory system of the processor.

3. The processor of claim 2, wherein the memory system includes a data structure that stores at least one priority queue that stores operation messages from the first processor core and operation messages from one or more other processor cores.

4. The processor of claim 3, wherein the priority queue stores all operation messages associated with an unlock operation at a higher priority than any operation messages associated with a lock operation, and operation messages are dequeued from the priority queue according to priority with higher priority operation messages being dequeued before lower priority operation messages.

5. The processor of claim 3, wherein all operation messages stored in the priority queue are associated with either (1) an unlock operation for a first lock stored in a first memory location, or (2) a lock operation for the first lock stored in the first memory location.

6. The processor of claim 5, wherein each processor core that sent an operation message stored in the priority queue is executing at most a single thread including an instruction associated with the first lock.

7. The processor of claim 1, wherein, after a predetermined threshold on the plurality of attempts, the first processor core places the first thread into an inactive state that enables the first processor core to temporarily execute threads other than the first thread until the first thread is placed back into an active state.

8. The processor of claim 7, wherein, after releasing the particular lock from the first thread, the first processor core determines if there are any waiting threads executing on a processor core other than the first processor core that were placed into the inactive state after at least one attempt at acquiring the particular lock, and if so, places at least one waiting thread back into the active state.

9. The processor of claim 1, wherein continuing to perform the lock operation for a plurality of attempts includes using a lock operation in a stored library accessible to the first thread.

10. The processor of claim 1, wherein the first processor core is configured to prioritize:

(1) the selected messages associated with instructions identified as being associated with an unlock operation, and (2) any messages associated with store instructions that are destined for a cache block that is being targeted by a pointer of the unlock operation.

11. A method for managing instructions on a processor comprising a plurality of processor cores, the method comprising:

managing lock and unlock operations for a first thread executing on a first processor core of the plurality of processor cores, the managing including;

for each instruction included in the first thread and identified as being associated with a lock operation corresponding to a particular lock stored in a particular memory location, in response to determining that the particular lock has already been acquired, continuing to perform the lock operation for a plurality of attempts using associated operation messages for accessing the particular memory location, and

for each instruction included in the first thread and identified as being associated with an unlock operation corresponding to a particular lock stored in a particular memory location, releasing the particular lock from the first thread using an associated operation message for accessing the particular memory location; and

prioritizing selected operation messages associated with an unlock operation over operation messages associated with a lock operation.

12. The method of claim 11, wherein interconnection circuitry connects each processor core to a memory system of the processor.

13. The method of claim 12, wherein the memory system includes a data structure that stores at least one priority queue that stores operation messages from the first processor core and operation messages from one or more other processor cores.

14. The method of claim 13, wherein the priority queue stores all operation messages associated with an unlock operation at a higher priority than any operation messages associated with a lock operation, and operation messages are dequeued from the priority queue according to priority with higher priority operation messages being dequeued before lower priority operation messages.

15. The method of claim 13, wherein all operation messages stored in the priority queue are associated with either (1) an unlock operation for a first lock stored in a first memory location, or (2) a lock operation for the first lock stored in the first memory location.

16. The method of claim 15, wherein each processor core that sent an operation message stored in the priority queue is executing at most a single thread including an instruction associated with the first lock.

17. The method of claim 11, wherein, after a predetermined threshold on the plurality of attempts, the first processor core places the first thread into an inactive state that enables the first processor core to temporarily execute threads other than the first thread until the first thread is placed back into an active state.

18. The method of claim 17, wherein, after releasing the particular lock from the first thread, the first processor core determines if there are any waiting threads executing on a processor core other than the first processor core that were placed into the inactive state after at least one attempt at acquiring the particular lock, and if so, places at least one waiting thread back into the active state.

19. The method of claim 11, wherein continuing to perform the lock operation for a plurality of attempts includes using a lock operation in a stored library accessible to the first thread.

20. The method of claim 11, wherein the first processor core prioritizes:

(1) the selected messages associated with instructions identified as being associated with an unlock operation, and (2) any messages associated with store instructions that are destined for a cache block that is being targeted by a pointer of the unlock operation.