Сакупљање смећа (рачунарство)

Овом чланку је потребна лектура текста. То подразумева исправку граматичких, правописних и интерпункцијских грешака или тона. Кликните на дугме „Уреди” и побољшајте га. (детаљније о уклањању овог шаблона обавештења)

У рачунарству, сакупљање смећа (СС) је форма аутоматског управљања меморијом. Сакупљач смећа, или само сакупљач, покушава да покупи смеће, или меморију окупирану објектима које програм више не користи. Сакупљач смећа је патентиран од стране Џона Макартнија, негде око 1959. године за апстрактно управљање меморијом у Лиспу.^[1][2]

Сакупљање смећа је чешће представљено као супротност мануелног управљања меморијом, које захтева од програмера да одреди које објекте да делоцира и врати у меморијски систем. Међутим, многи системи користе комбинацију приступа, укључујући друге технике као што је алокација језгра и приступ региона. Kao и друге технике управљања меморијом, сакупљање смећа може представљати значајан део укупне обраде времена у програму и, као резултат,  може имати значајан утицај на перформансе.

Ресурси различити од меморије, као што је интернет сокет, управљање базом података, кориснички интеракцијски прозор, и фајл и дескриптори уређаја, нису типично управљиви уз помоћ сакупљача смећа. Методе коришћене за управљање таквим ресурсима, посебно деструкторима, могу довољно добро да управљају меморијом, чинећи сакупљање смећа непотребним. Неки системи сакупљања смећа дозвољавају да други ресурси буду повезани са меморијском регијом, када се скупе, узроци других извора могу бити враћени; ово се назива финализација. Финализација може довести до компликација између ограничавања своје корисности, као што је неподношљиво кашњење између неупотребе и враћања посебно ограничених ресурса, или недостатак контроле над којим нит обавља посао враћања.

Основни принципи сакупљача смећа јесу да се нађе податак објекта у програму који се не може покренути, и вратити ресурс коришћен од стране тих објекта.

Мноштво програмских језика захтева сакупљаче смећа, као део програмске спецификације (на пример, Јава, C#, D програм, Гоу и мноштво скрипт програма) или ефективно за практичну имплементацију (нпр. , формални програми као ламбда рачун); за њих се каже да су програми за сакупљање смећа. Други програми су дизајнирани за употребу са маунелним управљањем меморије, али имају имплементацију сакупљања смећа  (нпр. C i C++). Неки програми, као Ада, Модула-3, и C++/CLI, дозвољава и сакупљање смећа и мануелно управљање меморијом да коегзистирају у истој апликацији користећи одвојене структуре података за сакупљене и мануелно управљиве објекте; неки програми, као D, имају сакупљача смећа али дозвољавају кориснику да мануелно обрише објекте и потпуно искључи сакупљање смећа када је брзина потребна.

Док интеграција сакупљача смећа у компилатору програмских језика и систему извршавања омогућава мноштво метода ,после-хока системи сакупљача смећа постоје, као АПБ (аутоматски приступ бројачу), и имају неке непотребне рекомпилације . (Пост-хок сакупљач смећа је понекад означен као колекција ђубрива.) сакупљач смећа ће скоро увек бити блиско интегрисан са меморијом алокатора.

Сакупљање смећа ослобађа програмера од мануелног слагања са меморијском делокацијом. Као резултат, одређене категорије багова су елеминисане или знатно редуковане:

• Апсолутни показивач багова, који се јављају када је део меморије слободан док су показивачи и даље ту, а један од тих показиача је неадресиран. До тада меморија се може користити у неке друге сврхе, са непредвидивим резултатима.
• Двоструко слободни багови, који се јављају када програм покушава да се ослободи дела меморије која је већ ослобођена, и можда поново подељена.
• Одређене врсте меморијских рупа (пукотина), у којим програм неуспешно покушава да ослободи меморију окупирану од стране објеката који су постали недоступни, могу довести до меморијског извршавања. (Смеће се обично не доводи у везу са неограниченом акумулациојм података (подаци који су доступни), али то заправно неће бити коришћено од стране програма.)
• Ефикасне имплементације сталних структура података.

Неки од багова, који су адресирани од стране сакупљача смећа, могу имати безбедносне компликације.

Сакупљање смећа има и неке недостатке, укључујући коришћење додатних средстава, утицај перформанси, могућа ограничења у извршавању прорама, и неусаглашеност са мануелним управљањем ресурса.

Сакупљач смећа троши рачунарске ресурсе у одлучивању који део меморије да ослободи, чак и ако је програмер већ знао ову информацију. Последица за не обележавање рока трајања објеката је та да је мануелно изворни код у ствари вишак , што може довесто до смањења или неуједначености перформанси.^[3] "Вршњак" магазин је дошао да решења да сакупљање смећа треба 5 пута меморију да компензује за простор изнад и да се изврши онолико брзо колико дозвољава експлицитно управљање меморијским менаџментом. ^[4] Интеракција са меморијско-хијерархијским ефектима може учинити простор изнад недопустивим у околностима које је тешко предвидети или детектовати у рутинском тестирању. Утицај на перформансе је навео Епл да не угради сакупљање смећа у iOS упркос томе што је то најжељенија карактеристика.^[5]

Моменат када је отпад сакупљен, може бити непредвидив, резултирајући то у виду ограничења (паузе у промени, слободна меморија). Непредвиђена ограничења могу бити неприхватљива у реалном-временском окружењу, у трансакцијском процесуирању, или иеактивним програмима. Растући, истовремени, сакупљачи смећа који раде у реалном времену, решавају ове проблеме различитим методама.

Модерне имплементације сакупљача смећа покушавају да избегну блокирање заустави свет ограничења, радећи што више у позадини, нпр. означавање недоступних инстанци отпада док апликациони процес наставља да ради. Упркос овим достигнућима, на пример у .NET CLR парадигми је и даље веома тешко одржавање великог броја објеката (милиони објеката) са резидентним објектима који су промовисани у старије генерације без запа стварања запаженијих кашњења (понекад траје неколико секунди).

Недетерминистичко сакупљање смећа је неспојиво са РАИИ (RAII) којем је управљање базирано на несакупљене ресурсе. Као резултат, потреба за експлицитнним мануелним управљањем ресурса (ослободити/затворити) за не сакупљене ресурсе, постаје преносан на композицију. То је: у не-детерминистичким системима сакуљпача смећа, ако ресурс или ресурс као објекат захтева мануелно управљање ресурсима (ослободити/затворити), и овај објекат је коришћен као део другог објекта, затим тај састављен објекат ће постати ресур као објекат који захтева мануелно управљање меморијом.

Путања сакупљања смећа је најчешћи тип сакупљања смећа, толико да се сакупљање смећа често односи на путању сакупљања смећа, чешће него остале методе као што је референтно бројање. Целокупна стратегија се статоји од одређовања које би објекте требало сакупити уз помоћ сакупљача смећа пратећи који су објекти доступни од стране ланца референци из појединих корена објеката, а остатак сматрајући смећем и покупити га. Међутим, постоје огромни бројеви алгоритама коришћених у имплементацији, са широком различитом комплексношћу и перформансним карактеристикама.

Референтно бројање је форма сакупљања смећа при чему сваки објекат има бројач броја референци на њега. Смеће је идентификовано уз помоћ бројања нулте референце. Бројач референце објеката се повећава када се креира референца на њега, а смањује када се референца уништи. Када бројач достигне нулу, меморија објеката се враћа.

Као код мануелног управљања меморијом, а за разилику од праћења сакупљања смећа, референтно бројање гарантује то да објекти буду уништени убрзо након што њихове последње референце буду уништене, а обично приступа меморији која је смештена у CPU, у објекте који су ослобођени, или директно уперене у оне, и на тај начин нема значајне негативне ефекте на CPU складиште и виртуалну меморију.

Постоји неколико мана референтног бројања; ово се генерално може решити или ублажити уз помоћ више софистицираних алгоритама:

Циклуси

Ако се два или више објекта односе један према другоме, они могу да креирају циклус којим ништа неће бити сакупљено тако што њихове заједничке референце неће допустити њиховим референцама да бројач дође до нуле. Неки системи сакупљача смећа користе референтно бројање (као у CPython-у) користећи специфичне алгоритме детектовања циклуса који се поклапају са овим исходом.^[6] Други начин је коришћење слабих референци за "реиндикаторе" који креирају циклус. Испод референтног бројања, слаба референа је слична слабој референци испод путање сакупљача смећа. To је специјални референтни објекат чија постојаност не увећава референтни бројач референтног објекта. Осим тога, слаба референца је сигурна када референтни објекат постане смеће, било која слаба референца у том случају је грешка, уместо да буде апсолутно дозвољена за преостале, тј. да се претвори у предвидиву вредност, као што је нулта референца.

Простор изнад (референтно бројање)

Референтно бројање захтева простор за расподелу складиштења објекта његовог референтног бројача. Бројач може бити сачуван упоредно у меморији објекта или у неком другом делу, али у сваком случају, свака појединачно избројана референца објекта захтева додатну меморију за референтни бројач. Меморијски простор са неприкљученим индикатором је често коришћен за овај случај, мислећи да 32-битни или 64-битни референтни бројачи морају бити расподељени на сваки објекат.

На неким системима је могуће смањити просто изнад користећи таговане индикаторе да сачувају референтни бројач у некоришћеним деловима меморије објекта. Често, архитектура не дозвољава програмима да 100% приступе адреси меморија која би се могла сачувати у свом природном индикатори; одређени број високих бајтова у адреси је неприметно или означено нулом. Ако се поуздано зна да објекат има индикатор на одређеној локацији, референтно бројање може бити сачувано у некоришћеним бајтовима индикатора. На пример, сваки објекат у Објектив-C-у има индикатора својекласе на почетку своје меморије; на ARM архитектури коришћеној у iOS 7, 19 некоришћених бајтова те класе индикатора је искоришћено да сачува референтни бројач објеката.
^[7][8]

Брзина простора изнад (раст/опадање)

У непогодним имплементацијама, сваки пренос референци и свако издвајање референци из делокруга често захтева модификације једног или више референтних бројача. Међутим, у очекиваном случају када је референца копирана од порменљиве (која је изван делокруга) у променљиву (које је у оквиру делокруга) тако да је животни век трајања променљиве унутар делокруга ограничен животним веком трајања променљиве која је изван делокруга, раст референце може бити елеминисана. Променљиве изван делокруга "поседују" референце. У програмском језику C++, ова техника је убачена и демонстрирана коришћењем const  референци.

Референтни бројач у C ++ је обично убачен користећи "паметне индикаторе" којим конструкотри, деструктори и задати оператори управљају уз помоћ референци. Паметан индикатор се може прећи преко референце до функције, која избегава потребу да буде копирана-конструкција новох паметнијег индикатора (који би повећао референтни бројач у уласку у функцију а смањио на изласку). Уместо тога, функција добија референцу са паметним индикатором који је јефтино произведен.

Потребна валентност

Када се користи у вишенитном окружењу, ове модификације (раст и опадање) могу бити потребне за валентне операције као што је упореди-и-размени, најмање за било који објекат који је доступан или потенцијално доступан међу више нити. Валентне операције су скупе на мултипроцесору, а још су скупље ако морају да буду слични са софтверским алгоритмима. Могуће је избећи овај проблем додајући по-навоју или по-CPU референтне бројаче и једини приступ глобалном референтном бројачу када локални референтни бројач постане или није више нула (или, другачије, користећи бинарно стабло реферетних бројача, или дати детерминистичку деструкцију у заемну за не добијање глобалног референтног бројача), али ово додаје значајну меморију изнад и на тај начин тежи да буде корисно само у специјалним случајевима (користи се, нпр. у референтном бројачу Линуксовог језгра модула).

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

Непрактичне имплементације референтног бројача генерално немају понашање реалног времена, зато што било који пренесени индикатор може потенцијално изазвати ограничени број објеката од стране расподељене величине меморије која је рекурзивно ослобођена док нит не може да обавља друге послове. Могуће је избећи овај проблем уз помоћ делегирања слободних објеката чији се референтни бројачи одбацују тј. изједначавају се са нулом за остале навоје, на трошку "простора изнад".

Избегавање анализе се може користити за претварање гомиле расподела у ограничене расподеле, смањујући износ потребног посла који ће бити одрађен од стране сакупљача смећа. Ово је урађено користећи анализу извршавања времена да би се одредио расподељени објекат без функције, који није приступачан изван тога (избегавање), на друге функције или теме. У таквом случају објекат се може расподелити директно на повезана ограничења и ослободити када се функција врати, смањујучи потенцијалну грешку сакупљача смећа.

Време извршавања сакупљања отпадака је форма статичке аналите која дозвољава меморији да се поново користи и буде враћена базирано на познате инваријанте током компилације. Ова форма сакупљања смећа је проучавана у Меркуријевом програмском језику,^[9] и показао се ефикаснијим са увођењем ВМНР аутоматски бројач референци (AБЦ)у Еплов екосистем (iOS и OS X) у 2011.^[10][11][12]

Генерално, програмски језици високог нивоа би требало да имају сакупљање смећа као стандардну одлику. У програмима који немају уграђено сакупљање смећа, оно се може додати кроз библиотеку, као што је случај са Боемов сакупљач смећа за C (за "скоро све програме") и C++. Овај приступ има грешке, као што је мењање креирања објекта и уништавање механизма.

Најфункционалнији програмски језици као што су МЛ (ML), Хаскел (Haskell) и АПЛ(APL), имају уграђено сакупљање смећа. Lisp је посебно значајан као први функционални програмски језик и као први програмски језик који је увео сакупљање смећа.

Остали динамички програми, као што је Руби (али не и Перл 5 или PHP пре верзије 5.3,^[13] који користе референтно бројање), такође користе сакупач смећа. Објектно оријентисани програми као што су Smalltalk, Јава и ЕЦМАСкрипт обично пружају интегрисано сакупљање смећа. Изузеци су C++ и Делфи који имају деструкторе.

Историјски гледано, програми намењени за почетнике, као што су Бејсик и Лого, су чешће користили сакупљање смећа за гомилу-алоцираних променивих-дужина типова података, као што су стрингови и листе, тако да не оптерећује програмере са мануелним управљањем меморије. На првим микрокомпијутерима, са њиховом лимитираном меморијом и спорим процесором, Бејсиков сакупљач смећа је могао често да изазове насумично, необјашњиве паузе усред извршавања програма.

Неки Бејсикомови интерпретатори, као што је Еплсофт БЕЈСИК из Епл 2 фамилије, су у више наврата скенирали стрингове дескрипторе за стринг који има највећу адресу да би био компактан у односу на високу меморију, дајући  Велико О перформансу, која може да произведе паузе од неколико минута у току извршавања интезивних програма. Измењени сакупљач смећа за Еплсофт БЕЈСИК представљен у Зови-EПЛ (Јануар 1981, 40-45 страна, Ренди Вигинтон) је идентификовао групу стрингова у сваком прелазу преко гомиле, што смањује драматично време сакупљања. БЕЈСИК. Систем, изашао 1983 у ПроДОС-у, садржи прозорски сакупљач смећа за БЕЈСИК који упрошћава мноштво сакупљања у фракцији секунде. 

Док Објектив-C традиционално није имао сакупљање смећа, са излазом ОS X 10.5 у 2007. години Apple Inc. је увео сакупљање смећа за Објектив-C 2.0, користећи  развијени брзи сакупљач.^[14] Међутим, у 2012, са изласком OS X 10.8, сакупљање смећа је застарело у корист LLVM-овог аутоматског приступа бројача (АПБ) који је уведен са OS X 10.7.^[15] Осим тога, од маја 2015, Епл забрањује коришћење сакупљања смећа за нове OS X апликације у Епл продавници.^[12][16] У iOS-у, сакупљње смећа се никада није користило за проблеме у перформансама апликације; уместо, iOS-a користи се AПБ.^[10]

Сакупљање смећа је ретко коришћено на уграђене системе или системе у реалном времену због строге потребе за уском контролом преко коришћења лимитираних ресурса. Међутим, сакупљачи смећа су компатибилни са лимитираним окружењима и тако су се развијали.^[17] Мајкрософтов. НЕТ Микро фрејмворк и Јава Платформа, Микро едиција су уграђене софтверске платформе тако да садрже сакупљаче смећа, као и њихови рођаци.

• Деструктор (рачунарство)
• Интернационални Симпозијум за управљање меморијом
• Управљање меморијом
• Дизајн изума библиотеке објекта

• Napier, Rob; Kumar, Mugunth (20. 11. 2012). iOS 6 Programming Pushing the Limits: Advanced Application Development for Apple iPhone, iPad and iPod Touch. John Wiley & Sons. ISBN 978-1-118-44997-4. 
• Jones, Richard; Hosking, Antony; Moss, Eliot (19 August 2011). The Garbage Collection Handbook: The Art of Automatic Memory Management. CRC Applied Algorithms and Data Structures Series. Chapman and Hall/CRC. Jones, Richard; Hosking, Antony; Moss, Eliot (17. 8. 2011). The Garbage Collection Handbook: The Art of Automatic Memory Management. Taylor & Francis. ISBN 978-1-4200-8279-1. CS1 одржавање: Формат датума (веза)
• Jones, Richard; Lins, Rafael D. . Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley. Jones, Richard; Lins, Rafael (1996). Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley. ISBN 978-0-471-94148-4. 
• Wilson, Paul R.; Johnstone, M. S.; Neely, M.; Boles, D. (1995). „"Dynamic Storage Allocation: A Survey and Critical Review"”. CiteSeerX 10.1.1.47.275 . . International Workshop on Memory Management.
• Wilson, Paul R. (1992). „"Uniprocessor Garbage Collection Techniques"”. CiteSeerX 10.1.1.47.2438 . . IWMM '92 Proceedings of the International Workshop on Memory Management (Springer-Verlag).