Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2005-04-12
2005-04-12
Kim, Kenneth S. (Department: 2111)
Electrical computers and digital processing systems: processing
Processing control
Branching
C711S141000, C711S145000, C711S152000, C711S155000, C712S225000
Reexamination Certificate
active
06880071
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: 5081572 (1992-01-01), Arnold
patent: 5893151 (1999-04-01), Merchant
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6223335 (2001-04-01), Cartwright, Jr. et al.
patent: 6356983 (2002-03-01), Parks
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86 00434 (1986-01-01), None
Agesen, Ole, et al.: “DCAS-Based Concurrent Deques,” SPAA 2000. 12th Annual ACM Symposium on Parallel Algorithms and Architectures, Bar Harbor, ME, Jul. 9-12, 2000, Annual ACM Symposium on Parallel Algorithms and Architectures, New York, NY: ACM, US, Jul. 9, 2000, XP002172095, ISBN: 1-58113-185-2, pp. 137-146.
Detlefs, David L. et al., “Even Better DCAS-Based Concurrent Deques,” Distributed Computing, 14th International Conference, Oct. 4, 2000, pp. 59-73, XP002172096.
H. Attiya and E. Dagan, “Universal Operations: Unary versus Binary,” Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, Phila., PA, May 23-26, 1996, pp. 223-232.
H. Massalin and C. Pu, “A Lock-Free Multiprocessor OS Kernel,” Technical Report TR CUCS-005-9, Columbia Univ., New York, NY, 1991, 21 pp.
Hagit Attiya and Ophir Rachman, “Atomic Snapshots in O (n log n) Operations,” SIAM Journal on Computing, vol. 27, No. 2, 1998 SIAM, pp. 319-340.
Hagit Attiya et al, “Are Wait-Free Algorithms Fast?”, Journal of the ACM, vol. 41, No. 4, Jul. 1994, pp. 725-763.
M. B. Greenwald and D. R. Cheriton, “The Synergy Between Non-Blocking Synchronization and Operating System Structure,” 2nd Symposium on Operating Systems Design and Implementation, Seattle, WA, Oct. 1996, 14 pp.
M. Herlihy and J.E.B. Moss, “Transactional Memory: Architectural Support for Lock-Free Data Structures,” Technical Report CRL 92/07, Digital Equipment Corp., Cambridge Research Lab. 1992, pp. 289-300.
M. P. Herlihy and J. M. Wing, “Linearizability: A Correctness Condition for Concurrent Objects,” ACM Transactions on Programming Languages and Systems, vol. 12, No. 3, Jul. 1990, pp. 363-492.
Maurice Herlihy, “A Methodology for Implementing Highly Concurrent Data Objects,” ACM Transactions on Programming Languages and Systems, vol. 15, No. 5, Nov. 1993, pp. 745-770.
Maurice Herlihy, “Wait-Free Synchronization,” ACM Transactions on Programming Languages and Systems, vol. 13, No. 1, Jan. 1991, pp. 123-149.
M68000 Family Programmer's Reference Manual, Motorola, Inc., 1992.
MC68020 32-Bit Microprocessor User's Manual, Motorola, Prentice-Hall, 2nd ed., 1986.
MC68030 User's Manual, Motorola, Prentice-Hall, 1989.
M68040 User's Manual. Motorola, Inc., 1990, rev. 1992, 1993.
Michael B. Greenwald, “Non-Blocking Synchronization and System Design,” PhD Thesis, Stanford Univ. Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, Aug. 1999, 260 pp.
N. Shavit and D. Touitou, “Software Transactional Memory,” Distributed Computing, Feb. 1997., vol. 10, No. 2, pp. 99-116, (34 pp.).
Nimar S. Arora et al., “Thread Scheduling for Multiprogrammed Multiprocessors,” Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, Puerto Vallarta Mexico, 1998, pp. 119-129.
The SPARC Architecture Manual, Version 9, Weaver and Germond, (eds.), SPARC International, Prentice Hall, Englewood Cliffs, NJ, 1994.
Yehuda Afek et al, “Disentangling Multi-Object Operations,” Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara CA, 1997, pp. 111-120 (10 pp.).
Anthony LaMarca, “A Performance Evaluation of Lock-Free Synchronization Protocols,” Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, CA, Aug. 14-17, 1994, pp. 130-140.
B. N. Bershad, “Practical Considerations for Non-Blocking Concurrent Objects,” Proceedings of the 13th IEEE Int'l Conf. on Distributed Computing Systems, IEEE Computer Society Press, Los Alamitos, CA, May 1993, 10 pp.
G. Barnes, “A Method for Implementing Lock-Free Shared Data Structures,” Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, Germany, Jun. 1993, pp. 261-270.
Henry Massalin, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” Dissertation submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, New York, NY, online, 1992; pp. 1-149 XP002172093 [retrieved from the Internet on Jul. 13, 2001: web site.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
Agesen Ole
Shavit Nir N.
Steele, Jr. Guy L.
Kim Kenneth S.
Sun Microsystems Inc.
Zagorin O'Brien Graham LLP
LandOfFree
Selective signalling of later reserve location memory fault... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Selective signalling of later reserve location memory fault..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selective signalling of later reserve location memory fault... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3442136