Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1999-02-04
2001-05-01
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S148000, C711S154000, C711S167000
Reexamination Certificate
active
06226717
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains generally to dynamic magnetic information storage and retrieval and more particularly to systems and methods used in controlling the electronic circuitry through which the information signal is processed.
2. Description of Related Art
A computer system generally includes at least one processor to perform computations and control components coupled to the computer system. Some computer systems include multiple processors that access shared resources within the computer system. For example, multiple processors may individually access a shared hard disk, a shared I/O channel, a shared peripheral, or a shared memory space to perform a particular function. Furthermore, such multiprocessors may access shared resources to communicate with other processors within the computer system. It is common, for example, for a processor to store data intended for another processor in a shared memory location. Thereafter, the other processor can read the data from the shared memory location.
It is common for multiple processors in a computer system to share a storage location, for example, in a database stored on a hard disk. Preferably, access to the shared storage location is coordinated to provide exclusive access to the shared storage location by any single processor. Otherwise, one processor may independently modify the content of the shared storage location without notice to another processor accessing the shared storage location at approximately the same time. Such processors are termed “competing processors”, in that they are competing for access to a shared storage location. A possible result of non-exclusive access to a shared storage location by competing processors is that corrupted or unintended data may be read or stored in the shared storage location by one of the processors.
Existing approaches for providing exclusive access to shared storage may be divided into at least four categories. These solutions can be compared based on their safety (i.e., the ability to provide mutual exclusion in all practical situations) and their freedom from deadlock. A deadlock, very simply, is a condition in which two or more processors wait for each other to release a shared resource before resuming their execution. Deadlock occurs if a processor attempts to initiate exclusive access to a shared storage location, but it and all other competing processors are thereafter denied exclusive access because at least two competing processors continually start, abort, and restart their attempts to gain exclusive access. Because all processors participating in a deadlock are suspended and cannot resume execution, they cannot therefore release the resources they own.
A first category of solutions involves exclusive access approaches that assume the set of processors requiring exclusive access to the shared storage is known in advance. In many applications, this assumption is not valid. Particularly in applications where the number and identity of the processors is dynamic to enable system scaling, such solutions are unsuitable for many uses.
Another category of solutions, that generally do not require knowledge of the set of processors eligible to compete for exclusive access to a shared memory location depend on timing characteristics of the storage subsystem. By this it is meant that the solutions only perform properly when the physical implementation of the storage subsystem behaves within predicted timing constraints. Accordingly, such solutions suffer from safety problems if the storage subsystem fails to satisfy the timing constraints. These solutions also mitigate against system scalability because as systems scale by adding new devices the timing behavior of the system may change.
Fischer's algorithm is an example of such a solution. In Fischer's algorithm the processor requesting exclusive access executes a delay operation, called a “race wait delay” before exclusive access is actually obtained or assumed. In other words, the race wait delay is a delay between the request for a mutex lock and the time that the resource is actually locked.
Each processor requesting the lock must first check the state of the lock, then assert control over the lock, then wait, then verify that it in fact remained in control of the lock for the wait period. Only after the wait period has elapsed and the verification step is complete can the requesting processor be assured that the lock has been obtained. In a race condition, for example, first and second processors both check the state of the lock at essentially the same time. This does not have to be simultaneous. Whenever the second processor checks the lock state before the first processor has assumed control, the check will reveal that the lock is available. Conversely, a race condition exists whenever the first processor asserts control over the lock at a time that is too late for the second processor to detect.
In a race condition described above, the second processor will override the first processor and take control of the lock for itself. Because the first processor must wait for the race wait delay, it will not attempt to, for example, write data to the shared resource until it has waited and then verified that it remains in control of the lock. In the race condition described above, the first processor will detect that it has lost control of the lock, and will have to wait and arbitrate for control of the lock later.
The race wait delay is a delay added to enable competing processors to self-arbitrate for access to the shared resource. Essentially, the race wait delay is a time period of sufficient length to ensure that in a race condition one or the other of competing processors detect the other processor's access attempt. In this manner, each processor that detects another processor's attempt can delay its own attempt at exclusive access.
A system operation in accordance with Fischer's algorithm never deadlocks, but safety is compromised if the timing constraints are not met. As such, to guarantee safety requires increasing the race wait delay to be at least as long as the longest foreseeable access latency experienced by the storage subsystem. This is an impractical burden in many applications and makes the system difficult to scale when such scaling results in access latency that violates the race wait delay assumed by the algorithm.
Solutions that do not depend on timing constraints suffer from potential deadlock when a race exists between two processors. An example of such a solution is the Fast Mutual Exclusion Algorithm, described by Leslie Lamport, in ACM Transactions on Computer Systems, Vol. 5, No. 1, February 1987, Pages 1-11.
Another class of solutions rely on particular properties of the shared storage interconnects. For example, SCSI disk subsystems can use the “SCSI Reserve” and “SCSI Unreserve” semantics to provide exclusive access to a disk. These types of solutions are not ideal because they narrowly apply to a particular disk subsystem and do not extend or scale to alternate storage subsystems.
Accordingly, need exists for a system and method for providing exclusive access to shared storage that does not rely on advance knowledge of the set of processors potentially accessing the shared storage. Furthermore, need exists for an exclusive access solution that accommodates competing processors without deadlock, accommodates the unpredictable timing properties of a shared storage subsystem, and does not rely on particular properties of any particular shared storage subsystem.
SUMMARY OF THE INVENTION
Briefly stated, the present invention involves a system and method for providing exclusive access to a shared storage location by a selected processor in a system having multiple processors. The shared storage location is associated with first and second critical storage blocks. A processor identifier associated with the selected processor is stored in the first critical storage block.
It is an advantage of an embodiment of the present inv
Gafni Eliezer
Lamport Leslie
Reuter James M.
Compaq Computer Corporation
Hogan & Hartson LLP
Kubida William J.
Thai Tuan V.
LandOfFree
System and method for exclusive access to shared storage does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for exclusive access to shared storage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for exclusive access to shared storage will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546411