Проблема мусора.

Он обычно появляется при реал-ции защиты от вис ссылок(или при ош-ках в пр-мме). Мусор – это эл-ты пам, к-е числятся занятыми, но недоступны пр-мме для исп-ния (к-рой принадл куча). Сущ спец алг-мы сбора мусора. Они бывают быстрыми и бывают экономными. В любом сл-е эти алг-мы вып-ся в 2 шага: 1)маркировка своб эл-тов, к-е помечаются как мусор. Проблема их распознать; 2)Утилизация эл-тов, помеченных как мусор.

Общие подходы к разработке алг-мов сбора мусора.

1 этап – маркировки вып-ся путем обхода по ссылкам активных, т е доступных для использ-я эл-тов кучи; 2 этап – утилизации состоит в последоват-м обходе всех эл-тов кучи и занесения эл-тов, помеченных как мусор, в список своб эл-тов. Для осущ-я маркировки треб-ся сл усл-я: 1)Сист должна иметь возм-ть выявить все ссылки на эл-ты кучи, записанные вне кучи (выявить внеш ссылки).

Для внеш ссылок должны быть опр-ны спец типы данных – работа с др типами запрещена; 2)Сист должна иметь возм-ть выявить все указ-ли на активные эл-ты кучи, к-е нах-ся в самих эл-тах кучи. Это значит, что либо все эл-ты кучи должны иметь одинак структуру, один, известный сист общий формат (чтобы все указ-ли были на одних и тех же местах) – нельзя опр-ть типы данных польз-ля. Либо для эл-тов кучи должны быть введены заголовки, опис-щие их формат. Как мин, это опр-е типов эл-тов, размещенных в куче. В этом сл-е кажд раз о указ-лю на эл-т кучи сист должна получать не только его адрес, но и его формат (где нах-ся указ-ли в этом эл-те); 3)Зарет на вып-е арифм оп-ций над указ-ми во вр вып-я пр-ммы; 4)В кажд эл-те кучи должно быть опр-но спец поле, явл-ся признаком того, активен эл-т, или превратился в мусор. Это поле недоступно в пр-мме. Обычно это поле наз бит присутствия, практ-ки резерв-ся байт. Алгоритмы: 1. Основан на исп-нии стека – затратный. Для работы алг-ма резерв-ся стек, в к-рый сист (сборщик мусора) в процессе обхода активных эл-тов кучи будет помещать ссылки на др активные эл-ты кучи, выявленные при просмотре. Нач сост-е стека – при иниц-ции помещ-ся 1-я внеш ссылка. {иниц-ция} поместить в стек 1-ю внеш ссылку; Пока есть непустые внеш ссылки на активные эл-ты кучи выполнить помещаем в стек непустую ссылку; пока стек не пуст выпонить выбрать ссылку из вершины стека; выбрать эл-т кучи поэтой ссылке; перебрать все поля, содержащие указ-ли, и записать все непустые ссылки на нах-ся в них активные эл-ты кучи в стек.{конец алг-ма} Для реал-ции маркировки по этой схеме нужно исп-ть бит сбора мусора. При иниц-ции алг-ма в битах сбора мусора в эл-тах кучи ставится пометка, что это мусор. Во вр работы алг-ма при выборе активных эл-тов кучи должно измен-ся зн-е бита сбора мусора – эл-т помеч-ся как активный (хотя бы по одной ссылке выбран – значит не мусор). Остается 2 проблемы – нал-е циклич ссылок и возм-ть неск-ких ссылок на один эл-т кучи. При выборе активного эл-та, до того, как начать проверку его полей, нужно проверить, не промаркирован ли он уже как активный (если да, то этот эл-т не выбирается). 2. Алг-м Шорра-Вейта. Для работы треб-ся хранить всего 2 ссылки: на тек, активный эл-т (обраб-емый) и на предыд (обраб-нный). Но зато в самих эл-тах кучи должны быть доп поля – есть еще поле, в к-ром хран-ся инф-я о том, какая ссылка в этом эл-те уже обработана. Если указ-ли, содерж-ся в эл-те кучи, предст собой массив, то такая инф-я – номер эл-та массива (под DOS алг-мов сбора мусора в си и паскале нет). Обход в этом алг-ме основан на обращении ссылок – при переходе по ссылке на эл-т, на к-рый она указ-ет, ссылка переворачивается. На ее место запис-ся ссылка на эл-т, из кот-го мы попали в данный эл-т (чтобы можно было сделать возвраты, при к-рых ссылки восст-ся.

C-активный, L-предыд. При иниц-ции С-активный, L-пусто. Ук-ль L будет исп-ся при при возвратах. Как только при возвратах он станет пустым, значит эл-т нах-ся на внеш ур иерархии – на него есть ссылки только внешние – можно выбирать след внеш ссылку. Выбранные в активном эл-те ссылки никуда не запис-ся – стека нет. Выбирается только одна ссылка и по этой ссылке вып-ся обход эл-тов вглубь по всей цепочке. Для перебрасывания ссылок исп-ся промежут указ-ль.