Electrical computers and digital processing systems: interprogra – Interprogram communication using shared memory
Reexamination Certificate
2007-02-27
2007-02-27
Bullock, Jr., Lewis A. (Department: 2195)
Electrical computers and digital processing systems: interprogra
Interprogram communication using shared memory
C719S314000, C718S100000, C707S793000
Reexamination Certificate
active
09976930
ABSTRACT:
A method for executing operations upon a linked data structure having at least one element such that the time during which the linked data structure is locked is reduced. The method includes performing a first set of operation tasks in a first phase, the first set of operation tasks being operable to effect a first set of element state transitions. A second set of operation tasks is developed in the first phase, the second set of operation tasks being operable to effect a second set of element state transitions, the second set of element state transitions being distinct from the first set of element state transitions. The second set of operation tasks is performed in a second phase. The method finds particular implementation in the rebalancing of tree data structures.
REFERENCES:
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5222238 (1993-06-01), Zobre et al.
patent: 5781910 (1998-07-01), Gostanian et al.
patent: 6868414 (2005-03-01), Khanna et al.
patent: 466339 (1992-01-01), None
Farook, Mohammad et al. “Managing Long Linked Lists using Lock Free Techniques.” University of Manitoba, Canada. Oct. 1998.
Prakash, Sundeep et al. “Non-Blocking Algorithms for Concurrent Data Structures.” Dept. of Computer and Information Sciences, University of Florida. Jul. 1, 1991.
Prakash, Sundeep et al. “A Non-Blocking Algorithm for Shared Queues Using Compare-and-Swap.” IEEE. May 1994.
Volois, John D. “Lock-Free Linked Listss Using Compare-and-Swap.” ACM. 1995.
Michael, Maged M. et al. “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”. ACM 1996.
Stone, Janice M. “A Simple and Correct Shared Queue Algorithm using Compare-and-Swap.” IEEE. 1990.
IBM Technical Disclosure Bulletin. “Serialization of AVL-Binary Tree Element Retrieval via Duplexed Pointers.” Mar. 1992.
Baer et al., “A Comparison of Tree-Balancing Algorithms,” Communications of the ACM, vol. 20, Issue 5, pp. 322-330 (May 1977).
Cannady, “Balancing Methods for Binary Search Trees,” Proceedings of the 16th Annual ACM Southeast Regional conference, pp. 181-186 (1978).
Ants Software, Inc.
Bullock, Jr. Lewis A.
Carr & Ferrell LLP
LandOfFree
Multiphase system and method of performing operations on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiphase system and method of performing operations on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiphase system and method of performing operations on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3881294