Lingering locks with fairness control for multi-node computer systems

In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a node while maintaining fairness among the nodes, the method comprising:

• tracking requests for the lock from requesting processing units by node;
• when the lock is released by a processing unit at a first node, keeping the lock at the first node if there is an outstanding lock request from a processing unit residing at the first node;
• and
• overriding the keeping step by forcing the lock to a second node if there is an outstanding lock request by a processing unit residing at the second node and the lock has been kept at the first node for more than a predetermined number of consecutive grants.

In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a node while maintaining fairness among the nodes, the method comprising:

• tracking requests for the lock from requesting processing units by node;
• when the lock is released by a processing unit at a first node, keeping the lock at the first node if there is an outstanding lock request from a processing unit residing at the first node;
• and
• overriding the keeping step by forcing the lock to a second node if there is an outstanding lock request by the second node and the lock has been kept at the first node for more than a predetermined time.

In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at the nodes while maintaining fairness among the nodes, the method comprising:

• grouping lock requests into sets by node;
• when the lock is released by a processing unit at a first node, keeping the lock at the first node if there is an outstanding lock request from a processing unit residing at the first node;
• and
• overriding the keeping step by forcing the lock to a second node when releasing a last outstanding lock request in one of the sets.

In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a specific node while maintaining fairness among the nodes by maintaining a queue of requests, the method comprising:

• enqueuing a plurality of lock requests into the queue, each lock request originating from one of the processing units, wherein each processing unit is associated with a single node;
• tracking from which node each lock request originates in the queue;
• tracking the number of preemptive positions conferred for each node;
• and
• upon receiving a lock request from a requesting processing unit at a node for which a lock request already exists in the queue, conferring a preemptive position in the queue to the requesting processing unit if the number of preemptive positions conferred for the node does not exceed a predetermined number.

In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock requestable by the processing units at a node while maintaining fairness among the nodes by maintaining a queue of node queue elements with a head and a tail to track lock requests, each node queue element corresponding to one of the nodes, the method comprising:

• if the lock is requested by a first processing unit when the lock is available and the queue is empty, granting the lock to the first processing unit and placing a node queue element in the queue corresponding to the node of the first processing unit;
• if the lock is requested by a second processing unit when the lock is unavailable and the queue contains a node queue element corresponding to the second processing unit's node not used more than a predetermined maximum number of times, preemptively queuing the lock request at the node queue element and spinning the second processing unit on the element;
• if the lock is requested by a third processing unit when the lock is unavailable and the queue does not contain a node queue element corresponding to the third processing unit's node not used more than a predetermined number of times, queuing a node queue element at the tail of the queue and spinning the third processing unit on the element;
• when the lock becomes available and the queue has at least one node queue element on which at least one processing unit is spinning, modifying the node queue element at the head of the queue to indicate that the lock is available to processing units spinning on the node queue element at the head of the queue, thereby granting the lock to a processing unit at a node corresponding to the node queue element at the head of the queue;
• and
• when the lock is released by a releasing processing unit and a node queue element at the head of the queue indicates that no more processing units are spinning on the element, dequeueing the node queue element.

A computer-readable medium having stored thereon a data structure for tracking requests for a lock in a computer having a number of interconnected nodes each having at least one processing unit, the data structure comprising:

• an ordered queue of spin state data structures with a head and a tail, each of the spin state data structures comprising:
• an available field upon which requesting processing units can spin, indicative of when the lock is available;
• a number-of-spinners field indicative of how many processing units are spinning on the spin state data structure;
• and
• a uses field indicative of how many times the spin state data structure has been used to acquire a position in the queue and limited to a predetermined number to enforce fairness among the nodes, wherein each spin state data structure is associated with one of the interconnected nodes, wherein the spin state data structure at the head of the queue indicates to which node the lock should be next granted if the number-of-spinners field is greater than zero;
• and
• a header structure facilitating management of the queue, the header structure comprising a reference to the head of the ordered queue, a reference to the tail of the queue, and a reference to a queue element, if any, for each of the interconnected nodes.

A computer-readable medium having stored thereon a data structure for tracking requests for a lock in a computer having a number of interconnected nodes each having at least one processing unit, the data structure comprising:

• a local structure for each node, the local structure comprising:
• a processing unit bit mask field comprising one bit per processing unit at the local structure's node, wherein each bit is set to indicate processing units acquiring the lock and nodes having processing units holding the lock;
• a spin state field indicating the number of consecutive times the local structure's node has held the lock if the lock is being held by a processing unit at the local structure's node, and indicating a maximum number of consecutive times if the lock is held by none of the processing units at the local structure's node, whereby at least one processing unit at the local structure's node can spin on the spin state field in order to acquire the lock;
• a previous spin state field indicating the value of the spin state field immediately before a processing unit at the local structure's node having the lock acquired the lock;
• and
• a pointer to a global structure shared by the nodes;
• and the global structure shared by the nodes, the global structure comprising:
• a latch value for indicating whether the lock is available;
• a field indicating whether the lock was conditionally acquired;
• a node bit mask field with one bit per node, wherein each bit is set to indicate nodes acquiring the lock and processing units holding the lock;
• and
• an array of pointers comprising a pointer for each node, the pointer pointing to the local structure for each node.

A computer-readable medium having stored thereon a data structure for tracking requests for a lock in a computer having a number of interconnected nodes each having at least one processing unit, the data structure associated with one of the nodes and able to be enqueued into an ordered list, the data structure comprising:

• a number-of-spinners bitfield indicative of how many processing units are actively spinning on the data structure;
• a number-of-uses bitfield indicative of how many times processing units have acquired a position in the ordered list with the data structure;
• a lock available field indicative of when the lock is available to one of the processing units actively spinning on the data structure;
• a number-of-references bitfield indicative of how many processing units require future access to the data structure;
• and
• a plurality of guard fields arranged within the data structure to guard underflows of at least two of the bitfields during atomic operations on the bitfields and the lock available field.