Managing fairness for lock and unlock operations using operation prioritization

• US 10,331,500 B2
• Filed: 09/07/2017
• Issued: 06/25/2019
• 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
• Primary Examiner(s): Snyder, Steven G
• Application Number:
  US15/697,736
• Publication Number:
  US 20180293114A1
• Time in Patent Office: 656 Days
• Field of Search: None
• 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 operation messages associated with a lock operation or unlock operation include (1) information identifying a particular memory location to which access is being requested and (2) information identifying whether a lock operation or an unlock operation is being requested, and operation messages are sent by threads executing on the plurality of processor cores to a data structure stored in a memory system of the processor;

wherein the processor is configured to prioritize selected operation messages associated with an unlock operation over operation messages associated with a lock operation based at least in part on at least one of (1) an order among different operation messages stored in the data structure, or (2) relative priorities associated with the operation messages stored in the data structure.

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

3. The processor of claim 2, wherein the data structure 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;

wherein operation messages associated with a lock operation or unlock operation include (1) information identifying a particular memory location to which access is being requested and (2) information identifying whether a lock operation or an unlock operation is being requested, and operation messages are sent by threads executing on the plurality of processor cores to a data structure stored in a memory system of the processor; and

prioritizing selected operation messages associated with an unlock operation over operation messages associated with a lock operation based at least in part on at least one of (1) an order among different operation messages stored in the data structure, or (2) relative priorities associated with the operation messages stored in the data structure.

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

13. The method of claim 12, wherein the data structure 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.

21. 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 (1) selected operation messages 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 over (3) operation messages associated with a lock operation.

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

23. The processor of claim 22, 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.

24. The processor of claim 23, 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.

25. The processor of claim 23, 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.

26. The processor of claim 25, 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.

27. 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 (1) selected operation messages 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 over (3) operation messages associated with a lock operation.

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

29. The method of claim 28, 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.

30. The method of claim 29, 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.

31. The method of claim 29, 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.

32. The method of claim 31, 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.