Непосредственно перед сборкой мусора

the-cars the-cdrs

new-cars

new-cdrs

смесь полезных данных и мусора

рабочая память

свободная

свободная память

свободная память

new-cars new-cdrs

сразу после сборки мусора

освобожденная память

новая

свободная

память

the-cars the-cdrs

новая

рабочая

память

Рис. 5.15: Перестройка памяти в процессе сборки мусора.

мещены и просканированы. В этот момент указатель scan догонит указатель free, и процесс завершится.

Алгоритм остановки с копированием можно описать как последовательность команд регистровой машины. Базовый шаг, состоящий в перемещении объекта, проделывается подпрограммой relocate-old-result-in-new. Эта подпрограмма принимает свой аргумент, указатель на объект, подлежащий перемещению, в регистре old. Она перемещает данный объект (по пути обновляя free), помещает указатель на перемещенный объект в регистр new, и возвращается, переходя на точку входа, хранимую в регистре relocate-continue. В начале процесса сборки мы с помощью этой подпрограммы перемещаем указатель root, после инициализации free и scan. Когда root перемещен, мы записываем новый указатель в регистр root и входим в основной цикл сборщика мусора.

begin-garbage-collection (assign free (const 0)) (assign scan (const 0)) (assign old (reg root))

(assign relocate-continue (label reassign-root)) (goto (label relocate-old-result-in-new)) reassign-root

(assign root (reg new)) (goto (label gc-loop))

В основном цикле сборщика мусора нам нужно определить, есть ли еще подлежащие сканированию объекты. Для этого мы проверяем, совпадает ли указатель scan с указателем free. Если указатели равны, значит, все доступные объекты перемещены, и мы переходим на gc-flip. По этому адресу расположены восстановительные действия, после которых можно продолжить прерванные вычисления. Если же еще есть пары, которые требуется просканировать, мы зовем подпрограмму перемещения для car следующей пары (при вызове мы помещаем указатель car в регистр old). Регистр relocate-continue устанавливается таким образом, чтобы при возврате мы могли обновить указатель car.

gc-loop

(test (op =) (reg scan) (reg free)) (branch (label gc-flip))

(assign old (op vector-ref) (reg new-cars) (reg scan)) (assign relocate-continue (label update-car)) (goto (label relocate-old-result-in-new))

На метке update-car мы изменяем указатель car сканируемой пары. После этого мы перемещаем ее cdr, а затем возвращаемся на метку update-cdr. Наконец, когда cdr перемещен и обновлен, сканирование пары закончено, и мы продолжаем главный цикл.

update-car (perform

(op vector-set!) (reg new-cars) (reg scan) (reg new)) (assign old (op vector-ref) (reg new-cdrs) (reg scan)) (assign relocate-continue (label update-cdr)) (goto (label relocate-old-result-in-new))

update-cdr (perform

(op vector-set!) (reg new-cdrs) (reg scan) (reg new)) (assign scan (op +) (reg scan) (const 1)) (goto (label gc-loop))

Подпрограмма relocate-old-result-in-new перемещает объекты следующим образом: если перемещаемый объект (на него указывает old) не является парой, мы возвращаем указатель на него неизменным (в регистре new). (К примеру, мы можем сканировать пару, в car которой находится число 4. Если значение в car представляется как n4, как описано в разделе 5.3.1, то нам нужно, чтобы «перемещенный» car по-прежнему равнялся n4.) В противном случае требуется произвести перемещение. Если позиция car перемещаемой пары содержит метку разбитого сердца, значит, сама пара уже перенесена, и нам остается только взять перенаправляющий адрес (из позиции cdr разбитого сердца) и вернуть его в регистре new. Если же регистр old указывает на еще пе перенесенную пару, то мы ее переносим в первую пустую ячейку новой памяти (на нее указывает free), а затем строим разбитое сердце, записывая в старой ячейке метку разбитого сердца и перенаправляющий адрес. Процедура relocate-old-result-in-new хранит car или cdr объекта, на который указывает old, в регистре oldcr.18

relocate-old-result-in-new

(test (op pointer-to-pair?) (reg old))

(branch (label pair))

(assign new (reg old))

(goto (reg relocate-continue)) pair

(assign oldcr (op vector-ref) (reg the-cars) (reg old)) (test (op broken-heart?) (reg oldcr)) (branch (label already-moved))

(assign new (reg free)) ; новов мвсто для пары

;; Обновить указатвль free. (assign free (op +) (reg free) (const 1))

;; Скопировать car и cdr в новую память. (perform (op vector-set!)

(reg new-cars) (reg new) (reg oldcr)) (assign oldcr (op vector-ref) (reg the-cdrs) (reg old)) (perform (op vector-set!)

(reg new-cdrs) (reg new) (reg oldcr)) ;; Построить разбитов сврдцв. (perform (op vector-set!)

(reg the-cars) (reg old) (const broken-heart))

(perform

(op vector-set!) (reg the-cdrs) (reg old) (reg new)) (goto (reg relocate-continue))

18Сборщик мусора использует низкоуровневый предикат pointer-to-pair? вместо обыкновенного pair?, поскольку в настоящей системе могут иметься различные объекты, которые с точки зрения сборщика будут являться парами. Например, в системе, которая соответствует стандарту Scheme IEEE, объект-процедура может реализовываться особого рода «парой», которая не удовлетворяет предикату pair?. В нашем имитаторе можно реализовать pointer-to-pair? как pair?.