Lightweight recoverable virtual memory

Abstract

Recoverable virtual memory refers to regions of a virtual address space on which transactional guarantees are offered. This paper describes RVM, an efficient, portable, and easily used implementation of recoverable virtual memory for Unix environments. A unique characteristic of RVM is that it allows independent control over the transactional properties of atomicity, permanence, and serializability. This leads to considerable flexibility in the use of RVM, potentially enlarging the range of applications than can benefit from transactions. It also simplifies the layering of functionality such as nesting and distribution. The paper shows that RVM performs well over its intended range of usage even though it does not benefit from specialized operating system support. It also demonstrates the importance of intra- and intertransaction optimizations.

References

1. 1 Andrade, J.M., Carges, M.T., Kovach, K.R. Building a Transacticm Processing System on UNIX Systems. In UniForum Conference Proceedings. San Francisco, CA, February, 1989.
2. 2 Baron, R.V., Black, D.L., Bolosky, W., Chew, J., Golub, D.B., Rashid, R.F., Tevanian, Jr, A., Young, M.W. Mach Kernel Interface Manual School of Ccnnputer Science, Carnegie Mellon University, t 987.
3. 3 Bemstein, P.A., Hadzilacos, V., Goodman, N. Concurrency Control and Recovery in Database Systems, Addison Wesley, 1987.
4. 4 Bershad, B.N., Anderson, T.E., Lazowska, E.D., Levy, H.M. Lightweight Remote Procedure Call. ACM Transactions on Computer Systems 8(1), February, 1990.
5. 5 Birrell, A.B., Jones, M.B., Wobber, E.P. A Simple and Efficient Implementation for Small Databases. In Proceedings of the Eleventh ACM Symposium on Operating System Principles. Austin, TX, November, 1987.
6. 6 Chang, A., Mergen, M.F. 801 Storage: Architecture and Programming. ACM Transactions on Computer Systems 6(1), February, 1988.
7. 7 Chew, K-M, Reddy, A.j., Romer, T.H., Silbersehatz, A. Kernel Support for Recoverable-Persistent Virtual Memory. In Proceedings of the USENIX Math IIl Symposium. Santa Fe, NM, April, 1993.
8. 8 Cooper, E.C., Draves, R.P. C Threads. Technical Report CMU-CS-88-154, Department of Computer Science, Carnegie Mellon University, June, 1988.
9. 9 Eppinger, J.L. Virtual Memory Management for Transaction Processing Systems. PhD thesis, Department of Computer Science, Camegie Mellon University, February, 1989.
10. 10 Eppinger, J.L., Mummert, L.B., Spector, A.Z. Camelot and Avalon. Morgan Kaufmann, 1991.
11. 11 Garcia-Molina, H., Salem, K. Sagas. In Proceedings of the ACM Sigmod Conference. 1987.
12. 12 Good, B., Homan, P.W., Gawlick, D.E., Sammer, H. One thousand transactions per second. In Proceedings oflEEE Compcon. San Francisco, CA, 1985.
13. 13 Gray, J. Notes on Database Operating Systems. in Goos, G., Hartmanis, J. (editor), Operating Systems: An Advanced Course. Springer Verlag, 1978.
14. 14 Gray, J., Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
15. 15 Haskin, R., Malachi, Y., Sawdon, W., Chan, G. Recovery Management in QuickSilver. ACM Transactions on Computer Systems 6(1), February, 1988.
16. 16 Kistler, J.J., Satyanarayanan, M. Disconnected Operation in the Coda File System. ACM Transactions on Computer Systems 10(1), February, 1992.
17. 17 Kumar, P., Satyanarayanan, M. Log-based Directory Resolution in the Coda File System. In Proceedings of the Second International Conference on Parallel and Distributed Information Systems. San Diego, CA, January, 1993.
18. 18 Lampson, B.W. Atomic Transactions. In Lampson, B.W., Paul, M,, Siegert, H.J. (editors), Distributed Systems -- Architecture and Implementation. Springer Verlag, 1981.
19. 19 Lampson, B. W. Hints for Computer System Design. In Proceedings of the Ninth ACM Symposium on Operating Systems Principles. Bretton Woods, NH, October, 1983.
20. 20 Leffier, S.L., McKusick, M.K., Karels, M.J., Quarterman, J.S. The Design and Implementation of the 4.3BSD Unix Operating System. Addison Wesley, 1989.
21. 21 Liskov, B.H., Scheifler, R.W. Guardians and Actions: Linguistic Support for Robust, Distributed Programs. ACM Transactions on Programming Languages 5(3), July, 1983.
22. 22 Mashbum, H., Satyanarayanan, M. RVM User Manual School of Computer Science, Carnegie Mellon University, 1992.
23. 23 Moss, J.E.B. Nested Transactions: An Approach to Rehable Distributed Computing. MIT Press, 1985.
24. 24 Nettles, S.M., Wing, J.M. Persistence + Undoabillty = Transactions. In Proceedings of HICSS-25. Hawaii, January, 1992.
25. 25 O'Toole, J., Nettles, S., Gifford, D. Concurrent Compacting Garbage Collection of a Persistent Heap. In Proceedings of the Fourteenth ACM Symposium on Operating System Principles, Asheville, NC, December, 1993.
26. 26 Ousterhout, J.K. Why Aren't Operating Systems Getting Faster As Fast as Hardware? In Proceedings of the USENIX Summer Conference. Anahetm, CA, June, 1990.
27. 27 Patterson, D.A., Gibson, G., Katz, R. A Case for Redundant Arrays of Inexpensive Disks (RAID). In Proceedings of the ACM SIGMOD Conference. 1988.
28. 28 Rosenblum, M., Ousterhout, J.K. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems 10(1), February, 1992.
29. 29 Satyanarayanan, M. RPC2 User Guide and Reference Manual School of Computer Science, Camegie Mellon University, 1991.
30. 30 Satyanarayanan, M., Kistler, J.J., Kumar, P., Okasaki, M.E., Siegel, E.H., Steere, D.C. Coda: A Highly Available File System for a Distributed Workstation Environment. IEEE Transactions on Computers 39(4), April, 1990.
31. 31 Satyanarayanan, M., Steere, D.C., Kudo, M., Mashbum, H. Transparent Logging as a Toohniquo for Dobugging Complex Distributed Systems. In Proceedings of the Fifth ACM SIGOPS European Workshop. Mont St. Michel, France, September, 1992.
32. 32 Serlin, O. The History of DebitCredit and the TPC. In Gray, J. (editors), The Benchmark Handbook. Morgan Kaufman, 1991.
33. 33 Spector, A.Z. The Design of Camelot. In Eppinger, J.L., Mummert, L,B., Spector, A.Z. (editors), Camelot and Avalon. Morgan Kaufmann, 1991.
34. 34 Smut, P.D., Jaffe, E.D., Spector, A.Z. Performance of Select Camelot Functions. In Eppinger, J.L., Mummert, L.B., Spector, A.Z. (editors), Camelot and Avalon. Morgan Kaufmann, 1991.
35. 35 Encina Product Overview Transarc Corporation, 1991.
36. 36 TUXEDO System Product Overview Unix System Laboratories, 1993.
37. 37 Wing, J.M., Faehndrich, M., Mordseu, G., and Nettles, S.M. Extensmns to Standard ML to Support Transactions. In ACM SIGPLAN Workshop on ML and its Applications. San Francisco, CA, June, 1992.
38. 38 Wing, J.M. The Avalon Language. In Eppinger, J.L., Mummert, LB., Spector, A.Z. (editors), Camelot and Avalon. Morgan Kaufmann, 1991.
39. 39 Young, M.W. Exporting a User Interface to Memory Management from a Communication-Oriented Operating System. PhD thesis, Department of Computer Science, Camegie Mellon University, November, 1989.
40. 40 Young, M.W., Thompson, D.S., Jaffe, E. A Modular Architecture for Distributed Transaction Processing. In Proceedings of the USENIX Winter Conference. Dallas, TX, January, 1991.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Measurement

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Virtual memory