Composite abortable locks

Details Composite abortable locks Composite abortable locks

2011-07-19

2011-07-19

To, Jennifer N (Department: 2195)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C718S104000, C710S200000, C710S240000, C711S147000, C711S152000, C707S999010

Reexamination Certificate

active

07984444

ABSTRACT:
A lock implementation has properties of both backoff locks and queue locks. Such a “composite” lock is abortable and is provided with a constant number of preallocated nodes. A thread requesting the lock selects one of the nodes, attempts to acquire the selected node, and, if successful, inserts the selected node in a wait-queue for the lock. Because there is only a constant number of nodes for the wait-queue, all requesting threads may not be queued. Requesting threads unable to successfully acquire a selected node may backoff and retry selecting and acquiring a node. A node at the front of the wait-queue holds the lock.

REFERENCES:
patent: 6182177 (2001-01-01), Harriman
patent: 6678802 (2004-01-01), Hickson
patent: 6965961 (2005-11-01), Scott
patent: 7130905 (2006-10-01), Dinker et al.
patent: 7162557 (2007-01-01), Takeda et al.
patent: 2003/0131041 (2003-07-01), Dinker et al.
patent: 2003/0200457 (2003-10-01), Auslander et al.
patent: 2004/0098723 (2004-05-01), Radovic et al.
patent: 2005/0080963 (2005-04-01), Schopp
Tsigas, Philippas; Zhang, Yi. “Efficient Wait-Free Queue Algorithms for Real-Time Synchronization.” Technical Report May 2002, Department of Computing Science, Chalmers University of Technology, 2002. Retrieved Sep. 3, 2010.
Scherer, William N., III; Scott, Michael L. “Contention Management in Dynamic Software Transactional Memory.” Proceedings of the ACM PODC Workshop on Concurrency and Synchronization in Java Programs. Jul. 2004.
Radovic, Z. and Hagersten, E.; Hierarchical Backoff Locks for Nonuniform Communication Architectures. In Proceedings of the 9th International Symposium on high Performance Computer Architecture (Feb. 2003) 12 pages.
Scott, M.L. and Scherer III, W.N. Scalable Queue-Based Spin Locks with Timeout. Proceedings of the 8th Symposium on Principles and Practice of Parallel Programming 36, 7 (2001), 9 pages.
Lim, B.H., and Agarwal, A.; Reactive Synchronization Algorithms for Multiprocessors. In ASPLOS-VI: Proceedings of the sixth international conference on Architectural support for programming languages and operating systems (1994), 11 pages.
Magnusson, P.S., Oandin, A. and Hagersten, E.; Queue Locks on Cache Coherent Multiprocessors. In Proceedings of the 8th International Symposium on Parallel Processing (1994), 7 pages.
Craig, T.S.; Building FIFO and Priority-Queuing Spin Locks from Atomic Swap. Tech. Rep. TR 93-02-02, Department of Computer Science, University of Washington, Feb. 1993, 29 pages.
Mellor-Crummey, J.M., and Scott, M.L.; Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems 9, 1 (1991), 45 pages.
Graunke, G and Thakkar, S.; Synchronization Algorithms for Shared-Memory Multiprocessors. Computer 23, 6 (1990) 10 pages.
Anderson, T.E.; The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors. IEEE Transactions on Parallel and Distributed Systems 1, 1 (1990) 11 pages.
Scott, Michael L.; Non-Blocking Timeout in Scalable Queue-Based Spin Locks; Department of Computer Science; University of Rochester; New York; 2002; 10 pages.
BritishExpats.com, Dallas Walk-In: British Expat Discussion Forum, Jan. 7, 2002, http://britishexpats.com/forums/showthread.php?t=59651 (8 Pages).

Affiliated with

Also associated with

Rating

Composite abortable locks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Composite abortable locks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Composite abortable locks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2700604