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.

Other References

• Margaret H. Eich, "Graphic Directed Locking", IEEE Transaction of Software Eng., vol. 14, No. 2, Feb. 1988, p. 133-140.
• Marina Roesler, "Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes", *8th Intl. Conf. on Distributed Computing System, Jun. 13-17, 1988, IEEE 1988, p. 224-233.
• Suh-Yin Lee et al., "A Multi-Granularity Locking Model for Concurrency Control in Object-Oriented Database Systems", IEEE Transaction on Knowledge and data Engineering, vol. 8, No. 1, Feb. 1996, p. 144-156.
• Y.C. Tay, "Locking Performance in Centralized Database", ACM Transaction on Database System, vol. 10, No. 4, Dec. 1985, p. 415-462.
• Bach, "Multiprocessor Systems,"The Design of the UNIX Operating System, Prentice-Hall, Inc., pp. 1-3, 391-411 (.COPYRGT. 1986)
• Bolosky et al., "Simple But Effective Techniques for NUMA Memory Management," ACM SIGOPS Operating Systems Review, 23:5; pp. 19-31 (Dec. 3-6, 1989)
• Bonwick, "The Slab Allocator: an Object-Caching Kernal Memory Allocator," Sun Microsystems (1993)
• Chapin, et al., "Memory System Performance of UNIX on CC-NUMA Multiprocessors," Sigmetrics '95, Computer Science Laboratory, Stanford University pp. 1-13 (1995)
• Craig, "Building FIFO and Priority-Queuing Spin Locks from Atomic Swap," Technical Report 93-02-02, Department of Computer Science and Engineering, FR-35, University of Washington, pp. 1-29 (Feb. 1993)
• Graunke et al., "Synchronization Algorithms for Shared-Memory Multiprocessors," Computer, pp. 60-69 (Jun. 1990)
• Grunwald et al., "CustoMalloc: Efficient Synthesized Memory Allocators," Software--Practice and Experience, vol. 23(8), pp. 851-869 (Aug. 1993)
• Lim, et al., "Reactive Synchronization Algorithms for Multiprocessors," ASPLOS, vol. 1 (.COPYRGT. Oct. 1994)
• McKenney, et al., "Efficient kernel Memory Allocation on Shared Memory Multiprocessors," 1993 Winter, USENIX, pp. 295-305, Jan. 25-29 (1993)
• Magnusson et al., "Efficient Software Synchronization on Large Cache Coherent Multiprocessors," SICS Research Report T94:07, pp. 1-32 (Feb. 1994)
• Mellor-Crummey et al., "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors," ACM Transcations on Computer Systems, 9:1, pp. 21-65 (Feb. 1991)
• Mellor-Crummey et al., "Synchronization Without Contention," ACM SIGARCH Computer Architecture News, 19:2, pp. 269-278 (Apr. 1991)
• Vahalia, "Synchronization and Multiprocessors," UNIX.RTM. Internals the New Frontiers, Prentice-Hall, Inc., pp. 1-3; 187-219 (.COPYRGT. 1996)
• Verghese et al., "Operating system support for improving data locality on CC-NUMA compute servers," ACM SIGOPS Operating System Review, 30:5, pp. 279-289 (Dec. 1996)
• Wills, "Process Synchronization and Interprocess Communication," The Computer Science and Engineering Handbook, CRC Press, Ch. 79, pp. 1725-1746 (.COPYRGT. 1997)
• Wolski et al., "Program Partitioning for NUMA Multiprocessor Computer Systems," Journal of Parallel and Distributed Computing, vol. 19, pp. 203-218 (1993