Concurrent access of shared resources utilizing tracking of request reception and completion order

• US 7,047,337 B2
• Filed: 04/24/2003
• Issued: 05/16/2006
• Est. Priority Date: 04/24/2003
• Status: Active Grant

• Current Assignee: Lenovo International Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Armstrong, Troy David, Lucke, Kyle Alan
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): PHAN, RAYMOND NGAN
• Application Number:
  US10/422,193
• Publication Number:
  US 20040215858A1
• Time in Patent Office: 1,118 Days
• Field of Search: 709100-108, 709213-219, 710/200, 710 60- 61, 710240-244, 710104-119, 718/104, 711/150
• US Class Current: 710/200
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

An apparatus, program product and method to manage access to a shared resource by a plurality of processes in a multithreaded computer via a collection of atomic operations that track both the order in which requests that use a shared resource are received, and the order in which processing of such requests are completed after they are received. Dispatching of requests is effectively deferred until processing of all non-dispatched requests that were received earlier than a most recently completed request has been completed. In many instances, completion of processing of requests can be performed non-atomically, thus reducing contention issues with respect to the shared resource. Furthermore, dispatching of requests may be batched to reduce the overhead associated with individual dispatch operations.

Claims

1. A method of accessing a shared resource in a computer, the method comprising, in a first process among a plurality of processes capable of asynchronously issuing requests that use the shared resource:

atomically assigning a unique identifier to a current request that uses the shared resource, wherein the unique identifier is assigned to the current request based upon the order in which the current request is received relative to other requests issued by the plurality of processes;

completing processing of the current request using the unique identifier;

atomically incrementing a count of completed requests after processing of the current request is complete;

atomically determining if processing of every other request issued prior to a most recently completed request has been completed after processing of the current request is complete; and

in response to determining that processing of every other request issued prior to the most recently completed request has been completed, dispatching each non-dispatched request for which processing has completed.

2. The method of claim 1, wherein completing processing of the current request is performed non-atomically.

3. The method of claim 1, further comprising, in the first process, atomically determining if the current request is the most recently completed request after processing of the current request is complete.

4. The method of claim 1, further comprising, in the first process, after processing of the current request is complete, atomically determining if the current request is the first request issued after a last dispatch operation, and dispatching the current request in response to determining that the current request is the first request issued after the last dispatch operation.

5. The method of claim 1, wherein dispatching each non-dispatched request for which processing has completed includes dispatching a plurality of requests in a batch.

6. The method of claim 1, wherein atomically assigning the unique identifier to the current request includes incrementing a request counter, wherein atomically incrementing the count of completed requests includes incrementing a done counter, wherein the method further comprises atomically updating a last done counter to the unique identifier of the current request after completing processing of the current request is complete in response to determining that the current request is the most recently completed request, wherein atomically determining if processing of every other request issued prior to the most recently completed request has been completed includes comparing the last done counter to the done counter, and wherein dispatching each non-dispatched request for which processing has completed includes updating a last dispatch counter to equal the last done counter.

7. The method of claim 1, further comprising:

in response to determining that processing of every other request issued prior to the most recently completed request has not been completed, deferring dispatching of each non-dispatched request for which processing has completed; and

in a second process among the plurality of processes;

completing processing of an earlier request to the current request, the earlier request having a unique identifier assigned thereto that precedes that of the current request;

atomically determining that processing of every other request issued prior to the most recently completed request has been completed after processing of the earlier request is complete; and

in response to determining that processing of every other request issued prior to the most recently completed request has been completed, dispatching each non-dispatched request for which processing has completed.

8. The method of claim 1, wherein completing processing of the current request includes preparing the request.

9. The method of claim 1, wherein the shared resource comprises at least one slot in a frame buffer of an input/output adapter, wherein completing processing of the current request comprises communicating data using the slot, and wherein dispatching each non-dispatched request comprises notifying a client of reception of the communicated data.

10. The method of claim 1, wherein the shared resource is selected from the group consisting of a processor, a hardware device, an input/output device, a storage device, an adapter, a controller, a database, a file system, a service, and a component of the same.

11. The method of claim 6, wherein each of the request, done, last done and last dispatch counters is updated using a monotonically-increasing sequence of numbers.

12. The method of claim 9, wherein the computer comprises a logically-partitioned computer, and wherein the input/output adapter is a virtual input/output adapter coupled to a virtual local area network used for inter-partition communication in the logically-partitioned computer.

13. An apparatus, comprising:

a shared resource;

at least one processor configured to execute a plurality of processes capable of asynchronously issuing requests that use the shared resource; and

program code configured to be executed on the at least one processor in a first process to atomically assign a unique identifier to a current request that uses the shared resource;

complete processing of the current request using the unique identifier;

atomically increment a count of completed requests after processing of the current request is complete;

atomically determine if processing of every other request issued prior to a most recently completed request has been completed after processing of the current request is complete; and

in response to determining that processing of every other request issued prior to the most recently completed request has been completed, dispatch each non-dispatched request for which processing has completed, wherein the unique identifier is assigned to the current request based upon the order in which the current request is received relative to other requests issued by the plurality of processes.

14. The apparatus of claim 13, wherein the program code is configured to complete processing of the current request non-atomically.

15. The apparatus of claim 13, wherein the program code is further configured to atomically determine if the current request is the most recently completed request after processing of the current request is complete.

16. The apparatus of claim 13, wherein the program code is further configured to, after processing of the current request is complete, atomically determine if the current request is the first request issued after a last dispatch operation, and dispatch the current request in response to determining that the current request is the first request issued after the last dispatch operation.

17. The apparatus of claim 13, wherein the program code is configured to dispatch each non-dispatched request for which processing has completed by dispatching a plurality of requests in a batch.

18. The apparatus of claim 13, further comprising a request counter, a done counter, a last done counter and a last dispatch counter, wherein the program code is configured to atomically assign the unique identifier to the current request by incrementing the request counter, wherein the program code is configured to atomically increment the count of completed requests by incrementing the done counter, wherein the program code is further configured to atomically update the last done counter to the unique identifier of the current request after completing processing of the current request is complete in response to determining that the current request is the most recently completed request, wherein the program code is configured to atomically determine if processing of every other request issued prior to the most recently completed request has been completed by comparing the last done counter to the done counter, and wherein the program code is configured to dispatch each non-dispatched request for which processing has completed further by updating the last dispatch counter to equal the last done counter.

19. The apparatus of claim 13, wherein the program code is first program code, wherein the first program code is further configured to defer dispatching of each non-dispatched request for which processing has completed in response to determining that processing of every other request issued prior to the most recently completed request has not been completed, and wherein the apparatus further comprises second program code configured to execute on the at least one processor in a second process to complete processing of an earlier request to the current request, the earlier request having a unique identifier assigned thereto that precedes that of the current request;

atomically determine that processing of every other request issued prior to the most recently completed request has been completed after processing of the earlier request is complete; and

in response to determining that processing of every other request issued prior to the most recently completed request has been completed, dispatch each non-dispatched request for which processing has completed.

20. The apparatus of claim 13, wherein the program code is configured to complete processing of the current request by preparing the request.

21. The apparatus of claim 13, wherein the shared resource comprises at least one slot in a frame buffer of an input/output adapter, wherein the program code is configured to complete processing of the current request by communicating data using the slot, and wherein the program code is configured to dispatch each non-dispatched request by notifying a client of reception of the communicated data.

22. The apparatus of claim 13, wherein the shared resource is selected from the group consisting of a processor, a hardware device, an input/output device, a storage device, an adapter, a controller, a database, a file system, a service, and a component of the same.

23. The apparatus of claim 18, wherein each of the request, done, last done and last dispatch counters is updated using a monotonically-increasing sequence of numbers.

24. The apparatus of claim 21, wherein the apparatus comprises a logically-partitioned computer, and wherein the input/output adapter is a virtual input/output adapter coupled to a virtual local area network used for inter-partition communication in the logically-partitioned computer.

25. A program product, comprising:

program code configured to be executed in a first process among a plurality of processes in a computer that are capable of asynchronously issuing requests that use a shared resource to atomically assign a unique identifier to a current request that uses the shared resource;

complete processing of the current request using the unique identifier;

atomically increment a count of completed requests after processing of the current request is complete;

atomically determine if processing of every other request issued prior to a most recently completed request has been completed after processing of the current request is complete; and

in response to determining that processing of every other request issued prior to the most recently completed request has been completed, dispatch each non-dispatched request for which processing has completed, wherein the unique identifier is assigned to the current request based upon the order in which the current request is received relative to other requests issued by the plurality of processes; and

a tangible computer readable signal bearing medium bearing the program code.