Two major tasks of any computer program are the allocation of memory to hold new data and the reclamation of that memory when the data is no longer required. An important feature of modern programming languages is that these tasks are automated so that the programmer need not be involved. For example, object-oriented programming languages such as Java [GJS96] support the construction of sophisticated graphs of objects where it is very difficult if not impossible for the programmer to determine which objects are still required at any point in time. To relieve the programmer of this almost impossible task all Java implementations include some form of garbage collection scheme [Wilson92].
A garbage collector is responsible for analysing the memory being used by a program and working out which areas hold data that is no longer in use, i.e. garbage. Garbage can then be reclaimed and made available to the memory allocator. Although a large number of collection algorithms exist they all suffer a serious problem namely, they must analyse memory that is being modified by a running program. Some algorithms avoid the problem by suspending the running program whilst the collector runs. This can lead to pauses in execution and for large memories may prove unacceptable. The alternative is not to suspend the running program but to make it cooperate with the collector. The enforced cooperation can greatly increase the complexity of these concurrent collectors and slow-down the program execution.
The choice of collection strategy is further complicated in systems that must support large scale data sets. In these systems the traditional approaches do not always work as the memory being used now forms a hierarchy of main memory and disks. A poor choice of collection algorithm could prove disasterous if it were to cause numerous unnecessary disk accesses. Given the problems of scale a significant number of collection algorithms have been devised that attempt to collect small areas of memory, known as generations, but guarantee to eventually collect all garbage in the entire storage hierarchy. However very few algorithms have been developed specifically to handle large-scale data sets. One of the most significant algorithms in this area is PMOS [MMH96] which is a development of the popular train algorithm [HMM+97].
A significant difficulty encountered with the PMOS algorithm is that it is a concurrent collector that has to be integrated with the running program. This led the prototype implementation [MBMM98] to be a programming language specific implementation rather than a more general tool that could be reused in other systems. A brief analysis of the implementation indicates that it should be possible to separate PMOS from the running program if page faults could be exposed. That is, if all page transfers from disk to memory and vice-versa could be intercepted, a PMOS implementation could operate within the storage hierarchy independently of the running program.
An implementation technique does exist that will allow the exposure of page fault induced I/O. This technique is derived from work on an Australian Research Council Small Grant "Timely Access to Satellite Data in a Hierarchical File System". A Hierarchical File System, HFS [Sto93], was constructed from a user written Network File System implementation [Sun95,PVH+98]. It was observed that if a file is mapped into memory from the HFS then all page fault behaviour is exposed. A persistent object store [Bro89] has been constructed using this technique and has achieved acceptable performance [Bro99]. Given the success of the prototype, it should be possible to extend the design to a hierarchical persistent object store that transparently moves data between memory, disks and tapes in the same way as a traditional HFS.
The primary aim of the proposed research is to investigate using a PMOS implementation as part of an experimental hierarchical persistent object store. This should operate independently of the running program and any garbage collection scheme employed within the program's memory. The expected outcomes are a programming language independent PMOS implementation, a more thorough understanding of the PMOS algorithm and its behaviours and an evaluation environment for testing garbage collection algorithms for large data sets.
This work is significant for several reasons. Firstly, it will serve as a proof of concept for this novel implementation technique. It will also demonstrate the utility of the PMOS algorithm to the wider community. The implementation technique may also be applicable to other garbage collection algorithms and would be of particular interest to the Java community. The Java community is very interested in garbage collection algorithms and how they can be applied to large scale real-life applications.
Research Plan, methods and techniques
The proposed research will be made up of the following steps:
A new hierarchical persistent object store will be designed on the assumption that user programs will read and write data using virtual memory paging. A page structure will need to be defined that describes how memory objects can be located and references between objects detected. In addition, a convention will need to be adopted on how a running program creates objects. The PMOS algorithm will need adapting to work with the chosen page structure so that it can detect changed objects and select appropriate areas of the storage hierarchy for garbage collection. Fortunately, PMOS was designed for use with fixed-sized units such as pages so this should not be an onerous task. A major difference between this approach and the original PMOS implementation is that all reads are visible to PMOS. This allows the PMOS implementation to control what versions of a page can be seen by a running program. This allows PMOS to move memory objects between pages without interfering with the running program. Without this ability virtual memory mechanisms need to be employed to deny access to areas of a program's memory that PMOS is modifying.
Interfacing to an Existing Persistent Programming System
The persistent programming system Napier88 [MBC+93] will be used for the experiments. Napier88 was used for the first implementation of PMOS since its memory architecture was designed for cost-effective experimentation [BDM+90]. To interface Napier88 to the new hierarchical object store, the Napier88 persistent object store will be simplified to remove the garbage collection mechanisms and adopt the new object creation mechanism. These changes will not be visible to the Napier88 compiler or its run-time environment [CBC+89] so very little work will be necessary.
Evaluation of the New Store
A major advantage of using Napier88 for the experiments is that the new hierarchical object store can be compared with the first PMOS implementation and the Napier88 standard release system. In each case, the Napier88 system can run identical programs without the need to recompile anything. The only variation between the systems is the underlying persistent object store. Initially the benchmarking experiments conducted on the first PMOS implementation will be re-run in order to test the implementation.
Having established that the hierarchical object store functions correctly, additional benchmarking programs will be tested. The initial PMOS implementation employed the industry standard benchmark OO1 [CS92]. Unfortunately, this benchmark does not significantly exercise a garbage collector so the more sophisticated OO7 [CDN93] benchmark will be measured. This will present the behaviour of the new and existing PMOS implementations using a benchmark that other researches can use to evaluate the significance of this work.
The evaluation process will not simply run benchmark programs, it will also investigate the policy decisions that underpin the PMOS implementations. For example, PMOS assumes a certain fixed-size for pages. The effect of varying page sizes will be investigated. Different mechanisms for selecting which pages to collect will also be evaluated. Experience with other garbage collection algorithms suggests that PMOS should be vulnerable to poor choices. One aspect of the evaluation will be to discover what worst case behaviour looks like in a PMOS implementation and whether or not any simple safe guards can employed to avoid it.
Future Work
The proposed research presents several opportunities for future work. One such area is to compare PMOS behaviour with alternative algorithms. Few if any comparisons have been conducted between such algorithms due to the difficulty of isolating the performance effects of the algorithm from other secondary effects. However, the hierarchical framework for this project in combination with the Napier88 memory architecture may provide an excellent environment for conducting such important experiments.
Another area for future work is to extend the evaluation process to incorporate feedback from running programs. Rather than just reacting to program behaviour it may be helpful if the running program can drop hints as to its future behaviour. In hierarchical storage systems this is an important research area since data access may take micro-seconds or tens of seconds depending on where the data is located in the hierarchy. Clearly, good hints could make a significant difference to a program's performance.
References
[BDM+90] Brown, A.L., Dearle, A., Morrison, R., Munro,
D.S., Rosenberg, J. "A Layered Persistent Architecture for Napier88". International
Workshop on Computer Architectures to Support Security and Persistence
of Information, Universität Bremen, West Germany, (May 1990). In Security
and Persistence. (Eds. J.Rosenberg & L.Keedy). Springer-Verlag, 155-172.
[Bro89] Brown, A.L. "Persistent Object Stores", Phd Thesis, Department of Computational Science, Univesity of St.Andrews, Scotland, 1989.
[Bro99] Brown, A.L. "Using NFS to Expose Persistent Object Store I/O", 6th IDEA International Workshop, Rutherglen, Victoria, Australia, 27-29 January (1999).
[CBC+89] Connor, R.C.H., Brown, A.L., Carrick, R., Dearle, A. & Morrison, R. "The Persistent Abstract Machine". 3rd International Workshop on Persistent Object Systems, Newcastle, N.S.W., (January 1989), 80-95. In Persistent Object Systems (Eds. J.Rosenberg & D.Koch). Springer-Verlag, 353-366.
[CDN93] Carey, M.J., DeWitt, D.J. & Naughton, J.F. The OO7 Benchmark. ACM SIGMOD, May 1993.
[CS92] Cattell, R.G.G. & Skeen, J. "Object Operations Benchmark". ACM Transactions on Database Systems 17,1 (1992) pp 1-31
[GJS96] Gosling, J. Joy, B. & Steel, G.L.Jr, The Java Language Specification, Addison-Wesley, 1996.
[HMM+97] Hudson, R.L., Morrison, R., Moss, J.E.B. & Munro, D.S. "Garbage Collecting the World: One Car at a Time". Object Oriented Programming : Systems, Languages and Applications (OOPSLA), Atlanta (October 1997), pp 162-175.
[MBMM98] David S. Munro, Alfred L. Brown, Ron Morrison & J. Eliot B. Incremental Garbage Collection of a Persistent Object Store using PMOS. In Proceedings of the 8th International Workshop on Persistent Object Systems, Tiburon, California, 30 August - 1 September 1998.
[MMH96] J. Eliot B. Moss, David S. Munro, and Richard L. Hudson. PMOS: A complete and coarse-grained incremental garbage collector for persistent object stores. In Proceedings of the 7th International Workshop on Persistent Object Systems, pp. 140-150, Morgan Kaufmann, 1996.
[MBC+93] Morrison, R., Brown, A.L., Connor, R.C.H., Cutts, Q.I., Dearle, A., Kirby, G.N.C. & Munro, D.S. "The Napier88 Reference Manual (Release 2.0)", University of St Andrews technical report CS/93/15, 1993
[PVH+98] Patten, C.J., Vaughan, F., Hawick, K. & Brown, A.L. "DWorFS: File System Support for Legacy Applications in DISCWorld", Proc. Of the Fifth IDEA Workshop, Fremantle, Western Australia, Australia, 7-10 February (1998), pp30-33.
[Sun95] Sun Microsystems The NFS Distributed File Service, NFS White Paper, March 1995, http://www.sun.com/solaris/wp-nfs.
[Sto93] Stonebraker, M. Sequoia 2000 - A Reflection on the First Three Years. Technical Report, Department of Computer Science, University of California at Berkeley, California, USA, 1993.
[Wilson92] Wilson, P.R. Uni-processor Garbage Collection Techniques. In Bekkers and Cohen (Eds.) Proceedings of the International Workshop on Memory Management, St. Malo, France, 1992, Lecture-Notes in Computer Science, Vol. 637, Psringer-Verlag, 1992.