Қоқыс жинауды қадағалау - Tracing garbage collection

Бұл мақала үшін қосымша дәйексөздер қажет тексеру. Өтінемін көмектесіңіз осы мақаланы жақсарту арқылы дәйексөздерді сенімді ақпарат көздеріне қосу. Ресурссыз материалға шағым жасалуы және алынып тасталуы мүмкін. Дереккөздерді табу: «Қоқыс жинауды қадағалау»  – жаңалықтар  · газеттер  · кітаптар  · ғалым  · JSTOR (Шілде 2016) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Жылы компьютерлік бағдарламалау, қоқысты жинау формасы болып табылады автоматты жадыны басқару ол қандай объектілерді бөлу керек екенін анықтаудан тұрады («қоқыс жиналады») қол жетімді белгілі бір «тамыр» объектілерінің сілтемелер тізбегі бойынша, ал қалғандарын «қоқыс» деп санау және оларды жинау. Қоқыс жинауды қадағалау - бұл ең көп таралған түрі қоқыс шығару - сондықтан «қоқыстарды жинау» басқа әдістерден гөрі қоқысты жинауды жиі кездестіреді. анықтамалық санау - және іске асыруда қолданылатын алгоритмдердің саны өте көп.

Нысанға қол жетімділік

Бейресми нысанда, егер оған бағдарламаның кем дегенде бір айнымалысы сілтеме жасаса, тікелей немесе басқа қол жетімді объектілердің сілтемелері арқылы қол жетімді болады. Дәлірек айтқанда, нысандарға тек екі жолмен қол жеткізуге болады:

1. Тамырлардың белгілі жиынтығы: қол жетімді деп болжанған нысандар. Әдетте бұларға кез келген жерден сілтеме жасалған барлық объектілер кіреді шақыру стегі (яғни барлығы жергілікті айнымалылар және параметрлері және кез келген жаһандық айнымалылар.
2. Қол жетімді объектіден сілтеме жасалған кез келген нәрсеге өзі қол жетімді; формальды түрде қол жетімділік а өтпелі жабылу.

«Қоқыстың» қол жетімділік анықтамасы оңтайлы емес, өйткені бағдарлама объектіні соңғы рет қолданған кезде, ол объект қоршаған ортадан тыс қалуы мүмкін. Айырмашылық кейде арасында алынады синтаксистік қоқыс, бағдарлама мүмкін емес объектілерге жете алмайды және семантикалық қоқыс, бағдарлама объектілерді енді ешқашан қолданбайды. Мысалға:

Нысан х = жаңа Фу();Нысан ж = жаңа Бар();х = жаңа Quux();/ * Осы кезде біз Foo объектісі екенін білеміз  * бастапқыда x-ге тағайындалған ешқашан болмайды * қол жеткізілді: бұл синтаксистік қоқыс. */егер (х.бірдеңе()) {    х.бірдеңе жасау(ж);}Жүйе.Шығу(0);/ * Жоғарыдағы блокта y * мүмкін * семантикалық қоқыс болуы мүмкін; * бірақ x.check_something () қайтарылмайынша білмейміз * кейбір мән - егер ол мүлдем қайтарылса. */

Семантикалық қоқысты дәл анықтау проблемасы оңай көрінуі мүмкін ішінара шешімді: объектіні бөлетін бағдарлама X, ерікті енгізу бағдарламасын іске қосады P, және қолданады X егер және егер болса P әрлеу үшін қоқыс жинайтын коллекторды шешу қажет болады мәселені тоқтату. Қоқысты семантикалық анықтауға арналған консервативті эвристикалық әдістер белсенді зерттеу бағыты болып қалса да, практикалық қоқыстарды жинайтындардың барлығы синтаксистік қоқыстарға бағытталған.^{[дәйексөз қажет ]}

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

Күшті және әлсіз сілтемелер

Қоқыс жинаушы түбір жиынтығынан тікелей немесе жанама түрде сілтеме жасалмаған нысандарды ғана қайтарып ала алады. Алайда, кейбір бағдарламалар қажет әлсіз сілтемелер, ол объект болғанға дейін жарамды болуы керек, бірақ оның қызмет ету мерзімін ұзартпауы керек. Әлсіз сілтемелер туралы пікірталастарда кейде қарапайым сілтемелер деп аталады мықты сілтемелер. Нысан қоқысты жинауға құқылы, егер оған ешқандай күшті (яғни қарапайым) сілтемелер болмаса, дегенмен әлсіз сілтемелер болуы мүмкін.

Әлсіз сілтеме тек қоқыс жинаушыға мән бермейтін объектінің кез-келген нұсқаушысы ғана емес. Термин әдетте дұрыс басқарылатын арнайы сілтеме объектілерінің санаты үшін сақталады, оларды объект жоғалғаннан кейін де қолдануға қауіпсіз кідіріс қауіпсіз мәнге дейін (әдетте нөл). Қоқыс жинаушыға белгісіз қауіпті сілтеме объект бұрын тұрған мекен-жайға сілтеме жасай отырып, жай ғана ілулі қалады. Бұл әлсіз сілтеме емес.

Кейбір іске асыруларда әлсіз сілтемелер ішкі санаттарға бөлінеді. Мысалы, Java виртуалды машинасы әлсіз сілтемелердің үш формасын ұсынады, атап айтқанда жұмсақ сілтемелер,^[1] елес сілтемелер,^[2] және тұрақты әлсіз сілтемелер.^[3] Жұмсақ сілтеме жасалған объект тек қоқыс жинаушы бағдарламаның жады аз деген шешім қабылдаған жағдайда ғана қалпына келтіруге болады. Жұмсақ сілтеме немесе кәдімгі әлсіз сілтемеден айырмашылығы, елес сілтеме өзі сілтеме жасаған объектіге қол жеткізе алмайды. Керісінше, елес сілтеме дегеніміз - қоқыс жинаушыға сілтеме жасалған нысан болған кезде бағдарламаны хабарлауға мүмкіндік беретін механизм. қол жетімді. Нысанға қол жетімді, егер ол әлі де жадында болса және оған елес сілтеме сілтеме жасаса, бірақ финалдаушы орындалды. Сол сияқты, Microsoft.NET әлсіз сілтемелердің екі ішкі санатын ұсынады,^[4] атап айтқанда әлсіз сілтемелер (қайта тірілу тректері) және қысқа әлсіз сілтемелер.

Әлсіз коллекциялар

Мәліметтер құрылымы әлсіз бақылау мүмкіндіктері бар ойлап табуға болады. Мысалы, әлсіз хэш кестелер пайдалы. Кәдімгі хэш-кесте сияқты, әлсіз хэш-кесте де жұп нысандар арасындағы байланысты сақтайды, мұнда әр жұп кілт және мән деп түсініледі. Алайда, хэш-кесте бұл объектілерге нақты сілтеме бермейді. Ерекше тәртіп кілт немесе мән немесе екеуі де қоқысқа айналған кезде орын алады: хэш кестесінің жазбасы өздігінен жойылады. Тек әлсіз кілттері бар (мән сілтемелері кәдімгі, күшті сілтемелер) немесе әлсіз мәндері (кілт сілтемелері күшті) хэш кестелері сияқты қосымша нақтылау бар.

Әлсіз хэш кестелер объектілер арасындағы ассоциацияларды сақтау үшін маңызды, өйткені ассоциациямен айналысатын объектілер қоқысқа айналуы мүмкін, егер бағдарламада ештеңе бұдан былай оларға сілтеме жасамаса (ассоциациялық хэш кестеден басқа).

Мұндай мақсат үшін әдеттегі хэш-кестені қолдану «есте сақтаудың логикалық ағып кетуіне» әкелуі мүмкін: бағдарлама қажет етпейтін және пайдаланбайтын қол жетімді деректерді жинақтау.

Негізгі алгоритм

Калькуляторларды деп атайды, өйткені олар жадының жұмыс жиынын анықтайды. Бұл қоқыс жинаушылар цикл бойынша жинайды. Бөлу туралы сұранысты қанағаттандыру үшін жад менеджері үшін бос жад жеткіліксіз болған кезде циклдар басталады. Бірақ көбінесе циклдар мутацияны тікелей сұрауы мүмкін немесе уақыт кестесінде жұмыс істейді. Бастапқы әдіс аңқауды қамтиды таңбалау онда бүкіл жад жиынтығы бірнеше рет қозғалады.

Таңқаларлықтай тазарту

А бойынша іс-әрекеттегі аңғалдық үйінді құрамында сегіз нысандар. Көрсеткілер білдіреді объектілік сілтемелер. Шеңберлер нысандардың өзін бейнелейді. # 1, # 2, # 3, # 4 және # 6 нысандарына түбірлік жиынтықтан қатты сілтеме жасалған. Екінші жағынан, # 5, # 7 және # 8 нысандарына түбір жиынтығынан тікелей немесе жанама түрде сілтеме жасалмайды; сондықтан олар қоқыс.

«Таңбалау және тазалау» аңғалдық әдісінде жадыдағы әрбір объект тек қоқысты жинау үшін сақталған жалауша (әдетте бір бит) болады. Бұл жалау әрқашан тазартылды, жинау циклын қоспағанда.

Бірінші кезең - бұл белгі сатысы ол бүкіл «түбірлер жиынтығын» кесіп өтеді және түбір көрсеткен әрбір нысанды «қолданыста» деп белгілейді. Осы объектілер көрсеткен барлық нысандар және тағы басқалар, сондай-ақ түбір жиынтығы арқылы қол жеткізуге болатын барлық объектілер белгіленетін етіп белгіленеді.

Екінші кезеңде сыпыру кезеңі, барлық жады басынан аяғына дейін сканерленеді, барлық бос немесе қолданылған блоктарды зерттейді; «қолданыстағы» деп белгіленбегендерге тамырлар жете алмайды және олардың жады босатылады. Пайдалану кезінде белгіленген нысандар үшін келесі циклға дайындалып, қолданыстағы жалауша тазартылады.

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

Үш түсті таңбалау

8 нысаны бар үйіндіде үш түсті белгілердің мысалы. Ақ, сұр және қара нысандар сәйкесінше ашық-сұр, сары және көк түстермен бейнеленген.

Осы проблемаларға байланысты қазіргі заманғы қоқыс жинауыштар кейбір нұсқаларын қолданады үш түсті таңбалау абстракция, бірақ қарапайым коллекторлар (мысалы таңбалау коллектор) көбінесе бұл абстракцияны айқын көрсетпейді. Үш түсті таңбалау төменде сипатталғандай жұмыс істейді.

Үш жиын жасалған - ақ, қара және сұр:

• Ақ жиынтық немесе айыпталған жиынтық, бұл жадыны қайта өңдеуге үміткер объектілер жиынтығы.
• Қара жиын - бұл ақ жиынтықтағы объектілерге шығатын сілтемелері жоқ және тамырларынан қол жетімді болатындығын көрсетуге болатын объектілер жиынтығы. Қара жиынтықтағы нысандар жинауға үміткер емес.
• Сұр жиынтықта түбірлерден қол жеткізуге болатын, бірақ «ақ» нысандарға сілтеме жасау үшін сканерленетін барлық нысандар бар. Олар тамырлардан қол жетімді екендігі белгілі болғандықтан, олар қоқыс жинауға болмайды және сканерден өткеннен кейін қара жиынтықта қалады.

Көптеген алгоритмдерде бастапқыда қара жиын бос деп басталады, сұр жиынтық - бұл тамырларға тікелей сілтеме жасайтын объектілер жиынтығы, ал ақ жиынтыққа барлық басқа объектілер кіреді. Жадтағы барлық объектілер барлық уақытта үш жиынның біреуінде болады. Алгоритм келесідей жүреді:

1. Сұр жиынтықтан затты таңдап, қара жиынтыққа жылжытыңыз.
2. Сілтеме берілген әрбір ақ затты сұр жиынтыққа жылжытыңыз. Бұл бұл нысанды да, оған сілтеме жасаған кез-келген затты да қоқыс жинауға болмайтындығына кепілдік береді.
3. Соңғы жиынтығын сұр жиынтық бос болғанша қайталаңыз.

Сұр жиынтық бос болған кезде сканерлеу аяқталады; қара заттар түбірден қол жетімді, ал ақ заттар қоқыс жинамайды және жиналмайды.

Түбірлерден бірден қол жетпейтін барлық нысандар ақ жиынтыққа қосылатындықтан, объектілер ақтан сұрға және сұрдан қараға ауыса алатындықтан, алгоритм маңызды инвариантты сақтайды - ақ нысандарға қара нысандар сілтеме жасамайды. Бұл сұр жиынтық бос болғаннан кейін ақ нысандардың босатылуын қамтамасыз етеді. Бұл деп аталады үш түсті инвариант. Алгоритмдегі кейбір вариациялар инвариантты сақтамайды, бірақ барлық маңызды қасиеттерге ие түрлендірілген форманы қолданады.

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

Іске асыру стратегиялары

Қозғалмайтынға қарсы қозғалу

Қол жетпейтін жинақ анықталғаннан кейін қоқыс жинаушы жай шығаруы мүмкін қол жетпейтін нысандар және қалғандарының барлығын сол күйінде қалдырыңыз, әйтпесе ол қол жетімді объектілердің барлығын немесе барлығын жаңа жад аймағына көшіре алады, қажет болған жағдайда осы объектілерге барлық сілтемелерді жаңартады. Оларды тиісінше «қозғалмайтын» және «қозғалатын» (немесе, балама, «тығыздалмайтын» және «нығыздайтын») деп атайды.

Алдымен қозғалмайтын алгоритм қозғалмайтын алгоритммен салыстырғанда тиімсіз болып көрінуі мүмкін, өйткені әр циклде әлдеқайда көп жұмыс қажет болатын көрінеді. Қозғалатын алгоритм қоқыс жинау циклі кезінде де, бағдарламаны орындау кезінде де бірнеше тиімділіктерге әкеледі:

• Өлі заттар босатқан кеңістікті қалпына келтіру үшін қосымша жұмыс талап етілмейді; қол жетімді объектілер жылжытылған жадтың барлық аймағын бос кеңістік деп санауға болады. Керісінше, қозғалмайтын МК әр қол жетпейтін объектіге кіріп, оның жады бар екенін жазып отыруы керек.
• Сол сияқты, жаңа нысандарды тез бөлуге болады. Жадтың үлкен іргелес аймақтары әдетте қозғалмалы GC-ге қол жетімді болғандықтан, жаңа объектілерді жай «бос жад» көрсеткішін көбейту арқылы бөлуге болады. Қозғалмайтын стратегия біраз уақыттан кейін үлкен нәтижеге әкелуі мүмкін бөлшектелген үйінді, жаңа объектілерді бөлу үшін шағын бос жад блоктарының «еркін тізімдерін» қымбат кеңес алу қажет.
• Егер сәйкес өтпелі тәртіп қолданылса (мысалы, тізім үшін cdr-бірінші) минус ), объектілерді еске түсіретін объектілерге өте жақын жылжытуға болады, олардың сол жерде орналасу мүмкіндігі артады кэш сызығы немесе виртуалды жад бет. Бұл осы сілтемелер арқылы осы объектілерге қол жеткізуді едәуір жеделдетуі мүмкін.

Қозғалатын қоқыс жинауыштың бір кемшілігі мынада: ол қоқыс жиналатын орта арқылы басқарылатын сілтемелер арқылы қатынасуға мүмкіндік береді және оған жол бермейді көрсеткіш арифметикасы. Себебі қоқыс жинаушы сол заттарды жылжытса (олар айналады), объектілерге арналған кез-келген көрсеткіш жарамсыз болады ілулі көрсеткіштер ). Үшін өзара әрекеттесу жергілікті кодпен қоқыс жинаушы объектінің мазмұнын қоқыс жадынан тыс жерге көшіруі керек. Балама тәсіл түйреуіш қоқыс жинаушының оны жылжытуына жол бермейтін және жадыны жергілікті көрсеткіштермен тікелей бөлісуге мүмкіндік беретін жадыдағы объект (және көрсеткіш арифметикасына мүмкіндік беруі мүмкін).^[5]

«Белгілеу» және «тазалау» және «тазалау» емес, «көшіру»

Коллекторлар олардың қозғалатын немесе қозғалмайтындығымен ерекшеленіп қана қоймай, оларды жинау циклі кезінде ақ, ​​сұр және қара заттар жиынтығына қалай қарайтындығымен де бөлуге болады.

Ең қарапайым тәсіл - бұл жартылай кеңістіктік коллекторБұл 1969 ж. қозғалатын коллекторда жад бірдей көлемде «ғарыштан» және «ғарышқа» бөлінеді. Бастапқыда объектілер «кеңістікке» ол толғанға дейін және жинақтау циклі іске қосылғанша бөлінеді. Цикл басталған кезде «ғарышқа» «ғарыштан» айналады, керісінше. Түбір жиынтығынан қол жеткізуге болатын объектілер «кеңістіктен» «кеңістікке» көшіріледі. Бұл нысандар кезек-кезек сканерленеді және олар қол жеткізетін барлық объектілер «кеңістікке» көшірілгенше, олар «ғарышқа» көшіріледі. Бағдарлама орындалуын жалғастырғаннан кейін, жаңа объектілер қайтадан толғанға дейін және процесс қайталанғанша «кеңістікке» қайтадан бөлінеді.

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

A белгілеу және сыпыру қоқыс жинаушы әр затта ақ немесе қара болса, жазып алу үшін бір-екіден сақтайды. Сұр жиынтық бөлек тізім түрінде немесе басқа бит көмегімен сақталады. Анықтама ағашы жинау циклі кезінде жүріп өткендіктен («белгі» кезеңі), бұл биттерді коллектор басқарады. Жад аймақтарын соңғы «сыпыру» ақ заттарды босатады. Таңбалау және сыпыру стратегиясының артықшылығы бар, егер сотталған жиынтық анықталғаннан кейін, қозғалмалы немесе қозғалмайтын жинау стратегиясын ұстануға болады. Бұл стратегияны таңдау жадының қол жетімділігі ретінде жұмыс кезінде жасалуы мүмкін. Оның объектілерді аз мөлшерде «кебу» кемшілігі бар, өйткені тізімде / қосымша битте болғандықтан, әр объектінің жадының жасырын құны аз болады. Егер коллектор бөлуді қарастыратын болса, мұны біршама жеңілдетуге болады, өйткені ол бөліну деректер құрылымында пайдаланылмаған биттерді қолдануы мүмкін. Немесе бұл «жасырын жадты» а көмегімен жоюға болады Белгіленген көрсеткіш, процессор уақыты үшін жады құнын сату. Алайда, белгілеу және сыпыру бұл бірінші кезекте сыртқы бөлгіштермен оңай жұмыс істейтін жалғыз стратегия.

A белгілеңіз және сыпырмаңыз қоқыс жинаушы, таңбалау сияқты, әр затта ақ немесе қара болса, жазып алу үшін аздап сақтайды; сұр жиынтық бөлек тізім түрінде немесе басқа битті қолдана отырып сақталады. Мұнда екі негізгі айырмашылық бар. Біріншіден, қара мен ақ түстер белгілер мен сыпырғыш коллектордағыдан өзгеше мағынаны білдіреді. «Белгі қой және сыпырма» коллекторында барлық қол жетімді заттар әрқашан қара түсті болады. Нысанды бөлу кезінде ол қара деп белгіленеді және ол қол жетімсіз болып қалса да қара болып қалады. Ақ зат пайдаланылмаған жады болып табылады және оны бөлуге болады. Екіншіден, қара / ақ биттің интерпретациясы өзгеруі мүмкін. Бастапқыда қара / ақ бит (0 = ақ, 1 = қара) мағынасына ие болуы мүмкін. Егер бөлу операциясы қол жетімді (ақ) жадты таба алмаса, бұл барлық нысандар пайдаланылған деп белгіленеді (қара). Содан кейін қара / ақ биттің мағынасы төңкеріледі (мысалы, 0 = қара, 1 = ақ). Барлығы ақ түске айналады. Бұл инвариантты бұзады, қол жететін нысандар қара түсті, бірақ толық таңбалау кезеңі оларды қайтадан қара түспен белгілеу үшін бірден басталады. Мұны жасағаннан кейін, қол жетімді емес жадтың барлығы ақ болады. Ешқандай «сыпыру» кезеңі қажет емес.

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

The белгілеңіз және сыпырмаңыз сондықтан стратегияны оң және теріс жақтары арасындағы ымыраға келу ретінде қарастыруға болады белгілеу және сыпыру және тоқтату және көшіру стратегиялар.

Ұрпақты GC (уақытша GC)

Көптеген бағдарламаларда жақында жасалған объектілердің тез қол жетімсіз болып қалатындығы эмпирикалық түрде байқалды ( нәресте өлімі немесе буын гипотезасы). Ұрпақты ГК (эфемеральды ГК деп те аталады) объектілерді буынға бөледі және көптеген циклдарда тек ұрпақтар жиынтығының объектілерін бастапқы ақ (айыпталған) жиынтыққа орналастырады. Сонымен қатар, жұмыс уақыты жүйесі сілтемелердің жасалуы мен қайта жазылуын қадағалай отырып, сілтемелердің ұрпақтан-ұрпаққа өтуі туралы білімді сақтайды. Қоқыс жинаушы жұмыс істеген кезде, бұл білімді бастапқы ақ жиынтықтағы кейбір нысандарға бүкіл сілтеме ағашын айналып өтпестен қол жетімді еместігін дәлелдеу үшін қолдана алады. Егер ұрпақ гипотезасы болса, бұл қол жетімді емес объектілерді қалпына келтіру кезінде жинау циклдарының жылдамдығын арттырады.

Осы тұжырымдаманы іске асыру үшін көптеген ұрпақ қоқыс жинаушылар объектілердің әр түрлі жасына арналған бөлек жад аймақтарын пайдаланады. Аймақ толған кезде, аға буын (-дар) сілтемелерін тамыр ретінде пайдаланып, ондағы объектілерді іздейді. Бұл, әдетте, ұрпақтың көптеген объектілерінің жиналуына әкеледі (гипотеза бойынша), оны жаңа объектілерді бөлу үшін пайдалануға қалдырады. Коллекция көптеген объектілерді жинамаған кезде (гипотеза орындалмайды, мысалы, бағдарлама жаңа объектілердің үлкен жинағын есептегендіктен), ескі жадтан сілтеме жасалған тірі қалған объектілердің кейбірі немесе барлығы. аймақтар келесі жоғары аймаққа көтеріледі, содан кейін бүкіл аймақ жаңа нысандармен жазылуы мүмкін. Бұл әдіс қоқыстарды жылдам өсіруге мүмкіндік береді, өйткені бір уақытта бір ғана аймақтың қоқыстарын жинау қажет.

Унгар Классикалық ұрпақ тазалағышта екі ұрпақ бар. Ол «жаңа кеңістік» деп аталатын ең жас ұрпақты үлкен «эденге» бөледі, онда жаңа нысандар жасалады және екі кішігірім «тірі қалған кеңістіктер», өткен тірі қалған кеңістік және болашақ тірі қалған кеңістік. Жаңа кеңістіктегі нысандарға сілтеме жасай алатын аға буын нысандары «есте сақталған жиында» сақталады. Әрбір қоқыста жаңа кеңістіктегі заттар тамырлардан есте сақталған жиынтықта анықталып, болашақ тірі қалған кеңістікке көшіріледі. Егер болашақ тірі қалатын кеңістік толтырылса, сәйкес келмейтін нысандар ескі кеңістікке шығарылады, бұл процесс «тұрақтандыру» деп аталады. Тазартудың соңында кейбір объектілер болашақ тірі қалатын кеңістікте орналасады, ал эден және өткен тірі қалған кеңістік бос болады. Содан кейін болашақ тірі қалған кеңістік пен бұрынғы тірі қалған кеңістік алмасады және бағдарлама эденге объектілерді бөле отырып жалғасады. Унгардың бастапқы жүйесінде эден тірі қалған әрбір кеңістіктен 5 есе үлкен.

Қоқыстарды жинау - бұл а эвристикалық кейбір циклдарда қол жетімді емес объектілерді қалпына келтіруге болмайды. Сондықтан кейде барлық белгілерді орындау қажет болуы мүмкін, барлық қол жетімді жерлерді қайтарып алу үшін қоқыс жинауды сыпыру немесе көшіру. Шын мәнінде, қазіргі заманғы бағдарламалау тілдеріне арналған жұмыс уақыты жүйелері (мысалы Java және .NET Framework ) әдетте осы уақытқа дейін сипатталған әртүрлі стратегиялардың кейбір гибридтерін қолданыңыз; мысалы, жинау циклдарының көпшілігі бірнеше буынға ғана қаралуы мүмкін, ал кейде таңбалау жүргізіліп, сирек кездесуге қарсы толық көшірме жасалады. Коллекторлық агрессияның әр түрлі деңгейлерін сипаттау үшін кейде «кіші цикл» және «үлкен цикл» терминдері қолданылады.

Әлемді тоқтату және біртектеске қарсы

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

Мұның айқын кемшілігі бар: жинақтау циклі жұмыс істеп тұрған кезде бағдарлама ешқандай пайдалы жұмыс орындай алмайды (кейде «ұятты үзіліс» деп аталады)^[6]). Әлемде қоқысты жинау интерактивті емес бағдарламаларға жарамды. Оның артықшылығы - оны енгізу қарапайым және қоқысты жинауға қарағанда жылдамырақ.

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

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

Консервативті және ішкі көрсеткіштерге қарсы

Кейбір коллекционерлер объектідегі барлық сілтемелерді (сілтемелерді) дұрыс анықтай алады; бұлар аталады дәл (сонымен қатар дәл немесе дәл) коллекторлар, керісінше а консервативті немесе ішінара консервативті коллектор. Консервативті коллекционерлер жадтағы кез-келген биттік өрнек сілтеме ретінде түсіндірілуі мүмкін, егер ол бөлінген объектіні көрсететін болса, деп болжайды. Консервативті коллекционерлер жалған позитивтерді шығаруы мүмкін, олар пайдаланушының дұрыс идентификациясы болмағандықтан, пайдаланылмаған жады босатылмайды. Бұл бағдарлама іс жүзінде әрдайым проблема бола бермейді, егер бағдарлама сілтеме ретінде оңай анықталуы мүмкін көптеген деректерді өңдемесе. Жалған позитивтер әдетте онша проблемалы емес 64 бит қарағанда жүйелер 32 бит жүйелер, өйткені жарамды жад адрестерінің ауқымы 64 биттік мәндер диапазонының кішкене бөлігіне ұмтылады. Осылайша, ерікті 64-биттік үлгі жарамды көрсеткішті имитациялауы екіталай. Көрсеткіштер «жасырын» болса, жалған теріс болуы мүмкін, мысалы XOR байланыстырылған тізімі. Дәл коллектордың практикалық болуы, әдетте, қарастырылып отырған бағдарламалау тілінің типтік қауіпсіздік қасиеттеріне байланысты. Консервативті қоқыс жинаушы қажет болатын мысал - бұл C тілі, бұл типтелген (бос емес) көрсеткіштерді типтелмеген (жарамсыз) көрсеткіштерге түрлендіруге мүмкіндік береді, және керісінше.

Осыған байланысты мәселе ішкі көрсеткіштер, немесе нысан ішіндегі өрістерге сілтемелер. Егер тілдің семантикасы ішкі көрсеткіштерге мүмкіндік берсе, онда бір объектінің бөліктеріне сілтеме жасай алатын көптеген әр түрлі адресаттар болуы мүмкін, бұл объектінің қоқыс екендігін анықтауға қиындық туғызады. Бұған мысал ретінде C ++ бірнеше мұрагерлік сілтемелерді объектілердің әртүрлі адрестерге ие болуына әкелуі мүмкін тіл. Тығыз оңтайландырылған бағдарламада объектінің өзіне сәйкес көрсеткіш оның регистрінде қайта жазылуы мүмкін, сондықтан мұндай ішкі көрсеткіштерді сканерлеу қажет.

Өнімділік

Қоқыс жинауыштардың жұмысы - кешігу және өткізу қабілеттілігі - іске асыруға, жұмыс көлеміне және қоршаған ортаға айтарлықтай тәуелді. Жадпен шектелген ортада, атап айтқанда, ендірілген жүйелерде қарапайым іске қосу немесе қолдану басқа әдістермен салыстырғанда өте нашар өнімділікке әкелуі мүмкін, ал күрделі іске асыру және жеткілікті жады бар ортада қолдану керемет өнімділікке әкелуі мүмкін.^{[дәйексөз қажет ]}

Өткізу қабілеті тұрғысынан іздеу табиғаты бойынша белгілі бір уақытты талап етеді үстеме дегенмен, кейбір жағдайларда амортизацияланған шығындар өте төмен болуы мүмкін, кейбір жағдайларда стек бөлуден асып түсетін бір бөлу немесе жинау үшін бір нұсқаулықтан төмен.^[7] Жадыны қолмен басқару үшін жадты босатудың арқасында қосымша шығындар қажет, ал сілтемелерді санау сандық есептік көрсеткіштерді көбейту мен азайтудан және есептің асып кеткенін немесе нөлге дейін түскендігін тексеруден асып түседі.^{[дәйексөз қажет ]}

Күтуге келетін болсақ, қарапайым қоқыс жинаушылар қоқысты жинауға арналған бағдарламаны уақытша тоқтатады, бұл кездейсоқ уақытта болуы мүмкін және ерікті түрде ұзаққа созылуы мүмкін, сондықтан оларды пайдалануға жарамсыз етеді. нақты уақыттағы есептеу, атап айтқанда, ендірілген жүйелер, интерактивті қолдануға жарамсыздық немесе кез-келген жағдай, кешігу уақыты басым болатын кез-келген жағдай. Алайда, қоқыстарды көбейтетіндер нақты уақыт режимінде кепілдіктер бере алады, ал жиі жұмыс істемейтін және дербес компьютерлер сияқты бос жады жеткілікті жүйелерде қоқыс жинау бос уақытқа жоспарланып, интерактивті өнімділікке аз әсер етеді. Жадыны қолмен басқару (C ++ сияқты) және анықтамалық санау үлкен көлем құрылымын және оның барлық балаларын бөлу кезінде ерікті түрде ұзақ кідірістерге ұқсас мәселе тудырады, бірақ олар қоқыстың жиналуына байланысты емес, тек белгіленген уақытта болады.^{[дәйексөз қажет ]}

Үйінділерді қолмен бөлу

• жеткілікті көлемдегі ең жақсы / бірінші блокты іздеу
• ақысыз тізімді жүргізу

Қоқыстарды жинау

• қол жетімді объектілерді табу
• қозғалатын коллекторлар үшін қол жетімді объектілерді көшіру
• өсетін коллекторлар үшін кедергілерді оқу / жазу
• үздік / бірінші жарамды блокты іздеу және қозғалмайтын коллекторларға ақысыз тізімді қолдау

Екі жағдайды тікелей салыстыру қиын, өйткені олардың мінез-құлқы жағдайға байланысты. Мысалы, қоқыс жинау жүйесі үшін ең жақсы жағдайда, бөлу көрсеткішті көбейтеді, бірақ үйіндіде қолмен бөлу үшін ең жақсы жағдайда, бөлгіш белгілі мөлшердегі фрилисттерді сақтайды және бөлу тек көрсеткішке сүйенуді талап етеді. Алайда, бұл өлшемді бөлу әдетте сыртқы фрагментацияның үлкен дәрежесін тудырады, бұл кэштің жұмысына кері әсерін тигізуі мүмкін. Қоқысты жинау тіліндегі жадыны бөлу артында үйінділерді бөлу арқылы жүзеге асырылуы мүмкін (жай сілтегішті көбейтудің орнына), сондықтан жоғарыда аталған өнімділік артықшылықтары бұл жағдайда міндетті түрде қолданылмайды. Кейбір жағдайларда, ең бастысы ендірілген жүйелер, жад пулдарын алдын-ала бөлу арқылы және бөлу / бөлу үшін арнайы, жеңіл схеманы қолдану арқылы қоқысты жинауды және үйінділерді басқаруды болдырмауға болады.^[8]

Жазбаша кедергілердің үстіңгі жағы ан императивті -стиль бағдарламасы а-ға қарағанда қолданыстағы деректер құрылымына көрсеткіштерді жиі жазады функционалды -стиль бағдарламасы, ол деректерді бір рет қана құрастырады және оларды ешқашан өзгертпейді.

Қоқысты жинаудағы кейбір жетістіктерді өнімділік мәселелеріне реакциялар деп түсінуге болады. Алғашқы коллекторлар әлемдегі коллекционерлер болды, бірақ бұл тәсілдің өнімділігі интерактивті қосымшалардың назарын аударды. Артық жинау бұл бұзылудан аулақ болды, бірақ кедергілердің қажеттілігіне байланысты тиімділіктің төмендеуі есебінен. Өнімділікті арттыру үшін ұрпақ жинау әдістері әлемде де, қосымша коллекцияларда да қолданылады; сауда-саттық - бұл кейбір қоқыстар әдеттегіден ұзақ уақыт бойы анықталмайды.

Детерминизм

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

Қоқысты нақты уақытта жинау

Қоқыстарды жинау әдетте шешілмеген сипатта болса да, оны қатты қолдануға болады шынайы уақыт жүйелер. Нақты уақыттағы қоқыс жинаушы ең нашар жағдайда да ол есептеу ресурстарының белгілі бір санын мутациялық жіптерге арнайтындығына кепілдік беруі керек. Нақты уақыттағы қоқыс жинаушыға қойылған шектеулер әдетте жұмыс негізінде немесе уақытқа байланысты болады. Уақытқа негізделген шектеулер келесідей болады: әр уақыт терезесінде Т, мутациялық жіптер кем дегенде жұмыс істеуі керек Тм уақыт. Жұмысқа негізделген талдау үшін, ММУ (мутацияны минималды пайдалану)^[9] әдетте қоқыс жинау алгоритмі үшін нақты уақыттағы шектеу ретінде қолданылады.

Алғашқы іске асыруларының бірі нақты уақыт режимінде қоқыс жинау JVM негізіне алынды Метрономия алгоритмі,^[10] бөлігі ретінде қол жетімді болатын коммерциялық іске асыру IBM WebSphere нақты уақыты.^[11] Нақты уақыттағы қоқысты жинаудың тағы бір алгоритмі - Staccato IBM Келіңіздер J9 JVM Бұл сонымен бірге үлкен мультипроцессорлық архитектураның масштабталуын қамтамасыз етеді, сонымен бірге Метрономға және басқа алгоритмдерге қарағанда әртүрлі артықшылықтар береді, бұл керісінше мамандандырылған жабдықты қажет етеді.^[12]

Сондай-ақ қараңыз

• Өлі кодты жою

Әдебиеттер тізімі