Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2007-01-30
2007-01-30
Chu, Gabriel L. (Department: 2114)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C710S200000, C711S164000
Reexamination Certificate
active
10822954
ABSTRACT:
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.
REFERENCES:
patent: 4979105 (1990-12-01), Daly et al.
patent: 5305448 (1994-04-01), Insalaco et al.
patent: 5432929 (1995-07-01), Escola et al.
patent: 5615373 (1997-03-01), Ho
patent: 5623670 (1997-04-01), Bohannon et al.
patent: 5623671 (1997-04-01), Ando et al.
patent: 5669002 (1997-09-01), Buch
patent: 5892954 (1999-04-01), Tomas et al.
patent: 5892955 (1999-04-01), Ofer
patent: 6112222 (2000-08-01), Govindaraju et al.
patent: 6223335 (2001-04-01), Cartwright et al.
patent: 6301676 (2001-10-01), Kumar et al.
patent: 6539446 (2003-03-01), Chan
Microsoft Press Computer Dictionary Third Edition, “timeout”, Microsoft Press, 1997, p. 469.
AT&T Corp.
Chu Gabriel L.
LandOfFree
Fault-tolerant match-and-set locking mechanism for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fault-tolerant match-and-set locking mechanism for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fault-tolerant match-and-set locking mechanism for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3819635