Nauka teorii śmieciarstwa

Chcę poznać teorię śmieciarstwa. Jak mam to zrobić? Oczywistą odpowiedzią jest-podręcznik kompilatora... Pytanie brzmi, czy trzeba nauczyć się analizy leksykalnej, parsowania i innych rzeczy, które zwykle poprzedzają usuwanie śmieci w tekście?

Krótko mówiąc, jakie są warunki wstępne do poznania teorii zbierania śmieci?

P. S-wiem jaki jest cel parsowania, analizy leksykalnej itp. Po prostu nie w jaki sposób są one realizowane.

Author: earl, 2009-08-23
Source

7 answers

Przeczytaj te dokumenty w kolejności. Są one w kolejności stopniowej tematyki / trudności (nie chronologicznej).

Lista zaczerpnięta bezpośrednio z strony kursu zarządzania pamięcią Prof. Kathryn McKinley tutaj, gdzie znajdziesz linki do wszystkich artykułów.

Byłam na kursie w zeszłym semestrze, więc przeczytałam to wszystko i muszę powiedzieć, że nauczyłam się tego, czego chciałam się nauczyć!

  • przetwarzanie listy w czasie rzeczywistym na komputerze szeregowym , Baker, CACM, 21(4) 280--294, 1978.
  • a nonrecurssive list compacting algorithm , Cheney, CACM, 13(11): 677--678, 1970.
  • w czasie rzeczywistym garbage collector oparty na życiu obiektów , Lieberman & Hewitt, CACM, 26(6): 419--429, 1983.
  • Generation scavenging: a non-disruptive high-performance storage reclamation algorithm, Ungar, Proceedings of the first ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 1984, strony 157--167.
  • Simple generaational garbage collection and fast allocation , Appel, Software--Practice and Experience 19 (2): 171-183, February 1989.
  • [10]}Age-Based Garbage Collection, D. Stefanovic, K. S. McKinley, J. E. B. Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Applications. (OOPSLA), S. 370-381. Denver CO, listopad 1999.
  • Older-pierwsze usuwanie śmieci w praktyce: Ewaluacja w wirtualnej Javie Maszyna , D. Stefanovic, M. Hertz, S. M. Blackburn, K. S. McKinley, and J. E. B. Moss, Memory System Performance, Berlin, Germany, PP. 175--184, czerwiec 2002.
  • Beltway: Getting Around Garbage Collection Gridlock , S. M. Blackburn, R. Jones, K. S. McKinley, and J. E. B. Moss, ACM Conference on Programming Language Design and Implementation, Berlin, Germany, PP. 153--164, czerwiec 2002.
  • skuteczna, niezależna od maszyny procedura zbierania śmieci w various list structures, Schorr & Waite, CACM, 10(8): 501--506, 1967.
  • Comparison of compacting algorithms for garbage collection , Cohen & Nicolau, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 5, Issue 4, pages 532--553, October 1983.
  • MC2: High-Performance Garbage Collection for Memory-Constrainted Environments, Sachindran, Berger & Moss, ACM Conference on Object-Oriented Programming Systems, Languages and Aplikacje, S. 81-96, Vancouver, BC, październik 2004.
  • Immix: a Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance , Blackburn & McKinley, ACM Conference on Programming Language Design and Implementation, PP. 22--32, Tucson, AZ, czerwiec 2008.
  • wydajny Przyrostowy Automatyczny Śmieciarz , Deutsch & Bobrow, CACM, 19(9): 522--526, wrzesień 1976.
  • Liczenie Odniesień: Szybko Garbage Collection without the Wait, S. M. Blackburn and K. S. McKinley , Proceedings of the ACM 2003 Sigplan Conference on Object-Oriented Programming Systems, Languages and Applications, PP. 344-359, Annehiem, CA, October 2003.
  • Cycle Tracing: Efficient Concurrent Mark-Sweep Cycle Collection, Frampton & Blackburn, 2009. (W podporządkowaniu ISMM.)
  • Multiprocessing compactifying garbage collection , Guy L. Steele, Jr., CACM 18(9): 495-508, 1975.
  • [10]}w locie śmieciarka: ćwiczenie we współpracy, E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten i E. F. M. Steffens, Komunikacja ACM, 21(11):966--975, listopad 1978.
  • Correctness-Preserving Derivation of Concurrent Garbage Collection Algorithms, Vechev, Yahav, and Bacon, ACM Conference on Programming Language Design and Implementation, Ottawa, Ontario, PP. 341-353, 2006.
  • a Real-time Garbage Collector with Low Overhead and Consistent Utilization, Bacon, Cheng, and Rajan, ACM Symposium on Principles of Programming Languages, New Orleans, Louisiana, PP. 285-298, 2003.
  • Tax-and-spend: democratic scheduling for real-time garbage collection , Auerbach, Bacon, Cheng, Grove, Biron, Gracie, McCloskey, Micic, and Sciampacone, ACM International Conference On Embedded Software, Atlanta, GA, PP. 245-254, 2008.
  • wywóz śmieci w środowisko bez współpracy , H. Boehm i M. Weiser, praktyka i doświadczenie w zakresie oprogramowania, 18(9):807-820, 1988.
  • Hoard: a Scalable Memory Allocator for Multithreaded Applications, E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson, The Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, PP. 117--128, November 2000.
  • Cork: dynamiczne wykrywanie wycieków pamięci dla śmieci-zebranych Języki,Jump & McKinley, in submission to ACM Transactions on Software Practice & Experience, 2009. (Skrócona wersja pojawia się w konferencji ACM na temat języków programowania, Nicea, Francja, styczeń 2009.)
  • Leak Pruning , Bond & McKinley, ACM Conference on Architecture Support for Programming Languages and Operating Systems, Washington, DC, marzec 2009. (Pojawiać się.)
  • [[10]}Free-me: statyczna Analiza rekultywacji poszczególnych obiektów , Guyer & McKinley, ACM Conference on Programming Language Design and Implementation, Ottawa, Kanada, PP. 364-375, czerwiec 2006.
  • Garbage collection can be faster than stack allocation, Appel, Information Processing Letters 25 (4):275-279, 17 June 1987.
  • the Garbage Collection Advantage: Improving program location Huang, Blackburn, McKinley, Moss, Wang, & Cheng, ACM Conference on Object-Oriented Programming Systems, Languages, & Applications, Vancouver, BC, PP. 69-80, Październik 2004.
  • Demystifying Magic: High-level low-level Programming, Daniel Frampton, Stephen M. Blackburn, Perry Cheng, Robin Garner, David P. Grove, J. Eliot B. Moss & Sergey I. Salishev. ACM International Conference on Virtual Execution Environments, Washington DC, marzec 2009. (Pojawiać się.)
  • Mity i realia: wpływ wydajności zbierania śmieci , S. M. Blackburn, P. Cheng, and K. S. McKinley, ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, PP. 25--36, New York, NY, czerwiec 2004.
  • a unified theory of garbage collection , Bacon, Cheng, & Rajan, ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vancouver, BC, Canada, PP.50-68, 2004.
 19
Author: Sam Harwell,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-08-23 17:32:35

Jest cała książka o zbieraniu śmieci, i całkiem dobra, jeśli Mogę dodać:

Richard Jones & Rafael Lins, Garbage Collection, Wiley i synowie (1996), ISBN 0471941484

Richard Jones prowadzi również ładną stronę zbierającą zasoby do zbierania śmieci .

Większość wczesnych dokumentów do zbierania śmieci jest doskonale czytelna. Możesz zacząć od badania Paula Wilsona "Uniprocessor Garbage Collection Techniques" (1992, LNCS vol. 637) , a następnie zanurzyć się w oryginalnej literaturze na tematy, które brzmią interesująco.

 12
Author: earl,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-08-23 17:41:48
Chcę poznać teorię śmieciarstwa. Jak mam to zrobić?

Jestem również dabblerem, który interesuje się garbage collectingiem (do tego stopnia, że napisałem własną maszynę wirtualną o nazwie HLVM). Nauczyłem się czytając tyle artykułów naukowych na temat zbierania śmieci, ile tylko mogłem dostać w swoje ręce i bawiąc się pomysłami, zarówno surowymi w mojej maszynie wirtualnej, jak i pisząc bezpieczne dla pamięci symulacje wysokiego poziomu.

Oczywista odpowiedź is-podręcznik kompilatora... Pytanie brzmi, czy trzeba nauczyć się analizy leksykalnej, parsowania i innych rzeczy, które zwykle poprzedzają usuwanie śmieci w tekście?

Analiza leksykalna, parsowanie i inne rzeczy nie są istotne dla garbage collection. Możesz uzyskać Nieaktualny pobieżny przegląd zbierania śmieci z książki kompilatora, ale musisz przeczytać dokumenty badawcze, aby uzyskać aktualny widok, np. w odniesieniu do wielordzeniowości.

W skrócie, jakie są warunki wstępne do poznania teorii zbierania śmieci?

Musisz wiedzieć o podstawowej teorii grafów, wskaźnikach, stosach, wątkach i (jeśli jesteś zainteresowany wielowątkowością) niskopoziomowych podstawach współbieżności, takich jak blokady.

Garbage collection polega na określeniu osiągalności. Gdy program nie może już uzyskać odniesienia do wartości, ponieważ wartość ta stała się nieosiągalna, GC może przetwarzać pamięć, którą zajmuje wartość. Osiągalność zależy od w przeciwieństwie do innych wątków, które nie są w pełni kompatybilne z innymi wątkami (np. z innymi wątkami, np. z innymi wątkami, np. z innymi wątkami, np. z innymi wątkami, np. z innymi wątkami, np. z innymi wątkami, np. z innymi wątkami).]}

Projektowanie GC ma wiele aspektów, ale możesz zacząć od czterech głównych algorytmów zbierania śmieci:

  • Mark-and-sweep (McCarthy, 1960)
    • Mark-and-compact (Haddon and Waite, 1967)]}
  • Stop-and-copy (Cheney, 1970)
  • Mark-region (McKinley et al., 2007)

Być może najbardziej godne uwagi ewolucją tych podstawowych idei jest pokoleniowa zbiórka śmieci, która przez wiele lat była standardowym projektem defacto.

Moje osobiste odczucie jest takie, że niektóre niejasne prace nad śmieciarstwem przekazują tyle samo przydatnych informacji, więc również gorąco polecam: {]}
  • bieżnia piekarza (piękna bieżnia w czasie rzeczywistym).
  • VCGC (zupełnie inny schemat znakowania trójkolorowego).

Możesz również studiować trzy rodzaje bariera zapisu (Dijkstry, Steele 'a i Yuasy' a) i przyjrzeć się znakowaniu kart i zapamiętanym technikom set.

Następnie możesz również przeanalizować rzeczywiste decyzje projektowe, które niektórzy implementatorzy wybrali dla implementacji języków, takich jak Java i. NET, a także kompilator SML / NJ dla standardowego ML, kompilator OCaml, kompilator Glasgow Haskell i inne. Różnice między przyjętymi technikami są tak duże, jak podobieństwa między nimi!

Są też świetne dokumenty związane z tangencjalnie, takie jak dokładne zbieranie śmieci przez Hendersona w środowisku nie współpracującym [6]}. Użyłem tej techniki, aby uniknąć konieczności pisania stack walker dla HLVM.

Memorymanagement.org strona internetowa jest nieocenionym zasobem, w szczególności słownikiem terminów związanych z GC.

 4
Author: Jon Harrop,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-12-23 22:23:08

Nie znam żadnego podręcznika na kompilatorach, który również wyjaśnia zbiór śmieci, ponieważ, jak sam powiedziałeś, te dwa są całkiem niezwiązane.

Naprawdę podoba mi się Artykuł Wikipedii jako wstępne Wyjaśnienie z wieloma dobrymi wskazówkami. Zdecydowanie jeden z lepszych artykułów CS na Wikipedii.

 3
Author: Konrad Rudolph,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-08-23 14:06:17

Rozdział 9, "zarządzanie pamięcią", Object Oriented Software Construction, 2nd Edition autorstwa Bertranda Meyera jest dość pouczający.

 2
Author: Daniel Daranas,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-08-23 14:17:53

Zacznę od przeczytania tego artykułu: A unified theory of garbage collection, Bacon, Cheng, & Rajan, ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vancouver, BC, Canada, PP. 50-68, 2004.

 2
Author: Eran Yahav,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-09-30 18:34:59

Możesz również rzucić okiem na Squeak: Open Personal Computing , który obejmuje m.in. program Squeak Smalltalk garbage collector. Powinieneś również spojrzeć na Squeak Sam - jest prawie całkowicie napisany w Smalltalku, a wszystkie źródła, w tym GC, są swobodnie dostępne i łatwe do zbadania za pomocą przeglądarek Smalltalk.

 1
Author: ,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-08-23 14:22:20