Jonathan E. Cook
Alexander L. Wolf
ABSTRACT
The automatic reclamation of storage for unreferenced objects is very important in object databases. Existing language system algorithms for automatic storage reclamation have been shown to be inappropriate. In this paper, we investigate methods to improve the performance of algorithms for automatic for automatic storage reclamation of object databases. These algorithms are based on a technique called partitioned garbage collection, in which a subset of the entire database is collected independently of the rest. Specifically, we investigate the policy that is used to select what partition in the database should be collected. The policies that we propose and investigate are based on the intuition that the values of overwritten pointers provide good hints about where to find garbage. Using trace-driven simulation, we show that one of our policies requires less I/O to collect more garbage than any existing implementable policy and performs close to a near-optimal policy over a wide range of database sizes and object connectivities.
- 1.Henry G. Baker, Jr. List processing in real time on a serial computer. Comm. of the A CM, 21(4)'280-294, April 1978. Google Scholar
Digital Library
- 2.Anders Bj#rnerstedt. Secondary Stooge Garbage Collection for Decentralized Object.Baaed SyJtemJ. PhD thesis, Stockholm University, Dept. of Comp. Sys. Sciences, Royal Inst. of Tech. and Stockholm Univ., Kista, Sweden, 1993. Also appears as Systems Dee. and AI Lab. Report No. 77.Google Scholar
- 3.Margaret H. Butler. Storage reclamatlon in object-oriented database systems. In Proceedings of the A CM SIGMOD International Conference on the Management of Data, pages 410-423, San Francisco, CA, 1987. Google ScholarDigital Library
- 4.Jack Campln and Malcolm Atkinson. A persistent store garbage coUector with statistical facilities. Persistent Programmlng Reserarch Report 29, Department of Computing Science, University of Glasgow, Glasgow, Scotland, 1986.Google Scholar
- 5.Michael J. Carey, David 3. DeWier, and Jeffrey F. Naughton. The OO7 benchmark. In Proceeding# of the A CM SIGMOD International Conference on the Management of Data, Washington, DC, June 1993.Google Scholar
- 6.M. Cart and J. FerriC. Integrating Concurrency Control into an Object-orlented Database System. In Proceedings of the Second International Conference on Eztendlng Database Technology. Sprlnger-Verlag, March 1989. Google ScholarDigital Library
- 7.R. G. G. Cattell. The Benchmark Handbook for Database and Transaction Processing Systems, chapter 6, pages 247- 281. Morgan Kaufmmm Publishers, San Mateo, CA, 1991.Google Scholar
- 8.H.-T. Chou and D.J. Dewltt. An Evaluation of Buffer Managem~nt Strategies for Relational Database Systems. In Proc. of the l lth International Conf. on Very Large Data Bases, pages 127-141. Morgan Kaufmann, August 1985.Google Scholar
- 9.Jonathan Cook, Alexander Wolf, and Be#amin Zorn. The design of a simulation system for persistent object storage management. Technical Report CU-CS-647-93, Department of Computer Science, University of Colorado, Boulder, CO, March 1993.Google Scholar
- 10.Jonathan Cook, Alexander Wolf, and Benjamin Zorn. Partition selection policies in object database garbage coLiectlon. Tech_nlcal Report CU-CS-653-93, Department of Computer Science, University of Colorado, Boulder, CO, Revised December 1993.Google Scholar
- 11.D.J. Dewier, P. F#ttersack, D. M#ier, and F. Velez. A Study of Three Alternative Workstation-Server Architectures for Object-Orlented Database Systems. In Proceedings of the 16th International Conference on Very Large Data Bases, pages 107-121. Morgan Kaufmann, August 1990. Google ScholarDigital Library
- 12.Aloke Gupta and W. Kent Fuchs. Garbage collection in a distributed object-oriented system. IEEE Transactions on Knowledge and Data Engineering, 5(2):257-265, April 1993. Google ScholarDigital Library
- 13.Antony L. Hosklng, J. EHot B. Moss, and Darko Stefanovi#. A comparative performance evaluation of write barrier implementations. In A CM SIGPLAN 1992 Conference on Object Oriented Programming Systems, Languages and Applications (00PSLA '92), pages 92-109, Vancouver, British Columbia, Canada, October 1992. Google ScholarDigital Library
- 14.W. Kim. Introduction to Object-Oriented Databases. The MIT Press, 1990. Google ScholarDigital Library
- 15.ELliot Kolodner, Barbara Liskov, and WiRiam Weihl. Atomic garbage collection: Managing a stable heap. In Proceedings of the A CM SIGMOD International Conference on the Management of Data, pages 15-25, Portland, OR, June 1989. Google ScholarDigital Library
- 16.Elliot Kolodner and William Weihl. Atomic incremental garbage collection and recovery for a large stable heap. in Proceedings of the A CM SIGMOD International Conference on the Management of Data, Washington, DC, June 1993. Google ScholarDigital Library
- 17.Henry Lieberman and Carl Hewitt. A real-tlme garbage collector based on the llfetlmes of objects. Comm. of the A CM, 26(6):419--429, June 1983. Google ScholarDigital Library
- 18.David C. J. Matthews. Poly manual. 5IGPLAN Notices, 20(9), September 1985. Google ScholarDigital Library
- 19.K.P. Shannon and R.T. Snodgrass. Semantic Clustering. In Proceedings of the Fourth International Workshop on Per. siatent Object Systems, pages 361-374. Morgan Kaufmann, 1991.Google Scholar
- 20.Robert A. Shaw. Empirical Analysis of a Lisp System. PhD thesis, Stanford University, Stanford, CA, February 1988. Also appears as tech report CSL-TR-88-351. Google ScholarDigital Library
- 21.Alan J. Smith. Cache memories. A CM Computing Surveys, 14(3):473-530, September 1982. Google ScholarDigital Library
- 22.M. M. Tsangarls and J. F. Naughton. A stochastic approach for clustering in object bases. In Proceedings of the SIGMOD Conference on Management of Data, pages 12-21, Denver, CO, March 1991. Google ScholarDigital Library
- 23.David Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In SIGSOFT/SIGPLAN Practical Programming Environments C#nfcr#ncc, pagcu 157-107"# April 1964. Google ScholarDigital Library
- 24.David Ungar and Frank Jackson. An adaptive tenurlng policy for generation scavengers. A CM Trans. on Programming Languages and Systems, 14(1):1-27, January 1992. Google ScholarDigital Library
- 25.Voon-Fee Yong, Jeffrey Naughton, and Jie-Bing Yu. Storage reclamation and reorganization in cllent-server persistent object stores. In Proc. of the i Oth International Conference on Data Engineering, pages 120-131, February 1994. Google ScholarDigital Library
- 26.Benjamin Zorn. Comparative Performance Evaluation of Garbage Collection Algorithms. PhD thesis, University of California at Berkeley, Berkeley, CA, November 1989. Also appears as tech report UCB/CSD 89/544. Google ScholarDigital Library
Index Terms
- Partition selection policies in object database garbage collection
Recommendations
Partition selection policies in object database garbage collection
The automatic reclamation of storage for unreferenced objects is very important in object databases. Existing language system algorithms for automatic storage reclamation have been shown to be inappropriate. In this paper, we investigate methods to ...
A Highly Effective Partition Selection Policy for Object Database Garbage Collection
We investigate methods to improve the performance of algorithms for automatic storage reclamation of object databases. These algorithms are based on a technique called partitioned garbage collection, in which a subset of the entire database is collected ...
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Comments