Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-20
2003-06-10
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06578033
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of computer systems and, more particularly, to systems and methods of optimizing lock operations within computer systems.
2. Description of the Related Art
Computer systems can suffer severe performance degradation as a result of lock operations. In general, lock operations are associated with software locks which are used by computer systems to ensure that only one process at a time can access a resource, such as a critical region of memory. Throughout this specification, a memory region is used as an example of a resource associated with a lock. It is noted that the disclosed invention is equally applicable to other resources, such as an input/output location. A variety of locks have been implemented, ranging from simple spin-locks to advanced queue-based locks. Although simple spin-lock implementations can create very bursty traffic as described below, they are still the most commonly used software lock within computer systems.
Systems employing locks typically require that a given process perform an atomic operation to obtain access to a critical memory region. For example, an atomic test-and-set operation is commonly used. Generally speaking, an atomic operation is an indivisible operation. In other words, another process cannot access the lock between the test and set portion of the atomic operation. The test-and-set operation is performed to determine whether a lock bit associated with the memory region is cleared and to atomically set the lock bit. That is, the test allows the process to determine whether the memory region is free of a lock by another process, and the set operation allows the process to acquire the lock if the lock bit is cleared.
Referring now to
FIG. 1
, a diagram illustrating a spin-lock implementation is shown. In a spin-lock implementation, if the test of the lock bit indicates that the memory region is currently locked, i.e. another process has acquired the lock, the requesters for the lock initiate a loop wherein the lock bit is continuously read until the lock bit is cleared, at which time the process reinitiates the atomic test-and-set operation. Generally speaking, requesters are processes or other entities that seek to acquire the lock. Spin-locks may be implemented using either optimistic or pessimistic spin-lock algorithms. An optimistic spin-lock is depicted by the following algorithm:
top:
atomic_test&set
;read-to-own transaction
if failed
begin
while busy spin
;spin on read-to-share transaction
goto top
end
For the optimistic spin-lock algorithm shown above, the process first performs an atomic test-and-set operation upon the lock bit corresponding to the memory region for which access is sought. If the atomic test-and-set operation fails, the process reads the lock bit in a repetitive fashion until the lock bit is cleared by another process. The process then reinitiates the atomic test-and-set operation. Generally speaking, a read-to-own (RTO) transactions requests write access to data and a read-to-share (RTS) transaction requests read access to data. It is noted that names other than RTO and RTS may be used to describe the concepts of acquiring read and write access to data.
A pessimistic spin-lock is depicted by the following algorithm:
top:
while busy spin
; spin on read-to-share
atomic_test&set
; read-to-own
if failed
begin
goto top
end
For the pessimistic spin-lock algorithm, the process first reads the lock bit corresponding to the memory region for which access is sought in a repetitive fashion until the lock bit is cleared. When the process determines that the lock bit is clear in accordance with the read operation(s), the process performs an atomic test-and-set operation to lock and gain access to the memory region. If the test failed upon execution of the atomic test-and-set operation, the process again repetitively reads the lock bit until it is cleared.
In a shared memory computer system in which the requester performs a system bus, or global, transaction to test and set the lock, the above spin-lock algorithms create a large number of bus transactions. If the lock is not available, each requester attempting to acquire the lock bit continually performs global transactions until the lock becomes available. This large number of global transactions may adversely affect the performance of the computer system by using a large portion of the available bandwidth.
To reduce the number of global transactions performed by a spin-lock algorithm, the lock bit may be cached by each requester attempting to acquire it. In this manner, the repetitive reads to determine the state of the lock bit may be local transactions rather global transactions. While this may reduce the number of global transactions, the coherency traffic on the bus generated when the state of the lock bit changes may be unacceptable.
In a cached shared memory system, the read (or test) of the lock bit is treated as a read-to-share (RTS) operation. Since the atomic test-and-set operation includes a write, it is treated as a read-to-own (RTO) operation. The system will thus place the coherency unit containing the lock bit in a modified state in response to the atomic test-and-set operation.
For both the pessimistic and optimistic algorithms discussed above, when a memory region corresponding to a contended spin-lock is released, the owner writes to the lock to free it generating a RTO operation (1 bus transaction) which invalidates the line in the caches of all other devices. Therefore, all N spinning requesters subsequently miss and generate RTS transactions for the cache line containing the lock. The first requester to receive a data reply detects the free lock and generates an RTO transaction (1 bus transaction). Since the requester of each of the remaining RTS requests similarly receive an indication that the lock is free, each of these requesters also generates a RTO transaction (N−1 bus transactions). When the first RTO transaction is received, the requester issuing that transaction locks and gains access to the memory region. The test-and-set operations corresponding to the RTO requests of the remaining requesters therefore fail. The remaining N−2 requesters generate RTS transactions to cache the new lock bit (N−2 bus transactions).
Thus, the total number of transactions is potentially 3N−1 for the single transfer of a spin-lock from one requester to another (where N is the number of contenders for the lock). Due to this large number of transactions, the latency associated with the release of a lock until the next contender can acquire the lock is relatively high. The large number of transactions can further limit the maximum frequency at which ownership of the lock can migrate from node to node. Finally, since only one of the spinning requesters will achieve the lock, the failed test-and-set operations of the remaining processors result in undesirable RTO requests on the network. The coherency unit in which the lock is stored undesirably migrates from requester to requester, invalidating other copies. Network traffic is thereby further increased despite the fact that the lock is set.
Several lock designs to improve the performance of spin-locks have been devised, such as back-off locks and queue locks. In back-off locks, the requesters contending to acquire the lock implement a delay between attempts to acquire the lock. In this manner, the number of requesters contending for the lock at a given instance of time is reduced. The lock may be released and acquired by another requester before some requesters detect that the lock has been freed. Accordingly, the number of processes that attempt to acquire the lock when it becomes available is reduced. Low contention for the lock reduces the number of transactions when the lock changes state. The requesters that do not contend for the lock will generate a read-to
Hagersten Erik
Singhal Ashok
Kivlin B. Noäl
Metjahic Safet
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Nguyen Cam-Linh T.
Sun Microsystems Inc.
LandOfFree
System and method for accessing a shared computer resource... 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 accessing a shared computer resource..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for accessing a shared computer resource... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3151532