Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-05-15
2002-04-16
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C710S200000
Reexamination Certificate
active
06374285
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to granting mutual exclusion to processors during memory accesses, and more particularly to granting mutual exclusion to processors in a remote-write globally ordered network of processors.
BACKGROUND OF THE INVENTION
There has been much work in implementing fast mutual exclusion on computer systems that support a variety of capabilities in hardware. Most work has focused on a network of multi-processors where all processors can access a shared memory via some interconnect. The processors' view of the shared memory is usually kept consistent according to a particular memory consistency model, such as sequential consistency. For example, given sequential consistency, a number of algorithms are known, such as Decker's algorithm, Lamport's Bakery algorithm, Peterson's algorithm, and Lamport's 1-bit algorithm. Typically, these algorithms obtain mutual exclusion with respect to a named object known as a lock, so “acquiring a lock” expresses the concept of obtaining mutual exclusion for a process.
These algorithms have varying properties, such as whether they generalize easily to more than two processes, whether processes can get “starved”, how many reads and writes they do in the common case, and so forth. Please see, E. W. Dijkstra “Solution of a problem in concurrent programming control,” Communications of the ACM, Vol. 8, No. 9, p. 569, September 1965; Leslie Lamport “A new solution of Dijkstra's concurrent programming problem”, Communications of the ACM”, Vol. 17, No. 8, pp. 86-88, August 1974; Leslie Lamport “The Mutual Exclusion Problem: Part II—Statement and Solutions”, Journal of the ACM, Vol. 33, No., 2, pp. 327-346, April 1986; and G. L. Peterson “A new solution to Lamport's concurrent programming problem” ACM Transactions on Programming Languages and Systems, Vol. 5, No. 1, pp. 56-65, January 1983.
U.S. Pat. No. 5,553,298 “Method and apparatus for mutual exclusion in self-directed distributed systems” issued to Merryman on Sep. 3, 1996 describes a method of mutual exclusion between processes connected by a network. There, mutual exclusion is achieved by having the processors broadcast their interest in obtaining a lock. However, the method uses a simple back-off system where processors keep backing off until only one process is expressing an interest. The method uses time constants in the network to determine how long a process must wait after expressing an interest before it can be sure that it has the lock. The problem with that method is that in modem networks, time “constants” may change over time.
In shared memory systems, lock contention occurs when more than one process expresses an interest to acquire a particular lock at the same time. In a simple approach, this problem can be overcome by having a process write a value into an element of shared memory array to indicate that the process wants to acquire a lock. If there is no contention, then the process immediately gets the lock with just the single write access. However, when there is contention, all contending processes “back off” by zeroing their request from the corresponding elements of the array, and waiting a semi-random, and ever-increasing amount of time, and then trying again later until there is no contention. When there are many processes contending for the same lock, this back-off strategy can be very expensive, because processes can have repeated conflicts until they back-off for long amounts of time.
Therefore, there is a need for a mutual exclusion method that can acquire a lock with a single write access when there is no contention, yet the method would operate efficiently without back-off when there is contention. In addition, the method should grant locks to processes in a first-come, first-served “fair” manner that does not lead to “starvation” of individual processes.
SUMMARY OF THE INVENTION
The invention provides a method for acquiring a lock in a network of processors with globally ordered remote-writes. A process requesting a lock changes an associated ticket number from zero to one. Next, the process determines if every other process attempting to acquire the lock has a ticket number of zero. If true, the request for the lock is immediately granted. Otherwise, if false, the process changes its ticket number to a value greater than that of every other process, and the process waits until its ticket number is the lowest non-zero ticket number, in which case the lock is granted with mutual exclusion.
In one aspect of the invention, ticket numbers are integer values in the range from zero to a predetermined maximum integer value. Ticket numbers are assigned in order of lock requests.
In another aspect of the invention, the ticket number of the process is set to zero when the next available lowest ticket number is greater than the predetermined maximum integer value. In this case, the process restarts the process of acquiring the lock when the ticket numbers of all other processes requesting the lock are less than the predetermined maximum ticket number.
REFERENCES:
patent: 5068781 (1991-11-01), Gillett, jr. et al.
patent: 5553298 (1996-09-01), Merryman
patent: 5615374 (1997-03-01), Sadoi et al.
patent: 5699500 (1997-12-01), Dasgupta
patent: 5706515 (1998-01-01), Connelly et al.
patent: 5922057 (1999-07-01), Holt
patent: 5987492 (1999-11-01), Yue
patent: 5991845 (1999-11-01), Bohannon et al.
patent: 6018795 (2000-01-01), Boudou et al.
patent: 6161162 (2000-12-01), DeRoo et al.
patent: 6192514 (2001-02-01), Lurndal
Freudenthal et al., “Process Coordination with Fetch-and-Increment,” ACM, pp. 260-268, 1991.*
Kushilevitz et al., “Randomized Mutual Exclusion Algorithms Revisited,” ACM, pp. 275-283, 1992.*
Coulouris et al., “Distributed System Concepts and Design,” second edition, Addison-Wesley, Chapter 13, pp. 377-408, 1994.*
Bach, Maurice J., “The Design of the Unix Operating System,” Prentice Hall, Chapter 12, pp. 391-411, 1990.*
J,M, Mellor-Crummey and M.L. Scott, “Algorithms for Scalable Synchronization On Shared-Memory Multiprocessors,” ACM Transactions on Computer Systems, vol. 9, No. 1, pp. 22-47, Feb. 1991.*
Thomas E. Anderson, “The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors,”IEEE Transactions on Parallel and Distributed Systems, vol. 1, No. 1, pp. 6-16, Jan. 1990.*
Gary Graunke and Shreekant Thakkar, “Synchronization Algorithms for Shared-Menory Multiprocessors,” IEEE, pp. 60-69, Jun. 1990.*
Leslie Lamport; “A Fast Mutual Exclusion Algorithm”; ACM Transactions on Computer Systems; vol. 5, No. 1; pp. 1-11; 1987.
Lamport Leslie
Scales Daniel J.
Compaq Computer Corporation
Courtenay III St. John
Leah Sherry Oppenheimer Wolff & Donnelly
LandOfFree
Method for mutual exclusion of locks in a remote-write... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for mutual exclusion of locks in a remote-write..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for mutual exclusion of locks in a remote-write... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859283