用于授予对共享资源的访问的增强机制

摘要

提供在包括多个节点的数据处理系统中用于控制对代码的临界区的访问的机制，每个节点是一个计算设备。这些机制通过数据处理系统的发送者节点发送用于请求对代码的临界区的访问的访问请求。代码的临界区是访问共享资源的一部分代码。这些机制在发送者节点中从数据处理系统中的多个接收者节点接收对访问请求的响应。该响应中的每个响应包括由发送响应的对应接收者节点感知到的活动节点的数目。这些机制通过发送者节点基于在从接收者节点接收到的响应中的每个响应中识别出的活动节点的数目来控制对代码的临界区的访问。

说明书

技术领域

本申请总体涉及改进的数据处理装置和方法，并且更具体地涉及用于授予对共享 资源的访问的机制。

背景技术

Ricart-Agrawala算法是用于在分布式系统上的互斥的算法。该算法由Glenn Ricart和AshokAgrawala开发，并且是移除了对释放消息的需要的Lamport的分布式互斥 算法的扩展和优化。利用Ricart-Agrawala算法，当分布式环境中的节点(计算设备)需要进 入临界区——即访问不能同时由其他节点访问的共享资源(例如，数据结构、设备、等等)的 一部分代码——时，节点向它知道的所有其他节点发送指示进入临界区的需要的通知。

响应于接收到通知，如果接收节点不在临界区中，即不访问共享资源，或者将要进 入临界区但是具有比发送者节点更低的优先级值，则接收节点将批准由发送者节点对临界 区的访问的授予。如果接收节点已经在临界区中，即访问共享资源，则接收节点将不批准由 发送者节点对临界区的访问的授予。

在等待时间经过之后，发送者节点确定它是否已经从所有接收节点接收到指示对 临界区的访问的授予的批准的响应消息。如果是的话，发送者节点将进入临界区并且访问 共享资源。如果发送者节点没有获得对临界区的访问的授予的批准，则发送者节点将再次 发出通知并等待响应，基本上重复该尝试以获得对临界区的访问。

发明内容

在一个说明性实施例中，一种在包括多个节点的数据处理系统中用于控制对代码 的临界区的访问的方法，每个节点是一个计算设备。该方法包括由数据处理系统的发送者 节点发送用于请求对代码的临界区的访问的访问请求。代码的临界区是访问共享资源的一 部分代码。该方法还包括由发送者节点从数据处理系统中的多个接收者节点接收对访问请 求的响应。响应中的每个响应包括由发送响应的对应接收者节点感知到的活动节点的数 目。另外，该方法包括由发送者节点基于在从接收者节点接收到的响应中的每个响应中识 别出的活动节点的数目来控制对代码的临界区的访问。

在其他说明性实施例中，提供一种计算机程序产品，其包括具有计算机可读程序 的计算机可用或可读介质。计算机可读程序当在计算设备上运行时使计算设备执行以上关 于方法说明性实施例概述的操作中的各个操作及其组合。

在又一说明性实施例中，提供一种系统/装置。该系统/装置可以包括一个或多个 处理器和耦合到一个或多个处理器的存储器。存储器可以包括指令，当指令由一个或多个 处理器运行时使一个或多个处理器执行以上关于方法说明性实施例概述的操作中的各个 操作及其组合。

本发明的这些和其他特征和优点将在本发明的示例实施例的下面的具体实施方 式中进行描述，或者鉴于在本发明的示例实施例的下面的具体实施方式对本领域普通技术 人员将变得显而易见。

附图说明

本发明以及其优选使用模式和进一步的目标和优点将通过在结合附图阅读时参 考说明性实施例的下面的具体实施方式得到更好地理解。

图1是说明性实施例的各方面可以被实施在其中的分布式数据处理系统的示例 图；

图2是说明性实施例的各方面可以被实施在其中的计算设备的示例方框图；

图3是根据一个说明性实施例的计算设备集群的示例图；

图4是根据一个说明性实施例的临界区访问控制引擎的主要可操作元件的示例方 框图；

图5是根据一个说明性实施例的概述用于在节点到来之后抑制对访问请求的传输 的示例操作的流程图；并且

图6是根据一个说明性实施例的概述用于临界区访问控制的示例操作的流程图。

具体实施方式

如以上所提到的，Ricart-Agrawala算法可以被用于控制对被用于访问共享资源 (例如，数据结构、设备、等等)的代码的临界区的访问。Ricart-Agrawala算法在其中已知多 少节点(计算设备)可操作、节点的该数目保持稳定并且每个节点具有到分布式网络中的每 个其他节点的连接性的网络中效果很好。然而，在其中节点被散布在地理边界上的实际情 形中，例如在云计算等的情况下，这并非总是如此。节点交换心跳消息以感测可能在节点获 得增加的、移除的、丢失的网络连接、获得网络的排斥等时不断地或定期地变化的拓扑结 构。心跳消息实质上向发送心跳消息的节点所连接到的所有节点通知特定节点可操作。接 收节点必须基于这些心跳消息来更新列出可操作节点的它们自己的数据结构以指示接收 节点“看到”的哪些节点为可操作的。如果没有在预定时间段内从节点接收到心跳消息，则 节点可能不被检测作为拓扑结构的部分或者可以被认为是其他节点不可操作的。

感测分布式网络的拓扑结构花费大量时间，例如若干秒。因此，如其当前已知的， Ricart-Agrawala算法在分布式网络中的节点成员关系波动的情况下不能够被实施在分布 式网络中，并且因此，需要对分布式网络拓扑结构的感测。存在引起已知的Ricart- Agrawala算法不能适当地被实施在拓扑结构感测网络中的多种考虑。

第一考虑是在使节点可操作之后多久对临界区的访问能够被请求。也就是说，节 点能够随机地被启动、被重启并被关闭。在重启之后，如果节点发现没有其他可操作的节 点，则可能存在两种可能性：节点是唯一可操作的节点，或者还没有经过足够的时间以交换 心跳消息。因此，节点不应当在启动或重启之后立即请求对代码的临界区的访问。然而，关 于已知的Ricart-Agrawala算法，不存在对在节点的启动或重启之后多久节点能够请求对 代码的临界区的访问的控制。在本文中，访问代码的临界区在本文中与访问共享资源(例如 数据结构、设备、等等)的概念可互换地来使用，因为代码的临界区是被运行以访问共享资 源的一部分代码。

第二考虑是如何确保在剩余节点批准通过请求节点对临界区的访问时访问临界 区是安全的。当节点需要通过访问临界区来获得对共享资源(数据结构、设备、等等)的独占 权利时，可能不能够确定分布式环境中的节点的正确数目。因此，对共享资源的访问可能被 错误地授予。例如，假设存在四个节点A、B、C和D。如果节点A仅仅知道节点B和C，则节点A将 仅向如下节点B和C发送通知或请求，该节点B和C请求节点A关于对临界区的访问的批准。节 点B和C可能不在临界区中，而节点D可能实际上处在代码的临界区中。因此，节点B和C将批 准或授予节点A对临界区或共享资源的访问，并且因此节点A和D可能都同时在临界区中并 且将具有对应当仅仅被顺序访问的对应的共享资源的同时访问。因此，访问通知或请求的 发送者不应当盲目地接受来自接收节点的访问授予响应。

第三考虑是何时节点不应当请求对临界区或共享资源的访问。正常情况下，当节 点或节点集具有节点的分布式网络的不对称视图时，它们将倾向于使它们不可用，即到不 可操作的状态。然而，这不会即时地发生并且因此在节点使其本身不可用的该时间段期间， 节点可能仍然对访问请求做出响应并且发出访问请求。这可能导致类似于以上提到的共享 访问问题，因为具有不对称视图的节点提供不完整响应并将请求发出到不完整的节点集。

说明性实施例提供用于授予对共享资源的访问并且更具体地授予访问轮流访问 共享资源的代码的临界区的机制。说明性实施例提供用于解决以上提到的三种主要考虑的 机制。为了解决以上的针对在启动或重启之前多久访问请求应当被允许由节点发送的第一 考虑，说明性实施例提供用于控制节点的机制，使得如果节点例如通过启动操作、重启操 作、等等变得可操作，则节点确定在网络或节点的集群中是否存在可操作的法定数目的其 他节点(即预定义数目的节点的至少一半或更多)(说明性实施例可以在多个节点的任何集 合上操作并且可以被称为网络、集群、等等)。

当节点的集群被配置时，集群中的节点的数目已知并被通信给集群的节点。集群 的节点交换心跳消息以指示节点在集群内仍然是可操作的。如果没有在预定时间段内从节 点接收到心跳消息，则节点可以被确定为是不可操作的。因此，通过跟踪哪些节点已经发送 心跳信号并将可操作节点的总数目与集群中的节点的预定数目进行比较，可以做出法定数 目的节点是否是可获得的确定。

如果法定数目的节点在当前节点到来时不可获得，则节点必须在请求对代码的临 界区以及因此共享资源的访问之前等待预定延迟超时时间段。延迟超时时间段是取决于特 定实施的可调谐值。延迟超时时间段优选被设置为允许节点活跃并在集群的节点之间交换 心跳消息的时间段。如果法定数目的节点不能够被获得，则在发送者节点本身处拒绝集群 范围的访问，即在发送者节点处抑制对访问通知/请求的发送。

为了解决以上关于确保即使在集群的其他节点批准对临界区的访问时进入临界 区是安全的第二考虑，在说明性实施例中提供用于在集群的节点之间交换指示多少节点在 集群中被每个其他节点感知为可操作的信息的机制。也就是说，当节点启动或被添加到集 群时，节点从“不可用(DOWN)”状态转变为“停滞(DOWNBEAT)”状态，即其中节点能够发出心 跳消息但是尚未变成集群的可操作成员的状态。在DOWNBEAT状态之后，节点转变到“可用 (UP)”状态，在该状态下节点是集群的完全合格的成员。当节点处于DOWNBEAT状态或UP状态 中时，节点能够访问代码的临界区并且因此需要参与集群的访问授予/拒绝功能。注意，在 DOWNBEAT状态或UP状态中的节点被称为“活动”节点，而在DOWN状态中的节点被称为“不活 动”节点。

根据说明性实施例，为了确保发送者节点不仅仅依靠接收者节点的响应授予发送 者节点对临界区或共享资源的访问，在节点对访问通知或请求做出响应时，除了发送指示 请求的访问是否被授予或被拒绝的响应之外，节点还发送它们感知到的在集群中为活动节 点的节点的数目。发送者节点在从集群中的接收节点接收到这样的响应时将由接收节点感 知到的活动节点的数目与由发送者节点感知到的活动节点数目进行比较。如果发送者节点 确定在活动节点的这些数目之间存在差别，则发送者节点将拒绝其本身对临界区或共享资 源的访问，即使接收者节点已经利用对所请求的访问的授予来响应。

例如，使用以上关于节点A、B、C和D的先前示例，假设节点B能够检测到节点D处于 可用状态(例如由于从节点D接收到心跳消息)。还假设节点C和A不具有节点D的可见性，无 论是因为到节点D的连接是不可用的，节点D实际上处于不可用状态中，还是已经发生了使 节点D对节点C和A不可见的一些其他错误。假设节点B和C感知到节点A处于停滞状态中。

在这种情形下，当节点A发出访问通知或请求时，节点B发送响应<3,1,OK>，其中响 应格式具有类型<UP节点的#,DOWNBEAT节点的#,访问授予/拒绝>。类似地，节点C发送响应< 2,1,OK>。活动节点处于UP状态还是DOWNBEAT状态中被指示在由特定节点发出的心跳消息 中。也就是说，心跳信号包含指示UP状态或DOWNBEAT状态的状态指示符值。该信息由接收到 心跳信号的每个其他接收节点存储，使得每个节点具有它们自己的哪些节点UP以及哪些节 点处于DOWNBEAT状态中的相应视图。因此，每个节点能够计算它在集群拓扑结构中感知到 的UP节点的数目和DOWNBEAT节点的数目。

当然，响应的以上格式仅仅是示例并且可以使用其他格式。例如，响应可以代替地 将可用节点的数目和停滞节点的数目分离开，并且可以代替地发送活动节点数目，该数目 是可用节点和停滞节点之和。主要考虑在于由响应节点感知到的处于活动状态中的节点的 数目连同指示响应节点是否授予/拒绝所请求的访问的响应一起返回。

返回到以上示例，节点A将针对每个响应节点的活动的(即处于UP状态和DOWNBEAT 状态中的)节点的数目求和以确定针对该响应节点的对应的活动节点数，除非实施例利用 如以上提到的其中该相加已经完成的响应。在以上示例中，由节点B感知到的活动节点的数 目为4并且对于节点C为3。将由对访问通知/请求做出响应的接收者节点中的每个感知到的 活动节点的这些数目与发送者节点的自己的感知到的活动节点的数目(例如在这种情况下 为(2+1)＝3)进行比较。在该示例中，发送者节点(即节点A)的活动节点数与节点C的活动节 点数相匹配但是不与节点B的活动节点数相匹配。因此，由于不存在由所有节点的集群的一 致视图，所以存在如下可能性：节点A不将其访问通知/请求发送到集群中可能在临界区中 或访问共享资源的节点。因此，节点A拒绝其本身对临界区或共享资源的访问，即使节点B和 C两者都指示对访问的批准。

应当认识到，如果发送者节点感知到比所有响应的接收者节点更大数量的活动节 点，则发送者节点可以授予其本身访问(假设响应中的每个指示对访问的批准)。这是因为 发送者节点比响应的接收者节点具有更大的集群的可见性。例如，节点A的活动数为4并且 节点B和C中的每个利用活动数为3和对访问请求的批准来响应，则节点A可以授予其本身访 问，即使在它的活动数与响应的节点的活动数之间存在差别。

关于以上提到的第三个考虑，即评价在处于UP状态中之后何时节点不应当请求对 临界区的访问，根据说明性实施例，如果节点确定它具有集群的不对称视图，例如它感知为 集群的部分的活动节点的数目与由集群中的其他节点感知到的活动节点的数目不一致，则 节点可以启动计时器。节点可以定期地检查它的集群的视图以确定该不对称视图是否持续 存在。在由计时器测量的时间间隔期间，节点处于脆弱状态中并且应当避免访问临界区和 共享资源。因此，在该时间间隔期间可以抑制对访问通知/请求的发送，直到当节点确定其 不再具有不对称视图的这样的时间为止。因此，在发出访问通知/请求之前，发送者节点可 以检查以查看计时器是否已经开始。如果计时器已经开始，则发送者节点可以拒绝其本身 对临界区/共享资源的访问并抑制对访问通知/请求的发送。另外，节点可以不批准其他节 点的请求并且相反将自动地利用来自集群的其他节点的任何接收到的访问通知/请求的拒 绝来响应。如果不对称视图中止，则可以取消计时器并且可以重新开始节点的正常操作。

因此，说明性实施例提供用于基于来自集群的各个节点的节点的集群的各种感知 到的视图来控制对代码的临界区和共享资源的访问的机制。此外，提供用于控制节点从而 避免关于集群的不对称视图的问题的机制。这些机制包括等待预定延迟时间段以确保心跳 消息能够在集群的节点之间进行交换。该机制还允许对与每个节点的集群中的活动节点的 数目的感知到的视图有关的信息的交换。机制被提供用于允许发送者在合适时执行对临界 区/共享资源的访问的自我拒绝。

本发明的说明性实施例的以上方面和优点将在下文参考附图更详细地进行描述。 应当认识到，附图仅仅旨在说明本发明的说明性实施例。本发明可以包含未明确示出在附 图中但是鉴于说明性实施例的当前描述对本领域普通技术人员将显而易见的各方面、各实 施例和对所描绘的示范性实施例的修改。

所属技术领域的技术人员知道，本发明的各个方面可以实现为系统、方法或计算 机程序产品。因此，本发明的各个方面可以具体实现为以下形式，即：完全的硬件实施方式、 完全的软件实施方式(包括固件、驻留软件、微代码等)，或硬件和软件方面结合的实施方 式，这里可以统称为“电路”、“模块”或“系统”。此外，在一些实施例中，本发明的各个方面还 可以实现为在一个或多个计算机可读介质中的计算机程序产品的形式，该计算机可读介质 中包含计算机可读的程序代码。

可以利用一个或多个计算机可读介质的任何组合。计算机可读介质可以是计算机 可读信号介质或计算机可读存储介质。计算机可读存储介质是具有电子性质、磁性性质、光 学性质、电磁性质、或半导体性质的系统、装置或设备、前面的任何适当的组合、或者其等价 物。计算机可读存储介质的更具体示例(非穷举列表)将包括以下：具有存储能力的电气设 备、便携式计算机磁盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦可编程只读存 储器(EPROM或闪速存储器)、基于光纤的设备、便携式紧凑盘只读存储器(CDROM)、光学存储 设备、磁性存储设备或前面的任何适当的组合。在该文档的上下文中，计算机可读存储介质 是能够包含或存储用于由指令运行系统、装置或设备使用或与指令运行系统、装置或设备 相连的任何有形介质。

在一些说明性实施例中，计算机可读介质是非暂态计算机可读介质。非暂态计算 机可读介质是不为无实体信号或传播波(即纯信号或传播波本身)的任何介质。非暂态计算 机可读介质可以利用信号和传播波，但是本身不是信号或传播波。因此，例如，各种形式的 存储器设备和以例如用于维持其状态的任何方式利用信号的其他类型的系统、设备或装置 可以被认为是在本说明书内的非暂态计算机可读介质。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号， 其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括——但 不限于——电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是 计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者 传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。类似地，计算机可 读存储介质是不为计算机可读信号介质的任何计算机可读介质。

计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括——但不限 于——无线、有线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言的任意组合来编写用于执行本发明操作的计算 机程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、Smalltalk、C++ 等，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可 以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、 部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。 在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN) 或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务 提供商来通过因特网连接)。

下面将参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图 和/或框图描述本发明。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各 方框的组合，都可以由计算机程序指令实现。这些计算机程序指令可以提供给通用计算机、 专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些计算机 程序指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图 和/或框图中的一个或多个方框中规定的功能/动作的装置。

也可以把这些计算机程序指令存储在计算机可读介质中，这些指令使得计算机、 其它可编程数据处理装置、或其他设备以特定方式工作，从而，存储在计算机可读介质中的 指令就产生出包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的指令 的制造品(articleofmanufacture)。

计算机程序指令还可以被加载到计算机、其他可编程数据处理装置或其他设备上 以使一系列操作步骤被执行在计算机、其他可编程数据处理装置或其他设备上以产生计算 机实施的过程使得运行在计算机或其他可编程装置上的指令提供用于实施流程图和/或一 个或多个方框图方框中指定的功能/动作的过程。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程 序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代 表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用 于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标 注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基 本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的 是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规 定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组 合来实现。

因此，说明性实施例可以被利用在许多不同类型的数据处理环境中。为了提供针 对说明性实施例的具体元件和功能的描述的上下文，下文提供图1和图2作为说明性实施例 的各方面可以被实施在其中的示例环境。应当认识到，图1和图2仅仅是示例并且不旨在断 言或暗示关于本发明的各方面或各实施例可以被实施在其中的环境的任何限制。可以在不 脱离本发明的精神和范围的情况下进行对所描绘的环境的许多修改。

图1描绘说明性实施例的各方面可以被实施在其中的示例分布式数据处理系统的 图形表示。分布式数据处理系统100可以包括说明性实施例的各方面可以被实施在其中的 计算机的网络。分布式数据处理系统100包含至少一个网络102，其是被用于提供在一起连 接在分布式数据处理系统100内的各个设备与计算机之间的通信链路的媒介。网络102可以 包括连接，例如电线、无线通信链路或光纤线缆。

在所描绘的示例中，服务器104和服务器106连同存储单元108一起连接到网络 102。另外，客户端110、112和114还连接到网络102。这些客户端110、112和114可以例如为个 人计算机、网络计算机、等等。在所描绘的示例中，服务器104将诸如启动文件、操作系统图 像和应用的数据提供到客户端110、112和114。在所描绘的示例中，客户端110、112和114是 服务器104的客户端。分布式数据处理系统100可以包括额外的服务器、客户端以及未示出 的其他设备。

在所描绘的示例中，分布式数据处理系统100是具有表示使用传输控制协议/互联 网协议(TCP/IP)协议组来彼此通信的全球范围内的网络和网关的汇集的网络102的互联 网。互联网的核心是在包括路由数据和消息的数千的商用计算机系统、政府计算机系统、教 育计算机系统和其他计算机系统的主节点或主机计算机之间的高速数据通信线路的骨干 网。当然，分布式数据处理系统100还可以被实施以包括许多不同类型的网络，例如内联网、 局域网(LAN)、广域网(WAN)等等。如以上所陈述的，图1旨在为示例，而非旨在为针对本发明 的不同实施例的体系结构限制，并且因此，图1中示出的特定元件不应当被认为是关于本发 明的说明性实施例可以被实施在其中的环境的限制。

图2是说明性实施例的各方面可以被实施在其中的示例数据处理系统的方框图。 数据处理系统200是诸如图1的客户端110的计算机的示例，实施针对本发明的说明性实施 例的过程的计算机可用代码或指令可以被定位在该计算机中。

在所描绘的示例中，数据处理系统200采用包括北桥和存储器控制器中心(NB/ MCH)202以及南桥和输入/输出(I/O)控制器中心(SB/ICH)204的中心体系结构。处理单元 206、主存储器208和图形处理器210连接到NB/MCH202。图形处理器210可以通过加速图形 端口(AGP)连接到NB/MCH202。

在所描绘的示例中，局域网(LAN)适配器212连接到SB/ICH204。音频适配器216、键 盘和鼠标适配器220、调制解调器222、只读存储器(ROM)224、硬盘驱动器(HDD)226、CD-ROM 驱动器230、通用串行总线(USB)端口和其他通信端口232以及PCI/PCIe设备234通过总线 238和总线240连接到SB/ICH204。PCI/PCIe设备可以包括例如以太网适配器、扩展卡和针 对笔记本电脑的PC卡。PCI使用卡总线控制器，而PCIe不使用卡总线控制器。ROM224可以例 如是闪速基本输入/输出系统(BIOS)。

HDD226和CD-ROM驱动器230通过总线240连接到SB/ICH204。HDD226和CD-ROM驱 动器230可以使用例如集成驱动电子设备(IDE)或串行高级技术附件(SATA)接口。超级I/O (SIO)设备236可以连接到SB/ICH204。

操作系统运行在处理单元206上。操作系统协调并提供对图2中的数据处理系统200 内的各种部件的控制。作为客户端，操作系统可以是诸如的 商用操作系统。诸如JavaTM编程系统的面向对象编程系统可以结合操作系统运行并提供来 自运行在数据处理系统200上的JavaTM程序或应用的对操作系统的调用。

作为服务器，数据处理系统200可以例如是eServer^TM系统计算机系 统、运行高级交互式执行体的操作系统或操作系统。数据处理系统 200可以是包括处理单元206中的多个处理器的对称微处理器(SMP)系统。备选地，可以采用 单个处理器系统。

针对操作系统的指令、面向对象编程系统和应用或程序位于诸如HDD226的存储 设备上，并且可以被加载到主存储器208中以用于由处理单元206运行。针对本发明的说明 性实施例的过程可以由处理单元206使用计算机可用程序代码来执行，计算机可用程序代 码可以例如位于诸如主存储器208、ROM224的存储器中或一个或多个外围设备226和230 中。

如图2中示出的总线238和总线240的总线系统可以包括一个或多个总线。当然，总 线系统可以使用提供在附接到结构或体系结构的不同部件或设备之间的数据的传输的任 何类型的通信结构或体系结构来实施。诸如图2的调制解调器222或网络适配器212的通信 单元可以包括用于发送和接收数据的一个或多个设备。存储器可以例如是主存储器208、 ROM224或诸如图2中的NB/MCH202中找到的缓冲。

本领域普通技术人员将认识到图1和2中的硬件可以取决于实施方式而变化。除了 或代替图1和2中描绘的硬件，可以使用诸如闪速存储器、等价的非易失性存储器或光盘驱 动器、等等的其他内部硬件或外围设备。而且，在不脱离本发明的精神和范围的情况下，除 了先前提到的SMP系统，说明性实施例的过程可以被应用到多处理器数据处理系统。

此外，数据处理系统200可以采取包括客户端计算设备、服务器计算设备、平板电 脑计算机、膝上型计算机、电话或其他通信设备、个人数字助理(PDA)等等的许多不同的数 据处理系统中的任何的形式。在一些说明性示例中，数据处理系统200可以例如是被配置具 有闪速存储器以提供用于存储操作系统文件和/或用户生成的数据的非易失性存储器的便 携式计算设备。实质上，数据处理系统200可以是没有体系结构限制的任何已知的或稍后开 发的数据处理系统。

再次参考图1，服务器104、106、客户端计算设备110-114等等可以是通过运行代码 的临界区访问共享资源的多个计算设备的集合的部分。该多个计算设备的集合可以被称为 计算设备的网络、计算设备的集群等等，并且优选地具有在彼此之间的通信连接使得它们 可以交换控制和数据消息。出于当前描述的目的，将假设服务器104、106和其他服务器(未 示出)被配置为用于服务经由网络102来自客户端计算设备110-114的请求的服务器的集 群。因此，服务器104、106以及集群的其他服务器被配置为实施说明性实施例的机制和功 能。服务器104、106可以例如是例如在图2中描述的数据处理系统。

图3是根据一个说明性实施例的计算设备的集群的示例图。图3中的集群300是包 括仅仅四个节点A-D310-316的节点的简化集群，但是应当认识到集群300实际上可以包括 比本文描绘的多得多的节点，成百上千个节点可以是服务器计算设备、客户端计算设备或 其他类型的计算设备的节点优选地具有用于在它们之间通信控制和数据消息的通信连接。 节点310-316还利用本文描述的并且例如图4中描绘的说明性实施例的临界区访问控制机 制来配置。

在所描绘的示例中，节点A310知道仅仅节点B312和C314并且不能够感知到节 点D316为集群300的成员。因此，节点A310将请求对节点A对临界区或共享资源的访问的 批准的访问通知或请求仅仅发送到节点B312和节点C314。节点B312和节点C314可能不 在临界区中而节点D316可能实际上处在代码的临界区中。因此，节点B312和节点C314将 批准或授予节点A对临界区或共享资源的访问，并且因此节点A310和节点D316可能都同 时在临界区中并且将具有对对应的共享资源的同时访问。这可能在共享资源被预期为要通 过集群的节点以顺序的方式(例如节点必须获得关于共享资源的锁并且具有在执行关于共 享资源的操作时的独占访问)来访问时导致数据损坏问题。

为了实施说明性实施例的机制，集群的节点(例如出于说明性目的节点A310)在 UP状态之后实施法定数目抑制器，法定数目抑制器在确定在集群300中不存在法定数目的 节点时使节点抑制对访问通知/请求的发送。也就是说，响应于在集群300中节点被转变到 UP状态，例如在启动节点、重启节点、将节点添加到集群、等等之后，节点确定其是否已经从 集群300中的其他节点接收到心跳消息，使得其知道在集群300中存在法定数目的节点并且 法定数目的节点处于活动状态中，例如处于UP或DOWNBEAT状态中。节点310-316先验地被配 置具有指示集群300中的节点的总数目的信息，使得能够确定法定数目。法定数目可以被认 为是集群300的节点的至少一半、集群300中的节点的四分之三、或者集群300中的节点的任 何其他期望的预定数目。在一个示例中，节点A310在启动之后可以检查以确定在图3中示 出的集群300中是否有至少三个节点处于活动状态中。

如果法定数目的节点是不活动的，则节点可以启动计时器以测量在集群300中使 节点进入UP状态之后的预定延迟时间段。预定延迟时间必须在节点再次被允许请求对代码 的临界区以及因此对共享资源的访问之前到期。延迟时间段是如以上先前提到的可调谐 值。在该预定延迟时间段期间，在发送者节点本身处拒绝集群范围访问，即在发送者节点处 抑制对访问通知/请求的发送。在该预定延迟时间段已经到期之后，节点可以假设其是在集 群中UP的唯一节点并且以对临界区的访问前进。备选地，该过程可以在法定数目不再能够 被实现时被重复。如果法定数目在预定数量的尝试(例如对延迟计时器的重置)内没有被实 现，则错误通知可以被发送到系统管理员工作者或其他类型的通知可以被生成以联系合适 的人员来矫正该错误，或者节点可以假设其是集群中处于UP状态中的唯一节点并且以对临 界区的访问前进。

除了在UP状态引擎之后的法定数目抑制器，说明性实施例还实施集群视图交换机 制和访问的自我拒绝机制。集群视图交换机制辅助确保即使在集群的其他节点批准对临界 区的访问时，对于节点而言进入代码的临界区并且因此访问要求顺序访问的访问共享资源 是安全的。集群视图交换机制被提供在集群的每个节点中并且用于在节点与集群中的其他 节点之间交换指示节点将集群中的多少其他节点感知为可操作(即，处于活动状态中(无论 是UP还是DOWNBEAT状态中)的信息。

根据说明性实施例，为了确保发送者节点不仅仅依靠接收者节点的响应授予发送 者节点对临界区或共享资源的访问，在节点对访问通知或请求做出响应时，除了发送指示 请求的访问是否被授予或被拒绝的响应之外，集群视图交换机制维持当前节点能够感知为 处于活动状态中的什么其他节点的注册表。该信息被插入到由集群视图交换机制对访问通 知/请求的响应中并且得到的响应被发送回到发送者节点。因此，在图3的示例中，如以上所 讨论的，响应于来自节点A的访问通知/请求，节点B发送响应<3,1,OK>，该响应指示UP节点 的数目为3(例如，节点B、C和D)、DOWNBEAT节点的数目为1(例如，节点A)、以及访问被授予或 “OK”。类似地，节点C发送响应<2,1,OK>，该响应指示2个UP节点(例如，节点B和节点C)、1个 DOWNBEAT节点(例如，节点A)、以及访问被授予或“OK”。

当从集群中的接收节点接收到这样的响应时，发送者节点将由接收节点感知到的 活动节点的数目与由发送者节点感知到的活动节点的数目进行比较。如果发送者节点确定 在活动节点的这些数目之间存在差别，则发送者节点将拒绝其本身对临界区或共享资源的 访问，即使接收者节点已经利用对所请求的访问的授予来响应。因此，例如，节点A将对于每 个响应的节点活动的节点的数目求和，来确定针对该响应的节点的对应活动节点数，其中 结果是由节点B感知到的活动节点的数目为4并且对于节点C为3。将活动节点的这些数目与 发送者节点的自己的感知到的活动节点数目(例如，在这种情况下为3)进行比较。在该示例 中，发送者节点(即节点A)的活动节点数与节点C的活动节点数相匹配，但是不与节点B的活 动节点数相匹配。因此，由于不存在由所有节点的集群的一致视图，所以存在如下可能性： 节点A不将其访问通知/请求发送到集群中可能在临界区中或访问共享资源的节点。因此， 节点A的访问的自我拒绝机制拒绝其本身对临界区或共享资源的访问，即使节点B和C两者 都指示对访问的批准。如先前提到的，应当认识到，如果发送者节点感知到比所有响应的接 收者节点更大数量的活动节点，则发送者节点的访问的自我拒绝机制可以授予其本身访问 而非执行访问的自我拒绝，因为发送者节点比响应的接收者节点具有更大的集群的可见 性。

除了以上机制之外，说明性实施例还在集群的节点中提供用于启动计时器以抑制 对访问通知/请求的传输和对其他节点的访问通知/请求的肯定响应的不对称视图计时器 机制。也就是说，如果节点确定它具有集群的不对称视图，例如它感知为集群的部分的活动 节点的数目与由集群中的其他节点感知到的活动节点的数目不一致，则节点可以经由节点 的不对称视图计时器机制启动不对称视图计时器。节点的不对称视图计时器机制定期地检 查它的集群的视图以确定该不对称视图是否持续存在。在由计时器测量的时间间隔期间， 节点处于脆弱状态中并且应当避免访问临界区和共享资源。因此，在该时间间隔期间抑制 对访问通知/请求的发送，直到当节点确定其不再具有不对称视图的这样的时间或直到计 时器过期。因此，在发出访问通知/请求之前，发送者节点可以检查以查看计时器是否已经 开始。如果计时器已经开始，则发送者节点可以拒绝其本身对临界区/共享资源的访问并抑 制对访问通知/请求的发送。另外，节点可以不批准其他节点的请求并且相反将自动地利用 来自集群的其他节点的任何接收到的访问通知/请求的拒绝来响应。如果不对称视图中止， 则可以取消计时器并且可以重新开始节点的正常操作。

图4是根据一个说明性实施例的临界区访问控制引擎的主要操作元件的示例方框 图。元件可以被实施在节点的网络(例如，集群、互联网、等等)的一个或多个节点(例如，计 算设备、处理器、数据处理系统、等等)中。在一个说明性实施例中，网络是节点的集群，其中 集群中的每个节点实施它自己的临界区访问控制引擎的本地版本。临界区访问控制引擎的 元件可以以由计算设备的一个或多个处理器运行的软件、硬件或软件和硬件的任何组合来 实施。在一个说明性实施例中，图4中的元件被实施为运行在网络的节点的一个或多个处理 器上的软件指令。

如图4所示，临界区访问控制引擎400包括控制器410、接口420、法定数目抑制器 430、集群视图交换引擎440、集群视图数据结构450、访问的自我拒绝引擎460和不对称视图 计时器引擎470。控制器410控制临界区访问控制引擎400的总体操作并安排临界区访问控 制引擎400的其他元件的操作。接口420提供通信通道，通过其数据和控制消息可以在节点 与(集群)网络的其他节点之间传递。

法定数目抑制器430执行以上描述的关于确定法定数目的其他节点是否是活动的 操作。法定数目抑制器430还操作以在预定延迟时间段期间抑制对访问通知/请求的发送。

集群视图交换引擎440执行以上先前描述的用于将活动节点信息插入到对来自集 群中的另外的节点对访问通知/请求的响应中的操作。被用于将活动节点信息插入到响应 中的信息可以从将节点的当前视图存储在集群视图数据结构450中来获得。存储在集群视 图数据结构450中的信息根据从集群中的其他节点接收到的心跳消息来生成。心跳消息指 示在集群中哪些节点是活动的以及这些节点是否处于UP状态或DOWNBEAT状态中。节点从当 前节点能够在集群中感知到的其他节点接收心跳消息。

访问的自我拒绝引擎460执行以上描述的自我拒绝操作，该自我拒绝操作用于响 应于其他节点对与当前节点自身对于集群中的活动节点的视图不同的活动节点信息做出 响应，而自我拒绝节点的自己的访问通知/请求。然而，如果当前节点的集群的视图包括比 其他节点能够感知到的更多的活动节点，则访问的自我拒绝引擎460可以准许访问而非自 我拒绝访问。

不对称视图计时器引擎470执行以上描述的操作，该操作用于在其确定节点具有 集群的不对称视图时，启动计时器以抑制对访问通知/请求的传输和对其他节点的访问通 知/请求的肯定响应。对访问通知/请求的传输和肯定响应的抑制在由计时器测量的时间段 上继续。不对称视图计时器引擎470定期地检查其集群的视图以确定该不对称视图是否持 续存在，并且在不对称视图不再持续存在的情况下取消计时器。

图5是根据一个说明性实施例的概述用于在节点到来之后抑制对访问请求的传输 的示例操作的流程图。如图5所示，操作通过节点进入UP状态，例如在启动操作、重启操作或 用于将节点添加到集群的其他操作之后开始(步骤510)。节点确定在集群中是否存在处于 操作的活动状态中的法定数目的其他节点(步骤520)。如果存在处于活动状态中的法定数 目的节点，则准许访问请求传输(步骤530)。如果不存在处于活动状态中的法定数目的节 点，则启动延迟计时器(步骤540)并且在计时器计数预定时间间隔时抑制对访问请求的传 输(步骤550)。做出关于计时器是否已经超时(例如达到最小值或最大值)的确定(步骤 560)。如果计时器已经超时，则准许对访问请求的传输(步骤530)。继而操作结束。

图6是根据一个说明性实施例的概述用于临界区访问控制的示例操作的流程图。 操作通过确定由当前节点可视的集群的节点而开始(步骤610)。由当前节点可视的节点根 据集群视图数据结构来确定，集群视图数据结构被填充有来自从集群中的其他节点接收到 的心跳消息的信息。

当前节点将访问请求发出到由当前节点可视的集群的节点(步骤620)并且当前节 点等待来自其他节点的响应(步骤630)。编译来自接收到的响应的活动节点信息(步骤635) 并且将每个其他节点的在集群中看到的活动节点的指示与由当前节点可视的活动节点数 目进行比较(步骤640)。做出关于在由当前节点可视的活动节点数目与由其他节点可视的 活动节点的数目之间是否存在差别的确定(步骤650)。如果否，则做出关于其他节点中的任 何节点是否已经响应访问被拒绝的确定(步骤660)。如果是，则拒绝访问请求并且抑制对临 界区的访问(步骤670)。如果其他节点中的节点已经响应访问被拒绝，则准许对临界区的访 问并且当前节点访问临界区(步骤680)。

如果在步骤650中存在差别，则做出关于区别是否指示当前节点是否比集群中的 一个或多个其他节点具有更小数目的可视节点的确定(步骤690)。如果否，则操作前进到步 骤660。如果当前节点比集群中的一个或多个其他节点具有更小数目的可视节点，则启动不 对称视图计时器(步骤700)。做出关于不对称视图是否已经终止或不对称视图计时器是否 已经到期的确定(步骤710)。如果任一情况已经发生，则操作返回到步骤690。

应当认识到，尽管图6图示了关于步骤710的循环操作和到步骤690的返回，但是在 其他说明性实施例中，不必循环回并重复地检查节点的集群的视图以确定是否存在不对称 视图，相反，节点可以简单地关闭其操作并定期地检查其集群的视图以确定不对称视图是 否持续存在。如果不对称视图中止，则节点可以再次开始其发出对共享资源访问的请求的 正常操作。

因此，说明性实施例提供用于授予对共享资源的访问的机制并且更具体地提供用 于访问轮流访问共享资源的代码的临界区的机制。说明性实施例提供用于解决以上提到的 关于以下三个主要考虑的机制：在节点到来之后多久访问请求应当被允许被发送、确定对 于节点而言即使在其他节点指示对临界区的这样的访问的批准时进入临界区是否是安全 的、以及确定何时节点不应当请求对临界区的访问。说明性实施例在这三个方面扩展 Ricart-Agarwala算法。

如以上所指出的，应当认识到说明性实施例可以采取完全硬件实施例、完全软件 实施例或包含硬件元件和软件元件两者的实施例的形式。在一个示例实施例中，以软件或 程序代码来实施说明性实施例的机制，软件或程序代码包括但不限于固件、驻留软件、微代 码、等等。

适合于存储和/或运行程序代码的数据处理系统将包括直接地或通过系统总线间 接地耦合到存储器元件的至少一个处理器。存储器元件能够包括在程序代码的实际运行期 间采用的本地存储器、大容量存储装置、以及提供至少一些程序代码的临时存储以便减少 在运行期间必须从大容量存储装置检索代码的次数的缓存存储器。

输入/输出或I/O设备(包括但不限于键盘、显示器、指点设备、等等)能够直接地或 通过中介I/O控制器耦合到系统。网络适配器还可以耦合到系统以使得数据处理系统能够 变成通过中介私有或公共网络耦合到其他数据处理系统或远程打印机或存储设备。调制调 解器、线缆调制解调器和以太网卡仅仅是几个当前可用类型的网络适配器。

对本发明的描述已经出于说明和描述的目的被呈现，并且不旨在为穷举的或将本 发明限于所公开的形式。许多修改和变型对于本领域普通技术人员而言将是显而易见的。 实施例被选择并被描述以便最好地解释本发明的原理、实际应用，并且以便使得本领域其 他技术人员理解本发明用于具有如适于预见到的特定用途的各种修改的各种实施例。