When a computer system resource is shared by multiple processes running on multiple processors, or even on one processor, often there must be some way of insuring that no more than one such process may access that resource at any one time. In designing complex data storage systems including multiple processors, synchronizing access to shared resources has been recognized as an issue which must be addressed in order to maintain the consistency and validity of the data. However, the sharing issue may arise in connection with almost any resource that might be used by multiple requesters.
Many high-performance storage systems are intelligent data storage systems which may be accessible by multiple host computers. These intelligent data storage systems may include, in addition to one or more storage device arrays, a number of intelligent controllers for controlling the various aspects of the data transfers associated with the storage system. In such systems, host controllers may provide the interface between the host computers and the storage system, and device controllers may be used to manage the transfer of data to and from an associated array of storage devices (e.g. disk drives). Often, the arrays may be accessed by multiple hosts and controllers. In addition, advanced storage systems, such as the SYMMETRIX® storage systems manufactured by EMC Corporation of Hopkinton, Mass., generally include a global memory which typically is shared by the controllers in the system. The memory may be used as a staging area (or cache) for the data transfers between the storage devices and the host computers and may provide a communications path which buffers data transfer between the various controllers. Various communication channels, such as busses, backplanes or networks, link the controllers to one another and the global memory, the host controllers to the host computers, and the disk controllers to the storage devices. Such systems are described, for example, in Yanai et al, U.S. Pat. No. 5,206,939 issued Apr. 27, 1993, Yanai et al, U.S. Pat. No. 5,381,539 issued Jan. 10, 1995, Vishlitzky et al, U.S. Pat. No. 5,592,492 issued Jan. 7, 1997, Yanai et al, U.S. Pat. No. 5,664,144 issued Sep. 2, 1997, and Vishlitzky et al, U.S. Pat. No. 5,787,473 issued Jul. 28, 1998, all of which are hereby incorporated herein by reference in their entirety. The systems described therein allow the controllers to act independently to perform different processing tasks and provide for distributed management of the global memory resources by the controllers. This high degree of parallelism permits improved efficiency in processing I/O tasks. Since each of the controllers may act independently, there may be contention for certain of the shared memory resources within the system. In these systems, the consistency of the data contained in some portions of global memory may be maintained by requiring each controller to lock those data structures which require consistency while it is performing any operations on them which are supposed to be atomic.
Typically, synchronization of access to a shared resource, such as the global memory in the systems described above, is accomplished by associating a lock with the resource to permit a processor that obtains the lock to have exclusive access to the resource. Queued lock management allows a processor which initially fails to obtain the lock to queue for subsequent access. Lock management, including the design and operation of lock request queues, is well known in the art. Generally, the lock request queue must be implemented in a section of memory that is also shared, or at least accessible, by all of the processors which might need access to the shared resource, although it need not be on the same media as the shared resource. The procedures which allocate the lock may be centralized or distributed. In the intelligent data processing systems described above, the lock allocation procedures are typically distributed among the various intelligent controllers.
To obtain the lock for a resource, each requester from among the processors, such as one of the controllers, must first invoke a lock allocation procedure to attempt to obtain the lock. If it is not awarded the lock, its request will be entered in the lock request queue in accordance with a predetermined priority algorithm. To determine the status of its request, the requester must poll for the lock over the communication channel which links the two. If the lock is not available, the requester must wait, typically for a predetermined, fixed period, and poll again, repeating the loop until the lock is obtained.
Since locking inherently reduces the parallelism of the system and puts a high load on system resources, locking procedures must be designed with care to preserve system efficiency.