Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Сбор мусора




Счетчик ссылок

Обслуживание свободного пространства

Для списков общего вида удаляемый из одного списка узел не может быть просто отправлен в стек свободного пространства, так как он может входить более чем в один список. Для обслуживания свободного пространства могут быть использованы методы счетчиков ссылок и сбор мусора.

В методе счетчиков ссылок каждый узел содержит поле счетчика int count, равное числу узлов, ссылающихся на данный. При удалении узла из списка поле count уменьшается на единицу. Когда счетчик окажется равным нулю, узел можно отправить в свободное пространство. Метод не работает для рекурсивных списков, в которых узел может прямо или косвенно ссылаться на самого себя. Такой узел никогда не будет освобожден.

При использовании метода "сбор мусора" программы беззаботно рабо­тают до тех пор, пока не будет исчерпано свободное простран­ство. Брошенные и никем неиспользуемые узлы называют мусором. Когда свободное пространство исчерпано, вызывается мусорщик, целью которого является собрать мусор в стек свободного простран­ства. Каждый узел имеет бит маркировки. Метод работает в три фазы. В первой фазе обходится вся память, занятая списками и биты маркировки устанавливаются в "0". Вторая фаза систематически обходит все узлы списков и устанавливает в них бит маркировки в "1". Таким образом, маркированными нулём остаются только узлы, относящиеся к мусору. Третья фаза вновь обходит всю память и собирает узлы, помеченные нулем в стек свободного пространства.

Время работы мусорщика выражается формулой

, где

C1, C2 – константы, N – число всех узлов в списках, M – число всех узлов в памяти, отведенной под списки.

Таким образом, M-N – количество узлов, возвращаемых мусорщиком в стек свободного пространства. Время, расходуемое на возврат одного узла, составляет

Обозначим коэффициент загрузки памяти, тогда время, требуемое на возврат одного узла, составит

 
 

Как видно из последней формулы, недостатком метода является то, что он медленно работает, когда загрузка памяти велика. В таких случаях число узлов, возвращаемых в стек свободного простран­ства не окупает затраченных усилий. Те программы, которым не хватает памяти, впустую расходуют массу времени, многократно и бесплодно вызывая мусорщика перед тем, как окончательно исчерпать память. Метод сбора мусора малопригоден для работы в реальном времени, так как он вызывается в непредвиденные моменты времени и может долго работать.

Контрольные вопросы

1) Чем отличается связанное распределение памяти под данные от последовательного?

2) Какие преимущества даёт представление строки линейным списком по сравнению с представлением её как массива символов?

3) Какие операции могут быть выполнены над линейным списком?

4) Что такое голова списка и зачем она нужна?

5) Чем отличается кольцевой список от обычного и какие дополнительные возможности он имеет?

6) Какие дополнительные возможности предоставляет двусвязный список по сравнению с односвязным?

7) В каких случаях целесообразно применять ортогональные списки вместо многомерных массивов?

8) Чем отличается список общего вида от обычного линейного списка?

9) Дайте определение понятия "топологическая сортировка"

10) Что такое стек свободного пространства?

11) Каковы недостатки метода счетчика ссылок при обслуживании свободного пространства для списочных структур?

12) Аналогичный вопрос для метода "сбора мусора"




Поделиться с друзьями:


Дата добавления: 2014-12-08; Просмотров: 479; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.