Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1998-10-15
2001-01-09
Bragdon, Reginald G. (Department: 2751)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S153000
Reexamination Certificate
active
06173373
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates in general to the implementation and control of non-blocking queuing techniques for priority queues used in parallel software applications having shared data structure, and more particularly, but not by way of limitation, to a method and apparatus for selectively incrementing count numbers associated with addresses of nodes in free lists and priority queues using concurrent non-blocking queuing techniques.
BACKGROUND OF THE INVENTION
Computer systems are increasingly incorporating multiprocessing architectures which execute parallel software applications that share access to common data structures. Concurrent queues are used in multiprocessing computing environments. To insure “correctness,” concurrent access to shared queues is synchronized. Traditional approaches to synchronizing access to critical regions have incorporated operating system synchronization primitive. These approaches are “blocking” and are not suitable for providing multiprocessor safe synchronization of critical regions between multiple threads of execution in user space (i.e. application software). The blocking characteristic of spinlock methods also reduces software scalability in situations of high contention in critical regions of a multiprocessor environment.
A set of concurrent non-blocking methods which demonstrate good performance over traditional spinlock methods of multiprocessor synchronization have been developed by Maged M. Michael and Michael L. Scott. These methods allow multiple processors to gain concurrent non-blocking access to shared First In First Out (FIFO) queues with immunity from inopportune preemption and are especially useful for parallel software applications requiring shared access to FIFO queues. Furthermore, these methods demonstrate nearly linear scalability under high contention of critical regions in a multiprocessor environment and are incorporated directly in application software. These methods do not affect processor interrupts and do not require spinlock methods to provide mutual exclusion to a shared critical region. These methods are presented and described in greater detail in a publication authored by Maged M. Michael and Michael L. Scott, entitled
“Simple, Fast, and Practical Non
-
Blocking and Blocking Concurrent Queue Algorithms,”
published in the 15th ACM Symposium on Principles of Distributed Computing (PODC), May 1996, which is incorporated herein by reference.
One shortcoming of these queuing methods involves a condition referred to as an “ABA” condition. The “ABA” condition occurs on computing platforms, such as the Intel 486 and the Pentium class lines of processors, which utilize a Compare-And-Swap (CAS) atomic primitive. The “ABA” condition occurs when a process reads a value “A” from a shared memory location, computes a new value and then attempts the CAS operation. In certain circumstances, the CAS operation may succeed when it should have failed. Such a situation arises when, between the memory read and the CAS operation, some other process or processes change the value “A” to value “B” and then back to value “A.” Although the CAS operation succeeds since the value of the shared memory location has returned to value “A,” the value in the memory location to which “A” points may have changed. To reduce the probability of encountering the “ABA” condition, the aforementioned queuing methods implement a sequence or count number as part of node address associated with the shared memory location. The count number is incremented with every successful CAS operation so that a determination can be made as to whether the contents of the shared memory location has been altered. While the use of count numbers reduces the probability of encountering the “ABA” condition, the method falls short on the previously mentioned Intel processors due to the frequent incrementing of the count number which causes the count to wrap around and possibly end up at the original count number. The probability of a wrap around condition occurring is especially likely in high contention situations and increases as the speed of the processor increases and the total number of nodes in the queue decreases.
It would be advantageous therefore, to devise a method and apparatus which selectively increments count numbers associated with nodes in a priority queue to reduce the number of times the count numbers are incremented. Such a method and apparatus would increase the time between the occurrence of wrap around conditions and thereby, reduce the likelihood of encountering an “ABA” condition.
SUMMARY OF THE INVENTION
The present invention overcomes the above identified problems as well as other shortcomings and deficiencies of existing technologies by providing a method and apparatus for selectively incrementing a count number associated with a node which is subject to a compare and swap operation in a concurrent non-blocking priority queue. A memory stores data in multiple nodes residing in at least one of a free list queue and a priority queue. The nodes store both data and references to other nodes within the free list and the priority queue. An address of each node includes a pointer and a count number. Multiple processors access the memory and operate on the multiple nodes, including a compare and swap operation. The count number of a node is selectively incremented only upon a successful compare and swap operation and when a node is placed on a select FIFO list of the priority queue.
REFERENCES:
Stone, Janice, “A Simple and Correct Shared-Queue Algorithm Using Compare-and-Swap”, Proceedings of Supercomputing '90; 12-16 Nov. 1990; pp. 495-504.
Prakash, Sundeep et al., “A Nonblocking Algorithm for Shared Queues Using Compared-and-Swap”, IEEE Transaction on Computers, May 1994; pp. 548-559.
Mendel, Brett; “Server I/O all set to flow”;Lantimes,Oct. 27, 1997, vol. 14, Issue 22; cover page and p. 31.
Briggs, Chris; “Smarter and Faster I/O for Servers”; CORE: Operating Systems;Byte,May 1, 1996, vol. 2, No. 5.
Thompson, Tom; “I2O Beats I/O Bottlenecks”;Byte,Aug. 1997, pp. 85, 86 and 3 additional pages.
I2O Introduction; Technology Backgrounder; Aug. 13, 1997; http://www.i2osig.org/Architecture/TechBack.html.
i960®RP I/O Processor—the I2O SIG site; http://134.134.214.1/design/iio/i2osig.html; Feb. 6, 1998.
“Welcome to the I2O SIG® Web Site!”; http://www.i2osig.org; Feb. 6, 1998.
“About I2O Technology”; http://www.i2osig.org/Architecture; Feb. 6, 1998.
“Technology Backgrounder”, http://www.i2osig.org/Architecture/TechBack.html; Feb. 6, 1998; 6 pages.
“Questions and Answers”; http://www.i2osig.org/Architecture/QandA.html; Feb. 6, 1998; 4 pages.
“I2O® Specifications For Non-Members”; http://www.i2osig.org/Architecture/GetSpec.html; Feb. 6, 1998.
Amdahl, Carlton G.; “I2O Future Directions”; http://www.i2osig.org; Jun. 1996; 12 pages.
Goble, Scott, et al.; “Intelligent I/O Architecture”; http://www.i2osig.org; Jun. 1996; 22 pages.
“Press Releases and Clips”; http://www.i2osig.org/Press; Feb. 6, 1998; 4 pages.
Listing of Press Releases; http://altavista.digital.com/cgi-bin/quer . . . =21%2FMar%2F86&d1=&search.x=46&search.y=6; Feb. 6, 1998; 2 pages.
Crothers, Brooke; “Intel server chip gets big backing”, Oct. 7, 1997; http://www.news.com/News/Item/0,4,14962,00.html; Feb. 6, 1998.
“HP Demonstrates Commitment to I2O Standard With New I2O Disk-array Controller”;Hewlett Packard;Press Release, Atlanta, Oct. 8, 1997; http://hpcc920.external.hp.com/pressre1/oct97/08oct97b.html; Feb. 6, 1998; 2 pages.
“I2O: Disaster in the making for the freeware community”; Stephen S. Edwards; http://22.kenandted.com/i2o/disaster.html; Feb. 6, 1998; 2 pages.
Michael, Maged M. and Scott, Michael L.; “Simple Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”; Parallel Processing Symposium, 1997.Proceedings. Apr. 1997; pp. 267-273.
Michael, Maged M. and Scott, Michael L.; “Relative Performance of Preemption-Safe Locking and Non-Blocking Synchronization on Multiprogrammed Shared Memory Multiprocessors”; Proceedin
Bragdon Reginald G.
Compaq Computer Corporation
Fletcher Yoder & Van Someren
LandOfFree
Method and apparatus for implementing stable priority queues... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing stable priority queues..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing stable priority queues... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2537332