Sequentially performed compound compare-and-swap

Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C711S141000, C711S152000, C711S165000, C712S225000, C712S244000

Reexamination Certificate

active

07890722

ABSTRACT:
A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2is invalid and the contents of memory address A1are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.

REFERENCES:
patent: 3886525 (1975-05-01), Brown et al.
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4604694 (1986-08-01), Hough
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5081572 (1992-01-01), Arnold
patent: 5222238 (1993-06-01), Zobre et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5870537 (1999-02-01), Kern et al.
patent: 5893151 (1999-04-01), Merchant
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6223335 (2001-04-01), Cartwright, Jr. et al.
patent: 6718446 (2004-04-01), Peters et al.
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86/00434 (1986-01-01), None
U.S. Appl. No. 09/710,218, filed Nov. 10, 2000 and naming as inventor(s) Harris, Timothy.
Bacon, David F. et al., “Thin Locks: Featherweight Synchronization for Java,” ACM SIGPLAN Notices, vol. 33, No. 5, pp. 258-268, May 1998.
Israeli, Amos et al., “Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives,”Proc. 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 151-160, ACM Press, New York, NY, 1994.
Lamport, Leslie, “A Fast Mutual Exclusion Algorithm,”ACM Transactions on Computer Systems, vol. 5, No. 1, pp. 1-11, 1987.
Mellor-Crummey, J., et al., Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors,ACM Transactions on Computer Systems, vol. 9, No. 1, pp. 21-65, Feb. 1991.
Moir, Mark, “Practical implementation of non-blocking synchronization primitives,”Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 219-228, ACM Press, New York, NY, 1997.
Moir, Mark, “Transparent Support for Wait-Free Transactions,”Proceedings of the 11th International Workshop on Distributed Algorithms, pp. 305-319, Springer-Verlag, London, UK, 1997.
Shavit, N., et al., “Software Transactional Memory,”Distributed Computing, vol. 10, No. 2, pp. 99-116, Feb. 1997.
IBM Technical Disclosure Bulletin, “Conditional Multiple Store Instruction”, vol. 22, No. 9, pp. 4297-4299, Feb. 1, 1980.
Bershad, B. N., “Practical Considerations For Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273. IEEE Computer Society Press, Washington, D.C., 1993.
Attiya, H., et al., “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, New York, NY, 1996.
Greenwald, M. B., et al., “The Synergy Between Non-Blocking Synchronization and Operating System Structure,”Proceedings of the 2nd Symposium on Operating Systems Design And Implementation, pp. 123-136, Usenix Association, Berkeley, CA, 1996.
Afek, Y., et al., “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997. Santa Barbara, CA.
Arora, N. S., et al., “Thread Scheduling For Multiprogrammed Multiprocessors,”Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, ACM Press, New York, NY, 1998.
Attiya, Hagit, et al., “Atomic Snapshots In O(n log n) Operations,”SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
Agesen, Ole, et al.: “DCAS-Based Concurrent Deques,”SPAA 2000. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 137-146, ACM Press, New York, NY, ISBN: 1-58113-185-2, 2000.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Sequentially performed compound compare-and-swap does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sequentially performed compound compare-and-swap, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequentially performed compound compare-and-swap will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2626402

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.