Data processing: database and file management or data structures – Garbage collection – Mark-sweep
Reexamination Certificate
2004-01-05
2010-06-29
Jalil, Neveen Abel (Department: 2165)
Data processing: database and file management or data structures
Garbage collection
Mark-sweep
Reexamination Certificate
active
07747659
ABSTRACT:
A garbage collection system that needs to meet real-time requirements uses an eager read barrier that performs a forwarding operation as soon as a quantity is loaded. The barrier maintains a to-space invariant by including a forwarding pointer in the header of objects to be moved or accessed that normally points to the object itself. However, if the object has been moved, the forwarding pointer points to the new object location. The eager read barrier maintains the registers and stack cells such that the registers and stack cells always point into to-space. Barrier-sinking and common sub-expression elimination are used to minimize the overhead associated with the read barrier.
REFERENCES:
patent: 4989134 (1991-01-01), Shaw
patent: 5355483 (1994-10-01), Serlet
patent: 5687368 (1997-11-01), Nilsen
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 6529515 (2003-03-01), Raz et al.
patent: 6671707 (2003-12-01), Hudson et al.
patent: 6678742 (2004-01-01), Muramatsu et al.
patent: 6836782 (2004-12-01), Fresko et al.
patent: 6874074 (2005-03-01), Burton et al.
patent: 6985976 (2006-01-01), Zandonadi et al.
patent: 7107419 (2006-09-01), Ghemawat et al.
patent: 2003/0126352 (2003-07-01), Barrett
Kelvin D. Nilsen, Cost-Effective Hardware-Assisted Real-Time Garbage Collection, 1994 ACM SIGPLAN Conference on Programming Language Design and Implementation, ftp://ftp.cs.umd.edu/pub/faculty/pugh/sigplan—realtime—workshop—94
ilsen.ps.Z.
Steven M. Donahue, Matthew P. Hampton, Morgan Deters, Jonathan M. Nye, Ron K. Cytron, Krishna M. Kavi, Storage Allocation for Real-Time, Embedded Systems, Lecture Notes in Computer Science, vol. 2211, Jan. 2001, p. 131, http://www.springerlink.com/media/d86tgdpvxj7uvnf79trn/contributions/q/b/d/1/qbd1lfja2ka3bfnh.pdf.
Brooks, R. A. 1984. Trading data space for reduced time and code space in real-time garbage collection on stock hardware. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Texas, United States, Aug. 6-8, 1984). LFP '84. ACM Press, New York, NY, 256-262. DOI=http://doi.acm.org/10.1145/800055.802042.
Huelsbergen et al. A concurrent copying garbage collector for languages that distinguish (im)mutable data. Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (San Diego, California, May 19-22, 1993). PPOPP '93. ACM Press, New York, NY, 73-82. DOI=http://doi.acm.org/10.1145/155332.155340.
Bacon, D. F., Attanasio, C. R., Lee, H. B., Rajan, V. T., and Smith, S. Java without the coffee breaks: a nonintrusive multiprocessor garbage collector. Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation (Snowbird, Utah). PLDI '01. ACM Press, 92-103. DOI=http://doi.acm.org/10.1145/378795.378819.
David F. Bacon, Perry Cheng, V.T. Rajan, The Metronome: A Simpler Approach to Garbage Collection in Real-Time Systems, Lecture Notes in Computer Science, vol. 2889, Oct. 2003, pp. 466-478, http://www.springerlink.com/media/p3d6f5hcbl7rvgef5n2g/contributions/p/a/u/y/pauykwh9gvpkwy4c.pdf.
Bacon, D. F., Cheng, P., and Rajan, V. T. 2003. A real-time garbage collector with low overhead and consistent utilization. Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (New Orleans, Louisiana, Jan. 15-17, 2003). POPL '03. ACM Press, 285-298. DOI=http://doi.acm.org/10.1145/604155.
Bacon, D. F., Cheng, P., and Rajan, V. T. 2003. Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java. SIGPLAN Not. 38, 7 (Jul. 2003), 81-92. DOI=http://doi.acm.org/10.1145/780731.780744.
Nettles, S. and O'Toole, J. 1993. Real-time replication garbage collection. SIGPLAN Not. 28, 6 (Jun. 1993), 217-226. DOI=http://doi.acm.org/10.1145/173262.155111.
Bacon, D. F., Fink, S. J., and Grove, D. Space- and time-efficient implementation of the Java object model. In Proceedings of the Sixteenth European Conference on Object-Oriented Programming (Jun. 2002), B. Magnusson, Ed., vol. 2374 of Lecture Notes in Computer Science, pp. 111--132. http://citeseer.ist.psu.edu/bacon02space.html.
Silberschatz, Galvin, Gagne. Operating Systems Concepts, Sixth Edition. 2003. p. 288, Section 9.4.1, Memory Management, Basic Method.
Tarditi, D., Morrisett, G., Cheng, P., Stone, C., Harper, R., and Lee, P. 1996. TIL: A type-directed optimizing compiler for ML. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation (Philadelphia, Pennsylvania, United States, May 21-24, 1996). PLDI '96. ACM, New York, NY, 181-192.
Appel, A. W. 1989. Simple generational garbage collection and fast allocation. Softw. Pract. Exper. 19, 2 (Feb. 1989), 171-183. DOI=http://dx.doi.org/10.1002/spe.4380190206.
Hosking, A. L., Nystrom, N., Cutts, Q. I., and Brahnmath, K. 1999. Optimizing the Read and Write Barriers for Orthogonal Persistence. In Proceedings of the 8th international Workshop on Persistent Object Systems (Pos8) R. Morrison, M. J. Jordan, and M. P. Atkinson, Eds. Morgan Kaufmann Publishers, San Francisco, CA, 149-159.
Bacon David Francis
Cheng Perry
Rajan Vadakkedathu Thomas
Abel Jalil Neveen
Alexanian Vazken
Buchenhorner Michael J.
International Business Machines - Corporation
Radtke Mark Andrew X
LandOfFree
Garbage collector with eager read barrier does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Garbage collector with eager read barrier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Garbage collector with eager read barrier will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4247918