Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2001-09-28
2004-02-17
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S151000, C711S163000
Reexamination Certificate
active
06694411
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to processor-based devices and, more particularly, to a technique for implementing a lock that controls access to a shared resource accessible by a plurality of requesters in a processor-based device.
2. Background of the Related Art
This section is intended to introduce the reader to various aspects of art which may be related to various aspects of the present invention which are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
The use of computers has increased dramatically over the past few decades. In years past, computers were relatively few in number and primarily used as scientific tools. However, with the advent of standardized architectures and operating systems, computers soon became virtually indispensable tools for a wide variety of business applications. The types of computer systems similarly have evolved over time. For example, early scientific computers typically were stand-alone systems designed to carry out relatively specific tasks and required relatively knowledgeable users.
As computer systems evolved into the business arena, mainframe computers emerged. In mainframe systems, users utilized “dumb” terminals to provide input to and to receive output from the mainframe computer while all processing was done centrally by the mainframe computer. As users desired more autonomy in their choice of computing services, personal computers evolved to provide processing capability on each user's desktop. More recently, personal computers have given rise to relatively powerful computers called servers. Servers are typically multi-processor computers that couple numerous personal computers together in a network. In addition, these powerful servers are also finding applications in various other capacities, such as in the communications and Internet industries.
In many servers, multiple requesters (e.g., software threads, processors, hardware, etc.) may contend for access to shared resources, such as memory. Each time a requester accesses memory, it is likely that the contents of a memory location will be altered. Thus, care must be taken in a system that provides for concurrent access to a shared resource to ensure that a requester is accessing valid data. In addition to problems arising from concurrent requests, a requester that has control of the resource may be interrupted, thus providing yet further opportunity for another requester to alter the contents of the shared resource. Without some sort of scheme to govern requests for access to a shared resource, data processing errors or unrecoverable faults may occur.
In many systems, multiple requests to a shared resource are governed by an arbitration scheme which grants only one requester at a time access to a shared resource. The arbitration scheme typically results in a lock being placed on the critical region of the shared resource such that the other requesters are blocked until the current requester has completed the operation and released the lock. Such arbitration schemes become less effective as the number of requesters increases, as each requester must wait its turn to access the resource. Further, because the acts of acquiring and releasing the lock may result in communications being transmitted to each of the other waiting requesters, consumption of bus bandwidth and latency increase. Thus, these arbitration schemes may not readily scale to execution environments in which a large number of concurrent requests to a shared resource are possible.
In many known arbitration schemes, a lock to a particular shared resource typically is implemented as a memory location in the memory subsystem of the server or other processor-based device. To acquire ownership of the lock, a requester examines the appropriate field in the memory location to determine whether ownership of the lock is available. For instance, the memory location for implementing the lock may include a lock bit that is set (i.e., set to a logical “1” state) when the lock is owned and cleared (i.e., set to a logical “0” state) when the lock is available. If the lock is available, the requester sets the lock bit to the owned state and acquires the lock. However, because a variable in the memory location is altered when the requester acquires the lock, a communication must be sent to all requesters who have access to that memory location and, thus, a cache memory line that may be affected by the change.
While the lock is owned, each of the waiting requesters repeatedly examines the state of the lock bit to determine whether the lock has been released. When the lock is released, ownership of the lock is acquired by the first waiting requester that happens to reach the lock bit. Thus, passing of the ownership of the lock may not be performed in a particularly fair manner between waiting requesters having the same priority. Further, release of the lock involves changing the state of the lock bit, which again results in a communication that is sent to all requesters having access to the memory location.
Thus, known techniques for implementing a lock for a shared resource are not particularly efficient when utilized in a processor-based device in which a large number of requesters have access to the shared resource. The acts of acquiring and releasing the lock generate a great deal of traffic on the bus, thus having a detrimental effect on latency. Further, the act of passing ownership of the lock to another waiting requester is not necessarily implemented in a fair manner, thus creating uncertainty as to when a particular requester may acquire the lock.
Accordingly, it would be desirable to provide a scheme for arbitrating a lock on a shared resource that would minimize the number of communications transmitted on the bus when the lock is acquired and released. Such a scheme would be particularly useful in which a large number of requesters are contending for access to the shared resource. Further, the scheme would facilitate distributing ownership of the lock in a fair manner.
The present invention may be directed to addressing one or more of the problems set forth above.
REFERENCES:
Andrew S. Tanenbaum and Albert S. Woodhull, Operating Systems: Design and Implementation, Prentice Hall, Second Edition, pp. 59-68.*
Thomas E. Anderson, “The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors,” IEEE Transactions on Parallel and Distributed Systems, vol. 1, No. 1, Jan. 1990.
John M. Mellor-Crummey1and Michael L. Scott2, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors,” ACM Transactions on Computer Systems, Feb. 1991.
Ingo Molnar, “Re: possible spinlock optimizations,” pp. 1-2, Sep. 28, 1999.
Mark Russinovich, “Inside Win2K Scalability Enhancements, Part 2, ” 11 pages, Dec. 1999.
Mark Russinovich, “Win2K Queued Spinlocks,” pp. 1-2, date unknown.
Hewlett--Packard Development Company, L.P.
Inoa Midys
Padmanabhan Mano
LandOfFree
Technique for implementing a distributed lock in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technique for implementing a distributed lock in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for implementing a distributed lock in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335923