指令的多个并行被动线程利用“活动”信标协调对共享资源的访问。这些信标被称为活动的是因为这些信标发送消息给执行和/或控制电路以使得线程的状态改变。一线程可由线程调度器响应于未决相关性而被置于不活动状态，该未决相关性可由一信标指示。与该相关性相对应的线程状态变量被用于指示该线程处于不活动模式。当该相关性被解决时，将一消息传递给控制电路，使得相关性变量被清除。响应于被清除的相关性变量，将该线程置于活动状态。执行可在处于活动状态的线程上进行。
响应于由所述信标表示的一组预定条件中的至少一个的检测，将所述指令的可执行线程置于不活动状态；
对于所述指令的可执行线程，从所述信标将一消息发送给控制电路以执行所述指令的可执行线程，以从所述不活动状态改变所述指令的可执行线程的状态，其中所述消息包括用于标识所述指令的可执行线程以支持将所述消息传送给所述指令的可执行线程的数据。
2.如权利要求1所述的方法，其特征在于，从所述不活动状态改变所述指令的线程的状态包括将所述指令的线程的状态变成活动状态。
3.如权利要求2所述的方法，其特征在于，还包括当处于活动状态时执行所述指令的线程。
4.如权利要求1所述的方法，其特征在于，所述一组预定条件包括未决相关性。
5.如权利要求1所述的方法，其特征在于，所述一组预定条件包括来自所述信标的响应，指示与所述信标相对应的资源是不可用的。
6.如权利要求1所述的方法，其特征在于，还包括维持指令的多个可执行线程中每一个的状态指示。
7.如权利要求6所述的方法，其特征在于，所述多个可执行线程中每个线程的状态指示包括相关线程的与可能存在的相关性相对应的状态变量。
执行装置，用于响应于由信标表示的一组预定条件中的至少一个的检测将所述指令的可执行线程置于不活动状态；
通信装置，用于对于所述指令的可执行线程，从一信标将一消息发送给控制电路以执行所述指令的可执行线程，以从所述不活动状态改变所述指令的可执行线程的状态，其中所述消息包括用于标识所述指令的可执行线程以支持将所述消息传送给所述指令的可执行线程的数据。
9.如权利要求8所述的装置，其特征在于，还包括用于维持指令的多个可执行线程中每一个的状态指示的装置。
10.如权利要求9所述的装置，其特征在于，每个线程的状态的指示包括相关线程的与可能存在的相关性相对应的状态变量。
用于接收并执行指令的线程的执行电路，其中所述执行电路发送信标请求消息并响应于请求具有相关信标的资源的所述指令的线程将所述指令的线程置于不活动状态；和控制电路，所述控制电路包括线程调度电路，用于管理在所述处理核心上执行的多个线程的状态，以及信标实体，所述信标实体包括：
与所述执行电路耦合的控制逻辑，用以从所述执行电路接收所述相关信标请求消息，并响应于所述信标请求消息通过将对于所述指令的线程的信标确认消息发送到所述执行电路而选择性地准许所述指令的线程对所述信标的控制，所述信标确认消息包括用于标识所述指令的线程以支持将所述消息传送给所述指令的线程的数据，其中所述执行电路响应于接收所述信标确认消息从所述不活动状态中移除所述指令的线程。
12.如权利要求11所述的装置，其特征在于，还包括：执行指令的线程的至少一个附加执行电路；以及
与所述执行电路和至少一个附加执行电路耦合的线程分配器，用以分配由选定执行电路执行的线程。
13.如权利要求11所述的装置，其特征在于，所述执行电路响应于接收所述信标确认消息再继续所述指令线程的执行，包括访问与所述信标相关联的资源。
14.如权利要求11所述的装置，其特征在于，当所述指令线程处于不活动状态时，所述指令的执行停止且所述执行电路不轮询所述信标实体以确定所述信标请求消息的状态。
与所述存储器控制器耦合以接收并执行指令线程的执行电路，其中所述执行电路发送一信标请求消息并响应于请求具有相关信标的资源的所述指令的线程将所述指令的线程置于不活动状态；和控制电路，所述控制电路包括线程调度电路，用于管理在所述处理核心上执行的多个线程的状态，以及信标实体，所述信标实体包括：
与所述执行电路耦合的控制逻辑，用以从所述执行电路接收信标请求消息，并响应于所述信标请求消息通过将对于所述指令的线程的信标确认消息发送到所述执行电路而选择性地准许所述指令的线程对所述相关信标的控制，所述信标确认消息包括用于标识所述指令的线程以支持将所述消息传送给所述指令的线程的数据，其中所述执行电路响应于接收所述信标确认消息从所述不活动状态中移除所述指令的线程。
16.如权利要求15所述的系统，其特征在于，还包括：执行指令的线程的至少一个附加执行电路；以及
与所述执行电路和至少一个附加执行电路耦合的线程分配器，用于分配由选定的执行电路执行的线程。
17.如权利要求15所述的系统，其特征在于，所述执行电路响应于接收所述信标确认消息再继续所述指令线程的执行，包括访问与所述信标相关联的资源。
18.如权利要求15所述的系统，其特征在于，当所述指令的线程处于不活动状态时，所述指令的执行停止且所述执行电路不轮询所述信标实体以确定所述信标请求消息的状态。
具有被动线程和活动信标的处理架构
技术领域
[0001] 本发明涉及用于多线程处理的技术和架构，尤其涉及将被动线程和活动信标用于多线程处理的技术和架构。
背景技术
[0002] “信标”(也称作“关键段”或“互斥体”)是硬件和软件构成，它允许其中多个进程竞争共享资源(例如，存储器，文件)的操作的协调或同步。一般，信标是存储在进程可以检查和改变的操作系统存储器的指定位置中的值。根据信标的值，进程可以访问共享资源或者等待一段时间并再次检查该信标。
[0003] 常规计算机系统中的信标通常可用原子“测试和设定”或类似类型的指令(例如，锁定、位测试和设定、位测试和重设)的硬件支持实现为软件例程。使用该信标实现，可以通过共享(例如全局)数据和一个或多个信标来建立制造者-消费者通信关系。信标允许正尝试更改数据的多个进程中的选定一个更改共享数据，这提供了数据一致性。
[0004] 该信标构成是“被动的”，因为多个线程必须执行轮询操作以获得一信标。轮询要求消耗否则可用于其它用途的处理器和系统资源。因此，传统的信标会导致无效率。
附图说明
[0005] 借助示例而非限制地说明本发明，附图中相同的标号表示相似的元件。
[0006] 图1是整体多线程处理器架构的一个实施例的框图。
[0007] 图2是基于链接列表的信标结构的一个实施例的概念框图。
[0008] 图3是用于获得活动信标的一项技术的一个实施例的事件流程图。
[0009] 图4是用于释放活动信标的一项技术的一个实施例的流程图。
具体实施方式
[0010] 将描述与被动线程一起使用的活动信标。在以下描述中，为说明目的，阐述了大量特定细节以提供本发明的透彻理解。但显然，本领域的熟练技术人员可在没有这些特定细节的情况下实施本发明。在其它实例中，按框图形式示出结构和装置以避免模糊本发明。
[0011] 活动信标的示例使用的概述
[0012] 这里描述的是其中指令的多个并行被动线程(以下称作“线程”)用“活动”信标协调对共享资源的访问的一架构和相关方法。将信标称作是活动的，是因为信标实体发送消息给执行和/或控制电路以引起线程状态改变。例如，可响应于可由信标表示的未决相关性通过线程调度器将线程置于休眠(或不活动)模式。使用与该相关性相对应的线程状态变量来表示该线程处于休眠模式。
[0013] 当解决相关性时，将一消息传递到控制电路(例如，线程调度器)，使得该相关性变量被清除。响应于被清除的相关性变量，将线程置于活动(或唤醒)状态。执行可在活动状态中的线程上进行。
[0014] 继续以上示例，如果线程尝试获得一信标而不能，则将该线程置于不活动状态。因为线程是不活动的，所以它不能轮询信标以确定信标所指示的相关性何时被解决，如现有技术中所需要的那样。在(例如从信标实体)接收到指示已解决相关性的消息前该线程保持不活动状态。响应于该消息，将线程置于活动状态，这允许执行继续进行。
[0015] 图1是整体多线程处理器架构的一个实施例的框图。如这里所使用的，标签“整体多线程”架构表示包括可支持多线程执行的多个处理器的架构。在一个实施例中，每个处理器可以支持一个或多个线程。单个处理器上的多线程通过允许在其它线程处于不活动状态时执行活动线程而实现了较高的执行效率。等待信标的处于不活动状态中的线程不消耗/浪费处理器资源。尽管是关于整体多线程架构的描述，但信标构成和相关方法可应用于任何多线程架构，而不管所支持的线程数。
[0016] 整体多线程系统100包括存储器分层结构110，它存储数据和指令以便在执行期间由一个或多个处理核心使用。存储器分层结构110可以按任何本领域已知的方式包括动态随机存取存储器(DRAM)、一级或多级指令高速缓存、一级或多级数据高速缓存、和/或一级或多级共享指令和数据高速缓存。线程分配器120与存储器分层结构110耦合，接收与新线程相关联的信息，诸如指令指针和数据和/或数据指针。线程分配器120也经由消息总线125与处理核心耦合。在一个实施例中，线程分配器120负责管理处理核心的线程资源。在接收到新的未决线程时，线程分配器120选择具有所述资源的一个处理核心来执行该未决线程并将该线程分配到选定的处理核心上。在完成处理核心上的现有线程后，通知线程分配器120，从而使得处理核心上的线程资源可用于将来的未决线程。
[0017] 系统100示出具有多个处理器核心(130、131、139、150、151和159)，它们每一个都包括具有相关控制电路的执行电路。处理器核心可以是一样的，或者处理器核心可具有不同的功能性。任意数量的处理器核心可包含于系统100内。在一个实施例中，处理器核心按行配置，每一行都具有一个行控制器。例如，行控制器140可经由行控制总线145与处理器核心130、131和139耦合。类似地，行控制器160可经由行控制总线165与处理器核心150、151和159耦合。
[0018] 处理器核心还经由消息总线125与信标实体170耦合。信标实体170包括存储器和控制逻辑以提供这里所述的信标功能。在一个实施例中，信标实体170通过发送和接收消息而与处理器核心交互，如以下更详细地描述的。
[0019] 线程分配器120也经由消息总线125与信标实体170耦合。在一个实施例中，线程分配器代表一线程通过发送和接收消息而与信标实体170交互，如以下更详细地描述的。
[0020] 每个处理器核心中的控制电路可包含线程调度电路，用于管理同一处理核心上执行的多个线程的状态，并且还可包含指令调度电路，用于执行指令的活动线程。在指令执行期间，一个或多个处理核心将尝试访问共享的系统资源。为获得共享系统资源的控制，一线程必须通过相应的执行核心获得与要访问的共享系统资源相对应的信标的控制。
[0021] 在一个实施例中，为获得信标的控制，请求处理核心在消息总线125上将一信标请求消息发送给信标实体170。在发送该信标请求消息后，将请求线程置于不活动状态，其中执行和相关操作(例如，信标的轮询)停止。
[0022] 响应于接收到信标请求消息，信标实体170确定是否将信标的控制授予请求线程。当授予信标时，信标实体170发送一信标确认消息给请求线程。响应于该信标确认消息，请求线程恢复到活动状态，其中使用被请求资源的执行可以继续。当线程完成了共享资源的使用时，线程发送一释放信标消息给信标实体170。响应于该释放信标消息，信标实体170释放该信标并允许其它线程获得对该系统资源的访问。
[0023] 在一个实施例中，信标由处理器核心执行的指令(信标指令)以及在例如消息总线125上处理器核心和信标实体之间传递的消息(信标消息)支持。在可选实施例中，可以支持不同和/或附加的消息或指令。
[0024] 基于链接列表的信标实体
[0025] 图2是基于链接列表的信标结构的一个实施例的概念框图。在一个实施例中，传统的按信标队列由缓冲池代替，该缓冲池具有用于为每个信标形成链接列表的条目。因此，每个信标可以是指向由缓冲池中的条目形成的链接列表的首部指针。该链接列表可以是双向链接列表或单向链接列表。
[0026] 在一个实施例中，信标表200包括所支持的每个信标(例如，信标条目201和202)的指针。在一个实施例中，信标表200中的指针是指示要用于相应信标的链接列表的首部的首部指针。在一个实施例中，空闲池指针220指示缓冲池210的首部，且未使用的信标条目包括NULL指针。
[0027] 在一个实施例中，每个信标条目(例如，211、212、213、214、215、216)包括释放状态字段、确认-抑制字段、线程标识符字段、前一指针和下一指针。在可选实施例中，可以使用其它和/或不同的字段，例如可省去前一指针。在一个实施例中，每个信标也可包括单个位(或其它指示符)以指示与该信标相对应的链接列表是否是空的。
[0028] 在图2的示例中，空闲池指针220指向缓冲池中空闲条目的首部，且每个空闲条目都包括指向后续空闲条目的指针，例如，首部空闲条目216包括指向空闲条目215的指针。信标类似地具有相关链接列表。例如，信标表200中的条目201和202对应于活动信标。条目201包括指向作为信标链接列表中的首部条目的条目211的指针，并包括指向作为链接列表中的后续条目的条目212的指针。类似地，条目202包括指向作为信标链接列表中的首部条目的条目213的指针，并包括指向作为链接列表中的后续条目的条目214的指针。
[0029] 信标消息
[0030] 获得信标消息(ACQ_MSG)用于一线程，或者代表一线程的线程分配器，以向信标实体请求一信标的所有权。在一个实施例中，ACQ_MSG包含信标标识符字段、线程标识符字段、“自动释放”字段和“确认-抑制”(确认-抑制)字段。自动释放字段用于仅具有首部相关性的线程。即，该线程取决于前一线程，但无后续线程取决于该线程。确认-抑制字段用于仅具有尾部相关性的线程。即该线程不取决于任何先前的线程，但该线程具有取决于它的后续线程。ACQ_MSG可由线程分配器或与该线程相关联的其它控制电路发出。
[0031] 在一个实施例中，在接收到ACQ_MSG时，通过将首部条目从空闲池列表中去除并将其添加到选定信标的尾部，信标实体将请求线程的信标条目入队到目标信标的链接列表(由信标标识符字段指定)中。根据ACQ_MSG中的信息更新信标实体的字段：线程标识符字段、释放状态字段和确认-抑制字段由ACQ_MSG中的请求者的线程标识符、自动释放字段和确认-抑制字段代替。如果ACQ_MSG之前信标链接列表非空，则信标实体不发送消息。否则，如果在接收到ACQ_MSG之前信标链接列表是空的，则进行以下步骤之一。
[0032] 如果确认-抑制字段未被设定，则具有线程标识符的ACK_MSG在消息总线125上从信标实体发送到请求线程。如果确认-抑制字段被设定，则不从信标实体发送ACK_MSG。如果自动释放字段未被设定，则在信标链接列表中保留刚入队的信标条目。因此，信标链接列表非空且信标当前由线程所有。如果自动释放字段被设定，则从信标链接列表中去除刚入队的信标条目，因此信标链接列表是空的。
[0033] 释放信标消息(REL_MSG)用于一线程以向信标实体请求释放一信标的所有权。在一个实施例中，REL_MSG包括信标标识符字段和线程标识符字段。在一个实施例中，REL_MSG仅可由与拥有信标所有权的线程相关联的控制电路发出，即线程标识符位于信标链接列表的顶部。在接收到REL_MSG后，信标实体从信标链接列表的首部中去除该条目。
[0034] 在另一实施例中，REL_MSG可由与共享该信标的任何线程相关联的控制电路发出。在接收到REL_MSG时，信标实体复位释放状态字段到信标链接列表中的相应条目，而不管链接列表中条目的位置。如果信标条目位于链接列表的首部，则从信标链接列表的首部中去除该条目。随后，下一个条目变成链接列表的首部。如果下一个条目不是NULL，则它将被检查。如果链接列表的新首部设置了释放状态字段，则再次将它从信标链接列表的首部中去除。
[0035] 在一个实施例中，在链接列表首部为NULL(信标队列是空的)或者链接列表的首部未设置释放状态字段(等待信标从与条目相对应的线程释放)之前，继续该递归过程。如果链接列表的首部不是NULL且未设置确认-抑制字段，则信标实体将ACK_MSG发送给由条目的线程标识符字段所标识的线程。如果链接列表的首部不是NULL并且设定了确认-抑制字段，则不发送ACK_MSG。
[0036] 信标确认消息(ACK_MSG)由信标实体生成以通知线程所请求的信标已获得。在一个实施例中，ACK_MSG包括信标标识符字段和线程标识符字段。ACK_MSG仅由信标实体发出并由执行线程标识符字段所标识的线程的处理核心接收。
[0037] 在接收到ACK_MSG后，接收处理核心复位由线程标识符字段所标识的线程的等待-信标状态字段。如果该线程处于不活动状态，则将线程状态变成活动状态。
[0038] 信标指令
[0039] 获得信标(ACS)指令使得ACQ_MSG消息与所请求信标的信标标识符、请求线程的线程标识符一起被发送到信标实体，其中自动释放字段未被设定。将线程置于不活动状态，其中设定了等待-信标状态字段。ACS指令与释放信标(RLS)指令(以下描述)配对(RLS指令跟在后面)。例如，可使用用于关键段应用的ACS-RLS指令对。
[0040] 具有自动释放指令(ASR)的获得信标使得ACQ_MSG与所请求信标的信标标识符、请求线程的线程标识符一起被发送到信标实体，其中设定了自动释放字段。将该线程置于不活动状态，其中设定了等待-信标状态字段。在一个实施例中，ASR指令不能与RLS指令配对。在一个实施例中，ASR指令被用于仅具有首部相关性的线程。
[0041] 等待信标(WTS)指令使得等待-信标线程状态字段被检查。如果状态字段被设定，则将该线程置于不活动状态。如果状态字段未被设定，则该线程保持于活动状态。不响应于WTS指令将消息发送给信标实体。WTS指令的使用意味着先前由线程分配器使用ACQ_MSG代表该线程在线程分批时间获得信标。如果在线程分配器先前发出的ACQ_MSG中设定了确认-抑制字段，则不使用该WTS指令。
[0042] 释放信标(RLS)指令使得REL_MSG与所释放的信标的信标标识符和释放线程的线程标识符一起被发送给信标实体。释放线程保持于活动状态。如果先前已发出用于释放线程的ACS指令，则仅发出一个RLS指令。如果先前已发出用于释放线程的ASR指令，则不发出RLS指令。如果已发出用于释放线程的WTS指令，则根据由线程分配器发送的ACQ_MSG的自动释放字段，WTS指令之后可以紧接或不紧接RLS指令。如果未设定自动释放字段，则不应发出RLS指令。如果设定了自动释放字段，则RLS指令应紧接WTS指令。
[0043] 活动信标的示例获取
[0044] 图3是用于获取活动信标的技术的一个实施例的事件流程图。图3的示例具备对特定指令、消息、处理组件和数据结构的引用。但是，获取活动信标也可以用其它指令、消息、处理组件和/或数据结构来实现。
[0045] 当指令的线程由一处理核心执行时，在资源可用时执行这些指令。当需要具有一信标的一资源时，例如共亨存储器位置，会需要信标的所有权来访问该资源。因此，在需要信标(310)前，按任何本领域已知的方式实现指令线程的执行。
[0046] 在一个实施例中，当需要信标时(310)，执行获取信标(ACS)指令(320)。ACS指令可由执行请求该信标的指令线程的处理核心执行。作为ACS指令执行的一部分或响应该执行，获取信标消息(ACQ_MSG)由执行该线程的处理核心通过消息总线发送给信标实体(330)。以上描述了ACQ_MSG的一种格式。也可以使用其它格式。
[0047] 作为ACS指令执行的一部分或响应该执行，请求信标的线程被置于不活动状态，其中设定了等待-信标状态字段(340)。通过将该线程置于不活动状态，不执行线程中的指令，它包括在初始信标请求被拒绝的情况下所请求信标的轮询。通过将线程置于不活动状态，等待信标的线程不消耗处理器资源和系统带宽。对于支持多线程的处理核心，处理器资源和系统带宽可由其它活动线程使用。
[0048] 信标实体接收ACQ_MSG并将请求者信息条目置于目标信标的链接列表中(350)。如果该信标不由另一线程所有或控制，则由于没有其它的条目，该信标条目被置于信标链接列表的首部。如果该信标由另一线程所有或控制，则将该信标条目置于信标链接列表的尾部。在一个实施例中，通过将缓冲池中的链接列表条目从首部条目移动到尾部条目来标识链接列表的尾部，并且新条目变成新的尾部条目。在另一实施例中，链接列表的尾部由信标表中所存储的链接列表的尾部指针直接标识。
[0049] 当线程完成了与该信标相对应的资源的使用时，拥有该信标的线程释放该信标的控制，这将在以下更详细地描述。在释放信标时，信标链接列表的首部处的相应信标条目被移除，且链接列表中的后续信标条目变成链接列表的首部。
[0050] 当一信标条目变成信标链接列表的首部时，其状态字段由信标实体检查。如果确认-抑制字段未被设定，则从该信标实体向与该信标条目相关联的线程发送一确认消息(ACK_MSG)(360)。以上描述了用于ACK_MSG的一种格式。也可以使用其它格式。ACK_MSG向接收实体(例如，一线程)指示接收实体已被准许控制相应信标。
[0051] 响应于ACK_MSG，激活相应的线程(370)。当被激活时，线程中指令的处理再继续并可以访问与该信标相对应的共享资源(380)。当该线程已完成对共享资源的访问时，释放该信标，这将在以下更详细地描述。
[0052] 活动信标的释放示例
[0053] 图4是用于释放活动信标的技术的一个实施例的流程图。如同图3的示例，图4的示例具备了对特定指令、消息、处理组件和数据结构的引用。然而，活动信标的释放也可以用其它指令、消息、处理组件和/或数据结构实现。
[0054] 在一个实施例中，当执行释放信标(RLS)指令时释放一信标(410)。RLS指令可由执行请求该信标的指令线程的处理核心执行。作为RLS指令的执行的一部分或响应于该执行，将释放信标消息(REL_MSG)发送给信标实体(420)。以上描述了REL_MSG的一种格式。也可以使用其它格式。
[0055] 响应于该REL_MSG，信标实体使REL_MSG的线程标识符字段与信标链接列表相匹配。信标实体检查相应的信标条目是否处于链接列表的首部(422)。如果相应的信标条目位于链接列表的首部，则信标实体从链接列表的首部中移除该线程条目(430)。链接列表中的后续条目变成首部条目(440)。随后，该信标可被授予与新首部条目相对应的线程。如果相应的信标条目不在链接列表的首部，则信标实体设定信标条目的释放状态字段(424)。
[0056] 结论
[0057] 说明书中对“一个实施例”或“一实施例”的引用表示结合该实施例描述的特殊部件、结构或特征包含在本发明的至少一个实施例中。说明书中各处短语“在一个实施例中”的出现不必都涉及同一实施例。
[0058] 在以上说明书中，已参考其特定实施例描述了本发明，但显然，可对其进行各种修改和变化而不背离本发明的较宽精神和范围。因此，说明书和附图被认为是说明性而非限制性的。
