Semaphore with timeout and lock-free fast path for message passing architectures

• US 9,772,888 B2
• Filed: 04/10/2013
• Issued: 09/26/2017
• Est. Priority Date: 04/10/2013
• Status: Active Grant

• Current Assignee: Wind River Systems Incorporated (Aptiv PLC)
• Original Assignee: Wind River Systems Incorporated (Aptiv PLC)
• Inventors: Richardson, Raymond, Stults, Gregory
• Primary Examiner(s): Zaman, Faisal M
• Application Number:
  US13/859,852
• Publication Number:
  US 20140310438A1
• Time in Patent Office: 1,630 Days
• Field of Search: 710200, 707704
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The exemplary embodiments describe systems and methods for utilizing a semaphore with timeout and lock-free path for message passing architectures. One embodiment is related to a method comprising receiving a request from a client to access an object, the object including a plurality of resources, placing the request in a lock-free pend queue of a semaphore, manipulating a count of the semaphore based on an availability of at least one of the plurality of resources, and determining whether the client can use a fast path to the object.

Claims

1. A method, comprising:

receiving a request from a client to access an object, the object including a plurality of resources;

placing the request in a lock-free pend queue of a semaphore, the lock-free pend queue excluding a locking operation on the semaphore that prevents the semaphore from being isolated;

manipulating a decision variable based on an availability of at least one of the plurality of resources;

determining whether the client can use a fast path to the object by atomically manipulating the decision variable, wherein the fast path is an operation that utilizes a lock-free path to the object; and

tracking elapsed time to manage semaphore timeouts,

wherein at least one of the semaphore timeouts is used to adjust the decision variable.

2. The method of claim 1, further comprising:

releasing a thread from the lock-free pend queue upon receiving a pend message.

3. The method of claim 1, wherein the decision variable includes a release count and an in-flight release count.

4. The method of claim 3, further comprising:

incrementing the release count when the lock-free pend queue is empty;

releasing a thread immediately upon receiving a pend message; and

decrementing the release count upon release.

5. The method of claim 1, further comprising:

releasing a thread having an expired timeout.

6. The method of claim 1, wherein lock-free pend queue is a data structure capable of maintaining a specified order scheme of blocked clients on the semaphore.

7. The method of claim 1, wherein the decision variable is an atomically modifiable variable visible in memory to all entities that make use of the semaphore.

8. The method of claim 1, wherein the fast path is free of messaging and blocking.

20. The method of claim 1, wherein the decision variable is a count that includes a first range and a second range, wherein the first range of the count indicates free resources that and the second range of the count indicates a number of waiting clients.

9. A system, comprising:

an object including a plurality of resources;

a semaphore including a lock-free pend queue and a decision variable; and

an iso-locator core receiving a request from a client to access the object, placing the request in the lock-free pend queue of the semaphore, manipulating the decision variable of the semaphore based on an availability of at least one of the plurality of resources, and determining whether the client can use a fast path to the object by atomically manipulating the decision variable,

wherein the fast path is an operation that uses a lock-free path to the object,

wherein the lock-free pend queue excludes a locking operation on the semaphore that prevents the semaphore from being isolated,

wherein the iso-locator core further tracks elapsed time to manage semaphore timeouts, and wherein at least one of the semaphore timeouts is used to adjust the decision variable.

10. The system of claim 9, wherein the iso-locator core further releases a thread from the lock-free pend queue upon receive a pend message.

11. The system of claim 9, wherein the decision variable includes a release count and an in-flight release count.

12. The system of claim 11, wherein the iso-locator core further increments the release count when the lock-free pend queue is empty, releases a thread immediately upon receiving a pend message, and decrements the release count upon release.

13. The system of claim 9, wherein the iso-locator core further releases a thread having an expired timeout.

14. The system of claim 9, wherein lock-free pend queue is a data structure capable of maintaining a specified order scheme of blocked clients on the semaphore.

15. The system of claim 9, wherein the decision variable is an atomically modifiable variable visible in memory to all entities that make use of the semaphore.

16. The system of claim 9, wherein the fast path is free of messaging and blocking.

17. A computer readable storage medium including a set of instructions executable by a processor, the set of instructions operable to:

receive a request from a client to access an object, the object including a plurality of resources;

place the request in a lock-free pend queue of a semaphore, the lock-free pend queue excluding a locking operation on the semaphore that prevents the semaphore from being isolated;

manipulate a decision variable based on an availability of at least one of the plurality of resources;

determine whether the client can use a fast path to the object by atomically manipulating the decision variable, wherein the fast path is an operation that utilizes a lock-free path to the object; and

track elapsed time to manage semaphore timeouts,

wherein at least one of the semaphore timeouts is used to adjust the decision variable.

18. The computer readable storage medium of claim 17, wherein the decision variable includes a release count, and wherein the instructions are further operable to:

increment the release count when the lock-free pend queue is empty;

release a thread immediately upon receiving a pend message; and

decrement the release count upon release.

19. The computer readable storage medium of claim 17, wherein lock-free pend queue is a data structure capable of maintaining a specified order scheme of blocked clients on the semaphore.