Lingering locks with fairness control for multi-node computer systems

Abstract

The processors in a multiprocessor computer system are grouped into nodes. The processors can request a lock, but the lock is granted to only one processor at any given time to provide exclusive processor access to the resource protected by the lock. When a processor releases the lock, the lock is made available to another processor at the same node, even though a processor at a different node may have requested the lock earlier. To maintain fairness, the lock is forced to another node after granting a certain number of consecutive requests at a node or after a certain time period. In one embodiment, a specialized data structure representing a lock request from a processor at a particular node is placed into a queue. A later requesting processor can acquire a preemptive position in the queue by spinning on a data structure already in the queue if the data structure corresponds to the processor's node. To maintain fairness, the data structure is limited to a certain number of uses, after which additional processors are not permitted to spin on it. When the data structure has no more active spinners, it is dequeued, and the lock is made available to a processor spinning on the next structure in the queue. Logic for handling interrupts is included, and the bitfield arrangement of the data structure is tailored to the locking scheme. Preallocating data structures for the queue increases performance.