Electrical computers and digital data processing systems: input/ – Access locking
Reexamination Certificate
1999-05-14
2002-03-05
Thai, Xuan M. (Department: 2757)
Electrical computers and digital data processing systems: input/
Access locking
C710S220000, C710S240000, C711S147000, C711S154000
Reexamination Certificate
active
06353869
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to a method and apparatus for improving performance in systems where multiple processors contend for control of a shared resource through a queued lock associated with the shared resource, and more particularly to a method and apparatus for improving performance in intelligent data storage systems.
BACKGROUND OF THE INVENTION
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 than might be used by multiple requestors.
Many high-performance storage systems are intelligent data storage systems which may be accessible by multiple host computers. These 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, typically include at least one shared resource in the form of a global memory which is coupled to each of 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 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.
To provide reliable access by any host over any host channel to any of the data stored in the data storage devices, it is necessary to coordinate all of the host and device controllers in the system with each other. To simplify this coordination, the global memory is used as a buffer for data transfer between each host controller and each disk controller. Such systems are described, for example, in Yanai et al, U.S. Pat. No. 5,206,939 issued Apr. 27, 1993, (hereinafter “the '939 patent”), Yanai et al, U.S. Pat, No. 5, 381,539 issued Jan. 10, 1995, (hereinafter “the '539 patent”), Vishlitzky et al, U.S. Pat. No. 5,592,432 issued Jan. 7, 1997, (hereinafter “the '432 patent”), Yanai et al, U.S. Pat. No. 5,664,144 issued Sep. 2, 1997 hereinafter “the '144 patent”), and Vishlitzky et al, U.S. Pat. No. 5,787,473 issued Jul. 28, 1998, (hereinafter “the '473 patent”), all of which are herein incorporated in their entirety by reference. The systems described therein provide for distributed management of the global memory resources by the controllers. In these systems, the consistency of the data contained in some portions of global memory is maintained by allowing each controller to lock those data structures which require consistency while it is performing operations which are supposed to be atomic on them.
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. 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, as described, for example, in
Transaction Processing: Concepts and Techniques
, Jim Gray and Andreas Reuter, Morgan Kaufmann Publishers, 1993 edition;
Operating System Concepts
, Abraham Silberschatz and Peter Baer Galvin, Addison-Wesley, 1998 edition: “Resource Allocation with Immunity to Limited Process Failure”, Michael J. Fischer, Nancv A. Lynch. James E. Burns, and Alan Borodin, 20
th
Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico
, October '79, p 234-254; and “
Distributed FIFO Allocation of Identical Resources Using Small Shared Space”ACM Transactions on Programming Languages and Systems
, January '89, 11(1): 90-114. The lock request queue is a data structure which indicates the current holder of the lock and the priority of unsuccessful lock requests. 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 requestor 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. To minimize resource latency, i.e. “dead” intervals between the time when one processor relinquishes the lock and the next processor obtains it, the polling frequency is typically fixed at a relatively high value. In large systems with high activity, however, high polling rates can saturate communication channels and memory with unproductive calls, thereby seriously degrading the performance of the entire system. In some systems, a separate channel has been dedicated to lock requests in order to avoid these problems. However, this solution has the disadvantage of reducing system throughput by largely eliminating the lock request channel as a resource for productive data transfer within the system.
It would be advantageous therefore to provide a method and apparatus capable of dynamically varying the polling frequencies of multiple unsuccessful requesters in order to reduce both latency and saturation problems without requiring a dedicated lock request channel or otherwise reducing system performance.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus for improving performance in computer systems, and preferably intelligent data storage systems, where a queued lock prioritizes requests for access to a shared resource by contending requesters. In general, the invention provides that when each unsuccessful requestor periodically polls a lock request queue for information on the status of its pending lock request, it obtains information on its priority in the lock request queue and adaptively delays its next poll by a period determined as a function of this priority. In some aspects, the period is also a function of the average duration of a significant operation involving the shared resource. Typically, each unsuccessful requestor estimates, upon each poll, the number of prior entries in the lock request queue and adaptively determines its polling period as a function of the number of prior entries in the lock request queue. In some aspects, the requester may record the duration of one or more of its periodic polls of the lock request queue, and estimate the average duration of a significant processor operation involving the sh
Leneman Tuvia
Ofer Adi
Vishlitzky Natan
EMC Corporation
Gunther John M.
Thai Xuan M.
Wilson Penelope S.
LandOfFree
Adaptive delay of polling frequencies in a distributed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive delay of polling frequencies in a distributed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive delay of polling frequencies in a distributed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2830218