Алгоритм сборки мусора|Алгоритм GC Mark-Sweep

Эта статья является примечаниями к прочтению «Алгоритм и реализация сборки мусора».

Что такое алгоритм маркировки GC (Mark Sweep GC)

Алгоритм маркировки GC состоит из标记阶段и清除阶段составляют. На этапе маркировки все активные объекты будут отмечены, а затем объекты не отмечены на этапе очистки, то есть非活动Переработка объекта.

名词解释：

В мире ГК对象Относится к набору данных, используемых приложением. является базовой единицей GC. Обычно он состоит из заголовка и поля.

活动对象:Объект, на который может ссылаться эталонная программа, называется активным объектом. (объекты, которые могут быть прямо или косвенно получены из пространства глобальных переменных)

非活动对象:Объекты, на которые программа не может сослаться, называются неактивными объектами. (это цель очищается)

Псевдокод алгоритма очистки выглядит следующим образом:

func mark_sweep(){
    mark_phase()   // 标记阶段
    sweep_phase()  // 清除阶段
}

Маркерная фаза

Фаза маркировки — это процесс обхода объектов и их маркировки.

Псевдокод фазы маркировки выглядит следующим образом:

func mark_phase(){
    for (r : $roots)  // 在标记阶段，会给所有的活动对象打上标记
        mark(*r)
}

func mark(){
    if (obj.mark == False)
        obj.mark = True            // 先标记找出的活动对象
        for (child: children(obj)) // 然后递归的标记通过指针数组能访问到的对象
            mark(*child)
}

здесь$rootЭто начальная точка объекта-указателя, и все активные объекты можно обойти через $root.

На следующем рисунке показано состояние кучи в памяти до и после маркировки

этап очистки

В фазе очистки сборщик перебирает весь стек, нет пометки восстановления объектов (мусора), чтобы его можно было использовать снова.

Псевдокодовая реализация функцииswap_phase() выглядит следующим образом:

func sweep_phase(){
    sweeping = $heap_start            // 首先将堆的首地址赋值给 sweeping
    while(sweeping < $head_end){
        if(sweeping.mark == TRUE)
            // 如果是标记状态就设为 FALSE，如果是活动对象，还会在标记阶段被标记为 TRUE
            sweeping.mark == FALSE    
        else:
            sweeping.next = $free_list   // 将非活动对象 拼接到 $free_list 头部位置
            $free_list = sweeping
        sweeping += sweeping.size
    }     
}

sizeПоле относится к полю, в котором хранится размер объекта, и определяется заранее в заголовке объекта.

nextПоля используются только при создании списков свободных мест и выборке блоков из списков свободных мест.

分块(chunk)Имеется в виду заранее подготовленное пространство для использования предметов.

Маршрут генерации блока в памяти:分块-->活动对象-->垃圾—>分块-->...

На этапе очистки мы утилизируем бездействие. Переработка объекта заключается в том, чтобы рассматривать объект как блок и соединять его с空闲链表односвязный список. После выделения места вам нужно только пройти по свободному связанному списку, чтобы найти блок.

На следующем изображении показано состояние кучи после завершения фазы очистки:

распространять

Цель сбора мусора состоит в том, чтобы иметь возможность перераспределить

Когда программа подает заявку на блок, как можно выделить для программы блок подходящего размера?

Псевдокод распределения выглядит следующим образом:

func new_obj(size){  // size 是需要的分块大小
    chunk = pickup_chunk(size, $free_list)  // 遍历 $free_list 寻找大于等于 size 的分块
    if(chunk != NULL)  
        return chunk
    else
        allocation_fail()   // 如果没找到大小合适的分块 提示分配失败
}

pickup_chunk()Функция не только возвращает тот же размер, что и размер блока, но и возвращает размер больше, чем размер блока (в это время он будет разделен на размер размера блока и оставшийся размер после удаление размера блока, а оставшуюся часть вернуть в свободный связанный список).

Существует три стратегии распределенияFirst-fit,Best-fit,Worst-fit

First-fit: если будет найден блок больше или равный размеру, он будет немедленно возвращен

Best-fit: найти блок того же размера, что и size, и вернуться

``Худшее соответствие`: найдите самый большой фрагмент, а затем разделите его на размер и оставшийся размер (этот метод имеет тенденцию генерировать множество маленьких фрагментов).

сливаться

В зависимости от стратегии распределения в процессе выделения появится большое количество маленьких блоков.Если блоки непрерывны, мы можем объединить маленькие блоки в большой блок.合并是在清除阶段完成的, код очистки, включающий стратегию слияния, выглядит следующим образом:

func sweep_phase(){
    sweeping = $heap_start            // 首先将堆的首地址赋值给 sweeping
    while(sweeping < $head_end){
        if(sweeping.mark == TRUE)
            // 如果是标记状态就设为 FALSE，如果是活动对象，还会在标记阶段被标记为 TRUE
            sweeping.mark == FALSE    
        else:
            if(sweeping == $free_list + $free_list.size)  // 堆的地址正好和空闲链表大小相同
                $free_list.size += sweeping.size
            else
                sweeping.next = $free_list   // 将非活动对象 拼接到 $free_list 头部位置
                $free_list = sweeping
        sweeping += sweeping.size
    }     
}

$heap_end = $heap_start + HEAP_SIZE

Так вотsweeping == $free_list + $free_list.sizeЭто можно понять как адрес кучи оформления в самый раз и неработающее звено.

Преимущества недостатки

преимущество

Простота реализации
и保守式 GC 算法совместимый

недостаток

Серьезная фрагментация (как видно из алгоритма распределения, описанного выше, легко генерировать большое количество небольших блоков
Скорость распределения низкая (поскольку свободные блоки реализованы со связанными списками, блоки могут быть непоследовательными, и каждое выделение должно проходить через свободный связанный список, а в крайних случаях необходимо пройти весь связанный список.
и写时复制技术несовместимый

Копирование при записи — это метод оптимизации памяти, используемый во многих операционных системах UNIX. Например, при использовании функции fork() для копирования процесса в системе Linux большая часть пространства памяти не будет скопирована, а будет скопирован только процесс, а данные памяти будут скопированы только тогда, когда содержимое памяти будет скопировано. измененный.

Но если используется алгоритм маркировки-развертки, то память будет установлена标志位, репликация происходит часто, когда не должна.

Несколько бесплатных списков

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

Здесь мы используем метод множественных свободных списков для хранения неактивных объектов. Например: блоки из двух слов образуют свободный список, блоки из трех слов образуют еще один свободный список и так далее. .

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

Сколько бесплатных списков вам нужно создать?

Поскольку программа обычно не претендует на особо большой блок, мы обычно устанавливаем верхний предел размера блока, например 100, и формируется специальный свободный связанный список, если размер больше этого предела. Таким образом, достаточно 101 свободного списка.

растровый маркер

В чистом алгоритме маркировки GC биты, используемые для маркировки, размещаются в заголовке объекта. Алгоритм заключается в обработке объекта вместе с заголовком, но это несовместимо с копированием при записи.

位图标记Метод состоит в том, чтобы собирать и табулировать только флаговые биты каждого объекта, а не управлять объектами вместе. Вместо того, чтобы задавать позицию в заголовке объекта при маркировке, задайте позицию в конкретной таблице.

В битовых тегах важно, чтобы позиции битов в таблице битовых карт точно соответствовали объектам в куче. Обычно слово в куче выделяется битом.

Псевдокодовая реализация функции mark() в растровом маркере выглядит следующим образом:

func mark(obj){
    obj_num = (obj - $heap_start) / WORD_LENGTH  // WORD_LENGTH 是一个常量，表示机器中一个字的位宽
    index = obj_num / WORD_LENGTH
    offset = obj_num % WORD_LENGTH
    
    if ($bitmap_tbl[index] & (1 << offset)) == 0
        $bitmap_tbl[index] |= (1 << offset)
        for (child: children(obj)) // 然后递归的标记通过指针数组能访问到的对象
            mark(*child)
}

Obj_num здесь относится к форме битовой карты спереди. Бит флага Obj в первых нескольких. 8 — это obj_num, например, E.

Индекс частного, полученный путем деления obj_num на WORD_LENGTH, и смещение остатка представляют номер строки и номер столбца таблицы растровых изображений соответственно.

преимущество

Совместимость с технологией копирования при записи
Очистка более эффективна (вам может понадобиться очистить флаг в таблице только тогда, когда вам нужно пройти через форму битового зазора.

отсроченная очистка

Время, затрачиваемое на операцию очистки, пропорционально размеру кучи: чем больше куча, тем дольше выполняется действие пометки и очистки, и тем больше оно влияет на работу программы.

Ленивая развертка — это способ сократить максимальное время паузы программы из-за стоимости операции развертки.

最大暂停时间, максимальное время приостановки выполнения программы из-за выполнения сборщика мусора.

Функция new_obj() в ленивой очистке будет вызываться при выделенииlazy_sweep()Функция для выполнения операции очистки. Если блок может быть выделен с помощью операции очистки, блок возвращается, а если блок не может быть выделен, выполняется операция маркировки. Затем повторяйте этот шаг, пока блок не будет найден илиallocation_fail

Время паузы программы может быть уменьшено методом отложенной очистки, но эффект задержки не сбалансирован. Например, на следующем рисунке показана ситуация, когда куча только что была отмечена:

В это время активные объекты и неактивные объекты распределяются рядом.Если программа начинает очищать активный объект, все найденные объекты являются активными объектами, которые не могут быть очищены, и могут быть пройдены только непрерывно, и время паузы станет дольше.

Наконец, поблагодарите мою девушку за ее поддержку и терпимость, чем ❤️

Вы также можете ввести следующие ключевые слова в официальном аккаунте, чтобы получить исторические статьи:公号&小程序 | 设计模式 | 并发&协程