Fault-tolerant match-and-set locking mechanism for multiprocessor systems
View Patent ↗A match-and-set lock has a locked operating state and an unlocked operating state controlled by the value C. The lock returns a value R=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) to 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.
1. A method for controlling access by N users to a resource comprising the steps of:
receiving from a user a message that requests access to said resource, which message includes a number B obtained by performing a mathematical operation that is related to a number that represents said user and to N;
in response to said message, retrieving from a predetermined location associated with said resource a stored value C that is 0 when the resource is available to any user, and other than 0 otherwise;
if C indicates said resource is available to be accessed,
(a) sending a message to said user that includes a number D=0, and
(b) storing B in said predetermined location, thereby replacing C with B;
if C indicates said resource is unavailable to be accessed, sending said message to said user with D=C, wherein B=P+T*(N+1), where P is a number representing said user and is not greater than N, T is a number representing a time stamp, and symbol * stands for the multiplication operation.
2. A method executed relative to a resource that may be used by any user of N users and which may be locked to prevent access to the resource, comprising the steps of:
when a user of said users desires to gain access to said resource sending, to a lock, a message that includes the number P+T*(N+1), where P, which is less than (N+1), is a number representing said user, T is a number representing a time stamp corresponding to a time when said message is sent, and symbol * stands for the multiplication operation, and receiving from said lock a value corresponding to state of said lock;
when said value is 0, said user proceeding to treat said resource as being accessible;
when said value is C≠0, indicative of another of said N users having locked said resource, said user
(a) treating said resource as unavailable, and
(b) sending, to said lock, a message that includes said value C and said number P+T*(N+1), and proceeding to treat said resource as being accessible;
when said user of said users desires to release said resource, thereby permitting other users to gain access to said resource, sending to said lock a message comprising elements A and B, where A is equal to said number P+T*(N+1) that was previously sent to said lock and which resulted in said user proceeding to treat said resource as being accessible, and B=0.
3. The method of claim 2 where, when said value is C≠0, and prior to said step of sending, to said lock, a message that includes said value C and said number P+T*(N+1), said user determining whether said another of said N users erroneously failed to release said resource.