System and method for guaranteeing transactional fairness among multiple requesters
A system and method for guaranteeing transactional fairness among multiple requesters contending for a common resource in a cache-coherent multiprocessor system is described. Batch processing is used to control servicing of multiple requests made by multiple requesters (such as processors) of a common resource in a cache-coherent multiprocessor system. Specifically, identification numbers are assigned to requests as they are received from the multiple requesters. The identification numbers are then used in conjunction with batch processing to prioritize and guarantee servicing of the requests.
1. A system for guaranteeing fairness of transactions between multiple requestors, comprising:
an identification generator configured to generate a continuous ring of batch numbers in a sequential order from a lowest batch number to a highest-batch number, wherein the highest batch number and the lowest batch number of the batch numbers are contiguous;
a request assignment unit configured to assign identification numbers to requests made by the requesters;
a sliding-window comprising a fixed-range of the identification numbers configured to advance through the continuous ring of identification numbers in sequential order one or more identification numbers at a time, after at least one of an oldest pending request, having an identification number within the fixed-range of identification numbers, is serviced; and
a transaction authorization unit, configured to authorize a particular request be serviced if the identification number associated with the particular request is within the fixed-range of identification numbers indicated by the sliding-window;
wherein the fixed-range of batch number indicated by the sliding-window equals one or more batches each comprising a predetermined plurality of identification numbers.
2. The system as recited in claim 1 , wherein the transaction authorization unit is further configured to issue a retry notification to one of the requesters, if a particular identification number assigned to a particular request is not within the fixed-range of identification numbers indicated by the sliding-window.
3. The system as recited in claim 1 , wherein the identification generator comprises one or more counters.
4. The system as recited in claim 1 , wherein the sliding-window comprises one or more counters.
5. A method for guaranteeing transactional fairness among multiple requesters, comprising:
receiving a request from a particular requester;
assigning a batch number and an identification number to the request if the request is new, wherein if the request is retried the request already comprises an assigned batch number and an assigned identification number indicating that the request was previously received before;
determining whether the identification number is within a sliding-window;
enabling the request to be serviced, if the identification number is within the sliding-window for servicing the request and there are no conflicts associated with servicing the request; and
advancing the sliding-window after an oldest pending request with a assigned identification number in the sliding-window is enabled for service
wherein
a continuous ring of batch numbers in a sequential order from a lowest-batch number to a highest-batch number, wherein the highest-batch number and the lowest batch number of the batch numbers are contiguous; and
the fixed-range of batch number indicated by the sliding-window equals one or more batches each comprising a predetermined plurality of identification numbers.
6. The method as recited in claim 5 , further comprising instructing the particular requester to retry the request at a later time if the identification number associated with the request is not within the sliding-window.
7. The method as recited in claim 5 , further comprising instructing the particular requester to retry the request, if there is a conflict associated with servicing the request.
8. The method as recited in claim 5 , wherein the sliding-window comprises a fixed-number of identification numbers.
9. The method as recited in claim 5 , wherein the sliding-window comprises one or more batches each comprising a fixed-number of identification numbers.
10. The method as recited in claim 5 , further comprising instructing the particular requester to retry the request at a later time if the identification number associated with the request is not within the sliding-window, wherein instructing the particular requester to retry the request comprises issuing a retry notification message to the particular requester, the retry notification message comprising the identification number assigned to the request.
11. The method as recited in claim 5 , wherein the method is performed by a control system associated with a cache-coherent system.
12. The method as recited in claim 5 , wherein the method is performed by a control system associated with an input/output device.
13. The method as recited in claim 5 , wherein each requester is an agent in a multiple agent system.
14. The method as recited in claim 5 , wherein each requester is a processor in a multiple processor system.
15. The method as recited in claim 5 , wherein each request is a request to perform a particular transaction.
16. The method as recited in claim 5 , wherein determining whether the identification number is within a sliding-window for servicing the request comprises comparing the identification number to a range of identification numbers associated with the sliding-window to determine whether the identification number associated with the request is between the range of identification numbers associated with the sliding-window.
17. In a cache-coherent multiprocessor system, a coherency controller for preventing live locks by guaranteeing fairness of transactions between multiple requestors, the coherency controller comprising:
an identification generator configured to generate a continuous ring of batch numbers in a sequential order from a lowest batch number to a highest-batch number, wherein the highest batch number and the lowest batch number of the batch numbers are contiguous;
a request assignment unit configured to assign identification numbers to requests made by the requesters;
a sliding-window comprising a fixed-range of the identification numbers configured to advance through the continuous ring of identification numbers in sequential order one or more identification numbers at a time, after at least one of an oldest pending request, having an identification number within the fixed-range of identification numbers, is serviced; and
a transaction authorization unit, configured to authorize a particular request be serviced if the identification number associated with the particular request is within the fixed-range of identification numbers indicated by the sliding-window;
wherein the fixed-range of batch number indicated by the sliding-window equals one or more batches each comprising a predetermined plurality of identification numbers.
18. In a multiprocessor system, a system for preventing live locks by guaranteeing fairness of transactions, the system comprising:
requesting agents configured to send requests to a responding agent, each request agent identifies whether the request is a new request or a retried request, wherein if the request is retried the request already comprises an assigned identification number indicating that the request was previously made by the requesting agent;
a responding agent, configured to:
(i) receive a request from a particular requester and assign an a batch number and an identification number to the request if the request is new, wherein if the request is retried the request already comprises an assigned batch number and an assigned identification number indicating that the request was previously received before,
(ii) determine whether the identification number is within a sliding-window of identification numbers currently being serviced;
(iii) enable the request to be serviced, if the identification number is within the sliding-window of identification numbers and there are no conflicts associated with servicing the request; and
(iv) advance the sliding-window only after an oldest pending request with an assigned identification number within the sliding-window is enabled for service
wherein
a continuous ring of batch numbers in a sequential order from a lowest-batch number to a highest-batch number, wherein the highest-batch number and the lowest batch number of the batch numbers are contiguous; and
the fixed-range of batch number indicated by the sliding-window equals one or more batches each comprising a predetermined plurality of identification numbers.
19. The system as recited in claim 18 , wherein the responding agent is further configured to notify the particular requester to retry the request at a later time if the identification number associated with the request is not within the sliding-window.
20. The system as recited in claim 18 , wherein the sliding-window comprises a fixed number of identification numbers.
21. The system as recited in claim 18 , wherein the sliding-window comprises one or more batches each comprising a fixed-number of identification numbers.
22. The system as recited in claim 18 , wherein the responding agent comprises a counter configured to generate an of identification number for assignment to a new request each time a new request is received.