Сбор мусора

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

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

, где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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