Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
2000-11-09
2003-09-23
Auve, Glenn A. (Department: 2189)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S243000, C710S040000, C710S309000, C710S240000
Reexamination Certificate
active
06625678
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a livelock avoidance method, and, more particularly, to a livelock avoidance method in a data processing apparatus, which comprises a plurality of bus converters connected with each other in hierarchy and retries a request to be executed.
2. Description of the Related Art
The ordering standard of “Any normal response following a preceding write request without any preceding response must not go ahead of the preceding write request” is outlined in the PC1 bus standard. In order to keep up this ordering standard, the normal response should not be executed prior to the write request.
In a data processing apparatus including a plurality of bus converters which are connected with each other in hierarchy, in a case where a normal request buffer or a normal response buffer is busy in a bus converter, deadlock may possibly occur as a result of a violation in the ordering standard.
In prior art, in order to avoid the occurrence of any deadlock situation, in, a case where a normal response buffer is busy, the bus converter converts a request into a retry response, and sends the retry response to a bus converter having issued the request.
In a case where a request is converted into a retry response and transmitted to the converter having issued the request, the request may be repeatedly retried. Hence, a livelock situation “where the transaction is not processed for a long time or forever so that the transaction is suspended” may possibly occur.
In the above prior art, if the livelock situation occurs, the converter having issued the request detects a “retry-count overflow” error, and a system fault of the data processing apparatus occurs.
In Unexamined Japanese Patent Application KOKAI Publication No. H11-73397. there is disclosed a technique for preventing any livelock situation in a round robin circuit. This technique can not suitably be employed in a data processing apparatus comprising a plurality of bus converters connected with each other in hierarchy.
In Unexamined Japanese Patent Application KOKAI Publication No. H11-143824, there is disclosed a technique for eliminating livelock, by arbitrating among bus requests of the entire bus agents and determining one bus master, if the bus agents are in an idle state. However, this technique is prepared for arbitrating among only some of the entire bus agents, but not for arbitrating among the entire bus agents in its entirety, and can not suitably be employed in a data processing apparatus comprising a plurality of bus converters connected with each other in hierarchy. The contents of these references are incorporated into this specification.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above facts. It is accordingly an object of the present invention to provide a livelock avoidance method for reliably processing a retried request and avoiding occurrence of a system fault, and a data processing apparatus realizing the livelock avoidance method.
Another object thereof is to provide, in a data processing apparatus comprising a plurality of bus conveners connected with each other in hierarchy, a livelock avoidance method for reliably processing a retry request and avoiding occurrence of a system fault, and the data processing apparatus realizing the livelock avoidance method.
The order to accomplish the above objects, according to the first aspect of the present invention, there is provided a data processing apparatus comprising at least one high-level bus converter, a plurality of intermediate-level bus converters, and a plurality of low-level bus converters which are connected with one another in hierarchy, wherein:
said at least one high-level bus converter converts, if a normal-response buffer is busy when a normal request is received, the received normal request into a retry response and sends the retry response to one of said plurality of intermediate-level bus converters which has sent the normal request thereto, and sends, when an urgent request is received, a normal response in response to the received urgent request to one of said plurality of intermediate-level bus converters which has sent the urgent request thereto;
each of said plurality of low-level bus converters issues a normal request, and converts, when a retry response is received, the retry response into an urgent request, and reissues a request as the urgent request; and
each of said plurality of intermediate-level bus converters arbitrates, when a plurality of urgent requests compete with each other, between the plurality of urgent requests and transfers a winner urgent request to said at least one high-level bus converter, converts at least one looser urgent request into a normal request, and transfers the looser urgent request to said at least one high-level bus converter.
According to the second aspect of the present invention, there is provided a livelock avoidance method, as a data processing method carried out by a data processing apparatus comprising a plurality of bus converters connected with each other in hierarchy, said method comprising:
converting, in a bus converter having received a normal request, the normal request into a retry response, when a normal response buffer is busy, and sending the retry response to a bus converter, having issued the normal request, through reserved-response entry;
reissuing a request as an urgent request for requesting an urgent service based on the retry response in the bus converter having issued the normal request; and
arbitrating, when a plurality of urgent requests compete with each other in a bus converter arranged in a request path, between the plurality of urgent requests, transferring a winner urgent request to a high-level bus converter, and transferring at least one looser urgent request to the high-level bus converter as a normal request.
According to the third aspect of the present invention, there is provided a method for processing data as performed by a data processing apparatus comprising at least one high-level bus converter, a plurality of intermediate-level bus converters and a plurality of low-level bus converters which are connected with each other in hierarchy, wherein:
said high-level bus converter converts, if a normal-response buffer is busy when a normal request is received, the received normal request in a retry response and sends the retry response to one of said plurality of intermediate-level bus converters which has sent the normal request thereto, and sends, when an urgent request is received, a normal response in response to the received urgent request to one of said plurality of intermediate-level bus converters which has sent the urgent request thereto;
each of said plurality of low-level bus converters issues a normal request, and converts, when a retry response is received, the retry response into an urgent request, and reissues a request as an urgent request; and
each of said plurality of intermediate-level bus converters arbitrates, when a plurality of urgent requests compete with each other, between the plurality of urgent requests and transfers a winner urgent request to said high-level bus converter, converts a looser urgent request into a normal request, and transfers the looser urgent request to the high-level bus converter.
According to the fourth aspect of the present invention, there is provided a data processing apparatus comprising at least one high-level bus converter, a plurality of intermediate-level converters and a plurality of low-level bus converters which are connected with each other in hierarchy, wherein:
said high-level bus converter includes means for converting, if a normal-response buffer is busy when a normal request is received, the received normal request into a retry response and sends the retry response to one of said plurality of intermediate-level bus converters which has sent the normal request thereto, and means for sending, when an urgent request is received, a normal response in response to the received urgent request to on
Auve Glenn A.
Dickstein Shapiro Morin & Oshinsky LLP.
Vu Trisha
LandOfFree
Livelock avoidance method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Livelock avoidance method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Livelock avoidance method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095783