Správa paměti podle regionů

Správa paměti založená na regionech  je způsob správy paměti , ve kterém je každý objekt vytvořený v paměti přiřazen ke konkrétní „oblasti“.

Oblast, nazývaná také zóna, aréna [1] , oblast nebo paměťový kontext, je množina alokovaných objektů, které lze efektivně uvolnit ve stejnou dobu. Podobně jako u správy paměti založené na zásobníku , správa paměti založená na regionech usnadňuje alokaci paměti a dealokaci, což umožňuje provádět ji s minimální režií. Ve srovnání se zásobníkem však může být správa paměti pomocí regionů flexibilnější: umožňují objektům žít déle, než když jsou umístěny v rámci zásobníku. V typických implementacích jsou všechny objekty ve stejné oblasti alokovány ve stejném souvislém rozsahu adres paměti, podobně jako jsou obvykle alokovány zásobníkové rámce.

Výhody

Ve srovnání s alokací paměti na základě zásobníku umožňuje správa paměti podle regionů přirozenější způsob implementace alokace paměti v paralelním programování. Regiony navíc výrazně usnadňují práci s virtualizací a různými technikami optimalizace výkonu paměti, což zjednodušuje úkol současného přesunu všech objektů patřících do stejné oblasti do paměti s rychlejším nebo pomalejším přístupem [2] .

Příklad

Jako jednoduchý příklad zvažte následující kód C , který přiděluje a poté uvolňuje datovou strukturu, jako je například propojený seznam :

Region * r = createRegion (); ListNode * head = NULL ; for ( int i = 1 ; i <= 1000 ; i ++ ) { ListNode * newNode = allocateFromRegion ( r , sizeof ( ListNode )); newNode -> next = head ; hlava = novýUzel ; } // ... // (zde použijte seznam) // ... zničitRegion ( r );

Přestože vytvoření propojeného seznamu vyžadovalo mnoho operací, lze jej rychle zničit jednou operací, čímž se uvolní oblast, kam byly umístěny položky seznamu. Není třeba skenovat seznam a mazat jeho prvky jednotlivě.

Implementace

Jednoduché explicitní oblasti lze snadno implementovat; následující popis je založen na článku Davida Hansona [ 3 ] . Každá oblast je implementována jako propojený seznam velkých bloků paměti; každý blok musí být dostatečně velký, aby alokoval paměť pro mnoho objektů v něm. Struktura dat regionu obsahuje ukazatel na další volnou pozici v bloku, a pokud je blok plný, systém správy paměti přidělí nový blok a přidá jej do seznamu. Když se oblast uvolní, ukazatel další volné polohy se resetuje na začátek prvního bloku a celý seznam již vytvořených bloků lze znovu použít k přemístění objektů v oblasti. V alternativní implementaci, když je oblast uvolněna, může být seznam bloků, které jsou jí přiděleny, vrácen do globálního volného seznamu, ze kterého mohou později další oblasti přidělovat nové bloky. V rámci takto jednoduchého schématu však není možné jednotlivě uvolnit paměť od konkrétních objektů v rámci bloku.

Režie na přidělený bajt je pro toto schéma velmi nízká. Téměř všechny epizody alokace paměti zahrnují pouze porovnávání a aktualizaci ukazatele na další volnou pozici. Jedinou výjimkou jsou epizody, kdy dojde paměť v bloku a správce paměti musí k oblasti připojit nový blok. Uvolnění oblasti je operace s pevným časem, která se provádí jen zřídka. Na rozdíl od typických systémů pro shromažďování odpadků nemusí správa dat podle regionů označovat každý datový objekt jeho typem .

Historie a koncepty

Samotný koncept regionů je velmi starý. Poprvé byl implementován v roce 1967 v balíčku volného úložiště Douglas Ross AED , ve kterém byla paměť rozdělena do hierarchie zón. Pro každou ze zón může být disciplína správy paměti konfigurována individuálně. Každá ze zón mohla být uvolněna jednou společnou operací. Ross tedy v tomto softwarovém balíku poprvé prakticky implementoval koncept správy paměti založené na regionech [4] . V roce 1976 byl datový typ AREA zahrnut do jazykového standardu PL/I pro skupinovou správu datových struktur [5] . V roce 1990 Hanson demonstroval, že explicitně definované oblasti v C (které nazval arény) ve správě paměti mohou poskytnout výkon, měřený jako čas strávený na přidělený bajt, který překonává i nejrychlejší známý mechanismus alokace haldy [3] . Explicitní regiony hrály důležitou roli ve vývoji řady raných softwarových projektů založených na C, včetně Apache HTTP Server , kde se nazývají pooly, a PostgreSQL , kde se nazývají paměťové kontexty [6] . Stejně jako tradiční alokace haldy tato schémata neposkytují zabezpečení přístupu do paměti ; programátor může přistupovat k oblasti paměti poté, co byla uvolněna prostřednictvím visícího odkazu, nebo zapomenout oblast uvolnit, což má za následek únik paměti .

Odvození regionů

V roce 1988 začali vědci zkoumat, jak používat regiony pro bezpečnou alokaci paměti, a představili koncept inference regionu . V rámci této techniky jsou direktivy pro přidělování a uvolňování oblastí, stejně jako jednotlivé objekty umístěné v paměti, které jsou staticky propojeny s konkrétní oblastí, vloženy do kódu ve fázi kompilace kompilátorem. Kompilátor ví, jak to udělat tak, že může zaručit absenci visících ukazatelů a úniků paměti. V rané práci Ruggieri a Murtagh prozkoumali variantu této techniky, ve které je oblast vytvořena, když je každá funkce vykonána a uvolněna, když skončí [7] . Přitom použili analýzu toku dat k určení doby životnosti pro každý staticky alokovaný paměťový objekt a poté přiřadili tento objekt k přidělení nejmladší oblasti podle doby vytvoření, která obsahuje objekty s touto životností. V roce 1994 byla tato práce shrnuta v původní práci Tofteho a Talpina, kteří rozšířili techniku ​​navrženou Ruggierim a Murtaghem o podporu typového a funkčního polymorfismu vyššího řádu ve funkcionálním programovacím jazyce Standard ML . Práce Tofteho a Talpina použila jiný algoritmus založený na odvození typu a teoretických konceptech typů regionů a počtu regionů [8] [9] . Navrhli rozšíření lambda kalkulu, včetně regionů jako zvláštní entity. Ve skutečnosti přidali do lambda kalkulu následující dva konstrukty:

e 1 na ρ: vypočítejte výsledek výrazu e 1 a uložte jej do oblasti ρ; letregion ρ v e2 end: vytvořte oblast a spojte ji s ρ; vypočítejte e 2 a poté uvolněte oblast.

Kvůli této syntaktické struktuře jsou oblasti „vnořené“, což znamená, že pokud je r 2 vytvořeno po r 1 , musí být také uvolněno před r 1 . Výsledkem je „hromada“ regionů. Kromě toho musí být regiony uvolněny ve stejné funkci, ve které byly vytvořeny. Omezení byla částečně uvolněna Aikenem et al [10] .

Tento rozšířený počet lambda měl sloužit jako prokazatelně paměťově bezpečná střední reprezentace pro kompilaci standardních ML programů do strojového kódu. Vytvoření překladače, který by mohl poskytovat dobré výsledky pro velké programy, však narazil na řadu praktických omezení. Musely být vyřešeny pomocí nové analýzy, včetně práce s rekurzivními voláními, tail -rekurzivními voláními a eliminací oblastí obsahujících pouze jednu hodnotu z vygenerované mezilehlé reprezentace. Tato práce byla dokončena v roce 1995 [11] . Jeho výsledky byly použity v ML Kit, verzi ML , jejíž manipulace s pamětí byla založena na regionech, namísto garbage collection. Příchod sady ML Kit umožnil přímé srovnání mezi dvěma kompilacemi středně velkých testovacích programů, které poskytly velmi odlišné výsledky („10krát rychlejší a čtyřikrát pomalejší“) v závislosti na tom, jak „přívětivý k regionu“ konkrétní testovací program bylo [12] . ML Kit byl nakonec rozšířen pro velké aplikace. Byly v něm implementovány dva doplňky: samostatná kompilace modulů a hybridní technika, která kombinuje odečítání hranic regionů s pravidelným sběrem odpadu. [13] [14]

Implementace konceptu v jiných programovacích jazycích

Po vývoji ML Kitu se regiony začaly implementovat pro další programovací jazyky:

  • V různých rozšířeních programovacího jazyka C :
    • V zabezpečeném dialektu C , Cyclone , který kromě mnoha dalších funkcí přidal podporu pro explicitní oblasti. Tento jazyk byl z velké části zaměřen na migraci stávajících aplikací do C a jejich zdokonalování pro použití regionů [15] [16] [17] .
    • Rozšíření C nazvané RC také implementovalo explicitní oblasti [18] . Tento jazyk však používá počítání referencí specifické pro region, aby dále zaručil bezpečnost paměti tím, že zajistí, aby žádná oblast nebyla uvolněna předčasně [19] [20] . Oblasti snižují režii počítání referencí, protože interní odkazy na oblasti nevyžadují aktualizaci počítadel, když se změní. RC obsahuje explicitní systém statického typu pro oblasti, který umožňuje vyhnout se některým aktualizacím refcountu [21] .
    • Podmnožina C nazvaná Control-C vyžaduje, aby programy používaly oblasti (a pouze jednu oblast v jakémkoli daném okamžiku spuštění). Tato omezení považují autoři jazyka za součást jeho návrhu, aby zajistili bezpečnost statické paměti [22] .
  • Regiony byly implementovány pro podmnožinu jazyka Java [23] a staly se kritickou součástí správy paměti v jazyce Java v reálném čase , který je kombinuje s typy vlastnictví pro řízení zapouzdření objektů a eliminaci kontrol za běhu pro uvolnění regionu [24]. [25] [26] . V poslední době byl navržen poloautomatizovaný systém pro detekci regionů ve vestavěných Java aplikacích v reálném čase, který kombinuje statickou analýzu v době kompilace, politiku alokace oblastí řízenou za běhu a rady mezi programátorem a kompilátorem [27] [28] Oblasti se dobře hodí pro výpočty v reálném čase , protože časové náklady na jejich údržbu jsou staticky předvídatelné a mnohem jednodušší než tradiční sběrače odpadu.
  • Regiony byly implementovány pro logické programovací jazyky ​​Prolog [29] [30] a Mercury [31] [32] ; v těchto implementacích byl regionální inferenční model Tofteho a Talpina rozšířen o backtracking a prolog cut prohlášení .
  • Správa paměti založená na regionech se používá v paralelním programovacím jazyce ParaSail . Vzhledem k absenci explicitních ukazatelů v ParaSail [33] není při implementaci správy paměti potřeba další mechanismus počítání referencí.

Nevýhody

Systémy využívající regiony mohou mít problémy, kdy se regiony před uvolněním velmi zvětší, a proto obsahují vysoký podíl mrtvých dat. Takové oblasti se obvykle nazývají „úniky paměti“ (ačkoli jsou nakonec uvolněny). Oprava těchto úniků může vyžadovat restrukturalizaci programu. Obvykle se vyrábí přidáním nových oblastí s kratší životností. Ladění tohoto typu problému je obzvláště obtížné na systémech, které používají inferenci regionu , kde programátor musí porozumět inferenčnímu algoritmu, který je základem systému, nebo podrobně analyzovat přechodnou reprezentaci , aby diagnostikoval problém. Ladění programů pomocí tradičních garbage collectorů je mnohem jednodušší a včasného uvolnění paměti, která se dostane do netěsností, lze dosáhnout bez restrukturalizace programu, jednoduše odstraněním logických chyb v jeho konstrukci. Tyto úvahy daly vzniknout hybridním systémům kombinujícím oblastní správu paměti a konvenční garbage collection [13] . Na druhou stranu při ladění programů pomocí garbage collection může také dojít k únikům, pokud jsou uloženy odkazy na data, která již nebudou nikdy znovu použita, a tuto okolnost musí programátor sledovat mnohem pečlivěji než v systému s regionem správa paměti.

Správa paměti na základě oblastí funguje nejlépe, když je počet oblastí relativně malý a každá oblast obsahuje mnoho objektů. Programy, které obsahují mnoho řídkých regionů, budou trpět vnitřní fragmentací . To může v konečném důsledku vést ke ztrátě paměti a dalšímu času strávenému správou oblastí. Při práci s výstupem regionu může být opět obtížnější diagnostikovat tento problém.

Hybridní techniky

Jak bylo uvedeno výše, jazyk RC používá hybridní techniku ​​správy paměti, která zahrnuje regiony a počítání referencí . Tento přístup snižuje režii počítání referencí, protože propojení mezi objekty v oblasti nevyžadují aktualizaci čítačů, když jsou změněny, přidány nebo odebrány. Podobně některé hybridní metody využívající označování regionů kombinují sledování dosažitelnosti objektů sběru odpadu s regiony. Takové metody zahrnují rozdělení haldy do oblastí, provedení sledovacího průchodu, který označí všechny oblasti obsahující živé objekty, a pak uvolnění všech neoznačených oblastí. Aby byl tento přístup účinný, vyžaduje neustálou defragmentaci paměti [34] .

Poznámky

  1. v ruských zdrojích se tento termín téměř nepoužívá
  2. To může být nezbytné například pro umístění všech objektů souvisejících s konkrétní instancí paralelně prováděné procedury do paměťové sekce blízko konkrétního procesoru víceprocesorového systému .
  3. 1 2 Hanson, David R. Rychlá alokace a dealokace paměti na základě životnosti objektů  //  Software: Praxe a zkušenosti: deník. - 1989. - Sv. 20 , č. 1 . - str. 5-12 . - doi : 10.1002/spe.4380200104 . Archivováno z originálu 20. října 2012.
  4. Ross, Douglas. Balíček volného úložiště AED  (anglicky)  // Communications of the ACM . - 1967. - Sv. 10 , č. 8 . - str. 481-492 . - doi : 10.1145/363534.363546 .
  5. American National Standards Institute, Inc. Americký národní standardní programovací jazyk PL/I  (angličtina) . — 1976.
  6. 2010 PostgreSQL Global Development Group. Část 41.3: Správa paměti . Dokumentace PostgreSQL 8.2.15 (1996). Získáno 22. února 2010. Archivováno z originálu 12. února 2010.
  7. Ruggieri, Cristina; Murtagh, Thomas P. (1988). “Analýza životnosti dynamicky alokovaných objektů” . POPL '88: Sborník příspěvků z 15. sympozia ACM SIGPLAN-SIGACT o principech programovacích jazyků . New York, NY, USA: ACM. DOI : 10.1145/73560.73585 . Staženo 22. února 2010 .
  8. Tofte, Mads; Jean-Pierre Talpin (1993). A Theory of Stack Allocation in Polymorphically Typeed Languages ​​​​(Technická zpráva). Katedra informatiky, Kodaňská univerzita. 93/15. Dne Citeseer Archivováno 21. června 2007.
  9. Tofte, Mads ; Talpin, Jean-Pierre (1994). “Implementace typizovaného Call-by-Value λ-kalkulu pomocí Stack of Regions” . POPL '94: Sborník příspěvků z 21. sympozia ACM SIGPLAN-SIGACT o principech programovacích jazyků . New York, NY, USA: ACM. str. 188&ndash, 201. DOI : 10.1145/174675.177855 . ISBN  0-89791-636-0 . Archivováno z originálu dne 2014-07-04 . Načteno 15. dubna 2014 . Použitý zastaralý parametr |deadlink=( nápověda )
  10. Aiken, Alex; Manuel Fähndrich, Raph Levien (1995). Lepší správa statické paměti: Zlepšení regionální analýzy jazyků vyššího řádu ​​(technická zpráva). Katedra EECS, University of California, Berkeley. UCB/CSD-95-866. Dne Citeseer Archivováno 21. června 2007.
  11. Birkedal, Lars ; Tofte, Mads ; Weilstrup, Magnus (1996). „Od odvození regionu k von Neumannovým strojům prostřednictvím odvození reprezentace regionu“ . POPL '96: Sborník příspěvků z 23. sympozia ACM SIGPLAN-SIGACT o principech programovacích jazyků . New York, NY, USA: ACM. str. 171&ndash, 183. DOI : 10.1145/237721.237771 . ISBN 0-89791-769-3 . Staženo 22. února 2010 .  
  12. Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels. Retrospektiva správy paměti založené na regionech // Symbolické výpočty vyššího řádu. - 2004. - T. 17 , č. 3 . S. 245–265 . ISSN 1388-3690 . - doi : 10.1023/B:LISP.0000029446.78563.a4 .
  13. 1 2 Hallenberg, Niels; Elsman, Martin; Tofte, Madsi. Kombinace odvození regionu a shromažďování odpadků // Upozornění SIGPLAN. - 2003. - T. 37 , č. 5 . S. 141–152 . ISSN 0362-1340 . - doi : 10.1145/543552.512547 .
  14. Elsman, Martin. Bezpečnost shromažďování odpadků pro oblastní správu paměti  //  SIGPLAN Notices: journal. - 2003. - Sv. 38 , č. 3 . S. 123–134 . ISSN 0362-1340 . - doi : 10.1145/640136.604190 .
  15. Cyklon: ​​Úvod do regionů . Cyclone uživatelská příručka . Získáno 22. února 2010. Archivováno z originálu 21. srpna 2010.
  16. Grossman, Dan; Morrisett, Greg; Jim, Trevor; Hicks, Michael; Wang, Yanling. Správa paměti podle regionů v cyklonu // Upozornění SIGPLAN. - 2002. - T. 37 , č. 5 . S. 282–293 . - doi : 10.1145/543552.512563 .
  17. Hicks, Michael; Morrisett, Greg ; Grossman, Dan (2004). „Zkušenosti s bezpečnou manuální správou paměti v cyklonu“ . ISMM '04: Sborník příspěvků ze 4. mezinárodního sympozia o správě paměti . New York, NY, USA: ACM. str. 73&ndash, 84. DOI : 10.1145/1029873.1029883 . ISBN 1-58113-945-4 . Staženo 22. února 2010 .  
  18. Gay, David RC - Bezpečná, oblastně založená správa paměti pro C (downlink) . Domovská stránka Davida Gaye . Intel Labs Berkeley (1999). Získáno 22. února 2010. Archivováno z originálu 26. února 2009. 
  19. Gay, David ; Aiken, Alex (1998). „Správa paměti s explicitními oblastmi“ . PLDI '98: Sborník z konference ACM SIGPLAN 1998 o návrhu a implementaci programovacího jazyka . New York, NY, USA: ACM. str. 313&ndash, 323. DOI : 10.1145/277650.277748 . ISBN 0-89791-987-4 . Staženo 22. února 2010 .  
  20. Gay, David Edward (2001). Správa paměti s explicitními oblastmi (PDF) (PhD v oboru informatiky). Kalifornská univerzita v Berkeley. Archivováno (PDF) z originálu dne 2019-09-07 . Načteno 20. února 2010 . Použitý zastaralý parametr |deadlink=( nápověda )
  21. Gay, David ; Aiken, AlexJazyková podpora pro regiony // Upozornění SIGPLAN. - 2001. - T. 36 , č. 5 . — S. 70–80 . — ISSN 0362-1340 . - doi : 10.1145/381694.378815 .
  22. Kowshik, Sumant; Dhurjati, Dinakar; Adve, Vikram (2002). „Zajištění bezpečnosti kódu bez kontrol za běhu pro řídicí systémy v reálném čase“ . PŘÍPADY '02: Sborník z mezinárodní konference o kompilátorech, architektuře a syntéze pro vestavěné systémy z roku 2002 . New York, NY, USA: ACM. str. 288&ndash, 297. DOI : 10.1145/581630.581678 . ISBN 1-58113-575-0 . Staženo 22. února 2010 .  
  23. Christiansen, Morten V. (1998). Správa paměti založená na regionech v Javě (diplomová práce Masters in Computer Science). Katedra informatiky (DIKU), Univerzita v Kodani . Načteno 20. února 2010 .  (nedostupný odkaz)
  24. Beebee, William S.; Rinard, Martin C. (2001). “Implementace Scoped Memory pro Real-Time Java” . EMSOFT '01: Sborník z prvního mezinárodního workshopu o vestavěném softwaru . Londýn, Spojené království: Springer-Verlag. str. 289&ndash, 305. ISBN  3-540-42673-6 . Staženo 22. února 2010 . (nedostupný odkaz)
  25. Sălcianu, Alexandru; Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard (2003). Typový systém pro bezpečnou oblastní správu paměti v Real-Time Java (PDF) (Technická zpráva). Laboratoř výpočetní techniky MIT. MIT-LCS-TR-869. Archivováno (PDF) z originálu dne 28.09.2021 . Staženo 29. 4. 2020 . Použitý zastaralý parametr |deadlink=( nápověda )
  26. Boyapati, Chandrasekhar ; Salcianu, Alexandru ; Beebee, Jr., William (2003). „Typy vlastnictví pro bezpečnou správu paměti založenou na regionech v Javě v reálném čase“ . PLDI '03: Sborník z konference ACM SIGPLAN 2003 o návrhu a implementaci programovacího jazyka . New York, NY, USA: ACM. str. 324&ndash, 337. DOI : 10.1145/781131.781168 . ISBN 1-58113-662-5 . Staženo 22. února 2010 .  
  27. Nahkli, Chaker ; Rippert, Christophe ; Salagnac, Guillaume ; Yovine, Sergio (2007). „Efektivní správa paměti založená na regionech pro vestavěné systémy v reálném čase s omezenými zdroji“ (PDF) . Sborník příspěvků z "Workshopu o implementaci, kompilaci, optimalizaci objektově orientovaných jazyků, programů a systémů (ICOOOLPS'2006)" . Archivováno (PDF) z originálu 2012-02-26 . Staženo 22. února 2010 . Použitý zastaralý parametr |deadlink=( nápověda )
  28. Salagnac, Guillaume ; Rippert, Christophe (2007). „Poloautomatická správa paměti založená na regionech pro vestavěné systémy Java v reálném čase“. RTCSA '07: Sborník z 13. mezinárodní konference IEEE o vestavěných systémech a aplikacích výpočetních systémů v reálném čase . Washington, DC, USA: IEEE Computer Society. str. 73&ndash, 80. DOI : 10.1109/RTCSA.2007.67 . ISBN 978-0-7695-2975-2 .  
  29. Makholm, Henning (2000). Správa paměti založená na regionech v Prologu (PDF) (diplomová práce Masters in Computer Science). University of Copenhagen, Dánsko. Archivováno z originálu (PDF) dne 5. června 2011 . Načteno 20. února 2010 .
  30. Makholm, Henning (2000). „Správce paměti založené na regionech pro prolog“ . ISMM '00: Sborník příspěvků z 2. mezinárodního sympozia o správě paměti . New York, NY, USA: ACM. str. 25&ndash, 34. DOI : 10.1145/362422.362434 . ISBN 1-58113-263-8 . Staženo 22. února 2010 .  
  31. Phan, Quan ; Janssens, GerdaAnalýza statické oblasti pro Merkur. - Springer Berlin / Heidelberg, 2007. - T. 4670/2007. — S. 317–332. — (Poznámky z informatiky). - ISBN 978-3-540-74608-9 . - doi : 10.1007/978-3-540-74610-2 .
  32. Phan, Quan ; Somogyi, Zoltan (2008). „Běhová podpora pro oblastní správu paměti v Mercury“ . ISMM '08: Sborník příspěvků ze 7. mezinárodního sympozia o správě paměti . New York, NY, USA: ACM. str. 61&ndash, 70. DOI : 10.1145/1375634.1375644 . ISBN  978-1-60558-134-7 . Archivováno z originálu dne 2018-06-01 . Načteno 15. dubna 2014 . Použitý zastaralý parametr |deadlink=( nápověda )
  33. Taft, Tucker Cesta bez ukazatelů k objektově orientovanému paralelnímu programování . Blog ParaSail (2012). Získáno 14. září 2012. Archivováno z originálu 13. srpna 2012.
  34. Blackburn, Stephen M .; McKinley, Kathryn S. (2008). „Immix: sběrač odpadu ve značkové oblasti s prostorovou efektivitou, rychlým sběrem a výkonem mutátorů“ . PLDI '08: Sborník z konference ACM SIGPLAN z roku 2008 o návrhu a implementaci programovacího jazyka . New York, NY, USA: ACM. str. 22&ndash, 32. DOI : 10.1145/1375581.1375586 . ISBN  978-1-59593-860-2 . Archivováno z originálu dne 2018-11-19 . Načteno 15. dubna 2014 . Použitý zastaralý parametr |deadlink=( nápověda )