Data processing: database and file management or data structures – Organization of data – Object-oriented
Reexamination Certificate
2011-05-31
2011-05-31
Al-Hashemi, Sana (Department: 2156)
Data processing: database and file management or data structures
Organization of data
Object-oriented
C707S791000, C707S795000, C707S802000, C707S807000, C707S823000
Reexamination Certificate
active
07953778
ABSTRACT:
A method, system and computer program product for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions. Two or more updaters may be invoked to generate new group data elements. Each new data element created by the same updater is assigned a new generation number that is different than a global generation number associated with the data element group and which allows a reader of the data element group to determine whether the new data element is a correct version for the reader. The new generation numbers are different for each updater and assigned according to an order in which the updaters respectively begin update operations. The global generation number is updated so that when all of the updaters have completed data element update processing, the global generation number will correspond to the new generation number that is associated with the last of the updaters to begin update operations.
REFERENCES:
patent: 5442758 (1995-08-01), Slingwine et al.
patent: 5608893 (1997-03-01), Slingwine et al.
patent: 5727209 (1998-03-01), Slingwine et al.
patent: 5905990 (1999-05-01), Inglett
patent: 6219690 (2001-04-01), Slingwine et al.
patent: 6662184 (2003-12-01), Friedberg
patent: 6886162 (2005-04-01), McKenney
patent: 6920469 (2005-07-01), Cooke et al.
patent: 6996812 (2006-02-01), McKenney
patent: 7013289 (2006-03-01), Horn et al.
patent: 7353346 (2008-04-01), McKenney et al.
patent: 2001/0003189 (2001-06-01), Miyazawa et al.
patent: 2005/0149634 (2005-07-01), McKenney
patent: 2005/0198030 (2005-09-01), McKenney
patent: 2006/0090104 (2006-04-01), McKenney et al.
patent: 2006/0100996 (2006-05-01), McKenney
patent: 2006/0112121 (2006-05-01), McKenney et al.
patent: 2006/0117072 (2006-06-01), McKenney
patent: 2006/0123100 (2006-06-01), McKenney
patent: 2006/0130061 (2006-06-01), McKenney et al.
patent: 2006/0265373 (2006-11-01), McKenney et al.
patent: 2007/0083565 (2007-04-01), McKenney
patent: 2007/0101071 (2007-05-01), McKenney
patent: 2007/0226440 (2007-09-01), McKenney et al.
patent: 2007/0266209 (2007-11-01), McKenney et al.
patent: 2008/0033952 (2008-02-01), McKenney et al.
patent: 2008/0040720 (2008-02-01), McKenney et al.
patent: 2008/0082532 (2008-04-01), McKenney
patent: 2008/0120129 (2008-05-01), Seubert et al.
patent: 2008/0177994 (2008-07-01), Mayer
J. Seigh, “RCU + SMR for preemptive kernel/user threads,” Linux Kernel Mailing List, May 9, 2005, 2 pages.
M. Michael, “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects,” IEEE Transactions on Parallel and Distributed Systems, Jun. 2004, vol. 15, No. 6, pp. 491-504.
D. Samna et al., “Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications,” 2004 USENIX (UseLinux track) Jun. 2004, 9 pages.
P. McKenney, “RCU vs. Locking Performance on Different CPUs,” 2004 Linux.conf.au, 2004, 18 pages.
P. McKenney et al., “Scaling dcache with RCU,” Linux Journal, Jan. 1, 2004, 12 pages.
P. McKenney et al., “Using RCU in the Linux 2.5 Kernel,” Llnux Journal, Oct. 1, 2003, 11 pages.
P. McKenney et al.,“Read-Copy Update,” 2002 Ottawa Linux Symposium, Jul. 8, 2002, 28 pages.
H. Linder et al., “Scalability of the Directory Entry Cache,” 2002 Ottawa Linux Symposium, Jun. 26, 2002, pp. 289-300.
P. Mckenney et al., “Read-Copy Update,” 2001 Ottawa Linux symposium, Jul. 2001, 22 pages.
P. McKenney et al., “Read-Copy Update: Using Execution History to Solve Concurrency Problems,” PDCS, Oct. 1998, 11 pages.
S. Dietrich et al., “Evolution of Real-Time Linux,” 7th RTL Workshop, Nov. 17, 2005, 18 pages.
B. Gamsa, “Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System,” 1999, 14 pages.
Molnar et al., “Realtime and Linux,” 2005 Linux Kernel Summit, 8 pages.
H. Boehm, “The Space Cost of Lazy Reference Counting,” ACM SIGPLAN Notices, Proceedings of the 31st ASM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '04, vol. 39, Issue 1, Jan. 2004, p. 210-219.
M. Michael, “Scalable Lock-Free Dynamic Memory Allocation,” ACM SIGPLAN Notices, Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation; PLDI '04, vol. 39, Issue 6, Jun. 2004, p. 35-46.
D. Dice et al., “Mostly Lock-Free Malloc,” ACM SIGPLAN Notices, Proceedings of the 3rd International Symposium on Memory Management, ISMM '02, vol. 38, Issue 2 Supplement, Jun. 2002, p. 163-174.
J. Corbet, “Read-copy-update for realtime,” LWN.net, Sep. 26, 2006, 3 pages.
“Priority Inversion,” Wikipedia, Feb. 4, 2007, 3 pages.
McKenney, “Seven real-time Linux approaches (Part C)”, LinuxDevices.com, Jun. 7, 2005, 13 pages.
P. McKenney, “RCU and CONFIG—PREEMPT—RT progress,” Linux Kernel Mailing List, May 9, 2005, 2 pages.
O. Nesterov, QRCU: ‘Quick’ SRCU Implementation, Linux Kernel Mailing List, Dec. 1, 2005, 3 pages.
T. Gleixner, “High Resolution Timers/Dynamic Ticks-V2”, LWN.net, Oct. 1, 2006, 6 pages.
P. Mckenney, “Sleepable RCU”, LWN.net, Oct. 9, 2006, 10 pages.
O. Nesterov, “cpufreq—tsc() as core—initcall—sync”, LKML.org, Nov. 19, 2006, 2 pages.
P. McKenney, “Using RCU in the Linux 2.5 Kernel”, Kernel Korner, Oct. 1, 2003,11 pages.
A. Kleen, “How to do nothing efficiently or better laziness: No Idle tick on x86-64”, 2005, 16 pages.
P. McKenney, “Read-Copy Update Implementations”, 2001, 3 pages.
C. Boehm et al', “Searching in High-Dimensional Spaces-Index Structures for Improving the Performance of Multimedia Databases,” ACM Computing Surveys, vol. 33, No. 3, Sep. 2001, pp. 322-373.
T. Johnson et al., “Lazy Updates for Distributed Search Structure,” ACM O-89791-k92k1931000510337, 1993, pp. 337-346.
J. Zobel et al., “Inverted Files for Text Search Engines,” ACM Computing Surveys, vol. 38, No. 2, Article 6, Jul. 2006, pp. 1-56.
M. Herlihy, “A Methodology For Implementing Highly Concurrent Data Objects,” ACM Transactions on Programming Languages and Systems, vol. 15, Issue 5, Nov. 1993, pp. 745-770.
M. Michael, “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes,” Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, Jul. 2002, 10 pages.
N. Barghouti et al, “Concurrency Control in Advanced Database Operations,” Jan. 1994, 83 pages.
P. McKenney, “Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels,” OGI School of School of Science & Engineering at Oregon Health & Science University, Jul. 2004, pp. 1-380.
P. McKenney et al., “Extending RCU for Realtime and Embedded Workloads,” 2006 Ottawa Linux Symposium, Aug. 11, 2006, 15 pages.
P. McKenney, “The design of preemptible read-copy-update,” LWN.net, Oct. 8, 2007, 27 pages.
McKenney Paul E.
Walpole Jonathan
Al-Hashemi Sana
Duft Walter W.
International Business Machines - Corporation
LandOfFree
Efficient support of consistent cyclic search with read-copy... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient support of consistent cyclic search with read-copy..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient support of consistent cyclic search with read-copy... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2668863