В этом обсуждении будет использоваться код micropython, но, поскольку он такой простой, я надеюсь, что он будет полезен для общего обсуждения mark+sweep
Micropython использует сборку мусора, в частности пометку и очистку; давайте это определим.
Отметить
На этапе отметить gc следует за ссылками на память и буквально отмечает используемые блоки памяти, чтобы указать, что они доступны из набора корневых блоков.
Очистка
После завершения фазы маркировки подметальная машина перебирает всю кучу, и если блок памяти используется, но не отмечен, это означает, что код недоступен для него. поэтому он "освобожден", т.е. помечен как бесплатный. С блоков памяти, отмеченных на этапе mark, эта метка удалена.
Текущая реализация требует атомарного вызова для выполнения сборки мусора, также известного как gc, но мне было интересно, можно ли разделить его на несколько вызовов, а не монолитный/атомарный вызов.
Это помогло бы уменьшить джиттер: вместо одного большого совпадения по времени у вас была бы разбросана куча более мелких вызовов. (Детали реализации «распределения» вызовов gc здесь не обсуждаются... если кто-то не думает, что это дополнит обсуждение.)
Если gc работает «в фоновом режиме» — между байт-кодами или после предопределенных байт-кодов - тогда выделение (или освобождение) в неправильной точке может привести к состоянию гонки и повреждению кучи. Прежде чем мы сможем разделить gc выполнение, мы должны определить возможные условия гонки.
Можно выполнить две операции: выделение и освобождение.
Распределение
Что может произойти, если пользователь выполнит выделение в середине фазы маркировки или развертки?
Давайте посмотрим на конкретный пример кода
>> var1 = SomeAllocation()
Распределение во время маркировки
В приведенном выше примере инструкция выполняется в REPL, поэтому любые добавления в словарь будут вноситься в глобальный словарь, который является записью в GC Roots. Если запись добавляется в глобалы до ее сканирования, ничего "плохого" не происходит: новый блок памяти будет отмечен так, как должен быть.
Проблема в том, что глобальные переменные изменяются после сканирования. В этом случае блок памяти не будет помечен, поэтому на этапе очистки он будет считаться "недоступным" и будет освобожден. . . хотя этого быть не должно.
Распределение во время развертки
Если блок выделяется до того, как подметальная машина пройдет эту точку в памяти, она освободит его, потому что у него нет специальной метки из отметить этап. Если блок выделяется после того, как очиститель прошел указанный блок, ничего плохого не происходит.
Решение
Если gc находится в процессе выполнения, пометьте выделенный блок как помеченный. Единственным недостатком является то, что если вы выделяете в фазе развертки и после того, как подметальная машина проверит вновь выделенный блок, вы закончите gc с блоком, помеченным отметкой. Если пользователь явно не освободит его, вам потребуется пройти дополнительный цикл gc, чтобы освободить его, если он станет недоступным.
Но для этого есть простое решение: если вы выделяете во время фазовой развертки, вы проверяете положение подметальщика: если за ним находится новый-подлежащий-распределению-блок, не помечайте его меткой а в противном случае пометьте его отметкой, потому что очиститель удалил бы отметку. Таким образом, вы не выйдете из gc с блоками, помеченными отметкой.
Освобождение
Что может произойти, если пользователь выполнит выделение в середине фазы маркировки или развертки?
Освобождение во время маркировки
Если блок освобождается до сканирования ссылающегося (родительского) блока, ничего не происходит.
Если блок освобожден и у него есть дочерние элементы, которые уже были отмечены, возникает несоответствие, поскольку блоки должны быть отмечены только в том случае, если они имеют родитель, который также помечен (или родитель имеет GC root). В результате эти недостижимые, но помеченные блоки не будут освобождены до дополнительного gc цикла, потому что, будучи помеченными, эти блоки без родителя, но помеченные, не будут освобождены по фазе. сметать.
Однако я не думаю, что это проблема, потому что это ничем не отличается от случая с монолитным gc. В монолитном gc вам нужно будет завершить текущий gc цикл, затем пользователь вызовет free(ptr), а затем дочерние элементы этого блока будут освобождены в течение следующего gc. Количество времени, в течение которого куча находится в «правильном» состоянии, не изменится.
Освобождение во время очистки
Если блок освобождается до того, как его проверит чистильщик, ничего особенного не происходит. Операция свободно изменяет статус целевого блока с отмечено на свободно, а затем, когда очиститель достигает его, . . . здесь не на что смотреть, просто свободный блок.
Если блок освобожден после его проверки, операция free изменяет статус целевого блока с используется на свободен. .
ВОПРОС
Верен ли мой анализ: можно ли разделить сборку мусора mark+sweep?
