Generic fault-tolerant locking mechanism for multiprocessor systems
AssigneeAT&T Corp.
InventorYuguang Wu
Life of this patent
Estimating the term…
Loading patent…
AssigneeAT&T Corp.
InventorYuguang Wu
Estimating the term…
A generic fault tolerant “match-and-set” locking mechanism and method for controlling access to resources shared among a plurality of users N. The match-and-set lock has a locked operating state and an unlocked operating state controlled by the value C of its content such that the lock is in its locked operating state when C≠0 and in its unlocked operating state where C=0. The lock returns a value R, equal to the lock's current content C, to an inquiring user seeking access to the resource. A return value R=0 denotes that the resource is free, and a return value R≠0 denotes that the resource is locked by another user. The lock is responsive to a command in the form (A, B), such that the lock substitutes B for C if A=C. Thus, the lock may be locked by issuing the command (A, B) where A=C and B≠0; and the lock may be released by issuing the command (A, B) where A=C and B=0. A deadlock condition may be avoided by setting the lock to the value B=P+T*(N+1), where P<(N+1) and identifies the user issuing this command (A, B), and T is the current global time stamp when the user issues this command. When the return value R≠0, R identifies the user currently locking the resource and the time when that user locked the resource: the locking user id is simply R%(N+1), and the locking time is R/(N+1). An inquiring user can then determine if the user currently locking the resource has failed, or restarted, since locking the resource. If so, the inquiring user can rescue the lock from the control of the failed user. The mechanism of “match-and-set” ensures that exactly one such user can succeed in rescuing that lock. Crashed users can come back online and participate in new locking operations: the locking semantics is always maintained and this system suffers no deadlocks. The implementation requirements are easy to satisfy: that there is a global reference clock, that any user maintains a time stamp (off the global clock) of its latest reboot time, and the match-and-set access is an indivisible operation. The last can be implemented in hardware in a way similar to that of the traditional test-and-set lock. The plurality of users may be processors in a multiprocessor computer system, and the processors may form a telecommunications system.
A match-and-set lock for controlling access to a resource that is shared among a plurality of users N, said lock having a locked operating state and an unlocked operating state controlled by a value C such that the lock is in its locked operating state when C≠0 and in its unlocked operating state where C=0, said lock being responsive to a command in the form (A, B), said lock substituting B for C if A=C, whereupon:
A software program implemented in a multiprocessor computer system, said software program controlling access to a shared resource from a plurality of processors N, by employing a match-and-set lock that has a current content C and that is responsive to a match-and-set command (A, B) that writes B into the current content if A=C, said lock committing the shared resource to the control of that processor that most recently set the current content to a non-zero value, said software program allowing the multiprocessor system to:
A method of controlling access to a shared resource from a plurality of processors N, comprising the steps of:
A method of controlling access to a shared resource from a plurality of processors N, said method employing a match-and-set lock that has a current content C and that is responsive to a match-and-set command (A, B) that writes B into the current content if A=C, said lock committing the shared resource to the control of that processor that most recently set the current content to a non-zero value, said method comprising the steps of:
Dependencies are inferred from the claim text.