Структуры данных и алгоритмы (1021739), страница 92
Текст из файла (страница 92)
12.2) указателем на новую ячейку,которая содержит атом I и нуль-указатель. Эта ячейка будет изъята из вершины списка свободного пространства. Возможно также, что время от времени указатели будут изменяться таким образом, что переменные программы станут освобождать занятые ими ячейки, как это случилось, например, с ячейками, содержащими g и А, нарис. 12.3. Например, ячейка, содержащая с, может в какой-то момент указывать наячейку, содержащую g. Или еще один пример: значение переменной В может в какой-то момент измениться, что приведет (если не изменится что-либо еще) к освобождению ячейки, на которую сейчас на рис. 12.2 указывает В, а также ячейки, со12.2.
УПРАВЛЕНИЕ БЛОКАМИ ОДИНАКОВОГО РАЗМЕРА343держащей d и е (но не ячейки, содержащей с, поскольку она по-прежнему будет доступна из А). Ячейки, на которые невозможно перейти ни из одной переменной и которые отсутствуют в списке свободного пространства, называются недоступными.Когда ячейки освобождаются и, следовательно, уже не требуются программе, было бы неплохо, если бы они каким-то образом возвращались в список свободного пространства и могли после этого использоваться повторно. Если такие ячейки не будут"утилизироваться", рано или поздно возникнет ситуация, когда программа не использует ни одной ячейки и, тем не менее, ей требуется очередная ячейка из свободного пространства памяти, в то время как список свободного дространства пуст.Именно в этот момент системе потребуется время на выполнение "сборки мусора".Этап чистки памяти выполняется "неявным" образом в том смысле, что мы не выдавали никакого специального запроса на получение дополнительных ячеек памяти.Контрольные счетчикиВесьма привлекательным подходом к выявлению недоступных ячеек являетсявключение в каждую ячейку так называемого контрольного счетчика, или счетчика ссылок (reference count), т.е.
целочисленного поля, значение которого равняетсяколичеству указателей на соответствующую ячейку. Работу такого счетчика обеспечить несложно. С момента создания указателя на какую-либо ячейку значение контрольного счетчика для этой ячейки увеличивается на единицу. Когда переназначается ненулевой указатель, значение контрольного счетчика для указываемой ячейкиуменьшается на единицу. Если значение контрольного счетчика становится равнымнулю, соответствующая ячейка оказывается невостребованной и ее можно вернуть всписок свободного пространства.К сожалению, контрольные счетчики иногда не срабатывают.
Ячейки с g и h нарис. 12.2 являются недоступными ячейками, образующими цикл. Значения их контрольных счетчиков равны 1, поэтому нельзя вернуть эти ячейки в список свободногопространства. Разумеется, есть способы обнаружения циклов недоступных ячеек, но эффективность таких способов невелика. Контрольные счетчики удобно использовать вструктурах, в которых невозможно появление циклов указателей.
Примером подобнойструктуры является совокупность переменных, указывающих на блоки, содержащиеданные (см. рис. 12.1). В этом случае можно выполнять явную чистку памяти. Для этогодостаточно просто "подобрать" блок, когда значение его контрольного счетчика становится равным нулю. Однако когда структуры данных допускают появление циклов указателей, метод контрольных счетчиков оказывается неэффективным — как с точки зренияпространства, требующегося для его реализации, так и с точки зрения времени, затрачиваемого на решение проблемы недоступных ячеек. Более эффективным в этом случае оказывается другой метод, который мы обсудим в следующем разделе.12.3.
Алгоритмы чистки памяти для блоков одинаковогоразмераРассмотрим алгоритм, позволяющий определить, к каким ячейкам, показаннымна рис. 12.2, возможен доступ из переменных программы. Точную постановку задачиможно выполнить, определив тип ячейки, который в языке Pascal будет представленопределенным типом записи. Четыре варианта, которые мы обозначим РР, РА, АР иАА, определяются тем, какие из двух полей данных являются указателями, а какие — атомами (Р обозначает поле указателя (от pointer — указатель), А — полеатома).
Например, РА означает, что левое поле является указателем, а правое поле —атомом. Дополнительное булево поле в ячейках, называемое mark (метка), показывает, является ли данная ячейка свободной, т.е. установив при "сборке мусора" дляполя mark значение true, мы помечаем соответствующую ячейку как доступную дляпоследующего использования. Определения типов данных показаны листинге 12.1.344ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮЛистинг 12.1 .Объявления типов ячеекtypeatomtype = {один из подходящих типов данных для атомов,желательно того же размера, что и указатели }patterns = (РР,РА.АР.АА) ;celltype = recordmark: boolean;case pattern: patterns ofPP: (left: tcelltype; right: Tcelltype);PA: (left: Tcelltype; right: atomtype);AP: (left: atomtype; right: Tcelltype);AA: (left: atomtype; right: atomtype);end;Предполагаем, что имеется массив ячеек, занимающий большую часть памяти,и определенная совокупность переменных, которые представляют собой указателина ячейки. С целью упрощения также предполагаем, что есть только одна переменная, называемая source (исходная), которая указывает на ячейку (хотя обобще1ние на случай многих переменных не представляет особой трудности).
Таким образом, объявляемvarsource: Tcelltype;шелюгу: array [1..memorysize] of celltype;Чтобы пометить ячейки, доступные переменной source, сначала отменяем пометкувсех ячеек (независимо от их доступности или недоступности), просматривая массивmemory (память) и устанавливая для поля mark значение false. Затем выполняем поиск в глубину по дереву ячеек, исходя из ячейки source и помечая все посещаемыеячейки. Посещенные ячейки — именно те, которые доступны из программы и, следовательно, используются программой. Затем просматриваем массив memory и добавляем в список свободного пространства все непомеченные ячейки. В листинге 12.2представлена процедура dfs, выполняющая поиск в глубину; вызов dfs осуществляется процедурой collect (выбор), которая отменяет пометку всех ячеек, а затем маркирует доступные ячейки, вызывая dfs.
Мы не показываем программу, создающуюсвязанный список свободного пространства, из-за особенностей языка Pascal. Например, несмотря на то что можно было бы связать свободные ячейки с помощью либовсех левых, либо всех правых полей ячеек, поскольку предполагается, что указателии атомы имеют одинаковый размер, но мы не имеем права заменять атомы на указатели в ячейках типа АА.Листинг 12.2. Алгоритм маркировки доступных ячеек(1) procedure dfs ( currentcell: Tcelltype );{ Если текущая ячейка помечена, не делать ничего.В противном случае она помечается и вызывается dfsдля всех ячеек, на которые указывает текущая ячейка }begin(2)with currentcel.zT do(3)if mark = false then begin(4)mark := true;1В каждом языке программирования должен быть предусмотрен метод представления текущей совокупности переменных.
Для этого подходит любой из методов, обсуждавшихся вглавах 4 и 5. Например, в большинстве реализаций для хранения таких переменных используется хеш-таблица.12.3. АЛГОРИТМЫ ЧИСТКИ ПАМЯТИ ДЛЯ БЛОКОВ ОДИНАКОВОГО РАЗМЕРА 345(5)(6)(7)(8)(9)(10)if (pattern = PP) or (pattern = PA) thenif left <> nil thendfs(left);if (pattern - PP) or (pattern = AP) thenif right <> nil thendfs(right)endend; { dfs }(11)procedure collect;var(12)(13)(14)(15)i: integer;beginfor i := 1 to memorysize do{ отмена маркировки всех ячеек }memory[i] .mark-.= false;dfs(source); { пометить доступные ячейки }{в этом месте должен быть код для сбора доступных ячеек)end; { collect }Сборка на местеАлгоритм, представленный в листинге 12.2, страдает небольшим изъяном.
В вычислительной среде с ограниченным объемом памяти у нас может не оказаться достаточно места для хранения стека, требующегося для рекурсивных вызовов dfs. Какуже указывалось в разделе 2.6, каждый раз, когда dfs вызывает сама себя, Pascal(или любой другой язык, допускающий рекурсию) создает для данного вызова dfsтак называемую активационную запись. Вообще говоря, в такой активационной записи предусмотрено место для параметров и переменных, локальных по отношениюк процедуре, причем для каждого вызова требуется свой собственный экземпляр активационной записи.
Кроме того, в каждой активационной записи нужно указыватьадрес возврата — место программы, в которое необходимо передать управление после завершения рекурсивного вызова процедуры.При вызове процедуры dfs требуется лишь место для параметра и адреса возврата. Однако если бы вся память была связана в цепочку, исходящую из ячейки source(и, следовательно, количество активных вызовов dfs в какой-то момент времени стало равным длине этой цепочки), для стека активационных записей могло бы потребоваться значительно больше пространства, чем имеется в памяти. И если бы свободного пространства не оказалось, было бы невозможно выполнять маркировку освободившихся ячеек.К счастью, разработан замечательный алгоритм, известный под названием алгоритма Дойча — Шорра — Уэйта (Deutsch — Schorr — Waite), который выполняетмаркировку на месте.
Читатель должен проверить сам, что последовательность ячеек, на которых был выполнен (но еще не завершен) вызов dfs, действительно образует путь от source до ячейки, на которой был сделан текущий вызов dfs. Поэтомуможно воспользоваться нерекурсивной версией процедуры dfs, а вместо стека активационных записей, предназначенного для отслеживания пути ячеек от source доячейки, анализируемой в данный момент, можно использовать поля указателейвдоль этого пути, которые и будут формировать этот путь. Таким образом, каждаяячейка на этом пути, за исключением последней, содержит или в поле left (влево),или в поле right (вправо) указатель на ее предшественника — ячейку, расположенную ближе к ячейке source. Мы опишем алгоритм Дойча — Шорра — Уэйта, использующий еще одно однобитовое поле, которое называется back (назад).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
