Бағдарламалық ресурстарды есепке алу әдісі

Кіріспе

Бағдарламалық ресурстарды қадағалау техникасы

Компьютерлік ғылымда сілтемелерді санау – ресурсқа, мысалы, объектіге, жад блогына, дискідегі орынға және басқаларына жасалған сілтемелердің, көрсеткіштердің немесе тұтқалардың санын сақтаудың бағдарламалау техникасы. Қоқыс жинау алгоритмдерінде сілтемелер саны қажет болмай қалған объектілерді босату үшін қолданылуы мүмкін.

Графикті түсіндіру

Қоқыс жинау схемаларымен жұмыс істегенде, анықтамалық графты қарастыру көбінесе пайдалы, ол бағытталған граф, онда түйіндер объектілер болып табылады және егер А объектісінде В объектісіне сілтеме болса, А-дан В-ға қабырға бар. Сондай-ақ, жергілікті айнымалыларды және орындалу жүйесі ұстап тұрған сілтемелерді көрсететін арнайы түйін немесе түйіндер бар, және ешқандай қабырға осы түйіндерге бармайды, бірақ олардан басқа түйіндерге қабырғалар баруы мүмкін. Бұл контексте, объектінің қарапайым сілтеме санағы – оның түйінінің кіріс дәрежесі болып табылады. Түйінді жою – объектіні жинаумен бірдей. Бұл тек түйінде кіріс қабырғалары болмаған жағдайда ғана жасалуы мүмкін, сондықтан ол басқа түйіндердің шығу дәрежесіне әсер етпейді, бірақ басқа түйіндердің кіріс дәрежесіне әсер етуі мүмкін, егер олардың кіріс дәрежесі де 0-ге төмендесе, олардың сәйкес объектілері де жиналады. Арнайы түйін бар қосылған компонент жинауға болмайтын объектілерді қамтиды, ал графтың басқа қосылған компоненттерінде тек қоқыс болады. Егер сілтеме санау арқылы қоқыс жинау алгоритмі іске асырылса, онда осы қоқыс компоненттерінің әрқайсысында кем дегенде бір цикл болуы керек; әйтпесе, олардың сілтеме санағы (яғни кіріс қабырғаларының саны) нөлге жеткенде жиналып кеткен болар еді.

Жаңартулардың тиімсіздігімен күресу

Анықтамалық санауды әрбір сілтеме жасалғанда немесе жойылғанда көбейту және азайту өнімділіктің айтарлықтай төмендеуіне әкелуі мүмкін. Бұл операциялар уақытты қана емес, кэштің жұмысын нашарлатып, құбыржол тоқтап қалуына себеп болуы мүмкін. Тіпті тізімнің ұзындығын есептеу сияқты тек оқу операциялары да анықтамалық санаудың қарапайым әдісімен анықтамаларды жаңарту үшін көптеген оқу және жазу операцияларын қажет етеді. Бір қарапайым тәсіл – компилятордың бірнеше жақын анықтамалық жаңартуларды біріктіруі. Бұл әсіресе жылдам жасалып, жылдам жойылатын сілтемелер үшін тиімді. Дегенмен, ертерек жоюдан сақтану үшін біріктірілген жаңартуды дұрыс орналастыруға көңіл бөлу керек. Deutsch Bobrow әдісінің анықтамалық санау тәсілі көбінесе анықтамалық санау жаңартулары жергілікті айнымалыларда сақталатын сілтемелерден туындайтынын ескереді. Ол осы сілтемелерді ескермейді, тек дерек құрылымдарындағы сілтемелерді ғана есептейді, бірақ анықтама саны нөлге тең объектіні жою алдында жүйе стек пен тіркеуіштерді сканерлеу арқылы оған басқа сілтемелердің жоқ екеніне көз жеткізуі керек. Генри Бейкер ұсынған тағы бір тәсіл – кейінге қалдырылған арттыру, онда жергілікті айнымалыларда сақталатын сілтемелер сәйкес анықтама санын дереу арттырмайды, ал қажет болғанша кейінге қалдырады. Егер мұндай сілтеме жылдам жойылса, санауды жаңартудың қажеті болмайды. Бұл қысқа өмір сүретін сілтемелермен байланысты көптеген жаңартуларды болдырмайды (мысалы, жоғарыдағы тізім ұзындығын есептеу мысалы). Алайда, егер мұндай сілтеме дерек құрылымына көшірілсе, кейінге қалдырылған арттыру сол уақытта орындалуы тиіс. Нысанның саны нөлге жетер алдында кейінге қалдырылған арттыруды орындау да маңызды, ертерек жоюдан сақтану үшін. Леванони мен Петранк санауды жаңартуға кететін шығынды күрт азайтты. Олар көптеген артық анықтамалық санау жаңартуларын біріктіретін жаңартуды біріктіру әдісін енгізді. Орындалудың белгілі бір кезеңінде бірнеше рет жаңартылатын меңзерді қарастырайық. Ол алдымен O1 нысанына, содан кейін O2 нысанына және т.б. аралықтың соңында белгілі бір нысанға сілтеме жасайды. Анықтамалық санау алгоритмі әдетте rc(O1), rc(O2)++, rc(O2), rc(O3)++, rc(O3), ..., rc(On)++ орындайды. Бірақ олардың көпшілігі артық. Аралықтың соңында анықтама санын дұрыс есептеу үшін rc(O1) және rc(On)++ орындау жеткілікті. Қалған жаңартулар артық. 2001 жылы Леванони мен Петранк мұндай жаңартуды біріктіруді анықтамалық санау жинақтағышында қалай пайдалануға болатынын көрсетті. Жаңа нысандарды тиісті түрде өңдеумен жаңартуды біріктіруді пайдаланғанда, Java-ның әдеттегі өлшемдері үшін санау жаңартуларының 99%-дан астамы жойылады. Қызығы, жаңартуды біріктіру бірнеше жіптерде меңзерді жаңарту кезінде атомдық операцияларды қолдану қажеттілігін де жояды, бұл бірнеше жіптерде анықтамалық санау мәселелерін шешеді. Сондықтан жаңартуды біріктіру қарапайым анықтамалық санаудың үшінші мәселесін шешеді (яғни, бірнеше жіптердегі жоғары шығындар). Леванони мен Петранк жақсы синхронизацияны қолдана отырып, көп жіпті қолданбалармен бір мезгілде жұмыс істей алатын жетілдірілген алгоритм ұсынды. 2003 жылы Блэкберн мен Маккинлидің қосымша анықтамалық санау әдісі кейінге қалдырылған анықтамалық санауды көшірмелік балабақшамен біріктіреді, көрсеткіштердің көпшілігі жас нысандарда болатынын байқайды. Бұл алгоритм ең жылдам ұрпақтық көшірме жинақтағыштарымен салыстырмалы өнімділікті қамтамасыз етеді, анықтамалық санаудың аз үзіліс уақытымен шектеледі.

Incrementing and decrementing reference counts every time a reference is created or destroyed can significantly impede performance. Not only do the operations take time, but they damage cache performance and can lead to pipeline bubbles. Even read only operations like calculating the length of a list require a large number of reads and writes for reference updates with naive reference counting. One simple technique is for the compiler to combine a number of nearby reference updates into one. This is especially effective for references which are created and quickly destroyed. Care must be taken, however, to put the combined update at the right position so that a premature free can be avoided. The Deutsch Bobrow method of reference counting capitalizes on the fact that most reference count updates are in fact generated by references stored in local variables. It ignores these references, only counting references in data structures, but before an object with reference count zero can be deleted, the system must verify with a scan of the stack and registers that no other reference to it still exists. Another technique devised by Henry Baker involves deferred increments, in which references which are stored in local variables do not immediately increment the corresponding reference count, but instead defer this until it is necessary. If such a reference is destroyed quickly, then there is no need to update the counter. This eliminates a large number of updates associated with short lived references (such as the above list length counting example). However, if such a reference is copied into a data structure, then the deferred increment must be performed at that time. It is also critical to perform the deferred increment before the object's count drops to zero, to avoid a premature free. A dramatic decrease in the overhead on counter updates was obtained by Levanoni and Petrank. They introduce the update coalescing method which coalesces many of the redundant reference count updates. Consider a pointer that in a given interval of the execution is updated several times. It first points to an object O1, then to an object O2, and so forth until at the end of the interval it points to some object On. A reference counting algorithm would typically execute rc(O1) , rc(O2)++, rc(O2) , rc(O3)++, rc(O3) , , rc(On)++. But most of these updates are redundant. In order to have the reference count properly evaluated at the end of the interval it is enough to perform rc(O1) and rc(On)++. The rest of the updates are redundant. Levanoni and Petrank showed in 2001 how to use such update coalescing in a reference counting collector. When using update coalescing with an appropriate treatment of new objects, more than 99% of the counter updates are eliminated for typical Java benchmarks. Interestingly, update coalescing also eliminates the need to employ atomic operations during pointer updates in a concurrent setting, this solving reference counting issues in a concurrent setting. Therefore, update coalescing solves the third problem of naive reference counting (i. e., a costly overhead in a concurrent setting). Levanoni and Petrank presented an enhanced algorithm that may run concurrently with multithreaded applications employing only fine synchronization. Blackburn and McKinley's ulterior reference counting method in 2003 combines deferred reference counting with a copying nursery, observing that the majority of pointer mutations occur in young objects. This algorithm achieves throughput comparable with the fastest generational copying collectors with the low bounded pause times of reference counting.

Анықтамалық циклдермен жұмыс істеу

Мүмкін, эталондық циклдарды басқарудың ең айқын жолы – жүйені оларды жасаудан аулақ болу үшін жобалау. Жүйе сілтеме циклдарын тікелей тыйым салуы мүмкін; қатты сілтемелері бар файлдық жүйелер көбінесе осылай жасайды. «Жеңіл» (саналмайтын) сілтемелерді тиімді пайдалану да циклдарды сақтаудан аулақ болуға көмектеседі; мысалы, Cocoa фреймворкі ата-ана мен бала арасындағы қатынас үшін «күшті» сілтемелерді, ал баладан ата-анаға қатынас үшін «жеңіл» сілтемелерді пайдалануды ұсынады. Жүйелер өздері құратын циклдарды қандай да бір жолмен көтеру немесе түзету үшін де жобалануы мүмкін. Дамытушылар деректер құрылымы қажет болмай қалғанда сілтемелерді нақты «бұзу» үшін код жасай алады, бірақ бұл деректер құрылымының өмір сүру мерзімін қолмен қадағалауды қажет етеді. Бұл техниканы «иесі» объектісін жасау арқылы автоматтандыруға болады, ол жойылған кезде оны бұзады; мысалы, Graph объектісінің деструкторы GraphNodes жиектерін жойып, графтың сілтеме циклдарын бұзуы мүмкін. Циклдар тіпті қысқа ғұмырлы және аздаған циклдық қоқысқа ие жүйелерде де ескерілмеуі мүмкін, әсіресе жүйе циклдық деректер құрылымдарынан мүмкіндігінше аулақ болу әдістемесін қолдана отырып жасалған жағдайда, көбінесе тиімділіктің есебінен. Компьютер ғалымдары деректер құрылымын өзгертуді қажет етпей, сілтеме циклдарын автоматты түрде анықтау және жинау тәсілдерін тапты. Бір қарапайым шешім – циклдарды қайтару үшін мерзімді іздеу қоқыс жинаушын пайдалану; циклдар әдетте қайтарылған кеңістіктің салыстырмалы түрде аз бөлігін құрайтындықтан, коллекторды қарапайым іздеу қоқыс жинаушыдан гөрі әлдеқайда сирек іске қосуға болады. Bacon сілтеме санаумен циклдарды жинау алгоритмін сипаттаған, ол іздеу коллекторларымен ұқсас, соның ішінде бірдей теориялық уақыт шектері бар. Бұл циклді тек сілтеме санауы нөлден жоғары мәнге дейін азайтылған кезде ғана оқшаулауға болатынына негізделген. Бұл оқиғаның барлық нысандары тамырлар тізіміне қосылады, содан кейін бағдарлама тамырлардан қол жетімді нысандар арасында циклдарды іздейді. Сілтемелердің барлық санауларын цикл бойынша азайту оларды барлығын нөлге дейін жеткізеді, осы кезде циклді жинауға болатынын біледі. Paz және басқалар жасаған осы алгоритмнің жетілдірілген нұсқасы басқа операциялармен бір мезгілде жұмыс істей алады және Levanoni және Petrank-тың жаңартуды біріктіру әдісін пайдалану арқылы тиімділігін арттырады, сондай-ақ Watson & Watson 1987 жылғы еңбектерінде көрсетілгендей.

Perhaps the most obvious way to handle reference cycles is to design the system to avoid creating them. A system may explicitly forbid reference cycles; file systems with hard links often do this. Judicious use of "weak" (non counted) references may also help avoid retain cycles; the Cocoa framework, for instance, recommends using "strong" references for parent to child relationships and "weak" references for child to parent relationships. Systems may also be designed to tolerate or correct the cycles they create in some way. Developers may design code to explicitly "tear down" the references in a data structure when it is no longer needed, though this has the cost of requiring them to manually track that data structure's lifetime. This technique can be automated by creating an "owner" object that does the tearing down when it is destroyed; for instance, a Graph object's destructor could delete the edges of its GraphNodes, breaking the reference cycles in the graph. Cycles may even be ignored in systems with short lives and a small amount of cyclic garbage, particularly when the system was developed using a methodology of avoiding cyclic data structures wherever possible, typically at the expense of efficiency. Computer scientists have also discovered ways to detect and collect reference cycles automatically, without requiring changes in the data structure design. One simple solution is to periodically use a tracing garbage collector to reclaim cycles; since cycles typically constitute a relatively small amount of reclaimed space, the collector can be run much less often than with an ordinary tracing garbage collector. Bacon describes a cycle collection algorithm for reference counting with similarities to tracing collectors, including the same theoretical time bounds. It is based on the observation that a cycle can only be isolated when a reference count is decremented to a nonzero value. All objects which this occurs on are put on a roots list, and then periodically the program searches through the objects reachable from the roots for cycles. It knows it has found a cycle that can be collected when decrementing all the reference counts on a cycle of references brings them all down to zero. An enhanced version of this algorithm by Paz et al. is able to run concurrently with other operations and improve its efficiency by using the update coalescing method of Levanoni and Petrank. and Watson & Watson in 1987.

Тікелей емес сілтемелерді есептеу

Жанама сілтемелерді санағанда сілтеменің бастауын қадағалау қажет. Бұл объектіге екі сілтеме сақталады дегенді білдіреді: тікелей сілтеме, ол шақырулар үшін қолданылады; және жанама сілтеме, ол Дикстра-Шолтен алгоритмі сияқты тарату ағашының бөлігін құрайды, бұл қоқыс жинаушыға қолданылмаған объектілерді анықтауға мүмкіндік береді. Бұл тәсіл объектінің мерзімінен бұрын жойылмауын қамтамасыз етеді.

Қоқыс жинау

Жинақтау алгоритмі ретінде сілтемелерді санау әрбір объект үшін басқа объекттердегі оған жасалған сілтемелердің санын қадағалайды. Егер объектінің сілтеме саны нөлге жетсе, онда объект қолжетімсіз болып саналады және жойылуы мүмкін. Объект жойылғанда, осы объектке сілтеме жасаған басқа объекттердің сілтеме саны да кемиді. Осы себепті, бір сілтемені жою көптеген объектілердің босатылуына әкелуі мүмкін. Көп қолданылатын өзгерту сілтеме санауын кезеңдік етуге мүмкіндік береді: сілтеме саны нөлге жеткенде объектті бірден жоюдың орнына, ол сілтемесіз объектілер тізіміне қосылады және белгілі бір уақыт аралығында (немесе қажет болған жағдайда) осы тізімдегі бір немесе бірнеше элемент жойылады. Қарапайым сілтеме санауды жиі жаңарту қажет. Сілтеме жойылғанда немесе жаңасымен ауыстырылғанда, ол сілтеме жасайтын объектінің сілтеме саны азаяды, ал сілтеме жасалғанда немесе көшірілгенде, ол сілтеме жасайтын объектінің сілтеме саны артады. Сілтеме санау файлдық жүйелерде және таратылған жүйелерде де қолданылады, онда толық емес, кезеңдік іздеу арқылы қоқысты жинау объектілер графигінің үлкендігі мен баяу қол жеткізілу жылдамдығы салдарынан тым көп уақытты қажет етеді.

Компоненттік нысанның моделі

Microsoft Component Object Model (COM) және WinRT жүйелері сілтемелік санауды кеңінен пайдаланады. Шындығында, барлық COM объектілері міндетті түрде ұсынатын үш әдістің екеуі (IUnknown интерфейсінде) сілтеме санауын арттырады немесе кемітеді. Windows Shell-дің көп бөлігі және көптеген Windows қосымшалары (MS Internet Explorer, MS Office және көптеген үшінші тарап өнімдері сияқты) COM-ға негізделген, бұл сілтемелік санаудың кең ауқымды жүйелерде тиімді екенін көрсетеді. COM-те сілтемелік санауды қолданудың басты себептерінің бірі – әртүрлі бағдарламалау тілдері мен орындалу орталары арасындағы өзара әрекеттесуді қамтамасыз ету. Клиентке объектінің өмірлік циклын басқару үшін объект әдістерін қалай шақыру керектігін білу жеткілікті; осылайша, клиент COM объектісінің іске асырылуы қолданатын жад бөлушіден толығымен абстракцияланады. Мысалы, COM объектісін пайдаланатын Visual Basic бағдарламасы, бұл объектінің C++ бөлігішімен немесе басқа Visual Basic компонентімен бөлінгенін (содан кейін босатылуы керек) білмейді.

C++ тілінде

C++ әдетте сілтемелерді санамайды, өйткені пайдаланушы нақты сұрамаған жағдайда қосымша шығындар тудыруы мүмкін функционалдылықты қосуға қарсы тұрады. Ортақ, бірақ меншігі жоқ объектілерге сілтеме, шикі көрсеткіш немесе итератор (көрсеткіштердің тұжырымдамалық жалпыламасы) арқылы қол жеткізуге болады. Бірақ, соған қарай, C++ пайдаланушыларға мұндай функционалдылықты таңдауға мүмкіндік беретін құралдарды ұсынады: C++11 классы арқылы сілтемелік санаулы смарт көрсеткіштерді ұсынады, бұл динамикалық түрде бөлінген объектілердің автоматты түрде ортақ жадты басқаруын қамтамасыз етеді. Бағдарламашылар циклдық тәуелділікті жою үшін әлсіз көрсеткіштермен ( ) бірге оны пайдалана алады. Динамикалық түрде бөлінген, бірақ ортақ пайдалануға арналмаған объектілердің өмір сүру мерзімін автоматты түрде басқаруға болады. Сонымен қатар, C++11-дің жылжыту семантикасы функция объектіні қайтарған кезде әдетте қолданылатын терең көшіруді алып тастау арқылы сілтемелерді өзгерту қажеттігін одан әрі азайтады, бұл аталған объектінің көрсеткішінің қарапайым көшірмесін жасауға мүмкіндік береді.

Какао (C-мақсат)

Apple компаниясының Cocoa және Cocoa Touch фреймворктері (және Core Foundation сияқты байланысты фреймворктер) COM сияқты қолмен сілтеме санауды пайдаланады. Бұрын бағдарламашылар объектілерге сақтау және босату туралы хабарламаларды қолмен жіберу арқылы осыны істеген, бірақ iOS 5 және Mac OS X 10.7 нұсқаларында қажет болған жағдайда осы хабарламаларды автоматты түрде қосатын Clang компиляторының мүмкіндігі – Автоматты Сілтеме Санауы енгізілді. Mac OS X 10.5 нұсқасында сілтеме санаудың орнына іздеу арқылы қоқыс жинағыш ұсынылған, бірақ ол OS X 10.8 нұсқасында қолданыстан шығарылды және macOS Sierra-да Objective C орындалу ортасы кітапханасынан алынып тасталды. iOS ешқашан іздеу арқылы қоқыс жинағышты қолдаған емес.

Нысан

GOбъектіге бағытталған бағдарламалау жүйесі өз базалық типтерінде, оның ішінде әлсіз сілтемелерде сілтемелерді санауды іске асырады. Сілтемелерді арттыру және азайту операциялары жіп қауіпсіздігін қамтамасыз ету үшін атомдық операцияларды пайдаланады. Жоғары деңгейлі тілдерден GObject-ке байланыстарды жасаудың маңызды бөлігі – GObject сілтеме санауын тілдің өзінің жад басқару жүйесімен үйлестіруде жатыр. Vala бағдарламалау тілі GObject сілтеме санауын негізгі қоқыс жинау жүйесі ретінде қолданады, сондай-ақ көп көшіруді қажет ететін жолдармен жұмыс істеумен бірге.

Perl (жазу)

Perl сонымен қатар сілтемелерді санауды қолданады, айналма сілтемелерді ерекше өңдемейді, бірақ (Cocoa және C++ жоғарыда айтылғандай), Perl әлсіз сілтемелерді қолдайды, бұл бағдарламашыларға циклдар жасаудан сақтануға мүмкіндік береді.

PHP-де

PHP өзінің ішкі айнымалыларын басқару үшін сілтемелік санау механизмін пайдаланады. PHP 5.3 нұсқасынан бастап ол Бейконның жоғарыда аталған мақаласында сипатталған алгоритмді қолданады. PHP пайдаланушы деңгейіндегі функциялар арқылы циклдық жинауды қосуға және өшіруге мүмкіндік береді. Сондай-ақ, ол тазалау механизмін қолмен күштеп іске қосуға да рұқсат етеді.

Python-тың атауы

Python сонымен қатар сілтемелік санауды қолданады және циклдарды анықтау мүмкіндігін де ұсынады (және сілтемелік циклдарды қайта пайдалана алады).

Қасқыр

Қоян эталондық есептеуді циклді анықтаумен бірге пайдаланады. Бұл кішкентай тіл бейне ойын индустриясының шеңберінде көп танымал емес, бірақ эталондық есептеудің қаншалықты практикалық және тиімді болатынының (әсіресе нақты уақыт ортасында) нақты мысалы болып табылады.

Тез

Swift сынып инстанцияларының жадын қадағалау және басқару үшін сілтеме санауды пайдаланады және әлсіз сілтемелерді жасау үшін "әлсіз" түйін сөзін ұсынады. Құнды түрлердің инстанциялары сілтеме санауды қолданбастады.

ТТК

Tcl 8 мәндерді жадыда басқару үшін сілтемелік санауды қолданады (Tcl Obj құрылымдары). Tcl-дің мәндері өзгермейтін болғандықтан, сілтемелік циклдар құрылуы мүмкін емес және циклдарды анықтау схемасы қажет емес. Мәнді өзгертілген көшірмемен алмастыруға тиіс операциялар, әдетте, түпнұсқаны өзгертуге оңтайландырылады, егер оның сілтеме саны ортақ қолданыста еместігін көрсетсе. Сілтемелер дерек құрылымы деңгейінде есептеледі, сондықтан жоғарыда талқыланған жиі жаңартулардың проблемалары туындамайды.

Қожа

Xojo сонымен қатар циклдық сілтемелерді ерекше өңдеусіз сілтемелерді санауды пайдаланады, бірақ (Какао және C++-тағыдай) Xojo әлсіз сілтемелерді қолдайды, бұл бағдарламашыларға циклдардың пайда болуын болдырмауға көмектеседі.

Файл жүйелері

Көптеген файлдық жүйелер кез келген блокқа немесе файлға сілтемелер санын есептейді, мысалы, Unix жүйелеріндегі inode сілтемелерінің саны, олар көбінесе қатты сілтемелер деп аталады. Сан нөлге жеткенде, файлды қауіпсіз түрде босатуға болады. Сілтемелерді каталогтардан жасау мүмкін болғанымен, кейбір Unix жүйелері тек жұмыс істеп тұрған процестерден ғана сілтеме жасауға рұқсат береді, сондай-ақ файлдық жүйе иерархиясының сыртында файлдар болуы мүмкін.