Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
В інформатиці, підрахунок посилань — техніка зберігання кількості посилань, вказівників або хендлерів на ресурс такий як об'єкт, ділянка пам'яті, простір диску або інший ресурс. Також це може означати алгоритм прибирання сміття, який використовує знання кількості посилань для знищення об'єктів на які більше не посилаються.
Використання в прибиранні сміття
Як одна з форм алгоритму прибирання сміття, підрахунок посилань слідкує за кількістю посилань на кожний об'єкт з боку інших об'єктів. Якщо кількість посилань об'єкта досягає нуля, об'єкт стає недосяжним, і може бути знищеним.
Коли об'єкт знищений, всі об'єкти на які він посилався зменшують свої лічильники посилань. Тобто вилучення одного посилання може викликати звільнення великої кількості об'єктів. Зазвичай використовується підхід за яким замість негайного знищення об'єкта при досягненні його лічильником посилань нуля, він додається до списку недоступних об'єктів, і через певні проміжки часу (або за потребою) один або більше елементів з цього списку знищуються.
Простий підрахунок посилань вимагає частих оновлень. Щоразу, коли посилання знищується або змінюється лічильник посилань об'єкта на який воно вело зменшується, і щоразу, коли посилання створюється або копіюється лічильник посилань відповідного об'єкта збільшується.
Підрахунок посилань також використовується в дискових операційних системах і розподілених системах, де прибирання сміття відстеженням із негайним видаленням вивільнених об'єктів також поглинає багато часу через великий розмір графу об'єктів і повільний доступ.
Переваги і недоліки
Головною перевагою підрахунку посилань над прибиранням сміття відстеженням (англ. tracing garbage collection) є те, що об'єкт утилізується одразу ж як на нього перестають посилатися, і в кроковому (англ. incremental) підході, без довгих перерв для циклів прибирання і з чіткою тривалістю життя кожного об'єкта. В реальночасових застосунках або системах з обмеженою пам'яттю, це важливо для підтримки реактивності (здатності до реагування). Підрахунок посилань також одна з найпростіших для здійснення форм прибирання сміття. Він також дозволяє ефективно керувати не тільки ресурсами пам'яті, а й об'єктами операційної системи, які набагато дефіцитніші ніж пам'ять (системи прибирання сміття використовують завершувачі (англ. finalizers) для цього, але відкладена утилізація може викликати проблеми). Зважений підрахунок посилань це хороший вихід в розподілених системах.
Цикли прибирання сміття відстеженням запускаються надто часто, якщо набір живих об'єктів займає більшу частину вільної пам'яті; така техніка потребує більше місце для ефективності. Видатність підрахунку посилань не погіршується із зменшенням вільного місця.
Кількість посилань також є корисною інформацією для інших оптимізацій часу виконання. Наприклад, системи, які активно використовують незмінні об'єкти, такими є багато функціональних мов програмування, можуть зменшити негативний вплив на ефективність через часті копіювання. Однак, якщо ми знаємо, що об'єкт має лише одне посилання (як це буває у більшості в багатьох системах), і це посилання втрачається одночасно зі створенням нового об'єкта (як в додаванні до рядка str ← str + "a"), ми можемо просто замінити цю операцію зміною первісного об'єкта.
Підрахунок посилань має два головні недоліки порівняно з прибиранням сміття відстеженням, обидві вимагають додаткові механізми для поліпшення:
- Часті оновлення які він вимагає є причиною неефективності. Хоча прибирання сміття відстеженням сильно впливає на ефективність через перемикання контексту і похибки кешу, але саме прибирання відбувається нечасто, в той час як доступ до об'єктів постійно. Також, менш важливо, підрахунок посилань вимагає від кожного об'єкта виділення місця від кількість посилань. В прибиранні сміття відстеженням, цю інформацію неявно несуть самі посилання на цей об'єкт, зберігаючи місце, хоча прибиральники сміття відстеженням, особливо кроковий, може вимагати додаткове місця для інших цілей.
- Простий алгоритм описаний вище не може обробити циклічні посилання, тобто об'єкт, який прямо або непрямо посилається на себе. Механізм, що покладається виключно на кількість посилань ніколи не розпізнає циклічні ланцюги об'єктів для вилучення через те, що їхні кількості посилань гарантовано будуть ненульовими. Підхід для цієї ситуації існує, але також збільшує накладні витрати і складність підрахунку посилань — з іншого боку, цей підхід має бути застосований лише для даних, які можуть утворювати цикли, часто це мала підмножина всіх даних. Один з таких підходів це використання .
Представлення графом
При роботі з прибиранням сміття, часто корисно думати про граф посилань, який є (орієнтованим графом) де вершинами є об'єкти і існує ребро від об'єкта A до об'єкта B якщо A містить посилання на B. Ми також маємо особливі вершини, що представляють локальні змінні і посилання, які утримує рантайм система, ніякі ребра не ведуть до цих вершин, хоча можуть вести з них до інших вузлів.
У цьому припущенні, проста кількість посилань об'єкта це вхідна степінь вершини. Вилучення вершини схоже на прибирання об'єкта. Це може відбутись лише якщо немає вхідних ребер, тобто це не впливає на кількість вихідних ребер будь-якої іншої вершини, але може вплинути на вхідну степінь інших вершин, спричиняючи їх можливе прибирання.
Одна з (компонент зв'язності) графу містить об'єкти, що не можуть бути прибраними, в той час як інші компоненти зв'язності містять сміття. За природою підрахунку посилань, кожна з компонент зі сміттям має містити не менше одного циклу.
Обробка неефективності через оновлення
Збільшення і зменшення кількості посилань щоразу, коли посилання створюється або знищується може значно зашкодити видатності. Виконання цих операцій не тільки поглинає час, але ще й шкодить видатності кешу і може призвести до конфліктів в конвеєрі. Навіть дії тільки на читання як-от підрахунок довжини списку вимагає великої кількості читань і записів для оновлення посилань при простому підрахунку посилань.
Один простий підхід для компілятора це об'єднати кілька сусідніх оновлень посилань в одне. Це особливо ефективно для посилань, які створюються і швидко знищуються. Однак, треба бути обережним і помістити об'єднане оновлення в потрібне місце задля уникнення передчасного вивільнення.
Метод відкладеного підрахунку посилань Дойтча-Боборова (англ. Deutsch-Bobrow)отримує зиск з того, що більшість оновлень кількість посилань насправді відбувається через посилання збережені в локальних змінних. Алгоритм ігнорує ці посилання, але перед тим як видалити об'єкт з нульовою кількістю посилань, система має перевірити чи немає посилань на цей об'єкт зі стека і регістрів. Перевірка відбувається коли таблиця об'єктів з нульовою кількістю посилань (англ. zero count table) заповнюється. В цій таблиці знаходять об'єкти двох типів: ті, на які посилаються лише локальні зміні і ті, на які ніхто не посилається.
Робота з циклічними посиланнями
Існує багато шляхів виконання задачі знайдення і прибирання циклічних посилань. Один з них це пряма заборона таких циклів. В деяких системах подібних до файлової системи це загальновживане рішення. Іноді, в системах з коротким часом життя і маленькою кількістю циклічного сміття, на цикли просто не звертають уваги, особливо коли система була розроблена використовуючи підхід, який уникає циклічних структур даних коли це можливо.
Інший підхід покладається на періодичне використання прибирання сміття відстеженням для утилізації циклів. Оскільки цикли зазвичай складають відносно малу частину звільненого місця, прибирання циклів може відбуватись нечасто порівняно зі звичайним прибиранням сміття відстеженням.
Примітки
- Wilson, Paul R. Uniprocessor Garbage Collection Techniques. Proceedings of the International Workshop on Memory Management. London, UK: Springer-Verlag. с. 1—42. . Section 2.1.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici pidrahunok posilan tehnika zberigannya kilkosti posilan vkazivnikiv abo hendleriv na resurs takij yak ob yekt dilyanka pam yati prostir disku abo inshij resurs Takozh ce mozhe oznachati algoritm pribirannya smittya yakij vikoristovuye znannya kilkosti posilan dlya znishennya ob yektiv na yaki bilshe ne posilayutsya Vikoristannya v pribiranni smittyaYak odna z form algoritmu pribirannya smittya pidrahunok posilan slidkuye za kilkistyu posilan na kozhnij ob yekt z boku inshih ob yektiv Yaksho kilkist posilan ob yekta dosyagaye nulya ob yekt staye nedosyazhnim i mozhe buti znishenim Koli ob yekt znishenij vsi ob yekti na yaki vin posilavsya zmenshuyut svoyi lichilniki posilan Tobto viluchennya odnogo posilannya mozhe viklikati zvilnennya velikoyi kilkosti ob yektiv Zazvichaj vikoristovuyetsya pidhid za yakim zamist negajnogo znishennya ob yekta pri dosyagnenni jogo lichilnikom posilan nulya vin dodayetsya do spisku nedostupnih ob yektiv i cherez pevni promizhki chasu abo za potreboyu odin abo bilshe elementiv z cogo spisku znishuyutsya Prostij pidrahunok posilan vimagaye chastih onovlen Shorazu koli posilannya znishuyetsya abo zminyuyetsya lichilnik posilan ob yekta na yakij vono velo zmenshuyetsya i shorazu koli posilannya stvoryuyetsya abo kopiyuyetsya lichilnik posilan vidpovidnogo ob yekta zbilshuyetsya Pidrahunok posilan takozh vikoristovuyetsya v diskovih operacijnih sistemah i rozpodilenih sistemah de pribirannya smittya vidstezhennyam iz negajnim vidalennyam vivilnenih ob yektiv takozh poglinaye bagato chasu cherez velikij rozmir grafu ob yektiv i povilnij dostup Perevagi i nedolikiGolovnoyu perevagoyu pidrahunku posilan nad pribirannyam smittya vidstezhennyam angl tracing garbage collection ye te sho ob yekt utilizuyetsya odrazu zh yak na nogo perestayut posilatisya i v krokovomu angl incremental pidhodi bez dovgih pererv dlya cikliv pribirannya i z chitkoyu trivalistyu zhittya kozhnogo ob yekta V realnochasovih zastosunkah abo sistemah z obmezhenoyu pam yattyu ce vazhlivo dlya pidtrimki reaktivnosti zdatnosti do reaguvannya Pidrahunok posilan takozh odna z najprostishih dlya zdijsnennya form pribirannya smittya Vin takozh dozvolyaye efektivno keruvati ne tilki resursami pam yati a j ob yektami operacijnoyi sistemi yaki nabagato deficitnishi nizh pam yat sistemi pribirannya smittya vikoristovuyut zavershuvachi angl finalizers dlya cogo ale vidkladena utilizaciya mozhe viklikati problemi Zvazhenij pidrahunok posilan ce horoshij vihid v rozpodilenih sistemah Cikli pribirannya smittya vidstezhennyam zapuskayutsya nadto chasto yaksho nabir zhivih ob yektiv zajmaye bilshu chastinu vilnoyi pam yati taka tehnika potrebuye bilshe misce dlya efektivnosti Vidatnist pidrahunku posilan ne pogirshuyetsya iz zmenshennyam vilnogo miscya Kilkist posilan takozh ye korisnoyu informaciyeyu dlya inshih optimizacij chasu vikonannya Napriklad sistemi yaki aktivno vikoristovuyut nezminni ob yekti takimi ye bagato funkcionalnih mov programuvannya mozhut zmenshiti negativnij vpliv na efektivnist cherez chasti kopiyuvannya Odnak yaksho mi znayemo sho ob yekt maye lishe odne posilannya yak ce buvaye u bilshosti v bagatoh sistemah i ce posilannya vtrachayetsya odnochasno zi stvorennyam novogo ob yekta yak v dodavanni do ryadka str str a mi mozhemo prosto zaminiti cyu operaciyu zminoyu pervisnogo ob yekta Pidrahunok posilan maye dva golovni nedoliki porivnyano z pribirannyam smittya vidstezhennyam obidvi vimagayut dodatkovi mehanizmi dlya polipshennya Chasti onovlennya yaki vin vimagaye ye prichinoyu neefektivnosti Hocha pribirannya smittya vidstezhennyam silno vplivaye na efektivnist cherez peremikannya kontekstu i pohibki keshu ale same pribirannya vidbuvayetsya nechasto v toj chas yak dostup do ob yektiv postijno Takozh mensh vazhlivo pidrahunok posilan vimagaye vid kozhnogo ob yekta vidilennya miscya vid kilkist posilan V pribiranni smittya vidstezhennyam cyu informaciyu neyavno nesut sami posilannya na cej ob yekt zberigayuchi misce hocha pribiralniki smittya vidstezhennyam osoblivo krokovij mozhe vimagati dodatkove miscya dlya inshih cilej Prostij algoritm opisanij vishe ne mozhe obrobiti ciklichni posilannya tobto ob yekt yakij pryamo abo nepryamo posilayetsya na sebe Mehanizm sho pokladayetsya viklyuchno na kilkist posilan nikoli ne rozpiznaye ciklichni lancyugi ob yektiv dlya viluchennya cherez te sho yihni kilkosti posilan garantovano budut nenulovimi Pidhid dlya ciyeyi situaciyi isnuye ale takozh zbilshuye nakladni vitrati i skladnist pidrahunku posilan z inshogo boku cej pidhid maye buti zastosovanij lishe dlya danih yaki mozhut utvoryuvati cikli chasto ce mala pidmnozhina vsih danih Odin z takih pidhodiv ce vikoristannya Predstavlennya grafomPri roboti z pribirannyam smittya chasto korisno dumati pro graf posilan yakij ye oriyentovanim grafom de vershinami ye ob yekti i isnuye rebro vid ob yekta A do ob yekta B yaksho A mistit posilannya na B Mi takozh mayemo osoblivi vershini sho predstavlyayut lokalni zminni i posilannya yaki utrimuye rantajm sistema niyaki rebra ne vedut do cih vershin hocha mozhut vesti z nih do inshih vuzliv U comu pripushenni prosta kilkist posilan ob yekta ce vhidna stepin vershini Viluchennya vershini shozhe na pribirannya ob yekta Ce mozhe vidbutis lishe yaksho nemaye vhidnih reber tobto ce ne vplivaye na kilkist vihidnih reber bud yakoyi inshoyi vershini ale mozhe vplinuti na vhidnu stepin inshih vershin sprichinyayuchi yih mozhlive pribirannya Odna z komponent zv yaznosti grafu mistit ob yekti sho ne mozhut buti pribranimi v toj chas yak inshi komponenti zv yaznosti mistyat smittya Za prirodoyu pidrahunku posilan kozhna z komponent zi smittyam maye mistiti ne menshe odnogo ciklu Obrobka neefektivnosti cherez onovlennyaZbilshennya i zmenshennya kilkosti posilan shorazu koli posilannya stvoryuyetsya abo znishuyetsya mozhe znachno zashkoditi vidatnosti Vikonannya cih operacij ne tilki poglinaye chas ale she j shkodit vidatnosti keshu i mozhe prizvesti do konfliktiv v konveyeri Navit diyi tilki na chitannya yak ot pidrahunok dovzhini spisku vimagaye velikoyi kilkosti chitan i zapisiv dlya onovlennya posilan pri prostomu pidrahunku posilan Odin prostij pidhid dlya kompilyatora ce ob yednati kilka susidnih onovlen posilan v odne Ce osoblivo efektivno dlya posilan yaki stvoryuyutsya i shvidko znishuyutsya Odnak treba buti oberezhnim i pomistiti ob yednane onovlennya v potribne misce zadlya uniknennya peredchasnogo vivilnennya Metod vidkladenogo pidrahunku posilan Dojtcha Boborova angl Deutsch Bobrow otrimuye zisk z togo sho bilshist onovlen kilkist posilan naspravdi vidbuvayetsya cherez posilannya zberezheni v lokalnih zminnih Algoritm ignoruye ci posilannya ale pered tim yak vidaliti ob yekt z nulovoyu kilkistyu posilan sistema maye pereviriti chi nemaye posilan na cej ob yekt zi steka i registriv Perevirka vidbuvayetsya koli tablicya ob yektiv z nulovoyu kilkistyu posilan angl zero count table zapovnyuyetsya V cij tablici znahodyat ob yekti dvoh tipiv ti na yaki posilayutsya lishe lokalni zmini i ti na yaki nihto ne posilayetsya Robota z ciklichnimi posilannyamiIsnuye bagato shlyahiv vikonannya zadachi znajdennya i pribirannya ciklichnih posilan Odin z nih ce pryama zaborona takih cikliv V deyakih sistemah podibnih do fajlovoyi sistemi ce zagalnovzhivane rishennya Inodi v sistemah z korotkim chasom zhittya i malenkoyu kilkistyu ciklichnogo smittya na cikli prosto ne zvertayut uvagi osoblivo koli sistema bula rozroblena vikoristovuyuchi pidhid yakij unikaye ciklichnih struktur danih koli ce mozhlivo Inshij pidhid pokladayetsya na periodichne vikoristannya pribirannya smittya vidstezhennyam dlya utilizaciyi cikliv Oskilki cikli zazvichaj skladayut vidnosno malu chastinu zvilnenogo miscya pribirannya cikliv mozhe vidbuvatis nechasto porivnyano zi zvichajnim pribirannyam smittya vidstezhennyam PrimitkiWilson Paul R Uniprocessor Garbage Collection Techniques Proceedings of the International Workshop on Memory Management London UK Springer Verlag s 1 42 ISBN 3 540 55940 X Section 2 1