Enhanced mechanisms for granting access to shared resources

Mechanisms are provided, in a data processing system comprising a plurality of nodes, each node being a computing device, for controlling access to a critical section of code. These mechanisms send, by a sender node of the data processing system, an access request for requesting access to the critical section of code. The critical section of code is a portion of code that accesses a shared resource. The mechanisms receive, in the sender node, from a plurality of receiver nodes in the data processing system, responses to the access request. Each response in the responses includes a number of active nodes perceived by a corresponding receiver node that transmitted the response. The mechanisms control, by the sender node, access to the critical section of code based on the number of active nodes identified in each of the responses received from the receiver nodes.

BACKGROUND

The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for granting access to shared resources.

The Ricart-Agrawala algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm was developed by Glenn Ricart and Ashok Agrawala, and is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm which removes the need for release messages. With the Ricart-Agrawala algorithm, when a node (computing device) in a distributed environment needs to enter a critical section, i.e. a portion of code that accesses a shared resource (e.g., a data structure, device, or the like) that must not be concurrently accessed by other nodes, the node sends a notification to all the other nodes of which it is aware indicating the need to enter the critical section.

In response to receiving the notification, the receiving nodes, if not in the critical section, i.e. not accessing the shared resource, or is about to enter the critical section but has a lower priority value than the sender node, will approve the grant of access to the critical section by the sender node. If the receiving node is already in the critical section, i.e. accessing the shared resource, the receiving node will not approve the grant of access to the critical section by the sender node.

After the lapse of a wait time, the sender node determines if it has received response messages from all of the receiving nodes indicating approval of the grant of the access to the critical section. If so, the sender node will enter the critical section and access the shared resource. If the sender node does not get approval of the grant of access to the critical section, the sender node will again send out the notification and await responses, basically repeating the attempt to obtain access to the critical section.

SUMMARY

In one illustrative embodiment, a method, in a data processing system comprising a plurality of nodes, each node being a computing device, for controlling access to a critical section of code. The method comprises sending, by a sender node of the data processing system, an access request for requesting access to the critical section of code. The critical section of code is a portion of code that accesses a shared resource. The method further comprises receiving, by the sender node, from a plurality of receiver nodes in the data processing system, responses to the access request. Each response in the responses includes a number of active nodes perceived by a corresponding receiver node that transmitted the response. In addition, the method comprises controlling, by the sender node, access to the critical section of code based on the number of active nodes identified in each of the responses received from the receiver nodes.

DETAILED DESCRIPTION

As mentioned above, the Ricart-Agrawala algorithm may be used to control access to critical sections of code that are used to access a shared resource, e.g., data structure, device, or the like. The Ricart-Agrawala algorithm works well in networks where it is known how many nodes (computing devices) are operational, this number of nodes remains steady, and each node has connectivity to each other node in the distributed network. In a practical situation, however, where nodes are scattered over geographical boundaries, such as in the case of cloud computing or the like, this is not always the case. Nodes exchange heart beat messages to sense the topology which may be constantly or periodically changing as nodes get added, removed, lose network connection, get expelled from the network, or the like. The heart beat messages essentially inform all of the nodes, to which a node transmitting the heart beat message is connected, that a particular node is operational. The receiving nodes must updating their own data structures listing the operational nodes based on these heart beat message to indicate which nodes the receiving nodes “sees” as being operational. If a heart beat message is not received from a node within a predetermined period of time, the node may either not be detected as being part of the topology or may be considered to not be operational by the other nodes.

Sensing the topology of the distributed network takes a significant amount of time, e.g., several seconds. As a result, the Ricart-Agrawala algorithm, as it is currently known, cannot be implemented in distributed networks where nodal membership in the distributed network fluctuates and as a result, the sensing of the distributed network topology is needed. There are a number of considerations that cause the known Ricart-Agrawala algorithm to not be adequately implemented in topology sensing networks.

A first consideration is how soon an access to a critical section can be requested after a node is made operational. That is, a node can be randomly booted, rebooted, and shutdown. After a reboot, if a node finds no other node operational, there may be two possibilities: either the node is the only node that is operational, or enough time has not lapsed to exchange heart beat messages. Hence a node should not request access to a critical section of code immediately after boot or reboot. However, with the known Ricart-Agrawala algorithm, there are no controls over how soon after boot or reboot of a node, the node can request access to a critical section of code. Herein, accessing a critical section of code is used herein interchangeably with the concept of accessing a shared resource, such as a data structure, device, or the like, since the critical section of code is a portion of code executed to access a shared resource.

A second consideration is how to ensure that it is safe to access a critical section when the rest of the nodes approve of the access by the requesting node to the critical section. When a node needs to gain an exclusive right to a shared resource (data structure, device, or the like) by accessing a critical section, it may not be possible to ascertain the right number of nodes in the distributed environment. As a result, access to the shared resource may be granted erroneously. For example, suppose there are four nodes A, B, C, and D. If node A is aware of only nodes B and C, then node A will send notifications, or requests, to only nodes B and C requesting approval of node A's access to the critical section and thus, the shared resource. Nodes B and C may not be in a critical section while node D may actually be in the critical section of code. Thus, nodes B and C would approve, or grant, node A's access to the critical section and thus, the shared resource, and as a result, nodes A and D would both be in the critical section simultaneously and would have simultaneous access to the corresponding shared resource which should only be accessed sequentially. Thus, a sender of an access notification or request should not blindly accept access granted responses from receiving nodes.

A third consideration is when a node should not request access to a critical section or shared resource. Normally, when a node or a set of nodes has an asymmetric view of the distributed network of nodes, they will tend to bring themselves down, i.e. to an inoperable state. This, however, does not happen instantaneously and therefore, during this period of time when the node is bringing itself down, the node may still respond to access requests and send out access requests. This may cause shared access problems similar to that noted above since a node with an asymmetric view is providing incomplete responses and sending out requests to an incomplete set of nodes.

The illustrative embodiments provide mechanisms for granting access to shared resources and more specifically to accessing a critical section of code that in turn accesses a shared resource. The illustrative embodiments provide mechanisms for addressing the three main considerations noted above. In order to address the first consideration above directed to how soon an access request should be allowed to be sent by a node after boot or reboot, the illustrative embodiments provide mechanisms for controlling a node such that if a node becomes operational, such as through a boot operation, reboot operation, or the like, the node determines if there is a quorum of other nodes (i.e. at least half or more of a predefined number of nodes) operational in the network or cluster of nodes (the illustrative embodiments may operate on any set of a plurality of nodes and may be referred to as a network, a cluster, or the like).

When the cluster of nodes is configured, a number of nodes in the cluster is known and communicated to the nodes of the cluster. The nodes of the cluster exchange heartbeat messages to indicate that the nodes are still operational within the cluster. If a heartbeat message is not received from a node within a predetermined period of time, the node may be determined to be non-operational. Thus, by tracking which nodes have sent heartbeat signals and compare the total number of operational nodes to the predetermined number of nodes in the cluster, a determination may be made as to whether a quorum of nodes is available.

If a quorum of nodes is not available when the current node comes up, then the node has to wait for a predetermined delay timeout period before requesting access to the critical section of code, and thus, the shared resource. The delay timeout period is a tunable value that is dependent upon the particular implementation. The delay timeout period is preferably set to a period of time to allow nodes to be brought up and heartbeat messages to be exchanged between the nodes of the cluster. If a quorum of nodes is not able to be obtained, then cluster-wide access is denied at the sender node itself, i.e. the sending of access notifications/requests is inhibited at the sender node.

To address the second consideration above with regard to ensuring that it is safe to enter a critical section even when the other nodes of the cluster approve the access to the critical section, mechanisms are provided in the illustrative embodiment to exchange information between the nodes of the cluster indicating how many nodes each other node perceives as being operational in the cluster. That is, when a node boots up or is added to a cluster, the node transitions from a “DOWN” state to a “DOWNBEAT” state, i.e. a state where the node is capable of sending out heartbeat messages but has not yet become an operational member of the cluster. After the DOWNBEAT state, the node transitions to an “UP” state where the node is a fully qualified member of the cluster. Whether a node is in a DOWNBEAT state or an UP state, the node is capable of accessing critical sections of code and hence needs to participate in the access grant/denial functionality of the cluster. Nodes that are in a DOWNBEAT state or UP state are referred to as “active” nodes, whereas nodes that are in a DOWN state are referred to as “inactive” nodes.

In accordance with the illustrative embodiments, to ensure that a sender node does not rely just on the receiver nodes' responses granting the sender node's requested access to the critical section or shared resource, when nodes respond to an access notification or request, in addition to sending the response indicating whether the access requested is granted or denied, the nodes also send the number of nodes they perceive to be active nodes in the cluster. The sender node, when receiving such responses from the receiving nodes in the cluster, compares the number of active nodes perceived by the receiving nodes to the number of active nodes perceived by the sender node. If the sender node determines that there is a discrepancy between these numbers of active nodes, then the sender node will deny itself access to the critical section or shared resource even though the receiver nodes have responded with a grant of the requested access.

For example, using the previous example above with nodes A, B, C, and13, assume that node B is able to detect that node D is in an up state (such as due to receipt of a heartbeat message from node D). Also assume that nodes C and A do not have visibility of node D, either because a connection to node D is down, node D is actually in a down state, or some other error has occurred making node D not visible to nodes C and A. Assume that nodes B and C perceive node A to be in a downbeat state.

In this scenario, when node A sends out an access notification or request, node B sends the response <3, 1, OK>, where the response format is of the type <# of UP nodes, # of DOWNBEAT nodes, access grant/deny>. Similarly, node C sends a response of <2, 1, OK>. Whether an active node is in an UP state or DOWNBEAT state is indicated in the heartbeat messages being sent out by the specific not. That is, the heartbeat signal contains a state indicator value that indicates either an UP state or a DOWNBEAT state. This information is stored by each other receiving node that receives the heartbeat signal so that each node has their own respective view of which nodes are UP and which nodes are in a DOWNBEAT state. As such, each node is able to calculate the number of UP nodes and number of DOWNBEAT nodes it perceives in the cluster topology.

Of course the above format of the response is only an example and other formats may be used. For example, a response may instead of separating out the number of up nodes and number of downbeat nodes, may instead send an active node number which is a sum of the up nodes and downbeat nodes. The main consideration is that the number of nodes perceived by the responding node to be in an active state is returned along with the response indicating whether the responding node grants/denies the requested access.

Returning to the example above, node A sums the number of nodes that are active, i.e. in an UP state and DOWNBEAT state, for each responding node to determine a corresponding active node count for that responding node, unless the embodiment utilizes a response in which this summation has already been done, as noted above. In the above example, the number of active nodes perceived by node B is 4 and for node C is 3. These numbers of active nodes perceived by each of the receiver nodes responding to the access notification/request is compared to the sender node's own perceived number of active nodes, e.g., (2+1)=3 in this case. In this example, the sender node, i.e. node A, active node count matches with node C's active node count but does not match node B's active node count. As a result, since there is not a consistent view of the cluster by all of the nodes, there is the possibility that node A did not send its access notification/request to a node in the cluster that may be in the critical section or accessing the shared resource. Thus, node A denies itself access to the critical section or shared resource even though both nodes B and C indicated approval of the access.

It should be appreciated that if the sender node perceives a larger number of active nodes than all of the responding receiver nodes, then the sender node may grant itself access (assuming that each of the responses indicates approval of the access). This is because the sender node has a larger visibility of the cluster than the responding receiver nodes. For example, if node A's active count is 4 and each of nodes B and C respond with active counts of 3 and approval of the access request, then node A may granted itself access even though there is a discrepancy between its active count and the active count of the responding nodes.

With regard to the third consideration mentioned above, i.e. evaluating when a node should not request access to a critical section after in an UP state, in accordance with the illustrative embodiments, if a node determines that it has an asymmetric view of the cluster, e.g., its number of active nodes is inconsistent with the number of active nodes perceived by other nodes in the cluster, the node may initiate a timer. The node may periodically check its view of the cluster to determine if this asymmetric view persists. During the time interval measured by the timer, the node is in a vulnerable state and should avoid accessing critical sections and shared resources. Thus, sending of access notifications/requests may be inhibited during this time interval until such time as the node determines that it no longer has an asymmetric view. Thus, prior to sending out an access notification/request, the sender node may check to see if the timer has been started. If the timer has been started, the sender node may deny itself access to the critical section/shared resource and inhibit the sending of access notifications/requests. In addition, the node may not approve other node's requests and instead will automatically respond with a denial of any received access notification/request from other nodes of the cluster. If the asymmetric view discontinues, the timer may be canceled and normal operation of the node may be resumed.

Thus, the illustrative embodiments provide mechanisms for controlling access to critical sections of code and shared resources based on the various perceived views of the cluster of nodes from the various nodes of the cluster. Moreover, mechanisms are provided for controlling nodes so as to avoid issues with asymmetric views of a cluster. These mechanisms include waiting a predetermined delay time period for ensuring that heartbeat messages are able to be exchanged between nodes of a cluster. The mechanisms further allow for the exchange of information about each node's perceived view of the number of active nodes in the cluster. Mechanisms are provided for allowing the sender to perform self-denial of access to a critical section/shared resource when appropriate.

The above aspects and advantages of the illustrative embodiments of the present invention will be described in greater detail hereafter with reference to the accompanying figures. It should be appreciated that the figures are only intended to be illustrative of exemplary embodiments of the present invention. The present invention may encompass aspects, embodiments, and modifications to the depicted exemplary embodiments not explicitly shown in the figures but would be readily apparent to those of ordinary skill in the art in view of the present description of the illustrative embodiments.

Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium is a system, apparatus, or device of an electronic, magnetic, optical, electromagnetic, or semiconductor nature, any suitable combination of the foregoing, or equivalents thereof. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical device having a storage capability, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber based device, a portable compact disc read-only memory (CDROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium is any tangible medium that can contain or store a program for use by, or in connection with, an instruction execution system, apparatus, or device.

In some illustrative embodiments, the computer readable medium is a non-transitory computer readable medium. A non-transitory computer readable medium is any medium that is not a disembodied signal or propagation wave, i.e. pure signal or propagation wave per se. A non-transitory computer readable medium may utilize signals and propagation waves, but is not the signal or propagation wave itself. Thus, for example, various forms of memory devices, and other types of systems, devices, or apparatus, that utilize signals in any way, such as, for example, to maintain their state, may be considered to be non-transitory computer readable media within the scope of the present description.

As a server, data processing system200may be, for example, an IBM® eServer™ System p® computer system, running the Advanced Interactive Executive (AIX®) operating system or the LINUX® operating system. Data processing system200may be a symmetric multiprocessor (SMP) system including a plurality of processors in processing unit206. Alternatively, a single processor system may be employed.

With reference again toFIG. 1, the servers104,106, client computing devices110-114, or the like may be part of a set of a plurality of computing devices that access shared resources by executing critical sections of code. This set of a plurality of computing devices may be referred to as a network of computing devices, a cluster of computing devices, or the like, and preferably have communication connections between each other such that they may exchange control and data messages. For purposes of this description, it will be assumed that the servers104,106, and other servers (not shown) are configured to be a cluster of servers for servicing requests from client computing devices110-114via the network102. Thus, the servers104,106, as well as other servers of the cluster, are configured to implement the mechanisms and functionality of the illustrative embodiments. The servers104,106may be data processing systems such as described inFIG. 2, for example.

FIG. 3is an example diagram of a cluster of computing devices in accordance with one illustrative embodiment. The cluster300inFIG. 3is a simplified cluster of nodes comprising only four nodes A-D310-316but it should be appreciated that the cluster300, in actuality, may comprise many more nodes than that depicted here, hundreds or even thousands of nodes. The nodes, which may be server computing devices, client computing devices, or other types of computing devices, preferably have communication connections for communicating control and data messages between them. The nodes310-316are further configured with the critical section access control mechanisms of the illustrative embodiments described herein and depicted, for example, inFIG. 4.

In the depicted example, node A310is aware of only nodes B312and C314and cannot perceive the node D316as being a member of the cluster300. Thus, node A310will send access notifications or requests to only nodes B312and C314requesting approval of node A's access to the critical section or shared resource. Nodes B312and C314may not be in a critical section while node D316may actually be in the critical section of code. Thus, nodes B312and C314would approve, or grant, node A's access to the critical section or shared resource, and as a result, nodes A310and D316may both be in the critical section simultaneously and would have simultaneous access to the corresponding shared resource. This may lead to data corruption issues when the shared resource is expected to be accessed in a serial manner by nodes of the cluster, e.g., a node must obtain a lock on the shared resources and have exclusive access while performing operations with regard to the shared resource.

In order to implement the mechanisms of the illustrative embodiments, the nodes of the cluster, e.g., node A310for illustrative purposes, implements a quorum inhibitor following UP status that causes the node to inhibit the sending of access notifications/requests when it is determined that a quorum of nodes is not present in the cluster300. That is, in response to a node being transitioned to an UP state in the cluster300, e.g., after booting, re-boot, adding of the node to the cluster, or the like, the node determines if it has received heartbeat messages from other nodes in the cluster300such that it knows that a quorum of nodes are present and in an active state in the cluster300, e.g., in an UP or DOWNBEAT state. The nodes310-316are configured a priori with information indicating the total number of nodes in the cluster300such that a quorum can be determined. The quorum may be considered to be at least half of the nodes of the cluster300, three-quarters of the nodes in the cluster300, or any other desired predetermined number of nodes in the cluster300. In one example, node A310, upon booting, may check to determine if at least three nodes are in an active state in the cluster300shown inFIG. 3.

If quorum of nodes is not active, then the node may initiate a timer to measure a predetermined delay time period following the node being brought to an up state in the cluster300. The predetermined delay time must expire before the node is once again allowed to request access to the critical section of code, and thus, the shared resource. The delay time period is a tunable value as previously mentioned above. During this predetermined delay time period, cluster-wide access is denied at the sender node itself, i.e. the sending of access notifications/requests is inhibited at the sender node. After this predetermined delay time period has expired a node may assume it is the only node UP in the cluster and go ahead with access to the critical section. Alternatively, this process may be repeated if a quorum is again not able to be achieved. If the quorum is not achieved within a predetermined number of attempts, e.g., resetting of the delay timer, then an error notification may be sent to a system administrator workstation or other type of notification may be generated to contact appropriate personnel to rectify the error, or the node may assume that it is the only node that is in an UP state in the cluster and go ahead with access to the critical section.

In addition to the quorum inhibitor following UP status engine, the illustrative embodiments further implement a cluster view exchange mechanism and self denial of access mechanism. The cluster view exchange mechanism assists in ensuring that it is safe for a node to enter a critical section of code, and thus access a shared resource that requires sequential access, even when the other nodes of the cluster approve the access to the critical section. The cluster view exchange mechanism is provided in each node of a cluster and operates to exchange information between the node and other nodes of the cluster indicating how many other nodes in the cluster the node perceives as being operational, i.e. in an active state (either UP or in a DOWNBEAT state).

In accordance with the illustrative embodiments, to ensure that a sender node does not rely just on the receiver nodes' responses granting the sender node's requested access to the critical section or shared resource, when nodes respond to an access notification or request, in addition to sending the response indicating whether the access requested is granted or denied, the cluster view exchange mechanism maintains a registry of what other nodes the current node can perceive as being in an active state. This information is inserted into the response to the access notification/request by the cluster view exchange mechanism and the resulting response is transmitted back to the sender node. Thus, in the example ofFIG. 3, as discussed above, in response to an access notification/request from node A, node B sends the response <3, 1, OK> indicating that the number of UP nodes is 3 (e.g., nodes B, C, and D), the number of DOWNBEAT nodes is 1 (e.g., node A), and access is granted or “OK.” Similarly, node C sends a response of <2, 1, OK>, indicating 2 UP nodes (e.g., nodes B and C), 1 DOWNBEAT node (e.g., node A), and access is granted or “OK.”

The sender node, when receiving such responses from the receiving nodes in the cluster, compares the number of active nodes perceived by the receiving nodes to the number of active nodes perceived by the sender node. If the sender node determines that there is a discrepancy between these numbers of active nodes, then the sender node will deny itself access to the critical section or shared resource even though the receiver nodes have responded with a grant of the requested access. Thus, for example, node A sums the number of nodes that are active for each responding node to determine a corresponding active node count for that responding node with the results being that the number of active nodes perceived by node B is 4 and for node C is 3. These numbers of active nodes is compared to the sender node's own perceived number of active nodes, e.g., 3 in this case. In this example, the sender node, i.e. node A, active node count matches with node C's active node count but does not match node B's active node count. As a result, since there is not a consistent view of the cluster by all of the nodes, there is the possibility that node A did not send its access notification/request to a node in the cluster that may be in the critical section or accessing the shared resource. Thus, the self denial of access mechanism of node A denies itself access to the critical section or shared resource even though both nodes B and C indicated approval of the access. As mentioned previously, it should be appreciated that if the sender node perceives a larger number of active nodes than all of the responding receiver nodes, then the self denial of access mechanism of the sender node may grant itself access rather than performing the self denial of access since the sender node has a larger visibility of the cluster than the responding receiver nodes.

In addition to the above mechanisms, the illustrative embodiments further provide an asymmetric view timer mechanism in nodes of the cluster for initiating a timer to inhibit the transmission of access notifications/requests and positive responses to other nodes' access notifications/requests. That is, if a node determines that it has an asymmetric view of the cluster, e.g., the number of active nodes it perceives as part of the cluster is inconsistent with the number of active nodes perceived by other nodes in the cluster, the node may initiate an asymmetric view timer via the asymmetric view timer mechanism of the node. The asymmetric view timer mechanism of the node may periodically check its view of the cluster to determine if this asymmetric view persists. During the time interval measured by the timer, the node is in a vulnerable state and should avoid accessing critical sections and shared resources. Thus, sending of access notifications/requests are inhibited during this time interval until such time as the node determines that it no longer has an asymmetric view or until the timer expires. Thus, prior to sending out an access notification/request, the sender node may check to see if the timer has been started. If the timer has been started, the sender node may deny itself access to the critical section/shared resource and inhibit the sending of access notifications/requests. In addition, the node may not approve other node's requests and instead will automatically respond with a denial of any received access notification/request from other nodes of the cluster. If the asymmetric view discontinues, the timer may be canceled and normal operation of the node may be resumed.

FIG. 4is an example block diagram of the primary operational elements of a critical section access control engine in accordance with one illustrative embodiment. The elements may be implemented in one or more nodes, e.g., computing devices, processors, data processing systems, or the like, of a network of nodes, e.g., a cluster, the Internet, or the like. In one illustrative embodiment, the network is a cluster of nodes with each node in the cluster implementing its own local version of the critical section access control engine. The elements of the critical section access control engine may be implemented in software executed by one or more processors of a computing device, hardware, or any combination of software and hardware. In one illustrative embodiment, the elements inFIG. 4are implemented as software instructions executed on one or more processors of a node of a network.

As shown inFIG. 4, the critical section access control engine400comprises a controller410, an interface420, a quorum inhibitor430, a cluster view exchange engine440, a cluster view data structure450, a self denial of access engine460, and an asymmetric view timer engine470. The controller410controls the overall operation of the critical section access control engine400and orchestrates the operation of the other elements of the critical section access control engine400. The interface420provides a communication pathway through which data and control messages may be passed between the node and other nodes of the network (cluster).

The quorum inhibitor430performs the operations described above with regard to determining if a quorum of other nodes is active. The quorum inhibitor430also operates to inhibit the sending of access notifications/requests during a predetermined delay time period.

The cluster view exchange engine440performs the operations previously described above for inserting active node information into a response to an access notification/request from another node in the cluster. The information used to insert the active node information into the response may be obtained from the storing of the node's cluster view in the cluster view data structure450. The information stored in the cluster view data structure450is generated from the heartbeat messages received from other nodes in the cluster. The heartbeat messages indicate which nodes are active in the cluster and whether those nodes are in an UP state or DOWNBEAT state. A node receives heartbeat messages from other nodes that the current node can perceive in the cluster.

The self denial of access engine460performs the above described self denial operations for self-denying the node's own access notifications/requests in response to other nodes responding with active node information that differs from the current node's own view of active nodes in the cluster. However, if the current node's view of the cluster comprises more active nodes than the other nodes can perceive, then the self denial of access engine460may permit access rather than self deny access.

The asymmetric view timer engine470performs the above described operations for initiating a timer to inhibit the transmission of access notifications/requests and positive responses to other nodes' access notifications/requests when it is determined that the node has an asymmetric view of the cluster. The inhibiting of the transmission of access notifications/requests and positive responses continues for a period of time measured by the timer. The asymmetric view timer engine470periodically checks its view of the cluster to determine if this asymmetric view persists and canceling the timer in the event that the asymmetric view no longer persists.

FIG. 5is a flowchart outlining an example operation for inhibiting the transmission of an access request after a node comes up in accordance with one illustrative embodiment. As shown inFIG. 5, the operation starts by the node entering an UP state, such as after a boot operation, reboot operation, or other operation for adding the node to a cluster (step510). The node determines if there is a quorum of other nodes in an active state of operation in the cluster (step520). If there is a quorum of nodes in an active state, then access request transmission is permitted (step530). If there is not a quorum of nodes in an active state, a delay timer is initiated (step540) and transmission of access requests is inhibited while the timer is counting a predetermined time interval (step550). A determination is made as to whether the timer has timed-out, e.g., reached a minimum or maximum value (step560). If the timer has timed-out, then transmission of the access request is permitted (step530). The operation then terminates.

FIG. 6is a flowchart outlining an example operation for critical section access control in accordance with one illustrative embodiment. The operation starts by determining the nodes of the cluster that are viewable by the present node (step610). The nodes that are viewable by the present node are determined from a cluster view data structure that is populated with information from heartbeat messages received from other nodes in the cluster.

The present node sends an access request out to the nodes of the cluster that are viewable by the present node (step620) and the present node waits for responses from the other nodes (step630). The active node information from received responses is compiled (step635) and each other node's indication of active nodes viewed in the cluster is compared to the number of active nodes viewable by the present node (step640). A determination is made as to whether there is a discrepancy between the number of active nodes viewable by the present node and the active nodes viewable by the other nodes (step650). If not, then a determination is made as to whether any of the other nodes have responded that access is denied (step660). If so, then the access request is denied and access to the critical section is inhibited (step670). If none of the other nodes have responded that access is denied, then access to the critical section is permitted and the present node accesses the critical section (step680).

If there is a discrepancy in step650, a determination is made as to whether the discrepancy indicates that the present node has a smaller number of viewable nodes than one or more other nodes in the cluster (step690). If not, then the operation goes to step660. If the present node has a smaller number of viewable nodes than one or more other nodes in the cluster, then an asymmetric view timer is initiated (step700). A determination is made as to whether the asymmetric view has terminated or if the asymmetric view timer has expired (step710). If either has happened, the operation returns to step690.

It should be appreciated that whileFIG. 6illustrates a loop operation with regard to step710and the return to step690, in other illustrative embodiments, rather than looping back and repeatedly checking the node's view of the cluster to determine if there is an asymmetric view, instead the node may simply shut down its operation and periodically check its view of the cluster to determine if the asymmetric view persists. If the asymmetric view discontinues, then the node may begin its normal operation of sending out requests for shared resource access again.

Thus, the illustrative embodiments provide mechanisms for granting access to shared resources and more specifically to accessing a critical section of code that in turn accesses a shared resource. The illustrative embodiments provide mechanisms for addressing the three main considerations noted above with regard to how soon after a node comes up that access requests should be allowed to be transmitted, determining if it is safe for a node to enter a critical section even when other nodes indicate approval of such access to the critical section, and determining when a node should not request access to a critical section. The illustrative embodiments extend the Ricart-Agarwala algorithm in these three areas.