Fair scalable reader-writer mutual exclusion

Details Fair scalable reader-writer mutual exclusion Fair scalable reader-writer mutual exclusion

2005-08-30

2010-06-01

An, Meng-Ai (Department: 2195)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C712S229000

Reexamination Certificate

active

07730491

ABSTRACT:
Implementing fair scalable reader writer mutual exclusion for access to a critical section by a plurality of processing threads in a processing system is accomplished by creating a first queue node for a first thread on the first thread's stack, the queue node representing a request by the first thread to access the critical section; adding the first queue node to a queue pointed to by a single word reader writer mutex for the critical section, the queue representing a list of threads desiring access to the critical section, each queue node in the queue being on a stack of a thread of the plurality of processing threads; waiting until the first queue node has no preceding write requests as indicated by predecessor queue nodes on the queue; entering the critical section by the first thread; exiting the critical section by the first thread; and removing the first queue node from the queue.

REFERENCES:
patent: 6081665 (2000-06-01), Nilsen et al.
patent: 6112222 (2000-08-01), Govindaraju et al.
patent: 6341302 (2002-01-01), Celis
patent: 6480918 (2002-11-01), McKenney et al.
patent: 6546443 (2003-04-01), Kakivaya et al.
patent: 6684398 (2004-01-01), Chaudhry et al.
patent: 6934950 (2005-08-01), Tuel et al.
patent: 6965961 (2005-11-01), Scott
patent: 7234139 (2007-06-01), Feinberg
patent: 7430627 (2008-09-01), McKenney
patent: 7493618 (2009-02-01), Michael et al.
patent: 2002/0032719 (2002-03-01), Thomas et al.
patent: 2003/0023656 (2003-01-01), Hutchison et al.
patent: 2006/0048149 (2006-03-01), Clift
patent: 2006/0225078 (2006-10-01), Anderson
patent: 2007/0044103 (2007-02-01), Rosenbluth et al.
patent: 2007/0157200 (2007-07-01), Hopkins
patent: 0943993 (1999-09-01), None
Mellor-Crummey, J. M., et al.; “Scalable reader-writer synchronization for shared memory multi-processors”; ACM SIGPLAN Notices, ACM, Association for Computing Machinery; New York, NY, US; vol. 26 No. 7; Jul. 1991; XP002402085; ISSN: 0362-1340; pp. 106-113.
Danny Hendler, et al.; “A Scalable Lock-Free Stack Algorithm”; Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures; Barcelona, Spain; XP002408296; Jun. 27, 2004; pp. 206-215.
Orran Krieger, et al.; “A Fair Fast Scalable Reader-Writer Lock”; Proceedings of the International Conference on Parallel Processing, XP002402082; 1993; 4 pages.
Mellor-Crummey J. M., et al.; “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”; ACM Transactions on Computer Systems, ACM, New York, NY, US, vol. 9 No. 1, Feb. 1, 1991, XP000240573, ISN: 0734-2071, pp. 21-65.
Anonymous, “Spin Queues Nov. 1975” IBM Technical Disclosure Bulletin, W.W. Collier and K.L. Howell; vol. 18, No. 6, Nov. 1, 1975, New York, US, XP002408297, pp. 1953-1954.
International Search Report and Written Opinion; International Application No. PCT/US2006/030521; date of mailing Dec. 12, 2006; 13 pages.
International Preliminary Report on Patentability, International Application No. PCT/US2006/030521, mailing date Mar. 13, 2008, 8 pages.
Krieger et al—1993 Proc. Intl. Conf. on Parallel Processing—A Fair Fast Scalable Reader-Writer Lock.
Mellor-Crummey et al—Scalable Reader-Writer Synchronization for Shared—Memory Multiprocessors.
Harris—A Pragmatic Implementation of Non-Blocking Linked-Lists.

Affiliated with

Also associated with

Rating

Fair scalable reader-writer mutual exclusion does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fair scalable reader-writer mutual exclusion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair scalable reader-writer mutual exclusion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4165830