Парные метки
Рисунок 4.7. Парные метки
Похожим образом присоединяется и сосед, стоящий после него. Единственное отличие состоит в том, что этого соседа все-таки нужно извлекать из списка свободных блоков.
Фактически, парные метки можно рассматривать как способ реализации решения, предложенного нами как одна из идей мозгового штурма: двунаправленного списка, включающего в себя как занятые, так и свободные блоки, и отсортированного по адресу. Дополнительное преимущество приведенного алгоритма состоит в том, что мы можем отслеживать такие ошибки, как многократное освобождение одного блока, запись в память за границей блока и иногда даже обращение к уже освобожденному блоку. Действительно, мы в любой момент можем проверить всю цепочку блоков памяти и убедиться в том, что все свободные блоки стоят в списке, что в нем стоят только свободные блоки, что сами цепочка и список не испорчены и т. д.
