Система за почистване на паметта (компютърни науки)

Система за почистване на паметта (СПП) (на английски: garbage collection) в информатиката е форма на автоматично управление на паметта. Тя се опитва да почисти „боклука“ или да освободи паметта, използвана от обекти, които вече няма да се използват при изпълнението на програмата. Създадена е от Джон Маккарти през 1959, за да се замени ръчното управление на паметта в Лисп.

СПП е често описвана като противоположност на ръчното управление, което задължава програмиста да посочва кои обекти да освобождава и връща на системната памет. Много системи използват комбиниран подход, включващи други техники като stack allocation и region inference. За разлика от други техники за управляване на паметта, СПП може да консумира значителна част от времето за обработка на програмата и като резултат, може да има значително влияние върху производителността.

Ресурси като network sockets, database handles, user interaction windows и файлове и дескрипторни устройства, обикновено не се обработват от СПП. Методите за управление на тези ресурси, например деструкторите, може да са достатъчни за управление на паметта и тогава няма нужда от СПП. Някои СПП позволяват свързването на такива други ресурси с определен регион от паметта, така че позволяват тяхното рекултивиране – това се нарича финализация. Финализацията може да причини усложнения като недопустима латентност между бездействие и възстановяване, особено при ограничени ресурси или липса на контрол върху коя точно нишка се изпълнява регенерирането, което ограничава ползата от нея.

Принципи

Основните принципи на работа на СПП са да се намерят обектите, които няма да бъдат необходими в бъдеще и да се възстановят ресурсите, използвани от тях.

Много програмни езици изискват СПП, като част от езиковите спецификации (например Java, C#, D language, Go и повечето скриптови езици) или ефективно за практическото изпълнение (например формалните езици като lambda calculus). За тях може да се каже, че са СПП езици. Други езици са проектирани да използват ръчно управление на паметта, но разполагат и със СПП (например C и C++). Някои езици като Ada, Modula-3, и C++/CLI, позволяват СПП и ръчното управление на паметта да съществуват заедно, като използват разделени heaps за събираните и ръчно управляваните обекти. Други като D имат СПП, но позволяват на потребителя ръчно да изтрива обекти и също така да изключва СПП, когато се изисква скорост.

Предимства

СПП освобождава програмиста от ръчна работа с паметта. Като резултат някои категории бъгове се елиминират или намаляват значително. Такива са:

• Dangling pointer bugs
• Двойно освободени бъгове (Double free bugs), които се появяват, когато програмата се опитва да освободи област от паметта, която вече е освободена и вероятно вече е разпределена отново.
• Определени видове от memory leaks, в която една програма не успее да освободи памет заета от обекти, които са станали недостъпни, което води до изчерпване на паметта.
• Някои от бъговете разгледани от СПП могат да доведат до последствия за сигурността.

Недостатъци

Обикновено СПП има определени недостатъци включващи консумирането на допълнителни ресурси и несъвместимост с ръчно управление на ресурсите.

• СПП консумира компютърни ресурси за вземане на решения, коя памет да освободи, въпреки че програмиста може би вече знае тази информация.
• Моментът в който „боклукът“ се събира, може да непредсказуем, в резултат на което забавянията са разпръснати из сесията. Непредсказуемите забавяния могат да бъдат неприемливи в реално време и в интерактивни програми. Допълнителните едновременни системи за почистване на паметта се справят с тези проблеми с различни компромиси.
• Модерните реализации на СПП се опитват да избегнат забавянията, наречени „спрете-света“, като извършват повече работа фоново, например маркират недостижимите непотребни инстанции, докато процесът продължава да тече. Независимо от тези подобрения, например в .NET CLR все още е много трудно да се поддържат големи купчини от милиони обекти с резидентни обекти, които се насърчават да наследят старите поколения, без да има забележими закъснения (понякога няколко секунди).

Следяща СПП

Следящата СПП е най-често срещаният тип СПП. Цялостната стратегия се състои от определяне на това кои предмети трябва да бъдат събрани от СПП чрез проследяване на обекти, които са с лесен достъп. Въпреки това, съществуват голям брой алгоритми, използвани в изпълнението, с най-различна сложност и работни характеристики.

Референтно броене

• Референтното броене е форма на СПП, при която всеки обект има брояч на препратките към него. „Боклуците“ се идентифицират чрез стойност нула на брояча. Референтният брояч на даден обект се увеличава, когато се създава препратка към него, и намалява когато референцията е унищожена. Когато броячът стане нула, паметта на обекта е рекултивирана.
• Както при ръчно управляваната памет, и за разлика от следящата СПП, методът на референтно броене гарантира, че обектите се унищожават веднага щом изчезне последната им референция и по този начин няма значителни отрицателни странични ефекти върху процесорния кеш и виртуалната оперативна памет.
• Референтното броене има и редица недостатъци, но те обикновено могат да бъдат решени или смекчени чрез по-сложни алгоритми.

Цикли

• Ако два или повече обекта препращат един към друг, те могат да създадат цикъл, при който няма да се съберат като техни взаимни препратки и никога не позволяват техния референтен номер да стане нула. Някои СПП използват референтно броене (като това в CPython) което използва определен цикъл за откриване на алгоритми, за да се справят с този проблем.
• Друга стратегия е да се използват слаби референции за „предишни указатели“, които създават цикли. Слабата референция при референтното броене е подобна на слаба референция в следяща СПП и представлява специален референтен обект, чието съществуване не увеличава референтния брояч на обекта. Освен това, при слаба референция когато обектът става „боклук“, тя изчезва, вместо да остане висяща, което означава, че тя се превръща в една предвидима стойност, като например нулева референция.

Space overhead

Референтното броене изисква пространство, за да бъде разпределено за всеки обект, за съхранение на референтния брой. Броят може да се съхранява в близост до паметта на обекта, в отделна таблица или някъде другаде, но и в двата случая, всеки един рефертно броящ се обект изисква допълнително място за съхранение за своето референтно преброяване. Паметта обикновено се използва за тази задача, което означава, че 32 или 64 битова препратка се съхранява в референтно броящият склад и трябва да бъде разпределена за всеки обект.

В някои системи това натоварване е възможно да се намали с помощта на показател за съхранение на референтния брой в неизползвани части от паметта на обекта. Често архитектурата не позволява на програмата да използва пълния диапазон на паметта.

Ако обект има указател на определено място, референтния брой може да се съхранява в неизползвани битове. Например, всеки обект в Objective-C има указател към класа в началото на паметта; при ARM64 архитектура с помощта на IOS 7, са използвани 19 неизползвани части от този клас за съхраняване на референтния брой на обекта.

Speed overhead (нарастване / намаляване)

Всяка справка попадаща извън обхвата често изисква модификации на един или повече референтни броячи. Въпреки това, в общия случай, когато справката се копира в променлива и след това във вътрешна (вложена) променлива, така че животът на вътрешната променлива е ограничен от времето на животът на външната, тази референция, увеличаване може да бъде елиминирана. Външната променлива „притежава“ собствена референция. В програмния език C++, тази техника се прилага лесно и доказано с използването.

Референтно броене в C++ обикновено се осъществява чрез използване на „умни“ указатели, чиито конструктори, деструктори и оператори за присвояване управляват препратките. „Умен“ указател може да се предава чрез препратка към функция, която се избягва необходимостта да копирате конструкцията на нов „умен“ указател (което би увеличило референтния брой на влизане във функцията и да го намалят на излизане). Функцията получава препратка към „умен“ указател, който се произвежда евтино.

Изискване за атомарност

В многонишкова среда тези модификации (увеличаване и намаляване) може да се наложи да бъдат атомарни операции (изпълняват се като едно цяло или въобще не се изпълняват) като compare-and-swap, поне за споделените или потенциално споделените между много нишки обекти. Атомарните операции са скъпи с мултипроцесори и още по-скъпи, когато трябва да емулират със софтуерни алгоритми.

Възможно е този проблем да се избегне чрез добавяне на брояч към всяка нишка или процесорна референция и те да се достъпват само когато локалните броячи са с определена стойност, но това добавя излишна памет и заради това има тенденция да се използва само в специални случаи (използва се например в Linux при референтно броене на ядрените модули).

Не е в реално време

Naive имплементации на броя референции като цяло не осигуряват поведение в real-time (реално време), защото всяко присвояване на пойнтъра може потенциално да създаде брой от обекти, свързани само с размера на крайната разпределена памет да бъдат рекурсивно освободени, докато треда е неспособен да изпълни друга задача. Възможно е за са избегне този проблем чрез делегиране но освобождаването на обекти, чиито брой референции е паднал до нулата до друг тред, с цената на допълнителна излишна памет.

Escape анализ

Escape анализ може да се използва за конвертиране на алокации на heap-а в алокации на stack-а, за да се редуцира количеството работа, от което СПП се нуждае. Това се извършва, използвайки се анализ от времето на компилиране, за да се определи който и да е алокиран обект с функция, която да не е достъпна за други функции и тредове. В такъв случай обектът може да бъде разпределен директно в stack-а на треда и освободен от там при връщане на функцията, редуцирайки потенциална излишна памет в СПП.

Compile-time

Compile-time СПП е форма на статичен анализ, позволяващ паметта да бъде използвана повторно и регенерирана въз основа на известните инварианти по време на компилация. Тази разновидност на СПП е изучена при програмния език Mercury и е приложена по-широко с въвеждането на автоматичен брояч LLVM's в екосистемата на Apple (iOS и OS X) през 2011.

Реализации

Най-общо казано, програмните езици от високо ниво е по-вероятно да имат СПП като стандартна характеристика. В езици, в които няма вградена СПП, често може да бъде добавен такъв чрез библиотека, като Boehm за C (за почти всички програми) и C++. Този подход не е без недостатъци, като например промяна на създаването на обекти и унищожителния механизъм.

Повечето функционални програмни езици, като ML, Haskell, и APL имат вградени СПП. Lisp e особено забележителен с това, че е първият функционален програмен език и първият със СПП. Други динамични езици като Ruby (но не и Perl 5 или PHP преди версия 5.3, които използват референтно броене) също имат тенденция да използват СПП. Обектно-ориентираните програмни езици като Smalltalk, Java и ECMAScript често са снабдени с интегрирана СПП. Забележими изключения са C++ и Delphi, които имат деструктори.

BASIC

В исторически план, езици като BASIC и Logo, предназначени за начинаещи, често използват СПП за heap-алокирани дължинно-стойностни типове данни като низове и списъци, така че да не товарят програмиста с ръчно управление на паметта. При ранните микрокомпютри с тяхната ограничена памет и бавен процесор, BASIC СПП би могъл да причини, очевидно случайно, необясними паузи по средата на изпълняващата се програма.

Някои BASIC интерпретации, като Applesoft BASIC от семейството на Apple II многократно сканира низовия дескриптор за низа с най-висок адрес с цел да го компактира към високата памет, резултираща в O(n2) производителност, което може да доведе до паузи в раките на минути по време на изпълнението на низ-интензивни програми. Замяната на СПП за Applesoft BASIC въвежда групи низове във всеки преход през heap-а, което скъсява времето за колекция значително.

Objective-C

Макар и Objective-C традиционно да няма СПП, с релийза на OS X 10.5 в 2007 Apple се представя СПП за Objective-C 2.0, използваща in-house разработен колектор в реално време. Обаче с релийза през 2012 на OS X 10.8 СПП е заменена с LLVM's automatic reference counter (ARC), представен в OS X 10.7. Освен това през май 2015 г. Apple дори забранява употребата на СПП за новите OS X приложения в App Store. В iOS СПП не е въведена заради проблемите в отклика и производителността на приложенията; вместо нея iOS използва ARC.

Лимитирани среди

СПП е рядко използвана във вградени системи или в такива в реално време заради нуждата му от много строг контрол над употребата на лимитирани ресурси. Обаче е разработена съвместимост за СПП с лимитирани среди. Microsoft .NET Micro Framework и Java Platform, Micro Edition са вградени софтуерни платформи, които като своите далечни братовчеди поддържат СПП.