Компьютер жадысын басқарудың іздеу әдісі

Кіріспе

Компьютерлік жадыны басқарудың түрі

Компьютерлік бағдарламалауда, іздеу арқылы қоқыс жинау – автоматты жадты басқарудың бір түрі болып табылады. Ол, белгілі бір "түпкілік" объектілерден сілтеме тізбегі арқылы қандай объектілерге қол жеткізілетінін анықтау арқылы, қай объектілерді босату керектігін ("қоқыс жинауды") анықтаудан тұрады, ал қалғандарын "қоқыс" деп санап жинайды. Іздеу – қоқыс жинаудың ең көп таралған түрі, сондықтан "қоқыс жинау" көбінесе басқа әдістерге қарағанда, мысалы, сілтеме санауына емес, осы іздеу әдісін білдіреді, және іске асыруда көптеген алгоритмдер қолданылады.

Мықты және әлсіз сілтемелер

Қоқыс жинағыш тек түбір жиынтығынан тікелей немесе жанама түрде сілтеме жасамайтын объектілерді ғана қайта пайдалана алады. Дегенмен, кейбір бағдарламаларға әлсіз сілтемелер қажет, олар объект бар болғанша қолданылуы керек, бірақ оның өмір сүру мерзімін ұзартпауы керек. Әлсіз сілтемелер туралы талқылауларда, қалыпты сілтемелер кейде күшті сілтемелер деп аталады. Объект, егер оған күшті (яғни қалыпты) сілтемелер болмаса, қоқыс жинауға жарамды болады, тіпті оған әлі де кейбір әлсіз сілтемелер болуы мүмкін. Әлсіз сілтеме – бұл қоқыс жинағыштың қамқорлық танытпайтын кез келген объектке жасалған көрсеткіш емес. Бұл термин әдетте дұрыс басқарылатын арнайы сілтеме объектілерінің санатына арналған, олар объект жойылғаннан кейін де қауіпсіз қолданылады, себебі олар қауіпсіз мәнге (әдетте null) өтеді. Қоқыс жинағышқа белгісіз қауіпсіз сілтеме, объект бұрын орналасқан мекенжайға сілтеме жасау арқылы әрең тірі қалады. Бұл әлсіз сілтеме емес. Кейбір жүзеге асыруларда әлсіз сілтемелер кіші топтарға бөлінеді. Мысалы, Java виртуалды машинасы әлсіз сілтемелердің үш түрін ұсынады: жұмсақ сілтемелер, фантомдық сілтемелер және қалыпты әлсіз сілтемелер. Жұмсақ сілтемеленген объект, егер қоқыс жинағыш бағдарламаның жады жетіспейді деп шешсе ғана қайта пайдалануға жарамды болады. Жұмсақ сілтемеден немесе қалыпты әлсіз сілтемеден айырмашылығы, фантомдық сілтеме сілтеме жасалған объектіге қол жеткізуді қамтамасыз етпейді. Оның орнына, фантомдық сілтеме – бұл қоқыс жинағыштың сілтеме жасалған объект фантомдық түрде қолжетімді болған кезде бағдарламаға хабарлауға мүмкіндік беретін механизм. Объект, егер ол әлі де жадыда болса және оған фантомдық сілтеме жасалса, бірақ оның finalizer-і орындалған болса, фантомдық түрде қолжетімді болып саналады. Microsoft .NET да әлсіз сілтемелердің екі кіші тобын ұсынады: ұзақ әлсіз сілтемелер (қайта тірілуді қадағалайды) және қысқа әлсіз сілтемелер.

Жеңіл жинақтар

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

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

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

Наивті таңбалау және сыпыру

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

Жылжымалы және жылжымайтын

Жетілмейтін жиын анықталғаннан кейін, қоқыс жинағыш жетуге болмайтын объектілерді босатып, қалған барлық нәрсені өзгеріссіз қалдыра алады, немесе жетуге болатын объектілердің бір бөлігін немесе барлығын жадтың жаңа аймағына көшіріп, қажет болған жағдайда осы объектілерге жасалған барлық сілтемелерді жаңарта алады. Бұлар тиісінше "қозғалмайтын" және "қозғалатын" (немесе, балама ретінде, "жинақтамайтын" және "жинақтайтын") қоқыс жинағыштар деп аталады. Алғашында, қозғалатын алгоритм қозғалмайтын алгоритмге қарағанда тиімсіздей көрінуі мүмкін, себебі әр циклда көбірек жұмыс істеуге тура келеді. Бірақ қозғалатын алгоритм қоқыс жинау циклының өзінде де, бағдарлама орындалу кезінде де бірнеше артықшылықтарға ие: өлі объектілер босаған орынды қайтару үшін қосымша жұмыс қажет емес; жетуге болатын объектілер көшірілген жадтың барлық аймағы бос деп есептелуі мүмкін. Керісінше, қозғалмайтын қоқыс жинағыш әрбір жетуге болмайтын объектіні тексеріп, ол орналасқан жадтың бос екенін тіркеуі керек. Сол сияқты, жаңа объектілерді өте жылдам құруға болады. Жадының үлкен үздіксіз аймақтары көбінесе қозғалатын қоқыс жинағыш арқылы бос болады, сондықтан жаңа объектілерді жай ғана "бос жад" көрсеткішін арттыру арқылы құруға болады. Қозғалмайтын стратегия уақыт өте келе жадтың күрт бөлінуіне әкелуі мүмкін, нәтижесінде жаңа объектілерді құру үшін жадтың кішкентай бос блоктарының "бос тізімдерін" қарастыру қажет болады. Егер тиісті бағытталған тәртіп қолданылса (мысалы, тізімдік құрастыру үшін cdr бірінші), объектілер жадыда олар сілтеме жасайтын объектілерге жақын жылжытылуы мүмкін, бұл олардың бірдей кэш жолында немесе виртуалды жад бетінде орналасу ықтималдығын арттырады. Бұл сілтемелер арқылы осы объектілерге қол жеткізу жылдамдығын едәуір арттыра алады. Қозғалатын қоқыс жинағыштың бір кемшілігі – ол тек қоқыс жинау ортасымен басқарылатын сілтемелер арқылы қол жеткізуге мүмкіндік береді және көрсеткіш арифметикасына жол бермейді. Себебі, егер қоқыс жинағыш осы объектілерді жылжытса, оларға жасалған көрсеткіштер жарамсыз болады (олар "ілулі" көрсеткіштерге айналады). Жергілікті кодпен өзара әрекеттесу үшін қоқыс жинағыш объектінің мазмұнын жадтың қоқыс жиналған аймағынан тыс жерге көшіруі керек. Баламалы тәсіл – объектіні жадта бекіту, қоқыс жинағышқа оны жылжытуға рұқсат бермеу және жадты тікелей жергілікті көрсеткіштермен бөлісуге мүмкіндік беру (сондай-ақ көрсеткіш арифметикасына рұқсат беру).

Once the unreachable set has been determined, the garbage collector may simply release the unreachable objects and leave everything else as it is, or it may copy some or all of the reachable objects into a new area of memory, updating all references to those objects as needed. These are called "non moving" and "moving" (or, alternatively, "non compacting" and "compacting") garbage collectors, respectively. At first, a moving algorithm may seem inefficient compared to a non moving one, since much more work would appear to be required on each cycle. But the moving algorithm leads to several performance advantages, both during the garbage collection cycle itself and during program execution:
No additional work is required to reclaim the space freed by dead objects; the entire region of memory from which reachable objects were moved can be considered free space. In contrast, a non moving GC must visit each unreachable object and record that the memory it occupied is available. Similarly, new objects can be allocated very quickly. Since large contiguous regions of memory are usually made available by a moving GC, new objects can be allocated by simply incrementing a 'free memory' pointer. A non moving strategy may, after some time, lead to a heavily fragmented heap, requiring expensive consultation of "free lists" of small available blocks of memory in order to allocate new objects. If an appropriate traversal order is used (such as cdr first for list conses), objects can be moved very close to the objects they refer to in memory, increasing the chance that they will be located in the same cache line or virtual memory page. This can significantly speed up access to these objects through these references. One disadvantage of a moving garbage collector is that it only allows access through references that are managed by the garbage collected environment, and does not allow pointer arithmetic. This is because any pointers to objects will be invalidated if the garbage collector moves those objects (they become dangling pointers). For interoperability with native code, the garbage collector must copy the object contents to a location outside of the garbage collected region of memory. An alternative approach is to pin the object in memory, preventing the garbage collector from moving it and allowing the memory to be directly shared with native pointers (and possibly allowing pointer arithmetic).

Көшіру мен белгілеп-тұрып алу және белгілеп-тұрып алмау

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

Not only do collectors differ in whether they are moving or non moving, they can also be categorized by how they treat the white, grey and black object sets during a collection cycle. The most straightforward approach is the semi space collector, which dates to 1969. In this moving collector, memory is partitioned into an equally sized "from space" and "to space". Initially, objects are allocated in "to space" until it becomes full and a collection cycle is triggered. At the start of the cycle, the "to space" becomes the "from space", and vice versa. The objects reachable from the root set are copied from the "from space" to the "to space". These objects are scanned in turn, and all objects that they point to are copied into "to space", until all reachable objects have been copied into "to space". Once the program continues execution, new objects are once again allocated in the "to space" until it is once again full and the process is repeated. This approach is very simple, but since only one semi space is used for allocating objects, the memory usage is twice as high compared to other algorithms. The technique is also known as stop and copy. Cheney's algorithm is an improvement on the semi space collector. A mark and sweep garbage collector keeps a bit or two with each object to record if it is white or black. The grey set is kept as a separate list or using another bit. As the reference tree is traversed during a collection cycle (the "mark" phase), these bits are manipulated by the collector. A final "sweep" of the memory areas then frees white objects. The mark and sweep strategy has the advantage that, once the condemned set is determined, either a moving or non moving collection strategy can be pursued. This choice of strategy can be made at runtime, as available memory permits. It has the disadvantage of "bloating" objects by a small amount, as in, every object has a small hidden memory cost because of the list/extra bit. This can be somewhat mitigated if the collector also handles allocation, since then it could potentially use unused bits in the allocation data structures. Or, this "hidden memory" can be eliminated by using a Tagged pointer, trading the memory cost for CPU time. However, the mark and sweep is the only strategy that readily cooperates with external allocators in the first place. A mark and don't sweep garbage collector, like the mark and sweep, keeps a bit with each object to record if it is white or black; the grey set is kept as a separate list or using another bit. There are two key differences here. First, black and white mean different things than they do in the mark and sweep collector. In a "mark and don't sweep" collector, all reachable objects are always black. An object is marked black at the time it is allocated, and it will stay black even if it becomes unreachable. A white object is unused memory and may be allocated. Second, the interpretation of the black/white bit can change. Initially, the black/white bit may have the sense of (0=white, 1=black). If an allocation operation ever fails to find any available (white) memory, that means all objects are marked used (black). The sense of the black/white bit is then inverted (for example, 0=black, 1=white). Everything becomes white. This momentarily breaks the invariant that reachable objects are black, but a full marking phase follows immediately, to mark them black again. Once this is done, all unreachable memory is white. No "sweep" phase is necessary. The mark and don't sweep strategy requires cooperation between the allocator and collector, but is incredibly space efficient since it only requires one bit per allocated pointer (which most allocation algorithms require anyway). However, this upside is somewhat mitigated, since most of the time large portions of memory are wrongfully marked black (used), making it hard to give resources back to the system (for use by other allocators, threads, or processes) in times of low memory usage. The mark and don't sweep strategy can therefore be seen as a compromise between the upsides and downsides of the mark and sweep and the stop and copy strategies.

Ұрпақ GC (ефемерлік GC)

Көптеген бағдарламаларда соңғы уақытта жасалған нысандар тез арада қолжетімсіз нысандар болып табылатыны эмпирикалық тұрғыдан байқалады (мұны балалар өлімі немесе ұрпақ гипотезасы деп атайды). Ұрпақтық жинағыш (эфемеральды жинағыш деп те аталады) нысандарды ұрпақтарға бөледі және көптеген циклдарда тек ұрпақтардың бір бөлігіндегі нысандарды бастапқы ақ (құрылысқа жіберілген) жиынтығына қосады. Бұдан әрі, орындалу уақыты жүйесі сілтемелердің құрылуын және жаңартылуын бақылап, сілтемелердің ұрпақтар арасында қалай өтетіні туралы ақпаратты сақтайды. Қоқыс жинағыш жұмыс істегенде, бұл ақпаратты пайдаланып, бастапқы ақ жиынтықтағы кейбір нысандарға толық сілтеме ағашын араламай-ақ қолжетімсіз екенін дәлелдей алады. Егер ұрпақ гипотезасы дұрыс болса, бұл жинау циклдарын едәуір жылдамдатып, қолжетімсіз нысандардың көп бөлігін қайтаруға мүмкіндік береді. Бұл тұжырымды іске асыру үшін көптеген ұрпақтық жинағыштар әртүрлі жастағы нысандар үшін бөлек жад аймақтарын пайдаланады. Аймақ толғанда, ондағы нысандар ізделіп, ескі буынның сілтемелері түбір ретінде қолданылады. Бұл әдетте ұрпақтағы көптеген нысандардың жиналуына (гипотеза бойынша) әкеледі, осылайша жаңа нысандарды бөлу үшін оны бос қалдырады. Егер жинау көп нысандарды жинамаса (мысалы, бағдарлама сақтап қалғысы келетін көптеген жаңа нысандарды есептеген болса, гипотеза орындалмайды), ескі жад аймақтарынан сілтеме жасалған сақталған нысандардың бір бөлігі немесе барлығы келесі жоғары аймаққа жылжытылады, содан кейін бүкіл аймақ жаңа нысандармен жаңартылады. Бұл техника өте жылдам инкременттік қоқыс жинауға мүмкіндік береді, себебі әдетте бір уақытта тек бір аймақтың қоқысын жинау жеткілікті. Унгардың классикалық ұрпақтық жинағышы екі ұрпақтан тұрады. Ол ең жас ұрпақты "жаңа кеңістік" деп аталатын үлкен "Едемге" бөледі, онда жаңа нысандар жасалады, және екі кіші "аман қалған кеңістікке" – өткен аман қалған кеңістікке және болашақ аман қалған кеңістікке. Жаңа кеңістіктегі нысандарға сілтеме жасай алатын ескі буынның нысандары "есте сақталған жиынтықта" сақталады. Әр жинау кезінде жаңа кеңістіктегі нысандар есте сақталған жиынтықтағы түбірлерден ізделіп, болашақ аман қалған кеңістікке көшіріледі. Егер болашақ аман қалған кеңістік толса, сыймайтын нысандар ескі кеңістікке жылжытылады, бұл процесс "жасақтану" деп аталады. Жинау аяқталғанда, кейбір нысандар болашақ аман қалған кеңістікте болады, ал Едем және өткен аман қалған кеңістік бос болады. Содан кейін болашақ аман қалған кеңістік пен өткен аман қалған кеңістік алмастырылады және бағдарлама жалғасады, Едемде нысандарды бөледі. Унгардың бастапқы жүйесінде Едем әр аман қалған кеңістіктен 5 есе үлкен. Ұрпақтық қоқыс жинау – эвристикалық тәсіл, сондықтан кейбір қолжетімсіз нысандар әр циклда қайтарылмауы мүмкін. Сондықтан кейде барлық бос орынды қайтару үшін толық белгілеу және жинау немесе көшіру операциясын жүргізу қажет болуы мүмкін. Шындығында, қазіргі заманғы бағдарламалау тілдерінің (Java және .NET Framework сияқты) орындалу уақыты жүйелері әдетте бұрын сипатталған әртүрлі стратегиялардың араласуын пайдаланады; мысалы, жинау циклдарының көпшілігі бірнеше ұрпаққа ғана қарауы мүмкін, ал кейде белгілеу және жинау жүргізіледі, тіпті сирек жағдайда фрагментациямен күресу үшін толық көшіру жасалады. "Кіші цикл" және "үлкен цикл" терминдері кейде жинағыштың агрессивтілігінің осы әртүрлі деңгейлерін сипаттау үшін қолданылады.

It has been empirically observed that in many programs, the most recently created objects are also those most likely to become unreachable quickly (known as infant mortality or the generational hypothesis). A generational GC (also known as ephemeral GC) divides objects into generations and, on most cycles, will place only the objects of a subset of generations into the initial white (condemned) set. Furthermore, the runtime system maintains knowledge of when references cross generations by observing the creation and overwriting of references. When the garbage collector runs, it may be able to use this knowledge to prove that some objects in the initial white set are unreachable without having to traverse the entire reference tree. If the generational hypothesis holds, this results in much faster collection cycles while still reclaiming most unreachable objects. In order to implement this concept, many generational garbage collectors use separate memory regions for different ages of objects. When a region becomes full, the objects in it are traced, using the references from the older generation(s) as roots. This usually results in most objects in the generation being collected (by the hypothesis), leaving it to be used to allocate new objects. When a collection doesn't collect many objects (the hypothesis doesn't hold, for example because the program has computed a large collection of new objects it does want to retain), some or all of the surviving objects that are referenced from older memory regions are promoted to the next highest region, and the entire region can then be overwritten with fresh objects. This technique permits very fast incremental garbage collection, since the garbage collection of only one region at a time is all that is typically required. Ungar's classic generation scavenger has two generations. It divides the youngest generation, called "new space", into a large "eden" in which new objects are created and two smaller "survivor spaces", past survivor space and future survivor space. The objects in the older generation that may reference objects in new space are kept in a "remembered set". On each scavenge, the objects in new space are traced from the roots in the remembered set and copied to future survivor space. If future survivor space fills up, the objects that do not fit are promoted to old space, a process called "tenuring". At the end of the scavenge, some objects reside in future survivor space, and eden and past survivor space are empty. Then future survivor space and past survivor space are exchanged and the program continues, allocating objects in eden. In Ungar's original system, eden is 5 times larger than each survivor space. Generational garbage collection is a heuristic approach, and some unreachable objects may not be reclaimed on each cycle. It may therefore occasionally be necessary to perform a full mark and sweep or copying garbage collection to reclaim all available space. In fact, runtime systems for modern programming languages (such as Java and the NET Framework) usually use some hybrid of the various strategies that have been described thus far; for example, most collection cycles might look only at a few generations, while occasionally a mark and sweep is performed, and even more rarely a full copying is performed to combat fragmentation. The terms "minor cycle" and "major cycle" are sometimes used to describe these different levels of collector aggression.

Stop-the-world және қосымша және бір мезгілде

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

Нақты және консервативті және ішкі сілтемелер

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

Детерминизм

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

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

Қоқыс жинау әдетте детерминистік емес болғанымен, оны нақты уақыт жүйелерінде қолдану мүмкін. Нақты уақыттағы қоқыс жинаушы ең нашар жағдайда да белгілі бір сандағы есептеу ресурстарын мутатор жіптеріне (thread) бөлуге кепілдік беруі керек. Нақты уақыт қоқыс жинаушыға қойылатын шектеулер көбінесе жұмысқа немесе уақытқа негізделген. Уақытқа негізделген шектеу мынадай болуы мүмкін: T ұзақтығындағы әрбір уақыт терезесінде мутатор жіптері кем дегенде Tm уақыты бойы жұмыс істеуі тиіс. Жұмысқа негізделген талдау үшін, MMU (минималды мутаторды пайдалану) әдетте қоқыс жинау алгоритмі үшін нақты уақыт шектеуі ретінде қолданылады. JVM үшін қатты нақты уақыт қоқыс жинаудың алғашқы іске асырылымдарының бірі Метроном алгоритміне негізделген, оның коммерциялық нұсқасы IBM WebSphere Real Time құрамында қолжетімді. Тағы бір қатты нақты уақыт қоқыс жинау алгоритмі – Staccato, ол IBM-нің J9 JVM-де бар, сонымен қатар үлкен көппроцессорлық архитектураларға масштабталу мүмкіндігін ұсынады және Metronome мен басқа алгоритмдерге қарағанда түрлі артықшылықтар береді, олар керісінше арнайы аппаратты талап етеді. Қазіргі заманғы көп ядролы архитектураларда нақты уақыт қоқыс жинаудың маңызды міндеті – бұл бұғаттамайтын (non-blocking) параллель қоқыс жинауды жобалау, яғни бір мезгілде жұмыс істейтін жіптердің бір-бірін тоқтатып, болжауға келмейтін кешігулер тудырмау. Бұғаттамайтын нақты уақытты параллель қоқыс жинауға мүмкіндік беретін алгоритмдерді зерттеу Pizlo және авторлар тобының Microsoft Research-те жарияланған мақаласында келтірілген.