总线系统和其死锁避免电路

摘要

本发明涉及一种死锁避免电路，包括：先前业务信息管理部分；业务发出终止确定部分；和响应输出控制部分。

说明书

技术领域

本公开涉及总线系统。更具体地，本公开涉及在总线系统的互连中使用 的死锁避免电路。

背景技术

在总线系统中，连接的装置被链接到总线(还称为互连)，且在连接的装 置之间传输数据。在两个装置之间传输数据的扮演主导角色的连接装置被称 为主体(master)，而操作为无源装置的其他连接的装置被称为从体(slave)。 典型地，假设处理器是称为主体的连接装置，而假设存储器是称为从体的连 接装置。

在这种总线系统中，称为用于传输数据的业务(transaction)的操作序列 包括传输数据请求和实际传输数据。通过像分裂的业务一样独立于彼此来控 制用于传输和实际传输数据的请求，可以改善传输数据的效率。如果在与允 许分裂的业务的情况相同的时刻，主体向多个从体发出具有依赖关系的业务， 担心在传输数据请求和实际传输数据之间出现死锁。

在此，让我们假设一种其中主体M1和M2以及从体S1和S2链接到互 连的系统。让主体M1向从体S1然后从体S2发出具有依赖关系的读业务， 而主体M2向从体S2然后从体S1发出具有依赖关系的读业务。

在该情况下，“主体M1向从体S1发出具有依赖关系的读业务，然后向 从体S2发出具有依赖关系的读业务”的术语暗示主体M1向从体S1和S2分 别提供第一读地址和第一读地址之后的第二读地址，并期望从该从体S1接收 第一数据，并从该从体S2接收第一数据之后的第二数据。由于相同的原因， “主体M2向从体S2发出具有依赖关系的读业务，然后向从体S1发出具有依 赖关系的读业务”的术语暗示主体M2向从体S1和S2分别提供第三读地址和 第三读地址之后的第四读地址，并期望从该从体S2接收第三数据，并从该从 体S1接收第三数据之后的第四数据。

由从体S1和S2接收的读地址如以下表述：

S1：M1₁和M2₂

S2：M2₁和M1₂

在读地址的上述表述中，附加于符号M1或M2的后缀指示读地址是先 前的读地址还是稍后的读地址，从该先前的读地址，将由从体读出并由主体 接收先前的数据，从该稍后的读地址，将由从体读出并由主体接收稍后的数 据。例如，读地址M1₂是在业务中由主体M1发出的读地址，且附加于符号 M1的后缀2指示，主体M1期望接收从读地址M1₂读出的稍后的数据作为业 务的结果。也就是说，符号M1₁和M1₂分别表示由主体M1发出的第一读 地址和由主体M1发出的第二读地址期望接收从读地址M1₁读出的先前数 据，并接收从读地址M1₂读出的稍后数据。

在该情况下，如果每个从体先前输出首先由主体期望的数据，不发生死 锁。如果每个从体从不同主体接收业务读地址，并在没有被任何数据输出顺 序限制的状态下被输入，另一方面，从体可以以任何顺序向主体输出数据。 对于其中从体S1分别从主体M1和M2接收读地址M1₁和M2₂而从体S2 分别从主体M2和M1接收读地址M2₁和M1₂的上述情况，假设例如，从 体S1试图在从读地址M1₁读出的数据之前输出从读地址M2₂读出的数据， 而从体S2试图在从读地址M2₁读出的数据之前输出从读地址M1₂读出的数 据。在该情况下，主体M1和M2不接受从体S1和S2正尝试输出的数据。 这是因为主体M1期望从体S1首先向主体M1输出从读地址M1₁输出的数据， 但其是尝试首先向主体M1输出从读地址M1₂读出的数据的从体S2。由于相 同的原因，主体M2期望从体S2首先向主体M2输出从读地址M2₁输出的数 据，但其是尝试首先向主体M2输出从读地址M2₂读出的数据的从体S1。只 要主体M1不尝试接受从读地址M1₂读出的数据，且主体M2不接受从读地 址M1₁读出的数据，如由主体M1期望的，而从体S2不能输出由主体M2 期望的从读地址M2₁读出的数据。以此方式，如果从体以不由主体期望的改 变的顺序向主体输出数据，则担心发生死锁。

为了解决上述地所问题，已经提出了用于通过控制业务的重排序来避免 死锁的技术。例如，已经提出了用于通过混淆来用单个标识符替换业务标识 符使得业务的重排序困难来避免死锁的数据处理装置。预知该数据处理装置 的更多信息，建议读者来参考诸如日本专利特开No.2008-041099的文档(图 1)。

发明内容

根据上述现有技术，试图防止发生死锁，不进行业务的重排序。然而， 只要在互连中不监视对所有从体发出地址，自然难以控制由主体向多个从体 发出的地址的到达顺序。因此，在从体处的地址到达顺序不一定匹配其中主 体发出地址的顺序。因此，即使从体不示范地改变业务顺序，其确实在死锁 发生的可能性范围内。

因此，本公开的目的解决了上述问题，以提供防止允许主体提供采用分 离业务技术对多个从体同时访问的总线系统发生死锁的能力。

为了解决上述问题，根据本公开的第一模式，提供一种死锁避免电路或 使用该死锁避免电路的总线系统。所述死锁避免电路具有：

先前业务信息管理部分，被配置以管理关于之前由与所述死锁避免电路 相关联的主体发给多个从体的先前业务的信息；

业务发出终止确定部分，被配置以基于关于所述先前业务的所述信息来 确定由所述主体新发出的最近业务是否是死锁的原因，被配置以如果确定所 述最近业务是死锁的原因则终止所述最近业务的发出；以及

响应输出控制部分，被配置以控制操作来将由所述从体生成的响应传递 给所述主体，以便如果一些响应已经响应于所述先前业务，以不同于预期的 响应输出顺序的顺序，由所述从体输出到所述主体，则维持所述预期的响应 输出顺序。

因此，死锁避免电路带来防止允许对多个从体同时访问的总线系统发生 死锁的效果。

另外，根据本公开的第一模式的所述死锁避免电路还具有响应节省缓冲 器还可以具有响应保存缓冲器，用于如果响应已经响应于所述先前业务之一， 以不同于所述预期的响应输出顺序的顺序，由所述从体中的任一输出到所述 主体，则保存所述响应。在该情况下，所述业务发出终止确定部分基于所述 响应保存缓冲器的容量来确定由所述主体新发出的最近业务是否是死锁的原 因。因此，到响应保存缓冲器的容量所确定的程度，死锁避免电路带来允许 可能成为死锁的原因的业务的发出的效果。

基于此，在根据本公开的第一模式的死锁避免电路，可以在所述从体中 的任一中提供所述响应保存缓冲器。因此，能够向从体的任何一个带来响应 保存缓冲器的功能。

另外，在根据本公开的第一模式的所述死锁避免电路中，如果响应已经 响应于所述先前业务中的特定一个，以不同于预期的响应输出顺序的顺序， 由所述从体中的任一输出到所述主体，则所述响应输出控制部分进行控制来 丢弃所述响应并重新发出所述丢弃响应的所述特定先前业务。因此，死锁避 免电路带来允许可能成为死锁的原因的先前业务的发出的效果。

另外，根据本公开的第二模式，提供一种死锁避免电路或使用该死锁避 免电路的总线系统。所述死锁避免电路包括：

先前业务信息管理部分，被配置以管理先前业务信息，该先前业务信息 包括用作之前由多个主体向所述从体中的任一发出的先前业务的目标的多个 从体的标识符和所述标识符的顺序；以及

业务发出终止确定部分，被配置以基于所述先前业务信息来确定由所述 主体中的任一新发出的最近业务是否是死锁的原因，且如果确定所述最近业 务是死锁的原因则终止所述最近业务的发出。

因此，死锁避免电路带来如果确定最近业务员是死锁的原因则终止最近 业务的发出的效果。

根据本公开，能够带来防止允许主体提供采用分离业务技术对多个从体 同时访问的总线系统中发生死锁的极佳效果。

附图说明

图1是图示根据本公开的实施例的总线系统的典型总体配置的方框图；

图2是图示根据本公开的实施例的总线系统中使用的互连的典型配置的 方框图；

图3是示出通过根据AXI协议的读地址信道传输的信号的表；

图4是示出通过根据AXI协议的读数据信道传输的信号的表；

图5是示出通过根据AXI协议的写数据信道传输的信号的表；

图6是示出通过根据AXI协议的写数据信道传输的信号的表；

图7是示出通过根据AXI协议的写响应信道传输的信号的表；

图8是图示用作根据本公开的第一实施例的电路的在互连中使用的死锁 避免电路的典型配置的方框图；

图9是图示用作根据本公开的第一实施例的部分的在死锁避免电路中使 用的先前业务信息管理部分的典型配置的方框图；

图10是图示用作根据本公开的第一实施例的部分的在死锁避免电路中 使用的业务发出终止确定部分进行的典型业务动作确定处理的流程图；

图11是图示用作根据本公开的第一实施例的部分的在死锁避免电路中 使用的响应输出控制部分的典型配置的方框图；

图12是图示根据本公开的第二实施例的死锁避免电路的基本配置的方 框图；

图13是图示用作根据本公开的第二实施例的部分的在死锁避免电路中 使用的先前业务信息管理部分的典型配置的方框图；

图14是图示用作根据本公开的第二实施例的部分的在死锁避免电路中 使用的业务发出终止确定部分进行的典型业务动作确定处理的流程图；

图15是图示用作根据本公开的第二实施例的部分的在死锁避免电路中 使用的响应输出控制部分的典型配置的方框图；

图16是图示根据本公开的第三实施例的死锁避免电路的基本配置的方 框图；

图17是图示用作根据本公开的第三实施例的部分的在死锁避免电路中 使用的响应输出控制部分的典型配置的方框图；

图18是图示根据本公开的第四实施例的互连的典型配置的方框图；

图19是图示用作根据本公开的第四实施例的电路的在互连中使用的死 锁避免电路的典型配置的方框图；

图20是图示用作根据本公开的第四实施例的部分的在死锁避免电路中 使用的先前业务信息管理部分的典型配置的方框图；

图21A到21C是示出在根据本公开的第四实施例的先前业务信息管理中 使用的信息管理队列上注册先前业务信息的典型操作的图；

图22A和22B每个是用作根据本公开的第四实施例的部分的在描述由在 死锁避免电路中使用的业务发出终止确定部分采用的死锁确定技术时参考的 图；

图23是图示用作根据本公开的第四实施例的部分的在死锁避免电路中 使用的业务发出终止确定部分进行的典型业务动作确定处理的典型流程图；

图24A到24C是在描述由本公开的第四实施例采用的第一典型死锁确 定技术时参考的图；

图25A到25C是在描述由本公开的第四实施例采用的第二典型死锁确 定技术时参考的图；

图26A到26C是在描述由本公开的第四实施例采用的第三典型死锁确 定技术时参考的图；以及

图27A到27C是在描述由本公开的第四实施例采用的第四典型死锁确 定技术时参考的图。

具体实施方式

以下按以下顺序参考附图来说明本公开的实施例。

1：第一实施例(在响应保存缓冲器中保存依赖性响应的典型实施方式)

2：第二实施例(丢弃依赖性响应并重新尝试的典型实施方式)

3：第三实施例(使用从体也用作响应保存缓冲器的典型实施方式)

4：第四实施例(以集成方式管理通过所有主体作出的请求的典型实施 方式)

1：第一实施例

总线系统的总体配置

图1是图示根据本公开的实施例的总线系统的典型总体配置的方框图。 在该总线系统中，用作总线的互连300被链接到多个连接的装置。连接的装 置是M个主体100和S个从体200。主体100是在主体100和从体200之间 传输数据中扮演重要角色的连接的装置。另一方面，从体200是在从体200 和主体100之间传输数据的无源连接的装置。处理器可以被假设为主体100 的典型例子，而存储器可以被假设为从体200的典型例子。注意，上述符号 M和S每个是等于或大于1的整数。

图2是图示根据本公开的实施例的互连300的典型配置的方框图。在包 括两个主体100和两个从体200的典型的总线系统中使用图中所示的互连 300。

另外，作为由用于彼此独立地控制对传输数据的请求和实际传输数据的 互连300实施的(分离业务的)总线的代表性例子，假设AXI(高级可扩展 接口)协议。在该AXI协议中，作为读操作的路径，提供读地址信道和读数 据信道。当主体100通过读地址信道向从体200发出包括读地址的数据传输 请求时，从体200响应于对传输数据的请求通过读数据信道向主体100传输 数据。

另外，在该AXI协议中，作为写操作的路径，提供写地址信道、写数据 信道和写响应信道。当主体100分别通过写地址信道和写数据信道向从体200 发出包括写地址和写数据的写操作请求时，从体200响应于对写操作的请求 进行写操作。然后，从体200通过写响应信道向主体100传输写操作的结果。

在AXI协议中，读地址信道和读数据信道的一组被用于进行读业务，而 写地址信道、写数据信道和写响应信道的一组被用于进行写业务。作为AXI 协议的一般规则，用于进行相同业务员的信道具有相同的标识符。如果向用 于进行不同业务的信道分配相同标识符，需要保证进行业务以便业务变为具 有依赖关系的业务的顺序(或顺序依赖性)。具有依赖关系的业务是要以预先 确定的顺序进行的业务。

在AXI协议的情况下，用通过写地址信道和写响应信道的传输的相反顺 序、通过读地址信道和读数据信道的传输的相反顺序、或通过写地址信道和 写数据信道的传输的相反顺序而导致死锁。由于基本上相同的死锁避免机构 可以用于避免读和写两个信道的死锁，在以下描述中，写地址信道和读地址 信道每个被称为用于写地址信道和读地址信道的普通技术术语的地址信道， 而写响应信道和读数据信道每个被称为作为写响应信道和读数据信道的普通 技术术语的响应信道。

地址信道总线矩阵310是用于处理地址信道的连接的部分，而响应信道 总线矩阵320是用于处理响应信道的连接的部分。地址信道总线矩阵310传 递由主体100向从体200发出的请求，而响应信道总线矩阵320传递由从体 200向主体100生成的响应。

在本公开的第一实施例中，为M主体100的每个提供死锁避免电路400。 死锁避免电路400是用于控制操作以便防止由与死锁避免电路400相关联的 主体100进行的业务生成死锁的电路。在这种业务中，信号线10和20表示 地址信道，而信号线30和40表示响应信道。为了方便的目的，每个信号线 的箭头朝向与信号线传输的主信号相同的方向。但是，实际上，信号线还传 输除了主信号以外的控制信号，且因此由信号线表示的信道用于在两个方向 上交换控制信号。

在AXI协议中，当已经在地址和响应信道的每个上对有效性信号和准备 信号赋值时，传播信息。也就是说，当已经在地址和响应信道的每个上对有 效性信号和准备信号赋值时，例如，从从体200向主体100传输读数据。在 例如读地址信道的情况下，用作读地址传输源的主体100设置读地址等，在 读信道上对有效性信号ARVALID赋值1。此时，只要从体200变得准备好接 收读地址，在读地址接收侧上的从体200在读信道上对准备信号ARREADY 赋值1。因此，当为1的有效性信号ARVALID和为1的准备信号ARREADY 时，从主体100向从体200传输读地址和其他信息。

在AXI协议中的信道配置

图3是示出通过根据AXI协议的读地址信道传输的信号的表。在主体100 和从体200之间的读地址信道是用于从主体100向从体200传输读地址的信 道。更详细地，读地址信道用于传输用于传递读地址标识符、读地址、突发 长度、突发尺寸、突发类型、锁定类型、缓存类型、保护类型、读地址有效 性指示符和读地址准备指示符的信号，如表中所示。从主体100向从体200 传输信号，除了传递从从体200向主体100传输的读地址准备指示符的信号。

读地址标识符ARID[3:0]是具有4位的标记，用于标识传递读地址标识 符ARID[3:0]的信号的读地址组。在AXI协议中，当主体100向主体200发 出业务时，如果主体100请求从体200维持业务的顺序，向业务分配相同的 标识符。换句话说，在具有彼此不同的标识符的业务的情况下，不假设业务 的顺序的维持。

读地址ARADDR[31:0]是用于传递32位读地址的信号，从该32位读地 址，读出数据。读地址是在突发传输中的初始数据的地址。

突发长度ARLEN[3:0]是用于在突发传输中传递数据的数量的4位信号。 在突发传输中的数据的数量是在范围1到16中的数，并被编程为4位的码。

突发尺寸ARSIZE[2:0]是用于对每个突发传输传递传输尺寸的3位信号。 传递尺寸被编码为表示表达式2ⁿ的n的3位码。由于传输尺寸表示作为在范 围1到7中的整数的n，表达式2ⁿ表示表达式2⁰，2¹，2²，2³，2⁴，2⁵，2⁶和2⁷。

突发类型ARBURST[1:0]是用于在突发传输中传递地址的计算的类型的 2位信号。更具体地，突发类型ARBURST[1:0]被用于指定FIFO类型、连续 访问类型或缓存线类型。

锁定类型ARLOCK[1:0]是用于传递原子访问的信息的2位信号。更具体 地，锁定类型ARLOCK[1:0]被用于指定正常访问、排他访问或具有锁定的访 问。

缓存类型ARCACHE[3:0]是用于传递控制缓存存储器需要的信息的4位 信号。更具体地，缓存类型ARCACHE[3:0]用于指定控制信息，诸如数据是 否可缓存的信息，该操作是写通过操作，该操作是写回操作等。

保护类型ARPROT[2:0]是用于传递控制保护需要的信息的3位信号。更 具体地，保护类型ARPROT[2:0]被用于指定保护水平，诸如特权访问、不安 全访问和指令访问。

读地址有效性指示符ARVALID是用于指示地址或控制信号的有效性的 信号。另一方面，由从体200生成的读地址准备指示符ARREADY是用于指 示从体200是否已经进入准备好从主体100接收地址或控制信号的状态的信 号。如前所述，当读地址有效性指示符ARVALID和读地址准备指示符 ARREADY已经在主体100和从体200之间的信道上被赋值时，通过该信道 从主体100向从体200发送地址和控制信号。

图4是示出通过根据AXI协议的读数据信道传输的信号的表。在主体100 和从体200之间的读数据信道是用于从从体200向主体100传输读数据的信 道。更详细地，读数据信道用于传输用于传递读地址标记、读数据、响应、 最后的读、读有效性指示符和读准备指示符，如表中所示。从从体200向主 体100传输信号，除了传递从主体100向从体200传输的读准备指示符的信 号。

读标识符标记RID[3:0]是具有4位的标记，用于标识传递读标识符标记 RID[3:0]的信号的读数据组。读标识符标记RID[3:0]由从体200生成，且必 须匹配上述读地址标识符ARID[3:0]。

读数据RDATA[31:0]是由从体200在读业务中输出的读数据。在该情况 下，读数据总线被假设为具有32位的宽度。但是，读数据RDATA的位数根 据读数据总线的宽度。读数据总线可以具有8，16，32，64，128，256，512或 1,024位的宽度。

读响应RRESP[1:0]是用于在读业务中指示数据传输的状态的2位信号。 接下来，将描述读响应RRESP[1:0]的详细。

最后的读RLAST是用于在读业务中指示最后的数据传输的2位信号。

读有效性指示符RVALID是用于指示请求的读数据的有效性的信号。由 主体100发出读准备指示符RREADY是用于指示主体100是否进入了准备 好从从体200接收请求的读数据的状态的信号。如上述，当读有效性指示符 RVALID和读准备指示符RREADY已经在主体100和从体200之间的信道 上被赋值时，通过该信道从从体200向主体100传输请求的读数据。

图5是示出通过根据AXI协议的写数据信道传输的信号的表。在主体100 和从体200之间的写地址信道是用于从主体100向从体200传输写地址的信 道。更详细地，写地址信道用于传输用于传递写地址标识符、写地址、突发 长度、突发尺寸、突发类型、锁定类型、缓存类型、保护类型、写地址有效 性指示符和写地址准备指示符的信号，如表中所示。从主体100向从体200 传输信号，除了传输从从体200向主体100传输的写地址准备指示符的信号。

写地址标识符AWID[3:0]是具有4位的标记，用于标识传递写地址标识 符AWID[3:0]的信号的写地址组。写地址AWADDR[31:0]是用于传递32位 写地址的信号，要向该32位写地址，写数据。写地址是在突发传输中的初始 数据的地址。

突发长度AWLEN[3:0]是用于在突发传输中转移数据的数量的4位信号。 突发尺寸AWSIZE[2:0]是用于对每个突发传输传递传输尺寸的3位信号。突 发类型AWBURST[1:0]是用于在突发传输中传递地址的计算的类型的2位信 号。锁定类型AWLOCK[1:0]是用于传递原子访问的信息的2位信号。缓存 类型AWCACHE[3:0]是用于传递控制缓存存储器需要的信息的4位信号。保 护类型AWPROT[2:0]是用于传递控制保护需要的信息的3位信号。上述这些 信号基本上与通过读地址信道传输的那些相同。

写地址有效性指示符AWVALID是用于指示地址或控制信号的有效性的 信号。另一方面，由从体200生成的写地址准备指示符AWREADY是用于 指示从体200是否已经进入准备好从主体100接收地址或控制信号的状态的 信号。如前所述，当写地址有效性指示符AWVALID和写地址准备指示符 AWREADY已经在主体100和从体200之间的信道上被赋值时，通过该信道 从主体100向从体200发送地址和控制信号。

图6是示出通过根据AXI协议的写数据信道传输的信号的表。在主体100 和从体200之间的写数据信道是用于从从体100向主体200传输写数据的信 道。更详细地，写数据信道用于传输用于传递写地址标记、写选通、最后的 写、写有效性指示符和写准备指示符，如表中所示。从主体100向从体200 传输信号，除了传输从从体200向主体100传输的写准备指示符的信号。

写标识符标记WID[3:0]是具有4位的标记，用于标识传递写标识符标记 WID[3:0]的信号的写数据组。写标识符标记WID[3:0]由主体100生成，且必 须匹配上述写地址标识符AWID[3:0]。

写数据WDATA[31:0]是在写业务中由主体100向从体200输出的写数 据。在该情况下，写数据总线被假设为具有32位的宽度。但是，写数据WDATA 的位数根据写数据总线的宽度。写数据总线可以具有8，16，32，64，128，256， 512或1,024位的宽度。

写选通WSTRB[3:0]是用于指示在从体200中使用的存储器中的字节位 置的4位信号。字节位置是要用写数据的字节更新的字节的位置。写数据总 线的每8位与写选通WSTRB[3:0]的位相关联。也就是说，写选通位WSTRB [i]与写数据字节WDATA[(8×i)+7(8×i)]相关联。

最后的写WLAST是用于在写业务中指示最后的数据传输的2位信号。

写有效WVALID是用于指示要在从体200中存储的写数据的有效性的 信号。

由从体200生成的写准备指示符WREADY是用于指示从体200是否已 经进入准备好从主体100接收要在从体200中存储的写数据的状态的信号。 如前所述，当写地址有效性指示符WVALID和写准备指示符WREADY已 经在主体100和从体200之间的信道上被赋值时，通过该信道从主体100向 从体200发送写数据。

图7是示出通过根据AXI协议的写响应信道传输的信号的表。写响应信 道是用于传输从从体100向主体200的写业务的结果的信道。更详细地，写 响应信道用于传输用于传递响应标识符、写响应、写响应有效性指示符和响 应准备指示符的信号，如表中所示。从从体200向主体100传输信号，除了 传递从主体100向从体200传输的写准备指示符的信号。

响应标识符BID[3:0]是用于表示写响应的4位标记。响应标识符BID[3:0] 必须匹配上述写地址标识符AWID[3:0]。

写响应BRESP[1:0]是用于在写业务中指示数据传输的状态的2位信号。 将描述该信号的细节。

写响应有效性指示符BVALID是用于指示写响应的有效性的信号。由主 体100发送的响应准备指示符BREADY指示主体100是否已经进入准备好从 从体200接收写响应的状态。如前所述，当写响应有效性指示符BVALID和 响应准备指示符BREADY已经在主体100和从体200之间的信道上被赋值 时，通过该信道从从体200向主体100发送写响应。

死锁避免电路的配置

图8是图示根据本公开的第一实施例的死锁避免电路400的基本配置的 方框图。如图所示，死锁避免电路400使用先前业务信息管理部分410、业 务发出终止确定部分420、响应输出控制部分430和响应保存缓冲器470。另 外，死锁避免电路400也包括锁存器442、逻辑积门(logical-product gate) 451、另一逻辑积门452、解复用器460、复用器480和另外的逻辑积门491。

先前业务信息管理部分410是用于管理关于之前由与所述死锁避免电路 400相关联的主体100发给多个从体200中的任一的先前业务的信息的部分。 在以下描述中，关于先前业务的信息也称为先前业务信息。先前交易信息管 理部分410具有用于保存先前业务信息的信息管理队列411。先前交易信息 管理部分410向业务发出终止确定部分420和响应输出控制部分430供应先 前业务信息。

基于由先前业务信息管理部分410管理的先前业务信息，所述业务发出 终止确定部分420确定由与死锁避免电路400相关联的所述主体100新发出 的最近业务是否是死锁的原因。如果业务发出终止确定部分420确定由与死 锁避免电路400相关联的主体100新发出的最近业务是死锁的原因，所述业 务发出终止确定部分420停止向从体200递送最近业务的操作。

更具体地，从先前业务信息管理部分410，业务发出终止确定部分420 接收由先前业务信息管理部分410生成的XFULL信号来指示在先前业务信 息管理部分410中使用的信息管理队列411未满、在由与死锁避免电路400 相关联的主体100进行的访问上向不同从体200中的任一传递信息的 STATUS信号、和PID信号。PID信号传递伴随向不同从体200中的任一的 访问的每个业务的标识符。STATUS信号根据其标识符由PID信号传递的业 务来传递访问的数量。另外，从与死锁避免电路400相关联的主体100，业 务发出终止确定部分420还接收DID信号，其传递由主体100新发出的最近 业务的标识符。基于从先前业务信息管理部分410和与死锁避免电路400相 关联的主体100接收的这些信息，业务发出终止确定部分420确定由主体100 新发出的最近业务是否是死锁的原因，且如果业务发出终止确定部分420确 定由主体100新发出的最近业务员是死锁的原因，则业务发出终止确定部分 420通过激活向逻辑积门451输出的STOP信号来停止向从体200递送最近 业务的操作。

要注意，如上所述，先前业务信息管理部分410生成STATUS信号和PID 信号，而所述业务发出终止确定部分420基于该STATUS信号和PID信号确 定由与死锁避免电路400相关联的所述主体100新发出的最近业务是否是死 锁的原因。但是，要注意，本公开的实施方式决不限于此配置。例如，也可 能提供一种配置，其中业务发出终止确定部分420通过参考在先前业务信息 管理部分410中使用的信息管理队列411的所有内容，来确定由与死锁避免 电路400相关联的所述主体100新发出的最近业务是否是死锁的原因。

响应输出控制部分430是用于基于由先前业务信息管理部分410管理的 先前业务信息来控制要递送到与死锁避免电路400相关联的主体100的响应 的部分。如果来自多个从体200作为对先前业务的响应的响应按不同于预期 的响应输出顺序的顺序而到达响应输出控制部分430，则响应输出控制部分 430控制向与死锁避免电路400相关联的主体100输出响应的操作，以便其 中向主体100递送响应的顺序匹配预期的响应输出顺序。

响应保存缓冲器470是用于保存来自多个从体200的作为对先前业务的 响应的响应的缓冲器，以防响应按不同于预期的响应输出顺序的顺序到达响 应输出控制部分430。响应输出控制部分430基于由先前业务信息管理部分 410管理的先前业务信息而控制向响应保存缓冲器470供应响应并从响应保 存缓冲器470读出响应的操作。

锁存器442是用于保存来自与死锁避免电路400的地址信道相关联的主 体100的信号的存储器。逻辑积门451是用于根据由业务发出终止确定部分 420输出的STOP信号来使得掩蔽在锁存器442中锁存的AVALID信号的门。 也就是说，如果STOP信号请求停止AVALID信号，掩蔽AVALID信号， 使得信号通过地址信道到达以被保存在锁存器442中。

逻辑积门452是用于产生来自从体200的AREADY(AREADY_IN)信号 和由逻辑积门451输出的信号的逻辑积的门。如果由逻辑积门352向先前业 务信息管理部分410输出的逻辑积信号PUSH处于有源状态(active state)， 由主体100发出的近来业务员被保存在先前业务信息管理部分410中使用的 信息管理队列411中。也就是说，如果由主体100向地址信道输出的AVALID 信号和由从体200向地址信道输出的AREADY(AREADY_IN)信号都有源， 逻辑积门420向先前业务信息管理部分410输出在有源状态中的逻辑积信号 PUSH以便进行向信息管理队列推送最近业务的操作。

解复用器460是用于通过复用器480向响应保存缓冲器470或主体100 递送来自从体200的响应的部分。复用器480是用于直接来自解复用器460 的响应或暂时保存在响应保存缓冲器470中保存的响应的部分。复用器480 向主体100递送所选的响应。响应输出控制部分430生成用于控制解复用器 460和复用器480的控制信号。

逻辑积门491是用于产生来自主体100的RREADY(RREADY_IN)信号 和由从体200输出的RVALID信号的逻辑积的门。如果由逻辑积门491向先 前业务信息管理部分410输出的逻辑积信号POP处于有源状态，在先前业务 信息管理部分410中使用的信息管理队列411中保存的业务被释放。也就是 说，如果由主体100向响应信道输出的RREADY(RREADY_IN)信号和由从 体200向响应信道输出的RVALID信号都有源，逻辑积门491向先前业务信 息管理部分410输出在有源状态中的逻辑积信号POP以便进行从信息管理队 列弹出业务的操作。

图9是图示根据本公开的第一实施例的先前业务信息管理部分410的典 型配置的方框图。如图所示，先前交易信息管理部分410使用上述信息管理 队列411、管理信息生成部分142和队列状态生成部分413。

信息管理队列411是用于通过采用所谓FIFO(先进先出)技术来保存 先前业务信息的队列。每个先前业务信息包括由业务的标识符ID和作为被分 配给用作业务的目标的从体200的目标从体号构成TGT的对。每个先前业务 信息被保存在信息管理队列411的条目中。另外，每个条目还用于保存有效 性信号V，指示在条目中保存的先前业务信息的有效性。信息管理队列411 可以用于保存x个先前业务信息，其中符号x是整数。可以分别通过信号线 401、402和403从条目提取在条目中保存的有效性信号V、标识符ID和目 标从体号TGT。

当由逻辑积门452输出的PUSH信号被激活时，作为ID_IN和TGT_IN 的对的新条目被添加到信息管理队列411。另一方面，当由逻辑积门491输 出的POP信号被激活时，根据FIFO技术从信息管理队列411删除最早的条 目。

要注意，作为在从体侧上的AXI协议，仅具有不同标识符的业务的顺序 可以在重排序处理中改变。因此，能够管理每个具有目标从体号TGT的业务， 如在该本公开的实施例的情况下。

管理信息生成部分412是用于生成关于在信息管理队列411中保存的先 前业务信息的信息的部分。也就是说，管理信息生成部分412生成表示关于 由与死锁避免电路400相关联的主体100进行的访问作为对多个不同从体200 的访问的信息的STATUS和PID信号。如先前描述的，PID信号是伴随向多 个不同从体200的访问的每个业务的标识符，而STATUS信号是与PID信号 相关联的访问的数量。

队列状态生成部分413是用于生成关于信息管理队列411的状态的信息 的部分。更具体地，队列状态生成部分413生成XFULL信号，指示在先前 业务信息管理部分410中使用的信息管理队列411还没有满。

图10是图示用作根据本公开的第一实施例的业务发出终止确定部分进 行的典型业务动作确定处理的流程图。如图所示，流程图开始于步骤S911， 此处，从主体100接收最近业务。当从主体100接收最近业务时，业务发出 终止确定部分420如下确定是否可以向从体200递送最近业务。

首先，在随后的步骤S912中，业务发出终止确定部分420确定是否存在 在最近业务和先前业务之间的依赖关系以及最近业务是否具有不同于先前业 务的目标从体。如果不在最近业务和先前业务之间存在依赖关系，不需要考 虑死锁。因此，在该情况下，业务动作确定处理的流程继续到步骤S915中， 此处，向从体200递送最近业务。即使存在在最近业务和先前业务之间的依 赖关系，最近业务的目标从体200可以匹配先前业务的目标从体200。在该 情况下，不发生突变，只要目标从体200维持该顺序。因此，业务动作确定 处理的流程也继续到步骤S915。

另一方面，如果存在在最近业务和先前业务之间的依赖关系，且最近业 务具有不同于先前业务的目标从体的目标从体，业务动作确定处理的流程继 续到步骤S914。

依赖关系存在的先前业务包括被发给不同目标从体200的多组具体业 务。在步骤S914中，业务发出终止确定部分420输出该多组具体业务的数量， 且确定这多组具体业务的数量小于整数n，该n是包括响应保存缓冲器470 的级的数量。

如果这种具体业务的数量小于整数n，具体业务可以被保存在响应保存 缓冲器470中。因此，在该情况下，业务动作确定处理的流程也继续到步骤 S915。另一方面，如果这种具体业务的数量不小于整数n，业务动作确定处 理的流程继续到步骤S916，此处，停止最近业务的发出。

图11是图示根据本公开的第一实施例的响应输出控制部分430的典型配 置的方框图。如图所示，响应输出控制部分430使用基于最早响应的业务发 出历史搜索部分431和最近响应推送确定部分433。另外，响应输出控制部 分430还具有基于最早响应的业务员发出历史搜索部分432，、最早响应弹出 确定部分434和最早响应第一优先级处理部分435。

基于最近响应的业务发出历史搜索部分431是用于搜索信息管理队列 411以找到每个具有匹配从从体200接收的响应的标识符的标识符的已经发 出的业务的部分。也就是说，基于最近响应的业务发出历史搜索部分431比 较从从体200接收的响应的标识符RID和在信息管理队列411的x个条目中 保存的所有业务的标识符ID1到Idx，以便找到每个具有匹配标识符RID的 标识符ID的业务。

最近响应推送确定部分433是用于确定向主体100递送具体业务的顺序 的部分。也就是说，最近响应推送确定部分433确定是否在响应保存缓冲器 470中保存来自从体200的对从操作中发现的业务中选择的具体业务的响应， 该操作已经被基于最近响应的业务发出历史搜索部分431进行以搜索信息管 理队列411，作为每个具有匹配标识符RID的标识符ID的业务。具体业务是 具有匹配从从体200接收的响应的目标从体号的目标从体号的业务。也就是 说，最近响应推送确定部分433比较在搜索操作中找到的每个业务的目标从 体号TGT403和从从体200接收的响应的目标从体号RTGT，以便找到具有 匹配目标从体号RTGT的目标从体号TGT403的业务。然后，如果找到的业 务不是最近的那个，则最近响应推送确定部分433激活route_shltr_w信号， 并向最早响应第一优先级处理部分435供应该信号。route_shltr_w信号是请 求来自从体200的响应可以被保存在响应保存缓冲器470中的信号。

基于最早响应的业务发出历史搜索部分432是用于搜索信息管理队列 411以找到每个具有匹配在响应保存缓冲器470的头部处保存的响应的标识 符的标识符的已经发出的业务的部分。

也就是说，基于最早响应的业务发出历史搜索部分432比较在响应保存 缓冲器470的头部处保存的响应的标识符SID和在信息管理队列411的x个 条目中保存的所有业务的标识符ID1到Idx，以便找到每个具有匹配标识符 SID的标识符ID的业务。

最早响应弹出确定部分434是用于确定向主体100递送具体业务的顺序 的部分。也就是说，最早响应弹出确定部分434确定是否递送在响应保存缓 冲器470中保存的对从操作中发现的业务中选择的具体业务的响应，该操作 已经被基于最早响应的业务发出历史搜索部分432进行以搜索信息管理队列 411，作为每个具有匹配标识符SID的标识符ID的业务。具体业务是具有匹 配在响应保存缓冲器470的头部处保存的响应的目标从体号的目标从体号的 业务。也就是说，最早响应弹出确定部分434比较在搜索操作中找到的每个 业务的目标从体号TGT403和在响应保存缓冲器470的头部处保存的响应的 目标从体号STGT，以便找到具有匹配目标从体号STGT的目标从体号 TGT403的业务。然后，如果找到的业务不是最近的那个，则最早响应弹出 确定部分434激活drain_shltr_w信号，并向最早响应第一优先级处理部分435 供应该信号。drain_shltr_w信号是请求在响应保存缓冲器470的头部处保存 的响应被递送到主体100的信号。

如果在响应保存缓冲器470的头部处保存的响应可以被递送给主体100， 则最早响应第一优先级处理部分435进行控制以优先处理响应。因此，如果 在响应保存缓冲器470的头部处保存的响应可以被递送给主体100，则最早 响应第一优先级处理部分435向递送响应到主体100的处理给出最高的优先 级，允许响应的处理优先于要对新来自从体200的最近响应进行的处理。也 就是说，从响应保存缓冲器470的头部去处响应的命令DRAIN_SHELTER被 如下表述：

DRAIN_SHELTER＝drain_shltr_w & ANY_IN_SHELTER

在以上表达式中，符号ANY_IN_SHELTER表示当已经在响应保存缓冲 器470中保存了至少一个响应时激活的ANY_IN_SHELTER信号。另一方面， 在响应保存缓冲器470中保存响应的命令ROUTE_SHELTER被如下表述：

ROUTE_SHELTER＝NOT(DRAIN_SHELTER)& route_shltr_w

如上所述，根据本公开的第一实施例，死锁避免电路400包括用作用于 存储响应的存储器的响应保存缓冲器470，以防按不同于期望的顺序的顺序 接收响应。因此，能够容忍具有依赖关系并被发出给不同从体200的业务。 在该情况下，可以在响应保存缓冲器470中保存的响应的最大数量是整数n。 因此，如果在响应保存缓冲器470中保存的响应的数量大约要超过整数n， 业务发出终止确定部分420停止向从体200发出业务的操作。

2：第二实施例

在以下中，描述了本公开的第二实施例。在本公开的第一实施例的情况 下，假设使用响应保存缓冲器470。在本公开的第二实施例的情况下，假设 不使用响应保存缓冲器470。如果按不同于预期顺序的顺序从从体200接收 响应，丢弃响应，且进行重试来向从体200重新发出用于丢弃的响应的业务。 注意，在第二实施例中的总线系统的总体配置与参考图1先前描述的相同。

死锁避免电路的配置

图12是图示根据本公开的第二实施例的死锁避免电路500的基本配置的 方框图。如图所示，死锁避免电路500使用先前业务信息管理部分510、业 务发出终止确定部分520、响应输出控制部分530、选择器541、锁存器542 以及逻辑积门551，552，561和591。

先前业务信息管理部分510是用于按与先前业务信息管理部分410相同 的方式来管理关于之前由与所述死锁避免电路500相关联的主体100发给多 个从体200中的任一的先前业务的信息的部分。很像先前业务信息管理部分 410，先前业务信息管理部分510具有用于保存先前业务信息的信息管理队列 511。先前交易信息管理部分510按与先前业务信息管理部分410相同的方式 向业务发出终止确定部分520和响应输出控制部分530供应先前业务信息。 但是，先前业务信息管理部分510不同于先前业务信息管理部分410之处在 于，在先前业务信息管理部分510的情况下，在由响应输出控制部分530作 出的RETRY请求处，先前业务信息管理部分510为由在信息管理队列511 中的RETRY_IDX信号指定的业务重新发出RETRY_CMD命令。

基于由先前业务信息管理部分510管理的先前业务信息，所述业务发出 终止确定部分520按与业务发出终止确定部分420相同的方式确定由与死锁 避免电路500相关联的所述主体100新发出的最近业务是否是死锁的原因。 如果业务发出终止确定部分520确定由与死锁避免电路500相关联的主体100 新发出的最近业务是死锁的原因，所述业务发出终止确定部分520停止向从 体200递送最近业务的操作。更具体地，如果业务发出终止确定部分520确 定由与死锁避免电路500相关联的主体100新发出的最近业务是死锁的原因， 所述业务发出终止确定部分520通过激活向逻辑积门551输出的STOP信号 来停止向从体200递送最近业务的操作。但是，在第二实施例的情况下，假 设不使用响应保存缓冲器470。因此，不考虑在响应保存缓冲器470中的级 的数量。

响应输出控制部分530是用于按与响应输出控制部分430相同的方式、 基于由先前业务信息管理部分510管理的先前业务信息来控制要递送到与死 锁避免电路500相关联的主体100的响应的部分。但是，在第二实施例的情 况下，假设不使用响应保存缓冲器470。因此，响应输出控制部分530控制 仅从从体200接收的响应。

选择器541是用于选择从与地址信道相关联的主体100新接收的最近业 务或在由从先前业务信息管理部分510接收的RETRY_CMD命令请求的重试 中包含的业务的选择部分。锁存器542是用于保存由选择器541选择的业务 的信号。逻辑积门551是用于按与逻辑积门451相同的方式根据由业务发出 终止确定部分520输出的STOP信号来掩蔽在锁存器542中锁存的AVALID 信号的门。逻辑积门552是用于产生来自从体200的AREADY(AREADY_IN) 信号和由逻辑积门551输出的信号的逻辑积的门。逻辑积门561是用于当响 应输出控制部分530正进行用于重试的请求时、掩蔽由从体200通过响应信 道30供应的RVALID(RVALID_IN)信号的门。如果由逻辑积门561输出的信 号是有源的，由从体200供应的响应被丢弃。逻辑积门591是用于按与逻辑 积门491相同的方式产生来自主体100的RREADY(RREADY_IN)信号和由 从体200输出的RVALID信号的逻辑积的门。如果由逻辑积门591输出的逻 辑积信号是有源的，在先前业务信息管理部分510中使用的信息管理队列511 中保存的业务被释放。

图13是图示根据本公开的第二实施例的先前业务信息管理部分510的典 型配置的方框图。如图所示，先前交易信息管理部分510使用上述信息管理 队列511、管理信息生成部分152、队列状态生成部分513、逻辑和门514和 选择器515。

很像信息管理队列411，信息管理队列511是用于通过采用所谓FIFO(先 进先出)技术来保存先前业务信息的队列。很像管理信息生成部分412，管 理信息生成部分，512是用于生成关于在信息管理队列511中保存的先前业务 信息的信息的部分。也就是说，管理信息生成部分512按与管理信息生成部 分412相同的方式，生成表示关于由与死锁避免电路500相关联的主体100 进行的访问作为对多个不同从体200的访问的信息的STATUS和PID信号。 很像队列状态生成部分413，队列状态生成部分513是用于生成关于信息管 理队列511的状态的信息的部分。更具体地，队列状态生成部分513按与队 列状态生成部分413相同的方式生成XFULL信号，指示在先前业务信息管 理部分511中使用的信息管理队列510还没有满。

逻辑和门514是用于产生POP和RETRY信号的逻辑和的门。由逻辑和 门514输出的信号被用作用于从信息管理队列511的头部提取先前业务信息 的弹出信号。也就是说，在第一实施例的情况下，由逻辑积门491输出的信 号被照原样用作弹出信号，但另一方面，在第二实施例的情况下，还当由响 应输出控制部分530生成的RETRY信号是有源的时，进行该信息弹出操作。

选择器515是用于从信息管理队列511的条目中选择由RETRY_IDX信 号指定的条目的部分。由选择器515输出的信号被供应给选择器541的输入 终端之一作为RETRY_CMD命令。因此，可以对在信息管理队列511的任一 条目中保存的业务进行重试操作。

图14是图示用作根据本公开的第二实施例的业务发出终止确定部分进 行的典型业务动作确定处理的流程图。表示由根据本公开的第二实施例的业 务发出终止确定部分520进行的典型业务动作确定处理的流程图类似于表示 由根据通过参考图10先前描述的本公开的第二实施例的业务发出终止确定 部分520进行的典型业务动作确定处理的流程图。图14所示的流程图的步骤 S921到S926分别对应于图10所示的流程图的步骤S911到S916。但是，要 注意，如从步骤S914中明显的，第一实施例容许具有依赖关系并传播到不同 目标从体200的n组先前的业务，其中，符号n是包括响应保存缓冲器470 的级的数量。另一方面，如从步骤S924中明显的，第二实施例容许具有顺序 依赖关系并传播到不同目标从体200的x组先前的业务，其中，符号x是包 括响应信息管理队列511的条目的数量。这是因为，如果具有顺序依赖关系 并传播到不同目标从体200的先前业务的组的数量超过x，则先前业务不再 能够被先前业务信息管理部分510控制。

图15是图示根据本公开的第二实施例的响应输出控制部分530的典型配 置的方框图。如图中所述，响应输出控制部分530使用基于最近响应的业务 发出历史搜索部分531和最近响应推送确定部分533。

很像基于最近响应的业务发出历史搜索部分431，基于最近响应的业务 发出历史搜索部分531是用于搜索信息管理队列511以找到每个具有匹配从 从体200接收的响应的标识符的标识符的已经发出的业务的部分。

最近响应推送确定部分533是用于确定向主体100递送具体业务的顺序 的部分。也就是说，最近响应推送确定部分533确定是否丢弃来自从体200 的对从操作中发现的业务员中以与最近响应推送确定部分433相同的方式选 择的具体业务的响应，该操作已经被基于最近响应的业务发出历史搜索部分 531进行以搜索信息管理队列511，作为每个具有匹配从从体200接收的响应 的标识符的标识符的业务。具体业务是具有匹配从从体200接收的响应的目 标从体号的目标从体号的业务。也就是说，如果具有匹配从从体200接收的 响应的目标从体数量的目标从体数量的具体业务不是最早(least recent)业务， 最近响应推送确定部分533输出用于传递具体业务的条目号的RETRY_IDX 信号和用于作出对业务的另一响应的条目的请求的RETRY信号。

如上所述，根据本公开的第二实施例，如果按不同于预期顺序的顺序从 从体200接收响应，丢弃该响应以便保证将从从体200接收的响应按预期的 顺序传递到主体100。在该情况下，通过向从体200传输对该重试的请求来 请求从体200发送另一响应，来对对应于丢弃的响应的业务进行重试。由于 第二实施例不包括在第一实施例中使用的响应保存缓冲器470，第二实施例 的电路与第一个相比变得简单。

3：第三实施例

在以下中，描述了本公开的第三实施例。在本公开的第一实施例的情况 下，假设在死锁避免电路400中使用响应保存缓冲器470，而在本公开的第 三实施例的情况下，使用每个从体200来同样用作响应保存缓冲器。要注意， 在第三实施例中的总线系统的整体配置与通过先前图参考1说明的相同。

死锁避免电路的配置

图16是图示根据本公开的第三实施例的死锁避免电路600的基本配置的 方框图。如图所示，死锁避免电路600使用先前业务信息管理部分610、业 务发出终止确定部分620、响应输出控制部分630、选择器641、锁存器642 以及逻辑积门651，652，691和691。

先前业务信息管理部分610是用于按与先前业务信息管理部分410相同 的方式来管理关于之前由与所述死锁避免电路600相关联的主体100发给多 个从体200中的任一的先前业务的信息的部分。很像先前业务信息管理部分 410，先前业务信息管理部分610具有用于保存先前业务信息的信息管理队列 611。先前交易信息管理部分610按与先前业务信息管理部分410相同的方式 向业务发出终止确定部分620和响应输出控制部分630供应先前业务信息。

基于由先前业务信息管理部分610管理的先前业务信息，所述业务发出 终止确定部分620按与业务发出终止确定部分420相同的方式确定由与死锁 避免电路600相关联的所述主体100新发出的最近业务是否是死锁的原因。 如果业务发出终止确定部分620确定由与死锁避免电路600相关联的主体100 新发出的最近业务是死锁的原因，所述业务发出终止确定部分620停止向从 体200递送最近业务的操作。更具体地，如果业务发出终止确定部分620确 定由与死锁避免电路600相关联的主体100新发出的最近业务是死锁的原因， 所述业务发出终止确定部分620通过激活向逻辑积门651输出的STOP信号 来停止向从体200递送最近业务的操作。

响应输出控制部分630是用于按与响应输出控制部分430相同的方式、 基于由先前业务信息管理部分610管理的先前业务信息来控制要递送到与死 锁避免电路600相关联的主体100的响应的部分。但是，在第三实施例的情 况下，假设还使用每个从体200作为响应保存缓冲器。因此，响应输出控制 部分630控制要被保存在这种缓冲器中的响应作为给从体200的命令。

选择器641是用于选择从与地址信道相关联的主体100新接收的最近业 务或与从先前业务信息管理部分630接收的外部命令相关的业务的选择部 分。锁存器642用于保存由选择器641选择的业务的信号。逻辑积门651是 用于按与逻辑积门451相同的方式根据由业务发出终止确定部分620输出的 STOP信号来掩蔽在锁存器642中锁存的AVALID信号的门。

逻辑积门652是用于按与逻辑积门452相同的方式产生来自从体200的 AREADY(AREADY_IN)信号和由逻辑积门651输出的信号的逻辑积的门。 逻辑积门691是用于按与逻辑积门491相同的方式产生来自主体100的 RREADY(RREADY_IN)信号和由从体200输出的RVALID信号的逻辑积的 门。如果由逻辑积门691输出的逻辑积信号是有源的，在先前业务信息管理 部分611中使用的信息管理队列610中保存的业务被释放。

图17是图示根据本公开的第三实施例的响应输出控制部分630的典型配 置的方框图。因此，响应输出控制部分630具有类似于响应输出控制部分430 的配置的配置。但是，在第三实施例的情况下，在从体200中提供响应保存 缓冲器。因此，为了模拟响应保存缓冲器，响应输出控制部分630还被提供 有业务标识符/从体号保存部分636和命令生成部分637。另外，响应输出控 制部分630使用最早响应第一优先级处理部分635来替换最早响应第一优先 级处理部分435。

业务标识符/从体号保存部分636是用于保存从从体200接收的保存的数 据的部分。更具体地，业务标识符/从体号保存部分636保存与从目标从体200 接收的响应相关的业务的标识符RID和目标从体200的从体号RTGT。

业务标识符/从体号保存部分636向基于最早响应的业务发出历史搜索部 分632关于所保存的也标识符RID，作为保存的业务标识符SID，并向最早 响应弹出确定部分634关于保存的业务从体号RTGT作为保存的业务从体号 STGT。也就是说，最早响应的业务发出历史搜索部分632从业务标识符/从 体号保存部分636接收保存的业务标识符SID，而最早响应弹出确定部分634 接收从业务标识符/从体号保存部分636接收保存的业务从体号STGT。

如果在从体200中存在的响应保存缓冲器200中保存的响应可以被递送 给主体100，则最早响应第一优先级处理部分635进行控制以优先处理响应。 因此，如果在从体200中存在的响应保存缓冲器200中保存的响应可以被递 送给主体100，则最早响应第一优先级处理部分635向递送响应到主体100 的处理给出最高的优先级，允许响应的处理优先于要对新来自从体200的最 近响应进行的处理。也就是说，通过输出以下表述作为用于从缓冲器中取出 保存的数据的信号的ISSUE_READ信号，进行从从体200中存在的响应保存 缓冲器读出响应的操作

ISSUE_READ＝drain_shltr_w & ANY_IN_SHELTER

在以上表达式，符号ANY_IN_SHELTER表示ANY_IN_SHELTER信号， 其当DRAIN_SHELTER信号被设置为1时转变为0，且当ROUTE_SHELTER 信号被设置为1时转变为1。另外，通过输出以下表述作为用于向缓冲器中 存储响应的信号的ISSUE_WRITE信号，进行向从体200中存在的响应保存 缓冲器中传递响应的操作。

ISSUE_WRITE＝NOT(ISSUE_READ)& route_shltr_w

命令操作部分637是用于基于从最早响应第一优先级处理部分635接收 的ISSUE_READ和ISSUE_WRITE信号、生成访问在从体200中存在的响 应保存缓冲器的命令的部分。更具体地，当ISSUE_READ信号被激活时， 命令生成部分637生成进行读取在从体200中存在的响应保存缓冲器中的具 体地址处保存的数据以便取出数据的操作的EXT_COMMAND命令。另一方 面，当ISSUE_WRITE信号被激活时，命令生成部分637生成进行在从体200 中存在的响应保存缓冲器中的具体地址处写向主体100传递的响应以便存储 响应的操作。命令生成部分637向选择器641的输入端之一关于 EXT_COMMAND命令。

如上所述，根据本公开的第三实施例，如果按不同于预期顺序的顺序从 从体200输出响应，在从体200中存在的响应保存缓冲器中保存响应。因此， 能够容许具有依赖关系且由不同从体100生成的响应。

4：第四实施例

在以下中，描述了本公开的第四实施例。在本公开的第一到第三实施例 的情况下，为每个主体100提供死锁避免电路。另一方面，在本公开的第四 实施例，提供对所有主体100公共的一个死锁避免电路以用作由主体100共 享的电路。注意，在第四实施例中的总线系统的总体配置与参考图1先前描 述的相同。

互连的配置

图18是图示根据本公开的第四实施例的互连300的典型配置的方框图。 在以下描述中，假设总线系统具有链接到两个主体100和两个从体200的互 连300。要注意，第四实施例还与第一到第三实施例相同的方式采用AXI协 议。

在第四实施例的情况下，互连300使用对所有主体100公共的一个死锁 避免电路700。死锁避免电路700是用于控制操作以便由主体100进行的业 务不导致死锁的电路对于用作第一主体的主体#1，地址信道被信号线11和 21实现，而响应信道被信号线31和41实现。另一方面，对于用作第二主体 的主体#2，地址信道被信号线12和22实现，而响应信道被信号线32和42 实现。表示地址和响应信道的每个的箭头的方向与通过由箭头表示的信道传 播的主信号的方向相同。但是，实际上，如果通过信道传播的信号包括控制 信号，控制信号通常在两个方向上交换。

死锁避免电路的配置

图19是图示根据本公开的第四实施例的死锁避免电路700的基本配置的 方框图。如图所示，死锁避免电路700使用先前业务信息管理部分710、业 务发出终止确定部分720、响应输出控制部分730以及逻辑积门741、742。

先前交易信息管理部分710是管理关于由每个主体100发出的先前业务 的信息的部分。先前交易信息管理部分710包括为每个主体100提供的信息 管理队列711，以用作用于保存关于由主体100发出的先前业务的信息的队 列。先前交易信息管理部分710通过信号线719向业务发出终止确定部分720 供应关于先前业务的信息。在以下描述中，关于先前业务的信息也被称为先 前业务信息。

基于由先前业务信息管理部分710管理的先前业务信息，所述业务发出 终止确定部分720确定由主体100新发出的最近业务是否是死锁的原因。如 果业务发出终止确定部分720确定由主体100新发出的最近业务是死锁的原 因，所述业务发出终止确定部分720停止向从体200递送业务的操作。业务 发出终止确定部分720还确定根据由主体100新发出的业务的访问是否处于 在传输期间维持真实的叉乘关系，以便检测死锁的可能性。稍后将具体描述 确定方法。如果业务发出终止确定部分720确定不存在死锁的可能性，业务 发出终止确定部分720通过信号线729向先前业务信息管理部分710输出关 于该业务的信息，然后先前业务信息管理部分710注册关于为发出业务的主 体100提供的信息管理队列711的信息。

逻辑积门741和742的每个是用于根据由业务发出终止确定部分720输 出的STOP信号，避免AVALID信号的门，该AVALID信号正通过地址信道 传播。更具体地，当业务发出终止确定部分720通过信号线721向逻辑积门 741关于用于作为第一主体100的主体#1的STOP信号时，逻辑积门741掩 蔽第一主体100的AVALID信号。由于相同的原因，当业务发出终止确定部 分720通过信号线722向逻辑积门741关于用于作为第二主体100的主体#2 的STOP信号时，逻辑积门742掩蔽第二主体100的AVALID信号。

响应输出控制部分730是用于通过信号线739通知先前业务信息管理部 分710当由从体200生成的响应已经被传递到主体100时已经完成了显著的 传输的部分。

图20是图示根据本公开的第四实施例的先前业务信息管理部分710的典 型配置的方框图。如图所示，先前交易信息管理部分710使用分别为M个主 体100提供的信息管理队列711-1到711-M。信息管理队列711-1到711-M是 用于通过采用FIFO技术来保存先前业务信息的队列。在该情况下，假设在 信息管理队列711中保存的先前业务信息包括目标从体号TGT。因此，通过 使用信息管理队列711-1到711-M，能够管理目标从体号TGT和关于其中由 主体100发出业务的顺序。先前交易信息管理部分710通过信号线719向业 务发出终止确定部分720供应先前业务信息。

当业务发出终止确定部分720允许由主体100作出的作为用于访问从体 200的请求时，业务发出终止确定部分720通过信号线729向先前业务信息 管理部分710关于从体200的目标从体号。然后，先前交易信息管理部分710 在从信息管理队列711-1到711-M中选择作为为主体100提供的队列的信息 管理队列711上注册目标从体号。

另外，当从体200通过响应输出控制部分730向主体100传输响应时， 响应输出控制部分730通过信号线739通知先前业务信息管理部分710有关 被分配给从体200的目标从体号。然后，先前交易信息管理部分710在从信 息管理队列711-1到711-M中选择作为为主体100提供的队列的信息管理队 列711中删除目标从体号。

图1A到21A是示出在根据本公开的第四实施例的信息管理队列711上 注册先前业务信息的典型操作的图。首先，如图21A所示，用作第一主体100 的主体M1向用作第一从体200的从体S1发出业务M1₁，而用作第二主体100 的主体M2向用作第二从体200的从体S2发出业务M2₁。那时，如图21B所 示，被分配给第一从体200(或从体S1)的从体号S1被注册在为第一从体 100(或主体M1)提供的信息管理队列711-1的头部处，而被分配给第二从 体200(或从体S2)的从体号S2被注册在为第二主体100(或主体M2)提 供的信息管理队列711-2的头部处。

然后，如图21A所示，第一主体100(或主体M1)向第二从体200(或 从体S2)发出业务M1₂，而第二主体100(或主体M2)向第一从体200(或 从体S1)发出业务M2₂。那时，如图21C所示，被分配给第二从体200(或 从体S2)的从体号S1被注册在为第一从体100(或主体M1)提供的信息管 理队列711-1的尾部处，而被分配给第一从体200(或从体S1)的从体号S1 被注册在为第二主体100(或主体M2)提供的信息管理队列711-2的尾部处。

图图22A和22B每个是用作根据本公开的第四实施例的业务发出终止确 定部分720采用的死锁确定技术的以下描述中参考的图。业务发出终止确定 部分720使用图22A所示的虚拟电路811和822以便确定死锁性能。第一虚 拟电路811是表示由第一主体100(或主体M1)进行的访问之间的互相依赖 关系的块，而第二虚拟电路812是表示由第二主体100(或主体M2)进行的 访问之间的互相依赖的关系的块。虚拟电路811和822的每个的每个输入端 被分配给从体200之一，而虚拟电路811和822的每个的每个输出端被分配 给从体200之一，以便表示根据在输入和输出端之间的连接的存在/不存在的 互相依赖的关系。图22A和22B所示的典型例子具有四个从体200。

以下使用图21A到21C所示的典型例子。首先，在用作第一主体100的 主体M1中，示出了从从体号S2到从体号S1的依赖关系。因此，假设从在 第一虚拟电路811中的输入端S2到输出端S1的连接。另外，在用作第二主 体100的主体M2中，示出了从从体号S1到从体号S2的依赖关系。因此， 假设从在第二虚拟电路812中的输入端S1到输出端S1的连接。然后，虚拟 电路811和812彼此串联连接。供应给第一虚拟电路811的输入端的信号与 从第二虚拟电路812的输出端输出的信号相比较，且如果从两个信号检测相 同电平，则确定在访问中的(叉乘)依赖关系。在同一图中所示的典型例子 中，从体号S2对应于此。

图23是图示用作根据本公开的第四实施例的业务发出终止确定部分720 进行的典型业务动作确定处理的流程图。如图所示，流程图开始于步骤S931， 此处，从主体Mi接收最近业务。当从主体Mi接收最近业务时，业务发出终 止确定部分720如下确定是否可以向从体200递送最近业务。

首先，在以下步骤S932处，业务发出终止确定部分720检查从相同主体 接收的业务。也就是说，业务发出终止确定部分720确定是否存在在从主体 M1接收的最近业务和也从主体Mi接收的先前业务之间的依赖关系以及最近 业务是否具有不同于先前业务的目标从体。如果不在最近业务和先前业务之 间存在依赖关系，不需要考虑死锁。因此，在该情况下，业务动作确定处理 的流程继续到步骤S935中，此处，向从体200递送最近业务。即使存在在最 近业务和先前业务之间的依赖关系，最近业务的目标从体可以匹配先前业务 的目标从体。在该情况下，不发生突变，只要从体200维持该顺序。因此， 业务动作确定处理的流程也继续到步骤S935。

另一方面，如果存在在最近业务和先前业务之间的依赖关系，且最近业 务具有不同于先前业务的目标从体的目标从体，业务动作确定处理的流程继 续到步骤S933。

然后，在以下步骤S933处，业务发出终止确定部分720检查从主体Mi 和另一主体接收的业务。也就是说，业务发出终止确定部分720确定该另一 主体是否发出了具有依赖关系的传输，传输的目标从体是否完全匹配主体Mi 的目标从体，以及预期响应转发(forwarding)顺序是否被反转了。这种关系 的存在暗示了存在叉乘的依赖关系。因此，在该情况下，业务动作确定处理 的流程图继续到步骤S36，此处，停止传递最近业务的操作。另一方面，如 果不存在叉乘依赖关系，业务动作确定处理的流程图继续到步骤S35，此处， 禁止向从体200传递最近业务的操作。

要注意，为了检测叉乘依赖关系，可以使用先前参考图22A和22B说明 的虚拟电路811和822。

死锁确定

图24A到24C是在以下描述由本公开的第四实施例采用的第一典型死 锁确定技术时参考的图。在如图24A所示的典型情况下，用作第一主体100 的主体M1向用作第一从体200的从体S1发出业务M1₁，而用作第二主体100 的主体M2向用作第三从体200的从体S3发出业务M2₁。那时，如图24B所 示，被分配给第一从体200(或从体S1)的从体号S1被注册在为第一从体 100(或主体M1)提供的信息管理队列711-1的头部处，而被分配给第三从 体200(或从体S3)的从体号S3被注册在为第二主体100(或主体M2)提 供的信息管理队列711-2的头部处。

然后，如图24A所示，第一主体100(或主体M1)向第二从体200(或 从体S2)发出业务M1₂，而第二主体100(或主体M2)向第四从体200(或 从体S4)发出业务M2₂。那时，如图24B所示，被分配给第二从体200(或 从体S2)的从体号S1被注册在为第一从体100(或主体M1)提供的信息管 理队列711-1的尾部处，而被分配给第四从体200(或从体S4)的从体号S4 被注册在为第二主体100(或主体M2)提供的信息管理队列711-2的尾部处。

因此，在表示在由第一主体100(或主体M1)进行的访问之间的依赖关 系的块中，假设从输入端S2到输出端S1的连接，如在图24C的左侧所示。 由于相同的原因，在表示在由第二主体100(或主体M2)进行的访问之间的 依赖关系的块中，假设从输入端S4到输出端S3的连接，如在图24C的右侧 所示。因此，结论是，无法检测叉乘依赖关系。

图25A到25C是在以下描述由本公开的第四实施例采用的第二典型死 锁确定技术时参考的图。在如图25A所示的典型情况下，用作第一主体100 的主体M1向用作第一从体200的从体S1发出业务M1₁，而用作第二主体100 的主体M2也向从体S1发出业务M2₁。那时，如图25B所示，被分配给第一 从体200(或从体S1)的从体号S1被注册在为第一从体100(或主体M1) 提供的信息管理队列711-1的头部处，而从体号S1也被注册在为第二主体100 (或主体M2)提供的信息管理队列711-2的头部处。

然后，如图25A所示，第一主体100(或主体M1)向第二从体200(或 从体S2)发出业务M1₂，而第二主体100(或主体M2)向第三从体200(或 从体S3)发出业务M2₂。那时，如图25B所示，被分配给第二从体200(或 从体S2)的从体号S1被注册在为第一从体100(或主体M1)提供的信息管 理队列711-1的尾部处，而被分配给第三从体200(或从体S3)的从体号S3 被注册在为第二主体100(或主体M2)提供的信息管理队列711-2的尾部处。

因此，在表示在由第一主体100(或主体M1)进行的访问之间的依赖关 系的块中，假设从输入端S2到输出端S1的连接，如在图25C的左侧所示。 由于相同的原因，在表示在由第二主体100(或主体M2)进行的访问之间的 依赖关系的块中，假设从输入端S3到输出端S1的连接，如在图25C的右侧 所示。因此，结论是，无法检测叉乘依赖关系。

图26A到26C是在以下描述由本公开的第四实施例采用的第三典型死 锁确定技术时参考的图。在如图26A所示的典型情况下，用作第一主体100 的主体M1向用作第一从体200的从体S1发出业务M1₁，而用作第二主体100 的主体M2向用作第三从体200的从体S3发出业务M2₁。那时，如图26B所 示，被分配给第一从体200(或从体S1)的从体号S1被注册在为第一从体 100(或主体M1)提供的信息管理队列711-1的头部处，而被分配给第三从 体200(或从体S3)的从体号S3被注册在为第二主体100(或主体M2)提 供的信息管理队列711-2的头部处。

然后，如图26A所示，第一主体100(或主体M1)向第二从体200(或 从体S2)发出业务M1₂，而第二主体100(或主体M2)向第一从体200(或 从体S1)发出业务M2₂。那时，如图26B所示，被分配给第二从体200(或 从体S2)的从体号S1被注册在为第一从体100(或主体M1)提供的信息管 理队列711-1的尾部处，而被分配给第一从体200(或从体S1)的从体号S1 被注册在为第二主体100(或主体M2)提供的信息管理队列711-2的尾部处。

因此，在表示在由第一主体100(或主体M1)进行的访问之间的依赖关 系的块中，假设从输入端S2到输出端S1的连接，如在图26C的左侧所示。 由于相同的原因，在表示在由第二主体100(或主体M2)进行的访问之间的 依赖关系的块中，假设从输入端S1到输出端S3的连接，如在图26C的右侧 所示。因此，结论是，无法检测叉乘依赖关系。

图27A到27C是在以下描述由本公开的第四实施例采用的第四典型死 锁确定技术时参考的图。在图中所示的典型情况下，分别假设也称为主体M1， M2和M3的三个主体100。因此，分别为三个主体100提供三个信息管理 队列711-1到711-3。由于这个原因，用于检测叉乘依赖关系的三个虚拟电 路在三个级处提供，且彼此串联连接。另外，虚拟电路的每个通过逻辑和门 向其他虚拟电路供应其输出。

首先，在如图27A所示的典型情况下，用作第一主体100的主体M1向 用作第一从体200的从体S1发出业务M1₁，而用作第二主体100的主体M2 向用作第三从体200的从体S3发出业务M2₁，且用作第三主体100的主体 M3向用作第二从体200的从体S2发出业务M3₁。

那时，如图27B所示，被分配给第一从体200(或从体S1)的从体号S1 被注册在为第一从体100(或主体M1)提供的信息管理队列711-1的头部处， 而被分配给第三从体200(或从体S3)的从体号S3被注册在为第二主体100 (或主体M2)提供的信息管理队列711-2的头部处，且被分配给第二从体200 (或从体S2)的从体号S2被注册在为第三主体100(或主体M3)提供的信 息管理队列711-3的头部处。

然后，如图27A所示，第一主体100(或主体M1)向第二从体200(或 从体S2)发出业务M1₂，而第二主体100(或主体M2)向第一从体200(或 从体S1)发出业务M2₂，且第三主体100(主体M3)向第三从体200(或从 体S3)发出业务M3₂。那时，如图27B所示，被分配给第二从体200(或从 体S2)的从体号S1被注册在为第一从体100(或主体M1)提供的信息管理 队列711-1的尾部处，而被分配给第一从体200(或从体S1)的从体号S1被 注册在为第二主体100(或主体M2)提供的信息管理队列711-2的尾部处， 且被分配给第三从体200(或从体S3)的从体号S3被注册在为第三主体100 (或主体M3)提供的信息管理队列711-3的尾部处。

因此，在表示在由第一主体100(或主体M1)进行的访问之间的依赖关 系的块中，假设从输入端S2到输出端S1的连接，如在图27C的左侧所示。 由于相同的原因，在表示在由第二主体100(或主体M2)进行的访问之间的 依赖关系的块中，假设从输入端S1到输出端S3的连接，如在图26C的中间 所示。以相同方式，假设从输入端S3到输出端S2的连接，如在图26C的右 侧所示。因此，结论是，检测到叉乘依赖关系。

如上所述，根据本公开的第四实施例，如果检测叉乘依赖关系，停止传 递业务的操作。因此，能够防止发生死锁。

也就是说，根据本公开的实施例，能够防止发生死锁，同时相比于现有 技术而减少性能恶化。另外，通过选择互连的需要的性能电平和对互连施加 的限制适当的死锁避免机制，可以实现分裂的总线系统。

要注意，本公开的实施例不限于死锁避免电路的典型实施方式。如从本 公开的实施例的描述明显的，本公开的实施例的术语与本权利要求的范围中 描述的其分别的发明细节相关联。由于相同的原因，在本权利要求的范围中 描述的发明细节与作为每个具有与本发明细节之一相同的名称的项目的在本 公开的实施例中描述的其各个项目相关联。但是，本公开的实施方式决不限 于本公开的实施例。也就是说，能够通过将实施例进一步改变为在不脱离本 公开的实质的范围内的修改版本来实现本公开。

本公开包含涉及分别在2010年9月29日在日本专利局提交的日本优先 权专利申请JP 2010-218612中公开的主题，其全部内容被引用附于此。