Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
2000-02-29
2003-05-20
Dharia, Rupal (Department: 2189)
Electrical computers and digital data processing systems: input/
Access arbitrating
C709S241000
Reexamination Certificate
active
06567873
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention pertains to improving multi-processor performance in which the various processors compete for spinlock acquisition, and in particular, to optimizing a processor's spinlock acquisition as it competes with other processors to access a shared resource.
In a multi-processor system, several processors typically compete for shared resources, such as memory and Input/Output (I/O) devices. Competition (or contention) occurs when two or more processors attempt to access a shared resource at a given time. To maintain data coherency (i.e., to prevent data from becoming corrupt), only one processor usually gains access to the resource while the other competing processors are excluded until the accessing processor is done with the resource. Resources are shared on the multi-processor system to maximize their usage and further economize the system. In addition, by sharing a resource, a task may be segmented and cooperatively processed by the several processors. This effectively accelerates the task's processing time when compared with a uni-processor system. Sharing of resources is made possible by a multi-tasking operating system that allows the several processors to operate in parallel. In theory, each additional processor multiplies the performance of the system. For example, an eight-processor system may theoretically increase the performance by eight fold over a uni-processor system. However, because of various factors including processor competition and processor synchronization, performance degradation usually occurs.
Take for instance a shared memory system. Unless there is an orderly system for accessing a shared memory, there is a likelihood that two or more processors may modify the same area of the memory simultaneously, resulting in the stored data becoming corrupt. To prevent this, a multi-processor system may use one or more locking mechanisms to control access to the shared memory. In one known method, each processor keeps a status list of all the locks associated with the memory segments. To keep the status list consistent, each lock/unlock action of a processor causes a message to be transmitted to all the other processors so that they may update their lists. Thus, by inquiring its status list before a memory access operation, a processor is able to determine which memory segments are locked/unlocked.
For example, if the memory segment a processor attempts to access is currently locked, the processor may enter a wait mode. On receiving an unlock message for the memory segment, the processor transmits a lock message that locks the segment and enables the processor to gain access to the resource. In another method, a special processor instruction to access a memory segment causes other processors to be locked out at the instruction level for that particular memory segment. This special instruction is available to the multi-processor system, which instructs the operating system to perform the lock-out. While such elaborate schemes may ensure orderly access to the shared memory, such schemes require substantial overhead and add complexity to the system. Moreover, because each processor needs to be synchronized for an access operation, this results in a detriment to the overall multi-processing performance and also prolongs memory access operations.
In another known method, processor requests for memory access are organized according to a queuing scheme that ensures sequential consistency. However, implementation of such a scheme requires a substantial overhead on behalf of the operating system. More importantly, because of the first in first out (FIFO) nature of the queue, subsequent processor memory requests are biased over those requests already in the queue. When congestion arises in the queue, unacceptable delays occur on the subsequent requests which degrade the overall performance of the system.
Spinlocks (sometimes referred to as “semaphores”) are mechanisms that allow for an orderly access to a shared resource such as a memory. The shared memory system typically contains a number of spinlocks that controls access to the memory. For example, a spinlock may ensure that only one processor is accessing a segment of the memory at any given time. Each segment of the memory has a spinlock associated with it and whenever a processor requires access to a segment, it determines whether the spinlock is “locked” or “unlocked.” A lock status of the spinlock indicates that another processor is currently accessing that segment of the memory. Conversely, an unlocked status indicates that the segment is available for access. For example, when a processor attempts to access a memory segment, regardless of the status of the other processors, it simply tests the spinlock associated with the segment to determine whether that segment is already being accessed by another processor. If not, the testing processor acquires and locks the spinlock to exclude other processors from accessing the segment. The processor then performs one or more operations on the data contained in the segment. Because the accessing processor has locked the spinlock, the processor is able to perform the various operations without interference from the other processors. Once the processor has completed its access, it unlocks the spinlock to allow access by other processors.
Generally, processors that access a particular segment at the same time compete for acquisition of the spinlock. Processors that fail to gain access typically wait for a period of time before re-attempting access. This is generally performed by causing the processor to enter into a finite loop (i.e., the processor “spins,” hence, spinlock). A waiting processor continuously tests the spinlock until it gains access. One problem associated with a waiting processor continuously testing the spinlock is that, as the number of processors competing for the spinlock increases, severe memory contention arises. This, in turn degrades overall system performance. Accordingly, what is needed is a way to reduce spinlock access contentions and to increase multi-processing performance.
SUMMARY OF THE INVENTION
The present invention comprises a method and apparatus for optimizing acquisition of a spinlock by a processor in a multi-processor system when various processors compete for spinlock acquisition. According to the invention, if a processor fails to acquire the spinlock, it reattempts access of the lock after waiting a period of time. Here, the wait period is preferably a relatively small wait period If the spinlock is still locked when the processor reattempts access, the wait period is incremented a predetermined amount. Subsequent unsuccessful attempts to access the spinlock progressively increase the wait period until a maximum wait period is reached. At this point, the wait period is reset to its initial small wait interval and the procedure is repeated until the processor gains access to the spinlock.
REFERENCES:
patent: 5729765 (1998-03-01), Cheng
patent: 5864699 (1999-01-01), Merryman
patent: 6314485 (2001-11-01), Potts
Bertsekas et al., Data Networks, Second Edition, 1992, 1987, Prentice-Hall, Inc.
J. F. Hayes,An Adaptive Technique for Local Distribution,Copyright © 1978 IEEE.
R. L. Rivest,Network Control by Bayesian Broadcast,Massachusetts Institute of Technology, Sep. 1985.
J. I. Capetanakis,The Multiple Access Broadcast Channel: Protocol and Capacity Considerations,Massachusetts Institute of Technology, Aug. 1977.
Dharia Rupal
Huynh Kim T.
Novell Inc.
Schwegman, Lundberg, Woessman & Kluth, P.A.
LandOfFree
Spinlock with adaptive delay does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spinlock with adaptive delay, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spinlock with adaptive delay will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3059833