Memory Management in Shared Memory Architectures: A Tutorial
Resumo
This paper presents a survey of the most important algorithms and architectures for dynamic memory management in shared memory machines.
Palavras-chave:
Multiprocessors, Memory management, Shared memory, Garbage collection Introduction
Referências
A.W. Appel, J.R. Ellis, and K.Li. Real-time concurrent collettion on stock multiprocessors. ACM SIGPLAN Notices, 23(7):11-20, 1988.
K. Appleby, M. Carlsson, S. Haridi, and D. Sahlin. Garbage collection for Prolog based on WAM. Communications of the ACM, 31(6):719-741, 1988.
H.G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978.
Y.Bekkers, O. Ridoux, and L. Ungaro. A survey on memory management for logic programming. In I WMM'92, LNCS 637,Springer Verlag, 1992.
M.Ben-Ari. On-the-fly garbage collection: new algorithms inspired by program proofs. Automata, languages and programming., 14-22, Springer-Verlag, 1982.
M.Ben-Ari. Algorithms for on-the-fly garbage collection. ACM Trans. Prog.Lang. & Syst., 6(3):333-344, July 1984.
D.G. Bobrow. Managing reentrant structures using referente counts. ACM Transactions on Programming Languages and Systems, 2(3):269-273, July 1980.
H-J.Boehm, A.J. Demers, and S.Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157-164, 1991.
R. A. Brooks. Trading data space for reduced time and code space in real-time garbage collection on stotk hardware. SLFP'82, 256-242, 1984. ACM.
D.R. Brownbridge. Cyclic referente counting for combinator machines. FP&CA '85, Springer-Verlag.
C.J.Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677-8, November 1970.
J.Cohen. Garbage collection of linked data structures. ACM Computing Surveys, 13(3):341-367, September 1981.
G.E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655-657, Dec. 1960.
J.Crammond. A garbage collection algorithm for shared memory parallel processors. lnternational Journal of Parallel Programming, 17(6):497-522, 1988.
J.DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DECSRC, Paio Alto, California, August 1990.
E. W. Dijkstra. Notes on a real time garbage collection system. From a conversation with D.E.Knuth (private collection of D.E.Knuth), 1975.
E.W. Dijkstra, L.Lamport, et al. On-the-fiy garbage collection: An exercise in cooperation. LNCS 4 6, Springer-Verlag, 1976.
E.W. Dijkstra, L.Lamport, et al. On-the-fiy garbage collection: An exercise in cooperation. CACM21(11):965-975, November 1978.
L. Ehn. A contribution to the increase of efficiency of on-the-fly garbage collection. Computers And Artificial lntelligence, 8(1):83-91, 1989.
R. Fenichel and J. Yochelson. A Lisp garbage collector for virtual memory computer systems. Communications of the ACM, 12(11):611-612, Nov. 1969.
D.P. Friedman and D.S. Wise. Reference counting can manage the circular environments of mutual recursion. lnf Process. Lett., 8(1):41-45, Jan. 1979.
D.Gries. An exercise in proving parallel programs correct. Communications of thc ACM, 20(12):921-930, Dec. 1977.
D.Gries. On believing programs to be correct. Communications of the ACM, 20(1):49-50, Jan. 1977.
R.H. Halsiead, Jr. lmplementation of Multilisp: Lisp on a multiprocessor. L&FP'84, ACM, 1984.
T.P. Hart and T.G.Evans. Notes on implementing LISP for the M-460 computer. The Programming Language LISP: lts Operation and Applications., 191-203, 1964. Information International, Inc.
B. Hayes. Using key object opporiunism to collect old objects. In OOPSLA91, pages 33-46. ACM, October 1991. Phoenix, Arizona.
T. Hickey and J.Cohen. Performance analysis of on-the-fly garbage collection. Communications of the ACM, 27(11):1143-1154, Nov. 1984.
R.J.M.Hughes. Managing reduction graphs with reference counts. Departmental Research Report CSC/87 /R2, University of Glasgow, March 1987.
R.E.Jones and R.D.Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management, John Wiley & Sons, 1996. ISBN 0 471 941484.
K. Kakuta, H.Nakamura, and S.Iida. Parallel reference counting algorithm. Information Processing Letters, 23(1):33-37, 1986.
D.E. Knuth. The art of computer programming, volume I: Fundamental algorithms, chapter 2. Addison-Wesley, Reading, Ma., 2nd edition, 1973.
H.T. Kung and S.W. Song. An efficient parallel garbage collection system and its correctness proof. IEEE Foundations of CS, 120-131. IEEE, 1977.
L.Lamport. Garbage collection with multiple processes: An exercise in parallelism. ICPP'76, 50-54, 1976.
H.Lieberman and C.Hewitt. A real-time garbage collector based on the lifetimes of objects. CACM, 26(6):419-29, 1983.
R.D. Lins. Cyclic reference counting with lazy mark-scan. Information Processing Letters, vol 44( 4): 215-220, North-Holland, December 1992.
R.D. Lins. A shared memory architecture for parallel cyclic reference counting. Microprocessing and Microprogramming, 34:31-35, September 1991.
R.D. Lins. A multi-processor shared memory architecture for parallel cyclic reference counting. Microprocessing and Microprogramming, 35:563-568, 1992.
R.D.Lins and R.E.Jones. Dynamic Memory Management: Algorithms for Garbage Collection. to be published by John Wiley & Sons.
A.D. Martinez, R.Wachenchauzer, and R.D. Lins. Cyclic reference counting with local mark-scan. Information Processing Letters, 34:31-35, 1990.
J.H.McBeth. On the reference counter method. Communications of the ACM, 6(9):575, September 1963.
J.McCarthy. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3:184-195, 1960.
F.L.Morris. A time-and space-efficient garbage compaction algorithm. Communications of the ACM, 21(8):662-5, 1978.
LA. Newman, R.P. Stallard, and M.C. Woodward. Performance of parallel garbage collection algorithms. Computer Studies, 166, September 1982.
I.A. Newman, R.P. Stallard, and M.C. Woodward. Improved multiprocessor garbage collection algorithms. In IC Parallel Processing, 367-368, 1983.
I. A. Newman, R.P. Stallard, and M.C. Woodward. A hybrid multiple processor garbage collection algorithm. Computer Journal, 30(2):119-127, 1987.
S.Owicki and D.Gries. Verifying properties of parallel programs: An axiomatic approach. Communications of the ACM, 19(5):279-285, May 1976.
S.Owicki and L.Lamport. Proving liveness properties of concurrent programs. ACM T.Programming Languages and Systems, 4(3):455-495, 1982.
E.J.H. Pepels, M.C.J.D. van Eekelen, and M.J. Plasmeijer. A cyclic reference counting algorithm and its proof. TR-CS 88-10, University of Nijmegen, 1988.
F.J. Pollack, G.W. Cox, et al. Supporting Ada memory management in the iAPX-432. pages 117-131. SIGPLAN Notices (ACM) 17,4, 1982.
S. Ramesh and S.L. Mehndiratta. The liveness property of on-the-fty garbage collector - a proof. Information Processing Letters, 17(4):189- 195, 1983.
N. Rojemo. A concurrent generational garbage collector for a parallel graph reducer. PIWMM'92, LNCS 637, Springer Verlag, 1992.
J .D. Salkild. lmplementation and analysis of two reference counting algorithms. Master's thesis, University College, London, 1987.
R.A. Saunders. The LISP system for the Q-32 computer. The Programming Language LISP: lts Operation and Applications., 220-231, Inf.International Inc, 1964.
H. Schorr and W. Waite. An efficient machine independent procedure for garbage collection in various list structures. CACM, 10(8):501-506, Aug. 1967.
T. Le Sergent and B. Barthomieu. Incremental multi-threaded garbage collection on virtually shared memory architectures. IWMM'92, LNCS 637, Springer Verlag, 1992.
R.Sharma and M.L.Soffa. Parallel generational garbage collection. In Proceedings of OOPSLA '91, pages 16-32, 1991.
R.A. Shaw. Empirical Analysis of a Lisp System. PhD thesis, Stanford University, 1988. Tech. Rep. CSL-TR-88-351.
G.L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975.
G.L. Steele. Corrigendum: Multiprocessing compactifying garbage collection. Communications of the ACM, 19(6):354, June 1976.
S.J. Thompson and R.D. Lins. Cyclic reference counting: a correction to Brownbridge's algorithm. unpublished notes, 1988.
D.M. Ungar. Generation scavenging: a non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157-167, Aprill984.
P.L. Wadler. Analysis of an algorithm for real-time garbage collection. Communications of the ACM, 19(9):491-500, September 1976.
B.Zorn. Comparing mark-and-sweep and stop-and-copy garbage collection. ACM Lisp and FP, June 1990.
K. Appleby, M. Carlsson, S. Haridi, and D. Sahlin. Garbage collection for Prolog based on WAM. Communications of the ACM, 31(6):719-741, 1988.
H.G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978.
Y.Bekkers, O. Ridoux, and L. Ungaro. A survey on memory management for logic programming. In I WMM'92, LNCS 637,Springer Verlag, 1992.
M.Ben-Ari. On-the-fly garbage collection: new algorithms inspired by program proofs. Automata, languages and programming., 14-22, Springer-Verlag, 1982.
M.Ben-Ari. Algorithms for on-the-fly garbage collection. ACM Trans. Prog.Lang. & Syst., 6(3):333-344, July 1984.
D.G. Bobrow. Managing reentrant structures using referente counts. ACM Transactions on Programming Languages and Systems, 2(3):269-273, July 1980.
H-J.Boehm, A.J. Demers, and S.Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157-164, 1991.
R. A. Brooks. Trading data space for reduced time and code space in real-time garbage collection on stotk hardware. SLFP'82, 256-242, 1984. ACM.
D.R. Brownbridge. Cyclic referente counting for combinator machines. FP&CA '85, Springer-Verlag.
C.J.Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677-8, November 1970.
J.Cohen. Garbage collection of linked data structures. ACM Computing Surveys, 13(3):341-367, September 1981.
G.E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655-657, Dec. 1960.
J.Crammond. A garbage collection algorithm for shared memory parallel processors. lnternational Journal of Parallel Programming, 17(6):497-522, 1988.
J.DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DECSRC, Paio Alto, California, August 1990.
E. W. Dijkstra. Notes on a real time garbage collection system. From a conversation with D.E.Knuth (private collection of D.E.Knuth), 1975.
E.W. Dijkstra, L.Lamport, et al. On-the-fiy garbage collection: An exercise in cooperation. LNCS 4 6, Springer-Verlag, 1976.
E.W. Dijkstra, L.Lamport, et al. On-the-fiy garbage collection: An exercise in cooperation. CACM21(11):965-975, November 1978.
L. Ehn. A contribution to the increase of efficiency of on-the-fly garbage collection. Computers And Artificial lntelligence, 8(1):83-91, 1989.
R. Fenichel and J. Yochelson. A Lisp garbage collector for virtual memory computer systems. Communications of the ACM, 12(11):611-612, Nov. 1969.
D.P. Friedman and D.S. Wise. Reference counting can manage the circular environments of mutual recursion. lnf Process. Lett., 8(1):41-45, Jan. 1979.
D.Gries. An exercise in proving parallel programs correct. Communications of thc ACM, 20(12):921-930, Dec. 1977.
D.Gries. On believing programs to be correct. Communications of the ACM, 20(1):49-50, Jan. 1977.
R.H. Halsiead, Jr. lmplementation of Multilisp: Lisp on a multiprocessor. L&FP'84, ACM, 1984.
T.P. Hart and T.G.Evans. Notes on implementing LISP for the M-460 computer. The Programming Language LISP: lts Operation and Applications., 191-203, 1964. Information International, Inc.
B. Hayes. Using key object opporiunism to collect old objects. In OOPSLA91, pages 33-46. ACM, October 1991. Phoenix, Arizona.
T. Hickey and J.Cohen. Performance analysis of on-the-fly garbage collection. Communications of the ACM, 27(11):1143-1154, Nov. 1984.
R.J.M.Hughes. Managing reduction graphs with reference counts. Departmental Research Report CSC/87 /R2, University of Glasgow, March 1987.
R.E.Jones and R.D.Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management, John Wiley & Sons, 1996. ISBN 0 471 941484.
K. Kakuta, H.Nakamura, and S.Iida. Parallel reference counting algorithm. Information Processing Letters, 23(1):33-37, 1986.
D.E. Knuth. The art of computer programming, volume I: Fundamental algorithms, chapter 2. Addison-Wesley, Reading, Ma., 2nd edition, 1973.
H.T. Kung and S.W. Song. An efficient parallel garbage collection system and its correctness proof. IEEE Foundations of CS, 120-131. IEEE, 1977.
L.Lamport. Garbage collection with multiple processes: An exercise in parallelism. ICPP'76, 50-54, 1976.
H.Lieberman and C.Hewitt. A real-time garbage collector based on the lifetimes of objects. CACM, 26(6):419-29, 1983.
R.D. Lins. Cyclic reference counting with lazy mark-scan. Information Processing Letters, vol 44( 4): 215-220, North-Holland, December 1992.
R.D. Lins. A shared memory architecture for parallel cyclic reference counting. Microprocessing and Microprogramming, 34:31-35, September 1991.
R.D. Lins. A multi-processor shared memory architecture for parallel cyclic reference counting. Microprocessing and Microprogramming, 35:563-568, 1992.
R.D.Lins and R.E.Jones. Dynamic Memory Management: Algorithms for Garbage Collection. to be published by John Wiley & Sons.
A.D. Martinez, R.Wachenchauzer, and R.D. Lins. Cyclic reference counting with local mark-scan. Information Processing Letters, 34:31-35, 1990.
J.H.McBeth. On the reference counter method. Communications of the ACM, 6(9):575, September 1963.
J.McCarthy. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3:184-195, 1960.
F.L.Morris. A time-and space-efficient garbage compaction algorithm. Communications of the ACM, 21(8):662-5, 1978.
LA. Newman, R.P. Stallard, and M.C. Woodward. Performance of parallel garbage collection algorithms. Computer Studies, 166, September 1982.
I.A. Newman, R.P. Stallard, and M.C. Woodward. Improved multiprocessor garbage collection algorithms. In IC Parallel Processing, 367-368, 1983.
I. A. Newman, R.P. Stallard, and M.C. Woodward. A hybrid multiple processor garbage collection algorithm. Computer Journal, 30(2):119-127, 1987.
S.Owicki and D.Gries. Verifying properties of parallel programs: An axiomatic approach. Communications of the ACM, 19(5):279-285, May 1976.
S.Owicki and L.Lamport. Proving liveness properties of concurrent programs. ACM T.Programming Languages and Systems, 4(3):455-495, 1982.
E.J.H. Pepels, M.C.J.D. van Eekelen, and M.J. Plasmeijer. A cyclic reference counting algorithm and its proof. TR-CS 88-10, University of Nijmegen, 1988.
F.J. Pollack, G.W. Cox, et al. Supporting Ada memory management in the iAPX-432. pages 117-131. SIGPLAN Notices (ACM) 17,4, 1982.
S. Ramesh and S.L. Mehndiratta. The liveness property of on-the-fty garbage collector - a proof. Information Processing Letters, 17(4):189- 195, 1983.
N. Rojemo. A concurrent generational garbage collector for a parallel graph reducer. PIWMM'92, LNCS 637, Springer Verlag, 1992.
J .D. Salkild. lmplementation and analysis of two reference counting algorithms. Master's thesis, University College, London, 1987.
R.A. Saunders. The LISP system for the Q-32 computer. The Programming Language LISP: lts Operation and Applications., 220-231, Inf.International Inc, 1964.
H. Schorr and W. Waite. An efficient machine independent procedure for garbage collection in various list structures. CACM, 10(8):501-506, Aug. 1967.
T. Le Sergent and B. Barthomieu. Incremental multi-threaded garbage collection on virtually shared memory architectures. IWMM'92, LNCS 637, Springer Verlag, 1992.
R.Sharma and M.L.Soffa. Parallel generational garbage collection. In Proceedings of OOPSLA '91, pages 16-32, 1991.
R.A. Shaw. Empirical Analysis of a Lisp System. PhD thesis, Stanford University, 1988. Tech. Rep. CSL-TR-88-351.
G.L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975.
G.L. Steele. Corrigendum: Multiprocessing compactifying garbage collection. Communications of the ACM, 19(6):354, June 1976.
S.J. Thompson and R.D. Lins. Cyclic reference counting: a correction to Brownbridge's algorithm. unpublished notes, 1988.
D.M. Ungar. Generation scavenging: a non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157-167, Aprill984.
P.L. Wadler. Analysis of an algorithm for real-time garbage collection. Communications of the ACM, 19(9):491-500, September 1976.
B.Zorn. Comparing mark-and-sweep and stop-and-copy garbage collection. ACM Lisp and FP, June 1990.
Publicado
07/10/1997
Como Citar
LINS, Rafael D..
Memory Management in Shared Memory Architectures: A Tutorial. In: TUTORIAIS - INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 9. , 1997, Campos do Jordão/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1997
.
p. 31-46.
DOI: https://doi.org/10.5753/sbac-pad_estendido.1997.22649.
